Midterm Topics
CIS313, Winter 2008
date: Monday, February 18
time: 10:00-10:50
place 307 Volcanology
format: Open text and notes.
review session tba
Previous midterms:
- Winter 2007 (pdf)
(Sample solution: pdf)
- Fall 2006 (pdf)
(Partial sample solution: pdf)
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).
- Recurrence Relations
- reading: section 4.3.
- 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 and 2-4 trees
- reading: chapter 13
- fair questions: insertion, know properties.