CS 173: Skills list for fifth examlet

The proof for this examlet will be long. Therefore, you should expect a correspondingly smaller amount of short-answer material.

• Recursive definition
  • Understand how to read a recursive definition, e.g. compute selected values or objects produced by that definition.
  • Know that a recursive definition, and an inductive proof, require a both a base case and an inductive step/formula.
  • Define the Fibonacci numbers.
  • Know the definition of the k-dimensional hypercube graph, its shorthand name Q_k, and how many vertices it contains.
• Unrolling
  • Given a recursively defined function, find its closed form by "unrolling". Test questions will involve either doing certain key steps or a very simple example, not an entire long messy unrolling.
• Induction
  • Write inductive proofs that need to use the truth of the claim for more than one immediately previous value, e.g. multiple previous values, a previous value several steps back.
  • Determine whether an inductive proof requires more than one base case and, if so, which ones.
  • Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.
  • For recursively defined sets of objects (e.g. graphs), use induction to prove that they have some specific property (e.g. number of edges) and/or write a recurrence for the values of some property of the objects (e.g. number of edges).
• Trees
  • Define a (full) binary tree recursively: it's either a single node, 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 node, parent, child, sibling, (proper) ancestor, (proper) descendent, level of a node, height of tree.
  • Define what it means for a tree to be binary, n-ary, full, full and complete, or balanced.
  • Know key facts: a tree has one more node than edges, a full m-ary tree with i internal nodes has mi+1 nodes total, a full binary tree with n internal nodes has n+1 leaves (and thus 2n+1 nodes total),
  • Know key facts about binary trees of height h: the number of leaves is between 1 and 2^h, the number of nodes is between (h+1) and (2^h+1 - 1)
  • Know that the height of a full complete binary tree with n nodes (or n leaves) is θ(log n).
• String notation and regular expressions
  • The empty string (ε)
  • Concatenation, *, and | operations
  • A^* is the set of all finite-length strings with characters from A.
  • Know what a "bit string" is (a string of one's and zero's)
• Grammar Trees
  • Correctly interpret the definition of a context-free grammar: variables, rules, start symbols, terminal symbols
  • Correctly interpret a grammar rule, e.g. what does ε or a vertical bar mean on the righthand side of a rule.
  • Given a grammar G, give examples of trees that are/aren't generated by G, determine whether a given tree could be generated by G.
  • Given a string s and a grammar G, briefly explain why s can/can't be generated by G.
  • Build a tree matching grammar G with a specific terminal string s. When multiple trees are possible, build more than one or describe the set of possible trees.
• Tree induction
  • Prove a claim about labelled or unlabelled trees using induction.
  • Use induction to prove a claim about other sorts of objects, where your induction variable is the size of the object and there may be more than one object of each size.
• Recursion Trees
  • 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 the textbook, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)
  • Find a big-O solution for a simple recursive definition, of the types that we've seen as examples of unrolling and recursion trees.