Please explain it assuming it I do not know any thing. Following the Divide-Conq
ID: 3604664 • Letter: P
Question
Please explain it assuming it I do not know any thing.
Following the Divide-Conquer strategy, we divide the circular
region in to 4 roughly equal parts, with two line segments.
The vertices on this circular boundary together with these two
line segments form a set S. We first find the maximum element of S.
This takes O(N). Let x be this maximum element. If x appears
on the intersection of the circular boundary or the vertical
or the horizontal line segments, then x is already a local maximum,
because all its neighbors are also in S.
Suppose x is not on an intersection, then we check its neighbors
to see if it is a local maximum, and if so we are done.
If not it has a neighbor y in the interior of one of the 4 subregions
and y > x. We then focus on this subregion.
Inductively we have the following, we have a subregion R on the boundary
we have a vertex x' with value that is the maximum on the boundary,
and x' has an interior neighbor y' in R, such that y' > x'.
When R is sufficiently small, say, of size < 10, we find a global maximum
z of R, which has z >= y' > x'. Thus z is not on the boundary of R,
since x' is the maximum on the boundary. Thus z is an interior point of
R. An interior point that is a local maximum of R is also
a local maximum of the original graph. Done.
(NOTE: without the condition on x' and y' > x', it is NOT in general
true that a local maximum of a subregion R is also a local maximum of
the parent region.)
Thus we have the recurrence
T(n) = O(N) + T(N/4)
which gives O(N) in total.
This is the solution. Please explain it further.
This is a variant of a homework problem which we further discussed in class. The essence of the solution for the problem on the chessboard still applies for the circular region. As the circle has radius N, it should be clear that the number of vertices of this graph in Problem 3 is approximately pi NA2 = Theta(N^2). Therefore we cannot afford to read the value at each vertex, to achieve time o(N'2). The problem asks us to find an algorithm with worst case bound 0 (N).Explanation / Answer
Solution:
If we solve the recurrence T(N)= T(N/4) + O(N),
We can solve this using Master theorem
as per master theorem, the format of the recurrence relation should be like this aT(n/b) + f(n)
so, here a= 1, b= 4 and f(n)= n
n^ logb a= n^0= 1
comparing f(n) and 1 we can say that this falls into case-3 of master theorem
so time complexity T(n)= O(N).
I hope this helps, please let me know in case of any doubt. Thumbs up if this helped.
,