Lecture notes for Algorithm Design

Lecture Notes for Algorithm Design

Induction and Algorithm Design, 24 April 2000

a simple problem: show sum(i = 1 to n, i) = n(n + 1)/2
simple induction
1. if something is true for n, and also is true for n + 1, then it is true for all j >= n
2. the inductive hypothesis H(n) - n the parameter of the induction
3. the base case - show H(i) holds
4. the inductive step - assume H(j) is true for some j >= i and consider H(j + 1)
5. example
  1. show for all natural numbers x and n, xⁿ - 1 is divisible by x - 1
  2. hypothesis - H(n) = x - 1 div xⁿ - 1 for n = 0
  3. the inductive step - assume H(j) holds for some j >= 0 and consider H(j + 1)
6. can also assume H(j - 1) and show H(j), but be careful how you specify j.
the inductive approach to algorithm design
1. reduce the problem to a very simple form (base case)
2. show how to get the next solution by a small step from the previous solution (inductive step)
3. advantages
  1. both the base and inductive steps are simple, although it may be difficult to find simple base and inductive steps
  2. recursion, which can be unfolded if necessary (but that could be complex)
4. disadvantages
  1. divide and conquer is uneven, could lead to expensive algorithms

example - polynomial evaluation

evaluate P_n(x) = a_nxⁿ + a_{n - 1}x^{n - 1} + . . . + a₁x + a₀ for some x
first cut
1. hyp - H(n) = I can compute P_n(x)
2. bas - H(0) = a₀
3. ind - Suppose H(j) for j >= 0 and consider H(j + 1)
  1. I can compute P_j(x)
  2. I can compute a_{j + 1}x^{j + 1} + P_j(x)
  3. repeatedly exponentiating x is expensive
second cut
1. try a different, stronger, hypothesis
2. hyp - H(n) = I can compute P_n(x) and xⁿ
3. bas - H(0) = a₀ and x⁰ = 1
4. ind - Suppose H(j) for j >= 0 and consider H(j + 1)
  1. I can compute P_j(x) and x^j
  2. I can compute a_{j + 1}x^{j + 1} + P_j(x) and x^jx
  3. 2n multiplications

third cut

try a different order - instead of a_nxⁿ + (a_{n - 1}x^{n - 1} + . . . + a₁x) + a₀), use

	(a_nxⁿ + a_{n - 1}x^{n - 1} + . . . + a₁x) + a₀
=	x(a_nx^{n - 1} + a_{n - 1}x^{n - 2} + . . . + a₁) + a₀
=	x(x(a_nx^{n - 2} + a_{n - 1}x^{n - 3} + . . . + a₂) + a₁) + a₀

from this P_j(x) = sum(i = 0 to j, a_{n - i}x^{j - i})

hyp - H(j) = I can compute P_j(x)
bas - H(0) = P₀(x) = a_{n - 0}x^{0 - 0} = a_n
ind - Suppose H(j) for j >= 0 and consider

H(j + 1) = xP_{j - 1 + 1}(x) + a_{n - j + 1})

= xP_j(x) + a_{n - j + 1}
n multiplications - Horner's rule

example - induced subgraphs
1. a graph G, and induced subgraph of G
2. problem - find the largest k-degree induced subgraph of G.
3. solution - how about greed
  1. if a vertex of G has degree less than k, it cannot be in the induced subgraph
  2. greed works, but is the result exact; that is, is the result the largest possible k-degree induced subgraph; does order of removal make any difference
  3. hyp - H(n) = greed finds a largest k-degree induced subgraph of any graph with n vertices
  4. bas - H(i) for i <= k - there is no such largest, k-degree induced subgraph and greed removes all vertices
  5. bas - H(k + 1) - greed removes no vertices because the graph is complete or it removes all vertices otherwise
  6. ind - assume H(j) holds for j >= 0 and consider H(j + 1). Let G be a graph with j + 1 vertices. There are two cases to consider:
    1. If G has no vertices of degree less than k, G is the largest, k-degree induced subgraph and greed removes no vertices.
    2. If G has a vertex with degree less than k, greed will remove it. But then G is a graph with j vertices and, because H(j) is true, greed will find the largest, k-degree induced subgraph.
    In either case greed works on a j + 1 vertex graph and H(j + 1) holds
4. example - one-to-one mappings
  1. mapping a set onto itself
  2. one-to-one mappings
  3. find the largest subset containing a 1-1 mapping
  4. hyp - H(n) = can find maximal 1-1 mappings for n-element sets
  5. bas - H(1) is true
  6. ind - let H(j) be true for j >= 1 and consider H(j + 1)
    1. how to reduce to H(j)?
    2. chose i with in-degree zero - it can't be in the maximal 1-1 set
    3. no such i - the whole set's 1-1
5. example - finding a celebrity
  1. be careful how you reduce from j - 1 to j
  2. everyone knows a celebrity, the celebrity knows nobody
  3. in a directed graph, a sink pointed to by all other nodes
  4. problem - find the celebrity (or sink)
  5. hyp - H(n) = can find the celebrity in an n-node graph
  6. bas - H(2) is true
  7. ind - let H(j) be true and consider H(j + 1)
  8. how to get to H(j) from H(j + 1)
    1. pick an arbitrary j + 1 - either H(j) finds the celebrity or it doesn't
      1. if it does, ask 2 questions to compare the celebrity against j + 1
      2. if it doesn't ask 2j questions to check if j + 1 is the celebrity
    2. pick a non-celebrity j + 1 - it's easy with one question
      1. if H(j) doesn't find a celebrity, there is none
      2. if H(j) finds a celebrity, 2 questions checks the celebrity against j + 1
      3. in either case a theta(n) algorithm
6. example - maximum consecutive subsequence
  1. sometimes the hypothesis needs to be strengthened
  2. the sum of consecutive numbers x₁, ..., x_n - find the largest such sum
  3. hyp - H(n) = can find the mcs in an n-number sequence
  4. bas - H(1), yup
  5. ind - assume H(j) is true for j >= 1 and consider H(j + 1)
    1. H(j) has two cases - the mcs ends at x_j or it doesn't
    2. if it does, just increase the mcs
    3. if it doesn't, x_{j + 1} may contribute to a consecutive subsequence that isn't maximal yet
7. example - balance factors
  1. sometimes strong induction is necessary
  2. a root's balance factor - the difference between the heights of the left and right subtrees
  3. hyp - H(n) = can find the balance factor for an n-node tree
  4. bas - H(1) is easy
  5. ind - assume H(j) is true for j >= 1 and consider H(j + 1)
  6. but, you can't compute a parent's balance from the children's balance - you need their heights
This page last modified on 25 April 2000.

H(j + 1)	=	xP_{j - 1 + 1}(x) + a_{n - j + 1})
	=	xP_j(x) + a_{n - j + 1}