Exam Policies
 Closed book
 Closed notes
 No calculators or other electronic devices
 Begins promptly at 2:30 and ends promptly at 3:20
Topics Covered
The intention of the exam is to cover the material up through
Dijkstra's algorithm that was not covered on the first exam. However,
the course material builds in many ways, so it is "fair
game" to rely on asymptotic complexity, to use queues, stacks,
and trees in appropriate ways or in contrast to other data structures,
etc. The main topics for this exam are amortized analysis, disjoint
sets and unionfind, hash tables and collisionresolution strategies,
and all the graph topics up through and including Dijkstra's
algorithm. All material covered on the exam will have been discussed
in class and included in the posted lecture materials though you may
be asked to apply ideas in slightly new ways.
The exam will not cover any material from Lecture 16.
Exam Format and Sample Midterms
Our exam will consist of various types of shortanswer questions.
You may be asked to write or read Java code or pseudocode. It will be
similar in style to the first midterm, but covering different topics
and with the potential for slightly different styles of questions.
Below are several sample exams from prior offerings of CSE373
but please understand these caveats:
 Topics covered on these exams may not be the exact same topics
covered on our exam; please see above for the topics covered on our
exam. In particular:

Many of these exams include questions about locality,
which we have not studied yet. (This is likely to be covered on
the final exam.)

Some of the older exams cover leftist heaps and skew heaps,
which we did not study. (We won't cover these topics.)

These exams do not have questions about Dijkstra's algorithm or
amortized analysis (because those courses had not covered the
topics yet), so we have also posted some additional example
questions, but as usual our exam may have different kinds of
questions.

Many of these exams have questions about priority queues and
minheaps, which we covered on the first midterm. We may refer
to priority queues since they are useful in Dijkstra's
algorithm, but they will not be a focus by themselves.

The sample exams are provided as a study guide, not as
any guarantee of the format of our actual midterm in terms of
length or type of questions. In particular, they are from a
different instructor since Dan has not taught CSE373 before, and
every instructor brings a certain style to examwriting.
We think you will find the actual exam somewhat familiar
compared to the sample midterms, but some differences are likely.
Sample exams:
Some example questions about Dijkstra's algorithm and amortized analysis:
unsolved
solved
Additional Study Suggestions
 Rework problems from lecture and homework.
 Do additional problems from the textbook.
 Practice all the operations on unionfind, hashing with various
collision resolution strategies, and graphs.
 Be prepared to describe the running time of the operations on each data structure.