Com S 227 --- Introduction to Computer Programming
HOMEWORK 8: VECTORS
(File $Date: 1993/12/02 15:41:42 $)
Due: (((1-6 8) (Dec 1)) ((9-16 17-22 23-29) (Dec 3)) ; many are sugg. practice
((all extra credit problems) (Dec 3)))
In chapter 9 (we skipped chapter 8), you will learn how to write in
the imperative style, and also in a ``mostly functional'' style
that builds on the techniques of chapter 7. This mostly functional style
has important benefits for parallel processing and productive programming.
We also give a few examples from Physics in this homework, but don't worry,
the physics will all be explained in the problems.
Our treatment in this chapter will start out differently than in chapter 9
of the book. Pay attention to the directions in the problems and in
lectures (see also /home/cs227/slides/vectors.slides).
In particular, we will be using a different set of basic procedures for
vectors than the ones in chapter 9. The procedures we consider basic are:
vector, make-vector, vector?, vector-length, vector-ref, and vector-set!.
These are all built-in to Scheme. (The reason for doing this is so that
you can see how vector-generator emerges as the abstraction of other
procedures, much like flat-recur emerges as the abstraction of list
procedures in chapter 7. Last semester this seemed like it would make more
sense, and Springer and Friedman agree.) Another difference is that we won't
spend a lot of time trying (and failing) to implement vectors, as on pages
278-281.
A convention used in the problems below is that the ith element of a
mathematical vector value is written as a_i. For example, in the vector
a = <3.2 9.6 7.1>, we have a_0 = 3.2, a_1 = 9.6, and a_2 = 7.1.
Sometimes we will write
``a = , for i = 0, ..., n-1''
when the particular values are not important. This is a vector of length n,
having elements a_0, a_1, a_2, a_3, ..., a_{n-1}.
All the directions from homework 2 apply to this homework.
In particular, remember to hand in labeled printouts for procedures,
and transcripts showing your testing.
(LECTURE) IMPERATIVE PROGRAMMING WITH THE BASIC PROCEDURES FOR VECTORS
This material is what is not in the book.
In this section, you should *NOT* use vector-generator.
The point is to learn how to do what vector-generator does for you
(which will be needed to program in certain languages like BASIC
that lack adequate abstraction mechanisms).
The program vector-copy in problem 3 below shows the general pattern
for your code in this section.
1. (0 points; suggested practice)
Play with the basic procedures for vectors:
vector, make-vector, vector?, vector-length, vector-ref,
and vector-set! on the computer.
Also use ``eq?'' and quoted vectors like '#(1 2 3).
2. (0 points; suggested practice)
Design equations for vectors that relate make-vector to vector,
the quoted form to vector, and say what vector?, vector-length, vector-ref,
and vector-set! do for vectors.
3. (10 points)
Consider the following procedure.
(define vector-copy ; TYPE: (-> ((vector T)) (vector T))
(lambda (v)
; ENSURES: result is a new vector that has the same value as v
(let ((len (vector-length v)))
(let ((vec (make-vector len)))
(letrec
((init! ; TYPE: (-> (natural) void)
(lambda (i)
; REQUIRES: i < len
; for all 0 <= j < i:
; (vector-ref v j) = (vector-ref vec j)
; MODIFIES: vec
; EFFECT: put the elements of v into vec, start at i
(if (< i len)
(begin
(vector-set! vec i (vector-ref v i))
(init! (add1 i)))))))
(init! 0))
vec))))
The code for this is in the file "/home/cs227/homework/vector-copy.ss"
on Vincent. Load this, or type in the above, and experiment to answer
the following questions.
a. What is the result of (vector-copy '#(1 2 3))?
b. For this and the following parts, consider the following definitions.
(define my-vec '#(1 2 3))
(define my-copy1 (vector-copy my-vec))
(define my-copy2 (vector-copy '#(1 2 3)))
(define my-copy3 my-vec)
What is the result of (eq? my-vec my-copy1)?
c. What is the result of (eq? my-vec my-copy2)?
d. What is the result of (eq? my-vec my-copy3)?
e. What is the result of (equal? my-vec my-copy1)?
f. What is the result of
(begin
(vector-set! my-vec 1 99.3)
(vector-ref my-copy3 1))
g. What is the result of
(begin
(vector-set! my-vec 1 99.3)
(vector-ref my-copy1 1))
h. The following code is supposed to implement eq? for vectors.
Fill in the blanks so that it acts the same as eq? does for vector
arguments.
(define eq?-for-vectors ; TYPE: (-> ((vector T) (vector S)) boolean)
(lambda (v1 v2)
; REQUIRES: special-symbol-for-eq?-for-vectors is not the 0th
; element of v2.
; ENSURES: result is the same as (eq? v1 v2)
(if (and (zero? (vector-length v1)) (zero? (vector-length v2)))
(eq? ______ _______)
(let ((v1-zeroth-elem (vector-ref v1 0)))
(vector-set! v1 0 'special-symbol-for-eq?-for-vectors)
(if (eq? (vector-ref v2 0) 'special-symbol-for-eq?-for-vectors)
(begin
(vector-set! v1 0 ___________________)
__________) ; write #t or #f to the left
(begin
(vector-set! v1 0 ___________________)
___________)))))) ; write #t or #f to the left
i. What happens in vector-copy if you take out the LET that defines len
and replace each occurrence of len in vector-copy with (vector-length v)?
j. What happens in vector-copy if you take out the LET that defines vec
and replace each occurrence of vec in vector-copy with the expression
(make-vector (vector-length v))?
4. (8 points)
In physics, one often uses vectors of 3 numbers to represent
locations in space, or forces etc. that are directed in space.
The number 3 is special because our universe has 3-dimensional space,
where the 3 directions are called x, y, and z. In physics,
such vectors are so common they are usually just called ``vectors''.
For example, the laws of mechanics are summarized by
the vector equation:
F = m * a
where F = is a vector of 3 numbers, representing
a force of a certain magnitude directed in space, called the force vector,
``m'' is the mass, and a = is the acceleration vector.
Write a procedure, ``force'', that takes a number, m,
a vector of numbers, ``a'', and returns a new vector of numbers,
whose value is
in the case where a = . Don't mutate the arguments.
For example,
(force 3.0 (vector 5.2 3.1 8.7)) ==> #(15.6 9.3 26.1)
(force 72 (vector -8.2 -3.14 -32.0)) ==> #(-590.4 -226.08 -2304.)
Note that your answers will not match these exactly, due to the
approximations of Scheme's inexact (floating point) numbers, but that is
okay. By the way, Dr. Crusher (of Star Trek the Next Generation)
wants you to be sure that she can use your program
for beings that live in more than 3 dimensions. For example,
(force 3.0 (vector 5.2 3.1 8.7 4. 5.)) ==> #(15.6 9.3 26.1 12. 15.)
Do not use vector-generator, but write ``force'' in the style of
vector-copy in problem 3 above.
5. (5 points)
Define a procedure vec- that takes two vectors ``a'' and ``b'' as
arguments and returns a new vector vector whose value is
, for i = 0, ..., n-1.
when the values of ``a'' and ``b'' are given by
a = , for i = 0, ... ,n-1,
and b = , for i = 0, ... , n-1.
You may assume that ``a'' and ``b'' have the same length.
For example,
(vec- (vector 1 2 3 4) (vector 0 1 2 3)) ==> #(1 1 1 1)
Do not use vector-generator, but write ``vec-'' in the style of
vector-copy in problem 3 above. Don't mutate the arguments.
6. (10 points)
The ``fields'' discussed in physics can be thought of as
curried vector functions. For example, to find the
gravitational field generated by some mass, you give the function the mass,
and get a function that takes a radius vector,
and returns a function that takes a mass and gives a (new) force vector.
That is, the type of a gravitational field procedure would be
(-> (mass) (-> (radius-vector) (-> (mass) (-> (force-vector)))))
Here mass is a type of numbers, and both radius-vector and force-vector
are (3-element in earth-based physics) vectors
of numbers (presumably in units of length and force, respectively).
Write a procedure ``grav-field'' that has the above type, and such that
(grav-field m1) is the gravitational field produced by m1.
(This can be thought of as associating to each location in space
and to each mass placed at that location, a force vector.)
That is,
(((grav-field m1) r) m2)
= <-G*m1*m2/(r_x)^2, -G*m1*m2/(r_y)^2, -G*m1*m2/(r_z)^2>
where the value of the radius vector r = .
and G is the universal gravitational constant.
You can assume that the MKS (or SI) system is used for all dimensions,
and thus that G = 6.670e-11 (with units N*m^2/kg^2).
(Don't worry if you don't understand that last sentence;
just use 6.670e-11 for G.) If any component of the radius vector is zero,
the result is defined to be zero in that component.
For example,
(((grav-field 1) (vector 1 0 1)) 1) ==> #(-6.67e-11 0.0 -6.67e-11)
(((grav-field 1) (vector 1 2 3)) 10)
==> #(-6.67e-10 -1.6675e-10 -7.41111111111111e-11)
(((grav-field 0.001) (vector 0.05 0 0)) 0.5)
==> #(-1.3339999999999998e-11 0.0 0.0)
(let ((mass-of-earth 5.96e24) ; kg
(radius-of-earth 6.370e9)) ; m
(((grav-field mass-of-earth) (vector 0 0 radius-of-earth)) 1))
==> #(0. 0. -9.797002728153211e-6)
Note that these answers are inexact.
(By the way, the units in the results are Newtons; the last result says that
a 1kg mass placed at the earth's surface feels a force of about 2.2 pounds.)
Do not use vector-generator, but write ``grav-field'' in the style of
vector-copy in problem 3 above. Don't mutate the arguments,
return a new vector.
7. (8 points; extra credit only)
Often computer scientists have to look up some numbers in order to do
a problem like the above. This is part of our job, learning the knowledge
of some other field (pardon the pun) in order to encode it in a program.
For this problem you'll have to do that: look up the numbers for the
electric field generated by a point charge, and do the same thing as the
previous problem for the electric field.
8. (10 points)
Define a procedure ``vector-map2'' that takes a 2-argument procedure, ``p''
and two vectors ``x'' and ``y'',
and returns a new vector whose value is
<(p x_0 y_0), ... (p x_{n-1} y_{n-1})>
when x = for i = 0, ..., n-1,
and y = for i = 0, ..., n-1.
That is, this is like map2 for lists. For example,
(vector-map2 + (vector 1 2 3) (vector 7 6 5)) ==> #(8 8 8)
(vector-map2 * (vector 1 2 3 4) (vector 7 6 5 1)) ==> #(6 12 15 4)
(vector-map2 / (vector 8 15 27 9) (vector 2 3 9 9)) ==> #(4 5 3 1)
(vector-map2 make-vector '#(1 2 3) '#(a b c))
==> #(#(a) #(b b) #(c c c))
Do not use vector-generator, but write ``vector-map2'' in the style of
vector-copy in problem 3 above. Don't mutate the arguments,
return a new vector.
SECTION 9.2, VECTOR-GENERATOR and VECTOR-ACCUMULATE
Read especially pages 272-275 for examples of using vector-generator,
and pages 275-278 about vector-accumulate.
9. (0 points; suggested practice)
A basic point about vectors is that the value of a vector can be thought of
as a function. Such functions can be represented in Scheme by
lambda expressions.
For example, the vector viewed at prompt [2] on page 269 of the text
can be thought of as the function represented by
(lambda (i) (add1 i))
which is the same as add1. Of course, since vectors are finite functions,
a better representation might be
(lambda (i)
(if (and (<= 0 i) (<= i 5))
(add1 i)
(error i " is not a valid index")))
Similarly the vector at prompt [6] on page 269 can be thought of as
the function
(lambda (i)
(if (and (<= 0 i) (<= i 3))
(* i i)
(error i " is not a valid index")))
To test this, one can use vector-generator. For example,
> (load "ch9.ss")
> ((vector-generator
(lambda (i)
(if (and (<= 0 i) (<= i 3))
(* i i)
(error i " is not a valid index"))))
4))
#(0 1 4 9)
>
Write down and test similar Scheme representations for the vectors viewed at
(a) prompt [7] on page 269, and (b) prompt [2] on page 271.
10. (0 points; suggested practice)
Do the same as the previous exercise for prompts [3] and [4] on page 271.
11. (0 points; suggested practice)
Do exercise 9.1 (successive-powers)
12. (0 points; suggested practice)
Do problem 5, ``vec-'', using vector-generator.
13. (10 points)
Do problem 6, ``grav-field'', using vector-generator.
14. (10 points)
Do problem 8, ``vector-map2'', using vector-generator.
15. (0 points; suggested practice)
Write a procedure ``vector-stretch-fill'' that is like ``vector-stretch''
(program 9.5), but takes an additional argument, ``fill-value''.
The ``fill-value'' is used as the initial value for elements
of the result for which there is no corresponding element in
the argument ``vec''.
For example,
(vector-stretch-fill (vector 'a 'b 'c) 6 'new))
==> #(a b c new new new)
16. (10 points)
The weighted score of a vector of data, d = for i = 0, ..., n-1,
with weights w = for i = 0, ..., n-1,
and possible scores p = for i = 0, ..., n-1,
is given by the formula:
(w_0 * d_0) + ... + (w_{n-1} * d_{n-1})
----------------------------------------
(w_0 * p_0) + ... + (w_{n-1} * p_{n-1})
Using both vector-accumulate and vector-generator, write
a procedure ``weighted-score'' that takes a vector of numbers, ``data'',
and a vector of numbers between 0.0 and 1.0, ``weights'',
and a vector of numbers, ``possible'',
and returns the weighted score of the data. Don't mutate the arguments.
You can assume that all vectors have the same length,
that not all of the weights are 0.0, and that the sum of the possible
scores is greater than 0.0.
For example,
(weighted-score (vector 90 100) (vector 0.3 0.7) (vector 100 100))
==> 0.97
You must use both vector-accumulate and vector-generator in your solution.
MORE PRACTICE WITH VECTORS
17. (0 points; suggested practice)
Can you define vector-map using vector-accumulate, vector-set!, and lambdas?
18. (0 points; suggested practice)
Do exercise 9.2 on page 289 (view).
19. (0 points; suggested practice)
Barbara Liskov thinks that the elements of a vector should be printed
abstractly. She points out that if you print a vector of vectors using
``view'', you'll see the internal representation printed.
Solve her problem by writing a procedure ``view-abs''
that takes a procedure, ``element-print'',
and a vector, ``vec'', as arguments, and prints ``vec'',
using ``element-print'' to print the elements.
For example,
> (view-abs view (vector (vector 1 2) (vector 3 4)))
#(#(1 2)
#(3 4))
> (view-abs write (vector "printed" "with" "quotes"))
#("printed" "with" "quotes")
20. (0 points; suggested practice only)
Do exercise 9.5 (vector-linear-search).
21. (0 points; suggested practice only)
Do exercise 9.6 (vector-append, vector-reverse).
For example,
(vector-append (vector 1 2 3) (vector 4 5)) ==> #(1 2 3 4 5)
(vector-reverse (vector 1 2 3)) ==> #(3 2 1)
(vector-reverse (vector )) ==> #()
Check your work on the computer.
22. (0 points; suggested practice only)
Use unrestricted lambda to define ``vector-append'' so that it appends
any number of vectors.
SECTION 9.3, PAGES 282-289, IMPERATIVE (MUTATING) PROCEDURES
Look especially at the descriptions of the procedures whose names end in ``!''.
23. (10 points)
Define a procedure multiply-by-scalar! that takes a number, ``c'',
and vector of numbers, ``vec'', and mutates vec so in the final state,
the ith element of vec is the result is ``c'' times
the initial ith element of ``vec''. Do not create a new vector,
mutate the argument vector ``vec''.
Note that nothing is returned by multiply-by-scalar!, that is, it has type:
(-> (number (vector number)) void)
For example, consider the following transcript.
> (define my-vec (vector 3 4 5 6))
> my-vec
#(3 4 5 6)
> (multiply-by-scalar! 2 my-vec)
> my-vec
#(6 8 10 12)
> (multiply-by-scalar! 2 my-vec)
> my-vec
#(12 16 20 24)
> (multiply-by-scalar! 3 (vector 2 7))
> my-vec
#(12 16 20 24)
24. (6 points)
This problem is related to the Towers of Hanoi.
Recall that a state of the puzzle consists of 3 integers,
telling how many disks are on the left, center, and right posts.
In this problem we will represent that state using a vector containing
3 integers. The contents of a state vector at index 0 represents
the number of disks on the left post, at index 1 the center,
and at 2 the right. Write a procedure, ``tower-move!'' that takes
two symbols (either l, c, or r), ``src'' and ``dest'',
and returns a procedure that takes a state, ``posts'',
and mutates the vector so that the final value of ``posts'' has one less
disk on ``src'' and one more on ``dest''. Don't return a new vector,
mutate the vector ``posts''.
For example, consider the following transcript.
> (define posts #(2 0 0))
> posts
#(2 0 0)
> ((tower-move! 'l 'c) posts)
> posts
#(1 1 0)
> ((tower-move! 'l 'r) posts)
> posts
#(0 1 1)
> ((tower-move! 'c 'r) posts)
> posts
#(0 0 2)
> ((tower-move! 'l 'r) (vector 7 0 0))
> posts
#(0 0 2)
25. (0 points; suggested practice)
Write an imperative procedure ``vector-tower-of-hanoi'', that is like
``tower-of-hanoi'', except that instead of returning a list of moves,
it returns a list of 3-element vectors.
Each 3 element vector represents the state of the problem: how many disks
are on the left, center, and right needles.
For example, #(3 2 1) represents the state where there are three disks
on the left needle, 2 on the middle, and one on the right.
For example,
(vector-tower-of-hanoi 2) ==> (#(2 0 0) #(1 1 0) #(0 1 1) #(0 0 2))
Hint: use ``vector-copy'' and a variable ``posts'' that is
outside the recursion, holding the state.
26. (10 points)
Define a procedure ``vector-mutate!'' that takes a procedure, ``proc'',
of type (-> (natural) T) and a vector, ``v'', of type (vector T),
and mutates the vector so that the ith element of v is (proc i).
The mutations happen by first calling (proc 0), then (proc 1), etc.
For example,
> (define avec (vector 1 10 100))
> (vector-mutate! (lambda (i) (* i (vector-ref avec i))) avec)
> avec
#(0 10 200)
> (vector-mutate! (lambda (i) (vector-ref avec (- 2 i))) avec)
> avec
#(200 10 200)
The last result is correct, because the 0th element of avec is first set to
200, then when the 2th element is set, it uses the current value of the 0th
element.
27. (0 points; suggested practice)
Define a procedure ``parallel-vector-mutate!'' that takes a procedure,
``proc'', of type (-> (natural) T) and a vector, ``v'', of type (vector T),
and mutates the vector so that the ith element of v is (proc i).
The mutations are done ``in parallel'' so that they don't interfere with
each other. For example,
> (define avec (vector 1 10 100))
> (vector-mutate! (lambda (i) (vector-ref avec (- 2 i))))
> avec
#(100 10 1)
28. (0 points; suggested practice)
Write a procedure ``vector-for'' that takes a procedure,
``proc'', of type (-> (natural) void) and a vector, and which has no
return value. This procedure should call the proc for each index of the
vector, starting with 0. For example,
> (define avec (vector 1 10 100))
> (vector-for (lambda (i) (writeln i)) avec)
0
1
2
> (vector-for (lambda (i) (vector-set! avec i 0)) avec)
> avec
#(0 0 0)
29. (0 points; suggested practice)
On the bottom of page 270, the text says that Program 9.3
is ``very inefficient.'' Analyze the program and estimate its order
(see p. 126). (Computer Scientists call this ``time complexity.'')
MATRICES (9.4)
We are going to skip this section this semester.
You can do any of the problems for practice with the ideas of this chapter.
The code for matrices is gotten by loading the file for this chapter.
CHAPTER 10
We are not going to cover chapter 10 in class this semester.
But there are many interesting exercises in that chapter.
These exercises concern such basic computer algorithms
such as sorting and searching,
and an introduction to relational databases (in section 10.4).
You can do these for additional practice with vectors and mostly functional
programming.