CSE 373 Winter 2006

Midterm 2 topics

You are responsible for everything covered in lecture and on the homework up to the basic definitions for graphs. You are not responsible for any specific readings in the book, but you should be familiar with the material in the book relevant to these topics. The exam will be biased towards topics covered since the first midterm, but may include earlier material - particularly in comparing earlier topics to current ones. You are still responsible for topics from the first midterm, even if they aren't covered extensively on this one.

• Binary search trees and their operations (mostly review), particularly insert, find, and remove
• Iterators for trees
• Balanced trees, particularly AVL and splay trees, but also the basic ideas behind 2-4 trees and red-black trees
  • Motivation - why are balanced trees important?
  • Cost of operations - what are the asymptotic average and worst-case costs? How much work is needed to do the balancing?
  • What can the different trees look like? What are the relationships between the number of nodes, shortest and longest paths, etc.?
  • When are balancing operations performed?
• For balanced trees you should focus on:
  • What do the different balancing (rotation) operations look like, particularly for AVL and splay trees? Know the diagrams - don't memorize code, but be able to code up the details of any particular diagram (either one of the standard ones or one that is given on the test) if you need to
  • Be able to draw diagrams showing the results of various operations (i.e., what happens if we search, insert, or delete these values in a particular kind of tree)
  • Know how to represent trees with Java data structures (objects), both with and without stored pointers to parent nodes, and be able to write code to manipulate them
• Hashing
  • Know the basic ideas behind computing and scaling hash functions to select hash table buckets
  • What makes a good hash function? (even distribution of keys among buckets, fast to compute, etc.); how do you compute hash codes for compound objects?
  • Colision handling - what happens when two or more keys have the same hash value
  • Load factor - what is it (# items / # buckets), why it should be fairly small and how small should that be, rehashing to redistribute items in a larger table if the load factor is too big
  • Performance - what are the expected costs of various operations, particularly insert, find, and remove?
  • Java specifics - where are equals(...) and hashCode() defined? How should they be overridden in user-defined classes? What is the relationship between equals(...) and hashCode()?
• Graphs
  • Know the basic terminology such as nodes, edges (directed vs. undirected), etc.