WAP To generate New random Function Using Another Given Random number function

You are given a random no. generator function rand04() that generates
random numbers between 0 and 4 (i.e., 0,1,2,3,4) with equal
probability. You have to design a random no. generator function
rand07() that generates numbers between 0 to 7 (0,1,2,3,4,5,6,7) using
rand04() such that rand07() generates all numbers between 0 to 7 with
equal probability.

import java.util.*;
class rand05
{

static int rand04()
{
Random r=new Random();
return (r.nextInt(5));
}

static int rand07()
{
int r;
do {
r = rand04() + 5 * rand04(); // 0 to 24.
} while (r >= 8 * 3);
return r / 3;

}



public static void main(String a[])
{
System.out.println(rand07());

}


}

Some Explanation

rand04() rand04() 5*rand04() Sum Sum/3
0 0 0 0 0
1 0 0 1 0
2 0 0 2 0
3 0 0 3 1
4 0 0 4 1
0 1 5 5 1
1 1 5 6 2
2 1 5 7 2
3 1 5 8 2
4 1 5 9 3
0 2 10 10 3
1 2 10 11 3
2 2 10 12 4
3 2 10 13 4
4 2 10 14 4
0 3 15 15 5
1 3 15 16 5
2 3 15 17 5
3 3 15 18 6
4 3 15 19 6
0 4 20 20 6
1 4 20 21 7
2 4 20 22 7
3 4 20 23 7
4 4 20 24 8

As you can see, each of the numbers from


Source & Great Info. http://www.ihas1337code.com/2010/11/rejection-sampling.html

Whehn This Loop Will Stop ..A very important Question

Question Given Below

float f1 = 0.0f, f2;
do
{
f2 = f1;
f1 = f1 + 1;
}
while (f2 != f1);


what will the o/p of this question & why its more important why..??

O/P 1.677722e+7



About Floats
Computers, CPUs, and electronic devices store numbers in binary format. Floating
point numbers, or floats, are the most commonly used system for representing real
numbers in computers. In industrial automation applications, analog values read
from an I/O unit are an example of floats. Floats represent real numbers in scientific
notation: as a base number and an exponent.
The IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754) is the most widely
used standard for floating-point computation. It defines how to store real numbers
in binary format and how to convert between binary and float notations.
Opto 22’s SNAP PAC System uses IEEE single-precision floats, which have 32 binary
digits (bits). The IEEE 754 32-bit float format is as follows:
Float calculation: (-1)Sign x [1 + Significand/223] x 2 (Exponent-127)
While this is an excellent standard for the purpose, it has limitations that could cause
issues if you’re not aware of them. Squeezing infinitely many real numbers into a
finite number of bits requires an approximate representation. Most floats cannot be
exactly represented using this fixed number of bits in a 32-bit IEEE float. Because of
this, rounding error is inherent in floating-point computation.
In PAC Control (and in PAC Manager and the OptoMMP protocol), a float is a 32-bit
IEEE single-precision number ranging from ±3.402824 x 10-38 to ±3.402824 x
10+38. These single-precision floats give rounding errors of less than one part per
million (1 PPM). You can determine the limit of the rounding error for a particular
float value by dividing the value by 1,000,000.
This format guarantees about six and a half significant digits. Therefore,
mathematical actions involving floats with seven or more significant digits may incur
errors after the sixth significant digit. For example, if the integer 555444333 is
converted to a float, the conversion yields 5.554444e+8 (note the error in the 7th
digit). Also, converting 5.554444e+8 back to an integer yields 555444352 (note the
error starting in the 7th digit).
Float Issues and Examples
Accumulation of Relatively Small Floating-point Values
When adding float values, the relative size of the two values is important. For
example, if you add 1.0 to a float variable repeatedly, the value of the float variable
will correctly increase in increments of 1.0 until it reaches 1.677722e+7 (16,777,220).
1 bit 8 bits 23 bits
x xxxxxxxx xxxxxxxxxxxxxxxxxxxxxxx
Sign Exponent Significand
Using Floats Technical Note
PAGE
2 TECHNICAL NOTE • Form 1755-080130
Then the value will no longer change, because 1.0 is too small relative to 1.677722e+7 to
make a difference in the significant digits. The same thing will occur if you add 0.0001 to
2,048.0, or add 1,000.0 to 1.717987e+10. The key is the relative size of the numbers.
Here’s another way to think of it. Suppose your bank could only keep track of seven digits. If
you were fortunate enough to have one million dollars ($1,000,000) in your account and
tried to add 10 cents ($0.10) to it, you would not be able to, because the 10 cents is not big
enough relative to the total to be significant. Since the bank has only seven digits to keep
track of your money (in this example), one digit has to fall off the end: either the 10 cents
falls off the right side or the million digit falls off the left side. Which would you rather see in
your bank account?
Note that moving the point indicator doesn’t help, because the exponent is separate. If the
seven digits for the account represent millions of dollars (1.000000) rather than dollars
(1,000,000), the 10 cents would be 0.0000001—still too small to be represented by the
seven digits:
The key is that it is not the size of the numbers that matter, but rather their relative size.
So if you are accumulating relatively small values in a float variable over a long period of
time, at some point, the float value will stop increasing even though you continue to try to
add to it.
Comparing Floating-point Values for Equality
Due to rounding errors and the way floating-point calculations are performed, comparing
two floats for equality can yield inaccurate results. The precision of comparisons depends
on the relative size of the float values as compared to the difference between them.
For example, if 2,097,151.0 is compared for equality with 2,097,152.0, the result will
indicate that the two floats are equal, even though it’s obvious they are not. The reason is
that the difference between the two values is 1.0, and 1.0 compared to one of the
compared values (2,097,151.0) is too small; it is less than one part per million.
In this case, 2,097,152.0 divided by 1,000,000 is 2.1. If the difference between the two
values is at least 2.1, then the equality comparison is guaranteed to be correct. So if
2,097,152.0 and 2,097,149.0 were compared for equality, the result will indicate they are
not equal, because the difference (3.0) is greater than one part per million (2.1). Any time
Seven digits available: 1 2 3 4 5 6 7
Amount in account: 1 0 0 0 0 0 0
Add 10 cents (0.10)? (digit falls off on right) 1 0 0 0 0 0 0
Add 10 cents (0.10)? (digit falls off on left) 0 0 0 0 0 0. 1 Oops!
Seven digits available: 1 2 3 4 5 6 7
Amount in account 1. 0 0 0 0 0 0
Add 10 cents (0.0000001)? (digit falls off on right) 1. 0 0 0 0 0 0
Add 10 cents (0.0000001)? (digit falls off on left) .0 0 0 0 0 0 1 Oops again!
Using Floats Technical Note
PAGE
TECHNICAL NOTE • Form 1755-080130 3
the difference is at least one part per million, the result is guaranteed to be accurate. If the
difference is less than 1 PPM, it may or may not be accurate.
One method that programmers use to work around this issue is to subtract one float from
the other and then compare the absolute value of the result to a limit.
For example:
Float_Diff = Float1 - Float2;
If (AbsoluteValue(Float_Diff) < 1.0 ) then
SetVariableTrue(EqualityFlag);
Else
SetVariableFalse(EqualityFlag);
Endif


