digital design and algorithm module 1 ppt

ppt

1. || JAI SRI GURUDEV||
SJB INSTITUTE OF TECHNOLOGY
#67, BGS HEALTH & EDUCATION CITY, DR. VISHNUVARDHAN ROAD, KENGERI,
BENGALURU –560060,KARNATAKA, INDIA
Module 1: Introduction to Algorithms
IV Semester
Design and Analysis of algorithms
(18CS56)
By
L Kala Chandrashekhar
Asst. Prof.
Department of Computer Science and Engineering

2. COURSE OBJECTIVE:
UNDERSTAND THE BASIC CONCEPT OF ALGORITHM
DESCRIBE VARIOUS METHODS OF ALGORITHM ANALYSIS
COURSE OUTCOME:
“UNDERSTAND THE BASICS OF ALGORITHM, METHODS FOR
ANALYZING ALGORITHM AND ALSO EXPRESSING THE BOUNDARIES
OF EFFICIENCIES USING ASYMPTOTIC NOTATIONS”,

3. TABLE OF CONTENTS
•Algorithm
•What Is An Algorithm
•Euclid’sAlgorithm
•Twoforms ofEuclid’salgorithm
•Other methods for computing gcd
•Othermethodsfor finding gcdcontinued…
•SieveofEratosthenes

4. ALGORITHM
•Analgorithmisanexactspecificationofhowtosolveacomputationalproblem
•Analgorithmmustspecifyeverystepcompletely,soacomputercanimplementitwithout
anyfurther“understanding”
•Analgorithmmustworkforallpossibleinputsoftheproblem.
•Algorithmsmustbe:
•Correct:Foreachinputproduceanappropriateoutput
•Efficient:runasquicklyaspossible,anduseaslittlememoryaspossible–moreaboutthis
later
•Therecanbemanydifferentalgorithmsforeachcomputationalproblem.

5. WHATISANALGORITHM?
“Computer”
Analgorithmisasequenceofunambiguousinstructions forsolvinga
problem,i.e.,forobtainingarequired outputforanylegitimateinputin
a finiteamountof time.
Problem
Algorithm
Input Output
8

6. EUCLID’SALGORITHM
•Problem:Findgcd(m,n),thegreatest commondivisoroftwo nonnegative,not both zero
integers mandn
•Examples:gcd(60,24)= 12, gcd(60,0)= 60, gcd(0,0)=?
•Euclid’salgorithmis basedon repeatedapplicationof equality
•gcd(m,n)=gcd(n,mmodn)
•until the second number becomes 0, which makes the problem trivial.
•Example:gcd(60,24)=gcd(24,12)=gcd(12,0)=12

7. TWOFORMS OFEUCLID’SALGORITHM
•Step 1Ifn= 0,returnmand stop;otherwisegoto Step2
•Step 2Dividembynandassignthevalueoftheremaindertor
•Step 3 Assignthevalueofn to mand thevalueofrton.Goto Step1.
•whilen≠0do
•r←mmodn m← n
•n←r
•returnm

8. OTHER METHODS FOR COMPUTING GCD
Consecutiveintegercheckingalgorithm
Step 1Assignthevalueof min{m,n}tot
Step 2Dividembyt.Iftheremainderis0,gotoStep3; otherwise, gotoStep 4
Step 3Dividenbyt.Iftheremainderis0,returntandstop; otherwise, gotoStep 4
Step 4Decrease tby1andgotoStep2

9. OTHERMETHODSFOR FINDING GCDCONTINUED…
Middle-schoolprocedure
Step 1Find the prime factorization of m
Step 2Find the prime factorization of n
Step 3Findallthecommonprimefactors
Step 4Computetheproductofallthe commonprimefactors andreturnitasgcd(m,n)

10. SIEVEOFERATOSTHENES
Input:Integern≥ 2
Output:Listofprimeslessthanorequalton
for p←2to ndoA[p]←p
for p←2tosqrt(n)do
ifA[p]0//phasn’tbeeneliminatedonpreviouspasses
j←p*p
whilej ≤ n do
A[j]←0//markelement as eliminated
j←j+p
•Example:234567891011121314151617181920
•Output:235711131719

11. This Photoby Unknown Author is licensed under CC BY-SA