CS3230 : Design and Analysis of Algorithms
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), amortised analysis, NP-completeness, and some selected advanced topics.
Prerequisite: (CS2010 or its equivalent) and (CS1231 or MA1100)
Brief list of topics to be covered
Lectures: Every Tuesday 10-12 pm at LT15. First lecture on 16th August, 2011 (9th August is National Day holiday).
Tutorials: All tutorials will take place in COM1/215.
Group 1 : Tuesdays 2-3pm.
Group 2 : Tuesdays 3-4pm.
Group 3 : Tuesdays 4-5pm.
Group 4 : Wednesdays 2-3pm.
Group 5 : Wednesdays 3-4pm.
Office Hours: Every Monday 2-3 pm (or by appointment).
Name : Rahul Jain
Office : S15-04-01
Email: first name at comp.nus.edu.sg
Phone: 65168826 (off).
We will use the following as textbook. All that we will study will be from this book.
Title : Algorithms
Authors : R. Johnsonbaugh and M. Schaefer
Publication : Pearson Prentice Hall, 2004 (International Edition)
You may use the following texts as alternate for your own reference:
1. “Introduction to Algorithms” by Cormen, Leiserson, Rivest and Stein (Prentice Hall, Second Edition)
2. “The Art of Computer Programming, Volume 1 : Fundamental Algorithms” by Knuth (Addison-Wesley, Third Edition)
3. “Algorithms : The Spirit of Computing” by Harel (Pearson Education, Second Edition)
There will be one midterm (worth 35 marks) and one final examination (worth 50 marks). These will be open book exams.
In addition there will be two quizzes conducted during lectures each worth 5 marks (these will also be open book).
There will 5 marks for the tutorials. The details are mentioned below under the tutorial heading.
These together will add up to 100 marks.
There will be no programming assignments.
These are lecture notes using power-point slides. You are encouraged to also take your own notes.
Lecture 1-12 (powerpoint slides)
Lecture 1-12 (pdf)
Tutorial sheets will be made available online a week before they are discussed in the tutorial classes. If you wish you may hand in your tutorial solutions at the start of your tutorial class, however there are no marks for these. A feedback will be provided and they will be handed over back in the next tutorial class.
You must volunteer to present the answers to the questions in the tutorial sheets (on the black board) during the tutorial classes. There will be 5 marks awarded for these.
Besides the tutorials, you are encouraged to work on several other problems given in the text book.
According to my information current implementation of the R-modules is as follows:
- Discuss with the lecturer that you would like to do the R-module.
- The lecturer will decide whether it is appropriate for you after teaching you for a period (around middle of semester or end of semester).
- Start work on it after the lecturer has decided (middle of the current semester or at the next semester). The course will be registered only in the following semester.