Lecture 1 overview
Static Methods:   Design Recipe in Java
Inexact computations:   Review of Dr  Racket
Loops and accumulators:   Review of Dr  Racket

Lecture 1: Design Recipe and DrRacket Review

Introduces the Design Recipe for designing functions in the context of designing static methods in Java.
Reviews the foldl and foldr loops in DrRacket and highlights the problems encountered in computing with inexact numbers.

     ExamplesAlgorithms.java      inexact.rkt   

Lecture 1 overview

There are no prerequisites for this lecture, but it assumes the reader has seen the Design Recipe in the context of HtDP2e and has a basic knowledge of programming in the teaching languages of DrRacket.

A reader who is starting without this background should be able to follow most of this lecture and fill in the missing pieces.

All programs shown here run as defined - in a regular Java environment, or within the DrRacket IDE - as appropriate.

Topics covered:

Static Methods: Design Recipe in Java

The first computers have been designed to perform computations of mathematical functions. These computations may represent physical behavior of objects (the location of a moving object at the given time, the size of the balloon as it is being inflated, etc.), financial calculations (e.g. the pay for a given number of hours worked at the known rate of pay, the cost of an order that consists of the given number of items at the known price, etc.), the statistical evaluation of data (e.g. computing the averages, means, the standard deviation, correlations, etc.) and other instances where the computation needs to be repeated a number of times, each time with the different given values.

Here is the simple problem: In a game, a car moves across the screen at the constant speed. (Later, we will add the chicken that wants to cross the road without getting hit.) What do we need to compute to model the car movement? We need to be able to determine the car’s location at any time.

The following steps will help us in designing the solution:


Let us consider another problem. We want to model the landing of a spaceship. When first seen at the top of the screen, the spaceship moves at some known (fixed) speed. It stops when it reaches the ground at the bottom of the screen.

We think of the problem, the information that is relevant, and what is it we need to model in our program. We come up with the following idea:

Determine the position of the rocket after one tick, given its current position (height) and its speed.

Rather than computing the position at some given time, we wory only about the change in the rocket’s position at each tick.

Our reasoning now follows the same steps as before:

Inexact computations: Review of DrRacket

The goal of this section is to recall some of the things you have learned in the first course, using DrRacket teaching languages. Read through this, run some of the examples, as we will refer to them at various times during the semester.

In our scientific measurement we came across a strange problem. We are given a list of points and the distances between them, and need to compute the total distance when traversing them in the given order:

To compute the distance traveled we can use one of the following two functions:

(define NUM-LIST (list #i+9e23  #i+8e23  #i-1e23  #i+6e23))


(define (sum-right alist)

  (foldr + 0 alist))


(define (sum-left alist)

  (foldl + 0 alist))


;; one way to add all numbers

(sum-right NUM-LIST)


;; another way to add all numbers

(sum-left NUM-LIST)

Run this and observe the results. Actually, both results are inaccurate! Try the following, and reason about the numbers yourself, to see what the correct result should be.

;; adding the large numbers first

(+ (+ #i+9e23  #i+8e23) #i+6e23)


;; then subtracting the small one => correct result

(+ (+ (+ #i+9e23  #i+8e23) #i+6e23) #i-1e23)

We have two problems here. The inaccuracies in compound computations with inexact numbers are inevitable and we will not solve this problem here - we just want to make sure you are aware of it when writing your own programs.

Finally, remember that the tests that anticipate an inexact value as the result need to specify not only the expected value, but also the range within which the result should fall:

(check-within (sum-right NUM-LIST) #i2.2e+24 #i0.001e+24)

(check-within (sum-left NUM-LIST) #i2.2e+24 #i0.001e+24)

Loops and accumulators: Review of DrRacket

The second problem can be illustrated as follows. Work out the steps the computer goes through when doing the following computations:

;; one way to add all numbers

(sum-right (list 4 5 6))


;; another way to add all numbers

(sum-left (list 4 5 6))

Notice the difference. The definition of foldr and foldl shows how the computation proceeds:

;; foldr: [X Y -> Y] Y [Listof X] -> Y

;; (foldr f base (list x1 ... xn)) = (f x1 ... (f xn base)...))

(define (foldr f base alox ...)


;; foldl: [X Y -> Y Y [Listof X] -> Y

;; (foldl f base (list x1 ... xn)) = (f xn ... (f x1 base))...)

(define (foldl f base alox) ...)

Define two functions sum-recipe and sum-accumulator that add the numbers in the given list - once from left to right, once from right to left. For the first method follow the design recipe. For the second one use an accumulator. Which one is which?

Now use the stepper to run the methods you designed on the following examples:

;; one way to add all numbers

(sum-recipe (list 4 5 6))


;; another way to add all numbers

(sum-accumulator (list 4 5 6) 0)

Sometimes you cannot solve the problem, unless you use some accumulator. The accumulator represents some information you need to remember from having seen the earlier steps of your program.

Suppose we ask you to compute the distance along some route, but give you just the locations of the points on the way. (Assume you travel between any two points in a straight line.)

We know that the distance between two posns is define as

;; compute the distance between the two given points

;; dist: Posn Posn -> Number

(define (dist p1 p2)

  (sqrt (+ (sqr (- (posn-x p1) (posn-x p2)))

           (sqr (- (posn-y p1) (posn-y p2))))))


;; examples

(check-expect (dist (make-posn 2 3) (make-posn 5 3)) 3)

(check-expect (dist (make-posn 1 1) (make-posn 4 5)) 5)

Define the function total-distance that consumes a list of Posns that represent a route to travel and produces the total distance for the travel along this route.

Hint: What information do you need to remember as you traverse over the list of points?

Make sure you use helper functions as needed.

Make sure you describe in the purpose statement the meaning of the accumulator(s) that you need.

Recap: There are two key points to remember here: