Read carefully and answer the questions that follow: Suppose we want to create a

Question

Read carefully and answer the questions that follow:

Suppose we want to create an address book which contains names, phone numbers, emails, and other personal information. In the question below, give support to your answer based on the typical operations (for example, finding a person by his/her email) you might use. Explain why the algorithm and/or data structure you use gives a good tradeoff between memory use and runtime complexity. The question below could require nested data structures.

Suppose you know which of the people in you address book are friends which each other. Now suppose you take yourself out of the graph. Which algorithm(s) and data structure(s) would help you determine the number of unrelated groups of friends you have? Give reasoning for your answer.

Explanation / Answer

In this case, graph is the best possible data structure. Each node represents an individual. Each individual has a set of links that are connected to other individuals who know each oher.

When I take myself out, the problem of finding the number of unrelated group of friends reduces to the problem of finding the number of disjoint connected components in the graph. The best algorithm to find it is DFS or BFS. Let us consider DFS (Depth first Search) here.

Algorithm findComponents(Graph g)
Start
Initialize all vertices in g as not visited.
Do following for every vertex 'v'.
If 'v' is not visited before, call visit(v,{empty})
End
     
Algorithm visit(v,C)
Start
Mark 'v' as visited.
Add 'v' to C
Do following for every adjacent 'u' of 'v'.
If 'u' is not visited, then recursively call visit(u)

Output C
End

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.