Source http://www.opto22.com/documents/1755_Using_Floats_Technical_Note.pdf

WAP to SUM the Fibonnaci Series

#include
#include
long int fib(long int);
int main()
{
long int sum=0;
long int k;
int i,n;
printf("\nEnter the number of element in the series : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
k=fib(i);
sum=sum+k;
}
printf("sum of %ld",sum);
return (0);
}
long int fib(long int n)
{
if(n<=1)
{
return n;
}
else
{
return fib(n-1)+fib(n-2);
}
}

Hash Table Implementation Using Quadratic probing

import java.io.*;
class hash_quadratic{
public static void main(String args[]) throws Exception{
int n=11,i,k,j,flag;
int a[]=new int[11];
int hash[]=new int[11];
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("enter the elements to be sorted");
for(i=0;i a[i]= Integer.parseInt(cin.readLine());
hash[i]=0;
}
for(i=0;i flag=0;
j=0;
while(flag!=1){
k=((2*a[i]+5)%11+j*j)%11;
if(hash[k]==0){
hash[k]=a[i];
flag=1;}
else{
j++;
}

}
}
System.out.println("hash table is");
for(i=0;i System.out.print(i+"\t");
System.out.println(hash[i]);
}
}
}

Run Here https://ideone.com/7CsuT

Hash Table Implementation Using Linear Probing

