Exercises

All exercises must be submitted for review to the Code Critic

Do and submit exercises one at a time. They do not have to be done in order, except when an exercise specifically says it's a sequel to another. You don't have to wait for one exercise to be completely approved before beginning another, but do not submit more than two new exercises at a time.

For a few tips on using PLT Scheme, see here.


SICP 1.3: sum-squares-larger

PLT Language Level: Beginner

Do exercise 1.3. Name the function as above, for testing purposes.

First, put the following test code in the Definitions window in DrScheme, and click the Run button. Make sure the only error is that sum-squares-larger is not defined.

(check-expect (sum-squares-larger 1 2 3) 13)
(check-expect (sum-squares-larger 3 2 1) 13)
(check-expect (sum-squares-larger 4 2 4) 32)
(check-expect (sum-squares-larger -1 -2 -3) 5)
(check-expect (sum-squares-larger 3 3 5) 34)
(check-expect (sum-squares-larger 3 3 2) 18)

Then add your definition code that passes the tests. Feel free to define subfunctions, if appropriate, and add more tests.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote. Don't send book code or the test code above.


HTDP 1.4: concat, split, delete-nth

PLT Language Level: Beginner

Define the functions named to pass these tests.

(check-expect (concat "hello" "world") "hello_world")

(check-expect (split "helloworld" 5) "hello_world")
(check-expect (split "helloworld" 0) "_helloworld")
(check-expect (split "helloworld" 10) "helloworld_")

(check-expect (delete-nth "helloworld" 5) "helloorld")
(check-expect (delete-nth "helloworld" 0) "elloworld")
(check-expect (delete-nth "helloworld" 9) "helloworl")

These functions are based on exercises 2, 3, and 4, respectively, from HTDP, with these changes:

Feel free to define subfunctions, if appropriate, and add more tests.

Don't repeat code. If a function you've defined is useful in another function, use it.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including any new tests you added. Don't send book code or the test code above.


SICP 1.7.a: first-guess

PLT Language Level: Beginner

This is a prequel exercise for SICP 1.7. Newton's method will not converge to an answer if the initial guess is way off. So the book's use of 1.0 as an initial guess falls apart when testing with very large numbers, which SICP 1.7 requires.

Implement, with tests, the decimal algorithm given here for generating initial guesses, based on the size of the number. Break first-guess down into two subfunctions:

The first function needs to loop, the second does not.

Here are few tests but you should add more:

(check-expect (first-guess 123456) 600)
(check-expect (first-guess 12345) 200)
(check-expect (first-guess 0.003) 0.06)
(check-expect (first-guess 0.0003) 0.02)

SICP 1.7: square-root

PLT Language Level: Beginner

Do exercise 1.7. Name the function as above, for testing purposes.

First, put the following test code in the Definitions window in DrScheme, and click the Run button. Make sure the only error is that square-root is not defined. Note that the tolerance for error is based on the size of the answer. This is to be consistent with the textbook's definition of good-enough?.

(define *tolerance* 0.001)

(check-within (square-root 9) 3 (* 3 *tolerance*))
(check-within (square-root 16) 4 (* 4 *tolerance*))
(check-within (square-root 7) 2.645 (* 2.645 *tolerance*))
(check-within (square-root 1) 1 (* 1 *tolerance*))

Then add the code for square roots given in Section 1.1.7. Use copy and paste to minimize errors. Type control-I (Windows, Unix) or command-I (MacOS) to fix the indentation. Rename sqrt to square-root.

Finally, add your code for Exercise SICP-1.7.a. Change the book code that uses 1.0 as the initial guess to call first-guess on the input number instead.

Before changing any other code, run the tests. Make sure there are no undefined functions and that all the tests pass.

Now add at least two test cases, to illustrate the two situations that the book exercise describes. Run the tests and make sure that both fail with the book code.

Then change the code to satisfy the exercise requirements. This means changing good-enough? to test how close the old and new guess are, and changing sqrt-iter to call the good-enough? with two guesses rather than a guess and a square.

Feel free to define subfunctions, if appropriate, and add more tests.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including the new tests you added. Don't send book code or the test code above.


SICP 1.8: cube-root

PLT Language Level: Beginner

Do exercise 1.8. Name the function as above, for testing purposes.

First, put the following test code in the Definitions window in DrScheme, and click the Run button. Make sure the only error is that cube-root is not defined.

