MIT6006 Problem Set 1 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 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}).
a) b) c) d)
f1 = log(nn ) f2 = (log n)n f3 = log(n6006 ) f4 = (log n)6006 f5 = log log(6006n) f1 = 2n f2 = 6006n f3 = 26006n f4 = 60062n f5 = 6006n2 f1 = n n+4 + n!
√
f2 = n 7 n f3 = 43n log n f4 = 7n2 f5 = n 12+1/n
2 Problem Set 1
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).
build(X) Initialize database with pages from iterator X in O(|X|) time.
place mark(i, m) Place bookmark m ∈ {A, B} between the page at index i and the page at index i + 1 in O(n) time.
read page(i) Return the page at index i in O(1) time.
shift mark(m, d) 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.
move page(m) Take the page currently in front of bookmark m ∈ {A, B}, and move it in front of the other bookmark in O(1) time.
(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.
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.
Problem Set 1 3
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()
(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.
(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.
(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 web- site.
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms