Design & Analysis of Algorithms
- Introduction, Course Logistics Algorithm
Runtime Analysis
- Recursive Equations and Solving with substitution method
Master Theorem
- Divide and Conquer and Insertion Sort
Quick Sort
- Quiz 1
Selecting kth element
- Lower bound for sorting
Linear Sorting
- Amortized Analysis
Graph Review, Weighted Graph, BFS, DFS
- Holiday
Dynamic Programming (String alignment) Single source shortest path
- Quiz 2
Single source shortest path
- All pairs shortest path Midterm
Introduction to Greedy algorithms
- Holiday
Midterm Exam Review
- Midterm
Minimum Spanning Tree (Prim)
- Minimum Spanning Tree (Kruskal)
Introduction to Network Flow
- Minimum cut and maximum flow in graph
Backtracking
- Quiz 3
More backtracking examples (Graph coloring)
- Introduction to computation complexity
NP-Complete and NP-Hard
- Holiday
Final exam course review