(define *tolerance* 0.001)

(check-within (cube-root 27) 3 (* 3 *tolerance*))
(check-within (cube-root 64) 4 (* 4 *tolerance*))
(check-within (cube-root 100) 4.642 (* 4.642 *tolerance*))
(check-within (cube-root 1) 1 (* 1 *tolerance*))
(check-within (cube-root 0.001) 0.1 (* 0.1 *tolerance*))
(check-within (cube-root 0.000001) 0.01 (* 0.01 *tolerance*))

Then add your code for square roots and change it to do cube roots, using the formula given for SICP Exercise 1.8. You can try using the same first-guess function, and see if that works, or create a first-guess function that's more appropriate for cube root.

Feel free to define subfunctions, if appropriate, and add more tests.

When all tests pass, submit your code to the Code Critic. Send only the code you changed to do cube roots, including any new tests you added. Don't send book code, the test code above, or your unchanged code from square roots.


Roman numerals: decimal->roman, roman->decimal

PLT Language Level: Beginner

Define functions to handle Roman numerals, using only basic Scheme arithmetic, string and character functions -- no lists or other data structures. Make this code clear and simple and easy to follow. There are many solutions to this problem on the web, including in Scheme, but most use lists and other data structures, and many are not very easy to follow.

Define (decimal->roman n) to a positive integer, up to 5000, and returns a string with the Roman numeral equivalent.

Define (roman->decimal str) to take a string containing a Roman number, and returns the decimal integer equivalent.

One tricky bit with reading Roman numbers is that "X..." might mean "add 10," as in "XXI," or "subtract 10," as in "XLI." It's easier to handle this if you convert Roman numerals from right to left, keeping track of the sum so far.

Make sure your code passes these tests, but don't try to do them all at once. Start with just "I" through "III" and make sure they work. Then add "IV" through "VIII" and get them working. Then work on "IX" through, say, "XXI." By then you should have the pattern down for the other Roman symbols.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including any new tests you added. Don't send the test code I created.


Bouncing UFOs

PLT Language Level: Beginner

New things to learn: PLT structures, PLT random numbers

Don't confuse the general notion of structures with the specific example of posn (position) described in HTDP. We are not using posn for this exercise.

Movie: rockets.swf

You have two jobs in this exercise:

To get started, download rocket-cycle.ss, the code for the bouncing UFO's generated in class. Make sure it runs and the three images correctly bounce up and down vertically between the top and bottom of the window.

The rocket-cycle.ss code has been updated for PLT Scheme 2.4.2. If you load it in PLT Scheme 2.4.3, you will get an error about loading the image library twice, and/or redefining empty-scene. Now would be a good time to install PLT Scheme 2.4.2.

Animation Change

Change this code so that each UFO starts with a sideway velocity of either +1, -1, or 0. +1 means that each time step it moves 1 pixel to the right, -1 means it moves 1 pixel to the left, and 0 means it doesn't move left or right. Each time you click Run, a new sideway velocity for each UFO should be selected randomly.

To make the objects bounce like billiard balls off all four sides, you just have to cycle the horizontal position (x) back and forth within the width of the window, just as the code currently cycles the vertical position (y).

Code Cleanup

The basic ideas for cycling numbers are in get-ufo-height and the functions it calls, but they are not cleanly encoded. A novice programmer would copy and paste and change the vertical code to do horizontal locations. That leads to an unmaintainable mess.

Instead you will do a litte data abstraction and a little procedural abstraction to generate code that's simpler but does more. The first simplification is to make the following definition of create-UFO-scene work:

(define (create-UFO-scene n)
  (place-ufo UFO-3 n
             (place-ufo UFO-2 n
                        (place-ufo UFO-1 n (empty-scene WIN-WIDTH WIN-HEIGHT)))))

You need to define (place-ufo ufo n scene) to take a UFO object (see below), an animation time, and a scene, and return a scene with the UFO placed at the appropriate location for time n.

For this to be possible, a UFO object must contain not only the image, but also the UFO's initial horizontal starting point and its horizontal velocity (+1, 0 or -1). That means you need to:

(random n) generates a number between 0 and n - 1. You want -1, 0, or 1. You can make this happen with a tiny bit of arithmetic -- no conditionals needed.

For clarity, place-ufo should call functions to calculate the location of the UFO:

