# click the upper-left icon to select videos from the playlist
source: UC Davis Academics 2014年10月17日
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.
Printed course material: www.cs.ucdavis.edu/~gusfield/itunesU
More advanced lectures: www.cs.ucdavis.edu/~gusfield/cs222f07/videolist.html
Introduction to the videos 2:26
Introduction to the course and algorithm complexity 49:07
Big-Oh, Omega and Theta notation 48:20
Time analysis of Mergesort 49:58
A more complex recurrence relation and counting inversions 52:49
Counting inversions; Fast integer multiplication 48:12
Fast integer multiplication, randomized selection and median finding 48:11
More on randomized selection and median finding 52:14
Expected number of comparisons in randomized select 50:11
Greedy algorithms: Picking largest set of non-overlapping intervals 50:31
Greedy algorithms: The classroom scheduling problem 16:36
Dijkstra's shortest path algorithm 51:42
Start of minimum spanning tree problem 49:35
Correctness of Kruskal's algorithm. 26:42
Recursive programming and memoization 47:38
Intro to dynamic programming, weighted interval problems 49:37
Intro to the RNA folding problem and recurrences 50:09
Dynamic programming for RNA folding. 49:36
Dynamic programming for shortest path problem 37:30
Floyd-Warshall algorithm for all-pairs shortest path 48:29
The unique-decipherability problem 52:20
Unique-Decipherability. Graph algorithm and proof of correctness 51:20
Linear-time pattern matching. Z-values and Z-algorithm 51:46
Finish of linear-time pattern matching 51:36
Introduction to approximation algorithms 47:52
Introduction to P and NP 50:08
An intuitive view of NP 48:03
Formal definition of P and NP 45:30
Major theorems of NP-completeness 50:27
Coping with NP-completeness 39:37
