Assignment 6
Due Date : 10/30 @ 11:59pm
Instructions
Each of you should have a repository in GitHub with the name
assignment5-githubHandle
. Use this repository
and add all your work there. In order to clone the repositories
from GitHub to your machine (or watch this video video
instructions):
-
Sign in to GitHub.
-
On your GitHub home page your Github Handle should appear on the left as a button/drop down menu. Click that button and from the drop down menu select
cs2500f14
. The GitHub page will then navigate to the class' web page and to the contents that is available to you. -
On the right you should be able to see all repositories to which you have been given access. Find the repository whose name matches the pattern
assignment5-githubHandle
, where githubHandle is your GitHub account name, e.g,assignment5-john123
, and click on it. -
On the repositories home page look at the bottom right hand corner for a button with the text Clone in Desktop. By clicking on this button your browser will launch the GitHub client that we installed in class and ask for a location on your drive to store the repository.
If you are not using the GitHub client the clone URL is located above the Clone in Desktop button. Copy the URL and issue the following command on your shell
git clone URL
. - Create a file and save it under the folder on your drive that you selected in the preceding step.
Remember to push your changes to the GitHub repository often.
Note
For each question that asks you to design a program you are
expected to follow the Design Recipe in the same way as we did
in class. Failure to show all your work for each step
will cost you points. All tests should use check-expect
.
For this assignment you can assume that data definitions for
- List of Numbers (LoN)
- List of Strings (LoS)
- List of Symbols (LoSy)
Problem 1
-
Design a function called
lookup
that consumes a list ofStrings
los
and aNumber
n
and returns the string inlos
at indexn
. For example(lookup (cons "a" (cons "b" empty)) 2) => "b"
You may assume thatn
is always greater or equal than 1 and less than or equal to the size oflos
. -
Design a program called
string-cp
that given aString
s
and aNumber
n
returns a list of strings that containss
n
times, i.e.,(string-cp "Test" 4) => (cons "Test" (cons "Test" (cons "Test" (cons "Test" empty))))
-
Design a program called
string-dup
that consumes aString
s
and aNumber
n
and returns aString
that is the concatenation ofs
n
times with spaces between each instance ofs
, i.e.,(string-dup "a" 3) => "a a a"
-
Design a program called
string-reduce
that consumes aString
s
and aNumber
n
and produces a list of strings. The resulting list containsn
elements, the first element is the concatenation ofs
n
times with spaces in between, the second element is the concatenation ofs
n -1
times with spaces inbetween etc. For example(string-reduce "Test" 4) => (cons "Test Test Test Test" (cons "Test Test Test" (cons "Test Test" (cons "Test" empty))))
Hint: You might findstring-dup
usefull here.
Problem 2
You are provided with the following definition for binary tries
(define-struct leaf ()) ;; interpretation: represents a leaf on a BT, a node with no children (define-struct node (word left right)) ;; interpretation: represents a node on a BT with a word, a left and a right ;; subtree ;; A BinaryTree (BT) is one of ;; - (make-leaf) ;; - (make-node String BT BT)Using the above definitions
-
Provide the template for
BT
-
Design the program
bt-has?
that consumes aBT
tree
and aString
w
and returnstrue
ifw
is intree
andfalse
otherwise. -
Design the program
bt->los
that consumes aBT
tree
and returns the elements of the tree as a list of strings. At each node your function should- process the left subtree
- process the word at this node
- process the right subtree
(define bt-abc (make-node "b" (make-node "a" (make-leaf) (make-leaf)) (make-node "c" (make-leaf) (make-leaf)))) (bt->los bt-abc) (cons "a" (cons "b" (cons "c" empty))) (define bt1 (make-node "i" (make-node "d" (make-node "b" (make-node "a" (make-leaf) (make-leaf)) (make-node "c" (make-leaf) (make-leaf))) (make-node "f" (make-node "e" (make-leaf) (make-leaf)) (make-node "g" (make-leaf) (make-leaf)))) (make-node "p" (make-node "k" (make-node "j" (make-leaf) (make-leaf)) (make-node "l" (make-leaf) (make-leaf))) (make-node "r" (make-node "q" (make-leaf) (make-leaf)) (make-node "s" (make-leaf) (make-leaf)))))) (bt->los bt1) (cons "a" (cons "b" (cons "c" (cons "d" (cons "e" (cons "f" (cons "g" (cons "i" (cons "j" (cons "k" (cons "l" (cons "p" (cons "q" (cons "r" (cons "s" empty))))))))))))))))
Hint: lookup the documentation for the Racket functionappend
. You can solvebt->los
without the use ofappend
or any other function, just withcons
.