{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman{\*\falt Thorndale};}{\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};}{\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\mo11\dy21\hr22\min6}{\printim\yr2002\mo10\dy29\hr9\min52}{\version3}{\edmins3}{\nofpages1}{\nofwords335}{\nofchars1913}{\*\company CNRS-HSU}{\nofcharsws2349}{\vern8269}}\margt2114 
\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 #11\tab \tab p. }
{\field{\*\fldinst {\fs16 \\page}}{\fldrslt {\fs16\lang1024\langfe1024\noproof 1}}}{
\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 #11
\par DUE: Friday, December 6th, 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 same homework and style guidelines apply as before.
\par }{\b\fs20 
\par }\pard \s15\ql \fi-435\li420\ri0\nowidctlpar\aspalpha\faauto\rin0\lin420\itap0 {\fs20 1.\tab 
Do Exercise 25.1.2 on p. 362 of HtDP. (Note: copy over all the data definitions, auxiliary functions, etc. that you need from the posted class examples...!) (Note also: you are required to }{\b\fs20 appropriately}{\fs20 
 use at least one of the Scheme built-in functions from Figure 57, p. 313) (Note finally: if your function }{\b\fs20 move-balls}{\fs20  is very long, that is not a good sign...)
\par 
\par 2.\tab Consider the version of }{\b\fs20 qsort}{\fs20  discussed in lecture 11-21-02. Consider: what, }{\i\fs20 really}{\fs20 , needs to be done if a list contains only one 
item? How can you tell if a list has only one item? Modify our in-class version of }{\b\fs20 qsort}{\fs20 
 to handle a one-item list as one of its cases. (Add at least one example/test involving a one-item list; add at least one example/test of a reverse-order 2-item list, also.)
\par 
\par 3.\tab Do Exercise 25.2.3 on p. 367 of HtDP. Start with the version of }{\b\fs20 qsort}{\fs20  that you end up with at the end of Question #2, above; modify it to result in }{\b\fs20 qsort2}{\fs20  that uses }{\b\fs20 sort}{\fs20 
 from section 12.2 if the length of the input is below some threshhold. (Hmm; I believe that they are assuming that this threshhold ought to be a named constant rather than an additional }{\b\fs20 qsort2}{\fs20  parameter. We'll go with that assumption.)

\par 
\par 4.\tab Do Exercise 25.2.4 on p. 367 of HtDP. Consider the first question to be rhetorical (think about it, but you do not have to turn in an answer for it...) Basically, write }{\b\fs20 qsort3}{\fs20 
 (based on your final version of qsort from Question #2) that also works for lists where duplicate values are permitted (values can appear in the list more than once) such 
that the resulting list is sorted, but is still of the same length as the original input list (duplicated values appear as many times in the sorted result as they do in the original list.) Be sure to add at least one example/test including such repeated v
alues; also include at least one example/test containing all the same value and with length >3. (Beware: the required change doesn't involve very much code, but you do need to be careful...)
\par 
\par }{\b\fs20 
\par 
\par \tab 
\par }\pard \s15\ql \li0\ri0\nowidctlpar\aspalpha\faauto\rin0\lin0\itap0 {\b 
\par }}