Reference no: EM133309543

Just draw representation of the tasks and implement solution

You are going to use graphs to implement a roommate payment algorithm. The problem is that a group of N number of roommates all owe each other different amounts of money. Your first task is to create graph representation of the problem and print it out. The second task is to implement an algorithm that makes it so each roommate only has to pay one person. For example, if Roommate A owes Roommate B $10.00 and Roommate C $15.00, then Roommate A could pay $25.00 to Roommate B and Roommate B could pay $15.00 to Roommate C. This makes it so a roommate only has to make one transaction.

Remember to think about sources/sinks in the graph, whether or not the edges in this graph have weights, how cycles may impact the algorithm, and draw the problem and examples out.

Steps:

Draw a representation of the first task in the problem with different examples (make sure one has a cycle in it) to ensure you understand the problem (i.e., don't worry about solving the second part of the assignment)

Draw a representation of your approach to the second task with examples (make sure one has a cycle in it) to ensure you understand the problem and how to model a solution

Implement your solution to the problem.