Create Time: 2nd April 2024
Title: "[[DAA-Assignment-1]]"
status: DONE
Author:
- AllenYGY
tags:
- DAA
- Assignment
created: 2024-04-02T17:07
updated: 2024-04-08T13:35
Given the input A=[11, -7, 8, 12, 6, 5, -6, 3] , track the divide-and-conquer algorithm to find the maximum contiguous subarray. You need to show the recursive calls as a tree. The input and output for each recursive call should also be indicated as well.
Algorithm Maximum Contiguous Subarray Problem
if i=j then
return R[i]
else
s1←MCS(R,i,⌊(i+j)/2⌋)//Using floor function for lower rounding
s2←MCS(R,⌊(i+j)/2⌋+1,j)
A←MaxSuffix(R,i,⌊(i+j)/2⌋)+MaxPrefix(R,⌊(i+j)/2⌋+1,j)
return MAX(s1,s2,A)
end if
Given two polynomials
Algorithm Polynomial Multi2(A(x),B(x))
if n=0 then
return a0×b0
else
A0(x)=a0+a1x+⋯+a⌊2n⌋−1x⌊2n⌋−1
A1(x)=a⌊2n⌋+a⌊2n⌋+1x+⋯+anxn−⌊2n⌋
B0(x)=b0+b1x+⋯+b⌊2n⌋−1x⌊2n⌋−1
B1(x)=b⌊2n⌋+b⌊2n⌋+1x+⋯+bnxn−⌊2n⌋
Y(x)=PolyMult2(A0(x)+A1(x),B0(x)+B1(x))
U(x)=PolyMult2(A0(x),B0(x))
Z(x)=PolyMult2(A1(x),B1(x))
return U(x)+(Y(x)−U(x)−Z(x))x⌊2n⌋+Z(x)x2⌊2n⌋
end if
In the deterministic linear-time divide-and-conquer algorithm taught in class for the selection problem, the input array is divided into groups of 5 elements. Analyze the running time of the algorithm if the input array is divided into groups of 7. Does your algorithm run in linear time?
The Algorithm is still run in linear time
Algorithm Deterministic-Select(A,p,r,i)
if p=r then
return A[p]
end if
q=Deterministic−Partition(A,p,r)
k=q−p+1
if i=k then
return A[q]
end if
if i<k then
return Deterministic−Select(A,p,q−1,i)
end if
if i>k then
return Deterministic−Select(A,q+1,r,i−k)
end if
Assume always Deterministic-Select Right (wlog)
Proof
Base case: When
A segment is a pair of positive integers
Given a sequence of
Algorithm Check for Intersection in Segments
function DoesIntersect(Segments, Left, Right, R)
if Left≥Right then
return false
end if
Mid←⌊(Left+Right)/2⌋
LeftIntersect← DoesIntersect(Segments, Left, Mid, R)
RightIntersect← DoesIntersect(Segments, Mid+1, Right, R)
if LeftIntersect or RightIntersect then
return true
end if
MaxLeftB← FindMaxB(Segments, Left, Mid)
MinRightA← FindMinA(Segments, Mid+1, Right)
if MaxLeftB>MinRightA then
return true
end if
return false
end function
function FindMaxB(Segments,Left,Mid)
MaxB←−∞
for i←Left to Mid do
MaxB←max(MaxB,Segments[i].b)
end for
return MaxB
end function
function FindMinA(Segments,Mid,Right)
MinA←∞
for i←Mid+1 to Right do
MinA←min(MinA,Segments[i].a)
end for
return MinA
end function
When
Assume: The number of terms in the polynomials is always an integer power of
In other words,
Hint: please pay attention to the input size
Algorithm PolyMulti(A(x),B(x))
A′(x)=M(A(x))
B′(x)=M(B(x))
return GPolyMultic(A′(x),B′(x))
It will not increase the time complexity comparing to the original algorithm.
The time cost will slightly increase.
Suppose there are 2 polynomials with
After the operation it now turn to
In original algorithm the time complexity is
Now the time complexity is
There are almost the same time complexity