CSL 356: Analysis and Design of AlgorithmsSemester I 2013-2014Instructor : 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.
Approximation algorithms.
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 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