Assignment 3: Divide-and-Conquer

EECS 340/454: Algorithms 
Assignment 3: Divide-and-Conquer

Problem 1
Let 0 < λ < 1 < a < b be constants. Solve the following recurrences using Master Method, noting
the case that applies.
(a) T(n) = bT(n/a) + Θ(n).
(b) T(n) = a
2T(n/a) + Θ(n
2
).
(c) T(n) = T(λn) + n
λ
.
(d) T(n) = aT(n/a) + Θ(n
λ
(log n)
b
).
Problem 2
Prove the solutions to the following recurrences using Substitution Method:
(a) For any constant 0 < α < 1, if T(n) = T(αn) + T((1 − α)n) + Θ(n), then T(n) = O(n log n).
(b) For any constant k > 0, if T(n) = Θ(n) + Pk
i=1 T(n/2
i
), then T(n) = O(n).
Problem 3
Dr. Purplesheep discovered a new class of materials, which are useful in converting solar energy to
electrical energy. She has designed 25 unique materials that belong to this class, and she would like
to identify the top 3 out of these 25 materials in terms of their effectiveness. Unfortunately, however,
she does not have an experimental method that can be used to quantify the effectiveness of a given
material. Instead, she can run comparative experiments such that each experiment provides a
ranking of 5 materials in terms of their effectiveness (from most effective to least effective). Running
these experiments is rather expensive, so she would like to minimize the number of experiments she
runs. Can you help her design a strategy that will identify the 3 most effective materials among
25 materials by performing the minimum number of experiments? What is the minimum number
of experiments needed to conclusively determine the 3 most effective materials? You do not need
to write pseudo-code; a verbal explanation, possibly supported by graphics, will suffice.
Example. Suppose Dr. Purplesheep performs an experiment on materials M3, M7, M9, M14, M25.
Then, the result of the experiment will be a ranking such as: M14 > M3 > M25 > M7 > M9.
Problem 4
We are given a dictionary D, which is an array of n distinct strings, sorted in lexicographic order.
We are also given a procedure Compare-Strings(x, y), which will compare two strings x and y
in Θ(1) time, and return true if x comes before y, and false if y comes before x in lexicographic
order. We are also given an array C, which contains n−1 of the n strings in D, but C is not sorted.
We would like to develop an algorithm that will find the string that is missing in C.
(a) Design a divide-and-conquer algorithm that will find the missing string in Θ(n) time. You
can assume that we can utilize the Partition algorithm that is used by QuickSort, by
modifying it to compare strings instead of comparing numbers (you do not need to show how
to do the modification). Write the pseudo-code of your algorithm and explain how it works.
(Hint: You can select the pivot used for Partition algorithm in an informed manner that
guarantees the resultant subarrays to be of nearly equal size.)
(b) Show that the runtime of your algorithm is Θ(n).
Example. Suppose D = {”W”, ”X”, ”Y ”, ”Z”} and C = {”Y ”, ”Z”, ”W”}. D contains n = 4
strings and C contains all n − 1 = 3 strings in D except ”X”. Thus, missing string in C is: ”X”.