# 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 #03-59. Email: sanjay@comp.nus.edu.sg
(office hours: Wed 14:00--15:00)

## 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.

## 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 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 divide and conquer, greedy algorithms, dynamic programming, branch-and-bound, graph traversal, amortised analysis, and randomized approaches) NP-completeness 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.

## Assignments

• Assignment 1 Submit the assignment to my office (COM2 03-59) 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 03-59) or just before class on 4th Apr, 2018