�Discrete Mathematics (MAD101)

Lecture notes by PhuongVTM

(phuongvtm11@fe.edu.vn/

minhphuong1105.sphn@gmail.com)

​

Chapter 3:

The Integers & Algorithms

• Algorithms
• Growth of Functions
• The integers: division, primes, greatest common divisors
• Integers & Algorithm

​

1.1 Algorithm

• Definition: An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.
• Example: Searching, Finding Max, Min, Sorting,...
• Properties of algorithms:
• Input. An algorithm has input values from a specified set.
• Output. From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.
• Definiteness. The steps of an algorithm must be defined precisely.
• Correctness. An algorithm should produce the correct output values for each set of input values.
• Finiteness. An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.
• Effectiveness. It must be possible to perform each step of an algorithm exactly and in a finite amount of time.
• Generality. The procedure should be applicable for all problems of the desired form, not just for a particular set of input values.

1.1 Algorithm

• Finding max

(Pseudocode)

Procedure max (a₁,a₂,a₃,…,a_n: integers):

max:=a₁

for i:=2 to n

if max < a_i then max:= a_i

return max {max is the largest element}

​

Example: How many comparisons needed? How many assignments needed in worst case?

a) 5, 2,1, 3, 0

b) 1, 2, 3, 5

1.1 Algorithm

• Searching Algorithm

Linear Search (tìm tuyến tính)

​

Procedure linear search (x: integer, a₁,a₂,…,a_n :distinct integers)

i:=1

while i ≤ n and x ≠ a_i

i:=i+1

if i ≤ n then location:= i

else location:=0

return location {location is the subscript of the term that equals x, or is 0 if x is not found}

​

Example: x= 5

a= 7,8,2,5,6

1.1 Algorithm

• Searching Algorithm

Binary Search (tìm nhị phân)

procedure binary search ( x:integer, a₁,a₂,…,a_n : increasing integers)

i:=1 { i is left endpoint of search interval} input: x=5

j:=n { j is right endpoint of search interval} a=1,4,6,7,8,9

while i<j ouput: ?

m:= ⎣(i+j)/2⎦

if x>a_m then i:=m+1

else j:= m

if x=a_i then location := i

else location:=0

return location {location is the subscript of the term that equals x, or is 0 if x is not found}

1.1 Algorithm

• Sorting (sắp xếp)

Bubble Sort (sắp xếp nổi bọt)

​

procedure bubble sort (a₁,a₂,…,a_n :real numbers with n ≥ 2)

for i:= 1 to n-1

for j:=1 to n- i

if a_j > a_j+1 then interchange a_j and a_j+1

{a₁,a₂,…,a_n are sorted}

​

Example: 3, 2, 4, 1, 5

1. How many comparisons?
2. How many comparisons in the worst case ?

​

1.1 Algorithm

• Sorting (sắp xếp)

Bubble Sort (sắp xếp nổi bọt)

1.1 Algorithm

Insertion Sort (sắp xếp chèn)

​

procedure insertion sort (a₁,a₂,…,a_n :real numbers with n ≥ 2)

for j:= 2 to n { j: position of the examined element }

begin

{ finding out the right position of a_j }

i:=1

while i<j and a_j > a_i

i:= i+1

m:=a_j { save a_j }

{ moving j-i elements backward }

for k:=0 to j-i-1 a_j-k:=a_j-k-1

{move a_j to the position i}

a_i:= m

end

{a₁,a₂,…,a_n are sorted}

a: 1 2 3 5 7 4 6 (n= 7)

j=6

i=3

m=4

a: 1 2 3 4 6

a: 1 2 3 5 6

a: 1 2 3 4 5 7 6

5 7

5 7

1.1 Algorithm

• Greedy Algorithm (Thuật tham lam)
• Use: solve optimization problems: finding max, min
• Method: select the best choice at each step, instead of considering all steps that may lead to the optimal solution (sometime ‘not efficient' in term of time, complexity of algorithm…)

Example:

• Find the shortest path from city A to city B
• Encode messages/ information using fewest bits
• Change an amount of money with fewest number of coins

​

1.1 Algorithm

• Greedy Algorithm (Thuật tham lam)

Greedy Change-Making Algorithm. (thuật đổi tiền)

Procedure change(c₁,c₂,...,c_r: values of denominations (mệnh giá) of coins, where c₁ > c₂ > ··· > c_r ; n: a positive integer (số tiền cần đổi))

for j := 1 to r

dⱼ := 0 // dⱼ counts the coins of denomination cⱼ used

while n ≥ cⱼ

dⱼ := dⱼ + 1 // add a coin of denomination cⱼ

n := n−cⱼ

// d_i is the number of coins of denomination c_i in the change for i = 1,2,...,r

Example: a) n=135, c= 20, 10, 5

b) n=135, c= 20,10,1

c) n= 135, c=20, 10, 7

​

1.1 Algorithm

• Quiz:

Q1: Consider the algorithm “Finding Max”. How many comparisons are done when the output is a= 1, 2, 6, 3, 7, 5 ?

1. 5 B. 6 C. 11 D. 12 E. Neither

Q2: Given the sequence: 5 7 1 3 2 4. What is the result obtained when the second loop of the Bubble Sort is executed ?

1. 7 5 1 3 2 4
2. 5 1 3 2 4 7
3. 1 3 2 4 5 7
4. 1 2 3 4 5 7

Q3. Consider the algorithm “Linear Search”. How many comparisons are done in the worst case for an input string of length n ?

