Skip to content
Data Structures and Algorithms

DSA I · January–April 2023

IIT Gandhinagar · ES242

This archived edition introduces data structures through the operations they support, then develops graph representations and traversal, searching, sorting, heaps and search trees.

Published lecture schedule

DateTopic
03 Jan, 20231. Introduction to Data Structures [W1] Data Structures - philosophy and examples • Representing games
05 Jan, 20232. Stable Marriages [W1] The Stable Marriage Problem • Gale-Shapley Algorithm
10 Jan, 20233. Representing Sequential Data [W2] Arrays • Lists • Implementing the Gale-Shapley Algorithm
12 Jan, 20234. Representing Graphs [W2] Adjacency Lists • Adjacency Matrices • Edge Lists
17 Jan, 20235. Dequeues [W3] The Gilbreath Shuffle • Properties of the shuffle
19 Jan, 20236. Dequeues [W3] Queues and Stacks as special cases of Dequeues
24 Jan, 20237. Euler Tours [W4] Euler Tour Demonstration • The Bridges of Königsberg
31 Jan, 20238. Euler Tours [W5] Computing Euler Tours • Hierholzer's algorithm
02 Feb, 20239. Recap Class [W5] Review of topics covered so far.
09 Feb, 202310. Navigating Graphs (BFS) [W6] Breadth-First Search • Correctness • Analysis of Running Time
14 Feb, 202311. BFS Applications [W7] Shortest Paths • Pseudopolynomial algorithm for weighted graphs
21 Feb, 202313. Navigating Graphs (DFS) - I [W8] Depth-First Search • Implementation with Stacks
23 Feb, 202314. Navigating Graphs (DFS) - II [W8] Depth-First Search • DFS-based classification of vertices • DFS-based classificaton of edges • Cycles and backedges
03 Mar, 202315. BFS and DFS Applications [W9] Testing Bipartiteness • Topological Sort
16 Mar, 202316. Sorting Algorithms [W10] Examples of Sorting Algorithms • Properties of sorting algorithms
21 Mar, 202317. Asymptotics [W10] Comparing Algorithms by Performance • Big-O Notation
28 Mar, 202318. Heaps [W12] Supporting only Insert and FindMin • The challenge of ExtractMin • The Heap Property • Insert • FindMin • ExtractMin
06 Apr, 202319. Heaps [W13] Representing Heaps with Arrays • Analysis: Heapify in Linear Time
11 Apr, 202320. Trees [W14] Rooted Trees • Inorder, Preorder, and Postorder Traversals
13 Apr, 202321. Search [W14] Binary Search • Ternary Search
18 Apr, 202322. Balanced Binary Search Trees [W15] Introduction to BSTs • (2,3)-Trees
20 Apr, 202323. Balanced Binary Search Trees [W15] Insertion in (2,3)-Trees • Analysis of Height
25 Apr, 202324. Balanced Binary Search Trees [W16] Deletion in (2,3)-Trees
27 Apr, 202325. Recap [W16] Review of topics covered so far.

Original course page · Shared slide library

The original page has an older 2022 title in its outer heading; its course heading and dated lecture schedule identify this as the January–April 2023 edition.