Midterm Topics

date: Monday, February 19

time: 2:00-2:50

place 123 McKenzie

format: Open text and notes.

review session Thursday, February 15, 10:00-11:30, room 260 DES

Previous midterms:

• Winter 2005 (Word) (Partial sample solution: pdf)
• Winter 2006 (pdf) (Partial 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.