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 Minimum
spanning trees 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 union-find, hash tables and collision-resolution
strategies, and all the graph topics up through and including
minimum spanning trees. 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 the lectures on 2/21 and 2/24.
Exam Format and Sample Midterms
Our exam will consist of various types of short-answer 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 exams prior to Fall 2013 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, minimum spanning trees, 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
min-heaps, 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 Aaron has not taught CSE373 before, and
every instructor brings a certain style to exam-writing.
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
Some example questions about minimum spanning trees:
unsolved
solved
Additional Study Suggestions
- Re-work problems from lecture and homework.
- Do additional problems from the textbook.
- Practice all the operations on union-find, hashing with various
collision resolution strategies, and graphs.
- Be prepared to describe the running time of the operations on each data structure.
