1) Modeling with recurrence relations

• example 1. Counting rabbits

  • Fibonacci sequence : f_n = f_(n-1) + f_(n+2)

• example 2. Hanoi puzzle

  • The goal of the puzzle is to have all the disks on the second peg in order of size, with the largest on the bottom.
    ∴ H_n = H_(n-1) + 1 + H_(n-1)

  • where H_(n-1) denotes the number of moves needed to solve with (n-1) disks.
    ∴ H_n = 2^n - 1 and H_1 = 1

• example 3. Counting bits strings of length n with no two consecutive 0

  • a_n denotes the number of bit strings of length n that don't have two consecutive 0.
  • 2 types (those that end in 1 / those that end in 0)
    • those that end in 1 → a_(n-1) with 1 added at the end
    • those that end in 0 → must have 1 as their (n-1)st bit → a_(n-2) with 10 added at the end
  • a_1 = 2, a_2 = 3
    ∴ a_n = a_(n-1) + a_(n-2) for n ≥ 3

2) Algorithms and recurrence relations

• dynamic programming : when it recursively breaks down a problem into simpler overlapping sub-problems, and computes the solution using the solutions of the sub-problems.

• example

  • total n talks, where talk_j begins at time s_j, ends at time e_j, and w_j students
  • T(j) maximum # of total attendees for an optimal schedule from the first j talks.
    • sort the taks in order of increasing end time
    • renumber the talks so that e_1 ≤ e_2 ≤ ... ≤ e_n
  • compatible if the times they are scheduled do not overlap
  • p(j) = i, for which e_i ≤ s_j, i < j (talk_j 가 시작하기 전에 끝나는 가장 늦은 talk_i)

• solution

  • first, develop a key recurrence relation.
    • case 1 ) talk_j belongs to the optimal schedule
    • case 2 ) talk_j doesn't belongs to the optimal schedule
  • case 1
    • p(j)+1, ..., j-1 은 optimal schedule에 포함될 수 없음 (∵ not compatible with j)
    • optimal schedule은 1, ..., p(j) 로 구성되어진다.
      ∴ T(j) = w_j + T(p(j))
  • case 2
    • optimal schedule from talks 1,...,j is the same as an optimal schedule from talks 1,...,j-1.
      ∴ T(j) = T(j-1)
  • Combining case 1 and case 2
    ∴ T(j) = max(w_j + T(p(j)), T(j-1))

• algorithm

  • the algorithm is efficient by storing the value of each T(j) after we compute it.
  • memorization

1) Introduction

• Definition 1. A linear homogeneous ( f(ax) = a^nf(x) ) recurrence relation of degree k with constant coefficients is a recurrence relation of the form (previous k terms of the sequence)
  a_n = c_1 * a_(n-1) + c_2 * a_(n-2) + ... c_k * a_(n-k)

  • a_n = a_(n-5) : linear homogeneous recurrence relation of degree 5

• Link: homogeneous

2) Solving linear homogeneous recurrence relations (LHRR) with constant coefficients

• First, solutions of the form a_n = r^n where r is a constant.

  • r^n = c_1 * r^(n-1) + ... + c_k * r^(n-k)
  • divide by r^(n-k)
  • r^k - c_1 * r^(k-1) _ ... - c_(k-1) * r - c_k = 0
  • 위 식을 특성 방정식 이라고 하고 이 방정식의 근을 특성근 (characteristic root) 라고 한다.

• Second, linear combination of two solutions of LHRR is also a solution.

• Theorem 1. Let c_1 and c_2 be real numbers. Suppose that r^2 - c_1 * r - c_2 = 0 has two distinct roots r_1 and r_2. Then the sequence {a_n} is a solution of the RR. a_n = c_1 * a_(n-1) + c_2 * a_(n-2) ⇔ a_n = b_1 * (r_1)^n + b_2 * (r_2)^n where b_1 and b_2 are constants.

• 동차 선형 점화식 (LHRR) 의 일반항 a_n 이 있고, 이의 k차 특성 방정식의 서로 다른 특성근이 r_1, r_2 이면, 동차 선형점화식의 일반항 a_n 은 특성근들의 일차결합으로 나타낼 수 있다.

• Link : Recurrence Relation

• example 3. LHRR

  • a_n = a_(n-1) + 2 * a_(n-2) with a_0 = 2, a_1 = 7
  • r^2 - r - 2 = 0 and roots are 2, -1. ∴ a_n = b_1 * 2^n + b_2 * (-1)^n

• Theorem 2. Let c_1 and c_2 be real numbers with c_2 ≠ 0. Suppose that r^2 - c_1 * r - c_2 = 0 has only one root r_0. A sequence {a_n} is a solution of the recurrence relation a_n = c_1 * a_(n-1) + c_2 * a_(n-2) ⇔ a_n = b_1 * (r_0)^n + b_2 * n * (r_1)^n where b_1 and b_2 are constants.

1) Divide-and-Conquer RR

• Divide-and-Conquer

  • size n problem → a sub-problems * size (n/b)
  • g(n) extra operations are required in the conquer step to combine the solutions of the sub-problems into a solution of the original problem.
  • f(n) represents the # of operations required to solve the problems of size n ∴ f(n) = a f(n/b) + g(n)
  • ex) merge sort, binary search, a^b

• example

  • size n 을 2 분할로 나누다 보면 총 log_2 n 단계까지 나눠짐 (ex) 8개를 2개씩 나누면 3번)
  • ① 나누어지는 문제의 개수 (a)
  • ② 분할 후 문제의 크기 (n/b)
  • ③ 각 문제마다 병합 혹은 정복 단계에서 걸리는 시간 (d)

Link: Divide-and-Conquer

• 한 개의 데이터를 처리하는데 필요한 시간이 c 이면 n 개 데이터 처리하는데는 cn
• b로 나눠서 i번 분기하면 분기횟수 i = log_b n

• Theorem 1.
  Let f(n) = a f(n/b) + c

  • f(n) = O( n^(log_b a) ) if a > 1
  • f(n) = O( log n ) a = 1

• Theorem 2. Master theorem
  Let f(n) = a f(n/b) + c * n^d whenever n = b^k

  • f(n) = O( n^d ) if a < b^d
  • f(n) = O( n^d * log n ) if a = b^d
  • f(n) = O( n^(log_b a) ) if a > b^d

• example 12. the closest-pair problem

  • brute-force : O(n^2) (∵ C(n,2) = n(n-1)/2 )
  • for simplicity, n = 2^k
  • when n=2, only one pair of points
  • divide-and-conquer cases
  • (1) both left → d_L (2) both right → d_R (3) one in left one in right
  • d = min(d_L, d_R)

1) Introduction

• definition 1. Generating function (멱급수 형태)
  G(x) = a_0 + a_1 * x + ... a_k * x^k + ... = sum (a_k * x^k) (0 ≤ k ≤ ∞)

• example

  • n개의 서로 다른 종류 중 r개 선택하기 (단, each kind 마다 최소 1개는 반드시 골라야 함)

ref : discrete mathematics and its applications