| Instructor: | Abolfazl Asudeh, Assistant Professor |
| Office: | SEO 1131 (email, home page) |
| Office Hours: | Th 5:00pm-7:00pm |
| GTA: | Steve Huang (email) |
| Office: | TBH 190 |
| Office Hours: | Wed. 2:00-4:00pm |
| Week | Date | Topic | Reading | Notes |
|---|---|---|---|---|
| 1 | 8/27 | Intro and Review Analysis and Design | KT 1 | Jeff Erickson's Intro KT: Intro, KT: Stable matching demo |
| 8/29 | Analysis of algorithms Intro Review: recurrences | KT 1 | ||
| 2 | 9/3 | Review Analysis of algorithms and big-Oh | KT 2.1, 2.2, 2.4, CLRS 3-4 |
KT: Analysis of Algorithms
Combinarorial cheat sheet |
| 9/5 | Review: recurrences | Divide-and-conquer recurrences Class Notes | ||
| 9/6 | Last day to complete late registration. Last day to add/drop a course(s) via the Web. | |||
| 3 | 9/10 | Review: graphs | KT 3, CLSR VI-1 | KT: Graphs Class Notes |
| 9/12 | Review: graphs | KT 3, CLSR VI-1 | Class Notes | |
| 9/13 | Homework 1 posted on Blackboard. The deadline is Tuesday Sep 24 3:29 pm | |||
| 4 | 9/17 | Greedy algorithms | KT 4.1 | KT: Greedy algoritms |
| 9/19 | Greedy algorithms | KT 4.2, 4.3 | ||
| 5 | 9/24 | Greedy | KT 4.3 | HW1 Solution |
| 9/26 | Greedy: shortest path and Minimum Spanning Tree (MST) | KT 4.4, 4.5; CLRS VI-(2,3,4) | KT: Greedy algoritms, continued Jeff Erikson: MST, a different view | |
| 6 | 10/1 | Greedy, Divide and conquer | KT 4.5,CLRS VI-(2,3,4); KT 5 |
KT:Divide and conquer Class Notes |
| 10/3 | Divide and conquer | KT 5 | Class Notes | |
| 7 | 10/8 | Divide and conquer, Dynamic programming | KT 5, 6.1, 6.2; CLRS VII-28 | Dynamic programming
Notes on Recurrences (Fibonacci numbers) Class Notes |
| 10/10 | Homework 2 posted on Blackboard. The deadline is Thursday Oct. 17 3:29 pm | |||
| 10/10 | Dynamic Programming | KT 6.1, 6.2; CLRS 15 | Class Notes | |
| 8 | 10/15 | Dynamic programming | KT 6.1, 6.2 | Dynamic programming
Class Notes |
| 10/17 | Dynamic programming | KT 6.3, 6.4 | Class Notes | |
| 9 | 10/22 | Midterm in class | ||
| 10/24 | Dynamic programming: RNA Secondary Structure | KT 6.5 | ||
| 10 | 10/29 | Dynamic programming: Sequence Alignment | KT 6.6, 6.7 | |
| 10/31 | Dynamic programming: Bellman-Ford | KT 6.8, 6.9, 6.10 | Bellman-Ford shortest paths | 11 | 11/5 | Network flow | KT 7.1, 7.2; CLRS 26.1 | Network flow, Network flow demo |
| 11/7 | Network flow | KT 7.1, 7.2, 7.3, 7.4; CLRS 26.1,2 | Class Notes | |
| 11/8 | Homework 3 posted on Blackboard. The deadline is Friday Nov. 15 11:59 pm | |||
| 12 | 11/12 | Network flow | Class Notes | |
| 11/14 | Network flow and applications | KT 7.5, 7.6,7.7, 7.8; CLRS 26.3 | Network flow applications | |
| 13 | 11/19 | NP completeness and intractability | KT 8.1; CLRS 34-1,2 |
Poly time reductions
Class Notes HW3-solution |
| 11/21 | Poly time reductions | KT 8.1,2,3; CLRS 34 |
Reductions via gadgets: 3-SAT to Independent Set
Class Notes |
|
| 14 | 11/26 | Definition of NP, NP-hard problems | KT 8.3, 8.4, 8.5 | Efficient certifiers and definition of NP
Class Notes |
| 11/28 | Thanks Giving! | |||
| 15 | 12/3 | NP-hard problems | KT 8.3, 8.4, 8.5 |
Sequencing problems Longest path song
Class Notes |
| 12/5 | Final Review | HW4-Solution | ||
| 12/13 | (Friday) Final exam from 1-3pm in SES 230. | |||