Exam 1 Study Guide

Changelog

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.

FAQ

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.

• Mock Exam
• Solutions

Definitions/Concepts

• 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

Algorithms

• insertion sort
• merge sort
• binary search