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