Homework 6 Solution

$30.00

Category: Tag:

Description

When a user searches for a person (\target”) on an online social network, the user might want to be a friend of the tar-get, but the user is not currently a friend of the target. For example, a user would like Donald Trump to be his/her friend, but the user is not a friend of Donald Trump. How would you design a system to help the user?

HW6 explores graph algorithms that can help the user nds mutual friends or \intermediate” friends of the user and the target. A mutual friend is someone who is both a friend of the user and the target. For example, if areFriends(user, Mickey) and areFriends(Mickey, target), Mickey is a mutual friend. An intermediate friend is someone who is a friend of the user and is indirectly connected to the target in the social network. For example, if areFriends(user, Mickey), areFriends(Mickey, x), areFriends(x, y), …, and areFriends(z, target), Mickey is an intermediate friend. Naturally, we also desire the intermediate friend who is closet to the target. The user can ask the mu-tual or intermediate friend to introduce the user to the target. Moreover, users can add friendships 🙂 and remove friendships :-(.

To nd mutual or intermediate friends, we can use the breadth- rst search algorithm. The algorithm allows us to nd the shortest path from the user to the target. If the path is of length 2, a mutual friend exists. If the path length is more than 2, an intermediate friend exists. Note that multiple paths of the same length might exist and a path might not exist at all. If at least one shortest path exists, the system will report the shortest path(s) and the mutual/intermediate friend(s).

Friends (adjacent vertices) are visited in alphabetical or-der (to produce unique output for easier testing/debugging). We will be evaluating your submission on code01. t.edu; we strongly recommend you to ensure that your submission func-tions properly on code01. t.edu.

Extra Credit 1 (10 points) Separate submission via hw6extra1.c (or HW6Extra1.java). Similar to regular credit, except if ties exist, multiple shortest paths are reported (in the order when adjacent vertices are visited alphabetically).

Extra Credit 2 (10 points) Separate submission via hw6extra2.c (or HW6Extra2.java). Not all friendships are equally close. Closer friendships are more desirable in nd-ing the target. To estimate how close a friendship is, we can measure the frequency of communication (e.g. texts, email, calls, …) between two users. Frequency of communication in HW6 is the average number of days between two successive communications and is an integer (for simplicity). Using Di-jkstra’s shortest path algorithm, we can nd the mutual or intermediate friend on the shortest path from the user to the target. Similar to regular credit, report the rst shortest path found|adjacent vertices are visited alphabetically.

Extra Credit 3 (10 points) Separate submission via hw6extra3.c (or HW6Extra3.java). Similar to Extra Credit 1, except if ties exist, multiple shortest paths are reported (in the order when adjacent vertices are visited alphabetically).

Input: Command-line argument for hw6.c (HW6.java) [and

Extra Credit] is:

lename of initial friendships|the rst line has the num-ber of users, each of the following lines has two users who are friends (followed by frequency of communcation for Extra Credits 2 and 3)

lename of actions|possible actions (each on one line) are:

{ AddFriendship user1 user2 [frequency in Extra Credits 2 and 3]

{ RemoveFriendship user1 user2 { WantToBefriend user target

For simplicity, all the users are in the initial friendships and the number of users does not change during the actions. As-sume users are valid in the actions.

Output: Output goes to the standard output (screen):

  1. AddFriendship user1 user2 (frequency in Extra Credit) [ExistingF riendshipError]

  1. RemoveFriendship user1 user2 [NoF riendshipError]

  1. WantToBefriend user target [AlreadyAF riendError]

    • Length of the shortest path: k

    • Your mutual=intermediate friend is x.

    • Path: user x y … z target

or

  • Sorry, none of your friends can help introduce you to target.

Extra Credit 1: Only WantToBefriend is di erent with possibly additional mutual/intermediate friends and paths. The following 2 lines are repeated for each additional mu-tual/intermediate friend:

  • Your mutual=intermediate friend is x.

  • Path: user x y … z target

Extra Credits 2 and 3: Same as the corresponding output for Regular Credit and Extra Credit 1.

Sample intput and output les are on the course website.

Submission: Submit hw6.c (HW6.java) that has the main method and other program les. Submissions for Individual and GroupHelp have the same guidelines as HW1.

For Extra Credits, submit hw6extra1.c, hw6extra2.c, and/or hw6extra3.c (or HW6Extra1.java, HW6Extra2.java, and/or HW6extra3.java) that have the main method and other pro-gram les. GroupHelp and late submissions are not applicable.

Note the late penalty on the syllabus if you submit after the due date and time as speci ed at the top of the assignment.

1