Comp200 hw03

Comp 200 hw03: Sorting; trees

Due in class 01.Feb.21 (Wed)

For all problems where you write a function, be sure to apply your function to a couple of test cases, and show the results.

Turn in a printout from drscheme; If you have your test-cases up in the definitions window, you can just handwrite-in the results of your test cases.
Remember, you are encouraged to work in groups, but you must then write up the answer later, out of your own head.
Please staple! (else -1pt, grrr!)

(1pt) Okay, the grade database is now working; go ahead and register; then in later weeks you can check grades on-line.
(2pts) (Details to follow later: instructions for taking a digital picture of yourself, and i'll construct a face-book for the class.) Oops -- never mind, i haven't had a chance to set this up yet; no need for you to do anything!

(5pts) Generalize pentagon done in lab, to polygon.

;; (polygon: n size before): number, number, snapshot --> snapshot
;; Draw an n-sided polygon (each side length n) on "before",
;; and return the new snapshot.
;;
(define (polygon n size before)
   ...)

Be sure to first write smaller (helper) functions, as suggested in the notes, for drawing an individual side.

(3pts) Write the function insert, which takes a number n and a list-of-numbers lon which is already sorted (in ascending order). It returns a new list of numbers which contains n inserted into lon in the correct place.

;; (insert n lon): num,list-of-num --> list-of-num
;; lon is assumed to be sorted in ascending order.
;; Return a new list of numbers which contains n inserted
;; into lon in the correct place.
;;
(define (insert n lon)
   (if (empty? lon)
       ...n...   ;; How to insert something into the empty list?
       ...n...(first lon)...(insert n (rest lon))...
                 ;; How to combine these three things to get the desired list?

Here are some test cases for you (you should determine the expected answer yourself):

(insert 15 empty)
(insert  4 (list 7 9 11))
(insert 15 (list 10))
(insert 15 (list 7 9 11))
(insert 10 (list 7 9 11))

Hint: for each test case, ask yourself what the above recipe provides: e.g., when lon is (list 7 9 11) and n is 10, what is (insert n (rest lon)), exactly?

(3pts) We will write the function sort, which takes a list of numbers, and sorts it. How on earth to write this? Well, let's start with the generic recipe we've seen repeatedly for lists, and see if that helps.
A list of numbers is either
1. empty, or
2. (cons n lon), where n is a number, and lon is a list of numbers.
We've seen that functions which handle lists-of-numbers tend to have a shape similar to the shape of the above definition:
```
(define (sort l)
   (if (empty? l)
       ; How to sort the empty list?:
       ...             
       ; What are these two things?  How to combine them to get l, sorted?
       ...(first l)...(sort (rest l))...)))
```
Make up your own test cases, and try them!
(3 pts) Write the function timesHalved, which takes a number n and returns how many times n could be halved before it gets smaller than or equal to one. (Think, how many times you could bet half your wealth and (sadly) lose, until you had no more than a dollar?) Test your function on several test cases, including 1,048,576. (By the way, this will give the same answer as numberOfDoublings discussed in class, except that we approach the problem by dividing towards 1, rather than multiplying towards n.)
(3pts) Type in koch from class your class notes, and run it in drscheme. Now, try making up a different fractal curve. Decide what your "attempt 1" curve might look like on paper. Modify your code to do this, and see what attempts 2,3,... look like. You might want to modify your "attempt 1" curve so that it looks cooler when higher-level attempts are made. You can see some other ideas linked from an alternate view on the Koch curve.
What is the dimension of your curve, the "infinite attempt" version? That is, if your microscope zooms in by a factor of k, and you get k^d copies of your original figure, then your figure is dimension d. (See also the link above.)

Optional (3pts) Remembering the definition of a FamTree from lecture, write a function

;; (contains-name? a-name a-tree) : symbol, FamTree --> boolean
;; Does a-name occur in a-tree?
;; 
(define (contains-name? a-name a-tree)
   (if (unknown? a-tree)
       ...
       ..(child-name a-tree)..(child-ma a-tree)..(child-pa a-tree)..)))

(You can use to the FamTree code from lecture.) Now, write a function

;; (some-name-twice? a-tree) : FamTree --> boolean
;; Does a-tree contain a duplicated name, anywhere?
;; 
(define (some-name-twice? a-tree)
   (if (unknown? a-tree)
       ...
       ..(child-name a-tree)..(child-ma a-tree)..(child-pa a-tree)..)))

Here are some sample FamTrees to test your functions on. (They presume you have already the code for make-child!)