Do not infer anything about the scope or length of the exam from this collection of practice problems.
Solutions are available.
Problem 0: Review old homework assignments.
Problem 1: Write a method called MAJORITY-5 that takes as its input an array of five 0's and 1's and returns 0 if there are more 0's than 1's in the array and 1 otherwise. Assuming that each input is equally likely, what is the expected number of array accesses your method performs? (If your answer is 5 then rewrite your algorithm so the expected number of accesses is less than 5.)
Problem 2: Suppose that you have run the Matrix Chain Multiplication algorithm to find the optimal way to parenthesize A1 * ... * An but you have lost the s array. Show that it is still possible to recover the optimal parenthesization in O(n2) time using just the m array.
Problem 3: Devise an algorithm that, given an array of n numbers and k, finds the elements of rank 1, k+1, 2k+1, .... What is the asymptotic running time of your algorithm in terms of n and k?