Algorithm design techniques and their real life examples.

An algorithm is a sequence of instructions written to solve a well formulated problem. Over the past half century, computer scientists have discovered several algorithms that use different approaches to solve a similar problem. We will discuss some of them here along with their real-life applications.

Brute Force Algorithms:

A brute force search algorithm is the most straightforward way of solving a problem by examining every possible alternative to find a solution of a given problem. They are the easiest algorithms to design as they do not need any prior domain knowledge but are relatively slower for practical problems than other algorithms.

For example, imagine you have a small padlock with 4 digits ranging from 0–9. Unfortunately, you forgot your password and can not afford a new one so you apply brute force algorithm by setting all numbers from 0000 to 9999 which gives us a possibility of 10⁴ combinations.

Branch and Bound Algorithms:

These algorithms are generally used for optimization problems (problems involving finding the best solutions from the feasible ones) in which a root problem is further divided into subproblems which helps in ruling out a large number of alternatives.

For example, suppose you live in a three story home and want to find a ringing phone which could be anywhere on all of the three floors. If you are standing on the first floor and hear your phone ringing above your head, you can immediately rule out the possibilities of it being in the basement or on the first floor and directly go to the second floor to search for it.

Greedy Algorithms:

Greedy algorithms are based on a design technique that chooses the next option based on the most obvious and attractive benefit. A greedy algorithm works in two phases

1. The first phase includes taking what you can get at best right now without thinking about the future consequences.

2. Hoping that what you chose in the first step will eventually lead to a global optimal solution.

The greedy algorithm always gives an optimal solution to US currency. For example, you went to a shop and your total was 3.61$. You handed over a 10$ bill to the cashier. Now the cashier will use greedy algorithm to find you a change by selecting the largest possible bill or coin that does not cross the limit.

1. a $5 bill

2. a $1 bill, to make $6

3. a 25¢ coin, to make $6.25

4. A 10¢ coin, to make $6.35

5. four 1¢ coins, to make $6.39

Recursive Algorithms:

Recursive algorithms are the type of algorithms that call themselves by inputting the result of the current step to themselves to eventually come up with a solution

For example, some of you might have noticed that if you type recursion on google there is a “did you mean” clause having the value “recursion” that upon click returns you to the same page. It is kind of an inside joke that by pressing the link you create an infinite loop which will help you in understanding the true meaning and application of recursion

Divide and conquer algorithms:

Big problems are difficult to solve altogether but if we divide them into smaller ones they become easier and efficient to handle and solve. Divide-and-conquer algorithms do exactly the same. They split a problem into smaller subproblems, solving the subproblems independently, and then combining the solutions of subproblems into a solution of the original problem.

This technique can be divided into the following three parts:

1. Divide: This involves dividing the problem into some sub problem.

2. Conquer: Sub problem by calling recursively until sub problem solved.

3. Combine: The Sub problem Solved so that we will get find problem solution.

For example, while solving a puzzle, we always tend to divide the pieces into certain types like left corner, right corner and middle parts and progressively combine the pieces into larger ones until we reach the final result. So this approach also comes under the hood of design and conquer algorithm technique.

Randomized algorithms:

Randomized algorithms are algorithms that utilizes a degree of randomness in their logic. The output of such algorithms are based on the probabilistic random choices made by algorithm during its execution.

For example, in cryptography, one time pad (OTP) is an encryption technique that uses randomized algorithm approach to prepare a random secret key to pair with plain text that can not be cracked.

Conclusion:

We discussed some of the most frequently used algorithm techniques and how they could be applied in our everyday life tasks. It is necessary to develop a good understanding of different design techniques as it will enable us to understand our problems better and apply the right design technique to them.

Here is the link to my favorite book about algorithms and their applications.

Thanks for reading!