Introduction to Algorithms: 6.006Massachusetts Institute of Technology February 1, 2011Professors Erik Demaine, Piotr Indyk, and Manolis Kellis Problem Set 1Problem Set 1This problem set is divided into two parts: Part A problems are theory questions, and Part Bproblems are programming tasks.Both Part A and Part B questions are due Monday, February 14 at 11:59PM.Solutions should be turned in through the course website. Your solution to Part A should be inPDF format using LATEX or scanned handwritten solutions. Your solution to Part B should be avalid Python file which runs from the command line. A template for writing up solutions in LATEXis available on the course website. Remember, your goal is to communicate. Full credit will begiven only to a correct solution which is described clearly. Convoluted and obtuse descriptionsmight receive low marks, even when they are correct. Also, aim for concise solutions, as it willsave you time spent on write-ups, and also help you conceptualize the key idea of the problem.Part A:Problem 1-1. [18 points] Asymptotic GrowthFor each group of four functions below, rank the functions by increasing order of growth; that is,find an arrangement g1, g2, g3, g4of the functions satisfying g1= O(g2), g2= O(g3), g3= O(g4).(For example, the correct ordering of n, n2, n3, n4is n, n2, n3, n4.)(a) [6 points] Group 1:f1=√n f2=n2f3= 22100000f4= log n(b) [6 points] Group 2:f1(n) = 1/n f2(n) = log log log n f3(n) = n/ log n f4(n) = n0.99(c) [6 points] Group 3:f1(n) = 2nf2(n) = n · 2n/2f3(n) = log nnf4(n) =nXi=0iProblem 1-2. [6 points] Unimodal MaximumDefine an array A[0 . . n − 1] of numbers to be unimodal if there exists a maximum element A[k]such that2 Problem Set 1A[i] > A[i − 1] for all i such that 0 < i ≤ k, andA[i] < A[i − 1] for all i such that k < i < nFor example, [1, 4, 8, 9, 7, 6, 2] is unimodal, while [1, 3, 5, 4, 1, 2] is not.Assume that all the numbers in A are distinct.Devise an efficient algorithm to find the maximum element in a unimodal array A. Prove that youralgorithm runs in O(log n) time.Problem 1-3. [6 points] (Re)writing HistoryFor next year’s State of the Onion address, President Banach Bahama needs help crafting hisspeech so that it’s not too similar to the one he gave this year. He’s been advised that MIT 6.006students have been taught about document distance and has found this to be a reasonable metricto use in crafting his new speech. And thus he has turned to you to help advise him in writing hisnew speech.Recall that a document distance of θ = 0 means the speeches are identical and that θ = 90◦meansthey don’t even share a word. Starting with a copy of this year’s speech, Banach wants to knowwhether each of the following strategies will improve his speech (i.e., increase θ) or not help at all(i.e., keep θ the same). He also requires an explanation for each of your answers.(a) [2 points] Strategy 1: re-arrange the order of the words while somehow keeping itcoherent (or not).(b) [2 points] Strategy 2: pad the speech with extra words, none of which appeared in hisspeech for this year.(c) [2 points] Strategy 3: remove some number of words from his speech for this year.Problem 1-4. [20 points] Augmented Binary Search TreesClasses have started and you are still searching for an “Introduction to Algorithms” textbook. Asyou search for textbooks, you decide to use an AVL tree to keep track of the prices you comeacross. Besides the standard operations of an AVL tree (e.g., insert(k) and search(k)), you alsowant to the tree to support num textbooks in range(a, b), which finds how many textbooks fallwithin the price range a to b inclusive. For example, if the set of textbook prices were [6, 9, 16, 3,5], then num textbooks in range(5, 11) = 3, since the prices 5, 6, and 9 are in the specified rangeof [5, 11].(a) [6 points] Describe an implementation of the num textbooks in range(a, b) opera-tion on a regular (non-augmented) AVL tree. What is its running time?If we augment the AVL tree so that each node maintains the size of the subtree rooted at that node(in addition to a price and pointers to parent and children), we can speed up the num textbooks inrange operation to take O(log n) time.Problem Set 1 3(b) [14 points] Describe your implementation of the num textbooks in range(a, b) op-eration. Argue that it takes O(log n) time.Part B:Problem 1-5. [50 points] Peak FindingConsider an array A[0 . . n − 1] of n integers. Define a peak of A to be an index i with 0 ≤ i < nsuch that A[i − 1] ≤ A[i] and A[i] ≥ A[i + 1], where we imagine A[−1] = A[n] = −∞. Inother words, a peak x is greater than or equal to its neighbors in A, where we treat the first and lastelements as having only one neighbor. Note that A might have multiple peaks.For example, if A = [10, 6, 4, 3, 12, 19, 18], then A has two peaks, 10 and 19.Note that the absolute maximum of A is always a peak, but it requires Ω(n) time to compute.(a) [20 points] Write quick find 1d peak(A) to compute a peak of an arrayA[0 . . n − 1] of integers in O(log n) time, using the algorithm described in lecture.Now consider an n×n matrix B of integers. Define the neighborhood of element B[i][j] to consistof B[i+1][j], B[i−1][j], B[i][j +1], and B[i][j −1]. To properly handle the boundary, we imagineB[−1][j] = B[i][−1] = B[i][n] = B[n][j] = −∞. Define an element B[i][j] to be a peak of B ifit is greater than or equal to all of its neighbours. Note that the maximum element of B is a peak,but that requires Ω(n2) time to compute.(b) [30 points] Write quick find 2d peak(B) to compute a peak of n × n arrayB of integers in O(n) time, using the algorithm described in lecture.For Python coding help, we have provided code skeletons for you to fill in, including a few help-ful auxiliary routines, and an implementation of the O(n log n) algorithm for 2D peak findingdescribed in lecture (medium find 2d
View Full Document