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.