Overview

The CS 225 final exam is worth 150 points.

The final exam will contain a mix of multiple choice, short answer, and programming problems. We view the final exam as an exam that combines a theory and a programming exam into a single exam. The weight of the programming and theory components of the exam will be roughly equal.

The final exam is comprehensive. Topics not covered on a previous exam (ex: graphs) will appear more than topics covered on a previous exam.

Topics Covered

All topics covered in previous exams:

• Programming Exam A
• Programming Exam B
• Programming Exam C
• Theory Exam 1
• Theory Exam 2
• Theory Exam 3

Topics not covered in a previous exam:

• Disjoint Sets
  • UpTree
  • An array-based implementation of an UpTree
  • Operation find
  • Operation union
  • “Smart Union”: Union by Size, Union by Height
  • Path Compression
  • Iterated logarithm
• Graphs
  • Terminology
  • Graph implementations
  • Edge List
  • Adjacency Matrix
  • Adjacency List
  • Tradeoff between graph implementations
  • Traversals
  • What do all graph traversals find and count?
  • BFS
    • Discovery Edges
    • Cross Edges
      
  • DFS
    • Discovery Edges
    • Cross Edges
  • Solving problems with graphs traversals
  • Minimum Spanning Trees (MSTs)
  • Kruskal’s Algorithm
  • Prim’s Algorithm
  • Fibonacci heap’s improvement to Prim’s runtime (ex: decrease-key)
  • Solving problems on MSTs
  • Single Source Shortest Path (SSSP)
  • Dijkstra’s Algorithm
  • Dijkstra’s and Edge Weights
  • Dijkstra’s and Cycles
  • Dijkstra’s and Negative Weight Cycles
  • Dijkstra’s and Negative Weight Edges
  • Solving problems with SSSPs
  • All Pairs Shortest Path (APSP)
  • Dynamic programming
  • Floyd-Warshall
  • Solving problems with SSSPs
  • Running Times

Assignments referenced:

• All MPs
• All labs