C++ Project
$30-250 USD
Pago na entrega
Due date: Tuesday, Dec. 6,
What to submit: For each program, you should discuss briefly how you designed it. This may be done by providing
a simple piece of pseudo-code, and/or describe your considerations, concerns, and the problems that you have
encountered during coding and debugging. For each program, you should turn in a hard-copy (i.e., printed version)
of your code (including the discussion) during class. Also, in each program, you should include appropriate
comment lines to describe the source code.
1. Re-write the class template for a hash table using STL’s vector and list containers. The HashTable class
must have this function prototypes
template <class DataType>
class HashTable
{
public:
HashTable( int (*hf)(const DataType &), int s );
bool insert( const DataType & newObject );
bool retrieve( DataType & retrieved );
bool remove( DataType & removed );
bool update( DataType & updateObject );
void makeEmpty( );
private:
Array< LinkedList<DataType> > table;
int (*hashfunc)(const DataType &);
};
#include "[url removed, login to view]"
After you create the class
template, you will demonstrate its Θ(1) complexity. For this task, first create a HashTable of integers (int), and
then insert 1 million random integers (in the range 0 to 9,999,999) into this hash table. Measure the CPU time
required to insert all elements. Next, generate 100,000 random integers (in the same range) and search the hash table
using the retrieve function. Again, measure the CPU time required for all queries combined. Repeat the same
experiment for 10 million random integers and comment on the results. For both experiments, use a hash table of
size 1,000,117.
To generate random numbers in C++:
(i) Seed the random number generator: srand( time(NULL) );
(ii) To produce a random integer in the range 0 to (n-1): rand()%n; Note that function rand() returns an
integer in the range 0 to RAND_MAX, where RAND_MAX is compiler dependent and equal to 2m-1 (for
some value m). In some compilers, m can be as small as 15, thus returning values up to 32767 (which is not
sufficient to produce large random integers). Therefore, first find out what the value of m is in your
compiler (you can simply cout it) and, if it is not sufficient, use this statement instead when producing
random numbers: ((rand() << m) + rand())%n;
2. Your task is to compare the complexities of counting sort and quicksort when sorting elements with values within
a small range. First, generate 1 million random integers in the range 0 to 99,999 and store them in a vector
container. Then, write a counting sort function to sort the vector, and measure the CPU time required to complete
the sorting. Next, generate a new random vector and apply the sort algorithm of STL (that uses some variation of
quicksort). Again, measure the CPU time required to complete the sorting. Repeat the same experiment, but now
choose random values in the range 0 to 999,999. Comment on the results.
ID do Projeto: #1321759