ES 242 | Aug-Nov 2022

ES242. Data Structures and Algorithms I.

August — November 2022

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

Lectures on Tuesdays and Wednesdays • 10AM — 11AM • 1/101 Labs on Wednesdays • 4PM — 6PM • 7/108 and 7/109

TAs and Office hours

Office Hours

By appointment.

Theory:

1. Harshil Mittal (mittal_harshil@iitgn.ac.in)
2. Saraswati Nanoti (nanoti_saraswati@iitgn.ac.in)

Labs:

1. Ksheer Agrawal (ksheer.agrawal@iitgn.ac.in)
2. Progyan Das (progyan.das@iitgn.ac.in)
3. Nipun Mahajan (mahajan.n@iitgn.ac.in)
4. Yash More (yash.mh@iitgn.ac.in)

ADH Mentors:

1. Xhitij Choudhary (xhitij.cm@iitgn.ac.in)
2. Bhavesh Jain (bhavesh.jain@iitgn.ac.in)

Evaluation policy

• Weekly Assignments on Google Classroom. 2 * [top 10] = 20

• Lab Assignments on repl.it. 1 * [top 10] = 10

• Class participation via Mentimeter. 0.5 points per class capped at 10

• Midsem Exam. 10 (lab) + 10 (theory) = 20

• Final Exam. 10 (lab) + 15 (theory) = 25

• Four quizzes (two theory, two lab & top 3 outcomes counted). 3 * 5 = 15

Registration

For IITGN students, (pre-)register through IMS as usual.

If you are not from IITGN and are interested in taking up the course, then please send me an email.

Registration for the course is now closed. The next edition of this course will be offered in the Jan - Apr 2023 semester.

Note: contents being actively updated at the time of this writing. Enroled students will find all materials in the Google classroom for this course. Items marked are coming soon!

Lectures

Labs

Mentimeter

Heads Up

These questions are integrated into the lectures and may not make sense standalone. Please check the slides and/or notes for additional context.

Assignments

Quizzes

Exams