ES 242 | Aug-Nov 2022

ES242. Data Structures and Algorithms I.

January - April 2023

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

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

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.

  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

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.

Office Hours

By appointment.

TAs.
  • Yash More
  • Gaurav Viramgami
  • Reuben Devanesan
  • Xhitij

  • 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.

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.

Date Lecture Slides Notes Video
03 Jan, 2023 1. Introduction to Data Structures [W1]
Data Structures - philosophy and examples • Representing games
05 Jan, 2023 2. Stable Marriages [W1]
The Stable Marriage Problem • Gale-Shapley Algorithm
10 Jan, 2023 3. Representing Sequential Data [W2]
Arrays • Lists • Implementing the Gale-Shapley Algorithm
12 Jan, 2023 4. Representing Graphs [W2]
Adjacency Lists • Adjacency Matrices • Edge Lists
17 Jan, 2023 5. Dequeues [W3]
The Gilbreath Shuffle • Properties of the shuffle
19 Jan, 2023 6. Dequeues [W3]
Queues and Stacks as special cases of Dequeues
24 Jan, 2023 7. Euler Tours [W4]
Euler Tour Demonstration • The Bridges of Königsberg
31 Jan, 2023 8. Euler Tours [W5]
Computing Euler Tours • Hierholzer's algorithm
02 Feb, 2023 9. Recap Class [W5]
Review of topics covered so far.
09 Feb, 2023 10. Navigating Graphs (BFS) [W6]
Breadth-First Search • Correctness • Analysis of Running Time
14 Feb, 2023 11. BFS Applications [W7]
Shortest Paths • Pseudopolynomial algorithm for weighted graphs
16 Feb, 2023 12. Exam [W7]
Syllabus: representations, arrays, lists, stacks, queues, dequeues, Euler tours, stable marriages
21 Feb, 2023 13. Navigating Graphs (DFS) - I [W8]
Depth-First Search • Implementation with Stacks
23 Feb, 2023 14. Navigating Graphs (DFS) - II [W8]
Depth-First Search • DFS-based classification of vertices • DFS-based classificaton of edges • Cycles and backedges
03 Mar, 2023 15. BFS and DFS Applications [W9]
Testing Bipartiteness • Topological Sort
16 Mar, 2023 16. Sorting Algorithms [W10]
Examples of Sorting Algorithms • Properties of sorting algorithms
21 Mar, 2023 17. Asymptotics [W10]
Comparing Algorithms by Performance • Big-O Notation
28 Mar, 2023 18. Heaps [W12]
Supporting only Insert and FindMin • The challenge of ExtractMin • The Heap Property • Insert • FindMin • ExtractMin
06 Apr, 2023 19. Heaps [W13]
Representing Heaps with Arrays • Analysis: Heapify in Linear Time
11 Apr, 2023 20. Trees [W14]
Rooted Trees • Inorder, Preorder, and Postorder Traversals
13 Apr, 2023 21. Search [W14]
Binary Search • Ternary Search
18 Apr, 2023 22. Balanced Binary Search Trees [W15]
Introduction to BSTs • (2,3)-Trees
20 Apr, 2023 23. Balanced Binary Search Trees [W15]
Insertion in (2,3)-Trees • Analysis of Height
25 Apr, 2023 24. Balanced Binary Search Trees [W16]
Deletion in (2,3)-Trees
27 Apr, 2023 25. Recap [W16]
Review of topics covered so far.
No matching items
Issued Assessment Problems Solutions Due
06 Jan, 2023 W01. Introduction to C

CountDown • Life Goal • Game of Trust • Rock Papers Scissors • Finding the Coefficient • Validating a Self-Working Card Trick [Optional] • Stable Marriage [Optional]
13 Jan, 2023 W02. Lists and Arrays

Sorting a List • Sorting a List: Challenge the Solution • Maintain a Network • Stable Matchings
20 Jan, 2023 W03. The Cardstack

Linked Lists • Parentheses • Challenge the Parentheses Solution • Print Alternate Cards
27 Jan, 2023 W04. Graph Representations and Euler Tours

Adjacency Matrix • Adjacency List • Edge List • Sanity Check • Which Way is the Highway? [Optional] • Edge Orientation Puzzle [Optional]
03 Feb, 2023 W05. Recap Lab

Reviewed unsolved and practice problems.
10 Feb, 2023 W06. Navigating Graphs (BFS)

BFS Implementation • Unique Servers
17 Feb, 2023 W07. No Lab

Classes Suspended
24 Feb, 2023 W08. Navigating Graphs (DFS)

DFS Implementation • Is it a DAG?
28 Feb, 2023 W09. BFS Implementation

BFS Implementation Recap
02 Mar, 2023 W09. DFS Implementation

DFS Implementation Recap
17 Mar, 2023 W10. BFS/DFS Practice Problems

Make It Happen • Switching Lines • Prolonged Vacation
07 Apr, 2023 W13. Heaps

Heap operations (ExtractMax, Delete, Insert) • Heapify • Heapsort
No matching items
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.

Issued Assessment Problems Solutions Due
05 Jan, 2023 Quiz 01
12 Jan, 2023 Quiz 02
19 Jan, 2023 Quiz 03
24 Jan, 2023 Quiz 04
No matching items
Issued Assessment Problems Solutions Due
16 Feb, 2023 Exam 1

Syllabus: representations, arrays, lists, stacks, queues, dequeues, Euler tours, stable marriages
Exam 2 (Lab)

Syllabus: arrays, lists, stacks, queues, graphs, BFS/DFS
Exam 3

Syllabus: BFS/DFS, heaps, sorting algorithms, tree traversals, 2,3-trees
No matching items

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.