Functional Problem Solving (CSC 151 2014F) : Assignments
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Due: 10:30 p.m., Tuesday, 4 November 2014
Summary: You will apply the basic and helper recursion patterns to a variety of problems.
Purposes: To practice writing a variety of procedures that perform recursion over lists and numbers. To give you more experience verifying preconditions and writing local procedure bindings.
Collaboration: If you have been assigned to a group, you must work with your assigned partners on this assignment. The partner assignments are available at http://www.cs.grinnell.edu/~rebelsky/Courses/CSC151/2014F/partners/assignment.06.html. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.
Wrapper (Prologue): Individually read through this assignment and make sure that you understand what is required. Then use the form available at http://bit.ly/151hw6pro to indicate (a) how long you think this assignment will take and (b) what you think will be the most challenging aspect of this assignment.
Wrapper (Epilogue): When you are done with the assignment, fill out the form available at http://bit.ly/151hw6epi to indicate (a) how long the assignment took, (b) what the most challenging part of the assignment was, and (c) something important you learned from doing the assignment. If you find that the assignment took much less or much more time than you expected, also include (d) a note as to what might have led to that difference.
Submitting:
Email your answer to <grader-151-01@cs.grinnell.edu>
. The subject of your email
should have the form CSC 151.01 Assignment 6: Exercises in Recursion
and
should contain your answers to all parts of the assignment. Scheme code
should be in the body of the message.
Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.
Your procedures need not verify their preconditions, except as directed in the instructions to particular problems.
Write and document a procedure
(
that, given a list of values as a parameter, computes the sum of the
numeric values in the list. That is, safe-sum
values
)safe-sum
should ignore all non-numeric values.
>
(safe-sum (list 1 2 3))
6
>
(safe-sum (list 3 'a 'b 5))
8
>
(safe-sum (list 'a 'b))
0
a. Write a procedure, (
, that, given a list of real
numbers (including both positive and negative numbers), returns the
value closest to zero in the list. Your solution should use basic recursion.
closest-to-zero
values
)
Hint: Think about how, given two numbers, you determine which is closer to zero.
Note: If there are multiple values equally close to zero, and all are closer than any other value, you may return any of them.
b. Write a second version of closest-to-zero
that uses helper recursion. That is, you should have an additional
helper procedure that takes closest-so-far
and remaining
as parameters.
c. Explain which version of closest-to-zero
you
prefer and why.
Averaging two colors is a fairly simple task: simply average each of the respective red, green, and blue components, as in the following procedure.
;;; Procedure: ;;; irgb-average ;;; Parameters: ;;; irgb1, an integer-encoded RGB color ;;; irgb2, an integer-encoded RGB color ;;; Purpose: ;;; Compute the "average" of two integer-encoded RGB colors. ;;; Produces: ;;; irgb-avg, an integer-encoeded RGB color ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; (irgb-red irgb-avg) is the average of (irgb-red irgb1) and ;;; (irgb-red irgb2) ;;; (irgb-green irgb-avg) is the average of (irgb-green irgb1) and ;;; (irgb-green irgb2) ;;; (irgb-blue irgb-avg) is the average of (irgb-blue irgb1) and ;;; (irgb-blue irgb2) (define irgb-average (lambda (irgb1 irgb2) (irgb-new (quotient (+ (irgb-red irgb1) (irgb-red irgb2)) 2) (quotient (+ (irgb-green irgb1) (irgb-green irgb2)) 2) (quotient (+ (irgb-blue irgb1) (irgb-blue irgb2)) 2))))
We also saw how to average a list of colors in the lab on Recursion Basics. But what if we want to do something slightly different? Given a list of colors, we want averages, but only of neighboring elements in the list.
Write a procedure, (
, that, given a list of colors,
computes a new list of colors, by averaging subsequent pairs of
colors. For example, if the input list is the standard seven
rainbow colors (red, orange, yellow, green, blue, indigo, and violet),
the output list will consist of
a red-orange average, an orange-yellow average, a yellow-green
average, a green-blue average, a blue-indigo average, and an
indigo-violet average.
rgb-averages
colors
)
The length of the resulting list will be one less than the length of the input list.
Write and document a function (
that produces a new list containing alternating elements from the lists
riffle
first
second
)first
and second
.
If one list runs out before the other, then the remaining elements
should appear at the end of the new list.
>
(riffle (list 'a 'b 'c) (list 'x 'y 'z))
'(a x b y c z)
>
(riffle (list 'a 'b 'c) (iota 10))
'(a 0 b 1 c 2 3 4 5 6 7 8 9)
Write and document a procedure, (
, that
extracts element my-list-ref
lst
n
)n
of a list.
Your procedure should verify its preconditions and give helpful error
messages. For example,
>
(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 5)
"indigo"
>
(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 0)
"red"
>
(my-list-ref 3 (list "red" "orange" "yellow" "green" "blue" "indigo" "violet"))
my-list-ref: expected a list as first argument, given 3>
(my-list-ref (list "red" "orange" "yellow" "green" "blue" "indigo" "violet") 15)
my-list-ref: index too large for list
Even though this procedure does the same thing as
list-ref
, you should not use
list-ref
to implement it. Instead, your goal
is to figure out how list-ref
works, which means
that you will need to implement this procedure using recursion.
Hint: When recurring, you will need to simplify both the numeric parameter (probably by subtracting 1) and the list parameter (probably by taking its cdr).
You may recall that in our early work with lists, we built lists of numbers
by using iota
and then using map
to scale the
elements or increment the elements. For example, if wanted a list of
six multiples of five, starting with ten, we might write the following
expression.
> (map (o (l-s + 10) (l-s * 5)) (iota 6)) '(10 15 20 25 30 35)
Now that we know numeric recursion, we can write a recursive procedure that generates such simple arithmetic sequences.
Document and write a procedure, (
, that produces a list in which
the initial element is sequence
start
increment
bound
)start
, each other
element is increment
greater than the
previous element, and all of the elements are strictly less than
bound
.
> (sequence 10 5 37) '(10 15 20 25 30 35)
You must implement sequence
using recursion.
(You may use helper recursion, if you deem it useful to do so.)
You may not use map
or anything similar.
As you've noted, when we're careless with numeric recursion, we sometimes
write procedures that recur forever. Hence,
your sequence
procedure must not only check its
obvious preconditions, it must also ensure that the parameters are such
that it is possible to create a finite sequence with the given parameters.
Define and test a Scheme procedure, (
, that takes a list as
argument and returns a list of two lists, one comprising the elements in
even-numbered positions in the given list, the other comprising the
elements in odd-numbered positions.
unriffle
lst
)
>
(unriffle (list 'a 'b 'c 'd 'e 'f 'g 'h 'i))
'((a c e g i) (b d f h))
>
(unriffle (list))
'(() ())
>
(unriffle (list 'a))
'((a) ())
>
(unriffle (list 'b))
'((b) ())
>
(unriffle (list 'a 'b))
'((a) (b))
Hint: There are many ways to solve this problem. Before writing code, try solving it by hand to develop your algorithm.
We will apply our standard evaluation criteria to this assignment. That is, solutions should be correct, clear, well documented, and tested (either with unit tests or with manual experiments).