Reference no: EM13163851
Objective: familiarize with the performance characteristics of Quicksort under normal and worst case conditions. The assignment will require some programming and interpretation of the results.
Assignment: Using the pseudocode provided in the Cormen text for Quicksort, implement a working program that uses Quicksort to sort the elements in an array. In order to make meaningful comparisons, your array should be fairly large. (Try n=10,000 and see if you observe measurable changes in performance. You might also try a larger array if the time measurements do not vary significantly.) Do not use the library function, as it may include features that will prevent you from observing the differences between expected and worst case performance.
I suggest that your program be implemented in c, or c++, so that you can use debugging tools, such as gdb and ddd, if necessary.
Part I
Generate a main program which initializes your data array to be sorted - be careful with your array index numbers. You can use a random number generator to generate entries for the array. Then, call your Quicksort routine and sort the array while you measure the elapsed time. In the same program, using the sorted array as an input, call your Quicksort routine and again measure the elapsed time.
Part II
Modify your code to use a randomized selection of the pivot value as shown in the Randomized Quicksort pseudocode and rerun the experiment. Again, measure the execution times of sorting unsorted and already sorted arrays.
|
Prevent from the loss of confidentiality caused by malware?
: 1. Cybercirminals can use malware to steal files and information from computer, if this happens have loss of confidentiality. Explain how antivirus can be help to prevent from the loss of confidentiality caused by malware?
|
|
Implementation for the r-type instructions add, or, and and
: figuring out how to add an implementation for the R-type instructions ADD, OR, and AND. This is a MIPS architecture. // Incomplete behavioral model of MIPS pipeline
|
|
What is the order of the public key?
: the weaknesses that arise in Elgamal encryption if a public key of small order is used. We look at the following example. Assume Bob uses the group Z ? 29 with the primitive element ?= 2. His public key is ?= 28.
|
|
Design a java program that simulates a slot machine
: Design a java program that simulates a slot machine. When the program runs, it should do the following: Ask the user to enter the amount of money he or she wants to insert into the slot machine. ? Instead of displaying images, the program will random..
|
|
Characteristics of quicksort
: familiarize with the performance characteristics of Quicksort under normal and worst case conditions. The assignment will require some programming and interpretation of the results.
|
|
What is the total amount paid by the corporation
: A U.S. corporation has purchased currency call options to hedge a 70,000 pound payable. The premium is $.02 and the exercise price of the option is $.50. If the spot rate at the time of maturity is $.65, what is the total amount paid by the corporati..
|
|
Display the dfs starting from a specified vertex
: Design and implement a driver to show the following (check for 2 graphs; 1 is provided, including the starting vertex):Display the dfs starting from a specified vertex;Display the discovery/finishing time for each node in the graph;Show the Parenthes..
|
|
Client class to test implementation of the vector class
: Write a client class to test your implementation of the Vector3D class thatyou implemented. Name the package in which this class is defined (projectname) vector3dapp.
|
|
Attribute information about an array of floating point
: Write a program that contains a main function and three other functions that will return various attribute information about an array of floating point
|