CSC373 – Problem Set 5
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside of your group, the course notes, and the course staff, that you consulted.
Problem Set: due December 3, 2016 22:00
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity.
Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question are contained in the [square brackets].
You may work in groups of up to THREE to complete these questions.
Please be concise and accurate in your responses. Short, accurate algorithmic descriptions are worth more than long, vague
or unnecessarily complicated explanations.
1 Flow Approximation
Here is an algorithm to consider for maximum-flow.
algorithm(G, s, t): for each edge (u, v) in E:
f(u, v) = 0 while there exists a path from s to t in G:
let p be a shortest path from s to t in G
cf(p) = min {cf(u, v) : (u, v) on p}
for each edge (u, v) on p:
f(u, v) = f(u, v) + cf(p)
This algorithm is incorrect (it does not necessarily produce a maximum flow).
[5 marks] Does this algorithm have a finite approximation ratio, or is the algorithm an arbitrarily-bad approximation algo- rithm? Provide a proof to support your choice.
2 Gold Bars
You have a knapsack of weight capacity W, and n gold bars with weights w1,w2,…,wn. The goal is to maximize the weight of the gold placed in the knapsack subject to the W weight capacity constraint.
This problem is NP-complete.
[5 marks] Give pseudocode for a polynomial, 2-approximation algorithm for this problem. Prove that your algorithm runs in polynomial-time and is a 2-approximation algorithm.