## Syllabus |
## Schedule |
## Assignments |

- Readings in
**bold**are directly relevant to the lecture and are mandatory. You are expected to do the reading**before class**so that you will be ready to participate. - Readings not in bold are for {background, to refresh your memory, for fun}. I strongly encourage you to at least skim them.
- This schedule will be updated regularly as the course goes on.
**Check back here frequently!**

# | Date | Topic | Reading |
---|---|---|---|

1 | F 9/8 | Course Overview, Stable Matching | --- |

2 | T 9/12 | Greedy Algorithms: Interval Scheduling, Minimizing Lateness | KT 4.1-4.3KT 1-3 |

3 | F 9/15 | Greedy Algorithms: Shortest Paths, Minimum Spanning Trees | KT 4.4-4.6 |

4 | T 9/19 | Divide-and-Conquer Algorithms: Counting Inversions, Selection, Closest Pair | KT 5.1-5.4Optional: Erickson 1.7 |

5 | F 9/22 | Divide-and-Conquer: Integer Multiplication and FFT | KT 5.5-5.6 |

6 | T 9/26 | Dynamic Programming: Weighted Interval Scheduling | KT 6.1-6.2 |

7 | F 9/29 | Dynamic Programming: Finish Basic Techniques | KT 6.3-6.5Optional: Erickson 5 |

8 | T 10/3 | Dynamic Programing: Edit Distance / Alignments, Shortest Paths | KT 6.6-6.10Optional: Erickson 6.1 |

9 | F 10/6 | Network Flow: Basic Concepts, Duality, Ford-Fulkerson Algorithm | KT 7.1-7.2 |

10 | T 10/10 | Network Flow: Choosing Good Paths | KT 7.3-7.4 |

11 | F 10/13 | Network Flow: Applications, Wrap-Up | KT 7.5-7.6KT 7.7-7.13 |

- | T 10/17 | No Class---FOCS |
--- |

12 | F 10/20 | Midterm |
--- |

13 | T 10/24 | Intractability: NP-completeness and reductions | KT 8.1-8.5Optional: Erickson 30.1-30.9 |

14 | F 10/27 | Intractability: More hard problems | KT 8.7-8.8Optional: Erickson 30.10-30.11 |

- | T 10/31 | No Class---Flight Delay :( |
--- |

15 | F 11/3 | Finish NP-Completeness Introduce Randomized Algorithms |
Erickson 13.1-13.3 |

16 | T 11/7 | Randomized Algorithms: String Matching and Contention Resolution | KT 13.1Optional: Review KT 13.12 |

17 | F 11/10 | Randomized Algorithms: Global Min-Cut and Expectation | KT 13.2-13.5 |

18 | T 11/14 | Randomized Algorithms: Dictionaries, Hashing, Load Balancing | KT 13.6, 13.10 |

19 | F 11/17 | Finish Randomized Algorithms Start Linear Programming |
--- |

- | F 11/24 | No Class---Thanksgiving |
--- |

- | T 11/28 | No Class---Jon in Berkeley |
--- |

20 | F 12/1 | Linear Programming: Basic Concepts, Simplex Algorithm | Kevin Wayne's Notes I Optional: Erickson 26, 27 |

21 | T 12/5 | Linear Programming: Applications, Duality | Kevin Wayne's Notes II |

22 | F 12/8 | Online Learning, Course Wrap-Up | --- |

23 | W 12/13 | Final Exam: 1:00-4:30 in 110 WVH |
--- |