CSL 356: Analysis and Design of Algorithms

Semester I 2013-2014

Instructor : Sandeep Sen


Lectures: T,Th,F 11 - 11:50, Venue IV LT3

Tutorials: 1-1:50pm Cycles 1: T 2:W, 3:Th, 4:F, 5: M Venue IIA 201

Office hours: Thu: 4-5:30pm

Teaching Assistants:

Evaluation policy

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

Attendence requirement Students should abide by the attendence rules stipulated by the Institute. Students failing to meet attendence requirements will be reported for possible penal actions.

Assignment submission Must be submitted within the mentioned deadline as printed typeset document (use of latex is highly recommended). Upto 2 days after deadline, you will be penalised 25%, following which it will be 50% upto 4 days and subsequently no credit. Please mention your Name, Entry number and group number clearly.

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


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)

Lectures

Lecture 1 (Introduction/Computation models)   Lecture 2   Lecture 3   Lecture 4   Lecture 5   Lecture 6   Lecture 7   Lecture 8

Lecture 9   Lecture 10   Lecture 11   Lecture 12-13   Lecture 14   Lecture 15   Lecture 16   Lecture 17   Lecture 18   Lecture 19   Lecture 20
  Lecture 21   Lecture 22   Lecture 23   Lecture 24   Lecture 25   Lecture 26   Lecture 27   Lecture 28   Lecture 29   Lecture 30  
Lecture 31, 32   Lecture 33   Lecture 34   Lecture 35   Lecture 36-37   Lecture 38   Lecture 39   Lecture 40   Lecture 41   Lecture 42


Sandeep Sen
Last modified: Mon July 18 2006