Algorithm Design and Analysis: Recent Episodes
Dan Gusfield
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.
Lecture 28: Gusfield recaps NP-completeness. The professor discusses coping with NP-complete problems: approximation algorithms and lowering the exponent of exponential-time algorithms.
Lecture 27 covers the major theorems of NP-completeness, P = NP question, and how to prove a new problem in NP-complete.
In Lecture 26, Gusfield gives correct, formal definitions of P and NP, ending with a brief definition of NP-complete problems (languages).
Lecture 23 covers approximation algorithms - definition, factor of two approximation for the center cover problem.
In Lecture 21, Gusfield covers linear-time pattern matching. He also discusses Z-values and Z-algorithms.
Lecture 20 deals with unique-decipherability: efficient graph-based algorithm and proof of correctness.
Lecture 19 covers the unique-decipherability problem and gives definitions and the start of a graph-based solution.
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.
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.
Lecture 16 deals with the solution to the RNA folding problem using dynamic programming.
In Lecture 15, Gusfield finishes the discussion of interval selection, and then introduces the RNA folding problem and talks about recurrences for it.
Lecture 14 reviews memoization; introduction to dynamic programming (DP) for the weighted interval problem and traceback in DP.
In Lecture 13, Gusfield introduces recursive programming and memoization through the problem of computing the maximum weight set of pairwise non-overlapping intervals.
In Lecture 10, students learn about Dijkstra's algorithm for shortest paths in a graph with non-negative edge weights.
In Lecture 9A, Gusfield provides another scheduling problem to be solved by a greedy algorithm.
For Lecture 9, Gusfield starts discussion of greedy algorithms: Picking the largest number of non-overlapping intervals on a line.
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|.
During Lecture 7, students learn more on randomized selection and median finding: algorithm and start of analysis.
In Lecture 6, Gusfield finishes the discussion of integer multiplication by divide and conquer. He then starts randomized selection and median finding.
Lecture 5: Gusfield lectures about counting the number of inversions in a permutation. He introduces fast integer multiplication by divide and conquer.
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.
In Lecture 3, Gusfield gives the worst-case analysis of MergeSort by setting up a recurrence relation and solving it by unwrapping.
In Lecture 2, Gusfield discusses Big-Oh, Omega and Theta notation. He describes Mergesort and Merge and the start of their time analysis.
This is the course introduction about algorithm complexity, including what "worst case running time" means and how it is measured.
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 more advanced lectures is: www.cs.ucdavis.edu/~gusfield/cs222f07/videolist.html