0% found this document useful (0 votes)
79 views95 pagesAda 1
Uploaded by
pranshubhatia1Copyright
© © 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
0% found this document useful (0 votes)
79 views95 pagesAda 1
Uploaded by
pranshubhatia1Copyright
© © 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
/ 95
UNIT-A
Basics of algorithms: Algorithms and characteristics, algorithm design paradigms,
fundamentals of algorithmic problem solving, fundamental data structures.
Analysis of algorithms: The efficient algorithm-average, worst and best case analysis,
asymptotic notations and its properties, amortized analysis, recurrences: substitution
method, recursion tree method and master’s method.
Computational Problem: A computational problem is a task solved by a computer. A
computation problem is solvable by mechanical application of mathematical steps, such as
an algorithm.
Algorithm: Algorithm is a step-by-step procedure, which defines a set of instructions to be
executed in a certain order to get the desired output. Algorithms are generally created
independent of underlying languages, i.e. an algorithm can be implemented in more than one
programming language.
Characteristics of an algorithm are:
1. Finiteness: An algorithm must always terminate after a finite number of steps.
2. Definiteness: Each step of an algorithm must be precisely defined; the actions to be
carried out must be rigorously and unambiguously specified for each case.
3, Input: An algorithm has zero or more inputs, i.e, quantities which are given to it initially
before the algorithm begins.
4. Output: An algorithm has one or more outputs ie, quantities which have a specified
relation to the inputs.
5. Effectiveness: An algorithm is also generally expected to be effective. This means that
all of the operations to be performed in the algorithm must be sufficiently basic that
they can in principle be done exactly and in a finite length of time.
Complexity of Algorithm: (Algorithm Efficiency)
The efficiency of an algorithm is mainly defined by two factors i.e. space and time. A good
algorithm is one that is taking less time and less space, but this is not possible all the time,
There is a trade-off between time and space. If you want to reduce the time, then space
might increase. similarly, if you want to reduce the space, then the time may increase. So,
you have to compromise with either space or time,
fe Xis an algorithm and mis the size of input data, the time and space used by the
Suppos ain factors, which decide the efficiency of x.
algorithm X are the two mi
ime Factor ~ Time is measured by counting the number of key operations such as
. in the sorting algorithm,
‘comparison:
Scanned with CamScanner
@eeeme Beoeoeoveoaonoeeeesnoeaeeeaeove
22S eP 22002000 ‘+ Space Factor - Space is measured by counting the maximum memory space required
by the algorithm.
The complexity of an algorithm f{n) gives the running time and/or the storage space required
by the algorithm in terms of n as the size of input data.
‘Space Complexity
Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle, The space required by an algorithm is equal to the sum of the
following two components ~
+ A fixed part that is a space required to store certain data and variables, that are
independent of the size of the problem. For example, simple variables and constants
used, program size, etc.
+ Avariable partis a space required by variables, whose size depends on the size of the
problem. For example, dynamic memory allocation, recursion stack space, etc.
Space compiexity S(P) of any algorithm P is S{P) = C + SP(I), where Cis the fixed part and S(I)
is the variable part of the algorithm, which depends on instance characteristic |. Following is.
a simple example that tries to explain the concept -
Algorithm: SUM(A, B)
Step 1- START
Step2-CEA+B410
Step 3- Stop
Here we have three variables A, 8, and C and one constant. Hence S(P) = 1 +3, Now, space
depends on data types of given variables and constant types and it will be multiplied
accordingly.
Time Complexity
Time complexity of an algorithm represents the amount of time required by the algorithm
to run to completion. Time requirements can be defined as a numerical function T(n), where
T(n) can be measured as the number of steps, provided each step consumes constant time.
For example, addition of two n-bit integers takes n steps. Consequently, the total
computational time is T(n) = c * n, where cis the time taken for the addition of two bits.
Here, we observe that T(n) grows linearly as the input size increases
We design an algorithm to get a solution of a given problem. A problem can be solved in more
than one ways.
Scanned with CamScanner
|
|
|
|
|
|
i
|
|
|
erteeeeeeeveeeeevneeeeeoeeeoeooeooeSeeaeoegoeaee Ty ra
Problem |
7 S
ssuton * etn
Hence, many solution algorithms can be derived for a given problem, The next step is to
analyze those proposed solution algorithms and implement the best suitable solution.
Running Time of an Algorithm:
The running time of an algorithm for a specific input depends on the number of operations
executed. The greater the number of operations, the longer the running time of an algorithm.
‘We usually want to know how many operations an algorithm will execute in proportion to the
size of its input, which we will call n
‘We can calculate the running time of an algorithm by using a technique known as algorithm
analysis. We can also estimate the performance of an algorithm by estimating or counting the
number of basic operations required by an algorithm to process an input of specific size.
Basic Operation: The time to complete the basic operation doesn’t depend on the specific
value of its operand, So, it takes a constant amount of time.
Input Size: It is the number of inputs processed by an algorithm. For a given problem we
characterize the input size n appropriately. For example:
Sorting problem: Total number of item to be sorted
Graph Problem: Total number of vertices and edges
Numerical Problem: Total number of bits needed to represent a number
Growth Rate: The growth rate of an algorithm is a rate at which the running time or the cost
of algorithm grows as the size of input grows.
Example:
Let us consider an array having n elements and we have to find out the largest element from
given array. The steps of algorithm are given as:
1. Consider two variables, say “max_element” and “current_element .
2. for Oto n-1
if current_element > max_element
‘max_element = current_element
3. Return max_element.
Scanned with CamScanner
>PHOHOSHKRHHKGHSHSSOSOGHOSHOHOCHOHRDFPSOOHOOOC HALO Complexity of algorithm = O(1+n+1) = o(n+2)=O(n)
Analysis of an Algorithm:
It means how much time an algorithm will take to execute, how much memory, it need and
the number of resources, it takes during the execution.
Suppose we have to find the sum of first n natural numbers then, the different algorithm may.
be given as:
Analysis of Algorithm
|
ALGOL ALGO2
Initial time of execution (ta) = time(); Initial time of execution (ti2}= time();
Finishing time (tr) = time();
Algorithm time ta
fae ta;
ALGOL ALGO2
int sum (int N) int sum (int N)
{ {
int s=0; ints =0;
for (i=0; s=NF(N41)/2;
s=stl; return s;
return 5; 2
}
‘The complexity of algo 1 is 0 (N) and its execution is dependent upon the input size N, and in
case of algo , the complexity is O(1) and its execution is independent of the input size n
Scanned with CamScanner Asymptotic Notation:
Asymptotic notations are used to represent the complexities of algorithms for asymptotic
analysis. These notations are mathematical tools to represent the complexities. There are
three notations that are commonly used.
Big Oh Notation
Big-Oh (0) notation gives an upper bound for a function f{n) to within a constant factor.
We write f{n) = O(g(n)), If there are positive constants no and c such that, to the right of no
the f(n) always lies on or below c*g(n)..
‘Ofg(n)) = { f(n} : There exist positive constant c and no such that 0 ¢ f(n) < ¢ g(n), for all n 2 no
}
Big Omega Notation
Big-Omega (0) notation gives a lower bound for a function f(n) to within a constant factor.
We write f(n) = Q(g(n)), If there are positive constants no and c such that, to the right of no
the f(n) always lies on or above c*g(n).
‘(g(n)) = {F(n) : There exist positive constant c and no such that 0 < ¢ g(n) < f(n), for all n > no
}
Big Theta Notation
Big-Theta(®) notation gives bound for a function f(n) to within a constant factor.
ls
Scanned with CamScanner flo)
= gin)
a
‘We write f(n) = ©(g(n)), If there are positive constants no and cl and c2 such that, to the right
of no the f(n) always lies between c1*g(n) and c2*g(n) inclusive.
G{g{n)) = {f{n) : There exist positive constant ct, c2 and ng such that 0 < ci g(n) < f{n) < c2
8(n), forall n> no}
Fundamentals of Algorithmic Problem Solving:
Understand the problem
*
Decide on:
computational means,
exact vs. approximate solving,
algorithm design technique
+
Design an algorithm \«
ee
Prove correctness
*.
Analyze the algorithm
*
Code the algorithm
Scanned with CamScanner eR
.
« Understanding the Problem:
From a practical perspective, the first thing you need to do before designing an algorithm is
to understand completely the problem given. Read the problem’s description carefully and
. ask questions if you have any doubts about the problem, do a few small examples by hand,
think about special cases, and ask questions again if needed.
‘An input to an algorithm specifies an instance of the problem the algorithm solves. It is very
important to specify exactly the set of instances the algorithm needs to handle. If you fail to
. do this, your algorithm may work correctly for a majority of inputs but crash on some
“boundary” value, Remember that a correct algorithm is not one that works most of the time,
.
but one that works correctly for all legitimate inputs,
°
< Ascertaining the Capabilities of the Computational Device:
< It means how the objects can be represented using the different computational devices and
how the operations would be implemented on these objects. We have to assure that the
s capabilities of the computational devices must be good and select between the exact and
3 approximate solutions of the problem, To get these solutions, we have to implement the
F appropriate data structures. According to the problem specification and computational
° means, the appropriate algorithm design technique may be applied. Some examples of the
iS algorithm design techniques are:
eS © Divide and conquer technique
* Greedy approach
e
© Dynamic programming
Back trekking
© Branch and Bound etc.
e
3 Design an Algorithm:
es Based upon selected algorithm design technique, a computational model is developed to
E solve the given problem. There are different methods to design the algorithm, The most
< common method is based on use of pseudocodes.
= Prove Correctness:
* Once an algorithm has been specified, you have to prove its correctness. That is, you have to
e prove that the algorithm yields a required result for every legitimate input in 2 finite amount
of time. There must be correct output for each input in a finite time. For this purpose, we may
. use different mathematical formulae and concepts like mathematical induction for recursion.
e
Analyzing an Algorithm
°
Analysis of an algorithm means how much the algorithm is good?
=. as
We usually want our algorithms to possess several qualities, After correctness, by farthe most
° important is efficiency. In fac, there are two kinds of algorithm efficiency: time efficiency,
e indicating how fast the algorithm runs, and space efficiency, indicating how much extra
.
° memory it use
e
eo |7 =
Scanned with CamScanner Another desirable characteristic of an algorithm is simplicity. Unlike efficiency, which can be
precisely defined and investigated with mathematical rigor, simplicity, like beauty, is to a
considerable degree in the eye of the beholder.
Yet another desirable characteristic of an algorithm is generality. There are, in fact, two issues
here: generality of the problem the algorithm solves and the set of inputs it accepts. On the
first issue, note that it is sometimes easier to design an algorithm for a problem posed in more
general terms. Consider, for example, the problem of determining whether two integers are
relatively prime, ie., whether their only common divisor is equal to 1. It is easier to design an
algorithm for a more general problem of computing the greatest common divisor of two
integers and, to solve the former problem, check whether the GCD is 1 or not. There are
situations, however, where designing a more general algorithm is unnecessary or difficult or
even impossible. For example, it is unnecessary to sort a list of m numbers to find its median,
which is its n/2 th smallest element. To give another example, the standard formula for roots
of a quadratic equation cannot be generalized to handle polynomials of arbitrary degrees.
Coding an algorithm:
At last, any algorithm is implemented as a computer program. This step includes that how the
object and operations in the algorithm are represented in the selected programming
language.
Scanned with CamScanner ee — —
=| Classification of Nal SUicine
if Nal Bec laaes ane mnbawelly divided iat ling”
Gilinaten 2 i imi tive dats. Wructires
Gii)-Non=Prinoibive das. LG bihen
i] es
Vii bee Non- Primibive
octet Stetina aan Sis
aac peal a
pos
=f +f f
Totegue Pow” chy. Rahat fry Ui Bus }
jl
Gnd these kind
Scanned with CamScanner ‘PAGE NO.
[pm
—
=
gp
toms on Dole Slincl
Hint dalii_appeasing geal alec otal a
“Si 2. ko of the opesskiess —
Et Biel cA cyst fsb ptomacane dda
jth Suareiog 1 fnis operstive ; fob the pastenes ef The sleditl.
| Fine the totations ff ott 1 ee
| ity Sonting : dk Onan pig lal al
—~_— 1 pia = to Une. yD cecs od.
Bote ARs Aika aie efit e e
| data ee i the LY of data thin M4 Dt wae abs
| Ct tarw Conditions:
ecord ¢; that contin Iw, fn the |
| fpecodd) ono be prowaced. a
Fra vse: cee seing The a. a
Daief Cetin Hs i Abiealitney
Sain eee
poo ee ee ey ee |
4 4. Se
- th Lome ¢ -
bor “ornaye
Scanned with CamScanner FRENE:
[exe
ees 5 idtzgen TLtenbes Apc
Se + asi
niet tat | re ample ! po ee
I,
7 (te acces IE fit eas
le Je —
fae daca ps at iel on clea
dase element poll be Specifies
Te
‘ Qo} and ala) bese LeveL «
[uate aang sl alisoys be Kore
b pe Aaad fn
Got sass ohentenG Dhol
dm aman, ie: The Bids an ahdog—§ on Ey ef
L oui
iven by Wil
Cuppetound= lowebound) +1
$$) fon the above ald if pnvutel be (9-0) +/ =l0.
Whe, Ours The awe 6b sund of The, aAsan ound
4 inde app ound » F
ie cette ay Ti
pratt Line aad other.
fein |)
fe Lied hae ptet)
Cin >? ail,
a
(b for baiting Gan ao
de st [aukex ath; ee
Wwe Oke mo? OY Uoastinng Qe a weeks
% rgadmp Tn 2B omoy , Ho woos!
Scanned with CamScanner [PAGE NO.
lore] TT
eS
te ah ater sows Seu awk!
Gr iste 2 A tiatt ox a ineans sides
~— 20. celleetien sf Voxiable relia Groin eng ed
are ll tre omit Commonly used n= prirmitice. bala
| Atimetian: Ary elimeat: fe
fern ing addasrs odes
eka ty ds We Use pai
dietd | ef Ahe Las” Must be pnioles Lip :
a3 Hemet, a Mated Lif! jn a tinean
res Pcatlectien al meoli es leh bs Dna
xvas | |-Aineor order in given og —ntens of Dainliis 3
Linked List With S-Nedec
4 Pe Rioter field ee Node
To Formeties Fett of thind Node
~D_|Staoki: A Mack in also an ovdehed calle ction Lelemputs Jee,
Ae | ir a. _fpedat be cli
insation of cement fon be _done_endy fron one end Cobted
Lhe TOP 4 Tre Adele. Du $0" popes iP Ge oan
A | Cold os ast in by a lol Atiaaddiane CULE A).
A Or could be Haught” of jus Like fr plolis plocd —
Ads a hej Mules ays (Ble ofl 0 fe
—__] ro cthe op one paced ealS
“ Dae Aleck ale the hsp
és
Scanned with CamScanner Queues be Gite: ase (a faba But: (Fieo) Ie
clot Alfin.ctins Toa qustist meno elenieaG are
qutut fra o a
lend catted te Pho T end. femcaal a teeplgl
pie
ene 6 fst O_O 2 AI: Ee xenp!
i name and Sfeavels_ ~ak Kine, etal of _—
veut) aad the, fobs ylhig
ft ine taacastiony i s
a ee eh
\
end. :
oc. Fw les |e LET
FRont Boag,
= usu with S y elements =
(_|Tuux: At .
— mum bu Baty exchuive. in pan
‘Scanned with CamScanner = poe Aecacchiiny “Ine grvagh- Veatiees on the raph are Ahan. -
| Abfinetinne, capi ; ine cit
Ad Ke ctirss Sk Wes nd_applicatiznd fn hiverse fields —
A Graph GIV,E) in a. sek of Vestine Vand edeaé Aa
a Point orci clin ond edged one dlaaion od Obed me
en.
\ \
*
St 7 %, iW Vv
= Nhuctid aad Weghld Guph + = Unckinseled Groph +
]
Scanned with CamScanner Fao: sf Anal ff ‘thm
i Aratstizaliies’ pith iy
a NH tT
51 Dale. Arolysin, Gnd Vidwehizaien
o_eyon Piste Nstitin and Atandanaleffiieney Clases
Mathematical tray Saeeeoek ene
/w) Amovtizatio : An _amoatized aria ee [ehh Pte
W_Armortization : abe
[Aad of operations fe Aho i
—da_Amold , toh ip a single opin mit ae dep a onget
bet eens LE foafets te fieding the. Newent al
OVA Ou _wOAsE Case defence patrons,
i
rs Tt ib nok. Jecithmic_Hichnique > ls just a_oose acc ubok,
I srebinigua analysing rithms. Under Some Canoitions |
Ane oie. Aeweral Kohniquis uned_in amostined. | awatipcts rN
(0 Agata ti ins - Bi
{I On Accouvirg Or Taxation meted ag
(iip_Palintial Method
_——Aggpett Ae Pn. ogg “ howe (6 compas
boat tone, unebing nes Tn). fe. te! esp of 1 -opaating
[Ge amorcth whoge) Cost_of each ¢ operat in" “ro9fn?
— Grama tired coh sin+ applied IF each dpetabion rn Bh
Ott ana Aosta gps Opsotions im tee Aare
' — Aon Sapajelt acai mare
—— TL) fv os AL pina
SL Rr aT eae
Example. Atal 6p Pern Cion = MvLT) Pop ">:
Push — Prods an ehtvaenl” Js tne Lisp of. Maxk
boP ~ ldalis_ov sti fron the ‘tape ¥ Abner,
I eh Oe one f ith
_ i On, autre
i] MULTI Po PCS.
ba Jobibe yoo Aloe tmp Sedat
i iirease de chor (3)!
nee eee
Scanned with CamScanner ee -
. eA
-bPehodties MuttifoP yohich ~vi Deut a
| ch vemaves kK phic
a PJ a
SaEs Ltipsp 4 i Gitar ctl
HUweh me ust Has Alia in empl ch.
3 Thue Ae Afoele epevallns fy, The voartt" cane
A Aefutect oto pst, psp and enubdipyp opevelisas
pao er oialy Senply Abate Qne Worl ease caste
04 rouUGipy vatinn iy Oln) Afnu ‘the Alii Size |
Ho_aknantt n, bo rte wtoQll? cane’ Pane o ccpentiliin.|
lO) Homer al. Asstt of mpemsbe oot bed
Now, we vited Aome ny IS cwecege Orel the nibs
Arse Sf cepa relies, tn fael pre Aaa caste 4
; petetiewk onan initially empty Alek Aoi Ain) a
ae Un_become Qach exbjeu” Cows be _pepped at invest orice
—sfeceneh Mos Proll Sy Pata. Hower the Wu rnbed of fun
PoP can be catted ona on een py AXGshe. ey ae Yi
am ak Paw suimben of pulls operating alisha On). z
Ate OC) yPree. Jono he bound as dank Sittin’ papped
pay.one fre sashs shou fe si pote be TE HiT
Doce ds val fn Kile past and
Lis O(4)., theed pce poe sf on At
—epedation in O(m). Grunt amerticd tot of
Loeb Ads Opens tea san ain ep vse O(n) Jn.
stv as OAL) + Howse OU ata optatins hoe an /
—amobtired toate of oft).
OD Pecaustig. an [rxalion bs | atid S
pia if peent _Chosge yelp pewat= bpesetiie
Scanned with CamScanner Charge encerds 15 00 Lue! pif _fhin The difperoee
wh hed ano data Amelie —pbjul an cele Ge
Chedils ote bed hen “the. eperotien a Dabs ‘then
ste Ors. “Gus state! credit tered sm a lati Alaatore
jin net atiowed Jp be—ve: Te fam of amortised Cott
cary Acpusmer Opshetises aust be Gn upp. brand
— foc “The acboul peer of thane, open
ee a wwe_cfenole the “aebiol Lait of
ij_amontise cart by
——- Alek pei a
oon. usey.. veh, we_¢ tla. (arnostised Cet)
lowing ae
Hale hel pap and. 29. ulti ps Pnact be _cqit rotting,
Gye Auta cperstion ti Cesk df out af
2 pbich Lf pays _ fp The Gclivsl Coal of the sprotion..
are the CThev anes Aepesiled bon Thee CLaneent oof
Pay —tahea Lif. poppet ee
Teale. poms 3 push. tepen Cohliig, fodie hos ‘the
=e faq cinttipap ppestide 2 —_
iene cmh_ nig i ae
Reta ee Z
Scanned with CamScanner — For 204 Atgusns_of mn cperadions of pur, - papa attire
—— th dell Arno Atized Coat is_an seppecbaund a Pm —
~- Hall actin Cot. Afar Gli amoebae! C086
——Otn), 40 b the Aell aatust oh
tts Piet Metbad 3. Trtlted of Jesputenteg_prupaid.waovk, OS __
' ~CeaditAtirad esity. Bpecibje objedi in the dole AbtacGin —__
| — tee olintial vetted cf amobtited analtyin apostate oe
Repaid waar, as‘ potential enurge’ or Almply * polentiol 7 |
ae cthor can be feeleased be pay fee frucbine Bpehabes: —
KE Gre Adal Pret Lo arsocttzy with phe entihe dala
Atala athe thon Aperifye objec within the dan Atactine
bh 2 Inde dafee a. paberchinl fumetion
forte clot Attuctin. mat J, Sribintly equal AF eno ond
} do abooys Mma=neg ative, Gre amortized coat Sf an operon
Jy U6 _octinl cost ply Ghowds Sn prlintid Gnd differnt —_
(A Metatios ured in tks inetd act yi
fp De stein the initicl dats, Abiclite on_tahich ‘et opeyedie
ps -PUsformed. See a unl
One
DY > Neto tw slate AtLudbiins afte jt operate. a
Cpe Dk dn tke ae tinal oak ef im operation.
La. PM 10.0 Polinkiad prune etenps each Di Nodne be
Lo? 115 _foliatiah Voda edi), Anelteale 4D.) 20. oad
aa pd) 7.0fr nt. Lo
he _Amnaiizedl Cable of 1M gperatin with wespedk 45 pin
—__doffined ay
GSE FPO) = pO) —O- ————
Lat ag = ld) —4 (oe) Fecehonge fo polit
ee & = G+ hh as
Aine, tata Oma atizers Cont” ofrc on) Bptrelvs — ta be
pa Ti Ht by burnt of ee (Fy 7 .
- Scanned with CamScanner =>
a = Ge Cope) — $0.)
SG +S q0) ET ba”
ta
: ae SG + f (n+ ts) + §tD3) += Jot + 6(n3)
‘ ; & + ol bo)'}
eT = —) oT =
a morbleed cat = ue B50) “bound
nthe. tote} netiral lot er e fen
uv
Net Ney ners 1 pening Aged ene g Gols
doe Or jon enedchonge. forthe im apelin and
——Saurer On Fneroane in oti Kini torte <0
fit es On _unelerclorge arc kere Sy “aul i
— fie eration a
Se poltalid tenckion b= mo. obj 3 in Sack
Eat Stes Das) Cbs)..2.0
Shae afc Ld) wer Cusetized co!" ne
mo ectiacs worn thy tefartaels On, ble =|
Onde aekial coal”
Seanet oy — Che VET
snes eS ane 7
i ae gp elt
J—S_| Ce6 = S24
isi
0c a ot D a See psa i
‘ ate ae
ee eo
Scanned with CamScanner Basic Efficiency classes
‘The tii
ime efficiencies of a large number of algorithms fall into only a few classes.
fast, 1 constant High time efficiency
logn logarithmic
n linear
nlogn nlogn
v quadratic
w cubic
2 ‘exponential
stow ¥ n! factorial Jow time efficieney
__ Mathematical analysis (Time Efficiency) of Non-recursive Algorithms
General plan for analyzing efficiency of non-recursive algorithms:
J, Decide on parameter n indicating input size
2. Identify algorithm’s basic operation
3 Check whether the number of times the basic operation is executed depends only
on the input size n. Tf it also depends on the type of input, investigate worst,
average, and best case efficiency separately.
4, Setup ‘summation for C(n) reflecting the number of times the algorithm's basic
operation is executed.
5, Simplify summation using standard formulas
Example: Finding the largest element in a given array
ALOGORITHM MaxElement(A(0..n-1)
“perermines the value of largest element in a given array
‘Maput: An array A[0..n-1] of real ruumbers
Output: The value of the largest element in A
currentMax < AO]
for ie 1ton-1 do
if Ali) > currentMax
currentMax — Ali}
return currentMax
Scanned with CamScanner p
Analysis:
1. Input size: number of elements
2. Basic operation:
a) Comparison
b) Assignment
NO best, worst, average cases.
Let C (n) denotes number of comparisons:
each execution of the loop, which is repeatet
i within the bound between I and n ~ 1
nel
c@= SL’
(size of the array)
Algorithm makes one comparison on
for each value of the loop’s variable
5. Simplify summation using standard formulas
wt :
14st
CM) = SLF_ (oy mumder ot times)
i=1
C@=1) Or) =n}
Cine O(n)
Example: Element uniqueness problem
Algorithm UniqueElements (A[0..n-1])
Checks whether all the elements in a given array are distinct
Minput: An array A[O.n-1]
‘WOurput: Returns true if all she elements in
fori € Oton-2do
forj €i+ 1ton—1 do
iff] == AU)
return false
Aare distinct and false otherwise
return true
Analysis
1. Input size: number of elements =n (size of the array)
Basie operation: Comparison
Best, worst, average cases EXISTS.
Worst case input is an array giving largest comparisons.
‘= Array with no equal elements
2 Array with last two elements are the only pait of equal elements
4, Let C (n) denotes number of comparisons in worst case: Algorithm makes one
comparison for each repetition ofthe innermost loop i-e., for each value of the
Toop's variable j between is limits i+ 7 and m ~ Is and this i repeated for each
ayy a
Scanned with CamScanner wir
value of the outer loop i.e, for each value of the loop’s variable i between its
limits 0 and n-2
n-2/n-1
cm= S132 )
i= Kj:
5. Simplify summation using standard formulas
n-2
C@= > @-D-G+D+)
fo oa
a2
CMs Dl (n-1-i)
0
n-2 n-2
Cim)= DU 1) Dis t
= =O in
coe o-n Fo > ** £0
a &
ne
c@=@-p>1- S22e DY) +
i=0
Coys @-Da-p - @-2e-V
2
C@= (n-1)(@-1) - m=2)
2
Cin)= (n-1)2n-2-n+2)
2
Ci) =(-) @)2
in’ —n)/2
= (n?)/2 — n/2
Cac OW)
Scanned with CamScanner G Gove tee fllowstag pecuever wind
~ eeusion tae method 37
T (wo)
PPO
= 2T a) +71
a T tH) +m)
Sy Tim) = 7 mh) 4-0
Rost node.
we Be
z
14n4+2
uu
fa “pen
&
of
O06 @ O-
4 ARE Kg :
dar 2k oy yeaah
syen ap amy re me sa tae
mers TON RREHHOKHHTHYVOBYHWY YC YT E YH ~ -
" Comflenily= eK
> lag
Ow OY 06 ©
h
\ J vil
bre ! 6
I Jeet Ey )
Scanne J with CamScanner
nna MMOD SD Ar n- ) por 17)
Sohation Bt | et) es +n a
Tot) = T (m-1-1) + n-!)
(Tims = 7 (yn) + (9)
Subsite TN 4 (I)
Th) = Tmyring+ 2
3 TLE
Reuncive
Tex
T (9-2) = T (m-27!)+ (n2)
pea Th Sam
SubdhdWa fn ean ®
T(w) = Tha) 92) +f) 40
Recursive ais
Term
TM) =Tin3a-1) +(n-3)
FT) = Toray (H-5]
SR
Pk 19 ep
T(m) = T(r-4) tna) +23 ptmeen
'
'
T(wj< 7 (n-thea ate)
¥ (m-(n- i ——y
Scanned with CamScanner
POP PLPLPPLLLLEP PPP PRDD DPR A PD Ppp qo Thy) = TY) pr tet pee +n
= [rite - wnee EN
Cee ee
Ae.
= “A patina q]
~ 3 [ox + (m1)
- “Tot a1]
nN (m4) _ en
ms one) Qe,
Tne Or) |
© 7 tm. } Teo) leg nif IQ:
rir Hey ]
T (4) = T (1-1-1) + bag f-1)
. Thy + bey (ml) furin)
t 2
(m) ze TER balmy) pap
Tid = Tlyr-1) + ly n-)
FT (may 4
fn
fuk “4. oe }
Scanned uith CamScanner UE————
1) 0
Ten) = -TUns)-+ eg n>) + HY aig
TO} = T(m-Con) + bog (n= (2) E
+ bsg (m- (N-4)) + --- +g» a
= TOY +404 beg thy +. - ‘i
aaae + bein Z
= 1 Lapa + bags a lagha thy i
| bog fren - “hog 29 4 uj» | =
Pad dof (DB UE-- aM)
SIF WG kr eae ty T
KN «
= \+4o9(])
- \4+ Jef (1°)
‘Scanned with CamScanner Tln) = ln logo
“The © Ol mlga)
; @ 7 “T lv) TE) +e ym
ae
TIS) = T(4) +
TR) 40 borin ®
ls, Uadte re
Thy) = T(R)+ Re ==)
Ei eats ete
| Ty 6
Scanne J with CamScanner
_— b Pa ey ey Pay PY Py Poy Boy Bo Bf Bol BS fy
4 Bt |
“Thay = TC) + Ke
def
al
ae
m= 2k
“Taleing Log oo bolb Lido
tym ap
egos Kk ba?
Ik biog oy
THM)= TU) 4 bans
=elace lyn
Je “FOR O(n)
+
Scanne J with CamScanner __—_———————————=<_——
Maslavs Method | Maalen!s Tnnorers
We forme nce of Une “Pe
Fey svat(Zy av
0
where Os! br , 40) _awelp
Combe goles} with msl Mued
Core Tie CRIG OH Nevarion!) a a seg
~~ Ib Tix) = 0 ane “=. jo ore
a: a.
Constant Ero, then T(n) <8 (at)
Care- TEs. (BIG- OMEGA NOTATION) 97679
Trips a [nl re) ero,
“hen THN) = 9 Ly)
Gre Tir (Q - Notation) ( equotit)
= sage
a Tin = 6 (w | )
Mineo: TW: 0 (mm xetg
Scanned with CamScanner Uo Toy = a toyy +
ler ws tompaxe Jver pacuurrence, wath
Tuy) = an") + tl»).
Q@2@ bea, > a ve fom
’
To bind ye),
a
b g
nV on tt
anh y
=~ Bytes
flr) = 4tHy= 7?
$$ ogin)
Hew. Coke- opples piee
[Thy = 6)
@ Tey =2T(Va) Halogen , using Malet
nethed}: /
As De gies KCunerte In mol aoe lf
he.
fdawderol ReECUmHeR Thel om
Jlond wiry rica atl BOs un bowee
ic ceil tole the egunivalin” ey. roe
fave B eke Sone it pO ons —
a Rie
(Sn he \
-
“> 2 K 1 ke lan.
n= [p> = K =
. “I Scanned with CamScanner ® Ler Tot) = SUS)
po aT (ie) +e i
> Sly) -29(K) +4
SOx) = 2 6Ck) +k
hehee er, b= , b=!
“Te find glk),
Kei er
Fue bik) = 4lk)
*. Ge Th pall be apples.
SCk) =6CK * lyk)
T (ok) = 0 (K* Lyk)
G) To) = cul) tnt
arb", bre, f= yt
=) we fie ow
fom > 4ln)
TO) 20 (m1),
Scanned with CamScanner
04
a a
Coe Ds. Oo (n) = 27 (Ya) FS tanttom
WO Peerame w 2}
pias
oe
me
defini
TOs oT (et) +o
\TO5 = 27 OM ¢ |
DL Avot
(Tos) = S(k)
Uke 2 s(le) + ec
’. Q@=21, b>2, fl Cc.
ie oe
jn = K > ioleine qn.
(ey +c
tye 9H rfl)
OS" $d = Blk)
T(2*) - OLR)
PTO) = 6 (lps |
cannes J with CamScanner
AN ANHHKA LA eee eee ee
© wn inal oppeadie be ave frome :
Tony> oT Cy) On a
2 rim = UTy,) t leg n
a=2, bar, Lor} = ojo
WE
Y= fe
na i
at = 7 finde ep |
aay i =™ ail :
Multipy both T') = Hf)
&de by ban
th nya dap
Treg will nes epuer.
& As po anel 9 tn) tall Neve
we, lau
aT
Scanned with CamScanner UNIT-II
Divide and conquer: Binary search, Strassen’s matrix multiplication, closest-pair and convex-
hull problems.
Sorting Algorithm: Counting sort, radix sort.
Dynamic Programming: Overview, difference between dynamic programming and divide and
conquer, multistage graphs, optimal binary search trees, knapsack problem, fast fourier
transform. ———
Divide and conquer: In divide and conquer approach, the problem in hand, is divided into
smaller sub-problems and then each problem is solved independently. When we keep on
dividing the sub problems into even smaller sub-problems, we may eventually reach a stage
where no more division is possible. Those "atomic" smallest possible sub-problem (fractions)
are solved. The solution of all sub-problems is finally merged in order to obtain the solution
of an original problem.
abe de to hi db Problem
Dvide (2 » © @ oe iE a falinjtr Sub-Problam
conmuer (A) 8 6 BE FG H 1 J Sub-Solution
acperF GHG Solution
Merge a
Broadly, we can understand divide-and-conquer approach in a three-step process:
1. Divide/Break |
This step involves breaking the problem into smaller sub-problems. Sub-
problems should represent a part of the original problem. This step generally takes a
recursive approach to divide the problem until no sub-problem is further divisible. At
this stage, sub-problems become atomic in nature but still represent some part of the
actual problem.
2. Conquer/Solve
This step receives a lot of smaller sub-problems to be solved. Generally, at this
level, the problems are considered ‘solved’ on their own.
Scanned with CamScanner 3, Mage | comb toe:
When the smaller sub-problems are solved, this stage recursively combines them
until they formulate a solution of the original problem. This algorithmic approach works
recursively and conquer & merge steps works so close that they appear as one.
Examples
The following computer algorithms are based on divide-and-conquer programming
approach -
© Merge Sort
+ Quick Sort
+ Binary Search
‘+ Strassen's Matrix Multiplication
‘+ Closest pair (points)
Binary Search:
«Binary search is the search technique which works efficiently on the sorted lists .e. it
works only on a sorted set of elements. Hence, in arder to search an element into
some list by using binary search technique, we must ensure that the list is sorted
© Abinary search is an advanced type of search algorithm that finds and fetches data
from a sorted list of items. Its core working principle involves dividing the data in the
list to half until the required value is located and displayed to the user in the search
result. Binary search is commonly known as a half-interval search or a logarithmic
search.
Binary Search Algorithm:
Binary_search ( L, low, high, k)
1. Iflow> high, then
Binary search is unsuccessful, print “element not found”.
2. Else compute: low + high)/2
CASE 1: if k= L{mid], then print, “element found”,
return mid.
CASE 2: if k< L{mid}, then
Binary_search (L, low, mid-1, k)
CASE 3: if k< L{mid], then
Binary_search (L, mid+1, high, k)
3, End
For a binary search to work, it is mandatory for the target array to be sorted/ ordered.
Example:
Consider the following sorted array and let us assume that we need to search the location of
element 21 using binary search.
1, L= 12, 21, 25, 30, 34, 39, 45, 50, 55, 59, 63, 69, 70, 74, 75
Scanned with CamScanner 2-13 _]4 [5 Je |7 [8 |9 |10 [11 [12 [23 [a4 Jas
i
12 [21 [25 [30 [34 [39 [45 [so [55 [59 [63 [69 [70 |74 [75
i. Asthe given array is sorted, and k= 21, so we will find the value of mid as:
lows 1 and high= 15 hence mid= (low+ high)/2 = (1+15)/2= 8
L{mid]= L [8] = 50 which is greater than k= 21.
Hence, now we will try to search the element in the left sub list.
ii, L=[12, 21, 25, 30, 34, 39, 45]
low= 1, high= 7 so mid =4
L [mid]= L [4] = 30 which is again greater than k= 21 so we again consider the left sub
list to search element k=21.
ii, L= (42,21, 25)
low= 1, high= 3 and mid= 2
L [2] = 21 which is equal to k=21 i.e. K=L [ mid], hence element found and search is
successful.
2, L=18, 21, 23, 25,29, 35, 39, 45, 47, 48, 50, 61, 66, 69
Use binary search algorithm to find element 66.
1_]2_13_[4 [5 [6 [7 [s [9 [10 [11 faz [13 |14
18/21 [23 [25 [29 |35 [39 [45 [47 [4a |so |e [66 [6s
i. low= 4, high= 14, mid> (lows high)/2= (1+14)/2=7.5 = ceil (7.5) =8
L [8] = 45 which is less then k= 66.
‘As K>L [mid] , so we will search right sub list.
ii, L=[47, 48, 50, 61, 66, 69]
Lowe 1,, high= 6 , mid = ceil (3.5) =4
[4] = 61 which is less then k= 66 so we will search right sub list.
iii, L= [66,69]
low = 1, high= 2, mide floor(1.5)= 1
L [1]= 66 which is equal to k=66, hence element found and search Is successful.
. low+ high)/2= (1+14)/2= 7.5 = cell (7.5) =8
L [8] = 45 which is less then k= 66.
‘As K> L [mid] , so we will search right sub list.
3 10 it wz B 14
a7 48 50 61 66 69
I= (9 + 14)/2= floor (11.5) = 11
Lf]
‘Ask >L [mid], so we will search right sub list.
az 13, 14
61 66 69
3
Scanned with CamScanner
5-2
JS IID IF IID DS 9 5 eS > 2
)
J 22) St 5S 9 SSD
) IP J)
3
JP VIO
Ji
low= 12, high= 14, mid= 13
L [13] = 66 which is equal to K= 66
Hence element found at 13" position and search is successful.
Strassen‘s Matrix Multiplication:
Given two square matrices A and B of size nxn each, find their multiplication matrix.
Naive Method
Following is a simple way to multiply two matrices.
void multiply(int Af](N}, int B[J{W], int C{IN}) t
{
for {int i= 0; i< N; i++)
{
for (int j = 0; j