CS 330

Summer 2007

Assignment #5

Date Due: Tuesday, June 26

Reading: Chapter 35, pages 1022-1039.

Problems:

1. Carry out the dynamic programming RNA algorithm on the sequence of bases A G G C A C C U G C A U A G C U C U to find the maximum number of legal matchings in this sequence.

2. Carry out the dynamic programming TSP cycle for the graph below to find the minimum weight TSP cycle through the graph.

Graph to be handed out in class.

3. Problem 26.1-5 on page 650.

4. Problem 26.2-3 on page 663.

5. Problem 26.3-1 on page 668.

6. Suppose G is a connected flow graph with integer capacities and that a maximum flow through G is known.

a. Suppose one edge weight in the flow graph (that is, some capacity) is increased by 1. Give an O(E) time algorithm to update the max flow of G.

b. Suppose one edge weight in the flow graph is decreased by 1. Give an O(E) time algorithm to update the max flow of G.

7. Problem 26.2-8 on page 664

8. Problem 26-2 on page 692