You are given functions f and g such that f(n) = O(g(n)). Is f(n) log2(f(n)) = O(g(n) log2(g(n))) ? (Here cis some positive constant.) You should assume that f and g are nondecreasing and always bigger than 1.

Assume again two (positive) nondecreasing functions f and g such that f(n) = O(g(n)). Is 27(n) = O(29(n)) ? (Multiple answers may be correct, you should check all of those that apply.)

K-way-Merge Sort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, then merge the 4th given array with the merged version of the first three arrays, and so on until you merge in the final (kth) input array. What is the running time taken by this successive merging algorithm, as a function of k and n? (Optional: can you think of a faster way to do the k-way merge procedure ?)

Arrange the following functions in increasing order of growth rate (with g(n) following f(n) in your list if and only if f(n) = O(g(n)))

• a)22 n

• b)2 n2

• c)n2 log(n)

• d)n

• e)n2 n

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 7 T(n / 3) +n2. What’s the overall asymptotic running time (i.e, the value of T(n))?

• Ө(n2 log n) 

• Ө(n2)

• Ө(n2.81)

• Ө(n log n)

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 9T(n / 3) +n2. What’s the overall asymptotic running time (i.e, the value of T(n))?

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 5T(n / 3) +4n. What’s the overall asymptotic running time (i.e, the value of T(n))?

Consider the following pseudocode for calculating a where a and bare positive integers)  

FastPower(a,b) :    if b = 1        return a  else    c : = a*a   ans := Fast Power(c,[b/2])  if b is odd      return a*ans  else return ans end

Choose the smallest correct upper bound on the solution to the following recurrence T(1) = 1 and T (n) ≤ T( [√n]) +1 for n > 1. Here [x] denotes the “floor” function, which rounds down to the nearest integer. (Note that the Master Method does not apply.)

Let 0 < a <.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is ≥ a times the size of the original array?

Define the recursion depth of QuickSort to be the maximum number of successive recursive calls before it hits the base case — equivalently, the number of the last level of the corresponding recursion tree. Note that the recursion depth is a random variable, which depends on which pivots get chosen. What is the minimum-possible and maximum-possible recursion depth of QuickSort, respectively?

Consider a group of k people. Assume that each person’s birthday is drawn uniformly at random from the 365 possibilities. (And ignore leap years.) What is the smallest value of k such that the expected number of pairs of distinct people with the same birthday is at least one?

[Hint: define an indicator random variable for each ordered pair of people. Use linearity of expectation.]

• Let X1, X2, X3 denote the outcomes of three rolls of a six-sided die. (l.e., each Xi  is uniformly distributed among 1,2,3,4,5,6, and by assumption they are independent.) Let Y denote the product of X1 and X2 and Z the product of X2 and X3. Which of the following statements is correct?

How many different minimum cuts are there in a tree with n nodes (ie. n – 1 edges)?

Let “output” denote the cut output by Karger’s min cut algorithm on a given connected graph with n vertices, and let p =1/(n2) . Which of the following statements are true? 

For hints on this question, you might want to watch the short optional video on “Counting Minimum Cuts”.

Let .5< a < 1 be some constant. Suppose you are looking for the median element in an array using RANDOMIZED SELECT (as explained in lectures). What is the probability that after the first iteration the size of the subarray in which the element you are looking for lies is ≤ a times the size of the original array?

The minimum s-t cut problem is the following. The input is an undirected graph, and two distinct vertices of the graph are labelled “s” and “t”. The goal is to compute the minimum cut i.e., fewest number of crossing edges) that satisfies the property that s and t are on different sides of the cut.

Suppose someone gives you a subroutine for this s-t minimum cut problem via an API. Your job is to solve the original minimum cut problem (the one discussed in the lectures), when all you can do is invoke the given min s-t cut subroutine. (That is, the goal is to reduce the min cut problem to the min s-t cut problem.)

Now suppose you are given an instance of the minimum cut problem — that is, you are given an undirected graph (with no specially labelled vertices) and need to compute the minimum cut. What is the minimum number of times that you need to call the given min s-t cut subroutine to guarantee that you’ll find a min cut of the given graph? 

Recall the Partition subroutine that we used in both QuickSort and RSelect. Suppose that the following array has just been partitioned around some pivot element: 3, 1, 2, 4, 5, 8, 7, 6,9

Which of these elements could have been the pivot element? (Hint: Check all that apply, there could be more than one possibility!)

Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4

Suppose we run Merge Sort on this array. What is the number in the 7th position of the partially sorted array after the outermost two recursive calls have completed (i.e., just before the very last Merge step)? (When we say “7th” position, we’re counting positions starting at 1; for example, the input array has a “0” in its 7th position.)

What is the asymptotic worst-case running time of MergeSort, as a function of the input array length n?

What is the asymptotic running time of Randomized QuickSort on arrays of length n, in expectation over the choice of random pivots) and in the worst case, respectively?

Let f and g be two increasing functions, defined on the natural numbers, with f(1),g(1) ≥1. Assume that f(n) =O(g(n)). Is 2f(n) ) = 0(29(n)) ? (Multiple answers may be correct, check all that apply.)

Let 0 < a <.5 be some constant. Consider running the Partition subroutine on an array with no duplicate elements and with the pivot element chosen uniformly at random (as in QuickSort and RSelect). What is the probability that, after partitioning, both subarrays (elements to the left of the pivot, and elements to the right of the pivot) have size at least a times that of the original array?

Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Divide the k arrays into k/2 pairs of arrays, and use the Merge subroutine taught in the Merge Sort lectures to combine each pair. Now you are left with k/2 sorted arrays, each with 2n elements. Repeat this approach until you have a single sorted array with kn elements. What is the running time of this procedure, as a function of k and n?

Running time of Strassen’s matrix multiplication algorithm: Suppose that the running time of an algorithm is governed by the recurrence T(n) = 7T(n/2) + n2. What’s the overall asymptotic running time (i.e., the value of T(n))?

Recall the Master Method and its three parameters a, b, d. Which of the following is the best interpretation of ba, in the context of divide-and-conquer algorithms?