My Question is how would i make the function run at O(log(n)) time. would i need

ID: 3751958 • Letter: M

Question

My Question is how would i make the function run at O(log(n)) time. would i need something like a binary tree. I have the first two functions do they look alright.

This is my code below so far

#include "trendtracker.h"

Trendtracker::Trendtracker(string filename)

{

string tags;

ifstream file;

file.open(filename);

if (file) {

while (file >> tags) {

Entry trends;

trends.hashtag = tags;

trends.pop = 0;

E.push_back(trends);

}

file.open("tiny.txt");

file.open("small.txt");

file.open("hashtags.txt");

file.open("tweeted.txt");

file.close();

}

int Trendtracker::size()

{

return E.size();

}

The code below is the main.cpp and the header file

#include <cassert>

#include <fstream>

#include <iostream>

#include <cstdlib>

#include <string>

#include "trendtracker.h"

using namespace std;

inline void _test(const char* expression, const char* file, int line)

{

cerr << "test(" << expression << ") failed in file " << file;

cerr << ", line " << line << "." << endl;

abort();

}

#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : _test(#EXPRESSION, __FILE__, __LINE__))

int main()

{

// Setup

vector<string> R;

string s, line;

// Test constructor, size(), popularity(), tweeted()

Trendtracker T1("small.txt");

test(T1.size() == 4);

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 0);

test(T1.popularity("#C++") == 0);

T1.tweeted("#programming");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 1);

test(T1.popularity("#C++") == 0);

T1.tweeted("#programming");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 2);

test(T1.popularity("#C++") == 0);

T1.tweeted("#programming");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 0);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 3);

test(T1.popularity("#C++") == 0);

T1.tweeted("#cs4all");

test(T1.popularity("#algorithms") == 0);

test(T1.popularity("#cs4all") == 1);

test(T1.popularity("#programming") == 3);

test(T1.popularity("#C++") == 0);

T1.tweeted("#algorithms");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 1);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 3);

test(T1.popularity("#C++") == 0);

T1.tweeted("#cs4all");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 3);

test(T1.popularity("#C++") == 0);

T1.tweeted("#datastructures");

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#datastructures") == -1);

test(T1.popularity("#programming") == 3);

test(T1.popularity("#C++") == 0);

Trendtracker T2("small.txt");

T2.tweeted("#programming");

T2.tweeted("#C++");

T2.tweeted("#cs4all");

T2.tweeted("#algorithms");

test(T2.popularity("#algorithms") == 2);

test(T2.popularity("#cs4all") == 3);

test(T2.popularity("#programming") == 5);

test(T2.popularity("#C++") == 4);

// Enforce no usage of global variables

test(T1.popularity("#algorithms") == 1);

test(T1.popularity("#cs4all") == 2);

test(T1.popularity("#programming") == 3);

test(T1.popularity("#C++") == 0);

// Test top_trend(), top_three_trends()

Trendtracker T3("small.txt");

T3.top_three_trends(R);

test(R.size() == 3);

T3.tweeted("#programming");

test(T3.top_trend() == "#programming");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#programming");

T3.tweeted("#C++");

test(T3.top_trend() == "#C++");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#C++");

test(R[1] == "#programming");

T3.tweeted("#algorithms");

test(T3.top_trend() == "#algorithms");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#algorithms");

test(R[1] == "#C++");

test(R[2] == "#programming");

T3.tweeted("#cs4all");

test(T3.top_trend() == "#cs4all");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#cs4all");

test(R[1] == "#algorithms");

test(R[2] == "#C++");

// At this point:

// cs4all: 4

// algorithms: 3

// C++: 2

// programming: 1

T3.tweeted("#programming");

test(T3.top_trend() == "#programming");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#programming");

test(R[1] == "#cs4all");

test(R[2] == "#algorithms");

// At this point:

// programming: 5

// cs4all: 4

// algorithms: 3

// C++: 2

T3.tweeted("#cs4all");

T3.tweeted("#algorithms");

test(T3.top_trend() == "#cs4all");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#cs4all");

test(R[1] == "#programming");

test(R[2] == "#algorithms");

// At this point:

// cs4all: 6

// programming: 5

// algorithms: 4

// C++: 2

for (int i = 0; i < 10000; ++i)

T3.tweeted("#C++");

test(T3.top_trend() == "#C++");

