Description
You are asked to implement two linear-time selection algorithms: random and deterministic
selection algorithms. The algorithm takes an array of 𝑛 integers and a number 0 ≤ 𝑖 ≤ 𝑛 − 1 as
inputs. It will output the 𝑖-th smallest item in the array, which is called the order-𝑖 item. Note that
𝑖 starts from 0. This means the order-0 item is the smallest one in the entire array and the order-
(𝑛 − 1) item is the largest one. Based on the user specification, a corresponding selection
algorithm will be called.
1. Input format
You will read the data from the standard input. (For the ease of testing, you can write each test
case in a file and then use Linux file redirection function “<” to read from the file.)
The first line is an integer, which specifies the selection algorithm you should call. The integer
can take two values: 0 for random selection algorithm and 1 for deterministic selection algorithm.
Other values are illegal, but you can assume that the user will not input illegal values.
The second line specifies the number of integers in the input array. Let that number be 𝑛. The
third line is an integer 0 ≤ 𝑖 ≤ 𝑛 − 1, which indicates the algorithm will output the order-𝑖 item
in the array. You can assume that the user always inputs an order 𝑖 in the valid range. The
following n lines list the 𝑛 integers in the array.
An example of input is
0
5
2
-1
-3
2
0
4
This example calls random selection algorithm to get the order-2 item in an array of 5 elements.
That item should be 0.
2. Output Specification
Your program should output:
The order- item is
For the above example, the output is
The order-2 item is 0
III. Algorithm Runtime Comparison
We also ask you to study the runtime efficiency of these two selection algorithms. To do this,
you should generate different arrays of random integers with different sizes. Then you should
apply your selection algorithms to these arrays. Note the that runtime also depends on the
specified order 𝑖. To eliminate the dependency on 𝑖, for a given array, you should choose
multiple 𝑖’s, run your algorithm over all these 𝑖’s, and report the average runtime over all 𝑖’s. We
also ask you to compare the runtimes of these two selection algorithms with the quick sort
algorithm. Your final report should include a figure showing the runtimes of the two selection
algorithms and the quick sort algorithm versus the array size. For comparison purpose, you
should plot these three curves in the same figure. (You do not need to upload the source codes
for this comparison program.)
Hint:
1. You may want to write another program that calls the core selection procedures to do this
study.
2. You can use mrand48() to generate integers uniformly distributed in the range [-2
31, 231
-1].
3. You can use clock() function to get the runtime. See
http://www.cplusplus.com/reference/ctime/clock/
4. Although the major factor that affects the runtime is the size of the input array, however, the
runtime for an algorithm may also weakly depend on the detailed input array. Thus, for each
size, you should generate a number of arrays of that size and obtain the average runtime over
all these arrays. Also, for fair comparison, the same set of arrays should be applied to all the
algorithms.
5. You should try at least 5 representative sizes.
IV. Implementation Requirements and Restrictions
You must make sure that your code compiles successfully on a Linux operating system.
You may #include
may be included, and you may not make any call to any function in any other library.
V. Compiling
In order to let us test your code automatically, we ask you to provide a Makefile for us. The
output program should be named main.
VI. Testing
To make sure that the program works, you should test each selection algorithm you write
extensively. A hint: You can apply quick sort to verify whether the output of the selection
algorithm is correct.
VII. Submitting and Due Date
You should submit all the source code files for the program described in Section II, a
Makefile, and a report of the runtime comparison of the two selection algorithms and the
quick sort algorithm. The Makefile compiles a program named main. The report should be
in pdf format. At the end of your report, please attach your source code for the program
described in Section II. These files should be submitted as a tar file via the online judgment
system. See the announcement from the TAs for details about submission. The submission
deadline is 11:59 pm on Oct. 21, 2018.
VIII. Grading
Your program will be graded along five criteria:
1. Functional Correctness
2. Implementation Constraints
3. General Style
4. Performance
5. Report on the performance study
Functional Correctness is determined by running a variety of test cases against your program,
checking your solution using our automatic testing program. We will grade Implementation
Constraints to see if you have met all of the implementation requirements and restrictions.
General Style refers to the ease with which TAs can read and understand your program, and the
cleanliness and elegance of your code. Part of your grade will also be determined by the
performance of your algorithm. We will test your program with some large test cases. If your
program is not able to finish within a reasonable amount of time, you will lose the performance
score for those test cases. Finally, we will also read your report and grade it based on the quality
of your performance study.
