Final Exam Topics
CIS313, Winter 2007
date: Thursday, March 22
time: 3:15pm - 5:15pm
format: Open text and notes.
location: 301 Condon
review session: Wednesday, March 21, 11:00am-1:00pm, room 200 DES
previous finals:
TOPICS:
- 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).