Com S 227 --- Introduction to Computer Programming HOMEWORK 3: DATA ABSTRACTION AND NUMBERS (File $Date: 1993/09/24 02:25:41 $) Due: problems 1-7 Sept. 24.; 8-16 Sept. 29. 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. SECTION 3.2, OPERATIONS ON NUMBERS You might also want to read chapter 4 of the ``Little LISPer''. 1. (0 points; suggested practice) Do exercise 3.1. Check your answer on the computer. 2. (0 points; suggested practice) Do exercises 3.2, 3.3, and 3.4. You can think of the n-tuples discussed in these exercises as the vectors of physics. (Especially if the n-tuple has 3 elements.) So pairwise-sum is vector addition, dot-product forms the scalar product of 2 vectors, and mult-by-n multiplies a vector by a scalar. 3. (10 points) In Physics, the laws of mechanics are summarized by the vector equation F = m * a where F = (F_x, F_y, F_z) is a 3-tuple, representing the force vector, m is the mass, and a = (a_x, a_y, a_z) is the acceleration vector. Write a procedure, force, that takes a number, m, a 3-tuple of numbers, a, and returns the 3-tuple of numbers (m * a_x, m * a_y, m * a_z) that represents the force vector. For example, (force 3.0 '(5.2 3.1 8.7)) ==> (15.6 9.3 26.1) (force 72 '(-8.2 -3.14 -32.0)) ==> (-590.4 -226.08 -2304.) Note that your answers will not be exact if you use inexact (floating point) numbers, but that is okay. By the way, Geordi La Forge (of ``Star Trek the Next Generation) wants you to be sure that he can use your program when they enter universes with different dimensions. Would your program work for 4-dimensional universes? Or 8-dimensional universes? (That is, would it work for 4- or 8-tuples as well as for 3-tuples?) If it doesn't, fix it so it does. 4. (0 points; suggested practice) Do exercise 3.5 (index). 5. (12 points) Ben Bittwiddle wants to output to his new ``easy-sound'' sound card. He has several favorite songs for which he can remember the solfege syllables (do, re, mi, etc.), and needs to translate them into a number of Hertz for each sound. Patti Pathagoras says that to her, Ben's rendition of ``do'' sounds like an ``a 2 octaves below middle c'', which she says is 55 Hertz. Can you help Ben interface to his easy-sound card? Write a procedure ``solfege->hertz'' that takes a symbol from the list (do do-sharp re re-sharp mi fa fa-sharp so so-sharp la la-sharp ti) and returns the frequency (in Hertz) that corresponds to that note. This can be done by computing the symbols index in the list above (hint: see exercise 3.5), and returning 55 multiplied by 1.059463094359295 to power of the index. For example, (solfege->hertz 'do) ==> 55 (solfege->hertz 're) ==> 61.735412657015495 (solfege->hertz 'mi) ==> 69.29565774421798 (solfege->hertz 'fa) ==> 73.41619197935182 (solfege->hertz 'ti) ==> 103.82617439498608 6. (0 points; suggested practice) Do exercise 3.6 (make-list). 7. (15 points) Do exercise 3.7 (count-background). Make up a story to go with this problem; that is, write down a context for which this procedure might be useful. Hand in both the program, the transcript of your testing, and the story. 8. (10 points; basic) A classically conceived newspaper story has the most important information at its beginning, so that an editor can shorten it by cutting from the bottom as needed. Write a procedure ``cut-story'' that takes a nonnegative integer ``count'' and a list ``story'' and returns a list of the first count items of story. If ``count'' is larger than ``story'', then an error is signaled, using the procedure ``error''. The procedure error, from page 199 of the text, is automatically loaded into Chez Scheme on Project Vincent (if you did homework 0 correctly). If you are using some other Scheme, you may have to load that yourself. For example, (cut-story 9 '(ames iowa the squaw creek overflowed its banks today it caused the worst flooding in a century ...)) ==> (ames iowa the squaw creek overflowed its banks today) (cut-story 17 '(washington dc the supreme court in an unprecedented ruling said that iowa state university was the best university in the country when asked why the ...)) ==> (washington dc the supreme court in an unprecedented ruling said that iowa state university was the best) (cut-story 0 '(chicago the city celebrated the amazing world series victory of the cubs today)) ==> () and (cut-story 3 '(washington dc)) gives the error message: Error: length of (washington dc) is less than 3. 9. (0 points; suggested practice) Do (one or more of) problems 3.10, 3.11, and 3.12. Check your answer on the computer. 10. (5 points; extra credit only) Do problem 3.13 (efficiency). SECTION 3.3, EXACT ARITHMETIC AND DATA ABSTRACTION Procedures for this section must be written at the appropriate level of detail. That is, unless you are implementing one of the basic procedures for ratls, your code should work for any representation of ratls. (This property is called representation independence.) If your code is too low-level, you will lose points (and you'll have a harder time writing it too). You will find it useful to use rprint in testing your code. You can load the code from chapter 3, including rprint, by typing (load "/home/cs227/lib/ch3.ss") to the Scheme interpreter. To test whether your procedures are written at the right level, you can load one of the files "ratl4.ss" or "ratl3.ss" in the directory /home/cs227/lib. Load one of them after you have loaded the file for chapter 3, or it will have no effect. Test you code, and then try it with the other too if you like. 11. (12 points; basic) Look at the code in /home/cs227/lib/ratl3.ss and in /home/cs227/lib/ratl4.ss Describe their representation of the ratls and how they differ form the representation used in chapter 3. It would be helpful to describe how 2/3 is represented in each case. 12. (0 points; suggested practice) Do exercises 3.14 and 3.15. Check your answers on the computer. Here are some examples for exercise 3.14. (rprint (rminus (make-ratl 2 3))) =prints=> -2/3 (rprint (rminus (make-ratl -7 27))) =prints=> 7/27 13. (7 points; basic) Do exercise 3.16. Here are some examples. (rprint (rabs (make-ratl 2 3))) =prints=> 2/3 (rprint (rabs (make-ratl -7 3))) =prints=> 7/3 (rprint (rabs (make-ratl 9 -7))) =prints=> 9/7 14. (0 points; suggested practice) Write a procedure, ratl->inexact, that takes a ratl r and returns a floating point number that approximates r. Note that adding 0.0 to an integer makes it a floating point number. 15. (8 points; basic) Do exercise 3.17 (make-ratl). 16. (10 points) The ``golden ratio'' is a number that is found in art, biology, and architecture. For example, the ratio of the breadth to the height of the Parthenon in Athens is the golden ratio. The golden ratio is the positive solution to the equation x = 1 + (1 / x). Substituting the right hand side for the x on the right hand side gives us the formula. x = 1 + (1 / (1 + (1 / x))) If we keep going we get that x = 1 + (1 / (1 + (1 / (1 + (1 / x))))). If we keep this up forever, we get what mathematicians call a continued fraction. x = 1 + (1 / (1 + (1 / (1 + (1 / (1 + ...)))))). Is it possible to compute such a number? Not exactly, but we can approximate it. This problem calls for you to make a ratl approximation to the golden ratio. That is, you are to use the procedures for ratls to compute a ratl. Specifically, you are to write a procedure, golden-ratio, that takes as it input a nonnegative integer, k, and returns a level k approximation to the golden ratio as a ratl. A level 0 approximation is defined as 1/1; and for k>0, a level k approximation is defined as (1/1) + (1/z), where z is a level k-1 approximation. For example, (rprint (golden-ratio 0)) =prints=> 1/1 (rprint (golden-ratio 3)) =prints=> 5/3 (rprint (golden-ratio 11)) =prints=> 233/144 EXTRA CREDIT EXPLORATIONS 17. (15 points; extra credit) The complex numbers are often used in physics, especially in the theory of electricity. Describe how you might represent the complex numbers in Scheme. Implement procedures ``make-cmplx'', ``real-part'', and ``imag-part''. 18. (10 points; extra credit) Describe another implementation of the complex numbers, which is different than the one you used for the previous problem. Implement the procedures ``make-cmplx'', ``real-part'', and ``imag-part'' using this representation. 19. (12 points; extra credit) Look up in a book how to add, subtract, multiply, and divide complex numbers. Implement the procedures ``c+'', ``c-'', ``c*'', and ``c/''. 20. (10 points; extra credit) Alyssia P. Hacker thinks its strange to have to use ``r+'' and ``c+'' to add ratl and cmplx numbers, when the Scheme built-in ``+'' can add lots of different kinds of numbers. Can you define a procedure ``plus'' that can add all the different kinds of numbers? Is there any way to call it ``+'' and still have it work?