MIT6006 Problem Set 2 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 2-1. [15 points] Solving recurrences
Derive solutions to the following recurrences. A solution should include the tightest upper and lower bounds that the recurrence will allow. Assume T (1) = Θ(1).
Solve parts (a), (b), and (c) in two ways: drawing a recursion tree and applying Master Theorem. Solve part (d) only by substitution.
(a) [4 points]
(b) [4 points]
(c) [4 points]
(d) [3 points] T (n) = T (n − 2) + Θ(n)
Problem 2-2. [15 points] Sorting Sorts
(a) [5 points] Suppose you are given a data structure D maintaining an extrinsic order on n items, supporting two standard sequence operations: D.get at(i) in worstcase Θ(1) time and D.set at(i, x) in worst-case Θ(n log n) time. Choose an algorithm to best sort the items in D in-place.
(b) [5 points] Suppose you have a static array A containing pointers to n comparable objects, pairs of which take Θ(log n) time to compare. Choose an algorithm to best sort the pointers in A so that the pointed-to objects appear in non-decreasing order.
(c) [5 points] Suppose you have a sorted array A containing n integers, each of which fits into a single machine word. Now suppose someone performs some log log n swaps between pairs of adjacent items in A so that A is no longer sorted. Choose an algorithm to best re-sort the integers in A.
2 Problem Set 2
Problem 2-3. [10 points] Friend Finder
Jean-Locutus Πcard is searching for his incapacitated friend, Datum, on Gravity Island. The island is a narrow strip running north–south for n kilometers, and Πcard needs to pinpoint Datum’s location to the nearest integer kilometer so that he is within visual range. Fortunately, Πcard has a tracking device, which will always tell him whether Datum is north or south of his current position (but sadly, not how far away he is), as well as a teleportation device, which allows him to jump to specified coordinates on the island in constant time.
Unfortunately, Gravity Island is rapidly sinking. The topography of the island is such that the north and south ends will submerge into the water first, with the center of the island submerging last. Therefore, it is more important that Πcard find Datum quickly if he is close to either end of the island, lest he short-circuit. Describe an algorithm so that, if Datum is k kilometers from the nearest end of the island (i.e., he is either at the kth or the (n − k)th kilometer, measured from north to south), then Πcard can find him after visiting O(log k) locations with his teleportation and tracking devices.
Problem 2-4. [15 points] MixBookTube.tv Chat
MixBookTube.tv is a service that lets viewers chat while watching someone play video games.
Each viewer is identified by a known unique integer ID . The chat consists of a linear stream of messages, each written by a viewer. Viewers can see the most recent k chat messages, where k depends on the size of their screen. Sometimes a viewer misbehaves in chat and gets banned by the streamer. When a viewer gets banned, not only can they not post new messages in chat, but all of their previously sent messages are removed from the chat.
Describe a database to efficiently implement MixBookTube.tv’s chat, supporting the following operations, where n is the number of all viewers (banned or not) in the database at the time of the operation (all operations should be worst-case):
build(V) Initialize a new chat room with the n = |V| viewers in V in O(n log n) time.
send(v, m) Send message m to the chat from viewer v (unless banned) in O(log n) time.
recent(k) Return the k most recent not-deleted messages (or all if < k) in O(k) time.
ban(v) Ban viewer v and delete all their messages in O(nv + log n) time, where nv is the number of messages that viewer v sent before being banned.
Problem Set 2 3
Problem 2-5. [45 points] Beaver Bookings
Tim the Beaver is arranging Tim Talks, a lecture series that allows anyone in the MIT community to schedule a time to talk publicly. A talk request is a tuple (s, t), where s and t are the starting and ending times of the talk respectively with s < t (times are positive integers representing the number of time units since some fixed time).
Tim must make room reservations to hold the talks. A room booking is a triple (k, s, t), corresponding to reserving k > 0 rooms between the times s and t where s < t. Two room bookings
(k1,s1,t1) and (k2,s2,t2) are disjoint if either t1 ≤ s2 or t2 ≤ s1, and adjacent if either t1 = s2 or t2 = s1. A booking schedule is an ordered tuple of room bookings where: every pair of room bookings from the schedule are disjoint, room bookings appear with increasing starting time in the sequence, and every adjacent pair of room bookings reserves a different number of rooms.
Given a set R of talk requests, there is a unique booking schedule B that satisfies the requests, i.e., the schedule books exactly enough rooms to host all the talks. For example, given a set of talk requests
R = {(2, 3), (4, 10), (2, 8), (6, 9), (0, 1), (1, 12), (13, 14)} pictured to the right, the satisfying room booking is:
B = ((1, 0, 2), (3, 2, 3), (2, 3, 4), (3, 4, 6), (4, 6, 8), (3, 8, 9), (2, 9, 10), (1, 10, 12), (1, 13, 14)).
(a) [15 points] Given two booking schedules B1 and B2, where n = |B1| + |B2| and B1 and B2 are the respective booking schedules of two sets of talk requests R1 and R2, describe an O(n)-time algorithm to compute a booking schedule B for R = R1 ∪ R2.
(b) [5 points] Given a set R of n talk requests, describe an O(n log n)-time algorithm to return the booking schedule that satisfies R.
(c) [25 points] Write a Python function satisfying booking(R) that implements your algorithm. You can download a code template containing some test cases from the website.
1 def satisfying_booking(R):
2 ’’’
3 Input: R | Tuple of |R| talk request tuples (s, t) 4 Output: B | Tuple of room booking triples (k, s, t)
5 | that is the booking schedule that satisfies R
6 ’’’
7 B = []
8 ##################
9 # YOUR CODE HERE #
10 ################## 11 return tuple(B)
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms