(given there is not a forum yet for "discussion on final", I just continue posting here in the main forum)
one of the questions I got for Quiz-3 is as follows:
"
Question: Suppose we want to use graphs to solve the problem of assigning rooms for all of the final exams at Carnegie Mellon University. For simplicity, let's assume that all rooms have a capacity of 200 seats, and that no class on campus has an enrollment of more than 200 students.
We could make a graph in which each node represented the final exam of a specific course. For example, there would be a node for 15-211's final exam, for 21-127's final exam, and so on. Then, there would be an edge between two nodes if the final exams for those two classes were scheduled on overlapping times. So, for example, if 15-211's and 21-127's final exams were both scheduled for a Tuesday at 8:30am, then there would be an (undirected) edge connecting the nodes for those two courses.
Given this graph structure, how would you determine whether there are enough available rooms on campus to hold final exams?
Correct Answer: check if the degree of any node is greater than the number of available rooms
Feedback: If any nodes have degree greater than the number of available rooms, then there are more exams scheduled for a particular time then there are rooms available.
"
MY answer is: Check if there are more edges in the graph than the number of available rooms.(given that's what I think the best of the four choices there) though if I were able to write down the answer it'd be" check if there are more edges in the graph than the number of available rooms minus one"
Can someone tell me where I was wrong in choosing My answer rather than the Corrent answer ? I am not able to understand why I was wrong even after being told what's supposed to be correct
Thanks for any explanation or help!
Feedback: If any nodes have degree greater than the number of available rooms, then there are more exams scheduled for a particular time then there are rooms available.
|