Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

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

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

- Reachability