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