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

Tentative Lectures Schedule and Lecture Notes

Tentative Schedule of Lectures

  • Week 0: 04-Aug-2009 -- Course Briefing (20 mins) | Overview (ppt)

  • Week 1: 11-Aug-2009 -- L01: Algorithms Technology, Stable Marriage Problem, Sample Problem, Interval Scheduling

  • Week 2: 18-Aug-2009 -- L02: Analysis of Algorithms (also Master Theorem), Randomized Quicksort

  • Week 3: 25-Aug-2009 -- L03: Greedy Algorithm: Interval Scheduling Problem, Shortest Path Algorithms, MST, Heaps

  • Week 4: 01-Sep-2009 -- L04: Dynamic Programming Algorithms:

  • Week 5: 08-Sep-2009 -- Lecture cancelled (Replaced on 22-Sep-2009)

  • Week 6: 15-Sep-2009 -- L05: Data Structures: Abstraction in Problem Solving, Augmenting DS, LEDA, Binomial Heaps

  • Break Week: 22-Sep-2009 -- L06: Amortized Complexity, F-Heaps (Replacement lecture)

  • Week 7: 29-Sep-2009 -- L07: DNSRA Project, Problem Reduction
  • Week 8: 06-Oct-2009 -- L08: NP-Completeness, Proving NP-Completeness
  • Week 9: 13-Oct-2009 -- L09: Cook's Theorem, Approximation Algorithms

  • Week 10: 20-Oct-2009 -- L10: Approximation Algorithms and Network Flows
  • Week 11: 27-Oct-2009 -- L11: Network Flows and Maximum Matching
  • Week 12: 03-Nov-2009 -- L12: Graph Partitioning and BAP Case Study
  • Week 13: 10-Nov-2009 -- L13: Project Presentations Local Search Algorithms
  • STUDY WEEK --
  • Week E2: 30-Nov-2009 [Mon] -- Final Exam (OPEN BOOK) AM

    • CS5206 Lectures Page
    CS5206 Home Page