T3.top_three_trends(R);

test(R.size() == 3);

test(R[0] == "#C++");

test(R[1] == "#cs4all");

test(R[2] == "#programming");

Trendtracker T4("hashtags.txt");

test(T4.size() == 300000);

ifstream f;

f.open("tweeted.txt");

assert(f.is_open()); // If this fails, you're missing tweeted.txt

while (getline(f, line))

T4.tweeted(line);

f.close();

test(T4.popularity("#programming") == 10);

test(T4.popularity("#computer") == 9);

test(T4.popularity("#is") == 8);

test(T4.popularity("#very") == 7);

test(T4.popularity("#fun") == 6);

test(T4.popularity("#but") == 5);

test(T4.popularity("#sometimes") == 5);

test(T4.popularity("#can") == 5);

test(T4.popularity("#be") == 5);

test(T4.popularity("#challenging") == 5);

test(T4.top_trend() == "#programming");

T4.top_three_trends(R);

test(R[0] == "#programming");

test(R[1] == "#computer");

test(R[2] == "#is");

// Test a Trendtracker with a single hashtag

Trendtracker T5("tiny.txt");

test(T5.size() == 1);

test(T5.popularity("#solo") == 0);

test(T5.popularity("#duo") == -1);

T5.tweeted("#solo");

test(T5.popularity("#solo") == 1);

test(T5.popularity("#duo") == -1);

test(T5.top_trend() == "#solo");

T5.top_three_trends(R);

test(R.size() == 1);

test(R[0] == "#solo");

cout << "Assignment complete." << endl;

}

The header file below

#ifndef TRENDTRACKER_H

#define TRENDTRACKER_H

#include <cassert>

#include <fstream>

#include <vector>

#include <string>

using namespace std;

class Trendtracker

{

// For the mandatory running times below:

// n is the number of hashtags in the Trendtracker.

public:

// Creates a Trendtracker containing hashtags

// found in the provided file.

// The file is promised to have the following format:

// string1

// string2

// ...

// stringN

// where string1 < string2 < ... < stringN

// Must run in O(n) time.

Trendtracker(string filename);

// Return the number of hashtags in the Trendtracker.

// Must run in O(1) time.

int size();

// Adds 1 to the total number times a hashtag has been tweeted.

// If the hashtag does not exist in TrendTracker, does nothing.

// Must run in O(log(n)) time.

void tweeted(string ht);

// Returns the number of times a hashtag has been tweeted.

// If the hashtag does not exist in Trendtracker, returns -1.

// Must run in O(log(n)) time.

int popularity(string name);

// Returns a most-tweeted hashtag.

// If the Trendtracker has no hashtags, returns "".

// Must run in O(1) time.

string top_trend();

// Fills the provided vector with the 3 most-tweeted hashtags,

// in order from most-tweeted to least-tweeted.

// If there are fewer than 3 hashtags, then the vector is filled

// with all hashtags (in most-tweeted to least-tweeted order).

// Must run in O(1) time.

void top_three_trends(vector<string> &T);

private:

// A simple class representing a hashtag and

// the number of times it has been tweeted.

class Entry

{

public:

string hashtag;

int pop;

};

// Optional helper method.

// Returns the index of E containing an Entry with hashtag ht.

// If no such hashtag is found, returns -1.

// Should run in O(log(n)).

int search(string ht);

// Entries sorted (lexicographically) by hashtag.

vector<Entry> E;

// Stores indices of the (up to) three most-tweeted

// entries in E.

vector<int> S;

};

#endif

void tweeted(string ht) and int popularity(string name) and int search(string ht) They must run at O(log(n)) time

string top_trend() and void top_three_trends(vector<string> &T) They must run at O(1) time

thanks for your help

