Brute force

A straightforward approach usually based on

problem statement and definitions
(Pendekatan langsung biasanya didasarkan pada
pernyataan masalah dan definisi)

Examples:
1. Selection Sort
2. Graph Traversal
3. Simple Computational Tasks
4. Exhaustive Search
Design and Analysis of Algorithms –
1
Chapter 3
Brute force strengths and weaknesses
• Strengths:
– wide applicability

– simplicity

– yields reasonable algorithms for some important problems

• sorting; matrix multiplication; closest-pair; convex-hull

– yields standard algorithms for simple computational tasks and

graph traversal problems

Design and Analysis of Algorithms –

2
Chapter 3
Brute force strengths and weaknesses
Weaknesses:
– rarely yields efficient algorithms

– some brute force algorithms unacceptably slow

• e.g., the recursive algorithm for computing Fibonacci numbers

– not as constructive/creative as some other design techniques

Design and Analysis of Algorithms –

3
Chapter 3
 Graph traversal
Many problems in A.I. and operations research
require the systematic processing of vertices and
edges of graphs

Graph traversal algorithms:

– Depth-first search
– Breadth-first search

First, graph representations!

Design and Analysis of Algorithms –

4
Chapter 4
 Graph representations using data
structures
Adjacency Matrix Representation
– Let G = (V, E), n = |V|, m = |E|, V = {v1, v2, …,
vn)
– G can be represented by an n  n matrix C

Design and Analysis of Algorithms –

5
Chapter 4
Adjacency list representation

Design and Analysis of Algorithms –

6
Chapter 4
 Traversing graphs
Depth-First Search (DFS) and Breadth-First Search (BFS)

– Two elementary traversal strategies

– Both provide efficient ways to “visit” each vertex and edge
of a graph
– Both work on directed and undirected graphs
– They differ in the order of “visiting” vertices

Design and Analysis of Algorithms –

7
Chapter 4
 Depth-first search
• Explore graph always moving away from last visited vertex
• Pseudocode for Depth-first-search of graph G=(V,E)

DFS(G) dfs(v)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
(unvisited) for each vertex w adjacent to v
for each vertex v V do do
if v is marked with 0 if w is marked with 0
dfs(v) dfs(w)

Design and Analysis of Algorithms –

8
Chapter 4
 Example – undirected graph
a b c d

e f g h

dfs(v)
count := count + 1
mark v with count
Depth-first traversal: for each vertex w adjacent to v
do
if w is marked with 0
Design and Analysis of Algorithms –
dfs(w)
9
Chapter 4
 Question
How to rewrite the procedure dfs(v), using a
stack to eliminate recursion

dfs(v)
count := count + 1
mark v with count
for each vertex w adjacent to v do
if w is marked with 0
dfs(w)

Design and Analysis of Algorithms –

10
Chapter 4
Non-recursive version of DFS algorithm
Algorithm dfs(v)
s.createStack();
s.push(v);
count := count + 1
mark v with count
while (!s.isEmpty()) {
let x be the node on the top of the stack s;
if (no unvisited nodes are adjacent to x)
s.pop(); // backtrack
else {
select an unvisited node u adjacent to x;
s.push(u);
count := count + 1
mark u with count
}
Design and Analysis of Algorithms –
} 11
Chapter 4
 Time efficiency analysis
DFS can be implemented with graphs
represented as:
– Adjacency matrices:

DFS(G) dfs(v)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
(unvisited) for each vertex w adjacent to v
for each vertex v V do do
if v is marked with 0 if w is marked with 0
dfs(v) dfs(w)
Design and Analysis of Algorithms –
12
Chapter 4
 Time efficiency analysis
DFS can be implemented with graphs
represented as:
– Adjacency linked lists:

DFS(G) dfs(v)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
(unvisited) for each vertex w adjacent to v
for each vertex v V do do
if v is marked with 0 if w is marked with 0
dfs(v) dfs(w)
Design and Analysis of Algorithms –
13
Chapter 4
 Time efficiency analysis
DFS can be implemented with graphs represented
as:
– Adjacency matrices: Θ(V2)
– Adjacency linked lists: Θ(V+E)

DFS(G) dfs(v)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
(unvisited) for each vertex w adjacent to v
for each vertex v V do do
if v is marked with 0 if w is marked with 0
dfs(v) dfs(w)
Design and Analysis of Algorithms –
14
Chapter 4
Application: checking graph connectivity and
finding connected components

