CS 173: Skills list for Examlet 7
- Logic and proofs
- Recap from the past: give the negation of a statement or the contrapositive
(if/then statements only), simplifying it
so that all negations are on individual propositions/predicates.
- Write a proof by contradiction.
- Collections of sets
- 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 the power set P(A) for a set A.
- Given a specific set A, list the elements of its power set.
- Correctly interpret set-builder definitions of sets containing other sets.
- Correctly 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).
- Write simple proofs involving collections of sets and/or
functions whose input and/or output values are sets.
- 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.
- 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 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.
- 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 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 strings
- 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.