1 What is This Assignment’s Purpose?🔗

Sometimes, we have to operate computers in faulty environments, usually caused by physical devices (everything from sensors breaking to devices being miscalibrated to a stream of cosmic rays). This can cause computations to produce faulty answers. In this assignment, we’re going to study that question in a limited setting where we can easily simulate the problem and assess the outcomes.Many thanks to David Ackley! This assignment is entirely due to him. Specifically, we are going to measure robustness: how gracefully an algorithm degrades in the face of faults.

2 Theme Song🔗

BIRDS OF A FEATHER by Billie Eilish

3 Problem Setup🔗

4 Assignment🔗

1. The sorters. A sorter takes a deck and a comparator (honest or faulty) and returns a deck. We’ll name that type as well:

   type Sorter = (Deck, Comparator -> Deck)

   Implement each of the following sorting algorithms as a Sorter. You can look up the algorithms on Wikipedia, but be sure to implement them following the style rules of this course:

   • bubble sort, doing a fixed number of passes (see the termination rule above)—not “until sorted”;

   • insertion sort;

   • selection sort (remove may come in handy);

   • merge sort;

   • quick sort. Partition so that each element is compared to the pivot exactly once. Otherwise, with a faulty comparator, an element can end up in both halves or neither. You may use partition for this—it calls its predicate exactly once per element, which is exactly the property you want.

   By passing the comparator as an argument, we can swap out different comparators without changing the underlying sorting code.

2. Preregistration. Preregister your beliefs. How do you expect the above algorithms to fare? Why? Write down what you think/expect before you continue! You will turn this in later; save it and don’t modify it.

3. The faulty comparator. Write a function that, given a fault rate, produces a comparator with that rate:

   make-noisy-lt :: (Number -> Comparator)

   Use num-random for the coin flips. Because num-random draws from a global source, calling num-random-seed once at the top of a run makes that run reproducible—very handy when debugging a “why did I get a weird graph” moment.

4. The metric. Write

   positional-error :: (Deck -> Number)

   computing \(E\) above.

5. The harness. Put it together:

   average-error :: (Sorter, List<Deck>, Number -> Number)

   The first parameter is a sorter. The second is a list of decks. The third is the fault rate \(p\). The result is the average positional error when that sorter (using a fault-rate-\(p\) comparator) is run on each of those decks.

   Build your list of decks once, and use that same list for every algorithm and every fault rate. That way the comparison is paired: the algorithms all run on exactly the same decks, so a difference you see is due to the algorithm, not the luck of the shuffle. (The number of decks is your number of trials; use enough that the averages are stable.)

   Run this for each fault rate \(p \in \{0.1, 0.2, \dots, 0.9\}\), for each of the sorting algorithms.

6. The more robust variant. A common way to handle unreliable components is by voting: ask the same question several times and take the majority answer. We can apply the same principle here. Write a wrapper that turns any comparator into a more reliable one by calling it \(k\) times and taking the majority vote:

   majority :: (Comparator, Number -> Comparator)

   (Use an odd \(k\) so there are no ties.) Now run your quick sort and merge sort again, but wrapping the noisy comparator in majority with \(k = 5\). Call these quick-maj5 and merge-maj5 and include them in your experiments.

7. The graphs. Use the chart library (import chart as C). To save you the trouble of digging through documentation, here are the commands with placeholders.

   A single series is an x list and a y list:

   # one algorithm's curve: fault rates on x, its errors on y

   C.render-chart(

   C.from-list.line-plot(FAULT-RATES, ERRORS-FOR-ONE-ALGORITHM))

   .title("bubble sort")

   .x-axis("fault rate p")

   .y-axis("mean positional error")

   .display()

   To put every algorithm on one axis, make one line-plot per algorithm, give each a legend, and combine them with render-charts:

   C.render-charts(

   [list:

   C.from-list.line-plot(FAULT-RATES, ERRORS-BUBBLE).legend("bubble"),

   C.from-list.line-plot(FAULT-RATES, ERRORS-QUICK).legend("quick")

   # ... one per algorithm ...

   ])

   .title("sorting robustness")

   .x-axis("fault rate p")

   .y-axis("mean positional error")

   .display()

   A bar chart comparing the algorithms at a single fault rate takes a list of names and a list of values:

   C.render-chart(

   C.from-list.bar-chart(ALGORITHM-NAMES, ERRORS-AT-ONE-RATE))

   .title("error by algorithm at p = 0.1")

   .x-axis("algorithm")

   .y-axis("mean positional error")

   .display()

   Produce at least these three: a per-algorithm curve, the combined summary, and a bar chart at one fault rate (say \(p = 0.1\)). The full chart docs are here if you want to go further—colors, other chart types, and so on. Tip: to drop a chart into your report, right-click the rendered chart image and copy it.

5 Testing🔗

Because the experiments involve a good deal of randomness, you can’t really do much end-to-end testing. But the pieces are very testable, and you should test them:

• Honest sorting. At fault rate \(0\), every sorter must sort perfectly.

• The metric. A sorted deck scores \(0\); a reversed deck scores \(\lfloor n^2/2 \rfloor\); and so on.

• Termination and permutation. Even with a comparator that lies on every call (fault rate \(1\)), each sorter must finish and must return a permutation of its input. Which subset of the properties from Sortacle still apply? Obviously not all, but also not none!

6 Analysis🔗

Please clearly mark and append your preregistration document to your report. There are no “wrong answers” here! We are just curious to see how you thought about this initially.

7 Built-Ins🔗

The sorting algorithms must be your own work: you may use the list helpers above as building blocks, but you should build the actual sorting algorithms yourself, not use ones from libraries. You may, of course, use sort and sort-by for testing.

8 Starter🔗

Starter (opens in a new tab)