CS21003 Algorithms – I
 CS29003 Algorithms Laboratory
Spring 2019

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

Schedule

Instuctor     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, CIC
Teaching 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

[1]     Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press/McGraw-Hill, 2001.
[2]     Jeff Erickson, Algorithms, Prepublication Draft, 2018.
[3]     Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh V. Vazirani, Algorithms, Tata McGraw-Hill, 2008.
[4]     Jon Kleinberg and √Čva Tardos, Algorithm Design, Pearson, 2005.
[5]     Michael T Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Second Edition, Wiley, 2006.
[6]     Udi Manber, Algorithms – A Creative Approach, Addison-Wesley, Reading, MA, 1989.
[7]     Harry R. Lewis and Larry Denenberg, Data Structures and Their Algorithms, Harper Collins, 1997.
[8]     Robert Sedgewick and Kevin Wayne, Algorithms, fourth edition, Addison Wesley, 2011.
[9]     Muhammad H. Alsuwaiyel, Algorithms: Design Techniques and Analysis, World Scientific, 1999.
[10]     Gilles Brassard and Paul Bratley, Algorithmics: Theory and Practice, Prentice-Hall, 1995.
[11]     Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and Analysis, third edition, Addison-Wesley, 2000.
[12]     Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.

Tests

Programming Assignments

No Topic Start date Due date More info
A0 Brush up your PDS skills 08-Jan-201908-Jan-2019 Solution
A1 Polynomial vs logarithmic running times 15-Jan-201915-Jan-2019 Blackbox: gcc, g++
Solution
A2 Divide-and-conquer algorithms 22-Jan-201922-Jan-2019 Blackbox: gcc, g++
Solution
A3 Greedy algorithms 29-Jan-201929-Jan-2019 Solution
A4 Dynamic-programming algorithms 05-Feb-201905-Feb-2019 Solution
A5 Stacks, queues and trees 12-Feb-201912-Feb-2019 Blackbox: gcc, g++ | Header file
Solution
A6 Heaps and priority queues 05-Mar-201905-Mar-2019 Solution
A7 Binary search trees (rotations included) 12-Mar-201912-Mar-2019 Black box: gcc, g++ | Header file
Solution
A8 Union-find disjoint-sets data structure 19-Mar-201919-Mar-2019 Solution
LT Syllabus: Up to (including) A7 26-Mar-201926-Mar-2019 Sample inputs: Even | Odd
Solution
Evaluation: Even (by AH) | Odd (by AD)
Samples used for evaluation
A9 Graph traversal 02-Apr-201902-Apr-2019 Solution
AA Minimum spanning trees 09-Apr-201909-Apr-2019 Solution
AB Graph applications 16-Apr-201916-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