Chapter 5

• Divide and Conquer: class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions to these subproblems into an overall solution
• Recurrence Relation: bounds the running time recursively in terms of the running time on smaller instances
• Divide and conquer strategy may reduce the running time to a lower polynomial from the brute-force polynomial time.

• Mergesort: sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls using the linear time algorithm for merging sorted lists
• Base Case: when input has been reduced to size 2, T(n_ is equal to a constant when n is a constant.
  • Stop the recursion and sort the two element
• For some constant c, T(n) ⇐ 2T(n/2) + cn when n >2, and T(2) ⇐ c
• To gain an explicit bound, we need to solve the recurrence relation so that T appears only on the left-hand side of the inequality, not the right-hand side as well.

Approaches to Solving Recurrences

1. “unroll” the recursion, accounting for the running time across the first few levels, identifying a pattern that can be continues as the recursion expands. Sum up the running times over all levels → total running time
2. Start with a guess, substitute in the recurrence relation, check if it works; Use an argument by induction on n to formally justify this approach

Unrolling the MergeSort Recurrence

• Analyzing the first few levels: single problem of size n
  • level 0: takes at most cn plus the time spent in all subsequent recursive calls
  • level 1: two problems of size n/2; each takes at most cn/2 time
  • level 3: four problems of size n/4; each takes at most cn/4 time
• Identifying a pattern: level j: number of subproblems has doubled j times: 2^j; each ahs shrunk in size by a factor of two j times, and so each has size n/2^j; each level contributes at most 2^j(cn/2^j)=cn to the total running time.
• Summing over all levels of recursion: we've found that the recurrence in (5.1) has the property that the same upper bound of cn applies to total amount of work performed at each level. Number of levels: logn. Total running time = O(nlogn)

Substituting a Solution into the Mergesort Recurrence

• Belief: T(n) ⇐ cnlogn for all n>2
  • want to check if this is true
• Plug it into the recurrence:
  • for n=2: true, since cnlogn = 2c
  • By induction: T(m) ⇐ cmlogm, for all values of m less than n, and we want to establish this for T(n).
    • T(n/2) ⇐ c(n/2)log(n/2) → log(n/2) = logn -1

An Approach Using Partial Substitution

• One guesses the overall form of the solution without pinning down the exact values of all the constants and other parameters at the outset.
• Suppose we believe that T(n) = O(nlogn)
• First write T(n) ⇐ knlogbn for some constant k and base b
• Try out one level of the induction as follows
  • T(n) ⇐ 2T(n/2) + cn ⇐ 2k(n/2)logb(n/2)+cn
• Chose 2 as the base to help with simplification to:
  • T(n) = (knlogn) - kn + cn
• k must be at least as large as c, so:
  • T(n) ⇐ (knlogn) - kn +cn ⇐ knlogn

Using mergesort as the example was helpful, as I am pretty familiar with that algorithm at this point. We went over it in class which helped me follow along with the step-by-step process of coming up with an appropriate recurrence relation. Still though, this material is a little difficult for me and I know I'll need more practice with its application before I really understand it.

Readability: 6.0 Interesting: 6.0