MATH 211 Exam 2, Spring 2013

MATH 211 SPRING 2013 TEST II VERSION A NAME: SECTION: (1) True/False Questions: (1 point each). T F f(x) is O(1) means that f(x) is a constant function. T F If f(x) is Ω(g(x)) then there exist unique constants C and k such that |g(x)| < C|f(x)| for all x > k. T F For any positive integers A, b and m, (a mod m)+(b mod m) = (a + b mod m) T F It is not possible to find functions f(x) and g(x) such that f(x) is O(g(x)) and g(x) is O(f(x)). T F If f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then the function f1(x)f2(x) is O(max(g1(x), g2(x))). T F If a ̸= 0 and ab ≡ ac( mod m) then b ≡ c( mod m). T F Given that lcm(a, b) = 14 and a × b = 42 then necessarily gcd(a, b) = 3. T F Consider the following two linear congruential generators, both of the form xn+1 = axn + b(modm). (I) a = 7, b = 4, x0 = 3 and m = 9 (II) a = 7, b = 3, x0 = 3 and m = 9 The first generator is better. T F The integer 111222333444 is divisible by 3 and 6 but not divisible by 9. T F The complexity of the linear search algorithm is O(n). 1 2 (2) (3 pts.) Show by using mathematical induction that for every nonnegative integer n, the integer n5 − n is divisible by 5. 3 (3) (3 pts.)Write the bubble sort algorithm and show the steps needed to sort the sequence 5, 7, 2. 4 (4) (3 pts.) Given is the following procedure written in pseudo-code: procedure lst(input: a1,...,an: integers) L:=1 M:=a1 for i=2 to n if (ai > m) then begin m:=ai L:=i end else if (ai = m) then L:=i {output: M and L} Provide the output of this function when the input sequence 4, 4, 2, 3, 2, 4, 3, 1 is entered, and state what the code does in general. (5) (3 pts.) Use the Euclidean Algorithm to find gcd(50, 14) and then represent it in the form as + bt. 5 (6) Given is the following procedure written in pseudo-code: procedure locc(input: a1,...,an: integers) m:= a1 for i=2 to n if (ai < m) then m:=ai l:=0 for i=2 to n if (ai = m) then l:=i {output: l} (a) (2 pts.)Provide the output of this function when the input sequence 4, 4, 2, 3, 2, 4 is entered, and state what the code does in general. (b) (2 pts.)Calculate the number of comparisons if the above code as a function of the the input size n. 6 (7) (3 pts.) Show that a composite integer n must have a prime divisor less than or equal to √n. 7 (8) (3 pts.) Solve the congruence equation 15x ≡ 7( mod 11) (9) (4 pts.) Find a function g(n) so that 4n2 − 5 is Θ(g(n)). Make sure you include the necessary witnesses.