- Problem set 3, Due Monday. (TeX)
- Study guide for prelim 1
- CMS has been set up for the course. See the link at the top of the page. We'll post your grades for PS1 there; PS2 will be submitted there as well.
- Problem set 2, Due Friday. (TeX, pset class file)
- Prelim I will be Wednesday, July 17
- Problem Set 1, Due Monday
- Quiz from Monday
- Textbook: "Algorithm Design" by Kleinberg and Tardos. It's required and also useful.

All readings are from the text unless otherwise indicated.

Topic | Date | Reading | Lecture |
---|---|---|---|

7/1 | §1.2 | introduction | |

Greedy algorithms | 7/2 | §1.1 | stable matching |

7/3 | §4.1, §4.2 | interval scheduling, minimizing lateness | |

7/4 | notes | no class (happy independence day!) | |

7/5 | §4.5 | minimum spanning trees | |

7/8 | — | Kruskal's algorithm | |

Divide and conquer | 7/9 | §5.1, §5.2 | mergesort, solving recurrences, master theorem |

7/10 | §5.5, §6.1, §6.2 | large integer multiplication | |

Dynamic programming | fibonacci, memoization, weighted interval scheduling | ||

7/11 | §6.6 | sequence alignment | |

7/12 | §6.8 | Bellman-Ford | |

Flow | 7/15 | browse chapter 7 | network flow, a cornucopia of problems |

7/16 | review | ||

7/17 | prelim I | ||

7/18 | §7.1 | Ford-Fulkerson | |

7/19 | §7.2 | max-flow min-cut theorem | |

7/22 | §7.3 | delta-scaling, circulation | |

7/23 | §7.7 | circulation with lower bounds | |

NP completeness | §8.1 | polynomial time reductions | |

7/24 | §8.3, § 8.4 | definitions of P, NP, NP-hard, NP-complete, | |

§8.2 | vertex cover and independent set | ||

7/25 | §8.2 | fun with SAT | |

7/26 | §8.5 | Hamiltonian paths | |

7/29 | §8.1, §8.5 | traveling salesman problem, set cover | |

7/30 | §8.6, §8.7, §8.8 | 3-coloring, 3d matching, subset sum | |

§8.10 | taxonomy of NP-complete problems | ||

Undecidability | 7/31 | notes, §1, §2 | Turing machines |

8/1 | notes, §5.2 | proving Cook-Levin, nondeterministic Turing machines | |

8/2 | notes, §3 | universal turing machines | |

8/5 | notes, §4.1–§4.4 | undecidability, the halting problem | |

8/6 | notes, §4.5 | Rice's theorem |

- Instructor: Michael George (Mike). mdgeorge@cs.cornell.edu
- TA: Christopher Yu. cy284

- Location: Upson 207
- Monday—Friday, 8:30—9:45
- July 1—August 9

- Location: Upson 4105A (inside of 4105)
- Monday—Friday, 10:00—11:00 or by appointment

- Location: Upson 360
- Time: Monday and Wednesday, 1:30—2:30

- Location: in class (Upson 207)
- Date: Wednesday, July 17

- Location: take home
- Date: distributed in class 8/2, due in class 8/5

- Location: in class (Upson 207)
- Date: August 9 (last day of class)

The course grade will be based on the homeworks (roughly 20%), the exams (roughly 20% prelim I, 20% prelim II, 25% final exam), and class participation (roughly 15%, including mini problem sets that I will give for discussion).

Academic integrity is important for two reasons. The first is that the course is designed to help you learn the material. If you don't do the work you won't learn the material. The second is that we grade you; this would be meaningless if the work we grade is not yours.

You are encouraged to work together to figure out solutions to the problem sets. However, the work you submit should be your own; copying others' papers is forbidden. My strategy is to write rough notes while working with others and then try to write up my submission without referencing them. This ensures both that I learn the material, and that I comply with the requirements of integrity.