# Final Exam Study Guide

## Changelog

2022-12-10 Create the study guide.

## FAQ

**Q**: When is the final?

**A** Thursday, December 15, 8am-10.15. NAC 5/102 (the regular classroom).

**Q**: May I bring a page of notes?

**A**: Yes, same as the prior exams, you may bring one 8 1/2 x 11in page of notes.

**Q**: If something isn't on this list, am I responsible for it?
**A**: Yes. (Though, in full disclosure, I use the list as an aid in writing the exam.)

## Things to be Prepared For

- Defining terms
- Explaining the tradeoff between two implementations of a data structure (eg open addressing vs chaining in a hash table)
- Knowing the assumptions of/preconditions for using an algorithm
- Applying/modifying one of the algorithms we've seen to solve a problem

## Definitions/Concepts

- computational complexity
- hashing
- load factor
- linear + quadratic probing
- double hashing
- uniform hashing

- graphs
- direct and undirect graphs
- weighted graphs
- cycle
- DAG: directed acyclic graph

- connected components
- strongly connected components
- bipartite graph

- trees
- traversals of binary search trees:
- pre-order
- in-order
- post-order

- successor/predecessor
- height

## Data Structures

- arrays
- linked lists
- singly linked lists
- doubly linked lists

- stacks
- queues and deques
- hash tables (and implicitly hash sets)
- bloom filters
- binary search trees
- heaps
- priority queues
- graphs:
- directed/undirected
- adjacency list representation
- adjacency matrix representation

## Algorithms

- sorts
- insertion sort
- merge sort
- heap sort
- quick sort
- counting sort
- radix sort
- bucket sort

- binary search
- graph algorithms
- breadth-first search
- depth-first search
- topological sorting
- discovering strongly connected components
- Bellman-Ford
- Dijkstra