2 Homework 3
This assignment is due Thursday, 1/23 by MIDNIGHT
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW3 assignments on Gradescope. This page has additional information, and allows us to format things nicely.
2.1 Problem 1
The greatest common divisor (GCD) of two natural numbers is the largest natural that divides both evenly. Design a function called common-divisors that takes two naturals and returns a sorted list of all their common divisors. Using common-divisors, write a function called gcd-ref that returns the GCD of two numbers. (Note (gcd-ref 0 0) is 0).
There is a clever algorithm, due to Euclid, that calculates GCD. Look up the definition of Euclid’s algorithm online and design a function gcd that calculates GCD using it. 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 divisor according to the reference implementation gcd-ref.
NOTE: the autograder will only be checking gcd (i.e., the efficient algorithm) and gcd-prop; the suggestion to implement gcd-ref is in order to help writing gcd-prop, but if you want to organize it in another way, you are welcome to.
2.2 Problem 2
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).
2.3 Problem 3
Design a function exclusive-range? that takes three integers, lo, hi, and n, and returns #t if n is between lo and hi, and #f if it is either equal to them or outside the range.
Use check-contract to ensure that your function satisfies the contract you gave it.
Next write a function exclusive-range?-prop that takes two integers, lo and hi, picks a random number between them, and ensures that exclusive-range? always returns #t. If it is passed input where (>= (add1 lo) hi), you can just have it return #t. Ensure that this works using check-contract (note that, as a property that should always hold, it should return True).
2.4 Problem 4
Define a contract Odd for odd integers. Use that to design a function double-plus1 which takes a number, doubles it and adds 1. It should take in and produce Odd numbers. Verify that it works using check-contract.
2.5 Problem 5
Define a predicate divisible-by-3-or-5? that takes an integer and checks whether it is divisible by either 3 or 5. Use check-contract to make sure it satisfies the contract you give it. Then use it to define a contract Divis3Or5. Then design a function divide-3-or-5 that takes an integer and if it is divisible by 3 or 5, returns the same number; otherwise it should return 0. The output type of your function should be Divis3Or5, and you should confirm your function satisfies its contract with check-contract.