Fundamentals of Computer Science I: Media Computing (CS151.02 2007F)
Primary: [Front Door] [Glance] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings] [Reference]
Reference: [Scheme Report (R5RS)] [Scheme Reference] [DrScheme Manual]
Related Courses: [CSC151.01 2007F (Davis)] [CSC151 2007S (Rebelsky)] [CSCS151 2005S (Stone)]
Summary: In this laboratory, you will further explore issues of deep recursion introduced in the reading on pairs and pair structures and continued in the reading on deep recursion.
a. Make sure that you have the reading on pairs and pair structures and the reading on deep recursion open in separate tabs and windows.
b. Make sure that you have a piece of paper and writing instrument handy.
Recall that a list is a data structure defined recursively as follows:
In the reading on pairs and pair structures, the section entitled
“Recursion with Pairs” includes a procedure that works
on “number trees”, nested structures built with the
pair
procedure.
Write a recursive definition for number trees, trees built from only numbers and cons cells, similar to that for lists.
Using your recursive definition of number
trees from the previous problem, write a procedure,
(number-tree? val)
that returns true
if val is a number tree and false otherwise.
Consider again the sum-of-number-tree
procedure from the
reading, reproduced here.
;;; Procedure: ;;; sum-of-number-tree ;;; Parameters: ;;; ntree, a number tree ;;; Purpose: ;;; Sums all the numbers in ntree. ;;; Produces: ;;; sum, a number ;;; Preconditions: ;;; ntree is a number tree. That is, it consists only of numbers ;;; and cons cells. ;;; Postconditions: ;;; sum is the sum of all numbers in ntree. (define sum-of-number-tree (lambda (ntree) (if (pair? ntree) (+ (sum-of-number-tree (car ntree)) (sum-of-number-tree (cdr ntree))) ntree)))
a. Verify that sum-of-number-tree
works as
advertised on a single number.
b. Verify that sum-of-number-tree
works as
advertised on a pair of numbers.
c. Verify that it works as advertised on the first example.
>
(sum-of-number-tree (cons (cons (cons 0 1) (cons 2 3)) (cons (cons 4 5) (cons 6 7))))
d. What do you expect sum-of-number-tree
to return
when given (cons 10 11)
as a parameter? Verify your
answer experimentally.
e. What do you expect sum-of-number-tree
to return when
given the empty list as a parameter? Verify your answer experimentally.
f. What do you expect sum-of-number-tree
to return when
given (list 1 2 3 4 5)
as a parameter? Verify your answer
experimentally.
a. What preconditions should sum-of-number-tree
have?
b. Use the number-tree?
predicate from earlier
to rewrite sum-of-number-tree
so that it reports an
appropriate error if its preconditions are not met.
c. Some programmers consider it inappropriate to scan a tree twice,
once to make sure that it's valid and once to compute a value based on
the tree. Rewrite sum-of-number-tree
so that it checks
for and reports errors only when it is at one of the non-pair values.
a. Define and test a procedure named
cons-cell-count
that takes any Scheme value and
determines how many boxes would appear in its box-and-pointer diagram.
(The data structure that is represented by such a box, or the region
of a computer's memory in which such a structure is stored is called a
cons cell. Every time the cons
procedure is used, explicitly or implicitly, in the construction of
a Scheme value, a new cons cell is allocated, to store information
about the car and the cdr. Thus cons-cell-count
also
tallies the number of times cons
was invoked during the
construction of its argument.)
For example, the structure in the following box-and-pointer
diagram contains seven cons-cells, so when you apply
cons-cell-count
to that structure, it should
return 7. On the other hand, the string "sample"
contains
no cons-cells, so the value of (cons-cell-count "sample")
is 0.
In answering this question, you should consider whether each value, in
turn, is a pair using the pair?
predicate.
b. Use cons-cell-count
to find out how many cons
cells are needed to construct the list
(0 (1 (2 (3 (4)))))
See the notes at the end of the lab if you have trouble creating that list.
c. Draw a box-and-pointer diagram of this list to check the answer.
Recall the render-color-tree
from the
reading.
a. Add render-color-tree
to your definitions window.
b. Create a new 200x200 image named canvas
.
c. What effect do you expect the following instruction to have?
>
(render-color-tree color.blue canvas 0 0 200 200)
d. Check your answer experimentally.
e. What effect do you expect the following instruction to have?
>
(render-color-tree (cons color.black color.red) canvas 0 0 200 200)
f. Check your answer experimentally.
g. What effect do you expect the following instruction to have?
>
(render-color-tree (cons (cons color.green color.yellow) color.orange) canvas 0 0 200 200)
h. Check your answer experimentally.
i. Create a color tree that you might be able to render in some interesting fashion.
j. Rewrite render-color-tree
so that it splits the
image vertically rather than horizontally.
k. Rewrite render-color-tree
so that it randomly
chooses between splitting the image vertically and horizontally.
l. What do you expect to have happen if you apply your new version to the following color tree?
> (define red-black (cons (cons (cons color.red (cons color.black color.red)) (cons color.black (cons color.red color.black))) (cons color.red (cons color.black color.red))))
m. Check your answer experimentally.
n. What do you expect to have happen if you apply it again?
o. Check your answer experimentally.
p. Write a version of render-color-tree that alternates between splitting the image vertically and horizontally.
q. Write a procedure that, given a list of colors and a maximum depth, randomly generates a color tree. Render your trees to see what they look like!
One potentially interesting way to experiment with color trees is to have a procedure build those trees. How? We might provide the procedure with an intended size of the tree. If the number of colors is 1, we simply return a randomly-selected color. If the number of colors is 2, we cons together two trees of size 1. Otherwise, we pick a random size for the left subtree (the size should be at least 1 and strictly less than the intended size of the whole tree). We then recursively build a tree of that size and another tree of an appropriate size and then cons them together.
a. Using this technique, write a procedure, (
, that randomly builds a black and white tree of the appropriate size.
random-bw-tree
size
)
b. Using this technique, write a procedure, (
, that builds a random color tree of the desired size, randomly selecting the color from the list random-color-tree
size
colors
)colors
.
Create a new version of render-color-tree
that
has an extra parameter, vsplit?
, a Boolean value. If the
Boolean is true, when render-color-tree
should
split the area vertically (as it currently does). If the Boolean is
false, render-color-tree
should split the area
horizontally. In both cases, the recursive calls should negate that
Booelan value.
If you find that you have extra time, you might want to attempt one or more of the following problems.
As you may recall, a tree is either (a) a non-pair value or (b) the cons of two trees. In the reading, you saw a procedure that counted the number of values in a tree. In this lab, you wrote a procedure that counted the number of cons cells (pairs) in a tree. What is the relationship between the numbers returned by those two procedures?
a. Write a procedure, (color-tree.contains? ctree color)
, that
determines whether color
appears anywhere in
ctree
.
b. Rewrite the procedure to determine if a color nearby to color
appears somewhere in ctree
. (You might say that two colors
are nearby if their red, green, and blue components all differ by less
than sixteen.)
If, for some reason, you are having trouble creating the list
(0 (1 (2 (3 (4)))))
try
(list 0 (list 1 (list 2 (list 3 (list 4)))))
Primary: [Front Door] [Glance] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings] [Reference]
Reference: [Scheme Report (R5RS)] [Scheme Reference] [DrScheme Manual]
Related Courses: [CSC151.01 2007F (Davis)] [CSC151 2007S (Rebelsky)] [CSCS151 2005S (Stone)]
Copyright © 2007 Janet Davis, Matthew Kluber, and Samuel A. Rebelsky. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.