PineWikiUnless otherwise specified, all readings are in LevitinBook. Click on each date for detailed notes (if available). As always, the future is uncertain, so you should take parts of the schedule that haven't happened yet with a grain of salt.
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
/2004-01-13: Introduction: what algorithms are. What we will do in this course. Basic principles of algorithm design. Readings: Chapter 1, ComputationalModel, AlgorithmAnalysis.
/2004-01-15: Mathematical tools for algorithm analysis: measures of performance, asymptotic notation, computing sums. Readings: Sections 2.2, Appendix A, ProvingInequalities, AsymptoticNotation.
/2004-01-20: Analysis of iterative algorithms; counting steps, summations. Readings: Sections 2.1 and 2.3, ComputingSums.
/2004-01-22: More mathematical tools: recurrence relations and their solution. Readings: Sections 2.4-2.5, Appendix B, SolvingRecurrences.
/2004-01-27: General principles of algorithm design. Readings: ProblemSolvingTechniques, AlgorithmDesignTechniques.
/2004-01-29: Brute-force algorithm design. Readings: Chapter 3, BruteForce.
/2004-02-03: Divide and conquer algorithms; general principles and examples. Readings: Chapter 4, DivideAndConquer.
/2004-02-05: Randomized divide and conquer algorithms: QuickSelect and QuickSort.
/2004-02-10: DecreaseAndConquer algorithms: iterative (DecreaseByConstant) algorithms and basics of GraphAlgorithms. Readings: Sections 5.0-5.1.
/2004-02-12: More on GraphAlgorithms: DepthFirstSearch, BreadthFirstSearch, and applications. Readings: Sections 5.2-5.3.
/2004-02-17: DecreaseByConstantFactor and DecreaseByVariableFactor algorithms. Readings: Sections 5.5-5.6.
/2004-02-19: DataStructures: BalancedTrees. Readings: Sections 6.3 and 7.4.
/2004-02-24: Randomized DataStructures: HashTables and SkipLists. Readings: Section 7.3.
2004-02-26: Midterm exam. In class. See CS365/Assignments/MidtermExam.
/2004-03-23: Basics of CombinatorialOptimization and DynamicProgramming. Readings: Chapter 8.
/2004-03-25: More examples of DynamicProgramming.
/2004-03-30: GreedyMethod. Readings: Chapter 9.
/2004-04-01: ShortestPath algorithms and applications.
/2004-04-06: MaxFlow algorithms and applications.
/2004-04-13: LowerBounds, ComputationalComplexityTheory, and PvsNp. Readings: Sections 10.1-10.3.
/2004-04-15: More PvsNp. NP-completeness reductions.
/2004-04-20: ApproximationAlgorithms. Readings: Section 11.3.
2004-05-05, starting at 9:00am: Final exam. See CS365/Assignments/FinalExam.