Algorithms Analysis & Design - Lecture 1

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

2. What is an algorithm?
–An algorithm is a finite set of instructionsfor solving a problem in a
finite amount of time.
Computer
Problem
algorithm
input output
Al Khowarizmi

3. Greatest Common Divisor (GCD)
–The problem is given 2 numbers m and n find their greatest common
divisor (GCD).
▪Algorithm 1: Euclid’s Algorithm
▪Algorithm 2: Middle-school Algorithm

4. 1) Euclid’s algorithm
Step 1: If n = 0, return mand stop; otherwise go to Step 2.
Step 2: Divide mby nand assign the value of the remainder to r.
Step 3: Assign the value of n to m and the value of r to n. Go to Step 1.
while n ≠0 do
r ←m mod n
m ←n
n ←r
return m

5. Examples: GCD(60,24) = 12, GCD(60,0) = 60, GCD(0,0) = 0
Euclid’s algorithm is based on repeated application of equality until the second number
becomes 0, which makes the problem trivial.
GCD(m,n) = GCD(n, m mod n)
Example: GCD(60,24) = GCD(24, 60%24) = GCD(12, 24%12) = 12
12 0m n
Time complexity: O( log
2( min(m, n) ) ) = O(log
2??????)

O( log
2 ( min(60, 24) ) ) = O(log
224)
≈ 4.58

6. 2) Middle-school algorithm
Step 1: Find the prime factorization of m.
Step 2: Find the prime factorization of n.
Step 3: Find all the common prime factors.
Step 4: Compute the product of all the common primefactorsand return it as GCD(m,n).

7. Example: Find GCD(60,24).
▪Divide 60 by the smallest prime number (2): 60 ÷ 2 = 30
▪Divide 30 by 2 again: 30 ÷ 2 = 15
▪15 is not divisible by 2, so move to the next prime (3): 15 ÷ 3 = 5
▪5 is a prime number, so, the prime factorization of 60 is:
60 = 2
2
× 3
1
× 5
1
▪Divide 24 by the smallest prime number (2): 24 ÷ 2 = 12
▪Divide 12 by 2 again: 12 ÷ 2 = 6
▪Divide 6 by 2 again: 6 ÷ 2 = 3
▪3 is a prime number, so, the prime factorization of 24 is:
24 = 2
3
× 3
1
Step
1
Step
2

8. 60 = 2
2
× 3
1
× 5
1
24 = 2
3
× 3
1Step
3
Common factors: 2
2
× 3
1
Step
4
Result: 2
2
× 3
1
= 12
∴ GCD60,24 = 12
•Time complexity: Omax�,� = O(??????)
Omax60,24 = O(60)
≈7.75

9. Square Root Finding
Problem: design an algorithm for computing the square root of any positive
integer n without using any comparisons, your algorithm may only use the four
basic arithmetic operations.
Used equation (Numerical Analysis – Newton-Raphson Method):
??????
??????+1=
1
2
??????
?????? +
??????
??????
??????
When ??????=0,??????
0 is any initial guess of your choice.
Newton’s method is the method used by most software applications to
calculate roots.

10. Example: find 4 .
??????
??????+1=
1
2
??????
?????? +
??????
??????
??????
Let ??????
0=4
??????=0 ??????
1=
1
2
??????
0 +
4
??????0
=
1
2
4+
4
4
=2.5
??????=4
??????=1 ??????
2=
1
2
??????
1 +
4
??????1
=
1
2
2.5+
4
2.5
=2.05
??????=2 ??????
3=
1
2
??????
2 +
4
??????2
=
1
2
2.05+
4
2.05
=2.006
??????=3??????
4=
1
2
??????
3 +
4
??????
3
=
1
2
2.006+
4
2.006
≈2

11. Thank You!