Algorithm Analysis and Design

ETCS: 254
TUTORIAL SHEET 1
Ques1: Write an algorithm to find the largest value among n>=1 numbers.
Input : the value of n and n numbers
utput : the largest value
Steps :
Step !: "et the value of the first be the largest value denoted by #I$
Step 2: "et % denote the number of remaining numbers& %'n(!
Step ): If % *' + then it is implied that the list is still not e,hausted& Therefore loo- the
ne,t number .alled /E0&
Step 4: /o1 % be.omes %(!
Step 5: If /E0 is greater than #I$ then repla.e #I$ by the value of /E0
%epeat steps ) to 5 until % be.omes 2ero&
Step 3: 4rint #I$
Step 5: Stop
Ques2: Write an algorithm to find roots of a quadratic equation.
Input: the value of a6b6.
utput: all roots
Step !: Start
Step 2: De.lare variables a6 b6 .6 D6 ,!6 ,26 rp and ip7
Step ): Cal.ulate dis.riminant
D8b2(4a.
Step 4: If D9+
r!8:(b;<D=>2a
r28:(b(<D=>2a
Display r! and r2 as roots&
Else
Cal.ulate real part and imaginary part
rp8b>2a
ip8<:(D=>2a
Display rp;?:ip= and rp(?:ip= as roots
Step 5: Stop
Ques3: Write an algorithm to list all prime numbers between two limits m and n.
Input: "o1er limit: m and @pper limit: n
utput: 4rime numbers bet1een given limits
Steps:
Step !: Start
Step 2: De.lare variables m6 n6 .6 i6 ? 7
Step ): Set .'+
Step 4: %epeat for i'm till n
Step 5: %epeat for ?'2 till i
if i'26 then Display A4%IBE /: Ci
if iD?'+6then set .'.;!
set ?'?;!
EEnd of Inner "oopF
if .'+6 then Display A4%IBE /: Ci
Set .'+
Set i'i;!
EEnd of outer loopF
Step 5: Stop
Ques: !evise the algorithm that inputs three numbers and outputs them in ascending order.
Input: ) numbers :a 6 b 6 .=
utput: As.ending rder
Steps:
Step !: Start
Step 2: De.lare variables a 6b 6. 6ma, 6min 7
Step ): 4rint Enter the value of a 6 b and .
Step 4: S.an a
Step 5: S.an b
Step 3: S.an .
Step 5: Cal.ulate $reatest no
if:aGb HH aG.=
ma,'a
else if:bGa HH bG.=
ma,'b
else if:.Gb HH .Ga=
ma,'.

Step I: Cal.ulate Smallest no
if:aJb HH aJ.=
min'a
else if:bJa HH bJ.=
min'b
else if:.Jb HH .Ja=
min'.
Step K: 4rint As.ending rder
4rint min7
if:a*'ma, HH a*'min=
4rint a7
else if:b*'ma, HH b*'min=
4rint b7
else if:.*'ma, HH .*'min=
4rint .7
4rint ma,7
Step !+: Stop
Ques": !evise the algorithm to test whether a given point p#$%&' lies on $(a$is or &(a$is or in
)*))*)))*)+ quadrant.
Input: 4oint p:,6y=
utput: Luadrant
Steps:
Step !: Start
Step 2: De.lare variables , 6y 7
Step ): 4rint Enter the value of , and y
Step 4: S.an ,
Step 5: S.an y
Step 3: Cal.ulate Luadrant
if :,G+ HH yG+=
4rint !
st
Luadrant
else if:,J+ HH yG+=
4rint 2
nd
Luadrant
else if:,J+ HH yJ+=
4rint )
rd
Luadrant
else if:,G+ HH yJ+=
4rint 4
th
Luadrant
Step 5: Stop
Ques,: !evise the algorithm to compute the area of a circle of a given circumference.
Input: Cir.umferen.e: .
utput: Area
Steps:
Step !: Start
Step 2: De.lare variables area6 r 7
Step ): 4rint Enter .ir.umferen.e
Step 4: S.an .
Step 5: Cal.ulate radius
r 8 .>2M)&!4
Step 3: Cal.ulate area
area 8 )&!4MrMr
Step 5: 4rint area
Step I: Stop
TUTORIAL SHEET 2
Ques 1: What are the serious short comings of the binar& search method and sequential search
method.
Ans: SeNuential Sear.h method has poor effi.ien.y as its .omple,ity is :n=&0hereas #inary
sear.h method .an be applied only on ordered set of data& It is not appli.able for unsorted data&
Ques 2: )mplement the algorithms for searching and calculate the comple$ities.
Ans:
"I/EA% SEA%CO A"$%ITOB:
Pin.ludeJstdio&hG
Pin.ludeJ.onio&hG
main:=
Q
int AE5+F6i6,6n6.'+7
printf:Aenter the limit of array:C=7
s.anf:ADdC6Hn=7
printf:Aenter the elements:C=7
for:i'+7iJn7i;;=
Q
s.anf:ADdC6HAEiF=7
R
printf:Aenter the element 1hi.h should be sear.hed for:C=7
s.anf:ADdC6H,=7
for:i'+7iJn7i;;=
Q
if:AEiF'',=
Q
.;;7
printf:Aelement is present at Ddth positionC6i;!=7
R
R
if:.''+=
printf:Athe element is not presentC=7
get.h:=7
return +7
R
#I/A%S SEA%CO A"$%ITOB
Pin.ludeJstdio&hG
>M "ogi.: Elo16 highF denotes the range in 1hi.h element has to be present&
Initially lo1 ' +6 high ' numberTofTelements 1hi.h .overs entire range&
In every step 1e redu.e the range by doing the follo1ing
:i= If the middle element :mid= is less than -ey then -ey has to present in range Emid;! 6
highF
:ii= If middle element is the -ey6 then 1e are done&
:iii= If the middle element is greater than -ey then -ey has to be present in the
rangeElo16mid(!F
M>
int #inarySear.h:int Marray6 int numberTofTelements6 int -ey=
Q
int lo1 ' +6 high ' numberTofTelements(!6 mid7
1hile:lo1 J' high=
Q
mid ' :lo1 ; high=>27
if:arrayEmidF J -ey=
Q
lo1 ' mid ; !7
R
else if:arrayEmidF '' -ey=
Q
return mid7
R
else if:arrayEmidF G -ey=
Q
high ' mid(!7
R
R
return (!7
R
int main:=
Q
int numberTofTelements7
s.anf:ADdC6HnumberTofTelements=7
int arrayEnumberTofTelementsF7
5n titer7
>MInput has to be sorted in non de.reasing order M>
for:iter ' +7iter J numberTofTelements7iter;;=
Q
s.anf:ADdC6HarrayEiterF=7
R
>M Che.- if the input array is sorted M>
for:iter ' !7iter J numberTofTelements7iter;;=
Q
if:arrayEiterF J arrayEiter U !F=
Q
printf:A$iven input is not sortedVnC=7
return +7
R
R
int -ey7
s.anf:ADdC6H-ey=7
>M Calling this fun.tions sear.hes for the -ey and returns its inde,& It returns (!
if -ey is not found&M>
int inde,7
inde, ' #inarySear.h:array6numberTofTelements6-ey=7
if:inde,' ' (!=
Q
printf:AElement not foundVnC=7
R
else
Q
printf:AElement is at inde, DdVnC6inde,=7
R
return +7
R
CB4"EWITS:
A= "inear Sear.hing: :n=
#= #inary Sear.hing: :n logn=
Ques 3:Write an algorithm for selection sort. -ind the comple$it& of selection sort.
A"$%ITOB:
Sele.tion :item EF6 /= >M item is an array of si2e /M>
Q
Xor :I'+7 IJ/Y!7 I;;=
Q
Initiali2e BI/ by item EIF and p by I7
>Mfinding minimum elementM>
Xor :Z'I;!7 ZJ/7 Z;;=
IX item EZF JBI/ then set BI/ is eNuals to item EZF and p is eNuals to Z7
>Ms1apping the minimum element 1ith the target elementM>
Set itemEpF by item EIF and item EIF by BI/&
R
R
CB4"EWITS:
#est .ase performan.e U 0hen the list is already sorted :n
2
=&
0orst .ase performan.e U 0hen the list is sorted in reverse order :n
2
=&
Average .ase performan.e U :n
2
=&
Ques : Write the algorithm for merge sort method .
Ans:
Con.eptually6 a merge sort 1or-s as follo1s
Divide the unsorted list into n sublists6 ea.h .ontaining ! element :a list of ! element is
.onsidered sorted=&
%epeatedly merge sublists to produ.e ne1 sublists until there is only ! sublist remaining&
This 1ill be the sorted list
Top do1n merge sort algorithm 1hi.h uses re.ursion to divide the list into sub(lists6 then merges
sublists during returns ba.- up the .all .hain&
function merge_sort(list m)
// if list size is 0 (empty) or 1, consider it sorted and return it
// (using less than or equal prevents infinite recursion for a zero length m)
if length(m) < 1
return m
// else list size is ! 1, so split the list into t"o su#lists
var list left, right
var integer middle length(m) / $
for each % in m #efore middle
add % to left
for each % in m after or equal middle
add % to right
// recursively call merge_sort() to further split each su#list
// until su#list size is 1
left merge_sort(left)
right merge_sort(right)
// merge the su#lists returned from prior calls to merge_sort()
// and return the resulting merged su#list
return merge(left, right)
&n this e%ample, the merge function merges the left and right su#lists.
function merge(left, right)
var list result
"hile length(left) ! 0 or length(right) ! 0
if length(left) ! 0 and length(right) ! 0
if first(left) < first(right)
append first(left) to result
left rest(left)
else
append first(right) to result
right rest(right)
else if length(left) ! 0
append first(left) to result
left rest(left)
else if length(right) ! 0
append first(right) to result
right rest(right)
end "hile
return result
CB4"EWITS:
#est .ase U 0hen the array is already sorted :nlogn=&
0orst .ase U 0hen the array is sorted in reverse order :nlogn=&
Average .ase U :nlogn=&
E,tra spa.e is reNuired6 so spa.e .omple,ity is :n= for arrays and :logn= for lin-ed lists&
Ques ":Write an iterative algorithm to find the factorial of a number.
!& Input n
2& Set f'!7
)& %epeat for i'n till !
4& Set f'fMi
5& Set n'n(!
3& EEnd of loopF
5& 4rint Xa.torial of n is f
Ques ,: )teration v*s .ecursion
%e.ursive algorithms
Bany programming languages do not support re.ursion6 hen.e re.ursive mathemati.al
fun.tion is implemented using iterative methods& %e.ursion is a top do1n approa.h to
problem solving& It divides the problem into pie.es or sele.ts out one -ey step6 postponing
the rest&
Even though mathemati.al fun.tions .an be easily implemented using re.ursion it is
al1ays at the .ost of e,e.ution time and memory spa.e&
A re.ursive pro.edure .an be .alled from 1ithin or outside itself and to ensure its proper
fun.tioning it has to save in some order the return addresses so that6 a return to the proper
lo.ation 1ill result 1hen the return to a .alling statement is made&
The re.ursive programs needs .onsiderably more storage and 1ill ta-e more time&
Iterative methods
In iterative te.hniNues looping of statement is very mu.h ne.essary&
Iteration is more of a bottom up approa.h& It begins 1ith 1hat is -no1n and from this
.onstru.ts the solution step by step& The iterative fun.tion obviously uses time that is :n=
1hereas re.ursive fun.tion has an e,ponential time .omple,ity&
It is al1ays true that re.ursion .an be repla.ed by iteration and sta.-s& It is also true that
sta.- .an be repla.ed by a re.ursive program 1ith no sta.-
TUTORIAL SHEET 3
Ques1: !efine /mega notation.
To des.ribe lo1er bounds 1e use the big(omega notation f:n='[:g:n== usually defined by saying
for some .onstant .G+ and all large enough n6 f:n=9. g:n=&
Ques2: !efine 0ig(/ notation.
0e define big( notation by saying f:n=':g:n== if there e,ists some .onstant . su.h that for all
large enough n6 f:n=\ . g:n=&
Ques3: !efine 1heta notation.
0e define theta notation by saying that f:n=']:g:n== meaning that f is bounded both above and
belo1 by g asymptoti.ally& It is usually defined as g:n=&-! Jf:n=Jg:n=&-2 1here -!6 -2 are some
positive .onstants&
Ques: What is an algorithm2
An algorithm .an be defined as a seNuen.e of definite and effe.tive instru.tions6 1hi.h terminates
1ith the produ.tion of .orre.t output from the given input&
Every algorithm should have the follo1ing five .hara.teristi. feature
Input
utput
Definiteness
Effe.tiveness
Termination
Ques": What are the worst case and average case running time of insertion sort2
!& #est .ase performan.e U 0hen the array is already sorted :n=& Total number of .omparisons:
/ U ! and total number of e,.hanges: / U !&
2& 0orst .ase performan.e U 0hen the array is sorted in reverse order :n
2
=&/(! iterations of
.omparison and e,.hanges&
)& Average .ase performan.e U :n
2
=
Ques,: Which technique is used to sort elements in merge sort2
Divide and ConNuer te.hniNue is used in merge sort&
Ques3: What is the running time of merge sort2
#est .ase U 0hen the array is already sorted :nlogn=&
0orst .ase U 0hen the array is sorted in reverse order :nlogn=&
Average .ase U :nlogn=&
Ques4: 5ow merge sort is different from quic6 sort2
Berge Sort reNuires additional spa.e for sorting 1hereas Nui.- sort doesn^t reNuire e,tra spa.e&
So6 spa.e .omple,ity of merge sort is :n= for arrays and :logn= for lin-ed lists&
Ques7: What is the worst case running time of quic6 sort2
0hen the partitioning produ.es one region of si2e n(! :1here6 n is the total number of elements in
the list= and other of si2e !6 then .omple,ity is :n
2
=&
Ques18: !efine i(th order statistics of a set.
The i
th
order statistic of a set of n elements is the i
th
smallest element
Ques11: What is median of a set2
The median is the middle element of set 1hen all elements are arranged in their as.ending order&
If the n is even6
Bedian are : = and : ;!= th elements of set
If n is odd6
Bedian is : ;!= th element of set&