DFS(G) dfs(v)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
(unvisited) for each vertex w adjacent to v
for each vertex v V do do
if v is marked with 0 if w is marked with 0
dfs(v) dfs(w)

Design and Analysis of Algorithms –

15
Chapter 4
 Application: checking acyclicity

DFS(G) dfs(v)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
(unvisited) for each vertex w adjacent to v
for each vertex v V do do
if v is marked with 0 if w is marked with 0
dfs(v) dfs(w)

Design and Analysis of Algorithms –

16
Chapter 4
 Breadth-first search
Explore graph moving across to all the neighbors
of last visited vertex

Similar to level-by-level tree traversals

Applications: same as DFS, but can also find

paths from a vertex to all other vertices with the
smallest number of edges
Design and Analysis of Algorithms –
17
Chapter 4
 Example – undirected graph

a b c d

e f g h

Breadth-first traversal:

Design and Analysis of Algorithms –

18
Chapter 4
 Example – undirected graph

a b c d

e f g h

Depth-first search could be implemented on a stack

How about breadth-first search

Design and Analysis of Algorithms –

19
Chapter 4
 Breadth-first search algorithm
bfs(v)
BFS(G)
count :=0 count := count + 1
mark each vertex with 0 mark v with count
for each vertex v V initialize queue with v
do while queue is not empty do
if v is marked a := front of queue
with 0 for each vertex w adjacent to a do
bfs(v)
if w is marked with 0
count := count + 1
mark w with count
add w to the end of the queue
remove a from the front of the queue
Design and Analysis of Algorithms –
20
Chapter 4
 Breadth-first search: Notes
BFS has same efficiency as DFS and can be
implemented with graphs represented as:

– Adjacency matrices: Θ(V2)

– Adjacency linked lists: Θ(V+E)

Design and Analysis of Algorithms –

21
Chapter 4
 Brute force polynomial evaluation
Problem: Find the value of polynomial
p(x) = anxn + an-1xn-1 +… + a1x1 + a0
at a point x = x0

Design and Analysis of Algorithms –

22
Chapter 3
 Brute force polynomial evaluation
Problem: Find the value of polynomial
p(x) = anxn + an-1xn-1 +… + a1x1 + a0
at a point x = x0
x := x0
p := 0.0
Algorithm:
for i := n down to 0 do
power := 1
for j := 1 to i do
power := power * x
p := p + a[i] * power
return p
Efficiency:
Design and Analysis of Algorithms –
23
Chapter 3
 Brute force polynomial evaluation
Problem: Find the value of polynomial
p(x) = anxn + an-1xn-1 +… + a1x1 + a0
at a point x = x0 x := x0
p := 0.0
for i := n down to 0 do
Algorithm: power := 1
for j := 1 to i do
power := power * x
p := p + a[i] * power
return p
Efficiency: (n2)
Design and Analysis of Algorithms –
24
Chapter 3
 Brute force polynomial evaluation
Problem: Find the value of polynomial
p(x) = anxn + an-1xn-1 +… + a1x1 + a0
at a point x = x0 x := x0
p := 0.0
for i := n down to 0 do
Algorithm: power := 1
for j := 1 to i do
power := power * x
p := p + a[i] * power
return p
Efficiency: (n2)
Can we design a linear algorithm for this problem
Design and Analysis of Algorithms –
25
Chapter 3
Polynomial evaluation: improvement
 We can do better by evaluating from right to left: p(x) = anxn +
an-1xn-1 +… + a1x1 + a0 at a point x = x0
 Algorithm:

x := x0
p := a[0]
power := 1
for i := 1 to n do
power := power * x
p := p + a[i] * power
return p

 Efficiency: (n)

Design and Analysis of Algorithms –

26
Chapter 3
Polynomial evaluation: improvement
We can do better by evaluating from right to left:
p(x) = anxn + an-1xn-1 +… + a1x1 + a0 at a point x = x0
Algorithm:

x := x0
p := a[0]
power := 1
for i := 1 to n do
power := power * x
p := p + a[i] * power
return p
Efficiency: (n)
Can we design a better than linear algorithm for this problem
Design and Analysis of Algorithms –
27
Chapter 3
 Brute force closest-pair algorithm
Closest pair
• Problem: find the closest pair among n points in k-dimensional
space

Design and Analysis of Algorithms –

28
Chapter 3
 Brute force closest-pair algorithm
