COSC1285/2123: Algorithms & Analysis – Brute Force
COSC1285/2123: Algorithms & Analysis
Brute Force
Hoang MIT University
Email : sonhoang. .au
Lecture 4
(RMIT University) Brute Force Lecture 4 1 / 95
Outline
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 2 / 95
Overview
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 3 / 95
Overview
Levitin – The design and analysis of algorithms
This week we will be covering the material from Chapter 3.
Learning Outcomes:
• Understand the Brute Force algorithmic approach.
• Understand and apply:
• Sorting – selection and bubble sort.
• Exhaustive search – knapsack.
• Graph search – DFS, BFS.
• Examine a case study of using a brute force approach to solve a
problem.
(RMIT University) Brute Force Lecture 4 4 / 95
Brute Force
Brute force is a straightforward approach to solving a problem, usually
directly based on the problem statement and definitions of the
concepts involved, and can involve enumerating all solutions and
selecting the best one.
Examples:
1 Computing an (multiple ’a’ n times)
2 Searching for a key of a given value in an unsorted list.
(RMIT University) Brute Force Lecture 4 5 / 95
Overview
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 6 / 95
Sorting
Examples:
• Telephone book – Sorted by surname.
• Height in class – Tallest to shortest.
Why?
• Important to build efficient searching algorithms and data
structures, data compression.
• Heavily studied problem in computer science, with several widely
celebrated algorithms.
Sorting Problem
Given a sequence of n elements x1, x2, . . . , xn ∈ S, rearrange the
elements according to some ordering criteria.
(RMIT University) Brute Force Lecture 4 7 / 95
Sorting
Examples:
• Telephone book – Sorted by surname.
• Height in class – Tallest to shortest.
Why?
• Important to build efficient searching algorithms and data
structures, data compression.
• Heavily studied problem in computer science, with several widely
celebrated algorithms.
Sorting Problem
Given a sequence of n elements x1, x2, . . . , xn ∈ S, rearrange the
elements according to some ordering criteria.
(RMIT University) Brute Force Lecture 4 7 / 95
Sorting
Examples:
• Telephone book – Sorted by surname.
• Height in class – Tallest to shortest.
Why?
• Important to build efficient searching algorithms and data
structures, data compression.
• Heavily studied problem in computer science, with several widely
celebrated algorithms.
Sorting Problem
Given a sequence of n elements x1, x2, . . . , xn ∈ S, rearrange the
elements according to some ordering criteria.
(RMIT University) Brute Force Lecture 4 7 / 95
Brute Force Sorting: Selection Sort
Selection sort is a brute force solution to the sorting problem.
1 Scan all n elements of the array to find the smallest element, and
swap it with the first element.
2 Starting with the second element, scan the remaining n − 1
elements to find the smallest element and swap it with the
element in the second position.
3 Generally, on pass i(0 ≤ i ≤ n − 2), find the smallest element in
A[i . . . n − 1] and swap it with A[i].
(RMIT University) Brute Force Lecture 4 8 / 95
Brute Force Sorting: Selection Sort
Selection sort is a brute force solution to the sorting problem.
1 Scan all n elements of the array to find the smallest element, and
swap it with the first element.
2 Starting with the second element, scan the remaining n − 1
elements to find the smallest element and swap it with the
element in the second position.
3 Generally, on pass i(0 ≤ i ≤ n − 2), find the smallest element in
A[i . . . n − 1] and swap it with A[i].
(RMIT University) Brute Force Lecture 4 8 / 95
Selection Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
0COMPARES
(RMIT University) Brute Force Lecture 4 9 / 95
Selection Sort Example
15 21 1 25 12 6 8 3 5 19 10 18
0COMPARES +11
(RMIT University) Brute Force Lecture 4 10 / 95
Selection Sort Example
1810195386122515211
COMPARES 11 +10
(RMIT University) Brute Force Lecture 4 11 / 95
Selection Sort Example
1810195861225151 3 21
COMPARES 21 +9
(RMIT University) Brute Force Lecture 4 12 / 95
Selection Sort Example
1810198612251 3 21 155
COMPARES +830
(RMIT University) Brute Force Lecture 4 13 / 95
Selection Sort Example
1810198121 3 21 155 6 25
COMPARES 38 +7
(RMIT University) Brute Force Lecture 4 14 / 95
Selection Sort Example
1810191 3 21 155 6 25 128
COMPARES 45 +6
(RMIT University) Brute Force Lecture 4 15 / 95
Selection Sort Example
18191 3 21 155 6 128 10 25
COMPARES 51 +5
(RMIT University) Brute Force Lecture 4 16 / 95
Selection Sort Example
18191 3 21 155 6 8 10 2512
COMPARES 56 +4
(RMIT University) Brute Force Lecture 4 17 / 95
Selection Sort Example
18191 3 5 6 8 10 2512 15 21
COMPARES +360
(RMIT University) Brute Force Lecture 4 18 / 95
Selection Sort Example
191 3 5 6 8 10 2512 15 2118
COMPARES 63 +2
(RMIT University) Brute Force Lecture 4 19 / 95
Selection Sort Example
1 3 5 6 8 10 2512 15 2118 19
COMPARES 65 +1
(RMIT University) Brute Force Lecture 4 20 / 95
Selection Sort Example
1 3 5 6 8 10 12 15 18 19 21 25
COMPARES 66
(RMIT University) Brute Force Lecture 4 21 / 95
Selection Sort
ALGORITHM SelectionSort (A[0 . . . n − 1])
/* Order an array using a brute-force selection sort. */
/* INPUT : An array A[0 . . . n − 1] of orderable elements. */
/* OUTPUT : An array A[0 . . . n − 1] sorted in ascending order. */
1: for i = 0 to n − 2 do
2: min = i
3: for j = i + 1 to n − 1 do
4: if A[j] < A[min] then
5: min = j
6: end if
7: end for
8: swap A[i] and A[min]
9: end for
(RMIT University) Brute Force Lecture 4 22 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Selection Sort - Complexity
Selection Sort Complexity?
C(n) =
n−2∑
i=0
n−1∑
j=i+1
1 =
n−2∑
i=0
(n − 1− i) =
(n − 1)n
2
∈ O(n2)
• Needs around n2/2 comparisons and at most n − 1 exchanges.
• The running time is insensitive to the input, so the best, average,
and worst case are essentially the same (Why?).
Why use it?
• Selection sort only makes O(n) writes but O(n2) reads.
• When writes (to array) are much more expensive than reads,
selection sort may have an advantage, e.g., flash memory.
• Also, for small arrays, selection sort is relatively efficient and
simple to implement.
(RMIT University) Brute Force Lecture 4 23 / 95
Stable Sorting
• Definition: A sorting method is said to be stable if it preserves the
relative order of duplicate keys in the file.
Before Sorting After Sorting
1 Adams 1 Adams
2 Black 1 Smith
4 Brown 2 Black
2 Jackson 2 Jackson
4 Jones 2 Washington
1 Smith 3 White
4 Thompson 3 Wilson
2 Washington 4 Brown
3 White 4 Jones
3 Wilson 4 Thompson
Not all sorting methods are stable.
(RMIT University) Brute Force Lecture 4 24 / 95
Is Selection Sort Stable?
Question: Is selection sort stable?
Consider the following examples and apply selection sort on them:
5,5,3,2
(RMIT University) Brute Force Lecture 4 25 / 95
Brute Force Sorting: Bubble Sort
A bubble sort iteratively compares adjacent items in a list and
exchanges them if they are out of order.
Motivation:
• One of the classic (and elementary) sorting algorithms, originally
designed and efficient for tape disks, but with random access
memory, it doesn’t have much use these days.
• But insightful to study it and to understand why other sorting
algorithms are superior in one or more aspects.
• It is simple to code.
(RMIT University) Brute Force Lecture 4 26 / 95
Brute Force Sorting: Bubble Sort
A bubble sort iteratively compares adjacent items in a list and
exchanges them if they are out of order.
Motivation:
• One of the classic (and elementary) sorting algorithms, originally
designed and efficient for tape disks, but with random access
memory, it doesn’t have much use these days.
• But insightful to study it and to understand why other sorting
algorithms are superior in one or more aspects.
• It is simple to code.
(RMIT University) Brute Force Lecture 4 26 / 95
Bubble Sort
1 First iteration, compare each adjacent pair of elements and swap
them if they are out of order. Eventually largest element gets
propagated to the end.
2 Second iteration, repeat the process, but only from first to 2nd last
element (last element is in its correct position). Eventually second
largest element is at the 2nd last element.
3 Repeat until all elements are sorted.
(RMIT University) Brute Force Lecture 4 27 / 95
Bubble Sort Example – Round 1
15 21 1 25 12 6 8 3 5 19 10 18
0COMPARES
(RMIT University) Brute Force Lecture 4 28 / 95
Bubble Sort Example – Round 1
15 21 181019538612251
COMPARES 1
(RMIT University) Brute Force Lecture 4 29 / 95
Bubble Sort Example – Round 1
15 121 18101953861225
COMPARES 2
(RMIT University) Brute Force Lecture 4 30 / 95
Bubble Sort Example – Round 1
15 1810195386121 2521
COMPARES 3
(RMIT University) Brute Force Lecture 4 31 / 95
Bubble Sort Example – Round 1
15 18101953861 2521 12
COMPARES 4
(RMIT University) Brute Force Lecture 4 32 / 95
Bubble Sort Example – Round 1
15 1810195381 21 12 25 6
COMPARES 5
(RMIT University) Brute Force Lecture 4 33 / 95
Bubble Sort Example – Round 1
15 181019531 21 12 6 25 8
COMPARES 6
(RMIT University) Brute Force Lecture 4 34 / 95
Bubble Sort Example – Round 1
15 18101951 21 12 6 8 25 3
COMPARES 7
(RMIT University) Brute Force Lecture 4 35 / 95
Bubble Sort Example – Round 1
15 1810191 21 12 6 8 3 25 5
COMPARES 8
(RMIT University) Brute Force Lecture 4 36 / 95
Bubble Sort Example – Round 1
15 18101 21 12 6 8 3 5 25 19
COMPARES 9
(RMIT University) Brute Force Lecture 4 37 / 95
Bubble Sort Example – Round 1
15 181 21 12 6 8 3 5 19 25 10
COMPARES 10
(RMIT University) Brute Force Lecture 4 38 / 95
Bubble Sort Example – Round 1
15 1 21 12 6 8 3 5 19 10 25 18
COMPARES 11
(RMIT University) Brute Force Lecture 4 39 / 95
Bubble Sort Example – Round 1
15 1 21 12 6 8 3 5 19 10 18
COMPARES 11
25
(RMIT University) Brute Force Lecture 4 40 / 95
Bubble Sort Example – Round 2
151 12 6 8 3 5 19 10 18
COMPARES
2521
21
(RMIT University) Brute Force Lecture 4 41 / 95
Bubble Sort Example – Round 3
1 12 6 8 3 5 15 10 18
COMPARES
252119
30
(RMIT University) Brute Force Lecture 4 42 / 95
Bubble Sort Example – Round 4
1 6 8 3 5 12 10 15
COMPARES
25211918
38
(RMIT University) Brute Force Lecture 4 43 / 95
Bubble Sort Example – Round 5
1 6 3 5 8 10 12
COMPARES
2521191815
45
(RMIT University) Brute Force Lecture 4 44 / 95
Bubble Sort Example – Round 6
1 8 103 5 6
COMPARES 51
252119181512
(RMIT University) Brute Force Lecture 4 45 / 95
Bubble Sort Example – Sorted?
1 8 103 5 6
COMPARES 51
252119181512
(RMIT University) Brute Force Lecture 4 46 / 95
Bubble Sort
ALGORITHM BubbleSort (A[0 . . . n − 1])
/* Order an array using a bubble sort. */
/* INPUT : An array A[0 . . . n − 1] of orderable elements. */
/* OUTPUT : An array A[0 . . . n − 1] sorted in ascending order. */
1: for i = 0 to n − 2 do
2: for j = 0 to n − 2− i do
3: if A[j + 1] < A[j] then
4: swap A[j] and A[j + 1]
5: end if
6: end for
7: end for
(RMIT University) Brute Force Lecture 4 47 / 95
Bubble Sort - Complexity
Bubble Sort Complexity?
C(n) =
n−2∑
i=0
n−2−i∑
j=0
1 =
n−2∑
i=0
[(n − 2− i)− 0 + 1] =
n−2∑
i=0
(n − 1− i)
=
(n − 1)n
2
∈ O(n2)
• Best case: if original file is already sorted, about n2/2
comparisons & 0 exchanges – O(n2).
• Worst case: if original file is sorted in reverse order, about n2/2
comparisons & n2/2 exchanges – O(n2).
• Average case: if original file is in random order, about n2/2
comparisons & less than n2/2 exchanges – O(n2).
Is bubble sort stable?
(RMIT University) Brute Force Lecture 4 48 / 95
Bubble Sort - Complexity
Bubble Sort Complexity?
C(n) =
n−2∑
i=0
n−2−i∑
j=0
1
=
n−2∑
i=0
[(n − 2− i)− 0 + 1] =
n−2∑
i=0
(n − 1− i)
=
(n − 1)n
2
∈ O(n2)
• Best case: if original file is already sorted, about n2/2
comparisons & 0 exchanges – O(n2).
• Worst case: if original file is sorted in reverse order, about n2/2
comparisons & n2/2 exchanges – O(n2).
• Average case: if original file is in random order, about n2/2
comparisons & less than n2/2 exchanges – O(n2).
Is bubble sort stable?
(RMIT University) Brute Force Lecture 4 48 / 95
Bubble Sort - Complexity
Bubble Sort Complexity?
C(n) =
n−2∑
i=0
n−2−i∑
j=0
1 =
n−2∑
i=0
[(n − 2− i)− 0 + 1] =
n−2∑
i=0
(n − 1− i)
=
(n − 1)n
2
∈ O(n2)
• Best case: if original file is already sorted, about n2/2
comparisons & 0 exchanges – O(n2).
• Worst case: if original file is sorted in reverse order, about n2/2
comparisons & n2/2 exchanges – O(n2).
• Average case: if original file is in random order, about n2/2
comparisons & less than n2/2 exchanges – O(n2).
Is bubble sort stable?
(RMIT University) Brute Force Lecture 4 48 / 95
Bubble Sort - Complexity
Bubble Sort Complexity?
C(n) =
n−2∑
i=0
n−2−i∑
j=0
1 =
n−2∑
i=0
[(n − 2− i)− 0 + 1] =
n−2∑
i=0
(n − 1− i)
=
(n − 1)n
2
∈ O(n2)
• Best case: if original file is already sorted, about n2/2
comparisons & 0 exchanges – O(n2).
• Worst case: if original file is sorted in reverse order, about n2/2
comparisons & n2/2 exchanges – O(n2).
• Average case: if original file is in random order, about n2/2
comparisons & less than n2/2 exchanges – O(n2).
Is bubble sort stable?
(RMIT University) Brute Force Lecture 4 48 / 95
Bubble Sort - Complexity
Bubble Sort Complexity?
C(n) =
n−2∑
i=0
n−2−i∑
j=0
1 =
n−2∑
i=0
[(n − 2− i)− 0 + 1] =
n−2∑
i=0
(n − 1− i)
=
(n − 1)n
2
∈ O(n2)
• Best case: if original file is already sorted, about n2/2
comparisons & 0 exchanges – O(n2).
• Worst case: if original file is sorted in reverse order, about n2/2
comparisons & n2/2 exchanges – O(n2).
• Average case: if original file is in random order, about n2/2
comparisons & less than n2/2 exchanges – O(n2).
Is bubble sort stable?
(RMIT University) Brute Force Lecture 4 48 / 95
Bubble Sort - Complexity
Bubble Sort Complexity?
C(n) =
n−2∑
i=0
n−2−i∑
j=0
1 =
n−2∑
i=0
[(n − 2− i)− 0 + 1] =
n−2∑
i=0
(n − 1− i)
=
(n − 1)n
2
∈ O(n2)
• Best case: if original file is already sorted, about n2/2
comparisons & 0 exchanges – O(n2).
• Worst case: if original file is sorted in reverse order, about n2/2
comparisons & n2/2 exchanges – O(n2).
• Average case: if original file is in random order, about n2/2
comparisons & less than n2/2 exchanges – O(n2).
Is bubble sort stable?
(RMIT University) Brute Force Lecture 4 48 / 95
Early-Termination Bubble Sort
• This modification attempts to reduce redundant iterations, by
checking if any exchanges takes place in each pass. If there were
no exchanges in the current iteration, the sorting is stopped after
the current iteration.
• Why does this work?
• Best case - when the original file is already sorted, only one pass
is needed, n − 1 comparisons, 0 exchanges – O(n).
• Worst case - No improvement over the original implementation –
O(n2).
• Average case - Depending on the data set, few iterations can be
eliminated at the end of the sort. Therefore, the number of passes
is less than n − 1, and hence cost is lower than the original
implementation. The complexity is still likely to be O(n2).
(RMIT University) Brute Force Lecture 4 49 / 95
Early-Termination Bubble Sort
• This modification attempts to reduce redundant iterations, by
checking if any exchanges takes place in each pass. If there were
no exchanges in the current iteration, the sorting is stopped after
the current iteration.
• Why does this work?
• Best case - when the original file is already sorted, only one pass
is needed, n − 1 comparisons, 0 exchanges – O(n).
• Worst case - No improvement over the original implementation –
O(n2).
• Average case - Depending on the data set, few iterations can be
eliminated at the end of the sort. Therefore, the number of passes
is less than n − 1, and hence cost is lower than the original
implementation. The complexity is still likely to be O(n2).
(RMIT University) Brute Force Lecture 4 49 / 95
Early-Termination Bubble Sort
• This modification attempts to reduce redundant iterations, by
checking if any exchanges takes place in each pass. If there were
no exchanges in the current iteration, the sorting is stopped after
the current iteration.
• Why does this work?
• Best case - when the original file is already sorted, only one pass
is needed, n − 1 comparisons, 0 exchanges – O(n).
• Worst case - No improvement over the original implementation –
O(n2).
• Average case - Depending on the data set, few iterations can be
eliminated at the end of the sort. Therefore, the number of passes
is less than n − 1, and hence cost is lower than the original
implementation. The complexity is still likely to be O(n2).
(RMIT University) Brute Force Lecture 4 49 / 95
Overview
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 50 / 95
Exhaustive Search
A brute force approach involving enumerating/generating all possible
solutions, then selecting the “best” one.
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 keeping track of the best one found so far.
• When all items have been evaluated, announce the best
solution(s) found.
Typically applied to combinatorial problems, and insightful to study
brute force solutions to them, as some problems can only be solved
optimally by exhaustive search.
(RMIT University) Brute Force Lecture 4 51 / 95
Exhaustive Search
A brute force approach involving enumerating/generating all possible
solutions, then selecting the “best” one.
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 keeping track of the best one found so far.
• When all items have been evaluated, announce the best
solution(s) found.
Typically applied to combinatorial problems, and insightful to study
brute force solutions to them, as some problems can only be solved
optimally by exhaustive search.
(RMIT University) Brute Force Lecture 4 51 / 95
Exhaustive Search
A brute force approach involving enumerating/generating all possible
solutions, then selecting the “best” one.
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 keeping track of the best one found so far.
• When all items have been evaluated, announce the best
solution(s) found.
Typically applied to combinatorial problems, and insightful to study
brute force solutions to them, as some problems can only be solved
optimally by exhaustive search.
(RMIT University) Brute Force Lecture 4 51 / 95
Knapsack Problem
Knapsack Problem
Given n items of known weights w1, . . . ,wn and the values v1, . . . , vn
and a knapsack of capacity W , find the most valuable subset of the
items that fit into the knapsack.a
a
http://en.wikipedia.org/wiki/File:Knapsack.svg
(RMIT University) Brute Force Lecture 4 52 / 95
http://en.wikipedia.org/wiki/File:Knapsack.svg
Applications of Knapsack Problem
(RMIT University) Brute Force Lecture 4 53 / 95
Brute Force Knapsack Algorithm
Algorithm:
1 Consider all subsets of the set of n items.
2 Compute the total weight of each subset in order to identify
feasible subsets (the ones with the total not exceeding the
knapsack’s capacity).
3 Find the subset of the largest value among them.
Complexity: Since the number of subsets of an n-element set is 2n,
an exhaustive search produces an O(2n) algorithm.
(RMIT University) Brute Force Lecture 4 54 / 95
Brute Force Knapsack Algorithm
Algorithm:
1 Consider all subsets of the set of n items.
2 Compute the total weight of each subset in order to identify
feasible subsets (the ones with the total not exceeding the
knapsack’s capacity).
3 Find the subset of the largest value among them.
Complexity: Since the number of subsets of an n-element set is 2n,
an exhaustive search produces an O(2n) algorithm.
(RMIT University) Brute Force Lecture 4 54 / 95
Brute Force Knapsack Algorithm
Algorithm:
1 Consider all subsets of the set of n items.
2 Compute the total weight of each subset in order to identify
feasible subsets (the ones with the total not exceeding the
knapsack’s capacity).
3 Find the subset of the largest value among them.
Complexity: Since the number of subsets of an n-element set is 2n,
an exhaustive search produces an O(2n) algorithm.
(RMIT University) Brute Force Lecture 4 54 / 95
Brute Force Knapsack Algorithm
Algorithm:
1 Consider all subsets of the set of n items.
2 Compute the total weight of each subset in order to identify
feasible subsets (the ones with the total not exceeding the
knapsack’s capacity).
3 Find the subset of the largest value among them.
Complexity: Since the number of subsets of an n-element set is 2n,
an exhaustive search produces an O(2n) algorithm.
(RMIT University) Brute Force Lecture 4 54 / 95
Knapsack Problem
w3 = 4
3 = $40v
Item 3
v4 = $25
w4 = 5
Item 4
w2 = 3
v2 = $12
Item 2
v1 = $42
w1 = 7
Item 1Knapsack
10
(RMIT University) Brute Force Lecture 4 55 / 95
Knapsack Problem
Subset Total Weight Total Value
0 $0
{1} 7 $42
{2} 3 $12
{3} 4 $40
{4} 5 $25
{1, 2} 10 $36
{1, 3} 11 Not Possible
{1, 4} 12 Not Possible
{2, 3} 7 $52
{2, 4} 8 $37
{3, 4} 9 $65
{1, 2, 3} 14 Not Possible
{1, 2, 4} 15 Not Possible
{1, 3, 4} 16 Not Possible
{2, 3, 4} 12 Not Possible
{1, 2, 3, 4} 19 Not Possible
(RMIT University) Brute Force Lecture 4 56 / 95
Overview
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 57 / 95
Searching in Graphs
(a) How to find the shortest
path in a road network?
(b) How to find a path
through a maze?
(c) How to determine if a
power network is
connected?
(RMIT University) Brute Force Lecture 4 58 / 95
Graph example
B
A
E
C
F
D
(RMIT University) Brute Force Lecture 4 59 / 95
Depth-First Search – Overview
Depth-First Search (DFS) - Traversal:
1 Choose an arbitrary vertex and mark it visited.
2 From the current vertex, proceed to an unvisited, adjacent vertex
and mark it visited.
3 Repeat 2nd step until a vertex is reached which has no adjacent,
unvisited vertices (dead-end).
4 At each dead-end, backtrack to the last visited vertex and proceed
down to the next unvisited, adjacent vertex.
5 The algorithm halts there are no unvisted vertices.
(RMIT University) Brute Force Lecture 4 60 / 95
Depth-First Search – Overview
Depth-First Search (DFS) - Traversal:
1 Choose an arbitrary vertex and mark it visited.
2 From the current vertex, proceed to an unvisited, adjacent vertex
and mark it visited.
3 Repeat 2nd step until a vertex is reached which has no adjacent,
unvisited vertices (dead-end).
4 At each dead-end, backtrack to the last visited vertex and proceed
down to the next unvisited, adjacent vertex.
5 The algorithm halts there are no unvisted vertices.
(RMIT University) Brute Force Lecture 4 60 / 95
Depth-First Search – Overview
Depth-First Search (DFS) - Traversal:
1 Choose an arbitrary vertex and mark it visited.
2 From the current vertex, proceed to an unvisited, adjacent vertex
and mark it visited.
3 Repeat 2nd step until a vertex is reached which has no adjacent,
unvisited vertices (dead-end).
4 At each dead-end, backtrack to the last visited vertex and proceed
down to the next unvisited, adjacent vertex.
5 The algorithm halts there are no unvisted vertices.
(RMIT University) Brute Force Lecture 4 60 / 95
Depth-First Search – Overview
Depth-First Search (DFS) - Traversal:
1 Choose an arbitrary vertex and mark it visited.
2 From the current vertex, proceed to an unvisited, adjacent vertex
and mark it visited.
3 Repeat 2nd step until a vertex is reached which has no adjacent,
unvisited vertices (dead-end).
4 At each dead-end, backtrack to the last visited vertex and proceed
down to the next unvisited, adjacent vertex.
5 The algorithm halts there are no unvisted vertices.
(RMIT University) Brute Force Lecture 4 60 / 95
Depth-First Search – Overview
Depth-First Search (DFS) - Traversal:
1 Choose an arbitrary vertex and mark it visited.
2 From the current vertex, proceed to an unvisited, adjacent vertex
and mark it visited.
3 Repeat 2nd step until a vertex is reached which has no adjacent,
unvisited vertices (dead-end).
4 At each dead-end, backtrack to the last visited vertex and proceed
down to the next unvisited, adjacent vertex.
5 The algorithm halts there are no unvisted vertices.
(RMIT University) Brute Force Lecture 4 60 / 95
Depth-First Search – Overview
Depth-First Search (DFS) - Traversal:
1 Choose an arbitrary vertex and mark it visited.
2 From the current vertex, proceed to an unvisited, adjacent vertex
and mark it visited.
3 Repeat 2nd step until a vertex is reached which has no adjacent,
unvisited vertices (dead-end).
4 At each dead-end, backtrack to the last visited vertex and proceed
down to the next unvisited, adjacent vertex.
5 The algorithm halts there are no unvisted vertices.
(RMIT University) Brute Force Lecture 4 60 / 95
Depth-First Search – Example
B
A
E
C
F
D
(RMIT University) Brute Force Lecture 4 61 / 95
Depth-First Search – Example
A
B
E
C
F
D
(RMIT University) Brute Force Lecture 4 62 / 95
Depth-First Search – Example
B
A
E
C
F
D
(RMIT University) Brute Force Lecture 4 63 / 95
Depth-First Search – Example
B
A
C
E F
D
(RMIT University) Brute Force Lecture 4 64 / 95
Depth-First Search – Example
B
A
C
E F
D
(RMIT University) Brute Force Lecture 4 65 / 95
Depth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 66 / 95
Depth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 67 / 95
Depth-First Search – Example
B
A
C D
FE
(RMIT University) Brute Force Lecture 4 68 / 95
Depth-First Search – Example
B
A
C D
FE
Backtrack.
(RMIT University) Brute Force Lecture 4 69 / 95
Depth-First Search – Example
B
A
C D
FE
(RMIT University) Brute Force Lecture 4 70 / 95
Depth-First Search – Example
B
A
C D
FE
Backtrack
(RMIT University) Brute Force Lecture 4 71 / 95
Depth-First Search – Example
B
A
C D
FE
(RMIT University) Brute Force Lecture 4 72 / 95
Depth-First Search – Pseudocode
ALGORITHM DFS (G)
/* Implement a Depth First Traversal of a graph. */
/* INPUT : Graph G = 〈V ,E〉 */
/* OUTPUT : Graph G with its vertices marked with consecutive */
/* integers in initial encounter order. */
1: count = 0 . number of nodes visited
2: for v in V do . mark all nodes unvisited
3: Marked[v ] = 0
4: end for
5: for v in V do . visit each unmarked node
6: if not Marked[v ] then
7: DFSR (v)
8: end if
9: end for
(RMIT University) Brute Force Lecture 4 73 / 95
Depth-First Search – Pseudocode
ALGORITHM DFSR (v)
/* Recursively visit all connected vertices. */
/* INPUT : A starting vertex v */
/* OUTPUT : Graph G with its vertices marked with consecutive */
/* integers in initial encounter order. */
1: count = count + 1 . increment the node visited counter
2: Marked[v ] = count . mark node as visited
3: for v ′ ∈ V adjacent to v do . recursively visit all
4: if not Marked[v ′] then . unmarked adjacent nodes
5: DFSR (v ′)
6: end if
7: end for
(RMIT University) Brute Force Lecture 4 74 / 95
Depth-First Search – Summary
• A DFS search can be implemented with graphs represented as:
• Adjacency matrices: O(|V |2)
• It is a graph traversal, so we need to iterate over all vertices (|V | of
these). For each vertex, we need to check the neighbours of it. For
the matrix represenation, the only way we can guranatee to find all
neighbours of vertex i is to do a linear scan across its row in the
matrix, which has |V | elements. So |V | * |V | gives O(|V |2)
complexity. The traversal also needs to setup visited status, which
requires O|V | complexity, but the quadratic term dominates.
• Adjacency lists: O(|V |+ |E |)
• Similarly to the matrix representation, we need to iterate over all the
vertices (|V | of these). For each vertex, we need to check the
neighbours of it. Different for the adjacency list represenation, we
only need to scan through the elements in the associated linked list.
The total number of elements across all the linked list (and total
number of neighbours to consider) is O(|E |). The traversal also
needs to setup visited status, which requires O|V | complexity. Hence
the total is O(|V |+ |E |).
(RMIT University) Brute Force Lecture 4 75 / 95
Breadth-First Search – Overview
Breadth-First Search (BFS) - Traversal:
1 Choose an arbitrary vertex v and mark it visited.
2 Visit and mark (visited) each of the adjacent (neighbour) vertices
of v in turn.
3 Once all neighbours of v have been visited, select the first
neighbour that was visited, and visit all its (unmarked) neighbours.
4 Then select the second visited neighbour of v , and visit all its
unmarked neighbours.
5 The algorithm halts when we visited all vertices.
(RMIT University) Brute Force Lecture 4 76 / 95
Breadth-First Search – Example
B
A
E
C
F
D
(RMIT University) Brute Force Lecture 4 77 / 95
Breadth-First Search – Example
A
B
E
C
F
D
(RMIT University) Brute Force Lecture 4 78 / 95
Breadth-First Search – Example
A
B
E
C
F
D
(RMIT University) Brute Force Lecture 4 79 / 95
Breadth-First Search – Example
B
A
C
E F
D
(RMIT University) Brute Force Lecture 4 80 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 81 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 82 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 83 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 84 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 85 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 86 / 95
Breadth-First Search – Example
B
A
C D
E F
(RMIT University) Brute Force Lecture 4 87 / 95
Graph Search – Analysis
DFS BFS
Applications connectivity,
acyclicity
connectivity,
acyclicity,
shortest
paths
Efficiency for adjacency matrix Θ(|V 2|) Θ(|V 2|)
Efficiency for adjacency lists Θ(|V |+ |E |) Θ(|V |+ |E |)
(RMIT University) Brute Force Lecture 4 88 / 95
Overview
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 89 / 95
Case Study
From this week onwards, we are going to study a particular problem
and how to solve it using one of the algorithms we learn in that week’s
paradigm.
The structure will be a general problem statement, we then discuss
how to map this to a problem we know the algorithm for, then solve it
using that algorithm. There maybe more than one algorithm that can
solve a problem, then we should evaluate in terms of the problem
requirements and characteristics such as time complexity.
(RMIT University) Brute Force Lecture 4 90 / 95
Case Study - Problem
Case Study Problem
ABC Gold Plated Power Company operates a power transmission
network and recently had some failures in their lines and shutdown of
some substations. They want to determine if all their substations and
customers’ homes are connected to the network.
They have asked you to help them. How would you approach this
problem?
(RMIT University) Brute Force Lecture 4 91 / 95
Case Study - Mapping the Problem to a Known
Problem
This can be mapped into a graph problem. Each substation and home
is a vertex in that graph. Each transmission line between substation
and/or home is an edge.
(RMIT University) Brute Force Lecture 4 92 / 95
Case Study - Solving the Problem
Finding whether this graph is connected is equivalent to finding if all
substations and homes are connected.
We know we can use either DFS and BFS to determine if a graph is
connected. A DFS or BFS traversal of this graph is fully connected if it
contains all vertices (why is this so?)
(d) Fully connected. (e) Not fully connected.
(RMIT University) Brute Force Lecture 4 93 / 95
Overview
1 Overview
2 Sorting
3 Exhaustive Search
4 Graph Search
5 Case Study
6 Summary
(RMIT University) Brute Force Lecture 4 94 / 95
Summary
• Introduced the Brute force algorithmic approach.
• Sorting - selection and bubble sort.
• Exhaustive search (enumeration) - knapsack
• Graph search - DFS, BFS
Next week: Decrease-and-conquer and learn about more algorithms
that can be used to solve interesting problems.
(RMIT University) Brute Force Lecture 4 95 / 95
Overview
Sorting
Exhaustive Search
Graph Search
Case Study
Summary