{\rtf1\ansi\deff0\adeflang1025
{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f1\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f2\froman\fprq2\fcharset0 Times New Roman;}{\f3\fmodern\fprq1\fcharset0 Courier New{\*\falt Cumberland};}{\f4\fnil\fprq2\fcharset0 HG Mincho Light J;}{\f5\fnil\fprq2\fcharset0 Arial Unicode MS;}}
{\colortbl;\red0\green0\blue0;\red128\green128\blue128;}
{\stylesheet{\s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\snext1 Default;}
{\s2\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af3\afs20\lang255\ltrch\dbch\af3\afs20\langfe255\loch\f3\fs20\lang1033\sbasedon1\snext2 Preformatted Text;}
{\*\cs4\cf1\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033 Numbering Symbols;}
}
{\info{\author Sharon Tuttle}{\creatim\yr2002\mo9\dy26\hr8\min15}{\operator Sharon Tuttle}{\revtim\yr2002\mo10\dy31\hr9\min51}{\printim\yr2002\mo10\dy31\hr9\min27}{\comment StarWriter}{\vern6410}}\deftab1250
{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn12240\pghsxn15840\marglsxn1800\margrsxn1800\margtsxn1440\margbsxn1440\pgdscnxt0 Default;}}
\paperh15840\paperw12240\margl1800\margr1800\margt1440\margb1440\sectd\sbknone\pgwsxn12240\pghsxn15840\marglsxn1800\margrsxn1800\margtsxn1440\margbsxn1440\ftnbj\ftnstart1\ftnrstcont\ftnnar\aenddoc\aftnrstcont\aftnstart1\aftnnrlc
\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\ltrch\loch\f2 {\ltrch\loch\f2 CS 131 - Fall 2002}
\par {\ltrch\loch\f2 Midterm #2 Study Suggestions}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab remember: anything covered in assigned course reading, in lecture, or on a homework, is FAIR GAME.}
\par 
\par {\ltrch\loch\f2 *\tab you are responsible for the material through the end of Section 11 and through HW #8, plus the {\b append}{\b0  function discussed in lecture on Tuesday, 10-29 (and demonstrated in that day's Scheme examples) }{\b AND Intermezzo 2, List Abbreviations!!!}{\b0  (it is AFTER Se
ction 12, but we discussed it BEFORE that, of course!)}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 
\par {\ltrch\loch\f2 *\tab these are simply suggestions of some especially important concepts, to help you in your studying.}
\par 
\par {\ltrch\loch\f2 *\tab the general style of the test will be similar to Midterm #1; there may be short-answer questions, and you will be both writing and reading functions and programs. Concepts and terminology may also be involved.}
\par 
\par {\ltrch\loch\f2 *\tab will the test be comprehensive? In some sense, that cannot be avoided --- previous concepts are the foundations for the new concepts. However, many of the questions will be {\b focused} on new material, (although there are a few exceptions, some of which are 
noted below).}
\par 
\par {\ltrch\loch\f2 *\tab the design recipe is still fair game, as are questions about the design recipe. (We've added more possibilities for the data definition and analysis part of this, remember --- see the latest posted design recipe template on the course web page.)}
\par 
\par {\ltrch\loch\f2 *\tab {\b structures}: even though they were covered on Midterm #1, we were still pretty early in our coverage of them, and you should be much more comfortable with them by now. I may even ask similar question(s) to those on Midterm #1, to verify how much more fami
liar you are with them now...}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab when might you decide to define and use a structure? how are they useful/beneficial?}
\par 
\par {\ltrch\loch\f2 *\tab be able to write, read {\b data} {\b definitions} for structures}
\par {\ltrch\loch\f2 *\tab be able to write, read Scheme {\b define-struct} expressions}
\par 
\par {\ltrch\loch\f2 *\tab given a structure definition, what {\b constructor} is created? what {\b selector(s)} are created? what {\b predicate} is created?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab how can these be used in making use of {\b instances } of your new structure?}
\par 
\par {\ltrch\loch\f2 *\tab how can you tell whether something is an instance of your new structure?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you should be able to write functions that manipulate structures}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b "mixed" data}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab be able to write a data definition for {\b mixed} data ("supertype" types), such as {\b pixel-2 }(HtDP, p. 82) or {\b shape }(HtDP, p. 84)}
\par 
\par {\ltrch\loch\f2 *\tab given such a data definition, how can you write functions handling such data?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is a {\b checked function}? How do you write one?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you should be able to read, write, understand the Scheme {\b error }operation;}
\par 
\par {\ltrch\loch\f2 *\tab when is it appropriate to use the Scheme {\b error} operation?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b lists}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b lists} will figure prominently on this test, as you can imagine;}
\par 
\par {\ltrch\loch\f2 *\tab be {\b very} familiar, comfortable with {\b empty}, {\b cons}, {\b first}, {\b rest}, {\b empty?}, {\b cons?};}
\par 
\par {\ltrch\loch\f2 *\tab be comfortable with writing {\b self-referential}/{\b recursive data definitions }for specialized lists of arbitrary length;}
\par 
\par {\ltrch\loch\f2 *\tab you will have to read and write expressions using lists and functions using lists;}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable with {\b Intermezzo 2: List Abbrevations}, also, especially the {\b list} operation.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab how does {\b list} compare to {\b cons}?}
\par 
\par {\ltrch\loch\f2 *\tab you are also responsible for {\b append} --- how does it compare to {\b list} and {\b cons}?}
\par 
\par {\ltrch\loch\f2 *\tab I'm considering {\b '} for lists less important, at this point, although you may use this notation if you wish.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b Recursion}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you know that this will figure prominently on the test, also;}
\par 
\par {\ltrch\loch\f2 *\tab we've had {\b recursive definitions} and {\b recursive functions};}
\par 
\par {\ltrch\loch\f2 *\tab what is/are the {\b base case(s)} in a recursive function or definition? what is/are the {\b recursive case(s) }in a recursive function or definition?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab I could ask you to identify them, for example;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what TWO things should be the case for a "good" recursive definition ot recursive function? (OK, I'll tell you:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 1. \tab it MUST have at least one{\b  }base case;}
\par {\ltrch\loch\f2 2. \tab all recursive calls must be on "smaller" instances of the problem, such that it can be proven that, eventually, a base case WILL be reached;)}
\par 
\par {\ltrch\loch\f2 *\tab I could give a recursive definition or function, and ask you if it is "good" or not, and why or why not;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab I could, of course, also describe a recursive situation, and ask you to write an appropriate recursive definition or recursive function;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab You know that:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you will have to read, write functions that process lists of arbitrary length;}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435{\ltrch\loch\f2{\b0\f2 *\tab some could return a single value,} (numeric, or boolean, for example);}
\par {\ltrch\loch\f0 * \tab some could return a structure;}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab some could return lists;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab the lists could be general (any list), or could be specialized; the lists might contain structures as well, or might contain lists themselves.}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b natural numbers}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab our set of {\b natural numbers}, {\b N}, is also fair game, and very likely to play a prominent roll in this midterm.}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable with the recursive definition for {\b N}, and how {\b add1}, {\b sub1}, and {\b zero? }can make it quite analogous to a list;}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable reading and writing recursive functions that process natural numbers of arbitrary size, and all sorts of interesting functions on numbers;}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af5\afs24\lang255\ltrch\dbch\af4\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 
\par }