DOC PREVIEW
UCF COT 3100 - COT 3100H Final Exam

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

COT 3100H Spring 2003Introduction toDiscrete StructuresFinal ExamApril 24, 2003Name : __________________1) (10 pts) Find a closed form solution for the following recurrence relation withoutusing generating functions:t(0) = 7, t(1) = 18, t(n) = 5t(n-1) – 6t(n-2), for all integers n>1.2) (10 pts) Use the method of generating functions to solve the following recurrencerelation:s(0) = 3, s(1) = 3, s(n) = 5s(n-1) + 14s(n-2), for all integers n>1.3) (10 pts) Let S be a set of five positive integers the maximum of which is at most 10.Prove that there exist two non-empty disjoint subsets of S that have the same sum ofelements. (Note: Two subsets can be disjoint even if the values of the elements in the twosets are equal. For example, two disjoint subsets of {1, 2, 3, 3, 4} are {1, 3} and {3, 4}since there are two copies of three in the set. We can think of the original set being {a, b,c, d, e} where a=1, b=2, c=3, d=3, e=4 and the two subsets as being {a,c} and {d, e}.)4) (8 pts) Let x be a positive integer greater than 1. Prove using induction on n that xn –1is divisible x – 1 for all positive integers n.5) (12 pts) Choose one of the two following questions:a) Prove )1)1((211ninifor all positive integers n.(Note: You may use either induction or another proof technique shown in class. Althoughthe induction works, a portion of it is tricky.) b) Prove 21 | (4n+1 + 52n-1) for all positive integers n, using induction.6) (8 pts) Use the laws of logic to show that the two following expressions are logicallyequivalent:a) p  q b) ((p  r)  (p  r))  (q  (q  r))7) (4 pts) a) Find gcd(705, 450) using Euclid's Algorithm. (6 pts) b) Find integers x and y such that 705x + 450y = gcd(705,450).8) (10 pts) For any arbitrary sets A, B and C from the same universe, prove that if andonly if A – (B – C)  A – B – C, then A  C = .9) (16 pts) A committee of 10 senators is to be chosen from the 100 U.S. senators. 45 ofthese senators are senior members while 60 of them are men. Of the women senators, 30of them are not senior members. Given the following restrictions, how many possiblecommittees can be picked? (Note: All four parts are independent of each other.)a) The committee is required to have at least two senior members. b) The committee must have exactly five members that are either men or senior members.c) The committee is entirely comprised of men that are not senior members and womenthat are senior members.d) The committee contains no men and contains no non-senior members.10) (10 pts) A gardener plants three maple trees, four oak trees and five birch trees in arow. He plants them in random order, each arrangement being equally likely. Find theprobability that no two birch trees are next to one another.11) (12 pts) In each of the following examples, R, S and T are all relations over the set ofintegers(Z). Find a counter-example to disprove each of the following claims:a) If RR is symmetric, then R is symmetric.b) If R  RR is transitive, then R is transitive.c) If RS  TS, then R  T.d) R = {(x,y) | x = 2y  y = 2x  x=y}. R is an equivalence relation.12) (18 pts) Let f, g, and h be functions over finite sets A, B, C, and D with f:AB,g:BC, h:CD such that h(g(f(x))) is a bijection. a) Prove that h must be a surjection and f must be an injection.b) Show that it is possible for h to not be injective, f to not be surjective, and g to beneither. (Show this using one single example. Please specify the sets A, B, C, D and thefunctions f, g, and h in your example.)13) (10 pts) Find nkkk111. (Hint: rationalize the denominator before determining the sum.)14) (2 pts) In what country did the Spanish Civil War take place? ___________________15) (2 pts) In what city is the Washington monument? ____________________________16) (2 pts) What company produces the Honda Accord?


View Full Document

UCF COT 3100 - COT 3100H Final Exam

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download COT 3100H Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view COT 3100H Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view COT 3100H Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?