Analysis and Design of Algorithms

Course code	COL351
Instructor	Ashish Chiplunkar (ashishc@...)
Teaching Assistants	Aman Shreshtha, Dhananjay Kumar Jha, Harsh Wardhan, Mehul Bose
Classes	LH316; Monday and Wednesday 11:00 - 12:00, Thursday 12:00 - 13:00 (Slot H)
Tutorial	LH527; Wednesday 14:00 - 15:00, Thursday 18:30 - 19:30

Eligibility and Prerequisites

This offering of COL351 is intended for students who want to take it as an OC course. Students taking it as a DC course will be de-registered.

COL106 - Data Structures is a hard prerequisite. A passing grade in COL106 is necessary for registering into this course. Moreover, it is also necessary that you recall everything you studied in COL106: more importantly,

Induction / recursion, asymptotic notation, recurrence relations
Data structures: linked lists, stacks, queues, heaps, (balanced) binary (search) trees
Algorithms: binary search, sorting
Graph concepts: undirected and directed graphs, trees, forests, cycles, directed acyclic graphs, connectivity and strong connectivity, adjacency matrix and adjacency list representations
Graph algorithms: breadth-first and depth-first traversals and their applications

Content

If you can solve small problems, you can also solve larger ones (Divide and conquer)
Practice makes an algorithm inefficient (Dynamic programming)
Be greedy and justify your greed (Greedy algorithms)
If you haven't achieved your goal, take one step towards it (Augmentation)
When none of the above works for you, put the blame on others (NP-completeness)

Textbooks

"Algorithm Design" by Jon Kleinberg and Éva Tardos
"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Known Overlapping Courses

COL702, ELL781, MTL342. Students who have done or are currently doing any of these courses will be disallowed from taking COL351 for a grade (but will be allowed to attend). If you think you have done or are currently doing any other course with significantly overlapping content, please contact the instructor.

Useful Platforms

Microsoft Teams for announcements, discussion forum, lecture material
Gradescope for exam feedback

Grading (tentative)

Quizzes	60%*
Major exam	40%

* 2 quizzes will be conducted in the minor exam slots and 2 more quizzes will be scheduled separately. Write any 3 of the 4 quizzes. If you write all 4 quizzes, marks of the first three quizzes will be counted. Beyond this, no compensation will be provided for missed quizzes for any reason whatsoever (even medical).

Passing criterion: 30%. No audits.

Attendance Policy

Grade will be completely determined by the performance in the quizzes and the major exam. Mathematically, grade and attendance will be conditionally independent given marks. (However, rest assured that unconditionally, grade and attendance will be heavily correlated!) Marking attendance in lectures and tutorials is mandatory nevertheless. Marking attendance without attending will be treated as academic dishonesty.