1/31/2012
Exponentiation by brute force
CS361: Algorithms and Data Structures
Week 3: Brute Force Methods
Power(a, n) // Computes an // Input: Any number a, and a non-negative integer n p1 for i 0 to n - 1 do p pxa return p
David Akers
Matrix multiplication by brute force
MatrixMultiplication (A[0..n-1, 0..n-1], B[0..n-1, 0..n-1])
// Multiplies two n-by-n matrices // Input: Two n-by-n matrices A and B // Output: Matrix C = AB
GCD by brute force
GCD (m, n)
// Input: Two non-negative integers m and n // Output: the greatest common divisor of m and n
for i 0 to n - 1 do for j 0 to n - 1 do C[i,j] = 0.0 for k 0 to n - 1 do C[i,j] C[i,j] + A[i,k] x B[k,j] return C
t min{m, n} while (t > 0) if (m % t == 0 and n % t == 0) return t else t t-1
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.
Levitin p. 97
Brute force vs. best known
Problem exponentiation matrix mult GCD Brute force (n) (n3) (n) Best known
1/31/2012
Brute force vs. best known
Problem exponentiation matrix mult GCD Brute force (n) (n3) (n) Best known (log n) (n2.807) (log n)
Why brute force?
Why brute force?
1. Works for almost all problems. 2. Results in simple, easy-to-implement algorithms. 3. May provide acceptable efficiency when: a) Only need to solve a few instances ) y b) Only need to solve instances with small n. 4. Sometimes we havent found a way to do better! 5. Can provide a useful yardstick for efficient algorithms. 6. Provides a placeholder for more efficient algorithms.
Bubble sort
BubbleSort(A[0..n-1])
// Input: An array A[0..n-1] of orderable elements // Output: Array A[0..n-1], sorted in ascending order.
for i 0 to n 2 do for j 0 to n - 2 i do if A[j + 1] < A[j] swap (A[j], A[j+1]) return A
Selection sort
SelectionSort (A[0..n-1]) // Sorts a given array // Input: An array A[0..n-1] of orderable elements. // Output: An array A[0..n-1] sorted in ascending order. A[0..n 1] for i 0 to n 2 do min i for j i + 1 to n - 1 do if A[j] < A[min] min j swap A[i] and A[min]
Selection sort
for i 0 to n 2 do min i for j i + 1 to n - 1 do if A[j] < A[min] min j swap A[i] and A[min]
find minimum element on right move it into position
1/31/2012
Truly brute force sorting?
BogoSort(A[0..n-1])
// Input: An array A[0..n-1] of orderable elements // Output: Array A[0..n 1], sorted in ascending order. A[0..n-1],
Sequential search
SequentialSearch(A[0..n-1], K)
// Input: An array A[0..n-1] of elements, and a search key K. // Output: Index of the first element of A that matches K (or -1 if there are no // matching elements).
while not InOrder(A[0..n-1]) do RandomShuffle(A);
i 0 while i < n and A[i] K do i i+1 if i < n return i else return -1 Whats the running time?
Enhanced sequential search
FasterSequentialSearch(A[0..n-1], K)
// Input: An array A[0..n-1] of elements, and a search key K. // Output: Index of the first element of A that matches K (or -1 if there are no // matching elements).
Brute force string matching
Search for DAB in the string DAVE DABBLES n characters D A V E - D A B B L E S D A B D A B D A B Whats the worst case D A B running time? D A B D A B m characters
A[n] K i 0 while A[i] K do i i+1 if i < n return i else return -1
// adding K as a sentinel
Brute force string matching
BruteForceStringMatch( T [0..n-1], P [0..m-1)]
// Input: // // Output: // An array T [0..n-1] representing a text, and an array P [0..m-1)] representing a pattern Index of the first character in the text that starts a matching substring, or -1 if the search is unsuccessful.
Multi-variable big-oh
One variable:
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
Multiple variables:
