代写 algorithm graph COMP90038  Algorithms and Complexity

COMP90038  Algorithms and Complexity
Lecture 5: Brute Force Methods (with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray

2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Compulsory Quizzes
Remember: you need to complete 8 of the quizzes to pass the hurdle
•
•
You can have as many attempts as you need, but on at least one of those attempts you need to score 100%
The first compulsory quiz (for week 2) closes
tomorrow
•
By “completing” a quiz, we mean getting all
•
answers right (100%) in one sitting

3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force Algorithms
•
•
• • • •
Selection sort
String matching
Closest pair
Exhaustive search for combinatorial solutions Graph traversal
Straightforward problem solving approach, usually Exhaustive search for solutions is a prime example.
•
based directly on the problem’s statement.

Example: Selection Sort
// swap A[i] and A[min]
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
// swap A[i] and A[min]
Time Complexity:
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
// swap A[i] and A[min]
Time Complexity: Θ(n2)
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Example: Selection Sort
// swap A[i] and A[min]
Time Complexity: Θ(n2)
We will soon meet better sorting algorithms
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Properties of   Sorting Algorithms
A Sorting algorithm is:
in-place if it does not require additional memory except, perhaps, for a few units of memory
stable if it preserves the relative order of elements with identical keys
input-insensitive if its running time is fairly independent of input properties other than size
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
•
•
•

6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
•
• • •
small collections of large records.
In-place?
Stable? Input-insensitive?
While running time is quadratic, selection sort
So: selection sort is a good algorithm for sorting
•
makes only about n exchanges.

6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
•
• • •
small collections of large records.
In-place? yes Stable? Input-insensitive?
While running time is quadratic, selection sort
So: selection sort is a good algorithm for sorting
•
makes only about n exchanges.

6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
While running time is quadratic, selection sort
So: selection sort is a good algorithm for sorting
•
makes only about n exchanges.
•
• • •
small collections of large records.
In-place? yes
?
Stable? Input-insensitive?

6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
•
• • •
small collections of large records.
In-place? yes
While running time is quadratic, selection sort
So: selection sort is a good algorithm for sorting
•
makes only about n exchanges.
? Input-insensitive? yes
Stable?

Selection Sort Stability
key: 4 val: ab
key: 3 val: bc
key: 4 val: de
key: 3 val: fg
0123
A[i]
7 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Selection Sort Stability
key: 4 val: ab
key: 3 val: bc
key: 4 val: de
key: 3 val: fg
0123
A[i]
8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Selection Sort Stability
key: 3 val: bc
key: 4 val: ab
key: 4 val: de
key: 3 val: fg
0123
A[i]
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Selection Sort Stability
key: 3 val: bc
key: 4 val: ab
key: 4 val: de
key: 3 val: fg
0123
A[i]
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Selection Sort Stability
key: 3 val: bc
key: 4 val: ab
key: 4 val: de
key: 3 val: fg
0123
A[i]
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Selection Sort Stability
key: 3 val: bc
key: 3 val: fg
key: 4 val: de
key: 4 val: ab
0123
A[i]
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Selection Sort Stability
key: 3 val: bc
key: 3 val: fg
key: 4 val: de
key: 4 val: ab
0123
A[i]
the relative order of the two “4” records has changed!
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
•
• • •
small collections of large records.
In-place? yes
While running time is quadratic, selection sort
So: selection sort is a good algorithm for sorting
•
makes only about n exchanges.
no Input-insensitive? yes
Stable?

Brute Force String Matching
Pattern p: a string of m characters to search for
Text t: a long string of n characters to search in
We use i to run through the text and j to run through the pattern
• • •
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching
N
O
B
O
D
Y
K
N
O
W
S
t:
0 1 2 3 4 5 6 7 8 9 10 11 m
p:
012
N
O
T
n
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 m
p:
012
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
n
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching t[i+j]
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 m
p:
012
p[j]
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
n
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching t[i+j]
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 m
p:
012
p[j]
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
n
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching t[i+j]
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 n
p:
012
p[j]
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
m
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 n
p:
012
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
m
18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 n
p:
012
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
m
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching t[i+j]
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 n
p:
012
p[j]
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
m
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force String Matching
t[i]
t:
0 1 2 3 4 5 6 7 8 9 10 11 n
p:
012
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
m
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Analysing Brute Force  String Matching
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Analysing Brute Force  String Matching
Basic operation: comparison p[j] = t[i+j]
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Analysing Brute Force  String Matching
Basic operation: comparison p[j] = t[i+j]
For each n – m + 1 positions in t  we make up to m comparisons
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Analysing Brute Force  String Matching
Basic operation: comparison p[j] = t[i+j]
For each n – m + 1 positions in t  we make up to m comparisons
Assuming m much larger than n: O(mn) comparisons. But for random text over reasonably large alphabet 
(e.g. English), average running time is linear in n
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Analysing Brute Force  String Matching
Basic operation: comparison p[j] = t[i+j]
For each n – m + 1 positions in t  we make up to m comparisons
Assuming m much larger than n: O(mn) comparisons. But for random text over reasonably large alphabet 
(e.g. English), average running time is linear in n
There are better algorithms, for smaller alphabets such as binary strings or strings of DNA nucleobases. But for many purposes, the brute-force algorithm is acceptable.
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force Geometric  Algorithms: Closest Pair
Problem: Given n points is k-dimensional space, find a pair of points with minimal separating Euclidean distance.
The brute force approach considers each pair in turn (except that once it has found the distance from x to y, it does not need to consider the distance from y to x).
For simplicity, we look at the 2-dimensional case, the points being (x0, y0), (x1, y1), … , (xn−1, yn−1).
•
•
•

Closest Pair Problem (2D)
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Brute Force Closest Pair
Try all combinations (xi,yi) and (xj,yj) with i < j: 24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 2 0 3 1 4 25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 2 0 3 1 4 25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=∞ 2 0 3 1 4 25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=∞ 2 0 5 3 1 4 25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=5 2 0 5 3 1 4 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=5 2 6 0 5 3 1 4 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=5 2 6 0 5 3 1 5 4 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=5 2 6 0 5 5 8 3 1 4 26 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=1 min=5 2 0 3 1 4 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=1 min=5 2 0 10 3 1 4 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=1 min=5 2 0 10 3 1 4 4 27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=1 min=4 2 0 10 3 1 4 4 28 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=1 min=4 2 0 and so on until i=3 and j=4  (which will find the minimum here) 10 3 1 4 4 28 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License 29 Analysing Brute Force  Closest Pair Algorithm Not hard to see that the algorithm is Note, however, that we can speed up the algorithm considerably, by utilising the monotonicity of the square root function Does that contradict the claim? Later we will see a clever divide and conquer approach leads to a Θ(n log n) algorithm Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • • • • 29 Analysing Brute Force  Closest Pair Algorithm Not hard to see that the algorithm is Θ(n2) Note, however, that we can speed up the algorithm considerably, by utilising the monotonicity of the square root function Does that contradict the claim? Later we will see a clever divide and conquer approach leads to a Θ(n log n) algorithm Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • • • • Analysing Brute Force  Closest Pair Algorithm Not hard to see that the algorithm is Θ(n2) • Note, however, that we can speed up the algorithm • considerably, by utilising the monotonicity of the 29 approach leads to a Θ(n log n) algorithm Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • • a

Related Posts