CS 173, Spring 2010
Skills list for first quiz
The first quiz will cover the material presented in lectures 1-8.
Since you have not yet had time to do homework problems on the
material from lectures 7-8, only more basic aspects of this material
will be tested. The corresponding sections of Rosen are listed on the
Lectures web page.
Specific skills you should know include:
- Administrative issues
- Know the day and time that your assigned discussion section
meets.
- Numbers and sets
- Know what sets these symbols represent: R, N, Z, Z+,
Q, C.
- Notation for set membership, e.g. x ∈ Z
- Know that 0 belongs to N but not Z+.
(There's two conventions about what's in N. This is the one we
are using this term.)
- Remember key equations for manipulating logs and
exponentials
(see notes for lecture 2).
- Know the definitions of the floor and ceiling functions,
i.e. ⌈ x ⌉ and ⌊ x ⌋
- Summations
- Know how to read summation notation, i.e. convert between it
and a list of terms with ellipsis (...). Same for product notation.
- Extract the first or last term in a sum or product.
- Rewrite a sum or product so that its index variable starts
at a different number.
- Know the closed forms for two special summations: (a) sum of all
integers from 1 to n and (b) the sum of
(1/2)i from 0 to n.
- Propositional and predicate logic
- Know the truth tables for basic logical operators,
especially implies. Know that, unless there is specific indication
otherwise, "or" means inclusive or.
- Know the meaning of the universal and existential
quantifier,
shorthand notation, and basic terminology such as "scope" of a
quantifier.
- Translate between English and logical shorthand. But we
realize that
it's hard to pin down the exact meaning of some English sentences.
- Be able to simplify the negation
of a complex statement by moving
the not's from the outside of the statement onto its
individual propositions. This requires knowing certain
key logical equivalences:
double negation, DeMorgan's laws, and the rules
for negating if/then statements and quantifiers.
-
Know the distributive, commutative, and associative laws and
that "p implies q" is equivalent to "(not p) or q".
- Other logical equivalences (e.g. the ones in the tables
on Rosen pp. 24-25) you do not have to know from memory.
If we give something that looks like one of these identities,
you should be able to figure out whether it's correct or not and
explain why using a truth table or counter-example.
- Identify statements which are neither true not false,
because
they contain variables not bound by a quantifier.
- Decide whether a complex statement is true, given
information about
the truth of the basic statements it's made out of.
- Given a statement, give its negative, converse, and
contrapositive.
Know that the contrapositive is equivalent to the original statement,
but
the converse is not.
- Know what it means for a statement to be "vacuously true."
- Be able to identify the hypothesis and the conclusion of an if/then statement.
- Number Theory
- Quote back definitions, decide if simple statements
involving them are true, understand the corresponding shorthand
notation:
- a divides b, b is a multiple of a,
- x is odd, x is even
- x is prime, x is composite
- x is a perfect square
- x is a rational number
- x and y are relatively prime
- Special cases for divides:
zero is even, zero divides itself
but not any other integer, and every integer divides zero.
- Special cases for prime: 0 and 1 are not prime (primes must
be greater than or equal to 2).
- Know the definitions of gcd(a,b) and lcm(a,b) and
be able to compute gcd(a,b) and lcm(a,b) for specific (smallish) values
of a and b.
- Write any (small) positive integer as a product of primes.
- Know that sqrt(2) is not rational.
- Know that there are infinitely many primes.
- Be able to state the Fundamental Theorem of Arithmetic:
Any positive integer can be written as the product of
primes and each integer has only one prime factorization
(except for the order in which you write the factors).