CSE2304 Tutorial #1 semester 1, 2000

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

Give the truth tables for the logical operators `and', `or', `=>' (implies).
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!
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.
Derive a program to solve the longest non-decreasing segment problem from the programming [Question-List].
Give a logical argument as to why the previous program (i) terminates and (ii) is correct.