CS 173, Spring 2010: 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 26-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, which might involve "strong" hypothesis, multiple base cases, a recursively defined function, an inequality, or a non-formula relationship (e.g. divides). (Notice that inductive proofs involving trees will not be covered on this exam. )
  • 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, give a precise non-recursive description of 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.
  • Write a recurrence for the big-O running time of each of the above algorithms.
  • Know that Karatsuba's algorithm divides a size n multiplication problem into 3 (better than 4!) half-size sub-problems. And that its running time is O(n^{log ₂ 3}), which is about O(n^1.6) and thus better than the O(n²) you get by dividing a multiplication into 4 half-size sub-problems. You aren't expected to reproduce the details.
  • Given an unfamiliar but fairly 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 found in the lectures or homework.)
  • Given a recursive algorithm (familiar or unfamiliar) express its big-O running time as a recurrence relation.
• Recurrences and unrolling
  • Know the closed forms for three key summations: sum of the first n integers, sum of 2^k (for k from 1 to n), and sum of (1/2)^k (for k from 1 to n)
  • Given a recursively defined function, find its closed form by "unrolling".
  • Given a recursively defined function, find its closed form by drawing a recursion tree and adding up the work at all levels. (Examples would look like those presented in lecture, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)
• Trees
  • Define a (full) binary tree recursively: it's either a single vertex, or a root with two subtrees children, or (for non-full trees) a root with one subtree child.
  • Define and use tree terminology: root, leaf, internal vertex, parent, child, sibling, ancestor, descendent, level of a vertex, height of tree
  • Define what it means for a tree to be binary, n-ary, full, or balanced.
  • Know key facts: a tree has one more vertex than edges, a full m-ary tree with i internal nodes has mi+1 nodes total, 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: the number of leaves is between 1 and ≤ 2^h, the number of vertices is between h+1 and &le 2^h+1 - 1
  • Know that the height of a full complete binary tree with n vertices (or n leaves) is θ(log n).