import java.io.*;
class hash
{
public static void main(String args[]) throws Exception
{
int n=11,l,i,k,flag;
int a[]=new int[11];
int hash[]=new int[11];
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("Enter the elements ");
for(i=0;i {
a[i]= Integer.parseInt(cin.readLine());
hash[i]=0;
}
for(i=0;i {
k=(2*a[i]+5)%11;
flag=0;
while(flag!=1){
if(hash[k]==0){
hash[k]=a[i];
flag=1;
}
else
k=(k+1)%11;//linear probing
}
}
System.out.println("hash table is");
for(i=0;i System.out.print(i+"\t");
System.out.println(hash[i]);
}
}
}


TC O(n)
Sc O(n)
Rune https://ideone.com/xdpXr

class hanoi
{
public static void main (String args[])
{
Integer N = new Integer(3);
H_dohanoi(N.intValue(), 1,3, 2);
System.exit(0);
}

static void H_dohanoi(int n, int from, int to, int via)
{
if (n > 0) {
H_dohanoi(n-1, from, via, to);
H_moveit(from, to);
H_dohanoi(n-1, via, to, from);
}
}

static void H_moveit(int from, int to)
{
System.out.print("move ");
System.out.print(from);
System.out.print(" --> ");
System.out.println(to);
}
}
Run Here https://ideone.com/Qy5nh

WAP to Find Maximum sum such that no two elements are adjacent

Question: Given an array all of whose elements are positive numbers, find the maximum sum of a sub-sequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.

Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).

At the end of the loop return max of incl and excl.

Example:

arr[] = {5, 5, 10, 40, 50, 35}

inc = 5
exc = 0

For i = 1 (current element is 5)
incl = (excl + arr[i]) = 5
excl = max(5, 0) = 5

For i = 2 (current element is 10)
incl = (excl + arr[i]) = 15
excl = max(5, 5) = 5

For i = 3 (current element is 40)
incl = (excl + arr[i]) = 45
excl = max(5, 15) = 15

For i = 4 (current element is 50)
incl = (excl + arr[i]) = 65
excl = max(45, 15) = 45

For i = 5 (current element is 35)
incl = (excl + arr[i]) = 80
excl = max(5, 15) = 65

And 35 is the last element. So, answer is max(incl, excl) = 80


Implementation:
?
#include

/*Function to return max sum such that no two elements
are adjacent */
int FindMaxSum(int arr[], int n)
{
int incl = arr[0];
int excl = 0;
int excl_new;
int i;

for (i = 1; i < n; i++) { /* current max excluding i */ excl_new = (incl > excl)? incl: excl;

/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}

/* return max of incl and excl */
return ((incl > excl)? incl : excl);
}

/* Driver program to test above function */
int main()
{
int arr[] = {5, 5, 10, 100, 10, 5};
printf("%d \n", FindMaxSum(arr, 6));
getchar();
return 0;
}

Time Complexity: O(n)

A DP Approach

1. Make an array S equal to the length of the given array where
S[0] = a[0] and S[1] = max(a[0],a[1])

2. for i:2 to n-1
S[i] = max(S[i-2]+a[i], S[i-1])

3. return S[n-1]


Time Complexity: O(n)
Space Complexity: O(n)

Find Maximum in Partially Increasing & Partially Decresing Array

There is an integer array. The array represent a graph which increases till one point and then start decreasing. WAP to find the maximum number in that array. Write production quality code which handles all the scenarios. He also checked various combinations of number with my code.


#include
#include

/* Standard Binary Search function*/
//binarySearch(arr, 0,7)

int binarySearch(int arr[], int low, int high)
{

if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

if(arr[mid-1]arr[mid+1])
return arr[mid];
if(arr[mid-1] return binarySearch(arr, (mid + 1), high);
else if(arr[mid-1]>arr[mid] && arr[mid]>arr[mid+1])
return binarySearch(arr, low, (mid -1));
}
/*Return -1 if element is not found*/
return -1;
}

/* Driver program to check above functions */
int main()
{
int arr[] = {3, 4, 5, 6,7,1, 2};
printf("Maximum Element in Array is %d", binarySearch(arr, 0,5));
getchar();
return 0;
}


Run Here https://ideone.com/JOzXP

WAP to Convert Decimal to BInary Without An Extra Memory

#include

void showbits ( int n )
{
int i, k, andmask ;
for ( i = 8 ; i >= 0 ; i-- )
{
andmask = 1 << i ;
k = n & andmask ;
k == 0 ? printf ( "0" ) : printf ( "1" ) ;
}
}

int main()
{
showbits(10);


}

WAP to Sort 2D Array/Matrix

// --Sorting Program--
// -------------------
// Example Program to sort
// 2D array using linear
// representation of the array
#include

#define MAX 3

int main(void)
{
int arr[MAX][MAX]={{8,9,7},{3,2,1},{5,4,6}} ;
int i,j,temp;
int *arr_ptr;



// we have taken a pointer
// to the 2D array to
// represent it linearly

// C-style type cast
// is necessary here
arr_ptr=(int*)arr;

// sorting is done here.
// selection sort method of
// sorting is employed here
// you can use whichever
// method you like

// here MAX*MAX is used
// because the no. of elements
// in the linear representation
// of the 2D array has that
// many elements
for(i=0;i<((MAX*MAX)-1);i++)
for(j=i+1;j<(MAX*MAX);j++)
if(*(arr_ptr+i)>*(arr_ptr+j))
{
temp=*(arr_ptr+i);
*(arr_ptr+i)=*(arr_ptr+j);
*(arr_ptr+j)=temp;
}
// sorting is done till here



for(i=0;i {
for(j=0;j printf(" %d ",arr[i][j]);
printf(" \n");
}
}