ECS 122A - Fall 2010 Algorithm Design and Analysis - Gusfield
CS 122A is the undergraduate course on algorithm design and analysis taught at UC Davis in the Department of
Computer Science. The graduate
version of this course is ECS 222A. Videos for lectures in CS 222A can be found at
CS 222A videos
Lecture Videos
Lecture 1
Lecture 1. Introduction to the course, Complexity rules of the road (see
handout on the class website).
Supplemental video
Another lecture on the same topic: Complexity rules of the game.
Lecture 2
2. Sept. 27: big-oh, omega and theta notation. Description of Mergesort and Merge
and the start of their time analysis. Algorithm Merge is proved correct by induction
on the sum of the sizes of the two lists. The worst-case number of comparisons in
algorithm Merge on two lists of total size n is n-1 (why?).
Lecture 3
3. Sept. 29: Worst case analysis of MergeSort by setting up a recurrence relation
and solving it by unwrapping.
Lecture 4
4. Oct. 1: Solving a more complex recurrence relation by unwrapping. Introduction
to the problem of counting the number of inversions in a permutation.
Supplemental video
Solving a divide and conquer recurrence by unwrapping the recurrence to set up and solve a summation.
Introduction to the inversion counting problem.
Lecture 5
5. Oct. 4. Counting the number of inversions in a permutation. Introduction to
fast integer multiplication by divide and conquer.
Lecture 6
6. Oct. 6. Finished the discussion of integer multiplication by divide and conquer.
Started the discussion of randomized Selection and median finding, which will lead to randomized quicksort.
Lecture 7
7. Oct. 8. More on randomized selection, setting up the analysis problem, random variables,
expected value (mean), partial derivation of the mean of a geometric distribution.
Lecture 8
8. Oct. 11 Complete analysis of the expected number of comparisons in the randomized version
of Select(S,k) as a function of |S| = n. The expected number is at most 8|S| = O(n).
Lecture 9
9. Oct. 13 Start of discussion of greedy algorithms - The problem of picking
the largest number of non-overlapping intervals given on a line.
Lecture 10
10. Oct. 15 Dijkstra's algorithm for shortest paths in a graph with non-negative edge weights.
Lecture 11
11. Oct. 18 Start of discussion of the minimum spanning tree problem. Prim's algorithm and
proof of correctness and running time. Kruskal's algorithm.
Lecture 12
12. Oct. 20 proof of correctness of Kruskal's algorithm. Return to scheduling problems -
classroom scheduling problem, algorithm and correctness.
Lecture 13
13. Oct. 22 Introduction to recursive programming and memoization through the problem of
computing the maximum weight set of pairwise non-overlapping intervals.
14. Oct. 25 midterm
Lecture 14
15. Oct. 27 review of memoization, introduction to dynamic programming in the weighted interval
problem. traceback in DP.
Lecture 15
16. Oct. 29 introduction to the RNA folding problem and recurrences for it.
Lecture 16
17. Nov. 1 dynamic programming for RNA folding.
Lecture 17
18. Nov. 3 dynamic programming for the shortest path problem in a weighted directed graph.
Lecture 18
19. Nov. 5 Floyd-Warshal algorithm for computing the shortest path in a weighted graph, between each
pair of nodes in the graph.
Lecture 19
20. Nov. 8. The Unique-Decypherability problem. Definitions and start of graph-based solution.
Lecture 20
21. Nov. 10 Unique-Decypherability - graph algorithm, proof of correctness.
Lecture 21
22. Nov. 12 Linear-time pattern matching. Z-values and Z-algorithm.
Lecture 22
23. Nov. 15 Linear-time pattern matching. Z-values and Z-algorithm.
Lecture 23
24. Nov. 17 Approximation Algorithms - definition, example of a factor of two approximation algorithm - center cover problem.
Lecture 24
25. Nov. 19 Approximation Algorithms - factor of two approximation to the vertex cover problem.
Lecture 25
26. Nov. 22 Introduction to P and NP and poly-time reductions
Lecture 26
27. Nov. 24 An intuitive view of NP - not the correct formal definition
28. Nov. 26 thanksgiving holiday
Lecture 27
29. Nov. 29 Correct, formal definitions of P and NP, ending with a brief definition of NP-complete problems (languages)
Lecture 28
30. Dec. 1 The major theorems of NP-completeness, P = NP question, the mechanics of how to prove a new problem is NP-complete.
Lecture 29
31. Dec. 3 Dealing with NP-complete problems - approximation algorithms, fast algorithms for subsets of the whole set of problem
instances, reducing the growth rate of exponential-time solutions. A DP algorithm for the Traveling Salesman problem for n cities that
runs in O(n^2 x 2^n) time, instead of the more naive method that would take theta(n!) time.