racket exercise
racket代写/racket作业代写: 这是一个比较典型的racket代写项目
• Make sure you read the OFFICIAL A07 post on Piazza for the answers to frequently
asked questions.
• Unless stated otherwise, all policies from Assignment 06 carry forward.
• You may use the following list functions and constants: cons, cons?, empty, empty?, first,
second, third, rest, list, append, length, string->list, list->string. You may not use reverse
(or define your own version) unless specified in the question.
• Some correctness marks will be allocated for avoiding exponential blowups, as demonstrated
by the max-list example in slide 07-6. (But note that not every repeated function invocation
leads to an exponential blowup.)
• You may not use abstract list functions.
Caution: Sketch out solutions to these problems on paper before implementing them. If you try
to compose this assignment in DrRacket directly without any pre-planning, you will with high
probability end up frustrated.
Here are the assignment questions you need to submit.
1. Perform the assignment 7 questions using the online evaluation “Stepping Problems” tool
linked to the course web page and available at
https://www.student.cs.uwaterloo.ca/˜cs135/stepping.
The instructions are the same as those in assignment 3; check there for more information if
necessary.
The use of local will involve defining constants and moving them to global scope. Don’t get
stuck because you are trying to re-submit those constants once they are in simplest form.
CS 135 — Fall 2017 Assignment 7 1
2. A trie (usually pronounced “try”) is a type of search tree suitable for searching through
collections of words. In the real world, trie-like structures can be useful for autocompletion
and text compression.
Your tries will be made up of TNodes, which are defined using a structure:
(define-struct tnode (key ends-word? children))
;; A TNode is a (make-tnode Char Bool (listof TNode))
;; requires: the TNodes of children are sorted in lexicographical
;; order by key.
We can then define a Trie:
(define-struct trie (children))
;; A Trie is a (make-trie (listof TNode))
;; requires: the TNodes of children are sorted in lexicographical
;; order by key.
Each key of a TNode is a character. Each TNode represents a character of at least one word
in the trie.
TNodes can have any number of children, but ordering is important: the children are sorted
by key in lexicographic order as determined by the charlist and list->string. This means that many of these functions will be
wrapper functions. The recursive helper functions you write will operate on lists of characters,
similar to the example given in slides 05-46 to 05-49, or Question 2 of Assignment 6.
This restriction on string functions also means you should not determine a string’s length with
string-length, or sort a list of strings (because that uses string