Ch 3.1 brute force, exhaustive search, & selection sort Flashcards
(32 cards)
a straightforward approach to solving a problem, usually
directly based on the problem statement and definitions of the concepts
involved
brute force
consider the exponentiation problem: compute an for a
nonzero number a and a nonnegative integer n. Although this problem might
seem trivial, it provides a useful vehicle for illustrating several algorithm design
strategies, including the brute force. (Also note that computing an mod m for some
large integers is a principal component of a leading encryption algorithm.) By the
definition of exponentiation,
a^n = a* …* a (n times)
This suggests simply computing an by multiplying 1 by a n times
the consecutive integer checking algorithm for computing gcd(m, n) and the definition-based algorithm for matrix multiplication are examples of what algorithm?
brute force
it seems to be the only general approach for which it
is more difficult to point out problems it cannot tackle. Second, for some important problems—e.g., sorting, searching, matrix multiplication, string matching—
the brute-force approach yields reasonable algorithms of at least some practical value with no limitation on instance size. Third, the expense of designing a
more efficient algorithm may be unjustifiable if only a few instances of a problem need to be solved and a brute-force algorithm can solve those instances with
acceptable speed. Fourth, even if too inefficient in general, a brute-force algorithm can still be useful for solving small-size instances of a problem. Finally,
a brute-force algorithm can serve an important theoretical or educational purpose as a yardstick with which to judge more efficient alternatives for solving a
problem.
brute force
We start selection sort by scanning the entire given list to find its smallest element
and exchange it with the first element, putting the smallest element in its final
position in the sorted list. Then we scan the list, starting with the second element,
to find the smallest among the last n − 1 elements and exchange it with the second
element, putting the second smallest element in its final position
on the ith pass through the list, which we number from 0 to n − 2, the algorithm searches
for the smallest item among the last n − i elements and swaps it with Ai
Another brute-force application to the sorting problem is to compare adjacent
elements of the list and exchange them if they are out of order. By doing it
repeatedly,
we end up “bubbling up” the largest element to the last position on
the list. The next pass bubbles up the second largest element, and so on, until
after n − 1 passes the list is sorted.
brute force algorithms
Brute force algorithms are straightforward methods of solving a problem that try every possibility rather than advanced techniques to improve efficiency.
Directly do the problem without considering time and space performance
Advantages
Simple and general (?)
Iterating through all possible solutions. Show that no other solutions exist
Usually efficient for small input size
Disadvantages
Often takes to much time
Brute force algorithms
Sorting
Bubble sort
Selection sort
Searching
Sequential search
Exhaustive search
String matching
Geometric problems
Closest pair, Convex Hull
insertion sort
insertion_sort(A)
for j = 2 to length[A]
{
key = A[j]
// insert A[j] into the sorted sequence A[1..j-1]
i = j – 1
while i>0 and A[i] > key
{
A[i+1] = A[i]
i = i – 1
}// end while
A[i+1] = key
}//end for
bubble sort
Swap pairwise elements which are out of order, from beginning to end
In each round, at least one element is in rightful position
bubble sort algorithm
Data Structure: Array
Input: A[0..n-1]
for i=0 to n-1 do
for j=i to n-1 do
if A[j] > A[j+1]
swap A[j] and A[j+1]
end;
end;
bubble sort c++
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
if (A[i] > A[j])
{
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
20 45 90 8
8 45 90 20
8 20 90 45
8 20 45 90
optimized bubble sort c++
flag = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n-1; j++)
{
if (A[j] > A[j+1])
{
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = 1; // if swapping occurs
}
}
if (flag == 0)
break; // the input list already sorted, no need for the inner loop
}
Sequential Search Algorithm
Data Structure: Array
Input A[0..n−1]
Target key: K
i ← 0
while A[i] K do
i = i + 1
end;
if (i<n)
“Found” at i
else
“not found“;
brute force string matching
Given a string of n characters called the text and a string of m characters (m n) called the pattern, find a substring of the text that matches the pattern.
Algorithm BruteForceStringMatch(T[0..n-1], P[0..m-1])
// Implements brute-force string matching
// Input: An array T[0..n-1] of n characters representing a text and
// an array P[0..m-1] of m characters representing a pattern
// Output: The index of the first character in the text that
// starts a matching substring or -1 if the search
// is unsuccessful
for i = 0 to n-m do
j=0
while j<m and P[j] = T[i+j] do
j = j+1
if j = m return i
return -1;
closest=pair and convex hull problems by brute force
In computational geometry, two well-known problems are to find the closest pair of points and the convex hull of a set of points.
The closest-pair problem, in 2D space, is to find the closest pair of points given a set of n points. Given a list P of n points, P1=(x1,y1), …, Pn=(xn,yn), find distance between two closest points in the plane
BruteForceClosest(P)
min = ∞;
for i = 1 to n-1
for j = i+1 to n do
d ← distance(Pi ,Pj) // Use sqrt(distances squared)
if d < min then
min = d;
return min;
Convex-Hall problem
A set of points (finite or infinite) in the plane is called convex if for any two points p and q in the set, the entire line segment with the endpoints at p and q belongs to the set.
It is a rubber band wrapped around the “outside” points.
The convex hull of a set S of points is the smallest convex set containing S. (The “smallest” requirement means that the convex hull of S must be a subset of any convex set containing S.)
Convex-Hall Problem Theorem
The convex hull of any set S of n > 2 points not all on the same line is a convex polygon with the vertices at some of the points of S. (If all the points do lie on the same line, the polygon degenerates to a line segment but still with the endpoints at two points of S.)
How could you write a brute-force algorithm to find the convex hull?
Compute a line segment (P1, P2) where P1 and P2 are on the convex hull’s boundary.
Check if and only if all the other points in the set lie on the same side of the line segment. For all points above the line, ax + by > c, while for all points below the line, ax + by < c. Using these formulas, we can determine if two points are on the boundary to the convex hull.
graph coloring problem
Given a graphGand a number of colors, find an assignment of colors to the vertices ofGsuch that two vertices that are connected by an edge are never assigned the same color
vertex coloring
Given m colors, find a way of coloring the vertices of a graph such that no two adjacent vertices are colored using same color. The other graph coloring problems likeEdge Coloring(No vertex is incident to two edges of same color) andFace Coloring(Geographical Map Coloring) can be transformed into vertex coloring.
chromatic number
The smallest number of colors needed to color the vertices of a graph G so that no two adjacent vertices share the same color is called its chromatic number.
