How to do your Scheme homework problems

• Recall that all homeworks are to be done in pairs. This directive includes both expository problems and programming problems.

1. Expository problems

• Some homework problems will be conventional "free response" questions that require a short written answer.
• All of the assigned free response problems should be answered in a single text (ASCII) file with extension .txt. You can create this text file using your editor of choice (e.g., NotePad on Windows machine, TextEdit on a Mac, or emacs on a Linux machine).
• At the top of your expository solution file, please put a header with the assignment number, your name and e-mail address, and your partner's name and e-mail address, like this:

      ;; COMP 211 HW #01
      ;; Christopher Warrington <chrisw@rice.edu>
      ;; Gregory Malecha <gmalecha@rice.edu>

1.1 Hand evaluation problems

• Most expository problems will be hand-evaluation 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

        Given
           (define (poly x y) 
               (+ (expt 2 x) y))
    
               (poly 3 5)
            => (+ (expt 2 3) 5))
            => (+ 8 5)
            => 13

• • Example 2: Hand evaluation

        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

2. Programming problems

• Most of your homework problems will be programming problems.
• Most (70%) 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
  • Following the design recipe carefully and documenting your program as you are taught in course (see below), and
  • Good programming style as taught in the course.

• 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 e-mail address, and your partner's name and e-mail address, like this:

      ;; 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.

Submitting your homework

For submission instructions, please see the SVN Turnin tutorial.

Requirements

You must include any data definitions introduced in your homework submissions. And the functions you write must follow the basic forms.

1. Data Definitions and Templates:

You must include any data definitions introduced in your homework submissions. You need to think (and document) your design for data definitions before you start writing functions that process data of this type. Data definitions should be documented as follows:

• Example 3. Data definition of shape:

      ;; A shape is either
      ;; * a triangle (make-triangle b h),
      ;;   where b and h are positive-reals
      ;; * a square (make-square s),
      ;;   where s is a positive-real.
      (define-struct triangle (base height))
      (define-struct square (side))
      ;;
      ;; Examples:
      ;; (make-triangle 1 2)
      ;; (make-triangle 2 5)
      ;; (make-square 4)
      ;; (make-square 2.5)
      ;;
      ;; Template: (enclosed in block comment brackets)
      #|
      ;; shape-function : shape -> ...
      (define (shape-function ... shape ...)
        (cond [(triangle? shape) ... (triangle-base shape)   ...
                                 ... (triangle-height shape) ...]
              [(square? shape)   ... (square-side shape)     ...]))
      |#

• Example 4. Data definition of list-of-numbers:

      ;; A list-of-numbers is either
      ;;    empty, or
      ;;    (cons n lon) 
      ;; where n is a number, and lon is a list-of-numbers
      ;;
      ;; Examples:
      ;; empty
      ;; (cons 1 empty)
      ;; (cons 1 (cons 4 empty))
      ;;
      ;; Template: (enclosed in block comment brackets)
      #|
      ;; lon-f : list-of-numbers -> ...
      (define (lon-f ... a-lon ...)
        (cond
          [(empty? a-lon) ...]
          [(cons? a-lon) ... (first a-lon) ...
                         ... (lon-f ... (rest a-lon) ...) ... ]))
      |#

• Once your have written your data definition, you can use it in the rest of the assignment.
• The template for a function that consumes a particular datatype is based only on the type definition, and should not depend in anyway on the particular functions that you define on that type. In other words, there is only one template per data type. This same template is used as the starting point for writing functions that process that data type.
• If the type is a structure, the template should have the field extraction operations. If the type is a variety, the template needs to have an appropriate cond statement(example 3). If the type is recursive, the template tells us how the recursion should be done(example 4).

2. 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:

            ;; area-of-ring : positive-real-number positive-real-number -> positive-real-number
            ;; Purpose: to compute the area of a ring whose radius is 
            ;; outer and whose hole has a radius of inner 
            ;;
            ;; Examples:
            ;; (area-of-ring 5 3) => 50.24
            ;; (area-of-ring 5 0) => 78.5
            ;;
            ;; Template Instantiation: (degenerate)
            #|
            (define (area-of-ring outer inner) ...)
            |#
            ;; Code:

            (define (area-of-ring outer inner) 
              (- (area-of-disk outer) 
                 (area-of-disk inner))) 

            ;; Test Examples:
            (check-expect (area-of-ring 5 3) 50.24)
            (check-expect (area-of-ring 5 0) 78.5)
            ... 
            ;; Provide enough examples and tests to show you tested thoroughly

• • Example 6. Function definition for computing product of list-of-number:

            ;; product-of-lon : list-of-numbers -> number
            ;; to compute the product of numbers in a list
            ;; assuming product of empty list is 1

            ;; Examples:
            ;; (product-of-lon empty) => 1
            ;; (product-of-lon (cons 2 empty)) => 2
            ;; (product-of-lon (cons 3 (cons 2 empty))) => 6

            ;; Template instantiation 
            #|
             (define (product-of-lon a-lon)
               (cond
                 [(empty? a-lon) ...]
                 [(cons? a-lon) ... (first a-lon) ...
                                ... (product-of-lon (rest a-lon)) ... ]))
            |#

            ;; Code
            (define (product-of-lon a-lon) 
              (cond
                 [(empty? a-lon) 1]
                 [(cons? a-lon) (* (first a-lon) 
                                   (product-of-lon (rest a-lon)))]))
 
            ;; Test Examples:
            (check-expect (product-of-lon empty) 1) 
            (check-expect (product-of-lon (cons 2 empty)) 2)
            (check-expect (product-of-lon (cons 3 (cons 2 empty))) 6)
            ;; Provide enough examples and tests to show you tested thoroughly

