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