Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Question 1 . Solve the following recurrences using ( a ) repeated substitution method; and ( b ) master theorem if applicable and if not

Question 1. Solve the following recurrences using (a) repeated substitution method; and (b)
master theorem if applicable and if not say why.
1.T(1)=1, T(n)=2T(
n
2
)+ n
2Question 1. Solve the following recurrences using (a) repeated substitution method; and (b)
master theorem if applicable and if not say why.
1.T(1)=1,T(n)=2T(n2)+n2logn
2.T(1)=C,T(n)=T(n-1)+logn
3.T(1)=C,T(n)=2T(n2)+3n2
4.T(n)=3T(n2)+n
Question 2. Solve the following recurrences using recursion tree
1.T(n)=T(n5)+T(3n4)+cn
2.T(n)=3T(n2)+n
Question 3.
a) Design a brute-force algorithm for computing the value of a polynomial
p(x)=anxn+an-1xn-1+dots+a1x+a0
at a given point x0 and determine its worst-case efficiency class.
b) If the algorithm you designed is in (n2), design a linear algorithm for this problem.
c) Is it possible to design an algorithm with a better than linear efficiency for this problem?
Question 4. Given an unsorted array A[1..n]. Devise a divide-and-conquer based algorithm
to find the second largest number. (a) Write the pseudo code, and (b) What is the complexity?
Question 5. Consider a list A[1.n] of size n containing real numbers inR. Consider for exam-
ple, A={10,3.5,17.2,2.35,-15.45,9.1,-1.25}. Devise a divide and conquer based algorithm
(must be a single procedure) to compute the average
a) Briefly describe in no more than two lines the basic idea of your algorithm.
b) Write the pseudo code of your devised algorithm.
c) Write the recurrence relation expressing the complexity of the algorithm
log n
2.T(1)= C, T(n)= T(n 1)+ log n
3.T(1)= C, T(n)=2T(
n
2
)+3n
2
4.T(n)=3T(
n
2
)+ n
Question 2. Solve the following recurrences using recursion tree
1.T(n)= T(
n
5
)+ T(
3n
4
)+ cn
2.T(n)=3T(
n
2
)+ n
Question 3.
a) Design a brute-force algorithm for computing the value of a polynomial
p(x)= anx
n + an1x
n1+...+ a1x + a0
at a given point x0 and determine its worst-case efficiency class.
b) If the algorithm you designed is in \Theta (n
2
), design a linear algorithm for this problem.
c) Is it possible to design an algorithm with a better than linear efficiency for this problem?
Question 4. Given an unsorted array A[1..n]. Devise a divide-and-conquer based algorithm
to find the second largest number. (a) Write the pseudo code, and (b) What is the complexity?
Question 5. Consider a list A[1..n] of size n containing real numbers in R. Consider for example, A ={10,3.5,17.2,2.35,15.45,9.1,1.25}. Devise a divide and conquer based algorithm
(must be a single procedure) to compute the average
a) Briefly describe in no more than two lines the basic idea of your algorithm.
b) Write the pseudo code of your devised algorithm.
c) Write the recurrence relation expressing the complexity of the algorithm
image text in transcribed

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Students also viewed these Databases questions

Question

=+Is the guilt appropriate for the audience?

Answered: 1 week ago

Question

Develop successful mentoring programs. page 400

Answered: 1 week ago