| Date |
Topic |
Reading |
Lecture Notes |
Problem session (if any) |
| Monday, Aug. 26 |
Syllabus, big-O review |
Intro to algorithms |
Lecture Notes |
|
| Wednesday, Aug. 28 |
Review: Big-O, Induction |
Intro to algorithms |
Lecture Notes |
|
| Friday, Aug. 30 |
Review: Recurrences, Recursion |
Recurrence packet
Recursion chapter |
Lecture Notes |
|
| Wednesday, Sept. 4 |
Recursive algorithms |
Recurision chapter, Sec. 1.2, 1.3, 1.7
| Lecture Notes |
|
| Friday, Sept. 6 |
Recursive Algorithms |
Recurision chapter, Sec. 4
Recusive Backtracking, Sec. 2 |
Lecture Notes |
|
| Monday, Sept. 9 |
No class due to illness |
Dynamic Programming, Section 1 |
|
|
| Wednesday, Sept. 11 |
Dynamic Programming: LIS |
Recusive Backtracking, Sec. 3 |
Lecture Notes |
|
| Friday, Sept. 13 |
Dynamic Programming: Edit distance |
Section 5.5 |
Lecture Notes |
|
| Monday, Sept. 16 |
Dynamic Programming:
Independant Set in trees |
Section 4.2
Section 5.7 |
Lecture Notes |
|
| Wednesday, Sept. 18 |
Problem Session: Dynamic Programming |
|
|
Worksheet |
| Friday, Sept. 20 |
Greedy Algorithms: Scheduling classes |
Section 7.2 |
Lecture Notes |
|
| Monday, Sept. 23 |
Greedy: EDF scheduling |
|
Lecture Notes |
|
| Wednesday, Sept. 25 |
Greedy: Huffman codes |
Section 7.4 |
Lecture Notes |
|
| Friday, Sept. 27 |
Problem Session: Greedy algorithms |
|
|
Worksheet |
| Monday, Sept. 29 |
Graphs: DFS/BFS |
Graph theory notes |
Lecture Notes |
|
| Wednesday, Oct. 2 |
Graphs: MST |
MST notes |
Lecture Notes |
|
| Friday, Oct. 4 |
Impelmenting MST: Union Find |
Union Find notes |
Lecture Notes |
|
| Monday, Oct. 7 |
Shortest paths trees |
Reading |
Lecture Notes |
|
| Wednesday, Oct. 9 |
Problem session day |
|
|
Worksheet |
| Friday, Oct. 11 |
Flows and cuts |
Notes |
|
|
| Monday, Oct. 14 |
Computing flows |
Reading |
|
|
| Wednesday, Oct. 16 |
Review for midterm |
|
|
|
| Friday, Oct. 18 |
Midterm exam |
|
|
|
| Wednesday, Oct. 23 |
Flow Applications |
Reading |
Lecture Notes |
|
| Friday, Oct. 25 |
Network flow |
|
Lecture Notes |
Worksheet |
| Monday, Oct. 28 |
Uncomputability and hardness |
Reading |
Lecture Notes |
|
| Wednesday, Oct. 30 |
NP-Hardness |
Reading
An allegory to read
|
Lecture Notes |
|
| Friday, Nov. 1 |
NP-Hardness |
Reading |
Lecture Notes |
|
| Monday, Nov. 4 |
More reductions |
Reading
Online guide
|
Lecture Notes |
|
| Wednesday, Nov. 6 |
NP-Hardness |
|
|
Worksheet |
| Friday, Nov. 8 |
Approximation |
Reading
Additional reading
|
Lecture Notes |
|
| Monday, Nov. 11 |
More Approximation |
Reading
|
Lecture Notes |
|
| Wednesday, Nov. 13 |
More Approximation |
|
Lecture Notes |
|
| Friday, Nov. 15 |
No class
Reading assignment on LP |
Chapter 7.1
|
|
|
| Monday, Nov. 18 |
Linear Programs |
Chapter 7.1
Additional reading
|
Lecture Notes |
|
| Wednesday, Nov. 20 |
Linear Programming: Duality |
Chapter 7.4
Additional reading
|
Lecture Notes |
|
| Friday, Nov. 22 |
LP: Simplex |
Chapter 7.6
Additional reference
|
Lecture Notes |
|
| Monday, Nov. 25 |
Work day (extra credit) |
ICPC test program at SLU
|
|
Go(Relians) Again
|
| Monday, Dec. 2 |
Number Theory Algorithms |
|
Lecture Notes |
|
| Wednesday, Dec. 4 |
RSA |
|
Lecture Notes |
|