Problem Set

1. [6] Here is a version of binary search that returns the index of the element if it is found, or -1 if the element is not found.

1 def binary_search (A , x ):

2 '''

3 Pre : list A is sorted in ascending order and has no duplicate elements

4 Post : return the index of x in A if exists ; return -1 otherwise .

5 '''

6 if len ( A ) == 0:

7 return -1

8 m = len ( A )//2

9 if A [ m ] == x :

10 return m

11 elif A [ m ] > x :

12 return binary_search ( A [0.. m -1] , x )

13 else :

14 result = binary_search ( A [ m +1.. len ( A ) -1] , x )

15 if result == -1:

16 return -1

17 else :

18 return result + m + 1

(a) Write the recurrence for the worst-case runtime T(n) of the algorithm, and use the master theorem to find the asymptotic upper-bound on T(n). State clearly which case of the master theorem applies.

(b) Prove that this algorithm is correct.

2. Below is the mystery algorithm that we worked on in Problem Set.

1 def mystery ( lst ):

2 if len ( lst ) <= 1:

3 return

4 if lst [0] > lst [ -1]:

5 lst [0] , lst [ -1] = lst [ -1] , lst [0]

6 if len ( lst ) >= 3:

7 split = len ( lst ) // 3

8 mystery ( lst [0.. len ( lst ) - split - 1])

9 mystery ( lst [ split .. len ( lst ) - 1])

10 mystery ( lst [0.. len ( lst ) - split - 1])

We analyzed that the recurrence of the worst-case runtime of this algorithm is the following.

Some students have already realized that this algorithm is in fact a sorting algorithm. So in this problem set we will formalize our understanding of this interesting sorting algorithm.

(a) Find the asymptotic upper-bound on the worst-case runtime of mystery using the master theorem. State clearly which case of the master theorem applies.

(b) State the proper precondition and postconditi on for the mystery function. Note: "proper" precondition means that it is necessary and sufficient for the algorithm to work correctly. In particular, don't add unnecessary conditions.

(c) Prove that mystery is correct according to the precondition and postcondition that you specified in (b). Note: Be careful when finding the possible program paths, and state clearly which lines of code are executed for each program path (use the line numbers).

Assignment - Please follow all the instructions and write step by steps

http://www.cs.toronto.edu/~ylzhang/csc236/files/ps6.pdf

Lecture Notes

http://www.cs.toronto.edu/~ylzhang/csc236/files/lec07-master-theorem-correctness.pdf

http://www.cs.toronto.edu/~ylzhang/csc236/files/lec08-loop-invariant.pdf