CSL 356: Analysis and Design of Algorithms Semester II 2008-2009 Instructor: Huzur Saran

Lectures: Mon, Thurs, 9:30-10:55AM, Venue: IIA204

Tutorials: MF 2-3PM, Rooms: IIA204

IMPORTANT: Students attending this course should be a member of the Google Group on CSL 356. Click here to be a member.

Teaching Assistants:

• Madhulika
• Arindam Pal

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 (Prof Sandeep Sen)

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

Background Material in Counting and Probability (Prof Sandeep Sen)

Tutorial Problems Discussion Etc

Problem Set 0

Discussion

Reference books

Algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, McGraw-Hill.

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, Prentice Hall.