Question

You are an algorithm designer and you came up with four different divide-and-conquer algorithms for some problem Q. Those four algorithms are described below in parts (1), (2), (3), and (4). You wrote those descriptions a long time ago so now you want to remind yourself, for each one of them, what was the corresponding recurrence relation and provide an upper bound on the running time. So first give the recurrence then solve it using any method of your choice (show your work).

1. If you solve 4 sub-problems of size n/5, then the cost of combining the solutions of the sub-problems to obtain a solution for the original problem is 2n + 5;

2. If you solve 14 sub-problems of size n/4, then the cost for combining the solutions is 123;

3. If you solve 2 sub-problems of size n/2, then the cost for combining the solutions is 5n 3 + 2n 2 + 3;

4. If you solve 3 sub-problems of size 2n/3, then the cost for combining the solutions is 4n.

Answer #1

**Ans:** After closer observation it is quite clear
that all the algorithms mentioned in the question can be easily
solved using Master method.

**Master Method:**

Master method is mainly derived from recurrence tree method. If Recurrence relation is of the form:

where a >= 1 and b > 1

Then there exist following three cases:

**Case 1:** If f(n) = Θ(n^{c}) where c <
Log_{b}a then T(n) = Θ(n^{Logba})

**Case 2:** If f(n) = Θ(n^{c}) where c =
Log_{b}a then T(n) = Θ(n^{c}Log n)

**Case 3:** If f(n) = Θ(n^{c}) where c >
Log_{b}a then T(n) = Θ(f(n))

**Solution:** Each recurrence relation is of the
form:

(no. of sub problems)*T(size) + (cost of combining)

Hence,

**1)
**

Using Master Method,

a = 4; b = 5; c = 1; f(n) = 2n+5

Log_{b}(a) = Log_{5}(4) = 0.8613 < c

Hence, According to **Case 3**

**=>**

**2)
**

Using Master Method,

a = 14; b = 4; c = 0; f(n) = 123

Log_{b}(a) = Log_{4}(14) = 1.9037 > c

Hence, According to **Case 1**

**=>
**

**3)
**

Using Master Method,

a = 2; b = 2; c = 3; f(n) = 5n^{3}+2n^{2}+3

Log_{b}(a) = Log_{2}(2) = 1 < c

Hence, According to **Case 3**

**=>
**

**4)
**

Using Master Method,

a = 3; b = 3/2 = 1.5; c = 1; f(n) = 4n

Log_{b}(a) = Log_{1.5}(3) = 2.7095 > c

Hence, According to **Case 1**

**=>
**

Divide-and-Conquer technique is famous for providing O(n log n)
solutions for problems with O(n2) straight forward
solutions. One of those problems is the “Maximum Subarray Sum” or
“Maximum Value Contiguous Subsequence": Given a sequence of n
numbers A[0 ... n-1], give an algorithm for finding a contiguous
subsequence A[i ... j], for which the sum of elements in this
subsequence is the maximum we can get by choosing different i or
j.
For example: the maximum subarray sum for the...

Algorithms are used all the time today to solve problems, even
if people are not aware they are using them. Algorithms break down
one big problem into many smaller problems or steps that can be
more easily solved. One such problem in the business that can be
solved with algorithms is how much profit are they making based on
the sales of a product. The algorithm can be as follows:
Step 1: How many of the product has been sold?...

How to measure the time complexity of an
algorithm?
Identify an important operation in the algorithm that is
executed most frequently.
Express the number of times it is executed as a function of
N.
Convert this expression into the Big-O notation.
A. For each of the three fragments of code, what is its
worst-case time complexity, in the form "O(…)". (Use the
given solution to the first problem as a
model)
//----------------- This is a sample problem – solved
------...

For this lab assignment you will need to write some code and
create some graphs. You may use excel to create your graphs, or
other language of your choice. Your data needs to demonstrate the
experimental running time for Selection Sort (code in book), Merge
Sort (code in book), and the Arrays.sort() method.
Here is a basic outline of how you need to code this
assignment.
1) Create several arrays of size 100, 1000, 10000, 100000,
1000000, … (you need...

Suppose you are conducting an experiment where you flip a coin
four times and count the number of heads flips. For such an
experiment, you can either get 0/4, 1/4, 2/4, 3/4, or 4/4
heads.
a. Explain why there are five bars in the sampling distribution
for this experiment.
b. Draw a sampling distribution for this problem.
c. Use the equation √p * (1-p)/n to determine the
mean and standard deviation of the sampling distribution of sample
proportions with samples of...

I don't understand the difference between these two problems.
Problem #1 has you 4 P 4 / 4 = 4!/4 because I
guess you can rotate it 4 times and it'd still be in the same
arrangements as each of those women still have the same neighbors
during those 4 rotations. Please correct me if I am wrong.
However, in Problem #2, this time has 3 boys and 4 girls sitting
at a circular table, to which boys have to...

______ are programs designed to model the judgments of experts
in a particular field.
A. Expert systems
B. Expert
algorithms
C. Expert
operations
D. Expert
heuristics
Which of the following is an example of an ill-defined
problem?
A. solving Rubik’s
Cube puzzle
B. putting together
your schedule of classes for next semester
C. solving an algebra
problem
D. solving the Tower
of Hanoi problem
A(n) ______ problem has a clear goal, a...

Solve each problems using Polya's four-step problem-solving
strategy:
1. In the complex number system, i^1 = i; i^2 = -1; i^3 = -i;
i^4 = 1; i^5 = i... Find i^173.
2. A coffee shop is giving away a signature annual planner. In
the mechanics, each customer has to collect 24 stickers to avail of
the said planner, and customers can share stickers. At the end of
the promo period, John had a the most number of stickers, more than...

The purpose of this assignment is to solidify your understanding
on the applications of the time value of money. The scores of this
assignment will help in assessing the following learning goal of
the course: “students successfully completing this course will be
able to apply principles of time value of money to personal and
corporate financial decisions.” Instructions: You are required to
use a financial calculator or spreadsheet (Excel) to solve 10
problems (provided on page 3) on the applications...

You're are working on n different projects, but in m hours you
are going on vacation. Imagine that for each project i, you had a
function fi that told you how happy the people paying for project i
would be if out your m available hours you devoted 0 ≤ x ≤ m to
project i. Imagine further that each such function has maximum
value at most s, corresponding to the project being fully finished
(and thus the clients being...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 21 minutes ago

asked 34 minutes ago

asked 39 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago