Introduction to Algorithms: 6.006Massachusetts Institute of Technology September 15th, 2009Professors Srini Devadas and Constantinos (Costis) Daskalakis Handout 2Problem Set 1This problem set is divided into two parts: Part A problems are theory questions, andPart B problems are programming tasks.Part A questions are due Tuesday, September 22nd at 11:59PM.Part B questions are due Thursday, September 24th at 11:59PM.Solutions should be turned in through the course website in PDF form using LATEX orscanned handwritten solutions.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 correctsolution which is described clearly. Convoluted and obtuse descriptions might receivelow marks, even when they are correct. Also, aim for concise solutions, as it will save youtime spent on write-ups, and also help you conceptualize the key idea of the problem.Part A: Due Tuesday, September 22nd1. (18 points) Asymptotic GrowthFor each group of six functions below, rank the functions by increasing order ofgrowth; that is, find an arrangement g1, g2, . . . , g6of the functions satisfying g1=O(g2), g2= O(g3), . . . , g5= O(g6). Partition each list into equivalence classes suchthat f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).(a) (6 points) Group 1:f1(n) = 106006n2, f2(n) = 1/n, f3(n) = n6.006f4(n) = n, f5(n) = 1/6.006, f6(n) = 6.006n(b) (6 points) Group 2:f1(n) = n log n, f2(n) = log(log(n)), f3(n) =n50f4(n) = n1/50, f5(n) = log(n), f6(n) = log(√10n)(c) (6 points) Group 3:f1(n) = 2n, f2(n) = n2n, f3(n) = 2n+1f4(n) = 4n, f5(n) = n!, f6(n) = 3√n2. (12 points) Binary SearchBinary search is a fast algorithm used for finding membership of an element in asorted list. The iterative version of the algorithm is given below. The function takesa sorted list of numbers, alist, and a query, item, and returns true if and only ifitem ∈ alist. Let n denote the length of the list alist.2Handout 2: Problem Set 1def binarySearch(alist, item):first = 0last = len(alist)-1found = Falsewhile first<=last and not found:midpoint = (first + last)/2if alist[midpoint] == item:found = Trueelse:if item < alist[midpoint]:last = midpoint-1else:first = midpoint+1return found(a) (5 points) What is the runtime of the iterative version in terms of n, and why?(b) (7 points) Write a concise proof of correctness for the algorithm.3. (20 points) Uncoordinated Peak FindingConsider the Peak finding problem discussed in lecture (also refer to Problem 1 inPart B). An excited 6.006 student comes up with the following algorithm to solve theproblem:1 Let n = len(row(B)). Find the maximum element of the (n/2)thcolumn and callit cmax= 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[1..n][1..n/2-1] else B=B[1..n][n/2+1..n]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[1..n/2-1][1..n/2-1] else B=B[n/2+1..n][1..n/2-1]7 goto Step 1.(a) (10 points) Give a counterexample (an instance of B of size less than 7×7) wherethe above algorithm fails to find a peak in B even though it exists.(b) (10 points) We can fix the above algorithm by keeping track of the runningmaximum runmaxas below. Explain how i t solves the problem in the previouscounterexample.Handout 2: Problem Set 131 runmax= −∞2 Let n = len(row(B)). Find the maximum element of the (n/2)thcolumn andcall it cmax= B[i][n/2]3 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[1..n][1..n/2-1] else B=B[1..n][n/2+1..n]7 Else /* Update B to be the partition of B containing runmax*/8 If runmax∈ B[1..n][1..n/2−1] then B = B[1..n][1..n/2-1] else B=B[1..n][n/2+1..n]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[1..n/2-1][1..n/2] else B=B[n/2+1..n][1..n/2]14 Else /* Update B to be the partition of B containing runmax*/15 If runmax∈ B[1..n/2][1..n/2 − 1] thenB = B[1..n/2][1..n/2-1] else B =B[n/2+1..n][1..n/2-1]16 goto Step 2.Part B: Due Thursday, September 24th1. (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, thereis only one 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 tocompute.• (20 points) Write quickfind 1d peak to compute any peak of array A inO(log(n)) time using the algorithm described in the lecture.Now consider a two dimensional matrix B of integers of size n × n. We defineneighborhood of an element x = B[i][j] as B[i + 1][j], B[i − 1][j], B[i][j + 1] andB[i][j − 1]. For elements at the b oundary, we consider only three neigbors and for4Handout 2: Problem Set 1elements on the 4 corners, only two neighbors are considered. x is defined to be apeak of B if and only if it is greater than or equal to all of its neighbours. Note thatthe maximum element of B is a possible solution for x but that requires Ω(n2) time.For python coding help, the O(n log (n)) algorithm describ ed in the lecture is pro-vided as mediumfind 2d peak.• (30 points) Write quickfind 2d peak to compute any peak of array B inO(n) time using the algorithm described in the
View Full Document
Unlocking...