Com S 227 --- Introduction to Computer Programming
				   
		  HOMEWORK 4: DATA DRIVEN RECURSION
		 (File $Date: 1993/10/15 14:35:53 $)

Due: problems 1-4 Oct. 1; 5-8 Oct. 4; 10-11 Oct. 6; 16-19, 23-26 Oct. 13.

All the directions from homework 2 apply to this homework.
In particular, remember to hand in labeled printouts for procedures,
and transcripts showing your testing.


SECTION 4.2, FLAT RECURSION

   This might be a good time to read chapter 5 of the ``Little LISPer''.

1. (6 points; basic)
   In French, people often use titles (such as Madame, Monsieur, Mademoiselle,
   or their abbreviations Mr, Mlle, and Mme) when speaking and writing.
   Gary wants to have a procedure that can put the title in after writing
   a sentence or paragraph.  Make a procedure, ``insert-title'' that
   takes a title, a name, and a sentence, and inserts the title to
   left of *each* top-level occurrence (determined by equal?)
   of the name in the sentence.  For example,

	(insert-title 'president 'clinton
			'(i see clinton now
			    clinton is coming in))
		==> (i see president clinton now
		       president clinton is coming in)
	(insert-title 'monsieur 'napolean '(bon jour napolean ca va))
			; mr     napolean  ; good day napolean how's it going?
		==> (bon jour monsieur napolean ca va)
	(insert-title 'monsieur 'boulanger
			; mr      baker
			'(boulanger estime que boulanger
				est un nom interessant))
			; baker thinks that baker is an interesting name
		==> (monsieur boulanger estime que monsieur boulanger
				est un nom interessant)
	(insert-title '(m a d a m e) '(b o u l a n g e r)
			; mrs	       baker
			'((b o u l a n g e r) (acute-e c r i t)
		          (b o u l a n g e r)
			  (s u r) (s a) (p o r t e))
			; baker writes ``baker'' over her door
		==> ((m a d a m e) (b o u l a n g e r) (acute-e c r i t)
			(m a d a m e) (b o u l a n g e r)
			(s u r) (s a) (p o r t e))
	(insert-title 'dictator-for-life 'calvin '(hobbes))
		==> (hobbes)

2. (0 points; suggested practice)
   Do exercise 4.2.

3. (6 points)
   Write a procedure ``pronounize-all'' that takes a pronoun, a name,
   and a sentence, and returns the same sentence with *each* occurrence
   of the name replaced by the pronoun.  For example,

	(pronounize-all 'beatrice 'she '())
		==> ()
	(pronounize-all 'tom 'he '(tom said hello tom walked on proudly))
		==> (he said hello he walked on proudly)
	(pronounize-all 'mary 'she '(mary mary mary will not listen to me))
		==> (she she she will not listen to me)
	(pronounize-all '(j e a n) '(i l) '((j e a n) (e s t) (j e a n)))
		==> ((i l) (e s t) (i l))

4. (0 points; suggested practice)
   Do exercise 4.4 (deepen-1).  You might also try generalizing this to deepen-n.


SECTIONS 4.3 AND 4.4, DEEP RECURSION AND TREE REP OF LISTS

   Recall that we call a list with nested sublists a tree.
   You might also want to read chapter 6 of the ``Little LISPer'',
   but remember that we are suggesting a pattern that is slightly
   different than the pattern there and in the text.

5. (0 points; suggested practice)
   In Chez Scheme (or some other Scheme with trace) evaluate the following.
	(define sum-all ; TYPE: (-> (tree number) number)
	  (lambda (ton)
	    ; ENSURES: result is the sum of all the numbers in ton
	    (cond
	     ((null? ton) 0)
	     ((number? (car ton))
	      (+ (car ton) (sum-all (cdr ton))))
	     (else (+ (sum-all (car ton))
		      (sum-all (cdr ton)))))))
	(trace sum-all)
	(sum-all '(1 2 (3 4) (5 (6 7)) 8))

6. (8 points; basic)
   One way to think of a tree of numbers is as a very general form of a matrix.
   For example, a 2-dimensional matrix can be represented by a list of lists
   of numbers.  A 3-dimensional matrix can be represented by a list of
   2-dimensional matrices, etc.  An empty list can be thought of as an empty
   matrix.  Matrices are usually regular, but trees do not have to be.

   In this problem, you are to write a procedure ``non-zero-tree?'',
   that takes tree of numbers, ``tr'', and returns #t if no element of ``tr''
   is 0, and #f otherwise.  It returns #t on an empty tree.

	(non-zero-tree? '(1 0 3)) ==> #f
	(non-zero-tree? '((1 1 3)
	            	  (2 3 4)
	                  (3 4 5))) ==> #t
	(non-zero-tree? '(((1 1 1) (2 2 2) (3 3 3)
			   (4 4 4) (5 5 5) (0 0 0)))) ==> #f
	(non-zero-tree? '(9 (-5) (6 (1 1 78) 8) (1 ( 2 (0 () 4) 2 ) 1))) ==> #f
	(non-zero-tree? '()) ==> #t
	(non-zero-tree? '(() ())) ==> #t

7. (8 points)
   Write a procedure, ``tree-scalar-mult'', that takes a number ``s''
   and a tree of numbers, ``tr'', and returns a tree with the same shape
   as ``tr'' but with each number replaced by that number times s. 
   For example,

	(tree-scalar-mult 2 '(1 -22 3)) ==> (2 -44 6)
	(tree-scalar-mult 3 '((1 1 3) (2 3 4) (3 4 5)))
		==> ((3 3 9) (6 9 12) (9 12 15))
	(tree-scalar-mult -1 '(((1 1 1) (2 2 2) (3 3 3)
			   (4 4 4) (5 5 5) (0 0 0))))
		==> (((-1 -1 -1) (-2 -2 -2) (-3 -3 -3)
		      (-4 -4 -4) (-5 -5 -5) (0 0 0)))
	(tree-scalar-mult 10 '((-1) ((2) -4 ()) (((-33)))))
		  ==> ((-10) ((20) -40 ()) (((-330))))
	(tree-scalar-mult 3 '()) ==> ()
	(tree-scalar-mult 4 '(() ())) ==> (() ())

8. (10 points)
   A tree of symbols can be thought of as a generalized paragraph
   or as a structured document.  Write a procedure, ``insert-title-all''
   that takes a ``title'', a ``name'', and a tree of symbols, ``para'',
   and retuns a tree that has the same shape as ``para'' except that
   the title inserted to the left of every occurrence of the name.

	(insert-title-all 'king 'elvis '(() ())) ==> (() ())
	(insert-title-all 'dictator-for-life 'calvin '(hobbes)) ==> (hobbes)
	(insert-title-all 'president 'clinton
			'((i see clinton now)
			   (clinton is coming in)))
		==> ((i see president clinton now)
		     (president clinton is coming in))
	(insert-title-all 'monsieur 'napolean
			  '((bon jour napolean) (ca va) ()
			    ((voudriez - vous) un (napolean))))
		==> ((bon jour monsieur napolean) (ca va) ()
		     ((voudriez - vous) un (monsieur napolean)))

   Here ((voudriez - vous) un (napolean)) means ``would you like a `napolean'?''.

9. (10 points; extra credit)
   Do exercise 4.8.  Check your answer on the computer.
   For this problem, you can consider the argument to ``count-parens-all''
   to be a tree of atomic items, where an atomic item
   is a Scheme datum that is not a pair and not the empty list.

10. (15 points)
   A psychologist might want to count the percentage a certain word is used
   in a paragraph.  Write a procedure ``percent-occurs'' that takes a symbol
   ``sym'' and a tree of symbols, ``tr'' and returns the percentage of
   symbols in tr that are sym.  Return 0 for an empty tree.
   For example,
	(percent-occurs 'a '(() ())) ==> 0
	(percent-occurs 'far '(it is a far far better thing I do))
		==> 22.22222222222222
	(percent-occurs 'uh '(uh I think it was uh like you know uh like this))
		==> 25.

	(percent-occurs 'is '((i understand that (harvard university is
			     (making its diplomas (larger or smaller))))
			     (this is (a (step in the (right direction))))
			     (r m hutchins)))
		==> 8.695652173913043

   Of course, your answers don't have to come out exactly the same
   if you use inexact numbers.

11. (15 points)
   Gary found out that when traveling in France, it's best to make sentences
   using ``please'', or as they say in French: ``si vous plait''.
   Write a procedure, ``make-polite'' that takes a ``please-phrase'' and
   a tree of symbols, ``paragraph'' and makes it polite,
   by tacking the please phrase on to the end of the list
   where the rightmost symbol is found, at the same level as that symbol.
   You may assume that the tree contains at least one symbol,
   and that no subtree is empty.  For example,

	(make-polite 'please '(can i have a coke))
		==> (can i have a coke please)
	(make-polite '(sil vous plait) '(monsieur))
		==> (monsieur (sil vous plait))
	(make-polite '(sil vous plait) '(((une biere) (pour madame))
			 et ((un coca) (pour moi))))
		==> (((une biere) (pour madame)) et
		     ((un coca) (pour moi (sil vous plait))))

12. (5 points; extra credit)
   Do exercise 4.10 (leftmost).  You may assume that the argument is
   a tree of symbols.

13. (5 points; extra credit)
   Define a procedure ``middle-most'' that takes tree with an odd number of
   atomic items and returns the middle atomic item in tree.
   We do not specify what your code should do for a list with an even number of
   items.

14. (8 points; extra credit)
   Write a procedure ``arith'' that takes a tree of symbols and numbers,
   and returns the number that is the result
   of evaluating the tree as an arithmetic expression.
   You may assume that the arithmetic expression is well formed,
   and that the only symbols in the tree are +, -, *, and /.  For example,
	(arith '(+ 1 2)) ==> 3
	(arith '(+ (* 3 4) (/ 12 2))) ==> 18
   Note that the input is quoted.  You should make up additional examples.

15. (10 points; extra credit)
   Write a procedure ``cond->if'' that takes a Scheme expression
   involving numbers, variables, ``quote'', procedure calls, ``cond'',
   and ``if'', and translates the expression into an equivalent one that
   doesn't use ``cond''.  That is, you are to translate each use of ``cond''
   into ``if''.  You may assume that each ``cond'' comes with an ``else'',
   and that there are no syntax errors.
   For example,

	(cond->if '(cons (car y) (quote ())))
		==> (cons (car y) (quote ()))
	(cond->if '(cond ((null? x) (quote ())) (else (car x))))
		==> (if (null? x) (quote ()) (car x))
	(cond->if '(+ 3 (cond ((< x 0) (- x)) ((zero? x) 0) (else x))))
		==> (+ 3 (if (< x 0) (- x) (if (zero? x) 0 x)))

   You should make up additional examples.
   Note that (quote x) prints as 'x in Scheme.


SECTION 4.5, NUMERICAL RECURSION AND ITERATION

16. (0 points; suggested practice)
   Do exercise 4.12.  (This is a bit of easy fun, especially on Chez Scheme.)
   You might also try tracing the procedures fact and fact-it.

17. (0 points; suggested practice)
   Do exercise 4.13.  Try it on the computer!

18. (6 points)
   Do exercise 4.14.  Use inexact (floating point) arithmetic,
   otherwise your program will take too long to run.
   Show in a transcript that the inequality given in the problem holds.

19. (5 points; basic)
   An iterative procedure is not a procedure with an accumulator!
   For example, the procedure ``last-item'' of program 2.2 is iterative.
   Explain why last-item is iterative.

20. (10 points; extra credit)
   Define a procedure factors-of that takes a positive number
   greater than zero
   and returns the
   prime factors of that number as a list.  Note that 1 is not a prime.
   You may assume that the argument is 2 or greater.
   For example,
	(factors-of 15) ==> (3 5)
	(factors-of 16) ==> (2 2 2 2)
	(factors-of 17) ==> (17)
   See Chapter 1 of Structure and Interpretation of Computer Programs,
   by Abelson and Sussman for hints.  This is on reserve at the library.


SECTION 4.6, ANALYZING THE FIBONACCI ALGORITHM

21. (0 points; suggested practice)
   Do exercise 4.15.  This is to help you understand the recursive version.

22. (0 points; suggested practice)
   Do exercise 4.16.  This is to help you understand the iterative version.

23. (10 points; basic)
   Do exercise 4.17.  Write down your best guess as to their rates of growth.

24. (6 points; basic)
   Write an iterative procedure, ``prod-it'', that takes a list of numbers
   and returns the prod of the numbers in the list.
   For example,
	(prod-it '()) ==> 1
	(prod-it '(1 2 3 4)) ==> 24

25. (10 points; basic)
   Do exercise 4.19.  Be sure your procedures are iterative,
   and do not use reverse either!  For example,

	(mk-asc-list-of-ints 0) ==> ()
	(mk-asc-list-of-ints 1) ==> (1)
	(mk-asc-list-of-ints 7) ==> (1 2 3 4 5 6 7)

	(mk-dsc-list-of-ints 0) ==> ()
	(mk-dsc-list-of-ints 1) ==> (1)
	(mk-dsc-list-of-ints 8) ==> (8 7 6 5 4 3 2 1)

26. (8 points)
   Do exercise 4.20 (occurs, occurs-it).


EXTRA CREDIT EXPLORATIONS

27. (5 points; extra credit)
   Do exercise 1.21 in ``Structure and Interpretation of Computer Programs'',
   by Abelson and Sussman.  This is on reserve at the library.

28. (8 points; extra credit)
   Do exercise 1.22 in ``Structure and Interpretation of Computer Programs'',
   by Abelson and Sussman.

29. (7 points; extra credit)
   Can you write an iterative version of the procedure append?
   If not, say why not.  If so, do it.

30. (20 points; extra credit)
   In spoken French, the last consonant of a word is (usually) not pronounced,
   except for ``c'', ``f'', ``l'', ``m'', ``n'', and ``r'' which are
   always pronounced (``m'' and ``n'' make the preceding vowel nasal,
   but we won't go into that here).
   However, there is an important exception to this rule called ``liaison'',
   which means ``linking''.  That is, when the next word in a sentence begins
   with a vowel, any final consonant of a word is moved to the beginning
   of the next word.  Of course there are exceptions to liaison as well.
   Of the exceptions to liaison we only mention a few:
	* liaison never applies to the word ``et'' (meaning ``and'',
		probably because it is so common).
	* the consonants ``m'', ``n'' do not get moved by liaison (usually).
	* liaison never takes place across sentences; since we represent a
		sentence as a list of words, if we have a paragraph of
		sentences, then the liaison does not go from one list of words
		to the next.
   Can you write a procedure that helps Gary prosounce French by showing
   the effects of dropping final consonants and handling liason?  For example,

	(liaison '((j e) (s u i s) (a m acute-e r i c a i n)))
		==> ((j e) (s u i) (s a m acute-e r i c a i n))
	(liaison '((n o u s) (a i m o n s) (l a) (b i f t e c k)))
		==> ((n o u) (s a i m o n) (l a) (b i f t e c)))
	(liaison '((n i) (t o u t) (grave-a) (f a i t) (u n e) (a u t r e)))
		  ; neither exactly                    an other
		==> ((n i) (t o u) (t grave-a) (f a i) (t u n e) (a u t r e))
	(liaison '(((i l s) (s o n t) (i t a l i e n s))
		   ((e t) (e l l e) (e s t) (a m acute-e r i c a i n e)))
		==> (((i l) (s o n) (t i t a l i e n))
		     ((e) (e l l e) (e s) (t a m acute-e r i c a i n e)))

   Hint: this problem is not necessarily tied to any of the particular
   techniques in this chapter.  It is something that you should know how
   to do the pieces of, although putting them together will not be easy.

31. (30 points; extra credit)
   Can procedures that take trees be written iteratively?  Yes, they can.
   Write an iterative procedure ``sum-all'' which takes a tree of numbers,
   and returns their sum.  You can, of course, use helping procedures,
   but all helping procedures must be iterative.
   For example,
	(sum-all '()) ==> 0
	(sum-all '(() ())) ==> 0
	(sum-all '(3 4 5)) ==> 12
	(sum-all '(3 (4) () (5))) ==> 12
	(sum-all '((3 5 7) () ((9)))) ==> 24
	(sum-all '((1 1 3)
	           (2 3 4)
	           (3 4 5))) ==> 26
	(sum-all '((((5)) 6) 8)) ==> 19
   Note that only iterative procedures will get points for this.

32. (50 points; extra credit)
   Write an iterative procedure ``add1-to-all'' that takes a tree of numbers
   and returns a tree of numbers with the same shape that but with each
   number replaced by the corresponding number plus one.  For example,
	(add1-to-all '(((3 4) (5 6))
	               ((7 8) (9 0))))
	   ==> (((4 5) (6 7))
	        ((8 9) (10 1)))
	(add1-to-all '((1 2) (3 4)))
	   ==> ((2 3) (4 5))
	(add1-to-all '(1 2))) ==> (2 3)
	(add1-to-all '(1 () (2)))
	   ==> (2 () (3))
	(add1-to-all '()) ==> ()
   Note that only iterative procedures will get points for this.