Assignment 6 – Exploring recursion

Assigned

Friday, Apr 3, 2020

Due

Thursday, Apr 9, 2020 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 may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Submitting

Email your answers to csc151-02-grader@grinnell.edu. The subject of your email should be [CSC151 02] 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: 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 2: 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 $2^{-x} = \dfrac{1}{2^x}$. 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 $y^x$. 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.

Problem 3: Filtering vectors

Topics: vectors, vector recursion, higher-order procedures, filtering

Document and write a procedure, (vector-filter vec pred?), that creates a new vector which contains only the elements of vec for which pred? holds. The elements should appear in the same order that they do in vec.

In writing this procedure, you may create exactly one new vector. Hence, you will not find it productive to use vector-append. In addition, you may not create any lists. Hence, you will not find it productive to use list->vector or vector->list.

Hint: You may have to iterate the vector twice, once to determine the size of the result vector and once to fill it in. A helper procedure will be useful for that.

> (vector-filter (vector 1 2 3) number?)
'#(1 2 3)
> (vector-filter (vector 1 2 3 'a 'b 'c) number?)
'#(1 2 3)
> (vector-filter (vector 1 'a 2 'v 3 'c) number?)
'#(1 2 3)
> (vector-filter (vector 1 "you" 2 "can" 3 "do" "it") string?)
'#("you" "can" "do" "it")

Problem 4: Selective vector updates

Topics: vector recursion, higher-order programming

Write, but do not document, a procedure, (vector-selective-map! vec pred? proc), that updates all the elements in vec for which pred? holds by applying proc and leaves the other elements the same. That is, vector-selective-map! is like map, but for vectors and for only for some of the members of vec.

> (define numbers (vector 1 2 3 4 5 6 7 8 9))
> (vector-selective-map! numbers odd? square)
> numbers
'#(1 2 9 4 25 6 49 8 81)

Note that the vector can have mixed values. If the vector has mixed values, there may be limits on what predicates will work, as some of the following examples suggest. You can assume that the predicate will work on each element of the list.

> (define stuff (vector 'a 2 "bee" (list "c" 2 3) 15 "more"))
> stuff
'#(a 2 "bee" ("c" 2 3) 15 "more")
> (vector-selective-map! stuff number? square)
> stuff
'#(a 4 "bee" ("c" 2 3) 225 "more")
> (vector-selective-map! stuff (conjoin number? odd?) increment)
> stuff
'#(a 4 "bee" ("c" 2 3) 226 "more")
> (vector-selective-map! stuff
                         (lambda (val) 
                           (and (string? val) (char=? (string-ref val 0) #\b)))
                         string-upcase)
> stuff
'#(a 4 "BEE" ("c" 2 3) 226 "more")
> (vector-selective-map! stuff string? (section substring <> 1))
> stuff
'#(a 4 "EE" ("c" 2 3) 226 "ore")
> (vector-selective-map! stuff odd? square)
. . odd?: contract violation
  expected: integer
  given: "ore"

Note that our implementation of vector-selective-map! runs right to left. Your error message may be different.

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