Description
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 millions of users1 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).
#ads
2
vector S vector E 4 1 5
#gig
2
#hot
1
#dog
0
#cat
4
#fad
6
#big
8
#egg
9
string hashtag 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 hashtags.3
6. A text file (tweeted.txt) containing 1500000 hashtags.4
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 provided files compile into a program that runs with no failed tests. Submit the source file trendtracker.cpp.
3 Submission and Grading
Submit the aforementioned source file(s) via Blackboard as attached file(s). In the case of multiple submissions, the last submission before the deadline is graded.
For grading, each submission is compiled with the provided files and run. Submissions that do not run
to completion (i.e. fail to print “Assignment complete.”) receive no credit. Submissions that take an
1https://techcrunch.com/2017/06/27/facebook-2-billion-users/
2http://iswc2010.semanticweb.org/pdf/352.pdf
3Source: http://norvig.com/ngrams/count_1w.txt.
4Source: http://norvig.com/ngrams/count_1w.txt.
1
unreasonable amount of time (e.g. more than a minute or so) to run and do not meet the asymptotic
efficiency requirements receive no credit. All other submissions receive full credit.
See the course late work policy for information about receiving partial credit for late submissions.
2