Overview

Theory Exam 3 is worth 70 points.

Theory Exam 3 contains only multiple choice or short answer problems. You will not be required to write any standalone code outside of the PrairieLearn web interface. 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