CSci 1301: Problem Set 5

Due: Wednesday, November 30th at 11:59pm by e-mail

You are required to write signatures and descriptions for all functions, and also descriptions of all your structures. Additionally, functions, except the world problems, must be tested using check-expect. Write your tests before you write a function (but feel free to add more after it's been written).

The quality of your tests will be graded. Make sure to have enough test cases to demonstrate that the function is correct. I may take points off for a lack of testing (in addition to those taken off for incorrect behavior) if your function doesn't work on particular expected data and there is no test for it. It's much better to leave a test that fails (perhaps in comments) that shows that the function doesn't work on given data and you don't know how to fix it.

Problem 1: Abstract functions I (5 points)

Exercise 250. Write check-expects that represent the functionality you were abstracting over, and at least one check-expect that demonstrates different functionality.

Problem 2: Abstract functions II (15 points)

Important: do not use max or min for these functions. Note that your code may look slightly inefficient; that's ok.

1. Write a recursive function that finds the smallest number in a non-empty list of numbers (your base case should be a one-element list: it returns the only element in the list). Make sure to write check-expects first.
2. Write a recursive function that finds the largest number in a non-empty list of numbers (your base case should be a one-element list: it returns the only element in the list). Make sure to write check-expects first.
3. Write a recursive function that finds that shortest string in a non-empty list of strings (your base case should be a one-element list: it returns the only element in the list). Make sure to write check-expects first.
4. Write a general (abstract) function that consumes a list and a comparison function (i.e. a function on two elements that returns #true or #false, depending on what element is "larger"), and returns the "minimum" element of the list according to that comparison. Write the check-expects first. The first example (with the smallest number) must work when < and a list of numbers are passed to the function, and the second example must work when > and a list of numbers are passed. Think carefully what you need to pass to make the third example above work. You may write a helper function, or use a lambda.
   Make sure you write the most general signature for the abstract function (in particular, check that your signature works for the third example above).
   Write one example of using the abstract function that is not listed above.

Problem 3: Abstract functions III (12 points)

1. Write a function that consumes a list of numbers and returns the first odd number on the list. Make sure to write check-expects first.
2. Write another function that follows the same pattern: takes a list and returns the first element that satisfies some condition.
3. Generalize the functions by adding a parameter for a predicate, such as odd?. Write check-expects first; make sure you are giving the function the most general signature.

Problem 4: Using predefined functions (8 points)

For this exercise you need to use predefined functions in Section 18. You may not write your own recursive functions.

1. Use predefined functions to add all of the x coordinates in a list of positions
2. Use perdefined functions to select all strings that do not start with an "a" or "A" in a list of strings
3. Use predefined functions to create a list of 20 squares (images), in which the first one is 1-by-1 pixel, the second one is 2-by-2, and so on (hint: use build-list)
4. Use a predefined functions to sort a list of strings by length (shortest first)

CSci 1301 course web site.