CS 173: Skills list for "Examlet F"

• 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.
     
• Collections of sets
  • Write simple proofs involving collections of sets and/or functions whose input and/or output values are sets.
  • Interpret definitions for functions whose input and/or output values are sets (i.e. when the domain and/or co-domain is a power set).
  • Interpret set-builder definitions of sets containing other sets.
  • Given a specific set A, list the elements of its power set.
  • Define the power set (A) for a set A.
  • Manipulate sets containing other sets using standard set operations. (Be careful of getting the right number of brackets in examples involving the empty set and sets with only one element.)
• Partitions
  • Define a partition of a set A: be able to state the properties informally and also write them precisely in formal notation.
  • Determine whether a specific set P is a partition of some specific set A.
  • Know that the equivalence classes of an equivalence relation on A form a partition of A.
• Counting
  • Know the shorthand notation for binomial coefficients (number of combinations) and its definition in terms of factorials.
  • Know the formula for computing the number of combinations of k objects from n types, with repetition.
  • Know the Binomial Theorem and Pascal's Identity.
  • Be able to solve practical counting problems involving combinations, combinations with repetition, and applications of the Binomial Theorem.