Chapter 3

The Fundamentals:
Algorithms
The Integers
 Objectives
⚫ Algorithms
⚫ The Growth of Functions
⚫ Complexity of Algorithms
⚫ The Integers and Division
⚫ Primes and Greatest Common Divisors
⚫ Integers and Algorithms
 3.1- Algorithms (Thuật toán)

An algorithm is a finite set of precise

instructions for performing a computation or
for solving a problem.
(Thuật toán là một thủ tục xác định dùng một số bước hữu hạn để
giải một bài toán.)
Specifying an algorithm: natural language/
pseudocode
Properties of an algorithm
ALGORITHM 1.
Finding the Maximum Element in a Finite
Sequence.

Ex: Finding the Maximum Element in a Finite Sequence {8, 4, 11, 3, 10}.
ALGORITHM 2.
The Linear Search Algorithm.
(Xác định vị trí của một phần tử trong một bảng liệt kê theo thứ tự)

Example. List all the steps used to search for 9 in the sequence 2, 3, 4, 5, 6, 8,
9, 11 using a linear search. How many comparisons required to search for 9 in the
sequence.
 ALGORITHM 3.
The Binary Search Algorithm.

Example: To search for 19 in the list

1, 2, 3, 5, 6, 7, 8, 10, 12, 13, 15, 16, 18, 19, 20, 22
 Sorting

Defined: Putting elements into a list in which the elements are in

increasing order.
There are some sorting algorithms:
⚫ Bubble sort
⚫ Insertion sort
⚫ Selection sort (exercise p. 178)
⚫ Binary insertion sort (exercise p. 179)
⚫ Shaker sort (exercise p.259)
⚫ Merge sort and quick sort (section 4.4)
⚫ Tournament sort (10.2)
 Bubble Sort
EXAMPLE: Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.
Example. Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.
 Insertion Sort
procedure insertion sort (a1,a2,…,an :real numbers with n ≥ 2)
for j:= 2 to n { j: position of the examined element }
begin
{finding out the right position of aj }
i:=1 a: 1 2 3 6 7 8 5 9 12 11
while aj > ai i:= i+1 j= 7
m:=aj { save aj } i=4
{ moving j-i elements backward } m=5
for k:=0 to j-i-1 aj-k:=aj-k-1 a: 1 2 3 6 7 8 5 9 12 11
{move aj to the position i} a: 1 2 3 6 6 7 8 9 12 11
ai:= m a: 1 2 3 5 6 7 8 9 12 11
end
{a1,a2,…,an are sorted} It is usually not the most efficient

EX. Use the insertion sort to put the elements of the list 3, 2, 4, 1, 5 in increasing order.
 Greedy Algorithm
⚫ They are usually used to solve optimization problems: Finding
out a solution to the given problem that either minimizes or
maximizes the value of some parameter.
⚫ Selecting the best choice at each step, instead of
considering all sequences of steps that may lead to an
optimal solution.
⚫ Some problems:
– Finding a route between two cities with smallest total
mileage ( number of miles that a person passed).
– Determining a way to encode messages using the fewest
bits possible.
– Finding a set of fiber links between network nodes using
the least amount of fiber.
 3.2- The Growth of Functions
(Độ phức tạp của thuật toán)

⚫ The complexity of an algorithm that acts on a

sequence depends on the number of elements
of sequence.
⚫ The growth of a function is an approach that
help selecting the right algorithm to solve a
problem among some of them.
⚫ Big-O notation is a mathematical representation
of the growth of a function.
 3.2.1-Big-O Notation
Definition:
Let f and g be functions from the set of integers
or the set of real numbers to the set of real
numbers. We say that f(x) is O(g(x)) if there are
constants C and k such that |f(x)| ≤ C|g(x)|
whenever x>k
Example:
3.2.1-Big-O Notation
3.2.1-Big-O Notation
The Growth of
Combinations
of Functions
 Big-O: Theorem 1
Let f(x)=anxn + an-1xn-1+…+a1x+a0, where a0,a1,…,an
are real number, then f(x) is O(xn)
If x>1
|f(x)| =| anxn + an-1xn-1+…+a1x+a0|
≤ | anxn |+|an-1xn-1|+…+|a1x|+|a0| { triangle inequality }
≤ xn (| an |+|an-1xn-1/xn|+…+|a1x/xn|+|a0/xn|)
≤ xn (| an |+|an-1/x|+…+|a1/xn-1|+|a0/xn|)
≤ xn (| an |+|an-1|+…+|a1|+|a0|)
Let C= | an |+|an-1|+…+|a1|+|a0|
|f(x)| ≤ Cxn
➔ f(x) = O (xn)
Big-O: Theorems
HW.
 3.2.2- Big-Omega and Big-Theta
Notation

