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.

- Aaron Handleman,
Section A

Fri 1-2 PM, Cupples II L009 - Erik Tomasic,
Section B

Fri 2-3 PM, Cupples II L009 - Hengxuan Li,
Section C

Fri 3-4 PM, Cupples II L009

- Zongyi Li (head TA)

Office Hours: Sunday, 3-4pm - Priyanshu Jain

Office Hours: Sunday, 3-4pm - Chauncey Hill

Office Hours: Monday 3-4pm - Adam Kern

Office Hours: Tuesday 12:30-1:30pm - Adrien Xie

Office Hours: Wednesday noon-1pm - Sylvia Sheng

Office Hours: Thursday 12:30-1:30pm - Lexie Sun

Office Hours: Friday, 11am-noon - Wentao Wu

Office Hours: Saturday, 3-4pm

- Course overview
- Policy on collaboration and academic integrity
- Guide to submitting homework electronically
- Piazza discussion board

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 |