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": 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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.