CodeWordBlog

Sorting by Selection

2011-08-10T14:19:00.025+05:30

Here explain sorting of random ordered n integers in to ascending order using Selection. Firstly look at unsorted and sorted arrays It is simple and basic algorithm with simple two steps.

Comparing sorted and Unsorted arrays we can see that it can be done using following steps

Find the smallest element in unsorted array .
Place it (smallest element ) in position a[0] .

This process is shown in figure below.

//This code is for sort first element//

Min = a[0];

     
for(j=1;j<=n;j++){

 if(a[j]<min){

 min
= a[j];}}

 a[0]=
min;

From the figure we can see that 3 is to be selected as smallest element and placed into a[0] .But the problem is 20 is missing that was in previous a[0] position.To avoid this problem we will save the element 20 before 3 placing into a[0]. It can done with temporary variable. After placing 3 into a[0], 20 from temporary variable need placed into a[6] which is previous position of 3. Now we successfully sort the first element. Figure illustrate the sorted and unsorted parts. We don't want consider sorted part then. In unsorted part we need to do same process again and again. how can we write general code?.ok..Before general code just look the figure that an array is sorted by selection in step by step. We can easily grasp the algorithm. Also from figure we can see that the array taking 7 steps to sort 8 element array.So in general case we need (n-1) iteration to sort n element array.

Algorithm Description: While there are still elements in the unsorted part of the array do

1. Find the minimum and place it as first element in unsorted part of array a[n].

2. Exchange the min in the unsorted of the array with the first element a[i] in the unsorted array.

Implementation in C:

for(i=0;i<=n-2;i++){

min=a[i];

for(j=i+1;j<=n;j++){

if(a[j]<min){

min=a[j];

}

a[i]=min; }}

Google page rank algorithm

2011-08-08T08:11:00.001+05:30

The original PageRank algorithm was described by Lawrence Page and Sergey Brin in several publications. It is given by
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
where

	PR(A) is the PageRank of page A,
	PR(Ti) is the PageRank of pages Ti which link to page A,
	C(Ti) is the number of outbound links on page Ti and
	d is a damping factor which can be set between 0 and 1.

Algorithm to find smallest divisor of an integer

2011-08-06T07:18:00.000+05:30

To find smallest divisor of an integer n is very straight forward. Just take the numbers 2, 3, 4, …,n and divide n with each of number in ascending order. But not efficient method, because it need more iteration ( loops) .

To efficiently calculate this problem we must reduce the loops by various techniques. And are follows.

· All exact divisors of an integer are paired. What it means?. Nothing !. for example an integer 24 have following divisors 2, 3, 4, 6, 8, 12. And each divisor have pair.

Here 2 and 12 are paired. In other word they are linked because

24/2 = 12 ;

2, 12 are smaller and bigger factors respectively .

Same way 3 and 8 are paired, i.e. (24/3 = 8;) and so on.

Smaller factor	Bigger factor
2	12
3	8
4	6

Here we can see that smallest divisor 2 is paired with largest divisor 12. 2^nd smallest divisor is paired with 2^nd largest divisor. And so on . if the integer is 36 we can see divisor 6 is paired with 6 itself.

In general case we have to consider only less than or equal to biggest smaller divisor, now the problem!.how can we take that limit?.simple take √n, all smaller divisors of an integer are less √n.

· If n is an even number then its smallest divisor is 2. Now we need consider only odd numbers. If we get n is the smallest divisor of n then it’s a prime ,i.e. one is smallest divisor.

Algorithm steps:

1. Establish the integer n

2. If n is even then 2 is smallest divisor.

3. Else

a. Compute r = √n;

b. Initialize divisor d = 3;

c. While not an exact divisor and r ≠ √n

i. Generate next divisor d in odd sequence by d = d +2;

d. If d is exact divisor and d ≠ n, then d is the smallest divisor of n

Else n is prime

Counting

2011-08-01T06:57:00.000+05:30

Problem

Given a set of n students ‘s examination marks (in range 0 to100) make account of number of students that passed in the examination. A pass is awarded for all marks of 50 and above.

Algorithm development

