UNB/ CS/ David Bremner/ teaching/ cs2613/ labs/ CS2613 Lab 5

Background

Part 1: Tail Recursion

Time
30 minutes
Activity
Small groups / individuals
    #lang racket
    (module+ test
      (require rackunit))

    (define (odds-evens lst)
      (cond
        [(empty? lst) (list 0 0)]
        [(odd? (first lst)) (map + '(1 0) (odds-evens (rest lst)))]
        [(even? (first lst)) (map + '(0 1) (odds-evens (rest lst)))]))

    (module+ test
      (check-equal? (odds-evens (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4)))
    (define (odds-evens2 lst)
      (define (helper lst odds evens)
        (cond
          [(empty? lst) (list odds evens)]
          [(odd? (first lst)) (helper                             )]
          [(even? (first lst)) (helper                             )]))
      (helper lst 0 0))

    (module+ test
      (define random-list (build-list 100 (lambda (x) (random 1 100))))
      (check-equal? (odds-evens2 (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
      (check-equal? (odds-evens random-list) (odds-evens2 random-list)))

Part 2: for loops

Time
15 minutes
Activity
Group discussion/demo
    (define (odds-evens3 lst)
      (define-values (odds evens)
        (for/fold
            ([odds 0] [evens 0])
            ([n lst])
          (cond
            [(odd? n) (values (add1 odds)  evens)]
            [(even? n) (values odds (add1 evens))])))
      (list odds evens))

    (module+ test
      (check-equal? (odds-evens3 (list 3 2 1 1 2 3 4 5 5 6)) (list 6 4))
      (check-equal? (odds-evens random-list) (odds-evens3 random-list)))
    (define big-list (build-list 1000000 identity))
    (for* ([fun (list odds-evens odds-evens2 odds-evens3)]
           [rep '(1 2 3)])
      (display fun)
      (displayln rep)
      (time (fun big-list)))

Part 3: Racket review

Time
15 minutes
Activity
Group discussion

What's new in the first half of today's lab?

Part 4 Numerical Integration examples

Time
30 minutes
Activity
individuals (you may need your files for next lab)

In this section we'll play a bit with some crude numerical derivative and integral calculation. Don't worry about the calculus too much, this is mainly a chance to reinforce

We'll also think about about testing numerical functions.

    #lang racket
    (require racket/math)

    (module+ test
      (require rackunit)
      (define epsilon .001))

    (define dx 0.001)
    (define -2pi (* -2 pi))
    (define 2pi (* 2 pi))

    ;; compute the derivative of `f' at the given point `x'
    (define (deriv f x)
      (/ (- (f (+ x dx)) (f x)) dx))

    ;; Integrate a function from 0 to x (using tail recursion)
    (define (integrate f x)
      (define (loop y acc)
        (if (> y x)
            (* acc dx)
            (loop (+ y dx) (+ acc (f y)))))
      (loop 0 0))
    (module+ test
      (check-= (integrate cos (/ pi 4)) (sin (/ pi 4)) epsilon))
    (module+ test
      (define test-points (build-list 20 (lambda (x) (* 2 pi (random)))))
      (define (sin2 x) (integrate cos x))
      (define (cos2 x) (deriv sin x))
      (for ([x test-points])

                                          ))
    (define (integrate2 f x)
      (for/fold
          ([acc 0])
          ([y (in-range 0 x dx)])
        (+ acc (f y))))

    (module+ test
      (for ([x test-points])
        (check-= (integrate cos x) (integrate2 cos x) epsilon)))