Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

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.

TBA

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

  • Each non-practice lab will have a task worth 2 points. The total number of points you can earn through labs is capped at 20, and accounts for 20% of the grade. There are (tentatively) 11 labs that have graded exercises.

  • A random subset of classes will start with a short objective-type quiz based on the material from recent lectures, worth 2 points. The total number of points you can earn through quizzes is capped at 20, and accounts for 20% of the grade. There are (tentatively) 16 quizzes planned for this course.

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

  • Attendance will be tracked for classes and labs. However, there are no points for attending.

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
  • Assignments
  • Quizzes
  • Exams
  • Announcements
  • Discussions
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 - I [W7]

Shortest Paths • Pseudopolynomial algorithm for weighted graphs

16 Feb, 2023 12. BFS Applications - II [W7]

Testing Bipartiteness

21 Feb, 2023 13. Navigating Graphs (DFS) - I [W8]

Depth-First Search • Pre-Post Intervals

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

28 Feb, 2023 15. DFS Applications - I [W9]

Topological Sort (Algorithm)

02 Mar, 2023 16. DFS Applications - II [W9]

Postorder • Preorder • Topological Sort (Analysis)

14 Mar, 2023 17. Sorting Algorithms [W10]

Selection Sort • Properties of sorting algorithms

16 Mar, 2023 18. Asymptotics [W10]

Comparing Algorithms by Performance • Big-O Notation

21 Mar, 2023 19. Recap Week [W11]

Review of topics covered so far.

28 Mar, 2023 20. Heaps [W12]

Supporting only Insert and FindMin • The challenge of ExtractMin • The Heap Property • Insert • FindMin • ExtractMin

06 Apr, 2023 21. Heaps [W13]

Representing Heaps with Arrays • Analysis: Heapify in Linear Time

11 Apr, 2023 22. Trees [W14]

Rooted Trees • Inorder, Preorder, and Postorder Traversals

13 Apr, 2023 23. Search [W14]

Binary Search • Ternary Search

18 Apr, 2023 24. Balanced Binary Search Trees [W15]

Introduction to BSTs • (2,3)-Trees

20 Apr, 2023 25. Balanced Binary Search Trees [W15]

Insertion in (2,3)-Trees • Analysis of Height

25 Apr, 2023 26. Balanced Binary Search Trees [W16]

Deletion in (2,3)-Trees

27 Apr, 2023 27. Recap [W16]

Review of topics covered so far.

No matching items
Issued Assessment Problem Set 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

TBA

10 Feb, 2023 W06. Navigating Graphs (BFS)

TBA

17 Feb, 2023 W07. Navigating Graphs (DFS)

TBA

24 Feb, 2023 W08. More BFS & DFS

TBA

03 Mar, 2023 W09. Practice Lab

TBA

17 Mar, 2023 W10. Sorting Algorithms

TBA

31 Mar, 2023 W12. Sorting Algorithms

TBA

07 Apr, 2023 W13. Heaps

TBA

14 Apr, 2023 W14. Binary Search Trees - I

TBA

21 Apr, 2023 W15. Binary Search Trees - II

TBA

No matching items
Note

The assignments are NOT graded and are made available for practice only.

Issued Assessment Problem Set Solutions Due
Assignment 1

Assignment 2

Assignment 3

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.

Issued Assessment Problem Set Solutions Due
05 Jan, 2023 Quiz 01

05 Jan, 2023
12 Jan, 2023 Quiz 02

12 Jan, 2023
19 Jan, 2023 Quiz 03

19 Jan, 2023
24 Jan, 2023 Quiz 04

24 Jan, 2023
Quiz 05

Quiz 06

Quiz 07

Quiz 08

Quiz 09

Quiz 10

Quiz 11

Quiz 12

Quiz 12

Quiz 13

Quiz 14

Quiz 15

Quiz 16

No matching items
Issued Assessment Problem Set Solutions Due
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

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.


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×