Problem 1. You have managed to learn all friendship connections in the social network Basehook (Bh)....

Transcribed Image Text:

Problem 1. You have managed to learn all friendship connections in the social network Basehook (Bh). You want to forward a message from one person to another, but have observed that the impact of a message depends a lot on along how many connections it has to travel. You therefore want to compute the following: Given a sequence of friendship connections and specific persons A and B, determine the smallest k such that there is a sequence of persons Xo, X1, X2,..., Xk where A = Xo, B = Xk, and X₁ and X₁+1 are Bh-friends, for i = 0, 1, ..., k – 1. Describe briefly an efficient solution in words to this problem, using the concepts of this course, and give its time complexity. Problem 2. (Continued) You have studied this further and discovered that not all friendships are equal. Strong friendship connections are special, and using such friendship connections doesn't cost anything so to speak: the message can travel along arbitrarily many strong friend- ships connections without its impact becoming weaker. We call other connections weak. You want to compute the fewest number of weak friendship connections needed to route a message from given person A to person B (possibly using many strong connections). Problem 1. You have managed to learn all friendship connections in the social network Basehook (Bh). You want to forward a message from one person to another, but have observed that the impact of a message depends a lot on along how many connections it has to travel. You therefore want to compute the following: Given a sequence of friendship connections and specific persons A and B, determine the smallest k such that there is a sequence of persons Xo, X1, X2,..., Xk where A = Xo, B = Xk, and X₁ and X₁+1 are Bh-friends, for i = 0, 1, ..., k – 1. Describe briefly an efficient solution in words to this problem, using the concepts of this course, and give its time complexity. Problem 2. (Continued) You have studied this further and discovered that not all friendships are equal. Strong friendship connections are special, and using such friendship connections doesn't cost anything so to speak: the message can travel along arbitrarily many strong friend- ships connections without its impact becoming weaker. We call other connections weak. You want to compute the fewest number of weak friendship connections needed to route a message from given person A to person B (possibly using many strong connections).

Answer rating: 100% (QA)

The detailed answer for the above question is provided below ANswer Problem 1 This problem can be solved using a BreadthFirst Search BFS algorithm The BFS algorithm starts at the source node A and exp... View the full answer