Both of these functions need to calculate values that cycle between some limit. DRY -- don't repeat yourself. Define a general function, independent of graphics, for cycling values:

The cyclic modulo of n and m is

You will no doubt need to define other helper functions. Be sure to give them good names.

Test your code with different window sizes. Make sure that bouncing occurs correctly, and that each run has objects moving differently.

Submit your code to the Code Critic.


interleave

PLT Language Level: Beginner

New things to learn: list

Using the basic list recursion pattern, define (interleave list1 list2) to take two lists and return a new list that interleaves the elements from the two lists. Look at the test cases below to see how things are ordered and what happens if one list is shorter than the other.

(check-expect (interleave empty empty) empty)
(check-expect (interleave (list 1 2 3) empty) empty)
(check-expect (interleave empty (list 4 5 6)) empty)
(check-expect (interleave (list 1 2 3) (list 4 5 6)) (list 1 4 2 5 3 6))
(check-expect (interleave (list 4 5 6) (list 1 2 3)) (list 4 1 5 2 6 3))
(check-expect (interleave (list 1 2 3) (list 4 5)) (list 1 4 2 5))
(check-expect (interleave (list 1 2) (list 4 5 6)) (list 1 4 2 5))

Polynomials 1: mult-scalar and eval-poly

PLT Language Level: Beginner

Do the next three exercises in order. If you get stuck for more than a few hours on some part, email the TA or me for help. Put EECS 111 in the Subject line, and include what you've written so far.

Consider a simple polynomial in one variable, e.g.,

x3 - 4x + 7

One way to represent this is to

A few more examples:

2x4 - 3 (list 2 0 0 0 3)
-5x3 + x2 (list -5 1 0 0)
5x (list 5 0)
5 (list 5)

Mathematically, (list 0 3 0 -1) is the same polynomial as (list 3 0 1), and empty is the same polynomial as (list 0). However we will define the canonical list form of a polynomial as:

Note: SICP describes a more powerful way to represent polynomials but it's also more complex. Don't try to use that code here. After you do these exercises, you might want to compare your code with theirs.

One operation with polynomials is to multiply them by a simple number, called a scalar. This just means multiplying every coefficient by the number, e.g.,

(x3 - 4x + 7) * -3 = -3x3 + 12x -21

Define (mult-scalar poly number) to multiply a polynomial in list form by a scalar. Here are some test cases, but feel free to add more.

(check-expect (mult-scalar empty 5) (list 0))
(check-expect (mult-scalar (list 3) 7) (list 21))
(check-expect (mult-scalar (list 2 0 -3) 7) (list 14 0 -21))
(check-expect (mult-scalar (list 2 0 -3) 0) (list 0))
(check-expect (mult-scalar (list 1 0 -4 7) -3) (list -3 0 12 -21))

Use basic list recursion pattern. This will sometimes produce results that are not canonical, like empty instead of (list 0). Don't make the code more complicated. Instead, define a recursive helper function to do the multiplication loop, and another function, (fix-poly poly), to take a polynomial and return its canonical form. Then call fix-poly on the result returned by the helper function. This approach will be useful in several of these exercises.

Another operation with polynomials is to evaluate them for a given value of the variable, e.g., if x is 4,

x3 - 4x + 7 => (4)3 - 4(4) + 7 => 64 - 16 + 7 => 63

Define (eval-poly poly number) to evaluate a polynomial for a value. Here are some test cases for each, but feel free to add more.

(check-expect (eval-poly empty 5) 0)
(check-expect (eval-poly (list 5) 0) 5)
(check-expect (eval-poly (list 1 0 0 0) -1) -1)
(check-expect (eval-poly (list 1 0 -4 7) 0) 7)
(check-expect (eval-poly (list 1 0 -4 7) 4) 55)
(check-expect (eval-poly (list 1 0 -4 7) -1) 10)

Hint: it's simplest to do eval-poly from right to left, because you know the rightmost element is the coefficient for x0, the next is for x1, and so on. So define a recursive helper and pass it the polynomial reversed. Use reverse to do this. You should only need to call reverse once.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including any new tests you added. Don't send the test code I created.


Polynomials 2: add-poly and sub-poly

PLT Language Level: Beginner

Do not submit code for this exercise until you've received and understood critiques on the previous exercise. Avoid repeating mistakes.

Define (add-poly poly1 poly2) to add two polynomials, e.g.,

