Date: Fri, 29 Mar 2024 03:14:30 -0500 (CDT) Message-ID: <191766637.1139.1711700070366@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1138_1810857287.1711700070364" ------=_Part_1138_1810857287.1711700070364 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
.ss
file as your Scheme programming exercises. Each lin=
e in the answer to an expository question should begin a "comment escape ch=
aracter", namely ';' as the first character on that line. Alternatively, yo=
u can enclose an entire expository problem in a Scheme box (created using t=
he command Comment Out with a Box
or in Scheme block comment b=
rackets #|
and |#
(sometime called bookends=
em>). Note that you can create your entire homework file using the DrScheme=
editor.= Given =09 (define (poly x y) =09 (+ (expt 2 x) y)) (poly 3 5) =3D> (+ (expt 2 3) 5)) =3D> (+ 8 5) =3D> 13
= Given =09 (define (fact n) =09 (if (zero? n) 1 (* n (fact (- n 1))))) (fact 4) =3D> (if (zero? 4) 1 (* 4 (fact (- 4 1)))) =3D> (if false 1 (* 4 (fact (- 4 1)))) =3D> (* 4 (fact (- 4 1))) =3D> (* 4 (fact 3)) =3D> (* 4 (if (zero? 3) 1 (* 3 (fact (- 3 1))))) =3D> (* 4 (if false 1 (* 3 (fact (- 3 1))))) =3D> (* 4 (* 3 (fact (- 3 1)))) =3D> (* 4 (* 3 (fact 2))) =3D> (* 4 (* 3 (if (zero? 2) 1 (* 2 (fact (- 2 1)))))) =3D> (* 4 (* 3 (if false 1 (* 2 (fact (- 2 1)))))) =3D> (* 4 (* 3 (* 2 (fact (- 2 1))))) =3D> (* 4 (* 3 (* 2 (fact 1)))) =3D> (* 4 (* 3 (* 2 (if (zero? 1) 1 (* 1 (fact (- 1 1))))))) =3D> (* 4 (* 3 (* 2 (if false 1 (* 1 (fact (- 1 1))))))) =3D> (* 4 (* 3 (* 2 (* 1 (fact (- 1 1)))))) =3D> (* 4 (* 3 (* 2 (* 1 (fact 0))))) =3D> (* 4 (* 3 (* 2 (* 1 (if (zero? 0) 1 (* 0 (fact (- 0 1))= )))))) =3D> (* 4 (* 3 (* 2 (* 1 (if true 1 (* 0 (fact (- 0 1)))))))= ) =3D> (* 4 (* 3 (* 2 (* 1 1)))) =3D> (* 4 (* 3 (* 2 1))) =3D> (* 4 (* 3 2)) =3D> (* 4 6) =3D> 24
.ss<=
/code> file.
;= ; COMP 211 HW #01 ;; Christopher Warrington <chrisw@rice.edu> ;; Gregory Malecha <gmalecha@rice.edu>
You must include a data definition and corresponding template for each f= orm of data processed used in your homework submissions unless instructed o= therwise. You only need to include a data definition and corresponding temp= late once for an assignment, not once for every problem that uses that data= defintion.
You need to devise (and document) your data design before you start writ= ing functions that process this data. Data definitions should be documented= as follows:
;= ; 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 for shape #| ;; shape-function : shape -> ... (define (shape-function ... shape ...) (cond [(triangle? shape) ... (triangle-base shape) ... ... (triangle-height shape) ...] [(square? shape) ... (square-side shape) ...])) |#
;= ; 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 for list-of-numbers #| ;; 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) ...) ... ])) |#
cond
statement (see example 3). If the type is recurs=
ive, the template includes the expected recursive calls on the recursive da=
ta components (see example 4).= ;; area-of-ring : positive-real-number positive-real-number -> posi= tive-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) =3D> 50.24 ;; (area-of-ring 5 0) =3D> 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 thoroug= hly
= ;; 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) =3D> 1 ;; (product-of-lon (cons 2 empty)) =3D> 2 ;; (product-of-lon (cons 3 (cons 2 empty))) =3D> 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 thoroug= hly
equal?
test define
a name fo=
r 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.0
and empty
(cons 3 empty)
=
(cons 1 (cons 3 (con=
s 3 (cons 7 empty))))
The following text is a good solution to the problem of sorting a list o= f numbers into ascending order; it pulls together all of the specific piece= s of design documentation, code documentation, and testing mentioned above.= It would be better if it included a few more appropriately chosen tests.= p>
;; 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))) =3D '(10 -1 5) ;; (cons 1 (cons 2 (cons 3 empty))) =3D '(1 2 3) ;; (cons 3 (cons 2 (cons 1 empty))) =3D '(3 2 1) #| 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 du= plicates) as alon but in ascending order. ;; Examples: ;; (sort empty) =3D empty ;; (sort '(0)) =3D '(0) ;; (sort '(1 2 3)) =3D '(1 2 3) ;; (sort '(3 2 1)) =3D '(1 2 3) ;; (sort '(10 -1 10 -20 5)) =3D (-20 -1 5 10 10) #| 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 '(0)) '(0)) (check-expect (sort '(1 2 3)) '(1 2 3)) (check-expect (sort '(3 2 1)) '(1 2 3)) (check-expect (sort '(10 -1 10 -20 5)) '(-20 -1 5 10 10)) ;; Auxiliary function ;; Contract and purpose ;; insert: number list-of-numbers -> list-of-numbers ;; Purpose: (insert n alon), where alon is in increasing order, returns a l= ist containing n and the elts of alon in ascending order ;; Examples: ;; (insert 17 empty) =3D '(17) ;; (insert 17 '(17)) =3D '(17 17) ;; (insert 4 '(1 2 3)) =3D '(1 2 3 4) ;; (insert 0 '(1 2 3)) =3D '(0 1 2 3) ;; (insert 2 '(1 1 3 4)) =3D '(1 1 2 3 4) #| 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 (<=3D n (first a-lon)) (cons n a-lon) (cons (first a-lon) (insert n (rest a-lon))))])) ;; Tests (check-expect (insert 17 empty) '(17)) (check-expect (insert 17 '(17)) '(17 17)) (check-expect (insert 4 '(1 2 3)) '(1 2 3 4)) (check-expect (insert 0 '(1 2 3)) '(0 1 2 3)) (check-expect (insert 2 '(1 1 3 4)) '(1 1 2 3 4))
Note: the Examples and Tests for each function above ca=
n be collapsed into a single entry by cutting out each Tests block and past=
ing it over the corresponding Examples block. Forward references in c=
heck-expect
invocations work because the execution of check-ex=
pect
code is deferred to the end of the contents of the definitions =
pane. For example, the Auxiliary function
part can be rewritte=
n as follows:
;; Auxi= liary function ;; Contract and purpose ;; insert: number list-of-numbers -> list-of-numbers ;; Purpose: (insert n alon), where alon is in increasing order, returns a l= ist containing n and the elts of alon in ascending order ;; Examples and Tests: (check-expect (insert 17 empty) '(17)) (check-expect (insert 17 '(17)) '(17 17)) (check-expect (insert 4 '(1 2 3)) '(1 2 3 4)) (check-expect (insert 0 '(1 2 3)) '(0 1 2 3)) (check-expect (insert 2 '(1 1 3 4)) '(1 1 2 3 4)) #| 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 (<=3D n (first a-lon)) (cons n a-lon) (cons (first a-lon) (insert n (rest a-lon))))]))
If the template does not guarantee that a function terminates, you are r= equired to explain why that function will terminate for all possible inputs= .
quick-sort
:=20
;= ; quick-sort list-of-number -> list-of-number ;; Purpose: (quick-sort lon) sorts lon into ascending order ;; ;; Examples: ;; (quick-sort empty) =3D> empty ;; (quick-sort '(1)) =3D> '(1) ;; (quick-sort '(1 4 3 5)) =3D> '(1 3 4 5) ;; (quick-sort '(1 4 3 4 2 5)) =3D> '(1 2 3 4 4 5) ;; ;; Termination: ;; On each call, quick-sort partitions the list alon into three subli= sts using ;; smaller-than, larger-than, and equal-to. The lists produced by sm= aller-than ;; and larger-than are sorted using recursive applications of quick-s= ort. Since ;; the lists produced by smaller-than and larger-than are strictly sh= orter 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:" ...