MIT6006 Problem Set 4 Solution

Please write your solutions in the L ATEX and Python templates provided. Aim for concise solutions; convoluted and obtuse descriptions might receive low marks, even when they are correct.
Problem 4-1. [10 points] Binary Tree Practice
(a) [2 points] The Set Binary Tree T below is not height-balanced but does satisfy the binary search tree property, assuming the key of each integer item is itself. Indicate the keys of all nodes that are not height-balanced and compute their skew.

1 T.insert(2)
2 T.delete(49)
3 T.delete(35)
4 T.insert(85)
5 T.delete(84)
(c) [3 points] For each unbalanced node identified in part (a), draw the two trees that result from rotating the node in the original tree left and right (when possible). For each tree drawn, specify whether it is height-balanced, i.e., all nodes satisfy the AVL property.
2 Problem Set 4
Problem 4-2. Heap Practice [10 points]
For each array below, draw it as a complete binary tree and state whether the tree is a max-heap, a min-heap, or neither. If the tree is neither, turn the tree into a min-heap by repeatedly swapping items that are adjacent in the tree. Communicate your swaps by drawing a sequence of trees, marking on each tree the pair that was swapped.
(a) [4, 12, 8, 21, 14, 9, 17]
(b) [701, 253, 24, 229, 17, 22]
(c) [2, 9, 13, 8, 0, 2]
(d) [1, 3, 6, 5, 4, 9, 7]
Problem 4-3. [10 points] Gardening Contest
(a) [5 points] To support inclusion and reduce competition, Wonder-Grow wants to award identical trophies to the top k gardens. Given an unsorted array A of garden pairs and a positive integer k ≤ |A|, describe an O(|A| + k log |A|)-time algorithm to return the registration numbers of k gardens in A with highest scores, breaking ties arbitrarily.
(b) [5 points] Wonder-Grow decides to be more objective and award a trophy to every garden receiving a score strictly greater than a reference score x. Given a max-heap A of garden pairs, describe an O(nx)-time algorithm to return the registration numbers of all gardens with score larger than x, where nx is the number of gardens returned.
Problem Set 4
Problem 4-4. [15 points] Solar Supply
Entrepreneur Bonty Murns owns a set S of n solar farms in the town of Fallmeadow. Each solar farm (si,ci) ∈ S is designated by a unique positive integer address si and a farm capacity ci: a positive integer corresponding to the maximum energy production rate the farm can support. Many buildings in Fallmeadow want power. A building (bj ,dj ) is designated by a unique name string bj and a demand dj : a positive integer corresponding to the building’s energy consumption rate.
initialize(S) Initialize database with a list S = ((s0, c0), . . . , (sn−1, cn−1)) corresponding to n solar farms in O(n) time.
power on(bj ,dj ) Connect a building with name bj and demand dj to any solar farm having available capacity at least dj in O(log n) time (or return that no such solar farm exists).
power off(bj ) Remove power from the building with name bj in O(log n) time.
customers(si) Return the names of all buildings supplied by the farm at address si in O(k) time, where k is the number of building names returned.
Problem 4-5. [15 points] Robot Wrangling
Dr. Squid has built a robotic arm from n+1 rigid bars called links, each connected to the one before it with a rotating joint (n joints in total). Following standard practice in robotics , the orientation of each link is specified locally relative to the orientation of the previous link. In mathematical notation, the change in orientation at a joint can be specified using a 4 × 4 transformation matrix. Let M = (M0,...,Mn−1) be an array of transformation matrices associated with the arm, where matrix Mk is the change in orientation at joint k, between links k and k + 1.
To compute the position of the end effector , Dr. Squid will need the arm’s full transformation: the ordered matrix product of the arm’s transformation matrices, .
Assume Dr. Squid has a function matrix multiply(M1,M2) that returns the matrix product M1 × M2 of any two 4 × 4 transformation matrices in O(1) time. While tinkering with the arm changing one joint at a time, Dr. Squid will need to re-evaluate this matrix product quickly. Describe a database to support the following worst-case operations to accelerate Dr. Squid’s workflow:
initialize(M) Initialize from an initial input configuration M in O(n) time.
update joint(k,M) Replace joint k’s matrix Mk with matrix M in O(log n) time.
full transformation() Return the arm’s current full transformation in O(1) time.

