6.006 Introduction to Algorithms, Problem Set 1 Solutions

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Problem Set 1 Problem Set 1 Please write your solutions in the LATEX and Python templates provided. Aim for concise solutions; convoluted and obtuse descriptions might receive low marks, even when they are correct. Problem 1-1. [20 points] Asymptotic behavior of functions For each of the following sets of five functions, order them so that if fa appears before fb in your sequence, then fa = O(fb ). If fa = O(fb ) and fb = O(fa ) (meaning fa and fb could appear in either order), indicate this by enclosing fa and fb in a set with curly braces. For example, if the functions are: √ √ f1 = n, f2 = n, f3 = n + n, the correct answers are (f2 , {f1 , f3 }) or (f2 , {f3 , f1 }). c c Note: Recall that ab means a(b ) , not (ab )c , and that log means log2 unless a different base is specified explicitly. Stirling’s approximation may help for comparing factorials. a) f1 f2 f3 f4 f5 b) = log(nn ) = (log n)n = log(n6006 ) = (log n)6006 = log log(6006n) f1 f2 f3 f4 = 2n = 6006n n = 26006 n = 60062 2 f5 = 6006n c) d) f1 = n n   n f2 = n−6 f3 = (6n)!   n f4 = n/6 6 f5 = n f1 = nn+4 + n! √ f2 = n 7 n f3 = 43n log n 2 f4 = 7n f5 = n12+1/n Solution: a. (f5 , f3 , f4 , f1 , f2 ). Using exponentiation and logarithm rules, we can simplify these to f1 = Θ(n log n), f2 = Θ((log n)n ), f3 = Θ(log n), f4 = Θ((log n)6006 ), and f5 = Θ(log log n). For f2 , note that (log n)n > 2n for large n, so this function grows at least exponentially and is therefore bigger than the rest. b. (f1 , f2 , f5 , f4 , f3 ). This order follows after converting all the exponent bases to 2. (For exam2 ple, f5 = 2log(6006)n .) Remember that asymptotic growth is much more sensitive to changes in exponents: even if the exponents are both Θ(f (n)) for some function f (n), the functions will not be the same asymptotically unless their exponents only differ by a constant. 2 Problem Set 1 c. ({f2 , f5 }, f4 , f1 , f3 ). This order follows from the definition of the binomial coefficient and Stirling’s approximation. f2 has most terms cancel in the numerator and denominator, √ leav6 5/6 n ing a polynomial with leading term n /6!. The trickiest one is f4 = Θ((6/(5 )) / n) (by √ n repeated use of Stirling), which is about Θ(1.57 / √n). Thus f4 is bigger than the polynomials but smaller than the factorial and nn . f3 = Θ( n(6n/e)6n ) which grows asymptotically faster than nn by a factor of Θ(n5n+(1/2) (6/e)6n ). (Originally, f3 was presented as 6n! which could reasonably be interpretted as 6(n!), which would put f3 before f1 in the order. Because of this, graders should accept f1 and f3 in either order.) d. (f5 , f2 , f1 , f3 , f4 ). It is√easiest to see this by taking the logarithms of the functions, which give us Θ(n log n), Θ( n log n), Θ(n log n), Θ(n2 ), Θ(log n) respectively. However, asymptotically similar logarithms do not imply that the functions are asymptotically the same, so we consider f1 and f3 further. Note that f3 = (4log n )3n = (nlog 4 )3n = n6n . This is bigger (by about a factor of n5n ) than the larger of f1 ’s terms, so f3 is asymptotically larger. Rubric: • 5 points per set for a correct order • −1 point per inversion • −1 point per grouping mistake, e.g., ({f1 , f2 , f3 }) instead of (f2 , f1 , f3 ) is −2 points because they differ by two splits. • 0 points minimum Problem Set 1 3 Problem 1-2. [16 points] Given a data structure D that supports Sequence operations: • D.build(X) in O(n) time, and • D.insert at(i, x) and D.delete at(i), each in O(log n) time, where n is the number of items stored in D at the time of the operation, describe algorithms to implement the following higher-level operations in terms of the provided lower-level operations. Each operation below should run in O(k log n) time. Recall, delete at returns the deleted item. (a) reverse(D, i, k): Reverse in D the order of the k items starting at index i (up to index i + k − 1). Solution: Thinking recursively, to reverse the k-item subsequence from index i to index i + k − 1, we can swap the items at index i and index i + k − 1, and then recursively reverse the rest of the subsequence. As a base case, no work needs to be done to reverse a subsequence containing fewer than 2 items. This procedure would then be correct by induction. It remains to show how to actually swap items at index i and index i + k − 1. Note that removing an item will shift the index values at all later items. So to keep index values consistent, we will delete at the later index i + k − 1 first (storing item as x2 ), and then delete at index i (storing item as x1 ). Then we insert them back in the opposite order, insert at item x2 at index i, and then insert at item x1 at index i + k − 1. This swap is correct by the definitions of these operations. The swapping sub procedure performs four O(log n)-time operations, so occurs in O(log n) time. Then the recursive reverse procedure makes no more than k/2 = O(k) recursive calls before reaching a base case, doing one swap per call, so the algorithm runs in O(k log n) time. 1 2 3 4 5 6 7 8 def reverse(D, i, k): if k < 2: return x2 = D.delete_at(i + k - 1) x1 = D.delete_at(i) D.insert_at(i, x2) D.insert_at(i + k - 1, x1) reverse(D, i + 1, k - 2) Rubric: • • • • 5 points for description of algorithm 1 point for argument of correctness 2 point for argument of running time Partial credit may be awarded # base case # swap items i and i + k - 1 # recurse on remainder 4 Problem Set 1 (b) move(D, i, k, j): Move the k items in D starting at index i, in order, to be in front of the item at index j. Assume that expression i ≤ j < i + k is false. Solution: Thinking recursively, to move the k-item subsequence starting at i in front of the item at index j, it suffices to move the item at index i in front of the item B at index j, and then recursively move the remainder (the (k − 1)-item subsequence starting at index i in front of . As a base case, no work needs to be done to move a subsequence containing fewer than 1 item. If we maintain that: i is the index of the first item to be moved, k is number of items to be moved, and j denotes the index of the item in front of which we must place items, then this procedure will be correct by induction. Note that after removing the item A at index i, if j > i, item B will shift down to be at index j − 1. Similarly, after inserting A in front of B, item B will be at an index that is one larger than before, while the next item in the subsequence to be moved will also be at a larger index if i > j. Maintaining these indices then results in a correct algorithm. This recursive procedure makes no more than k = O(k) recursive calls before reaching a base case, doing O(log n) work per call, so the algorithm runs in O(k log n) time. 1 2 3 4 5 6 7 8 9 10 11 def move(D, i, k, j): if k < 1: return x = D.delete_at(i) if j > i j = j - 1 D.insert_at(j, x) j = j + 1 if i > j i = i + 1 move(D, i, k - 1, j) Rubric: • • • • 5 points for description of algorithm 1 point for argument of correctness 2 point for argument of running time Partial credit may be awarded Problem Set 1 5 Problem 1-3. [20 points] Binder Bookmarks Sisa Limpson is a very organized second grade student who keeps all of her course notes on individual pages stored in a three-ring binder. If she has n pages of notes in her binder, the first page is at index 0 and the last page is at index n − 1. While studying, Sisa often reorders pages of her notes. To help her reorganize, she has two bookmarks, A and B, which help her keep track of locations in the binder. Describe a database to keep track of pages in Sisa’s binder, supporting the following operations, where n is the number of pages in the binder at the time of the operation. Assume that both bookmarks will be placed in the binder before any shift or move operation can occur, and that bookmark A will always be at a lower index than B. For each operation, state whether your running time is worst-case or amortized. build(X) place mark(i, m) read page(i) shift mark(m, d) move page(m) Initialize database with pages from iterator X in O(|X|) time. Place bookmark m ∈ {A, B} between the page at index i and the page at index i + 1 in O(n) time. Return the page at index i in O(1) time. Take the bookmark m ∈ {A, B}, currently in front of the page at index i, and move it in front of the page at index i + d for d ∈ {−1, 1} in O(1) time. Take the page currently in front of bookmark m ∈ {A, B}, and move it in front of the other bookmark in O(1) time. Solution: There are many possible solutions. First note that the problem specifications ask for a constant-time read page(i) operation, which can only be supported using array-based implementations, so linked-list approaches will be incorrect. Also note that that until both bookmarks are placed, we can simply store all pages in a static array of size n, since no operations can change the sequence of pages until both bookmarks are placed. We present a solution generalizing the dynamic array we discussed in class. Another common approach could be to reduce to using two dynamic arrays (one on either end of bookmarks A and B), together with an array-based deque as described in Problem Session 1 to store the pages between bookmarks A and B. For our approach, after both bookmarks have been placed, we will store the n pages in a static array S of size 3n, which we can completely re-build in O(n) time whenever build(X) or place mark(i, m) are called (assuming n = |X|). To build S: • place the subsequence P1 of pages from index 0 up to bookmark A at the beginning of S, • followed by n empty array locations, • followed by the subsequence of pages P2 between bookmarks A and B, • followed by n empty array locations, • followed by the subsequence of pages P3 from bookmark B to index n − 1. We will maintain the separation invariant that P1 , P2 , and P3 are stored contiguously in S with a non-zero number of empty array slots between them. We also maintain four indices with semantic 6 Problem Set 1 invariants: a1 pointing to the end of P1 , a2 pointing to the start of P2 , b1 pointing to the end of P2 , and b2 pointing to the start of P3 . To support read page(i), there are three cases: either i is the index of a page in P1 , P2 , or P3 . • If i < n1 , where n1 = |P1 | = ai + 1, then the page is in P1 , and we return page S[i]. • Otherwise, if n1 ≤ i < n1 + n2 , where n2 = |P2 | = (b1 − a2 + 1), then the page is in P2 , and we return page S[a2 + (i − n1 )]. • Otherwise, i > a1 + n2 , so the page is in P3 , and we return page S[b2 + (i − n1 − n2 )]. This algorithm returns the correct page as long as the invariants on the stored indices are maintained, and returns in worst-case O(1) time based on some arithmetic operations and a single array index lookup. To support shift mark(m, d), move the relevant page at one of indices (a1 , a2 , b1 , b2 ) to the index location (a2 − 1, a1 + 1, b2 − 1, b1 + 1) respectively, and then increment the stored indices to maintain the invariants. This algorithm maintains the invariants of the data structure so is correct, and runs in O(1) time based on one array index lookup, and one index write. Note that this operation does not change the amount of extra space between sections P1 , P2 , and P3 , so the running time of this operation is worst-case. To support move page(m), move the relavent page at one of indices (a1 , b1 ) to the index location (b1 + 1, a1 + 1) respectively, and then increment the stored indices to maintain the invariants. If performing this move breaks the separation invariant (i.e., either pair (a1 , a2 ) or (b1 , b2 ) become adjacent), rebuild the entire data structure as described above. This algorithm maintains the invariants of the data structure, so is correct. Note that this algorithm: rebuilds any time the extra space between two adjacent sections closes; after rebuilding, there is n extra space between adjacent sections; and the extra space between adjacent sections changes by at most one per move page operation. Thus, since this operation takes O(n) time at most once every n operations, and O(1) time otherwise, this operation runs in amortized O(1) time. Rubric: • 4 points for general description of a correct database • 1 point for description of a correct build(X) • 2 points for description of a correct place mark(i, m) • 3 points for description of a correct read page(i) • 2 points for description of a correct shift mark(m, d) • 3 points for description of a correct move page(m) • 1 point for analysis of running time for each operation (5 points total) • Partial credit may be awarded Problem Set 1 7 Problem 1-4. [44 points] Doubly Linked List In Lecture 2, we described a singly linked list. In this problem, you will implement a doubly linked list, supporting some additional constant-time operations. Each node x of a doubly linked list maintains an x.prev pointer to the node preceeding it in the sequence, in addition to an x.next pointer to the node following it in the sequence. A doubly linked list L maintains a pointer to L.tail, the last node in the sequence, in addition to L.head, the first node in the sequence. For this problem, doubly linked lists should not maintain their length. (a) [8 points] Given a doubly linked list as described above, describe algorithms to implement the following sequence operations, each in O(1) time. insert first(x) insert last(x) delete first() delete last() Solution: Below are descriptions of algorithms supporting the requested operations. Each of these algorithm performs each constant-sized task directly, so no additional argument of correctness is necessary. Each runs in O(1) time by relinking a constant number of pointers (and possibly constructing a single node). insert first(x): Construct a new doubly linked list node a storing x. If the doubly linked list is empty, (i.e., the head and tail are unlinked), then link both the head and tail of the list to a. Otherwise, the linked list has a head node b, so make a’s next pointer point to b, make b’s previous pointer point to a, and set the list’s head to point to a. insert last(x): Construct a new doubly linked list node a storing x. If the doubly linked list is empty, (i.e., the head and tail are unlinked), then link both the head and tail of the list to a. Otherwise, the linked list has a tail node b, so make a’s previous pointer point to b, make b’s next pointer point to a, and set the list’s tail to point to a. delete first(): This method only makes sense for a list containing at least one node, so assume the list has a head node. Extract and store the item x from the head node of the list. Then set the head to point to the node a pointed to by the head node’s next pointer. If a is not a node, then we removed the last item from the list, so set the tail to None (head is already set to None). Otherwise, set the new head’s previous pointer to None. Then return item x. delete last(): This method only makes sense for a list containing at least one node, so assume the list has a tail node. Extract and store the item x from the tail node of the list. Then set the tail to point to the node a pointed to by the tail node’s previous pointer. If a is not a node, then we removed the last item from the list, so set the head to None (tail is already set to None). Otherwise, set the new tail’s next pointer to None. Then return item x. Rubric: • 2 points for description and analysis of each correct operation • Partial credit may be awarded 8 Problem Set 1 (b) [5 points] Given two nodes x1 and x2 from a doubly linked list L, where x1 occurs before x2, describe a constant-time algorithm to remove all nodes from x1 to x2 inclusive from L, and return them as a new doubly linked list. Solution: Construct a new empty list L2 in O(1) time, and set its head and tail to be x1 and x2 respectively. To extract this sub-list, care must be taken when x1 or x2 are the head or tail of L respectively. If x1 is the head of L, set the new head of L to be the node a pointed to by x2’s next pointer; otherwise, set the next pointer of the node pointed to by x1’s previous pointer to a. Similarly, if x2 is the tail of L, set the new tail of L to be the node b pointed to by x1’s previous pointer; otherwise, set the previous pointer of the node pointed to by x2’s next pointer to b. This algorithm removes the nodes from x1 to x2 inclusive directly, so it is correct, and runs in O(1) time by relinking a constant number of pointers. Rubric: • • • • 3 points for description of a correct algorithm 1 point for argument of correctness 1 point for argument of running time Partial credit may be awarded (c) [6 points] Given node x from a doubly linked list L1 and second doubly linked list L2, describe a constant-time algorithm to splice list L2 into list L1 after node x. After the splice operation, L1 should contain all items previously in either list, and L2 should be empty. Solution: First, let x1 and x2 be the head and tail nodes of L2 respectively, and let xn be the node pointed to by the next pointer of x (which may be None). We can remove all nodes from L2 by setting both it’s head and tail to None. Then to splice in the nodes, first set the previous pointer of x1 to be x, and set the next pointer of x to be x1. Similarly, set the next pointer of x2 to be xn. If xn is None, then set x2 to be the new tail of L; otherwise, set the previous pointer of xn to point back to x2. This algorithm inserts the nodes from L2 directly into L, so it is correct, and runs in O(1) time by relinking a constant number of pointers. Rubric: • • • • 4 points for description of a correct algorithm 1 point for argument of correctness 1 point for argument of running time Partial credit may be awarded (d) [25 points] Implement the operations above in the Doubly Linked List Seq class in the provided code template; do not modify the Doubly Linked List Node class. You can download the code template including some test cases from the website. Problem Set 1 Solution: 1 2 class Doubly_Linked_List_Seq: # other template methods omitted 3 4 5 6 7 8 9 10 11 12 def insert_first(self, x): new_node = Doubly_Linked_List_Node(x) if self.head is None: self.head = new_node self.tail = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node 13 14 15 16 17 18 19 20 21 22 def insert_last(self, x): new_node = Doubly_Linked_List_Node(x) if self.tail is None: self.head = new_node self.tail = new_node else: new_node.prev = self.tail self.tail.next = new_node self.tail = new_node 23 24 25 26 27 28 29 30 def delete_first(self): assert self.head x = self.head.item self.head = self.head.next if self.head is None: self.tail = None else: self.head.prev = None return x 31 32 33 34 35 36 37 38 def delete_last(self): assert self.tail x = self.tail.item self.tail = self.tail.prev if self.tail is None: self.head = None else: self.tail.next = None return x 39 40 41 42 43 44 45 46 47 48 49 50 def remove(self, x1, x2): L2 = Doubly_Linked_List_Seq() L2.head = x1 L2.tail = x2 if x1 == self.head: self.head = x2.next x1.prev.next = x2.next else: if x2 == self.tail: self.tail = x1.prev else: x2.next.prev = x1.prev x1.prev = None x2.next = None return L2 51 52 53 54 55 56 57 58 59 60 61 62 def splice(self, x, L2): xn = x.next x1 = L2.head x2 = L2.tail L2.head = None L2.tail = None x1.prev = x x.next = x1 x2.next = xn if xn: xn.prev = x2 else: self.tail = x2 9