Counting mechanism are very frequently used in computer algorithms. Generally a count must be made of number of item in a set which possess some particular property or which satisfy some particular condition or conditions. This class problem is typified by the “examination marks” problem.

As starting point for developing computer algorithm for this problem we can consider how we might solve a particular example by hand.

Suppose that we are given set of marks

55, 42, 77, 29, 57, 89

To make the count of passes for this set we can start at the left , examine the first mark (55), see if it is ≥50,and remember that one student has passed so far. The second mark is then examined and no adjustment is made to the count . when we arrive at the third mark we is it is ≥50 and so we add one to our previous count. The process continues in similar manner until all marks have been tested.

In more detail we have:

Order in which marks are examined	Marks	Counting details for passes
	55	Previous count = 0 current count = 1
	42	Previous count = 1 current count = 1
	77	Previous count = 1 current count = 2
	63	Previous count = 2 current count = 3
	29	Previous count = 3 current count = 3
	57	Previous count = 3 current count = 4
	89	Previous count = 4 current count = 5

After each mark has been processed the current count reflect the no of students that have passed in the marks list so far encountered

We must now ask, how can the counting be achieved ? from our example of above we see that every time we need increase the count we build on the previous value. That is

Current _count = previous_count +1

When for example we arrive at mark 57, we have

Previou_count = 3

Current_count therefore becomes 4. This means that when ever a new current_count is generated it must then assumed the role of previous_count before the next mark is considered. The two step in this process can be represented by

Current_count = previous_count + 1

previous_count = Current_count

algorithm description

1. Prompt then read the number of marks to be processed.

2. Initialize the count to zero.

3. While there are still marks to be processed repeatedly do

a. Read next mark,

b. If it is pass (i.e. ≥50) then add one to count.

4. Write out total number of passes.

Counting Sort

2011-07-30T11:12:00.000+05:30

Counting sort assumes that each of the elements is an integer in the range 1 to k, for some integer k. When k = O(n), the Counting-sort runs in O(n) time. The basic idea of Counting sort is to determine, for each input elements x, the number of elements less than x. This information can be used to place directly into its correct position. For example, if there 17 elements less than x, than x belongs in output position 18.

In the code for Counting sort, we are given array A[1 . . n] of length n. We required two more arrays, the array B[1 . . n] holds the sorted output and the array c[1 . . k] provides temporary working storage.

COUNTING_SORT (A, B, k)

1. for i ← 1 to k do

2. c[i] ← 0

3. for j ← 1 to n do

4. c[A[j]] ← c[A[j]] + 1

5. //c[i] now contains the number of elements equal to i

6. for i ← 2 to k do

7. c[i] ← c[i] + c[i-1]

8. // c[i] now contains the number of elements ≤ i

9. for j ← n downto 1 do

10. B[c[A[i]]] ← A[j]

11. c[A[i]] ← c[A[j]] - 1

Each line below shows the step by step operation of counting sort.

Analysis

The loop of lines 1-2 takes O(k) time
The loop of lines 3-4 takes O(n) time
The loop of lines 6-7 takes O(k) time
The loop of lines 9-11 takes O(n) time

Therefore, the overall time of the counting sort is O(k) + O(n) + O(k) + O(n) = O(k + n)

In practice, we usually use counting sort algorithm when have k = O(n), in which case running time is O(n).

The Counting sort is a stable sort i.e., multiple keys with the same value are placed in the sorted array in the same order that they appear in the input array.

Suppose that the for-loop in line 9 of the Counting sort is rewritten:

9 for j ← 1 to n

then the stability no longer holds. Notice that the correctness of argument in the CLR does not depend on the order in which array A[1 . . n] is processed. The algorithm is correct no matter what order is used. In particular, the modified algorithm still places the elements with value k in position c[k - 1] + 1 through c[k], but in reverse order of their appearance in A[1 . . n].

Note that Counting sort beats the lower bound of Ω(n lg n), because it is not a comparison sort. There is no comparison between elements. Counting sort uses the actual values of the elements to index into an array.

Algorithm to Generate Prime Numbers

2011-07-25T16:02:00.000+05:30

Algorithm Description

