Date | Assignment | Reading | Subject |
---|---|---|---|

Jan 24 | pre-test | Intro; define problem, efficiency, resource, problem size | |

Jan 26 | pre-test | Discuss pre-test; conclusions from timing data | |

Jan 28 | pre-test | Discuss pre-test;O(*), θ(*), o(*), Ω(*), ω(*),...; Euclid's Game | |

Jan 31 | Analyze Euclid's Game; hypotheses and proofs | ||

Feb 02 | Analyze Euclid's Game; inductive and indirect proofs | ||

Feb 04 | HW1 | 1.1 | Algorithmic problems; proofs about algorithms |

Feb 07 | Last day to add classes | ||

Feb 07 | 1.2 | More algorithmic problems | |

Feb 09 | 2.1-2.3 | Asymptotic analysis in practice | |

Feb 11 | 2.4-2.5 | More examples of asymptotic analysis | |

Feb 14 | 3.1-3.2 | Graphs: definitions, applications, basic algorithms | |

Feb 16 | 3.3-3.4 | Traversals, DFS, and BFS | |

Feb 18 | 3.5-3.6 | Directed graphs | |

Feb 21 | Last day to drop classes | ||

Feb 21 | HW1 due | class presentations of HW1 | |

Feb 23 | HW2 | More on graphs | |

Feb 25 | class presentations of HW1? Directed graphs? | ||

Feb 28 | 4.1-4.2 | Greedy algorithms and proofs about them | |

Mar 02 | 4.3-4.4 | Greedy algorithms; discuss homework | |

Mar 04 | I'll be out of town at a conference; problem session | ||

Mar 07 | HW2 due; HW3 | class presentations of HW2 | |

Mar 09 | I'll be out of town at a conference; problem session | ||

Mar 11 | I'll be out of town at a conference; problem session | ||

3/12-3/20 | Spring break | ||

Mar 21 | Discuss homework | ||

Mar 23 | Discuss homework | ||

Mar 25 | 4.5-4.6 | Minimum spanning trees and data structures for them | |

Mar 28 | Last day to withdraw from classes | ||

Mar 28 | 4.5-4.6 | Minimum spanning trees and data structures for them | |

Mar 30 | 4.5-4.6 | Minimum spanning trees and data structures for them | |

Apr 01 | 5.1-5.3 | Recursion and recurrence relations | |

Apr 04 | 5.4-5.6 | divide and conquer algorithms | |

Apr 06 | HW3 due | class presentations of HW2 and HW3 | |

Apr 08 | 6.1, 6.2 | memoization and dynamic programming | |

Apr 11 | Research day: classes officially cancelled, but I'll be here to make up for missed classes in March | ||

Apr 11 | 6.3, 6.4 | dynamic programming with multi-way choices or extra variables | |

Apr 13 | dynamic programming | ||

Apr 15 | dynamic programming | ||

Apr 18 | dynamic programming | ||

Apr 20 | 6.8-6.9 | shortest paths via dynamic programming | |

Apr 22 | 7.1-7.3, 7.5 | network flow | |

Apr 25 | computability | ||

Apr 27 | 8.1-8.3 | computability; computational complexity | |

Apr 29 | 8.4-8.5 | computational complexity | |

May 02 | HW4 | chap. 9 | space-bounded computational complexity |

May 04 | homework 1-3 due | class presentations of homework | |

May 06 | parallel computational complexity | ||

May 09 | HW4 due | catch up and review for final; class presentations of homework | |

May 16 | 344 final exam, 10:30 AM-12:30 PM |