Teaching
211 F '05
 
Assignments
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Set 10
Set 11
Set 12
Set 13
Set 14

Problem Set 10

If you run any of the functions (as opposed to just testing them), comment out the code for running the functions before you submit your solution.

N.B.: Tests are not runs. A test is when you evaluate an expression and compare it to some expected result, while a run is when you evaluate an expression without anticipating any particular result for the expression.

Due date: 11/18 @ NOON

The purpose of this problem set is to practice the implementation of generative recursion.

HtDP Problems:

Solve problems 27.1.4 and 27.1.5 using the world.ss teachpack.
27.3.1, 27.3.6, 28.2.1, 28.2.2, 28.2.3, 28.2.4

Problem 1:

Image processing is a ubiquitous application of computing in all kinds of disciplines. One image-processing operation is to mirror a picture along its diagonal. The operation is also called a tranposition, because a picture is often represented as a so-called matrix (a mathematical object) and transposing a matrix is equivalent to mirroring an image. The goal of this exercise is to develop a transposition program that can be applied to images in DrScheme.


;; Matrix =  (cons (Listof X) (Listof (Listof X)))
;; constraint: all lists in the matrix have the same length

;; Matrix -> Number
(define (height m) (length m))

;; Matrix -> Number 
(define (width m) (length (first m)))

Design create-matrix. The function consumes a list lox and a number n such that (= (remainder (length lox) m) 0). It produces a matrix of width m. (We really do mean design.)

Design transpose, a function that flips a matrix along the diagonal from the top-left to the bottom right. Example:


(equal? (transpose 
         '((a b c)
	   (1 2 3)
           (* & ^)) )
        '( (a 1 *)
           (b 2 &)
           (c 3 ^)))

Design the function mirror, which consumes an image and produces a mirror image of the image. Hint: Look up image->color-list and color-list->image in HelpDesk and experiment with them on small images. --- Apply mirror to an image of yourself.

Problem 2:

Testing functions in an interactive program is often difficult. To accomplish some amount of testing and to stress the function, programmers build test harnesses that apply these functions to random but legitimate inputs just to see whether they still produce proper outcomes under "harsh" conditions.

In order to expose you to the idea without getting into complicated details, let's look at a relatively simple example:


;; World = String 
;; the chars typed in so far, 
;; up to the visible width of the world 
(define WIDTH 100)

;; Keystroke World -> World 
;; gather chars from the keyboard 
(define (click key w)
  (cond
    [(char? key) (cond
                   [(< (image-width (draw w)) WIDTH) 
                    (string-append w (make-string 1 key))]
                   [else (end-of-time)])]
    [else w]))

;; World -> Image
;; create text image from given world 
(define (draw w) (text w 22 'red))

;; --- run program run 
(big-bang WIDTH 30 .1 "")
(on-tick-event (lambda (w) (update (draw w) produce w)))
(on-key-event click)

Obviously, you can develop examples and tests for click. Do so. A different way to test the function, however, is to "throw" randomly chosen characters at it until some condition is satisfied. At that point, you can check additional conditions to determine whether the function works according to your expectations.

Design the function test. It consumes a world and produces a boolean. Its purpose is to generate randomly chosen Chars and supply them to click until the string it produces is wider than WIDTH. What does this validate? Hint: Look up char->integer and integer->char in HelpDesk. Use these functions (with random) to randomly choose alphabetical characters.

Modify test so that when it hits the base condition it also checks that the world minus the last character does fit into the canvas of the given width. What does this variant of test validate?


last updated on Sat Nov 26 15:34:41 EST 2005generated with PLT Scheme