Analysis, Design of Algorithms
CS3610
Dr. Islam Hegazy
Associate Professor
F2023 Analysis, Design of Algorithms 1
Objectives
By the end of this lecture, you will:
🡪 Solve linear second-order recurrence
🡪 Know brute force algorithms
🡪 Compute complexity of searching algorithms
🡪 Compute complexity of sorting algorithms
F2023 Analysis, Design of Algorithms 2
Agenda
01 Homogenous recurrences 02 Non-homogenous recurrences
03 Brute-force algorithms
F2023 Analysis, Design of Algorithms 3
Homogenous recurrences
🡪 A homogeneous recurrence is a recurrence of the form:
𝑎0𝑇(𝑛) + 𝑎1𝑇(𝑛 − 1) + . . . + 𝑎𝑘𝑇(𝑛 − 𝑘) = 0
🡪 This recurrence is:
1. Homogenous
1. Linear - it does not contain terms of the form 𝑇(𝑛)𝑘, 𝑘 ≠ 1;
2. Homogeneous – linear combination of 𝑇(𝑛 − 𝑖) is 0;
3. With constant coefficients (𝑎𝑖 ∈ ℝ, 0 ≤ 𝑖 ≤ 𝑘)
🡪 Get the characteristic equation for such recurrence
F2023 Analysis, Design of Algorithms 4
Homogenous recurrences
1. Homogenous
F2023 Analysis, Design of Algorithms 5
Homogenous recurrences
1. Homogenous
F2023 Analysis, Design of Algorithms 6
Homogenous recurrences – Example
1. Homogenous
F2023 Analysis, Design of Algorithms 7
Homogenous recurrences – Example
1. Homogenous
F2023 Analysis, Design of Algorithms 8
Agenda
01 Homogenous recurrences 02 Non-homogenous recurrences
03 Brute-force algorithms
F2023 Analysis, Design of Algorithms 9
Non-homogenous recurrences
🡪 A non-homogeneous recurrence is a recurrence of the form:
𝑎0𝑇(𝑛) + 𝑎1𝑇(𝑛 − 1) + . . . + 𝑎𝑘𝑇(𝑛 − 𝑘) ≠ 0
2. Non-homogenous
🡪 Try to reduce the non-homogeneous recurrence in a homogeneous recurrence
F2023 Analysis, Design of Algorithms 10
Non-homogenous recurrences – Example
🡪 Compute the nth Fibonacci number recursively
🡪 Input: non-negative integer n
🡪 Output: nth Fibonacci number
2. Non-homogenous
F(n):
if n<= 1
return n
else
return F(n-1) + F(n-2)
F2023 Analysis, Design of Algorithms 11
Non-homogenous recurrences – Example
🡪 Recurrence relation:
A(n) = A(n-1) + A(n-2) + 1 for n>1
A(1) = 1, A(0) = 1
2. Non-homogenous
A(n) - A(n-1) - A(n-2) = 1
🡪 Convert to a homogenous recurrence
[A(n)+1] – [A(n-1)+1] – [A(n-2)+1] = 0
Let B(n) = A(n) + 1
B(n) – B(n-1) – B(n-2) = 0
r2 – r – 1 = 0
F2023 Analysis, Design of Algorithms 12
Agenda
01 Homogenous recurrences 02 Non-homogenous recurrences
03 Brute-force algorithms
F2023 Analysis, Design of Algorithms 13
Brute-force algorithms
🡪 Straightforward methods of solving a problem that rely on sheer computing
power and trying every possibility rather than advanced techniques to improve
efficiency.
3. Brute-force
🡪 For example, if you have a small padlock with digits from 0-9. You forgot your
combination of 4 digits, but you don't want to buy another padlock. Since you
can't remember any of the digits, you have to use a brute force method to open
the lock.
F2023 Analysis, Design of Algorithms 14
Brute-force algorithms – Sequential search
🡪 Implements sequential search with a search key as a sentinel
🡪 Input: An array A of n elements and a search key K
🡪 Output: The index of the first element in A[0..n − 1] whose value is equal to K or
−1 if no such element is found
3. Brute-force
SequentialSearch2(A[0..n], K)
A[n]←K
i ←0
while A[i] = K do
i ←i + 1
if i < n
T(n) = O(𝑛)
return i
T(n) = Ω(1)
else return −1
F2023 Analysis, Design of Algorithms 15
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
55 10 26 5 12
3. Brute-force
0 1 2 3 4
Original list
F2023 Analysis, Design of Algorithms 16
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 1 55 10 26 5 12
F2023 Analysis, Design of Algorithms 17
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 1 10 55 26 5 12
F2023 Analysis, Design of Algorithms 18
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 1 10 26 55 5 12
F2023 Analysis, Design of Algorithms 19
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 1 10 26 5 55 12
F2023 Analysis, Design of Algorithms 20
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 1 10 26 5 55 12
F2023 Analysis, Design of Algorithms 21
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 2 10 26 5 12 55
F2023 Analysis, Design of Algorithms 22
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 2 10 26 5 12 55
F2023 Analysis, Design of Algorithms 23
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 2 10 5 26 12 55
F2023 Analysis, Design of Algorithms 24
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 2 10 5 12 26 55
F2023 Analysis, Design of Algorithms 25
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 3 10 5 12 26 55
F2023 Analysis, Design of Algorithms 26
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 3 5 10 12 26 55
F2023 Analysis, Design of Algorithms 27
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 3 5 10 12 26 55
F2023 Analysis, Design of Algorithms 28
Brute-force algorithms – Bubble sort
🡪 Compare adjacent elements, and swap them if necessary
🡪 Repeat until the list is sorted
3. Brute-force
Pass 4 5 10 12 26 55
No swap in pass 4
🡪 Stop
F2023 Analysis, Design of Algorithms 29
Brute-force algorithms – Bubble sort
🡪 Sorts a given array by bubble sort
🡪 Input: An array A[0..n − 1] of orderable elements
🡪 Output: Array A[0..n − 1] sorted in nondecreasing order
3. Brute-force
BubbleSort(A[0..n − 1])
for i ←0 to n − 2 do
for j ←0 to n − 2 − i do
if A[j + 1]<A[j]
swap A[j] and A[j + 1]
T(n) = O(𝑛2)
T(n) = Ω(n)
F2023 Analysis, Design of Algorithms 30
Brute-force algorithms – Selection sort
🡪 The algorithm maintains two subarrays in a given array
• The subarray which is already sorted.
• Remaining subarray which is unsorted.
🡪 Repeatedly find the minimum element from unsorted part and putting it at the
3. Brute-force
right position.
55 10 26 5 12
Original list
F2023 Analysis, Design of Algorithms 31
Brute-force algorithms – Selection sort
🡪 Repeatedly find the minimum element from unsorted part and putting it at the
right position.
🡪 Step 1: Find the minimum element and put it at position 0
3. Brute-force
Minimum = 5 10 26 55 12
position 0
F2023 Analysis, Design of Algorithms 32
Brute-force algorithms – Selection sort
🡪 Repeatedly find the minimum element from unsorted part and putting it at the
right position.
🡪 Step 2: Find the minimum element and put it at position 1
3. Brute-force
Minimum = 5 10 26 55 12
position 1
F2023 Analysis, Design of Algorithms 33
Brute-force algorithms – Selection sort
🡪 Repeatedly find the minimum element from unsorted part and putting it at the
right position.
🡪 Step 1: Find the minimum element and put it at position 2
3. Brute-force
Minimum = 5 10 12 55 26
position 4
F2023 Analysis, Design of Algorithms 34
Brute-force algorithms – Selection sort
🡪 Repeatedly find the minimum element from unsorted part and putting it at the
right position.
🡪 Step 1: Find the minimum element and put it at position 3
3. Brute-force
Minimum = 5 10 12 26 55
position 4
F2023 Analysis, Design of Algorithms 35
Brute-force algorithms – Selection sort
🡪 Sorts a given array by selection sort
🡪 Input: An array A[0..n − 1] of orderable elements
🡪 Output: Array A[0..n − 1] sorted in nondecreasing order
3. Brute-force
SelectionSort(A[0..n − 1])
for i ←0 to n − 2 do
min ← i
for j ←i+1 to n − 1 do
if A[j + 1]<A[min]
min ← j
swap A[i] and A[min]
T(n) = O(𝑛2)
T(n) = Ω(𝑛2)
F2023 Analysis, Design of Algorithms 36
Brute-force algorithms – String match
🡪 Given a string of n characters called the text and a string of m characters (m ≤ n)
called the pattern, find a substring of the text that matches the pattern.
🡪 Input: An array T [0..n −1] of n characters representing a text and an array
P[0..m−1] of m characters representing a pattern
3. Brute-force
🡪 Output: The index of the first character in the text that starts a matching
substring or −1 if the search is unsuccessful
F2023 Analysis, Design of Algorithms 37
Brute-force algorithms – String match
BruteForceStringMatch(T [0..n − 1], P[0..m − 1])
for i ←0 to n − m do
j ←0
while j <m and P[j] = T [i + j] do
j ←j + 1
3. Brute-force
if j = m
return i
return −1
T(n) = O(m𝑛)
T(n) = Ω(𝑛)
F2023 Analysis, Design of Algorithms 38
Brute-force algorithms – Closest pair
3. Brute-force
F2023 Analysis, Design of Algorithms 39
Brute-force algorithms – Closest pair
🡪 Finds distance between two closest points in the plane by brute force
🡪 Input: A list P of n (n ≥ 2) points p1(x1, y1), . . . , pn(xn, yn)
🡪 Output: The distance between the closest pair of points
BruteForceClosestPair(P)
3. Brute-force
d←∞
for i ←1 to n − 1 do
for j ←i + 1 to n do
d ←min(d, sqrt((xi − xj)2 + (yi− yj)2))
return d
T(n) = O(𝑛2)
T(n) = Ω(𝑛2)
F2023 Analysis, Design of Algorithms 40
Summary
🡪 Homogenous recurrence relation
🡪 Non-homogenous recurrence relation
🡪 Brute force algorithms: sequential search, bubble sort, selection sort, string
match, closest pair
3. Brute-force
F2023 Analysis, Design of Algorithms 41
F2023 Analysis, Design of Algorithms 42