⚫ Big-O does not provide the lower bound for the size
of f(x)
⚫ Big-Ω, Big- θ were introduced by Donald Knuth in
the 1970s
⚫ Big-Ω provides the lower bound for the size of f(x)
⚫ Big-θ provides the upper bound and lower bound on
the size of f(x)
Big-Omega and Big-Theta Notation
 3.3- Complexity of Algorithms

⚫ Computational complexity = Time

complexity + space complexity.
⚫ Time complexity can be expressed in
terms of the number of operations used by
the algorithm.
– Average-case complexity
– Worst-case complexity
⚫ Space complexity will not be considered.
 Demo 1

Describe the time complexity of the algorithm for finding the

largest element in a set:
Procedure max ( a1,a2,…,an : integers)
max:= a1 i Number of
comparisons
for i:=2 to n
2 2
If max < ai then max:= ai 3 2 2(n-1) +1 = 2n-1
… 2 comparisions
Time Complexity is θ(n) n 2
n+1 1, max< ai is omitted
 Demo 2
Describe the average-case time complexity of the linear-search
algorithm :
Procedure linear search (x: integer, a1,a2,…,an :distinct integers)
i:=1
i Number of comparisons done
while (i ≤ n and x  ai) i:=i+1
if i ≤ n then location:= i 1 2
else location:=0 2 4
…
Avg-Complexity= [(2+4+6+…+2n) ]/n +1 +1 n 2n
= [2(1+2+3+…+n) /n+2 n+1 1, x  ai is omitted
= [2n(n+1)/2]/n + 2
=[n(n+1)]/n + 2
See demonstrations about the worst-
= n+1 + 2 = n+3
case complexity: Examples 5,6 pages
= θ(n) 195, 196
 Understanding the Complexity of
Algorithms
Complexity Terminology Problem class
Θ(1) Constant complexity Tractable (dễ), class P
Θ(log n) Logarithmic complexity Class P
Θ(n) Linear complexity Class P
Θ(n logn) n log n complexity Class P
Θ(nb) , b 1, Polynominal complexity Intractable, class NP
integer
Θ(bn), b>1 Exponential complexity
Θ(n!) Factorial complexity
NP : Non-deterministic Polynomial time
 3.4- The Integers and Division
Definition: If a and b are integers with a  0, we say that a
divides b if there is an integer c such that b=ac.
When a divides b, we say that:
a is a factor of b
b is a multiple of a
Notation: a|b : a divides b ałb : a does not divide b
Example:
3ł7 because 7/3 is not an integer
3|12 because 12/3=4 , remainder=0
Corollary 1:
a|b ^ a|c → a|(mb+nc), m,n are integers
 The Division Algorithm
Theorem 2: Division Algorithm: Let a be an integer and d a positive
integer. Then there are unique integers q and r, with 0 ≤ r<d, such
that a=dq+r
d: divisor , r : remainder, q: quotient (thương số)
Note: r can not be negative
Definition: a=dq+r
a: dividend d: divisor
q: quotient r : remainder,
q= a div d r = a mod d
Example:
101 is divided by 11 :101 = 11.9 + 2 ➔ q=9, r=2
-11 is divided by 3 : 3(-4)+ 1 ➔ q=-4, r=1
No OK : -11 is divided by 3 : 3(-3)-2 ➔ q=-3, r = -2
 Modular Arithmetic
Definition: a, b: integers, m: positive integer.
a is called congruent (đồng dư) to b modulo m if m|a-b
Notations:
a ≡ b (mod m), a is congruent to b modulo m
a  b (mod m), a is not congruent to b mod m
Examples:
15 is congruent to 6 modulo 3 because 3|15-6
15 is not congruent to 7 modulo 3 because 3 ł15-7
 Modular Arithmetic
Theorem 3
a,b: integers, m: positive integer
a ≡ b (mod m) ↔ a mod m = b mod m
Proof
(1) a ≡ b (mod m) → a mod m = b mod m
a ≡ b (mod m) → m| a-b → a-b= km→ a=b + km
→ a mod m = (b + km) mod m
→ a mod m = b mod m { km mod m = 0 }
(2) a mod m = b mod m → a ≡ b (mod m)
a = k1m + c ^ b=k2m + c → a-b = (k1-k2) m { suppose a>b)
= km { k= k1-k2}
→ m| a-b ➔ a= b (mod m)
 Modular Arithmetic…
Theorem 4
a,b: integers, m: positive integer
a and b are congruent modulo m if and only if there is
an integer k such that a = b + km
Proof
(1) a ≡ b (mod m) → a = b + km
a ≡ b (mod m) → m| a-b → a-b= km { from definition of division}
(2) a = b + km → a ≡ b (mod m)
a = b + km → a-b=km → m | a-b → a ≡ b (mod m)
 Modular Arithmetic…
Theorem 5
m: positive integer
a ≡ b (mod m) ^ c ≡ d (mod m) →
a+c ≡ b+d (mod m) ^ ac ≡ bd (mod m)
Proof : See page 204

Corollary 2:
m : positive integer, a,b : integers
(a+b) mod m = ((a mod m) + (b mod m)) mod m
ab mod m = ((a mod m)(b mod m)) mod m
Proof: page 205
 Applications of Congruences
Hashing Function: H(k) = k mod m
Using in searching data tin memory.
k: data searched, m : memory block
Examples:
H(064212848) mod 111= 14
H(037149212) mod 111= 65
Collision: H(k1) = H(k2). For example, H(107405723) = 14
 Applications of Congruences

Pseudo-random Numbers xn+1=(axn+c) mod m

a: multiplier, c: increment, x0: seed
with 2 ≤ a<m, 0 ≤ c<m, 0 ≤ x0<m
Examples:
m=9 ➔ random numbers: 0..8
a= 7, c=4, x0=3
Result: Page 207
 Applications of Congruences
Cryptography: letter 1 → letter 2
 Applications of Congruences
Cryptography: letter 1 → letter 2
Examples: shift cipher with k f(p) =(p+k) mod 26
→ f-1(p)=(p-k) mod 26
Sender: (encoding)
Message: “ABC” , k=3
Using f(p) = (p+3) mod 26 // 26 characters
ABC ➔ 0 1 2 → 3 4 5 ➔ DEF
Receiver: (decoding)
DEF ➔ 3 4 5
Using f-1(p) = (p-3) mod 26
3 4 5 ➔ 0 1 2 ➔ ABC
 3.5- Primes and Greatest Common
Divisors
Definition 1:
A positive integer p greater than 1 is called prime if the only
positive factors are 1 and p
A positive integer that is greater than 1 and is not prime is
called composite
Examples:
Primes: 2 3 5 7 11
Composites: 4 6 8 9
Finding very large primes: tests for supercomputers
 Primes…

Theorem 1- The fundamental theorem of

arithmetic:
Every positive integer greater than 1 can be written
uniquely as a prime or as the product of two or more
primes where the prime factors are written in order of
nondecreasing size
Examples:
Primes: 37
Composite: 100 = 2.2.5.5 = 2252
999 = 3.3.3.37 = 3337
 Primes…

Converting a number to prime factors

Examples: 7007
Try it to 2,3,5 : 7007 can not divided by 2,3,5
7007 : 7
1001 : 7
143: 11
13: 13
0
➔ 7007 = 72.11.13
 Primes…

Theorem 2: If n is a composite, then n has a

prime divisor less than or equal to √ ̅n
Proof:
n is a composite ➔ n = ab in which a or b is a prime
If (a> √ ̅n ^ b> √ ̅n) → ab>n ➔ false
➔ Prime divisor of n less than or equal to √ ̅n
 Primes…
Theorem 3: There are infinite many primes
Proof: page 212
Theorem 4: The prime number theorem:
The ratio of the number of primes not exceeding
x and x/ln x approaches 1 and grows with bound
( ln x: natural logarithm of x)
See page 213
Example:
x= 101000 → The odds that an integer near 101000 is
prime are approximately 1/ln 101000 ~ 1/2300
Conjectures and Open Problems About Primes

See pages: 214, 215

⚫ 3x + 1 conjecture
⚫ Twin prime conjecture: there are infinitely many twin
primes
 Greatest Common Divisors and
Least Common Multiples
Definition 2:
Let a, b be integers, not both zero. The largest
integer d such that d|a and d|b is called the
greatest common divisor of a and b.
Notation: gcd(a,b)
Example: gcd(24,36)=?
Divisors of 24: 2 3 4 6 8 12 = 2331
Divisors of 36: 2 3 4 6 9 12 18 = 2232
gcd(24,36)=12 = 2231 // Get factors having minimum power
 Greatest Common Divisors and
Least Common Multiples
Definition 3:
The integers a, b are relatively prime if their
greatest common divisor is 1

Example:
gcd(3,7)=1 ➔ 3,7 are relatively prime
gcd (17,22)=1 ➔ 17,22 are relatively prime
gcd(17,34) = 17 ➔ 17, 34 are not relatively prime
 Greatest Common Divisors and
Least Common Multiples
Definition 4:
The integers a1,a2,a3,…,an are pairwise relatively
prime if gcd(ai,aj)=1 whenever 1 ≤ i<j ≤ n
Example:
7 10 11 17 23 are pairwise relatively prime
7 10 11 16 24 are not pairwise relatively prime

➔ Adjacent number of every composite in

sequence must be a prime.
 Greatest Common Divisors and
Least Common Multiples
Definition 5:
The Least common multiple of the positive integer a
and b is the smallest integer that is divisible by both
a and b
Notation: lcm(a,b)
Example:
lcm(12,36) = 36 lcm(7,11) = 77
lcm (233572, 2433) = 243572
233572, 243370 ➔ 243572 // get maximum power
 Greatest Common Divisors and
Least Common Multiples
Theorem 5:
Let a, b be positive integers then
ab= gcd(a,b). lcm(a,b)
Example: gcd(8, 12) = 4 lcm(8,12)=24 ➔ 8.12 = 4.24
Proof: Based on analyzing a, b to prime factors to
get gcd(a,b) and lcm(a,b)
➔ ab=gcd(a,b). lcm(a,b)
 3.6- Integers and Algorithms

⚫ Representations of Integers
⚫ Algorithms for Integer Operations
⚫ Modular Exponentiation
⚫ Euclid Algorithm
 Representations of Integers
Theorem 1:
Let b be a positive integer greater than 1. Then if n is a
positive integer, it can be expressed uniquely in the form
n= akbk + ak-1bk-1+ … + a1b + a0
Where k is a nonnegative integer, a0,a1,a2,…,ak are
nonnegative integers less than b and ak  0
Proof: page 219
Example: (245)8= 2.82 + 4.8+5 = 165
Common Bases Expansions: Binary, Octal, Decimal,
Hexadecimal
Finding expansion of an integer: Pages 219, 220, 221
 Algorithm 1: Constructing Base b Expansions

Procedure base b expansion ( n: positive integer)

q:=n
k:=0
while q  0
begin
ak :=q mod b
q := q/b
k := k +1
end { The base b expansion of n is (ak-1ak-2…a1a0)}
 Algorithms for Integer Operations
Algorithm 2: Addition integers in binary format
Algorithm 3: Multiplying integers in binary format
Algorithm 4: Computing div and mod integers
Algorithm 5: Modular Exponentiation
 Algorithm 2: Adding of Integers

Complexity: O (n) procedure add ( a,b: integers)

{ a: (an-1an-2…a1a0)2 b: (bn-1bn-2…b1b0)2 }
c:=0
for j:=0 to n-1
Begin
1 1 1 0 0 d:= (aj+bj+c)/2 // next carry of next step
1 1 1 0 (a) sj= aj+bj+c - 2d // result bit
+ 1 0 1 1 (b) c:=d // updating new carry to next step
1 1 0 0 1 (s) End
sn= c // rightmost bit of result
{ The binary of expansion of the sum is (snsn-1…s1s0)}
 Algorithm 3: Multiplying Integers
Complexity: O (n2)
procedure multiply ( a,b: integer)
1 1 0 (a) { a: (an-1an-2…a1a0)2 b: (bn-1bn-2…b1b0)2 }
X 1 0 1 (b) for j:= 0 to n-1 Complexity: O (n)
1 1 0 begin
+ 0 0 0 0 if bj =1 then cj := a shifted j places
1 1 0 0 0 end
1 1 1 1 0 (p) { c0, c1, …, cn-1 are the partial products }
p := 0
for j:= 0 to n-1
p:=p+cj
{p is the value of ab}
 Algorithm 4: Computing div and mod
procedure division ( a: integer; d: positive integer)
q:=0
r:= |a|
while r ≥ d {quotient= number of times of successive subtractions}
begin
r:= r-d
q := q+1
end
If a<0 and r>0 then {updating remainder when a<0}
begin
r:= d-r
q := -(q+1)
end
{ q = a div d is the quotient, r=a mod d is the remainder}
Algorithm 5: Modular Exponentiation
{ bn mod m = ? . Ex: 3644 mod 645 = 36 }
procedure mod_ex ( b: integer, n=(ak-1ak-2…a1a0)2, m: positive integer)
x:=1
power := b mod m
for i:=0 to k-1
begin
if ai=1 then x:= (x.power) mod m
power := (power.power) mod m
end
{ x equals bn mod m }

Corollary 2: ab mod m = ((a mod m)(b mod m)) mod m

bn mod m = result of successive factori mod m
 The Euclidean Algorithm
Lemma: Proof: page 228
Let a= bq+r, where a, b, q, r are integers. Then gcd(a,b) = gcd(b,r)
Example: 287 = 91.3 + 14 ➔gcd(287,91) =gcd(91,14)= 7

procedure gcd(a,b: positive integer)

x:=a
y:=b
while y  0
begin
r := x mod y
x:=y
y:= r
end {gcd(a,b) is x}
 Summary
⚫ Algorithms
⚫ The Growth of Functions
⚫ Complexity of Algorithms
⚫ The Integers and Division
⚫ Primes and Greatest Common Divisors
⚫ Integers and Algorithms
Thanks