6.7
Assignment 17
Programming Language ISL+
Due Date Thurs 3/23 at 11:59pm
Possible Points 41
Purpose To use generative recursion to solve complex problems.
Graded Exercises
Exercise 1 Design the function slice which takes a list and a positive integer i and slices the list into segments of length i (with the last one possibly being shorter). For example, (slice '(a b c d e) 2) should return '((a b) (c d) (e)). Solve this problem with generative recursion.
(define-struct vector [length lookup]) ; A Vector is a (make-vector Natural [Natural -> Number]) ; and represents indexed numbers (where indices go from 0 up to and not including the length)
The following problem refers to monotonically increasing vectors. For any monotonically increasing
vector v, (<= ((vector-lookup v) i) ((vector-lookup v) (add1 i))) will always be
true for all natural numbers i such that (< i (sub1 (vector-length v))) is true.
Exercise 2 Design the function find-root which takes a monotonically increasing vector and outputs the index that corresponds to the leftmost 0. If there is no such index, output #false. Use binary search to make this efficient.