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
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
7.3 -3.14 10097.1 -99.0 7.3 -3.14 3.14 1000200.779 7.3 7.4
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?
Every program must be commented with appropriate
assertions, pre- & post-conditions, and
loop invariants, to show that the program is correct.
Total: [6 marks]
© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia