MS&E 217/317, Combinatorial Optimization, Autumn 2003-04.Instructor: Ashish Goel

Handout 5

Practice Problems for the Midterm (Please do not assume that material not covered by these problems is not kosher for the midterm)

1. Matroids: MS&E 317 students will have a choice of answering a matroid question.

(a) Problem 8.6

(b) Problem 8.8

(c) An alternative definition that we could use for a matroid keeps the same M0 and M1, but uses the following property M2’ as opposed to the property M2 discussed in the class and in the text:

(M2’) If A,B are both in I, and |A| < |B|, then there exists an element e in B-A such that A U {e} is also in I.

This is called the exchange property. Prove that this is an equivalent definition of a matroid.

2. Spanning Trees.

(a) Give an algorithm to find a spanning tree of a weighted, undirected graph which minimizes the maximum weight edge in the tree.

(b) Problem 2.10.

3. Shortest Path Trees.

(a) Problem 2.18.

(b) Problem 2.22.

(c) Problem 2.24.

(d) How would you modify Bellman-Ford to not just find whether a negative cycle exists, but also to output the negative cost cycle?

4. Dynamic Programming:

(a) There are n villages situated along the river Amazon. Let x_1, x_2, … x_n represent the positions of these villages along the river. Assume that the (i+1)-th village is downstream from the i-th village, i.e., j > i => x_j > x_i. A motorized ferry runs along the river, and the plan is to choose k villages to construct ferry stations. If there is no ferry station in a village, the villagers must use pedal boats to go to the next downstream station. Let d_i denote the distance from the i-th village to the nearest downstream station, and let D = d_1 + d_2 + …. + d_n. Give an efficient algorithm to find the minimum possible value of D as well as the choice of the k villages which results in this minimum value. Analyze the running time of your algorithm.

(b) A total of n-1 stepping stones were placed at one meter intervals across a river that is n meters wide. Over time, some of these stones got washed away. For 1 <= i <= n-1, A[i] = 1 if the i-th stepping stone is still there, and A[i] = 0 if this stone got washed away. A baby kangaroo wants to cross this river. Unfortunately the kangaroo can make only two kinds of jumps -- either k_1 meters or k_2 meters. You are given n, A, k_1, k_2 as input. Write a dynamic programming formulation to find out whether the kangaroo can cross the river, and if yes, the minimum number of leaps it needs to make. What is the running time of your algorithm? Assume that the kangaroo must start jumping from the bank i.e. from the point i = 0 and is allowed to land anywhere on the opposite side i.e. at any i >= n. Is this a polynomial time algorithm?