CS3230: Design and Analysis of Algorithms
CS3230: There will be no lecture on 11th April 2018
Prerequisites: You should be familiar
with material from
Discrete Mathematics or
Discrete Structures (CS1231), Programming Methodology (CS1010) and
Data Structures and Algorithms (CS2040) or equivalent.
Lecturer
Sanjay Jain. Office: COM2 #0359. Email: sanjay@comp.nus.edu.sg
(office hours: Wed 14:0015:00)
Tutors:
Ziquan Lan (Office Hours Friday 16:0017:00)
Satyam
Ruomu
Mid Term Date/Time: 13 March 2018, 6PM. Location: MPSH 1A.
Syllabus: All topics covered in class upto and including
the week just before the midterm.
Lectures: Wed 1214
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, lower bound arguments, average case analysis, and the
theory of NPcompleteness. 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,
branchandbound, graph traversal,
amortised analysis, and randomized approaches)
NPcompleteness and some selected advanced topics.
Course Assessment
Final Exam: 50%
Mid Term: 20%
Assignments: 20%
Tutorials Assignments and Class Participation: 10%
Reference Material and Books

R. Johnsonbaugh and M. Schaefer:
Algorithms, Pearson Prentice Hall, 2004.
Lecture Slides/Notes
(The links will be activated as we progress in the semester)
Assignments
Assignment 1
Submit the assignment to my office (COM2 0359) or just before class on
14th Feb, 2018
Answer Sketch Assignment 1 (updated 7th March 2018)
Assignment 2  Silicon Wafers
Submit the programs on codecrunch and writeup on IVLE by 16 March, 2018
Assignment 3
Submit the assignment to my office (COM2 0359) or just before class on
4th Apr, 2018
Answer Sketch Assignment 3
Tutorials