Introduction to Algorithms: 6.006Massachusetts Institute of Technology September 13, 2010Professors Konstantinos Daskalakis and Patrick Jaillet Problem Set 1Problem Set 1This problem set is divided into two parts: Part A problems are theory questions, and Part Bproblems are programming tasks.Part A questions are due Tuesday, September 21st at 11:59PM.Part B questions are due Thursday, September 23rd at 11:59PM.Solutions should be turned in through the course website. Your solution to Part A should be inPDF form using LATEX or scanned handwritten solutions. Your solution to Part B should be a validPython file which runs from the command line.A template for writing up solutions in LATEX is available on the course website.Remember, your goal is to communicate. Full credit will be given only to the correct solutionwhich is described clearly. Convoluted and obtuse descriptions might receive low marks, evenwhen they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups,and also help you conceptualize the key idea of the problem.Part A: Due Tuesday, September 21st1. (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) = n2nf2(n) = 2n/2f3(n) = n! f4(n) = (n/e)n(b) (6 points) Group 2:f1= (log n)1000f2= n1/2f3= 1/n f4= n6.006(c) (6 points) Group 3:f1(n) = n100f2(n) = n log n f3(n) =1nn100f4(n) = log(log(n))2. (12 points) Binary SearchBinary search is a fast algorithm used for finding membership of an element in a sorted list.The recursive version of the algorithm is given below. The function takes a sorted list ofnumbers, alist, and a query, item, and returns true if and only if item ∈ alist. Let ndenote the length of the list alist.2 Problem Set 1def binarySearch(alist, item):if len(alist) == 0:return Falseelse:midpoint = len(alist)/2if alist[midpoint]==item:return Trueelse:if item<alist[midpoint]:return binarySearch(alist[:midpoint],item)else:return binarySearch(alist[midpoint+1:],item)(a) (5 points) What is the runtime of the recursive version in terms of n, and why?(b) (7 points) Write a concise proof of correctness for the algorithm. (Note: you may wishto use a loop invariant for your proof. See section 2.1 of CLRS for an example.)3. (20 points) Uncoordinated Peak FindingRecall the 2-dimensional Peak finding problem discussed in lecture. Consider the followingalgorithm for solving the problem, given a 2-dimensional integer matrix B of size nxn:1 Let n = len(row(B)). Find the maximum element of the (n/2)thcolumn and call itcmax= B[i][n/2]2 If cmax≥ B[i][n/2 − 1] and cmax≥ B[i][n/2 + 1] return cmax3 If cmax< B[i][n/2− 1] then B = B[0..(n-1)][0..n/2-1] else B=B[0..(n-1)][n/2+1..(n-1)]4 Find the maximum element of the (n/2)throw of B and call it rmax= B[n/2][j]5 If rmax≥ B[n/2 − 1][j] and rmax≥ B[n/2 + 1][j] return rmax6 If rmax< B[n/2 − 1][j] then B = B[0..n/2-1][0..n/2-1] else B=B[n/2+1..(n-1)][0..n/2-1]7 goto Step 1.(a) (10 points) Give a counterexample (an instance of B of size no larger than 7× 7) wherethe above algorithm fails to find a peak in B even though it exists. (If your exampleis smaller than 7 × 7 and does not have a well-defined middle row or middle column,state which rows/columns you use as the middle rows/columns.)(b) (10 points) We can fix the above algorithm by keeping track of the running maximumrunmaxas below. Explain how it solves the problem in the previous counterexample.1 runmax= −∞2 Let n = len(row(B)). Find the maximum element of the (n/2)thcolumn and call itcmax= B[i][n/2]Problem Set 1 33 If cmax≥ runmaxthen4 If cmax≥ B[i][n/2 − 1] and cmax≥ B[i][n/2 + 1] then return cmax5 If cmax< B[i][n/2−1] then runmax= B[i][n/2−1] else runmax= B[i][n/2+1]6 If cmax< B[i][n/2−1] then B=B[0..(n-1)][0..n/2-1] else B=B[0..(n-1)][n/2+1..(n-1)]7 Else /* Update B to be the partition of B containing runmax*/8 If runmax∈ B[0..(n-1)][0..n/2-1] then B=B[0..(n-1)][0..n/2-1] else B=B[0..(n-1)][n/2+1..(n-1)]9 Find the maximum element of the (n/2)throw of B and call it rmax= B[n/2][j]10 If rmax≥ runmaxthen11 If rmax≥ B[n/2 − 1][j] and rmax≥ B[n/2 + 1][j] return rmax12 If rmax< B[n/2−1][j] then runmax= B[n/2−1][j] else runmax= B[n/2+1][j]13 If rmax< B[n/2 − 1][j] then B = B[0..n/2-1][0..n/2] else B=B[n/2+1..(n-1)][0..n/2]14 Else /* Update B to be the partition of B containing runmax*/15 If runmax∈ B[0..n/2 − 1][0..n/2 − 1] then B = B[0..n/2 − 1][0..n/2 − 1]else B = B[n/2 + 1..(n − 1)][0..n/2 − 1]16 goto Step 2.Part B: Due Thursday, September 23rd1. (50 points) Peak FindingConsider an array A containing n integers. We define a peak of A to be an x such thatx = A[i], for some 0 ≤ i < n, with A[i − 1] ≤ A[i] and A[i] ≥ A[i + 1]. In other words,a peak x is greater than or equal to its neighbors in A (for boundary elements, there is onlyone neighbor). Note that A might have multiple peaks.As an example, suppose 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.• (20 points) Write quick find 1d peak to compute any peak of array A in O(log(n))time using the algorithm described in the lecture.Now consider a three dimensional matrix B of integers of size n × n × n. We define theneighborhood of an element x = B[i][j][k] as B[i + 1][j][k], B[i − 1][j][k], B[i][j + 1][k],B[i][j − 1][k], B[i][j][k + 1] and B[i][j][k − 1]. For elements on a face we consider only fiveneigbors, for elements on an edge we consider only four neighbors, and for elements on theeight corners, only three neighbors are considered. x is defined to be a peak of B if and only4 Problem Set 1if it is greater than or equal to all of its neighbours. Note that the maximum element of B isa possible solution for x but finding it requires Ω(n3) time.For python coding help, the O(n log(n)) algorithm described in the lecture is provided asmedium find 2d peak.• (10 points) Describe an algorithm to find a peak of a three dimensional matrix B inO(n2) time, and explain why the running time of your algorithm is O(n2).• (20 points) Write quick find 3d peak to compute any peak of array B in O(n2)time using your
View Full Document
Unlocking...