Consider a very large class of students. The instructor wants to help students k
ID: 3832683 • Letter: C
Question
Consider a very large class of students. The instructor wants to help students know more people in the class, thus she decides to form x number of study groups. Each student identifies who s/he knows in the class. The instructor wants to use this information to create groups that maximize the number of people in each study group that don't know each other. Formulate this as a graph problem and write an algorithm for a reasonable solution. Please identify what a node represents, what an edge represents, whether it is directed or undirected, and weighted or unweighted. If it is directed and/or weighted, identify what that means in the context of the problem. Please add comments to your pseudocode so that we can follow the logic of your solution. The above approach was okay, but the instructor wants to get a little more sophisticated. She has the students again identify who s/he knows, but this time also characterize that relationship using a numbering system: 3:friend, 2:acquaintance, 1:know who they are, 0:no relation. Furthermore, she learned that two people who know each other sometimes rate their relationship differently (e.g. Vivek thinks of Fei as a friend but Fei thinks of Vivek as an acquaintance). The instructor also considers degrees-of-separation taking into account the type of relationship (e.g. friend or someone you know) and wants to pair people in a group who are seemingly the least likely to find a group of students that connects them (e.g. Leila does not know Issey but is friends with Jose, who is an acquaintance of Issey's, thus there is some degree of separation between Leila and Issey). The instructor wants to find those students who are least likely to find a connection, then distribute the first 10 pair she finds among the 10 study groups. Formulate this as a graph problem, create a heuristic to solve it, then write pseudocode to implement your heuristic. Please add comments to your code. At the end of the course, the instructor wants a measure of the success of these strategies. Establish a metric and a method to calculate it that reflects a kind of connectedness among students taking into account the isolation of any student (i.e. someone who identifies most relationships in the class as 0:no relation), which should create a strongly negative measure and the ultimate success (i.e. everyone in the class is friends with everyone else).
Explanation / Answer
Lets assume each student is equivalent to a node in a graph and the edges between two nodes will be there if they know each other. It is undirected graph without having any weight.
So, now we need to find the number of groups required to put the student such that in each group no students know each other. This is a similar problem of minimum number of color required to color a graph.
Example:
say there are 6 students in the class..roll no 1 knows 2, 2 knows 3,4,5 and 4 knows 5,7.
so if we construct the graph it will look like
3
|
|
1 --- 2
/
5 --- 4 ---- 7
There will be 2 group :
Group 1 : 2,7
Group 2: 1,3,4,5
Place 2 in one group and its adjacent in different group, then place 7 in the same group of 2.
Algortihm looks like greedy method.
1. Assign the 1st node in one group
2. for other nodes
assign it to a lowest number group such that all the adjacent nodes are not in the same group,if all the other groups are already assigned to adjacent vertices, assign a new group. It is kind of similar problem to graph coloring problem.