Instructor: Brendan Juba
Office Hours: 5:30-6:30, (after lecture) Hillman 60 -> Jolley 508. (I will answer questions in Hillman 60 following lecture, and return to Jolley 508 when there are no more questions.)
Email:
Monday and Wednesday, 4:00-5:30 PM, Hillman 60.
Instructor: Brendan Juba
Office Hours: 5:30-6:30, (after lecture) Hillman 60 -> Jolley 508.
(I will answer questions in Hillman 60 following lecture, and return to
Jolley 508 when there are no more questions.)
Email:
Please use the class Piazza board for all course-related communication We will use it for course announcements. Email of a personal/confidential nature may be directed to the instructor at the email above.
The schedule of topics for class meetings and of assignments may be subject to change as the semester progresses. Readings marked "KT" refer to sections of the course text relevant to each class. Assignments will be linked from the schedule as they are assigned.
| Lecture no. | Topic | Dates | Homework |
| Lec. 1 | Divide-and-Conquer I Matrix multiplication and Strassen's algorithm similar to KT 5.5 summary | 1/14 |
Assigned:
Review Ch. 2 of KT (asymptotic analysis). Review KT 5.1-5.2 (divide and conquer algorithms) |
| Lec. 2 | Greedy Algorithms I Scheduling KT 4.1 summary | 1/16 | Assigned: Homework 1 | Holiday | MLK Day - no lecture | 1/21 |
| Lec. 3 | Dynamic Programming I Weighted Scheduling KT 6.1-6.2 summary | 1/23 | Assigned: Review Ch. 3 of KT (on graphs). |
| Lec. 4 | Greedy Algorithms II Scheduling all requests; start Minimum Spanning Tree KT 4.5 summary | 1/28 |
Due:
Homework 1 Assigned: Homework 2 |
| Lec. 5 | Greedy Algorithms III Two algorithms: Kruskal and Prim finish KT 4.5 summary | 1/30 | |
| Lec. 6 | Divide-and-Conquer II: The closest pair problem KT 5.4 summary | 2/4 |
Due:
Homework 2 Assigned: Homework 3 |
| Lec. 7 | Dynamic Programming II Knapsack and Sequence Alignment KT 6.4, 6.6 summary | 2/6 | |
| Lec. 8 | Max Flow I Ford-Fulkerson Algorithm KT 7.1 summary | 2/11 |
Due:
Homework 3 Assigned: Homework 4 |
| Lec. 9 | Max Flow II Min-Cut KT 7.2, start 7.5 summary | 2/13 |
sample midterm exam |
| Lec. 10 | Reductions I Matchings and more finish KT 7.5, 7.10, start 8.1 summary | 2/18 |
Due:
Homework 4 |
| Exam 1 | Midterm Exam 1(in class) | 2/20 | |
| Lec. 11 | Reductions II Relating problems finish KT 8.1, start 8.2 summary | 2/25 | Assigned: Homework 5 |
| Lec. 12 | Intractability and NP-completeness KT finish 8.2, 8.3, start 8.4 summary | 2/27 | |
| Lec. 13 | Intractability via Reductions I KT finish 8.4, 8.8 summary | 3/4 |
Due:
Homework 5 Assigned: Homework 6 Review basic probability, KT 13.12, KT 13.3 |
| Lec. 14 | Average-case analysis: Naive trees and hashing summary | 3/6 | Holiday | Spring Break - no lecture | 3/11 | Holiday | Spring Break - no lecture | 3/13 |
| Lec. 15 | Randomized algorithms I From trees to treaps Roughly, KT 13.5; see also KT 13.9 summary | 3/18 |
Due:
Homework 6 Assigned: Homework 7 |
| Lec. 16 | Intractability via Reductions II KT 8.5, 8.7 summary | 3/20 | |
| Lec. 17 | Randomized algorithms II Hashing KT 13.6 summary | 3/25 |
Due:
Homework 7 Assigned: Homework 8 |
| Lec. 18 | Randomized algorithms III: Algorithms that may err KT 13.2, start 4.6 summary | 3/27 |
sample midterm exam |
| Lec. 19 | On-line algorithms I: Amortized Analysis KT 4.6, start 13.8 summary | 4/1 |
Due:
Homework 8 |
| Exam 2 | Midterm Exam 2(in class) | 4/3 | |
| Lec. 20 | On-line algorithms II: Competitive Analysis KT 13.8, 11.1, 11.3 summary | 4/8 | Assigned: Homework 9 |
| Lec. 21 | Approximation algorithms I Random solutions; start LPs KT 13.4, start 11.6 summary | 4/10 | |
| Lec. 22 | Approximation algorithms II Relaxing and rounding KT 11.6 summary | 4/15 |
Due:
Homework 9 Assigned: Homework 10 |
| Lec. 23 | Approximation algorithms III Polynomial-time approximation schemes KT 11.8 summary | 4/17 | |
| Lec. 24 | Smoothed Analysis summary | 4/22 |
Due:
Homework 10 |
| Lec. 25 | Span analysis of divide-and-conquer summary | 4/24 | Practice final exam |