[CSE2304] [progress]

CSE2304, Tutorial #1, semester 1, 2000 Group A: week 2, 6 March... Group B: week 3, 13 March...

Tutors: The purpose of the tutorials is not to solve the prac's!

1. Give the truth tables for the logical operators `and', `or', `=>' (implies).

2. Recap the properties of the Abstract Data Type (ADT) [..../tildeAlgDS/List/].
Note the fact that most programming languages, and particularly Lisp, use the noun `nil' for the special list-terminating pointer value, and the adjective `null' for the predicate `equals nil', but C has to be different, of course!

3. The function map, also known as ``apply to all'', is defined as
• map f nil = nil
• map f (cons h t) = cons (f h) (map f t)
e.g. map sqr [1,2,3] = [1,4,9]
compose, `o', is defined as
1. (f o g)(x) = f(g(x))
e.g. (sqr o plus1)(6) = 49

Prove formally that map (f o g) L = ((map f) o (map g)) L, for all functions f and g, and for all Lists L.

4. Derive a program to solve the longest non-decreasing segment problem from the programming [Question-List].

5. Give a logical argument as to why the previous program (i) terminates and (ii) is correct.

© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia