Group Project. Imagine that there are n students in CMPSC 465, ranked from 1 to n...

Transcribed Image Text:

Group Project. Imagine that there are n students in CMPSC 465, ranked from 1 to n by how comfortable they are with the course material, with 1 being the most comfortable. For the sake of this problem, a project has just been assigned that may be completed in pairs. Every student has a set of friends in the class, though these friendships may not be reciprocal. To maximize their odds of getting a good grade on the project, each student leverages their social network to find a friend of a friend of a friend (and so on) who is doing well in the course. When looking for a partner, the person with the best rank in each student's social network will be their first pick, regardless of any other students who share the same first pick. Note that students are in their own social network and that students may work alone, which is represented by being their own first pick. Your goal is to write an algorithm that, for every student, computes who their first pick will be. You may identify each student by their distinct ranking number. (a) Model this as a graph problem: give a precise definition of the graph involved. For each student, what question do you need to answer about your graph to find their first pick? (b) Give an algorithm that computes every student's first pick in O(V+E). Store the computed values in an array first-pick, where first pick[j] = i means student j's first pick is student i. (Hint: Consider the reverse graph of the graph you gave in part (a).) Group Project. Imagine that there are n students in CMPSC 465, ranked from 1 to n by how comfortable they are with the course material, with 1 being the most comfortable. For the sake of this problem, a project has just been assigned that may be completed in pairs. Every student has a set of friends in the class, though these friendships may not be reciprocal. To maximize their odds of getting a good grade on the project, each student leverages their social network to find a friend of a friend of a friend (and so on) who is doing well in the course. When looking for a partner, the person with the best rank in each student's social network will be their first pick, regardless of any other students who share the same first pick. Note that students are in their own social network and that students may work alone, which is represented by being their own first pick. Your goal is to write an algorithm that, for every student, computes who their first pick will be. You may identify each student by their distinct ranking number. (a) Model this as a graph problem: give a precise definition of the graph involved. For each student, what question do you need to answer about your graph to find their first pick? (b) Give an algorithm that computes every student's first pick in O(V+E). Store the computed values in an array first-pick, where first pick[j] = i means student j's first pick is student i. (Hint: Consider the reverse graph of the graph you gave in part (a).)

Answer rating: 100% (QA)

a Graph Definition The graph can be represented as an undirected graph GV E where V is the set of vertices representing students labeled from 1 to n E ... View the full answer