CS325 : Analysis of Algorithms |
|
Date |
Topics |
Reading Assignment |
Announcements/Notes |
|
Jan. 8 |
Introduction; Big O notation. Scanned Note |
Chapter 0 |
|
|
Jan 10 |
Graphs, data structure for representing
graphs, DFS |
Chapter 3.1, 3.2 |
|
| Jan 12 |
DFS, connected components Scanned Note |
Chapter 3.2 |
HW1 due, HW2 out |
| Jan 15 |
MLK day, no class |
||
| Jan 17 |
DFS in directed graphs strong connectivity Scanned Note |
Chapter 3.3, 3.4 |
|
| Jan 19 |
DAG, tiered connectivity Scanned Note |
Chapter 3.3, 3.4 |
HW2 due, HW3 out |
| Jan 22 |
Breath first search, shortest path Scanned Note | Chapter 4.1, 4.2 |
|
| Jan 24 |
Graphs with edge lengths, Dijkstra's
algorithm Scanned Note |
Chapter 4.3, 4.4 |
|
| Jan 26 |
Dijkstra's algo. (cont.) Priority Queue, heap Scanned note |
Chapter 4.5 |
|
| Jan 29 |
Heap (cont.) Greedy algorithms - Minnimum spanning tree Scanned note |
Chapter 4.5, 5.1 Notes on interval scheduling |
HW3 Due |
| Jan 31 |
Midterm 1 (up to ontents covered in
01/26) |
Practice questions part1 part2 |
|
| Feb 2 (F) |
Greedy algortihms MST cont. Prim's algo Scanned note |
Chapter 5.1 |
HW4 out |
| Feb 5 (M) |
Greedy algo, Kruskal algo. Scanned note |
Chapter 5.1 |
|
| Feb 7 (W) |
Kruskal's algo (union-find data
structure) Scanned note Divide and conquer merge sort |
Chapter 2.1-3 |
|
| Feb 9 (F) |
Divide and conquer recurrence relations Scanned note |
Chapter 2.1-3 |
HW4 due HW5 out |
| Feb 12(M) |
DP-edit distance Scanned note |
||
| Feb 14(W) |
DP-edit distance (cont) Shortest Path Revisited Scanned notes |
||
| Feb 16(F) |
DP Shortest path (finished) Knapsack w. repetition Scanned notes |
HW5 due HW6 out |
|
| Feb 19(M) |
DP Knapsack w/o repition Scanned notes |
||
| Feb 21(W) |
Lower bounds on sorting Scanned notes |
||
| Feb 23(F) |
Review |
HW6 due |
|
| Feb 26(M) |
Midterm 2 |
Practice questions Solutions |
Programming assignment 2 posted |
| Feb 28(W) |
P and NP |
Chapter 8.1 8.2 |
|
| Mar 2 (F) |
Reduction |
Chapter 8.3 |
HW 7 out |
| Mar 5 (M) |
Reduction |
Chapter 8.3 |
|
| Mar 7 (W) |
NP-completeness scanned notes, including the last few lectures |
Chapter 8.2-3 |
|
| Mar 9 (F) |
NP-completeness by generalization |
Chapter 8.3 |
HW7 due HW8 out |
| Mar 12(M) |
Cancelled |
||
| Mar 14(W) |
Heuristic Search for hard problems -
backtracking Scanned notes |
Chapter 9.1.1 |
|
| Mar 16(F) |
Final
review |
HW8 due |
|
| Mar 21 |
Final exam |
Practise questions sample soln to practice questions |
.