Description
Problems
-
(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.
-
(25 pts) Exercise 24.1-3.
-
(25 pts) Exercise 24.2-2.
-
(25 pts) Exercise 24.3-4.
-
(Extra credit 30 pts) Problem 24-2.
-
(30 pts) Explain in few lines the concept of transitive closure.
-
(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.
-
(20 pts) Exercise 25.2-1.
-
(20 pts) Exercise 25.2-4.
-
(25 pts) Exercise 25.2-6. (Extra Credit)
1
