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

Approximation Algorithms Part I
École normale supérieure via Coursera
Approximation Algorithms Part II
École normale supérieure via Coursera
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
Stanford University via Coursera
Algorithm Design and Analysis
University of Pennsylvania via edX
Delivery Problem
University of California, San Diego via Coursera