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 x₁,x₂,...,x_n, then x₁ XOR x₂ XOR ··· XOR x_n=1 if and only if an odd number of x_i 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.