CMPE371
C
M
P
E
3
7
1
A
n
a
l
y
s
i
s
o
f
A
l
g
o
r
i
t
h
m
s
F
A
L
L
2
0
2
0
-
2
0
2
1
L
e
c
t
u
r
e
5
Analysis of Algorithms
Part II:
Algorithm Design Techniques
•
Programming paradigms
•
Brute force approach
•
Divide and conquer
•
Dynamic programming:
•
matrix chain multiplication problem
•
longest common subsequence problem
•
rod cut
ing problem
•
Greedy algorithms:
•
activity selection problem
•
fractional knapsack problem
Programming paradigms
programming paradigm
= general approach to algorithm design
= general philosophy for solving a problem
there are different ways of solving a problem
several possible programming paradigms to solve the same problem
a programming paradigm may be adapted to a certain problem and not to another
B
r
u
t
e
F
o
r
c
e
A straightforward approach, usually based directly on the problem’s
statement and definitions of the concepts involved
Examples:
1.
Computing
a
n
(
a
> 0,
n
a nonnegative integer)
2.
Computing
n
!
3.
Multiplying two matrices
4.
Searching for a key of a given value in a list
B
r
u
t
e
-
F
o
r
c
e
S
o
r
t
i
n
g
A
l
g
o
r
i
t
h
m
Selection Sort
Scan the array to find its smallest element and swap it with
the first element. Then, starting with the second element, scan the
elements to the right of it to find the smallest among them and swap it
with the second elements. Generally, on pass
i
(0
i
n-
2), find the
smallest element in
A
[
i..n-
1] and swap it with
A
[
i
]:
A
[0]
. . .
A
[
i
-1] |
A
[
i
], . . . ,
A
[
min
], . . .,
A
[
n
-1]
in their final positions
Example: 7 3 2 5
A
n
a
l
y
s
i
s
o
f
S
e
l
e
c
t
i
o
n
S
o
r
t
Time efficiency:
Space efficiency:
Stability:
Θ
Θ
(
(
n^2
n^2
)
)
Θ
Θ
(
(
1
1
), so in place
), so in place
yes
B
r
u
t
e
-
F
o
r
c
e
S
t
r
i
n
g
M
a
t
c
h
i
n
g
•
pattern
: a string of
m
characters to search for
•
text
: a (longer) string of
n
characters to search in
•
problem: find a substring in the text that matches the pattern
Brute-force algorithm
Step 1 Align pattern at beginning of text
Step 2 Moving from left to right, compare each character of
pattern to the corresponding character in text until
•
all characters are found to match (successful search); or
•
a mismatch is detected
Step 3 While pattern is not found, and the text is not yet
exhausted, realign pattern one position to the right and
repeat Step 2
E
x
a
m
p
l
e
s
o
f
B
r
u
t
e
-
F
o
r
c
e
S
t
r
i
n
g
M
a
t
c
h
i
n
g
1.
Pattern:
001011
Text:
10010101101001100101111010
2.
Pattern:
happy
Text:
It is never too late to have a happy childhood.
P
s
e
u
d
o
c
o
d
e
a
n
d
E
f
f
i
c
i
e
n
c
y
Time efficiency:
Θ
Θ
(mn)
(mn)
comparisons (in the worst case)
comparisons (in the worst case)
B
r
u
t
e
-
F
o
r
c
e
P
o
l
y
n
o
m
i
a
l
E
v
a
l
u
a
t
i
o
n
Problem: Find the value of polynomial
p
(
x
) =
a
n
x
n
+
a
n
-1
x
n
-1
+… +
a
1
x
1
+
a
0
at a point
x
=
x
0
Brute-force algorithm
Efficiency:
p
p
0.0
0.0
for
for
i
i
n
n
downto
downto
0
0
do
do
power
power
1
1
for
for
j
j
1
1
to
to
i
i
do
do
//compute
//compute
x
x
i
i
power
power
power
power
x
x
p
p
p
p
+
+
a
a
[
[
i
i
]
]
power
power
return
return
p
p
0
0
i
i
n
n
i
i
=
Θ
Θ
(n^2) multiplications
(n^2) multiplications
P
o
l
y
n
o
m
i
a
l
E
v
a
l
u
a
t
i
o
n
:
I
m
p
r
o
v
e
m
e
n
t
We can do better by evaluating from right to left:
Better brute-force algorithm
Efficiency:
p
p
a
a
[0]
[0]
power
power
1
1
for
for
i
i
1
1
to
to
n
n
do
do
power
power
power
power
x
x
p
p
p
p
+
+
a
a
[
[
i
i
]
]
power
power
return
return
p
p
Θ
Θ
(
(
n)
n)
multiplications
multiplications
B
r
u
t
e
-
F
o
r
c
e
S
t
r
e
n
g
t
h
s
a
n
d
W
e
a
k
n
e
s
s
e
s
•
Strengths
•
wide applicability
•
simplicity
•
yields reasonable algorithms for some important problems
(e.g., matrix multiplication, sorting, searching, string
matching)
•
Weaknesses
•
rarely yields efficient algorithms
•
some brute-force algorithms are unacceptably slow
•
not as constructive as some other design techniques
E
x
h
a
u
s
t
i
v
e
S
e
a
r
c
h
A brute force solution to a problem involving search for an element
with a special property, usually among combinatorial objects such
as permutations, combinations, or subsets of a set.
Method:
•
generate a list of all potential solutions to the problem in a systematic
manner
•
evaluate potential solutions one by one, disqualifying infeasible ones and,
for an optimization problem, keeping track of the best one found so far
•
when search ends, announce the solution(s) found
E
x
a
m
p
l
e
1
:
T
r
a
v
e
l
i
n
g
S
a
l
e
s
m
a
n
P
r
o
b
l
e
m
•
Given
n
cities with known distances between each pair, find the
shortest tour that passes through all the cities exactly once before
returning to the starting city
•
Alternatively: Find shortest
Hamiltonian circuit
in a weighted
connected graph
•
Example:
How do we represent a solution (Hamiltonian circuit)?
TSP by Exhaustive Search
Tour Cost
a→
b
→
c
→
d
→
a 2+3+7+5 = 17
a→
b
→
d
→
c
→
a 2+4+7+8 = 21
a→
c
→
b
→
d
→
a 8+3+4+5 = 20
a→
c
→
d
→
b
→
a 8+7+4+2 = 21
a→
d
→
b
→
c
→
a 5+4+3+8 = 20
a→
d
→
c
→
b
→
a 5+7+3+2 = 17
Efficiency:
Θ
Θ
((n-1)!)
((n-1)!)
E
x
a
m
p
l
e
2
:
K
n
a
p
s
a
c
k
P
r
o
b
l
e
m
Given
n
items:
•
weights:
w
1
w
2
… w
n
•
values:
v
1
v
2
… v
n
•
a knapsack of capacity
W
Find most valuable subset of the items that fit into the knapsack
Example: Knapsack capacity W=16
item weight value
1
2 $20
2
5 $30
3
10 $50
4
5 $10
K
n
a
p
s
a
c
k
P
r
o
b
l
e
m
b
y
E
x
h
a
u
s
t
i
v
e
S
e
a
r
c
h
Subset
Total weight
Total value
{1} 2 $20 {2} 5 $30 {3} 10 $50 {4} 5 $10 {1,2} 7 $50 {1,3} 12 $70 {1,4} 7 $30 {2,3} 15 $80 {2,4} 10 $40 {3,4} 15 $60 {1,2,3} 17 not feasible {1,2,4} 12 $60 {1,3,4} 17 not feasible {2,3,4} 20 not feasible{1,2,3,4} 22 not feasibleEfficiency:
Efficiency:
Θ
Θ
(2^n)
(2^n)
Example 3: The Assignment Problem
There are
n
people who need to be assigned to
n
jobs, one person per
job. The cost of assigning person
i
to job
j
is C[
i
,
j
]. Find an assignment
that minimizes the total cost.
Job 0 Job 1 Job 2 Job 3
Person 0 9
2 7 8
Person 1 6 4 3 7
Person 2 5 8 1 8
Person 3 7 6 9 4
Algorithmic Plan:
Generate all legitimate assignments, compute
their costs and select the cheapest one.
How many assignments are there?
Pose the problem as one about a cost matrix:
n!
cycle cover in a
graph
9 2 7 8
6 4 3 7
5 8 1 8
7 6 9 4
Assignment
(col.#s)
Total Cost
1, 2, 3, 4
9+4+1+4=18
1, 2, 4, 3
9+4+8+9=30
1, 3, 2, 4
9+3+8+4=24
1, 3, 4, 2
9+3+8+6=26
1, 4, 2, 3
9+7+8+9=33
1, 4, 3, 2
9+7+1+6=23
etc.
(For this particular instance, the optimal assignment can be found by exploiting
the specific features of the number given. It is: )
A
s
s
i
g
n
m
e
n
t
P
r
o
b
l
e
m
b
y
E
x
h
a
u
s
t
i
v
e
S
e
a
r
c
h
C =
C =
2,1,3,4
F
i
n
a
l
C
o
m
m
e
n
t
s
o
n
E
x
h
a
u
s
t
i
v
e
S
e
a
r
c
h
•
Exhaustive-search algorithms run in a realistic amount of time
only on very
small instances
•
In some cases, there are much better alternatives!
•
Euler circuits
•
shortest paths
•
minimum spanning tree
•
assignment problem
•
In many cases, exhaustive search or its variation is the only known way to get
exact solution
Divide-and-Conquer
Divide-and-Conquer
D
i
v
i
d
e
-
a
n
d
-
C
o
n
q
u
e
r
The most-well known algorithm design strategy:
1.
Divide instance of problem into two or more smaller instances
2.
Solve smaller instances recursively
3.
Obtain solution to original (larger) instance by combining these
solutions
Divide-and-Conquer Technique (cont.)
subproblem 2
of size
n
/2
subproblem 1
of size
n
/2
a solution to
subproblem 1
a solution to
the original problem
a solution to
subproblem 2
a problem of size
n
(instance)
It general leads to a
recursive algorithm!
D
i
v
i
d
e
-
a
n
d
-
C
o
n
q
u
e
r
E
x
a
m
p
l
e
s
•
Sorting: mergesort and quicksort
•
Binary tree traversals
•
Binary search (?)
•
Multiplication of large integers
•
Matrix multiplication: Strassen’s algorithm
•
Closest-pair and convex-hull algorithms
General Divide-and-Conquer Recurrence
General Divide-and-Conquer Recurrence
T
T
(
(
n
n
) =
) =
aT
aT
(
(
n/b
n/b
) +
) +
f
f
(
(
n
n
)
)
where
where
f
f
(
(
n
n
)
)
(
(
n
n
d
d
),
),
d
d
0
0
Master Theorem
Master Theorem
: If
: If
a < b
a < b
d
d
,
,
T
T
(
(
n
n
)
)
(
(
n
n
d
d
)
)
If
If
a = b
a = b
d
d
,
,
T
T
(
(
n
n
)
)
(
(
n
n
d
d
log
log
n
n
)
)
If
If
a > b
a > b
d
d
,
,
T
T
(
(
n
n
)
)
(
(
n
n
log
log
b
b
a
a
)
)
Note: The same results hold with O instead of
Note: The same results hold with O instead of
.
.
Examples:
Examples:
T
T
(
(
n
n
) = 4
) = 4
T
T
(
(
n
n
/2) +
/2) +
n
n
T
T
(
(
n
n
)
)
?
?
T
T
(
(
n
n
) = 4
) = 4
T
T
(
(
n
n
/2) +
/2) +
n
n
2
2
T
T
(
(
n
n
)
)
?
?
T
T
(
(
n
n
) = 4
) = 4
T
T
(
(
n
n
/2) +
/2) +
n
n
3
3
T
T
(
(
n
n
)
)
?
?
(
(
n^2
n^2
)
)
(
(
n^2log n
n^2log n
)
)
(
(
n^3
n^3
)
)
M
e
r
g
e
s
o
r
t
•
Split array A[0..
n
-1] into about equal halves and make
copies of each half in arrays B and C
•
Sort arrays B and C recursively
•
Merge sorted arrays B and C into array A as follows:
•
Repeat the following until no elements remain in one of
the arrays:
•
compare the first elements in the remaining
unprocessed portions of the arrays
•
copy the smaller of the two into A, while incrementing
the index indicating the unprocessed portion of that
array
•
Once all elements in one of the arrays are processed, copy
the remaining unprocessed elements from the other array
into A.
Pseudocode of Mergesort
Pseudocode of Merge
Time complexity:
Θ
Θ
(
(
p+q
p+q
)
)
=
Θ
Θ
(
(
n
n
)
)
comparisons
Mergesort Example
The non-recursive version
of Mergesort starts from
merging single elements
into sorted pairs.
Analysis of Mergesort
•
All cases have same efficiency:
Θ
(
n
log
n
)
•
Number of comparisons in the worst case is close to theoretical minimum for
comparison-based sorting:
log
2
n
!
≈
n
log
2
n
- 1.44
n
•
Space requirement:
Θ
(
n
) (
not
in-place)
•
Can be implemented without recursion (bottom-up)
T(n) = 2T(n/2) +
T(n) = 2T(n/2) +
Θ
Θ
(n), T(1) = 0
(n), T(1) = 0
Exploring various programming paradigms and algorithm design techniques including Brute force approach, Divide and conquer, Dynamic programming, Greedy algorithms, and more. The content covers Brute-Force Sorting Algorithm, Selection Sort, Time and Space efficiency analysis, String Matching, and more.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
CMPE371 Analysis of Algorithms FALL 2020-2021 Lecture 5
Analysis of Algorithms Part II: Algorithm Design Techniques Programming paradigms Brute force approach Divide and conquer Dynamic programming: matrix chain multiplication problem longest common subsequence problem rod cuting problem Greedy algorithms: activity selection problem fractional knapsack problem
Programming paradigms programming paradigm = general approach to algorithm design = general philosophy for solving a problem there are different ways of solving a problem several possible programming paradigms to solve the same problem a programming paradigm may be adapted to a certain problem and not to another
Brute Force Brute Force A straightforward approach, usually based directly on the problem s statement and definitions of the concepts involved Examples: 1. Computing an (a > 0, n a nonnegative integer) Computing n! 2. Multiplying two matrices 3. Searching for a key of a given value in a list 4.
Brute Brute- -Force Sorting Algorithm Force Sorting Algorithm Selection Sort Scan the array to find its smallest element and swap it with the first element. Then, starting with the second element, scan the elements to the right of it to find the smallest among them and swap it with the second elements. Generally, on pass i (0 i n-2), find the smallest element in A[i..n-1] and swap it with A[i]: A[0] . . . A[i-1] | A[i], . . . , A[min], . . ., A[n-1] in their final positions Example: 7 3 2 5
Analysis of Selection Sort Analysis of Selection Sort Time efficiency: (n^2) Space efficiency: (1), so in place Stability: yes
Brute Brute- -Force String Matching Force String Matching pattern: a string of m characters to search for text: a (longer) string of n characters to search in problem: find a substring in the text that matches the pattern Brute-force algorithm Step 1 Align pattern at beginning of text Step 2 Moving from left to right, compare each character of pattern to the corresponding character in text until all characters are found to match (successful search); or a mismatch is detected Step 3 While pattern is not found, and the text is not yet exhausted, realign pattern one position to the right and repeat Step 2
Examples of Brute Examples of Brute- -Force String Matching Force String Matching 1. Pattern: 001011 Text: 10010101101001100101111010 2. Pattern: happy Text: It is never too late to have a happy childhood.
Pseudocode and Efficiency Pseudocode and Efficiency Time efficiency: (mn) comparisons (in the worst case)
Brute Brute- -Force Polynomial Evaluation Force Polynomial Evaluation Problem: Find the value of polynomial p(x) = anxn+ an-1xn-1 + + a1x1 + a0 at a point x = x0 Brute-force algorithm p 0.0 fori ndownto 0 do power 1 forj 1 toido power power x p p + a[i] power return p //compute xi 0 i ni = (n^2) multiplications Efficiency:
Polynomial Evaluation: Improvement Polynomial Evaluation: Improvement We can do better by evaluating from right to left: Better brute-force algorithm p a[0] power 1 fori 1 tondo power power x p p + a[i] power returnp Efficiency: (n) multiplications
Brute Brute- -Force Strengths and Weaknesses Force Strengths and Weaknesses Strengths wide applicability simplicity yields reasonable algorithms for some important problems (e.g., matrix multiplication, sorting, searching, string matching) Weaknesses rarely yields efficient algorithms some brute-force algorithms are unacceptably slow not as constructive as some other design techniques
Exhaustive Search Exhaustive Search A brute force solution to a problem involving search for an element with a special property, usually among combinatorial objects such as permutations, combinations, or subsets of a set. Method: generate a list of all potential solutions to the problem in a systematic manner evaluate potential solutions one by one, disqualifying infeasible ones and, for an optimization problem, keeping track of the best one found so far when search ends, announce the solution(s) found
Example 1: Traveling Salesman Problem Example 1: Traveling Salesman Problem Given n cities with known distances between each pair, find the shortest tour that passes through all the cities exactly once before returning to the starting city Alternatively: Find shortest Hamiltonian circuit in a weighted connected graph Example: 5 3 2 a b 4 8 c d 7 How do we represent a solution (Hamiltonian circuit)?
TSP by Exhaustive Search Tour Cost a b c d a 2+3+7+5 = 17 a b d c a 2+4+7+8 = 21 a c b d a 8+3+4+5 = 20 a c d b a 8+7+4+2 = 21 a d b c a 5+4+3+8 = 20 a d c b a 5+7+3+2 = 17 Efficiency: ((n-1)!)
Example 2: Knapsack Problem Example 2: Knapsack Problem Given n items: weights: w1 w2 wn values: v1 v2 vn a knapsack of capacity W Find most valuable subset of the items that fit into the knapsack Example: Knapsack capacity W=16 item weight value 1 2 $20 2 5 $30 3 10 $50 4 5 $10
Knapsack Problem by Exhaustive Search Knapsack Problem by Exhaustive Search SubsetTotal weightTotal value {1} 2 $20 {2} 5 $30 {3} 10 $50 {4} 5 $10 {1,2} 7 $50 {1,3} 12 $70 {1,4} 7 $30 {2,3} 15 $80 {2,4} 10 $40 {3,4} 15 $60 {1,2,3} 17 not feasible {1,2,4} 12 $60 {1,3,4} 17 not feasible {2,3,4} 20 not feasible {1,2,3,4} 22 not feasible Efficiency: (2^n)
Example 3: The Assignment Problem There are n people who need to be assigned to n jobs, one person per job. The cost of assigning person i to job j is C[i,j]. Find an assignment that minimizes the total cost. Job 0 Job 1 Job 2 Job 3 Person 0 9 2 7 8 Person 1 6 4 3 7 Person 2 5 8 1 8 Person 3 7 6 9 4 Algorithmic Plan: Generate all legitimate assignments, compute their costs and select the cheapest one. How many assignments are there? Pose the problem as one about a cost matrix: n! cycle cover in a graph
Assignment Problem by Exhaustive Search Assignment Problem by Exhaustive Search 9 2 7 8 6 4 3 7 5 8 1 8 7 6 9 4 C = Assignment (col.#s) 1, 2, 3, 4 1, 2, 4, 3 1, 3, 2, 4 1, 3, 4, 2 1, 4, 2, 3 1, 4, 3, 2 (For this particular instance, the optimal assignment can be found by exploiting the specific features of the number given. It is: ) Total Cost 9+4+1+4=18 9+4+8+9=30 9+3+8+4=24 9+3+8+6=26 9+7+8+9=33 9+7+1+6=23 etc. 2,1,3,4
Final Comments on Exhaustive Search Final Comments on Exhaustive Search Exhaustive-search algorithms run in a realistic amount of time only on very small instances In some cases, there are much better alternatives! Euler circuits shortest paths minimum spanning tree assignment problem In many cases, exhaustive search or its variation is the only known way to get exact solution
Divide Divide- -and and- -Conquer Conquer The most-well known algorithm design strategy: 1. Divide instance of problem into two or more smaller instances 2. Solve smaller instances recursively 3. Obtain solution to original (larger) instance by combining these solutions
Divide-and-Conquer Technique (cont.) a problem of size n (instance) subproblem 1 of size n/2 subproblem 2 of size n/2 a solution to subproblem 1 a solution to subproblem 2 It general leads to a recursive algorithm! a solution to the original problem
Divide Divide- -and and- -Conquer Examples Conquer Examples Sorting: mergesort and quicksort Binary tree traversals Binary search (?) Multiplication of large integers Matrix multiplication: Strassen s algorithm Closest-pair and convex-hull algorithms
General Divide-and-Conquer Recurrence T(n) = aT(n/b) + f (n)where f(n) (nd), d 0 Master Theorem: If a < bd, T(n) (nd) If a = bd, T(n) (nd log n) If a > bd, T(n) (nlog b a ) Note: The same results hold with O instead of . (n^2) (n^2log n) Examples: T(n) = 4T(n/2) + n T(n) = 4T(n/2) + n2 T(n) = 4T(n/2) + n3 T(n) ? T(n) ? T(n) ? (n^3)
Mergesort Mergesort Split array A[0..n-1] into about equal halves and make copies of each half in arrays B and C Sort arrays B and C recursively Merge sorted arrays B and C into array A as follows: Repeat the following until no elements remain in one of the arrays: compare the first elements in the remaining unprocessed portions of the arrays copy the smaller of the two into A, while incrementing the index indicating the unprocessed portion of that array Once all elements in one of the arrays are processed, copy the remaining unprocessed elements from the other array into A.
Pseudocode of Merge Time complexity: (p+q)= (n) comparisons
Mergesort Example 8 3 2 9 7 1 5 4 8 3 2 9 7 1 5 4 8 3 2 9 7 1 5 4 8 3 2 9 7 1 5 4 The non-recursive version of Mergesort starts from merging single elements into sorted pairs. 3 8 2 9 1 7 4 5 2 3 8 9 1 4 5 7 1 2 3 4 5 7 8 9
Analysis of Mergesort All cases have same efficiency: (n log n) T(n) = 2T(n/2) + (n), T(1) = 0 Number of comparisons in the worst case is close to theoretical minimum for comparison-based sorting: log2n! n log2 n - 1.44n Space requirement: (n) (not in-place) Can be implemented without recursion (bottom-up)
