Lab 6 Sample Solutions
----------------------

(1) Provide a regular expression that accepts the same language
    as the finite state machine described in the table below.

   Current  Next    New                     Clumsy Ascii FSM
    state  symbol  state                                          /\0
   ------- ------  ------                            0           / /
    start    0     accept                 start------------->accept
    start    1     odd                     |                /  ^
    accept   0     accept                  |           1__ /   |
    accept   1     odd                    1|    _______/       |0
    odd      0     even                    |   /               |
    odd      1     odd                     V  V     0          |
    even     0     accept                 _odd-------------->even
    even     1     odd                   | / ^______________/
                                         1-        1
    Sample solution
    0 | [01]*00+

    Essentially the fsm accepts a single zero, and also
    accepts any string that ends in at least two zeros.


(2) For each of the following binary strings, assuming we
    begin in the start state of the fsm shown above, give
    the sequence of five states the fsm goes through.
       (i)   10111
       (ii)  11000
       (iii) 01100
       (iv)  01010

    Sample solution
    (i)   (ii)    (iii)   (iv)
    odd   odd     accept  accept
    even  odd     odd     odd
    odd   even    odd     even
    odd   accept  even    odd
    odd   accept  accept  even


(3) For each of the three code segments below, classify them
    as one of: constant time, logarithmic, linear, quadratic,
    or exponential, and justify your answer.

       // code segment 1
       total = 0;  M = 1;
       for (i = 1; i <= N; i++) {
           M = M * 2;
           for (j = 1; j < M; j++) {
               total++;
           }
       }

       Sample solution
       we do one multiplication on each pass through the outer loop
          so O(N) multiplication operations,
       but the number of passes through the inner loop doubles each time,
          i.e. 1, 2, 4, 8, ..., 2^N
       so the number of times we increment total is
          1 + 2 + 4 + ... + 2^N
       which is 2^(N+1) - 1, i.e. O(2^N), so exponential



       // code segment 2
       total = 0;
       for (i = 1; i <= N; i = i * 2) {
           total = total + i;
       }

       Sample solution
        since i doubles each pass, and we stop when i > N,
           we make roughly log_2(N) passes,
        i.e. O(log(N)), so logarithmic



       // code segment 3
       total = 0;
       for (i = 1; i <= N; i++) {
          for (j = 1; j <= i; j++) {
              total = total + i + j;
          }
       }

       Sample solution

         we perform total+i+j once on the first pass,
            twice on the second pass,
            three times on the third,
            ...
            N times on the final pass
         so 1 + 2 + ... + N, giving N(N-1)/2,
         i.e. O(N^2), so quadratic