MATH 211 Final With Solution, Spring 2014

MATH 211-2014S FINAL EXAM NAME: (1) circle all the statements that are correct (Tr) F if2+1=0and1+2=2+1thn2+2=30r2+2=4 @) F there is exactly one set A such that |P(A)| <1 T (F) if AUC= BUC then A=B @) F The cardinality of B@ B does not depend on the cardinality of B (x) F A and B are two set such that |A] = 3 and |B| = 4. The number of one-to-one functions from A to B is P(4,3) T @) The bubble sort has complexity @(n*) T CF) The coefficient of x!y$ in the expansion of (x — 3y)’” is 0 T ®) The inverse of a modulo m always exists but it may not be unique unless gced(a,m) = 1 T ®) The number of subsets, of a set with 10 elements, that contain more than two element is 1013 fis ) The characteristic equation of the recurrence relation Qn = —An—2 — An_4 is r*#— 7? -1=0 (2) There are seven girls and seven boys in a group. A committee of 6 people is to include 3 girls and 3 boys. How many committees are there such that Lama is included but Sama is not included? (where, of course, Sama and Lama are two girls in the group). (3) ways Ce get swe ob |. beside Law a ( ¥ 2 Cauw2e Samae AS EXC | uv cee ) (3) A communication channel can transmit three types of signals, a, b, c. Each of the first two signals takes one microsecond to be transmitted, while the third signal takes two microseconds. So, for example, some of the messages that can be transmitted in 3 microseconds are: aaa, ac, bc, and cb. Write a recurrence relation for the number of distinct messages that can be transmitted in n microseconds if a message can only include some or all of the three signals described above. Specify any necessary initial conditions. ; snikal Comd hts ' OL, = 2 (either hae ab’) ar= 5 ( aa, ‘ab’, ‘ba’, “LW & ©’) Fa n>3now Piney MNESS ALR wil) ec Ator shank with ‘ol, LW’ on’c’. tf fol ore’: the nsot «| He message will be drans mctted in (n-1) micresetords: go we have 2x Ant Sucks one saga of Brnsith i xf Mae lar on starts wet fo" Wr We a Q ms SF We \nove (m-2) RL arnt n§ micre Seconds , Ant2 com \pe Ft ounsevs He ah in Mita. (n-Y ms. Se we - An =2On-\ + Gnea 3» NDB —_ (4) The number of bit strings that have length between 7 and 10 (inclusive) and both start and end with zeroes is Lensth Fi 2° 2 2& —— 8 a os a7 Y Length | Oo: B » ; 4 : fi ah 2 + o*.2', 2 = 324+ 64 +1294 256 = 470 3 (5) The number of English strings with four letters and that have exactly two distinct letters is 4 26 i ess = ene Gaol 5 . JK A 26 ; ; ; hen ti Can 2: (KO : ‘es xe ~ —- (order not yet i) The enswer is Ake Sum ra % + ¢ | (6) Given that a= 7 mod 12,b=11 mod 12,c=5 mod 12,d=6 mod 12, find the remainder of the division by 6 of at +b*+c*+d* a = 47 =1 med \2 = a’ =\ med (2 similealy Vato (® oe a bt elit 4 y disco mrdl2 somata bla clad = 3 mudi sr %-12K+3 = 6(2kK)4+ 2 > OU (7) A particular solution of the recurrence equation [O otc om { lhom 2° Gh. ad | 4 On = 3An—1 + 4dn—2 + 12” is One 4 k _ ) se Fem rat park ator soludion (Stee @ hs a wast ) Lin + $) 2 We. Te. te- pla tiv oe i ALG. (p : n Wwe ak Gon - ($n +!2) Zz, (8) Show that the relation R, consisting of all pairs (x,y) where x and y are binary strings of length two or more that agree in their first two bits, is an equivalent relation on the set of all binary strings of length two or more. State explicitly the equivalence classes of this relation. Let By, $o ky 2 be bnew) s dng A Leash > 2. (9) Consider the relations, on the set {1, 2, 3,4}, R= {(1, 1), (1, 2), (2, 1), (2, 2), (3,4), (4, 1), (4, 4)} , R= {(1, 1), (1, 2), (3, 4)} a. pe (a) represent each relation both using a digraph and a matrix. ryph(b) Write the matrices of the relations R; \ Ro, Ri ° Re. ) 2¢ }.(c) Which of these relations is antisymmetric? symmetric? >t. (d) Write down (your own) relation on the set {1, 2, 3,4} that is both symmetric and f antisymmetric? \ R, Cch—- } . : 3 ( a) t 2\ | \ ra Me =2/0 oOo O ye 43 Cer smell u| loo oO : ie 4 om R 2 & 4 2. 4 \ \ M R q 2) oO oO 3 ~ G i yle oO \) @ \ R ji &® & GW 4 K. S/ 7 {| & © o o | we \ RN a 4, " a3)e 2 29 9 4 | oS) 2 \ | u O (o) \ \ Ra + nat Sy mmebric IQR, 2 Lt 2 Ro | anti symmulv C4 = —- 0c ® RL, VF oe {OVO o& 112), C13), 4), (2,3), (4D, 43) | 6 (10) Apply the extended Euclidean Algorithm to find ged(765, 101), then use it to calculate the inverse of 101 modulo 765 ; 765 = Falol +58) 4 = 13 - Gx2 213- C(15-13) ope hx 5? 443) 2 219 — COD = F438 -2-19-G sy = 1x43 +15\= - 2015) + F(48) =-20(58-43) 47-4 4 = 2«\5 +13 1527(4%-20(58) = 97 (lol -53)- 2ox5i yo atx 13 +% la-42 (59) + 2H(lol)a 12 = xt + |-470 465 -Falol) + 2t(lol) 2= tel +O la B5E(lol) -4Fx FES. so the ine f lol mrdule FOS iss 356 (11) A and B are two set such that |A| = 3 and |B| = 4. Find the number of onto functions from B to A. 31 C (3,1) 3-1) 4 C(3,2)x (3 2 = 9/- 3x1643 = 36 (12) Suppose that the variable x represents students and y represents courses, and: U(y): yis an upper-level course My): y isa math course F(z): a is a freshman A(x): x is a part time student (x,y): student z is taking course y. Write the statements below using these predicates and any needed quantifiers. (a) every freshman student is taking at least two coursed. (b) there is a part time freshman student who is not taking any course. (c) there are at least two freshmen students who are taking the same upper level math courses. (®) Vx day, ( FCx) > T(uy,)n 1% ae, in Cb) dx (Fan AHA Vy Tey )) | (c) Sx, 3x% (ute a FOAF@)A mC G)a mo} > ( Vy) Tl (%aiJ ) 8 (13) Prove that an integer n is odd unless 5n? +7 isodd. | iy at i¢ ‘ We rund te shea that 36 Suty? ty nab odd on WW 1S wale . By Contre pos Won , Sw poe x A . AS NOY => Fn ks even +t US odd . (14) Find a function from Z to N that is a bijection. You will need to verify that your /\ function is one to one and onto. The Gollowins diasfnn a4vy phe Sumebrmn =| x \ uJ 42 fe) i sy | REM 4, Lot 4d , f 4 In Sy mbo \c i jC%) = ] 2z f Zz ws oo si tive oo me -2Z-\ J xm neqahve Sas {A , la hh EZ, & Zr one sudh Yat S(a)= fa uy His Value AS even, town both Ay by Ex ane. pes hy Se 22%, =-242. = Ba. xf this Common Vee vs odd , Then Zk daw <e Se 2 2,-L2z,-1., “2 y Sty « 9 (15) Give a recursive definition for the set of positive integers not divisible by 2 nor by 3. Base Cane: LEG 7 2¢€ 3 te , | i Re CursiVe a ; iS SE 3 Hon SF 6 € (16) Prove by induction that f? + f?+---+f2 = fafn+i where fy, is the n‘* Fibonacci number. Base Case: Melita Fah ale ate Td. big Suppose , Ja Some K, frat Fath wel sep : we ned to show that the. predicate 1S Jor ta (k+f) . > Prana haf = A Ay, ~ Soar Fe * Deas) ~ yy (Sea) This nee Sha inductive step. The wurallt Ww So\\ows by Mg geinc pe A vvaed ena eed induehm 10 (17) Given a list of integers (not necessarily all distinct), write a function that returns the last occurrence of the minimum. (For full credit, the function complexity must be linear, i.e. the number of computations must be O(n) where n is the size of the input list).