## 2016-06-22

### Design and Analysis of Algorithms (Spring 2015) at MIT

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

source: MIT OpenCourseWare 2016年3月4日/上次更新：2016年6月13日
MIT 6.046J Design and Analysis of Algorithms (Spring 2015) introduces students to the design of computer algorithms, as well as analysis of sophisticated algorithms.
View the complete course: http://ocw.mit.edu/6-046JS15
Instructors: Erik Demaine, Srinivas Devadas, Nancy Ann Lynch
More courses at http://ocw.mit.edu

1. Course Overview, Interval Scheduling 1:23:35
2. Divide & Conquer: Convex Hull, Median Finding 1:20:35
R1. Matrix Multiplication and the Master Theorem 53:46
3. Divide & Conquer: FFT 1:20:52
R2. 2-3 Trees and B-Trees 30:45
4. Divide & Conquer: van Emde Boas Trees 1:20:15
5. Amortization: Amortized Analysis 1:15:53
6. Randomization: Matrix Multiply, Quicksort 1:21:52
R4. Randomized Select and Randomized Quicksort 39:30
7. Randomization: Skip Lists 1:20:56
8. Randomization: Universal & Perfect Hashing 1:21:51
R5. Dynamic Programming 52:03
9. Augmentation: Range Trees 1:24:34
10. Dynamic Programming: Advanced DP 1:20:08
11. Dynamic Programming: All-Pairs Shortest Paths 1:21:49
12. Greedy Algorithms: Minimum Spanning Tree 1:22:10
R6. Greedy Algorithms 22:24
13. Incremental Improvement: Max Flow, Min Cut 1:22:58
14. Incremental Improvement: Matching 1:22:33
R7. Network Flow and Matching 51:12
15. Linear Programming: LP, reductions, Simplex 1:22:27
16. Complexity: P, NP, NP-completeness, Reductions 1:25:25
R8. NP-Complete Problems 45:47
17. Complexity: Approximation Algorithms 1:21:08
18. Complexity: Fixed-Parameter Algorithms 1:17:43
R9. Approximation Algorithms: Traveling Salesman Problem 31:59
19. Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees 1:17:34
20. Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees 1:12:03
R10. Distributed Algorithms 50:19
21. Cryptography: Hash Functions 1:22:01
22. Cryptography: Encryption 1:24:15
R11. Cryptography: More Primitives 49:30
23. Cache-Oblivious Algorithms: Medians & Matrices 57:57
24. Cache-Oblivious Algorithms: Searching & Sorting 1:17:41