Brute Force Algorithm

Introduction to Brute Force Algorithm

“Data is the new oil” this is the new mantra that is ruling the global economy. We live in the digital world, and every business revolves around data, which translates into profits and helps the industries stay ahead of their competition. With the rapid digitization, an exponential increase in the app-based business model, cyber-crimes is a constant threat. One such common activity that hackers perform is Brute force.

Brute Force is a trial and error approach where attackers use programs to try out various combinations to break into any websites or systems. They use automated software to repetitively generate the User id and passwords combinations until it eventually generates the right combination.

Brute-Force Search

Brute force search is the most common search algorithm as it does not require any domain knowledge; all that is required is a state description, legal operators, the initial state and the description of a goal state. It does not improve the performance and completely relies on the computing power to try out possible combinations.

The brute force algorithm searches all the positions in the text between 0 and n-m, whether the occurrence of the pattern starts there or not. After each attempt, it shifts the pattern to the right by exactly 1 position. The time complexity of this algorithm is O(m*n). If we are searching for n characters in a string of m characters, then it will take n*m tries.

Let’s see a classic example of a travelling salesman to understand the algorithm in an easy manner.

Suppose a salesman needs to travel 10 different cities in a country, and he wants to determine the shortest possible routes out of all the possible combinations. Here brute force algorithm simply calculates the distance between all the cities and selects the shortest one.

Another example is to make an attempt to break the 5 digit password; then brute force may take up to 10⁵ attempts to crack the code.

Brute Force Sort

In the brute force sort technique, the data list is scanned multiple times to find the smallest element in the list. After each iteration over the list, it replaces the smallest element to the top of the stack and starts the next iteration from the second smallest data in the list.

The above statement can be written in pseudo-code as follows.

 

 

 

 

Here the problem is of size ‘n’, and the basic operation is ‘if’ test where the data items are being compared in each iteration. The will be no difference between the worst and best case as the no of swap is always n-1.

Brute Force String Matching

If all the characters in the pattern are unique, then Brute force string matching can be applied with the complexity of Big O(n) where n is the string’s length. Brute force String matching compares the pattern with the substring of a text character by character until it gets a mismatched character. As soon as a mismatch is found, the substring’s remaining character is dropped, and the algorithm moves to the next substring.

The below pseudo-codes explain the string matching logic. Here the algorithm is trying to search for a pattern of P[0…m-1] in the text T[0….n-1].

Here the worst case would be when a shift to another substring is not made until M^Th comparison.

 

Closest Pair

Problem statement: To find out the two closest points in a set of n points in the two-dimensional cartesian plane. There is n number of scenarios where this problem arises. A real-life example would be in an air traffic control system where you have to monitor the planes flying near to each other, and you have to find out the safest minimum distance these planes should maintain.

Source Link: Wikipedia

The brute force algorithm computes the distance between every distinct set of points and returns the point’s indexes for which the distance is the smallest.

Brute force solves this problem with the time complexity of [O(n2)] where n is the number of points.

Below the pseudo-code uses the brute force algorithm to find the closest point.

Convex Hull

Problem Statement: A convex hull is the smallest polygon that contains all the points. The convex hull of a set s of the point is the smallest convex polygon containing s.

The convex hull for this set of points is the convex polygon with vertices at P1, P5, P6, P7, P3.

A line segment P1 and Pn of a set of n points is a part of the convex hull if and only if all the other points of the set lies inside the polygon boundary formed by the line segment.

Let’s relate it with the rubber band,

Point (x1, y1), (x2,y2) make the line ax+by = c

When a = y2-y1, b = x2-x1 and c = x1*y2 – x2*y1 and divides the plane by ax+by-c < 0 and ax+by-c > 0

So we need to check ax+by-c for the other points.

Brute force solve this problem with the time complexity of O(n³)

Exhaustive Search

For discrete problems in which there is no known efficient solution, it becomes necessary to test each and every possible solution sequentially.

Exhaustive search is an activity to find out all the possible solutions to a problem in a systematic manner.

Let’s try to solve the Travelling salesman problem (TSP) using a Brute exhaustive search algorithm.

Problem Statement: There are n cities that salesmen need to travel, he wants to find out the shortest route covering all the cities.

We are considering Hamilton Circuit to solve this problem. If a circuit exists, then any point can start vertices and end vertices. Once the start vertices are selected, then we only need the order for the remaining vertices, i.e. n-1

Then there would be (n-1)! Possible combinations and the total cost for calculating the path would be O(n). thus the total time complexity would be O(n!).

Conclusion

Now that we have reached the end of this tutorial, I hope you guys have now got a fair idea of what Brute Force is. We have also seen the various Brute force algorithm that you can apply in your application.

Recommended Articles

This has been a guide to Brute Force Algorithm. Here we discussed the Basic concepts of the Brute Force Algorithm. You can also go through our other suggested articles to learn more –

1. What is an Algorithm?
2. Algorithm Interview Questions
3. Introduction To Algorithm
4. Algorithm in Programming