Exercises

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.

   You may not use any loops or list/set/dictionary/generator comprehensions in your solution. You must use recursion.

   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. 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)
   

3. List manipulation. Write a function add-to-all that takes an item and a list of lists and returns a new list of lists, where each nested list is the result of prepending the first argument to the corresponding nested list in the second input argument.

   > (add-to-all 1 '(() (2) (3 4)))
   ((1) (1 2) (1 3 4))
   > (add-to-all '(foo bar) '((baz) ()))
   (((foo bar) baz) ((foo bar)))
   > (add-to-all 'qux '(((foo bar) baz) ((foo bar))))
   ((qux (foo bar) baz) (qux (foo bar)))
   

4. Merge sort. In this question, we will implement merge sort on lists of integers.

   1. Implement a merge function that given two sorted lists, returns a new sorted list that is the merge of the given lists.

      > (merge '(1 3 8) '(2 4 5))
      (1 2 3 4 5 8)
      

   2. Now implement a split function that given a list, returns a pair of lists consisting of the first and second half of the original list. The two halves should either be the exact same size, or the first half should be exactly one item larger than the second.

      > (split '(4 8 5 3 1 2))
      ((4 8 5) 3 1 2)
      > (split '(4 8 5))
      ((4 8) 5)
      

      You may find the built-in length procedure helpful. You may also find it helpful to write a helper function.

   3. Finally implement a mergesort function that given a list, returns its sorted counterpart.

      > (mergesort '(4 8 5 3 1 2 6 9 7))
      (1 2 3 4 5 6 7 8 9)
      

      Use split and merge in your solution.

Submission

Place your solutions to question 1 in the provided hw1_python.py file, and the solution to the remaining questions in hw1_scheme.scm. Submit hw1_python.py and hw1_scheme.scm to the autograder before the deadline. Be sure to register your partnership on the autograder if you are working with a partner.