Homework 2

Due Friday, Feb 12, 2021 at 8pm ET

A PDF version of this document is located here.

Use the following commands to download and unpack the distribution code:

$ wget https://amirkamil.github.io/homework/hw2/starter-files.tar.gz
$ tar xzf starter-files.tar.gz

You may work alone or with a partner. Please see the syllabus for partnership rules. As a reminder, you may not share any part of your solution outside of your partnership. This includes code, test cases, and written solutions.

The Python distribution code for this assignment, as well as the examples below, uses doctests to document examples and to provide a minimal set of test cases. You can run the tests from the command line as follows:

$ python3 -m doctest -v hw2_python.py

For the Scheme code in this assignment, you must write it in R5RS-compliant Scheme. The officially supported interpreter for this course is Racket[1]. Make sure you choose to run R5RS Scheme. If you use the DrRacket interface, select Language -> Choose Language -> Other Languages -> R5RS from the menu. You may need to click on Run before the interface will show that R5RS is chosen.

[1]	On MacOS, you can install Racket with Homebrew (brew install --cask racket).

You may also use the plt-r5rs command-line interpreter included in the Racket distribution, which is also available on CAEN after running the following command:

module load racket

To run with plt-r5rs on your own machine, you may need to add the bin directory under your Racket installation to your path[2] so that the plt-r5rs executable can be located.

[2]	Instructions: Windows; MacOS (e.g. export PATH="/Applications/Racket v7.4/bin:$PATH" for a Racket 7.4 installation on MacOS; this is unnecessary if you installed Racket with Homebrew)

The autograder for this assignment will also use plt-r5rs.

1. Recursion. Write a recursive function in Python that divides an input sequence into a tuple of smaller sequences that each contain 4 or 5 elements from the original sequence. For example, an input sequence of 14 elements should be divided into sequences of 4, 5, and 5 elements. Use as few 5-element sequences as necessary in the result, and all 5-element sequences should be at the end. Finally, preserve the relative ordering of elements from the original sequence, and subsequences should be of the same type as the input sequence.

   Hint: You may assume that the input sequence has length at least 12. Think carefully about how many base cases you need, and what they should be. Use slicing to form subsequences, which preserves the type.

   def group(seq):
       """Divide a sequence of >= 12 elements into groups of 4 or 5.
   
       Groups of 5 will be at the end. Returns a tuple of sequences,
       each corresponding to a group, with type matching that of the
       input sequence.
   
       >>> group(range(14))
       (range(0, 4), range(4, 9), range(9, 14))
       >>> group(tuple(range(17)))
       ((0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15, 16))
       """
       # add your solution below
   

2. Higher-order functions. Define a function make_accumulator in Python that returns an accumulator function, which takes one numerical argument and returns the sum of all arguments ever passed to the accumulator. Do not define any classes for this problem.

   def make_accumulator():
       """Return an accumulator function.
   
       The accumulator function takes a single numeric argument and
       accumulates that argument into a running total, then returns
       total.
   
       >>> acc = make_accumulator()
       >>> acc(15)
       15
       >>> acc(10)
       25
       >>> acc2 = make_accumulator()
       >>> acc2(7)
       7
       >>> acc3 = acc2
       >>> acc3(6)
       13
       >>> acc2(5)
       18
       >>> acc(4)
       29
       """
       # add your solution below
   

3. Scheme and recursion. Write a recursive function interleave that takes two lists and returns a new list with their elements interleaved. In other words, the resulting list should have the first element of the first list, the first of the second, the second element of the first list, the second of the second, and so on. If the two lists are not the same size, then the leftover elements of the longer list should still appear at the end.

   > (interleave '(1 3) '(2 4 6 8))
   (1 2 3 4 6 8)
   > (interleave '(2 4 6 8) '(1 3))
   (2 1 4 3 6 8)
   > (interleave '(1 3) '(1 3))
   (1 1 3 3)