How to do your Scheme homework problems
 Recall that all homeworks should be done in pairs if possible. Each pair should submit only one copy of their assignment from the account of either partner in the pair. This directive describes how to answer both expository problems and programming problems. For detailed instructions on how to format your homework as a single (.ss) file and submit it, see the HW Checklist.
Expository problems
 Some homework problems will be conventional expository questions that require a short written answer.
 All of the assigned expository problems should be answered in the same Scheme
.ss
file as your Scheme programming exercises. Each line in the answer to an expository question should begin a "comment escape character", namely ';' as the first character on that line. Alternatively, you can enclose an entire expository problem in a Scheme box (created using the commandComment Out with a Box
or in Scheme block comment brackets#
and#
(sometime called bookends). Note that you can create your entire homework file using the DrScheme editor.
Hand evaluation problems
 Most expository problems will be handevaluation problems where you are asked to evaluate a particularly Scheme program invocation. You must format your hand evaluation exactly like our examples.
 Example 1: Hand evaluation
Code Block Given (define (poly x y) (+ (expt 2 x) y)) (poly 3 5) => (+ (expt 2 3) 5)) => (+ 8 5) => 13
 Example 2: Hand evaluation
Code Block Given (define (fact n) (if (zero? n) 1 (* n (fact ( n 1))))) (fact 4) => (if (zero? 4) 1 (* 4 (fact ( 4 1)))) => (if false 1 (* 4 (fact ( 4 1)))) => (* 4 (fact ( 4 1))) => (* 4 (fact 3)) => (* 4 (if (zero? 3) 1 (* 3 (fact ( 3 1))))) => (* 4 (if false 1 (* 3 (fact ( 3 1))))) => (* 4 (* 3 (fact ( 3 1)))) => (* 4 (* 3 (fact 2))) => (* 4 (* 3 (if (zero? 2) 1 (* 2 (fact ( 2 1)))))) => (* 4 (* 3 (if false 1 (* 2 (fact ( 2 1)))))) => (* 4 (* 3 (* 2 (fact ( 2 1))))) => (* 4 (* 3 (* 2 (fact 1)))) => (* 4 (* 3 (* 2 (if (zero? 1) 1 (* 1 (fact ( 1 1))))))) => (* 4 (* 3 (* 2 (if false 1 (* 1 (fact ( 1 1))))))) => (* 4 (* 3 (* 2 (* 1 (fact ( 1 1)))))) => (* 4 (* 3 (* 2 (* 1 (fact 0))))) => (* 4 (* 3 (* 2 (* 1 (if (zero? 0) 1 (* 0 (fact ( 0 1)))))))) => (* 4 (* 3 (* 2 (* 1 (if true 1 (* 0 (fact ( 0 1)))))))) => (* 4 (* 3 (* 2 (* 1 1)))) => (* 4 (* 3 (* 2 1))) => (* 4 (* 3 2)) => (* 4 6) => 24
 Example 1: Hand evaluation
Programming problems
 Most of your homework problems will be programming problems.
 Half (50%) of your grade on programming problems depends on good style and following the recipe (program grading is described in detail on the homework grading page). In particular, these points will be based on
 25% for following the design recipe carefully and documenting your program as you are taught in course (see below), and
 25% for good programming style as taught in the course.
 The other half of your grade will be based on demonstrated correctness:
 25% for passing all of our tests and 25% for construction; and
 25% for constructing a comprehensive set of unit tests for each function in your program.
 All assigned programming problems should be done in the same
.ss
file.  At the top of your programming solution file, please put a header with the assignment number, your name and email address, and your partner's name and email address, like this:
Code Block ;; COMP 211 HW #01 ;; Christopher Warrington <chrisw@rice.edu> ;; Gregory Malecha <gmalecha@rice.edu>
 Strictly follow the formatting and documentation directives given below under the heading Requirements. The easiest way to follow these requirements is to imitate the Sample Program solution below.
Requirements
You must include a data definition and corresponding template for each form of data processed used in your homework submissions unless instructed otherwise. You only need to include a data definition and corresponding template once for an assignment, not once for every problem that uses that data defintion.
Data Definitions and Templates:
You need to devise (and document) your data design before you start writing functions that process this data. Data definitions should be documented as follows:
 Example 3. Data definition of shape:
Code Block ;; A shape is either ;; * a triangle (maketriangle b h), ;; where b and h are positivereals ;; * a square (makesquare s), ;; where s is a positivereal. (definestruct triangle (base height)) (definestruct square (side)) ;; ;; Examples: ;; (maketriangle 1 2) ;; (maketriangle 2 5) ;; (makesquare 4) ;; (makesquare 2.5) ;; ;; Template for shape # ;; shapefunction : shape > ... (define (shapefunction ... shape ...) (cond [(triangle? shape) ... (trianglebase shape) ... ... (triangleheight shape) ...] [(square? shape) ... (squareside shape) ...])) #
 Example 4. Data definition of listofnumbers:
