Midterm score distribution

Midterm Study Guide

Midterm Exam, Wednesday, July 22, 2009

• Exam policies
  • Closed book, closed notes.
  • The exam begins promptly at 10:50 and ends at 11:50.
• Topics covered
  • All material from lecture 1 up to and including through Splay trees is fair game.
  • This material corresponds to: Chapters: 1, 2, 3, 4 (not section 4.7 on B-trees), and 6.
  • Here is a (fairly complete, but not exhaustive) 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 (just the idea), 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
    • Leftist 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.
    • Splay trees - Zig, zig-zig, and zig-zag 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, leftist heaps, binomial queues, binary search trees, AVL trees, and splay 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 (Some have recurrence relation problems; I won't expect you to do this)
  • Winter 2006
  • Autumn 2007
  • Winter 2007
  • Spring 2007