Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i...

Consider the following algorithm. Algorithm Mystery(n) //Input: A nonnegative integer n S ← 0 for i ← 1 to n do S ← S + i * i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

Solutions

Expert Solution

Answer:----------

venereology answered 5 months ago

Next > < Previous

Related Solutions

A Mystery Algorithm Input: An integer n ≥ 1 Output: ?? Find P such that 2...

A Mystery Algorithm Input: An integer n ≥ 1 Output: ?? Find P such that 2 P is the largest power of two less than or equal to n. Create a 1-dimensional table with P +1 columns. The leftmost entry is the Pth column and the rightmost entry is the 0th column. Repeat until P < 0 If 2 P ≤ n then put 1 into column P set n := n − 2 P Else put 0 into column...

A Mystery Algorithm Input: An integer n ≥ 1 Output: ?? Find P such that 2^p...

A Mystery Algorithm Input: An integer n ≥ 1 Output: ?? Find P such that 2^p is the largest power of two less than or equal to n. Create a 1-dimensional table with P +1 columns. The leftmost entry is the Pth column and the rightmost entry is the 0th column. Repeat until P < 0 If 2^p≤n then put 1 into column P set n := n - 2^p Else put 0 into column P End if Subtract 1...

Consider the following program specification: Input: An integer n > 0 and an array A[0..(n –...

Consider the following program specification: Input: An integer n > 0 and an array A[0..(n – 1)] of n integers. Output: The largest index b such that A[b] is the largest value in A[0..(n – 1)]. For example, if n = 10 and A = [ 4, 8, 1, 3, 8, 5, 4, 7, 1, 2 ] (so A[0] = 4, A[1] = 8, etc.), then the program would return 4, since the largest value in A is 8 and...

a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based...

a. Design a recursive algorithm for computing 3n for any nonnegative integer n that is based on the formula 3n = 3n−1 + 3n−1 + 3n−1 b. Set up a recurrence relation for the number of additions made by the algorithm and solve it. c. Draw a tree of recursive calls for this algorithm and count the number of calls made by the algorithm. d. Is it a good algorithm for solving this problem?

Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:

USE Coral Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x / 2Note: The above algorithm outputs the 0's and 1's in reverse order.Ex: If the input is 6, the output is:011(6 in binary is 110; the algorithm outputs the bits in reverse).

Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:

In Java Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x / 2Note: The above algorithm outputs the 0's and 1's in reverse order.Ex: If the input is:6the output is:0116 in binary is 110; the algorithm outputs the bits in reverse.

[C] Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:

6.19 LAB: Convert to binary - functionsWrite a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x / 2Note: The above algorithm outputs the 0's and 1's in reverse order. You will need to write a second function to reverse the string.Ex: If the input is:6the output is:110Your program must define and call the following two functions. The IntegerToReverseBinary function...

(Python) Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:

In Python8.21 Program: Convert to binary. Sections 2.7, 3.8, 5.2. Functions.Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x // 2Note: The above algorithm outputs the 0's and 1's in reverse order. You will need to write a second function to reverse the string.Your program must define and call the following two functions. The function integer_to_reverse_binary() should return...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns,...

Write, in Python, a recursive algorithm that takes, as input, a positive integer n, and returns, as output, the sum of the first n positive odd integers. Your solution should be recursive, and it should not contain any "for" loops or "while" loops.

rogram that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary.

Write a program that takes in a positive integer as input, and outputs a string of 1's and 0's representing the integer in binary. For an integer x, the algorithm is:As long as x is greater than 0 Output x % 2 (remainder is either 0 or 1) x = x // 2Note: The above algorithm outputs the 0's and 1's in reverse order. You will need to write a second function to reverse the string.Ex: If the input is:6the output is:110Your program must define and call the following two functions. The function integer_to_reverse_binary() should return a string of 1's...

Subjects