Computer Science 431
Algorithms
Spring 2015, The College of Saint Rose
Lecture 23: Dynamic Programming Wrapup; Graph Algorithms
Date: Monday, April 20, 2015
Agenda
- Announcements
- Game design expo tomorrow and next week
- Lecture 21 assignment recap
- Problem Set 8: Dijkstra's Road Trip and More [HTML] [PDF] out
- Dynamic programming
- knapsack problem wrapup
- memory functions
- Graph algorithms
- Reachability
- Warshall's algorithm
Lecture 23 Assignment
Due at the start of class, Wednesday, April 22.
Please submit answers to these questions
in Submission
Box under "LA23" or in hard copy by the
start of our next class. We will discuss these questions at the
start of class, so no late submissions are accepted. Please be sure
that your name is clearly indicated in all submissions.
- Levitin Exercise 8.1.12, p. 292 (10 points - it's going to take some effort)
- Levitin Exercise 8.2.1, p. 296 (4 points)
- Levitin Exercise 8.2.6, p. 297 (3 points)
Terminology
- memory functions
- reachable
- transitive closure
- Warshall's algorithm
Examples