COP 5536 Spring 2020 Programming Project Due Date: March 30th, 2020, 11:55 pm EST 1. General Problem description You are required to implement a system to find the n most popular hashtags that appear on social media such as Facebook or Twitter. For the scope of this project hashtags will be given from an input file. Basic idea for the implementation is to use a max priority structure to find out the most popular hashtags. You must use the following structures for the implementation. 1. Max Fibonacci heap: use to keep track of the frequencies of hashtags. 2. Hash table: The key for the hash table is the hashtag, and the value is the pointer to the corresponding node in the Fibonacci heap. You can assume there will be a large number of hashtags appearing in the stream and you need to perform increase key operation many times. Max Fibonacci heap is recommended because it has an amortized complexity of O(1) for the increase key operation. You should implement all Fibonacci heap functions discussed in class. For the hash table, you can use an implementation from any library that your programming languages supports (e.g., STL). Programming Environment You may implement this assignment in Java or C++. Your program must be compilable with the compilers and run on the following environment: – Java or g++/gcc on the thunder.cise.ufl.edu server You may access the server using Telnet or SSH client on thunder.cise.ufl.edu. You must write a makefile document which creates an executable file named hashtagcounter. 2. Input and Output Requirements Your program is required to take the input file name as an argument. The following is an example (at the command prompt ‘$’) of a program that reads from a file named file_name. $hashtagcounter file_name Input Format Hashtags appear one per line in the input file and start with # sign. After the hashtag an integer will appear and that is the count of the hashtag (There is a space between hashtag and the integer). You need to increment the hashtag frequency by that count. Queries will also appear in the input file and once a query appears you should append the answer to the query to the output file. A query appears as an integer number (n) without # sign in the beginning. The answer to the query n is n hashtags with the highest frequency. These should be written to the output file. An input line with the word “stop” (without hashtag symbol) causes the program to terminate. The following is an example of an input file. #saturday 5 #sunday 3 #saturday 10 #monday 2 #reading 4 #playing_games 2 #saturday 6 #sunday 8 #friday 2 #tuesday 2 #saturday 12 #sunday 11 #monday 6 3 #saturday 12 #monday 2 #stop 3 #playing 4 #reading 15 #drawing 3 #friday 12 #school 6 #class 5 5 stop Output Format For each query n, you need to write the n most popular hashtags (i.e., highest frequency) to the output file in descending order of frequency (ties may be broken arbitrarily). The output for a query should be a comma separated list occupying a single line in the output “output_file.txt”. There should be no space character after the commas. Following is the output file for the above input file. saturday,sunday,monday saturday,sunday,reading,friday,monday You can have following assumptions 1. No uppercase letters in the input stream 2. No spaces in the hashtags. (only one word per one hashtag) 3. One query has only one integer. 4. Query integer, n<=20. i.e. you need to find at most 20 popular hashtags. 5. Input file may consist of more than 1 million hashtags. 3. Submission The following contents are required for submission: 1.Makefile: Your make file must be directly under the zip folder and named “Makefile”. No nested directories. 2. Source Program: Provide comments. 3. REPORT: · The report should be in PDF format. · The report should contain your basic info: Name, UFID and UF Email account · Present function prototypes showing the structure of your programs. Include the structure of your program. To submit, please compress all your files together using a zip utility and submit to the c a n v a s system. You should look for Assignment Project for the submission. Your submission should be named LastName_FirstName.zip. Please make sure the name you provided is the same as the name that appears on the Canvas system. Please do not submit directly to a TA. All email submission will be ignored without further notification. Please note that the due date is a hard deadline. No late submission will be allowed. Any submission after the deadline will not be accepted. 4. Grading Policy Grading will be based on the correctness and efficiency of algorithms. Below are some details of the grading policy. Correct implementation and execution: 60% Comments and readability: 15% Report: 25% Note: If you do not follow the input/output or submission requirements above, at least 25% of your score will be deducted, and then more will be deducted for additional mistakes. If your code does not compile or run in thunder.cise.ufl.edu server, at least 25% of your score will be deducted, and more will be deducted for additional mistakes. In addition, we may ask you to demonstrate your projects. 5. Miscellaneous • Your implementation should be your own. You have to work by yourself for this assignment (discussion is allowed). Program code will be checked and you may have negative result if it has reasonable doubt.
