Description
This project will extend the midterm project to further analyze the Twitter data. For this application responsiveness is very important,
so runtime should be minimized even at the expense of increased memory usage. This is a common situation in real-world applications.
Specifically, you need to create two new methods: Collection getFollowing(TwitterUser user) TwitterUser getByPopularity(int x)
In the midterm you read in a data file (social_network.edgelist) that indicated whom a user is following. The getFollowing method should
do the reverse — it should return a collection of the people who are following the user. The object that you return can be any type of
Java Collection that we have studied: list, queue, set, map, etc. Choose whichever is most appropriate. The getByPopularity method should
return the xth TwitterUser (starting from zero) when the users have been sorted by the following criteria:
Number of followers (largest to smallest)
If two users have the same number of followers, sort by the number of people that user is following (largest to smallest)
If two users have the same number of followers and are following the same number of people, sort by user id (smallest to largest)
Note that since user id is unique, these criteria impose a total rather than partial ordering on the TwitterUser objects (in other words,
there will never be any “ties”). The time complexity of both of these methods must be constant, i.e. O(1). In order to achieve this, you
will likely need to create additional data structures in the TwitterUser class, the driver program, or both. Keep in mind that it is ok
if reading in the data files and initializing all of the TwitterUser objects is slow (within reason). It is also fine if these objects
take up a lot of space in memory, as long as the program can execute on a standard desktop computer. For each method, write a comment (in your
code, right before the method implementations) that describes the changes you have made to your project since the midterm in order to implement
the method. Additionally, modify your driver program to test the operation of the two new methods.
You will be graded according to the following requirements:
• The getFollowing method returns the correct results
• The getFollowing method has a constant time complexity
• The comment explaining the getFollowing method is complete and clearly written
• The getByPopularity method returns the correct results
• The getByPopularity method has a constant time complexity
• The comment explaining the getByPopularity method is complete and clearly written
• The driver program tests the execution of both methods
• The program compiles
• The program runs
• The program is clearly written and follows standard coding conventions
