CS330 HW04

Problem 2 §

function VC(v)
	# including v
	in = 1
	for child c of v:
		in += min(c.in, c.ex)
	
	# not including v
	ex = 0
	for child c of v:
		ex += c.in
		
	v.in = in
	v.ex = ex
	
	return min(v.in, v.ex)

• Base case: for a leaf node leaf, leaf.in = 1, leaf.ex = 0
• IH: for node v with leaves u1..uk, assume ui.in, ui.ex is correct
• IS: for node v,
  • Case including: VC including v does not require u1..uk to be included, but including it may be more minimal. IH guarantees ui.in, ui.ex is correct so take the minimum
  • Case excluding: VC excluding v requires all of u1..uk to be included, so in that case sum all the ui.in values to guarantee counting all cases where children are included
• Time complexity: $T(n)\le \text{\#children}\cdot T\left(\frac{n}{\text{\#children}}\right)+O(1)=O(n)$

Problem 3 §

def PalindromeDecomposition
 
	# memo[n][n] is a 2-d array whose value is all "N"
	
	# in increasing order of gap
	for gap=1..n
		for i=0..n-gap-1
			j = i + gap
			
			# base case
			if i==j
				memo[i][j] = Y
				continue
				
			# if edges are same, check the inner
			if A[i] == A[j]
				if memo[i+1][j-1] == Y
					memo[i][j] == Y
				else
					memo[i][j] == N
					
			# if edges are diff, not palindrome
			else A[i] != A[j]
				memo[i][j] == N
	
	# memo_count[n][n] is a 2-d array whose value is all 0.
	
	# in increasing order of gap
	for gap=1..n
		for i=0..n-gap-1
			j = i + gap
			
			# if the whole length i-j is palindrome, 1
			if memo[i][j] == Y
				memo_count[i][j] = 1
				
			# if the whole length isn't palindromic...
			minPcount = +infty
			for k=0..j-i:
				# get the minimum palindrome split of all possible splits
				min(minPcount, memo[i][i+k-1] + memo[i+k][j])
			memo_count[i][j] = minPcount
	
	return memo_count[0][n]
 

• Part 1:

  • Base case: a length-1 string is a palindrome
  • IH1: substring $A[i+1][j-1]$ is a palindrome
    • IS1: then if $A[i]=A[j]$, the string $A[i][j]$ is a palindrome
  • IH2: substring $A[i+1][j-1]$ is not a palindrome
    • IS2: then the string $A[i][j]$ cannot be a palindrome

• Part 2:

  • Base case: If the string $A[i][j]$ is a palindrome, then it is the minimum palindromic split of count 1
  • IH: palindromic substring count has been computed correctly from all proper substrings of $A[i][j]$
  • IS: the minimum palindromic substring if $A[i][j]$ is the minimum of the sums $A[i][i+k-1]+A[i+k][j]$ for $k\in [i,j]$

• Thus proved

• Part 1 span: $O(n^2)$ as filling a 2-d array with $O(1)$ calculation per subarray

• Part 2 span: $O(n^3)$ as filling a 2-d array with $O(n)$ calculation per subarray

• ⇒ Total time complexity: $O(n^3)$