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

Tentative Lectures Schedule and Lecture Notes

Tentative Schedule of Lectures

  • Week 1: 08-Aug-2011 -- No lectures

  • Week 2: 15-Aug-2011 -- L01: Course Admin, Algorithms as Technology, Stable Marriage Problem, Five Sample Problems

  • Week 3: 22-Aug-2011 -- L02: Analysis of Algorithms, Quicksort, Divide and Conquer, Master Theorem

  • Week 4: 29-Aug-2011 -- L03: Greedy Algorithm: Interval Scheduling, Shortest Path & MST Algorithms, Heaps

  • Week 5: 05-Sep-2011 -- L04: Dynamic Programming Algorithms [Guest Lecture ?]

  • Week 6: 12-Sep-2011 -- L05: Heaps and Binomial Heaps, LEDA;

  • Week B: 19-Sep-2011 -- L06: Amortized Complexity
    (Note: This replaces Week 1 lecture)

  • Week 7: 26-Sep-2011 -- MID-TERM, Mon, 7:00-9:00pm (in class)

  • Week 8: 03-Oct-2011 -- L07: F-Heap, DNSRA Project

  • Week 9: 10-Oct-2011 -- L08: Problem Reduction, P, NP, NP-Completeness,

  • Week 10: 17-Oct-2011 -- L09: Proving NP-Completeness,

  • Week 11: 24-Oct-2011 -- L10: Cook's Theorem, Approximation Algorithms

  • Week 12: 31-Oct-2011 -- L11: Approx. Algorithms, Network Flows

  • Week 13: 07-Nov-2011 (public holiday) -- L12: Appl of Network Flows
  • STUDY WEEK: 16-Nov-2011 (Wed) -- Project Presentation / Demo
  • Week E2: 29-Nov-2011 [Tue] -- Final Exam (OPEN BOOK) AM

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