# 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.