Question

Design a recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns...

Design a recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns the total number of 1’s in n’s binary representation. Note that the input is n, not its binary representation. For example, A(9) should return 2 as 9’s binary representation is 1001, while A(7) should return 3 since 7 is 111 in binary. Note that your algorithm should have a running time of O(log n). Justify your answer. You need to do the following: (1) give a description of your algorithm in English or high-level pseudo-code; and (2) give its analysis, ie. recurrence equation and its solution.

Homework Answers

Answer #1

Recursive divide-and-conquer algorithm A(n) that takes an integer input n ≥ 0, and returns the total number of 1’s in n’s binary representation.

int A(int n)
{
   if(n==0)
   {
       return 0;
   }
   if(n%2==0)
       return 0 + A(n/2);
   return 1 + A(n/2);
}

The algorithm checks keeps on checking the last bit of the number, if the number is odd then add 1 to count and right n by 1 bit, i.e dividing n by 2 until n is zero, and call the A function after each shift.

The recurrence relation is

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1]...
Consider the following recursive algorithm. Algorithm Test (T[0..n − 1]) //Input: An array T[0..n − 1] of real numbers if n = 1 return T[0] else temp ← Test (T[0..n − 2]) if temp ≥ T[n − 1] return temp else return T[n − 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm’s basic operation count and solve it.
Divide-and-Conquer technique is famous for providing O(n log n) solutions for problems with O(n2) straight forward...
Divide-and-Conquer technique is famous for providing O(n log n) solutions for problems with O(n2) straight forward solutions. One of those problems is the “Maximum Subarray Sum” or “Maximum Value Contiguous Subsequence": Given a sequence of n numbers A[0 ... n-1], give an algorithm for finding a contiguous subsequence A[i ... j], for which the sum of elements in this subsequence is the maximum we can get by choosing different i or j.   For example: the maximum subarray sum for the...
A speedy Decrease-and-Conquer search. Use your newly acquired knowledge of “Decrease-and-Conquer” algorithm design strategy to design...
A speedy Decrease-and-Conquer search. Use your newly acquired knowledge of “Decrease-and-Conquer” algorithm design strategy to design a O( n ) algorithm to search for a given number in an n × n matrix in which every row and every column in this matrix is sorted in increasing order Write your algorithm as an elegant java method named findElement(int [][] arr, int element) that returns the index of that element in the array as a small int array made of 2...
Write a recursive method that takes as input a string s and returns a list containing...
Write a recursive method that takes as input a string s and returns a list containing all the anagrams of the string s. An anagram is a word formed by rearranging the letters of a different word. For example, the word ‘binary’ is an anagram of ‘brainy’. Note that the output list should not contain duplicates. Java
design an efficient algorithm that, on input a set of n real numbers {x1, . ....
design an efficient algorithm that, on input a set of n real numbers {x1, . . . , xn}, outputs all distinct numbers in the set. For example, if your input is {5, 10, 9, 10, 8, 5, 12, 11, 12, 9, 7, 6, 8, 5}, then you should output {5, 10, 9, 8, 11, 12, 7, 6} (any ordering of these number is acceptable).
Design an algorithm (write in pseudo code) which takes less than Θ(n) to search an entry...
Design an algorithm (write in pseudo code) which takes less than Θ(n) to search an entry (name of a person) in a telephone directory. Analyze this algorithm for its worst-case input situation. Make necessary assumptions to simplify your comparisons. If you don’t know what is a telephone directory, check out this link https://en.wikipedia.org/wiki/Telephone_directory
Write a recursive method public static int sumEveryOther(int n) that takes a positive int as an...
Write a recursive method public static int sumEveryOther(int n) that takes a positive int as an argument and returns the sum of every other int from n down to 1. For example, the call sumEveryOther(10) should return 30, since 10 + 8 + 6 + 4 + 2 = 30. The call sumEveryOther(9) should return 25 since 9 + 7 + 5 + 3 + 1 = 25. Your method must use recursion.
A Queue is a linked list with pointers to both the head of the list as...
A Queue is a linked list with pointers to both the head of the list as well as the tail (or the last element) of the list. Given a queue Q, Q.head gives the head of the queue and Q.tail gives the tail of the queue. Give O(1) time algorithms for the following tasks. Enqueue • Input: A queue Q of distinct integers and a queue element a not in Q. 1 • Output: Q with the element a added...
The main goal is to implement two recursive methods, each is built to manipulate linked data...
The main goal is to implement two recursive methods, each is built to manipulate linked data structures. To host these methods you also have to define two utterly simplified node classes. 1.) Add a class named BinaryNode to the project. This class supports the linked representation of binary trees. However, for the BinaryNode class Generic implementation not needed, the nodes will store integer values The standard methods will not be needed in this exercise except the constructor 2.) Add a...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT