CS5800 M Algorithms
(section 1) Spring 2012
Syllabus (subject to change)
Created: Mon 2 May 2005
Last modified:
|
Date |
Topic |
Reading |
Assignments |
||||
1 |
Tue |
Jan 10 |
Introduction
Fibonacci |
CLRS chapters 1,2 | ||||
2 |
Thur |
Jan 11 |
Analysis; Order of Growth | CLRS chapter 3 growth table 1 growth table 2 |
||||
| 3 | Tue |
Jan 17 |
Math primer Recurrences |
CLRS Appendix A | HW1 |
|||
| 4 | Thur |
Jan19 |
Recurrences | CLRS chapter 4 Iteration Method Master Theorem Simple Extended Master Theorem Advanced Notes on Master Theorem |
||||
| 5 | Tue |
Jan 24 |
HeapSort
MergeSort Divide and Conquer |
CLRS Chapter 6 |
HW1 due (beginning of class) HW2 |
|||
| 6 | Thur |
Jan26 |
Partition QuickSort QuickSort Analysis |
CLRS Chapter 7 |
||||
| 7 | Tue |
Jan 31 |
Median order statistics |
CLRS Chapter 9 |
HW3 |
|||
| 8 | Thur |
Feb 2 |
Sorting by comparison limits Sorting in linear time |
CLRS Chapter 8 |
||||
| 9 | Tue |
Feb 7 |
Greedy Method More on induction |
Chapter 16 |
HW4 due Thursday Feb 16 |
|||
| 10 | Thur |
Feb 9 |
Greedy Method |
|||||
| 11 | Tue |
Feb 14 | Dynamic programming | Chapter 15 |
HW5 |
|||
| 12 | Thur |
Feb 16 |
Dynamic programming | |||||
| 13 |
Tue |
Feb 21 | Dynamic programming | HW6 |
||||
| 14 | Thur |
Feb 23 |
Dynamic programming |
|
||||
| Tue | Feb 28 |
Midterm week | ||||||
| Thur |
Mar 1 |
Midterm week |
|
|||||
|
|
||||||||
Tue |
Mar 6 |
SPRING BREAK no class |
||||||
| Thur | Mar 8 |
SPRING BREAK no class |
|
|||||
| 15 | Tue |
Mar 13 |
Hash tables |
HW7 |
||||
| 16 |
Thur | Mar 15 |
Amortized Analysis |
|
|
|||
| 17 |
Tue |
Mar 20 |
Graphs representation, BFS DFS, cycles DAG, topological sort |
HW8 |
||||
| 18 |
Thur | Mar 22 |
Spanning trees Kruskal, Prim |
|
||||
| 19 |
Tue |
Mar 27 |
Single source shortest path Bellman Ford, Dijkstra |
HW9 |
||||
| 20 | Thur |
Mar 29 |
All-pair shortest path | |||||
| 21 | Tue |
Apr 3 |
Network flows | HW10 |
||||
| 22 | Thur | Apr 5 |
NP Completeness, Approx Algorithms | |||||
| 23 | Tue |
Apr 10 |
Number Theory |
HW11 |
||||
| 24 | Thur | Apr 12 |
Intro to cryptography | |||||
| 25 |
Tue |
Apr 17 |
Linear Programming |
|||||
| 26 |
Thur | Apr 19 |
||||||
| Apr23-28 |
Exam week |
|||||||
