CS 173, Spring 2014: Skills list for first midterm

The first midterm will cover the material through chapter 8. 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:

• Administrative issues
  • Know the day and time that your assigned discussion section meets.
• 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.
  • Basic rules for manipulating exponents and logs
  • 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.)
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
• 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 notation and definition of n factorial (n!).
  • Know the notations [a,b] and (a,b) for closed and open intervals of the real line.
  • Know the definitions of the floor and ceiling functions, i.e. ⌈ x ⌉ and ⌊ x ⌋
• 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".
  • Given a new, fairly simple logical equivalence, 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.
• 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).
  • 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.
• 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.
  • 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,
    • disprove a universal claim by exhibiting a counterexample.
    • prove an existential claim by exhibiting specific values that make the claim true
  • 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.)
• 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.
  • Cardinality
    • Know the inclusion-exclusion formula relating the cardinality of sets A and B to that of their union and intersection.
    • Given the cardinality of two 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.
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • Know what it means for two elements in a relation to be comparable.
  • Define equivalence relation, partial order, strict partial order, linear order.
  • Prove that a relation is, or isn't, an equivalence relation, an partial order, a strict partial order, or 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.
• 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 the composition of two functions. Compute the composition of two specific functions.
  • Be able to identify whether a function is onto, one-to-one, and/or bijective.