COMP 3711 Design and Analysis of Algorithms
Tutorial 2: Divide and Conquer
Expansion method
Copyright By PowCoder代写 加微信 powcoder
= +
Recursion tree approach
𝑛=2 2( )
recursion termination
Assumption is that is a power of . Left side is the call to on that level;
Right side is amount of (non-recursive) work performed by problem on that level. Note that there will only be one problem on each such level (so tree is a path)
Sum of all items above. Calculation on next page
Recursion tree approach
𝑇(𝑛) 1 𝑇(𝑛 − 2)
𝑇 1 or 𝑇 2 = 1
𝑛−1 𝑇(𝑛−2 2
Right side is amount of (non-recursive) work performed on that level.
Note that there will only be one problem on each such level (so tree is a path).
Left side is the call to on that level.
, , depending upon whether is odd or even and we get
Expansion method
Recursion tree approach
Assumption is that is a power of .
𝑛=3 3( )
Right side is amount of (non-recursive) work performed on that level.
Note that there will only be one problem on each such level (so tree is a path).
Left side is the call to on that level.
Expansion method
+
𝑇(𝑛) 𝑛 𝑛𝑛𝑛𝑛
if ; is a power of .
Recursion tree approach
3𝑖 ⋅ 𝑛 2
𝑇(𝑛/4) 𝑛 2
… … … …
… … …
… … …
𝑇(𝑛/4) 𝑛 𝑇(𝑛/4) 𝑛 …
… 𝑇(2) 𝑇(1)
𝑛 4
𝑛 𝑇 1 = 𝑛
= 𝒏𝐥𝐨𝐠𝟐 𝟑 + 𝒏𝟐
𝐥𝐨𝐠𝟐𝒏𝟏 𝟑𝒊
Left side is the call to on that
Right side is amount of (non-recursive) work performed on that level.
. Note that
Expansion method
Recursion tree approach
𝑇(𝑛) log 𝑛 log 𝑛 𝑇(𝑛/2) log 𝑛 log 𝑛
. Assume that
log 𝑛 2
2
is a power of
log 𝑛 2
log𝟐 𝒏 𝟐 log𝟐 𝒏 =𝟐+𝟐+𝟏
Right side is amount of (non-recursive) work performed on that level.
Note that there will only be one problem on each such level (so tree is a path)
Left side is the call to on that
Expansion method
Recallthatlog =log 𝑛−𝑖
. Assume that
Recursion tree approach
is a power of
2log 2 𝑇(𝑛/2) 2log 2 2 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛
2 log 2
𝑛log 𝑛 𝑛𝑛 𝑛𝑛 𝑛log𝑛
𝑇(𝑛) 𝑛log 𝑛
2 log 2
𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1)
𝑇(𝑛/4) 2 log 2
2 log 2
𝑛 log 𝑛 2
2
𝒏 log𝟐𝒏 𝟐 𝒏log𝟐𝒏 =𝟐+𝟐+𝒏
Left side is the call to on that
Right side is amount of (non-recursive) work performed on that level.
Expansion method
Input: a sorted array of distinct integers (Distinct means that there are no repetitions among the integers. The integers can be positive, negative or both).
Design an algorithm to return an
index such that , if such an exists. Otherwise, report that no such index exists.
As an example, in the array immediately below, the algorithm returns 4
while in the array below, the algorithm returns that no such index exists. 14
(*) If , then forall .
Follows directly from facts that the array is sorted and all integers are distinct.
The main observation is that
More specifically, those two facts imply that So, if =>
Statement (*) follows by mathematical induction.
A similar proof shows that
(**)If , then
Use observations that
(*) If , then forall .
(**)If , then forall .
• If , we have found solution and can stop
• If , from first observation,
if solution exists, it must be in
• If , from second observation if solution exists, it must be in
So, after checking against (choose m to be middle item), can either (i) stop or
(ii) throw away half of the array and solve the problem on the other half.
The running time of the algorithm has the recurrence
, which solves to .
Solution (Code)
INDEX-SEARCH(A,s,t) first call is INDEX-SEARCH(A,1,n)
termination condition (empty subarray)
return “no such index exists
\\ recurse
return INDEX-SEARCH(A,s,m-1)
only one item go left
else go right return INDEX-SEARCH(A,m+1,t);
Note that algorithm “assumes’’ 𝑠 ≤ 𝑡, i.e., that array 𝐴[𝑠 … 𝑡] is nonempty. Termination condition (𝑠 > 𝑡) implies that search has ended without finding solution. Convince yourself that this is valid by working through what happens when 𝑡 − 𝑠 = 0,1 in both successful and unsuccessful cases.
Going Further
We derived the algorithm from the observations that
Which followed from facts that the array is sorted and all integers are distinct. This yielded
(*) If , then forall .
(**)If , then forall .
• If , we have found solution and can stop
• If , from first observation,
if solution exists, it must be in
• If , from second observation if solution exists, it must be in
Follow-up questions:
(1) Is it possible that for more than one If yes, how?
(2) Is the algorithm still correct if the integers are NOT distinct (but the array is still sorted)?
Let be an array of elements. A majority element of is any element occurring more than times (e.g., if , then a majority element should occur at least 5 times). Your task is to design an algorithm that finds a majority element, or reports that no such element exist
Suppose that you are not allowed to order the elements;
the only way you can access the elements is to check whether two elements are equal or not.
Design an time algorithm for this problem.
Note: The intent here is to use standard divide-and-conquer techniques to solve the problem.
An solution to this problem that takes advantage of more problem specific properties also exists.
In the array below, 2 is the majority item:
In the array below there is no majority item:
The important observation is that
Algorithm is then
1. Find majority , if it exists, in
2. Find majority , if it exists, in
3. If exists, count how many times it occurs in If more than , report .
If exists, count how many times it occurs in . If more than , report .
If neither exist, report, “no majority”.
The base case is when ,
and we can simply return the only element as the majority.
If contains a majority element ,
=> must be a maj. element in at least one of and
1. Find majority , if it exists, in
2. Find majority , if it exists, in
3. If exists, count how many times it occurs in If more than , report .
If exists, count how many times it occurs in If more than , report .
If neither exist, report, “no majority”.
Algorithm’s correctness follows from the first observation on previous page. Its running time satisfies
which solves to
More about this problem and its practical uses can be found by googling
Heavy Hitters in Data Streams
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com