Homework 12
Due Date Wednesday, December 4 at 6pm
Purpose To practice working with accumulators and generative recursion.
You should submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept NO email submissions. Failure to submit a .rkt file will result in a 0.
You are only allowed to use the language specified at the top of this page: failure to do so will result in a 0.
Your code MUST conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.
You must follow all the steps of the design recipe when completing this assignment.
Please be sure to look at the feedback for assignments 10 and 11 before submitting, as we will be grading you more harshly on things we have warned you about before.
You must submit this assignment with your partner.
Exercise 1 Design the function remove-consec-dupl that takes a list of strings and eliminates consecutive duplicate elements. For example, eliminating the consecutive duplicate elements of (list "a" "a" "b" "c" "c" "c" "a" "b" "b") should produce (list "a" "b" "c" "a" "b").
Exercise 2 Design the function biggest-consec-streak which determines which string in a non-empty list of strings has the biggest consecutive streak. For example, "c" has the longest consecutive streak in (list "b" "a" "a" "b" "c" "c" "c" "b" "b"), despite not appearing the most times. Break ties by choosing the string that appeared earlier in the list.
Exercise 3 Design the function rotation? that takes two lists of strings and determines if they are rotations of each other. For example, the lists (list "a" "b" "c"), (list "c" "a" "b"), and (list "b" "c" "a") are all rotations of each other. The lists (list "a" "c" "b"), (list "b" "a" "c"), and (list "c" "b" "a") are also all rotations of each other. However, no list from the first group is a rotation of a list in the second group (and vice versa). Look to Homework 9 for a function that checks if two lists of strings are the same (do not use equal?).
Exercise 4 Design the function my-build-list, which functions exactly like the built-in list abstraction (you may not use build-list to define it).
Exercise 5 Consider the following data definitions for a forest of n-ary trees:
(define-struct ntnode [data children]) ; An [NTree X] is one of: ; - false ; - (make-ntnode X [NEList-of [NTree X]]) ; representing an n-ary tree or a leaf node ; A [Forest X] is a [List-of [NTree X]] ; and represents a forest of n-ary trees Complete the steps of the data design recipe for the given definitions. Then, design the function depth-trees that converts a forest into one that has the same structure of each tree, but the data represents the depth of each node. The following graphical example shows how this function would work on a [Forest String]:
Exercise 6 Design the function base10->16 that converts a non-negative integer from base 10 (decimal) to it’s string representation in base 16 (hexidecimal). Your function must adhere to the following algorithm:
Divide the number by 16.
Keep the remainder (in hexidecimal) as the digit
If the quotient isn’t zero, repeat the first step using the quotient as the number
For example, given the number 7562 the algorithm would go as follows:
7562 / 16 = 472 remainder 10 (digit = "A")
472 / 16 = 29 remainder 8 (digit = 8)
29 / 16 = 1 remainder 13 (digit = "D")
1 / 16 = 0 remainder 1 (digit = 1)
Result: "1D8A"
The following function will allow you to convert a single digit in base 16 to its string representation:
; base16->string : Nat[0, 15] -> 1String ; Converts a base16 digit to a string (check-expect (base16->string 0) "0") (check-expect (base16->string 5) "5") (check-expect (base16->string 9) "9") (check-expect (base16->string 10) "A") (check-expect (base16->string 15) "F") (define (base16->string nat) (local [(define BASE-ASCII (if (< nat 10) 48 55))] (string (integer->char (+ BASE-ASCII nat)))))
Exercise 7 Design the function mergesort that sorts a list of numbers. Your function must adhere to the following algorithm:
If the length of the supplied list is less than 2, return it
Otherwise, divide the list in half (if odd, the right gets the bigger)
Recursively sort each of the two halves
Merge them together and return the result
For the last step, take advantage of the fact that the two lists being merged are already sorted, so you can incrementally produce a new list just by looking at the first element of each of the two lists and choosing the smaller element (which must be smaller than all other numbers in that list). For example, if given (list 1 6) and (list 3 5 7) we would use the following process to merge them:
result = empty ; l1 = (list 1 6) ; l2 = (list 3 5 7)
result = (list 1) ; l1 = (list 6) ; l2 = (list 3 5 7)
result = (list 1 3) ; l1 = (list 6) ; l2 = (list 5 7)
result = (list 1 3 5) ; l1 = (list 6) ; l2 = (list 7)
result = (list 1 3 5 6) ; l1 = empty ; l2 = (list 7)
result = (list 1 3 5 6 7) ; l1 = empty ; l2 = empty