Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 3511: Algorithms Honors Homework 3
Instructions:
- Upload your solutions to as a single PDF on Gradescope. Please anonymize all your submissions (i.e., do not list your name in the PDF), but if you forget, it’s OK.
- You may collaborate with any classmates, textbooks, any resource on the internet (but don’t search for the problem solution), etc. Please upload a brief “collaboration state ment” listing any collaborators as the last page of your solutions PDF on Gradescope. But after the collaboration, always write your solutions individually.
- For each problem, you should aim to keep your writeup below one page. For some problems, this may be infeasible, and for some problems you may write significantly less than a page. This is not a hard constraint, but part of the assignment is figuring out how to easily convince the grader of correctness, and to do so concisely. “One page” is just a guideline: if your solution is longer because you chose to use figures (or large margins, display math, etc.) that’s fine.
- Each problem is worth ten points (even those with multiple subparts).
Problems:
§1 (Greedy Approximation Algorithms). Later in the course we will see that some of the optimization problems are NP-Hard, so we don’t expect to find the optimal solution in polynomial time. However, variants of the greedy algorithm can still help us obtain approximately optimal solutions in polynomial time.
(a) Suppose you are given a graph G = (V, E). The goal is to find a subset of vertices S ⊆ V of minimum size |S| while ensuring that for every edge (u, v) ∈ E, at least one of u or v is inside S. Let S ∗ denote the optimal solution to this problem. Consider an algorithm that arbitrarily orders the edges of G. Now we find a “greedy” matching M where we start with M = ∅ and add the next edge (u, v) in the ordering to M if both vertices u and v are not matched till now.
i. First prove that the optimal solution S ∗ has size at least |M|.ii. Next, find a subset of vertices S in polynomial time such that |S| ≤ 2|S ∗ | and for every edge (u, v) ∈ E at least one of u or v is inside S. Thus, S gives a 2-approximate solution to this problem.
(b) Suppose you are given n machines and m jobs where the jth job takes time
In the greedy algorithm we consider the jobs in an arbitrary order and schedule the next job on the machine that has the least load currently, breaking ties arbitrarily. Prove that this algorithm gives an O(1) approximation.
§2 (Huffman Coding)
(a) (3 pts) For binary Huffman coding over alphabet size n (which we saw in class), what’s the large length codeword that might be assigned to a single symbol (in Θ(·) notation)? Give an example of a distribution that achieves this bound.
(b) (5 pts) Suppose instead of binary {0, 1}, we are allowed three letters {0, 1, 2} design our prefix-free codeword. Given probabilities p1 ≤ p2 ≤ . . . ≤ pn and if the alphabet size n ≥ 3 is an odd number, give an algorithm (with a short intuition for correctness) to find the codeword with the least expected length.
(c) (2 pts) In part (b), how can we slightly modify the algorithm so that it works when n is an even number?
§3 (Fast Approximate Matching) Suppose we are given a bipartite graph G = ((A, B), E).
(a) Design a Θ(n + m) running time algorithm to find a matching M ⊆ E with the property that every augmenting path has length > 3 (i.e., ≥ 5 since augmenting paths have odd length).
(b) Prove that the above matching has size |M| at least 2/3 fraction of the maximum matching size.
(a) Suppose someone gives you a solution to the max-flow problem on a directed graph. How can you verify in O(n + m) time whether this is the max-flow?
(b) Consider a variant of the max-flow problem where each vertex v of the directed graph also has a maximum capacity cv ≥ 0. The goal is to find max-flow between given vertices s, t while ensuring that every vertex v has at most cv flow entering it. Show how to solve this problem by reducing it in Θ(n+m) time to a max-flow problem without vertex capacities (which we studied in class)?