- Introduction & Review
- Maximum Contiguous Subarray: case study in algorithm design
- Divide-and-Conquer Algorithms:
- Mergesort
- Polynomial Multiplication
- Randomized Selection
- Graphs:
- Review: Notation, Depth/Breadth First Search
- Cycle Finding & Topological Sort
- Minimum Spanning Trees: Kruskal's and Prim's algorithms
- Dijkstra's shortest path algorithm
- Dynamic Programming
- Knapsack
- Chain Matrix Multiplication,
- Longest Common Subsequence
- All Pairs Shortest Path
- Greedy algorithms:
- Activity Selection
- Huffman Coding
- Complexity Classes:
- Nondeterminism
- the classes P and NP,
- NP-complete problems
- polynomial reductions
Return to COMP271 Home page