CS320								Nov 17, 2009

Tutorial #10:  Dynamic Programming - 1D
By David Buchman

These tutorial notes do not necessarily cover everything that was said in class.

Question 1:

Frequently the D.P. solution starts by first defining the solution recursively.  However, we need to find out over which dimension (or multiple dimensions).

Here - obvious choice is over n.
Define:  L[i]  =	true		if T[1...i] can be broken into valid words
			false		otherwise
Now, L[i] can be defined recursively:
	Base:	L[0] = true	Why?  __  [  It's a sequence of 0 legal words  ]
	Induction:	L[i]  = true  if'f  L[1...n] can be broken to 2 parts,
					L[1...j] and L[j+1...n], such that L[j]=true 
					and L[j+1...n] is a word.

The answer is therefore L[n].
Notice:  we just needed a single boolean value L[n], but in order to define it, we added a dimension to the problem...

Calculating L[n]:
L[0] <-- true
for i=1...n
	//Now calculate L[i]:
	L[i] <-- false
	for j = 0...i-1
		if  L[j]==true  and  T[j+1...i] is a word in the dictionary
			L[i] <-- true

Memory complexity:		_____  [  O(n)     ]
Time      complexity:		_____  [  O(n^2)  ]

Optimizations:

1. A 'break' statement...  
    We can change the algorithm by  	_____
    Does it reduce the time complexity?	_______________

2. Usually there is an upper limit on word length...
    We can change the algorithm by  	_____
    Does it reduce the time complexity?	_______________

Reconstruction

Assume we don't only want to know whether or not T[1...n] can be broken to a sequence of words, but we also want to find this sequence.
For simplicity, in case there are different possible sequences, we are interested in just finding any (arbitrary) one of them.
How can we modify our algorithm, to also find the sequence?

This is a relatively general question.
Given a DP algorithm that returns a result (in this case, whether or not a word sequence exists), how can we change it to return more relevant information about the solution.
Possibilities:
1. Calculate and store the required information for every i=1...n.
In this case, this requires storing a sequence of words for every i for which L[i]=true.
Memory requirement:    ____  [  O(n^2)  ]
	---> Inefficient

2. How can we improve on (1)?

The information we want for a specific i is a sequence of words, that is comprised of a sequence for some  j<i,  and the single word  T[j+1...i].
---> So we can just store j.
       The sequence will be generated by recursion:    
			return (  sequence for j & T[j+1...i]  )
Memory requirement:	____
  [  Still O(n), but with a larger constant - store an integer instead of a bit.  ]

Notice:  the information stored was actually produced by the DP algorithm for each i, but wasn't stored before.

	Calculate_L_and_J_arrays( T[1...n] ):
	L[0] <-- true
	J[0] <-- <undefined>			//Undefined - but will never be read
	for i=1...n
		//Now calculate L[i] & J[i]:
		L[i] <-- false
		J[i] <-- <undefined>		//Undefined - but will never be read
		for j = 0...i-1
			if  L[j]==true  and  T[j+1...i] is a word in the dictionary
				L[i] <-- true
				J[i] <-- j

It is also possible to omit L, and mark false entries in L with a specific flag value in J.

Find_Sequence( T[1...n], L[1...n], J[1...n] )	
	//Called after L[1...n] and J[1...n] were calculated
if L[n]==false
	return "No sequence exists"
else
	if n==0
		return {}		//Empty sequence
	else
		j = J[n]
		return  Find_Sequence( T[1...j], L[1...j] )  &  T[j+1...n]
//Notice:  parameter passing is O(1),
//	not O(j), because what is being passed 
//	is only the pointers to the arrays + the
//	index j.

3. Not store any additional information.
Instead of storing the j for every i (for which L[i]=true), we will rerun the relavant part of the DP algorithm for this specific i, to find j.

Find_Sequence( T[1...n], L[1...n] )	
	//Called after L[1...n] was calculated
if n==0
	return {}		//Empty sequence
else
	for j = 0...n-1
		if  L[j]==true  and  T[j+1...n] is a word in the dictionary
			return  Find_Sequence( T[1...j], L[1...j] )  &  T[j+1...n]
//Notice:  parameter passing is O(1),
//	not O(j), because what is being passed 
//	is only the pointers to the arrays + the
//	index j.
	return "No sequence exists"

Storage:  _____
Time:  O(n^2).  (But O(n) if word length is limited.)

Discussion
Assuming that the word length is limited, both (2) and (3) become O(n) time and O(n) storage.
In many practical situations for DP algorithms, the approaches of both (2) and (3) are practical alternatives.  
Both have identical (O(n) in this case) storage requirements and running times.  The difference is in the "constants":  (2) multiplies the storage by a constant, and (3) multiplies the running time by a constant.
In practical situations, the actual choice usually depends on the tradeoff for the specific problem.  

Question 2:

In this question, all coin values are positive integers.

Intuitive, greedy algorithm - take at every step the largest possible coin:

	Greedy_Coins( X, A ):		//X = (x1, x2, ..., xn)
					//Return value:  the set of coins (with repetitions).
	If A==0
		return {}		//Empty set of coins
	else
		if A < all coins x[i]'s
			return "impossible"
		else
			i <-- largest value x[i] such that  x[i] <= A
			return x[i] & Greedy_Coins( X, A-x[i] )
				//Takes largest possible coin, and recurses

"Solution" = a set (with repetitions) of coins, adding up to A.
	Example:  X={2,5} ---> no solution for A=3.
"Optimal solution" = a solution using the smallest number of coins.
Is this greedy algorithm optimal?	________
	[  No.  E.g.:  X={1,5,7}, A=10.  ]

If a solution exist, does the greedy algorithm guarantee to find a solution (optimal or not)?	________
	[  No.  E.g.  X={10,25}, A=30.  The greedy algorithm will use the 25 coin,
	   and then fail.  ]

How can we create the DP algorithm for the optimal solution?

We usually start by defining the optimal solution, recursively:

	Min_Num_Coins_R( X, A ):
	If A==0
		return 0		//0 coins needed
	else
		for i = all coins x[i] that are  x[i] <= A
			call  Min_Num_Coins_R( X, A-x[i] )
		if all calls returned "impossible" (or 0 possible coins x[i])
			return "impossible"
		else
			return 1 + min( non-impossible values returned by 
						recursive call )

What is the storage complexity of the recursive solution?
	[  Local variables:  O(1).  Only the minimal value is stored for the loop.
	   Stack:  up to O(A) memory!  ]
What is the time complexity of the recursive solution?
	[  Might be exponential in A.  E.g.  X={1,2}, A=1,000,000 -
	   time is roughly the  1,000,000th  Fibonacci number...  
	   = ~ 1.6 ^ 1,000,000
	   The base actually depends on the set of coins used.  ]

It is possible to store the solutions for the sub-problems in a cache, instead of recomputing them.

	Min_Num_Coins_R_Cache( X, A ):
	if cache[A] exists
		return cache[A]
	else
		If A==0
			cache[0] <-- 0
			return 0		//0 coins needed
		else
			for i = all coins x[i] that are  x[i] <= A
				call  Min_Num_Coins_R_Cache( X, A-x[i] )
			if all calls returned "impossible" (or 0 possible coins x[i])
				result <-- "impossible"
			else
				result <-- 1 + min( non-impossible values returned by 
								recursive call )
			cache[A] <- result
			return result

What is the time complexity of the recursive solution with the cache?
	[  O(nA).  Each calculation done at most once, and takes O(n) time.  ]

The DP algorithm is actually very similar to the cached recursive algorithm.
However, it assumes all results for 0...A will be calculated, so instead of implementing a recursion and testing whether or not the sub-problems were already calculated and stored inside the "cache", it loops on 0...A, makes all calculations and stores all results.
Under DP terminology, we no longer call this array a "cache".

	Min_Num_Coins_DP( X, A ):
	//Calculate N[0...A], N[i] represents the minimal #coins for i:
	N[0] <-- 0		//0 coins needed
	for a = 1...A
		for i = all coins x[i] that are  x[i] <= a
			check  N[ a-x[i] ]
		if all entries checked are "impossible" (or 0 possible coins x[i])
			N[a] <-- "impossible"
		else
			N[a] <-- 1 + min( non-impossible entries )
	return N[A]		//N[A] coins are needed for A.

This DP algorithm gives us the minimal #coins necessary.
Now we want to extend its output - and also receive the specific coin combination.
We can adopt the general approaches (2) or (3) from the previous question.

Approach (2):
Store the "decision" made by the algorithm for all values 1...A, at the same time N[0...A] is being calculated.
In this case, the "decision" is the coin used.

	Min_Num_Coins_DP( X, A ):
	......  Updated, to also store the coin choice in an array C[0...A].  ......

Find_Coins( N[...], C[...], A )	
	//Called after N[0...A] and C[0...A] were calculated.
if N[A] == "impossible"
	return "impossible"
else
	if A==0
		return {}		//0 coins
	else
		return  C[A]  &  Find_Coins( N[...], C[...], A-C[A] )

Approach (3):
C[0...A] isn't stored.
Each necessary value C[a] is recalculated:

Find_Coins( N[...], A )	
	//Called after N[0...A] was calculated.
if N[A] == "impossible"
	return "impossible"
else
	if A==0
		return {}		//0 coins
	else
			//Recalculate:
			for i = all coins x[i] that are  x[i] <= A
				check  N[ A-x[i] ]
			c <-- coin value x[i] with minimal  N[ A-x[i] ]  
					//(For non-impossible entries.)
					//Here, at least 1 entry is possible...  (why?)

		return  c  &  Find_Coins( N[...], A-c )