• 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 and 1 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))))
• 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.

3. Same Programming Problem Solution

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 mentioned above. It would be better if it included a few more appropriately chosen tests.

;; COMP 211 HW #Sample
;; Corky Cartwright <cork@rice.edu>

;; A list-of-numbers is either:
;;   empty, or
;;   (cons n alon) where n is a number and alon is a list-of-numbers
;;
;; Examples:
;;   empty
;;   (cons 10 (cons -1 (cons 5 empty)))
;;   (cons 1 (cons 2 (cons 3 empty)))
;;   (cons 3 (cons 2 (cons 1 empty)))

;; Template: (enclosed in block comment brackets)
   (define (lon-f ... a-lon ...)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                         ... (lon-f ... (rest a-lon) ...) ... ]))
|#

;; Main function: sort

;; Contract and purpose:
;; sort: list-of-numbers -> list-of-numbers
;; Purpose: (sort alon) returns the a list with same elements (including duplicates) as alon but in ascending order.

;; Examples:
;; (sort empty) = empty
;; (sort (cons 1 (cons 2 (cons 3 empty)))) = (cons 1 (cons 2 (cons 3 empty)))
;; (sort (cons 3 (cons 2 (cons 1 empty)))) = (cons 1 (cons 2 (cons 3 empty)))
;; (sort (cons 10 (cons -1 (cons 10 (cons 5 empty))))) = (cons -1 (cons 5 (cons 10 (cons 10 empty))))

;; Template Instantiation:
#|
   (define (sort a-lon)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (sort (rest a-lon)) ... ]))
|#
;; Code:

   (define (sort a-lon)
     (cond
       [(empty? a-lon) empty]
       [(cons? a-lon) (insert (first a-lon) (sort (rest a-lon)))]))
   
;; Tests
(check-expect (sort empty) empty)
(check-expect (sort (cons 1 (cons 2 (cons 3 empty)))) (cons 1 (cons 2 (cons 3 empty))))
(check-expect (sort (cons 3 (cons 2 (cons 1 empty)))) (cons 1 (cons 2 (cons 3 empty))))
(check-expect (sort (cons 10 (cons -1 (cons 10 (cons 5 empty))))) (cons -1 (cons 5 (cons 10 (cons 10 empty)))))

;; Auxiliary functions
;; Contract and purpose
;; insert: number list-of-numbers -> list-of-numbers
;; 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) = (cons 17 empty)
;;  (insert 4 (cons 1 (cons 2 (cons 3 empty)))) = (cons 1 (cons 2 (cons 3 (cons 4 empty))))
;;  (insert 0 (cons 1 (cons 2 (cons 3 empty)))) = (cons 0 (cons 1 (cons 2 (cons 3 empty))))
;;  (insert 1.5 (cons 1 (cons 1 (cons 2 (cons 3 empty))))) = (cons 1 (cons 1 (cons 1.5 (cons 2 (cons 3 empty)))))

;; Template instantiation
#|
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) ...]
       [(cons? a-lon) ... (first a-lon) ...
                      ... (insert n (rest a-lon)) ... ]))
|#

;; Code
   (define (insert n a-lon)
     (cond
       [(empty? a-lon) (cons n empty)]
       [(cons? a-lon) 
        (if (<= n (first a-lon)) (cons n a-lon)
            (cons (first a-lon) (insert n (rest a-lon))))]))
;; Tests
(check-expect (insert 17 empty) (cons 17 empty))
(check-expect (insert 4 (cons 1 (cons 2 (cons 3 empty)))) (cons 1 (cons 2 (cons 3 (cons 4 empty)))))
(check-expect (insert 0 (cons 1 (cons 2 (cons 3 empty)))) (cons 0 (cons 1 (cons 2 (cons 3 empty)))))
(check-expect (insert 1.5 (cons 1 (cons 1 (cons 2 (cons 3 empty))))) (cons 1 (cons 1 (cons 1.5 (cons 2 (cons 3 empty))))))
(define (down-to n) 
    (if (< n 0) empty (cons n (down-to (sub1 n)))))

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 quick-sort:

      ;; quick-sort list-of-number -> list-of-number
      ;; Purpose: (quick-sort lon) sorts lon into ascending order
      ;;
      ;; Examples:
      ;; (quick-sort empty) => empty
      ;; (quick-sort '(1)) => '(1)
      ;; (quick-sort '(1 4 3 5)) => '(1 3 4 5)
      ;; (quick-sort '(1 4 3 4 2 5)) => '(1 2 3 4 4 5)
      ;;
      ;; Termination:
      ;; On each call, quick-sort partitions the list alon into three sublists using
      ;; smaller-than, larger-than, and equal-to.  The lists produced by smaller-than
      ;; and larger-than are sorted using recursive applications of quick-sort. Since
      ;; the lists produced by smaller-than and larger-than are strictly shorter than
      ;; alon (the given list), quick-sort terminates.
      (define (quick-sort alon)
        (cond
          [(empty? alon) empty]
          [else (append (quick-sort (smaller-items alon (first alon))) 
                        (equal-to alon (first alon)) 
                        (quick-sort (larger-items alon (first alon))))]))

      "Testing quick-sort:"
      ...

Access Permissions

• Set ALLOWTOPICCHANGE = TeachersComp211Group