Theory Exam 3 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.
Topics Covered
Note: Topics covered on previous exams may be referenced (eg: you need to be able to compare anything vs. the running time of a sorted array/list, etc).
New topics from lecture for the exam:
- AVL
- Difference between a “Tree”, “BST”, and an “AVL”
- Operation
find, including running times in terms of h and n
- Operation
insert, including running times in terms of h and n
- Operation
delete, including running times in terms of h and n
- Strategy for a 2-child delete
- AVL Tree Rotations
- Minimum/maximum nodes in an AVL tree
- BTree
- Difference between a key and a node in a BTree
- The order of a BTree
- Structural properties of a BTree
- The min/max keys/children in each node in a BTree
- The min/max total number of keys in a BTree
- Advantages of a BTree
- Running time of a BTree
- Hash Table
- Hash functions
- Properties of a good hash function
- SUHA
- Hash Table Array
- Load Factor
- Hash Table Collisions
- Open Hashing vs. Closed Hashing
- Separate Chaining
- Linear Probing
- Double Hashing
- Re-Hashing
- Runtime of a hash table, in terms of
n
- Load factor’s impact on running times
- Properties of a good hash table
- Heaps
- Construction of a Heap
- Heap runtime
- HeapifyUp
- HeapifyDown
- Priority queue ADT
Assignments referenced:
- MP4, MP5
- lab_huffman, lab_avl, lab_btree, lab_heaps
Points:70
Registration: Thursday, March 21
Start: Thursday, April 04
End: Sunday, April 07