(x3 - 4x + 7) + (2x2 + 5x) = x3 + 2x2 + x + 7

Here are some test cases, but feel free to add more.

(check-expect (add-poly empty empty) (list 0))
(check-expect (add-poly empty (list 7)) (list 7))
(check-expect (add-poly (list 7) empty) (list 7))
(check-expect (add-poly (list -3)(list 7)) (list 4))
(check-expect (add-poly (list 1 0 -4 7)(list 2 5 0)) (list 1 2 1 7))

Hint: once again, it's simplest to do addition from right to left. This makes it fairly easy to handle lists of different lengths. Use reverse to do this. You should only need to reverse at the start, and again at the end, but not on every iteration. Avoid calling reverse repeatedly in a loop, because it's an expensive function.

Define (sub-poly poly1 poly2) to subtract two polynomials, e.g.,

(x3 - 4x + 7) - (2x2 + 5x) = x3 - 2x2 - 9x + 7

Here are some test cases, but feel free to add more.

(check-expect (sub-poly empty empty) (list 0))
(check-expect (sub-poly empty (list 7)) (list -7))
(check-expect (sub-poly (list 7) empty) (list 7))
(check-expect (sub-poly (list -3)(list 7)) (list -10))
(check-expect (sub-poly (list 1 0 -4 7)(list 2 5 0)) (list 1 -2 -9 7))
(check-expect (sub-poly (list 1 2 3 4) (list 1 2 3 4)) (list 0))
(check-expect (sub-poly (list 1 2 3 4) (list 1 2 1 1)) (list 2 3))

DRY -- don't repeat yourself. First write code that passes all the tests. But then look for repeated code and repeated calculations. Refactor your code to remove these repetitions before submitting for review. Use functions you wrote for the previous exercise, such as fix-poly.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including any new tests you added. Don't send the test code I created.


Polynomials 3: mult-poly

PLT Language Level: Beginner

Do not submit code for this exercise until you've received and understood critiques on the previous exercise.

Using the same representation as in the previous exercise, define (mult-poly poly1 poly2) to multiply two polynomials., e.g.,

(x - 1) * (x - 1) = x2 - 2x1 + 1

As before, answers should be returned in canonical form.

Here are some test cases, but feel free to add more.

(check-expect (mult-poly empty empty) (list 0))
(check-expect (mult-poly empty (list 7)) (list 0))
(check-expect (mult-poly (list 7) empty) (list 0))
(check-expect (mult-poly (list -3)(list 7)) (list -21))
(check-expect (mult-poly (list 1 1)(list 1 1)) (list 1 2 1))
(check-expect (mult-poly (list 1 1)(list 1 -1)) (list 1 0 -1))
(check-expect (mult-poly (list 1 0 -4 7)(list 2 5 0)) (list 2 5 -8 -6 35 0))

DRY -- don't repeat yourself.

Hint: Multiplication for polynomials, as for numbers, is defined mathematically in terms of addition. That suggests some functions from the previous exercise will be helpful.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including any new tests you added. Don't send the test code I created.


find-pairs improved

PLT Language Level: Intermediate

Download find-pairs.ss. This defines the higher order function (find-pairs pred? list) that returns every unique pair of elements x and y in list for which (pred? x y) returns true and x comes before y in list. This generic higher order function is particularly useful in a game for things like "find all objects that are overlapping."

Run the code and make sure all tests pass.

This definition, while simple, is a bit inefficient. Consider the call

(find-pairs > (list 5 4 3 2 1))

This returns a list of 10 pairs, starting with (list (list 5 4) (list 5 3) (list 5 2) ...), but it does 20 conses to make that top-level list. Why? Because the recursion effectively does this:

(append (list (list 5 4) (list 5 3) (list 5 2) (list 5 1))
  (append (list (list 4 3) (list 4 2) (list 4 1))
    (append (list (list 3 2) (list 3 1))
      (append (list (list 2 1)) empty))))

Each (append list1 list2) makes a copy of list1, so this definition does twice as many top-level conses as necesary.

Make a fairly modest change to find-pairs and find-pairs-helper so that only N conses are used to build a top-level list of N pairs. Do not write a completely new version. The new version will probably not fit the simple basic list recursion pattern any more.

Make sure all the tests still pass.

When all tests pass, submit your code to the Code Critic. Send only the code you wrote, including any new tests you added. Don't send the test code I created.


tree->leaves and tree->paths

