C++ Project

Concluído Postado Dec 2, 2011 Pago na entrega
Concluído 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 &#920;(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.

Android Programação C# Programação C++ Java PHP

ID do Projeto: #1321759

Sobre o projeto

1 proposta Projeto remoto Ativo em Dec 2, 2011

Concedido a:

wittyDeveloper

Dear,sir. I'm ready to start right now. Regards.

$40 USD em 2 dias
(60 Comentários)
5.5