15-110 Spring 2011 Homework 3-Bonus
Due Monday, 7-Feb, at 11:59pm  (no late submissions for bonus hw)
Note:  This deadline is only for hw3-bonus.  Hw3 is still due on Sunday, 6-Feb, at 6pm.


Same basic directions as hw3, so read those carefully (replacing "hw3" with "hw3-bonus", where appropriate, of course).

Additional notes:


  1. Bonus/Optional:  Week #3 Bonus/Honors Topic   [5 pts]
    This bonus activity serves two purposes:  (1) to expose you to interesting, somewhat more challenging concepts that extend the topics covered in this assignment; and (2) to give you a sense of what the Honors mini will be like (as it will follow this same basic format, with about the same rigor).  Total time invested in this activity should be around 1.5 to 2 hours (which is about half the expected time for future Honors assignments), and you must complete the entire activity to receive credit.
      1. Bonus Lecture
        A lecture covering this week's bonus topics will be presented on Tuesday 1-Feb at 4:30pm in DH 1212, and should last about 45 minutes (again, about half the expected time for future Honors lectures).  Attendance is encouraged but not required (and space may be limited, so we will have a sign-up sheet for those interested).  A video of the lecture will be made available (perhaps online or perhaps via DVD's to loan).  If you do not attend the lecture, then watch this video (in its entirety and with the same focused attention that you would have in the classroom).   Note that there are no online lecture notes for this week.
      2. Bonus Assignment
        Note #1:  Place your answers in the files hw3-bonus.py and hw3-bonus.doc (or whatever other legal extension you wish to use), and add those files to your hw3-bonus folder before zipping it up and submitting hw3-bonus.zip.  If you do not know how to do this, ask your CA for help.  You can start from the code we wrote in lecture.

        1. Change selection sort to select largest elements...
          We wrote selection sort so it repeatedly finds the smallest remaining element and swaps it towards the front.  This is not how the visualization for selection sort works in xSortLab.  There, it finds the largest remaining element and swaps it towards the back.  Change selection sort to work in that way.

        2. Make merge sort work for arbitrary-length lists
          The way we wrote merge sort, it only works for lists with a length of a power of 2.  This restriction is easily lifted, so be sure that the merge sort that you submit works for lists of any size.

        3. Graph selection sort and merge sort
          Make two plots, one for selection sort, one for merge sort.  Place the # of elements in the list (N) on the x-axis, and the run time in seconds on the y-axis (so you will have to use our timing code repeatedly for each sort).  Are the curves linear?  Parabolic (quadratic)?  Something else?  Explain.  [ Note: you can paste an image of your plots into your Word document (and if you really, truly cannot do that, then place the images in your hw3-bonus directory and refer to them in your write-up; just please keep the images smallish, say, <50k each. ]

        4. Variance in run times
          For a fixed size N, every time you run selection sort (or merge sort) you tend to get similar-yet-different times.  Explain the variation.

        5. Radix Sort
          Read about radix sort, then answer these questions:

          1. Explain how radix sort would sort this list if the radix is 10:
                 [75, 52, 35, 15, 22, 45, 81, 43, 41, 85, 42 ]
            Include the partially-sorted list halfway through the sort  (after the first digit is sorted).

          2. The radix sort article includes code in Python.  Copy that code into your hw3-bonus.py file and time the algorithm on various sized lists.  Then:  which is faster, radix sort or selection sort?  radix sort or merge sort?

          3. Merge sort is a comparison-based sort, but radix sort is not.  Briefly explain.