For this assignment, you are to define numerous Scheme functions. For simplicity, place all of your function definitions in a single file named hw6.ss. Be sure to include a comment block at the top of the file containing you rname and also comment each function as to its behavior.

Part 1: Tail-Recursive Simulations

1. The random-walk function below simulates a random 1-dimensional walk. Initially, the walker is assumed to be at position 0. Depending on the flip of a coin, the walker either moves to the right (in the positive direction) or to the left (in the negative direction). The simulation ends when the walker reaches the specified goal distance, in either direction. (define (coin-flip) (if (< (random) 0.5) 'heads 'tails)) (define (random-walk goal-dist) (define (random-walk-help position) (begin (display "position: ") (display position) (newline) (cond ((= (abs position) goal-dist) #t) ((equal? (coin-flip) 'heads) (random-walk-help (add1 position))) (else (random-walk-help (sub1 position)))))) (random-walk-help 0))

   As is, this function displays each step in the walk and returns #t when the walk ends. Modify the function so that it keeps track of the number of steps in the walk and returns this value instead. Your modification should only utilize tail-recursion.

2. An interesting unsolved problem in mathematics concerns what is called the hailstone sequence of integers. This sequence is defined as follows: start with any integer. If that number is odd, then multiply it by 3 and add 1. If it is even, then divide it by 2. Now, repeat. For example, if we start with the number 5, we get the following sequence: 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . . Here, the subsequence 4, 2, 1 is reached which produces a loop. It was conjectured (by mathematician Lothar Collatz) that no matter what number you start with, you will always end up stuck in the 4, 2, 1 loop. It has, in fact, been shown to hold for all starting values less than 5 x 2⁶⁰ ≈ 5.764 x 10¹⁸. However, it still has not been proven for all numbers. Define a function named hailstone which has one input, the starting number, and which displays the hailstone sequence starting with that number and ending with 1. The function should return the length of the sequence. For example, (hailstone 1) should display the lone number 1 and evaluate to 1, while (hailstone 5) should display 5 16 8 4 2 1 and evaluate to 6. Your function should only utilize tail-recursion (perhaps a help function will be required).
   
   
3. Write a function named head% that simulates a specified number of coin flips and returns the percentage of those flips that were heads. For example, the call (head% 1000) would simulate 1,000 flips and return the percentage of heads, e.g., 50.8. Since the desired number of flips could be extremely large, your function should only utilize tail-recursion.

Part 2: Association Lists

Copy-and-paste this association list into your file and add the following definitions.

1. Define a function named translate that takes one input, a list representing a codon, and returns the abbreviation for the corresponding amino acid. For example, (translate '(G G A)) should evaluate to G.
   
   
2. Define a function named translate-sequence that takes one input, an arbitrarly long sequence of bases, and returns the corresponding list of amino acid abbreviations. That is, the first symbol in the returned list should be the amino acid corresponding to the first three bases, the second symbol should be the amino acid corresponding to the next three bases, etc. If the length of the sequence is not a multiple of three, any trailing bases should be ignored. For example, (translate-sequence '(G G A U U C A C C C)) should evaluate to (G F T).
   
   
3. When scientists extract mRNA samples from a cell, they invariably obtain partial sequences. Since the start of the sequence may be unknown, it is unclear exactly how the codons will be grouped in an actual translation. For example, in the sequence GGAUUCACCC the codons could be grouped starting at the beginning (yielding codons GGA UUC ACC), at the second base (yielding codons GAU UCA CCC), or at the third base (yielding codons AUU CAC). In addition, it is possible that the sequence has been read backwards, so the actual sequence to be translated should be CCCACUUAGG.

   Define a function named translate-all-possible that takes one input, an arbitrarly long sequence of bases, and returns a list containing all six possible translations of that sequence. Any extra bases at the beginning or end of the sequence should be ignored in the translation. For example, (translate-all-possible '(G G A U U C A C C C)) should evaluate to ((G F T) (N S P) (I H) (P T *) (P L R) (H L)).

Part 3: Binary Trees

In class, we discussed how structured lists could be used to represent binary trees. For example, the following binary tree is represented by the list to the right:

(define ANIMALS '(dog (bird (horse () ()) (cat () ())) (possum (dog () ()) ())))

Several utility functions (empty-tree?, root, left-subtree, and right-subtree) were provided for you in the lecture notes. Copy-and-paste these functions into your file and add the following functions for manipulating binary trees.

1. Define a function named height that takes one input, a list representing a binary tree, and returns the height of that tree. For example, given the ANIMALS structure above, (height ANIMALS) should evaluate to 3.
   
   
2. Define a function named contains? that takes two inputs, a list representing a binary tree and an atom, and returns #t if the list contains the atom (otherwise #f). For example, given the ANIMALS structure above, (contains? ANIMALS 'emu) should evaluate to #f while (contains? ANIMALS 'cat) should evaluate to #t.
   
   
3. Define a function named num-leaves that takes one input, a list representing a binary tree, and returns the number of leaf nodes in that tree. For example, given the ANIMALS structure above, (num-leaves ANIMALS) should evaluate to 3.