Final Time: December 14, 3-5pm, in class (or testing center)

---------------
Coverage: Lectures  1-23, Chapters 1, 2, 3, 4, 5, 6, 7, 9
Programming assignments 3, 4, 5.

--------------
Some exam information:

0) Format: Short questions (around 60 points), long questions and 
   programming questions (around 40 points)
1) Questions are mostly on the materials after the midterm (trees, hash table,
   priority queue, sorting, graph). No detailed implementation question on
   materials before the midterm. 
2) 20-25 points on programming assignments 3, 4, 5.
3) formal definition of O, theta, or Omega notations is in the exam.
4) Coding questions are all related to programming assignments.
5) Many of the problems are similar to those in the homework:
   make sure that you can do homework problems correctly and apply the
   techniques.

--------------

This reading list only contains materials after midterm: you must review 
materials before midterm as well.

Chapter 4: Trees

- General concepts: binary tree, complete binary tree, Vector representation
  of complete tree, 
- in-order, pre-order, post-order, and level-order traversal
- Binary search trees: definition, and implementation: insert, remove, 
  contains, findMin, findMax, 
- AVL trees: definition, insert (single rotation and double rotation)
- B-trees: definition, insert and remove operations

Chapter 5: Hash Table
- general idea
- hash function
- hash table implementation
  + separate chaining
  + linear probing
  + quadratic probing
  + double hashing

Chapter 6: Priority queue
- Partially ordered trees
- Heap
- Implementation of priority queue

Chapter 7: Sorting
- algorithms and implementations of different sorting schemes
  + bubble sort, insert sort, heap sort, merge sort, quick sort, bucket sort,
    radix sort
- lower bounds for simple sorting algorithms and the general lower bound for
  comparison based sorting

Chapter 9: Graph algorithms
- definitions of various graph concepts
- graph representation methods
- graph algorithms
  + topological sort
  + Dijkstra's single source shortest path algorithm

---------------------------------------------------------------------