Massachusetts Institute of Technology Handout 4 6.042J/18.062J: Mathematics for Computer Science September 7, 2000 Professors Nancy Lynch and Shlomi Dolev

Diagnostic Test

Due: Friday, September 8, 2000, at the beginning of tutorial. Instructions: Please answer these questions on your own, and without looking at any of the course material. Allow at most 30 minutes. This test will not affect your grade in any way. It is intended to help us compare what you know before and after taking the course.

1. Write your name:

2. (a) Find the derivative with respect to x of (x − 1) ln x.

(b) Find the indefinite integral of ln x.

3. What is the value modulo 5 of the product of 4,199,001 and 3,777,775?

4. For any set A, let P (A) be its power set, namely, the set of all its subsets; note that A ∈ P (A).

(a) List the elements in P ({1, 2}).

(b) List the elements in P ({∅, {∅}}).

(c) How many elements are in P ({1, 2, …, 8})?

5. Describe a simple counterexample to the claim that if A and B are finite sets, the size of A ∪ B is the same as the size of A plus the size of B.

6. Which of the following logical formulas are tautologies, i.e., they always hold:

(a) not[P or Q] ≡ not[P] and not[Q]

(b) [P implies Q] or [Q implies P]

(c) ∀x[P (x) or not[P (x)]]

(d) ∀x∃y[P (x) or not[P (y)]]

7. Write a simple arithmetic expression for ∑_{i=1}^{n} 2i.

8. Write a simple arithmetic expression for ∑_{i=0}^{n} x^{i}.

9. If you flip three fair coins, (a) What is the probability that all three will land on Heads?

(b) What is the probability that at least one will land on Heads?

(c) What is the average number of Heads you can expect to flip?

10. The Well-Ordering Principle is an axiom of Mathematics asserting that every nonempty set of nonnegative integers has a least member.

(a) Explain why the Well-Ordering Principle would not hold if the word “nonnegative” above were deleted.

(b) Explain why the Well-Ordering Principle would not hold if the word “integers” above were replaced by “rationals”.

(c) By this Principle, there must be a least nonnegative integer, m, that cannot be defined in fewer than fourteen words. But “The least nonnegative integer that cannot be defined in fewer than fourteen words,” is a thirteen word definition of m. Is there something wrong with the Well-Ordering Principle? Comment please.