CSL 356: Analysis and Design of Algorithms Semester I 2009-2010 Instructor : Sandeep Sen

Lectures: T,Th,F 11 - 11:50, Venue IIA 204

Tutorials: T 3-4 p , Th 3-4 p Venue IIA 204

Office hours: Th 4-5 p

Teaching Assistant:

• Manoj G. (CSE Research Scholar Room, Office hrs Tue, Thu 4-5 p)

Major exam Solutions and grading guidelines

The total will be computed as Minors 1 and 2 - 20% each, Major 40%, Quizes - and tutorial performance - 20%.

Major answerscripts can seen on Tue (1st Dec)- 11:30 - 12:30 ( strictly abide by this time please)

Prerequisites: CSL201 (Data Structures) Recommended : CSL105 (Discrete Structures)

Contents. RAM model and complexity; O(log n) bit model, integer sorting and string sorting. Review of fundamental data structures; Red-black trees, mergeable heaps, interval trees. Fundamental design methodologies and their implementations; Search Techniques, Dynamic Programming, Greedy algorithms, Divide-and-Conquer, Randomised techniques. Algorithms for set manipulations, their implementations and applications; Union-Find Randomized data structures; Skip lists, Universal Hash functions, Graph Algorithms with implementation issues; Depth-First Search and its applications, minimum Spanning Trees and Shortest Paths. Convex hulls, sorting, Selection Matrix multiplication, pattern matching, integer and polynomial arithmetic, FFT, introduction to the theory of lower bounds, NP-Completeness and Reductions. Approximation algorithms.

Lecture Notes

For any feedback/corrections regarding notes please send email to me with subject CSL356

Background Material in Counting and Probability

Tutorial Problems

Practice Problems 1

Problem Set 1

Solutions

Problem Set 2

Solutions

Practice problems 2(with solutions)

Minor 1 solutions

Problem Set 3

Solutions

Quiz 2 soln

Problem Set 4

Solutions

Problem Set 5

Solutions

Problem Set 6

Programming assignment

Reference books

Algorithms by Dasgupta, Papadimitriou and Vazirani, Pub: Tata McGraw-Hill.

The Design and Analysis of Computer Algorithms by Aho, Hopcroft and Ullman, Pub- Addison Wesley (Indian reprint available)

Algorithm Design: by Kleinberg and Tardos,
Low Priced Ed. by Pearson.

Introduction to Algorithms by Cormen, Leiserson and Rivest, Stein, Pub: MIT Press (Indian reprint by Prentice Hall)

---

Sandeep Sen
Last modified: Mon July 18 2006