1. Initialize and write out the first three primes . Also initialize the square of the 3^rd prime.

2. Initialize x to 5.

3. While x less than n do

a. Get next x value excluding multiple of 2 and 3

b. If not past end of multiple then

i. If x≥ square of largest prime then

1. Include next prime multiple as its square,

2. Update square by squaring next prime > √x.

c. While have not established x is non prime with valid prime multiples do

i. While current prime multiple is less than x ,increment by current prime value doubled,

ii. Do prime test by comparing x with current multiple;

d. If current x prime then

i. Write out x and if it is less than √n store it

Find largest number in a list

2011-07-24T21:33:00.000+05:30

Algorithm

Step 1: Establish an array a[0],a[1],….a[N-1] where n≥1.

Step2: Set temporory largest to first array element. Ie a[0].

Step3: While less than N array elements have been considered do

If next element is greater

than current maximum large then assign it to large

Step4: Return maximum large for the array of n elements

C implementation

#include<stdio.h>

int main(){

int a[50],size,i,big;

printf("\n Enter the size of the array: ");

scanf("%d",&size);

printf("\n Enter %d elements in to the array: ”, size);

for(i=0;i<size;i++)

scanf("%d",&a[i]);

big=a[0];

for(i=1;i<size;i++){

if(big<a[i])

big=a[i];

}

printf("\n Biggest: %d",big);

return 0;

}

Generation Of Pseudo-Random Numbers

2011-07-23T22:01:00.001+05:30

Random number generators are frequently used in computing for among other things, testing and analyzing the behavior of algorithms. A sequence of random numbers should exhibit the following behavior.

1. The sequence should appear as though each number had occurred by chance .

2. Each number should have a specified probability of falling with in a given range.

The approach is generally taken in computing science for random number generation is to simulate random process by deterministically producing a sequence of number that appear to exhibit random behavior. These sequence are predictable in advance and for this reason they are usually referred to as pseudo random sequences. There are many methods to generating pseudo random numbers. Perhaps the most widely used of these algorithms is the linear congruential method. When this method is approximately parameterized it will generate pseudo random sequences that for practical purposes, satisfy statistical criteria required of uniformly distributed random variables. In uniform distribution each possible number is equally probable.

The implementation of linear congruential method is very straightforward. Successive members of the linear congruential sequence {x} are generated using expression

X_n+1 = (ax_n+b) mod m for n ≥0

Where parameters a, b, m and x₀must be carefully chosen in advance according to certain criteria. The parameters a , b and m are referred to as the multiplier ,increment and modulus respectively.

All parameters should be integers greater than or equal to zero and m should be greater than x₀ ,a ,and b.

Parameter x₀

The parameter x₀can be chosen arbitrarily within the range 0 ≤ x₀< m.

Parameter m

The value of m should be greater than or equal to the length of random sequence required. In addition it must be possible to do the computation (a*x+b) mod m without round off.

Parameter a

The choice of a depends on choice of m. If m is a power of 2 then a should be satisfy the condition:

a mod 8 = 5

If m is power of 10 ,then a should be chosen such that :

a mode 200 = 21

Further requirement on a are that it should be larger than √m and less than m - √m , (a -1) should be a multiple of every prime dividing to m, and m is multiple of 4 then (a -1) should be multiple of 4.these conditions together with the requirement that b should be relatively prime to m are needed to guarantee that the sequence has period of m.

Parameter b

The constant b should be odd and not multiple of 5.

Algorithm To Find Square Root Of A Number

2010-12-03T20:37:00.000+05:30

      Algorithm to find square root of a number is absolutely a Guess work. To improve our algorithm we must start with simple examples. we know that square root of 4 is 2, square root of 9 is 3 so on.
i.e 4 = 2*2
          9 = 3*3
     so we can generate a general formula from above equations .if x is the square root of y .then the general formula is ,
                            x * x = y
   Next step to our algorithm is guessing. For example we want to find square root of 36. We guess 9 is the square root of 36.Using our general equation ,9*9 = 81 and is greater than 36. So decrease 1 from guessed square root . i.e 8 * 8 = 64 which is also greater than the 36 but closer ,So decrease 1.

   Now it can be generalize . choose a number x which must be less y which is the number to find square root.
if square of x is greater than y ,then decrease x by 1.Then the x² is less than y increase x by 0.1. Then x² is greater than y increase x by 0.01 and so on until we get the x² = y approx.

   The above method is so expansive because the huge number of iteration. if y is greater then more iteration will be needed. So we must find an alternative method.

   For best way,Consider example of 36, the first guess is 9 and its square is 81 which is greater than 36. Now we divide 36 with 9 give 4.And we choose it as second guessing square root. but 4² is less than 36.But we know that the exact square root is in between 4 and 9.

                          (9 + 4) =6.5
            2

    So the next step of algorithm is to find the average of 4 and 9 .which is to be 6.5. Now take square of 6.5 ,6.5² =42.25 which is greater than 36 .i.e Divide 6.5 into 36.which give 5.53. we can see that 5.53² is less than 36.
   Now take average of previous two guess roots as by previously.

                                  ( 6.5 + 5.53 )   = 6.015
                                          2
Now 6.015² = 36.6025 which has only slight difference with 36. repeat the step of averaging until to get the more approx square root. So by this method we get root with few iteration.
   Next step is the generalization of algorithm.if f1 is the initial guess ,in our example f1 = 9 .i.e general case of complementary value (36/9 = 4 ) is y/f1.
    Average of initial guess and complementary value give next approx root f2.

                               f2 = ( f1 + (y/f1 )) / 2

Our f2 = 6.5,we must repeat the above step, So we assume f2 as f1 .

                               f2 = ( f1 + (y/f1 )) / 2
   f1 = f2

    Last step of our algorithm is termination of loop. To terminate the loop ,we must set condition .which is the difference between f1 and f2 less than some value (such as0.0001). Take y/2 as initial guess which decrease.

Two Way merging

2010-11-25T07:57:00.000+05:30

Merging is the process to be used for organizing data. here explain two way merging technique or merge two array of integers , both with with their elements have in ascending order array
Consider two array with ascending order elements a and b have l and m elements respectively

After emerging we get a single merged array c with ascending order elements.

Now the question.How can we create emerging array generally? To evaluate this we simply take two single elements arrays a and b

    Compare a and b and move smaller value into c. In this 7 is less than 15 so 7 move to c array as first element then 15. so 7 is go in to c[1] and 15 is to c[2].

Now we can able to create start to first problem with m and l elements. The comparison between a[1] and b[1] set c[1]. so in our case b[1] is go to c[1].so next we compare a[1] and b[2]. and less element going
c[2] and so on.

Merging Process

If we follow the step by step merging ,we may get run out of element in one of an array and we can't make comparison between elements in the two arrays.i.e we must have a way to detecting one of array runs out. so here is the method,

while((i<=l)&&(j<=m)){

=>Compare a[i] and b[j] and merge.

=>Increment appropriate pointers.

}

if(i<l)

=>Copy the rest of a array elements in to c in order.

else

=>Copy rest of b array elements into c in order.

For easy implementation we use an alternate method,The largest element in two arrays is copied into other array as shown by figure.

Now we have a simple method and is implemented in c below.

C implementation:

       if(a[l]<b[m])

a[l+1] = b[m];

else

b[m+1] = a[m];

int i=1,j=1;

while((i<=l)&&(j<=m)){

if(a[i]<=b[j])

c[k] = a[i];

i++;

else

c[k] = b[j];

j++;

}

Array Order Reversal

2010-11-24T20:25:00.001+05:30

Reversing the order of an array of numbers can be start by design of algorithm

before reversal

after reversal

the reversing is easly observe by following figure

step[1]:   a[1]<=>a[7]
step[2]:   a[2]<=>a[6]
step[3]:   a[3]<=>a[5]
step[4]:   a[4]<=>a[4]

and the development of algorithm is given

        1 <=> 7-1+1 =7
        2 <=> 7-2+1 =6
        3 <=> 7-3+1 =5
        4 <=> 7-4+1 =4
General term : i <=> n-i+1
Exchange can be done by following mechanism
t       = a[1];
a[i]    = a[n-i+1];
a[n-i+1]= t;

we done!

Algorithm in steps:

1.Establish the array a[1...n] to be reversed
2.Compute noumber of exchange required to reverse
3.Exchange the ith element with [n-i+1]th element

Sine Function Computation Algorithms

2010-11-24T20:20:00.001+05:30

Sine series is given ;

sin(x) = (x/1!)-((x^3)/3!)+((x^5)/5!) -((x^7)/7!)+..........

Algorithm development:

Studying the expression for sin(x) we see the powers and factorials of following sequences

1,3,5,7..................

are required. We can easily generate this odd sequence by starting with 1 and successively adding 2. Our other problem is to compute the general term (x^i)/i! which can expressed as

(x^i)/i! = (x/1)*(x/2)*(x/3)*.......*(x/i) for i>=1

and it can done following loop

fp := 1;

j := 0;

while j<i do

begin

j := j +1;

fp := fp*(x/j);

end

The program can be completed by implementing the additions and subtraction and appropriate termination. With this approach each term (x^i)/i! is computed by smallest j value and working upward . To calculating n! we used the efficient approach of calculating each term from its predecessors .

To determine algorithm we examine specific series for example,

(x^3)/3! = (x*x*x)/(3*2*1) = (x^2)/(3*2) * (x^1)/1! i =3

(x^3)/3! = (x*x*x*x*x)/(5*4*3*2*1) = (x^2)/(5*4) * (x^3)/3! i =5

(x^3)/3! = (x*x*x)/(7*6*5*4*3*2*1) = (x^2)/(7*6) * (x^5)/5! i =7

In each term (x^2)/(3*2) , (x^2)/(5*4) ,(x^2)/(7*6) has a general term :

(x^2)/i(i - 1) for i= 3,5,7,....

i.e. generalized form of each term is:

current ith term = [ (x^2)/i(i - 1) ] * (previous term)

To get the terms to alternate in sign we can use

sign := -sign

algorithm description

setup initial conditions for the first term that cannot be computed iterativley .
while the absolute value of current term is greater than the acceptable error do

(a). identify the current ith term,

(b). generate current term from its predecessor,

(c). add current term with appropriate sign to the accumulated sum for sine function.

Generation Of Fibonacci Sequence Algorithm

2010-11-24T07:04:00.000+05:30

The first few term are

0,1,1,2,3,5,8,13,...

Each term beyond the first two is derived from the sum of its nearest predecessors.

Algorithm development:

From the definition we are given that:

New term = preceding term + term before preceding term

The last sentence of the problem statement suggest we may be able to use the definition to generate consecutive term (apart from the first two) iteratively.

Let us define:

a) As the term before preceding term

