# ES 242 | Aug-Nov 2022

## ES242. Data Structures and Algorithms I.

##### August — November 2022

*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!*

Date | Lecture | Slides | Notes | Video |

02 Aug, 2022 |
1. Introduction to Data StructuresData Structures - philosophy and examples • Representing games |
|||

03 Aug, 2022 |
2. Introduction to Data StructuresRepresenting Sequential Data • Arrays • Lists |
|||

09 Aug, 2022 |
Institute Holiday |
|||

10 Aug, 2022 |
Quiz 0 (Ungraded) |
|||

16 Aug, 2022 |
3. Representing GraphsAdjacency Lists • Adjacency Matrices • Edge Lists |
|||

17 Aug, 2022 |
4. Representing Graphs (contd.)Adjacency Lists • Adjacency Matrices • Edge Lists |
|||

23 Aug, 2022 |
5. DequeuesIntroducing the cardstack data structure • The Gilbreath Shuffle |
|||

24 Aug, 2022 |
6. DequeuesQueues and Stacks as special cases of Dequeues |
|||

30 Aug, 2022 |
7. Euler ToursEuler Tour Demonstration • Card trick • de Bruijn sequences • Constructing de Bruijn sequences using Euler Tours |
|||

31 Aug, 2022 |
8. Euler ToursComputing Euler Tours • Hierholzer's algorithm |
|||

06 Sep, 2022 |
9. Stable MarriagesThe Stable Marriage Problem • Gale-Shapley Algorithm |
|||

07 Sep, 2022 |
10. Stable MarriagesProof of Termination • Bounding the number of proposals • Proving the stability of the output |
|||

13 Sep, 2022 |
11. Recap LectureReview of arrays, linked lists, stacks, queues, and graphs |
|||

14 Sep, 2022 |
Theory Quiz 01 |
|||

20 Sep, 2022 |
12. Navigating GraphsAn introduction to navigating graphs |
|||

21 Sep, 2022 |
13. Navigating Graphs (BFS)Breadth-First Search • Correctness • Analysis of Running Time |
|||

11 Oct, 2022 |
14. Navigating Graphs (DFS)Depth-First Search • Pre-Post Intervals |
|||

12 Oct, 2022 |
15. Navigating Graphs (DFS)Depth-First Search • DFS-based classification of vertices • DFS-based classificaton of edges • Cycles and backedges |
|||

18 Oct, 2022 |
16. DFS ApplicationsTopological Sort (Algorithm) |
|||

19 Oct, 2022 |
17. DFS ApplicationsPostorder • Preorder • Topological Sort (Analysis) |
|||

25 Oct, 2022 |
18. Shortest PathsA teaser the challenges in extending BFS to weighted graphs • Pseudopolynomial running time |
|||

26 Oct, 2022 |
19. HeapsSelection Sort • Supporting only Insert and FindMin • The challenge of ExtractMin |
|||

01 Nov, 2022 |
20. HeapsThe Heap Property • Insert • FindMin • ExtractMin |
|||

02 Nov, 2022 |
21. HeapsRepresenting Heaps with Arrays |
|||

08 Nov, 2022 |
Institute Holiday |
|||

09 Nov, 2022 |
Theory Quiz 02 |
|||

15 Nov, 2022 |
22. Heaps RevisitedAnalysis • Heapify is Linear Time |
|||

16 Nov, 2022 |
23. Balanced Binary Search Trees(2,3)-Trees • Insertion • Deletion |
|||

22 Nov, 2022 |
24. Balanced Binary Search Trees(2,3)-Trees Height Analysis |
|||

23 Nov, 2022 |
25. RecapReview of BFS, DFS, Heaps, and Balanced BSTs |

Issued | Assessment | Problem Set | Solutions | Due |

02 Aug, 2022 |
Introduction to Data StructuresData Structures - philosophy and examples • Representing games |
|||

03 Aug, 2022 |
Introduction to Data StructuresRepresenting Sequential Data • Arrays • Lists |
|||

16 Aug, 2022 |
Representing GraphsAdjacency Lists • Adjacency Matrices • Edge Lists |
|||

17 Aug, 2022 |
Representing Graphs (contd.)Adjacency Lists • Adjacency Matrices • Edge Lists |
|||

23 Aug, 2022 |
DequeuesIntroducing the cardstack data structure • The Gilbreath Shuffle |
|||

24 Aug, 2022 |
DequeuesQueues and Stacks as special cases of Dequeues |
|||

30 Aug, 2022 |
Euler ToursEuler Tour Demonstration • Card trick • de Bruijn sequences • Constructing de Bruijn sequences using Euler Tours |
|||

31 Aug, 2022 |
Euler ToursComputing Euler Tours • Hierholzer's algorithm |
|||

06 Sep, 2022 |
Stable MarriagesThe Stable Marriage Problem • Gale-Shapley Algorithm |
|||

07 Sep, 2022 |
Stable MarriagesProof of Termination • Bounding the number of proposals • Proving the stability of the output |
|||

13 Sep, 2022 |
Recap LectureReview of arrays, linked lists, stacks, queues, and graphs |
|||

20 Sep, 2022 |
Navigating GraphsAn introduction to navigating graphs |
|||

21 Sep, 2022 |
Navigating Graphs (BFS)Breadth-First Search • Correctness • Analysis of Running Time |
|||

11 Oct, 2022 |
Navigating Graphs (DFS)Depth-First Search • Pre-Post Intervals |
|||

12 Oct, 2022 |
Navigating Graphs (DFS)Depth-First Search • DFS-based classification of vertices • DFS-based classificaton of edges • Cycles and backedges |
|||

18 Oct, 2022 |
DFS ApplicationsTopological Sort (Algorithm) |
|||

19 Oct, 2022 |
DFS ApplicationsPostorder • Preorder • Topological Sort (Analysis) |
|||

25 Oct, 2022 |
Shortest PathsA teaser the challenges in extending BFS to weighted graphs • Pseudopolynomial running time |
|||

26 Oct, 2022 |
HeapsSelection Sort • Supporting only Insert and FindMin • The challenge of ExtractMin |
|||

01 Nov, 2022 |
HeapsThe Heap Property • Insert • FindMin • ExtractMin |
|||

02 Nov, 2022 |
HeapsRepresenting Heaps with Arrays |
|||

15 Nov, 2022 |
Heaps RevisitedAnalysis • Heapify is Linear Time |
|||

16 Nov, 2022 |
Balanced Binary Search Trees(2,3)-Trees • Insertion • Deletion |
|||

22 Nov, 2022 |
Balanced Binary Search Trees(2,3)-Trees Height Analysis |
|||

23 Nov, 2022 |
RecapReview of BFS, DFS, Heaps, and Balanced BSTs |

Issued | Assessment | Problem Set | Solutions | Due |