| Wk |
Day |
Date |
Topic | Resources | Events |
|
| 1 | Mon | Jan 13 | Introduction to the Course | Course Website | |
|
|
| Wed | Jan 15 | Analysis of Quicksort | CLRS Chapter 7.4
Quicksort Analysis notes | |
|
|
| Fri | Jan 17 | Lower bounds for Sorting | CLRS Chapter 8.1
Comparison Sort Lower Bound Lecture Notes | Pretest |
|
| 2 | Mon | Jan 20 | Martin Luther King Day | | No Class |
|
|
| Wed | Jan 22 | Finding
Minimum
Maximum
ith item | CLRS Chapter 9.1-9.2
Medians and Order Statistics Lecture Notes | |
|
|
| Fri | Jan 24 | ith order statistic:
A better algorithm | CLRS Chapter 9.3 | |
|
| 3 | Mon | Jan 27 | Finish Order Statistics
Start Dynamic Programming
Dynamic Programming
The Elements of Dynamic Programming
Example: MCM | | |
|
|
| Wed | Jan 29 | Dynamic Programming
Example: MCM
Example: 0-1 Knapsack | CLRS Chapter 15.1-15.3
An Introduction to Dynamic Programming Lecture Notes | |
|
|
| Fri | Jan 31 | More Dynamic Programming
LCS | | |
|
| 4 | Mon | Feb 03 | LCS | CLRS Chapter 15.4-15.5
Dynamic Programming Lecture Notes | HW1 Due |
|
|
| Wed | Feb 05 | Optimal Polygon Triangulation | | |
|
|
| Fri | Feb 07 | Greedy Algorithms:
Activity Selection Problem | Introduction to Greedy Algorithms (review)
Minimum Spanning Trees (review)
Greedy Algorithms
CLRS Sections 16.1-16.3
| |
|
| 5 | Mon | Feb 10 | Review of Homework 1 | | |
|
|
| Wed | Feb 12 | Minimum Spanning Trees |
Greedy Algorithms Lecture Notes | |
|
|
| Fri | Feb 14 | Huffman Encoding |
Huffman Encoding Info and Applet | |
|
| 6 | Mon | Feb 17 | Optimal Binary Search Trees | | |
|
|
| Wed | Feb 19 | Amortized Analysis | CLRS Chapter 17
Amortized Analysis Lecture Notes | |
|
|
| Fri | Feb 21 | Amortized Analysis | | HW 2 due |
|
| 7 | Mon | Feb 24 | Amortized Analysis | | |
|
|
| Wed | Feb 26 | Network Flow | CLRS Sections 26.1-26.3
Maximum Flow Lecture Notes | |
|
|
| Fri | Feb 28 | Network Flow Problems | | |
|
| 8 | Mon | Mar 03 | Residual Networks and Augmenting Paths | | |
|
|
| Wed | Mar 05 | Max-flow min-cut theorem | | |
|
|
| Fri | Mar 07 | Ford Fulkerson Method |
Ford Fulkerson Algorithm Applet
| |
|
| 9 | Mon | Mar 10 | P, NP, NP-Complete | P, NP, and
NP-Complete (review)
| HW 3 due |
|
|
| Wed | Mar 12 | Review for Midterm | | |
|
|
| Fri | Mar 14 | Searching, Sorting, and Bounds
Greedy Algorithms
Dynamic Programming
Amortized Analysis
Network Flow | Pencil, Paper | Midterm Exam |
|
|
Spring Break Week |
|
| 10 | Mon | Mar 24 | Introduction to P, NP, NPC | CLRS Section 34.1
NP-Completeness Lecture Notes | |
|
|
| Wed | Mar 26 | Verification and NP | CLRS section 34.2 | |
|
|
| Fri | Mar 28 | NPC and Reductions | CLRS 34.3 | |
|
| 11 | Mon | Mar 31 | NPC Proofs | CLRS 34.4 | |
|
|
| Wed | Apr 02 | NPC Proofs | 34.4-34.5 | |
|
|
| Fri | Apr 04 | NPC Proofs | | |
|
| 12 | Mon | Apr 07 | Approximation Algorithms | CLRS Chapter 35 | |
|
|
| Wed | Apr 09 | Approximation Algorithm:
Travelling Salesman Problem | | |
|
|
| Fri | Apr 11 | CSE Day | | No Class
HW4 Due |
|
| 13 | Mon | Apr 14 | Approximation Algorithm:
Set Covering | | |
|
|
| Wed | Apr 16 | Approximation Algorithm:
Subset-Sum | | |