b) As the preceding term

c) New term

Then to start with we have:

             a := 0         first Fibonacci number

             b := 1         second Fibonacci   number

and c := a+b third Fibonacci number (from definition)

when the new term c has been generated we have the 3rd Fibonacci number. To generate fourth or next Fibonacci number, we need to apply the same definition again. Before we can make the next computation we need to make some adjustments. The fourth Fibonacci derived from the sum of the second and third Fibonacci numbers. With regard to the definition the second Fibonacci number has the role of term before the preceding term and the 3rd Fibonacci number has the role “preceding term” therefore , before making the next computation we must ensure that:

a) New term (i.e.) assumes the role of the preceding term,

b) And what is currently the preceding term must assume the role of the term

before the preceding term.

That is,

a := 0   [1]       term before preceding term

b :=1    [2]    preceding term

c := a+b [3]    new term

a := b   [4]    term before preceding term   becomes preceding term

b   :=c    [5]    preceding term become new term.

After making step [5] we are in position where we can use the definition to generate the next Fibonacci number. A way to do this is to loop back to step [3]. Further investigation of steps [3]->[5] indicates they can be placed in a loop to iteratively generate Fibonacci numbers (for n>2). The essential mechanism we could use is:

a := 0;

b := 1;

i := 2;

while i<n do

