Midterm score distribution

Midterm Study Guide

Midterm Exam, Friday, February 6, 2008

• Exam policies
  • Closed book, closed notes.
  • The exam begins promptly at 2:30 and ends at 3:20.
• Topics covered
  • All material from lecture up through AVL trees is fair game.
  • This material corresponds to: Chapters: 1, 2, 3, 4 (not section 4.5 on Splay trees or 4.7 on B-trees), and 6.
  • Here is a (fairly complete) summary of topics we’ve covered in lecture:
    • Linked lists. Simple linked lists, doubly linked lists, circularly linked lists.
    • Stacks and Queues, array and list implementations.
    • Recursion. Designing algorithms recursively.  Inductive proof.
    • Asymptotic analysis, Big-O. Worst, amortized, average, best cases.  Upper and lower asymptotic bounds.  Analyzing loops, recurrences.
    • Trees – definitions
    • Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increaseKey, decreaseKey, buildHeap.
    • Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey
    • Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey.
    • Dictionary ADT
    • Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find, build.
    • AVL trees - Single and double rotations, insert, find, delete, build.
  • The focus will be on ideas/concepts about data structures and algorithms, *not* Java.
     
• Study suggestions
  • Do concrete problems from the book and re-work problems from lecture, section, and HW.
  • Practice all the operations on binary heaps, skew heaps, binomial queues, binary search trees, AVL trees.
  • Practice analysis of algorithms.  Learn and be able to reason about the complexities of operations on the data structures we’ve discussed in class.
  • Try practice midterms.
     
• Practice midterms
  • Winter 2006
  • Winter 2007
  • Spring 2007