EECS 111

Home General Information Schedule Homework Newsgroup Resources 

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.
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 sumsquareslarger is not defined.
(checkexpect (sumsquareslarger 1 2 3) 13) (checkexpect (sumsquareslarger 3 2 1) 13) (checkexpect (sumsquareslarger 4 2 4) 32) (checkexpect (sumsquareslarger 1 2 3) 5) (checkexpect (sumsquareslarger 3 3 5) 34) (checkexpect (sumsquareslarger 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.
PLT Language Level: Beginner
Define the functions named to pass these tests.
(checkexpect (concat "hello" "world") "hello_world") (checkexpect (split "helloworld" 5) "hello_world") (checkexpect (split "helloworld" 0) "_helloworld") (checkexpect (split "helloworld" 10) "helloworld_") (checkexpect (deletenth "helloworld" 5) "helloorld") (checkexpect (deletenth "helloworld" 0) "elloworld") (checkexpect (deletenth "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.
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 firstguess down into two subfunctions:
The first function needs to loop, the second does not.
Here are few tests but you should add more:
(checkexpect (firstguess 123456) 600) (checkexpect (firstguess 12345) 200) (checkexpect (firstguess 0.003) 0.06) (checkexpect (firstguess 0.0003) 0.02)
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 squareroot 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 goodenough?.
(define *tolerance* 0.001) (checkwithin (squareroot 9) 3 (* 3 *tolerance*)) (checkwithin (squareroot 16) 4 (* 4 *tolerance*)) (checkwithin (squareroot 7) 2.645 (* 2.645 *tolerance*)) (checkwithin (squareroot 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 controlI (Windows, Unix) or commandI (MacOS) to fix the indentation. Rename sqrt to squareroot.
Finally, add your code for Exercise SICP1.7.a. Change the book code that uses 1.0 as the initial guess to call firstguess 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 goodenough? to test how close the old and new guess are, and changing sqrtiter to call the goodenough? 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.
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 cuberoot is not defined.
(define *tolerance* 0.001) (checkwithin (cuberoot 27) 3 (* 3 *tolerance*)) (checkwithin (cuberoot 64) 4 (* 4 *tolerance*)) (checkwithin (cuberoot 100) 4.642 (* 4.642 *tolerance*)) (checkwithin (cuberoot 1) 1 (* 1 *tolerance*)) (checkwithin (cuberoot 0.001) 0.1 (* 0.1 *tolerance*)) (checkwithin (cuberoot 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 firstguess function, and see if that works, or create a firstguess 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.
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.
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.
You have two jobs in this exercise:
To get started, download rocketcycle.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 rocketcycle.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 emptyscene. Now would be a good time to install PLT Scheme 2.4.2.
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).
The basic ideas for cycling numbers are in getufoheight 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 createUFOscene work:
(define (createUFOscene n) (placeufo UFO3 n (placeufo UFO2 n (placeufo UFO1 n (emptyscene WINWIDTH WINHEIGHT)))))
You need to define (placeufo 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, placeufo 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.
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.
(checkexpect (interleave empty empty) empty) (checkexpect (interleave (list 1 2 3) empty) empty) (checkexpect (interleave empty (list 4 5 6)) empty) (checkexpect (interleave (list 1 2 3) (list 4 5 6)) (list 1 4 2 5 3 6)) (checkexpect (interleave (list 4 5 6) (list 1 2 3)) (list 4 1 5 2 6 3)) (checkexpect (interleave (list 1 2 3) (list 4 5)) (list 1 4 2 5)) (checkexpect (interleave (list 1 2) (list 4 5 6)) (list 1 4 2 5))
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.,
x^{3}  4x + 7
One way to represent this is to
x^{3} + 0x^{2}  4x + 7
(list 1 0 4 7).
A few more examples:
2x^{4}  3  (list 2 0 0 0 3) 
5x^{3} + x^{2}  (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.,
(x^{3}  4x + 7) * 3 = 3x^{3} + 12x 21
Define (multscalar poly number) to multiply a polynomial in list form by a scalar. Here are some test cases, but feel free to add more.
(checkexpect (multscalar empty 5) (list 0)) (checkexpect (multscalar (list 3) 7) (list 21)) (checkexpect (multscalar (list 2 0 3) 7) (list 14 0 21)) (checkexpect (multscalar (list 2 0 3) 0) (list 0)) (checkexpect (multscalar (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, (fixpoly poly), to take a polynomial and return its canonical form. Then call fixpoly 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,
x^{3}  4x + 7 => (4)^{3}  4(4) + 7 => 64  16 + 7 => 63
Define (evalpoly poly number) to evaluate a polynomial for a value. Here are some test cases for each, but feel free to add more.
(checkexpect (evalpoly empty 5) 0) (checkexpect (evalpoly (list 5) 0) 5) (checkexpect (evalpoly (list 1 0 0 0) 1) 1) (checkexpect (evalpoly (list 1 0 4 7) 0) 7) (checkexpect (evalpoly (list 1 0 4 7) 4) 55) (checkexpect (evalpoly (list 1 0 4 7) 1) 10)
Hint: it's simplest to do evalpoly from right to left, because you know the rightmost element is the coefficient for x^{0}, the next is for x^{1}, 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.
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 (addpoly poly1 poly2) to add two polynomials, e.g.,
(x^{3}  4x + 7) + (2x^{2} + 5x) = x^{3} + 2x^{2} + x + 7
Here are some test cases, but feel free to add more.
(checkexpect (addpoly empty empty) (list 0)) (checkexpect (addpoly empty (list 7)) (list 7)) (checkexpect (addpoly (list 7) empty) (list 7)) (checkexpect (addpoly (list 3)(list 7)) (list 4)) (checkexpect (addpoly (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 (subpoly poly1 poly2) to subtract two polynomials, e.g.,
(x^{3}  4x + 7)  (2x^{2} + 5x) = x^{3}  2x^{2}  9x + 7
Here are some test cases, but feel free to add more.
(checkexpect (subpoly empty empty) (list 0)) (checkexpect (subpoly empty (list 7)) (list 7)) (checkexpect (subpoly (list 7) empty) (list 7)) (checkexpect (subpoly (list 3)(list 7)) (list 10)) (checkexpect (subpoly (list 1 0 4 7)(list 2 5 0)) (list 1 2 9 7)) (checkexpect (subpoly (list 1 2 3 4) (list 1 2 3 4)) (list 0)) (checkexpect (subpoly (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 fixpoly.
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.
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 (multpoly poly1 poly2) to multiply two polynomials., e.g.,
(x  1) * (x  1) = x^{2}  2x^{1} + 1
As before, answers should be returned in canonical form.
Here are some test cases, but feel free to add more.
(checkexpect (multpoly empty empty) (list 0)) (checkexpect (multpoly empty (list 7)) (list 0)) (checkexpect (multpoly (list 7) empty) (list 0)) (checkexpect (multpoly (list 3)(list 7)) (list 21)) (checkexpect (multpoly (list 1 1)(list 1 1)) (list 1 2 1)) (checkexpect (multpoly (list 1 1)(list 1 1)) (list 1 0 1)) (checkexpect (multpoly (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.
PLT Language Level: Intermediate
Download findpairs.ss. This defines the higher order function (findpairs 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
(findpairs > (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 toplevel 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 toplevel conses as necesary.
Make a fairly modest change to findpairs and findpairshelper so that only N conses are used to build a toplevel 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.
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.
Diagram  List equivalent 

(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.
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:
(checkexpect (mapapp identity empty) empty) (checkexpect (mapapp identity '((a b) (c) () (d e))) '(a b c d e)) (checkexpect (mapapp (lambda (x) (if (odd? x) (list x) empty)) (list 1 2 3 4 5 6)) (list 1 3 5))
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:
(checkexpect (tree>leaves empty) empty) (checkexpect (tree>leaves 'mammalia) '(mammalia)) (checkexpect (tree>leaves '(mammalia primates)) '(primates)) (checkexpect (tree>leaves '(mammalia (primates prosimii anthropoidea))) '(prosimii anthropoidea)) (checkexpect (tree>leaves '(mammalia (primates (anthropoidea catarrhini platyrrhini) prosimii))) '(catarrhini platyrrhini prosimii))
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>pathsiter tree path) then we should see the following trace of recursive calls for the fourth test case below:
(tree>pathsiter (mammalia (primates anthropoidea prosimii)) empty) (tree>pathsiter (primates anthropoidea prosimii) (mammalia)) (tree>pathsiter anthropoidea (primates mammalia)) > ((anthropoidea primates mammalia)) (tree>pathsiter 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:
(checkexpect (tree>paths empty) empty) (checkexpect (tree>paths 'mammalia) '((mammalia))) (checkexpect (tree>paths '(mammalia primates)) '((mammalia) (primates mammalia) )) (checkexpect (tree>paths '(mammalia (primates anthropoidea prosimii))) '((mammalia) (primates mammalia) (anthropoidea primates mammalia) (prosimii primates mammalia) )) (checkexpect (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) ))