Algorithm Design and Analysis

The purpose of this undergraduate course is to introduce fundamental techniques and viewpoints for the design and the analysis of efficient computer algorithms, and to study important specific algorithms. The course relies heavily on mathematics and mathematical thinking in two ways: first as a way of proving properties about particular algorithms such as termination, and correctness; and second, as a way of establishing bounds on the worst case (or average case) use of some resource, usually time, by a specific algorithm. The course covers some randomized algorithms as well as deterministic algorithms.

00:02:25 2010-09-23
This video shows the URL for printed material that accompanies the course, and a URL for more advanced lectures on material that overlaps and extends the course. The URL for printed course material is: www.cs.ucdavis.edu/~gusfield/itunesU The URL for mo...
00:49:06 2010-09-24
This is the course introduction about algorithm complexity, including what "worst case running time" means and how it is measured.
00:48:19 2010-09-27
In Lecture 2, Gusfield discusses Big-Oh, Omega and Theta notation. He describes Mergesort and Merge and the start of their time analysis.
00:49:57 2010-09-29
In Lecture 3, Gusfield gives the worst-case analysis of MergeSort by setting up a recurrence relation and solving it by unwrapping.
00:52:48 2010-10-01
In Lecture 4, students learn about solving a more complex recurrence relation by unwrapping. Gusfield also addresses the problem of counting inversions in a permutation.
00:48:11 2010-10-04
Lecture 5: Gusfield lectures about counting the number of inversions in a permutation. He introduces fast integer multiplication by divide and conquer.
00:48:10 2010-10-06
In Lecture 6, Gusfield finishes the discussion of integer multiplication by divide and conquer. He then starts randomized selection and median finding.
00:52:13 2010-10-08
During Lecture 7, students learn more on randomized selection and median finding: algorithm and start of analysis.
00:50:10 2010-10-11
In Lecture 8, Gusfield completes his analysis of the expected number of comparisons in randomized version of Select(S,k) as a function of |S|. The expected number is at most 8|S|.
00:50:30 2010-10-13
For Lecture 9, Gusfield starts discussion of greedy algorithms: Picking the largest number of non-overlapping intervals on a line.
00:16:35 2010-10-14
In Lecture 9A, Gusfield provides another scheduling problem to be solved by a greedy algorithm.
00:51:41 2010-10-15
In Lecture 10, students learn about Dijkstra's algorithm for shortest paths in a graph with non-negative edge weights.
00:49:34 2010-10-18
In Lecture 11, Gusfield covers Prim's algorithm and analysis, and Kruskal's algorithm.
00:26:41 2010-10-20
In Lecture 12, Gusfield talks about the proof of correctness of Kruskal's algorithm.
00:47:37 2010-10-22
In Lecture 13, Gusfield introduces recursive programming and memoization through the problem of computing the maximum weight set of pairwise non-overlapping intervals.
00:49:36 2010-10-27
Lecture 14 reviews memoization; introduction to dynamic programming (DP) for the weighted interval problem and traceback in DP.
00:50:08 2010-10-29
In Lecture 15, Gusfield finishes the discussion of interval selection, and then introduces the RNA folding problem and talks about recurrences for it.
00:49:35 2010-11-01
Lecture 16 deals with the solution to the RNA folding problem using dynamic programming.
00:37:29 2010-11-03
Lecture 17 covers dynamic programming for the shortest path problem in a weighted directed graph, as well as negative edge weights allowed but no negative cycles.
00:48:28 2010-11-05
In Lecture 18, Gusfield discusses Floyd-Warshall, the algorithm for computing the shortest path in a weighted graph between each pair of nodes in the graph.
00:52:19 2010-11-08
Lecture 19 covers the unique-decipherability problem and gives definitions and the start of a graph-based solution.
00:51:19 2010-11-10
Lecture 20 deals with unique-decipherability: efficient graph-based algorithm and proof of correctness.
00:51:45 2010-11-12
In Lecture 21, Gusfield covers linear-time pattern matching. He also discusses Z-values and Z-algorithms.
00:51:35 2010-11-15
Lecture 22 completes linear-time pattern matching using the Z-algorithm
00:47:51 2010-11-17
Lecture 23 covers approximation algorithms - definition, factor of two approximation for the center cover problem.
00:50:07 2010-11-22
Lecture 24 gives an introduction to P and NP and polynomial-time reductions.
00:48:02 2010-11-24
Lecture 25 deals with an intuitive view of NP - not the correct formal definition.
00:45:29 2010-11-29
In Lecture 26, Gusfield gives correct, formal definitions of P and NP, ending with a brief definition of NP-complete problems (languages).
00:50:25 2010-12-01
Lecture 27 covers the major theorems of NP-completeness, P = NP question, and how to prove a new problem in NP-complete.
00:39:36 2010-12-03
Lecture 28: Gusfield recaps NP-completeness. The professor discusses coping with NP-complete problems: approximation algorithms and lowering the exponent of exponential-time algorithms.