Chris Pollett>Old Classes>CS440, Fall 1997>Hw1

Homework #1

1. Verify (x1 and (x2 or not(x3))) is a propositional formula (as defined in class) over {and, or, not}.

2. Implement the Boolean function (x1 or not(x2 and not(x3))) in ML. Evaluate it in ML under all truth assignments.

3. Write an ML program which takes 5-tuples of reals and outputs their dot product. i.e.,

(a1,a2,a3,a4,a5)*(b1,b2,b3,b4,b5) = sum^5_{n=1}an*bn

4. Define fast(f,n) = f(1) if n=1 and f(fast(f,n-1)) if n >1. Implement fast in ML. Let f1(x)=2x. Let fn(x) = fast(fn-1,x). What function is f2? What function is f3?

Bonus: Implement f(n,x)=fn(x) in ML.

5. Write an efficient (as defined in class) ML program to compute the function G(n)

G(0)=G(1)=G(2):=1

G(n) := G(n-1) + 2G(n-2) + 2G(n-3).

Prepared by Chris Pollett.

Return to CS440 Syllabus.