CSC 2510
Name ______Test 2: Oct. 20, 2011
1. Mark the following statements true or false. If false, correct the statement so that it is true.
a. The set of Java programs is uncountable.
False, the set of Java programs is countable.
b. An equation that express the nth term an of a sequence in terms of one or more of the previous terms of the sequence for all integers n greater than a particular integer is called a recurrence relation.
True. (page 186)
c. The Cantor diagonalization argument is a proof technique used to show that the set of real numbers is uncountable.
True. (page 186).
d. In (identity matrix of order n): the n x n matrix that has all its entries equal to one..
False. (page 186.)
e. An uncomputable function is one for which no computer program in a programming language exists that finds its values.
True. (page 186)
f. A one-to-one function is also called a surjection.
False, it is called an injection. (page 186)
g. A pre-image lies in the domain while the image lies in the codomain..
True. (page 186)
h. A countable set is a set that either is finite or can be placed in a one-to-one correspondence with the set of positive integers.
True. (page 186)
i. A È B is the set containing those elements that are in both A and B.
False. (page 186)
j. A function from A to B is an assignment of exactly one element of B to each element of A.
True. (page 186)
2. Given the following sets:
A = {white, red, green, blue},
B = {a, b, c, d, e }, and
C = {1, 2, 3, 4, 5}
with the following relations, mark which category fits (if a term includes another, use the higher level term):
i. one-to-one,
ii. onto,
iii. a bijection,
iv. none of them.
a. f: A ® B (white, d), (red, b), (green, e), (red, b), (blue, a)
Þ one-to-one (red, b) is listed twice but only once counts in a set relationship) Ü
b. f: B ® C (a, 4), (b, 3), (c, 2), (d, 1), (e, 5)
Þ bijection Ü
c. f: A ® B (white, d), (red, b), (green, e), (red, c), (blue, a)
Þ none of them (red points to two items, therefore it is not a function) Ü
d. f: A ® C (white, d), (red, b), (green, e), (blue, a)
Þ one-to-one Ü
e. f: C ® A (4, white,), (1, red), (3, green), (2, blue)
Þ onto Ü
3. If f(x) =2x3 - 3 and g(x) = x3 + 1, what is:
a. f o g
Þ f(g(x)) = f(x3+1) = 2(x3 + 1)3 -3= 2x9 + 6x6 + 9x3 -1Ü
b. g o f
Þ g(f(x)) = g(2x3) = ((2x3-3)3 + 1) = 8x9 -36 x6 +54 x3-26 Ü
4. Which of the following are reversible, and if not, why not?
a. Z- ® Z+
Þ Yes, one-to-one from negative integers to positive integers and back Ü
b. f(x) = 2x3 - 1, where x is a real number.
Þ Yes, let y = f(x) = 2x3 - 1. Then y = 2x3 - 1 and x = ((y-1)/2)1/3Ü
c. Z ® R
Þ No, because integers are countable but reals are uncountable. Ü
d. f(x) = 2x3 - 1, where x is a real number.
Þ No, because the reverse is not necessarily an integer Ü
e. f(x) = 1/x, where x is an integer.
Þ yes Ü
5. Prove that 21/2 (the square root of 2) is irrational.
Answer: Page 86 (example 10)
6. Let the universe be the sets A={white, green, blue, yellow}, B={blue, yellow, red} and C={pink, purple}. Give the new set results from the following combinations:
a. Bc
Answer: {white, green, pink, purple}
b. B ∪ C
Answer: {Blue, yellow, red, pink, purple}
c. A ∆ B
Answer: {White, green, red}
d. C × B
Answer: {(pink, blue), (pink, yellow), (pink, red), (purple, blue),(purple, yellow),(purple red)}.
e. Ƥ (B ∪ C) (This is the power set)
Answer: {ø,{blue},{yellow},{red},{pink},{purple},{blue, yellow},{blue ,red},{ blue ,pink},{ blue ,purple},{ yellow ,blue},{ yellow ,red} ,{ yellow ,pink}, ,{ yellow ,purple}….} totally 32 elements.
6. Given matrices A = é 1 0 1 ù , B = é 0 1 -1 ù, and C = é 2 4 ù,
ê 0 -1 -1 ê ê 1 -1 0 ê ê 1 1 ê
ë -1 1 0 û ë -1 0 1 û ë 3 0 û
Perform the following operations or state why not:
a. A + B
é 1 1 0ù
ê 1 -2 -1 ê
ë -2 1 1 û
b. AT
é 1 0 -1ù
ê 0 -1 1 ê
ë 1 -1 0 û
c. AI (A * Identify matrix)
é 1 0 1ù
ê 0 -1 -1 ê
ë -1 1 0 û
d. AC
é 5 4 ù
ê -4 -1 ê
ë -1 -3 û
e. CA
Answer: cannot multiply a 3 *2 by a 3*3
7. Arrange the following in order of increasing complexity:
a. constant complexity
b. Exponential complexity
c. Factorial complexity
d. Linear complexity
e. Logarithmic complexity
f. n log n complexity
g. Polynomial complexity
Answer: a e d f g b c
8. Provide the solutions for the following expressions:
a. é3.5ù
Answer:4
b. ë-1.5û
Answer: -2
c. The 6th term of an = 1/n
Answer:1/6
d. The 4th term of an = an-1 + 3 , where a0 = 2
Answer: 11 or 14
e. The closed form for the expression åi = 1 to n i
Answer: n(n+1)/2