CS 173, Fall 2014: Skills list for ninth examlet

• Summations
  • Know the closed form for the sum of 2^k (for k from 0 to n).
• 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, (proper) ancestor, (proper) descendent, level of a vertex, 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 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).
• 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, terminals, 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 example of trees that are/aren't generated by G, determine whether a given tree could be generated by G.
• Tree induction
  • Prove a claim about labelled or unlabelled trees using induction.