Closest pair
• Problem: find the closest pair among n points in k-dimensional space
• Algorithm: Compute distance between each pair of points and
identify the pair resulting in the shortest distance
• What is (or should be) the basic operation of the algorithm?

Design and Analysis of Algorithms –

29
Chapter 3
Brute force closest-pair algorithm
 Closest pair
• Problem: find the closest pair among n points in k-dimensional
space
• Algorithm: Compute distance between each pair of points and
identify the pair resulting in the shortest distance
• Basic operation d
k

 (x  y ) i i
2

i 1
• (squaring): k
d2   (x  y )
i 1
i i
2

Design and Analysis of Algorithms –

30
Chapter 3
Brute force closest-pair algorithm
 Closest pair
• Problem: find the closest pair among n points in k-dimensional space
• Algorithm: Compute distance between each pair of points and
identify the pair resulting in the shortest distance
• Basic operation:
k
d  (x  y )
i 1
i i
2

k
d2   (x  y )
i 1
i i
2

• How many different pairs of points?

Design and Analysis of Algorithms –

31
Chapter 3
Principle of counting: Product Rule
The Product Rule
– Suppose that a procedure can be broken down
into a sequence of two tasks. If there are n1 ways
to do the first task and for each of these ways of
doing the first task, there are n2 ways to do the
second task, then there are n1n2 ways to do the
procedure.

Design and Analysis of Algorithms –

32
Chapter 3
Principle of counting: Product Rule
The Product Rule
– Suppose that a procedure can be broken down into a
sequence of two tasks. If there are n1 ways to do the first
task and for each of these ways of doing the first task,
there are n2 ways to do the second task, then there are
n1n2 ways to do the procedure.

Calculation
– Applying the product rule, there are n*(n-1) pairs among n
points
– Considering (a, b) and (b, a) as the same, we divide the
above number by 2 and thus, there are n*(n-1)/2 different
pairs of points

Design and Analysis of Algorithms –

33
Chapter 3
 Brute force closest-pair algorithm
Closest pair
• Problem: find the closest pair among n points in k-dimensional space
• Algorithm: Compute distance between each pair of points and
identify the pair resulting in the shortest distance
• Basic operation:
k
d  (x  y )
i 1
i i
2

k
d2   (x  y )
i 1
i i
2

• Efficiency: (n2)

Design and Analysis of Algorithms –

34
Chapter 3
 In-class exercise
Can you design a faster algorithm than the one based
on the brute-force strategy to solve the closest-pair
problem for n points x1, x2, … , xn on the real line?

What is the time efficiency of your algorithm?

Design and Analysis of Algorithms –

35
Chapter 3
 Convex hull problem
• Convex hull
– Problem:
Find smallest convex polygon enclosing n
points on the plane

– Convex:
• A geometric figure with no
convex indentations.
• Formally, a geometric figure is convex
if every line segment connecting
interior points is entirely contained
within the figure's interior.
Non-convex
Design and Analysis of Algorithms –
36
Chapter 3
 Example: Convex Hull
Input: p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11

Output: p2,p9,p11,p4,p5,p6,p8,p2 p9
p11
p4
p2 p1
p7 p3

p10 p5
p8
p6
 Convex hull: application domain*
• Computer visualization, ray tracing
– (e.g. video games, replacement of bounding boxes)
• Path finding
– (e.g. embedded AI of Mars mission rovers)
• Geographical Information Systems (GIS)
– (e.g. computing accessibility maps)
• Visual pattern matching
– (e.g. detecting car license plates)
• Verification methods
– (e.g. bounding of Number Decision Diagrams)
• Geometry
– (e.g. diameter computation)
*slide refer to http://www.montefiore.ulg.ac.be/~briquet/algo3-chull-20070206.pdf

Design and Analysis of Algorithms –

38
Chapter 3
Convex hull brute force algorithm
Extreme points of the convex p9
p11
polygon
– Consider all the points in the p4
polygon as a set. An extreme p2 p1
point is a point of the set that p3
p7
is not a middle point of any
line segment with end points p10 p5
in the set. p8
p6

Design and Analysis of Algorithms –

39
Chapter 3
Convex hull brute force algorithm
Extreme points of the convex p9
p11
polygon
– Consider all the points in the p4
polygon as a set. An extreme p2 p1
point is a point of the set that p3
p7
is not a middle point of any
line segment with end points p10 p5
in the set. p8
p6
Which pairs of extreme points need to be connected
to form the boundary of the convex hull?