4 Problem Set
Problem 4-6. [40 points] πz2a Optimization
Liza Pover has found a Monominos pizza left over from some big-TEX recruiting event. The pizza is a disc with radius z, having n toppings labeled 0,...,n − 1. Assume z fits in a single machine word, so integer arithmetic on O(1) such integers can be done in O(1) time. Each topping i:
• has integer tastiness ti ∈ R (note, topping tastiness can be negative, e.g., if it’s pineapple ).
Liza wants to pick a point (x0,y0) and make a pair of cuts from that point, one going straight down and one going straight left, and take the resulting slice, i.e., the intersection of the pizza with the two half-planes x ≤ x0 and y ≤ y0 . The tastiness of this slice is the sum of all ti such that xi ≤ x0 and yi ≤ y0 . Liza wants to find a tastiest slice, that is, a slice of maximum tastiness. Assume there exists a slice with positive tastiness.
(a) [2 points] If point (x0, y 0) results in a slice with tastiness t 6= 0, show there exists i, j ∈ {0, 1, . . . , n − 1} such that point (xi, y j ) results in a slice of equal tastiness t (i.e., a tastiest slice exists resulting from a point that is both vertically and horizontally aligned with toppings).
(b) [8 points] To make finding a tastiest slice easier, show how to modify a Set AVL Tree so that:
• it stores key–value items, where each item x contains a value x.val (in addition to its key x.key on which the Set AVL is ordered);
• it supports a new tree-level operation max prefix() which returns in worstcase O(1) time a pair (k∗, prefix(k∗)), where k∗ is any key stored in the tree T that maximizes the prefix sum , prefix(k) = {x.valP | x ∈ T and x.key ≤ k}(that is, the sum of all values of items whose keys are ≤ k); and
• all other Set AVL Tree operations maintain their running times.
(c) [5 points] Using the data structure from part (b) as a black box, describe a worst-case O(n log n)-time algorithm to return a triple (x, y, t), where point (x, y) corresponds to a slice of maximum tastiness t.
(d) [25 points] Write a Python function tastiest slice(toppings) that implements your algorithm from part (c), including an implementation of your data structure from part (b).
Problem Set 4
1 from Set_AVL_Tree import BST_Node, Set_AVL_Tree
2
3 class Key_Val_Item:
4 def __init__(self, key, val):
5 self.key = key
6 self.val = val
7
8 def __str__(self):
9 return "%s,%s" % (self.key, self.val)
10
11 class Part_B_Node(BST_Node):
12 def subtree_update(A):
13 super().subtree_update()
14 #########################################
15 # ADD ANY NEW SUBTREE AUGMENTATION HERE #
16 #########################################
17
18 class Part_B_Tree(Set_AVL_Tree):
19 def __init__(self):
20 super().__init__(Part_B_Node)
21
22 def max_prefix(self):
23 ’’’
24 Output: (k, s) | a key k stored in tree whose
25 | prefix sum s is maximum
26 ’’’
27 k, s = 0, 0
28 ##################
29 # YOUR CODE HERE #
30 ##################
31 return (k, s)
32
33 def tastiest_slice(toppings):
34 ’’’
35 Input: toppings | List of integer tuples (x,y,t) representing
36 | a topping at (x,y) with tastiness t
37 Output: tastiest | Tuple (X,Y,T) representing a tastiest slice
38 | at (X,Y) with tastiness T
39 ’’’
40 B = Part_B_Tree() # use data structure from part (b)
41 X, Y, T = 0, 0, 0
42 ##################
43 # YOUR CODE HERE #
44 ################## 45 return (X, Y, T)
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms