[CSE2304]
[progress]

### CSSE, Monash University, .au, CSE2304, Tutorial #2, semester 1, 2001

Group A: week 5, 26 March...

Group B: week 4, 19 March...

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

- Give the
*shortest possible* piece of code to set
the variable `numDifferent' to the number of *different*
values in the integer variables x, y and z (i.e. 1, 2, or 3).

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

- A[0..N-1] is an array of integers.
**Tutor, choose one question:**
- Give code to find the largest value in A.
- Give code to find the three largest values in A.
- Give code to find the largest value that occurs exactly once in A
(harder than it looks).

Your code must not change A[].
It must be as efficient as possible.

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=i-1, Hi2=i+1,
- Lo1=1, Hi1=10, Lo2=i, Hi2=10,
- Lo1=0, Hi1=9, Lo2= -i, Hi2=i,

- A
*partition* of an integer, n,
is a list of positive numbers that add up to n.
Here, each partition is written in non-increasing order, e.g. 3+2, not 2+3.
Partitions can be ordered lexicographically,

e.g. **5:** 1+1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, 5.

Write a C routine,
`nextPartition(int length, int partition[])`

,
which is given a (non-increasing) partition and prints the partition,
if any, that comes *next* in lexicographical order.
e.g. Given 2+1+1+1, print 2+2+1.

Give an argument, as formal as possible, that your routine is correct
and terminates.

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