Solo Assignment C

• Clarifications shown in magenta.

• Dueish: Mon Mar 15 (followed by a 2-day grace period)

• Notes:

  • Lyn is revising the expectation of “dueish” for Solo assignments to be more realistic. Rather than specifying an expected dueish date of 2 days after the assignment is posted, with a 7-day grace period, there will now be an expected dueish date of 7 days after the assignment with a 2-day grace period. This does not change the 9 total days until the end of the grace period, but does emphasize that 7 days is a more realistic target deadline than 2 days!

  • This is a solo assignment. You must complete all parts of this assignment entirely on your own without help from any other person and without consulting any resources other than course materials or Racket documentation. You may ask Lyn for clarification, but not for help.

  • You can do all problems on this assignment based on material you learned for PS3. Be sure to study the solutions to PS3 before doing this assignment.

  • This assignment has 48 solo points.

• How to Start Solo Assignment C

  Follow the instructions in the GDoc CS251-S21-T3 Pset Submission Instructions for creating your SOLO-C Google Doc. Put all written answers and a copy of all code into this SOLO-C GDoc.

• Submission:

  • For all parts of all problems, include all answers (including the small-step derivation and all Racket code) in your SOLO-C GDoc. Please format your big/small-step derivation in Problem 1 and your Racket function definitions in Problems 2 and 3 so that they’re easy to read. Format all derivations and code using a fixed-width font (Courier New or Consolas). You use a small font size if that helps.
  • For Problem 1 (Composition Semantics), include your small-step derivation in your GDoc.
  • For Problem 2 (Using Higher-order List Functions) and Problem 3 (Bean Counting)
    • Be sure that all your new function definitions in yourAccountName-solo-c-functions.rkt also appear in your Google Doc (so that I can comment on them)
    • Drop a copy of your yourAccountName-solo-c-functions.rkt in your ~/cs251/drop/solo-c drop folder on cs.wellesley.edu.

1. Composition Semantics (10 points)

Consider the following Racket functions:

(define curry2 (λ (binop) (λ (v1) (λ (v2) (binop v1 v2))))) 
(define o (λ (f g) (λ (x) (f (g x)))))
(define sub (λ (c d) (- c d)))
(define sq (λ (n) (* n n)))

Use the rules of small-step semantics to show a derviation of all steps in evaluating the expression ((o ((curry2 sub) 7) sq) 2)

As you did in PS3 Problem 1, (1) use curly braces to show the redex in each step and (2) show the justification for each step in square brackets. When expressions are complex, write them on multiple lines, using Racket-style indentation to clarify the structure of the expression. You may want to write your derivations in the Dr. Racket editor, which will help you (1) balance parens and (2) indent expressions properly.

2. Using Higher-order List Functions (28 points)

In this problem you will define several functions using higher-order list functions.

• Define all of your functions in a new file named yourAccountName-solo-c-functions.rkt that you create in Dr. Racket. Copy the following helper function definitions to the beginning of your file:

  (define (map-cons x ys)
    (map (curry cons x) ys))
  
  (define (exists? pred xs)
    (and (not (null? xs))
         (or (pred (first xs))
             (exists? pred (rest xs)))))
      
  (define (foldr-ternop ternop null-value xs)
    (if (null? xs)
        null-value
        (ternop (first xs)
                (rest xs)
                (foldr-ternop ternop null-value (rest xs)))))

  You may use these helper fuctions in your definitions.

• You have seen many of the following functions before in Solo Assignment B in the context of explicit recursion. But in this problem:
  • You must not use explicit recursion on lists in any of your definitions.
  • You must use higher-order list operations (e.g., foldr, foldr-ternop, map)
  • You must not define any functions other than (1) the four helper functions defined above and (2) the seven required functions below.
• Unless otherwise stated in a subproblem, the only built-in Racket list operators you may use in your definitions are: null, null?, cons, car, cdr, list, append, first, second, third, and rest. You may also use any Racket math or logic operators, such as +, max, equal?, etc. You must not use any form of list reversal in any of your solutions.

