CS 173: Skills list for Fifth Written Test

The fifth written test will have 3 questions that may require writing proofs, on topics related to trees, asymptotic analysis, and recurrences. The specific skills it will test are

• Trees
  • Know that free (unrooted) tree is an undirected connected, acyclic graph.
  • Know key properties of unrooted trees: existence of unique paths between vertices, and that number of edges in an n vertex tree is n-1.
  • Know what a rooted tree is.
  • Define and use tree terminology: root, leaf, internal node, parent, child, sibling, (proper) ancestor, (proper) descendent, level of a node, height of tree, level of a vertex.
  • Define what it means for a tree to be binary, n-ary, full, full and complete, or balanced.
  • Define rooted trees recursively: starting from root and some rooted trees with disjoint vertices, it is formed by making the rooted trees children of the root.
  • Know key facts: 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 m-ary tree with n nodes (or n leaves) is θ(log_m n).
  • Be able to prove a claim about labeled and unlabeled trees using induction.
• Algorithm Analysis
  • Know that the running time of an algorithm is the number of steps taken by the algorithm. Typically, we assume that each line in the pseudo code is one step.
  • Given a simple iterative algorithm, know how to compute an upper bound on its running time as a function of the length of the input.
  • Know how to get Big O/Theta analysis of the running time of simple algorithms.
• Big O
  • Define what it means for a function f to be o(g) (little o of g), O(g) (big O of g), θ(g), \Omega(g) where g is another function.
  • For specific functions f and g, identify whether f is o(g), O(g), θ(g), \Omega(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), θ(g), o(g), \Omega(g), by identifying c and k as in the definitions.
• Summing Series
  • Know what arithmetic and geometric progressions are.
  • Know how to compute the sum of an arithmetic progression, and finite and infinite geometric progressions.
  • Be able to do simple manipulations of a given sum to compute its closed form.
• Recurrences
  • Know what recurrences are.
  • Know how to use the "plug and chug method" (simple unrolling of a recurrence) to find closed form expressions for the nth term of a recurrences.
  • Know how to solve a general homogeneous linear recurrence.