CS 470 Fall 2006

Instructor: Phillip G. Bradford

Office Hours: MWF 11am to 12pm in 116 Houser Hall.

Grader: Bogdan Munteanu

Office Hour: Tuesday 11am to 12pm in 208 East Engineering.

**Scholarship Announcement: **

There are still several $3125 NSF scholarships available for this year. We have scholarships available at all levels: sophomores, juniors and seniors. Students must have completed CS124 and have a FAFSA form on file that demonstrates financial need as determined by UA.

You can get more information at:

**Homework late policy**: 1 day late: 20% off; No homework will be
accepted after one day late.

**Some Lectures & Exercises**

HW1, due 30-August: page 50: 3.1-2, 3.1-3, 3.1-5, page 57: 3.2-2 and for CS 570: page 59: 3-4

HW2 due 8-Sept: page 86: 4-1, p86, 4-4 a-d.

Lecture 5

First ACM Meeting of the Semester

Industrial Colloquia: 12-Sept-2006.

HW3 due Wednesday 20-Sept: page 135, 6.3-1 and 6.3-2, page 141, 6.5-3; CS570: 6.5-4.

**First Midterm**: Monday 25-September

HW4 due Monday 9-Oct: page 170, 8.2-3, 8.2-4 and page 173, 8.3-4.

Industrial Colloquia: 10-October-2006.

HW5 due Friday 13-Oct: page 192, 9.3-1, 9.3-3, 9.3-5.

HW6 due Friday 3-November: page 530: 22.1-6, p 591: 24.1-3, p595: 24.2-4, p 600: 24.3-2

Summer Opportunity at Berkeley

Colloquia on Multicore processing

HW7 due Wednesday 15-Nov:

- Page 640, 25.3-2, 25.3-3
- Dijkstra’s algorithm only works correctly with non-negative edge weights. Give a small example (not more than 5 nodes) of an acyclic digraph with positive and negative edge weights where Dijkstra’s algorithm fails to give a correct shortest path. Explain why Dijkstra’s algorithm will not find a correct shortest path in this case.
- Suppose we have a graph G with both positive and negative edge weights
(with no negative cycles). Does the following algorithm work for finding a
single-source shortest path in G? Give either a small counterexample or a
proof of correctness.
· Find the minimal edge weight in G, call this m. Without loss of generality assume m is negative.

· Add |m| to all edge weights giving a graph G’.

· Run Dijkstra on G’.

HW8: due the last lecture before study week (will accept by Wed of study week), p628: 25.1-5, 25.1-6, p1017: 34.5-1, 34.5-3, 34.5-5.

Last midterm: Friday 1-December.