Computer Science 15-190-mini, Spring 2010
Optional Homework 3
Due:  Never (optional)

This optional hw has no due date and will not affect your grade. But we'd be happy to grade what you do, and to provide whatever helpful feedback we can. And the assigned material is very worthwhile (or so I think!). I do hope some of you give it a go!

1) Write mergesort recursively.
In 15-110, we wrote mergesort iteratively. And in 15-190, we wrote quicksort recursively. It turns out there is a simple way to write mergesort recursively, too. Change the iterative version of mergesort (from 15-110) to be recursive as follows: replace the nested "for" loops with a method that instead does this: 1. Recursively mergesort the left half 2. Recursively mergesort the right half 3. Merge the two sorted halves The third step uses the exact same merge method from the iterative version. So this requires very little additional code. Be sure to think about your base case!

2) McCarthy's Function
As a test case for formal verification, the noted computer scientist John McCarthy invented the following function:
   M(n) = n - 10, if n>100
   M(n) = M(M(n+11)), if n<=100
Find a closed-form (non-recursive) solution to this function for all values of n. Using induction, if necessary, prove your result is correct.
Hint: do not Google this function, since doing so will immediately give away the answer and spoil your fun.

3) Fractals
Find a fractal tutorial of your liking (here is one of many). See if you can use recursion to generate a jpeg image of a Mandelbrot fractal (or any other reasonably interesting/challenging fractal). Use colors in interesting ways! Be creative!

Carpe diem!