Algorithms Analysis & Design - Lecture 5

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

3. What is brute-force?
–The first algorithm design strategy we shall explore together.
–A straightforward approach to solving problem, usually based on problem statement
and definitions of the concepts involved.
–"Force" comes from using computer power not intellectual power.
–In short, "brute force" means "Just do it!".

4. Why brute-force?
–We have already seen two brute force algorithms:
•Consecutive Integer Checking for GCD(m, n)
•Definition based matrix-multiplication
–It’s the only general approach that always works.
–Seldom gives efficient solution, but one can easily improve the brute force version.
–Usually can solve small sized instances of a problem.
–A yardstick to compare with more efficient algorithms.

6. Brute-force

7. Selection Sort
2 8 5 3 9 4 1
–The list is divided into two sub lists, sorted and unsorted.
–We find the smallest element from the unsorted sub-list and swap it with the element at the
beginning of the unsorted data.
–After each selection and swapping, the wall between the two sub-lists moves one element ahead,
increasing the number of sorted elements and decreasing the number of unsorted ones.
–A list of � elements requires �−1 passes to completely rearrange the data.

10. Complexity:
▪Worst Case: O(�
2
)
–input list is sorted in descending order (e.g., 7, 6, 5, 4, 3, 2, 1).
▪Average Case: O(�
2
)
▪Best Case: O(�
2
)
–input list is sorted in ascending order (e.g., 1, 2, 3, 4, 5, 6, 7).
??????�=෍
�=0
??????−2
෍
�=�+1
??????−1
1=෍
�=0
??????−2
�−1−�+1+1
2
×1+1=෍
�=0
??????−2
�−1−�
=
�−2−0+1
2
×�−1−0+�−1−�−2=
��−1
2

11. Advantages:
▪It’s simple and easy to implement.
▪It can be used for small data sets.
▪In-place sorting algorithm.
Disadvantages:
▪Running time of Selection sort algorithm is very poor – �(�
2
).
▪In case of large data sets, the efficiency of selection sort drops.

12. Brute-force

13. Bubble Sort
–In bubble sorting, consecutive adjacent pairs of elements in the array are
compared with each other.
–If the element at the lower index is greater than the element at the higher index,
the two elements are interchanged so that the element is placed before the
bigger one.
–This process will continue till the list of unsorted elements exhausts.
–This procedure of sorting is called bubble sorting because greater elements
‘bubble’ to the top of the list.

16. Complexity:
▪Worst Case: O(�
2
)
▪Average Case: O(�
2
)
▪Best Case: O(�)
–if a pass through the list makes no swaps, the list is sorted and we
can stop the algorithm.
??????�=෍
�=0
??????−2
෍
�=0
??????−2−�
1=෍
�=0
??????−2
�−2−�−0+1
2
×1+1=෍
�=0
??????−2
�−1−�
=
�−2−0+1
2
×�−1−0+�−1−�−2=
��−1
2

17. Best Case

18. Advantages:
▪Simple and easy to implement.
▪In this sort, elements are swapped in place without using additional
temporary storage, so the space requirement is at a minimum.
▪A stable sorting algorithm.
Disadvantages:
▪It’s a slow method — O�
2
.
▪Inefficient for large sorting lists.

19. Brute-force

20. Linear (or Sequential) Search
–Linear Search is one of the simplest search algorithms to understand and
implement.
–It can be used on both sorted and unsorted data.
–The algorithm checks each element in the array or list sequentially until the
desired element is found or the end of the list is reached.
target

22. 2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
2 8 5 3 9 4
Initial
Unsorted List
Example:
Target: find 9
1
st
Iteration
2
nd
Iteration
3
rd
Iteration
4
th
Iteration
5
th
Iteration
2 == 9 ?
8 == 9 ?
5 == 9 ?
3 == 9 ?
9 == 9 ?
Target

23. Complexity:
▪Worst Case: O(�) — last element
▪Average Case: O(�)
▪Best Case: O(1) — first element
Advantages:
▪The algorithm is straightforward to implement with minimal code.
▪Linear Search can be applied to any data structure that supports sequential access, such as
arrays, linked lists, and even files.
▪Linear Search is an in-place search algorithm and does not require any additional memory.
Disadvantages:
▪It’s inefficient for large datasets because it may require examining each element.

24. Brute-force

26. 0 1 2 3 4 5 6 7 8 9 1011
HELLO,WORLD!
0 1 2
LLO
??????
�
Size of ??????: �=12
Size of �: �=3
�
�

27. 0 1 2 3 4 5 6 7 8 9 1011
HELLO,WORLD!
0 1 2
LLO
??????
�
Size of ??????: �=12
Size of �: �=3
�
�

28. 0 1 2 3 4 5 6 7 8 9 1011
HELLO,WORLD!
0 1 2
LLO
??????
�
Size of ??????: �=12
Size of �: �=3
�
�

29. 0 1 2 3 4 5 6 7 8 9 1011
HELLO,WORLD!
0 1 2
LLO
??????
�
Size of ??????: �=12
Size of �: �=3
�
�

30. 0 1 2 3 4 5 6 7 8 9 1011
HELLO,WORLD!
0 1 2
LLO
??????
�
Size of ??????: �=12
Size of �: �=3
�
�

31. 0 1 2 3 4 5 6 7 8 9 1011
HELLO,WORLD!
0 1 2 3
LLO
??????
�
Size of ??????: �=12
Size of �: �=3
�
�
Done!

32. –Worst Case: O�×�
•The algorithm has to make all � comparisons before shifting the pattern, (
)
�−�+
1�.
–Best Case: O(�)
•The first character of the pattern is not present in text at all.
Complexity
HE LLO
M M
??????
�

33. Thank You!