| CPSC 327 | Data Structures and Algorithms | Spring 2026 |
Exam 3 will be in class. Take care of any necessary business before class so that you do not need to leave the room during the exam. If you have an unavoidable conflict with the date of an exam, please see me as soon as possible (before the exam date!) to discuss options for rescheduling. Last minute rescheduling/extensions will not be accommodated for something known about in advance.
The exam will be closed book, but you may use one page of notes (one side of an 8.5x11" piece of paper), which will be handed in with the exam. This page may be handwritten or typed and can contain whatever you would like, but it must be a hardcopy — on a piece of paper, not a laptop, tablet, phone, or other device — and must be personally prepared by you — you may not copy another student's page or hand out copies of yours to others. Creating your own notes is an essential part of the learning process — deciding what to include requires engagement with the material which reinforces understanding and improves long-term retention of the material, provides an opportunity for review in order to identify gaps in your knowledge in time to ask questions before the exam, increases confidence in what you do know, and encourages taking ownership of your own learning.
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 separate from graphs.) 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 implementations of the Graph ADT (adjacency list and adjacency matrix) and the resulting space requirements and running times for the Graph ADT operations
common graph algorithms
modeling problems as graph problems
For all of the graph algorithms listed above, you should know what the task is (e.g. what is a cut vertex or a transitive closure) and what the algorithm applies to (weighted graphs, directed graphs, acyclic graphs, ...). You should also be familiar with the applications of the task discussed in class and be able to new recognize situations where the task is applicable (e.g. determining an order of classes that satisfies prerequisites is an application of topological sort).
For everything but "other algorithms" (all-pairs shortest path and transitive closure) you should also know the algorithm itself (be able to trace it) and its running time with standard implementations of the relevant data structures.
Homeworks 6-7 and part of homeworks 5 and 8 (#1-2 only for hw5, #4 only for hw8) and the Graph ADT, Dijkstra's implementation, and ski-o programming assignments cover material that may be on the exam. Expect questions like those on the homeworks (tracing algorithms, modeling problems as graph problems, identifying the properties of a particular graph) as well as questions relating to implementation and running times (such as the running times of Graph ADT operations or graph algorithms using standard or alternative implementations of the Graph ADT and other data structures), though you won't be asked to write code.