CSC 653: Advanced Theory of Computing

A printable PDF is available.

Assignment 1: Due Tuesday, September 2

This assignment is a "warm-up exercise" with two purposes: one is to get you thinking mathematically again (if you're rusty!), and the other is to give me some information on your mathematics capabilities. The assignment grade will count into your final grade, but it will only count half as much as assignments later in the semester.

  1. Textbook, page 25, Exercise 0.2
  2. Textbook, page 26, Exercise 0.4
  3. Textbook, page 26, Exercise 0.5
  4. Textbook, page 26, Exercise 0.8
  5. Textbook, page 27, Problem 0.11
  6. Use induction to prove that for any n >= 1, if you have n boolean variables x1,x2,...,xn, then x1 XOR x2 XOR ··· XOR xn=1 if and only if an odd number of xi variables are 1. (Note that XOR is the exclusive-or operation, and it is an associative operation).
  7. Use proof by contradiction to prove the Pigeon-hole Principle: Given n pigeons in m pigeon holes, there must be at least one hole containing at least ceiling(n/m) pigeons.