STUDY GUIDE FOR MIDTERM

CSE 326 Autumn 2000

· Exam will be Friday, Oct 27^th, from 2:30 to 3:20.

· Material to be covered: everything through Wednesday, Oct 25th.

· Questions will be drawn from:

o Weiss, Chapters 1 – 5. Only Sections 1.2-1.3 of Chapter 1 are relevant.

o Material from Project 2 on searching graphs.

o The lecture handouts.

· There will NOT be any questions on:

o Splay trees

o Radix sort

o Details of C++

· The exam will be closed books, closed notes.

· Be sure you know:

o how to compare functions using O(N), Θ(N), and Ω(N) notation

o how to analyze the running times of programs using the notions of worst case and best case complexity

o how to solve a simple recursive equation

o basic concept of average case analysis

o how to carry out a simple amortized analysis, of the type done in the lecture notes for stretchy arrays and rehashing

o tree traversals (preorder, inorder, postorder)

o how the basic dictionary operations are implemented, what their worst-case (and when appropriate, average case) running times are and what the tradeoffs are for using

§ linked lists and array-based lists, including lists of lists

§ unsorted and sorted lists

§ binary search trees (without balancing)

§ AVL trees

§ B-trees

§ hashing (including separate chaining, linear probing, quadratic probing, and double hashing).

· Study suggestions

o go over all the previously assigned homework problems carefully

o practice dictionary operations (find/insert/delete) on each of the data structures mentioned above

o perform the following algorithm:

do { choose two data structures;

think of a real-world application where the first would be superior to the second;

} until ( ready for exam )