1 Introduction In the previous homework, you implemented a Trendtracker data structure that tracks information about a set of hashtags. Unfortunately, the efficiency of data structure's operations (tweeted, popularity, top_three_trends, etc.) probably wasn't great. For tracking a few thousand hashtags, the efficiency was good enough, but Twitter has hundreds of mllions of users using millions of distinct hashtags.2 So for this homework, you will implement the same class, but using an efficient two-vector-based data structure (see Figure 1) vector s 415 string hashtag #adsl #big | #cat | #dogl #eggl #fad | #gig | #hot vectorEntry» E 2 18 4-10- 9 10 12- 11 int pop Figure 1: Representing hashtags and their popularities using an efficient vector-based data structure. 2 Instructions The following files have been given to you 1. A C++ header file (trendtracker.h) declaring the Trendtracker class. 2. A C++source file (main.cpp) containing a main function with tests. 3. A text file (tiny.txt) containing 1 hashtag, 4. A text file (small.txt) containing 4 hashtags. 5. A text file (hashtags.txt) containing 300000 hashtags3 6. A text file (tweeted.txt) containing 1500000 hashtags. Download the files at http://andrewwinslow.com/3333/hwTT2/ Create a new C++ source file named trendtracker.cpp that implements the Trendtracker class, so that trendtracker.cpp and the pro- vided files compile into a program that runs with no failed tests. Submit the source file trendtracker.cpp.

Explanation / Answer

1) In the given question, we need to implement the a class Trendtracker but using an efficien two-vector based data structure.
2) will start with the main program MAIN.CPP:
#include
#include
#include
#include
#include
#include "trendtracker.h"

using namespace std;

inline void _test(const char expression, const char file, int line)
{
cerr << "test(" << expression << ") failed in file " << file;
cerr << ", line " << line << "." << endl;
abort();
}

#define test(EXPRESSION) ((EXPRESSION) ? (void)0 : test(#EXPRESSION, _FILE_, _LINE__))

int main()
{
// Setup
vector R;
string s, line;

// Test constructor, size(), popularity(), tweeted()
Trendtracker T1("small.txt");
test(T1.size() == 4);
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 0);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 0);
test(T1.popularity("#C++") == 0);

T1.tweeted("#programming");
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 0);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 1);
test(T1.popularity("#C++") == 0);

T1.tweeted("#cs4all");
test(T1.popularity("#algorithms") == 0);
test(T1.popularity("#cs4all") == 1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);

T1.tweeted("#algorithms");
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 1);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);

T1.tweeted("#cs4all");
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 2);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);

T1.tweeted("#datastructures");
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 2);
test(T1.popularity("#datastructures") == -1);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);

Trendtracker T2("small.txt");
T2.tweeted("#programming");
T2.tweeted("#programming");
T2.tweeted("#programming");
T2.tweeted("#programming");
T2.tweeted("#programming");
T2.tweeted("#C++");
T2.tweeted("#C++");
T2.tweeted("#C++");
T2.tweeted("#C++");
T2.tweeted("#cs4all");
T2.tweeted("#cs4all");
T2.tweeted("#cs4all");
T2.tweeted("#algorithms");
T2.tweeted("#algorithms");
test(T2.popularity("#algorithms") == 2);
test(T2.popularity("#cs4all") == 3);
test(T2.popularity("#programming") == 5);
test(T2.popularity("#C++") == 4);

// Enforce no usage of global variables
test(T1.popularity("#algorithms") == 1);
test(T1.popularity("#cs4all") == 2);
test(T1.popularity("#programming") == 3);
test(T1.popularity("#C++") == 0);

// Test top_trend(), top_three_trends()
Trendtracker T3("small.txt");
T3.top_three_trends(R);
test(R.size() == 3);

T3.tweeted("#programming");
test(T3.top_trend() == "#programming");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#programming");

T3.tweeted("#C++");
T3.tweeted("#C++");
test(T3.top_trend() == "#C++");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#C++");
test(R[1] == "#programming");

T3.tweeted("#algorithms");
T3.tweeted("#algorithms");
T3.tweeted("#algorithms");
test(T3.top_trend() == "#algorithms");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#algorithms");
test(R[1] == "#C++");
test(R[2] == "#programming");

T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
test(T3.top_trend() == "#cs4all");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#cs4all");
test(R[1] == "#algorithms");

test(R[2] == "#C++");

// At this point:
// cs4all: 4
// algorithms: 3
// C++: 2
// programming: 1

T3.tweeted("#programming");
T3.tweeted("#programming");
T3.tweeted("#programming");
T3.tweeted("#programming");
test(T3.top_trend() == "#programming");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#programming");
test(R[1] == "#cs4all");
test(R[2] == "#algorithms");

// At this point:
// programming: 5
// cs4all: 4
// algorithms: 3
// C++: 2

T3.tweeted("#cs4all");
T3.tweeted("#cs4all");
T3.tweeted("#algorithms");
test(T3.top_trend() == "#cs4all");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#cs4all");
test(R[1] == "#programming");
test(R[2] == "#algorithms");

