CS 2360 Assignment 2: Due Midnight Jan 23

In this assignment, you will be asked to write some functions which do various manipulations on lists, as well as solve a couple of word problems (with hints!) using lists.

You should use only the following Lisp functions: DEFUN, COND, IF, NULL, FIRST, CAR, REST, CDR, SECOND, THIRD, QUOTE ('),LENGTH, ATOM, LISTP, CONSP, CONS,LIST, the arithmetic functions (+,-,*,/,MOD), the boolean functions, and the equality predicates EQUAL and =. This is not to say that you will need to use all these, but don't use any others without approval of the TAs. Naturally, you may use any function you have written that only uses these functions (the transitive law applies here!).

You should remember that beginning programming is a prerequisite for this course, so things like reasonable comments, meaningful function and parameter names, readable indentation, modularity, etc. are fair game with respect to your grade.

Some of these function will need helper functions to get them to work properly, this is fine.

1) my-member

(my-member 'c '(a b c d e)) => ( c d e)

(my-member 'a '(d e f ) => NIL

This one is in Kurt's lecture notes, a gimme.

2) in-first-not-second

> (in-first-not-second '(a b c) '(a b e)) (C) > (in-first-not-second '(a b c) '(a b c)) NIL > (in-first-not-second '(a b c) '(d e f)) (A B C)

3) transpose

Write a function transpose which takes an item and item-list; this function should find each occurrence of the item in the item-list and then exchange it with whatever follows it. You may assume that the item will not appear twice consecutively and that it will not appear last. Example runs: > (transpose 'a '( a b a d)) (B A D A) > (transpose 'a '( a c d a d a d b)) (C A D D A D A B) > Be aware that you need to make sure you think clearly about when to take the FIRST and REST especially in the cases when you need to do the transposition. You'll need to avoid getting an extra copy of the item following the the target item.

4) count-atoms

> (count-atoms '(a b ( c (d) e) f g (h i (((((j)))))))) 10 > (count-atoms '()) 0 > (count-atoms '(a b c)) 3 Think carefully about what type of recursion this is in crafting your solution.

5) select-even

> (select-even '(a b c)) (B) > > (select-even '(a)) NIL > (select-even '(a b c d e f)) (B D F)

6) create-dictionary

This function should take in two lists (a list of keys and a list of values) and create a dictionary data structure like the one I explained in class. You can assume the inputs are the same length. The order in the result is important, it should be in the same order as the keys. Examples: > (create-dictionary '(a b c) '(x y z)) ((A X) (B Y) (C Z)) > (create-dictionary '(boston atlanta) '(red-sox braves )) ((BOSTON RED-SOX) (ATLANTA BRAVES)

7) remover

Write a function which removes an element from a list based on an input index. Consider: > (remover 2 '( a b c d)) (A C D) > (remover 3 '( a b c d)) (A B D) You may assume the index will always be valid.

8) destroyer

Use your answer to number 7 to create a function which can blow away elements of a list based on their location. Examples: > (destroyer '( a b c d e f g h) '( 6 2)) (A C D E G H) > (destroyer '(a b c) '(3 1)) (B) > (destroyer '(a b c) '(3 2 1)) NIL You may assume that the second list will be in decreasing order. Think about why this restriction is in place.

9) my-member

Rewrite your solution to number 1 using tail-recursion if you did not do so the first time. If you did, rewrite your solution to not use tail-recursion. Your comments should explain your changes that were required.

10) my-reverse

Write a tail recursive version of reverse called my-reverse. This function should reverse all the elements of a list, and the reverse of nil is nil. Again, your comments should explain why you think your version is tail-recursive and not just recursive.

Some Word Problems

Mobiles

We are going to do a word problem about mobiles (the things you hang up from your ceiling).

You will be doing all your work on this problem with an abstract data type called mobile-data. This is a recursive data structure which is represented as a list of two lists. Here is an example:

((1 2) (3 4)) This a one level mobile (has one stick) with two weights, one of weight 2 and one of weight 4. The left side of the mobile is given first. The object of weight 2 (on the left) is placed 1 unit from the center of the mobile, the object of weight 4 is placed 3 units from the center on the right. Here is a more complex example:

((1 2) (3 ((4 5)(6 7)))) This is a two level mobile, with a submobile on the right. The right hand side's submobile's string is 3 units from the center. However, on that submobile, 4 units left of center of that submobile is a weight of 5 units. 6 units from the right of the center of the submobile is a weight of 7 units.

First in defining this abstract data object we need some functions to access its pieces. You should write four functions which access the parts of the mobile data type. They are:

mobile-distance-left: This should return the distance from the left of a mobile data structure that the left weight (or submobile) is located
mobile-distance-right: Same as above only on the right.
mobile-data-left: This should extract either the atom or the submobile data structure that makes up the weight on the left hand side of a mobile data structure.
mobile-data-right: Same as mobile-data-left only extracting the right hand atom or submobile structure.

All of these function should take one parameter, a mobile data structure. Further, be careful to analyze your calls to FIRST and REST carefully, as you need to make sure to get exactly what I mentioned above. This can be a little tricky in the last two cases; make sure you get either an atom or a well-formed mobile data structure.

When computing things about a mobile you will frequently need to compute the weight of the entire mobile. This is basically just the sum of the weights on the strings. Write a function mobile-weight which sums up the weights on the strings of the mobile. This is not a calculation of torque (that's later) this is just the sum of the weights. Consider:

> (mobile-weight '((5 ((3 4)(5 6)))(1 60))) 70 Be sure to use the functions you wrote above to make your life easier.

Now we are going to compute torque. The torque is:

Torque= ( right hand weight * right hand distance) - left hand weight
* left hand distance )

Write a function mobile-torque which the functions you've written so far to compute the torque on a mobile.It should take one parameter, again a mobile data structure.

Note: Torque is not recursive. If a mobile has a submobile, the torque does not need to know the submobile's torques, just the weight of the whole submobile. Think about the fact that the whole submobile's weight is suspended by a thin string from a single point on the higher mobile, thus the subtorques don't matter because all the weight of the submobile is exerted on one point, so it might as well just be a weight.

Finally, we are ready to see if a mobile is balanced or not. A mobile is balanced if:

The mobile's torque is zero.
Its left submobile is balanced.
Its right submobile is balanced.

Note that simple weights are always balanced for the purposes of this calculation. The trick is the submobiles. Write a function mobile-balanced which returns t or nil depending on if its input (a mobile data structure) is balanced.

Making Change

In this problem you should write a function called "change-maker" which takes in a number (in cents) and produces a list which has the names of the denominations of change required to make that amount of change. You may assume we will not give you an amount greater than 100. You should use the largest possible coins whenever you can, not including 50 cent pieces. E.g.: > (change-maker 33) (QUARTER NICKEL PENNY PENNY PENNY) > (change-maker 86) (QUARTER QUARTER QUARTER DIME PENNY) Your comments must explain if your solution is tail-recursive or not and why. If it isn't, then explain how you might go about changing your solution so that it would be tail-recursive.

Back To The CS2360 Home Page

Ian Smith (iansmith@cc.gatech.edu)