Problems
1. (25 pts) Following the notes/slides/book, explain All-Source-Shorthest-Paths by edges DP using matrix multiplication trick. Write pseudocode for ASSP-Fast and the corre-sponding Extending-SP procedures.
2. (25 pts) Exercise 24.1-3.
3. (25 pts) Exercise 24.2-2.
4. (25 pts) Exercise 24.3-4.
5. (Extra credit 30 pts) Problem 24-2.
6. (30 pts) Explain in few lines the concept of transitive closure.
7. (20 pts) Exercise 25.1-6 (the book uses di erent notation for the matrices). Also explain how to use this result in order to display all-pair shortest paths, enumerating intermediary vertices (or edges) for each path.
8. (20 pts) Exercise 25.2-1.
9. (20 pts) Exercise 25.2-4.
10. (25 pts) Exercise 25.2-6. (Extra Credit)
1
