Back to Quizzes

Exam 3

Exam 3

Exam 3 is focused primarly on the material since Exam 2 but will also review the material from the pervious exam.

Exam 3 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.

Topics Covered

Topics from lecture (all BST concepts, no AVL trees):

  • BTree
    • Difference between a key and a node in a BTree
    • The order of a BTree
    • Structural properties 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
  • Graphs
    • Graph Representation
    • Graph Traversal
    • MST Algorithms Prim’s algorithm and Kruskal’s algorithm

Assignments referenced:

  • mp_traversals, mp_mazes
  • lab_hash, lab_btree, lab_heaps

Points:100

Registration: Wednesday, April 15

Start: Thursday, April 30

End: Friday, May 01