Proves the Ω(n log n) lower bound for comparison-based sorting, then introduces divide-and-conquer selection and the fast Fourier transform.
Save to open this file
Berkeley CS170: Efficient Algorithms and Intractable Problems
All
- 01-Introduction
01-Introduction
- 02-Divide-and-Conquer (Part I)
- 03-Divide-and-Conquer (Part II)
- 04-Divide-and-Conquer (Part III)
- 05-Decomposition of Graphs
- 06-Paths in Graphs (Part I)
- 07-Paths in Graphs (Part II)
- 08-Greedy (Part I)
- 09-Greedy (Part II)
- 10-Greedy (Part III)
- 11-Greedy Wrap-Up and Introduction to Dynamic Programming
- 12-Dynamic Programming (Part II)
- 13-Dynamic Programming (Part III)
- 14-Dynamic Programming (Part IV)
- 15-Linear Programming
- 16-Network Flow + Bipartite Matching
- 17-Duality, Zero-Sum Games
- 18-P vs NP
- 19-P vs NP (Part II)