CMPS 211 Exam 2 Sample, Fall 2010

1 1. (10 Points) Give an algorithm that takes a list of n integers a1,a2,…,an and finds the number of (how many) integers in the list are (each) greater than 5. procedure greaterthanfive (a1,…,an: integers) What is the worst-case complexity of your algorithm? (Count the number of comparisons used). What is the best-case complexity of your algorithm? (Count the number of comparisons used). 2. (5 Points) Use the definition of big-oh to prove that 13 + 23 + ... + n3 is O(n4). 3. (5 Points) Suppose n is a given positive integer, How many times will the following algorithm print hello: while n > 1 begin print ``hello''; n : = n/2 end. 2 4. (15 Points) This problem is about the Binary search algorithm which is is given below. procedure binary serach (x : intreger, a1, a2,…, an: increasing list of integers) i := 1 {i is left endpoint of search interval} j := n {j is right endpoint of search interval} while i < j begin m := (i+j)/2 if x > am then i := m+1 else j := m end if x = ai then location := i else location := 0 {location is the subscript of the term equal to x, or 0 if x is not found} a. Show how the binary search algorithm searches for 12 in the following list: 5 6 8 12 15 21 25 31. In particular show the changing values of i and j and give the consecutive choices of the sub-lists of the original list and the final value of location. i j List 1 8 5 6 8 12 15 21 25 31 location = 3 b. What is the best-case complexity of the binary search algorithm as given. Suggest a way to make it O(1), and give the resulting algorithm. (Only give the changes). c. Suppose that the binary search algorithm is to be rewritten, because the input is to be a decreasing list of integers (instead of increasing). Suggest minimal changes to the given algorithm. Just write down the changes next to the following pseudo-code: procedure binary serach (x : intreger, a1, a2,…, an: increasing list of integers) i := 1 {i is left endpoint of search interval} j := n {j is right endpoint of search interval} while i < j begin m := (i+j)/2 if x > am then i := m+1 else j := m end if x = ai then location := i else location := 0 {location is the subscript of the term equal to x, or 0 if x is not found} 4 5. (15 Points) In the questions below, find the time complexity (exact count) . Also, find the “best” big-oh notation to describe the complexity of the algorithm. Choose your answers from the following: 1, log2 n, n, nlog2 n, n2, n3,…, 2n, n!. a. A linear search to find the smallest number in a list of n numbers. (Count comparisons) Count(n) = Count(n) is O( ) b. The count of print statements in the following: i : = 1, j : = 1 while i ≤ n begin while j ≤ i begin print ``hello''; j : = j + 1 end i : = i + 1 end Count(n) = Count(n) is O( ) c. An iterative algorithm to compute n!, (count the number of multiplications). Count(n) = Count(n) is O( ) d. An algorithm that prints all bit strings of length n. (Just give big-oh, and say why) O( ) 5 6.(10 Points) a. Use mathematical induction to prove that every amount of postage of 6 cents or more can be formed using 3-cent and 4-cent stamps. Indicate where in the proof, you make use of the fact that the “amount is greater than or equal to 6.” b. Let a1 = 2, a2 = 9, and an = 2an − 1 + 3an − 2 for n ≥ 3. Show that an ≤ 3n for all positive integers n. 6 7. (12 Points) a. Given the function f (n) = f (n − 1) ⋅ f (n − 2) + 1, f (0) = 1, f (1) = 4.. Find f (2) and f (3). Show your computations. b. Consider the following recursive definition of a set S of strings: 1 ∈ S; x ∈ S → x11 ∈ S What is the set S ? List the first 4 strings. c. Give a recursive definition for the set S = { …. -6, -4, -2, 0, 2, 4, 6, …} 7 8. (8 Points) Consider the following program segment: i : = 1 total : = 1 while i < n begin i : = i + 1 total : = total + i end. a. Let p be the proposition “ ( 1) i i2 total + = and i ≤ n.” Show that p is a loop invariant. b. Use (a) to prove that the program segment computes the sum 1 +2 + ….+ n = n(n+1)/2. 8 9. (15 Points) In the questions below suppose that a “word” is any string of 6 capitalized letters of the alphabet, with repeated letters allowed. (There are 26 letters in the alphabet) Justify your answers a. How many words are there? b. How many words begin with A or end with B? c. How many words begin with a vowel and end with a vowel? (There are 5 vowels) d. How many words begin with a vowel or end with a vowel? e. How many words have exactly one vowel? 9 10. (10 Points) a. Show that if five points are picked on or in the interior of a square of side length 2, then there are at least two of these points no farther than 2 apart. (Hint: Divide the square into four congruent 1 × 1 squares.) b. A professor teaching a Discrete Math course gives a multiple choice quiz that has 10 questions, each with 4 possible responses: a, b, c, d. What is the minimum number of students that must be in the professor's class in order to guarantee that at least three answer sheets must be identical? (Assume that no answers are left blank.) 10 .