Can somebody please help me with these problems? These are from the textbook Fou
ID: 672229 • Letter: C
Question
Can somebody please help me with these problems? These are from the textbook Foundations of Algorithms by Richard Neapolitan and Kumarss Naimipour.
5. Suppose that, in Algorithm 2.1 (line 4), the splitting function is changed to mid = low;. Explain the new search strategy. Analyze the performance of this strategy and show the results using order notation.
6. Write an algorithm that searches a sorted list of n items by dividing it into three sublists of almost n/3 items. This algorithm finds the sublist that might contain the given item and divides it into three smaller sublists of almost equal size. The algorithm repeats this
process until it finds the item or concludes that the item is not in the list. Analyze your algorithm and give the results using order notation.
Thanks.
Explanation / Answer
1)
Procedure lm (low,high)
if high -> low+1 < 3 then compute a
else
mid <- [(low+high)/2]
x0 <- x[mid]
a1 <- lm(low; mid)
a2 <- lm(mid+1; high)
.a <- min [a1,a2]
k <- 0
for i <- 1 to n
if x(Y[i])-> x < a then
k <- k +1
T[k] <- Y[i]
end if
end for
a3 <- 2a
for i <- 1 to k -> 1
for j <- i +1 to min {i+7,k}
if d(T[i],T[j])< a3 then a3 <- d(T[i],T[j])
end for
end for
a <- min{a,a3}
end if
return a
2)
Procedure Search(low,high, x)
while(low <= high && high - low > 1)
mid1 = floor((low+high) / 3);
mid2 = floor(2 * (low+high) / 3);
if
(x == S[mid1])
return
mid1;
else
if
(x == S[mid2])
return
mid2;
if
(x < S[mid1])
high = mid1 - 1;
Search(low,high,x);
else
if(x > S[mid2])
low = mid2 +1;
Search(low,high,x);
else
if
(x > S[mid1] && x < S[mid2])
low = mid1 +1;
high = mid2 -1;
Search(low,high, x);
end
for
(i=low;i<=high;i++)
end
if(x==S[i])
end
end
end
If we analysis this algorithm time complexity will be O(log n)