HOMEWORK 7

Background material: Ch. 23.1, 23.4, 23.5.

Due November 5th:

• 7.1: CLR Exercise 23.1-3 (pg. 468).

• 7.2: Say we can get dressed in parallel. That is, imagine that any piece of clothing that depends only on clothing currently being worn can be put on all at once in unit time. Describe an efficient algorithm for computing the ``makespan'' of a DAG. This is minimum amount of time it would take to get dressed in parallel. Hint: Draw some DAGs and work out their makespans by hand. The calculation you need to perform fits very naturally with the topological sort algorithm.

• 7.3: CLR Exercise 23.5-5 (pg. 494).

• 7.4: Give a O(|V|+|E|) (linear time) algorithm for maximal (not maximum) bipartite matching.

• 7.5: (a) Give an example bipartite graph with 2k left nodes and 2k right nodes with a maximal matching of size k and a maximum matching of size 2k. (b) The ratio of the size of the maximum matching to the maximal matching is 2:1 in the previous construction. Prove that this is the largest possible ratio. We can conclude from this that a maximal matching is an approximation (to within a factor of 2) of the maximum matching. Hint: Consider a maximum matching. What can we say about the vertices in this matching, with respect to any maximal matching? [Extra Credit.]

• 7.6: Modify the code in lect16.cc to compute the makespan. Test it on the clothing graph that is currently in the code, as well as the DAG on page 487 of the book. This is due November 12th.