Starting from:
$25
VE281- Assignment 2 Linear-Time Selection Solved
I. Motivation
1. To give you experience in implementing two linear-time selection algorithms, i.e., random and deterministic selection algorithms.
2. To empirically study the runtime efficiency of the two selection algorithms and compare the runtime efficiency of the selection algorithms with the sorting algorithms.
II. Programming Assignment
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-<i item is <val
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 [-231, 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 <iostream, <fstream, <sstream, <string,
<cstdlib, <climits, <ctime, and <cassert. No other system header files 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.
1. To give you experience in implementing two linear-time selection algorithms, i.e., random and deterministic selection algorithms.
2. To empirically study the runtime efficiency of the two selection algorithms and compare the runtime efficiency of the selection algorithms with the sorting algorithms.
II. Programming Assignment
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-<i item is <val
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 [-231, 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 <iostream, <fstream, <sstream, <string,
<cstdlib, <climits, <ctime, and <cassert. No other system header files 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.
1 file (148.4KB)
