- 2022-11-12 Create the study guide
- 2022-11-19 Add some LeetCode problems

**Q**: What topics/material am I responsible for?

**A**: Class material through Depth First Search and assignment 5.

**Q**: What resources may I use during the exam?

**A**: As with exam 1, you may bring on 8 1/2 x 11in page of notes. You will hand in your notes with your exam. (I'll give them back--having access when I'm grading means I have an easy way to know why you and your study partner wrote the same answer.)

**Q**: Will there be a practice/sample exam again?

**A**: No. Here a couple of relevant LeetCode problems (these don't cover all relevant topics):

- Sum of Left Leaves
- Same Tree
- Maximum Depth of Binary Tree
- Binary Tree Level Order (I kind of wish I'd put this on the exam)

**Q**: What sort of questions will be on the exam?

**A**: Much like last time, expect to:

- explain trade-offs (why would we do X and not Y in situation ABC?)
- modify one of the algorithms we've seen to solve a problem
- use the data structures we've seen to solve a problem

- traversals of binary search trees
- pre-order
- in-order
- post-order

- successor/predecessor in a binary search tree
- height of a tree
- graphs (see appendix B.4 in the book)
- undirected graph
- directed graph
- cycle
- DAG: directed acyclic graph

- degree/in-degree/out-degree
- connected component
- complete graph
- bipartite graph

- Binary Search Trees
- Heaps
- max-heapify

- Priority Queues
- Graph (directed/undirected)
- adjacency lists
- adjacency matrix

- Heap sort
- Quicksort
- We talked about two different partitioning schemes. I will
*not*ask you about Hoare partitioning. If you need to implement quicksort on the exam, you may use whatever version you like.

- We talked about two different partitioning schemes. I will
- Counting sort
- Radix Sort
- Bucket Sort
- Breadth-first search
- Depth-first search