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

Logistics:

 

Lectures: Every Thursday 3-5 pm at LT15. First lecture on 16th 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).

Lecturer:

 

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

Books:

 

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)

 

Evaluations:

 

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.

 

Slides

 

The following slides are created by Rahul Jain

 

Slides

 

The following slides are created by Bakhadyr Khoussainov

 

Slides

 

 

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.