Introduction to Algorithms

1

1. Algorithms and Computation

1

Lecture 1: Algorithmic Thinking, Peak Finding

2

2. Data Structures and Dynamic Arrays

2

Lecture 2: Models of Computation, Document Distance

3

Introduction to Algorithms - Problem Session 1: Asymptotic Behavior of Functions and Double-ended...

3

Lecture 3: Insertion Sort, Merge Sort

4

3. Sets and Sorting

4

Lecture 4: Heaps and Heap Sort

5

4. Hashing

5

Lecture 5: Binary Search Trees, BST Sort

6

Problem Session 2 (MIT 6.006 Introduction to Algorithms, Spring 2020)

6

Lecture 6: AVL Trees, AVL Sort

7

5. Linear Sorting

7

Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting

8

Problem Session 3

8

Lecture 8: Hashing with Chaining

9

6. Binary Trees, Part 1

9

Lecture 9: Table Doubling, Karp-Rabin

10

7. Binary Trees, Part 2: AVL

10

Lecture 10: Open Addressing, Cryptographic Hashing

11

Problem Session 4

11

Lecture 11: Integer Arithmetic, Karatsuba Multiplication

12

8. Binary Heaps

12

Lecture 12: Square Roots, Newton's Method

13

9. Breadth-First Search

13

Lecture 13: Breadth-First Search (BFS)

14

Quiz 1 review

14

Lecture 14: Depth-First Search (DFS), Topological Sort

15

10. Depth-First Search

15

Lecture 15: Single-Source Shortest Paths Problem

16

11. Weighted Shortest Paths

16

Lecture 16: Dijkstra

17

Problem Session 5

17

Lecture 17: Bellman-Ford

18

12. Bellman-Ford

18

Lecture 18: Speeding up Dijkstra

19

13. Dijkstra

19

Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths

20

Problem Session 7

20

Lecture 20: Dynamic Programming II: Text Justification, Blackjack

21

14. APSP and Johnson

21

Lecture 21: Dynamic Programming III: Parenthesization, Edit Distance, Knapsack

22

Quiz 2 Review

22

Lecture 22: Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.

23

15. Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling

23

Lecture 23: Computational Complexity

24

16. Dynamic Programming, Part 2: LCS, LIS, Coins

24

Lecture 24: Topics in Algorithms Research

25

Problem Session 8

25

Recitation 1: Asymptotic Complexity, Peak Finding

26

17. Dynamic Programming, Part 3: APSP, Parens, Piano

26

Recitation 2: Python Cost Model, Document Distance

27

18. Dynamic Programming, Part 4: Rods, Subset Sum, Pseudopolynomial

27

Recitation 3: Document Distance, Insertion and Merge Sort

28

19. Complexity

28

Recitation 5: Recursion Trees, Binary Search Trees

29

Problem Session 9

29

Recitation 6: AVL Trees

30

Quiz 3 Review

30

Recitation 7: Comparison Sort, Counting and Radix Sort

31

20. Course Review

31

Recitation 8: Simulation Algorithms

32

21. Algorithms—Next Steps

32

Recitation 9: Rolling Hashes, Amortized Analysis

33

Recitation 9b: DNA Sequence Matching

34

Recitation 10: Quiz 1 Review

35

Recitation 11: Principles of Algorithm Design

36

Recitation 12: Karatsuba Multiplication, Newton's Method

37

Recitation 13: Breadth-First Search (BFS)

38

Recitation 14: Depth-First Search (DFS)

39

R15. Shortest Paths

40

Recitation 16: Rubik's Cube, StarCraft Zero

41

Recitation 18: Quiz 2 Review

42

Recitation 19: Dynamic Programming: Crazy Eights, Shortest Path

43

Recitation 20: Dynamic Programming: Blackjack

44

Recitation 22: Dynamic Programming: Dance Dance Revolution

45

Recitation 21: Dynamic Programming: Knapsack Problem

46

Recitation 23: Computational Complexity

47

Recitation 24: Final Exam Review