begin

i := i+1;

c := a+b;

a := b;

b := c

end

Algorithm Description

1) Prompt and read n, the number of Fibonacci numbers to be generated .

2) Assign first two Fibonacci numbers a and b.

3) Initialize count of number generated.

4) While less than n Fibonacci numbers have been generated do

a) Write out next two Fibonacci numbers;

b) Generate next Fibonacci number keeping a relevant ;

c) Generate next Fibonacci number from most recent pair keeping b relevant for next computation

d) Update count of numbers of Fibonacci numbers generated, i.

5)    If n even then   write out last two Fibonacci numbers else write out second last   Fibonacci number.

Reversing The Digit Of An Integer

2010-11-24T07:01:00.000+05:30

Reverse the order of digits of a positive integer.

Development:

A specific example of reversing is,
                          input no :1532
   reversed output :2351
Actually the number 1532 is

1*(10^3)+5*(10^2)+3*(10^1)+2*(10^0).
      We can access each digits. and start the access from rightmost
(least significant digit). To chop off least significant digit
from the number, use mod 10, mod give reminder of division

        i.e. 1532 mod 10 = 2
To get the remaining number 153, Use integer division by 10 with
the number

i.e, int(1532 div 10) = 153
Repeat the above two steps to access each digits in the number

To generalize above steps, imagine n is the number to be reverse
then,
        n mod 10 = r;
    r is the least significant digit
        n = int(n / 10);

