Exam 3

Structure

The exam will consist of a combination of autograded multiple choice, fill in the blank, and a single coding question. Most multiple choice questions will allow you to submit twice, first for full credit and the second for a moderate amount of points.

Concepts

The exam will cover material up to and including 4/22/25. While you may see some review questions from previous content, the focus will be on new material which includes:

• Python Sets
  • Python built-in operations for the set ADT
  • Jaccard Similarity
• Python Dictionaries
  • Python built-in operations for the hash table ADT
• Trees
  • Implementation details, how to use, and Big O for:
    • Binary Trees
    • Binary Search Trees
    • Huffman Trees
  • Tree balance calculations
    • The definition of balance in a binary tree
    • The importance (and meaning) behind a balanced tree
  • Algorithm details including correct output order and Big O for:
    • Pre-Order Traversal
    • In-Order Traversal
    • Post-Order traveral
    • Depth-First Traversal (Note: Can be implemented using pre, in, or post)
    • Breadth-First Traversal

You should be familiar with mp_genomics as well as labs up to and including lab_huffman. The coding question will require you to be familiar with Python sets and dictionaries at the level presented in mp_genomics!

Points: 75

Start: Tuesday, April 29

End: Thursday, May 01