CS218 - Design and Analysis of Algorithms
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
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.
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.
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?
This course should ideally be taken after CS213 - Data Structures and Algorithms.
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