Algorithms Analysis & Design - Lecture 8

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

4. –Brute-force: �
??????
= � ∗ � ∗ � ∗⋯ ∗ � O(n)
–Divide N Conquer: �
??????
= �
??????/2
∗ �
??????/2
O(log n)
•e.g., �
8
=�
4
∗�
4
=�
2
∗�
2
∗�
2
∗�
2
=�
1
∗�
1
∗�
1
∗�
1
∗�
1
∗�
1
∗�
1
∗�
1
–Decrease by one: �
??????
=�
??????−1
∗� O(n)
•e.g., �
8
=�
7
∗�=�
6
∗�∗�=⋯= �×�×�×�×�×�×�×�
–Decrease by constant factor: �
??????
=�
Τ
??????
2
2
O(log n)
•e.g., �
8
=�
42
=�
22
2
=�∗�
2
2
Exponentiation Problem (�
??????
)

5. Decrease N Conquer

6. Insertion Sort
–Insertion Sort is one of the simplest sorting algorithms, making it easy to
understand and implement.
–The algorithm mimics the way card players sort a hand of cards, by picking
and placing cards in the correct position.
–It is efficient for small datasets or arrays that are already mostly sorted.
–To insert an element into its correct position, it shifts larger elements to
the right.

8. Insertion Sort Algorithm
1)Iterate through the array starting from the second element.
2)For each element, compare it with the elements in the sorted portion of the array (to the
left of it).
3)Shift elements in the sorted portion to the right until the correct position for the current
element is found.
4)Insert the current element into its correct position in the sorted portion.
5)Repeat steps 2-4 until the entire array is sorted.
2 8 5 3 9 4

10. Complexity:
▪Worst Case: ??????(??????
2
)
▪Average Case: ??????(??????
2
)
▪Best Case: ??????(??????)
Advantages:
▪Relatively simple and easy to implement on small sets of data.
▪Can be efficiently implemented on datasets that are already substantially sorted.
▪The insertion sort is an in-place sorting algorithm.
▪Insertion sort is stable because it maintains the relative order of equal elements.
Disadvantages:
▪Inefficient for large sorting lists — ??????(??????
2
)

12. Assignment
Apply insertion sort to sort the list E, X, A, M, P, L, E in
alphabetical order.

13. Solution
E X A M P L E
E X
E X A
A E X M
A E M X P
A E M P X L
A E L M P X E
A E E L M P X

14. Decrease N Conquer

15. Topological Sorting
–Digraph is a short name of directed graph.
–Directed Acyclic Graph (DAG) is a finite directed graph with no directed cycles.
–Topological sort of a DAG G = (V, E) is a linear ordering of all its vertices such that
if G contains an edge (u, v), then u appears before v in the ordering.
–Topological sort of a graph can be viewed as an ordering of its vertices along a
horizontal line so that all directed edges go from left to right.
–If a back edge has been encountered, the digraph is not a DAG, and topological
sorting of its vertices is impossible.
–Topological sort problem may have several alternative solutions.

16. Directed Acyclic Graph

17. Applications of Topological Sorting
–Task Scheduling: Course scheduling, Project management, …, etc.
–Software Dependency Resolution: Package management systems and makefiles.
–Deadlock Detection: resource allocation in operating systems.
–Data Serialization: database backup and replication.
–Version Control Systems (VCS): Git rebase operations.
–Ranking Problems: PageRank algorithm for web pages.
–…
–etc.

18. 1)Store each vertex’s In-Degree (i.e., no. incoming edges) in an array.
2)While there are vertices remaining:
»Find a vertex with In-Degree zero and output it.
»Reduce In-Degree of all vertices adjacent to it by 1.
»Output and mark this vertex (In-Degree = −1).
B
A
C E
D
F
Topological Sorting Algorithm

19. A
B
C
D
E
F
0
1
2
1
2
0
In-Degree
Array
Adjacency List
B
D
E
C
C
B
A
C E
D
F
0
2
1 1
2
0
E
Topological Sorting Algorithm (Cont.)

20. Topological Sorting – Example
CA
B D
E
•Find the number of different possible topological orderings for the following
graph.

21. Topological Sorting – Example
CA
B D
E
•Step 1: write in-degree of each vertex.
0
1
2
2
2

22. Topological Sorting – Example
C
B D
E
•Step 2: vertex A has the least in-degree, so, remove it and its associated edges.
0
1
1
2
A

23. Topological Sorting – Example
•Step 3: vertex B has the least in-degree, so, remove it and its associated edges.
C
D
E
0
0
2
A B

24. Topological Sorting – Example
•Step 4: there’re two vertices with same least in-degree, so, we have 2 cases.
A B
C
D
E
0
0
2

25. Topological Sorting – Example
D
E
0
1
C
E
0
1
Case 1
(remove C)
Case 2
(remove D)
A B C A B D

26. Topological Sorting – Example
E0
E0
Case 1
(remove D)
Case 2
(remove C)
A B C A B DD C
•Step 5

27. Topological Sorting – Example
Case 1
(remove E)
Case 2
(remove E)
A B C A B DD CE E

28. •For the given graph, there are 2 different possible topological orderings as
follows
A B C D E
A B D C E
CA
B D
E
DONE!

29. –Initializing In-Degree array: O??????
–Finding vertex with In-Degree zero: O??????
2
•?????? vertices, each takes O?????? to search In-Degree array.
–Reducing In-Degree of all vertices adjacent to a vertex: O??????
–Output and mark vertex: O??????
Total Time: O??????
2
+?????? Quadratic Time!
Topological Sorting Analysis

30. Assignment
2 5
63
41
•Find the number of different possible topological orderings possible for the
following graph.

31. Decrease by a Constant Factor

