Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Srini Devadas and Constantinos Costis Daskalakis September 15th 2009 Handout 2 Problem Set 1 This problem set is divided into two parts Part A problems are theory questions and Part 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 or scanned 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 correct solution which is described clearly Convoluted and obtuse descriptions might receive low marks even when 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 22nd 1 18 points Asymptotic Growth For each group of six functions below rank the functions by increasing order of growth that is find an arrangement g1 g2 g6 of the functions satisfying g1 O g2 g2 O g3 g5 O g6 Partition each list into equivalence classes such that 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 106006 n2 f2 n 1 n f3 n n6 006 f4 n n f5 n 1 6 006 f6 n 6 006n b 6 points Group 2 n f1 n n log n f2 n log log n f3 n 50 f4 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 1 f4 n 4n f5 n n f6 n 3 n 2 12 points Binary Search Binary search is a fast algorithm used for finding membership of an element in a sorted list The iterative version of the algorithm is given below The function takes a sorted list of numbers alist and a query item and returns true if and only if item alist Let n denote the length of the list alist Handout 2 Problem Set 1 2 def binarySearch alist item first 0 last len alist 1 found False while first last and not found midpoint first last 2 if alist midpoint item found True else if item alist midpoint last midpoint 1 else first midpoint 1 return 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 Finding Consider the Peak finding problem discussed in lecture also refer to Problem 1 in Part B An excited 6 006 student comes up with the following algorithm to solve the problem 1 Let n len row B Find the maximum element of the n 2 th column and call it cmax B i n 2 2 If cmax B i n 2 1 and cmax B i n 2 1 return cmax 3 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 th row 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 rmax 6 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 21 7 goto Step 1 a 10 points Give a counterexample an instance of B of size less than 7 7 where the 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 running maximum runmax as below Explain how it solves the problem in the previous counterexample Handout 2 Problem Set 1 3 1 runmax 2 Let n len row B Find the maximum element of the n 2 th column and call it cmax B i n 2 3 If cmax runmax then 4 If cmax B i n 2 1 and cmax B i n 2 1 then return cmax 5 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 th row of B and call it rmax B n 2 j 10 If rmax runmax then 11 If rmax B n 2 1 j and rmax B n 2 1 j return rmax 12 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 24th 1 50 points Peak Finding Consider an array A containing n integers We define a peak of A to be an x such that x 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 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 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 two dimensional matrix B of integers of size n n We define neighborhood of an element x B i j as B i 1 j B i 1 j B i j 1 and B i j 1 For elements at the boundary we consider only three neigbors and for 4 Handout 2 Problem Set 1 elements on the 4 corners only two neighbors are considered x is defined to be a peak of B if and only if …
View Full Document
Unlocking...