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
- Course Syllabus
- 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.
- Introduction to complexity and rules of the
game Handout for Lecture 1
- First homework
- A rant on induction - useful if you are unsure about how to do inductive proofs
Handout for Lecture 1
- Solving recurrence relations by unwrapping and
the master method Handout for Lectures 1,2, 3 and 4
- Another exposition on the
master method for solving divide and conquer recurrences
Handout for Lectures 1,2, 3 and 4
- 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.
- A full proof of correctness of the algorithm to count the number of inversions.
Handout for Lecture 5
- 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.
-
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.
- Third homework.
- 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.
- Fifth homework
- Notes on traceback for the maximum weight independent set problem on a tree.
Handout for Lecture 14
- Notes on the unique-decipherability problem.
Handout for Lecture 19
- ud.pl Perl program to determine if a code is UD.
Handout for Lecture 19
- Sixth homework
- Notes on the Z-algorithm
Handout for Lecture 21
- 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.
- Eighth homework