The next step is to reverse the number, In above example 2 is the
first digit and 3 is second.We can reverse it by 2 (least significant digit)
is multiplying with 10 and add it with 3(next significant digit)
        i.e, 2*10 + 3 = 23

Repeat the above steps until fully reverse the number
Use while loop with condition n>0 to repeat the steps
        23 * 10 + 5 = 235
           235 * 10 + 1 = 2351
We are done!

To generalize above steps, initialize a variable reverse with zero

    i.e,reverse = reverse * 10 + r

implement in C:

#include<stdio.h>
main()
{
    int reverse = 0;
    int r,n;
    printf("Enter the number to reverse");
    scanf(%d,&n);
    while(n>0){
        r = n mod 10;
        n = n / 10;
        reverse = (reverse *10) + r;
        }
    printf(The reversed number is :%d,reverse);
    return 0;
}

Factorial Computation Algorithms

2010-11-24T06:58:00.000+05:30

We can start the development of this algorithm by the definition of n!

n! = 1*2*3*...........*(n-1)*n for n>=1 and 0!= 1

In our design we need to keep in mind that the computer's arithmetic unit can only multiply two numbers at a time

Applying the factorial definition we get

0!=1

1!=1*1

2!=1*2

3!=1*2*3

4!=1*2*3*4

We can see that 4! contains all factors of 3!. The only difference is 4. We can generalize this by observing that n!can always be obtained from (n-1)! by simply multiplying by n(for n>=1). that is,

n!=n*(n-1)! for n>=1

Using this def we can write the first few factorial as

1!=1*0!

2!=2*1!

3!=3*2!

4!=4*3!

If we start p=0!=1 we can write first few steps in computing n!as:

p:= 1 =0!

p:= p*1 =1!

p:= p*2 =2!

p:= p*3 =3!

p:= p*4 =4!

. .

From step 2 onwards we are actually repeating the same process over and over. For general (i+1)th step we have

p := p*i (i+1)

This general step can be placed in a loop to iteratively generate n!. this allows us to take advantage of the fact that the computer arithmetic unit can only multiply two numbers at a time.

In many ways this this problem is very much like the problem of summing a set of n numbers.In this problem we need to generate a set of products. it follow from the general (i+1)th step that all factorials for n>=1 can be generated iteratively. The instance where n=0 is special case which must be accounted for directly by assignment

p := 1 ( by definition of 0)

The central part of the algorithm for computing n! therefor involves a special initial step followed by n iterative steps.

1. Treat 0! as special case (p := 1)

2. Build the each of the n remaining products from its predecessors by an iterative process.

3. Write out the value of n!

Algorithm Description

1. Establish n, the factorial required where n>=0.

2. Set product p for 0! (special case). Also set product count to zero.

3. While less than n products have been calculated repeatedly do

(a) increment product count ,

(b) compute the i th product p by multiplying i by the most recent product.

4. Return the result n!