1. (2 points) Using filter, define a function my-remove that takes two arguments (a value and a list of values) and returns a new list containing all values in the list in their original order except for any values equal? to the specified value. For example:

    > (my-remove 5 '(5 6 5 7 6 8 5 6 7 5))
    '(6 7 6 8 6 7)
    > (my-remove 6 '(5 6 5 7 6 8 5 6 7 5))
    '(5 5 7 8 5 7 5)
    > (my-remove 7 '(5 6 5 7 6 8 5 6 7 5))
    '(5 6 5 6 8 5 6 5)
    > (my-remove 8 '(5 6 5 7 6 8 5 6 7 5))
    '(5 6 5 7 6 5 6 7 5)
    > (my-remove 9 '(5 6 5 7 6 8 5 6 7 5))
    '(5 6 5 7 6 8 5 6 7 5)
    > (my-remove '(1 2) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6))
    '(1 2 (1 2 3) 3 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)
    > (my-remove '(1 2 3) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6))
    '(1 (1 2) 2 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)
    > (my-remove '((1 2) (1 2) (1 2)) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6))
    '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 6)
    > (my-remove 5 '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6))
    '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) ((1 2) (1 2) (1 2)) 6)
    > (my-remove '(0 1) '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6))
    '(1 (1 2) 2 (1 2 3) 3 (1 2) 4 (0 1 2) 5 ((1 2) (1 2) (1 2)) 6)

   Your definition must flesh out the following skeleton:

   (define (my-remove x ys)
     (filter ; predicate goes here
             ys))

2. (3 points) Using foldr, define a recursive function remove-dups that takes one argument (a list of values) and returns a new list containing all values in the list in their original order except that all occurrences of a value equal? to the first occurrence have been removed. For example:

    > (remove-dups '(5 6 5 7 6 8 5 6 7 5))
    '(5 6 7 8)
    > (remove-dups '(1 2 3 4))
    '(1 2 3 4)
    > (remove-dups '(1 (1 2) 2 (1 2 3) 3 (1 2) 1 (0 1 2) 2 ((1 2) (1 2) (1 2)) 1 (1 2 3) 2 (1 2) 3 (0 1) 4))
    '(1 (1 2) 2 (1 2 3) 3 (0 1 2) ((1 2) (1 2) (1 2)) (0 1) 4)

   Notes:

   • Your definition must flesh out the following skeleton:

     (define (remove-dups xs)
       (foldr ; combining function goes here.
              ; null value goes here. 
              xs))

   • You should use my-remove in your definition, but not Racket’s member or any other member-like functions.

   • Other than my-remove, and null?/cons/first/rest, you may not use any helper functions in your definition.

3. (3 points) A length-n prefix of a list is a list containing its first n elements in the same relative order. For example:

   • The length-0 prefix of '(5 8 4) is '()
   • The length-1 prefix of '(5 8 4) is '(5)
   • The length-2 prefix of '(5 8 4) is '(5 8)
   • The length-3 prefix of '(5 8 4) is '(5 8 4)

   Using foldr, define a function prefixes that takes a list as its single argument and returns a list of all of its prefixes ordered from shortest to longest. For example:

    > (prefixes '(5 8 4))
    '(() (5) (5 8) (5 8 4))
    > (prefixes '(2 5 8 4))
    '(() (2) (2 5) (2 5 8) (2 5 8 4))
    > (prefixes '(7 2 5 8 4))
    '(() (7) (7 2) (7 2 5) (7 2 5 8) (7 2 5 8 4))
    > (prefixes (range 0 11))
    '(()
      (0)
      (0 1)
      (0 1 2)
      (0 1 2 3)
      (0 1 2 3 4)
      (0 1 2 3 4 5)
      (0 1 2 3 4 5 6)
      (0 1 2 3 4 5 6 7)
      (0 1 2 3 4 5 6 7 8)
      (0 1 2 3 4 5 6 7 8 9)
      (0 1 2 3 4 5 6 7 8 9 10))

   Your definition must flesh out the following skeleton:

   (define (prefixes xs)
     (foldr ; combining function goes here.
            ; null value goes here. 
            xs))

4. (5 points) Using foldr, define a function sum-max-squaresEvens that takes a list of integers its single argument and returns a triple (i.e., a three-element list) whose three elements are (1) the sum of the numbers in the list; (2) the maximum of the numbers in the list and (3) a list of the squares of all the even numbers in the list (maintaining relative order).

    > (sum-max-squaresEvens '(9 2 8 5 4 7 1 6 3))
    '(45 9.0 (4 64 16 36))
    > (sum-max-squaresEvens '(2 8 5 4 7 1 6 3))
    '(36 8.0 (4 64 16 36))
    > (sum-max-squaresEvens '(8 5 4 7 1 6 3))
    '(34 8.0 (64 16 36))
    > (sum-max-squaresEvens '(5 4 7 1 6 3))
    '(26 7.0 (16 36))
    > (sum-max-squaresEvens '(-9 2 -8 5 4 -7 1 -6 3))
    '(-15 5.0 (4 64 16 36))
    > (sum-max-squaresEvens '(-6 -3 -10 -5 -8))
    '(-32 -3.0 (36 100 64))
    > (sum-max-squaresEvens (append (range 1 101 7) (range 201 0 -2)))
    '(10951 201.0 (64 484 1296 2500 4096 6084 8464))

   Notes:

   • Your definition must flesh out the following skeleton:

     (define (sum-max-squaresEvens ints)
       (foldr ; combining function goes here.
              ; null value goes here. 
              ints))

   • Depending on how you determine the maximum, the result might display as a floating point number (as in 9.0) or as an integer (as in 9).

5. (4 points) Define a skipper of a list L to be a list formed by (possibly) skipping some of the elements in the list, leaving the “kept” elements in the same relative order.

   For example, if L is the list '(b o a t), then:

   • '(b o a t) is the single 4-element skipper of L;
   • '(o a t), '(b a t), '(b o t), '(b o a) are the the 3-element skippers of L that result from removing one element of '(b o a t);
   • '(a t), '(o t), '(o a), '(b t), '(b a), '(b o) are the the 2-element skippers of L that result from removing two elements of '(b o a t);
   • '(b), '(o), '(a), '(t) are the the 1-element skippers of L that result from removing three elements of '(b o a t);
   • '() is the the single 0-element skipper of L that results from removing all four elements of '(b o a t);

   (The above examples use lists with symbols. These are explained in Solo Assignment B, Problem 3e.)

   Using foldr, define a recursive function skippers that returns all of the skippers of a given list in the order suggested by the following examples:

    > (skippers '())
    '(())
    > (skippers '(t))
    '((t) ())
    > (skippers '(a t))
    ; Result has been manually reformatted to highlight the relationship between 
    ; (skippers '(a t)) and (skippers '(t))
    '((a t) (a) 
      (t)   ())
    > (skippers '(o a t))
    ; Result has been manually reformatted to highlight the relationship between 
    ; (skippers '(o a t)) and (skippers '(a t))
    '((o a t) (o a) (o t) (o) 
      (a t)   (a)   (t)   ())
    > (skippers '(b o a t))
    ; Result has been manually reformatted to highlight the relationship between 
    ; (skippers '(b o a t)) and (skippers '(o a t))
    '((b o a t) (b o a) (b o t) (b o) (b a t) (b a) (b t) (b) 
      (o a t)   (o a)   (o t)   (o)   (a t)   (a)   (t)   ())

   Your definition must flesh out the following skeleton:

   (define (skippers xs)
     (foldr ; combining function goes here.
            ; null value goes here. 
            xs))

6. (3 points) A length-n suffix of a list is a list containing its last n elements in the same relative order. For example:

   • The length-0 suffix of '(5 8 4) is '()
   • The length-1 suffix of '(5 8 4) is '(4)
   • The length-2 suffix of '(5 8 4) is '(8 4)
   • The length-3 suffix of '(5 8 4) is '(5 8 4)

   Define a function suffixes that takes a list as its single argument and returns a list of all of its suffixes ordered from longest to shortest. For example:

    > (suffixes '(5 8 4))
    '((5 8 4) (8 4) (4) ())  
    > (suffixes '(2 5 8 4))
    '((2 5 8 4) (5 8 4) (8 4) (4) ())
    > (suffixes '(7 2 5 8 4))
    '((7 2 5 8 4) (2 5 8 4) (5 8 4) (8 4) (4) ())
    > (suffixes (range 1 11))
    '((1 2 3 4 5 6 7 8 9 10)
      (2 3 4 5 6 7 8 9 10)
      (3 4 5 6 7 8 9 10)
      (4 5 6 7 8 9 10)
      (5 6 7 8 9 10)
      (6 7 8 9 10)
      (7 8 9 10)
      (8 9 10)
      (9 10)
      (10)
      ())

   Your definition must flesh out the following skeleton:

   (define (suffixes xs)
     (foldr ; combining function goes here.
            ; null value goes here. 
            xs))

7. (4 points) In this part, you will define a function related to suffixes named weighted-suffixes, which is assumed to take a list of numbers. The result of weighted-suffixes is a list similar to that returned by suffixes except that each nonempty sublist in the result of weighted-suffixes is the result of scaling all numbers in the corresponding nonempty sublist in the result of suffixes by its first element. (The empty sublist in suffixes yields the empty sublist in weighted-suffixes).

   For example, (weighted-suffixes '(7 2 5 8 4)) returns '((49 14 35 56 28) (4 10 16 8) (25 40 20) (64 32) (16) ()) because:

   • (49 14 35 56 28) is the result of scaling (7 2 5 8 4) by 7
   • (4 10 16 8) is the result of scaling (2 5 8 4) by 2
   • (25 40 20) is the result of scaling (5 8 4) by 5
   • (64 32) is the result of scaling (8 4) by 8
   • (16) is the result of scaling (4) by 4
   • () is the sublist in the result of weighted-suffixes that corresponds to the sublist () in the result of suffixes

   Here are more examples of weighted-suffixes, the last two of which illustrate negative numbers:

    > (weighted-suffixes (range 3 8))
    '((9 12 15 18 21) (16 20 24 28) (25 30 35) (36 42) (49) ())
   
    > (weighted-suffixes (range 1 11))
    '((1 2 3 4 5 6 7 8 9 10)
      (4 6 8 10 12 14 16 18 20)
      (9 12 15 18 21 24 27 30)
      (16 20 24 28 32 36 40)
      (25 30 35 40 45 50)
      (36 42 48 54 60)
      (49 56 63 70)
      (64 72 80)
      (81 90)
      (100)
      ())
       
    > (weighted-suffixes '(-2 6 1 -3 -8 4 7 -5))
    '((4 -12 -2 6 16 -8 -14 10)
      (36 6 -18 -48 24 42 -30)
      (1 -3 -8 4 7 -5)
      (9 24 -12 -21 15)
      (64 -32 -56 40)
      (16 28 -20)
      (49 -35)
      (25)
      ())
   
    > (weighted-suffixes (range -3 4))
    '((9 6 3 0 -3 -6 -9) (4 2 0 -2 -4 -6) (1 0 -1 -2 -3) (0 0 0 0) (1 2 3) (4 6) (9) ())

   Use foldr-ternop to define weighted-suffixes. Your definition must flesh out the following skeleton:

   (define (weighted-suffixes nums)
     (foldr-ternop ; ternary combining function goes here.
                   ; null value goes here. 
                   nums))

   Note: Recall that you may not define any new helper functions. And you must not use the suffixes function you defined above. But you may use map.

8. (4 points) Using foldr-ternop, define a function keepBiggerThanSomeFollowing that takes a list of numbers and returns a new list that keeps all numbers (in their same relative order in the input list) that are bigger than some number that follows them in the input list. It never keeps the last number.

    > (keepBiggerThanSomeFollowing  '(6 0 4 7 1 5 3 9 8 2))
    '(6 4 7 5 3 9 8)
   
    > (keepBiggerThanSomeFollowing '(9 5 8 4 7 3 6 1 2))
    '(9 5 8 4 7 3 6)
   
    > (keepBiggerThanSomeFollowing (range 0 100))
    '()
   
    > (keepBiggerThanSomeFollowing (append (range 0 100) (range 80 90)))
    '(81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99)
   
    > (keepBiggerThanSomeFollowing '(8))
    '()
   
    > (keepBiggerThanSomeFollowing '())
    '()

   Flesh out the following definition of a function skeleton that uses foldr-ternop to define keepBiggerThanSomeFollowing. You must use exactly this skeleton:

   (define (keepBiggerThanSomeFollowing nums)
     (foldr-ternop ; ternary combining function goes here.
                   ; null value goes here. 
                   nums))

   Note: You may use the following exists? function from PS3 that you defined at the top of your yourAccountName-solo-c-functions.rkt file.

   (define (exists? pred xs)
     (and (not (null? xs))
          (or (pred (first xs))
              (exists? pred (rest xs)))))

3. (10 points) Bean Counting

In this problem, you will define a function (beans b j) that satisfies the following specification:

Assume that b is a non-negative integer and that j is a positive integer. Given b beans and and a row of j jars, (beans b j) returns a sorted list of all configurations whereby all b beans are distributed among the j jars. Each configuration should be a list of length j whose elements are integers between 0 and b and the sum of whose elements is b. The returned list should be ordered lexicographically (i.e., in dictionary order).

It is possible to define the beans function using a combination of explicit recursion and foldr by fleshing out this skeleton:

(define (beans b j)
  (if (= j 1)
      ;; Base case goes here
      (foldr (lambda (beansInFirstJar allConfigsWithMoreBeansInFirstJar)
               ;; Body of combiner function goes here.
               ;; You *should* explicitly call beans recursively once in this body. 
               )
             ;; null value goes here
             (range 0 (+ b 1)))))

Your task is to define the beans function by fleshing out the above skeleton so that it satisfies the above specification and has the same behavior as the sample invocations below. (Some results have been manually reformated to fit on fewer lines and to also suggest a divide/conquer/glue strategy for a solution. Racket will not print your results using this special formatting.)

    > (beans 0 1)
    '((0))

    > (beans 0 2)
    '((0 0))

    > (beans 0 3)
    '((0 0 0))

    > (beans 0 4)
    '((0 0 0 0))

    > (beans 1 1)
    '((1))

    > (beans 1 2)
    '((0 1) (1 0))

    > (beans 1 3)
    '((0 0 1) (0 1 0) (1 0 0))

    > (beans 1 4)
    '((0 0 0 1) (0 0 1 0) (0 1 0 0) (1 0 0 0))

    > (beans 2 1)
    '((2))

    > (beans 2 2)
    '((0 2) (1 1) (2 0))

    > (beans 2 3)
    '((0 0 2) (0 1 1) (0 2 0) (1 0 1) (1 1 0) (2 0 0))

    > (beans 2 4)
    '((0 0 0 2) (0 0 1 1) (0 0 2 0) (0 1 0 1) (0 1 1 0) (0 2 0 0) 
      (1 0 0 1) (1 0 1 0) (1 1 0 0) 
      (2 0 0 0))

    > (beans 3 1)
    '((3))

    > (beans 3 2)
    '((0 3) (1 2) (2 1) (3 0))

    > (beans 3 3)
    '((0 0 3) (0 1 2) (0 2 1) (0 3 0) 
      (1 0 2) (1 1 1) (1 2 0) 
      (2 0 1) (2 1 0) 
      (3 0 0))

    > (beans 3 4)
    '((0 0 0 3) (0 0 1 2) (0 0 2 1) (0 0 3 0) 
      (0 1 0 2) (0 1 1 1) (0 1 2 0) 
      (0 2 0 1) (0 2 1 0) 
      (0 3 0 0)
      (1 0 0 2) (1 0 1 1) (1 0 2 0)
      (1 1 0 1) (1 1 1 0)
      (1 2 0 0)
      (2 0 0 1) (2 0 1 0)
      (2 1 0 0)
      (3 0 0 0))

    > (beans 4 1)
    '((4))

    > (beans 4 2)
    '((0 4) (1 3) (2 2) (3 1) (4 0))

    > (beans 4 3)
    '((0 0 4) (0 1 3) (0 2 2) (0 3 1) (0 4 0) 
      (1 0 3) (1 1 2) (1 2 1) (1 3 0) 
      (2 0 2) (2 1 1) (2 2 0) 
      (3 0 1) (3 1 0) 
      (4 0 0))

    > (beans 4 4)
    '((0 0 0 4) (0 0 1 3) (0 0 2 2) (0 0 3 1) (0 0 4 0)
      (0 1 0 3) (0 1 1 2) (0 1 2 1) (0 1 3 0)
      (0 2 0 2) (0 2 1 1) (0 2 2 0)
      (0 3 0 1) (0 3 1 0)
      (0 4 0 0)
      (1 0 0 3) (1 0 1 2) (1 0 2 1) (1 0 3 0)
      (1 1 0 2) (1 1 1 1) (1 1 2 0)
      (1 2 0 1) (1 2 1 0)
      (1 3 0 0)
      (2 0 0 2) (2 0 1 1) (2 0 2 0)
      (2 1 0 1) (2 1 1 0)
      (2 2 0 0)
      (3 0 0 1) (3 0 1 0)
      (3 1 0 0)
      (4 0 0 0))

    > (beans 5 1)
    '((5))

    > (beans 5 2)
    '((0 5) (1 4) (2 3) (3 2) (4 1) (5 0))

    > (beans 5 3)
    '((0 0 5) (0 1 4) (0 2 3) (0 3 2) (0 4 1) (0 5 0)
      (1 0 4) (1 1 3) (1 2 2) (1 3 1) (1 4 0)
      (2 0 3) (2 1 2) (2 2 1) (2 3 0)
      (3 0 2) (3 1 1) (3 2 0)
      (4 0 1) (4 1 0)
      (5 0 0))

    > (beans 5 4)
    '((0 0 0 5) (0 0 1 4) (0 0 2 3) (0 0 3 2) (0 0 4 1) (0 0 5 0)
      (0 1 0 4) (0 1 1 3) (0 1 2 2) (0 1 3 1) (0 1 4 0)
      (0 2 0 3) (0 2 1 2) (0 2 2 1) (0 2 3 0)
      (0 3 0 2) (0 3 1 1) (0 3 2 0)
      (0 4 0 1) (0 4 1 0)
      (0 5 0 0)
      (1 0 0 4) (1 0 1 3) (1 0 2 2) (1 0 3 1) (1 0 4 0)
      (1 1 0 3) (1 1 1 2) (1 1 2 1) (1 1 3 0)
      (1 2 0 2) (1 2 1 1) (1 2 2 0)
      (1 3 0 1) (1 3 1 0)
      (1 4 0 0)
      (2 0 0 3) (2 0 1 2) (2 0 2 1)  (2 0 3 0)
      (2 1 0 2) (2 1 1 1) (2 1 2 0)
      (2 2 0 1) (2 2 1 0)
      (2 3 0 0)
      (3 0 0 2) (3 0 1 1) (3 0 2 0)
      (3 1 0 1) (3 1 1 0)
      (3 2 0 0)
      (4 0 0 1) (4 0 1 0)
      (4 1 0 0)
      (5 0 0 0))

Notes:

• Define your beans function at the bottom of the file yourAccountName-solo-c-functions.rkt that you created in Problem 2.

• As usual, you should use divide/conquer/glue as your problem-solving strategy. Don’t attempt to write any code until you understand your strategy.

• Don’t forget the very powerful notion of “wishful” thinking, in which you apply a recursive function to smaller versions of the same problem and combine their results. Study the examples carefully to see how the result of a call to marbles is stitched together from the results of calls to “smaller” versions of marbles.

• The body of the combiner argument to foldr should explicitly call the beans function recursively once.

  • What should the arguments to this recursive call be?

  • How should the configurations returned by this recursive call to beans be combined with the configurations in the list allConfigsWithMoreBeansInFirstJar

• You may use the map-cons function from Problem 2 in the definition of beans.

• Here are things you should not do in your beans definition:

  • you should not generate duplicate lists that you later filter out
  • you should not check for duplicates before adding an element to the result list.
  • you should not reverse any lists
  • you should not sort any lists
  • you should not use an iterative strategy; use a recursive strategy instead by fleshing out the exact skeleton presented above.