# ES 242 | Aug-Nov 2022

## ES242. Data Structures and Algorithms I.

##### January - April 2023

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

Date | Lecture | Slides | Notes | Video |

1. Introduction to Data StructuresData Structures - philosophy and examples • Representing games |
||||

2. Stable MarriagesThe Stable Marriage Problem • Gale-Shapley Algorithm |
||||

3. Representing Sequential DataArrays • Lists |
||||

4. Representing GraphsAdjacency Lists • Adjacency Matrices • Edge Lists |
||||

5. DequeuesIntroducing the cardstack data structure • The Gilbreath Shuffle |
||||

6. DequeuesQueues and Stacks as special cases of Dequeues |
||||

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

8. Euler ToursComputing Euler Tours • Hierholzer's algorithm |
||||

9. Navigating Graphs (BFS) - IBreadth-First Search • Correctness • Analysis of Running Time |
||||

10. Navigating Graphs (BFS) - IIBreadth-First Search • Correctness • Analysis of Running Time |
||||

11. BFS Applications - IShortest Paths • Pseudopolynomial algorithm for weighted graphs |
||||

12. BFS Applications - IITesting Bipartiteness |
||||

13. BFS VariantsMultisource BFS • Parallel BFS |
||||

14. Recap LectureReview of arrays, linked lists, stacks, queues, and graphs |
||||

15. Navigating Graphs (DFS)Depth-First Search • Pre-Post Intervals |
||||

16. Navigating Graphs (DFS)Depth-First Search • DFS-based classification of vertices • DFS-based classificaton of edges • Cycles and backedges |
||||

17. DFS ApplicationsTopological Sort (Algorithm) |
||||

18. DFS ApplicationsPostorder • Preorder • Topological Sort (Analysis) |
||||

19. Sorting AlgorithmsSelection Sort • Properties of sorting algorithms |
||||

20. HeapsSupporting only Insert and FindMin • The challenge of ExtractMin |
||||

21. HeapsThe Heap Property • Insert • FindMin • ExtractMin |
||||

22. HeapsRepresenting Heaps with Arrays • Heapify is Linear Time |
||||

23. TreesRooted Trees • Inorder, Preorder, and Postorder Traversals |
||||

24. SearchBinary Search • Ternary Search |
||||

25. Balanced Binary Search TreesIntroduction to BSTs • (2,3)-Trees |
||||

26. Balanced Binary Search TreesInsertion in (2,3)-Trees • Analysis of Height |
||||

27. Balanced Binary Search TreesDeletion in (2,3)-Trees |
||||

28. RecapReview of BFS, DFS, Heaps, Balanced BSTs, Sorting and Searching |

Issued | Assessment | Problem Set | Solutions | Due |

W01. RepresentationsTBA |
||||

W02. C Warmup and RecapTBA |
||||

W03. Representing GraphsTBA |
||||

W04. The CardstackTBA |
||||

W05. Euler Tours and de Bruijn SequencesTBA |
||||

W06. Stable MarriagesTBA |
||||

W08. Navigating Graphs (BFS)TBA |
||||

W09. Practice LabTBA |
||||

W10. Navigating Graphs (DFS)TBA |
||||

W11. Graph Traversal ApplicationsTBA |
||||

W12. HeapsTBA |
||||

W13. Binary Search TreesTBA |
||||

W14. Practice LabTBA |

Issued | Assessment | Problem Set | Solutions | Due |

Assignment 1 |
||||

Assignment 2 |
||||

Assignment 3 |

Issued | Assessment | Problem Set | Solutions | Due |

Quiz 1 |
||||

Quiz 2 |
||||

Quiz 3 |
||||

Quiz 4 |
||||

Quiz 5 |
||||

Quiz 6 |
||||

Quiz 7 |
||||

Quiz 8 |
||||

Quiz 9 |
||||

Quiz 10 |
||||

Quiz 11 |
||||

Quiz 12 |

Issued | Assessment | Problem Set | Solutions | Due |

Exam 1 |
||||

Exam 2 |
||||

Exam 3 |