| CS21003 Algorithms – I CS29003 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 Algorithms Asymptotic notations and their significance, complexity analysis of algorithms, worst case and average case. 2 hours Algorithm Design 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: 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
EVALUATIONSubmission site | TA Allocation | Miscellaneous information
Schedule | Notices | Syllabus | References | Tests | Assignments | Previous Semesters: Theory, Lab