This is a list of terms that might help you study for the exam. It does not include all the terms that you will have learned in prerequisite courses.

• abstract data type
• worst case running time
• asymptotic running time
• big O
• big Omega
• big Theta
• rule of sums
• rule of products
• dictionary
• binary search tree
• AVL tree
• AVL balance
• height and depth of a tree node
• single and double AVL rotations
• splay tree
• splay
• concatenation of splay trees
• zig-zag and zig-zig rotations
• amortized running time
• hashing
• hash function
• hash table
• collision
• collision resolution
• separate chaining
• open addressing
• linear probing
• double hashing
• load factor
• rehashing
• universal class of hash functions
• quicksort
• pivot
• mergesort
• recurrence
• undirected graph
• directed graph
• vertex
• edge
• adjacent
• neighbor
• adjacency matrix
• adjacency list
• path
• cycle
• connected graph
• acyclic
• topological sort
• breadth-first search