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

*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`

.

*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)
```

*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))
```

*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)
```

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

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