CS 173, Spring 201: Skills list for final (aka thirteenth) examlet

• State Diagrams
  • Be able to 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.
  • Be able to 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.
• Counting states
  • Be able to calculate (or estimate for large cases) the number of states for an example system (e.g. a game).
  • Know that some examples involve an infinite number of states.
  • 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.
• Representing functions
  • Know that a function can be represented mathematically, or stored in a computer, as a list of input/output pairs.
  • Know that a more efficient way to store a function is to associate each input value with a location in a 1D array.
  • Know that the transition function might be stored as a 2D array (each array cell represents a pair of a state and an action). Or it could be stored more compactly as a 1D array of states, where each cell contains a list of actions and the corresponding output states.
• Cardinality
  • Define what it means for two sets to have the same cardinality: i.e. there is a bijection mapping one onto the other.
  • Show that two sets have the same cardinality by constructing a specific bijection between them.
  • Define when |A| <= |B|, i.e. there is a one-to-one function from A to B.
  • Know the definitions:
    • A countably infinite set is a set with the same cardinality as the integers (or the natural numbers).
    • A countable set is either countably infinite or finite.
    • Uncountable sets: infinite sets too large to be countable.
• Examples of countable sets
  • Know that the following sets are countably infinite: pairs of integers or natural numbers, rational numbers, the set of finite-length strings (with some specified finite character set), the set of all finite formulas or computer programs (with no restriction on length).
  • Know that subsets of countable sets are countable.
  • Know that a finite product of countable sets is countable. (E.g. if A is countable then so is the set of 5-tuples of elements of A.)
  • Know that a countable union of countable sets is countable.
  • Identify examples similar to these as countable.
• Examples of uncountable sets
  • Know that, for any set A, the power set of A has larger cardinality than A.
  • Know that the following sets are uncountable (not countable): the reals or an interval of the reals (e.g. [0,1]), the power set of the integers, the set of all functions from the integers to the integers.
  • Identify examples similar to these as uncountable.
  • Know that there are functions that don't have finite formulas, and functions that can't be computed by any program.
  • You won't need to reproduce the constructions (e.g. diagonalization) that were used to prove these results.