Algorithms/Dynamic Programming

Notes

Skiena Chapter 8

Fibonacci dynamic programming example

Skiena begins the chapter with the Fibonacci example.

Worst way to do Fibonacci calculation: using recursion

More efficient way to do Fibonacci calculation: cache the intermediate results

Most efficient way: specify the order of evaluation in such a way that the results that are needed are always available. No caching necessary. It's a bit trivial once you reach this point, but it is still dynamic programming - you're just specifying the order in which to evaluate the sub-problems so that you always have the information you need.

Binomial dynamic programming example

Skiena uses the binomial coefficient as an example of a problem with a single expression that can be evaluated, but that single expression will cause integer overflow.

Instead: use identity,

$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $

and the base cases:

$ \binom{p}{0} = 1 $

$ \binom{p}{1} = p $

$ \binom{p}{p} = 1 $

To implement this, we can build a table/array, which will contain Pascal's triangle...

Left column: m, top column: n

Now the order of operations is to fill in the edges of Pascal's triangle (the base cases) first

• Initialize column 0 = 1
• Initialize diagonal = 1

Now loop over each row and each column of the row to compute the binomial coefficient:

for i = 1 to n:
    for j = 1 to i:
        calculate binomial coefficient

Fuzzy string matching dynamic programming example

The next example Skiena covers is an important one: fuzzy string matching.

We are trying to pattern-match the string P in a larger text T.

To do approximate string matching, we must begin with a cost function. The cost function assigns a cost to each possible modification of our original string.

3 classes of edits:

• Substitution (turning one letter into another)
• Insertion
• Deletion

To find the minimum cost function to turn our pattern P into something in the original text T, we need to work backwards: from the ending point, work backwards 1 edit at a time.

Maintain a table:

• D(i,j) is the distance (the number of differences) between P1, P2, ..., Pi and the segment of T ending at j
• D(i,j) is the minimum of the three possible ways to extend the current string
• In other words, it is the minimum of the following:

Substitution: if $ P_i = T_j $ then $ D(i-1, j-1) $, otherwise $ D(i-1, j-1) + 1 $

Insert: $ D(i-1, j) + 1 $

Delete: $ D(i, j-1) + 1 $

Pseudocode for program:

# Non-Dynamic Programming Version of Fuzzy String Matching
def string_compare(s, t, i, j):

	# Base case
	if i==0 or j==0:
		return 

	# Option: Match
	match = string_compare(s, t, i-1, j-1) + match(s[i], t[j])

	# Option: Insert
	insert = string_compare(s, t, i, j-1) + insertdelete(t[j])

	# Option: Delete
	delete = string_compare(s, t, i-1, j) + insertdelete(s[i])

	# Pick minimum of these
	return min(match, insert, delete)

Skiena next presents a program that does hits... and says it is horribly inefficient. Why? Because it does not MEMOIZE! This means that it is repeating the same tasks over and over again

Resources

MIT Open Courseware 6.006

Links to Videos

Dynamic programming 1: Fibonacci, shortest paths: https://www.youtube.com/watch?v=OQ5jsbhAv_M

Dynamic programming 2: Blackjack: https://www.youtube.com/watch?v=ENyox7kNKeY

Dynamic programming 3: Parenthesization, edit distance, knapsack: https://www.youtube.com/watch?v=ocZMDMZwhCY

Dynamic programming 4: guitars, tetris, super mario: https://www.youtube.com/watch?v=tp4_UXaVyx8

MIT Open Courseware 6.046

Links to Videos

The topic of dynamic programming is covered in the MIT 6.046 open courseware playlist: https://www.youtube.com/watch?v=2P-yW7LQr08&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

The course begins with dynamic programming, by covering the divide and conquer approach for finding a convex hull: https://www.youtube.com/watch?v=EzeYI7p9MjU&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=2

It continues with a divide and conquer approach for matrix algebra and Fast Fourier Transforms: https://www.youtube.com/watch?v=iTMn0Kt18tg&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=4

It then covers divide and conquer for van Emde Boas trees: https://www.youtube.com/watch?v=hmReJCupbNU&index=6&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

Recitation with more dynamic programming examples: https://www.youtube.com/watch?v=krZI60lKPek&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp&index=12

Advanced dynamic programming: https://www.youtube.com/watch?v=Tw1k46ywN6E&index=14&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp

Dynamic programming for all pairs, shortest paths: https://www.youtube.com/watch?v=NzgFUwOaoIw&index=15&list=PLUl4u3cNGP6317WaSNfmCvGym2ucw3oGp