**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

· Divide and Conquer

· Greedy Algorithms

· Network Flow

· Dynamic Programming

· P/NP

Lectures:
Every Thursday 3-5 pm at LT15. First lecture on 16^{th} August, 2012.

Tutorials:

Group 1 :
Tuesdays 2-3pm (in AS6-0426).

Group 2 :
Tuesdays 3-4pm (in AS6-0426).

Group 3 :
Tuesdays 4-5pm (in AS6-0426).

Group 4 :
Wednesdays 2-3pm (in COM2-0108).

Group 5 :
Wednesdays 3-4pm (in COM2-0108).

Office
Hours for Rahul Jain: Every Thursday 1-2 pm (or by appointment).

Office Hours for Bakhadyr Khoussainov : Every Wednesday 10am-11am (or by appointment).

Name :
Rahul Jain

Office :
S15-04-01

Email:
first name at comp dot nus dot edu dot sg

Phone:
65168826 (off).

Name: Bakhadyr Khoussainov

Office:
COM2-03-30

Email: bmk
at cs dot auckland dot ac dot nz

Phone:
65162825

We will use
the following as textbook. All that we will study will be from this book.

Title : Algorithm Design

Authors : Jon Kleinberg and Éva Tardos

Publication : Pearson

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)

4. “Algorithms”
by R. Johnsonbaugh and M. Schaefer (Pearson Prentice Hall, 2004)

There will
be one midterm, worth 20 marks, and one final examination, worth 40 marks.
These will be open book exams.

In addition
there will be several quizzes conducted during lectures worth total of 15 marks
(these will also be open book).

There will
be 5 marks for forum participation in IVLE.

There will
5 marks for the answers during tutorial classes and 15 marks for tutorial answer
sheets.

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:

We will use parts of the following.

The following slides were created by Kevin Wayne and are
distributed by Pearson Addison-Wesley.

The following slides are created by Rahul Jain

The following slides are created by Bakhadyr Khoussainov

Tutorials:

Tutorial sheets will be made available online a week before they are
discussed in the tutorial classes. You will be required to hand in your tutorial
solutions at the start of your tutorial class. They will be marked and handed
over back in the next tutorial class. There will be 15 marks in total for all
the tutorial answer sheets.

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.

All the
five tutorial classes will be taken also by the two lecturers. The tutorial
sheets will be graded by tutors:

Name: Zhang
Jiangwei

Email: jiangwei at
nus dot edu dot sg

Name: Le
Minh Khue

Email:
minhkhue at comp dot nus dot edu dot sg

Tutorials sheets are available in IVLE.

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.