Exam 5

The exam will consist of multiple choice questions and one coding question. There will be no free response question on this exam. The coding question 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 coding question will require you to write some code on a graph.

The topics on the exam include all material through Monday April 21. While earlier material may show up, the focus is on the following topics:

• Graphs
  • Graph Implementations
  • Graph Traversal
  • MST Algorithms Prim’s algorithm and Kruskal’s algorithm
  • Shortest Path Dijkstra’s algorithm and Floyd–Warshall algorithm
• Fundamentals of Probability in CS
• Hashing
  • Properties of a hash function
  • SUHA
  • Types of Hashing
  • Resizing a hash table

Assignments referenced:

• mp_lists, mp_mosaics, mp_traversals, mp_mazes
• lab_flow, lab_hash
• lab_dict (less relevant to the broad topics than other three listed labs but may still show up)

Points:70

Registration: Thursday, April 17

Start: Monday, April 28

End: Wednesday, April 30