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 <g5sann@cdf.toronto.edu>
* 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.

-------------------------------------------------