Lecture Notes on Undergraduate Algorithms
A first course on undergraduate algorithms taught at Dartmouth
- Introduction, Worst Case Run Times
- Communicating Algorithms
- Big-Oh Notation
- Algorithms with Numbers
- Binary Search
- Divide and Conquer: MergeSort + Recurrences
- Divide and Conquer: Finding Top-k elements of an array
- Divide and Conquer: Finding Median in Linear Time
- Divide and Conquer: Counting Inversions
- Divide and Conquer: Karatsuba's Algorithm
- Divide and Conquer: Polynomial Multiplication via Fast Fourier Transform
- Divide and Conquer: Closest Points on a Plane
- Dynamic Programming: Smart Recursion
- Dynamic Programming: Subset Sum and Knapsack
- Dynamic Programming: Edit Distance
- Dynamic Programming: Longest Increasing Subsequence
- Dynamic Programming: When doesn't it work?
- Graphs: Depth First Search + Properties
- Graphs: Topological Sort + Applications
- Graphs: Strongly Connected Components via DFS
- Graphs: Breadth First Search + Dijkstra's Algorithm
- Graphs: Bellman-Ford Algorithm for Detecting Negative Cycles
- Graphs: Flows and Cuts
- Graphs: Ford-Fulkerson Algorithm for Max-Flow and Min-Cut
- Graphs: Issue with Ford-Fulkerson
- Graphs: Faster Flow Algorithms
- Graphs: Applications of Flows and Cuts
- Graphs: Boruvka's Algorithm for Minimum Spanning Tree
- Graphs: Prim and Kruskal's Algorithm for MST
- Linear Programming
- Hardness