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 presented in weeks 10 - 14. 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:

Note: It is likely we will not complete all graph algorithms by the end of week 14. If we cover it in week 15, the material will not show up on Exam 3 but may still show up on the final exam (or exam 3 retake).

• Trees
  • Implementation details, how to use, and Big O for:
    • Binary Trees
    • Binary Search Trees
    • Balanced Binary Search Trees (AVL Trees)
    • k-d Trees
    • Huffman Trees
  • 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
    • Nearest Neighbor Search
    • AVL Rotations (When to use, how to use, and what the rotations do)
• Graphs
  • Implementation details, how to use, and Big O for:
    • Edge Lists
    • Adjacency Matrices
    • Adjacency Lists
  • Algorithm details including correct output order and Big O for:
    • Depth-First Traversal
    • Breadth-First Traversal
    • Dijkstras Single-Source Shortest Path (SSSP) Algorithm
    • Minimum Spanning Tree Algorithms:
      • Kruskal
      • Prim

Points: 100

Start: Tuesday, April 25

End: Thursday, April 27