Homework 10: Handed out: April 29, due: May 6
Note: if you haven't used your one-time exemption, you can use it for homework, and hand it in in my office (Upson 4144) or to my admin, Cindy Robinson (Upson 4146) by 10 AM on Tuesday, May 11. It would make it easier for me and the graders if you could hand it in on time though.
I know there are a lot of problems here, but they should all be pretty short.
Read Chapters 23, 24, 25.1-3, and 26.1-3 (26.2 and 26.3 are not on the final).
Section Number Points Comments
23.1 3 4 You can describe the algorithms in English
23.2 1 4 Just state pi[v] and d[v] for every vertex after running
BFS-Search[3]
23.2 3 4 Say which line(s) in the BFS algorithm presented in class
change (and how) and then state the running time
23.3 2 5 Just state d[u] and f[u] for every vertex u
(no need to give the classification)
23.5 1 3 Hint: It can change by more than one.
Another hint: think of a cycle
24.1 1 3 Hint: there's a counterexample with 3 vertices.
24.1 2 3
24.1 3 4
24.2 1 4
24.2 4 6
25.1 7 3
25.2 1 5 Just draw a table with the d and pi values after every step.
25.2 2 6
25.3 1 6
26.1 5 3
26.2 5 2