CS21003 Algorithms ICS29003 Algorithms Laboratory |
Autumn 2011, L-T-P: 3-1-0 L-T-P: 0-0-3 |

Schedule | Notices | Syllabus | References | Tests | Assignments

## Schedule

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 algorithmsAsymptotic notations and their significance, complexity analysis of algorithms, worst case and average case. 2 hours Algorithmic paradigmsRecursion, divide-and-conquer, greedy, dynamic programming, lower bounds and optimal algorithms. 8 hours Basic data structuresStacks and queues, graphs and trees, binary trees. 2 hours HeapsHeaps, priority queues, min-max heaps, heap sort. 4 hours Dynamic search structuresBinary search trees, height balancing, B-trees, skip lists, hashing. 8 hours Algorithms on arraysLinear-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 algorithmsTraversal (BFS, DFS, topological sort), minimum spanning trees (Prim and Kruskal algorithms), shortest paths (Dijkstra and Floyd-Warshal algorithms) 8 hours ## Books and References

## 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