## 2017-01-12

### Advanced Lectures on Design and Analysis of Computer Algorithms (at UC Davis)

# click the upper-left icon to select videos from the playlist

Advanced Lectures on Design and Analysis of Computer Algorithms
These are lectures given over a span of about ten years, in several different graduate-level courses that discuss efficient computer algorithms. They are supplemented by additional lectures on advanced topics, recorded outside of any class. Additional supplemental lectures will be added as new lecture videos are made.

Complexity: Rules of the Game Introduction to worst-case analysis; upper and lower bounds. 46:34
Solving Divide and Conquer Recurrences 22:21
Finding the Closest Pair of Points on the Plane: Divide and Conquer 49:28
Computing the Lower Envelope of a Set of Lines 48:41
Counting the Number of Inversions by Divide and Conquer 35:49
Finding the Median of n Numbers in O(n) Time 47:38
Four-Russian's Method for Bit-Matrix Multiplication 1:00:31
Strassen's Matrix Multiplication by Divide and Conquer 52:43
Introduction to Information Theory Lower Bounds 18:36
Second Lecture on Information Theory Lower Bounds 46:33
Randomized Algorithm for Quicksort and Time Analysis 35:17
Second Lecture on Randomized Quicksort 5:46
Second Lecture on Adversary Lower Bounds 31:05
Introduction to Network Flow and Ford-Fulkerson Algorithm 43:30
Continuation of the Preflow-Push Network Flow Algorithm 51:18
Second lecture on Network Flow, Ford-Fulkerson Algorithm 51:00
Completion of Ford-Fulkerson, and Bipartite Matching 41:10
Network Flow, start of Preflow-Push Algorithm 9:00
Continuation of the Preflow-Push algorithm 44:41
Time Analysis for the Preflow-Push Algorithm 45:42
End of the Time Analysis of the Preflow-Push Algorithm 44:16
End of Season Elimination: Application of Network Flow 0:12
End of Season Elimination: Details 27:02
All-Teams End of Season Elimination: Generalization to Other Sports 1:29:24