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
