Page History

...

• 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 Racket .rkt file as your Scheme programming Racket programming exercises. Of course, you "comment out" each answer either by:

...

• Most expository problems will be hand-evaluation problems where you are asked to evaluate a particularly Scheme program particular Racket program invocation. You must format your hand evaluation exactly like our examples (except you will need to insert a comment escape character :.

  • 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

...

• All assigned programming problems should be done in the same .rkt file.

• At the top of your programming solution file, please put a header with the assignment number, your name, and your e-mail address like this:

  Code Block
  ;; COMP 211311 HW #01 ;; Christopher Warrington <chrisw@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.

...

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.

;; COMP 211311 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))) = '(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 (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 '(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 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 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 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) '(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))

...