magine a shopping mall, where the stores try to help each other out. Purchasing any item from one store means that you can choose one, and only one, coupon to another store, good for that day only. Of course, if you buy something from that other store, you can get a coupon for a third store, and so forth. Each coupon is for a different amount, so store X might give you a $5 off coupon for store Y, but store Y might give you a $10 off coupon for store X. Fortunately, they publish a list in advance, so you can plan your trip. Or you can have your computer figure it out for you.
For this assignment, write a program to figure out how to get the maximum savings for a set number of items. To keep things simple, assume that you need one item from each store, and that the price of each item is more than the coupon. To get the coupon amounts, you can use random values like
coupons = randi(100, N, N);
for N stores. Put zeros in the diagonals, or ignore them, since a store is not going to give a coupon for itself.
To make this clear, suppose that you have the following table. The left-most column is the "from" store, and the top-most row is the "to" store. For example, buying something at store w and means that you can collect a $5 coupon for store x.
One solution is to go from store w to z (+45), then from z to x (+51), then x to y (+10), for a total savings of $106.
Have your program count the number of comparisons that it does. You can simply increment a variable right before an "if" statement, though keep in mind that any functions that you call will also factor into this. For example, if you call a sort function, assume that it counts for N * log(N) comparisons every time it is called with N values. A min or max function requires N-1 comparisons.
Once you have this working, have it report the number of comparisons for 2 stores, 3 stores, 4 stores, and so forth, until you can establish the growth rate. When it goes from N to N+1 stores, how many more comparisons will it have to do?
