Question

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.

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

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
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 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 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, . . . , 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 (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
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 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 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 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 3 minutes ago

asked 4 minutes ago

asked 14 minutes ago

asked 15 minutes ago

asked 45 minutes ago

asked 49 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago