please also explain how the answer came about if possible
Homework Answers
Let T(n) be the time taken for input n
Base Case is T(1) = 1
One while loop which runs for n time and One recursive call of
2*RecursiveCall(n/2)
T(n) = 2*T(n/2) + n
We Can solve the using Master's theorem :-
a = 2 , b = 2, f(n) = n
g(n) = nlogb a = nlog
22 = n
We can see f(n) = g(n) , Hence T(n) = O(nlogb
a log n) =>
T(n) = O(nlog n)
Add Answer to:
please also explain how the answer came about if
possible
b) Base 7. Master Theorem (3...
3. Recursive Program (6 points) Consider the following recursive function for n 1: Algorithm 1 int...
3. Recursive Program (6 points) Consider the following recursive function for n 1: Algorithm 1 int recurseFunc(int n) If n 0, return 1. If n 1, return 1 while i< n do while j <n do print("hi") j 1 end while i i 1 end while int a recurse Func(n/9); int b recurse Func (n/9) int c recurse Func (n/9) return a b c (1) Set up a runtime recurrence for the runtime T n) of this algorithm. (2) Solve...
III. ASSIGNMENT 2.1 As discussed in class, the example program enumerates all possible strings (or if...
III. ASSIGNMENT 2.1 As discussed in class, the example program enumerates all possible strings (or if we interpret as numbers, numbers) of base-b and a given length, say l. The number of strings enumerated is b l . Now if we interpret the outputs as strings, or lists, rather than base-b numbers and decide that we only want to enumerate those strings that have unique members, the number of possible strings reduces from b l to b!. Furthermore, consider a...
1-Is it possible to run a program without a main() function? Yes No 2- How many...
1-Is it possible to run a program without a main() function? Yes No 2- How many main() functions can one have in a program? 2 This depends on what compiler you use. As many as you like 1 3- What does the following code fragment leave in x? char a = 'A'; int x = sizeof (a); 1 Depends on what compiler you use. 4 2 4- True or false: In a C program I can have two functions with...
2. Consider the function george (int n) computed by the following recursive C++ code. int george ...
2. Consider the function george (int n) computed by the following recursive C++ code. int george (int n) assert (n >= 0) if (n < 2) return 1; else return 2*george ((n+1)/2)+2*george (n/2)+2 george((n-1)/2)+2*george (n/2-1); (c) Design a memoization algorithm to compute george(n) for any given n. You do not have to write C++ code. This algorithm should be much faster than the dynamic programming algorithm. What is its time complexity?
2. Consider the function george (int n) computed by...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2)...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r-a%b Require: Array P with n > 0 values 1: i-1, j-n-l 2: while i<=j do for a=i to j by i do 4: 5: 6: 7: if Pla>Pat 11 and Pla]%2--0 then swap(Plal, Pla+1l) end...
X266: Recursion Programming Exercise: log For function log, write the missing base case condition and the...
X266: Recursion Programming Exercise: log For function log, write the missing base case condition and the recursive call This function computes the log of n to the base b.As an example: log 8 to the base 2 equals 3 since 8 = 2*2*2. We can find this by dividing 8 by 2 until we reach 1, and we count the number of divisions we make. You should assume that n is exactly b to some integer power. Examples: log(2, 4)...
Explain please II. (7 points) Consider the following bit of pseudocode: for (int k = 1; ks Ign; k++) (for (int i = 1; i r: i++) Print "Hello World"; for (int j-1;jsn:j++) Print "Hello Worl...
Explain please
II. (7 points) Consider the following bit of pseudocode: for (int k = 1; ks Ign; k++) (for (int i = 1; i r: i++) Print "Hello World"; for (int j-1;jsn:j++) Print "Hello World" when n = 2, how many times will "Hello World" be printed? When n 4, how many times will "Hello World be printed? O Assuming that the print is the basic operation, what is the complexity function of this pseudocode?
II. (7 points) Consider...
1 2 3 The base case; reduce problem and general solution of the recursive algorithm of...
1
2
3
The base case; reduce problem and general solution of the recursive algorithm of n! are: O A. O! =0 (n-1)! n(n-1)! OB.O!= 1 (n-1)! n(n-1)! OC. O!=0 (n-1)! n(n-1) OD.0! = 1 (n-1) n(n-1) To set up the table for a party, if we use n tables and set up one next another as the picture. How many seats are there when if one side of the table can place only one chair? When determine Four-Step Methodology...
3) [16 points totall Consider the following algorithm: int SillyCalc (int n) { int i; int Num, answer; if (n <...
3) [16 points totall Consider the following algorithm: int SillyCalc (int n) { int i; int Num, answer; if (n < 4) 10; return n+ else f SillyCalc(Ln/4) answer Num Num 10 for (i-2; i<=n-1; i++) Num + = answer + answer; answer return answer } Do a worst case analysis of this algorithm, counting additions only (but not loop counter additions) as the basic operation counted, and assuming that n is a power of 2, i.e. that n- 2*...
Find the worst case runtime f(n) for the following algorithms. Specify the number of operations executed...
Find the worst case runtime f(n) for the following
algorithms.
Specify the number of operations executed for an input size n,
for the worst case run time as a function of n.
Circle statement(s) and draw a line to the right
side specifying the number of operations.
If statement(s) are a part of an iteration of n, specify the
total number of iterations as a function of n.
Algorithm-01 int sum = 0; int j = 1; while ( <=...
3. Recursive Program (6 points) Consider the following recursive function for n 1: Algorithm 1 int recurseFunc(int n) If n 0, return 1. If n 1, return 1 while i< n do while j <n do print("hi") j 1 end while i i 1 end while int a recurse Func(n/9); int b recurse Func (n/9) int c recurse Func (n/9) return a b c (1) Set up a runtime recurrence for the runtime T n) of this algorithm. (2) Solve...
2. Consider the function george (int n) computed by the following recursive C++ code. int george (int n) assert (n >= 0) if (n < 2) return 1; else return 2*george ((n+1)/2)+2*george (n/2)+2 george((n-1)/2)+2*george (n/2-1); (c) Design a memoization algorithm to compute george(n) for any given n. You do not have to write C++ code. This algorithm should be much faster than the dynamic programming algorithm. What is its time complexity?
2. Consider the function george (int n) computed by...
6. Consider the following algorithm, where P is an array containing random numbers. The function swap(v1,v2) will swap the values stored in the variables v1 and v2. Note that % is the modulus operation, and will return the integer remainder r of a/b, i.e., r-a%b Require: Array P with n > 0 values 1: i-1, j-n-l 2: while i<=j do for a=i to j by i do 4: 5: 6: 7: if Pla>Pat 11 and Pla]%2--0 then swap(Plal, Pla+1l) end...
X266: Recursion Programming Exercise: log For function log, write the missing base case condition and the recursive call This function computes the log of n to the base b.As an example: log 8 to the base 2 equals 3 since 8 = 2*2*2. We can find this by dividing 8 by 2 until we reach 1, and we count the number of divisions we make. You should assume that n is exactly b to some integer power. Examples: log(2, 4)...
Explain please
II. (7 points) Consider the following bit of pseudocode: for (int k = 1; ks Ign; k++) (for (int i = 1; i r: i++) Print "Hello World"; for (int j-1;jsn:j++) Print "Hello World" when n = 2, how many times will "Hello World" be printed? When n 4, how many times will "Hello World be printed? O Assuming that the print is the basic operation, what is the complexity function of this pseudocode?
II. (7 points) Consider...
1
2
3
The base case; reduce problem and general solution of the recursive algorithm of n! are: O A. O! =0 (n-1)! n(n-1)! OB.O!= 1 (n-1)! n(n-1)! OC. O!=0 (n-1)! n(n-1) OD.0! = 1 (n-1) n(n-1) To set up the table for a party, if we use n tables and set up one next another as the picture. How many seats are there when if one side of the table can place only one chair? When determine Four-Step Methodology...
3) [16 points totall Consider the following algorithm: int SillyCalc (int n) { int i; int Num, answer; if (n < 4) 10; return n+ else f SillyCalc(Ln/4) answer Num Num 10 for (i-2; i<=n-1; i++) Num + = answer + answer; answer return answer } Do a worst case analysis of this algorithm, counting additions only (but not loop counter additions) as the basic operation counted, and assuming that n is a power of 2, i.e. that n- 2*...
Find the worst case runtime f(n) for the following
algorithms.
Specify the number of operations executed for an input size n,
for the worst case run time as a function of n.
Circle statement(s) and draw a line to the right
side specifying the number of operations.
If statement(s) are a part of an iteration of n, specify the
total number of iterations as a function of n.
Algorithm-01 int sum = 0; int j = 1; while ( <=...
Most questions answered within 3 hours.
-
A) Is there a point where an increasing spring constant no
longer affects the bounce height?...
asked 18 seconds from now -
At the end of their final exam, 550 students answered an
additional question in which they...
asked 22 minutes ago -
The boiling point of water, H2O, is 100.000 °C at 1 atmosphere.
Kb(water) = 0.512 °C/m...
asked 5 minutes ago -
Explain one example of interspecific
competition from primary peer-reviewed literature
only. In complete sentences, briefly summarize...
asked 5 minutes ago -
a player rolls a pair of fair die 10 times. the number X of 7's
rolled...
asked 8 minutes ago -
A cart loaded with bricks has a total mass of 22.1 kg and is
pulled at...
asked 14 minutes ago -
What are some ways that technology can help companies and leaders
to manage compensation, benefits plans,...
asked 13 minutes ago -
Twin studies suggest
that if a person has a ______ twin their relative risk of being...
asked 23 minutes ago -
Consider an argon-ion laser running at 514.5nm with a minimum
beam waist (radius) of wo =...
asked 34 minutes ago -
Discuss in your own words the application of risk management
techniques needed to make a facility...
asked 41 minutes ago -
Culver Co. purchased land as a factory site for $600,000. The
process of tearing down two...
asked 51 minutes ago -
ANSWER THE FOLLOWING AS TRUE OR FALSE
a) _____ there are no saturated fats in...
asked 1 hour ago