Final Exam Topics

date: Wednesday, March 17

time: 10:15pm - 12:15pm

format: Open text and notes.

location: 105 Esslinger

review session: Tuesday, March 16, 3:00-5:00, room 200 DES

previous finals:

• Winter 2009
• Winter 2008

• 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).

• Recurrence Relations
  • reading: sections 4.3-5.
  • fair questions: solve simple recurrence relations

• 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: chapters 13, 18
  • 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.

• Fibonacci Heaps
  • reading: chapter 19
  • fair questions: Know structure and performance of fibonacci heaps. Perform merge. Insert and delete values. Decrease key.

• 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, esp section 8.1
  • 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).