Chris Pollett>Old Classes>CS440, Fall 1997>Hw1
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.