College of Computer & Information Science Fall 2006 Northeastern University Handout 10 CSU690: Algorithms and Data 13 October 2006

Problem Set 4 (due Tuesday, October 24)

1. (5 + 5 = 10 points) Uniqueness of MSTs when all weights are distinct

• Suppose T_{1} and T_{2} are distinct minimum spanning trees for graph G. Let (u, v) be the lightest edge (smallest weight edge) among all edges that are in T_{1} and but not in T_{2}. Let (x, y) be any edge that is in T_{2} and not in T_{1}. Show that w(x, y) ≥ w(u, v).

• Prove that if the weights on the edges of a connected, undirected graph are distinct, then there is a unique minimum spanning tree.

2. (6 + 6 = 12 points) Bottleneck MSTs

Chapter 4, Exercise 9, page 192.

3. (2 + 10 = 12 points) Nesting boxes

We are given a set of n empty boxes B_{i} = (h_{i}, w_{i}, ℓ_{i}), 1 ≤ i ≤ n, where h_{i}, w_{i}, and ℓ_{i} denote the height, width, and length of box B_{i}. Let us say that box B_{i} nests within box B_{j} if and only if box B_{i} can be oriented so that it is strictly smaller than box B_{i} in each corresponding dimension. For example, even though the box B_{i} = (5, 1, 1) is taller than the box B_{j} = (2, 6, 3), B_{i} can be placed inside B_{j} by orienting it as a (1, 5, 1).

(a) Describe an O(1) time algorithm to determine whether one box nests within another.

(b) We would like to compute the maximum length k of a sequence of boxes B_{i_{1}}, …, B_{i_{k}} such that B_{i_{j}} nests inside B_{i_{j+1}}, 1 ≤ j < k. Design and analyze a polynomial-time algorithm for the problem. (Hint: One can use either dynamic programming or express the problem as a shortest-path problem in a suitably defined graph.)

4. (13 points) Word segmentation

Chapter 6, Exercise 5, page 316.

5. (13 points) Defending against robot attacks

Chapter 6, Exercise 8, page 319.