On this page:
1 A ball on a table
2 DNA compression
3 Sorting

Assignment 12: More Generative Recursion

This assignment is due on Wednesday, 11/15 at 11:59 PM. Submit it using the Handin server as assignment a12.

Note Whenever we say to "design a function", we mean that you need to follow (and when necessary, adapt) a design recipe. When you write a generative recursive function, you must provide a termination argument.

Note Use Intermediate Student with lambda on this assignment, and further assignments in this course.

1 A ball on a table

Imagine that we have a ball on a flat and level table, and we start the ball moving. If nothing stops the ball, it will roll off the table.

Exercise 1 Design a data representation for a Ball. It needs to have both a horizontal and a vertical position, as well as both a horizontal and a vertical velocity. Write two examples for your data definition.

Exercise 2 Design the function on-table? which determines if a given Ball is on a given Table. You’ll need to design the data representation for a Table. A table is circular with a radius, centered at a point. You might find the function dist provided in assignment 6 useful.

Exercise 3 Design the function move-ball, which moves a Ball by its particular velocity, for a length of 1 time unit, producing a new Ball.

Exercise 4 Design the function how-long, which determines how many steps it will take for the given Ball to fall off the given Table. If the ball isn’t on the table to start with, the answer is 0. Assume that the Ball is moving.

2 DNA compression

DNA is often modeled by strings of the characters A, C, G and T. They are very long and so often need to be compressed. A simple way to do this is run-length encoding. It means to replace all substrings of identical consecutive characters with the character followed by the length of the substring. These substrings must be as long as possible. For example, the run-length encoding of the string "AAGCCCCTTAAAAAAAAAA" is the string "A2G1C4T2A10". This is the only run-length encoding—something like "A2G1C4T2A4A6" is not valid.

Exercise 5 Design a function rle-encode that consumes a DNA string and produces its run-length encoding.

Here are two examples:
(check-expect (rle-encode "AAGCCCCTTAAAAAAAAAA") "A2G1C4T2A10")
(check-expect (rle-encode "") "")

The consumed strings will only consist of upper-case A, C, G and T.

You may find the built-in function number->string helpful.

Hint: The key part of generative recursion is figuring out what subproblem to solve recursively. Design a helper function to generate the subproblem from the problem.

Exercise 6 Design a function rle-decode that consumes the run-length encoding of a DNA string and produces the DNA string.

Here are two examples:

(check-expect (rle-decode "A2G1C4T2A10") "AAGCCCCTTAAAAAAAAAA")
(check-expect (rle-decode "") "")

The consumed strings will only consist of upper-case A, C, G and T and positive integers.

You may find the built-in functions string->number and replicate helpful.

Exercise 7 Think: on what kinds of input is run-length encoding most efficient (compresses the most) versus least efficient (compresses the least)? Express your answer by defining two constant DNA strings very-efficient and very-inefficient, such that
(> (compression-ratio very-efficient) 100)
(< (compression-ratio very-inefficient) 1)
; compression-ratio : String -> Number
; returns how many times shorter rle-encode makes the given string
(check-expect (compression-ratio "AAAA") 2)
(check-expect (compression-ratio "AA") 1)
(define (compression-ratio s)
  (/ (string-length s) (string-length (rle-encode s))))

3 Sorting

Exercise 8 Read the discussion of the quick-sort algorithm and recall the implementations from lecture.

Design the following variant on quick-sort, named quick-sort-2: Instead of a using one pivot to split the input list into two lists each time quick-sort-2 is called, use two pivots to split the input list into three lists. Obtain one pivot by applying first to the input list, and the other pivot by applying first to the rest of the input list. Your quick-sort-2 should work on all lists of numbers, even lists with duplicates.

Exercise 9 Read the discussion of the insertion-sort algorithm and recall the implementation in Figure 72.

Design a function num-comps that consumes a list of numbers and produces the number of comparisons performed by the sort> function as given in Figure 72. The number of comparisons is the number of times that the >= (greater than or equal) function is applied. Here are some examples:

(check-expect (num-comps (list 4 3 2 1)) 3)
(check-expect (num-comps (list 1 2 3 4)) 6)
(check-expect (num-comps (list))         0)
(check-expect (num-comps (list 1))       0)
(check-expect (num-comps (list 1 2))     1)
(check-expect (num-comps (list 2 1))     1)

Hint: Follow the design recipe as with sort>.