Final Exam Topics

date: Monday, March 17

time: 10:15pm - 12:15pm

format: Open text and notes.

location: 307 VOL

review session: tba

previous finals:

• Winter 2007
• Fall 2006

• Algorithm analysis
  • reading: chapters 2 and 3.
  • fair questions: deal with a logarithm, analyze a piece of code, Big-O notation (and Omega and Theta).

• Simple data structures
  • reading: chapter 10
  • fair questions: know implementation, simple uses of stacks and queues, write simple linked list code

• Binary Search Trees
  • reading: chapter 12
  • fair questions: insert values into BST, BST deletion, understand behavior of random BST (internal and external path lengths). Modify the BST to some purpose. Traversals (inorder, preorder, postorder).

• AVL, 2-4, and Red-Black trees
  • reading: chapter 13
  • fair questions: Insertion, deletion (for RB). Know properties.

• B-trees
  • reading: chapter 18 (esp. sections 1 and 2)
  • fair questions: Know definition of B-tree. Insert values into B-tree.

• Heaps and Heap Sort
  • reading: chapter 6
  • fair questions: Use or modify InsertHeap and Heapify algorithms. Understand and illustrate Buildheap and Heapsort algorithms. Generic heap questions.

• Binomial Heaps
  • reading: chapter 19
  • fair questions: Know structure and performance of binomial heaps. Perform merge. Insert and delete values.

• QuickSort
  • reading: chapter 7
  • fair questions: Illustrate quicksort on a sample input. Modify quicksort or partition to perform some task.

• Lower Bounds
  • reading: chapter 8
  • fair questions: Know the sorting lower bound and its consequences.

• Order Statistics
  • reading: chapter 9
  • fair questions: Know that selection can be done in linear time. Know how randomized-selection works (using partition).