ࡱ> L(  ) I 2Getting Startedd!PWriting the Data Definition and Analysis4/ Writing Examples>6*Defining the TemplateB=.Creating the Definition$DTesting <L(Data being consumed?\SHName(s) of the function(s) required?FZ2Examples of the behavior?@a,Operation on the data?4h Build Operations0oMap Operations6v"Filter Operations2}Fold Operations6"Search Operations2Data Conversion$Overview      2Getting Started2Getting Started2Getting Started2Data Conversion2@Getting Started2Getting Started2Getting Started2Getting Started2Getting Started2Getting Started2Getting Started2Getting Started$Overview<(Data being consumed?<(Data being consumed?<(Data being consumed?dPWriting the Data Definition and Analysisd PWriting the Data Definition and Analysisd$PWriting the Data Definition and Analysisd(PWriting the Data Definition and Analysisd,PWriting the Data Definition and Analysisd0PWriting the Data Definition and AnalysisV@BList Data Analysis and Definition`GLStructure Data Analysis and Definitiond\PBinary Tree Data Analysis and DefinitionZcFVector Data Analysis and DefinitionTj@Writing the Contract and Purpose$uOverview$|Overview>*Defining the Template>m*Defining the Template>*Defining the Template8$Structure Template.List Template$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$Overview$OverviewB.Natural Number Template$Overview>*Defining the Template<(Nested List Template$Overview>*Defining the Template<(Binary Tree Template$Overview8$Writing a Function$OverviewjVNatural Number Data Analysis and DefinitiondPNested List Data Analysis and Definition2Vector Template>*Defining the Template$*Overview$1Overview$2Overview$3Overview$NOverview6"Traversing a ListJ6Template / Operation Matrix$OverviewJ6Template / Operation Matrix2Building a List$OverviewJ6Template / Operation Matrix0 Mapping a ListJ 6Template / Operation Matrix$Overview4 Filtering a ListJ6Template / Operation Matrix$Overview4 Searching a List$Overview$Overview6"Build a StructureJ6Template / Operation MatrixJ6Template / Operation Matrix2Map a Structure$OverviewJ6Template / Operation MatrixF2Traverse a Natural Number$OverviewJ6Template / Operation Matrix@,Traverse a Nested List$OverviewJ 6Template / Operation Matrix>*Mapping a Nested ListJ6Template / Operation Matrix$OverviewB.Searching a Nested List$OverviewJ6Template / Operation Matrix<(Traverse Binary Tree$OverviewJ6Template / Operation Matrix$OverviewJv6Template / Operation Matrix@},Building a Binary Tree$OverviewJ6Template / Operation Matrix>*Mapping a Binary Tree$OverviewJ6Template / Operation Matrix$OverviewJ6Template / Operation MatrixB.Searching a Binary Tree$OverviewJ6Template / Operation Matrix:a &Traversing a Vector$c OverviewJj 6Template / Operation Matrix6q "Building a Vector$s OverviewJz 6Template / Operation Matrix, Map a VectorJ 6Template / Operation Matrix$ Overview2 Search a VectorJ 6Template / Operation Matrix$ OverviewH 4Sorting a List or a VectorH 4Sorting a List or a Vector/ 0DTimes New Roman\|v 0( 0DArialNew Roman\|v 0( 0" DLucida Console\|v 0( 01 ` .  @n?" dd@  @@`` `,K @:; < =>?@  9456       % 3 - %!&.7-"#$')(,*+ /0 1 2 8c $@3@{uʚ;2Nʚ;g4sdsdv 0ppp@ <4!d!d` 0LH}<4dddd` 0LH} <4BdBd 0L? %cOEmulating a Programming Tutor David M. Smith * OverviewWhat do you need help with? Getting Started Data Definition and Analysis Contract and Purpose Specifying Examples Writing a Function Making a Template Creating the Definition Testing the Code&  Getting StartedRead your problem carefully Ask yourself: Do you know the type(s) of data being processed? Do you know the name(s) of the function(s) required? Are you given examples of the behavior? What kind of operation are you performing on the data? Are you creating a new instance of the data collection? - Build Are you just touching all the data items? - Traversal Are you creating a collection of the same size but different content? - Map Are you reducing the size of the collection by some criteria? - Filter Are you summarizing (like adding up) information from the collection? - Fold Are you looking for some specific item in the collection? - Search Are you re-ordering the data? - Sort@** Data being Processed?ZThe data types will always be specified somewhere in the problem statement. They will be one of the following: Number String Structure List of something Binary tree Nested list Vector Figure out which data types you need for your problem and make a note of them. We ll worry about the details later.6pIupIu$Name(s) of the function(s) required?$The problem statement usually specifies the name of the main function If so, make a note of this name If not, or if you need helper functions that are not named, create a meaningful name for each function Good names might be list-sort-helper, or use-this-CD-record? A bad name would be X or Function-42 since theese give you no clue as to the functionality Make a note of these names.F g*7F g*   78EExamples of the behavior?Examples are powerful clues to the logic of your solution. Work through each example by hand, visualizing how your algorithm arrives at the answer they suggest. If there are not sufficient examples, create enough of them to be able to think through what you need to achieve. Try to cover all the cases suggested in the problem statement Numbers outside the specified range Empty lists or trees &Q:Q:Operation on the data?#We need to think abstractly about the nature of the processing. All data processing involves consuming one or more source data collections, and producing probably one resulting collection. The character of the source and result collections tells you the nature of the algorithm you require. &@@Build OperationsBuilding occurs when you are given data in a different form and asked to construct a new collection in this form. The source of the data for building this data type is frequently traversal of a different type of data collection.Map OperationsMapping is recognized when you are asked for a new collection of the same size and type as the existing data but the content of each item is changed by some criteria. It will require traversal of the source data and creation of another collection of the same type.$ J Filter OperationsFiltering is recognized when you must create a new collection of the same type, but containing fewer data items. The criteria by which you eliminate data items will be implemented as the filtering function.Fold OperationsFolding occurs when you consume a collection of items, and are asked for a single result. That result might be the sum or product of some content of each data item&ZJZJSearch OperationsAs the name suggests, searching a collection involves a partial traversal looking to satisfy some criterion. It is closely related to folding in that both return a single result rather than another collection. The distinction might be that fold requires traversal of the entire array, while search usually has an early termination. Traversal of the complete collection is usually associated with failure of the searchSort OperationsAs the name suggests, sorting implies ordering the data according to some ranking criteria Its application is normally confined to linear collections (lists, vectors) rather than non-linear. TraversalIf your application requires you to examine all of the data items, you will do a traversal. Frequently, traversal is combine with building a different data structure in a data conversion application (Writing the Data Definition and Analysis(Earlier, we determined the nature of the data collections we must process. Now, we put a standard data analysis and definition section at the beginning of our Scheme program file. The first line is always: ;; Data Analysis and Definition After that, we need one definition block for each data collection type: List Vector Structure Something Natural Number Something Else Nested List Yet another Binary TreeP Hc Hc !List Data Analysis and Definition;; a list of is either ;; empty, or ;; (cons X loX) where X is a , ;; and loX is a list of ,=5$! List Template;; a list of is either ;; empty, or ;; (cons X loX) where X is a , ;; and loX is a list of ,=5,)Traversing a List -+Mapping a List .,Filtering a List 0-Searching a List /*Building a List %"Writing a FunctionFGiven the following contract: A function can be defined as follows:&Structure Data Analysis and Definition &#Structure Template;; Data Analysis and Definition: (define-struct <name> (<label-1> & <label-n>)) ;; e.g. (define-struct CD (genre title artist)) ;; A <name> is a structure defined as ;; (make-<name> <i-1> & <i-n>) ;; where <i-1> is a <data-type> specifying the <whatever> ;; & ;; and <i-n> is a <data-type> specifying the <whatever>\\>)1=2/Build a Structure;; Data Analysis and Definition: (define-struct <name> (<label-1> & <label-n>)) ;; e.g. (define-struct CD (genre title artist)) ;; A <name> is a structure defined as ;; (make-<name> <i-1> & <i-n>) ;; where <i-1> is a <data-type> specifying the <whatever> ;; & ;; and <i-n> is a <data-type> specifying the <whatever>\\>)1=31Map a StructureTo map a structure, you start from the structure template. You create a new structure applying a specific transformation function to each structure item:(; _;`+Natural Number Data Analysis and DefinitionY;; a Natural Number is either ;; 0, or ;; (add1 nn) where nn is another natural numberZZ,2 '$Natural Number Templatel;; Data Definition ;; a Natural Number is either ;; 0, or ;; (add1 nn) where nn is another natural numbermm,E 42Traverse a Natural Number  (Nested List Data Analysis and Definition;; a nested list of is either ;; empty, or ;; (cons nloX nloX), or ;; (cons X nloX) where X is a , ;; and nloX is a nested list of >B 5!(%Nested List Template;; a nested list of is either ;; empty, or ;; (cons nloX nloX), or ;; (cons X nloX) where X is a , ;; and nloX is a nested list of >B 5!53Traverse a Nested List 64Mapping a Nested List 75Searching a Nested List !(Binary Tree Data Analysis and Definition(define-struct node (data left right)) ;; A BT-node is either ;; false, or ;; a structure defined as (make-node d l r) ;; where d is a Scheme data item, and ;; l and r are BT-nodes,)&Binary Tree Template;; Data Analysis and Definition (define-struct node (data left right)) ;; A BT-node is either ;; false, or ;; a structure defined as (make-node d l r) ;; where d is a Scheme data item, and ;; l and r are BT-nodes,(86Traverse a Binary Tree 98Building a Binary Tree :7 Insert into a Binary Search Tree <:Searching a Binary Tree =;Searching a Binary Search Tree ;9Mapping a Binary Tree # #Vector Data Analysis and Definition *'Vector Template ><Traversing a Vector ?=Building a Vector @> Map a Vector A?Search a Vector " Writing the Contract and Purpose Each function  either the main function or any required helper functions must have a contract and purpose section. This specified the name, the type and order of the items consumed and the type of the item produced: Writing Examples Defining the Template Creating the DefinitionSo now we actually write the code. We have the template(s) for the data collections we are processing We know the fundamental operation(s) we will perform on those data collections The following screens will provide generic code for solving your problem. The code will include specific functions (names enclosed in  <& > ) that will be needed to complete the project. Obviously, these must be written. Some may result in manipulating other collections by this same process. The matrix on the following chart takes us to the right combination of template and operation to guide us to the creation of the right code. 6%%+(Template / Operation Matrix B@Sorting a List or a VectorThis topic is too extensive to provide coding details here. Any good algorithms book will describe the algorithms. You will want to choose between the following: Heap Sort if you need just a few of the items in order Quick Sort if you are sure the data are not already sorted Otherwise Merge Sort The above are all O(NlogN). Never use O(N2) algorithms like: Insertion Sort Selection Sort Bubble Sort>* . ; **=O Testing  Code for Data Analysis Code for Contract and Examplesp;; Contract: new-CDs: (listof CD) symbol number ;; -> (listof string) ;; Purpose: list the titles of the CDs by the artist ;; specified by the symbol since the year specified by ;; the number ;; Examples (define my-CDs (list (make-CD 'soft-rock "Lovely" 'John-Tesh 12 1996) (make-CD 'pop "Thriller" 'Michael-Jackson 10 1996) (make-CD 'pop "Glory" 'John-Tesh 8 1999) (make-CD 'classics "Tchaikovski No 1" 'John-Tesh 4 2001) (make-CD 'pop "Lost World" 'Run_DMC 8 1999))) ;; (new-CDs my-CDs 'John-Tesh 1997) ;; should produce (list "Glory" "Tchaikovski No 1") qq>c   U   Code for TemplatesR;; Template(s) (define (process-CD-list here) (cond [(empty? here) ...] [else (... (process-CD (first here)) ... (process-CD-list (rest here)))])) (define (process-CD a-CD) (... (CD-genre a-CD) ... (CD-title a-CD) ... (CD-artist a-CD) ... (CD-tracks a-CD) ... (CD-year a-CD))) SS1Code for Definitions;; Definition(s) (define (new-CDs here this-artist this-year) (cond [(empty? here) empty] [(use-this-CD (first here) this-artist this-year) (cons (get-CD-data (first here)) (new-CDs (rest here) this-artist this-year))] [else (new-CDs (rest here) this-artist this-year)])) ;; Contract: use-this-CD: CD symbol number-> boolean ;; Purpose: determine whether this CD is acceptable ;; artist must match the symbol ;; year must be greater than the number (define (use-this-CD a-CD this-artist this-year) (and (symbol=? (CD-artist a-CD) this-artist) (> (CD-year a-CD) this-year))) ;; Contract: get-CD-data: CD -> string ;; Purpose: extract the data for the result list (define (get-CD-data a-CD) (CD-title a-CD) )Z,A&Code for Tests2;; Tests (new-CDs my-CDs 'John-Tesh 1997) (list "Glory" "Tchaikovski No 1") (new-CDs empty  Anyone 1997) empty (new-CDs my-CDs Pat-Boone 1997) empty , U  Questions?  P> ` ` ̙33` 333MMM` ff3333f` f` f` 3>?" dd@?" dd@  " @ ` n?" dd@   @@``PR    @ ` ` p>> tl(    6 `  T Click to edit Master title style! !  0 p   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  0 ``  \*H  0޽h ? ̙33 Default Design 0 0(   x  c $p  x  c $ `    H  0޽h ? ̙33*  @ 4j(  4r 4 S N`   r 4 S Bp    4 0@!0!0 4 0@!!0!0 4 0@j!0!0 4 0@/!0!0 4 00  @6!0!0  4 0P  @=!0!0  4 0p 0 @D!0!0  4 6@!0!0H 4 0޽h ? ̙33f     P8 (  8r 8 S T`  T r 8 S pTp  T  8 0p@h!0!0 8 0 p @o!0!0 8 0p p @v!0!0 8 0 p @}!0!0 8 0p0@!0!0  8 0@L!0!0  8 0`@S!0!0  8 0@@Z!0!0  8 0 p @!0!0 8 0 @a!0!0 8 s *3`P@!0!0" 8 s *`P@!0!0 8 6pP@!0!0H 8 0޽h ? ̙33.  ``n(  `r ` S (`   r ` S دp   " ` s *`P@!0!0 ` 03`P@!0!0H ` 0޽h ? ̙33.  pdn(  dr d S D`   r d S p   " d s *`P@!0!0 d 03`P@!0!0H d 0޽h ? ̙33.  hn(  hr h S `   r h S Hp   " h s *`P@!0!0 h 03`P@!0!0H h 0޽h ? ̙33.  ln(  lr l S tT`  T r l S 0T  T " l s *`P@@!0!0 l 03`P@!0!0H l 0޽h ? ̙33.  pn(  pr p S `   r p S p   " p s *`P@!0!0 p 03`P@!0!0H p 0޽h ? ̙33.  tn(  tr t S `   r t S `p   " t s *`P@!0!0 t 03`P@!0!0H t 0޽h ? ̙33.  xn(  xr x S `   r x S ,p   " x s *`P@!0!0 x 03`P@!0!0H x 0޽h ? ̙33.  |n(  |r | S `   r | S Lp   " | s *`P@!0!0 | 03`P@!0!0H | 0޽h ? ̙33.  n(  r  S `   r  S Tp   "  s *`P@!0!0  03`P@!0!0H  0޽h ? ̙33:  z(  x  c $p`   x  c $,p   "  s *`P@!0!0  03`P@!0!0H  0޽h ? ̙33.  n(  r  S x`   r  S 4p   "  s *`P@!0!0  03`P@!0!0H  0޽h ? ̙33     <2 (  <| < T 3fԔԔ?PPr < S g`    < S wp   ._ ~V." < s *`P@!0!0 < 6 @p @@!0!0 < 6 @ @G!0!0 < 6 @ @!0!0  < 6 @@!0!0  < 60 @@\!0!0  < 6 p @c!0!0  < 6 ` @!0!0  < 6 @!0!0 < 6 @!0!0 < 03`P@!0!0H < 0޽h ? ̙33'   D/(  Dr D S `   " D s *`P@!0!0 D S ~ 3 f8cԔ?   D B@GH<5 `   ,$D0 wCthe type of item on the list can be any Scheme or user defined itemDD D B Gb)H  p p,$D0 @ Either empty    D B G.H( ` p ` ,$D0 Jor (cons & )    D 03`P@!0!0N  D  W>1  ?Done!Arial Black5HY?fH0 ,$D0H D 0޽h ??0DD D ̙33Z    $0 (  x  c $ `   "  s *`P@!0!0  S ~ 3 f8cԔ? p    0   6Start with the list data definition This function will deal with one (cons & ) cell, not the whole list.6h T3  Z 3 fԔ?y  (define (process-X-list here) (cond [(empty? here) ...] [else (... (process-X (first here)) ... (process-X-list (rest here)))])) !y  03`P@!0!0l p   9p  ,$D0f2   6@f2   60@  xb B HZG0*HIoH@x@   < p p ,$D0 NFirst, check the base case^2  6PY^2  6Y 0 X2  0I @X2  0pYl @  K@I,$D0xb B HZG*HZAI5ox rb B BZG!H]=Iso X  <L3 @0 ,$D0 |Now, disassemble the cons cell  processing the first and rest??l    #K ',$D0rR  BGHLIoP [ xb B HZG*HMIpo 8 C  <l8  ,$D0 EBut the first item is of type X, and the rest is loX, so process themFF1X2  0Y X2  0 p yX2 ! 0 YX2 " 0 P N $  W>1  ?Done!Arial Black5HY?fH0 ,$D0H  0޽h ?_ " ! ̙33  0,(  x  c $A`   "  s *`P@!0!0  0D @  dStart with the template    ZL 3 fԔ?  ^;; Contract: traverse-list: (listof X) -> (define (traverse-list here) (cond [(empty? here) ] [else ( (first here) (traverse-list (rest here)))])) ,:}  03`P@N!0!0X2  0PYX2  0Y 0 X2  0I @X2  0pYX2  0Y X2  0 p yX2  0 YX2  0 P N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  ZY 3 fԔ?  (define (process-X-list here) (cond [(empty? here) ...] [else (... (process-X (first here)) ... (process-X-list (rest here)))])) !y^2 # 69^2 $ 6 0 X2 ' 0 ` ) BdG(5H @ ,$D0 LUpdate the function name * BhGH @ ,$D0 LUpdate the function name  + BlGH   ,$D0 e1Call the function that will initialize the result22  , BpGDHB  pP,$D0 f2Call the function that will insert into the result33H  0޽h ?O@)*+, ̙33  @(  x  c $v`   "  s *`P@!0!0  0y @  dStart with the template    ZX 3 fԔ?  _;; Contract: map-list: (listof X) -> (listof Y) (define (map-list here) (cond [(empty? here) ] [else (cons ( (first here)) (map-list (rest here)))])) >  03`P@!0!0X2  0PYX2  0Y 0 X2  0I @X2  0pYX2  0Y X2  0 p yX2  0 YX2  0 P N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z 3 fԔ?  (define (process-X-list here) (cond [(empty? here) ...] [else (... (process-X (first here)) ... (process-X-list (rest here)))])) !yX2  09X2  0 0 X2  0 `  BG6H p ,$D0 LUpdate the function name  BԝGwH p ,$D0 LUpdate the function name   BGH   ,$D0 e1Call the function that will initialize the result22  BG]H` @ p,$D0 _+Call the function that will change the item,,H  0޽h ?O@ ̙337  P/(  x  c $`   "  s *`P@ !0!0  0p @  dStart with the template  2  Z@ 3 fԔ?0 ' ;; Contract: filter-list: (listof X) -> (listof X) (define (filter-list here) (cond [(empty? here) ] [( (first here)) (cons (first here) (filter-list (rest here)))] [else (filter-list (rest here)))])) >!  03`P@!0!0X2  0PYX2  0Y 0 X2  0I @X2  0pYX2  0Y X2  0 p yX2  0 YX2  0 P N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  ZĖ 3 fԔ?  (define (process-X-list here) (cond [(empty? here) ...] [else (... (process-X (first here)) ... (process-X-list (rest here)))])) !yX2  09X2  0 0 X2  0 `  B`ϖG@Hڣ 0,$D0 LUpdate the function name  BӖGLtH< 0,$D0 LUpdate the function name   BזGH P  ,$D0 e1Call the function that will initialize the result22   BۖG<H @ p,$D0 g3Call the function that will decide to keep the item44H  0޽h ?O@ ̙33  f^`(  x  c $|`   "  s *`P@!0!0  0 @  dStart with the template    Z 3 fԔ?  P;; Contract: search-list: (listof X) -> boolean (define (search-list here) (cond [(empty? here) false] [( (first here)) true ] [else (search-list (rest here)))])) >m  03`P@!0!0X2  0PYX2  0Y 0 X2  0I @X2  0pYX2  0Y X2  0 p yX2  0 YX2  0 P N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z 3 fԔ?  (define (process-X-list here) (cond [(empty? here) ...] [else (... (process-X (first here)) ... (process-X-list (rest here)))])) !yX2  09X2  0 0 X2  0 `  BG^>H p0 ,$D0 LUpdate the function name  BX GlH  p0 ,$D0 LUpdate the function name  BG(H  @p ,$D0 a-Call the function that will decide this is it..H  0޽h ??0 ̙33     pG (  x  c $`   "  s *`P@!0!0  0 @  'Needs two functions: Initialize Insert N   r  ZH) 3 fԔ?   h;; Contract: insert-in-list: X (listof X) -> (listof X) (define (insert-in-list X here) (cons X here))i i, 4  03`P@!0!0X2  0PYX2  0Y 0 X2  0I @X2  0pYX2  0Y X2  0 p yX2  0 YX2  0 P N   W>1  ?Done!Arial Black5HY?fH0 ,$D0F  Z$- 3 fԔ?   N;; Contract: initialize-list: -> (listof X) (define (initialize-list) empty)O O"&X2  09X2  0 0 X2  0 `H  0޽h ? ̙33  [Ss(  r  S 9`   r  S p:      03`P@!0!0  ZP< 3 fԔ? 0  z(define (<name> <param-1> & <param-n>) ( <function body> ))> >,"  0`P@!0!0  B$FG,H P,$D0 CThe word define  BIGVHT  ` ,$D0 LThe name of the function  BMGH p @00 ,$D0 Q0 or more parameters consumed  BpQGXMHϸ  @,$D0 PBody of code to be evaluated  B4UG1HS  `@,$D0 uAFunction produces the Scheme item returned by evaluating the bodyBBN   W>1  ?Done!Arial Black5HY?fH0 ,$D0  ZY 3 fԔ?  @;; Contract: <name>: <cons-1> & <cons-n> -> <result> ;; Purpose: <a written description of the meaning of each ;; item consumed and the nature of the result>   BcGĕH PP,$D0 Ltype of the parameter(s)  BfGHƻ  pP,$D0 Lname of the parameter(s)H  0޽h ?p     ̙33      (    Zo 3 fԔ?   b(define-struct CD (genre title artist tracks year)) ;; A CD is a structure defined as (make-CD g ti a tr y) ;; where g is a symbol specifying the genre ;; ti is a string specifying the title ;; a is a symbol specifying the artist ;; tr is a number specifying the tracks ;; and y is a number specifying the year it was recordedc cbR4 S `r  S p`   "  0`P@ !0!0  B(iGHq ,$D0 b.For structures, specify the names of each item//  BDGXHW P P,$D0 BThen the types  BGhLH<;   ,$D0 ? And meaning    03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0H  0޽h ??0  ̙33     0  (  x  c $Ћ`   "  0`P@m!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  c \ 3 f8cԔ?@  X2  0X2  0 0 X2  0X2  0`  f  Z 3 fԔ?  ;; Template (define (process- an-instance) (... (- an-instance) ... ... ((- an-instance)))) l    ,$D0xb B HZG)HIoH   < 0 0 ,$D0 BStructure namel      ,$D0rb B BGHI o    < p  ,$D0 BList each itemH  0޽h ?/@ ̙33   !(  x  c $`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0,  ZD 3 fԔ?)   V;; Definition (make-<name> item-1 & item-n), ,X2  0X2  0 0 X2  0X2  0`    0 p  ACreating a new structure follows exactly from the data definitionB B   `0e0e 3 f8cԔ?    H  0޽h ? ̙33    x   (  x  c $˜`     03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  ZĘ 3 fԔ?   ;; Definition (define (map- an-instance) (make- ( (- an-instance)) ... ( (- an-instance)))) X2  0X2  0 0 X2  0X2  0`    0pޘ p  V  "  0`P@!0!0r  S ٘P   c  Z 3 fԔ?' ;; Template (define (process- an-instance) (... (- an-instance) ... ... (- an-instance))) H  0޽h ? ̙33   (  r  S `   "  0`P@$!0!0  c  3 f8cԔ?    BG1Hi p p,$D0 <Either 0    BG.H( ` p ` ,$D0 Jor (add1 & )    03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0H  0޽h ?/   ̙33-   (  x  c $`   "  0`P@!0!0  c  3 f8cԔ?0    03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z 3 fԔ?   ;; Template (define (process-NN a-num) (cond [(zero? a-num) ...] [else (... a-num ... (process-NN (sub1 a-num)))])) *cz p     0 ,$D0`2   0@`2   00@  rb B BZG0*HIoH@x@   6  p p ,$D0 NFirst, check the base casel ` `  ` ` ,$D0xb B HZGHIfo``   <$ @ ,$D0 GProcess this numberX2  0P`X2  0` @ X2  0`X2  0 l {  { ,$D0xb  HGHI)o{8   6 p P ,$D0 NMove towards the base caseH  0޽h ??`  ̙33      (  x  c $D`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  ZT" 3 fԔ? ;; Template (define (process-NN a-num) (cond [(zero? a-num) ...] [else (... a-num ... (process-NN (sub1 a-num)))])) *c^2  6p^2  6p @ X2  0P`X2  0` @ X2  0`X2  0   Z* 3 fԔ?I p ;; Definition (define (traverse-NN a-num) (cond [(zero? a-num) ] [else ( a-num (traverse-NN (sub1 a-num)))])) -v  B`5GhH  ,$D0 W#Initialize the resulting collection$$  B9GFH   ,$D0 p<Function to insert this number into the resulting collection==H  0޽h ?/  ̙333   ;(  r  S L;`   "  0`P@(!0!0  c T, 3 f8cԔ?    B@GH<5 `   ,$D0 wCthe type of item on the list can be any Scheme or user defined itemDD  BDGb)H  p p,$D0 @ Either empty    BGG.H( ` p ` ,$D0 Jor (cons & )    03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0H  0޽h ??0  ̙33  | (  x  c $\P`   "  0`P@!0!0  c Q 3 f8cԔ?     03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0!  ZT 3 fԔ? P );; Template (define (process-nested-list here) (cond [(empty? here) ...] [(list? (first here)) (... (process-nested-list (first here)) ... (process-nested-list (rest here)))] [else (... (process-X (first here)) ... (process-nested-list (rest here)))]))* *2z p      ` ,$D0`2   0@`2   00@  rb B BZG0*HIoH@x@   6h` p 9 ,$D0 NFirst, check the base casel @@ 0  @@ 0 ,$D0rb  BGpH Io@0   <d P@  ,$D0 MCheck for the nested casel P  P ,$D0rb  BGH,Io   <Hi P@ ,$D0 DNormal recursionX2  0@@X2  0 `` X2  0 @   BmG\H @`,$D0 V"Tree recursion (process each part)##X2  0H  0޽h ?Op  ̙33   Y Q  (  x  c $@u`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0-  ZDx 3 fԔ?pP 5;; Template (define (proc-nested-list here) (cond [(empty? here) ...] [(list? (first here)) (... (proc-nested-list (first here)) ... (proc-nested-list (rest here)))] [else (... (proc-X (first here)) ... (proc-nested-list (rest here)))]))6 6/X2  0@@X2  0 `` X2  0 @ X2  0  Z 3 fԔ? P Q;; Definition (define (trav-nested-list here) (cond [(empty? here) ] [(list? (first here)) ( (trav-nested-list (first here)) (trav-nested-list (rest here)))] [else ( (first here) (trav-nested-list (rest here)))]))R RbQHZ  BGnH ` ,$D0 T Initialize the result collection!!  B|GH   ,$D0 ])Insert a value into the result collection**  BGH$ P  ,$D0 RCombine two result collectionsH  0޽h ??0 ̙33Y     0 q (  x  c $h`   "  0`P@ !0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0-  Z 3 fԔ?pP 5;; Template (define (proc-nested-list here) (cond [(empty? here) ...] [(list? (first here)) (... (proc-nested-list (first here)) ... (proc-nested-list (rest here)))] [else (... (proc-X (first here)) ... (proc-nested-list (rest here)))]))6 6/X2  0@@X2  0 `` X2  0 @ X2  0,  ZH 3 fԔ? P 4;; Definition (define (map-nested-list here) (cond [(empty? here) empty] [(list? (first here)) (cons (map-nested-list (first here)) (map-nested-list (rest here)))] [else (cons ( (first here)) (map-nested-list (rest here)))]))5 50  BGFH @ ,$D0 a-Change the value in the resulting nested list..  B`GeH   ,$D0 uAEverything else just reconstructs a nested list of the same shapeBBH  0޽h ?/   ̙33;     @ S (  x  c $$š`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0-  Z(Ś 3 fԔ?pP 5;; Template (define (proc-nested-list here) (cond [(empty? here) ...] [(list? (first here)) (... (proc-nested-list (first here)) ... (proc-nested-list (rest here)))] [else (... (proc-X (first here)) ... (proc-nested-list (rest here)))]))6 6/X2  0@@X2  0 `` X2  0 @ X2  09  Zњ 3 fԔ? P A;; Definition (define (search-nested-list here item) (cond [(empty? here) false] [(list? (first here)) (or (map-nested-list (first here) item) (map-nested-list (rest here) item))] [( (first here) item) true] [else (search-nested-list (rest here) item)]))B B8  BݚG)5H9 `,$D0 BTest the value  BGH   ,$D0 i5Short-circuit evaluation cuts down unnecessary search66H  0޽h ?/    ̙33c   P {(  r  S p`   "  0`P@,!0!0  c  3 f8cԔ?       B0GH  ,$D0 g3For binary trees, specify only data, left and right44.  BGKHh  ,$D0 TIf the tree contains complex types, define that type and assert it in the data fieldUU  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0H  0޽h ?/  ̙33   W O ` (  x  c $`   "  0`P@!0!0  c  3 f8cԔ?@j    03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z 3 fԔ? q  S;; Template (define (process-BT here) (cond [(not (node? here)) ...] [else (... (process-X (node-data here)) ... (process-BT (node-left here)) ... (process-BT (node-right here)))])) )z p     @ ,$D0`2   0@`2   00@  rb B BZG0*HIoH@x@   6 p } ,$D0 NFirst, check the base casez @@ 0    p  ,$D0lb  <GpH Io@0   6 Q@ ,$D0 V"Process left and right recursively##  B GhHH P 0,$D0 The order of these three calls is important  results in in-order, pre-order or post-order traversaleeH  0޽h ??P  ̙33     p  (  x  c $`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z 3 fԔ?p S;; Template (define (process-BT here) (cond [(not (node? here)) ...] [else (... (process-X (node-data here)) ... (process-BT (node-left here)) ... (process-BT (node-right here)))])) )  Z( 3 fԔ?0   j;; Definition (define (traverse-BT here) (cond [(not (node? here)) ] [else ( (node-data here) (process-BT (node-left here)) (process-BT (node-right here)))])) ,  B/G_H P 0,$D0 The order of these three calls is important  results in in-order, pre-order or post-order traversalee  B3GKsH   ,$D0 X$Initialize the resulting collection %%  B7GH  0 P,$D0 ^*Combine the data with two recursive calls ++H  0޽h ??0 ̙33^     (  x  c $=`   "  s *`P@!0!0\  0$K @  |Needs two functions: Initialize Insert [we will assume the sorting associated with a Binary Search Tree (BST)] [next slide] N g  g  03`P@!0!0X2  0PYX2  0Y 0 X2   0I @X2   0pYX2   0Y X2   0 p yX2   0 YX2  0 P   ZV 3 fԔ? 7  B;; Contract: initialize-BT: -> BT (define (initialize-BT) false)C CX2  09X2  0 0 X2  0 `H  0޽h ? ̙33    (    Z,[ 3 fԔ?! S;; Template (define (process-BT here) (cond [(not (node? here)) ...] [else (... (process-X (node-data here)) ... (process-BT (node-left here)) ... (process-BT (node-right here)))])) )x  c $[`   "  0`P@v!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Zf 3 fԔ? h;; Definition (define (BST-insert here data) (cond [(not (node? here)) (make-node data false false)] [( (node-data here) data) (error 'BST-insert "equal keys")] [( data (node-data here)) (make-node (node-data here) (BST-insert (node-left here) data) (node-right here))] [else (make-node (node-data here) (node-left here) (BST-insert (node-right here) data))])) 0   BtGݦH/P `,$D0 GNew node at a leaf    BxG\H7 ` P,$D0 GCheck for equality    B{GH ,$D0 V"Data belongs in the left sub-tree ##  BGHH0e  `0,$D0 RCompare new data to this node   BGHu< 0  ,$D0 W#Data belongs in the right sub-tree $$  0  0 gEvery exit creates a new node H  0޽h ?_P    ̙33       (    Z 3 fԔ? S;; Template (define (process-BT here) (cond [(not (node? here)) ...] [else (... (process-X (node-data here)) ... (process-BT (node-left here)) ... (process-BT (node-right here)))])) )x  c $D`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z0 3 fԔ?   x ;; Definition (define (search-BT here item) (cond [(not (node? here)) ] [( (node-data here) item) ] [else ( (search-BT (node-left here) item) (search-BT (node-right here) item))]))   /   0  8If the tree is not ordered on the data you are searching49  3'  BشG"H  { ,$D0 \(Bad return (see contract for specifics) ))   BGwH= ` ,$D0 d0Good return (either true, or extract some data) 11  BG9H2  0,$D0 Look left and right, and combine the answers {use (or & ) for booleans} LL,-H  0޽h ??0 ̙33   F >   (    Z 3 fԔ?q S;; Template (define (process-BT here) (cond [(not (node? here)) ...] [else (... (process-X (node-data here)) ... (process-BT (node-left here)) ... (process-BT (node-right here)))])) )x  c $›`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0!  ZΛ 3 fԔ?  );; Definition (define (search-BST here item) (cond [(not (node? here)) ] [( (node-data here) item) ] [( item (node-data here)) (search-BT (node-left here) item)] [else (search-BT (node-right here) item)]))* *0   0lڛ  4If the tree is ordered on the data you are searching45  3'   B0G"H  ` ,$D0 \(Bad return (see contract for specifics) ))    BGwH= ` ,$D0 d0Good return (either true, or extract some data) 11   B`Gt5Hݹ @,$D0 n:Because the data are ordered, you know which way to look. ;;H  0޽h ??0    ̙33       > (      Z  3 fԔ? S;; Template (define (process-BT here) (cond [(not (node? here)) ...] [else (... (process-X (node-data here)) ... (process-BT (node-left here)) ... (process-BT (node-right here)))])) )x   c $`   "   0`P@!0!0   03`P@!0!0N    W>1  ?Done!Arial Black5HY?fH0 ,$D0   Z8 3 fԔ?{  _;; Definition (define (map-BT here) (cond [(not (node? here)) false] [else (make-node ( (node-data here)) (map-BT (node-left here) data) (map-BT (node-right here) data))])) '   0    RNote: if you started with a BST, this mapping might not preserve that relationshipS Sd`8   BGvaHD  ,$D0 X$Function that changes the node data %%H   0޽h ?  ̙33       (  x  c $`   "  0`P@0!0!0  Z 3 fԔ?)  $;; A Vector of Scheme items is a homogeneous collection of ;; 0 or more Scheme items defined as either ;; (make-vector n <fill>), or ;; (build-vector n ( num -> X )), or ;; (vector item-0 & item-n-1) ;; where n is the number of data items, and ;; item-0 & item-n-1 are instances of the same ;; Scheme item type\ \\&  Bh&G'H  ,$D0 LIf this form is used, the vector is filled with the optional fill data, or 0MM  B@*GvHð P P,$D0 If this form is used, the vector is loaded with data computed by applying the given function to the numbers 0 & (n-1)vv  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0H  0޽h ?/  ̙33       (  x  c $t`   "  0`P@!0!0  Z0 3 fԔ? 4;; Data Analysis and Definition ;; (make-vector n <fill>), or ;; (build-vector n ( num -> X )), or ;; (vector item-0 & item-n-1) ;; where n is the number of data items, and ;; item-0 & item-n-1 are the same type items +  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z< 3 fԔ?`  Z;; Template: (define (process-vector v) (do [(index 0 (add1 index)) (... ... ...)] ; other variables as required [(= index (length vector)) ...] ;terminating condition (... (vector-ref v index) ... ; code body (vector-set! v index ...))))   BGGIH `P,$D0 PIndex down the vector from 0  B(KGLH  0p ,$D0 CStop at the end  B`NG(H ` ,$D0 MAccess data in the vector  B$RGWH `,$D0 NReplace data in the vectorH  0޽h ?O@     ̙33X      ` (  x  c $W`   "  0`P@!0!0  03`P@!0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  ZZ 3 fԔ?  Z;; Template: (define (process-vector v) (do [(index 0 (add1 index)) (... ... ...)] ; other variables as required [(= index (length vector)) ...] ;terminating condition (... (vector-ref v index) ... ; code body (vector-set! v index ...))))    Z e 3 fԔ?   s;; Definition (define (traverse-vector v) (do [(index 0 (add1 index)) (res )] ; final answer [(= index (length vector) res)] ;terminating condition ( (vector-ref v index) res))) >PG<   BpGH P ,$D0 W#Initialize the resulting collection$$   BtG1H @,$D0 d0Insert a data item into the resulting collection11  BtxGH  ,$D0 T Produce the resulting collection!!H  0޽h ??0  ̙33   f ^   (  x  c $~`   "  0`P@j !0!0  03`P@c !0!0N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  Z 3 fԔ?  Z;; Template: (define (process-vector v) (do [(index 0 (add1 index)) (... ... ...)] ; other variables as required [(= index (length vector)) ...] ;terminating condition (... (vector-ref v index) ... ; code body (vector-set! v index ...)))) T  Z 3 fԔ?  &;; Definition (define (build-vector source) (do [(v (make-vector ( source))) (index 0 (add1 index)) (src source)] ; source data [(= index (vector-length v) v)] ;terminating condition (vector-set! v index ( src)) (set! src ( src))))' 'P{    BЗG3Hā P ,$D0 SInitialize the resulting vector     BG1H} p,$D0 `,Insert a data item into the resulting vector--   BiGH  ,$D0 QAdvance the source collection   BGHuf  @@P ,$D0 T Initialize the source collection!!H  0޽h ?O@    ̙33v   &   ~ (   x   c $`   "   0`P@z !0!0   03`P@s !0!0N    W>1  ?Done!Arial Black5HY?fH0 ,$D0   Z  3 fԔ?  Z;; Template: (define (process-vector v) (do [(index 0 (add1 index)) (... ... ...)] ; other variables as required [(= index (length vector)) ...] ;terminating condition (... (vector-ref v index) ... ; code body (vector-set! v index ...))))    Zd 3 fԔ? p ;; Definition (define (map-vector src) (do [(v (make-vector (vector-length src))) (index 0 (add1 index))] [(= index (vector-length v) v)] ;terminating condition (vector-set! v index ( (vector-ref src index))))) >!'    BGH'  ,$D0 SInitialize the resulting vector     BxŝG1H} p,$D0 `,Insert a data item into the resulting vector--   B`ɝGH  P ,$D0 ^*Change the item from the source collection++H   0޽h ??0    ̙338      $0 (  $x $ c $$ϝ`   " $ 0`P@ !0!0 $ 03`P@ !0!0N $  W>1  ?Done!Arial Black5HY?fH0 ,$D0 $ ZН 3 fԔ?  Z;; Template: (define (process-vector v) (do [(index 0 (add1 index)) (... ... ...)] ; other variables as required [(= index (length vector)) ...] ;terminating condition (... (vector-ref v index) ... ; code body (vector-set! v index ...))))  $ Z۝ 3 fԔ?   h;; Definition (define (search-vector src item) (do [(index 0 (add1 index)) (answer false)] [(or answer (= index (vector-length src)) answer)] (set! answer ( (vector-ref src index) item)))) >$d3 $ BGثH#  ,$D0 IInitialize the answer  $ BG1H} p,$D0 U!Terminate if found or out of data""  $ BtGHW  @p,$D0 Y%Check the item from the source vector&&  $ BG$H[ 0 0 ,$D0 EReturn the answerH $ 0޽h ?O@$ $ $ $ ̙33  0 (  r  S `   r  S p   "  0`P@u!0!0(  Z 3 fԔ?  R;; Contract: <function-name>: <cons-1> & <cons-n> -> <result> ;; Purpose: <a written description of the meaning of each ;; item consumed and the nature of the result>   03`P@!0!0  B<GnH@   P,$D0 SType of each data item consumed  N   W>1  ?Done!Arial Black5HY?fH0 ,$D0  B G6BH.U 0 p0 ,$D0 MType of the item producedH  0޽h ?/   ̙33.  @Pn(  Pr P S `   r P S p   " P s *`P@|!0!0 P 03`P@!0!0H P 0޽h ? ̙33   b Z P T(  Tr T S `   | T T 3fԔԔ?PP^ T 0" p VThe template(s) tell you all you could possibly do with the data collection(s) you are processing. For each collection you need, follow the instructions below: The first line is always: ;; Template(s) After that, we need one template for each data collection type: List Vector Structure Natural Number Nested List Binary Tree (including BST)h   @ N  @N_ ~V. T 6 p @!0!0  T 6  @!0!0  T 6  @!0!0  T 6@!0!0  T 60@!0!0  T 6 p @!0!0" T s *`P@*!0!0 T 03`P@!0!0H T 0޽h ? ̙33.  `Xn(  Xr X S /`   r X S 0   " X s *`P@1!0!0 X 03`P@!0!0H X 0޽h ? ̙33 I  HHpo`H(  x  c $P6`   "  s *`P@2!0!0  03`P@3!0!0e.v    #"."tttttt   <B? C  R  @`  <J?C  R  @` ~ <R? C R  @` | <Z? C  R  @` z <Pb?C  R  @` x <j?C R  @` v Bk?C RTraverse   @` q Bz?  NSort @` o B4?   PSearch @` m B?   PFilter @` k B<?+   MMap @` i B?+  OBuild @` g <,?C T  @` 8 <4?   R  @` 7 <̱?  R  @` 6 <?  R  @` 5 <@?  R  @` 4 <Hɞ?  R  @` 3 <(ў?  R  @` 1 <؞?    R  @` 0 <?   R  @` / <P?    R  @` . <?   R  @` - <?  R  @` , < ?   R  @` * < ?    R  @` ) <?   R  @` ( <?   R  @` ' <?   R  @` & <X'?   R  @` % </?   R  @` # <6? +   R  @` " <>?+   R  @` ! <8F? +   R  @`   <M? +  R  @`  <U?+  R  @`  <`]?+   R  @`  <e?  +  R  @`  <l? +  R  @`  <t? +  R  @`  <@|?  +  R  @`  <? +  R  @`  <?+  R  @`  Bč?  C PVector @`   B<? C U Binary Tree   @`   Bأ? C U Nested List   @`   B0?  C XNatural Number @`   Bح? C S Structure   @`   B?C NList @``B @ 0o ? ZB A s *1 ?C CZB C s *1 ?+ + ZB D s *1 ?  ZB E s *1 ?  ZB F s *1 ?  `B H 0o ? `B I 0o ?ZB K s *1 ?ZB L s *1 ?  ZB M s *1 ?  ZB N s *1 ?ZB O s *1 ?  `B P 0o ?  ZB h s *1 ?ZB w s *1 ?   0`  ? Operation 2   0ş  @ Collection 2 |  TW3?XImpact|  TW3?XImpact |  TW3?XImpact |  TW3?XImpact  |  TW3?XImpact |  TW3?XImpact   ZW3?XImpact    ZW3?XImpact   0P@!0!0  0@@!0!0  0@ @!0!0  0  @ !0!0  0  @!0!0  0s  @!0!0  0 p@ !0!0  0 P@!0!0  0s 0 @!0!0  0 0 @!0!0  0 0P@!0!0  00P@!0!0  0@0@}!0!0  0s 0 @!0!0  0`P@a !0!0  0@`@q !0!0  0 ` @ !0!0  0s ` @ !0!0  0 `p@ !0!0dr  <ZoLB  c $D0 0LB  c $D  0  @!0!0|  TW3?XImpact  |  TW3?XImpactl P |  TW3?XImpact |  TW3?XImpact t |  TW3?XImpact |  TW3?XImpactl P   0 0 @!0!0  ZW3?XImpact 0 H  0޽h ? ̙334  (t(  (r ( S `   r ( S ,p   " ( 0`P@ !0!0 ( 03`P@ !0!0H ( 0޽h ? ̙33.  Ln(  Lr L S `   r L S \p   " L s *`P@!0!0 L 03`P@!0!0H L 0޽h ? ̙33  JB (  x  c $\`   r   S p      03`P@!0!0H  0޽h ? ̙33  z (  ~  s *8`     C x 3 f8cԔ?'    BLG:UHr p `,$D0 U!Order and types of items consumed""  BGH4 ,$D0 A Type produced  BGH P @,$D0 SFree form discussion of purpose    B\GHUm @ 0,$D0 U!At least one call to the function"""   s *`P@!0!0   03`P@!0!0H  0޽h ?O@ ̙33   (  ~  s *`     C xx 3 f8cԔ?     BGH%   ,$D0 i5Derived precisely from the data definition for a list66  BPG?H;  PP ,$D0 X$Access to each item in the structure%%  B(GH  ,$D0 A Generic names  B\GߵH 7  ,$D0 A Generic names"   s *`P@!0!0   03`P@!0!0H  0޽h ?O@ ̙33  D<(  ~  s *%`     C x& 3 f8cԔ?g  "  s *`P@!0!0  03`P@!0!0H  0޽h ? ̙33  D<(  ~  s *2`     C x3 3 f8cԔ?w   "  s *`P@!0!0  03`P@!0!0H  0޽h ? ̙33  (R(  (r ( S :`     ( 03`P@!0!0H ( 0޽h ? ̙33  00(  0H 0 0޽h ? ̙33r Tn ď2hԣ @vZS{~CBk؍Dmr*)3Lr5y''T2Xa^Q BMZ-f BlOh+'0 `h  Code for Data AnalysisDavid M. SmithnDavid M. Smithn36iMicrosoft PowerPoints@@@&@g8vGg  3& &&#TNPPT2OMiS & TNPP &&TNPP    --- !---&&r}w@ 1Sw\w0- @Times New RomanSw\w0- .2  10/8/2003   .--iyH-- @"Arialw@ 5Sw\w0- .32 9Emulating a Programming Tutoro     !!   .--Q1-- @"Arialw@ ]Sw\w0- .2 mDavid M. Smith    . .2  10/8/2003  .--"System 0-&TNPP &՜.+,D՜.+,`    ( On-screen Show Georgia Institute of Technology? CTimes New RomanArialLucida ConsoleDefault DesignEmulating a Programming Tutor OverviewGetting StartedData being Processed?%Name(s) of the function(s) required?Examples of the behavior?Operation on the data?Build OperationsMap OperationsFilter OperationsFold OperationsSearch OperationsSort Operations Traversal)Writing the Data Definition and Analysis"List Data Analysis and DefinitionList TemplateTraversing a ListMapping a ListFiltering a ListSearching a ListBuilding a ListWriting a Function'Structure Data Analysis and DefinitionStructure TemplateBuild a StructureMap a Structure,Natural Number Data Analysis and DefinitionNatural Number TemplateTraverse a Natural Number)Nested List Data Analysis and DefinitionNested List TemplateTraverse a Nested ListMapping a Nested ListSearching a Nested List)Binary Tree Data Analysis and DefinitionBinary Tree TemplateTraverse a Binary TreeBuilding a Binary Tree!Insert into a Binary Search TreeSearching a Binary TreeSearching a Binary Search TreeMapping a Binary Tree$Vector Data Analysis and DefinitionVector TemplateTraversing a VectorBuilding a Vector Map a VectorSearch a Vector!Writing the Contract and PurposeWriting ExamplesDefining the TemplateCreating the DefinitionTemplate / Operation MatrixSorting a List or a Vector Testing Code for Data AnalysisCode for Contract and ExamplesCode for TemplatesCode for DefinitionsCode for Tests Questions?PowerPoint Presentation  Fonts UsedDesign Template Slide Titles?D 8@ _PID_HLINKSAD265,3,Getting Started/266,4,Writing the Data Definition and Analysis269,6,Writing Examples270,7,Defining the Template271,8,Creating the Definition268,9,Testing 272,4,Data being consumed?+273,5,Name(s) of the function(s) required? 274,6,Examples of the behavior?275,7,Operation on the data?276,8,Build Operations277,9,Map Operations278,10,Filter Operations279,11,Fold Operations280,12,Search Operations281,13,Data Conversion264,2,Overview -1,-1,PREV -1,-1,PREV -1,-1,PREV -1,-1,PREV -1,-1,PREV -1,-1,PREV265,3,Getting Started265,3,Getting Started265,3,Getting Started281,13,Data Conversion265,3,Getting Started265,3,Getting Started265,3,Getting Started265,3,Getting Started265,3,Getting Started265,3,Getting Started265,3,Getting Started265,3,Getting Started264,2,Overview272,4,Data being consumed?272,4,Data being consumed?272,4,Data being consumed?0266,15,Writing the Data Definition and Analysis0266,15,Writing the Data Definition and Analysis0266,15,Writing the Data Definition and Analysis0266,15,Writing the Data Definition and Analysis0266,15,Writing the Data Definition and Analysis0266,15,Writing the Data Definition and Analysis)267,16,List Data Analysis and Definition.283,17,Structure Data Analysis and Definition0286,20,Binary Tree Data Analysis and Definition+288,21,Vector Data Analysis and Definition(287,22,Writing the Contract and Purpose264,2,Overview264,2,Overview270,26,Defining the Template270,27,Defining the Template270,28,Defining the Template291,20,Structure Template289,17,List Template264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview292,22,Natural Number Template264,2,Overview270,29,Defining the Template293,24,Nested List Template264,2,Overview270,30,Defining the Template294,26,Binary Tree Template264,2,Overview290,18,Writing a Function264,2,Overview3284,21,Natural Number Data Analysis and Definition0285,23,Nested List Data Analysis and Definition295,28,Vector Template270,31,Defining the Template264,2,Overview264,2,Overview264,2,Overview264,2,Overview264,2,Overview297,18,Traversing a List#296,34,Template / Operation Matrix264,2,Overview#296,35,Template / Operation Matrix298,19,Building a List264,2,Overview#296,36,Template / Operation Matrix299,19,Mapping a List#296,36,Template / Operation Matrix264,2,Overview300,20,Filtering a List#296,36,Template / Operation Matrix264,2,Overview301,21,Searching a List264,2,Overview264,2,Overview303,26,Build a Structure#296,40,Template / Operation Matrix#296,40,Template / Operation Matrix305,27,Map a Structure264,2,Overview#296,41,Template / Operation Matrix!306,30,Traverse a Natural Number264,2,Overview#296,42,Template / Operation Matrix307,33,Traverse a Nested List264,2,Overview#296,43,Template / Operation Matrix308,34,Mapping a Nested List#296,43,Template / Operation Matrix264,2,Overview309,35,Searching a Nested List264,2,Overview#296,45,Template / Operation Matrix310,38,Traverse Binary Tree264,2,Overview#296,35,Template / Operation Matrix264,2,Overview#296,47,Template / Operation Matrix312,39,Building a Binary Tree264,2,Overview#296,48,Template / Operation Matrix313,41,Mapping a Binary Tree264,2,Overview#296,47,Template / Operation Matrix264,2,Overview#296,50,Template / Operation Matrix314,41,Searching a Binary Tree264,2,Overview#296,51,Template / Operation Matrix316,46,Traversing a Vector264,2,Overview#296,52,Template / Operation Matrix317,47,Building a Vector264,2,Overview#296,53,Template / Operation Matrix318,48,Map a Vector#296,53,Template / Operation Matrix264,2,Overview319,49,Search a Vector#296,53,Template / Operation Matrix264,2,Overview"320,55,Sorting a List or a Vector"320,55,Sorting a List or a Vector&_David M. SmithDavid M. Smith  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|~Root EntrydO)Current UserSummaryInformation(}PowerPoint Document(DocumentSummaryInformation8M