Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Konstantinos Daskalakis and Patrick Jaillet September 13 2010 Problem Set 1 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 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 in PDF form using LATEX or scanned handwritten solutions Your solution to Part B should be a valid Python 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 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 21st 1 18 points Asymptotic Growth For each group of four functions below rank the functions by increasing order of growth that is find an arrangement g1 g2 g3 g4 of the functions satisfying g1 O g2 g2 O g3 g3 O g4 For example the correct ordering of n n2 n3 n4 is n n2 n3 n4 a 6 points Group 1 f1 n n2n f2 n 2n 2 f3 n n f4 n n e n b 6 points Group 2 f1 log n 1000 f2 n1 2 f3 1 n f4 n6 006 c 6 points Group 3 f1 n n 100 1 n f4 n log log n f2 n n log n f3 n n 100 2 12 points Binary Search Binary 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 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 2 Problem Set 1 def binarySearch alist item if len alist 0 return False else midpoint len alist 2 if alist midpoint item return True else 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 wish to use a loop invariant for your proof See section 2 1 of CLRS for an example 3 20 points Uncoordinated Peak Finding Recall the 2 dimensional Peak finding problem discussed in lecture Consider the following algorithm 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 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 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 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 0 n 2 1 0 n 2 1 else B B n 2 1 n 1 0 n 21 7 goto Step 1 a 10 points Give a counterexample an instance of B of size no larger than 7 7 where the above algorithm fails to find a peak in B even though it exists If your example is 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 maximum runmax as 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 th column and call it cmax B i n 2 Problem Set 1 3 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 0 n 1 0 n 2 1 else B B 0 n 1 n 2 1 n1 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 n1 n 2 1 n 1 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 0 n 2 1 0 n 2 else B B n 2 1 n1 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 23rd 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 three dimensional matrix B of integers of size n n n We define the neighborhood of an element x B i j k as B i 1 j k B i 1 …
View Full Document
Unlocking...