CS21003/CS29003

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

Schedule

Instructor     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.

Tests

Class Test 1: 13-September-2011 [Questions with solutions]
Class Test 2: 08-November-2011 [Questions with solutions]
Mid-semester test: 27-September-2011 [Questions with solutions]
End-semester test: 22-November-2011 [Questions with solutions]
Lab Test 1: 12-September-2011 [Questions | Solution]
Lab Test 2: 14-November-2011 [Questions | Solution]

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

Instructor		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

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

[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.

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