Instructor

Abhiram Ranade

Semester

Autumn ‘20

Course Difficulty

This course is moderately difficult, and requires consistent effort and motivation. This should be expected from a course doing a deep dive into algorithms.

Time Commitment Required

6-8 hours per week

Grading Policy and Statistics

AA 12
AB 16
BB 11
BC 14
CC 12
CD 13
DD 2
Total 80

Pre-requisites

CS101 level knowledge is a must. A little bit of Data Structures and Algorithms knowledge would be beneficial, but is not a prerequisite, as the course doesn’t assume much knowledge in this regard.

Evaluation Scheme

20 marks : Best 4 of 5 assignments, 5 per selected assignment
5 marks : Quiz
25 marks : Midsem
50 marks : Endsem

Topics Covered in the Course

Models of computation, algorithm analysis, time and space complexity, average and worst case analysis, lower bounds. Algorithm design techniques: divide and conquer, greedy, dynamic programming, amortization, randomization. Problem classes P, NP, PSPACE; reducibility, NP-hard and NP-complete problems. Approximation algorithms for some NP-hard problems.

Tutorials/Assignments/Projects

Assignments are a bit time-consuming, but doable and easy to score in. It’s generally a list of exercises from the reference textbook, so though solutions are easy to find on the web, it is highly recommended to try on your own and give your best first, to help develop an algorithmic acumen.

Feedback on Exams

Quizzes were simple, and good conceptual understanding helps score easily in the quizzes.

Midsem and Endsem exams were moderately difficult, and a deep understanding of topics, and practice with various kind of questions is beneficial to come up with efficient algorithms on the spot.

Motivation for taking this course

You should take this course if you want to explore how to come up with efficient approaches to tackle seemingly complex problems, how some of the best algorithmic techniques work, famous algorithms used in production, and a decent depth of exposure into the various kinds of algorithms. The biggest takeaway from this course is the development of an algorithmic mindset.

How strongly would I recommend this course?

If the course motivation mentioned above resonates with you, this course is highly recommended. The professor is really good at teaching, and he also holds regular discussions, where he is extremely helpful and patient.
Though, keep in mind that courses like this have a lot of awesome alternative resources online to cover the same content if you only care about learning the topics, and not about also formally doing the course.

When to take this course?

5 semester.
This course should ideally be taken after CS213 - Data Structures and Algorithms.

References Used

Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf)

CS 218 Review By: Shubham Lohiya