CS 173: Skills list for Examlet 5
- 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
Qk, 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
2h, the number of nodes is between (h+1) and
(2h+1 - 1)
- Know that the height of a full complete
binary tree with n nodes (or n leaves)
is proportional to 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.