1. Write a recursive method using Java syntax that returns the number of 1s in t
ID: 664585 • Letter: 1
Question
1. Write a recursive method using Java syntax that returns the number of 1s in the binary representation of a non-negative integer N. Clearly indicate your base case(s).
[ The signature of the method is as follows: int NumberOfOnes(long N) ]
2. Consider the following algorithm for searching an unsorted array: If the size of the array is 1, then check if it contains the element to be searched. Otherwise, divide the entire array into two halves, and recursively search both halves. Is the actual running time of this algorithm likely to be better than a sequential search (which searches an item by scanning the entire array one item at a time)? Justify your answer.
3.Is it possible to sort four numbers A, B, C, D using at most five comparisons? If yes, then describe the steps to do that. If no, then clearly justify (with detailed explanation) why it is not possible to do so.
4. Indicate runtime complexities in terms of Big-Oh for the following scenarios:
(i) Insertion sort applied on a collection where all values are equal
(ii) Bubble sort applied on a collection where the items are already in sorted order
(iii) Merge sort applied on a collection where the items are already sorted in opposite order
Explanation / Answer
1.
public class recOnes{
public static int countOnes (int n)
{
int ones;
if (n==0)
{
> return ones;
}
else if (n%2==0)//n is even
{
> return ones;
}
else // n is odd
{
countOnes((n-1)/2);
return ones;
}
}
public static void main(String[]args)
{
int n;
n=Integer.parseInt(args[0]);
//countOnes(n);
System.out.println("The number of Ones are "+ countOnes(n));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.