1.solve the difference equation: T(N)=T(N/7)+C, where C is constant. (solve all
ID: 3671682 • Letter: 1
Question
1.solve the difference equation: T(N)=T(N/7)+C, where C is constant. (solve all in algorithms)
2.Bitwise computation
a. write a function, which given a positive integer,X,to count how many bits of X are 1's. The function runs in (k)time, where k is the number of 1-bits in X. It mustn't use any lookup.
b. write an infinite WHILE loop so that a variable, X , will iterate its value from 4 to 1, i.e., 4->3->2->1->4->3->2->1->, and repeat.....
3. Heap
a. write the code to transform an array of N integers, A[ 1..N ], into a heap
Explanation / Answer
2.
public static int getSetBits(int num) {
int count = 0;
while (num > 0) {
if (num % 2 != 0)
count++;
num = num / 2;
}
return count;
}
b.
int count = 4;
while(true){
System.out.println(count--);
if(count == 0){
count = 4;
}
}
3.)
package com.home.heap;
public class HeapSort {
private static int N;
private static boolean asc = false;
public static void main(String[] args) {
int arr[] = { 1, 3, 5, 7, 8, 9, 4, 6, 3, 10, 25, 31, 12 };
heapSort(arr);
boolean isFound = false;
int findElement = 6;
for(int i = 10; i > 0; i--){
if(findElement == arr[i]){
System.out.println(1+i);
isFound = true;
}
}
if(!isFound){
System.out.println(0);
}
}
public static void heapSort(int[] arr) {
heapify(arr);
for (int i = N; i > 0; i--) {
swap(arr, 0, i);
N = N - 1;
if (asc)
maxHeap(arr, 0);
else
minHeap(arr, 0);
}
}
private static void heapify(int[] arr) {
N = arr.length - 1;
for (int i = N / 2; i >= 0; i--) {
if (asc)
maxHeap(arr, i);
else
minHeap(arr, i);
}
}
private static void maxHeap(int[] arr, int i) {
int max = i;
int left = i * 2;
int right = i * 2 + 1;
if (left <= N && arr[left] > arr[max]) {
max = left;
}
if (right <= N && arr[right] > arr[max]) {
max = right;
}
if (max != i) {
swap(arr, max, i);
maxHeap(arr, max);
}
}
private static void minHeap(int[] arr, int i) {
int min = i;
int left = i * 2;
int right = i * 2 + 1;
if (left <= N && arr[left] < arr[min]) {
min = left;
}
if (right <= N && arr[right] < arr[min]) {
min = right;
}
if (min != i) {
swap(arr, min, i);
minHeap(arr, min);
}
}
public static void swap(int[] arr, int pos1, int pos2) {
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
}
Sorry I won't be able to answer 1st question.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.