CS 173: Skills list for eleventh examlet
- NP
- Know that certain classes of sentences have exponentially many parse trees.
(And thus producing all parses of a sentence requires exponential time.)
- Know that the Towers of Hanoi puzzle has been proved to require exponential time.
- Know that NP is the set of problems for which we can quickly
(polynomial time) justify "yes" answers.
- Know that co-NP is the set of problems for which we can quickly
(polynomial time) justify "no" answers.
- Know that problems in NP can be solved in exponential time, but it's
not known whether they can be solved in polynomial time.
- Know what an NP-complete problem is: a problem in NP for which
a polynomial-time algorithm would imply that any problem in NP can be solved
in polynomial time.
- Know some examples of NP-complete problems: graph colorability,
circuit satisfiability (Circuit SAT), propositional logic satisfiability,
marker making, the travelling salesman problem.
- Know that you can decide in polynomial time whether a graph is 2-colorable (aka bipartite).
- 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.