Comp210: Principles of Computing and Programming
Fall 2004 -- Homework #4   

All problems will require all (applicable) steps from the design recipe, including a template. Before you tackle the homework, remind yourself of our General Advice, Advice on Homeworks (in particular: staple and provide questions), and the Grading Guidelines.

1. (15 pts total) Functions returning lists

   1. (5 pts) A function map-square which consumes a list of numbers, and returns a list of the squares of those numbers.
      (The name "map" is traditional, coming from the math sense: a function mapping a bunch of inputs to a bunch of outputs.)
      
      

   2. (10 pts) A function substitute-num which takes in a list-of-numbers, plus a "before" number and "after" number and returns a list like the input, except that wherever the input list contains the "before" number, the output list now contains the "after" number.

      ; (only) one example of calling susbtitute-num:
      
      (substitute-num 1901 2001 (cons 6 (cons 1901 (cons 7 (cons 2001 empty)))))
      
      (cons 6 (cons 2001 (cons 7 (cons 2001 empty))))

2. (10 pts) Telephone Directory continued...
   
   Extend Problem 2 from last week to make a variation of substitute which operates on directories. We'll call it update, and it takes in a directory, a name, and a number. It returns a new directory with all the original entries, plus an entry with the given name/number. If that name already occurred in some entry (with possibly a different number), then the new directory should contain the udpated information, but you should not introduce any duplicate entries. (If you were given a directory that already had duplicate entries for the key you are updating, mention whether your code leaves them be, or eliminates them. (Either is fine.))
   
   

3. (10pts) Hand-evaluation

   Hand-evaluate:

   ;; prod: list-of-nums --> num
   
   ;; Return the product of a list of numbers.
   
   ;;
   
   (define (prod nums)
   
     (cond [(empty? nums)  1]   ; 1 is the identity element for *.
   
           [(cons?  nums)  (* (first nums) (prod (rest nums)))]))
   
   
   
   (prod (cons 2 (cons 7 empty)))
   
   

   As usual, your hand-evaluation should include one line per stepper step, and you should indicate (perhaps via underlining or italicizing) on your printout which sub-expression is about to be evaluated.

4. (10 pts) Natural Numbers

   Write the function my-odd?, which takes a NatNum and tells whether or not it's an odd number. (Include the data definition, examples, template for NatNums, of course.)

   Your function should follow directly from the template. Your code will be based on the fact that a non-zero natural number is odd iff its predecessor isn't.

   For this problem, do not use the built-in functions even?, odd?, remainder, modulo, nor round, ceiling, ...

5. (20 pts total) NatNum in, List out
   1. (0pts) Setup for this problem: Be sure to be using the draw.ss teachpack as in hw02 (Unless you cleared your teachpacks, it's still in use.) Also include the following:

      ; A constant, used for width of various bands, in part (b).
      
      ;
      
      (define band-width 20)
      
      
      
      ;; --------- Begin data definitions.
      
      
      
      ;; A posn is (make-posn num num)
      
      ;; and is already defined inside draw.ss.
      
      
      
      
      
      ;; A color is: one of {'red, 'yellow, 'white, 'black, 'blue, 'green}.
      
      
      
      
      
      ;;; Note: If you want to use your own structs from hw02
      
      ;;;       instead of these, that's okay.
      
      
      
      (define-struct rectangle (location width height color))
      
      ;; A rectangle is:
      
      ;;   (make-rectangle  posn num num color)
      
      ;; where location refers to the northwest corner.
      
      
      
      (define-struct circle (location radius color))
      
      ;; A circle is:
      
      ;;   (make-circle posn num color)
      
      ;; where location refers to the center.
      
      
      
      ;; A Shape is either:
      
      ;;   - a rectangle, or
      
      ;;   - a circle.
      
      ;;
      
      ;; (Note: Since we have already just defined "circle", "rectangle" as data,
      
      ;;  there's no need to repeat that info.)
      
      ;; --------- End data definitions.
      
      

   2. (10 pts) Do one of the following, whichever looks more fun to you:
      • rectangles: Write a simple function that is given a number i, and creates a rectangle whose northwest corner is at canvas location (i*band-width, 0), with width band-width and height (* i i).
      • circles: Write a simple function that is given a number i, and creates a circle centered at (say) canvas location (150,150), with radius (* i band-width), and either the color red or blue, depending on whether i is odd or even.
      Note: you don't need to recur on your input, so this is a simple function.
   3. (10 pts) Write a function which takes in a NatNum n, and returns a list of shapes: shapes created by the preceding function, called with n, n-1, n-2, ... 1, 0.
   4. (0pts) You are not required to write draw-list-of-shapes, and draw the output of your previous function. (It's pretty simple to do, though. Recall that to draw A and draw B, you can combine operations with and (since they all return true.)) If your structs representing circles and rectangles differed from those presented above, that's fine -- use whichever you like, but make sure your data definitions are correct.
6. (20 pts) Write two functions that return the largest number in a list of numbers: one written using natural recursion (reverse accumulation) and another using the accumulator style (forward accumulation). Be sure to test all possible inputs (assuming the input is a list)! Make sure that your function has well-defined behavior in all situations.

(85 pts total)

Last Revised Sunday, 21-Nov-2004 14:11:51 CST

©2004 Stephen Wong and Dung Nguyen