CS 37

Clab 36: Why Nondeterministic Computing Would Be Nice

Why Nondeterministic Computing Would Be Nice

We will soon look at a whole new way to do things. It's called non-deterministic computing. It may or may not be magic. But we can make a modified evaluator do it. Unfortunately, on ordinary computers, raw non-deterministic computing is very inefficient. But, if physicists can build modest size quantum computers, this will be an efficient way to program.

Before we really dig into this though I want you to spend this clab on some exercises. It is my hope that you will agree that these are not trivial in any of the ordinary imperative, functional, or object-oriented styles of programming. Next clab, we will see that they are easy in a non-deterministic, declarative style of programming.

  1. In your favorite language, write a function that will take a list (or array) as an argument and return all the permutations of that list (or array) either one at a time or in another collection.
  2. In your favorite language, write a program to solve: Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?
  3. The eight queens problem ex2.42 on page 124-126. (you can get this on the web by going to: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2.4 and backing up several screeen-fulls. (Here the hardest conceptual work is done for you, but make sure you thoroughly understand it.)
  4. Suppose sets of integers are represented by BSTs as described in section 2.3.3 of SICP. For example (define tree1 '(14 (7 () (12 () ())) (26 (20 (17 () ()) ()) (31 () ())))) Write a function path that will take an integer and a tree as arguments and return the path from the root to the integer given. For example: (path 31 tree1) (right right)

Next clab, I'll show you how to do these nondeterministically. Here is a sample run of my nondeterministic permutation function.

;;; Amb-Eval input: (nond-perm '(a b c)) ;;; Starting a new problem ;;; Amb-Eval value: (a b c) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (a c b) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (b a c) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (b c a) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (c a b) ;;; Amb-Eval input: try-again ;;; Amb-Eval value: (c b a) ;;; Amb-Eval input: try-again ;;; There are no more values of (nond-perm '(a b c))