First programming assignment : Due Sept 15
Implement the randomized algorithm and the deterministic algorithm for selection (to be taught this week) and compare their performance over problems sizes varying from 1000 to a million.
For the randomized algorithm take average over 10 runs.
To compare the performance, keep a counter that keeps track of the total number of comparisons and also the running time (from the CPU clock).
Also you must choose the same input and values of k.
The assignment will be done individually and you have to give a demo to one of the TAs.
- Sandeep Sen
Hello Everyone,
Please note carefully the following instructions for the submission of your first programming assignment.
-
Your code should accept as input (on the command line) the name of a file. This file will contain the input set (one element per line) - an example file is attached for your reference.
-
We will invoke your code with the filename as the first parameter, and the desired rank as the second parameter. (Note that the number of elements in the set must be deduced by your code). a. If the specified rank is greater than the size of the set, or less than 0, your code must report the same as an error message. b. If case(a) does not apply, your code should report the value in the set with the desired rank.
-
Zip your file(s) and submit on Moodle (link will be made available shortly). You may name your zip file "<your_entry_number>.zip".
-
Important: Ensure that your code runs on GCL machines. We will not be able to evaluate your code on your laptops/ personal machines.