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.