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: and what that means is to work backwards from what you want to do with your information, so that your storage style is optimized for the specific way in which you need to work with your data.

For example, the notes you might be taking in this class is a kind of 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 understand such trade-offs in several scenarios.

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: Tuesdays and Thursdays, 9PM - 10:30PM

Lab: Fridays, 9PM - 10:30PM

Venue: 1/102 (all sessions)

Note: Please bring your laptops to all classes.

TAs and Office hours

Office Hours

By appointment.

TAs.

• Yash More
• Gaurav Viramgami
• Reuben Devanesan
• Xhitij

Evaluation policy

• Each of the three exams account for 20% of the grade. The first exam will be pen-and-paper exams, the second exam will be a lab exam, and the third exam will be a viva.

• Labs for Weeks 1 — 4 count for two points each on an all-or-none basis. The seven problems in labs for Weeks 6,8 and 10 have seven problems worth 2 points each. Labs for Weeks 12 and 13 will count for two points each on an all-or-none basis. The total number of points you can earn from quizzes and assignments combined is capped at 20.

• Quizzes 2, 3, and 4 count for 2 points each. Assignments 1, 2, and 3 count for 7 points each. The total number of points you can earn from quizzes and assignments combined is capped at 20.

• There is no mandatory attendance requirement for this course, although it is strongly recommended that you attend classes, labs, and the ADH sessions.

Registration & Logistics

If you are at IIT Gandhinagar and would like to take up this course for credit, please fill up this form by midnight on the 30th of December to indicate your interest.

All weekly quizzes, labs, and exams will be managed via Gradescope. You can sign up using the entry code G2ZG3X.

Course announcements will be posted on this page. They will also be mirrored to this broadcast-only Whatsapp group.

You are welcome to post any comments/questions/feedback related to the course in the discussions tab of this page.

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

Lectures

Labs

Quizzes

Note

Quizzes will be administered online and in the classroom via Gradescope. If a quiz is submitted for evaluation in absence, then it amounts to a violation of the honor code and will result in a disqualification from the course.

Update: The quizzes in the course have been discontinued, and will be replaced with assignments. There will be 12 assignments worth 2 points each that will be made available in due course.

Exams

Announcements

02/17. Solutions to Exam 1 are now available.

02/03. Lecture slides and notes up to date for the lectures so far.

01/25. Solutions to Quiz 04 are now available.

01/20. Solutions to Quiz 03 are now available.

01/13. Solutions to Quiz 02 are now available.

01/11. Materials for the first two weeks (i.e, notes and slides the first four lectures) are now available.

01/10. Solutions to Quiz 01 are now available.

01/01. The timings are now fixed. The lectures will be held on Tuesdays and Thursdays, 9PM - 10:30PM while the lab will be during Fridays, 9PM - 10:30PM. The venue for all sessions is AB 1/102. Please bring your laptops to all sessions.

29/12. The course is open for enrolments and will be available from IMS soon. The timings are TBD. Please fill up this form to indicate your interest in joining the course.

Discussions