Homework 1 (assigned January 10, due January 16)

Reading: CLRS chapter 25. Reading for next week's lecture: CLRS chapter 26.

Written assignment: Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in.
Note: You are responsible for the material covered in both "Do" exercises and assigned problems.
Note: If you work with others, indicate their names at the top of your homework paper. Everyone must submit their own independently written solutions.

"Do" Exercises (not to be handed in):

1. Exercise 25.1-10, page 693. Argue that your algorithm is correct. Analyze its time and space requirements.

2. Exercise 25.2-3, page 699.

3. Compute the transitive closure of the following graph, using the algorithm on page 698. Overwrite the intermediate matrices, as done in class.
   

4. Exercise 25.2-8, page 700.

5. Exercise 25.3-1, page 704. Use the following graph instead of Figure 25.2.
   

6. Exercise 25.3-2, page 705.

7. Exercise 25.3-3, page 705.

8. Exercise 25.3-6, page 705.

Assigned Problems (to be handed in):

• For each problem that requires you to write an algorithm, give an English description of your algorithm, describe your algorithm in pseudocode, analyze its running time, and argue for its correctness. Your argument should be precise, i.e., rigorous enough to be converted to a formal argument if required.
• When describing an algorithm in pseudocode, explain the meaning of your variables in English. Comment the lines of your pseudocode. Your pseudocode should be short, clear, and complete to receive full credit. If your code is long, difficult to read, or incomplete, you will not receive full credit.

1. Problem 25-1, page 705.
   • part a, write pseudocode. (5 points)
   • part b, explain why your example requires Ω(V²) time. (3 points)
   • part c, write pseudocode (8 points); argue for O(V³) time bound (4 points).

2. Problem 25-2, page 706. (5 points for each part)

3. You are given a weighted, directed graph G = (V, E), in which each edge has a weight between 0 and 1, i.e. for all (u, v) in E, 0 ≤ w(u, v) ≤ 1. We call a directed cycle with m edges costly if the sum of the weights of the edges in the cycle is > m − 1.
   • Give an O(V³) algorithm to find the minimum-cost directed cycle in G. Assume that G contains no self-loops, so that a directed cycle contains at least two edges.
     • Describe your algorithm in pseudocode. (8 points)
     • Argue that your algorithm is correct. (1 point)
     • Justify the time complexity of your algorithm. (1 point)
   • Give an O(V³) algorithm to determine whether G contains a costly cycle.
     • Describe your algorithm in pseudocode. (6 points)
     • Argue that your algorithm is correct. (3 points)
     • Justify the time complexity of your algorithm. (1 point)

4. We define a directed graph G′ to be edge-parsimonious if among all directed graphs with the same transitive closure as G′, graph G′ has a minimum number of edges. Given a directed acyclic graph G = (V, E), give an efficient algorithm that finds an edge-parsimonious graph G′ with the same transitive closure as G. Maximum points for the most efficient algorithms.
   • Describe your algorithm in pseudocode. (8 points)
   • Analyze the running time of your algorithm. (2 points)