This month we revisit two classic problems of algorithm design. Those of you
who studied algorithm design are likely to have come across both, at one time
or another. So, original solutions only, please,
and no Internet searching.
Part 1:The usual complexity assumptions, which we'll be using for both parts this month, allow the definition of arrays that can be both queried and modified in constant time. However, these arrays do not get initialised: if we want an array to start off, say, composed entirely of zeroes, we have to spend on this time proportional to the size of the array, initialising one cell at a time.This is true at array definition, and is also true if we want to return an array to the all-zeroes state later on in the process. This month's question: construct with the available tools four functions, ALLOCATE_ARRAY, SET_VALUE, GET_VALUE and INITIALISE_ARRAY, each executing in constant time, that effectively, jointly, simulate a new type of array that can be initialised in constant time. The array should store real values. Part 2:Describe a function that finds the median of an array of reals in O(n) time, where n is the size of the array.Answer both questions for credit. Prove your claimed complexities. |
List of solvers:JJ Rabeyrin (8 July 19:39)Zhang Kaiyuan (26 July 12:45) |
Elegant and original solutions can be submitted to the puzzlemaster at riddles
brand.scso.com.
Names of solvers will be posted on this page. Notify if you don't want
your name to be mentioned.
The solution will be published at the end of the month.
Enjoy!