CS21003 Algorithms I
 CS29003 Algorithms Laboratory
Autumn 2011, L-T-P: 3-1-0 
L-T-P: 0-0-3 

Schedule | Notices | Syllabus | References | Tests | Assignments


Instuctor     Abhijit Das
Timing     Theory: Slot E [WED(11:30--12:30), THU(10:30--11:30), FRI(08:30--10:30)]
Lab: MON(01:30--04:30)
Venue     Theory: Room No 120, CSE Department
Lab: CIC (Computing Lab 1)
Teaching Assistants     Angshuman Karmakar
Binanda Sengupta
Indrasish Saha
Prasenjit Dhole
Ritwika Ghose
Sabyasachi Karati
Satrajit Ghosh

Notices and Announcements

July 19, 2011
Because of shortage of space, no non-CSE students will be allowed to register for this course (theory or lab) in Autumn 2011.

Tentative Coverage

Complexity of algorithms Asymptotic notations and their significance, complexity analysis of algorithms, worst case and average case. 2 hours
Algorithmic paradigms Recursion, divide-and-conquer, greedy, dynamic programming, lower bounds and optimal algorithms. 8 hours
Basic data structures Stacks and queues, graphs and trees, binary trees. 2 hours
Heaps Heaps, priority queues, min-max heaps, heap sort. 4 hours
Dynamic search structures Binary search trees, height balancing, B-trees, skip lists, hashing. 8 hours
Algorithms on arrays Linear-time median finding, sorting in linear time (counting sort, radix sort, bucket sort), string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms). 8 hours
Graph algorithms Traversal (BFS, DFS, topological sort), minimum spanning trees (Prim and Kruskal algorithms), shortest paths (Dijkstra and Floyd-Warshal algorithms) 8 hours

Books and References

[1]     Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press/McGraw-Hill, 2001.
[2]     Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
[3]     Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
[4]     Udi Manber, Algorithms -- A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[5]     Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins, 1997.
[6]     Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
[7]     Muhammad H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific, 1999.
[8]     Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1995.
[9]     Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, third edition, Addison-Wesley, 2000.
[10]     Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.


Programming Assignments

No Topic Start date Due date More info
Assignment 0 Complexity of algorithms July 25, 2011 Not for submission Solution
Assignment 1 Algorithm design techniques August 08, 2011 August 29, 2011 Solution
Assignment 2 Graphs, trees and heaps August 29, 2011 October 10, 2011 Solution
Lab Test 1 Graphs, trees and heaps September 12, 2011 September 12, 2011 Solution | Tree constructor
Assignment 3 Dictionaries October 10, 2011 October 31, 2011 Solution
Assignment 4 Graph algorithms October 31, 2011 November 14, 2011 Solution
Lab Test 2 Graphs, trees and heaps November 14, 2011 November 14, 2011 Solution

Submission site

Schedule | Notices | Syllabus | References | Tests | Assignments