Exam 4
Exam 4 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
- Array Representation
- Priority queue ADT
- Disjoint Sets
- Union
- Smart Union (Size and Height)
- Find
- Path Compression
- Array Representation
- Disjoing Set Runtime
- Union-Find (Disjoint Sets) ADT
Assignments referenced:
- MP4, MP5
- lab_huffman, lab_avl, lab_btree, lab_heaps
Points:75
Registration: Sunday, November 01
Start: Friday, November 13
End: Saturday, November 14