Scribd
Upload
46 views34 pages

Algorithms Lecture 4

This document summarizes key concepts from Lecture 4 on divide and conquer algorithms. It discusses three methods for solving algorithm recurrences: substitution method, master method, and recursion trees. It also provides examples of applying these methods to specific recurrences. The maximum subarray problem is presented as an example problem solved using divide and conquer. Details are given on the substitution method, including guessing a solution and using induction to prove it. Recursion trees are introduced as a way to generate guesses for recurrence solutions. The master method is described as applying to recurrences of the form T(n) = aT(n/b) + f(n).

Uploaded by

dalia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
46 views34 pages

Algorithms Lecture 4

This document summarizes key concepts from Lecture 4 on divide and conquer algorithms. It discusses three methods for solving algorithm recurrences: substitution method, master method, and recursion trees. It also provides examples of applying these methods to specific recurrences. The maximum subarray problem is presented as an example problem solved using divide and conquer. Details are given on the substitution method, including guessing a solution and using induction to prove it. Recursion trees are introduced as a way to generate guesses for recurrence solutions. The master method is described as applying to recurrences of the form T(n) = aT(n/b) + f(n).

Uploaded by

dalia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Algorithm Design & Analysis

by
Dr. Mohamed Abdel Hameed
Computer Science Dept.
Lecture 4
Lecture Rules
Chapter 4
Divide and Conquer
Divide and Conquer
Divide and Conquer
Divide and Conquer
Divide and Conquer
Divide and Conquer

(Normally, they can be ignored.)


Divide and Conquer

Three methods for solving recurrences:


• Substitution Method: Guess a bound and use Mathematical induction to prove.

• Master Method: Memorize three cases and use them to solve recurrences of the
form:
T(n) = a T(n/b) + f(n)

• Iteration Method: However, it is too easy to make an error in parenthesization,


and that recursion trees give a better intuitive idea than iterating the recurrence of
how the recurrence progresses.

Note: To help us finding a solution, we may use recursion-tree method that converts
the recurrence into a tree whose nodes represent the cost incurred at various level of
the recursion. We use techniques for bounding summations to solve the recurrence.
The Maximum-subarray problem

Three possibilities for the location of the maximum-subarray with respect to the
midpoint (the divide point):
The Maximum-subarray problem
The Maximum-subarray problem
The Maximum-subarray problem
The Maximum-subarray problem
The Maximum-subarray problem
The Maximum-subarray problem
Substitution method
1. Guess the solution.
2. Use induction to find the constants and show that the solution works.
Substitution method
Substitution method
Substitution method
Substitution method
Substitution method
Remedy: Subtract off a lower-order term.
Recursion Tree
• Use to generate a guess. Then verify by substitution method.
• Consider the recurrence
Recursion Tree

Note: not a complete binary tree.

Depth for leftmost branch:


Subproblem size for a node at depth i is .
Therefore, = 1 → i = log3n

Depth for the rigtmost:


Subproblem size for a node at depth i is .
Therefore, = 1 → i =
Recursion Tree
Recursion Tree
Recursion Tree
Master Method

• Let a, b, and k be integers


satisfying a ≥ 1, b ≥ 2, and k ≥ 0
• n/b can be either floor or ceiling
function.
• Floor: T(0) = u is given
• Ceiling: T(1) = u is given

Examples: T(n) = 4T(n/2) + n 


T(n)  ?
T(n) = 4T(n/2) + n2 
T(n)  ?
T(n) = 4T(n/2) + n3 
T(n)  ?
Master Method

F(n) is polynomially smaller


than
Master Method

F(n) is the same size as

F(n) is polynomially larger than .


It should also satisfy the
regularity condition
Master Method
Master Method
Assignment

You might also like