CS 173: Skills list for Examlet 7

• Proof by Contradiction
  • (Recap from the past:) Give the negation of a statement, simplifying it so that all negations are on individual propositions/predicates.
  • Write a proof by contradiction.
• 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.
• Countability
  • 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.
  • Know these examples of countable sets, identify examples similar to these as countable.
    • 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 (each item finite, but with no restriction on length).
    • subsets of countable sets
    • a finite product of countable sets (E.g. if A is countable then so is the set of 5-tuples of elements of A.)
    • a countable union of countable sets
  • Know these examples of uncountable sets, identify examples similar to these as uncountable
    • the reals, an interval of the reals (e.g. [0,1])
    • the power set of the integers (or of any other countably-infinite set)
    • products containing an uncountable set (e.g. pairs of reals, complex numbers)
    • a set that contains an uncountable subset (e.g. the reals with other stuff added)
    • the set of infinite-length sequences of bits
    • the set of all functions from an infinite set (e.g. the integers) to a set with at least two elements
  • Other uncountability facts
    • Know that, for any set A, the power set of A has larger cardinality than A.
    • Know that there are functions that don't have finite formulas, and functions that can't be computed by any program.
    • Know that it's impossible to build a program that determines whether an input program halts or runs forever (aka the Halting Problem).
    • (You won't need to reproduce the constructions (e.g. diagonalization) that were used to prove these results.)