CS 577: Introduction to Algorithms Homework 3
Ground Rules
• The homework is worth 5 points (out of a total of 100 points you can accumulate in this course).
• The homework is to be done and submitted in pairs. You can partner with someone from either section.
• The homework is due at the beginning of either lecture on the due date.
• No extensions to the due date will be given under any circumstances.
• Turn in your solution to each problem on a separate sheet of paper (or sheets stapled together), with your names
clearly written on top.
Problems
1. (Worth: 2 points. Page limit: 1 sheet; 2 sides) Solve Problem 12, Racetrack, on Page 12-13 of Chapter 18
in the book “Algorithms, Etc.” Your algorithm should run in time O(n
4
). Please provide a proof of correctness
and running time.
Link: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/18-graphs.pdf.
2. (Worth: 3 points. Page limit: 1 sheet; 2 sides) Sometimes there are multiple shortest paths between pairs of
nodes in a graph. Develop an algorithm for the following task: given an undirected graph G = (V, E) with unit
edge lengths and nodes v and w, output the number of distinct shortest paths from v to w. For example, for the
graph below, on input v and w your algorithm should output 2. Your algorithm should run in linear time. Prove
the correctness of your algorithm and analyze its running time.
v w
1
