CSE 373, Autumn 2001.

Midterm Friday, Nov 9 (during class, 12:30-1:20pm).

Closed book, closed notes.

The midterm will cover material from Chapters 1 through 5 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.

Basic Data structures:

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

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

Trees:

• 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).

Balanced Binary Search Trees:

• Goal and purpose of these kinds of trees.

• AVL trees: proof of depth, insert, running time.

• Splay trees: basic definitions and ideas; running time.

• B-trees: motivation and definition.

Hash Tables:

• Goal and purpose.

• Separate chaining.

• Open addressing techniques (linear, quadratic, double, rehashing).

Material NOT covered on the midterm:

• 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).

• Details of B-trees (insert, delete).

• Extendible hashing (section 5.6).

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, Splay trees, hash tables). 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?