Homework Four

Due Friday, June 22, 2001. 8:00AM

Problem 1
10 points
You've seen some examples of nested lists, but it can be a pain to count parenthesis to see just how many lists you have. Let's remedy this situation by writing a function called number-of-lists. This function will take in one parameter: a list, and will return how many lists you passed in. For example:

> (number-of-lists '())
1

> (number-of-lists '(a (b)))
2

> (number-of-lists '(42 (13 24) ((((8))) (3 2))))
7

> (number-of-lists '(1 2 3 4 5))
1

Problem 2
15 points
Write a function to reverse the elements of a list no matter how deeply nested they are. You must use tree recursion to solve this problem. Call your function deep-reverse. Example usage:

> (deep-reverse '(1 2 3))
(3 2 1)

> (deep-reverse '(a (b c)))
((c b) a)

> (deep-reverse '(a (b (c (d (e ()))))))
(((((() e) d) c) b) a)

> (deep-reverse '())
()

Problem 3
35 points total
We're going to implement a function that will sort a list of numbers. The algorithm we're going to use is called bubble-sort. So what does it mean to bubble-sort a list?

Well, the basis of the bubble sort is making a so-called bubble-pass over the list. What this does is compare elements side-by side and if the first element is larger than the second element, then you swap them. Write this function and call it bubble-pass. For example:

> (bubble-pass '(3 1 2 5))
(1 2 3 5)

> (bubble-pass '(5 3 2 -1 -8))
(3 2 -1 -8 5)

> (bubble-pass '(3 4 2 5 8 0))
(3 2 4 5 0 8)

Let's take a closer look at that last example:

Step one: 
	(3 4 2 5 8 0)
         ^ ^
         | |
         +-+----compare these two elements.  3 is less than 4, so no swapping

Step two:
	(3 4 2 5 8 0)
           ^ ^
           | |
           +-+----compare these two elements.  4 is greater than 2, so swap

Step three: 
	(3 2 4 5 8 0) ; notice that the 2 and the 4 are now swapped
             ^ ^
 	     | |
             +-+----compare these two elements, they're in order, so no swap

Step four:
	(3 2 4 5 8 0)
               ^ ^
               | |
               +-+----compare these two, no swap

Step five:  
	(3 2 4 5 8 0)
                 ^ ^
                 | |
                 +-+----compare these two and swap, which gives us:

	(3 2 4 5 0 8)
notice that the largest element has "bubbled" to the end of the list.  Hence
the "bubble" in "bubble sort".

Now, notice that if bubble-pass puts the largest element into place on the first pass, then it will put the second element into place on the second pass. Don't believe it? Trace through it and see what happens (if you're really ambitious you could even try to come up with a formal proof of it, but that's by no means required).

So if each run of bubble-pass puts one element in its place, then running bubble-pass once for every element in the list will sort the list. Write a function called bubble-sort which does just that: takes in a list, runs bubble-pass once for each element in the list (so if the list is 5 elements long then run 5 bubble-pass's) and returns the sorted list. For example:

> (bubble-sort '(1 2 3))
(1 2 3)

> (bubble-sort '(9 8 7 6 5 4 3 2 1))
(1 2 3 4 5 6 7 8 9)

> (bubble-sort '(6 3 4 5 -32))
(-32 3 4 5 6)

Now, some of you may have noticed that this sort wastes time if the list is sorted before the last pass. It also wastes time by making comparisons between elements we already know are in place (after the first pass, the largest element is in place, so it's wasteful to keep comparing it on each successive pass. After the second pass the two largest elements are in place, so it's wasteful to compare them on each successful pass, etc...). Write an improved version of bubble-sort called smart-bubble-sort which stops once the list is sorted and doesn't compare elements which are already in place.

point breakdown for this problem:

10 points for bubble-pass
15 points for bubble-sort
10 points for smart-bubble-sort

Problem 4
10 points
What is the big-O for bubble-pass?
What is the big-O for bubble-sort?
What is the big-O for smart-bubble-sort?

For the next few problems, we're going to use the following association list representation for trees:

((node-address (node-data (left-child-address right-child-address)))
 (node-address (node-data (left-child-address right-child-address)))
                      . . .

 (node-address (node-data (left-child-address right-child-address))))

We'll use the number zero to represent a so called (in CS land) "null" address. This just means that the address zero points nowhere. So the tree:

           A
          / \
         /   \
        B     C
       / \   / \
      D   E F   G

Can be represented like this:

((100 (A (101 102)))  ; head address is 100
 (101 (B (103 104)))
 (102 (C (105 106)))
 (103 (D (0 0)))
 (104 (E (0 0)))
 (105 (F (0 0)))
 (106 (G (0 0))))

or like this:

((42 (D (0 0))) ; head address is 13
 (99 (C (65 46)))
 (13 (A (38 99)))
 (46 (G (0 0)))
 (38 (B (42 1024)))
 (1024 (E (0 0)))
 (9999 (XXX (9999 9999)))
 (65 (F (0 0))))

Notice that ordering doesn't matter and that you can have other nodes not in the tree floating around. That doesn't change a thing; you can still traverse and search the tree data structure. How do we deal with these nasty implementation details? Why abstraction, of course (but you knew that already, right?). Let's write some functions to extract the data we want (so we can forget about the representation).

Problem 5
5 points
Write a function called dereference which will take in two parameters: an address and the data structure. It should return the list that contains that address. For example:

> (dereference 103 '((100 (A (101 102))) 
		     (101 (B (103 104)))
		     (102 (C (105 106)))
		     (103 (D (0 0)))
		     (104 (E (0 0)))
		     (105 (F (0 0)))
		     (106 (G (0 0)))))
(103 (D (0 0)))

Problem 6
5 points
Now write a function named get-node which will extract out the "node data" from the data structure at a given address. For example:

> (get-node   103  '((100 (A (101 102))) 
        	     (101 (B (103 104)))
		     (102 (C (105 106)))
		     (103 (D (0 0)))
		     (104 (E (0 0)))
		     (105 (F (0 0)))
		     (106 (G (0 0)))))
(D (0 0))

Problem 7
5 points
Now that we can get the node, let's get the data out of it. Write a function called get-data which will give you the data from a certain address. For example:

> (get-data 105  '((100 (A (101 102))) 
        	   (101 (B (103 104)))
		   (102 (C (105 106)))
		   (103 (D (0 0)))
		   (104 (E (0 0)))
		   (105 (F (0 0)))
 		   (106 (G (0 0)))))
F

Problem 8
5 points
Now let's say we want to know which node is the left child of the node at some given address. Write a function called get-left-addr which will (you guessed it) return the address of a node's left child. For example:

> (get-left-addr 102  '((100 (A (101 102))) 
        	        (101 (B (103 104)))
		        (102 (C (105 106)))
		        (103 (D (0 0)))
		        (104 (E (0 0)))
		        (105 (F (0 0)))
 		        (106 (G (0 0)))))
105

Problem 9
5 points
Write a function called get-right-addr. It's the companion of the function you wrote for problem eight. For example:

> (get-right-addr 102 '((100 (A (101 102))) 
        	        (101 (B (103 104)))
		        (102 (C (105 106)))
		        (103 (D (0 0)))
		        (104 (E (0 0)))
		        (105 (F (0 0)))
 		        (106 (G (0 0)))))
106

Problem 10
15 points
Write a function called node-count which will, given a head address and a binary tree data structure, return the number of nodes in the tree.

> (node-count 99 '((99 (the (0 13)))
		 (13 (quick (0 42)))
		 (42 (brown (61 38)))
		 (61 (fox (26 0)))
		 (38 (jumped (27 28)))
		 (26 (over (0 0)))
		 (27 (the (32 0)))
		 (28 (lazy (0 0)))
		 (32 (dogs (0 0)))))
9

Problem 11
20 points
Write a function called collect-leaves which will, given a head address and a binary tree data structure, return a list of the leaf nodes in the tree. For this class we'll define a leaf node to be any node which has no children.

> (collect-leaves 101 '((101 (foo (0 0)))))
(foo)

> (collect-leaves 1024 '((400 (doo (0 0)))
			 (800 (ghost (0 400)))
			 (768 (shaggy (1600 1200)))	
			 (2048 (mummy (0 0)))
			 (1024 (mystery-machine (768 800)))
			 (1600 (scooby (0 0)))
			 (1200 (doobie (0 0)))))
(scoobie doobie doo)
NOTE: you may not just run through the association-list representation looking
for nodes with (0 0) as their child addresses. Notice the "mummy" node floating
about the tree data structure but not actually part of the tree.

Problem 12
20 points
Let's say that you want to send a message to a friend, but you can only send ones and zeros. One way you can send the message is to give the recipient a "decoder tree¨. A decoder tree works like this:

Begin at the head of the tree
When you get a zero, move to the left child
When you get a one, move to the right child
Repeat steps 2 and 3 until you reach a leaf node
Return the data in the leaf node

Your job is to write a function named letter-decoder which will take in a list of ones and zeros, a decoder tree data structure, and the head node address for the decoder tree. Your function should return the value stored at the leaf node that the list of ones and zeros leads to. Note that your function should return as soon as it reaches a leaf node, not when the list of ones and zeros runs out.

> (letter-decoder 100 '((100 (X (102 101)))
			(102 (a (0 0)))
			(101 (Y (104 103)))
			(104 (b (0 0)))
			(103 (Z (106 105)))
			(106 (c (0 0)))
			(105 (d (0 0))))
						'(1 0 ))
b
> (letter-decoder 100 '((100 (X (102 101)))
			(102 (a (0 0)))
			(101 (Y (104 103)))
			(104 (b (0 0)))
			(103 (Z (106 105)))
			(106 (c (0 0)))
			(105 (d (0 0))))
						'(0 1))
a ; notice that we hit a leaf node before the list ran out.  That's ok.
> (letter-decoder 100 '((100 (X (102 101)))
			(102 (a (0 0)))
			(101 (Y (104 103)))
			(104 (b (0 0)))
			(103 (Z (106 105)))
			(106 (c (0 0)))
			(105 (d (0 0))))
						'(1 1 1))
d

Problem 13
15 points Now write a function called number-of-internals which will take in a head address and a tree data structure and will return the number of internal nodes in the tree. For this class we'll define an internal node to be all nodes in the tree which are not leaf nodes (remember, a leaf node is a node with no children). For example:

> (number-of-internals 103 '((103 (x (0 0)))))
0

> (number-of-internals 100 '((100 (A (101 102)))
			     (101 (B (103 104)))
			     (102 (C (105 106)))
			     (103 (D (0 0)))
			     (104 (E (0 0)))
			     (105 (F (0 0)))
			     (106 (G (0 0)))))
3