Practical 2&3, CSE2304, CSSE, Monash University

Practicals 2&3(A) and 2&3(B), CSE2304, CSSE, Monash, Semester 1, 2005

The practical problems are available online via the unit home page for this year. The [on-line] practical problems may include [links], corrections and supplementary material and are to be taken as the reference documents. Check the on-line material regularly.

Student: 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 on the practical-work guide, C and code modularity, missed practicals and plagiarism on the [home page]. It is better to have a program that solves only part of the problem 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.
Practical work is 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 each week's practical group is set its own specific problem. Make sure that you do the correct problem for your week! You will get zero marks if you solve the wrong problem. The exam, and the practical 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: This unit is about problem solving and algorithm analysis, including complexity. Here is a problem to solve; the solution's complexity is important.

All Groups: Write a program process dataFile for the following task.

The command-line parameter, dataFile, is the name of a file which contains a sequence, S[0..N-1], of N integers, followed by a blank line, followed by a sequence, P[0..M-1], of M pairs of integers. Each pair, P[m]=(i,j) satisfies 0<=i<=j<N, for all m, 0<=m<M.

Your program must

(i) Read the N integers.

(ii) For each pair (i,j), print the position of the largest integer in S[i..j] in the format "%i\n". (Break any tie in favour of the earlier position.)

e.g. dataFile: 5 9 -4 99 9 -100 1 9 9 1 1 4 6 8 1 1 output: 3 7 1

You must make interesting test data of your own. (There is also a program to generate large amounts of data in [gen2.c].)

Your program may store the sequence of integers.

It must not store the pairs; it must read one pair and process it before moving on to the next pair.

N and M can be very large indeed, e.g., in the millions, or larger.

Very carefully read the extra conditions on the different groups below.

A "few seconds" is about 10 seconds on a 3gHz machine, more on a slower m/c, less on a faster m/c. (Try "man time".) Reading or writing a lot of data takes time (time the generator alone to get an idea of how long); data files must be on the local machine's disc (or the output of the generator can be "piped" (|, see prac0) directly into your program). The O( )-"constant" might change if an array out-grows the CPU's cache. (And the machine must have enough memory.)

It is important to have a simple, slow program working correctly by the end your practical 2. (Directory [.../C/Basic/] includes examples of command-line processing, malloc, realloc, etc. which might or might not be useful.)

The work will be marked in your practical 3.

Practical 2&3(A), weeks 5 and 7, 4-8 and 18-22 April

As N grows, M also grows, but rather more slowly than N, in fact
M is expected to be very approximately N/log(N).
Your program must run as quickly as possible for these conditions:

Marking out of 12

Compiles but has bugs --> 0 to 5/12 marks.
Works correctly on all small examples --> 6/12 marks.
Works correctly, in a few seconds, for N about 200,000, M about 50,000. --> 8/12 marks.
Works correctly, in a few seconds, for N about 20,000,000, M about 500,000. --> 10/12 marks.
As above plus well written, tested (with evidence) and understood --> 12/12 marks.

Practical 2&3(B), weeks 6 and 9, 11-15 April and 2-6 May

As N grows, M grows more quickly than N, in fact
M can be a significant fraction of N×N.
Your program must run as quickly as possible for these conditions:

Marking out of 12

Compiles but has bugs --> 0 to 5/12 marks.
Works correctly on all small examples --> 6/12 marks.
Works correctly, in a few seconds, for N 2,000 to 10,000, M about 2,000,000. --> 8/12 marks.
Works correctly, in a few seconds, for N 10,000 to 100,000, M about 10,000,000. --> 10/12 marks.
As above plus well written, tested (with evidence) and understood --> 12/12 marks.

Created with "vi (Linux & IRIX)", charset=iso-8859-1