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.

1. 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).
   
   
2. 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?
   
   
3. A[0..N-1] is an array of integers. Tutor, choose one question:
   1. Give code to find the largest value in A.
   2. Give code to find the three largest values in A.
   3. 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.
   
   
4. 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=i-1, Hi2=i+1,
   2. Lo1=1, Hi1=10, Lo2=i, Hi2=10,
   3. Lo1=0, Hi1=9, Lo2= -i, Hi2=i,
   
   
5. 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