CS 173: Skills list for third CBTF Test

The CBTF test will have 5 multiple choice questions on topics related to number theory and the invariant method. 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.
  • Know the definitions of gcd(a,b) and be able to compute gcd(a,b) for specific (smallish) values of a and b.
  • Be able to state the "Division Algorithm" theorem.
  • Be able to compute quotient and remainder of a pair of numbers.
  • 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.
• 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.