1. n B. 2n C. 2n-1 D. 2n+2 E. Neither

​

1.2 The Growth of Functions

Big- O Notion

• Definition: Let f(x) be a function defined on a set of numbers D ( D can be ℕ, ℕ*, ℝ, or ℝ₊… ) to ℝ. We say that f(x) is O(g(x)) if
• there is a constant C>0
• there is a number k ∈ ℝ such that

| f(x) | ≤ C| g(x) | , for all x > k.

Notation: f(x)= O(g(x))

Remark: f(x) is O(g(x)) if and only if the quotient f(x)/g(x) is bounded for x > k !

• Example 1: Let f(x)= x² and g(x)= x².
• f(x) is O(g(x)). An easy way to see this is to consider the quotient :

| f(x)/g(x) | = | x /x² | = | 1/x | < 1, for all x > 1.

So f(x)=O(g(x)) (here C= 1 and k= 1 )

1.2 The Growth of Functions

Big- O Notion

• Example 1: Let f(x)= x and g(x)= x².

b) g(x) is not O(g(x)). Indeed, consider the quotient

| g(x)/f(x) | = | x²/x | = | x | , which is not bounded when x is increasing to infinity !

• Example 2: f(x)= x² + 2x +1, g(x) = x² . Then f(x) is O(g(x)) :

| f(x)/g(x) | = | (x² + 2x +1) /x² | = | 1+ 2/x + 1/ x² |

We see that | 1+ 2/x + 1/ x² | ≤ 1 + 2+ 1 = 4 , for all x >1 . So

| f(x)/g(x) | < 4 ⇔ | (x² + 2x +1) | < 4x², for all x > 1,

which means that x² + 2x +1 is O(x²).

(see the picture below)

1.2 The Growth of Functions

Big- O Notion

​

1.2 The Growth of Functions

Big- O Notation

• Theorem:
• Let f(x)= aₙxⁿ +aₙ₋₁xⁿ⁻¹ +...+a₁x +a₀ be a polynomial of degree n (aₙ ≠ 0). Then f(x) is O(xⁿ).
• Let f(x) be a polynomial of degree m, g(x) be a polynomial of degree n (m ≥ n). Then

​

• Example 3: (n ∈ ℕ*) Consider two functions log(n) and n. Then log(n) is O(n), since n grows “faster” than log(n). More precisely, we can verify that

which implies that log(n)/n is bounded when n is large, so log(n)=O(n) !

1.2 The Growth of Functions

Big- O Notation

The Big-O notation classifies the order of functions by its growth (mức độ tăng trưởng) :

1 log(n) n nlog(n) n² aⁿ n!

In this list, each function is “smaller” than the succeeding function (when n is large)

(you can easily verify by computing the limit of each quotient )

• Example: log(n⁴ +n) is O(log(n)).

when n > 1, we can estimate: n⁴ +n < n⁴ + n⁴ = 2n⁴

⇒ log(n⁴ +n) < log(2n⁴) = log(2) + log(n⁴) = 4log(n)+log(2)

Since 4log(n)+log(2) is O(log(n)), we can conclude that log(n⁴ +n) is also O(log(n)!

1.2 The Growth of Functions

Big- O Notation

1.2 The Growth of Functions

Big- O Notation

• Theorem: Suppose that f(x) = aₙxⁿ +aₙ₋₁xⁿ⁻¹ +...+a₁x +a₀

is a polynomial of degree n (aₙ ≠ 0). Then log(f(x)) is O(log(x))

• Exercise: Arrange the following functions in a list so that each function is Big-O of the next function:

n, , 2ⁿ, log(n¹º), nlog(n), n²

1.2 The Growth of Functions

Big- 𝛀 and Big- 𝛉 Notation

• Definition: Let f(x), g(x) be real functions. We say that
• f(x) is 𝛺(g(x)) (reading Big-Omega) if there is C >0 and k >0 such that

|f(x)| ≥ C|g(x)|, for all x > k

2. f(x) is 𝛳(g(x)) (reading Big-Theta) if f(x) is both O(g(x)) and 𝛺(g(x)): there exists C₁ >0 , C₂ >0 and k >0 such that

C₁|g(x)| ≤ |f(x)| ≤ C₂|g(x)|, for all x > k

• Example:
• x² is 𝛺(x), since x² > x , for all x >1 (here C= 1 and k= 1)

x² is not 𝛳(x), since x² is not O(x) !

​

​

1.2 The Growth of Functions

Big- 𝛀 and Big- 𝛉 Notation

b) log(n⁴ +n) is 𝛳(log(n)). Indeed, we have seen that log(n⁴ +n) is O(log(n)). To prove that log(n⁴ +n) is 𝛺(log(n)), we evaluate as follows :

n⁴ +n > n⁴ , for all n >0, so log(n⁴ +n) > log(n⁴)=4log(n)

which implies that log(n⁴ +n) is 𝛺(log(n)), hence log(n⁴ +n) is 𝛳(log(n)) !

• Remark: If f(x) is O(g(x)), then g(x) is 𝛺(f(x)) and conversely

For example, x is O(x²), so x² is 𝛺(x) !

• Theorem:
• If f(x) is a polynomial of degree n, then f(x)= 𝛳(xⁿ).
• log(f(n)) is 𝛳(log(n)) for any polynomial f(n) !

1.2 The Growth of Functions

1.2 The Growth of Functions

1.2 The Growth of Functions

1.2 The Growth of Functions

Find complexity (big O) of this algorithm: