#
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.