CS5206: Foundations in Algorithms
School of Computing, National University of Singapore
(Fall Sememster 2010)

Tentative Lectures Schedule and Lecture Notes

Tentative Schedule of Lectures

  • Week 0: 03-Aug-2010 -- No Course Briefing

  • Week 1: 10-Aug-2010 -- L01: Algorithms as Technology, Stable Marriage Problem, Five Sample Problems

  • Week 2: 17-Aug-2010 -- L02: Analysis of Algorithms, Quicksort, Divide and Conquer, Master Theorem

  • Week 3: 24-Aug-2010 -- L03: Greedy Algorithm: Interval Scheduling, Shortest Path Algorithms, MST, Heaps

  • Week 4: 31-Aug-2010 -- L04: Dynamic Programming Algorithms:

  • Week 5: 07-Sep-2010 -- L05: Data Structures: Abstraction in Problem Solving, Augmenting DS, LEDA, Binomial Heaps

  • Week 6: 14-Sep-2010 -- L06: Amortized Complexity, F-Heaps

  • Week B: 21-Sep-2010 --     ** BREAK **       ** BREAK **

  • Week 7: 28-Sep-2010 -- L07: DNSRA Project, Problem Reduction

  • Week 8: 06-Oct-2010 -- L08: NP-Completeness, Proving NP-Completeness

  • Week 9: 12-Oct-2010 -- L09: Cook's Theorem, Approximation Algorithms

  • Week 10: 19-Oct-2010 -- L10: Approximation Algorithms and Network Flows

  • Week 11: 26-Oct-2010 -- L11: Network Flows and Maximum Matching

  • Week 12: 02-Nov-2010 -- L12: Graph Partitioning and BAP Case Study

  • Week 13: 09-Nov-2010 -- L13: Local Search Algorithms
  • STUDY WEEK: Project Presentation / Demo
  • Week E2: 30-Nov-2010 [Tue] -- Final Exam (OPEN BOOK) PM

    • CS5206 (Fall 2010) Lectures Page
    CS5206 (Fall 2010) Home Page