# 程序代写 COMP 3711 Design and Analysis of Algorithms – cscodehelp代写

COMP 3711 Design and Analysis of Algorithms

Tutorial 2: Divide and Conquer

Expansion method

Copyright By cscodehelp代写 加微信 cscodehelp

= +

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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com