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
· P/NP
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.
Lecture notes:
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)
Tutorials:
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.
Regarding
CS3230R
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.