Mathematical Analysis of Algorithms in CMPE371 - Fall 2023-2024
CMPE371
Analysis of Algorithms
FALL
202
3
-202
4
Lecture
4
Part I
2
Mathematical Analysis of Non-recursive Algorithms
Remember that s
teps in mathematical analysis of
non-recursive algorithm
s are:
•
Decide on parameter
n
indicating
input size
•
Identify algorithm’s
basic operation
•
Determine
worst
anf
best
case for input of size
n
•
Set up summation
for
C(n)
reflecting algorithm’s
loop structure
•
Simplify summation
using standard formulas
.
3
Divide and Conquer
: Recursive Algorithms
Main Idea:
1.
Divide
the given problem
to sub-problems
2.
Solve the sub-problems
independent of each other.
3.
Conquer the solutions
By recursion!
S
imple
Example(N)
IF N=0 THEN
1
RETURN
ELSE
FOR i←1 TO N DO
N
+1
(‘x’)
N
S
imple
Example(N-1)
T(N-1)
T(N)
= O(1) if N=0
= (N+1)+N+T(N-1) = T(N-1)+
θ
(N), Otherwise
S
imple
E
xample
Calculating the algorithmic complexity
of a recursive algorithm
7
Steps in mathematical analysis of recursive
algorithms
•
Decide on parameter
n
indicating
input size
•
Identify algorithm’s
basic operation
•
Determine
worst
and
best case
for input of size
n
; depending on
the conditional operations in algorithm.
•
Set up a
recurrence relation
and initial condition(s)
•
Solve the recurrence
to obtain a closed form or estimate the
order
of growth
of the solution
.
Mathematical Analysis of Recursive Algorithms
How many moves does it take?
Did you know you should be able to complete the puzzle in (2
n
-1) moves where n is the
number of disks.
For 3 disks
2
n
-1= (2
3
– 1) = (8-1) =7 moves
Merge Sort Approach
•
To sort an array
A[p . . r]:
•
Divide
•
Divide the n-element sequence to be sorted into two
subsequences of
n/2
elements each
•
Conquer
•
Sort the subsequences recursively using merge sort
•
When the size of the sequences is 1 there is nothing more
to do
•
Merge
•
Merge the two sorted subsequences
Merge Sort
Alg.:
MERGE-SORT
(A, p, r)
if
p < r
Check for base case
then
q
←
(p + r)/2
Divide
MERGE-SORT
(A, p, q)
Conquer
MERGE-SORT
(A, q + 1, r)
Conquer
MERGE
(A, p, q, r)
Combine
•
Initial call:
MERGE-SORT
(A, 1, n)
1
2
3
4
5
6
7
8
6
2
3
1
7
4
2
5
p
r
q
Example –
n
Power of 2
Divide
Example –
n
Power of 2
Conquer
and
Merge
Example –
n
Not a Power of 2
Divide
Example –
n
Not a Power of 2
Conquer
and
Merge
Merging
•
Input:
Array
A
and indices
p, q, r
such that
p ≤
q < r
•
Subarrays
A[p . . q]
and
A[q + 1 . . r]
are sorted
•
Output:
One single sorted subarray
A[p . . r]
Merging
•
Idea for merging:
•
Two piles of sorted cards
•
Choose the smaller of the two top cards
•
Remove it and place it in the output pile
•
Repeat the process until one pile is empty
•
Take the remaining input pile and place it face-down onto
the output pile
A1
A[p, q]
A2
A[q+1, r]
A[p, r]
Example: MERGE(A, 9, 12, 16)
Example: MERGE(A, 9, 12, 16)
Example (cont.)
Example (cont.)
Example (cont.)
Done!
Merge - Pseudocode
Alg.:
MERGE(A, p, q, r)
1.
Compute
n
1
and
n
2
2.
Copy the first
n
1
elements into
L[1 . . n
1
+ 1]
and the next
n
2
elements into
R[1 . . n
2
+
1]
3.
L[n
1
+ 1]
←
;
R[n
2
+ 1]
←
4.
i
←
1; j
←
1
5.
for
k
←
p
to
r
6.
do if
L[ i ] ≤ R[ j ]
7.
then
A[k]
←
L[ i ]
8.
i
←
i + 1
9.
else
A[k]
←
R[ j ]
10.
j
←
j + 1
Running Time of Merge
(assume last for loop)
•
Initialization (copying into temporary arrays):
•
(n
1
+ n
2
) =
(n)
•
Adding the elements to the final array:
- n
iterations, each taking constant time
(n)
•
Total time for Merge:
•
(n)
Analyzing Divide-and Conquer Algorithms
•
The recurrence is based on the three steps of the
paradigm:
•
T(n)
– running time on a problem of size
n
•
Divide
the problem into
a
subproblems, each of size
n/b
:
takes
D(n)
•
Conquer
(solve) the subproblems
aT(n/b)
•
Combine
the solutions
C(n)
(1)
if
n
≤ c
T(n) =
aT(n/b) + D(n) + C(n)
otherwise
Recurrence Examples
Methods for Solving Recurrences
•
Substitution method
•
Iteration method
•
Recursion tree method
•
Master method
Explore the mathematical analysis of algorithms in CMPE371 for Fall 2023-2024, focusing on non-recursive and recursive algorithms. Learn how to analyze non-recursive algorithms by deciding on input size parameters, identifying basic operations, and simplifying summations. Dive into recursive algorithms, where you divide, solve, and conquer sub-problems through recursion. Calculate algorithmic complexity and understand the steps for analyzing recursive algorithms based on input size and conditional operations.
Uploaded on Sep 11, 2024 | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CMPE371 Analysis of Algorithms FALL 2023-2024 Lecture 4 Part I
Mathematical Analysis of Non-recursive Algorithms Remember that steps in mathematical analysis of non-recursive algorithms are: Decide on parameter n indicating input size Identify algorithm s basic operation Determine worst anf best case for input of size n Set up summation for C(n) reflecting algorithm s loop structure Simplify summation using standard formulas. 2
Divide and Conquer: Recursive Algorithms Main Idea: 1. Divide the given problem to sub-problems 2. Solve the sub-problems independent of each other. 3. Conquer the solutions By recursion! 3
Simple Example SimpleExample(N) IF N=0 THEN RETURN ELSE 1 FOR i 1 TO N DO PRINT( x ) SimpleExample(N-1) N+1 N T(N-1) T(N) = O(1) if N=0 = (N+1)+N+T(N-1) = T(N-1)+ (N), Otherwise
Calculating the algorithmic complexity of a recursive algorithm
Mathematical Analysis of Recursive Algorithms Steps in mathematical analysis of recursive algorithms Decide on parameter n indicating input size Identify algorithm s basic operation Determine worst and best case for input of size n; depending on the conditional operations in algorithm. Set up a recurrence relation and initial condition(s) Solve the recurrence to obtain a closed form or estimate the order of growth of the solution. 7
How many moves does it take? Did you know you should be able to complete the puzzle in (2n-1) moves where n is the number of disks. For 3 disks 2n-1= (23 1) = (8-1) =7 moves
Merge Sort Approach To sort an array A[p . . r]: Divide Divide the n-element sequence to be sorted into two subsequences of n/2 elements each Conquer Sort the subsequences recursively using merge sort When the size of the sequences is 1 there is nothing more to do Merge Merge the two sorted subsequences
Merge Sort r p q 1 5 2 2 3 4 4 7 5 1 6 3 7 2 8 6 Alg.: MERGE-SORT(A, p, r) if p < r Check for base case then q (p + r)/2 Divide MERGE-SORT(A, p, q) Conquer MERGE-SORT(A, q + 1, r) Conquer MERGE(A, p, q, r) Combine Initial call: MERGE-SORT(A, 1, n)
Example n Power of 2 1 5 2 2 3 4 4 7 5 1 6 3 7 2 8 6 Divide q = 4 1 5 2 2 3 4 4 7 5 6 7 8 1 3 2 6 1 5 2 2 3 4 4 7 5 6 7 8 1 3 2 6 5 1 5 2 2 3 4 4 7 6 7 8 1 3 2 6
Example n Power of 2 1 1 2 2 3 2 4 3 5 4 6 5 7 6 8 7 Conquer and Merge 1 2 2 4 3 5 4 7 5 6 7 8 1 2 3 6 1 2 2 5 3 4 4 7 5 6 7 8 1 3 2 6 5 1 5 2 2 3 4 4 7 6 7 8 1 3 2 6
Example n Not a Power of 2 1 2 3 4 5 6 7 8 9 10 11 4 7 2 6 1 4 7 3 5 2 6 q = 6 Divide 1 2 3 4 5 6 7 8 9 10 11 4 7 2 6 1 4 7 3 5 2 6 q = 3 q = 9 1 2 3 4 5 6 7 8 9 10 11 4 7 2 6 1 4 7 3 5 2 6 1 2 3 4 5 6 7 8 9 10 11 4 7 2 6 1 4 7 3 5 2 6 1 2 4 5 7 8 4 7 6 1 7 3
Example n Not a Power of 2 1 2 3 4 5 6 7 8 9 10 11 Conquer and Merge 1 2 2 3 4 4 5 6 6 7 7 1 2 3 4 5 6 7 8 9 10 11 1 2 4 4 6 7 2 3 5 6 7 1 2 3 4 5 6 7 8 9 10 11 2 4 7 1 4 6 3 5 7 2 6 1 2 3 4 5 6 7 8 9 10 11 4 7 2 1 6 4 3 7 5 2 6 1 2 4 5 7 8 4 7 6 1 7 3
Merging r p q 1 2 2 4 3 5 4 7 5 1 6 2 7 3 8 6 Input: Array A and indices p, q, r such that q < r Subarrays A[p . . q] and A[q + 1 . . r] are sorted Output: One single sorted subarray A[p . . r] p
r p q Merging 1 2 2 4 3 5 4 7 5 1 6 2 7 3 8 6 Idea for merging: Two piles of sorted cards Choose the smaller of the two top cards Remove it and place it in the output pile Repeat the process until one pile is empty Take the remaining input pile and place it face-down onto the output pile A1 A[p, q] A[p, r] A2 A[q+1, r]
Example: MERGE(A, 9, 12, 16) p p q q r r
Example (cont.) Done!
Merge - Pseudocode Alg.: MERGE(A, p, q, r) 1. Compute n1and n2 2. Copy the first n1elements into L[1 . . n1+ 1] and the next n2elements into R[1 . . n2+ 1] 3. L[n1+ 1] ; 4. i 1; j 1 5. for k p to r 6. do if L[ i ] R[ j ] 7. then A[k] L[ i ] 8. i i + 1 9. else A[k] R[ j ] 10. j j + 1 r p q 1 2 2 4 3 5 4 7 5 1 6 2 7 3 8 6 n2 n1 R[n2+ 1] p q 2 4 5 7 L q + 1 r 1 2 3 6 R
Running Time of Merge (assume last for loop) Initialization (copying into temporary arrays): (n1+ n2) = (n) Adding the elements to the final array: - n iterations, each taking constant time (n) Total time for Merge: (n)
Analyzing Divide-and Conquer Algorithms The recurrence is based on the three steps of the paradigm: T(n) running time on a problem of size n Divide the problem into a subproblems, each of size n/b: takes D(n) Conquer (solve) the subproblems aT(n/b) Combine the solutions C(n) (1) T(n) = aT(n/b) + D(n) + C(n) otherwise if n c
Recurrence Examples = = 0 0 n 0 0 n = ( ) T n = ( ) T n + ( ) 1 0 n T n n + ( ) 1 0 c T n n = = 1 c n 1 c n = ( ) T n = ( ) T n n n + + 1 aT cn n 2 1 T c n b 2
Methods for Solving Recurrences Substitution method Iteration method Recursion tree method Master method
