Lab 11: Generative recursion 1

Remember to follow (and when necessary, adapt) the design recipe for each function. When you write a generative recursive function, you must provide a termination argument.

1 Power

As you saw in Lecture 22: Merge sort, creatively decomposing problems can make them faster to solve. In this section, you’ll apply this lesson to a different problem: raising a given number to a given power. First you’ll use structural recursion to design a slow solution to the problem; then you’ll use generative recursion to design a fast solution to the problem.

Exercise 2. A typical bank account yields 0.01% interest per day. In such an account, how much money does $1 become in 10,000 days? Compute the answer by running (power 1.0001 10000). How long does the computation take? (You can measure how long it takes using time.)

Exercise 3. Because you designed power by following the template for processing a NaturalNumber, it decomposes the problem (power 1.0001 10000) into the problem (power 1.0001 9999). We can make power faster by decomposing the exponent 10000 differently, into the exponent 5000 instead of 9999. After all, the answer to (power 1.0001 10000) is simply the square of the answer to (power 1.0001 5000).

Because this function follows a processing template, you can be sure that it always terminates, and you do not need to write any termination argument.

Exercise 5. Combine generate-power-tree and power-tree-result to design a function fast-power like power: it takes a number x and a natural number n and returns the number that is x raised to the n-th power. The definition of fast-power is very short, does not use recursion, and can be written just by looking at the signatures of generate-power-tree and power-tree-result. Your fast-power should pass the same tests as power above. Again, do not use the slow power function you designed, and do not use any built-in function for exponentiation either.

Exercise 6. Compute the same answer as Exercise 6 by running (fast-power 1.0001 10000). How long does the computation take? (You can measure how long it takes using time.)

2 DNA decompression

DNA is often modeled by sequences of the characters A, C, G and T. These sequences are very long and so often need to be compressed. A simple way to do this is run-length encoding. It means to replace identical consecutive characters with the character followed by its count. For example, the run-length encoding of AAAAAAAAAAGCCCCC is A10G1C5. This is the only run-length encoding—something like A4A6G1C5 is not valid, because each count must cover as many identical consecutive characters as possible.

The goal of this section is decoding, to convert run-length encodings to DNA sequences. For example, we want to convert the run-length encoding A10G1C5 to the DNA sequence AAAAAAAAAAGCCCCC, and we want to convert the empty run-length encoding to the empty DNA sequence. We will decompose the problem of decoding A10G1C5 to the subproblem of decoding G1C5.

We will represent both the run-length encoding and the DNA sequence as [ListOf 1String]. Recall that a 1String is a string of length 1, in other words, a character.

Hint: Your definition of drop-digits can use the built-in function string-numeric?

Exercise 8. Design another helper function, which collects all the digits at the beginning of a given [ListOf 1String].

Hint: Use the helper functions you designed in Exercises 7 and 8 to turn the problem (explode "A10G1C5") into the subproblem (explode "G1C5"). Also, use the built-in function string->number.

3 DNA compression

The goal of this section is encoding, to convert DNA sequences to run-length encodings. For example, we want to convert the DNA sequence AAAAAAAAAAGCCCCC to the run-length encoding A10G1C5, and we want to convert the empty DNA sequence to the empty run-length encoding. We will decompose the problem of encoding AAAAAAAAAAGCCCCC to the subproblem of encoding GCCCCC.

Again, we will represent both the DNA sequence and the run-length encoding as [ListOf 1String], in other words, a list of characters.

Hint: Your definition of drop-digits can use the built-in function string=?

Exercise 13. Design another helper function, which collects all the copies of a given 1String at the beginning of a given [ListOf 1String].

Exercise 14. Next, you will use the helpers above to decompose encoding problems via the same DNATree that you used in the previous section to decompose decoding problems.

4 Challenges

Exercise 17. Abstract from the helpers drop-digits and drop-letter you designed in Exercises 7 and 12.

Exercise 18. Abstract from the helpers you designed in Exercises 8 and 13.