Pracs 2(A) and 2(B), CSE2304, CSSE, Monash, Semester 1, 2004

The [on-line] versions of the prac's may include [links], corrections and supplementary material and are to be taken as the reference documents. Check the on-line material regularly.

Candidate: You must prepare your solution to this programming exercise in advance (a 6pt subject => 12-hours work per week, every week). The designated platform, on which your solution must be demonstrated and on which it will be marked, is the `gcc' compiler running on `Linux'. If you develop a solution on another platform, it is your responsibility to ensure that it works correctly on the designated platform. Read the information under the [prac' guide], [on C and code modularity], [missed pracs] and [plagiarism] links on the [home page]. It is better to have a program that does only part of the prac' but compiles and runs rather than to have a more complex program that crashes or, even worse, does not compile. So keep copies of old working partial solutions.

Prac's are marked on the performance of your program and also on your understanding of the program. I.e. Perfect program with zero understanding => zero marks! ``Forgetting'' is not an acceptable explanation for lack of understanding. Unless otherwise noted, you must write all the code yourself, and may not use any external library routines, the usual I/O (e.g. printf) and mathematical (e.g. log) routines excepted.

NB. Remember that, from prac1, each week's prac' groups are set their own specific problems. Make sure that you do the correct problem for your prac'! You will get zero marks if you solve the wrong problem. The exam, and the prac' work, are both hurdles (half-marks) for the subject. If you fail one, or the other, or both, the highest mark that you can get for the subject is 44%(N).

Demonstrators are not obliged to mark programs that do not compile or that crash. Time allowing, they will try to help in tracking down errors, but they are not required to mark programs in such a state, particularly those that do not compile. Therefore keep backup copies of working partial-solutions (also see above).

Objectives: Problem solving, space- and time-complexity, algorithm correctness.
(The problems below could occur during analysis of time-series, e.g. data on the weather, share prices, etc..)

Prac 2(A), week 5, 29 March - 2 April 2004

Test data [here].

Write an efficient program:

longest m f

with these command-line parameters:

m is a non-negative integer, and

f is the name of a file containing n integers, i₀, i₁, ..., i_n-1, in free format.

Your program must find the longest interval, i_j, i_j+1, ..., i_k, such that  mx-mn<=m, and must print the interval's start position, j, its end position, k, and its length, k-j+1, where

mx = max(i_j, i_j+1, ..., i_k) and

mn = min(i_j, i_j+1, ..., i_k).

(Break any ties in favour of the earlier interval.)

There is no limit at all on the value of n (except that it can be stored in a 32-bit integer); it can be very large indeed. Do not assume that the file's contents can be held in memory, if you want high marks.

The only limit on a value in the file is that it can be stored in a 32-bit integer.

There is no particular limit on m (but it will be less than the size of the computer's memory in bytes divided by 1,000, for the sake of argument).

Example:

m = 2

the file contains:	5 9 4 2	3 5 4 4 5	6 3 8
solution:	4 8 5

Real examples will be much bigger!

Marking

Prac 2(B), week 7, 19-23 April 2004

Test data [here].

Write an efficient program:

stable r f

with these command-line parameters:

r is a positive integer,

f is the name of a file containing n floating-point numbers, x₀, x₁, ..., x_n-1, in free format.

Your program must find the "most-stable" interval x_j, x_j+1, ..., x_j+r-1, of length equal to  r, i.e. the interval such that  xb-xs  is as small as possible, and must print its start position, j, its smallest value, xs, its largest number, xb, and the range, xb-xs, where

xb = max(x_j, x_j+1, ..., x_j+r-1) and

xs = min(x_j, x_j+1, ..., x_j+r-1).

(Break any ties in favour of the earlier interval.)

There is no limit at all on the value of n (except that it can be stored in a 32-bit integer); it can be very large indeed. Do not assume that the file's contents can be held in memory, if you want high marks.

The only limit on a value in the file is that it can be stored in a 32-bit float.

There is no particular limit on r (but it will be less than the size of the computer's memory in bytes divided by 100, for the sake of argument).

Example:

r = 6

the file contains:	3.14 1.0
	3.14 3.000 3.140 3.2 3.14 3.141	6.99
	3.00 3.2
solution:	2  3.0  3.2  0.2

Real examples will be much bigger!

Marking