ES 242 | Aug-Nov 2022

ES242. Data Structures and Algorithms I.

January - April 2023

About the Course

Data structures give us principled ways to stow away information. It’s important to do this nicely based on what you want to do with the information.

For example, the notes you might be taking in this class is information. If you have no plans of revisiting them later, you can take them as you please, or better yet, not take them at all!

However, you want your notes optimised for giving you quality company during a 2AM revision session on exam day, competing with Maggi for attention, you want your notes to be competently taken: they don’t have to be neat, and it’s enough for them to be useful.

On the other hand, if you are taking notes so that a special someone who will inevitably miss a few classes will almost certainly ask for later, then you would be making notes to impress, and that potentially requires a different approach.

Throughout this course, we will try to make sense of trade-offs.

Topics

sequential data (arrays, dynamic arrays, linked lists and variants) • dequeues, stacks, queues • graph representations • graph traversals (BFS/DFS) and applications (connected components, bipartiteness, topological sort) • searching and sorting • heaps • BSTs • (2,3)-trees

Target Audience

This course is aimed at undergraduates in their first or second year, as a first introduction to data structures and algorithms.

Prerequisites

The course is largely self-contained. Working familiarity with a programming language will be useful for the labs, where solutions are expected to be written out in C.

References

1. Open Data Structures by Pat Morin
2. Lecture notes by John Bullinaria
3. Data Structures Using C & C++ by Aaron M. Tenebaum; Moshe J. Augenstein; Yedidyah Lansam
4. Data Structures and Algorithms by A. Aho, J. Hopcroft, J. Ullman
5. Algorithms by Jeff Erickson

Timings and Venue

TBA

TAs and Office hours

Office Hours

By appointment.

TAs.

TBA

Evaluation policy

• Each of the three exams account for 20% of the grade.

• Each lab will have a task worth 2 points. The total number of points you can earn through quizzes is capped at 20, and accounts for 20% of the grade.

• The first class each week will start with a short objective-type quiz based on the material from the previous week, worth 2 points. The total number of points you can earn through quizzes is capped at 20, and accounts for 20% of the grade.

• The are three assignments that are not graded but are recommended for practice.

Registration

If you are at IIT Gandhinagar and would like to take up this course for credit, please fill up this form to indicate your interest.

If you are not from IITGN and are interested in taking up the course, then please send me an email with the subject line 2023 DSA-1 Participation.

Note: contents being actively updated at the time of this writing.

Lectures

Labs

Assignments

Quizzes

Exams