CMU 15-190 Spring 2017: Topics in Intermediate Programming
Homework 4 (Due Wednesday 15-Feb, at 11:59pm)

• This hw is optional. It is for students who want to get a bit more out of the optional/advanced talk last week, and in particular for those who may wish to get 3 units of pass/fail credit for 15-190 (for whom it is required). We hope that's quite a few of you!


• Work Solo or in Groups of 2-5 (and groups are strongly recommended) Have fun!


• We will grade the hw, but loosely, and chiefly based on effort. You should expect to invest 1-2 hours on it and you'll be fine. This is not about the grade, of course, but about the learning. So take your time, discuss issues with your groupmates, have fun, and enjoy.


• Please track when you start and stop working on this, and with whom you collaborate. You'll need that for your submission. And again, have fun.

1. quickSort with median-of-three pivot selection
   First, watch the video and study the quickSort code from here. Then, read the Choice of Pivot section in the Wikipedia article on quicksort (here), especially the choice-of-three part. Then, modify quicksort so it uses the choice-of-three pivot selection algorithm.
   • Adapt our timing code from here to test the original version of quicksort and this median-of-three version. How does the median-of-three affect the runtime of quickSort for large lists (so, large values of N)?


2. radixSort in arbitrary bases
   First, watch the video and study the radixSort code from here. Then, modify radixsort so it takes a second parameter, the base, so it's radixsort(L, base). In class, we discussed how radixSort could work in base 10, and then again briefly in base 2. Here, it should work for an arbitrary base. If we have 10 buckets in base 10, and 2 buckets in base 2, clearly the base determines the number of buckets to use. And then be sure to extract the kth digit in that given base.
   • Adapt our timing code from here to test radixSort using different bases -- 2, 3, 10, 100, 1000. How does changing the base affect the runtime of radixSort for large lists (so, large values of N)?


3. What to Submit
   Each member of the group should submit their own PDF file, 15-190-hw4.pdf, containing this information:
   1. Your name and andrew id
   2. The names and andrew id's of your groupmates
   3. The start/stop times you worked, and the total time you worked.
   4. Your thoughts about this exercise -- useful, interesting, etc? This will help us improve the 15-190 experience as we go.
   5. The solutions from above. Note: one way to create a PDF is to first make a Word file, then export that to PDF.
   You can submit your hw to the 15-190 autolab site here.