Design an algorithm for computing√nfor any positive integer n. Besides assignment and comparison, your algorithm may...
Design an algorithm for computing√nfor any positive integer n. Besides assignment and comparison, your algorithm may only use the four basic arithmetical operations.
Homework Answers
Hey,
Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries
- Function sqrt(x)
- Define and initialize x0=1;
- Define and initialize prev=0;
- Define and initialize err=1;
- while(err>0.0001)
- prev=x0;
- x0=(0.5)*(prev+num/prev);
- if(x0>prev)
- err=x0-prev
- Else
- err=prev-x0;
- EndIf
- EndLoop
- RETURN x0
- EndFunction
Kindly revert for any queries
Thanks.
Add Answer to:
Design an algorithm for computing√nfor any positive integer n.
Besides assignment and comparison, your algorithm may...
a. Write a pseudocode for computing for any positive integer n Besides assignment and comparison, your...
a. Write a pseudocode for computing for any positive integer n Besides assignment and comparison, your algorithm may only use the four basic arithmetical operations. What is the time efficiency of your algorithm for the worst and best cases? Justify your answer. (The basic operation must be identified explicitly). Give one instance for the worst case and one instance for the best case respectively if there is any difference between the worst case and best case. Otherwise please indicate that...
1. Let m be a nonnegative integer, and n a positive integer. Using the division algorithm...
1. Let m be a nonnegative integer, and n a positive integer. Using the division algorithm we can write m=qn+r, with 0 <r<n-1. As in class define (m,n) = {mc+ny: I,Y E Z} and S(..r) = {nu+ru: UV E Z}. Prove that (m,n) = S(n,r). (Remark: If we add to the definition of ged that gedan, 0) = god(0, n) = n, then this proves that ged(m, n) = ged(n,r). This result leads to a fast algorithm for computing ged(m,...
Lower bound arguments. In class, we proved that any comparison-based algorithm that has to sort n...
Lower bound arguments. In class, we proved that any comparison-based algorithm that has to sort n numbers runs in Ω (nlogn) time. Let’s change the problem a bit. Suppose S[1. . . n] is a sorted array. We want to know if S contains some element x. a. How would you solve this problem and what is the running time of your algorithm? (Note: you can just say what algorithm you will use.) b. Show that any comparison-based algorithm(i.e., one...
Design and implement a Θ(n) algorithm that will simultaneously find the largest and second-largest elements (integers)...
Design and implement a Θ(n) algorithm that will simultaneously find the largest and second-largest elements (integers) in an array. Note that the second largest element should be distinctly smaller than the largest element. You should also adhere to the following restrictions. (1) You should traverse through the array ONLY ONCE. (2) The array could have both positive and negative elements. So, you should NOT initialize any temporary variables to very small negative values as part of your algorithm. (3) You...
(a) Let n be any positive integer. Briefly explain (no formal proofs) why n > 1...
(a) Let n be any positive integer. Briefly explain (no formal proofs) why n > 1 ≡ ¬(n = 1). (b) Recall that a positive integer p is prime iff there do not exist a positive integers n and m, both greater than 1, such that p = nm. (I.e., Prime(p) means ¬∃n ∃m (n > 1 ∧ m > 1 ∧ p = nm).) Give a formal proof of the following: for any prime p, any positive integers n...
Q18 12 Points For any positive integer n, let bn denote the number of n-digit positive...
Q18 12 Points For any positive integer n, let bn denote the number of n-digit positive integers whose digits are all 1 or 2, and have no two consecutive digits of 1. For example, for n - 3, 121 is one such integer, but 211 is not, since it has two consecutive 1 's at the end. Find a recursive formula for the sequence {bn}. You have to fully prove your answer.
The Collatz conjecture concerns what happens when we take any positive integer n and apply the...
The Collatz conjecture concerns what happens when we take any positive integer n and apply the following algorithm: if n is even 3 xn+1, if n is odd The conjecture states that when this algorithm is continually applied, all positive integers will eventually reach 1. For example, if n- 35, the sequence 1S 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4,2,'1 Write a C program using the fork) system call that generates this sequence in the...
6. Let n be any positive integer which n = pq for distinct odd primes p....
6. Let n be any positive integer which n = pq for distinct odd primes p. q for each i, jE{p, q} Let a be an integer with gcd(n, a) 1 which a 1 (modj) Determine r such that a(n) (mod n) and prove your answer.
This assignment will test your algorithm/logic development in which you will perform the sort function with some different characteristics.
This assignment will test your algorithm/logic development in which you will perform the sort function with some different characteristics. You will be required to ensure that your program meets the following requirements: i. Existence of an array which can accept an unknown number of positive integersii. ExistenceofafunctionwhichcanperformadifferentsortwheretheEvennumberswillappear first before the Odd numbers. In this sorted sequence, all the even numbers will appear first in descending order followed by the odd numbers (in the same order). You are only allowed to use one...
1. [10 marks] Modular Arithmetic. The Quotient-Remainder theorem states that given any integer n and a positive integer...
1. [10 marks] Modular Arithmetic. The Quotient-Remainder theorem states that given any integer n and a positive integer d there exist unique integers q and r such that n = dq + r and 0 r< d. We define the mod function as follows: (, r r>n = qd+r^0<r< d) Vn,d E Z d0 Z n mod d That is, n mod d is the remainder of n after division by d (a) Translate the following statement into predicate logic:...
a. Write a pseudocode for computing for any positive integer n Besides assignment and comparison, your algorithm may only use the four basic arithmetical operations. What is the time efficiency of your algorithm for the worst and best cases? Justify your answer. (The basic operation must be identified explicitly). Give one instance for the worst case and one instance for the best case respectively if there is any difference between the worst case and best case. Otherwise please indicate that...
1. Let m be a nonnegative integer, and n a positive integer. Using the division algorithm we can write m=qn+r, with 0 <r<n-1. As in class define (m,n) = {mc+ny: I,Y E Z} and S(..r) = {nu+ru: UV E Z}. Prove that (m,n) = S(n,r). (Remark: If we add to the definition of ged that gedan, 0) = god(0, n) = n, then this proves that ged(m, n) = ged(n,r). This result leads to a fast algorithm for computing ged(m,...
Q18 12 Points For any positive integer n, let bn denote the number of n-digit positive integers whose digits are all 1 or 2, and have no two consecutive digits of 1. For example, for n - 3, 121 is one such integer, but 211 is not, since it has two consecutive 1 's at the end. Find a recursive formula for the sequence {bn}. You have to fully prove your answer.
The Collatz conjecture concerns what happens when we take any positive integer n and apply the following algorithm: if n is even 3 xn+1, if n is odd The conjecture states that when this algorithm is continually applied, all positive integers will eventually reach 1. For example, if n- 35, the sequence 1S 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4,2,'1 Write a C program using the fork) system call that generates this sequence in the...
6. Let n be any positive integer which n = pq for distinct odd primes p. q for each i, jE{p, q} Let a be an integer with gcd(n, a) 1 which a 1 (modj) Determine r such that a(n) (mod n) and prove your answer.
1. [10 marks] Modular Arithmetic. The Quotient-Remainder theorem states that given any integer n and a positive integer d there exist unique integers q and r such that n = dq + r and 0 r< d. We define the mod function as follows: (, r r>n = qd+r^0<r< d) Vn,d E Z d0 Z n mod d That is, n mod d is the remainder of n after division by d (a) Translate the following statement into predicate logic:...
Most questions answered within 3 hours.
-
Explain why case-mix analysis should be performed by
health care facilities. List other types of analysis...
asked 2 minutes from now -
1.
Today Tomorrow
Price of Coke 1.90 2.10
Quantity of Pepsi 297 303
a. Write down...
asked 1 hour ago -
Fluorine-20 has a half-life of 11.0 s. If a sample initially
contains 36.0 μg of this...
asked 1 hour ago -
How many fissions take place per second in a 190-MW reactor?
Assume 200 MeV is released...
asked 2 hours ago -
IQ scores are normally distributed with a mean of 100 and a
standard deviation of 15....
asked 2 hours ago -
You are to assess the biomechanics of a male’s arm using his
bicep to hold a...
asked 4 hours ago -
What is the maximum number of grams of N-acetyl-p-toluidine can
be prepared from 70. milliliters of...
asked 5 hours ago -
A researcher is using a two-tailed hypothesis test with α =
.05 to evaluate the effect...
asked 7 hours ago -
Two long, straight wires are parallel and 8.5 cm apart. The top
wire carries a current...
asked 9 hours ago -
Three arguments used to promote trade barriers are the national
security argument, the infant-industry argument, and...
asked 9 hours ago -
Question 3:
Percentage of Completion
Method (12 marks) On January 1, 2017, Eagle Construction Ltd.
started...
asked 9 hours ago -
A company purchased a tract of land for its natural resources at
a cost of $2,042,900....
asked 9 hours ago