- (50 points) Problem 1. Recurrences.
Assume that given a problem, we come up with
3 different divide-and-conquer algorithms to solve the
problem:
- Algorithm I: finds a solution to its input problem by
dividing it into 5 subproblems, each of half the size of its input problem,
recursively solves each of these 5 subproblems, and then combines their
solutions to form the solution of the input problem in linear time (= n).
- Algorithm II: finds a solution to its input problem of
size n by recursively solving 2 subproblems of size n-1, and then
combines their solutions to form the solution of the input problem in
constant time.
- Algorithm III: finds a solution to its input problem of
size n by recursively solving 9 subproblems of size n/3, and then
combines their solutions to form the solution of the input problem in
quadratic time (= n2).
- (10 points, 3.3 for each recurrence)
Write a recurrence for the runtime T(n) of each
of the algorithms above.
Assume that the base case T(1) runs in constant time.
- (39 points) Solve each recurrence.
That is, for each recurrence, find a function g(n) such that T(n) is O(g(n))
(the tighter the upper bound, the better), following the directions below:
- (9 points, 3 for each recurrence)
Use the master theorem, if applicable. Explain your work.
- (30 points, 10 for each recurrence)
In addition,
use either the recursion-tree method (= "unrolling" the recurrence),
or the substitution method (= "guess + induction") to provide another
proof of the result.
To make sure you practice with all these methods,
you must use the recursion-tree method for at least one of the 3 recurrences,
and the substitution method for at least one of the 3 recurrences.
- (1 point) Everything else being equal, which one of the 3 algorithms
would you choose to solve the problem? Explain your answer.
- (80 points) Problem 2. Multi-Merge.
Consider the merge procedure used in MergeSort. It receives
two sorted arrays each of n elements, and outputs a single array
of size 2n containing all the elements of the two input arrays
sorted in the right order. merge runs in linear time O(n).
In this problem, we'll create an extended version of this merge
procedure, called multi-merge that receives k sorted arrays
(where k is a variable)
each of size n, and returns a single array
of size kn containing all the elements of the k input arrays
in the right order.
- Strategy I.
Consider solving this problem by calling the merge procedure from
MergeSort
to merge the first 2 input arrays, and then call it again to merge this
resulting array with the 3rd input array, and then this resulting array
with the 4th input array, and so on until you're done merging all the k arrays.
(Assume that merge works as expected even if the 2 input arrays are not
of the same size).
Let's call this algorithm naive-multi-merge.
- (10 points)
Construct the runtime function T(n,k) for naive-multi-merge.
Explain your work.
- (10 points)
Calculate the time complexity of this algorithm in terms of k and n.
That is, provide a function g(n,k) such that the
runtime T(n,k) of this algorithm is O(g(n,k)).
Explain your work.
- Strategy II.
Provide a more efficient, divide-and-conquer approach to solve this
problem.
Let's call your algorithm smart-multi-merge.
This algorithm uses the merge function, but it is smarter than
naive-multi-merge about what pairs of arrays to merge.
If convenient, assume that k is a power of 2.
- (5 points)
Explain your algorithm design clearly.
- (10 points)
Write your smart-multi-merge algorithm in detailed pseudo-code.
Your pseudo-code should make calls to the function merge.
- (10 points)
Prove that your algorithm is correct.
That is, you need to show that for all inputs:
(1) your algorithm terminates; and
(2) it produces the correct output.
You can assume that the merge algorithm is correct,
since its correctness is proven in section 2.3.1 of the textbook.
- (5 points)
Write a recurrence for the runtime
T(n,k) of the algorithm.
- (10 points)
Solve the recurrence. That is, find some function
g(n,k) such that T(n,k) is O(g(n,k))
(the tighter the upper bound, the better).
For this, either use the recursion-tree method (= "unrolling" the recurrence),
the substitution method (= "guess + induction"), or the master theorem.
Show your work and explain your answer.
- Python Implementation.
- (5 points) merge Implementation.
Implement the merge function in Python.
This function should receive two sorted lists as input and output a third
list with the elements in the the two lists sorted in ascending order.
(Note that to simplify life, the returned list will be a new list,
not any of the two input lists.)
You can reuse the merge part of the mergeSort code available at
mplemented in the online textbook
Problem Solving with Algorithms and Data Structures
by Brad Miller and David Ranum.
- (5 points) naive-merge Implementation.
Implement naive-multi-merge in Python.
- (5 points) smart-merge Implementation.
Implement your smart-multi-merge algorithm in Python.
- (5 points) Runtime evalution.
Compare the runtime of naive-multi-merge and smart-multi-merge
on the following inputs:
- n = 100, k = 16. That is, merging 16 lists of size 100 each.
Make each of these lists equal to [0,1,...,n-1].
- Same as above, but with the following values for n and k:
n = 100, 200, 300, 400, 500.
For each value of n above, k = 16, 32, 64, 128, 256, 512
(you might have to stop earlier if your machine runs out of memory).
- Include your results in your written reports.
- Provide plots/visualizations of your results and your observations
about these results.
- (20 points) Problem 3. Base of a logarithm.
State whether the base of a logarithmic expression in
each of the cases below can be ignored or not.
That is, whether the particular base of the logarithm
(log2, log10, ln, ...)
makes a difference or not.
If it can be ignored, prove it rigorously.
If it cannot be ignored, show an example in which the base of the
logarithm makes a difference.
- (5 points)
O(loga n), where a is a constant greater than 1.
That is, you need to show whether or not:
O(loga n) = O(logc n), for any constants a and c greater than 1.
- (5 points)
O(nlogab), where a and b are constants greater than 1.
That is, you need to show whether or not:
O(nlogab) = O(nlogcb),
for any constants a, b, and c greater than 1.
- (5 points)
O(logf(n) n), where f(n) is any function of n
(e.g., f(n) = √ n).
For this part, show whether or not:
O(logf(n) n) = O(logc n),
where f(n) is any function of n,
and c is any constant greater than 1.
- (5 points)
O(loga n), where a is a constant between 0 and 1.
For this part, show whether or not:
O(loga n) = O(logc n),
a is a constant between 0 and 1, and
and c is any constant greater than 1.
Note: The same results you obtained above for Big-Oh, apply also to Big-Omega
Ω and Big-Theta Θ, but you don't need to prove it.