CMSC 351 - "Thought Questions" - CMSC 351
Not Graded but Should be Done

(1)
Assume rich deposits of clean underground water have been found in Utah.
The state of Nevada would like to build a central pipeline from Utah
  to the border of Nevada for bringing in that water.
There are n wells in Utah and you have their longitude and
  latitude positions.

The rules imposed on you are:
   - pipes can only be laid North/South or East/West (no diagonals)
   - all n wells need to be connected to the central pipeline
        using the minimum amount of pipe

Provide an algorithm that will provide the optimal latitude on which
  to run the central pipeline.

Way to turn this into a more familiar problem.




(2)
    Consider the following solution for finding the MINIMUM element
    in a list of n elements:
        If the list has only one element, then return it
        Otherwise...
          Step 1: divide into pairs and compare
                  discard the larger of each pair as a candidate
                     to create a new (smaller) list of candidates
          Step 2: recursively call this function to find the MINIMUM
                     of this smaller list


    We have discussed in class that it can't run in better than n-1
    number of comparisons.  Use a recurrence tree to carefully model 
    this recursive solution and show that this tree can be used to 
    establish that the run time for this is exactly  n-1.

      NOTES: Don't worry about floors and ceilings (ie: assume the list is a power of 2). 
             Use a recurrence tree.
             Don't over-approximate.


If you are stuck on how to start, the recurrence becomes this.




(3)
    Imagine that we have a helper function H1 that runs in Θ(n) time and
    another helper function H2 that runs in Θ(n2) time.

    If I had an algorithm F that would
        - call H1 on the input list which would return two sublists
             each containing half of the original list
        - make a recursive call to F on each of these two sublists
          which would each return a single value from their sublist
        - call H2 on a list containing the two values returned in 
             the previous step
    then what is the asymptotic class of that algorithm?

If you want to make sure you've got the right recurrence before you move
forward, here's the recurrence and another note.




(4)
    Assume we can find the 4th smallest element in a group 
    of 8 using A comparisons.
        Step 1: Divide the original list into groups of 8 
                and find the 4th smallest in each group.  
                Call these the "Candidates".
        Step 2: Find the median of the "Candidates" and call
                this our pivot.
        Step 3: Partition around this pivot.
        Step 4: Recursively do selection on the appropriate of 
                the two "buckets" created during partitioning.
                For our analysis, we will assume we have to look 
                in the bigger bucket.

    (a) Determine the worst-case runtime's recurrence relation.
    (b) Determine the Big-O asymptotic runtime of this, and then use
        constructive induction to determine the constant factor for
        it in terms of A.

         Partial Solution