The exam will be similar in style to Exam 1. It will be cumulative in that if you have totally forgotten everything from the first exam, you won't be able to do the second exam. However, the emphasis will be on material since the first exam.

You may bring one 8.5 by 11 inch sheet of paper with your own notes on it to the exam. You may write on both sides.

Review the following:

• lecture notes, Slides 195-283 plus material on AVL trees and skip lists

• assigned readings, Standish Chs 7, 8 (through Sec 10, skipping Sec 8), 9, and 10 (through Sec 5, excluding QuickSort)

• Quizzes 7 through 10 and their solutions (given in class)

• Programs 5 and 6

• For the List ADT, know
  • the specification (using the abstract state style)
  • the array implementation(s)
  • the linked list implementation(s)
  • the pros and cons of the different implementations (space and time of the various operations)
  • applications: LISP, strings, dynamic memory allocation

• Trees and their related definitions and facts; binary tree traversals

• Binary heap: definition, algorithms for insert and remove, array implementation, applications (priority queue, heapsort)

• For the Dictionary ADT, know
  • the specification (using the abstract state style)
  • the search tree implementations
    • know details of basic binary search tree
    • know details of trie
    • know general idea about balanced search trees (AVL, red-black, B-tree)
  • the hash table implementations:
    • chaining: implementation, space and time (both worst-case and average case), criterion for good hash function
    • open addressing w/ linear probing and w/ double hashing: implementations, space and time (both worst-case and average case), criterion for good hash function
  • the skip list implementation: space and time (both worst-case and average case)
  • the pros and cons of the different implementations (space, and time of the various operations)
  • database application

• Sorting: insertion sort, heapsort, treesort, mergesort.