YoVDO

Design and Analysis of Algorithms

Offered By: Massachusetts Institute of Technology via MIT OpenCourseWare

Tags

Algorithms and Data Structures Courses Algorithm Design Courses Divide and Conquer Algorithms Courses Greedy Algorithms Courses Dynamic programming Courses Complexity Theory Courses Distributed Algorithms Courses Approximation Algorithms Courses

Course Description

Overview

This is an intermediate algorithms course with an emphasis on teaching techniques for the design and analysis of efficient algorithms, emphasizing methods of application. Topics include divide-and-conquer, randomization, dynamic programming, greedy algorithms, incremental improvement, complexity, and cryptography.

Syllabus

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


Taught by

MIT OpenCourseWare

Tags

Related Courses

The Next Generation of Infrastructure
Delft University of Technology via edX
The Beauty and Joy of Computing - AP® CS Principles Part 2
University of California, Berkeley via edX
Advanced Data Structures in Java
University of California, San Diego via Coursera
Theory of Computation
Indian Institute of Technology Kanpur via Swayam
离散数学
Shanghai Jiao Tong University via Coursera