Exam 1 Study Guide


2022-10-04 Added sample exam and solutions 2022-09-24 Added list of topics and concepts covered.
2022-09-22 Create the study guide. This is clearly a work in progress.


Q: What topics/material am I responsible for?
A: Class material through 9/22 (bloom filters) and assignment 3.

Q: What resources may I use during the exam?
A: You may bring one 8 1/2 x 11 in page of notes. You will hand your notes in with your exam.

Sample Exam

Note: Do not assume this sample is representative of the length of the actual exam. You can also bet I'll ask a bloom filter question.


  • computational complexity
    • big-O, Ω, Θ
    • little-o, ω
    • amortization (the concept; I will not ask you to do the calculation)
  • hashing
    • load factor
    • linear probing
    • quadratic probing
    • double hashing
    • uniform hashing
    • rehashing

Data Structures

  • arrays
  • linked lists
  • doubly linked lists
  • linked lists with sentinels
  • queues
  • deques (double-ended queues)
  • stacks
  • hash tables
  • bloom filters


  • insertion sort
  • merge sort
  • binary search