Exam 3 Review Information

Exam 3 will be a take-home exam. You may use the textbook, your own notes and problem solutions, the materials posted on the course website, and external websites directly linked from the course website. You may not use other resources, including web resources linked from things the course website links to. You may not get notes or other materials from or share notes or other materials with other students once the exam has been handed out, even if those notes/materials aren't directly related to the exam.

The only person you may discuss the exam with is me - I will answer clarification questions, but the exam is meant to be a demonstration of what you can do so I will not provide help on how to solve the problems.

The exam will primarily cover graphs. (Older material such as analysis of algorithms, ADTs, and data structures may appear as relevant to that topic, but there won't be questions solely about that material.) Specific topics include:

graph terminology: vertex, edge, incident, adjacent, degree (indegree, outdegree), path, cycle, self loops, multiedges
graph properties: undirected vs directed graph, connected vs not connected, simple vs not simple, sparse vs dense, cyclic vs acyclic, weighted vs unweighted
the Graph ADT discussed in class
standard graph implementations (and the resulting running times for the Graph ADT operations)
common graph algorithms
- DFS, BFS, and their applications (reachability, connected components, unweighted shortest paths, bipartite graphs/two coloring, detecting cycles, cut vertices and edges, topological sort)
- weighted shortest paths: Dijkstra's algorithm, Bellman-Ford
- minimum spanning tree: Kruskal's algorithm, Prim's algorithm
- other algorithms discussed in class (all-pairs shortest paths, transitive closure)

For the graph algorithms listed above, you should know what the task is (e.g. what is a cut vertex or what is a transitive closure) and be able to state and explain the algorithm's running time for standard implementations of the relevant data structures. For everything but all-pairs shortest path and transitive closure you should additionally know the algorithm itself (be able to trace it) and when it is applicable (weighted graphs, directed graphs, acyclic graphs, ...).

Homeworks 11-12 and the two programming assignments (Graph ADT and Dijkstra's algorithm) cover material that may be on the exam, though you won't be asked to write code. In addition to the algorithm tracing questions similar to the homeworks, you might be asked about the properties of a particular graph, the behavior of a graph algorithm, something involving Graph ADT implementation, or how a different implementation of a key data structure impacts the overall running time of an algorithm.