# 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.

## 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