Download and extract the code skeleton for this exercise. As last week, the code includes an outline of how to organize your work and some tests.

Go Get

The tests provided for this exercise use the assert package which is excellent, but not part of the standard library. It will give us a chance to see how easily Go can install external dependencies:

go get github.com/stretchr/testify/assert

Mutating Methods

Our Point class from last week was effectively immutable (from outside the package) since there were no exported members, and not methods that changed its state.

Let's add some methods that change the Point in place. In order to modify the struct, a method must use a pointer receiver argument. Feel free to copy your Point implementation from last week, and in points.go, change the package to exer9 and…

Scale

Add a .Scale(f) method to the Point from last week. It should change an existing point in place and stretch it by a factor of f. For example:

p := Point{1, 2}
p.Scale(5)
fmt.Println(p)

… should print (5, 10).

Rotate

We can add another transformation to a Point: rotation. We would like to call .Rotate(angle) and have the point rotated by angle radians around the origin. For angle \(a\), the transformation is: \[ x \leftarrow x \cdot \cos(a) - y\cdot\sin(a) \\ y \leftarrow x \cdot \sin(a) + y\cdot\cos(a) \]

The result should be that this code:

p := Point{1, 0}
p.Rotate(math.Pi / 2)
fmt.Println(p)
p.Rotate(math.Pi / 2)
fmt.Println(p)

… should print (0, 1) and (-1, 0) (but probably not exactly due to floating-point error, but the results will be close to these values).

Random Arrays

We want to generate some random arrays. In array_stats.go, write a function that creates and returns an array with length integers and values from 0 to maxInt-1 with this signature:

func RandomArray(length int, maxInt int) []int { … }

When doing this, create a new random number generator that has a reasonable initial seed.

Array Summary Stats

We want to calculate the mean and standard deviation of values in an array/slice. For arrays with values \(x\) and \(n\) elements, we will use these formulas:

\(\mu = \left(\sum x\right) / n \)

\(\sigma = \sqrt{\left(\sum x^2\right)/n - \left(\left(\sum x\right)/n\right)^2} \)

In order to calculate these, we need the length of the slice (easy), \(\sum x\) and \(\sum x^2\). Those are things we can calculate in parallel on a large array.

We will break the array into some evenly-sized slices and want to calculate the two sums on each of the chunks concurrently in goroutines. Our function will take the array/slice and number of chunks to break the array into:

func MeanStddev(arr []int, chunks int) (mean, stddev float64) { … }

You can assume that the length of arr is divisible by chunks: no rounding error to worry about.

In order to do this, you need to create:

• A struct to hold partial sums as they are generated.
• A channel to communicate these partial sums back to the MeanStddev function.
• A function that can run in a goroutine, calculate the sum and sum of squares on a slice, and send the values back along the channel.

In MeanStddev, you will need to create chunks goroutines to calculate partial sums. Then receive chunks values from the channel, create the final sums, and return the correct values.

Sorting

There is a built-in sort package in Go, but that doesn't have to stop us from implementing some sorting algorithms. In sort.go…

Insertion Sort

Implement an insertion sort that sorts an array slice in-place:

func InsertionSort(arr []float64) { … }

Quicksort

Implement a Quicksort that sorts an array slice in-place:

func QuickSort(arr []float64) { … }

There is a function partition in the provided sort.go file that might be useful.

Tuning Quicksort

Quicksort is actually slower than insertion sort for small arrays: the mechanics of Quicksort only make sense for larger arrays.

Update your Quicksort function so that for slice lengths below insertionSortCutoff, it calls InsertionSort instead of recursing to QuickSort.

The provided benchmark functions will time your Quicksort: adjust insertionSortCutoff to a reasonable value (of which there is a fairly wide range).

The built-in sorting implementation is included in the benchmark: it's noticeably slower that (at least my) Quicksort. I think that it's because the built-in sort promises to be stable, and our Quicksort doesn't. If anybody has an alternate explanation, let Greg know.

Writing Tests

In the provided exer9_test.go, add some test functions that test for correct behaviour in:

• Point.Scale()
• Point.Rotate()
• MeanStddev()

You can (and maybe should?) use the functions from the assert package in your tests.

Submitting

Submit your files through CourSys for Exercise 9.