Homework Answers
a) The j loop prints Whatsup 
And i loop runs from 1 to n
Total number of times it prints is 
b) Which equals 
Using the sum of squares formula 
That is, 
c) In terms of big theta notation, we have 
Add Answer to:
Problem 1: Let W(n) be the number of times "whatsup" is printed by Algorithm WHATSUP (see below) ...
Problem 1: Give the exact and asymptotic formula for the number f(n) of letters “A” printed...
Problem 1: Give the exact and asymptotic formula for the number f(n) of letters “A” printed by Algo- rithm PRINTAs below. Your solution must consist of the following steps: (a) First express f(n) using a summation notation 2 (b) Next, give a closed-form formula for f(n). (c) Finally, give the asymptotic value of the number of A's (using the O-notation.) Include justification for each step. Note: If you need any summation formulas for this problem, you are allowed to look...
Asymptotic notation O satisfies the transitive property i.e. if f(n)=O(g(n)) and g(n)=O(h(n)), then f(n)=O(h(n)). Now we...
Asymptotic notation O satisfies the transitive property i.e. if f(n)=O(g(n)) and g(n)=O(h(n)), then f(n)=O(h(n)). Now we know that 2n =O(2n-1), 2n-1 =O(2n-2?),....... , 2i=O(2i-1?),....... So using rule of transitivity, we can write 2n =O(2i-1?).We can go extending this, so that finally 2n =O(2k?), where k is constant.So we can write 2n =O(1?). Do you agree to what has been proved?If not,where is the fallacy? 6 marks (ALGORITHM ANALYSIS AND DESIGN based problem)
3. 0 marks Suppose you have an algorithm which has the following recurrence relation for W(n),...
3. 0 marks Suppose you have an algorithm which has the following recurrence relation for W(n), assuming n is a power of 2, i.e. assuming n-2, k20: for n for n- W()-2W(n/2)+2n+ 2 W(n)- Using back substitution and assuming n is a power of 2, ie. n-2, find an exact (ie non-recursive) formula for Win). Be sure to show your work and to simplify your final answer as much as possible. Note that you do NOT need to verify your...
Several algorithms have a loop structure that iterates n times and for the k-th iteration, they...
Several algorithms have a loop structure that iterates n times and for the k-th iteration, they perform on the order of k2 operations. In this case, the running time of the loop can be obtained by k2. In this problem, we will derive a closed formula for this sum and show that the sum is O(ui) 1. A telescoping sum is a sum of the form Σ-i (aj - a-1). It is easy to see that this sum equals an...
1. (13 points) Use the limit of a Riemann Sum (i.e. sigma notation and the appropriate...
1. (13 points) Use the limit of a Riemann Sum (i.e. sigma notation and the appropriate summation formulas) to evaluate the net-signed area between the graph of f(0) = 23 – 3 and the interval (0, 2). Let 27 be the right endpoint of the k-th subinterval (where all subintervals have equal width). Give your answer as a single integer or frac- tion, whichever is appropriate. Using any technique other than a limit of a Riemann Sum will earn no...
Consider the function f(x)=x22−9. (1 point) Consider the function f(x) = 9. 2 In this problem...
Consider the function
f(x)=x22−9.
(1 point) Consider the function f(x) = 9. 2 In this problem you will calculate " ( - ) dx by using the definition Lira f(x) dx = lim f(x;)Ar i=1 The summation inside the brackets is R, which is the Riemann sum where the sample points are chosen to be the right-hand endpoints of each sub- interval. r2 Calculate R, for f(x) = -9 on the interval [0, 3] and write your answer as a...
Exercise 5.12. Let n∈N and S={0,1,...,n−1}, and suppose that P({s}) = 1/n for each s∈S. Let...
Exercise 5.12. Let n∈N and S={0,1,...,n−1}, and suppose that P({s}) = 1/n for each s∈S. Let X:S→R be the random variable defined by X(s) =s. i) Find a closed form formula for MX(z), which does not use sigma notation or any other iterative notation. (ii) Calculate E[X]. (iii) Calculate Var[X].
How much time does the following "algorithm" require as a function Problem 4.1. of n? for...
How much time does the following "algorithm" require as a function Problem 4.1. of n? for i 1 to n do for j 1 to n do for k 1 to n3 do Express your answer in 6 notation in the simplest possible form. You may consider that each individual instruction (including loop control) is elementary
Use iteration to guess an explicit formula for the sequence... Materials for Reference: Homework Problems Solve the following problems 1. Use iteration to guess an explicit formula for the sequenc...
Use iteration to guess an explicit formula for the
sequence...
Materials for Reference:
Homework Problems Solve the following problems 1. Use iteration to guess an explicit formula for the sequence. Use the formulas from summation formula.pdf to simplify your answers whenever possible. (Follow the solution of exercise set 57-problem #5, on page A-43) dk-4dk-1+3, for all integers k2 2,where d1-2 2. Use iteration to guess an explicit formula for the sequence. Use the formulas from summation formula.pdf to simplify your...
1. a) Let f(n) = 6n2 - 100n + 44 and g(n) = 0.5n3 . Prove...
1. a) Let f(n) = 6n2 - 100n + 44 and g(n) =
0.5n3 . Prove that f(n) = O(g(n)) using the definition
of Big-O notation. (You need to find constants c and n0).
b) Let f(n) = 3n2 + n and g(n) = 2n2 . Use
the definition of big-O notation to prove that
f(n) = O(g(n)) (you need to find constants c and n0) and
g(n) = O(f(n)) (you need to find constants c and n0).
Conclude that...
Problem 1: Give the exact and asymptotic formula for the number f(n) of letters “A” printed by Algo- rithm PRINTAs below. Your solution must consist of the following steps: (a) First express f(n) using a summation notation 2 (b) Next, give a closed-form formula for f(n). (c) Finally, give the asymptotic value of the number of A's (using the O-notation.) Include justification for each step. Note: If you need any summation formulas for this problem, you are allowed to look...
3. 0 marks Suppose you have an algorithm which has the following recurrence relation for W(n), assuming n is a power of 2, i.e. assuming n-2, k20: for n for n- W()-2W(n/2)+2n+ 2 W(n)- Using back substitution and assuming n is a power of 2, ie. n-2, find an exact (ie non-recursive) formula for Win). Be sure to show your work and to simplify your final answer as much as possible. Note that you do NOT need to verify your...
Several algorithms have a loop structure that iterates n times and for the k-th iteration, they perform on the order of k2 operations. In this case, the running time of the loop can be obtained by k2. In this problem, we will derive a closed formula for this sum and show that the sum is O(ui) 1. A telescoping sum is a sum of the form Σ-i (aj - a-1). It is easy to see that this sum equals an...
1. (13 points) Use the limit of a Riemann Sum (i.e. sigma notation and the appropriate summation formulas) to evaluate the net-signed area between the graph of f(0) = 23 – 3 and the interval (0, 2). Let 27 be the right endpoint of the k-th subinterval (where all subintervals have equal width). Give your answer as a single integer or frac- tion, whichever is appropriate. Using any technique other than a limit of a Riemann Sum will earn no...
Consider the function
f(x)=x22−9.
(1 point) Consider the function f(x) = 9. 2 In this problem you will calculate " ( - ) dx by using the definition Lira f(x) dx = lim f(x;)Ar i=1 The summation inside the brackets is R, which is the Riemann sum where the sample points are chosen to be the right-hand endpoints of each sub- interval. r2 Calculate R, for f(x) = -9 on the interval [0, 3] and write your answer as a...
How much time does the following "algorithm" require as a function Problem 4.1. of n? for i 1 to n do for j 1 to n do for k 1 to n3 do Express your answer in 6 notation in the simplest possible form. You may consider that each individual instruction (including loop control) is elementary
Use iteration to guess an explicit formula for the
sequence...
Materials for Reference:
Homework Problems Solve the following problems 1. Use iteration to guess an explicit formula for the sequence. Use the formulas from summation formula.pdf to simplify your answers whenever possible. (Follow the solution of exercise set 57-problem #5, on page A-43) dk-4dk-1+3, for all integers k2 2,where d1-2 2. Use iteration to guess an explicit formula for the sequence. Use the formulas from summation formula.pdf to simplify your...
1. a) Let f(n) = 6n2 - 100n + 44 and g(n) =
0.5n3 . Prove that f(n) = O(g(n)) using the definition
of Big-O notation. (You need to find constants c and n0).
b) Let f(n) = 3n2 + n and g(n) = 2n2 . Use
the definition of big-O notation to prove that
f(n) = O(g(n)) (you need to find constants c and n0) and
g(n) = O(f(n)) (you need to find constants c and n0).
Conclude that...
Most questions answered within 3 hours.
-
(Expected rate of return and risk) Carter Inc. is evaluating a
security. Calculate the investment’s expected...
asked 1 hour ago -
What specific indicators can point to lack of progress for
African Americans in American society?
asked 2 hours ago -
1-The Electrons in a beam are moving at 2.7×108 m/s in an
electric field of 15000...
asked 2 hours ago -
A gas tank is a vertical cylinder. It has a radius of 1m, a
height of...
asked 2 hours ago -
Accent Software faces the following conditions. All of these
support Accent’s use of a market-penetration pricing...
asked 3 hours ago -
A mathematically inclined friend emails you the following
instructions: "Meet me in the cafeteria the first...
asked 3 hours ago -
A monopoly sells in two countries . The demand curves in the two
countries are p1...
asked 4 hours ago -
A .15kg rubber ball is bounced off a wall. Before hitting the
wall, the ball moves...
asked 5 hours ago -
A manufacturing company preparing to build a new plant is
considering three potential locations for it....
asked 5 hours ago -
B. If compound Y has approximately the same values of solubility
in toluene as compound X,...
asked 6 hours ago -
Oscar Inc. has inventory in Japan valued at 39,051,000 Yen one
year ago. One year ago...
asked 6 hours ago -
If Canada suffered from "fundamental disequilibrium," and its
government choose not to devalue its currency, a...
asked 6 hours ago