CSE 373 Winter 2007

Midterm topics

You are responsible for everything covered in lecture and on the homework up through balanced trees and hashing. 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.

You may bring to the exam one (1) 4x6" or smaller index card with whatever notes you find useful. Otherwise the exam is closed book, notes, etc.

Don't waste time memorizing detailed Java code - instead focus on knowing the pictures, ideas, and strategies behind the different data structures and algorithms so you can come up with detailed code when you need to.

Some of the basic topics here are mostly review from previous courses (fundamentals of arrays, lists, stacks, queues, trees, etc.). These will not be emphasized on the test, but you should be familiar with them and be able to use them as needed.

• Basic collection types and their operations; understand how to use them, both with and without generic type parameters.
  • Lists (add, contains, indexOf, size, isEmpty, remove, clear, etc.)
  • Stacks (push, pop, top, isEmpty, etc.)
  • Queues (enqueue, dequeue, front, isEmpty, etc.)
  • Sets (add, contains, size, remove, etc.)
• Standard Java collection classes - don't memorize JavaDoc, but be able to use these classes if you are given reference information about them
• Implementation techniques for collections
  • Arrays
  • Linked lists (single, double, be able to work with variations like circular lists and extra header/tail nodes if requested)
  • Binary trees and binary search trees; including terminology, traversals, insert, delete, search, etc.
  • Hash tables
• Trading off extra data and bookkeeping to speed up operations (e.g., calculating size of a list vs storing it in a variable)
• Iterators
  • Creating and using iterators; why do we have them?
  • Implementing iterators for various collections (arrays, linked lists, trees, ...)
• Basic complexity theory
  • Concept of asymptotic complexity
  • Definition of O(...); know how to prove that a function is O(...) and what that means
  • Know the basic complexity classes in order from least to most expensive (O(1), O(log n), O(n), ...)
  • Complexity classes of operations in the different collection implementations
  • Amortized complexity - for example, why can we say that insert in a dynamically- expanding arraylist is O(1) and how do we prove it?
• Balanced trees, particularly AVL and splay trees, but also the basic ideas behind B 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?
  • Be able to draw diagrams showing the results of various operations (i.e., what happens if we search, insert, or delete particular 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?
  • Collision 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? When can costs be worse than this and how can this be avoided (quality of hash functions, rehashing)?
  • 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()?
• Java best practices
  • Proper coding style and techniques (how to define interfaces and classes; public/private; use of Java language constructs including arrays, objects and new; types; inheritance basics; etc.)
  • Commenting, including writing and reading basic JavaDoc
  • Testing, particularly using JUnit for unit tests and test coverage strategies (empty, one, many; typical vs edge cases; etc.)
  • Generic types: know the basics of how to declare a generic type parameter (<T>) and use it in a parameterized collection class; you do not need to know details like wildcards(<?>), bounded types (extends or super), etc.