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

Candidate: You must prepare your solution to this programming exercise in advance. 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 that compiles and runs than to have a more complex program that crashes or, even worse, does not compile. So keep copies of old working partial solutions.

Unless otherwise noted, you must write all the code yourself, and may not use any external library routines, standard I/O (e.g. printf) and mathematical (e.g. log) routines excepted.

Prac's are marked on the performance of the program and on your understanding of it. I.e. Perfect program with zero understanding => zero marks! (``Forgetting'' is not an acceptable explanation.)

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

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.

NB. Note that each week's prac' groups are set their own specific problems. 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 prac' work (1--5), are both hurdles (50%) for CSE2304. If you fail one, or the other, or both, the highest mark that you can get is 44%(N).

Objectives:

Problem solving, time (and space) complexity, algorithm correctness.

Prac 2(A), week 5, 31 March - 4 April 2003

A (sub-)string is said to be ``skewed'' if some characters occur much more frequently than other characters, e.g. the following example string contains only 2×`B':

D C A D A C C D C A D A C A D A C A D D C A D A C A D C A D A C A A C A D D C A D A C A D C A D A C A D A B A D A C C D C A D A C D A C A D C D A A C A D C A D A C A D C A D A C A D A C A D A C A D C A D A C A B A C A D D C A D A C A D C A D A C A C A C A

 

Ignored characters: Here, as if any ignored characters were never in the input.

Task: write a program,

skewed chSet1 chSet2 f fileName

to find the longest skewed substring in file fileName (break ties arbitrarily) where

chSet1 is a set of ``real characters'' not to be ignored on input (all other characters are ignored),

chSet2 is a set of ``preferred characters'', &

f is a ``minimum skew'' (fraction) of preferred characters that the substring must contain,

and print the substring's start & end positions, its length, actual skew to the preferred characters, and also the characters if it is short else the first few and last few characters.

e.g. skewed ABCD AD 0.8 example

output: substring = 9..23 (15), AD-skew = 12/15 = 0.8, ADACADACADDCADA

(Character positions start at zero.)

[e.g. data (click)]

Prac 2(B), week 6, 7-11 April 2003

Given a series of positive and negative numbers, f[0], f[1], f[2], .., f[n-1], the sum of the ``part''  f[i..j]  is f[i]+f[i+1]+...+f[j] if j>=i and is zero if i>j.

A part of the series is said to be ``acceptable'' if its sum is >=0.

1.1 -3.3 1.0 -0.5 0.0 1.0 -3.14 1.1 -0.2

e.g. The series might be balance of payment figures, and it is not acceptable to be in the red over a part  (political joke omitted).

 

Task: Write a program,

acceptable fileName

to find the longest acceptable part in the series contained in file fileName (break ties arbitrarily),

and print the part's start, end, length and sum, also the values if it is short else the first few and last few values.

e.g. acceptable example

output: part = 2..5 (4), sum = 1.5,   1.0 -0.5 0.0 1.0

(Positions in the series are numbered from zero.)

[e.g. data (click)]