Homework Answers
a)
given
D(N) = 2 D(N / 2) + N .....................(0)
by induction
D(N/2) = 2 D(N/4) + N ..................... (1)
when N is replaced by N/2 in eq (0)
D(N/22) = 2 D(N/8) + N
.....................(2)
N is replaced by N/4 """"""""
..........,
..............
D (N / 2k ) = D (1) = 0 ...........................(k) N is replaced by N/2k
applying above (1) to (k) equations into equation
(0).
D(N) = 2*2*2* ......*D(1) + N + N + N + ..... k times
= N +
N + N + N +..............k times
becuase N/2k == 1 hence 2k == N implies k = log2
N
therefore D(N) = N (1 + 1 + 1 + 1 + .................k times)
= N k
= N log2 N
=============================================================
b) Note: base is 2 so ( log2 10n will not
equal to n but equals to n * log210)
number of operations = N log N
given N = 106
hence N log N = 106 log 106
= 106 * 6 log 10
total time taken by cpu = no of operations / operation per
second
= 106 * 6 log 10 / 100
= 6 * 10 4 * log 10
= 6 * 10 4 * 3.322
= 19.932 * 104 seconds
therefore time taken by CPU 19.932 * 104 seconds for execution of N = 106 problem size.
Add Answer to:
Prove the proposition given in a) with induction or by picture. a) If D(N) satisfies D(N)...
4. Suppose T (n) satisfies the recurrence equations T(n) = 2 * T( n/2 ) +...
4. Suppose T (n) satisfies the recurrence equations T(n) = 2 * T( n/2 ) + 6 * n, n 2 We want to prove that T (n)-o(n * log(n)) T(1) = 3 (log (n) is log2 (n) here and throughout ). a. compute values in this table for T (n) and n*log (n) (see problem #7) T(n) | C | n * log(n) 2 4 6 b. based on the values in (a) find suitable "order constants" C and...
Induction proofs. a. Prove by induction: n sum i^3 = [n^2][(n+1)^2]/4 i=1 Note: sum is intended...
Induction proofs. a. Prove by induction: n sum i^3 = [n^2][(n+1)^2]/4 i=1 Note: sum is intended to be the summation symbol, and ^ means what follows is an exponent b. Prove by induction: n^2 - n is even for any n >= 1 10 points 6) Given: T(1) = 2 T(N) = T(N-1) + 3, N>1 What would the value of T(10) be? 7) For the problem above, is there a formula I could use that could directly calculate T(N)?...
Q) prove correctness the recurrence relation for case n = 2^x using a proof bt induction....
Q) prove correctness the recurrence relation for case n = 2^x using a proof bt induction. T(n) if n <= 1 then ....... 0 if n > . 1 . then ............1+4T(n/2) hint : when n = 2^x each of recursive calls in a given instnace of repetitiveRecursion in on the subproblem of the smae size the equation n = j-i +1 may be helpful in expressiong the problem size in terms of parameters i and j the closed-form expression...
proving that the language of the grammar is the given one. Prove by induction on n...
proving that the language of the grammar is the given one. Prove by induction on n that sum of 2^k for k = 0 to n = 2^(n+1) -1 for n>=0 Basis P(0) when n = 0: ** = ** is true. Assume P(i) is true, AL = AR when n = i: ** = ** for i>=0 Inductive Step P(i) to P(i+1), Show when n = i+1: ** = ** ...
Exercise 1.6.4: Prove the following by induction: (a) “k - n(n+1)(2n +1) k= 1 (b) If...
Exercise 1.6.4: Prove the following by induction: (a) “k - n(n+1)(2n +1) k= 1 (b) If n > 1, then 13-n is divisible by 3. (c) For n 3, we have n +4 <2". (d) For any positive integer n, one of n, n+2, and 11+ 4 must be divisible by 3. (e) For all n e N, we have 3" > 2n +1. ()/Prove that, for any x > -1 and any n e N, we have (1+x)" 21+1x.
Proposition 8. Σdno(d)= n. Proof. Consider the n rational numbers 1, 2, ,. Reduce each frac- tion...
Proposition 8. Σdno(d)= n. Proof. Consider the n rational numbers 1, 2, ,. Reduce each frac- tion to lowest terms. Then the numerator and denominator will be relatively prime. Claim: if d| n then exactly φ(d) of the denominators will be d. Since the claim is true (you will show this in an exercise; we also did this in class), and since every denominator will be a divisor of n it follows that din ф(d-n. nn'L Screen Shot 2019-03-28 at...
1. Solve the recurrence relation T(n) = 2T(n/2) + n, T(1) = 1 and prove your...
1. Solve the recurrence relation T(n) = 2T(n/2) + n, T(1) = 1 and prove your result is correct by induction. What is the order of growth? 2. I will give you a shortcut for solving recurrence relations like the previous problem called the Master Theorem. Suppose T(n) = aT(n/b) + f(n) where f(n) = Θ(n d ) with d≥0. Then T(n) is: • Θ(n d ) if a < bd • Θ(n d lg n) if a = b...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1],...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1], A[2], , Aln]. You'd like to output a two-dimensional n-by-n array B in which B[i, j] (for i <j) contains the sum of array entries Ali] through Aj]-that is, the sum A[i] Ai 1]+ .. +Alj]. (The value of array entry B[i. Λ is left unspecified whenever i >j, so it doesn't matter what is output for these values.) Here's a simple algorithm to...
You are given an algorithm that uses T(n) a n2b.3" basic operations to solve a problem...
You are given an algorithm that uses T(n) a n2b.3" basic operations to solve a problem of size n, where a and b are some real non-negative constants. Suppose that your machine can perform 400,000,000 basic operations per second (a) If a = b = 1, how long does it take for your algorithm to solve problems of size n = 10, 20, 50. For each size of n, include the time in seconds and also using a more appropriate...
Prove using mathematical induction that for every positive integer n, = 1/i(i+1) = n/n+1. 2) Suppose...
Prove using mathematical induction that for every positive integer n, = 1/i(i+1) = n/n+1. 2) Suppose r is a real number other than 1. Prove using mathematical induction that for every nonnegative integer n, = 1-r^n+1/1-r. 3) Prove using mathematical induction that for every nonnegative integer n, 1 + i+i! = (n+1)!. 4) Prove using mathematical induction that for every integer n>4, n!>2^n. 5) Prove using mathematical induction that for every positive integer n, 7 + 5 + 3 +.......
4. Suppose T (n) satisfies the recurrence equations T(n) = 2 * T( n/2 ) + 6 * n, n 2 We want to prove that T (n)-o(n * log(n)) T(1) = 3 (log (n) is log2 (n) here and throughout ). a. compute values in this table for T (n) and n*log (n) (see problem #7) T(n) | C | n * log(n) 2 4 6 b. based on the values in (a) find suitable "order constants" C and...
Exercise 1.6.4: Prove the following by induction: (a) “k - n(n+1)(2n +1) k= 1 (b) If n > 1, then 13-n is divisible by 3. (c) For n 3, we have n +4 <2". (d) For any positive integer n, one of n, n+2, and 11+ 4 must be divisible by 3. (e) For all n e N, we have 3" > 2n +1. ()/Prove that, for any x > -1 and any n e N, we have (1+x)" 21+1x.
Proposition 8. Σdno(d)= n. Proof. Consider the n rational numbers 1, 2, ,. Reduce each frac- tion to lowest terms. Then the numerator and denominator will be relatively prime. Claim: if d| n then exactly φ(d) of the denominators will be d. Since the claim is true (you will show this in an exercise; we also did this in class), and since every denominator will be a divisor of n it follows that din ф(d-n. nn'L Screen Shot 2019-03-28 at...
6. Consider the following basic problem. You're given an array A consisting of n integers A[1], A[2], , Aln]. You'd like to output a two-dimensional n-by-n array B in which B[i, j] (for i <j) contains the sum of array entries Ali] through Aj]-that is, the sum A[i] Ai 1]+ .. +Alj]. (The value of array entry B[i. Λ is left unspecified whenever i >j, so it doesn't matter what is output for these values.) Here's a simple algorithm to...
You are given an algorithm that uses T(n) a n2b.3" basic operations to solve a problem of size n, where a and b are some real non-negative constants. Suppose that your machine can perform 400,000,000 basic operations per second (a) If a = b = 1, how long does it take for your algorithm to solve problems of size n = 10, 20, 50. For each size of n, include the time in seconds and also using a more appropriate...
Prove using mathematical induction that for every positive integer n, = 1/i(i+1) = n/n+1. 2) Suppose r is a real number other than 1. Prove using mathematical induction that for every nonnegative integer n, = 1-r^n+1/1-r. 3) Prove using mathematical induction that for every nonnegative integer n, 1 + i+i! = (n+1)!. 4) Prove using mathematical induction that for every integer n>4, n!>2^n. 5) Prove using mathematical induction that for every positive integer n, 7 + 5 + 3 +.......
Most questions answered within 3 hours.
-
What's the streaming business's problem on the
horizon?
asked 13 minutes ago -
I need help with writing the conclusion for this online lab
report
Abstract
By testing the...
asked 26 minutes ago -
For the reaction 1N2+3H2-----> 2NH3, would the reaction rate
trend be: delta[NH3]/ delta t = -2...
asked 1 hour ago -
Within your current/past organization, identify a problem/issue
and format a design to address same. You may...
asked 43 minutes ago -
A sock stuck to the side of a clothes-dryer barrel has a
centripetal acceleration of 24...
asked 1 hour ago -
A perfect gas undergoes an isentropic process such that its
volume doubles. If the ratio of...
asked 2 hours ago -
list the elements in groups 3A to 6A in the same order as in the
periodic...
asked 2 hours ago -
Estimating effect size. Peng and Chen (2014)
evaluated effect size estimates for various tests. In their...
asked 2 hours ago -
Write a script in MySQL that creates and calls a stored
procedure name test. This procedure...
asked 2 hours ago -
If we test the following: H0: μ = 17
vs. H1: μ ≠ 17 and the...
asked 2 hours ago -
in the past year TVG had revenues of 3 million, cost
of goods sold of $25...
asked 2 hours ago -
4) In a polypeptide, which bond cannot rotate because of its
partial double bond character?
The...
asked 3 hours ago