Math 55: Sample Final Exam, 9 December 20091: (a) Compute 115555mod 17.(b) Find the smallest positive inverse of 10 mod 17.(c) State the Chinese Remainder Theorem.(d) Use the procedure of the Chinese Remainder Theorem to compute 115555mod170.(e) State Fermat’s little Theorem.(f) Use Fermat’s little Theorem to find the smallest odd prime number whichdivides 115555− 1.2: Choose a posi tive integer solution (x1> 0, x2> 0, x3> 0) ofx1+ x2+ x3= 42at random, where each solution has equal probability.(a) What is the probability of selecting (14, 14, 14)?(b) What is the probability that at least one of the x’s is exactly equal to20?(c) What is the probability t hat x1= 10, given that x2= 14?3: (a) Let B be the set of finite bit stringsB = {x | ∃n ≥ 0 (x = b0b1b2. . . bnwhere bi= 0 or 1) }.Is B finite, counta ble or uncountable? Why?(b) Let F be the set of all Boolean-valued functions f : N → {0, 1} of anonnegative integer variable. Is F finite, countable or uncountable? Why?(c) Given any Boolean-valued function f of a nonnegative integer variablen, can we a lways find a C program which accepts input n and outputs f (n)?Why or why not?4: The cycle Cnis the simple graph on vertices V = {1, 2, 3, . . . , n} withedges E = {{1, 2}, {2, 3}, {3, 4}, . . ., {n − 1, n}, {n, 1}}. The coc ycle¯Cnis itscomplement, with vertices¯V and edges¯E. Justify your answer to each ofthe following questions.1(a) Determine the cardinality of¯E.(b) For which n are Cnand¯Cnisomorphic?(c) For which n does¯Cnhave an Euler circuit?5: Define the divisibility relation R on Zn= {1, 2, 3, 4, . . . , n} by aRb ↔ a|b.(a) Define a partial order and prove or disprove that R is o ne.(b) Let M be the matrix of R. Show that the number d(j) of divisors of anyinteger j ∈ Znis given by the sum of the entries in column j of M:d(j) =nXi=1Mij.(c) Evaluate d(p) f or a ny prime p ∈ Znand d(2k) for any 2k∈ Zn.(d) Consider the experiment of selecting an integer j from Znat random,with equal probabilities. Show t hatE(d) ≤nXk=11k.6: Consider the following algorithm:procedure S( a, b : positive integers )c := 1while a 6= bif a mod 2 = b mo d 2 = 0a := a/2b := b/2c := 2celse if a mod 2 = 0 ∧ b mod 2 = 1a := a/2else if a mod 2 = 1 ∧ b mod 2 = 0b := b/2elsed := |a − b|b := min(a, b)a := dend if2end whilereturn acend(a) What does S(38, 14) return?(b) What function of (a, b) does S compute? Justify your answer.(c) What is t he worst-case complexity of S in terms of a and b? Justify youranswer.7: Define a directed graph Gn= (Vn, En) for nonnegative integers n asfollows. G0has one vertex named 0 and no edges. Given Gn= (Vn, En), weform Vn+1by adding one more vertex n + 1. The edge set En+1is Enplusedges (j, n + 1) for a ll even j ∈ Vn. The first few loo k like this:0 1 2 3G1G0 1 2G2G00130(a) Find the smallest partial order  o n Vnwhose directed graph containsGnand describ e it concretely: i  j iff . . .(b) Draw the Hasse diagram for  when n = 4.(c) Define maximal elements of a poset and determine all maximal elementsof the poset (Vn, ).(d) Derive a first-order recurrence for the number enof edges in Gn.(e) Derive a second-order recurrence for the number enof edges in Gn.(f) Solve your second-order recurrence and check the results for n ≤ 3.(g) Use the recurrence relation to find an explicit formula with noPor . . .for the generating functionG(x) =∞Xn=0enxn.8: Define a relation R on simple graphs G = (V, E) by the requirement thatG1RG2iff |V1| = |V2|, |E1| = |E2|, and there is a bijection f : V1→ V2suchthat for every v ∈ V1, deg(f(v)) = deg(v).3(a) State the definition of an equivalence relation and prove that R is anequivalence relation.(b) Define isomorphism of simple graphs and prove that if G1is isomorphicto G2then G1RG2.(c) Find two nonisomorphic simple gra phs G1and G2such that G1RG2.(d) Draw one representa tive of each equivalence class C of R, for simplegraphs with n = 4 vertices and e = 0 to 4 edges.(e) Fix n = 4 vertices and consider the experiment of selecting an equivalenceclass C at ra ndom with equal probabilities. Let f(C) be the random var ia blewhich is 1 if every graph in C contains an Euler circuit and 0 otherwise. Stategeneral formulas for the expectation E(f ) and varia nce V (f ) of f. ComputeE(f) and V (f).9: Fo r each of the f ollowing pairs of graphs, either specify an isomorphismbetween the left and the right graph, or state why there cannot be one.54 6321(a)56143212 3645(b)45 326112 34 65(c)1 2645310: Consider the following undirected pseudograph G:21(a) Write down the adjacency matrix A o f G.(b) Find all paths of length 3 fro m 1 t o 2; for example, one is (1, 1, 1, 2),where the path loops twice at 1 then goes from 1 to 2.(c) Use the adjacency matrix A to express the number of paths from 1 to 2of any specified length n ≥ 1 in terms of the Fibonacci numbers (defined byf0= 0, f1= 1, fn+1= fn+ fn−1for n ≥ 1).411: Let S be the set of permutations of n ≥ 100 objects.(a) How many elements of S leave the third object fixed?(b) Consider the experiment o f choosing an element of S randomly with equalprobabilities. Let f be the random variable defined by f (σ) = |{j : σ(j) =j}|, so f (σ) is the number of fixed points of σ. Compute the expectation o ff.(c) Compute the variance V (f ) and standard deviation σ(f) of f .(d) Show that a randomly chosen permutation of n ≥ 100 objects is 99%certain to leave less than 11 objects fixed.12: Find the remainder of 2326(a) mod 2,(b) mod 5.(c) State Fermat’s little Theorem.(d) Find 2326mod 47.(e) State the Chinese Remainder Theorem fo r three moduli.(f) Use the preceding results (a), (b), (d) and (e) to compute 2326mod 470.13: The simplex graph Sn= (Vn, En) in n dimensions is defined recursively asfollows. S0has one vertex a nd no edges. G iven Sn= (Vn, En), we form Vn+1by adding one more vertex v. The edge set En+1is Enplus edges connectingv to every vertex in Vn. The first few loo k like t his:12S121S2213 3 4S3(a) Find the number vnof vertices in Sn.(b) Find the degree d of each vertex in Sn.(c) Use the Handshaking Theorem to find t he number enof edges in Sn.(d) Derive a first-order inhomogeneous recurrence relation for t he numberenof edges in Sn.(e) Derive the generating function for enfrom the recurrence relation.(f) Taylor-expand the generating function to derive a closed formula for enand check against (c).514: Define the divisibility relation R on the set Z = {1, 2, 3, 4, . . .} of po sitiveintegers by aRb