1. Consider a very large class of students. The instructor wants to help student
ID: 3823196 • Letter: 1
Question
1. 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.
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.