4 Homework 3A
Due:
Tuesday, 1/23 at 9PM
This assignment may be done with an approved PARTNER.
This assignment is entirely AUTOGRADED.
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW3A assignment on Gradescope. This page has additional information, and allows us to format things nicely.
4.1 Problem 1
Design a function, cyclic-shuffle that takes a string and shifts its contents a random number of places i.e., moving a character from the end to the beginning. i.e., "abc" might turn into "cab" or "bca" or "abc" (because there are three characters, so up to three different shifts).
The signature and informal purpose should be straightforward, but you should write a formal purpose in the form of a function cyclic-shuffle-prop that takes a string input and checks that your function did the right thing on it. Hint: notice that "abcabc" contains all three possibilities above.
Once you have that, write the implementation and test it using cyclic-shuffle-prop (think about why it would be hard to test it via normal unit tests).
4.2 Problem 2
The greatest common divisor of two natural numbers is the largest natural that divides both evenly. There is a recursive algorithm, due to Euclid, to calculate this (note that (gcd 0 0) should be 0). In this problem, we’d like you to design a function gcd to calculate this. As before, follow the design recipe, including writing a formal specification gcd-prop that takes two naturals and ensures that gcd indeed returns the greatest common denominator.
Note that the reader of gcd-prop should be able to immediately know that it is correct, so in particular, it should not do the recursive Euclidean algorithm. Instead, it should be a straightforward translation of the informal specification: that the output divides both inputs, and that there isn’t a bigger number that also does so.
Once you have gcd-prop, implement gcd, using gcd-prop to write tests.
4.3 Problem 3
In a list of numbers (or any other elements), a majority element is one that appears more than half the time. In this problem, we want you to design find-majority that takes a list of natural numbers and produces the majority element, if one exists, or -1, if no such element exists. As before, write down the signature, informal purpose, and formal purpose in the form of a function find-majority-prop that takes the input list and ensures that, when find-majority is called, the output is indeed the majority if it returns something other than -1 (note that find-majority-prop does not need to check that there is no majority if -1 is returned: this is a simplification for the sake of the problem).
Next, implement find-majority. We’d suggest looking up the Boyer-Moore majority voting algorithm for a simple way to do it with two accumulator arguments (a counter and candidate element).