Midterm Topics

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.