Catalog

Introduction to Algorithms

Electrical Engineering and Computer Science MIT CC BY-NC-SA 4.0 47 lectures

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems.

Syllabus

  1. 1 Lecture 1: Algorithmic Thinking, Peak Finding
  2. 2 Lecture 2: Models of Computation, Document Distance
  3. 3 Lecture 3: Insertion Sort, Merge Sort
  4. 4 Lecture 4: Heaps and Heap Sort
  5. 5 Lecture 5: Binary Search Trees, BST Sort
  6. 6 Lecture 6: AVL Trees, AVL Sort
  7. 7 Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting
  8. 8 Lecture 8: Hashing with Chaining
  9. 9 Lecture 9: Table Doubling, Karp-Rabin
  10. 10 Lecture 10: Open Addressing, Cryptographic Hashing
  11. 11 Lecture 11: Integer Arithmetic, Karatsuba Multiplication
  12. 12 Lecture 12: Square Roots, Newton's Method
  13. 13 Lecture 13: Breadth-First Search (BFS)
  14. 14 Lecture 14: Depth-First Search (DFS), Topological Sort
  15. 15 Lecture 15: Single-Source Shortest Paths Problem
  16. 16 Lecture 16: Dijkstra
  17. 17 Lecture 17: Bellman-Ford
  18. 18 Lecture 18: Speeding up Dijkstra
  19. 19 Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths
  20. 20 Lecture 20: Dynamic Programming II: Text Justification, Blackjack
  21. 21 Lecture 21: Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
  22. 22 Lecture 22: Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
  23. 23 Lecture 23: Computational Complexity
  24. 24 Lecture 24: Topics in Algorithms Research
  25. 25 Recitation 1: Asymptotic Complexity, Peak Finding
  26. 26 Recitation 2: Python Cost Model, Document Distance
  27. 27 Recitation 3: Document Distance, Insertion and Merge Sort
  28. 28 Recitation 5: Recursion Trees, Binary Search Trees
  29. 29 Recitation 6: AVL Trees
  30. 30 Recitation 7: Comparison Sort, Counting and Radix Sort
  31. 31 Recitation 8: Simulation Algorithms
  32. 32 Recitation 9: Rolling Hashes, Amortized Analysis
  33. 33 Recitation 9b: DNA Sequence Matching
  34. 34 Recitation 10: Quiz 1 Review
  35. 35 Recitation 11: Principles of Algorithm Design
  36. 36 Recitation 12: Karatsuba Multiplication, Newton's Method
  37. 37 Recitation 13: Breadth-First Search (BFS)
  38. 38 Recitation 14: Depth-First Search (DFS)
  39. 39 Recitation 15: Shortest Paths
  40. 40 Recitation 16: Rubik's Cube, StarCraft Zero
  41. 41 Recitation 18: Quiz 2 Review
  42. 42 Recitation 19: Dynamic Programming: Crazy Eights, Shortest Path
  43. 43 Recitation 20: Dynamic Programming: Blackjack
  44. 44 Recitation 21: Dynamic Programming: Knapsack Problem
  45. 45 Recitation 22: Dynamic Programming: Dance Dance Revolution
  46. 46 Recitation 23: Computational Complexity
  47. 47 Recitation 24: Final Exam Review

Course materials