Code Block ;; A listofnumbers is either ;; empty, or ;; (cons n lon) ;; where n is a number, and lon is a listofnumbers ;; ;; Examples: ;; empty ;; (cons 1 empty) ;; (cons 1 (cons 4 empty)) ;; ;; Template for listofnumbers # ;; lonf : listofnumbers > ... (define (lonf ... alon ...) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... ... (lonf ... (rest alon) ...) ... ])) #
 Once your have written a data definition, you can use it in the rest of the assignment.
 The template for writing a function that processes a particular kind of data (data type) is based only on the corresponding data definition, not on the particular functions that you happen define on that type. Hence, there is only one template per data type. This same template is used as the starting point for writing all functions that process that data type.
 If the type is a structure, the template should include the field extraction operations. If the type is a union, the template needs to have an appropriate
cond
statement (see example 3). If the type is recursive, the template includes the expected recursive calls on the recursive data components (see example 4).
Basic form of a function definition
 The basic form for each function that you write, including axillary and local functions, is as follows:
 Example 5. Function definition for computing area of a ring:
Code Block ;; areaofring : positiverealnumber positiverealnumber > positiverealnumber ;; Purpose: to compute the area of a ring whose radius is ;; outer and whose hole has a radius of inner ;; ;; Examples: ;; (areaofring 5 3) => 50.24 ;; (areaofring 5 0) => 78.5 ;; ;; Template Instantiation: (degenerate) # (define (areaofring outer inner) ...) # ;; Code: (define (areaofring outer inner) ( (areaofdisk outer) (areaofdisk inner))) ;; Test Examples: (checkexpect (areaofring 5 3) 50.24) (checkexpect (areaofring 5 0) 78.5) ... ;; Provide enough examples and tests to show you tested thoroughly
 Example 6. Function definition for computing product of listofnumber:
Code Block ;; productoflon : listofnumbers > number ;; to compute the product of numbers in a list ;; assuming product of empty list is 1 ;; Examples: ;; (productoflon empty) => 1 ;; (productoflon (cons 2 empty)) => 2 ;; (productoflon (cons 3 (cons 2 empty))) => 6 ;; Template instantiation # (define (productoflon alon) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... ... (productoflon (rest alon)) ... ])) # ;; Code (define (productoflon alon) (cond [(empty? alon) 1] [(cons? alon) (* (first alon) (productoflon (rest alon)))])) ;; Test Examples: (checkexpect (productoflon empty) 1) (checkexpect (productoflon (cons 2 empty)) 2) (checkexpect (productoflon (cons 3 (cons 2 empty))) 6) ;; Provide enough examples and tests to show you tested thoroughly
 Example 5. Function definition for computing area of a ring:
 Remember to follow the design recipe.
 It is important that things are presented in this order, so that is clear that you know the correct order for doing things.
 You are allowed to use the
equal?
test only for testing. You are not allowed to use it anywhere else in the code.  If your examples get too big, then simply
define
a name for that big argument somewhere before you use it. You can use this name both in your comments in the example section and in the test cases in the Tests section.  Be sure to test throughly. Corner cases and edge cases should be tested. For example, when dealing with numerical functions,
0
and1
are often good test cases.  When testing lists, make sure you test the following cases:
 empty list:
empty
 list with one element: ex:
(cons 3 empty)
 list with more than one element: ex:
(cons 1 (cons 3 (cons 3 (cons 7 empty))))
 empty list:
 Local functions cannot be tested individually, so specific tests are not required for them. However, you main function's tests need to be comprehensive enough to test the local functions.
Sample Solution to a Programming Problem
Anchor  


The following text is a good solution to the problem of sorting a list of numbers into ascending order; it pulls together all of the specific pieces of design documentation, code documentation, and testing mentioned above. It would be better if it included a few more appropriately chosen tests.
Code Block 

