ECS 122A - Undergraduate Course on Design and Analysis of Algorithm - UC Davis, Computer Science
Dan Gusfield

This page links to various handouts connected to individual lectures on the iTunes and Utube course.
It also links to homeworks that were assigned in the class in 2010.
The textbook used was ``Algorithm Design" by J. Kleinberg and E. Tardos, published by Addison-Wesley.

Distribution List

  1. Course Syllabus

  2. There are also videos for GRADUATE-level lectures that cover some of the same material as in CS 122A, but also contain much additional material.
    These lectures may be of interest to students following the lectures for CS122A. The graduate-level lecture videos are found at
    list of graduate-level videos on Design and Analysis of Algorithms. These lectures will be augmented and later posted on iTunes as Lectures on Graduate Level Algorithms.

  3. Introduction to complexity and rules of the game Handout for Lecture 1
  4. First homework
  5. A rant on induction - useful if you are unsure about how to do inductive proofs Handout for Lecture 1
  6. Solving recurrence relations by unwrapping and the master method Handout for Lectures 1,2, 3 and 4
  7. Another exposition on the master method for solving divide and conquer recurrences Handout for Lectures 1,2, 3 and 4
  8. Second homework
    To do the unwrapping for a recurrence problem on Homework 2, you can assume that the base case is T(n) = cn for some constant c. What c is exactly will not influence the asymptotic solution.
  9. A full proof of correctness of the algorithm to count the number of inversions. Handout for Lecture 5
  10. The algorithm Select (S,k) is on page 728 of the book. In my printing it defines it as the k'th largest element in S, but that is clearly wrong - it is the k'th smallest element.
  11. For a complete derivation of the mean of the geometric distribution, see page 228, Example 6.4 in the following: a chapter on expected value
    You only need to read page 228, but the chapter is a good introduction to expected value, especially the early part of the chapter. You will need to understand the expected value of a geometric distribution when we analyze randomized Select and randomized Quicksort.
  12. Third homework.
  13. Fourth homework
    On HW 4, problem 5, you can assume that the road is straight with no turns or curves. For extra credit, try to solve the problem where the road is not assumed to be straight. I don't know a solution for that case.
  14. Fifth homework
  15. Notes on traceback for the maximum weight independent set problem on a tree. Handout for Lecture 14
  16. Notes on the unique-decipherability problem. Handout for Lecture 19
  17. ud.pl Perl program to determine if a code is UD. Handout for Lecture 19
  18. Sixth homework
  19. Notes on the Z-algorithm Handout for Lecture 21
  20. Seventh homework Note, the tone of problem 2 makes it seem that the conjecture is surely correct. It might not be, so don't exclude that possibility.
  21. Eighth homework