
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.
1: Algorithmic Thinking, Peak Finding
2: Models of Computation, Document Distance
3: Insertion Sort, Merge Sort
4: Heaps and Heap Sort
5: Binary Search Trees, BST Sort
6: AVL Trees, AVL Sort
7: Counting Sort, Radix Sort, Lower Bounds for Sorting
8: Hashing with Chaining
9: Table Doubling, Karp-Rabin
10: Open Addressing, Cryptographic Hashing
11: Integer Arithmetic, Karatsuba Multiplication
12: Square Roots, Newton’s Method
13: Breadth-First Search (BFS)
14: Depth-First Search (DFS), Topological Sort
15: Single-Source Shortest Paths Problem
16: Dijkstra
17: Bellman-Ford
18: Speeding up Dijkstra
19: Dynamic Programming I: Fibonacci, Shortest Paths
20: Dynamic Programming II: Text Justification, Blackjack
21: Dynamic Programming III: Parenthesization, Edit Distance, Knapsack
22: Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros.
23: Computational Complexity
24: Topics in Algorithms Research
Prerequisites: A firm grasp of Python and a solid background in discrete mathematics are necessary prerequisites to this course.
Summary of Main Course Features
Instructors: Prof. Erik Demaine and Prof. Srinivas Devadas