;; COMP 211 HW #Sample ;; Corky Cartwright <cork@rice.edu> ;; A listofnumbers is either: ;; empty, or ;; (cons n alon) where n is a number and alon is a listofnumbers ;; ;; Examples: ;; empty ;; (cons 10 (cons 1 (cons 5 empty))) = '(10 1 5) ;; (cons 1 (cons 2 (cons 3 empty))) = '(1 2 3) ;; (cons 3 (cons 2 (cons 1 empty))) = '(3 2 1) # Template: (enclosed in block comment brackets) (define (lonf ... alon ...) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... ... (lonf ... (rest alon) ...) ... ])) # ;; Main function: sort ;; Contract and purpose: ;; sort: listofnumbers > listofnumbers ;; Purpose: (sort alon) returns the a list with same elements (including duplicates) as alon but in ascending order. ;; Examples: ;; (sort empty) = empty ;; (sort '(0)) = '(0) ;; (sort '(1 2 3)) = '(1 2 3) ;; (sort '(3 2 1)) = '(1 2 3) ;; (sort '(10 1 10 20 5)) = (20 1 5 10 10) # Template Instantiation: (define (sort alon) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... ... (sort (rest alon)) ... ])) # ;; Code: (define (sort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (sort (rest alon)))])) ;; Tests (checkexpect (sort empty) empty) (checkexpect (sort '(0)) '(0)) (checkexpect (sort '(1 2 3)) '(1 2 3)) (checkexpect (sort '(3 2 1)) '(1 2 3)) (checkexpect (sort '(10 1 10 20 5)) '(20 1 5 10 10)) ;; Auxiliary function ;; Contract and purpose ;; insert: number listofnumbers > listofnumbers ;; Purpose: (insert n alon), where alon is in increasing order, returns a list containing n and the elts of alon in ascending order ;; Examples: ;; (insert 17 empty) = '(17) ;; (insert 17 '(17)) = '(17 17) ;; (insert 4 '(1 2 3)) = '(1 2 3 4) ;; (insert 0 '(1 2 3)) = '(0 1 2 3) ;; (insert 2 '(1 1 3 4)) = '(1 1 2 3 4) # Template instantiation (define (insert n alon) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... ... (insert n (rest alon)) ... ])) # ;; Code (define (insert n alon) (cond [(empty? alon) (cons n empty)] [(cons? alon) (if (<= n (first alon)) (cons n alon) (cons (first alon) (insert n (rest alon))))])) ;; Tests (checkexpect (insert 17 empty) '(17)) (checkexpect (insert 17 '(17)) '(17 17)) (checkexpect (insert 4 '(1 2 3)) '(1 2 3 4)) (checkexpect (insert 0 '(1 2 3)) '(0 1 2 3)) (checkexpect (insert 2 '(1 1 3 4)) '(1 1 2 3 4)) 
Note: the Examples and Tests for each function above can be collapsed into a single entry by cutting out each Tests block and pasting it over the corresponding Examples block. Forward references in checkexpect
invocations work because the execution of checkexpect
code is deferred to the end of the contents of the definitions pane. For example, the Auxiliary function
part can be rewritten as follows:
Code Block 

;; Auxiliary function ;; Contract and purpose ;; insert: number listofnumbers > listofnumbers ;; Purpose: (insert n alon), where alon is in increasing order, returns a list containing n and the elts of alon in ascending order ;; Examples and Tests: (checkexpect (insert 17 empty) '(17)) (checkexpect (insert 17 '(17)) '(17 17)) (checkexpect (insert 4 '(1 2 3)) '(1 2 3 4)) (checkexpect (insert 0 '(1 2 3)) '(0 1 2 3)) (checkexpect (insert 2 '(1 1 3 4)) '(1 1 2 3 4)) # Template instantiation (define (insert n alon) (cond [(empty? alon) ...] [(cons? alon) ... (first alon) ... ... (insert n (rest alon)) ... ])) # ;; Code (define (insert n alon) (cond [(empty? alon) (cons n empty)] [(cons? alon) (if (<= n (first alon)) (cons n alon) (cons (first alon) (insert n (rest alon))))])) 
4. Termination Argument: (For Chapter 23 onwards only)
If the template does not guarantee that a function terminates, you are required to explain why that function will terminate for all possible inputs.
 Example 7. Termination argument for
quicksort
:Code Block ;; quicksort listofnumber > listofnumber ;; Purpose: (quicksort lon) sorts lon into ascending order ;; ;; Examples: ;; (quicksort empty) => empty ;; (quicksort '(1)) => '(1) ;; (quicksort '(1 4 3 5)) => '(1 3 4 5) ;; (quicksort '(1 4 3 4 2 5)) => '(1 2 3 4 4 5) ;; ;; Termination: ;; On each call, quicksort partitions the list alon into three sublists using ;; smallerthan, largerthan, and equalto. The lists produced by smallerthan ;; and largerthan are sorted using recursive applications of quicksort. Since ;; the lists produced by smallerthan and largerthan are strictly shorter than ;; alon (the given list), quicksort terminates. (define (quicksort alon) (cond [(empty? alon) empty] [else (append (quicksort (smalleritems alon (first alon))) (equalto alon (first alon)) (quicksort (largeritems alon (first alon))))])) "Testing quicksort:" ...