hw5.txt

Name: Kyle Holzinger
BUID: U92663004
Date: 11.13.14

Problem 1

The first thing to do is to calculate the number of vertices and edges in graph G. Then, using the Floyd Warshall algorithm with a few minor changes, that is to say you still read from K=0 to K = N, given the following changes it now computes the number of different paths between each pair of vertices:

1. Make a list of counters for each pair of vertices
2. Run the original Floyd Warshall algorithm, however now you  keep track of the start and end vertices. For each path discovered, add 1 to that counter.
3. Given that we know the number of verticves in G, when any path's length gets to greater than the total number of vertices, there is definitely an infinite cycle because you can't have the number of edges go over the number of vertices without a cycle.
4. To get the number of paths between two vertices, look at the counter associated with that pair.


Problem 2

M1      M2      M3      M4      M5
R1  R2  R2  R3  R3  R4  R4  R5  R5  R6
4   10  10  5   5   30  30  6   6   11

Initial Analysis:
C(1,2) = 4*10*5 = 200
C(2,3) = 10*5*30 = 1500
C(3,4) = 5*30*6 = 900
C(4,5) = 30*6*11 = 1980

C(i, j) = min(C(i, k) + C(k+1, j) + (Ri*R(k+1)*R(j+1)
C(i, i+2)
C(1, 3) = min(C(1, k) + C(k+1, 3) + (R1*R(k+1)*R4)
k = 1 or 2
k = 1: C(1, 3) = min(C(1, 1) + C(2, 3) + (4*10*30) = 0 + 1500 + 1200 = 2700
k = 2: C(1, 3) = min(C(1, 2) + C(3, 3) + (4*5*30) = 200 + 0 + 600 = 800
min is C(1,3) = 800 when k=2

...

C(i, i+4)
C(1, 5) = min(C(1, k) + C(k+1, 5) + (R1*R(k+1)*R6)
k = 1, 2, 3 or 4
k = 1: C(1, 5) = min(C(1, 1) + C(2, 5) + (4*10*11) = 0 + 1780 + 440 = 2220
k = 2: C(1, 5) = min(C(1, 2) + C(3, 5) + (4*5*11) = 200 + 1230 + 220 = 1650
k = 3: C(1, 5) = min(C(1, 3) + C(4, 5) + (4*30*11) = 800 + 1980 + 1320 = 4100
k = 4: C(1, 5) = min(C(1, 4) + C(5, 5) + (4*6*11) = 1220 + 0 + 264 = 1484
min is C(1, 5) = 1484 when k = 4

((M1*M2)(M3*M4))(M5) = 1484 multiplications

CHECKING ANSWER:
M1*M2 = 4*10*5 = 200; yields 4x5 matrix
M3*M4 = 5*30*6 = 900; yields 5x6 matrix
(M1*M2)(M3*M4) = 4*5*6 = 120; yields 4x6 matrix
(M1*M2)(M3*M4)(M5) = 4*6*11 = 264; yields 4x11 matrix
200 + 900 = 1100 + 120 = 1220 + 264 = 1484 Multiplications

Problem 3
Prove that P(n) is Omega(2^n) (big omega)

Table of P(n)

n   P(n)        2^n
1   1       <    2
2   1       <    4
3   2       <    8
4   5       <    16
5   14      <    32 
6   42      <    64
7   132     >    128
8   429     >    256
9   1430    >    512
10  4862    >    1024

As is evident from this table, the P(n) function (after n = 6) is greater than 2^n.

Problem 4

The greedy approach to this is the following:

Look at the coins in order from largest too smallest.
For each coin, if the input value n is greater than the current value of coin C, you set the count of the current coin to n // C and subtract (n // C) * C where // is integer division.

Proof that this yields the optimal solution (It does not)

Proof by Contradiction
Say after running our algorithm, we have a list of (c1, c2, c3…..cm), where each c represents one of the 4 types of coins, and the sum of all the c’s add up to n (amount of change). We consider this to be our optimal solution. If we remove c1, we have the remainder of the list left, which is equal to n minus the value of c1. If the remainder of our list (c2...cm) is not the optimal solution to this problem, then that means there is another list of coins that is the optimal solution. The number of coins in that list must then be less than the number of coins in our list (c2...cm). If that solution were to be the better one, then adding c1 to that list would also give us a better solution. This would then contradict our statement about (c1, c2...cm) being the optimal solution. 
We can also swap any coin in our list with another in the same list, knowing that it would still add up to n and yield an optimal solution. If we remove one coin (A) with the highest value from the list, then that means we have to replace that coin with at least two coins (B1, B2…) that have a lower value. Since it takes at least two coins to replace the coin that was previously removed, then the list that has A in it would be the better solution since it yields less coins. This means that solution with A in it would be the optimal solution.