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):

1. Sign in to GitHub.

2. 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.

3. 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.

4. 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.

5. 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)

are given to you. You are encouraged to write templates for these data definitions if you need them, but they are not required.

Problem 1

1. Design a function called lookup that consumes a list of Strings los and a Number n and returns the string in los at index n. For example

   (lookup (cons "a" (cons "b" empty)) 2) => "b"

   You may assume that n is always greater or equal than 1 and less than or equal to the size of los.
2. Design a program called string-cp that given a String s and a Number n returns a list of strings that contains s n times, i.e.,

   (string-cp "Test" 4) => (cons "Test" 
                                 (cons "Test" 
                                       (cons "Test" 
                                             (cons "Test" empty))))

3. Design a program called string-dup that consumes a String s and a Number n and returns a String that is the concatenation of s n times with spaces between each instance of s, i.e.,

    (string-dup "a" 3) => "a a a" 

4. Design a program called string-reduce that consumes a String s and a Number n and produces a list of strings. The resulting list contains n elements, the first element is the concatenation of s n times with spaces in between, the second element is the concatenation of s 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 find string-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

1. Provide the template for BT
2. Design the program bt-has? that consumes a BT tree and a String w and returns true if w is in tree and false otherwise.
3. Design the program bt->los that consumes a BT tree and returns the elements of the tree as a list of strings. At each node your function should
   1. process the left subtree
   2. process the word at this node
   3. process the right subtree
   For example,

   (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 function append. You can solve bt->los without the use of append or any other function, just with cons.