[CSE2304] [progress]

Practical #2, semester 1, 2000
Group A: week 5, 27 March...
Group B: week 6, 3 April...

The problem is to write a program which reads a sequence of `N' floating point numbers from a file, finds the `M' smallest values in the file, and prints them. M and the filename are given as command line parameters (see ..../C/Basic/). This operation might be useful if studying the tail of a probability distribution, for example.
N is potentially very large, probably too large for all of the N numbers to fit into memory.
M is expected to be much less than N, M<<N, certainly small enough for M numbers to fit in memory.
Write a program in C to carry out the task:

   smallest M thefile
e.g. if thefile contains
then `smallest 4 thefile' are:
-99.0  -3.14  -3.14  3.14

You must NOT sort all N numbers and then print the first M values! Your program must not use more than O(M)-space. Efficiency is important.

Both groups must instrument their programs so that the numbers of comparisons of numbers carried out are printed. What can you say about the best-, average- and/or worst-case time-complexity of your program as a function of M and N?
[1 mark]

Every program must be commented with appropriate assertions, pre- & post-conditions, and loop invariants, to show that the program is correct.
[1 mark]

Total: [6 marks]

© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia