Media Management Research Lab

National University of Singapore

  • Increase font size
  • Default font size
  • Decrease font size
Home

Teaching

CS3230: Design and Analysis of Algorithms
Course Summary(Fall 2008 )
This module introduces different techniques of designing and analysing algorithms. Students will learn about the framework for algorithm analysis, for example, lower bound arguments, average case analysis, and the theory of NP-completeness. In addition, students are exposed to various algorithm design paradigms. The module serves two purposes: to improve the students' ability to design algorithms in different areas, and to prepare students for the study of more advanced algorithms. The module covers lower and upper bounds, recurrences, basic algorithm paradigms (such as prune-and-search, dynamic programming, branch-and-bound, graph traversal, and randomised approaches), amortized analysis, NP-completeness, and some selected advanced topics.
General Information
People
Announcements and FAQ
Prerequisites
Prerequisites: (CS1102 or CS1102C or CS1102S) and (CS1231 or CS1231S) Preclusions: EEE and CPE students can only take this module as a technical elective to satisfy the program requirements or UEM but not CFM/ULR-Breadth.
Required Reading Materials
Introduction to the design and analysis of algorithms
Author:Anany Levitin
2nd / 2007
ISBN:0321364139
Pearson/Addison WesleyCompulsory11-Aug-2008
Introduction to Algorithms
Author:Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
2e / 2001
ISBN:0262032937
MIT PressSupplementary15-Dec-2008
Lectures
Lecture content subject to change
DateTopicHandouts
Exams and Assignments

This module will have the following assessments:

2 Open book midterms (2x10%) Week 7, Week 13
2 Programming assignments (2x10%), due Friday of Week 6 and Week 11
Tutorial participation (10%)
Open book exam: 29 November 2008, afternoon 1:00 pm, location: MPSH 6 (50%)

Assignment Descriptions
Seminal Papers in Database Research
Academic Integrity
Related Web Sites