CSE2304 Tutorial #2 semester 1, 2000

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.
1. Give code to find the (smallest | largest) value in A.
2. Give code to find the two smallest values in A.
3. Give code to find the three smallest values in A.
4. 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
1. Lo1=1, Hi1=10, Lo2=1, Hi2=10,
2. Lo1=1, Hi1=10, Lo2=i, Hi2=10,
3. Lo1=1, Hi1=10, Lo2=1, Hi2=i,
4. 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]