PLT Language Level: Intermediate with Lambda

This exercise focuses on symbols, using lists to represent trees, and recursion.

Taxonomies provide a simple but powerful example of using symbols and lists to represent knowledge. Taxonomies are used in almost every field of study to organize concepts into hierarchies. There are folk taxonomies and scientific taxonomies. An example of the latter is the primate taxonomy in the image on the left.

DiagramList equivalent
primate taxonomy
(mammalia
  (primates
    (anthropoidea 
       (catarrhini
         (hominoidea
           ...)
         cercopithecoidea)
       platyrrhini)
    prosimii))

In computer science, a taxonomy is one example of a very general and useful data structure called a tree. Each name in a taxonomy is called a node. Each node has zero or more children. Each child is, recursively, a tree. If a node has children, it is called a parent. If it does not, it is called a leaf. E.g., in the example, Primates is a parent and Prosimii is a leaf. The topmost parent in the tree is called the root.

There's an obvious way to represent a tree in a list. Use symbols for the names. If a node is a leaf, just use the name. If a node is a parent, make a list with the parent in the car of the list and its children in the cdr.

Define mapapp

It's fairly common when processing trees to need to append together values returned from recursion. Both of the functions below do this. Therefore, your first task is to define a higher order function (mapapp fn list) that works like map but appends the results returned. A few test cases:

(check-expect (mapapp identity empty) empty)
(check-expect (mapapp identity '((a b) (c) () (d e))) '(a b c d e))
(check-expect (mapapp (lambda (x) (if (odd? x) (list x) empty))
                      (list 1 2 3 4 5 6))
              (list 1 3 5))

Define tree->leaves

Define the function (tree->leaves tree) to return a list of the leaves of a tree. The leaves should appear left to right order. (This makes coding easier.) Here are some test cases:

(check-expect (tree->leaves empty) empty)
(check-expect (tree->leaves 'mammalia) '(mammalia))
(check-expect (tree->leaves '(mammalia primates)) '(primates))
(check-expect (tree->leaves '(mammalia (primates prosimii anthropoidea)))
              '(prosimii anthropoidea))
(check-expect (tree->leaves
               '(mammalia
                 (primates (anthropoidea catarrhini platyrrhini)
                           prosimii)))
              '(catarrhini platyrrhini prosimii))

Define tree->paths

Don't even think of trying this until you've gotten tree->leaves working.

A path in a tree is the list of nodes from a node to the root, e.g., Anthropoidea Primates Mammalia. A list of all paths in a tree is often more useful for code to answer questions like "is a Gorilla a Catarrhini?" You just find the list that starts with gorilla, then see if catarrhini is in it.

Define the function (tree->paths tree) to return a list of all the paths in a tree. The basic algorithm is to call a recursive helper with the tree and the path so far, e.g., if the helper is (tree->paths-iter tree path) then we should see the following trace of recursive calls for the fourth test case below:

(tree->paths-iter (mammalia (primates anthropoidea prosimii)) empty)
  (tree->paths-iter (primates anthropoidea prosimii) (mammalia))
    (tree->paths-iter anthropoidea (primates mammalia))
    -> ((anthropoidea primates mammalia))
    (tree->paths-iter prosimii) (primates mammalia))
    -> ((prosimii primates mammalia))
  -> ((primates mammalia)
      (anthropoidea primates mammalia)
      (prosimii primates mammalia))
-> ((mammalia)
    (primates mammalia)
    (anthropoidea primates mammalia)
    (prosimii primates mammalia))

Here are some test cases:

(check-expect (tree->paths empty) empty)
(check-expect (tree->paths 'mammalia) '((mammalia)))
(check-expect (tree->paths '(mammalia primates))
              '((mammalia)
                (primates mammalia)
                ))
(check-expect (tree->paths '(mammalia (primates anthropoidea prosimii)))
              '((mammalia)
                (primates mammalia)
                (anthropoidea primates mammalia)
                (prosimii primates mammalia)
                ))
(check-expect (tree->paths
               '(mammalia
                 (primates (anthropoidea catarrhini platyrrhini)
                           prosimii)))
              '((mammalia)
                (primates mammalia)
                (anthropoidea primates mammalia)
                (catarrhini anthropoidea primates mammalia)
                (platyrrhini anthropoidea primates mammalia)
                (prosimii primates mammalia)
                ))

Valid HTML 4.01 Strict