CSC148H SUMMER 97

EVENING SECTION

MIDTERM SOLUTIONS
------------------------------------------------------------------------

(note: most of these solutions are more detailed then what was
required for full marks.)


1.

a.  A B D E C F

b.  The maximum size of the stack will be equal to the height of tree.
    [Answering "3" was not enough for full marks, since the question
    pertained to _any_ tree.]

c.  A maze is similar because if you consider the entrance to be the
    root, and the paths to be edges, then the decision points in the
    maze are like tree nodes.  You can traverse a maze to find an exit
    the same way you traverse a tree.  [Anything along these lines was
    accepted.]

d.  A maze that has loops is not like a tree, because a tree cannot
    have loops.  [Many people said a maze that has several entrances,
    or exits, but these are trees.  Many said a maze with a single
    path and no decision points, but this is a 'degenerate' tree.


2.

a. O(1).  Since we have a pointer to the front of the list, all we
   have to do is manipulate a few pointers.

b. O(n).  Since we don't have a pointer to the end of the list, we
   have to follow all the links starting at the front, until we reach
   the end.  This will take n steps.

c. No, because we cannot do a binary search on a linked list.  At
   least, we can't do an O(log n) binary search.  There is no way to
   directly go to the middle element---we have to follow the pointers.

d. O(n^2).  The outer loop will have exactly n iterations, because
   'done_this' moves backwards through the list one node at a time
   until it reaches 'head'.  The inner loop has a worst case time of n
   iterations.  It moves 'curr' forward through the list until it
   reaches 'done_this'.  So the first time, it will do n iterations,
   the second time it will do n-1 iterations, third time n-2, and so
   on.
   This is an O(n) loop nested inside a loop that iterates n
   times, so O(n^2).

   Or you could add up all the work like this:
     n + (n-1) + (n-2) + ... + 1 
     ^     ^       ^
     |     |       work of inner loop on 3rd iteration of outer loop
     |     work of inner loop on 4th iteration of outer loop
     work of inner loop on first iteration of loop

   There is a formula for this   sum of 1..n = (n^2+n)/2

   So this takes (n^2+n)/2 which is O(n^2).

   BTW:  this code reverse-prints a linked list.  There is a simple
   recursive algorithm of maybe 5 lines of code that does it in O(n).


3.

a.  There are many choices:
      - a linked list of strings
      - an ordered array of strings
      - a tree where each node stores a string

b.  Depends on choice of a.
      - linked list has unlimited size (except by memory)
      - sorted array would make operation of part c. more efficient.
      - tree also has unlimited size, but combining to salads would be
        easy (just treat each as a subtree of a new tree).

c.  Depends on choice of a.
      - linked list does not have 'direct' access; must follow pointers.
      - sorted array must be kept sorted after insertions (takes time)
      - tree does not have direct access either.  


d.  The algorithm goes like this.  For each fruit in the array, look
    over the whole array to see if it occurs again somewhere.  If it
    doesin't, return the fruit.  Otherwise move on to the next fruit.
    You can use a counter to count the fruit of the same type, or just
    a boolean flag that says whether or not the fruit occurs more than
    once.

    There are ways to make minor improvements to the efficiency of the
    code below (like using conditional loops instead of for-loops, so
    you can exit them prematurely), but it would still be O(n^2) code.


    function OccursOnce( salad : array 1..* of string, size : int) : string

        var occurs_twice_or_more : boolean
        var the_one : string := ""

        for i : 1..size

            occurs_twice_or_more := false
            for j : 1..size
                if salad(i) = salad(j) and i not= j then
                    occurs_twice_or_more := true
                end if
            end for

            if not occurs_twice_or_more then
                the_one := salad(i)
            end if

         end for

         result the_one

    end OccursOnce