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

Schedule | Notices | Syllabus | References | Tests | Assignments | Autumn 11

## Schedule

Instuctor Abhijit Das Partha Bhowmick (coinstructor in lab) Timing Theory:Slot B [MON(10:30--11:30), TUE(07:30--09:30), THU(11:30--12:30)]

Lab:WED (01:30--04:30), CICVenue Theory:Room No F-232

Lab:CICTeaching Assistants Arnab Dhar

Debajit Dey

Sabyasachi Karati

Souvik Kolay

Viswas Kumar Kushwaha## Notices and Announcements

- October 17, 2012
- Third (final) set of notes submitted to the photocopy center.
- September 07, 2012
- Second set of notes submitted to the photocopy center.
- July 28, 2012
- Roll lists: CS21003, CS29003. Submission server ready. All lab students added.
- July 23, 2012
- List of shortlisted external (non-CSE) students: This list is based on the registration status at 3:00pm of 23-July-2012. The only selection criterion used was the current performance (latest CGPA). The list is taken to be frozen at this point. Students with high CGPAs who decide to apply later will not be permitted, since students who are not shortlisted should be given time in order to register for other elective/additional subjects.
- July 20, 2012
- At most ten non-CSE students can be accommodated in the course (theory and lab). Shortlisting, if needed, will be based on the CGPA's of the applicants, and will be carried out in Monday (July 23) afternoon.
## 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: 11-September-2012 (Tuesday), 06:00pm--07:00pm, F-142 [Questions with solutions]
- Class Test 2: 15-November-2012 (Thursday), 06:00pm--07:00pm, F-142 [Questions with solutions]
- Mid-semester test: 25-September-2012 (Tuesday), 02:00--04:00pm, F116, F142, NR221, NR222, V4 [Questions with solutions]
- End-semester test: 20-November-2012 (Tuesday), 02:00--05:00pm, V1, V2, S302 [Questions with solutions]
## Programming Assignments

No Topic Start date Due date More info Warm-up assignment Recursive algorithms July 25, 2012 Not for submission Solution Assignment 1 Recursive algorithms August 01, 2012 August 01, 2012 Solution Assignment 2 Designing efficient algorithms August 08, 2012 August 08, 2012 Solution Assignment 3 Dynamic programming August 22, 2012 August 22, 2012 Solution Assignment 4 Representation of graphs August 29, 2012 September 05, 2012 Solution Assignment 4s Supplement to Assignment 4 September 05, 2012 Not for submission Sample animation Assignment 5 Heaps and priority queues September 12, 2012 September 12, 2012 Solution Assignment 6 Binary search trees September 19, 2012 September 19, 2012 Solution Assignment 7 String matching October 10, 2012 October 10, 2012 Solution Assignment 8 Hash tables October 17, 2012 October 31, 2012 Solution Assignment 9 Graph-theoretic algorithms October 31, 2012 November 14, 2012 Solution: .c, .h ## Submission site | Miscellaneous information

Schedule | Notices | Syllabus | References | Tests | Assignments | Autumn 11