// At this point:
// cs4all: 6
// programming: 5
// algorithms: 4
// C++: 2

for (int i = 0; i < 10000; ++i)
T3.tweeted("#C++");
test(T3.top_trend() == "#C++");
T3.top_three_trends(R);
test(R.size() == 3);
test(R[0] == "#C++");
test(R[1] == "#cs4all");
test(R[2] == "#programming");

Trendtracker T4("hashtags.txt");
test(T4.size() == 300000);

ifstream f;
f.open("tweeted.txt");
assert(f.is_open()); // If this fails, you're missing tweeted.txt
while (getline(f, line))
T4.tweeted(line);
f.close();

test(T4.popularity("#programming") == 10);
test(T4.popularity("#computer") == 9);
test(T4.popularity("#is") == 8);
test(T4.popularity("#very") == 7);
test(T4.popularity("#fun") == 6);
test(T4.popularity("#but") == 5);
test(T4.popularity("#sometimes") == 5);
test(T4.popularity("#can") == 5);
test(T4.popularity("#be") == 5);
test(T4.popularity("#challenging") == 5);

test(T4.top_trend() == "#programming");

T4.top_three_trends(R);
test(R[0] == "#programming");
test(R[1] == "#computer");
test(R[2] == "#is");

// Test a Trendtracker with a single hashtag
Trendtracker T5("tiny.txt");
test(T5.size() == 1);
test(T5.popularity("#solo") == 0);
test(T5.popularity("#duo") == -1);
T5.tweeted("#solo");
test(T5.popularity("#solo") == 1);
test(T5.popularity("#duo") == -1);
test(T5.top_trend() == "#solo");
T5.top_three_trends(R);
test(R.size() == 1);
test(R[0] == "#solo");

cout << "Assignment complete." << endl;
}

//END MAIN.CPP

3) Now will write the TRENDTRACKER.CPP code:
// TRENDTRACKER.CPP

#include "trendtracker.h"

// Creates a Trendtracker containing hashtags
// found in the provided file.
// The file is promised to have the following format:
//
// string1
// string2
// ...
// stringN
//
// where string1 < string2 < ... < stringN
//
// Must run in O(n) time.
Trendtracker::Trendtracker(string filename)
{
string line;
ifstream file(filename);
while (file >> line)
{
Entry sample;
sample.hashtag = line;
sample.pop = 0;
E.push_back(sample);
}
}

// Return the number of hashtags in the Trendtracker.
//
// Must run in O(1) time.
int Trendtracker::size()
{
return E.size();
}

// Adds 1 to the total number times a hashtag has been tweeted.
// If the hashtag does not exist in TrendTracker, does nothing.
//
// Must run in O(log(n)) time.
void Trendtracker::tweeted(string ht)
{
for (vector<Entry>::size_type x = 0; x != E.size(); x++)
{
if (E[x].hashtag == ht)
{
E[x].pop++;
return;
}
}
}

// Returns the number of times a hashtag has been tweeted.
// If the hashtag does not exist in Trendtracker, returns -1.
//
// Must run in O(log(n)) time.
int Trendtracker::popularity(string name)
{
for (int i=0; i <E.size(); i++)
{
if (E[i].hashtag == name)
{
return E[i].pop;
}
}

return -1;
}

// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
//
// Must run in O(1) time.
string Trendtracker::top_trend()
{

if(size() == 0)
return "";
//return an empty string if empty

int i, n, popular;

//loops through Trendtracker checking for the hashtag with most tweets
for (i = 1, n = E.size(), popular = 0; i < n; i++) {
if (E[i].pop > E[popular].pop)
popular = i;
}
return E[popular].hashtag;

}

void Trendtracker::top_three_trends(vector<string> &T)

{

T.clear();
//Clears the vector for further use
if (size() == 0)
return;
//Returns if trends are empty
int n = E.size();
Entry dummy = { "", -1 };
E.push_back(dummy);
//Create a dummy entry with a

//Create a dummy entry with a negative value and assume its the largest
//first, second and third point to it

int i, j, first, second, third;
for (i = 0, first = second = third = n; i < n; i++) {
if (E[i].pop > E[first].pop) {
third = second;
second = first;
first = i;
}
else if (E[i].pop > E[second].pop) {
third = second;
second = i;
}
else if (E[i].pop > E[third].pop) {
third = i;
}
}

T.push_back(E[first].hashtag);
if (second != n && second != first)
T.push_back(E[second].hashtag);
if (third != n && third != second)
T.push_back(E[third].hashtag);
//Check if the pointers still point to the dummy variable
//insert only if it doesn't
E.pop_back();

}

