Back to Exams

Exam 5

There will be one programming question. The programing question will be in an enviroment identical to the PotDs. It will require programming complete and correct C++ programs. Partial credit will only be given for working, compilable code that passes some test cases. Code that doesnt compile will not receive any credit. Multiple (but not unlimited) submissions will be allowed.

The programming question will be to implement some heap functionality and to use it.

There will also be several short answer or multiple choice questions on material up to and including Wednesday November 15th. For a rough list of topics worth studying (not guaranteed to be exhaustive!):

  • Heaps
    • Construction of a Heap
    • Heap runtime
    • HeapifyUp
    • HeapifyDown
    • Array Representation
    • Priority queue ADT
  • Hash Table
    • Dictionary ADT
    • Open Hashing vs Closed Hashing
    • Collision Resolution Strategies
    • Hash Table Resizing (When and How)
    • The Simple Uniform Hashing Assumption (SUHA)
    • Expectation vs Big O
  • Bloom Filter
    • ADT and Big O
    • Probabilistic Accuracy
    • Optimality Equation (and FPR)
    • Bit Vector operations
  • MinHash
    • ADT and Big O
    • Cardinality Estimation with Kth Minimum Value
    • Jaccard Similarity
    • Similarity Estimation (Direct and Indirect)
  • Graphs
    • Graph Implementations (ADT and Big O)

Assignments referenced:

  • mp_traversals, mp_mazes, mp_sketching
  • lab_heaps, lab_bloom, lab_hash

Points:60

Registration: Thursday, November 09

Start: Monday, November 27

End: Wednesday, November 29