cmsc210

Review for Final Exam

Dec. 2000

PLEASE NOTE: The format of this page is less than desirable. After creating the page with Word and getting all the special characters and subscripts and superscripts right, I was not able to save it as an html document. THEREFORE I have spent the last 3 hours inserting as many html control characters as I know to get it as readable as it is. (sub) means subscript and ^ means exponent. I give up on the graph for nos.27-30. Just draw a kite: 4 vertices forming a rhombus(diamond) and a tail with the fifth vertex at the end. Best I can do. Good luck. e-mail me with any questions.

R = {(8,u),(6,t),(4,t),(4,s),(2,u)} S = {(1,6),(1,2),(2,4),(3,8),(3,6),(3,4)}

a. {8,6,4,2} b. {u,t,s} c. the integers d. the letters of the alphbet e. it does not have a domain

2. What is the range of R?

a. {8,6,4,2} b. {u,t,s} c. the integers d. the letters of the alpahbet e. it does not have a range

3. Is R a function? Why or why not?

a. yes, because it is a set of ordered pairs.

b. yes, because it has a domain element that is used more than once.

c. no, because it has a range element that is used more than once.

d. no, because it has a domain element that is used more than once.

e. it is not possible to tell without a rule or description.

4. List the elements in R^-1 (the inverse of R).

a. {2,u),(4,s,),(4,t),(6,t),(8,u)}

b. {(8,u),(6,t),(4,t),(4,s),(2,u)}

c. {(u,8),(t,6),(t,4),(s,4),(u,2)}

d. {u,t,t,s,u}

e. it does not have an inverse.

5. Which of the following is the composition of relations S and R, denoted R o S ?

a. {(1,u),(1,t),(2,t),(3,s),(3,u)}

b. {(2,u)}

c. {(1,8),(1,6),(2,4),(3,4),(3,2)}

d. {(1,t),(1,u),(2,t),(2,s),(3,u),(3,t),(3,s)}

e. It is impossible to form a composite relation from these two relations.

6. T =

{(1,1),(1,3),(1,5),(3,1,),(3,3),(3,5),(5,1),(5,3),(5,5),(2,2),(2,6), (6,2),(6,6),(4,4)}

Which of the following is false?

a. T is symmetric.

b. T is reflexive.

c. T is transitive.

d. T is a partial order

e. T is an equivalence relation.

7. U = {(1,1),(1,4),(4,1,),(3,3),(2,2),(4,4),(4,2),(2,4),(2,1),(1,2)} .

U is an equivalence relation on X = {1,2,3,4}.

What is the set of equivalence classes of X given by relation U?

a. { {1,2}, {1,4}, {2,4} }

b. { {1}, {2}, {4} }

c. { {1,2,4}, {3} }

d. { {4},{1,2,3} }

e. Any partition of X.

8. Which of the following numerals does not have the same value as the others?

a. 1007(8) b. 1000000111(2) c.207(16) d. 2567(10) e. all are equal

9. Find the sum of these hexadecimal numerals: 42EA +84F

10. The worst case time for an algorithm is defined as

a. the minimum time needed to execute the algorithm for all inputs of size n.

b. the maximum time needed to execute the algorithm for all inputs of size n.

c. the average time needed to execute the algorithm for all inputs of size n.

d. the process of deriving estimates for the time and space needed to execute the algorithm.

e. the constants and coefficients in the expression.

11. The best case time for an algorithm is defined as

a. the minimum time needed to execute the algorithm for all inputs of size n.

b. the maximum time needed to execute the algorithm for all inputs of size n.

c. the average time needed to execute the algorithm for all inputs of size n.

d. the process of deriving estimates for the time and space needed to execute the algorithm.

e. the constants and coefficients in the expression.

12. If an algorithm requires t(n) units of time (without regard to whether that is the best, worst, or average case time), and t(n) = Omega(g(n)), which of the following is NOT true?

a. t(n) is of order at least g(n)

b. |t(n)| >= C|g(n)| for some constant C and for all but some finite number of n's

c. Omega(n) = Theta(n)

d. t is bounded below by g

e. g grows at most as fast as t

13. If an algorithm requires t(n) units of time (without regard to whether that is the best, worst, or average case time), and t(n) = O(g(n)), which of the following is NOT true?

a. t(n) is of order at most g(n)

b. |t(n)| < C|g(n)| for some constant C and all but some finite number of n's

c. O(n) = Theta(n)

d. t is bounded above by g

e. g grows at least as fast as t

14. Given 5 algorithms: a,b,c,d,e and their theta notation:

a(n)= Theta(n2), b(n)= Theta(1), c(n)= Theta(log2n), d(n)= Theta(n), e(n)=Theta(2n) .

a. Which algorithm is the most efficient?

b. Which algorithm is the least efficient?

c. Which algorithm could be a linear search of n items?

d. Which could be a binary search of n ordered items?

e. Which could be a hash function?

15. What is the order of complexity for the following algorithm?

i = n;

while (i > 1)

{ x++;

i = |_ i/2_| }

a.Theta(n^2) b.Theta(1) c.Theta(log n) d. Theta(n) e.Theta(2^n)

