| CS21003 Algorithms I CS29003 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
Instructors 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 KushwahaNotices 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 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
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