100%(1)100% found this document useful (1 vote) 3K views290 pagesDesign and Analysis of Algorithms-Compressed (1) - Compressed
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here.
Available Formats
Download as PDF or read online on Scribd
Dyn) il} INHIB
Of
CS) TASS
For VI Sem
As pec the Syllabus of
A awa
89107842
A
PUBLISHERS Golo 34x42
Design & Analysis of Algorithms
For Sixth Semester B.C.A
As per Bangalore University Syllabus
‘
BY
Srikanth .S
REFERENCE BOOK
Skyward Publishers
11157, 3rd Main, 70-Cross, Chamara|zet, Bengalora - 560018
Ph --080-26603525/ 44559339 Mob -61 1185999 / 4559514760
‘rail - skyword.publishers@amal.cam wwwaskywardpeblisherscam
mi |
GCD (m,n) = " ifn=0
GCD (n,.MOD(n,1)), otherwise
Here, MOD (im, n) is nothing “7 modulo n” i.e., the remainder obtained when dividing 7
bye. The thitd part of the equality ie., GCD (n,n) = GED in, MOD (in, n)) is the heart
| ofthe problem which is applied repestedly until MOD (m, n) becomes zero
thumple: GCD (288, 108) = GCD (108, MOD (288. 108))
GCP (108, 72) = GCD (72, MOD (108, 723)
(D (72,36) = GCD (36, MOP (72, 36)
= GCP 36.0) = 36
So, the following steps are adapted according to Buclid.
Step I:Check the second equality first in the definition ie. ifm = 0, return the value of mm!
and-stop. Otherwise go to step 2.
Stop 2:Caleulate MOD. (ma, 1}
and assign this value'to a temporary variable“?
Step 3:Assign the value of ‘i! to ‘in’ and ‘t' to ‘x’, Go to step 1
Algorithm : Euclid (vt, 7)
1 Computing the GCD (m, nm}
‘Input ; lwo non-negative, not-both-zere integers m, 2
/) Qutput : Greatest common divigor of m and n
#@ do
in mod np
ag
is
8
“0
return’ fm ;
y
{f we recall the features of an algorithm, the first feature that the algorithm should terminate
after a particular number of steps is true in this example. The terminating step here is, when
ahecomes ‘0’ i.e., MOD (m,n) becomes zero i.¢., the second equality step GCD (mm,
t= me, 6 The Design & Analysis of atenith
Technique 2: (Consecutive Integer checking algorithm)
Thiis technique is based on the general definition of a GC thata GCD is the largest integer that
divides both the numbers evenly: Obviously, suet ‘an integer cannot be greater than any of the
{wo integers, Sa GED (m, n) $ min (m, n}. Let us consider GCD (m,n) as a temporary
votable '¢' and assign the minimum of m undo the variable (4.8. 1= are (i, 0). Now westait
ohevking whether ‘f divides both mund 7. Llitdoes, the GCD (m, n)is ‘1’ otherwise decrease
‘by Land check once again. ‘The process continues until ‘r' reaches a number that divides both
mand n.
Example:
Consider the sane example GCP (288, 108)
ics m= 288, a= 108 and
t= min (288, 108) = 108
Now check whether MOD (mt, )=0
As MOD (288, 108) #0, decrease rby Live. f= 107.
Now, as MOD (288, 107) #=0, decreases by Lie. r= 106
Again, as MOD (288, 106) 40, decreases by | i.e, 7= 105
Again, as MOD (288, 97) #0, decrease by 1 1c.,1=96
But, as MOD (288, 96) = 0,
Now check whether MOD (n, r) =0
As MOD (108, 96) # 0, decrease ( by Lie. t=95
and check whether MOD (m, t)=0.
As MOD (288, 95) #0, decrease rby 1 ie. r=94
Now, ds MOD (288, 94) #0, deerease t by Lie. t= 93
Again as MOD (288, 93) #0, decrease t by i@.0=92
Again, as MOD (288, 73) #0, decrease r by i.e.
But, as MOD (283, 72)=0, Anyeadiction
Now check whether: MOD (n,)=0-
As MOD (108,72) #0, decrease by Lie.,1=71
and check whether MOD (mm; n=0
As MOD(288, 71) #0, decrease rby 1 ie, r= 70
Again, As MOD (288, 37) # 0, dectéase t by Lie. r=36
But, as MOD (288, 36) =0,
Now check whether MOD (n, )=0
‘As MOD (108,36) =
‘The result is 36,
80°36’ is the greatest common divisor thatdivides both 288 and 108.
The following steps can be adopted for this,
Step T: Assign the value of min {ma 2} to
Step 2: Calculate MOD (m, 1). Witis zero, goto step 3, else go to step4.
Step 3: Calculate MOD (n, 1). [fitis “zero”, return the value of as answer and stop, else g0 10
slep-4,
Step 4: Decrement ‘7 by | and goto step 2.
Algorithm: CICA (m,n)
Vi
iy
Il
Computing the Gcn im, aj
Taput : Two. nm Negative, net-both zero integers m, n.
Output + Greatest common divisor of mand 2.
& = min (a, a);
while (t #1) do
t=mmod cj}
if (t = 0)
a
b= nmod tj
d= (tu = 0)
fi
return t ; 8 . hs Desiew a Analysis of Ala
‘The drawback in this alporithm techniques it doesn't Work when any one or both of the input
vuluési-e.. mand mare zeros, because when any One of mand are zeros, the minimum: value
becomes *0’ Le..f=0. Then MOD (m, 1) or MOD (u, t) isnot defined,
So theextrucondition forinput when perférming this algorithm is'the integers should be
non-negative, nol-zero,
‘Technique 3 (Middle - School Algorithm)
‘The third technique is the one thatis more familiar tothe middle =school students and hence the
atric, iy this method, thie prime factors ot the integers are found and then by identifying all Ot
common terms and multiplying them gives the gel.
Example: GED (288, 108)
‘The prime factors of 288 =2°X 3? g| ton = -2| 288
The prime factors of 108 =2" 38 gisa = 1
Noiw, thecommon terms are 2? and 3* ee
“+, The ged of 288 and 108=2?x3'=4x9=36 © 912 _ Boe
“The steps involved in this prozess F oe
Stop 1: Find the prime factors of eT
Step 2:
Step 3: Identify the common prime factors of the above (wo step factors.
‘ind the prime factors of 1
Step 4: Compute the product of the comrnon factors of step 3 and return the resull which is th
ged.
Designing wn algorithm for this technique is: more complex though the way we followed in th
example looks very eusy because using a pen we can calculate the prime factors and th
commion prime factors very easily but the computer will take a large amount of time fe
performing this method. . 9
liviadacsiow
Soun algorithm for generating the consecutive primes is inverted in ancient greace and is
named as sieve of Erasthenes.
Sieve of Erasthenes:
This generates all of the prime numbers less than or equal ton. Start by writing the numbers
from 2, 3,4... 2 ina line. Then keep repeating the following process until all the elements
or numbers less than or equal to va haye been crossed out or circled.
Circle the next number whieh is neither circled nor crossed out, and cross out all other
multiples of thal number which are in the list (some of these are probably already erossed
out).
The numbers which are not crossed out when the process terminates are all of the primes
between 2 tom.
Example {: To list out the prime numbers less than or equal to 36,
i.e., when n= 36
2|3 |4]5 |e ]7 |e
nm [t2 | ra | a fas Ff 18
20 | 24 | 22 | 28 25 | 26 | 27 | 28]
30 | 1/82 | 33 | 84 | 35 | 36
The square root of 36 is 6 and therefore we haye to repeat the process mentioned earlier
until all the elements are crossed out or circled lessthan or equal to 6.
Consider a first number 2, which is-not yet circled or crossed out. Circle the number 2 and
crossout all the multiples of 2 except 2 i.¢., 4, 6.8, 1
a a 7 9
i 13 15 Ww lo
21 23 [Set] 25 [ae] 27
2 al 3B. aD
‘Consider the next number which is neither crossed out nor circled. i.e., number 3. Now,
cirele the number’ and cross out all the multiples of 3 except 3,
fe, (6, 9, 12,15, ....2. 33, 36),
[some of them are-already crossed out, then'no need to cross them again
W 13 7 19:
od 23
29 3
