05.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 5: Brute Force Methods
(with thanks to Harald Søndergaard)
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
• By “completing” a quiz, we mean getting all
answers right (100%) in one sitting
• 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
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force Algorithms
• Straightforward problem solving approach, usually
based directly on the problem’s statement.
• Exhaustive search for solutions is a prime example.
• Selection sort
• String matching
• Closest pair
• Exhaustive search for combinatorial solutions
• Graph traversal
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
4
// swap A[i] and A[min]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
4
// swap A[i] and A[min]
Time Complexity:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
4
// swap A[i] and A[min]
Time Complexity: Θ(n2)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
4
// swap A[i] and A[min]
Time Complexity: Θ(n2)
We will soon meet better sorting algorithms
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
Properties of Selection Sort
• While running time is quadratic, selection sort
makes only about n exchanges.
• So: selection sort is a good algorithm for sorting
small collections of large records.
• In-place?
• Stable?
• Input-insensitive?
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
• While running time is quadratic, selection sort
makes only about n exchanges.
• So: selection sort is a good algorithm for sorting
small collections of large records.
• In-place?
• Stable?
• Input-insensitive?
6
yes
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
• While running time is quadratic, selection sort
makes only about n exchanges.
• So: selection sort is a good algorithm for sorting
small collections of large records.
• In-place?
• Stable?
• Input-insensitive?
6
yes
?
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
• While running time is quadratic, selection sort
makes only about n exchanges.
• So: selection sort is a good algorithm for sorting
small collections of large records.
• In-place?
• Stable?
• Input-insensitive?
6
yes
yes
?
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
7
key: 4
val: ab
0 1 2 3
key: 3
val: bc
key: 4
val: de
key: 3
val: fg
A[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
8
key: 4
val: ab
0 1 2 3
key: 3
val: bc
key: 4
val: de
key: 3
val: fg
A[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
9
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg
A[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
10
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg
A[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
11
key: 3
val: bc
0 1 2 3
key: 4
val: ab
key: 4
val: de
key: 3
val: fg
A[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
12
key: 3
val: bc
0 1 2 3
key: 3
val: fg
key: 4
val: de
key: 4
val: ab
A[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Selection Sort Stability
12
key: 3
val: bc
0 1 2 3
key: 3
val: fg
key: 4
val: de
key: 4
val: ab
A[i] the relative order
of the two “4” records
has changed!
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Selection Sort
• While running time is quadratic, selection sort
makes only about n exchanges.
• So: selection sort is a good algorithm for sorting
small collections of large records.
• In-place?
• Stable?
• Input-insensitive?
13
yes
yes
no
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
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
15
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
m
n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
15
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
m
n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
15
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
t[i+j]
p[j]
m
n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
16
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
t[i+j]
p[j]
m
n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
17
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
t[i+j]
p[j]
n
m
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
18
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
n
m
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
18
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
n
m
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
19
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
n
m
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
19
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
t[i]
n
m
t[i+j]
p[j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
20
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
n
m
t[i]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force String Matching
20
N O B O D Y
0 1 2 3 4 5 6
K N O W S
7 8 9 10 11
t:
p: N O T
0 1 2
n
m
t[i]
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
21
Basic operation: comparison p[j] = t[i+j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Brute Force
String Matching
21
Basic operation: comparison p[j] = t[i+j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Brute Force
String Matching
21
Basic operation: comparison p[j] = t[i+j]
For each n – m + 1 positions in t
we make up to m comparisons
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Brute Force
String Matching
21
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.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Brute Force
String Matching
21
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
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Brute Force
String Matching
21
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.
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).
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem (2D)
23
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Closest Pair Problem (2D)
23
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Brute Force Closest Pair
24
Try all combinations (xi,yi) and (xj,yj) with i < j: Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 25 0 1 2 3 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 25 0 1 2 3 4 i=0 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 25 0 1 2 3 4 i=0 min=∞ Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 25 0 1 2 3 4 i=0 min=∞ 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 26 0 1 2 3 4 i=0 min=5 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 26 0 1 2 3 4 i=0 min=5 5 6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 26 0 1 2 3 4 i=0 min=5 5 6 5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 26 0 1 2 3 4 i=0 min=5 5 6 5 8 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 27 0 1 2 3 4 i=1 min=5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 27 0 1 2 3 4 i=1 min=5 10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 27 0 1 2 3 4 i=1 min=5 10 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 28 0 1 2 3 4 i=1 min=4 10 4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Closest Pair Problem (2D) 28 0 1 2 3 4 i=1 min=4 10 4 and so on until i=3 and j=4 (which will find the minimum here) 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 • 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 algorithm 29 Θ(n log n) 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 • 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 algorithm 29 Θ(n2) Θ(n log n) 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 • 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 algorithm 29 Θ(n2) a < b ⟹ a < b Θ(n log n) 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 • 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 algorithm 29 Θ(n2) a < b ⟹ a < b Θ(n2) Θ(n log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Brute Force Summary • Simple, easy to program, widely applicable. • Standard approach for small tasks. • Reasonable algorithms for some problems. • But: Generally inefficient—does not scale well. • Use brute force for prototyping, or when it is known that input remains small. 30 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Exhaustive Search • Problem type: • Combinatorial decision or optimization problems • Search for an element with a particular property • Domain grows exponentially, for example all permutations • The brute-force approach—generate and test: • Systematically construct all possible solutions • Evaluate each, keeping track of the best so far • When all potential solutions have been examined, return the best found 31 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example 1: Travelling Salesperson (TSP) • Find the shortest tour (visiting each node exactly once before returning to the start) in a weighted, undirected graph. 32 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 a node (aka vertex) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 a node (aka vertex) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 a node (aka vertex) an edge Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 a node (aka vertex) an edge Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 a node (aka vertex) an edge an edge weight Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Side Note: Graph Concepts 33 a node (aka vertex) an edge an edge weight This graph is undirected since edges do not have directions associated with them. Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example 1: Travelling Salesperson (TSP) • Find the shortest tour (visiting each node exactly once before returning to the start) in a weighted, undirected graph. 34 Tours Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Example 2: Knapsack • Given n items with • Weights: w1, w2, …, wn • Values: v1, v2, …, vn • Knapsack of capacity W • find the most valuable selection of items whose combined weight does not exceed W 35 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Knapsack Example 36 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Knapsack: Example 37 NF means “not feasible”: exhausts the capacity of the knapsack. Later we’ll find a better algorithm based on dynamic programming Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Comments on Exhaustive Search • Exhaustive search algorithms have acceptable running times only for very small instances. • In many cases there are better alternatives, for example, Eulerian tours, shortest paths, minimum spanning trees, . . . • But for some problems, it is known that there is essentially no better alternative. • For a large class of important problems, it appears that there is no better alternative, but we have no proof either way. 38 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hamiltonian Tours • The Hamiltonian tour problem is this: • In a given undirected graph, is there a simple tour (a path that visits each node exactly once, except it returns to the starting node)? • Is there a Hamiltonian tour of this graph? 39 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Eulerian Tours • The Eulerian tour problem is this: • In a given undirected graph, is there a path which visits each edge exactly once? • Is there a Eulerian tour of this graph? 40 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Hard and Easy Problems • Recall that by a problem we usually mean a parametric problem: an infinite family of problem “instances”. • Sometimes our intuition about the difficulty of problems is not very reliable. The Hamiltonian Tour problem and the Eulerian Tour problem look very similar, but one is hard and the other is easy. We shall see more examples of this phenomenon later. • For many important optimization problems we do not know of solutions that are essentially better than exhaustive search (a whole raft of NP-complete problems, including TSP, knapsack). • In those cases we may look for approximation algorithms that are fast and still find solutions that are reasonably close to the optimal. • We plan to return to this idea in Week 12. 41 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License Next Up • Recursion as a problem solving technique 42