Computer Science 269
Introduction to Data Structures
Spring 2000
Final Exam Preparation Page
This page will provide some guidance in preparing for the Final Examination,
which is scheduled for Wednesday, May 10.
Last modification: May 8, 2000

-
There will be a number of true/false or fill in the blank questions.
These could involve anything covered in the course.
-
I expect you to be able to calculate the time complexity of a very small
piece of code. Here are some samples:
-
I will expect you to be able to state loop invariants and input and
output conditions in simple cases. Here are some samples:
-
I will expect you to be able to prove correctness of a function in
a very simple case.
-
I might ask you to analyze the time complexity of a recursive function
in a fairly difficult case.
-
I will expect you to be able to select an appropriate data structure
for a problem. The problem could be a problem that was given in
class or for a programming assignment, or it could be some new but
simple problem created just for the test. Actual C++ coding may not
be required or these questions.
-
Be ready to write
one of the following two in C++ on the final:
-
Be prepared to explain several implementations of the ADT Search Structure
that we have introduced in the course.
-
Analyze all the sorting algorithms
we did this semester.
-
Be prepared to use dynamic programming by hand
to solve some very small problem such as, for example,
finding the minimum weight path between two nodes in a weighted
directed acyclic graph with 10 or 12 nodes that I will provide on
the test.
-
Be prepared to find the minimum spanning tree of a small weighted graph
by hand, showing, by diagram, union/find, including path compression.