32. Binary Search
–It uses the divide-and-conquer approach to reduce the search space by half with
each comparison.
–Binary Search continually divides the search interval in half and compares the
middle element with the target value.
–Binary Search requires the data to be sorted in ascending or descending order
before searching.
–Binary Search can be implemented recursively or iteratively.
1 2 3 4 5 8 9
Right or Low
0 1 2 3 4 5 6
Mid
(Low + High) / 2
Left or High
Sorted
List

35. Binary Search Algorithm
1)Let min = 0 and max = n – 1, where n is the number of elements in the sorted array.
2)Compute the midpoint:
a)mid = (low + high) / 2
3)Compare the target value with the element at the midpoint:
a)If target == array[mid], return mid (target found).
b)If target < array[mid], set high = mid - 1 (discard the right half).
c)If target > array[mid], set low = mid + 1 (discard the left half).
4)Repeat steps 2-3 until low <= high.
5)If the target value is not found after the loop, return a message indicating it is not
in the array.

36. Initial
Sorted List
Example:
Target: find 3
2
nd
Iteration
3
rd
Iteration
Target = arrmid ?
Return mid (target found).
Target < arr[mid] ?
Set high = mid - 1 (discard the right half).
Target > arr[mid] ?
Set low = mid + 1 (discard the left half).
Target
Mid High
1 2 3 4 5 8 9
1 2 3 4 5 8 9
1 2 3 4 5 8 9
Low HighMid
Low
High
Mid
Low
No. Iterations =log
27=3 iterations
1
st
Iteration

37. Mid High
1 2 3 4 5 8 913172030
Low
Mid High
1 2 3 4 5 8 913172030
Low
Mid
High
1 2 3 4 5 8 913172030
Low
Target = 20
Mid
Low + (High – Low) / 2
or
(High + Low) / 2
Target = arrmid ?
Return mid (target found).
Target < arr[mid] ?
Set high = mid - 1 (discard the right half).
Target > arr[mid] ?
Set low = mid + 1 (discard the left half).
1 2 3 4 5 8 913172030
Mid
High
Low

38. Given the list { 1, 2, 3, 4, 5, 8, 9 } and the target value 3
1. First iteration:
1.Calculate mid: mid = (0 + 6) / 2 = 3 (integer division)
2.Compare target 3 with the middle element 4
3.Since 3 < 4, update right boundary: High = 3 − 1 = 2
2. Second iteration:
1.Calculate new mid: mid = (0 + 2) / 2 = 1
2.Compare target 3 with middle element 2
3.Since 3 > 2, update low boundary: Low = 1 + 1 = 2
3. Third iteration:
1.Calculate new mid: mid = (2 + 2) / 2 = 2
2.Compare target 3 with element at index 2: 3
3.Target found at index 2
Thus, it took 3 iterations to find the target value 3.
Target
Mid High
1234589
Low HighMid
Low
High
Mid
Low
1234589
1234589

39. Complexity:
▪Worst Case: ??????(log??????)
▪Average Case: ??????log??????
▪Best Case: ??????(1) — at the middle.
Advantages:
▪The algorithm is relatively simple to implement, especially in its iterative form, and easy to understand.
▪Highly efficient and faster for searching large sorted datasets.
▪It does not require additional memory beyond a few variables for indices.
Disadvantages:
▪If the data is not sorted, Binary Search cannot be applied directly. Sorting the data first would incur additional time complexity.
▪Binary Search is not efficient for data structures that do not support random access, such as linked lists, because it relies on
indexing to access the middle element.
▪While the iterative version is simple, the recursive version can be more complex due to additional overhead from recursive
function calls, which use more stack space.
▪For small datasets, the overhead of repeatedly dividing the search space and comparing elements might make it slower compared
to a simpler linear search.

40. Decrease by a Constant Factor

41. Russian Peasant Multiplication
–Russian Peasant Multiplication, also known as Egyptian Multiplication, is an
ancient algorithm for multiplying two numbers.
–Its origins date back to ancient civilizations, including the Egyptians and Russians,
who used this method for its simplicity and ease of use with basic arithmetic
operations.
–The algorithm's beauty lies in its use of only basic operations: addition, halving,
and doubling.

42. Russian Peasant Multiplication — Algorithm
1)Let the two given numbers be 'a' and 'b'.
2)Initialize result 'res' as 0.
3)Do the following while 'b' is greater than 0
a)If 'b' is odd, add 'a' to 'res'
b)Double 'a' and halve 'b'
4)Return 'res'.

43. ÷2 ×2
&#3627408462;&#3627408463;
Cancel every row with even numbers.
&#3627408462;&#3627408463;

44. Add other rows with odd numbers.
&#3627408462;&#3627408463;
Therefore, the result of multiplying
50 by 65 is 3250.
+

45. def russianMult(a, b)
res = 0
while a > 0:
# if x is odd
if a % 2 != 0:
res += b
a = a >> 1 # halve a
b = b << 1 # doubleb
return res
Method #1

46. def russianMult(a, b)
res = 0
while a > 0:
# if x is odd
if a % 2 != 0:
res += b
a /= 2 # halve a
b *= 2 # doubleb
return res
Method #2

47. Complexity:
▪Worst Case: Olog&#3627408462; – &#3627408462; is a large integer.
▪Average Case: Olog&#3627408462; – &#3627408462; is a random integer.
▪Best Case: O(log&#3627408462;) – &#3627408462; is a very small integer.
Advantages:
▪Simplicity – easy to implement with basic arithmetic and bitwise operations.
▪Efficiency – logarithmic time complexity, scalable for large values.
Disadvantages:
▪Less practical compared to modern optimized multiplication algorithms.
▪No Built-In Hardware Optimization – relies on software-based arithmetic without direct hardware
support.

48. Thank You!