CSL 356: Analysis and Design of Algorithms
Semester I 2013-2014
Instructor : Sandeep Sen
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.
For any feedback/corrections regarding notes please send email to me with subject CSL356
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)
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