{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman{\*\falt Thorndale};}{\f2\fmodern\fcharset0\fprq1{\*\panose 02070309020205020404}Courier New;}
{\f29\fswiss\fcharset128\fprq2{\*\panose 020b0604020202020204}Arial Unicode MS;}{\f30\fswiss\fcharset128\fprq2 @Arial Unicode MS;}{\f31\froman\fcharset238\fprq2 Times New Roman CE{\*\falt Thorndale};}
{\f32\froman\fcharset204\fprq2 Times New Roman Cyr{\*\falt Thorndale};}{\f34\froman\fcharset161\fprq2 Times New Roman Greek{\*\falt Thorndale};}{\f35\froman\fcharset162\fprq2 Times New Roman Tur{\*\falt Thorndale};}
{\f36\froman\fcharset177\fprq2 Times New Roman (Hebrew){\*\falt Thorndale};}{\f37\froman\fcharset178\fprq2 Times New Roman (Arabic){\*\falt Thorndale};}{\f38\froman\fcharset186\fprq2 Times New Roman Baltic{\*\falt Thorndale};}
{\f47\fmodern\fcharset238\fprq1 Courier New CE;}{\f48\fmodern\fcharset204\fprq1 Courier New Cyr;}{\f50\fmodern\fcharset161\fprq1 Courier New Greek;}{\f51\fmodern\fcharset162\fprq1 Courier New Tur;}{\f52\fmodern\fcharset177\fprq1 Courier New (Hebrew);}
{\f53\fmodern\fcharset178\fprq1 Courier New (Arabic);}{\f54\fmodern\fcharset186\fprq1 Courier New Baltic;}{\f265\fswiss\fcharset0\fprq2 Arial Unicode MS Western;}{\f263\fswiss\fcharset238\fprq2 Arial Unicode MS CE;}
{\f264\fswiss\fcharset204\fprq2 Arial Unicode MS Cyr;}{\f266\fswiss\fcharset161\fprq2 Arial Unicode MS Greek;}{\f267\fswiss\fcharset162\fprq2 Arial Unicode MS Tur;}{\f268\fswiss\fcharset177\fprq2 Arial Unicode MS (Hebrew);}
{\f269\fswiss\fcharset178\fprq2 Arial Unicode MS (Arabic);}{\f270\fswiss\fcharset186\fprq2 Arial Unicode MS Baltic;}{\f273\fswiss\fcharset0\fprq2 @Arial Unicode MS Western;}{\f271\fswiss\fcharset238\fprq2 @Arial Unicode MS CE;}
{\f272\fswiss\fcharset204\fprq2 @Arial Unicode MS Cyr;}{\f274\fswiss\fcharset161\fprq2 @Arial Unicode MS Greek;}{\f275\fswiss\fcharset162\fprq2 @Arial Unicode MS Tur;}{\f276\fswiss\fcharset177\fprq2 @Arial Unicode MS (Hebrew);}
{\f277\fswiss\fcharset178\fprq2 @Arial Unicode MS (Arabic);}{\f278\fswiss\fcharset186\fprq2 @Arial Unicode MS Baltic;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;
\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}
{\stylesheet{\ql \li0\ri0\widctlpar\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 \fs24\lang1033\langfe1033\cgrid\langnp1033\langfenp1033 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{
\s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 \fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 \snext15 Default;}{\s16\ql \li0\ri0\nowidctlpar\tqc\tx4320\tqr\tx8640\aspalpha\faauto\rin0\lin0\itap0 
\fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 \sbasedon15 \snext16 header;}{\*\cs17 \additive \fs24\cf1\lang0\langfe255\langfenp255 Numbering Symbols;}}{\info{\author Sharon Tuttle}{\operator CNRS}{\creatim\yr2002\mo10\dy11\hr14\min30}
{\revtim\yr2002\mo10\dy25\hr16\min56}{\printim\yr2113\mo1\dy1}{\version2}{\edmins4}{\nofpages2}{\nofwords786}{\nofchars4485}{\*\company CNRS-HSU}{\nofcharsws5507}{\vern8269}}\margt2079 
\deftab1250\widowctrl\ftnbj\aenddoc\noxlattoyen\expshrtn\noultrlspc\dntblnsbdb\nospaceforul\hyphcaps0\horzdoc\dghspace120\dgvspace120\dghorigin1701\dgvorigin1984\dghshow0\dgvshow3\jcompress\viewkind1\viewscale90\nolnhtadjtbl \fet0\sectd 
\sbknone\linex0\headery1440\sectdefaultcl {\header \pard\plain \s16\ql \li0\ri0\nowidctlpar\tqc\tx4320\tqr\tx8640\aspalpha\faauto\rin0\lin0\itap0 \fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 {\fs16 CS 131 - Homework #8\tab \tab p. }
{\field{\*\fldinst {\fs16 \\page}}{\fldrslt {\fs16\lang1024\langfe1024\noproof 2}}}{
\par }{\fs16 Fall 2002
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \s15\qc \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 
\fs24\cf1\lang1033\langfe255\cgrid\langnp1033\langfenp255 {\b\fs20 CS 131 - Intro to Computer Science I - Fall 2002
\par Homework #8
\par DUE: Friday, November 1st, by }{\b\fs20\ul 5:00 pm}{\b\fs20 
\par }{\b\fs20\ul 
\par }\pard \s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 {\fs20 As always, you will turn in certain function definitions and expressions that you have typed into the DrScheme definitions window and saved into one or more file names ending in }{
\b\fs20 .scm}{\fs20  .
\par 
\par The program recipe in effect for this homework is the }{\b\fs20 10-11 version}{\fs20 , w
hich now requires a brief description at the end of each data definition (especially for structures, and if the meaning is not clear for "supertype"-style and list-style data definitions). Please let me know if you have any questions about this latest pro
gram recipe version.
\par 
\par The same general class style guidelines still apply, also:
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {\fs20 *\tab choose meaningful function, parameter, and variable names.
\par *\tab use auxiliary functions whenever they are appropriate.
\par *\tab reuse functions whenever possible and appropriate. If a function has already been defined for a previous problem within the same definitions file, you may simply use it in a later problem's function.
\par *\tab define constant values in your functions as named variables written in all capital letters; for example,
\par \tab (define CRUST-WIDTH 1)
\par *\tab a data definition is not repeated for every function that uses that data; the data definition is only given once in a particular Scheme file. The template for that data definition only has to appear once, as well; HOWEVER, if you find 
it helpful, you may repeat that template before each appropriate function body for which you find that template useful.
\par 
\par In particular: please note that a problem may ask you to write a particular function. When it is appropriate, you should also write unspecified auxiliary functions that you decide are useful in writing the specifically-requested function.
\par }{\b\fs20 
\par }{\fs20 1.\tab (Adapted from Keith Cooper's section of Rice University's COMP 210, Spring 2002)
\par \tab Develop a program}{\b\fs20  first-k : list N -> list. }{\fs20 (Remember, N is the natural numbers, as defined in lecture and in the course text.) Your program should consume two arguments, a list}{\b\fs20  l a}{\fs20 nd a natural number}{\b\fs20  k. 
}{\fs20 It should produce a list that contains the first}{\b\fs20  k }{\fs20 elements of the input list}{\b\fs20  l}{\fs20 .}{\b\fs20  }{\fs20 For example, 
\par }{\b\fs20 
\par \tab }{\af2\fs20 (first-k (list 1 'f 4 'b true 0 'hello) 3) }{\fs20 should return }{\af2\fs20 (list 1 'f 4)}{\fs20 
\par 
\par 2.\tab (Adapted from Keith Cooper's section of Rice University's COMP 210, Spring 2002)
\par \tab Consider the domain of natural numbers (N), as discussed in lecture and in the course text. Write a program}{\b\fs20  mult }{\fs20 that ta
kes two natural numbers and returns their product --- BUT your program may NOT use the built-in multiply function (*); instead, you need to use addition and subtraction to compute the answer.
\par }{\b\fs20 
\par }{\fs20 3.\tab First, write a function }{\b\fs20 draw-my-pic }{\fs20 
that draws a shape/picture of your choice (you set the color(s), the size, and the shape(s) involved) given a position indicating where it should be drawn (That is, this function takes a position as input, and draws the shape/picture you decide at that po
sition. Assume an already-open canvas.) It should return }{\b\fs20 true }{\fs20 if successful.}{
\par }\pard \s15\ql \fi-435\li855\ri0\nowidctlpar\aspalpha\faauto\rin0\lin855\itap0 {\b\fs20 \tab }{\fs20 (for example, your shape might be a face, or 3 concentric circles, or colored lines that make a pleasing pattern, or connected rectangles, etc.)
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {\fs20 
\par \tab Next, write a function}{\b\fs20  clear-my-}{\fs20 pic that clears the shape/picture drawn by}{\b\fs20  draw-my-pic, }{\fs20 again given a position as input. It, too, should return}{\b\fs20  true }{\fs20 if successful.
\par }{\b\fs20 
\par \tab }{\fs20 Finally, write a function}{\b\fs20  animate-my-pic }{\fs20 that takes two natural numbers}{\b\fs20  how-many }{\fs20 and}{\b\fs20  space-amt }{\fs20 as input, and does a simple "animation" of your shape/picture drawn by}{\b\fs20  draw-my-pic 
}{\fs20 by causing it}{\b\fs20  }{\fs20 to}{\b\fs20  
\par \tab }{\fs20 "bounce around"}{\b\fs20  how-many }{\fs20 times (be drawn and cleared}{\b\fs20  how-many }{\fs20 times), with a "pause" of 
\par }{\b\fs20 \tab space-amt }{\fs20 seconds between each bounce. It should return}{\b\fs20  true}{\fs20  if all of this was successful.}{\b\fs20 
\par 
\par \tab }{\fs20  (That is,}{\b\fs20  (animate-my-pic 4 7) }{\fs20 
will cause your shape/picture to be drawn at a random location on your canvas (1st), then 7 seconds later it will disappear and be drawn at another location (2nd), then 7 seconds later it will disapper and be drawn at anothe
r location(3rd), and 7 seconds later it will disappear and be drawn at another location(4th), and 7 seconds later it will disappear (and that's it).)
\par }{\b\fs20 
\par }{\fs20 3.\tab (Adapted from Keith Cooper's section of Rice University's COMP 210, Spring 2002)
\par \tab We can define a}{\b\fs20  list-of-list-or-symbol }{\fs20 as: 
\par }{\b\fs20 
\par }\pard \s15\ql \fi-435\li855\ri0\nowidctlpar\aspalpha\faauto\rin0\lin855\itap0 {\fs20\loch\af2 \hich\af0\dbch\af0\loch\f2 ;;----------------------------------------------------------
\par \hich\af0\dbch\af0\loch\f2 ;; a list-of-list-or-symbol is one of:
\par \hich\af0\dbch\af0\loch\f2 ;;    1. the empty list, empty, or
\par \hich\af0\dbch\af0\loch\f2 ;;    2. (cons sym list-or-sym-list)
\par \hich\af0\dbch\af0\loch\f2 ;;       ... where sym is a symbol and list-or-sym-list is \hich\af0\dbch\af0\loch\f2 a
\par \hich\af0\dbch\af0\loch\f2 ;;       list-of-list-or-symbol, or
\par \hich\af0\dbch\af0\loch\f2 ;;    3. (cons list-or-sym-list1 list-or-sym-list2)
\par \hich\af0\dbch\af0\loch\f2 ;;       ... where list-or-sym-list1 and list-or-sym-list2 are
\par \hich\af0\dbch\af0\loch\f2 ;;       both list-of-list-or-symbol.
\par \hich\af0\dbch\af0\loch\f2 ;; That is, the elements of such a list may be symbols, or may be
\par \hich\af0\dbch\af0\loch\f2 ;; lists of symbols... (list 'a 'b 'c 'd) is one, but so is
\par \hich\af0\dbch\af0\loch\f2 ;; (list (list 'a) (list 'b 'c) 'd)
\par \hich\af0\dbch\af0\loch\f2 ;;----------------------------------------------------------
\par }{\b\fs20\loch\af2 
\par }{\fs20 (a)\tab Write a program}{\b\fs20  symbol-count }{\fs20 that takes a list-of-list-or-symbol and returns the number of symbols occurring in the input list (no matter how "nested" within lists). For example, 
\par 
\par \tab }{\af2\fs20 (symbol-count (list 'fee (list 'fie 'foe) (list 'fum) 'foo))}{\fs20 
\par }{\fs20\loch\af2 
\par \tab }{\fs20 ...should return 5.}{\fs20\loch\af2 
\par }{\b\fs20 
\par }{\fs20 (b)\tab Write a program}{\b\fs20  flatten }{\fs20 that consumes a list-of-list-or-symbol and produces a new list-of-symbols that has all of the symbols from the list-of-list-or-symbol, in order of their appearance. For example, 
\par }{\b\fs20 
\par \tab }{\af2\fs20 (flatten (list 'fee (list 'fie 'foe) (list 'fum) 'foo))}{\fs20 
\par }{\fs20\loch\af2 
\par \hich\af0\dbch\af0\loch\f2  \tab }{\fs20 ...should return }{\fs20\loch\af2 \hich\af0\dbch\af0\loch\f2 (list 'fee 'fie 'foe 'fum 'foo)
\par }{\b\fs20 
\par }{\b\fs20\ul 
\par }\pard \s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 {
\par }{\loch\af2 
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {\loch\af2 
\par }\pard \s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 {
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {
\par }}