CS21003 Algorithms – ICS29003 Algorithms Laboratory |
Spring 2018 |

Schedule | Notices | Syllabus | References | Tests | Assignments | Previous Semesters: Theory, Lab

## Schedule

Instructors Abhijit Das Aritra Hazra (co-instructor in lab) Timing Theory:Slot D4 [MON(12:00–12:55), TUE(10:00–11.55), THU(08:00–08:55)]

Lab:TUE (02:00–05:00)Venue Theory:Room No NC233

Lab:PC LAB II and V, CICTeaching Assistants Ashish Sharma

Atrayee Majumder

Harshit

Papia Mahato

Pritam Bhattacharya

Sandeep Kumar Pani

Snigdha Das

Sohan Shantanu De Sarkar

Souvik Sur

## Notices and Announcements

January 05, 2018, 2:15pm- All pending cases are now approved. Because of deadly slow and faulty responses from the ERP server, this took me more than an hour. I consider these decisions final.
I will no longer update the approval page for the theory or the lab.

January 04, 2018, 9:00pm- I have taken decisions for most of the applicants. Applicants only from a narrow band of CGPA's are still kept in the "Pending" status. The class and lab are now full to the capacity. I will take decisions on these pending cases by tomorrow (05-Jan-2018) 12:00 noon. There is no need to send me e-mails, because irrespective of my willingness to accommodate as many students as possible, I have capacity constraints. I cannot exceed the limits without diluting the courses. I will no longer reply to your individual e-mails, but take my own decisions by the time mentioned above.
For the moment, let me make an appeal to the approved applicants.

If for some reasons, you cancel subject registration after approval, please do it by tomorrow 12 noon.This will help me approve some other applicants.

January 03, 2018

- Since the student population is not yet finalized, there will be no class on 04-Jan-2018. Classes will start from 08-Jan-2018.

December 28, 2017

- Interested students are requested to apply via the ERP portal. Please keep in mind the following requirements.

- The timings for both theory and laboratory as mentioned above are to be treated as frozen and final. These timings are chosen so as to reduce clashes with other courses. However, it is impossible to find any slot that is free for everybody. So any further change may solve a few cases but will introduce new cases of clash.
- An applicant must not have any clash with these timings. If so, the students are supposed to make attempts to shift the other courses/labs clashing with these. Many of the lab assignments are to be submitted during the lab hours only. The submission server does not support extended deadlines on a case-by-case basis.
- The maximum capacity of the theory is 100 and of the lab is 125. If the applicant counts are much more than these, shortlisting will be made based only on CGPA (and on no other criteria). In order that the applicants who are not shortlisted can register for other courses, and keeping in view that the last date for course registration is 05-Jan-2018, I consider only those ERP requests that are recorded by 04-Jan-2018 08:00pm. I will do the shortlisting (if needed) immediately after that.
All approvals by me in ERP will wait until that time.- Neither the course nor the lab has any prerequisites (under the assumption that all applicants have cleared PDS theory and lab). Since the theory course and the lab are complementary to one another, it does not make enough sense to register for only one (unless somebody has done the other earlier or plans to do it later).
## Tentative Coverage

Complexity of AlgorithmsAsymptotic notations and their significance, complexity analysis of algorithms, worst case and average case. 2 hours Algorithm Design 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: 08-Feb-2018 (Thursday), 7:00–8:00pm, CSE 107/119/120 [Questions with solutions]
- Class Test 2: 13-Apr-2018 (Friday), 7:00–8:00pm, CSE 107/108/119/120 [Questions with solutions]
- Mid-Semester Test: 22-Feb-2018 (Thursday), 2:00–4:00pm, Vikramshila and Nalanda [Questions with solutions]
- End-Semester Test: 24-Apr-2018 (Tuesday), 2:00–5:00pm, Vikramshila and Nalanda [Questions with solutions]
## Programming Assignments

No Topic Start date Due date More info Assignment 0 Brush up your PDS skills 09-Jan-2018 09-Jan-2018 Solution Assignment 1 Polynomial vs logarithmic running times 16-Jan-2018 16-Jan-2018 Blackbox: gcc, g++ | Solution Assignment 2 Divide-and-conquer algorithms 23-Jan-2018 23-Jan-2018 Blackbox: gcc, g++ | Solution Assignment 3 Greedy and dynamic-programming algorithms 30-Jan-2018 30-Jan-2018 Solution Assignment 4 Binary trees 06-Feb-2018 06-Feb-2018 Solution Assignment 5 Heaps and priority queues 13-Feb-2018 13-Feb-2018 Solution Assignment 6 Binary search trees 06-Mar-2018 06-Mar-2018 Solution Assignment 7 Hash tables 13-Mar-2018 13-Mar-2018 Solution Assignment 8 Graph traversal 20-Mar-2018 20-Mar-2018 A bigger example | Solution Assignment 9 Shortest paths in graphs 03-Apr-2018 03-Apr-2018 A bigger example | Solution Assignment 10 Wind it up 10-Apr-2018 10-Apr-2018 Blackbox: gcc, g++ | Solution Lab Test Algorithm design techniques and data structures 27-Mar-2018 27-Mar-2018 Samples:Even0 | Even2 | Odd1 | Odd3

Solution: Even | Odd

EVALUATION## Submission site | TA Allocation | Miscellaneous information

Schedule | Notices | Syllabus | References | Tests | Assignments | Previous Semesters: Theory, Lab