CS3230: Design and Analysis of Algorithms

Prerequisites: You should be familiar with material from Discrete Mathematics or Discrete Structures (CS1231), Programming Methodology (CS1101) and Data Structures and Algorithms (CS1102, CS2010).

Lecturer

Sanjay Jain. Office: COM2 #03-59. Email: sanjay@comp.nus.edu.sg

Tutor

Li Xiaohui. Office: COM1 #01-11. Email: lixiaohui@comp.nus.edu.sg

Mid Term Date: 15 October 2010, 6PM. Location LT19.

Syllabus: All topics covered in class upto and including the lectures on 4th October and Tutorials on 12th and 13th October.

Lectures: Mon 12--14

Office Hours:

Sanjay: Mon 11--11:50 or by appointment

Li Xiaohui: Wed 15:00--16:00 or by appointment

Aims and Objectives:

To study various algorithmic techniques for solving problems. To study methods for analysing the complexity of algorithms.

Syllabus

This module introduces different techniques of designing and analysing algorithms. Students will learn about the framework for algorithm analysis, for example, low 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 divide and conquer, greedy algorithms, dynamic programming), NP-completeness and some selected advanced topics.

Course Assessment

End Semester Exam: 60%
Mid Term: 30%
Tutorials Assignments and Class Participation: 10%

Reference Material and Books

R. Johnsonbaugh and M. Schaefer: Algorithms, Pearson Prentice Hall, 2004.