Sample Problems for the CMSC 341 Midterm, Spring 2019

1. Determine the Big Oh for the running time of this code fragment, when
the key (rate limiting) operation is 

a) key comparisons

b) object moves
 


for (int i=0; i < n; i++)
  {
   if (a[i].key > a[j].key)
     {swap(i,j);};
   for (int k=1; k < n; k=k*2)
     {
       if (a[k].key > a[j].key)
          total++;
     }
  }





2.  Write the axioms for the data type with the following functions:

start:  --> S  (build an empty structure)

extend: S, string, value --> S (adds the string*value pair to the structure)

update: S, string, value --> S (replaces the old pair with string as the
                                first component, with the string*value pair)

view:   S, string --> value    (returns the value currently associated with
                                this string in the structure)








3. Suggest two possible implementations for the structure you specified
in part 2 (describe in English).




4. Code-up one of those implementations.

5. Defend the implementation choices you just made (based on speed, space, 
ease of coding, ease of maintenance).




6.  Give the formal definition of the Big Oh Notation.


7.  Build an special two-dimensional array class in Java/C++/pseudocode.
    The constructor takes a number n and builds an array with
    2n rows where the size of row i is i for i < n and 2n-i for
    i > n.

    for example when n is 3, the array looks like
    1
    12
    123
    123
    12
    1