CS 213 – DATA STRUCTURES AND ALGORITHMS

Course Name

CS 213: Data Structures and Algorithms (Minor)

Year for which the review is written

2017 – 2018 Spring

Professor who took the course

Prof. Abhiram Ranade

Motivation behind the course

The motivation for this course is learning to apply algorithms suitably to access, store and later update the data which requires quite a lot of visualisation and thinking of the various data structures thereby improving our logical thinking as well.

The course also aims to familiarise the student with fundamental data structures like arrays, binary search trees, heap trees, vectors, maps, 2-3 Trees (extension of binary trees), Tries, hash tables, undirected and directed graphs, doubly linked lists and stacks.

Various Algorithms that were introduced are merging and sorting arrays, heapsort and quicksort as advanced sorting techniques, Dijkstra’s and Bellman Ford’s shortest path algorithms, fast multipole method and insertion, deletion and accessing advanced data structures. Also, a brief application of Line Scan technique was discussed.

The above-mentioned topics are important as a building block for studying further organisational structures as it helps in understanding them more deeply. Also, the algorithms discussed are applicable in various other courses such as computer networks and the basic structure of an algorithm can always be built upon in more advanced courses such as machine learning.

Course Content

Introduction to Correctness and Time Complexity of algorithms Binary Search and Merge Sort Algorithms applied to arrays Storing variable length entities on the Heap Pointers and Abstract data types The string class, template classes vector and map Binary Rooted Trees, Min/Max Heap Trees Binary Search Trees and Priority Trees/Queues 2-3 Trees and Tries Structural Recursion by developing an analogy to LaTex Hash tables and Fast Multipole Method Graphs and algorithms on them such as Dijkstra’s and Bellman Ford Satisfiability problems, Breadth First and Depth First Search Introduction to Doubly Linked Lists, Stacks and Line Scan Technique

Pre-requisite

CS101- Computer Programming and Utilization

Feedback on lectures

The professor demanded 80% attendance from the students. The lectures were interesting and the professor would present a problem at the beginning of a class and would develop ideas to tackle it. The professor would not give any breaks and so the student is expected to maintain his concentration for the full class. Attending classes with full concentration helped quite a lot in understanding deep ideas which the professor explained very nicely and with ease.

Feedback on tutorials, assignments and exams

There were 3 C++ programming assignments throughout the course. Problem sets were given for practice occasionally. Solving the assignments cleared any doubts quite effectively. Problems in the exam required a thorough understanding of the concepts as well as speed. The exams were not too scoring for the students with average hovering around 30 to 40 percent.

Evaluation Scheme was as follows:

Assignments: 4%

Quiz: Best 2 out of 3 : 46 %(23 % for each quiz)

End semester exam: 50%

Grading

Moderately Tough as can be seen from the following:

AA 5

AB 11

BB 20

BC 22

CC 26

CD 27

DD 28

FR 33

II 3

W 7

Study Material and References

The Professor uploaded the slides taught in class on Moodle. He also referred to the following:

An Introduction to Programming through C++ (by the professor himself) was followed for the first half of the semester including the problems in the quizzes.

For the later half of the semester mainly Algorithms By S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani was followed.

Advanced courses that can be taken after this course

CS218 – Design and Analysis of Algorithms

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