Lecture Notes for Algorithm Design

Algorithm Design via Induction, 2 November 1999

1. 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)

2. example - polynomial evaluation

   1. evaluate P_n(x) = a_nxⁿ + a_{n - 1}x^{n - 1} + . . . + a₁x + a₀ for some x

   2. 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 + 1}(x)

         2. I can compute a_{j + 1}x^{j + 1} + P_j(x)

         3. repeatedly exponentiating x is expensive

   3. 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 + 1}(x) and x^{j + 1}

         2. I can compute a_{j + 1}x^{j + 1} + P_j(x) and x^jx

         3. 2n multiplications

   4. third cut

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

      2. hyp - H(j) = I can compute xP_{j - 1}(x) + a_{n - j}

      3. bas - H(0) = P₀(x) = a_{n - 0} = a_n

      4. ind - Suppose H(j) for j >= 0 and consider

         H(j + 1)	=	xPj - 1 + 1(x) + an - (j + 1)
         	=	xPj(x) + an - (j + 1)

      5. n multiplications - Horner's rule

3. 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) - the graph itself is a k-degree induced subgraph, it is largest, and greed removes no vertices.

      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. everyone knows a celebrity, the celebrity knows nobody

      2. in a directed graph, a sink pointed to by all other nodes

      3. problem - find the celebrity (or sink)

      4. hyp - H(n) = can find the celebrity in an n-node graph

      5. bas - H(2) is true

      6. ind - let H(j) be true and consider H(j + 1)

      7. how to get to H(j) from H(j + 1)

         1. pick an arbitrary n - it's the celebrity or not

         2. pick a non-celebrity - it's easy with one question

   6. example - divide and conquer

      1. reducing a problem by one each time may lead to an O(n²) algorithm

      2. reducing by half each time may be better, if the combination is not expensive

   7. example - balance factors

      1. a root's balance factor - the difference between the heights of the left and right subtrees

      2. hyp - H(n) = can find the balance factor for an n-node tree

      3. bas - H(1) is easy

      4. ind - assume H(j) is true for j >= 1 and consider H(h + 1)

      5. but, you can't compute a parent's balance from the children's balance - you need their heights

   8. example - maximum consecutive subsequence

      1. the sum of consecutive numbers - find the largest such sum

      2. hyp - H(n) = can find the mcs in an n-number sequence

      3. bas - H(1), yup

      4. ind - assume H(j) is true for j >= 1 and consider H(h + 1)

   ---

   This page last modified on 12 November 1999.