Midterm Topics

date: Monday, February 15

time: 10:00-10:50

place 105 Esslinger

format: Open text and notes.

review session Fri, Feb 12, 11-12 in room 200 DES and 2-3 in room 160 DES (note: check room 326 DES first, we will move to the larger rooms if needed)

Previous midterms:

• Winter 2009 (pdf) (Sample solution: pdf)
• Winter 2008 (pdf) (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: 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 and 2-4 trees
  • reading: a little in chapters 13 and 18
  • fair questions: insertion, know properties.