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

    Lecture 1

        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

    Lecture 2

    Lecture 3

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

   Lecture 4

   Lecture 5

    First ACM Meeting of the Semester

    Lecture 6

    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

Midterm 1


        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.

Examples for Midterm 2

Midterm 2

Colloquia 16-October-2006.

    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


Dynamic Programming Slides


    HW7 due Wednesday 15-Nov:

  1. Page 640, 25.3-2, 25.3-3
  2. 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.
  3. 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.


Introduction to NP-C slides

Last midterm: Friday 1-December.

Midterm 3

Midterm 3 with answers

Final exam