Exam 2

Structure

The exam will consist of autograded multiple choice, fill in the blank questions, 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 Wednesday March 6th. You should be familiar with everything covered in class or as part of an assignment. That said, to help you identify core topics that you should definitely prepare for:

• Some review questions from past material
• Recursion
  • Breaking problems down into ‘base case’, ‘recursive step’, ‘combining step’
  • Fundamentals of reading small recursive functions
• Trees
  • Fundamental tree terminology
  • Implementation details (the ADT), how to use, and Big O for:
    • Binary Trees
    • Binary Search Trees
  • Algorithm details including correct output order and Big O for:
    • Pre-Order Traversal
    • In-Order Traversal
    • Post-Order Traveral
    • Depth-First Search
    • Breadth-First Search
  • Tree balance calculations
    • The definition of balance in a binary tree
    • The importance (and meaning) behind a balanced tree

You should be familiar with mp_automata as well as labs up to and including lab_trees. The coding question will require you to be familiar with 2D Lists / Matrices at the level presented in mp_automata!

Points: 75

Start: Tuesday, March 19

End: Thursday, March 21