Latest DATA STRUCTURE Aptitude Question SOLUTION: You are planning the group seating arrangement for a open book test given a list of students, V from different schools to participate. Assuming the fact that students who are known

• Placement Papers
• /
• DATA STRUCTURE
• /
• Programming
• /
• Technical

DATA STRUCTURE Question Papers:

(#M40151839) DATA STRUCTURE Programming question Keep an EYE

You are planning the group seating arrangement for a open book test given a list of students, V from different schools to participate. Assuming the fact that students who are known to each other directly or indirectly will probably cheat more as compared to unknown people sitting together.
Suppose you are also given a lookup table T where T[u] for u ? V is a list of students that u knows. If u knows v, then v knows u. You are required to arrange the seating such that any student at a table doesn't knows any other student sitting at the same table either directly or through some other student sitting at the same table. For example, if x knows y, and y knows z, then x, y, z can sit at the same table. Describe an efficient algorithm that, given V and T, returns the minimum number of tables needed to achieve this requirement. Analyze the running time of your algorithm.

Asked In DATA STRUCTURE aditi yadav (9 years ago)

Unsolved Read Solution (1)

Is this Puzzle helpful?   (8)   (3) Submit Your Solution Technical

Read Solution (1) :

Kostav Chaudhuri  (9 years ago)

We can construct an undirected graph G = (V, E) with guests as vertices,
and an edge between two vertices means the two guests know each other. Table T
represents the adjacency lists for the vertices. Two guests can sit at the same table if
there is a path between them. If we start from one vertex s and search the graph using
breadth-first search (BFS) or depth-first search (DFS), all the guests that are reachable
from s can sit at the same table, and additional tables are needed for vertices that are
unreachable from s.
Hence, to find the minimum number of tables, we can iterate through s ∈ V . If
s is not visited, increment the number of tables needed and call DFS-VISIT(s, T)
or BFS(s, T), marking vertices as visited during the traversal. Return the number
of tables needed after iterating through all the vertices. This problem is equivalent to
finding the number of connected components in the graph. The running time is Θ(V +
E) because every vertex or edge is visted exactly once. Below is the pseudocode.
NUM-TABLES(V, T)
1 visited = {}
2 n = 0
3 for s ∈ V
4 if s ∈/ visited
5 n = n + 1
6 add s to visited
7 DFS-VISIT(s, T, visitied)
8 return n
DFS-VISIT(u, T, visitied)
1 for v ∈ T[u]
2 if v ∈/ visited
3 add v to visited
4 DFS-VISIT(v, T, visited)

Is this solution Helpfull? Yes | No   

Please Login to Read Solution.