^CSE2304^
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.
© 2005 L. Allison,
School of Computer Science and Software Engineering,
Monash University, Australia 3800.
Created with "vi (Linux & IRIX)", charset=iso-8859-1