[CSE2304]
[progress]

### CSE2304, Tutorial #2, semester 1, 2000

Group A: week 4, 20 March...

Group B: week 5, 27 March...

Tutors: Select *some* of the questions to deal with.

- Give the
*shortest possible* piece of code to set
the variable `small' to the smaller of the values of x and y.

- Give code to set `small' to the smallest of x, y and z.
Resolve ties arbitrarily.
What is the lowest, average and
highest number of comparisons carried out?

- A[0..N-1] is an array of integers.
- Give code to find the (smallest | largest) value in A.
- Give code to find the two smallest values in A.
- Give code to find the three smallest values in A.
- Give code to find the longest segment A[i..j] of A
that is an arithmetic progression
such that A[i+1]-A[i] = A[i+2]-A[i+1] = ... A[j]-A[j-1].

Give assertions, pre- & post-conditions, loop-invariants
and arguments why the pieces of code *terminate* and
are *correct*.

- for i from Lo1 to Hi1 do
- for j from Lo2 to Hi2 do
- body

end_for

end_for

How many times is body executed if
- Lo1=1, Hi1=10, Lo2=1, Hi2=10,
- Lo1=1, Hi1=10, Lo2=i, Hi2=10,
- Lo1=1, Hi1=10, Lo2=1, Hi2=i,
- Lo1=1, Hi1=10, Lo2=i, Hi2=i+3 ?

- Permutations can be order lexicographically,
e.g. `1 2 3' < `2 1 3'.
If the integer array A contains a permutation of 1..n,
give an algorithm to change A so that it contains the
*next*
permutation in lexicographical order.

e.g. if n=7, A[ ] = 2 4 6 3 7 5 1 ---> 2 4 6 5 1 3 7

Why does your algorithm work?
Be as precise as possible.
[- after Dijkstra]

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