CMSC 351 - Homework #2 - Due by 11:59pm on February 8th

Write clearly. Scan/photograph clearly. If we can't read it, we will grade it as incorrect.

After you finish your answers, scan or carefully photograph your answer sheets and create a single PDF with those images to upload to the ELMS entry.

If your Windows machine doesn't have a "Print to PDF" option, you might find the free CutePDF Writer useful.

You cannot e-mail them to me.

Even though you are uploading to ELMS, be sure to write your name and section clearly on the top of the first page.

We might not grade all questions.

(1) Given the following SwappySort algorithm:

    Do not approximate things in this problem - solve to a formula based on n.

    Assume we have indices from 1..n for the list.
	for i = 1 to n-1
	   for j = i to n
	     if (ai > aj) then swap(ai,aj)



     (a) Does it sort correctly?  (A simple yes/no answer is fine.)
     (b) Regardless of whether it sorts correctly, what is the best-case 
         input ordering (describe carefully) if all we care about are the
         calls to the swap function, and what is the run-time for
         that input in terms of calls to the swap function for that 
         input?  
     (c) Regardless of whether it sorts correctly, what is the worst-case 
         input ordering (describe carefully) if all we care about are the
         calls to the swap function, and what is the run-time for
         that input in terms of calls to the swap function for that 
         input?  








(2) Problem input:  an array of length 3 where the contents are unique 
                         strings from {Bush, Obama, Trump}

    Problem output: an array sorted based on the "President Number" of 
       person named in the original values (so Bush was #43, Obama
       was #44, Trump is #45).

    Additional information : each string does NOT have an equal 
        chance of being in each of the three array positions;  there 
        is only a 30% chance that "Trump" will be the string in the 
        first spot of the input array (but other than that, everything 
        else is equally likely).

      (a) List all possible inputs along with the probability that it
          would appear as the input in a randomly selected example.
          HINT for #2a

      (b) Given the SwappySort algorithm above, compute the EXPECTED
          run-time in terms of calls to the swap function within 
          these input constraints.  The expected runtime is sometimes
          called the average runtime.

          HINT for #2b
    
      (c) Provide either the name of a sort that you think would be 
          best for this problem, or provide an algorithm of your own.
          Specify the runtime of the sort (whether a named one or your 
          own algorithm).  You do not have to prove that runtime here.








(3) Use integration to establish a set of bounds around the following:

      n-1
       Σ [loge(j3)+j-1]
      j=2

    Show the details and present the upper and lower bound functions
    that you obtain.  You may leave constants such as ln(2) as
    part of the solution (you don't need to resolve things like that to
    the actual value for this problem) but you do need to try to simplify
    other things as much as possible using algebra and the rules on the 
    formula sheet.

    Give your opinion as to whether both bounds would be members of 
    the same Big-O class.  If you aren't sure at all, feel free to
    say that.
 
    For this course, whenever we have a runtime for a constructive
    algorithm, we will assume that it is always increasing as our
    default.  You do not have to prove this property for this problem.

    HINT for #3