| Topics | |
Reading | |
Assignments |
|---|
Mathematical background
- Getting started
- Growth of functions
- Recurrences
- The Master Method
- Class notes
| |
Chapter 1
2.1 - 2.3
3.1 - 3.2
4.1
4.3 |
|
Assignment 1
Quiz 1
Solutions |
Analysis techniques
- Dynamic programming
- Matrix multiplication
- Elements of dynamic programming
- Longest common subsequence
- Greedy methods
- A lecture-scheduling problem
- The knapsack problem
- Elements of the greedy strategy
- Matroids and minimum spanning trees
- A task-scheduling problem
- Huffman codes
- Class notes
- Java
implementations
| |
Chapter 4
Section 15
15.2
15.2
15.4
Section 16
notes
16.2
16.2
16.4
16.5
16.3 |
|
Assignment 2
Quiz 2
Solutions |
Graph algorithms
- Elementary graph algorithms
- Depth-first search
- Topological sort
- Strongly connected components
- Shortest paths
- The Bellman-Ford algorithm
- Dijkstra's algorithm
- The Floyd-Warshall algorithm
- Class notes
- Java
implementations
| |
Chapter 6
Section 22
22.3
22.4
22.5
Section 24
24.1
24.2 - 24.5
25.1 - 25.2 |
|
Assignment 3
Quiz 3
Solutions |
|
***** Midterm Exam I ***** Fri, Oct 17 |
Flow in networks
- Definition of a flow
- The Ford-Fulkerson method
- Maximum bipartite matching
- Class notes
| |
Section 26
26.1
26.2
26.3 |
|
Assignment 4
Quiz 4
Solutions |
| Algebraic algorithms | |
Chapter 7
28.1 - 28.2
28.4
30.1 - 30.3 |
|
|
| String matching | |
Section 32
32.1
32.2
32.3 |
|
Assignment 5
Quiz 5
Solutions |
Geometric algorithms
- Constructing self-nonintersecting polygons
- Finding the convex hull
- Alpha-shapes
- Finding the closest pair of points
- Diameter of a point set
- Class notes
- Java
implementations
| |
Section 33
33.3
33.4 |
|
|
|
***** Midterm Exam II ***** Wed, Nov 19 |
NP-completeness
- Polynomial time verification
- NP-completeness and reducibility
- NP-completeness proofs
- NP-complete problems
- Class notes
| |
Section 34
34.1 - 34.2
34.3
34.4
34.5 |
|
|
Approximation algorithms
- The vertex cover problem
- The traveling salesman problem
- The set-covering problem
- The subset-sum problem
- Class notes
| |
Section 35
35.1
35.2
35.3
35.5 |
|
|
Intro to randomized
algorithms
- The Max-3-CNF satisfability
- The generalMax-CNF problem
- The Monte-Carlo methods
- The Las Vegas algorithms
- Class notes
| |
Section 35
35.4
online notes
online notes
online notes |
|
|
|
***** Final Exam ***** Mon, Dec 15, 12:00 - 2pm in M316 |