Solutions for Sample Exam #1 ============================ 1. (a) Here are some possible inputs for the program. For each input, indicate the corresponding output. dog 9 looking: 3 4 7 4 cat 9 looking: 3 4 7 looking: 1 2 3 3 pig 9 looking: 3 4 7 looking: 0 8 8 looking: 0 9 9 -1 dog 3 looking: 1 2 3 -1 cat 3 looking: 1 2 3 3 ant 1 looking: 0 1 1 1 (b) If triSearch is asked to search a list of N items, approximately how many times on average will the function need to go through its loop? _______ | | 2 3 N 2N N/3 N/log N N/log N log N | log N | N N 2 3 2 | 3 | ------- In one sentence, explain your answer. The function divides the list into three parts each time through the loop, and log3N is the number of times you can do that. MORE INFORMATION: Suppose the size of the list, N, is 27 to begin with. Then the largest number of steps that could be required to narrow the list down to a single matching key is 4, or log 27=3. In terms of N, that is log N (or just log N). 3 3 3 There are a maximum of 3 steps as follows: step 1 N=27 . . . . . . . . . . . . . . . . . . . . . . . . . . . 3^3 2 . . . . . . . . . (divide by 3, list size is now 9) 3^2 3 . . . (divide by 3, list size is now 3) 3^1 . (divide by 3, list size is now 1) 3^0 (note: this doesn't count as a step) 2. (a) Suppose the input is: 4 4.0 2.0 -10.0 2.4 What is the output? 4.0 8.0 -40.0 9.6 0.5 2.0 -20.0 4.8 -2.5 -5.0 -10.0 -24.0 0.6 1.2 -0.24 2.4 In the next four parts, we want to evaluate how long the program will take to run, by counting the number of times selected statements are executed. In parts (b) and (c), the statements counted are input and output commands ("get" and "put"); in parts (d) and (e), we are interested in real-number operations instead. (b) i. For the input specified in part (a), how many times is a "get" statement executed? (Count ALL the "get" statements in the program.) 1 + 4 = 5 ii. And how many times is a "put" statement executed? 4 x 4 + 4 = 16 + 4 = 20 (c) Give a formula expressing the total number of "get" and "put" commands executed, in terms of N, the size of the array A. (1+N) + N (N+1) = 1 + N + N^2 + N = 1 + 2N + N^2 = (1+N)^2 (d) i. For the input specified in part (a), how many times are real-number multiplications executed? 3 + 2 + 1 + 0 = 6 ii. And how many times are real-number divisions executed? 0 + 1 + 2 + 3 = 6 (e) Give a formula expressing the total number of real-number operations (multiplications and division together) executed, in terms of N, the size of the array A. 2 ( 0 + 1 + 2 + ... + (N-1) ) = 2 ( 0.5 (N-1)(N) ) = N (N-1) = N^2 - N 3. function myStrintok (S : string) : boolean const L := length (S) var i := 1 % current character position loop exit when i>L or S(i) not= " " i += 1 end loop if i>L then result false end if if S(i)="+" or S(i)="-" then i += 1 end if if i>L then result false end if loop exit when i>L or not (S(i) >= "0" and S(i) <= "9") i += 1 end loop result i>L end myStrintok ------------------------------------------------- MORE INFORMATION ABOUT BIG-O NOTATION.......... * Newsgroups: ut.cdf.csc108h * From: Anna * Subject: Big O notation * Date: Fri, 29 Nov 1996 17:37:05 GMT Why does... for i: 1 .. N for j: 1.. i-1 a(i) := a(i) * a(i) end for end for have O(Nsquared) complexity? Here is formal proof: When i=1 we perform i-1 = 0 multiplications i=2 i-1 = 1 i=2 i-1 = 2 ... i=N-1 i-1 = N - 2 i=N i-1 = N - 1 multiplications So the number of multipl. performed is 0+1+2+3+... + N-2 + N-1 (we have N terms in this sum -- i goes from 1 to N ) Equivalently, if we discard the first 0, we have sum of numbers from 1 to N-1 (1+2+3+... + N-2 + N-1) Thus, if we use formulae stating that SUM of numbers from 1 to N is equal to N(N+1)/2, then we get: (N-1)N/2. If N=5, the number of multipl. performed is 4*5/2 = 10. ________ Now let's see that the above mentioned formulae is indeed correct: We want to sum numbers from 1 to N, so write them in following order: 1 + 2 + 3 + 4 + ... + N-3 + N-2 + N-1 + N + N + N-1+ N-2+ N-3+... + 4 + 3 + 2 + 1 ________________________________________________ N+1 + N+1+ N+1 +N+1+ ... + N+1 + N+1 + N+1 +N+1 As you can see, we are summing (N+1) N times, so the result is N*(N+1) Since we summed numbers from 1 to N twice, we need to take half of the result, therefore the final formulae is N*(N+1)/2. -------------------------------------------------