CS 173: Skills list for "Examlet E"

• Recursion Trees
  • Given a recursively defined function, find its closed form by drawing a recursion tree and adding up the work at all levels. (Examples would look like those presented in the textbook, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)
  • Find a big-O solution for a simple recursive definition, of the types that we've seen as examples of unrolling and recursion trees.
• Tree induction
  • Prove a claim about labelled or unlabelled trees using induction.
• 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
  • 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)
  • Given an unfamiliar but fairly simple function in pseudo-code, analyze how long it takes using big-O notation. You should be able to analyze nested for loops, recursive functions, and simple examples of while loops.
    • For an algorithm involving loops (perhaps nested), express its running time using summations.
    • Given a recursive algorithm (familiar or unfamiliar) express its running time as a recursive definition.