Design and Analysis of Algorithms –

40
Chapter 3
Convex hull brute force algorithm

A line segment connecting two points Pi and Pj of a

set of n points is a part of its convex hull’s boundary if
and only if all the other points of the set lies on the
same side of the straight line through these two
points.

Design and Analysis of Algorithms –

41
Chapter 3
 Convex hull brute force algorithm
The straight line through two points (x1, y1), (x2, y2)
in the coordinate plane can be defined by the
following equation
– ax + by = c
where a = y2 – y1, b = x1 – x2, c = x1y2 - y1x2

Such a line divides the plane into two half-planes: for

all the points in one of them: ax + by > c, while for all
the points in the other, ax + by < c.

Design and Analysis of Algorithms –

42
Chapter 3
 Convex hull brute force algorithm
Algorithm: For each pair of points p1 and p2 determine
whether all other points lie to the same side of the
straight line through p1 and p2, i.e. whether ax+by-c all
have the same sign

Efficiency:

Design and Analysis of Algorithms –

43
Chapter 3
 Convex hull brute force algorithm
• Algorithm: For each pair of points p1 and p2
determine whether all other points lie to the same
side of the straight line through p1 and p2, i.e.
whether ax+by-c all have the same sign

• Efficiency: (n3)

Design and Analysis of Algorithms –

44
Chapter 3
 Exhaustive search: definition

• A brute force solution to a problem involving search

for an element with a special property, usually among
combinatorial objects such as a permutations,
combinations, or subsets of a set.

Design and Analysis of Algorithms –

45
Chapter 3
 Exhaustive search: method
• Construct a way of listing all potential solutions to
the problem in a systematic manner
– all solutions are eventually listed
– no solution is repeated
• Evaluate solutions one by one, perhaps disqualifying
infeasible ones and keeping track of the best one
found so far
• When search ends, announce the winner

Design and Analysis of Algorithms –

46
Chapter 3
 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.
2
• Example: a b
5 3
8 4

c 7
d
Design and Analysis of Algorithms –
47
Chapter 3
 Traveling salesman 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:

Design and Analysis of Algorithms –

48
Chapter 3
 Traveling salesman 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)!/2

Design and Analysis of Algorithms –

49
Chapter 3
 0-1 Knapsack problem
• Given a knapsack with maximum capacity W, and a
set S consisting of n items

• Each item i has some weight wi and benefit value vi

• Problem: How to pack the knapsack to achieve

maximum total value of packed items?

Design and Analysis of Algorithms –

50
Chapter 3
0-1 Knapsack problem: a picture
Weight Benefit value
Items
wi vi

2 3
This is a knapsack 3 4
Max weight: W = 20 4 5

5 8
W = 20

9 10
Design and Analysis of Algorithms –
51
Chapter 3
 0-1 Knapsack problem
• Problem, in other words, is to find

max  vi subject to w W i
iT iT

 The problem is called a “0-1” problem, because

each item must be entirely accepted or rejected.
 In the “Fractional Knapsack Problem,” we can
take fractions of items.

Design and Analysis of Algorithms –

52
Chapter 3
 0-1 Knapsack problem: brute-force approach

Let’s first solve this problem with a straightforward

algorithm

• We go through all combinations (subsets) and

find the one with maximum value and with total
weight less or equal to W

Design and Analysis of Algorithms –

53
Chapter 3
 Example 2: Knapsack Problem
Given n items:
– weights: w1 w2 … wn
– values: v1 v2 … vn
– a knapsack of capacity W
Find the most valuable subset of the items that fit into
the knapsack

Example:
item weight value Knapsack capacity W=16
1 2 $20
2 5 $30
3 10 $50
4 5 $10
Design and Analysis of Algorithms –
54
Chapter 3
 Knapsack by exhaustive search
Subset Total weight Total value
 0 $0
{1} 2 $20 Most valuable subset?
{2} 5 $30
{3} 10 $50
{4} 5 $10
{1,2} 7 $50
{1,3} 12 $70 Efficiency:
{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

Design and Analysis of Algorithms –

55
Chapter 3
 0-1 Knapsack problem: brute-force approach

• Algorithm:
– We go through all combinations and find the one with
maximum value and with total weight less or equal to
W
 Efficiency:
• Since there are n items, there are 2n possible
combinations of items.
• Thus, the running time will be O(2n)

Design and Analysis of Algorithms –

56
Chapter 3