6 Homework 4A
Due:
Tuesday, 1/30 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 HW4A assignment on Gradescope. This page has additional information, and allows us to format things nicely.
6.1 Problem 1
Design a function duplicate-element that, given a list of non-negative
integers, if there exists at least one that appears more than once, returns one
of those repeated integers. If there are no duplicates, it should return -1
(since the input list is all positive, this value is easily identifiable). First
write the signature, informal purpose, and formal purpose as
duplicate-element-prop that ensures that the returned element does indeed
appear more than once. If -1 is returned, duplicate-element-prop need not
validate that this was the correct choice. Implement the function (hint: sorting
first might help) and use check-contract with duplicate-element-prop
to ensure your function works. You could also try to write regular unit tests,
but they might be fragile—
6.2 Problem 2
Design a function common-element that, given a list of lists of non-negative integers, if there exists an element common to all of them, returns it, or -1 if there is no such element. Again, first implement a formal purpose statement common-element-prop that checks that the function works (if -1 is returned, common-element-prop need not validate that this was the correct choice), and then implement the function itself. (Hint: while an efficient algorithm might have to be clever, a simple one can look through the first sublist for any element that appears in all other sublists).
6.3 Problem 3
Design a function pair-with-sum that, given a list of integers and a target number, returns either a list with exactly two elements that sum to that target number, or an empty list if there are no two elements that sum to the target. As before, first write a formal purpose pair-with-sum-prop that validates the solution (if an empty list was returned, pair-with-sum-prop need not validate that this was the correct choice), and then write an implementation. (Hint: since you are only matching two elements together, you can proceed through the list, checking each element with all that follow it).