public:
// Creates a new Trendtracker tracking no hashtags.
//
// Must run in O(1) time.
Trendtracker();

// Inserts a hashtag (tweeted 0 times) into the Trendtracker.
// If the hashtag already is in Trendtracker, does nothing.
//
// Must run in O(n) time.
void insert(string ht);

// Return the number of hashtags in the Trendtracker.
//
// Must run in O(1) time.
int size();

// Adds 1 to the total number times a hashtag has been tweeted.
// If the hashtag does not exist in TrendTracker, does nothing.
//
// Must run in O(n) time.
void tweeted(string ht);

// Returns the number of times a hashtag has been tweeted.
// If the hashtag does not exist in Trendtracker, returns -1.
//
// Must run in O(n) time.
int popularity(string name);

// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
//
// Must run in O(n) time.
string top_trend();

// Fills the provided vector with the 3 most-tweeted hashtags,
// in order from most-tweeted to least-tweeted.
//
// If there are fewer than 3 hashtags, then the vector is filled
// with all hashtags (in most-tweeted to least-tweeted order).
//
// Must run in O(n) time.
void top_three_trends(vector<string> &T);

private:
// A simple class representing a hashtag and
// the number of times it has been tweeted.
class Entry
{
public:
string hashtag;
int pop;
};

// END TRENDTRACKER.CPP
4) Now we need to write a function in TRENDTASKER.H that after the excution of the program is done it will print "Assignment Complete."
5) First will be writing the TRENDTASKER.H code:
//TRENDTRACKER.H

#ifndef TRENDTRACKER_H
#define TRENDTRACKER_H

#include
#include
#include
#include

using namespace std;

class Trendtracker
{
// For the mandatory running times below:
// n is the number of hashtags in the Trendtracker.

public:
// Creates a Trendtracker containing hashtags
// found in the provided file.
// The file is promised to have the following format:
//
// string1
// string2
// ...
// stringN
//
// where string1 < string2 < ... < stringN
//
// Must run in O(n) time.
Trendtracker(string filename);

// Return the number of hashtags in the Trendtracker.
//
// Must run in O(1) time.
int size();

// Adds 1 to the total number times a hashtag has been tweeted.
// If the hashtag does not exist in TrendTracker, does nothing.
//
// Must run in O(log(n)) time.
void tweeted(string ht);

// Returns the number of times a hashtag has been tweeted.
// If the hashtag does not exist in Trendtracker, returns -1.
//
// Must run in O(log(n)) time.
int popularity(string name);

// Returns a most-tweeted hashtag.
// If the Trendtracker has no hashtags, returns "".
//
// Must run in O(1) time.
string top_trend();

// Fills the provided vector with the 3 most-tweeted hashtags,
// in order from most-tweeted to least-tweeted.
//
// If there are fewer than 3 hashtags, then the vector is filled
// with all hashtags (in most-tweeted to least-tweeted order).
//
// Must run in O(1) time.
void top_three_trends(vector &T);

private:
// A simple class representing a hashtag and
// the number of times it has been tweeted.
class Entry
{
public:
string hashtag;
int pop;
};

// Optional helper method.
// Returns the index of E containing an Entry with hashtag ht.
// If no such hashtag is found, returns -1.
//
// Should run in O(log(n)).
int search(string ht);

// Entries sorted (lexicographically) by hashtag.
vector E;

// Stores indices of the (up to) three most-tweeted
// entries in E.
vector S;
};

#endif

// END TRENDTRACKER.H
6) and the function for printing printing "Assignment Complete."
#include <iostream>

int main()
{
std::cout << "Assignment Complete." << std::endl;
return 0;
}

Navigate

My Question is as following: Forty-two percent of a corporation’s blue-collar em

My Question is the yield on MBS is lower than Treasury bonds, isn\'t it buy low

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

My Question is how would i make the function run at O(log(n)) time. would i need

Question

Explanation / Answer

Related Questions

Navigate