Table of Contents

Coin Collector: Problem Statement

Let's suppose you are a coin collector in a foreign country. They have a set of coins that you have never seen before. You find an ATM, but a sign above says you can only make one transaction. Luckily you are rich and can withdraw as much as you want.

The ATM gives change in the greedy algorithm we went over in class. How much should we withdraw to get the most variety of coins?

Coin Collector: Problem Statement

• Given find the withdraw amount which will maximize the variety of coins
  • will always be
  • Assume

Coin Collector: Greedy Choice

• What are some greedy choices we could make?

Coin Collector

• Picking the largest/smallest coin available!
  • But what does available mean?

Coin Collector: Code

• Now provide the algorithm for this question!

Coin Collector: Code

def withdraw_amount(C):
	p = [1]
	for c, i in enumerate(C[1:-1]):
		if sum(p) + c < C[i]:
			p.append(c)
	p.append(C[-1])
	return p

Coin Collector: Greedy Property

• Proving the greedy choice property

Frogger: Problem Statement

Frankie loves to sit on the stone with the most sun in the lake.
But the sun moves around throughout the day!
Frankie wants to know if she is strong enough to jump from stone to stone, such that she can reach any stone in the lake!

Frogger: Problem Statement

• Given find the maximum distance Frankie has to be able to jump in order to make it from any stone in the lake to any other stone

Frogger: Associations

• What algorithms may prove useful here?

Frogger: Floyd Warshall

• How does this algorithm help with our problem?

Frogger: Modifying Floyd Warshall

def floyd_warshall(W, n):
  D = [None] * (n + 1)
  D[0] = W
  for k in range(1, n + 1):
    D[k] = [[0] * n] * n # n x n
    for i in range(1, n + 1):
      for j in range(1, n + 1):
        D[k][i][j] = min(
          D[k - 1][i][j],
          D[k - 1][i][k] + D[k - 1][k][j]
        )

Frogger: Modifying Floyd Warshall

def floyd_warshall(W, n):
  D = [None] * (n + 1)
  D[0] = W
  for k in range(1, n + 1):
    D[k] = [[0] * n] * n # n x n
    for i in range(1, n + 1):
      for j in range(1, n + 1):
        D[k][i][j] = min(
          D[k - 1][i][j],
          max(D[k - 1][i][k], D[k - 1][k][j])
        )
	return max(D)

Frogger: Run Through