CS 173, Spring 2009: Skills list for second midterm

The second midterm will cover the material presented in lectures 1-27. It will focus on the material since lecture 14 (the last lecture covered in depth on the first midterm). Since you have not yet had time to do homework problems on the material from lectures 25-27, only more basic aspects of this material will be tested. The corresponding sections of Rosen are listed on the Lectures web page.

• Everything on the skills lists for the first quiz and the first midterm.
• Everything on the skills list for the second quiz. Since the second quiz was very recent and it was too short to properly test some of these skills, expect the exam to emphasize them. New and especially important skills include:
  • Write an inductive proof.
  • Given functions f and g, prove that f is O(g), Ω(g), and/or θ(g).
  • Given functions f and g, prove that f is not O(g), Ω(g), and/or θ(g).
  • Given a recursive definition of a set, describe precisely what elements the set contains.
• Algorithms
  • Know how the following algorithms work. It would be hard to reproduce the full code from scratch. Expect to fill in key tidbits of code, or hand-simulate the algorithm.
    • linear and binary search
    • bubble, insertion, merge sort
    • Towers of Hanoi solver
  • Know the big-O running times of the above algorithms.
  • Given a simple function in pseudo-code, analyze how long it takes using big-O notation. (We only plan to ask about examples very similar to those presented in lecture.)
• Recurrences and unrolling
  • Know that a recursive definition of a function (recurrence relation) requires an inductive step and also a base case.
  • Given a recursively defined function, find its closed form by "unrolling".
  • Given a recursively defined function, find its closed form using a recursion tree. Questions of this form would involve recurrences very similar to those found in the merge sort and the Towers of Hanoi examples.
  • Know the closed forms for an arithmetic series and a geometric series (see lecture 22).
• Trees
  • Define a tree
  • Define and use tree terminology: root, leaf, internal vertex, parent, child, sibling, ancestor, level of a vertex, height of tree
  • Define: binary tree, full binary tree, balanced binary tree
  • Know key facts: a tree has one more vertex than edges, a full binary tree with n internal vertices has n+1 leaves (and thus 2n+1 vertices total),
  • Know key facts about binary trees of height h: ≤ 2^h leaves, &le 2^h+1 - 1 vertices, ≥ h+1 vertices
  • Inductive proofs involving trees will not be covered on this exam.