CS 173: Skills list for Examlet 5
- 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, or balanced. (The definitions for "full" and "complete" trees will be provided.)
- 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 approximately 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 ones and zeroes)
- 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.
- Big O
- Define what it means for a function f to be asymptotically smaller than g (f ≪ g), O(g) and/or θ(g). where g is another function.
- For specific functions f and g, identify whether f is asymptotically smaller than g (f ≪ g), O(g) and/or θ(g).
- Know the asymptotic relationships among key primitive functions: constant, log n, n, n log n, polynomials of higher orders, exponentials, factorial.
- Given functions f and g, prove that f is O(g) and/or θ(g).
- Algorithms
- Know the big-O running times of basic operations on linked lists and arrays. These include
reading/writing values, adding/removing elements, and dividing the list/array
at locations at/near the start, in the middle, and at the end.
- Be familiar with the overall structure and big-O running times of the following algorithms.
- merge two sorted lists
- binary search
- merge sort
- graph reachability (what's in x's connected component)