Exam 2 Study Guide


  • 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):

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

Data Structures

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