| CS21003 Algorithms – I CS29003 Algorithms Laboratory |
Spring 2019 |
Schedule | Notices | Syllabus | References | Tests | Lab assignments | Previous Semesters: Theory, Lab
Schedule
Instructors Abhijit Das and Aritra Hazra Timing Theory: Slot D4 [MON(12:00–12:55), TUE(10:00–11.55), THU(08:00–08:55)]
Lab: Slot L [TUE (02:00–05:00)]Venue Theory: Room No NC233 and NC331 (Sectioning)
Lab: PC LAB II and V, CICTeaching Assistants Theory Bhanupriya Pegu, Gagan Sharma Lab Akshay Patil, Anirban Chakraborty, Ashwin Sudhakar Bhoyar, Bijoy Das, Prajnamaya Dass, Pritam Pallab, Ronit Nath, Sayandeep Sanyal, Souvik Sur Notices and Announcements
- February 04, 2019
- Schedule for Class Test I is announced.
- January 05, 2019
- Sectioning done as per institute policy. Look at the links below.
Student-wise allocation | Room-wise allocation
- January 03, 2019, 08:25pm
- CGPA-based screening is made on all the requests available until now. WE WILL PROCESS NO NEW REQUESTS.
The theory course will run in two classrooms with half the registered population in each classroom. One classroom is NC233. The other will be announced after it is arranged centrally. The lab will run in two side-by-side CIC labs (PC LAB II and V). The split of the students will later be announced in this web page.
- January 02, 2019
- All initerested students are requested to apply before tomorrow 8:00pm. We will not entertain applications that are recorded after that (even in the case that ERP extends its deadline for course registration). We do not respond to individual e-mails about the application and the application-approval processes.
- December 15, 2018
- 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 04-Jan-2019, I consider only those ERP requests that are recorded by 03-Jan-2019 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 (10%): 12-February-2019 (Tuesday), 07:00pm–08:00pm, F-116 (Bhatnagar Auditorium, Section 1) and F-142 (Raman Auditorium, Section 2)
Questions with solutions- Class Test 2 (10%): 09-April-2019 (Tuesday), 06:00pm–07:00pm, F-116 (Bhatnagar Auditorium, Section 1) and F-142 (Raman Auditorium, Section 2)
Questions with solutions- Mid-Semester Test (30%): 21-February-2019 (Thursday), 2:00pm–04:00pm, Nalanda (Centrally scheduled)
Questions with solutions
Common mistakes- End-Semester Test (50%): 25-April-2019 (Thursday), 2:00pm–05:00pm, Nalanda (Centrally scheduled)
Questions with solutions
Common mistakesProgramming Assignments
No Topic Start date Due date More info A0 Brush up your PDS skills 08-Jan-2019 08-Jan-2019 Solution A1 Polynomial vs logarithmic running times 15-Jan-2019 15-Jan-2019 Blackbox: gcc, g++
SolutionA2 Divide-and-conquer algorithms 22-Jan-2019 22-Jan-2019 Blackbox: gcc, g++
SolutionA3 Greedy algorithms 29-Jan-2019 29-Jan-2019 Solution A4 Dynamic-programming algorithms 05-Feb-2019 05-Feb-2019 Solution A5 Stacks, queues and trees 12-Feb-2019 12-Feb-2019 Blackbox: gcc, g++ | Header file
SolutionA6 Heaps and priority queues 05-Mar-2019 05-Mar-2019 Solution A7 Binary search trees (rotations included) 12-Mar-2019 12-Mar-2019 Black box: gcc, g++ | Header file
SolutionA8 Union-find disjoint-sets data structure 19-Mar-2019 19-Mar-2019 Solution LT Syllabus: Up to (including) A7 26-Mar-2019 26-Mar-2019 Sample inputs: Even | Odd
Solution
Evaluation: Even (by AH) | Odd (by AD)
Samples used for evaluationA9 Graph traversal 02-Apr-2019 02-Apr-2019 Solution AA Minimum spanning trees 09-Apr-2019 09-Apr-2019 Solution AB Graph applications 16-Apr-2019 16-Apr-2019 Solution Evaluation Guidelines Black boxes for other platforms: Ubuntu 18 | Mac Submission site | TA Allocation | Miscellaneous information
Schedule | Notices | Syllabus | References | Tests | Lab assignments | Previous Semesters: Theory, Lab