16. What is the order of complexity for the following algorithm?

for (i = 1; i <2n; i++)

for (j = 1; j x++;

a.Theta(n^2) b.Theta(1) c.Theta(log n) d.Theta(n) e.Theta(2^n)

17. What does this algorithm return for n = 5. Show trace.

int whatsitdo(int n)

{If (n = 1 or n = 2)

return 1;

else return whasitdo(n-1) + (n-2)

}

a. 7 b. 3 c. 5 d. 1 e. nothing

18. What does this algorithm return for n = 5. Show trace.

int whatsitdo(int n)

{If (n = 1 or n = 2)

return 1;

else return whasitdo(n-1) + whasitdo(n-2)

}

a. 7 b. 3 c. 5 d. 1 e. nothing

19. S = {s(sub)n} where s(sub)1 = 1 and s(sub)n = s(sub)(n-1) + 3

a. Find s(sub)5

b. Find a closed form for s(sub)n

c. Let c(sub)n = summation of s(sub)i as i=1 to n. Find c(sub)5

20. S = {s(sub)n} where s(sub)1 = 1 and s(sub)n = s(sub)(n-1) + n

a. Find s(sub)5

b. Find a closed form for s(sub)n

c. Let c(sub)n = summation of s(sub)i as i=1 to n. Find c(sub)5

21. Let f be a function from a finite set X to a finite set Y where |X| > |Y|.

Can the function be one-to-one? Prove your answer.

22. Let f be a function from a finite set X to a finite set Y where |X| = n, |Y| = m and n>m.

At least how many domain values will have the same range values?

X = {0,1}.

23. How many elements are in the power set of X, denoted P(X)?

a. 0 b. 2 c. 4 d. 8 e. F

24. List the elements in power set of X, denoted P(X).

25. How many 8 bit strings can be made over X?

a. 4 b. 16 c. 32 d. 64 e. 256

26. How many 8 bit strings can be made over X that begin and end with the same value?

Do not list them. Show your reasoning.

b._________c.

Consider this graph /\ \

a./ \ \

\__________\

e. d.

27. Is this graph connected? Prove your answer.

28. Is this a complete graph? Prove your answer.

29. Is this graph bipartite? If so, show exactly how. If not, explain why.

30. Does this graph have a cycle that begins and ends at vertex b? If so show it. If not, explain why.

31. Prove: Any positive integer m > 2 is prime if and only if no integer between 2 and sqrt(m) divides m.

32. C(sub)X is the characteristic function of set X in U, the universe.

Prove: C(sub)(XunionY)(x) = C(sub)X(x) + C(sub)Y(x) -C(sub)X(x)*C(sub)Y(x) for any element x in U.

33. Prove : If X is a subset of Y then C(sub)X(x) <= C(sub)Y(x) for any element x in U.

34. Let f be the function from X = {0,1,2,3,4} to X defined by: f(x) = 4x mod 6

Write f as a set of ordered pairs. Is f one-to-one or onto?

Explain why or why not.

35. g is a function from X to Y and f is a function from Y to Z. Is the following statement true or false?

If f is one-to-one, then f o g is one-to-one. Prove your answer.

36. Prove by mathematical induction:

7^n - 1 is divisible by 6, for n = 1,2,...

37. Prove sqrt(3) is an irrational number using an indirect proof.

P(x,y) is the propositional function "x loves y". The domain of discourse is the set of all living people. Consider the proposition:

Someone loves everybody.

38. Write the proposition symbolically.

39. Write the negation of the proposition in words without using the phrases "it is false that" and "it is not true that".

40. Is a conditional proposition equivalent to its contrapositive?

Prove your answer by a truth table.

41. DeMorgan's Law gives us an equivalent form for the negation of a conjunction. State it symbolically.

42. Y is a leap year iff Y is divisible by 4 and (Y is not divisible by 100 or Y is divisible by 400).

Write the parenthesized phrase as an equivalent conditional.

Solutions:

1. a 2. b 3. d 4. c. 5. d. 6. d 7. c 8. d 9. 4B39 10. b 11. a 12. c 13. c

14. a. b(n) b. e(n) c. d(n) d. c(n) e. b(n)

15. c 16. a 17. a 18. c

19. a. 13 b. 3n-2 c. 35

20. a. 15 b. (1+n)n c. 35

------

21. no. Pigeon Hole principle state there must be at least 2 range values

f(x1 ) = f(x2 ) where x1 does not equal x2

22. ceiling function of n/m

23. c 24. { {}, {0},{1},{0,1} } 25. 256

26. 1 _ _ _ _ _ _ 1

or 0 _ _ _ _ _ _ 0 2^6 + 2^6 = 128

27. yes (must show path exists between each pair of vertices)

28. no (no edge between a & e - or between b & d)

29. yes { {a,c,e} {b,d} }

30. yes (bcdeb or bedcb)

31,32,33, 34,35,36,37 see your notes

38. there exists x for all y, P(x,y)

39. Everyone does not love someone.

40. yes

41. ~(p /\ q) = ~p \/ ~q

42. if Y is divisible by 100 then y is divisible by 400