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?