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

Tentative Lectures Schedule and Lecture Notes

Tentative Schedule of Lectures

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

  • Week 1: 11-Aug-2008 -- L01: Motivation, Mathematics of AA

  • Week 2: 18-Aug-2008 -- L02: Randomized Quicksort, Interval Scheduling Problem, Augmenting DS
    IMPT: Lecture Venue changed to SR2, (COM1-204)

  • Week 3: 25-Aug-2008 -- L03: Speeding up Graph Algorithms with Priority Queues

  • Week 4: 01-Sep-2008 -- L04: Binomial Heaps, LEDA, Amortized Analysis

  • Week 5: 08-Sep-2008 -- L05: Fibonacci Heaps, Dynamic Programming

  • Week 6: 15-Sep-2008 -- L06: Dynamic Programming and BAP Case-Study & Project

  • BREAK: break week
  • Week 7: 29-Sep-2008 -- L07: Graph Partitioning; BAP Case Study & Project
  • Week 8: 06-Oct-2008 -- L08: Project, BAP Programming, Local Search Methods;
  • Week 9: 13-Oct-2008 -- L09: Local Search Methods II;

  • Week 10: 20-Oct-2008 -- L10: Network Flows, Problem Reduction
  • Week 11: 27-Oct-2008 -- No class (Deepavali Holiday)
  • Week 12: 03-Nov-2008 -- L11: NP-Completeness, Cook's Theorem
  • Week 13: 10-Nov-2008 -- L12: Proving NP-Completeness, Approximation Algorithms
  • STUDY WEEK -- Course Summary (ppt)
  • Week E2: 01-Dec-2008 -- Final Exam (OPEN BOOK) PM

    • CS5206 Lectures Page
    CS5206 Home Page