CSci 1301: Problem Set 5

Due: Tuesday, November 14th at 11:59pm by e-mail

Problem 1

Read Section 10.2 and do the following exercises:

1. Exercise 168 (4 points)
2. Exercise 169 (4 points)
3. Exercise 170 (4 points)

Problem 2

Read Section 11.3 in the textbook and do the following exercises:

1. Exercise 187 (4 points)
2. Exercise 188 (4 points)
3. Exercise 190 (10 points). Make sure to start with check-expects and a signature. Note that the function needs a recursive helper function.
   There are two possible interpretations of "all prefixes":
   • An empty list of letters is a prefix of every list of letters. Then the base case is an empty list of letters, and your check-expects would include:

     
     	    (check-expect (prefixes (list "a" "b" "c")) (list empty (list "a") (list "a" "b") (list "a" "b" "c")))
     	    (check-expect (prefixes (list "a")) (list empty (list "a")))
     	    ;; base case:
     	    (check-expect (prefixes empty) (list empty))
     	

   • The smallest list of letters (and the smallest prefix) is a one-letter list. Then your base case is when the list of letters has exactly one element, and your check-expects include:

     
     	    (check-expect (prefixes (list "a" "b" "c")) (list (list "a") (list "a" "b") (list "a" "b" "c")))
     	    ;; base case:
     	    (check-expect (prefixes (list "a")) (list (list "a")))
     	

   Both approaches have their challenges, but can be solved by carefully thinking of a solution in terms of the recursive case and the first element.

Don't forget to write signatures before you write the any code!
Note that the problem also involves the suffixes. You need to develop the check-expects for it.

Problem 3 (5 points)

Write a function list-append that takes two lists and combines them into one list:

    (check-expect (list-append (list 2 5 6) (list 1 3)) (list 2 5 6 1 3))

You need more test cases (and, as always, a signature) before you write the function.

Problem 4: extra credit, up to 15 points

This problem has a lot in common with Problem 2, so you might want to carefully study your solution before you attempt this one. Just like in problem 2, you will be working with lists of letters (1Strings). Your goal is to write a function arrangements that takes a list of letters and returns a list of all possible rearrangments of these letters. For instance, (arrangements (list "c" "a" "r")) would produce a list

    (list (list "c" "a" "r") (list "a" "c" "r") (list "a" "r" "c") (list "c" "r" "a") (list "r" "c" "a") (list "r" "a" "c"))

(which may or may not be in this order).
You would need to use the function list-append that you wrote in Problem 3 (or you may use an equivalent function append that is already defined in Racket).

The function arrangements will require several recursive helper functions. The discussion here gives you some hints for working on this problem. Work at your own pace, use paper and pencil to work through examples, and ask questions when you get stuck.

CSci 1301 course web site.