CS 173: Skills list for "Examlet F"

• 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.)
  • 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 formulas for counting permutations, and permutations with indistinguishable objects.
  • Apply permutation formulas to count the numbers of possible functions or one-to-one functions between sets of specific sizes.
  • Know how a function being onto or one-to-one constrains the size of its domain relative to its co-domain. (Finite sets only.)
  • Apply these formulas to solve simple concrete word problems.
  • Apply the Pigeonhole Principle to simple concrete examples.
  • Apply the Pigeonhole Principle in writing proofs (straightforward examples only).
  • 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.
• State Diagrams
  • Read basic notation for state diagrams, e.g. state diagrams are directed graphs, states are the vertices, actions are labelled on the edges, how are start and end states marked, loops and multi-edges are possible.
  • Know what is/isn't allowed in a deterministic state diagram.
  • Trace walks in a state diagram: walks must follow the edge directions, therefore cycles and paths also must follow the edge directions, the full description of a walk contains the state sequence and the action sequence.
  • Know the basic description of the transition function δ, i.e. each input is a pair of a state plus an action, each output is a set of possible next states. Remember that this means that the co-domain is the powerset of the set of states.
  • Have a general familiarity with some common examples of state diagrams: states of a game or puzzle, memory states of a computer program, phone lattice for a set of words.
  • Construct state diagrams that meet a (simple) specification, e.g. a phone lattice that represents a set of words.
  • Counting states
    • Calculate (or estimate for large cases) the number of states for an example system (e.g. a game).
    • Know that algorithms can be made more efficient by not creating multiple states with identical properties. Or, said another way, organizing your work so that you don't repeatedly re-solve a sub-problem.