CS29003 Algorithms Laboratory - Spring 2021

Instructor: Somindu Chaya Ramanna and Palash Dey

Teaching Assistants: Nitesh Meena, Jayanta Sharma, Ashwini Rawat, Lakkam Sai Krishna Reddy, Anju Sujith

Course overview:
 The laboratory component will emphasize two areas: Implementation of algorithms covered in class: This will involve running the algorithms under varying input sets and measuring running times, use of different data structures for the same algorithm (wherever applicable) to see its effect on time and space, comparison of different algorithms for the same problem etc. Design of Algorithms: This will involve design and implementation of algorithms for problems not covered in class but related to topics covered in class. The exact set of algorithms to design and implement is to be decided by the instructor. In addition, there will be at least one significantly large design project involving some real world application. An efficient design of the project should require the use of multiple data structures and a combination of different algorithms/techniques.

Classes: Tuesday (14:00–17:00) [Slot L]. TA Allocation for Evaluation, TA Allocation for Queastion and Answering

Grading: 2 Class Tests: 60%; Weekly Assignments: 40%

Assignments:
January 05 SCR A0 PDS Brush up (not graded) --
January 12 PD A1 Running time of algorithms Sample code
Test case and evaluation guidline
January 19 SCR A2 Recursive formulation of algorithms Evaluation Guidlines
January 26 -- -- Institute holiday Republic Day
February 2 PD A3 Divide-and-conquer algorithms Evaluation guidline
Solution hint: Skyline problem
February 9 SCR A4 Greedy algorithms --
February 16 -- -- Institute holiday Holi
February 23 -- - Class Suspension in Institute Convocation
March 2 -- -- Class Suspension in Institute Spring Break
March 7 (SUNDAY) PD C1 First class test Evaluation guidline
Solution hint: Minimum swap bracket balancing
March 9 SCR A5 Dynamic-programming algorithms --
March 16 PD A6 Binary trees and binary search trees Evaluation guidline
Solution hint: Splay tree
March 23 SCR A7 Heaps and priority queues --
March 30 PD A8 Application of Graph traversals Evaluation guidline
Solution hint: here
April 6 SCR A9 Shortest path --
April 13 SCR C2 Second class test --
References:
  1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms.
  2. Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005.
  3. Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.

Policy on Plagiarism

Academic integrity is expected of all the students. Ideally, you should work on the assignment/exam consulting only the material we share with you. You are required to properly mention/cite anything else you look at. Any student submitting plagiarised code will be penalised heavily. Repeated violators of our policy will be deregistered from the course. Read this to know what is plagiarism.