Description
Practicing Chapter 5 (DC) and 6 (DP)
1. (15 Points) Asymptotic running time of divide-and-conquer algorithms:
(a) (10 Points) Master Theorem. If T(n) = aT(n/b) + O(nd) for some constants a >
0, b > 1, d ≥ 0, then prove that it is:
T(n) =
!
“#
“$
O(nd) if d > logba
O(ndlogn) if d = logba
O(nlogba) if d < logba
(b) (5 Points) Then show that the divide-and-conquer algorithms we did in class Mergesort,
Binary Search, Matrix multiplication (classic) and Fast Matrix Multiplication (Strassen)
are all special cases of the Master Theorem. In particular, for each of these problems:
(i) give the parameters a, b, d for each algorithm and (ii) write down the recursive and
closed form equation for T(n).
2. (20 Points) Chapter 5: More recursions: Solve the following recurrence relations and
give a O bound for each of them:
(a) (5 Points) T(n) = 2T(n/3) + 1
(b) (5 Points) T(n) = 5T(n/4) + n
(c) (5 Points) T(n) = 9T(n/3) + n2
(d) (5 Points) T(n) = 2T(n − 1) + 1
3. (5 points) Chapter 6: Dynamic Programming: WIS via DAG Consider the intervals
below, each interval i has start time and a finish time and a weight vi indicated on top of the
interval i in the figure.
1
(a) (2.5 points) First create a DAG for these intervals as follows: Each node represents one
interval. For each interval i add edge (i, p(i)) of the length/weight of vi. You will need
two extra nodes One dummy sink node 0 for interval 0 (Remember in solving WIS we
say that p(1) = 0, so we need to have a dummy 0 interval as a sink node), plus another
dummy source node s connected with the last interval (node) 5. Add an edge from s
to 5 of length 0. For each interval i add edge (i, i − 1) of length 0. Second what is the
running time of creating this DAG, assuming that the intervals were initially sorted.
nlogn
(b) (2.5 points) Now given a general interval problem instance I let and let G(I) denote a
DAG constructed similar to the one you did in the previous problem. You need to find
the optimal solution for the weighted interval scheduling. Can you solve this problem
by running Dijkstra? Why?
4. (30 Points) Chapter 5: Variations of Knapsack Problem: Multidimensional Knapsack. Consider each item i = 1, …n has a weight wi, a volume zi and a value vi. You still
want to choose a subset of the n items so as to maximize total value. However, you now need
to meet two constraints: (1) the total weight of the selected items should not exceed a given
W and (2) the total volume of the selected items should not exceed a given Z.
(a) (10 Points) Design a DP algorithm that finds the optimal solution to this problem.
(b) (5 Points) Prove that your algorithm finds indeed the optimal solution.
(c) (5 Points) Analyze the running time.
(d) (10 Points) Consider the example problem from class: there are n = 5 items with values
{v1 = 1, v2 = 6, v3 = 18, v4 = 22, v5 = 28} and weights {w1 = 1, w2 = 2, w3 = 5, w4 =
6, w5 = 7}; the constraint on the total weight is W = 11. In addition, consider that the
items have volumes {z1 = 1, z2 = 10, z3 = 3, z4 = 2, z5 = 2} and that the total allowed
volume is Z = 15. Apply your algorithm to solve this example.
5. (30 Points) Chapter 5: Variations of Knapsack Problem: Knapsack with Repetition.
(a) (10 Points) Given n types of items (with weights w1, …, wn and values v1, …, vn, respectively), describe a DP algorithm that finds the most valuable set of items, subject to a
total weight constraint W. You are allowed to use repetition, i.e., to use items of the
same type multiple times. What is the asymptotic running time of your solution? Apply
your algorithm to the example with the following n = 4 items and capacity W = 10:
Item i 1 2 3 4
Weight wi 6 3 4 2
Value vi 30 14 16 9
(b) (10 Points) For the above example, draw the graph with nodes the DP subproblems and
edges the dependencies between them. Is it a DAG? Can you re-state this particular
variant of the KP problem as finding a path on this graph?
(c) (10 Points) Implement one of your DP algorithms, in Python, and run it on the example
above. You should submit your code – the grader should be able to run your code
with the input text file (format and example provided on Canvas – see KP all.ZIP and
README therein) and test that it gives the correct output!
2
(a) (10 Points) Given n types of items (with weights w1, …, wn and values v1, …, vn, respectively), describe a DP algorithm that finds the most valuable set of items, subject to a
total weight constraint W. You are allowed to use repetition, i.e., to use items of the
same type multiple times. What is the asymptotic running time of your solution? Apply
your algorithm to the example with the following n = 4 items and capacity W = 10:
Item i 1 2 3 4
Weight wi 6 3 4 2
Value vi 30 14 16 9
(b) (10 Points) For the above example, draw the graph with nodes the DP subproblems and
edges the dependencies between them. Is it a DAG? Can you re-state this particular
variant of the KP problem as finding a path on this graph?
(c) (10 Points) Implement one of your DP algorithms, in Python, and run it on the example
above. You should submit your code – the grader should be able to run your code
with the input text file (format and example provided on Canvas – see KP all.ZIP and
README therein) and test that it gives the correct output!
3
