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.
-------------------------------------------------