Completed
R9. Approximation Algorithms: Traveling Salesman Problem
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Design and Analysis of Algorithms
Automatically move to the next video in the Classroom when playback concludes
- 1 1. Course Overview, Interval Scheduling
- 2 2. Divide & Conquer: Convex Hull, Median Finding
- 3 R1. Matrix Multiplication and the Master Theorem
- 4 3. Divide & Conquer: FFT
- 5 R2. 2-3 Trees and B-Trees
- 6 4. Divide & Conquer: van Emde Boas Trees
- 7 5. Amortization: Amortized Analysis
- 8 6. Randomization: Matrix Multiply, Quicksort
- 9 R4. Randomized Select and Randomized Quicksort
- 10 7. Randomization: Skip Lists
- 11 8. Randomization: Universal & Perfect Hashing
- 12 R5. Dynamic Programming
- 13 9. Augmentation: Range Trees
- 14 10. Dynamic Programming: Advanced DP
- 15 11. Dynamic Programming: All-Pairs Shortest Paths
- 16 12. Greedy Algorithms: Minimum Spanning Tree
- 17 R6. Greedy Algorithms
- 18 13. Incremental Improvement: Max Flow, Min Cut
- 19 14. Incremental Improvement: Matching
- 20 R7. Network Flow and Matching
- 21 15. Linear Programming: LP, reductions, Simplex
- 22 16. Complexity: P, NP, NP-completeness, Reductions
- 23 R8. NP-Complete Problems
- 24 17. Complexity: Approximation Algorithms
- 25 18. Complexity: Fixed-Parameter Algorithms
- 26 R9. Approximation Algorithms: Traveling Salesman Problem
- 27 19. Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees
- 28 20. Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees
- 29 R10. Distributed Algorithms
- 30 21. Cryptography: Hash Functions
- 31 22. Cryptography: Encryption
- 32 R11. Cryptography: More Primitives
- 33 23. Cache-Oblivious Algorithms: Medians & Matrices
- 34 24. Cache-Oblivious Algorithms: Searching & Sorting
