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

Schedule | Notices | Syllabus | References | Tests | Assignments | Autumn 12 | 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-127

Lab:CICTeaching Assistants Aayush Goel

Arnab Dhar

Rahul Katare

Sabyasachi Karati

Suvadeep Hajra

## Notices and Announcements

- July 24, 2013
- The shortlisting of the external (non-CSE) students are done. Other external students will be deregistered by ERP.
- July 20, 2013
- 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 on Tuesday (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-2013, V2, 06:00–07:00pm

Questions with solutions | Complete code- Class Test 2: 14-November-2013, F142, 06:00–07:00pm

Questions with solutions | Complete code- Mid-semester test: 24-September-2013, 02:00–04:00pm

Questions with solutions- End-semester test: 19-November-2013, 02:00–05:00pm

Questions with solutions## Programming Assignments

No Topic Start date Due date More info Warm-up assignment Recursive algorithms July 24, 2013 Not for submission Solution Assignment 1 Divide-and-conquer algorithms July 31, 2013 July 31, 2013 Solution Assignment 2 Greedy algorithms August 07, 2013 August 10, 2013 Solution Assignment 3 Dynamic-programming algorithms August 14, 2013 August 14, 2013 Solution Assignment 4 Working with graphs August 21, 2013 August 28, 2013 Solution Assignment 5 Working with heaps September 04, 2013 September 04, 2013 Solution Assignment 6 Working with binary search trees September 11, 2013 September 18, 2013 Solution Assignment 7 Algorithms on arrays October 09, 2013 October 09, 2013 Solution Lab Test 1 Algorithm design and data structures October 23, 2013 October 23, 2013 Solution Assignment 8 Graph algorithms October 30, 2013 November 13, 2013 Solution ## Submission site | Miscellaneous information

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