CS 173: Skills list for Third Written Test

The written test will have 3 questions, that require writing proofs, on topics related to number theory, the invariant method, and structural induction. The specific skills it will test are

• 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
    • when a and b are congruent modulo n
  • Special cases for divides: zero is even, zero divides itself but not any other integer, and every integer divides zero.
  • Prove simple number theory claims involving the divides relation.
  • Be able to state the "Division Algorithm" theorem.
  • Be able to compute quotient and remainder of a pair of numbers.
  • Be able to prove properties of quotients and remainders.
  • Know that congruence modulo n is an equivalence relation
  • Know that congruence modulo n is preserved by adding or multiplying equivalent numbers.
  • Be able to compute the value modulo n/remainder modulo n, or arithmetic expressions by using "remainder arithmetic", where one repeated simplifies sub-expressions by taking the remainder modulo n.
  • Be able to prove simple theorems about the congruence modulo n definition.
  • Know the definitions of gcd(a,b) and be able to compute gcd(a,b) for specific (smallish) values of a and b.
  • 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.
  • Know what it means for two numbers to be relatively prime, i.e., gcd(a,b) = 1.
  • Know Bezout's theorem that states the the gcd(a,b) can be expressed as a linear combination of a and b.
  • Be able to prove simple facts about gcd.
  • Be able to use Bezout's theorem to prove simple facts about numbers.
  • Know what Euler's Totient Function is: phi(n), is the number of positive integers < n that are relatively prime to n.
  • Know the value of Euler's Totient Function for primes and product of two primes. For p and q prime, phi(p) = p-1, and phi(pq) = (p-1)(q-1).
  • Know Euler's theorem. For any integer a that is relatively prime to n, a^{phi(n)} is congruent to 1 modulo n.
  • Be able to use Euler's theorem in simple proofs.
• Invariant Principle
  • Know what a state machine is.
  • Know what a preserved invariant is.
  • Know Floyd's Invariant Principle, and how it can be used to prove correctness of algorithms.
  • Be able to check if some predicate is a preserved invariant of a given state machine
  • Be able to identify a predicate that will be the preserved invariant of a state machine.
• Recursive structures and definitions
  • Understand how recursive structures are defined using a base case and a constructor case.
  • Understand how to read a recursive definition.
  • Know that a recursive definition matches the definition of the recursive structure, in its base cases and constructor cases.
  • Know the recursive definition of strings, and well matched brackets and functions defined on them, like length.
• Structural Induction
  • Know how to write structural induction proofs for properties on recursive structures.