CS 173, Spring 2012: Skills list for first midterm

The first midterm will cover the material through lecture 10. Since you have not yet had time to do homework problems on functions, only more basic aspects of this material will be tested.

When you take the exam, you cannot use cheat sheets, calculators, other electronic devices, etc. We try to write the questions so that such assistance won't be required. Also remember to bring a photo ID to show the proctors.

Specific skills you should know include:

• Math prerequisites
  • Algebraic manipulations with
    • equations
    • inequalities
    • fractions
    • absolute value
    • squares and square roots
  • 2nd order polynomials: solving, factoring, finding roots. Easy cases only: don't worry if you don't remember the quadratic formula.
  • Exponents and logs: see lecture 2 and Rosen appendix A-2.
  • Defining and composing numerical functions. E.g. if f(x) = x-6 and g(x) = 7x, then g(f(x)) = 7(x-6).
  • Prime numbers, factoring a number into primes. (Where we only consider numbers >= 2.)
• 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.)
  • 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)ⁱ 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.
  • Be able to identify the hypothesis and the conclusion of an if/then statement.
  • Understand the difference in meaning between the statement ∀ x, ∃ y P(x,y) and the statement ∃ y, ∀ x, P(x,y).
  • Negate a statement containing multiple quantifiers.
• 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).
• Logic and Proof techniques.
  • Write a simple direct proof, using familiar concepts, with good mathematical style. Make sure your statements are in logical order, starting with the given information and ending with what you needed to show.
  • Write the negation or contrapositive of a statement, moving all negations onto individual propositions.
  • Write a proof by cases
  • Convert a claim to its contrapositive and prove that using direct proof.
  • Given a claim about the non-existence of something, outline a proof by contradition. Fill in details of the proof if it involves familiar concepts.
  • Know the following standard ways to approach parts of a proof:
    • prove a universal claim by choosing a representative object of the appropriate type
    • prove an if/then statement by assuming whatever's in the hypothesis and proving the conclusion,
    • prove an existential claim by exhibiting specific values that make the claim true
  • Disprove a universal claim by exhibiting a counterexample.
  • Know what it means for a statement to be "vacuously true."
• Pseudocode
  • Be able to read and write simple bits of pseudocode. (We aren't picky about the precise syntax.)
• Number Theory
  • Define what it means for x and y to be congruent mod k
  • Be able to state the "Division Algorithm" theorem.
  • Compute the gcd of two larger numbers using the Euclidean algorithm, i.e. trace the execution of the algorithm. Be able to reproduce its pseudocode.
  • Prove simple number theory claims using direct proof and the definitions of the terms involved. For example, if a divides b and a divides c, then a divides b+c.
  • For congruence mod k, know which integers are in the equivalence class of x. Know the shorthand notation [x].
  • In Z_k, do simple arithmetic: addition, multiplication, taking small integer powers, deciding if two elements are equal.
• Set Theory
  • Notation
    • set builder notation for defining sets
    • set membership and inclusion notation: ⊆, ∈
    • special symbol for the empty set: ∅
    • an ordered pair, triple, n-tuple
  • Define formally, be familiar with standard notation, compute the values for concrete input sets
    • A is a subset of B
    • The cartesian product of two sets A and B, of three or more sets
    • The cardinality of a set
    • The complement of a set (given some specified universe).
    • The union, intersection, and difference of two sets.
  • Know the meaning of the term disjoint.
  • Know what happens if one of the inputs to these operations is the empty set.
  • Given a simple set relationship, recognize whether it's correct or not. If not, show a counter-example.
  • Know DeMorgan's laws and the distributive laws for sets.
  • Prove a set inclusion by choosing an element from the smaller set and showing it's in the larger set.
  • Prove a set equality by proving inclusion in both directions.
• Set theory and counting
  • Know the inclusion-exclusion formula relating the cardinality of sets A and B to that of their union and intersection.
  • Given the cardinality sets A and B, compute the cardinality of their cartesian product.
  • Apply these two formulas to real-world counting problems.
• Relations
  • Define a relation on a set A.
  • Represent a relation as a set of pairs or a directed graph, convert between the two representations.
  • Define reflexive, irreflexive, symmetric, anti-symmetric, transitive. For any of these problems, determine if a specific relation has the property.
  • Define equivalence relation, partial order, strict partial order, linear order.
  • For an equivalence relation R, define the equivalence class [x] of an element x. For a specific element x, determine what's in [x].
  • List or describe all of R's equivalence classes.
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • Prove that a relation is, or isn't, an equivalence relation, an partial order, a strict partial order, or linear order.
• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, and image.
  • Identify when a formula or diagram defines something that is not a function (e.g. two output values for a single input).
  • Define when a function is one-to-one, onto, bijective, incresing, strictly increasing.
  • Define the identity function on a set A and know its shorthand name (id_A)
  • Define the composition of two functions.
  • Identify whether a concrete example has one of these properties.
  • Know that a strictly increasing function is always one-to-one.
• Counting and functions
  • Be able to state the Pigeonhole Principle and apply it to simple concrete examples.
  • Know the notation and definition of n factorial (n!).
  • Know the formulas for counting permutations, and permutations with indistinguishable objects.
  • Apply these formulas to solve simple concrete word problems.