[CSE2304] [progress]

### CSSE, Monash University, .au, CSE2304, Tutorial #1, semester 1, 2001 Group A: week 3, 12 March... Group B: week 2, 5 March...

Tutors: (i) The purpose of the tutorials is not to solve the prac's! (ii) The purpose of the tutorials is to check answers, and discuss particular sticking points, not to simply make answers available. It will only be possible to cover all questions if the class has prepared them all in advance.

1. Give the truth table for the expression `(p and q) -> (not p and not q)`

2. An action, not a question:   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. Here are definitions for functions `length' and `append'.
length:
length nil = 0
length (cons H T) = 1 + length T
append:
append nil L = L
append (cons H T) L = cons H (append T L)
Prove formally that
length (append L1 L2) = (length L1) + (length L2)
for all lists L1 and L2.

4. Derive a program to solve the following problem from the programming [Question-List]:
A is an array of N integers. A segment, A[i..j], consists of the elements A[i], A[i+1], ..., A[j], if i<=j, and is empty otherwise. A segment A[i..j] is said to be an odd-even-run (OER) if there are nowhere three or more odd numbers adjacent to each other in the segment, and nowhere three or more even numbers adjacent to each other in the segment.
Write a piece of efficient C-code to find the longest OER in the array A, and print the start and end positions of this OER.

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

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