# Final Exam Final Exam

Registration opens: | Thursday, March 22 |
---|---|

Exam starts: | Thursday, May 3 |

Exam ends: | Thursday, May 10 |

## 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