3. [10] A bunch of UTM students, who were good friends of each other, went out f
ID: 3728153 • Letter: 3
Question
3. [10] A bunch of UTM students, who were good friends of each other, went out for a trip to Niagara Falls together, long story short, something happened and some of them stopped being friends and don't want to see each other ever again. After getting back to UTM, they realize that there is a money problem they need to solve: They haven't yet split the cost incurred in the trip evenly. Some of them spent more than they should and therefore are owed some amount of money, while some others spent less than they should and therefore owe some amount of money. This and wouldn't have been a problem if everybody could still talk to each other. But now since some of them are no longer friends, it might be impossible for everyone to even out the money You, as an outsider and a CSC263 trained computer scientist, want to help out, so you ask each person to tell you how much money she owes or is owed, and with whom she is still friends. Given this information, you will figure out whether it's possible for everyone to get even, with money only being given between persons who are still friends The input for your algorithm consists of two lists owing and friendship. The length of the list owing is the total number of students: owing [i] is the amount that student i is owing (0Explanation / Answer
The list of friendships (pair(i,j)) can be considered to be a bi-directional graph. with i and j having an edge. Consider the pairs (i,j) and (j,k). Now in this case, if i owes money to k then he can communicate to k and collect it. Meaning if in a graph k is reachable from i and k owes money to i then the problem can be solved.
PSEUDOCODE
Given list Friendships and list Owing
not_reachable[n][n] = {} // n is the number of studnets
for friend in Friendships:
{
for j in owing
{
if i != j and BFS(i,j)==false // Assumes a breadth first search that returns true if reachable and false otherwise
not_reachable[i].append(j)
}
}
for i in not_reachable
for j in not_reachable[i]
if j in owing[i]
return false
return true.
RUNTIME ANALYSIS
We are checking if all friends are either connected to others or don't owe anything to each other.
Consider a graph with n nodes (owning size) and m edges (friednship size)
Runtime complexity is O(n+m)2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.