Assignment 12a
Due Date: Monday at 9:00pm (Week 12)
Purpose To practice designing generative recursive functions.
Exercise 1 Complete the run-length encoding problem from lecture. Recall that the idea behind run-length encoding was to replace repeated sequences of the same character (a "run") with one copy of the character followed by the count of how many times it appeared in a row. For example, "AAAAAA" turns into "A6", and "AAABCCA" turns into "A3B1C2A1". Design a function run-length-encode that takes a [List-of 1String], and produces a single string containing the run-length encoded result. For convenience, use the explode function:(check-expect (run-length-encode (explode "AAABCCA")) "A3B1C2A1")
Exercise 2 Recall the data definition of a Wiki from class:
(define-struct page [title content]) ; A Wiki is a [List-of Page] ; A Page is a (make-page Symbol [List-of Symbol]) ; INTERPRETATION: An individual page contains a title and a ; list of links to other pages (represented by their titles). Design the function out-links that accepts a Symbol and a Wiki, and returns a [List-of Symbol] representing all pages that the given page links to. (This should not need to be a generative function.)
Exercise 3 Design the function in-links that accepts a Symbol and a Wiki, and returns a [List-of Symbol] representing all pages that link to the given page.
Graded Exercises
Exercise 4 Design the function cycle? that accepts a Wiki and returns a Boolean representing whether or not a cycle exists in the Wiki. In other words, is there a way to start on some page in the Wiki, follow links, and end up back at the same page?
Hint: You should not use accumulators for this problem; solve it generatively. Consider the structure of in-links and out-links in a Wiki, when there is a cycle present and when there is not. What cannot be true about the links for any pages involved in a cycle, and can you use that fact to come up with a generative idea?
Reminder: When designing a generative function, you need to explicitly write down the generative idea that guides why the recursion works, and you also need to explicitly write down the termination argument that explains why the function does not loop forever.
Exercise 5 Consider a simple binary-tree data definition. It contains no data, but rather is just the outline of a tree:
(define-struct node [left right]) ; A TreeOutline is one of ; - 'leaf ; - (make-node TreeOutline TreeOutline) Design the function all-trees-of-size that takes a Natural, and returns a list of all possible TreeOutlines with that many nodes in them.
Exercise 6 Challenge! (not graded) Design the function all-trees-of-height that takes a Natural and returns a list of all possible TreeOutlines of the given height (i.e., the longest distance from root to a 'leaf). Be careful with this function: it is very easy to generate duplicates (i.e. generate the same tree multiple times). A correct solution will not do so.