| Topics | |
Reading | |
Assignments |
|---|
Mathematical background
- Getting started
- Growth of functions
- Recurrences
- The Master Method
- Class notes
| |
3 Sections
2.1 - 2.3
3.1 - 3.2
4.1
4.3 |
|
posted on
Canvas
|
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
| |
2 Sections
Section 15
15.2
15.2
15.4
Section 16
notes
16.2
16.2
16.4
16.5
16.3 |
|
|
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
- Graph coloring
- Class notes
- Java
implementations
| |
2 Sections
Section 22
22.3
22.4
22.5
Section 24
24.1
24.2 - 24.5
25.1 - 25.2
class notes |
|
|
|
***** Midterm Exam I ***** Mon, Mar 4 |
Flow in networks
- Definition of a flow
- The Ford-Fulkerson method
- Maximum bipartite matching
- Class notes
| |
Section 26
26.1
26.2
26.3 |
|
|
| Algebraic algorithms | |
2 Sections
28.1 - 28.2
30.1 - 30.3 |
|
|
| String matching | |
Section 32
32.1
32.2
32.3 |
|
|
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 ***** Sat, Apr 13 |
| NP-completeness | |
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 general Max-CNF problem
- The Monte-Carlo methods
- The Las Vegas algorithms
- Class notes
| |
Section 35
35.4
online notes
online notes
online notes |
|
|
|
***** Final Exam ***** Thu, May 9, 3pm - 5:00pm in SW3009 |