Exam 2 Study Guide

Changelog

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

FAQ

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

Definitions/Concepts

• 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

Data Structures

• Binary Search Trees
• Heaps
  • max-heapify
• Priority Queues
• Graph (directed/undirected)
  • adjacency lists
  • adjacency matrix

Algorithms

• 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.
• Counting sort
• Radix Sort
• Bucket Sort
• Breadth-first search
• Depth-first search