CS代考 COMP90038 – cscodehelp代写

COMP90038
Algorithms and Complexity
Lecture 5: Brute Force Methods (with thanks to Harald Søndergaard)

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
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]
Time Complexity: Θ(n2)
We will soon meet better sorting algorithms
3 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
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
•
•
•

5
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?
Stable?
Input-insensitive? yes
yes ?

Selection Sort Stability
key: 4 val: ab
key: 3 val: bc
key: 4 val: de
key: 3 val: fg
0123
A[i]
6 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]
7 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]
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: 3 val: fg
key: 4 val: de
key: 4 val: ab
0123
A[i]
the relative order of the two “4” records has changed!
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

12
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?
Stable?
Input-insensitive? yes
yes no

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
• • •
13
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
14 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
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 n
p:
012
p[j]
N
O
B
O
D
Y
K
N
O
W
S
N
O
T
m
16 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
17 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
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

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 n much larger than m: 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.
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

21
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)
22 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: 23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) i=0 min=∞ 2 0 5 3 1 4 24 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 25 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 26 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 27 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 28 approach leads to a Θ(n log n) algorithm Copyright University of Melbourne 2016, provided under Creative Commons Attribution License • • a