CSE 326, Winter 2001.  Midterm Review

Friday, Feb 2 (during class, 1:30-2:20pm).
Closed book, closed notes.

The midterm will cover material from Chapters 1
through 4 in the Weiss book, along with any
other material discussed in class, discussed
in discussion, or that appeared on the homework
and/or programming assignments.


Material you should know:

Basic Mathematics from Chapter 1, including
+ How to manipulate exponents, logarithms, and
series.

+ You should be able to prove a simple
loop invariant or the correctness of a simple
recursive function by induction.

+ There will be no esoteric questions about
C++ templates.  However, code might appear
on the exam, which you will need to be able
to read and understand.

Algorithmic Analysis tools:
+  Big-Oh notation: definitions, rules of thumb
to determine the Big-Oh relationship between
two functions.

+ The RAM model.  Advantages and disadvantages
of the RAM model.  How to analyze running times
of algorithms in the RAM model.

+ Binary search on an array.  Analysis.

+ Abstract data types.  Definition.  Why it is
a useful concept when programming.

+ Lists, stacks, queues.  Linked list and array
implementations.  Applications.

+ Trees.  Definition.  Applications.  Implementation.
Preorder traversal, postorder traversal.  Binary Trees.

+ Binary Search Trees.  Definition.  Dictionary
operations (find, insert, remove) and their
Big-Oh running times.  Inorder traversal.  Average
depth of a binary search tree after N insertions.
Other operations (findMin, findMax, Selection).

+ Balanced Binary Search Trees.  Goal and purpose
of these kinds of trees.  AVL trees: proof of depth,
insert.  Splay trees: basic definitions
and ideas.


Material NOT covered on the midterm:
- programming details such as makefiles.
- Matricies (section 1.7).
- Radix sort (in section 3.2.7).
- Multilists (in section 3.2.7).
- Infix to postfix conversion (in section 3.3.3)


Tips for studying:

Read through the book (slowly) from Chapter 1 onwards.
Review the definitions and concepts.  As you do this,
review your notes and homework problems related to the
material.

Work on some (or all) of the suggested homework problems.
As promised, one or more of them will appear on the
midterm, either word-for-word or a very close variation.

Consider variations of the homework problems and solve
them.  (For example, in problem #2 on HW #2, suppose
the probabilities were 90% and 10% instead of 80%
and 20%. Does that change your judgement about which
scheme is better?)

Practice doing dictionary operations (find, insert,
remove) on the various data structures encountered
so far (lists, stacks, queues, binary search trees,
AVL trees).

Consider any real-world application and think about
what kind of data structure you would use in its
implementation.  Why would one data structure be
better than another in the application?