Assignment 6 – Exploring recursion

Assigned
Wednesday, Oct 31, 2018
Due
Wednesday, Nov 7, 2018 by 10:30pm
Summary
For this assignment, you will apply your knowledge of recursion to solve a variety of problems that require different kinds of general repetition.
Collaboration
You must work with your assigned partner(s) on this assignment. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Submitting
Email your answers to csc151-01-grader@grinnell.edu. The subject of your email should be [CSC151 01] Assignment 6 and should contain your answers to all parts of the assignment. Please send your scheme code in an attached .rkt file.

Problem 1: Finding the indices of an element

Topics: list recursion

As you know, the (index-of val lst) procedure finds the index of the first instances of val in lst. If val is not in lst, it returns the value -1.

What if we wanted all of the indices, not just the first one? We’d probably have to write our own procedure.

Document and write a recursive procedure, (indices-of val lst), that creates a list of all the position in lst where val appears. If the value does not appear, indices-of should return the empty list.

> (indices-of 'skip (list 'hop 'skip 'and 'jump))
'(1)
> (indices-of 'skip (list 'hop 'skip 'jump 'and 'skip 'again))
'(1 4)
> (indices-of 5 (list 5 4 3 2 1 2 3 4 5))
'(0 8)
> (indices-of "eraser" (list "pencils" "paper" "index cards" "markers" "ball-point pens"))
'()

Note: You may not use list-ref (or index-of) in implementing indices-of.

Problem 2: Riffling lists

Topics: list recursion

Document and write a procedure, (riffle3 first second third), that produces a new list containing alternating elements from the lists first, second, and third. If one list runs out before the others, continue riffling the remaining two lists.

> (riffle3 (list 'a 'b 'c) (list 'p 'q 'r) (list 'x 'y 'z))
'(a p x b q y c r z)
> (riffle3 (list 'a 'b 'c 'd) (list 'e 'f) (list 'g 'h 'i))
'(a e g b f h c i d)
> (riffle3 (list 'a 'b 'c) null (list 'd 'e 'f))
'(a d b e c f)
> (riffle3 (list 'c 'b 'a) (list 'd 'd 'd) (list 'e 'f 'g))
'(c d e b d f a d g)

Problem 3: Generating permutations

Topics: recursion

Given a list of items, it can be useful to know all possible ways the list can be uniquely ordered. A specific ordering of items is called a permutation and the notion appears frequently in mathematics.

Write, but do not document, a procedure called (permutations lst) that takes a list as a parameter returns a list of all possible permutations of the elements of lst. Here are a few example executions of the procedure.

> (permutations (list 1 2))
'((1 2) (2 1))
> (permutations (list 0 1 2))
'((0 1 2) (1 0 2) (1 2 0) (0 2 1) (2 0 1) (2 1 0))
> (permutations (list 'a 'b 'c))
'((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))
> (permutations (list "a" 'b 7))
'(("a" b 7) ("a" 7 b) (b "a" 7) (b 7 "a") (7 "a" b) (7 b "a"))
> (permutations (list "hello"))
'(("hello"))
> (permutations null)
'(())

You will find the following procedure helpful. (You should understand what the procedure does. You need not understand how it achieves its goal.)

;;; Procedure:
;;;   insert-everywhere
;;; Parameters:
;;;   val, a Scheme value
;;;   lst, a list
;;; Purpose:
;;;   Create a new list consisting of the result of inserting `val`
;;;   at every possible location in `lst`.
;;; Produces:
;;;   inserted, a list of lists
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * (length inserted) = (+ 1 (length lst))
;;;   * (list-ref inserted i) = is the result of inserting val before
;;;     the value at position i in lst.
;;; Practica:
;;;    > (insert-everywhere 'a (list 'b))
;;;    '((a b) (b a))
;;;    > (insert-everywhere 'a (list 1 2 3))
;;;    '((a 1 2 3) (1 a 2 3) (1 2 a 3) (1 2 3 a))
;;;    > (insert-everywhere 'a null)
;;;    '((a))
(define insert-everywhere
  (lambda (val lst)
    (if (null? lst)
        (list (list val))
        (cons (cons val lst)
              (map (section cons (car lst) <>)
                   (insert-everywhere val (cdr lst)))))))

How will this procedure help? To compute the permutations of a non-empty list, you make all of the permutations of the cdr of the list, insert the car of the list at each position in each permutation, and then join them all together.

> (insert-everywhere 1 '(2))
'((1 2) (2 1))
> (insert-everywhere 0 '(1 2))
'((0 1 2) (1 0 2) (1 2 0))
> (insert-everywhere 0 '(2 1))
'((0 2 1) (2 0 1) (2 1 0))
> (append (insert-everywhere 0 '(1 2)) (insert-everywhere 0 '(2 1)))
'((0 1 2) (1 0 2) (1 2 0) (0 2 1) (2 0 1) (2 1 0))

Problem 4: Joining sorted lists

Topics: list recursion, sorting

Write but do not document a recursive procedure, (merge-sorted-lists lst1 lst2), that takes as input two lists of real numbers that are ordered from smallest to largest and returns the combination of those two lists, still in sorted order.

You may not use sort in your solution.

> (merge-sorted-lists '(1 5 6 7 22) '(0 2 3 4 7 18 19))
'(0 1 2 3 4 5 6 7 7 18 19 22)
> (merge-sorted-lists '(1 3 5 7) '(2 3 4 5 6))
'(1 2 3 3 4 5 5 6 7)

Problem 5: Generalizing power-of-two

Topics: numeric recursion, generalizing code

The following procedure finds the value of 2^x when x is a positive integer.

(define power-of-two
  (lambda (x)
    (if (= x 0) 1 (* 2 (power-of-two (- x 1))))))

While this procedure is useful in specific situations, we sometimes want to take negative exponents or raise numbers other than two to some power. Make the following improvements to this procedure:

a. Modify the procedure so it will work for negative exponents. Recall than . Include at least four test cases with your code for this part; these do not need to be in a rackunit test suite.

b. Modify the procedure so it takes an additional parameter, the base of the exponent and returns . You will need to rename the procedure and change its signature. Include at least four test cases with your code for this part; these tests do not need to be in a rackunit test suite.

Note: you may not use expt or any other mathematical procedures other than *, /, +, -, and = in your solution to this problem.

Evaluation

We will primarily evaluate your work on correctness (does your code compute what it’s supposed to and are your procedure descriptions accurate); clarity (is it easy to tell what your code does and how it achieves its results; is your writing clear and free of jargon); and concision (have you kept your work short and clean, rather than long and rambly).