CSC 344
Homework 5

Assigned April 24, due May 5

There are 9 problems and 11 days.

As you're doing these, think of which one you'd like to present in class, and let me know as soon as you've decided. Solutions will be presented in class May 5-7.

Written problems from textbooks (to be done individually)

• Shaffer problem 11.10 (working through Dijkstra's algorithm for a specific graph)
• Shaffer problem 11.17 (working through Prim's algorithm for a specific graph)
• Shaffer problem 11.18 (working through Kruskal's algorithm for a specific graph)
• Shaffer problem 11.23 (comparing the shortest-paths problem with the MST problem)
• CLRS problem 22-2 (finding articulation points, bridge edges, and biconnected components in undirected graphs)
• CLRS problem 24-2 (nesting boxes)
• CLRS exercise 26.2-11 (using max-flow to solve a connectivity problem)
• CLRS problem 26-1 (using max-flow to solve the "escape" problem in a 2-D grid)

Programming problem (may be done in teams of two, if you wish)

Shaffer programming project 11.5 (finding connected components using a UNION/FIND data structure)