C++ Data Structure Problem

Completed Posted Aug 19, 2003 Paid on delivery
Completed Paid on delivery

Sorted Vector

----------------

class SortedVector{

public:

void add(double myVal);

// adds myVal to the SortedVector. duplicates are allowed, so myVal is always added

double get(i);

// pre: i < number of values in the SortedVector.

// post: return is the value in position i (position 0 holds the smallest value).

int size(); //returns the number of elements currently in the SortedVector

private:

//.....

};

Implement this class however you can so that each add or get is fast. The class is called SortedVector because it allows you to keep adding values to it, and it behaves as if it keeps them in a vector sorted in ascending order -- [url removed, login to view](3) returns the value that would be in myVec[3].

Here is a test program with some test cases:

a=10 p=17 n=10 ==> 12 ,10 were placed in position 10

a=10 p=100,000,007 n=522 ==> 92884289 was placed in position 522

a=10, p=100,000,007 n=520 ==> 94387374, 58959785 were placed in position 520

a=10, p=17, n=100,000 ==> 16 was placed in position 100,000 at least 20 times

int main(){

cout<<"enter a,p,n "; int a,p,n; cin>>a>>p>>n;

cout<<"storing "<<n<<" values into the SortedVector"<<endl;

SortedVector sv; int val = 1;

for(int i=0; i<n; i++){

val = a*val%p; [url removed, login to view](val);

}

cout<<"finished "<<n<<" adds. Now will add and get "<<n<<" times"<<endl;

int ct=0;

for(int i=0; i<n; i++){

val = a*val%p; [url removed, login to view](val);

if( [url removed, login to view](n)==val && ct++<20 ) cout<< val << " was placed in position "<<n<<endl;

}

return 0;

}

REQUIREMENT: if n is 100,000 this program should finish in less than 30 seconds after entering a,p,n.

## Deliverables

1) I need the problem solved with an efficient algorithm involving data structures so it will complete in a reasonable amount of time.

2)All lines of code must be commented. The program must be run from debug mode within Visual C++ Studio (6.0 or higher).

3)Before coding, please describe how you plan to complete the problem and what algorthims and data structures you plan on using.

## Platform

WindowsXP, Visual C++ Studio 6.0( or equiv)

C Programming Engineering MySQL PHP Software Architecture Software Testing

Project ID: #2965069

About the project

15 proposals Remote project Active Aug 20, 2003

Awarded to:

mihaidanila

See private message.

$2 USD in 5 days
(12 Reviews)
3.3

15 freelancers are bidding on average $11 for this job

mihaiscortaru

See private message.

$10.2 USD in 5 days
(160 Reviews)
6.0
emilianbold

See private message.

$8.5 USD in 5 days
(77 Reviews)
5.8
projetcoder

See private message.

$17 USD in 5 days
(39 Reviews)
5.0
Uplink03

See private message.

$17 USD in 5 days
(68 Reviews)
4.8
vw821235vw

See private message.

$8.5 USD in 5 days
(94 Reviews)
4.3
lalesculiviu

See private message.

$17 USD in 5 days
(18 Reviews)
4.2
teamvw

See private message.

$17 USD in 5 days
(36 Reviews)
3.8
vw472664vw

See private message.

$6.8 USD in 5 days
(37 Reviews)
3.0
vasilevalaiba

See private message.

$17 USD in 5 days
(9 Reviews)
2.5
codepvw

See private message.

$10.2 USD in 5 days
(9 Reviews)
2.6
gurux

See private message.

$11.05 USD in 5 days
(4 Reviews)
2.7
blabbone

See private message.

$17 USD in 5 days
(1 Review)
1.9
bruce1970

See private message.

$4.25 USD in 5 days
(5 Reviews)
1.7
vw914040vw

See private message.

$5.95 USD in 5 days
(16 Reviews)
1.6