CS 218 – DESIGN AND ANALYSIS OF ALGORITHMS

Course Name

CS 218: Design and Analysis of Algorithms (Minor)

Year for which the review is written

2018 – 2019 Autumn

Professor who took the course

Prof. Sundar Vishwanathan

Motivation behind the course

As discussed in my review of CS 213: Data Structures and Algorithms, this course is a step up for those interested in learning how people came up with the algorithms in the first place. The motivation for this course is learning to come up with algorithms for any problem you may encounter and being able to optimize the running time by analysing the algorithm you have come up with.

Also, in the later-half of the course we see the data structures we have studied in CS 213 come up as natural necessities to the algorithms we finally design which is quite beautiful.

The below-mentioned topics are important as building blocks for studying further algorithm spaces as it helps in understanding them better. Also, the algorithms discussed are applicable in various other domains. We thus eventually realise the need to appreciate Algorithm design as a field in its own right.

Course Content

1.Revision of the ideas covered in Data Structures and Algorithms 2.Augmenting the Binary Search Tree to obtain Balanced Binary Search Tree 3.Basic Principles of Algorithm Design and Emphasis on recursive algorithms 4.Designing and Analysing Algorithms of standard problems often encountered 5.Introduction to Dynamic Programming 6.Application of Dynamic Programming and Recursion to solve problems 7.Introduction to Greedy Algorithms 8.Introduction to NP, NP – Hard and NP – complete classes of problems 9.What next?

Pre-requisite

CS 213 – Data Structures and Algorithms

Feedback on lectures

The professor didn’t demand attendance but emphasized problem solving. The lectures were interesting and the professor would present a problem at the beginning of a class and would expect us to completely solve the problem so as to appreciate the principles. Classes could be a bit boring at times since you are usually required to think about the problem independently. Attending classes with enthusiasm and concentration helped quite a lot in understanding difficult concepts which the professor explained as if it were quite natural to approach the problem in the way he approached it.

Feedback on tutorials, assignments and exams

There were 2 algorithm design assignments throughout the course. Solving the assignments took a lot of time as they were quite difficult compared to examples discussed in the class. Problems in the exam required a thorough understanding of the concepts. The quizzes involved one problem which had been discussed in the class and two new problems. They were of moderate difficulty. The end semester exam involved 4 new problems and were towards the difficult side.

Evaluation Scheme was as follows:

Homework Assignments: 10%

Quizzes: Best 2 out of 3: 40 % (20 % for each quiz)

End semester exam: 50%

Grading

Quite decent as can be seen from the following:

AA 4

AB 15

AP 1

BB 20

BC 13

CC 10

CD 4

DD 3

FR 5

II 1

Study Material and References

The Professor uploaded lectures on the website he had hosted which were more than enough if lectures were regularly attended.

A reference book: Algorithm Design by Kleinberg and Tardos is easily available online.

Reviewed By: Himanshu Pradeep Aswani (himanshuaswani123@gmail.com)