Algorithms Calling Algorithms!
Introduction to Algorithms in easiest way.
Hello, This is probably going to be yet another blog around algorithms but I want all of you people to bear with me. In this blog I am going to explain the algorithms in Layman’s terms as so that more of you (Tech as well as non-Tech) folks can understand easily and maybe they might lose some fear or at least I can hope so. Let’s get started.
Introduction to algorithms
Imagine, you live in a house or an apartment with joint family or nucleus family and either your mother or you cooking for the family every day twice with limited resources and time. Tasty food and limited dishes to do after. But then comes the festival time in year maybe multiple times in a year specially in India where we get to meet lots of our colleagues and relatives visit our house with greetings and sweets. We share food a lot, share memories with each other and that’s how we celebrate the festivals.
Now you all must be thinking why am I telling you this instead of explaining algorithms. Here’s the surprising factor, when you and your few family members having food cooked on daily basis with limited resources and time, we should consider that happy moments, hence we that in tech terms as “Best Case”. But in festive season the amount of food, the dishes, the people, and time increased manifolds, which takes lot of time and efforts, hence we take that as “Worst Case”. So that we can be prepared for it. As in above example we managed to feed all the people having already a thought of worst case scenario.
In day-to-day life we try to act as if anything goes wrong, we would be able to tackle with it with least collateral damage or minimum stress. Similarly, while building algorithms around the problems in world we tend to think of worst case and then optimize it to solve the complex problems. I hope you can comprehend the explanation. Let’s move further into technicalities.
History
The concept of algorithms has existed since antiquity. Arithmetic algorithms, such as a division algorithm, were used by ancient Babylonian mathematicians. 2500 BC and Egyptian mathematicians. 1550 BC. Greek mathematicians later used algorithms in 240 BC in the sieve of Eratosthenes for finding prime numbers, and the Euclidean algorithm for finding the greatest common divisor of two numbers. Arabic mathematicians such as al-Kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.
In English, the word algorithm was first used in about 1230 and then by Chaucer in 1391. English adopted the French term, but it was not until the late 19th century that "algorithm" took on the meaning that it has in modern English.
Computational Algorithms
In mathematics and computer science, an algorithm is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus".
Algorithm Design
Algorithm design refers to a method or a mathematical process for problem-solving and engineering algorithms. The design of algorithms is part of many solution theories, such as divide-and-conquer or dynamic programming within operation research. Techniques for designing and implementing algorithm designs are also called algorithm design patterns, with examples including the template method pattern and the decorator pattern.
Typical steps in the development of algorithms:
Problem definition
Development of a model
Specification of the algorithm an algorithm
Checking the correctness of the algorithm
Analysis of algorithm
Implementation of algorithm
Program testing
Documentation preparation
Complexities
One of the most important aspects of algorithm design is resource (run-time, memory usage) efficiency; the big-Oh notation (O) is used to describe e.g. an algorithm's run-time growth as the size of its input increases.
0 <= f(n) <= Cg(n) for all n >= n0>
Big Omega notation (Ω) is defined as lower bound on an algorithm is the least amount of time required i.e. best case scenario.
0 <= Cg(n) <= f(n) for all n >= n0
Big Theta notation (Θ) is define as tightest bound and tightest bound is the best of all the worst case times that the algorithm can take. i.e. average case scenario.
Mathematically,
0 <= f(n) <= C1g(n) for n >= n0
0 <= C2g(n) <= f(n) for n >= n0
**Merging both the equation, we get : **
0 <= C2g(n) <= f(n) <= C1g(n) for n >= n0
There are different types of complexities used, let's see one by one:
1. Constant Time O(1)
An algorithm is said to have constant time with order O(1) when it is not dependent on the input size n. Irrespective of the input size n, the runtime will always be the same.
int[] arr = [ 1, 2, 3, 4, 5];
arr[2]; // => 3
2. Linear Time O(n)
An algorithm is said to have a linear time complexity when the running time increases linearly with length of the input. When the function involves checking all the values in input data, with this order O(n).
// if we used for loop to print out the values of the arrays
for (int i = 0; i < array.length; i++) { System.out.println(array[i]);}
int[] arr1 = [1, 2, 3, 4]; //=> 4 steps
int[] arr2 = [1, 2, 3, 4, 5]; //=> 5 steps
3. Logarithmic Time O(log n)
An algorithm is said to have a logarithmic time complexity when it reduces the size of the input data in each step. this indicates that the number of operations is not the same as the input size. The number of operations gets reduced as the input size increases. Algorithms are found in Binary trees or binary search functions.
//Iterative Method
binarySearch(arr, x, low, high){
repeat till low = high
mid = low + (high - low) / 2
if (x == arr[mid])
return mid
else if (x > arr[mid]) // x is on the right side
low = mid + 1
else // x is on the left side
high = mid - 1
//Recursive Method
binarySearch(arr, x, low, high)
if(low > high)
return false
else
mid = low + (high - low) / 2
if (x == arr[mid])
return mid
else if (x > arr[mid) //x is on the right side
return binarySearch(arr, x ,mid + 1, high)
else // x is on the left side
return binarySearch(arr, x, low, mid - 1)
4. Quadratic Time O(n^2)
An algorithm is said to have a non-linear time complexity where the running time increases non-linearly(n^2) with the length of the input. Generally, nested loops come under this order where one loop takes O(n) and if the function involves a loop with a loop, then it goes for O(n) * O(n) = O(n^2) order.
for(int i = 0; i < length; i++) { //has O(n) time complexity
for(int j = 0; j < length; j++) { //has O(n^2) time complexity // More loops?
}}
Algorithmic analysis
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms--the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity).
An algorithm is said to be efficient when this function's values are small, or grow slowly compared a growth in the size of the input. Different inputs of the same size may cause the algorithm to have different behavior, so *best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm.
The term "analysis of algorithms" was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources need by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable direction of search for efficient algorithms.
Different algorithms may complete the same task with different set of instructions in less or more time, space, or effort than others. For example, a binary search algorithm (with cost O(log n)) outperforms a sequential search (cost O(n)) when used for table lookups on sorted lists or arrays.
Formal versus empirical
The analysis of algorithms is often practiced abstractly without the use of specific programming language implementation. In this sense, algorithm analysis resembles other mathematical disciplines in that it focuses on the underlying properties of the algorithm and not on the specifics of any particular implementation.
Usually pseudocode is used for analysis as it is the simplest and most general representation. However, ultimately, most algorithms are usually implemented on particular hardware/software platforms and their algorithmic efficiency is eventually put to the test using real code.
Empirical testing is useful because it may uncover unexpected interactions that affect performance. Benchmarks may be used to compare before/after potential improvements to an algorithm after program optimization. Empirical tests cannot replace formal analysis, though, and are not trivial to perform in a fair manner.
Execution efficiency
To illustrate the potential improvements possible even in well-established algorithms, a recent significant innovation, relating to FFT (Fast Fourier Transform) algorithms (used heavily in the field of image processing), can decrease processing time up to 1,000 times for applications like medical imaging.
In general, speed improvements depend on special properties of the problem, which are very common in practical applications. Speedups of this magnitude enable computing devices that make extensive use of image processing (like digital cameras and medical equipment) to consume less power.
Classifications of algorithms
There various ways to classify algorithms, each with its own merits.
By implementation
Recursion
int gcd(int A, int B) {
if (B == 0)
return A;
else if (A > B)
return gcd(A - B, B);
else
return gcd(A, B - A);
}
A recursion algorithm is one that invokes (makes reference to) itself repeatedly until a certain condition (also known as termination condition) matches, which is a method common to function programming.
Iterative algorithms use repetitive constructs like loops and sometimes additional data structures like stacks to solve the given problems. Some problems are naturally suited for one implementation or the other.
For example, Towers of Hanoi is well understood using recursive implementation.
Every recursive version has an equivalent ( but possibly more ore less complex) iterative version, and vice versa.
Logical
An algorithm may be viewed as controlled logical deduction. This notion may be expressed as: Algorithm = logic + control. The logic component expresses the axioms that may be used in the computation and the control component determines the way in which deduction is applied to the axioms.
This is the basis for the logic programming paradigm. In pure logic programming languages, the control component is fixed and algorithms are specified by supplying only the logic component. The appeal of this approach is the elegant semantics: a change in the axioms produces a well-defined change in the algorithm.
Serial, parallel or distributed
Algorithms are usually discussed with the assumption that computers execute one instruction of an algorithm at a time. Those computers are sometimes called serial computer. An algorithm designed for such an environment is called a serial algorithm, as opposed to parallel algorithms or distributed algorithms.
Parallel algorithms take advantage of computer architectures where several processors can work on a problem at the same time, whereas distributed algorithms use multiple machines connected with a computer network.
Parallel or distributed algorithms divide the problem into more symmetrical or asymmetrical subproblems and collect the results back together.
Deterministic or non-deterministic
Deterministic algorithms solve the problem with exact decision at every step of the algorithm whereas non-deterministic algorithms solve problems via guessing although typical guesses are made more accurate through the use of heuristics.
By design paradigm
It categorizes further into different types of algorithms:
Brute-force or exhaustive search
This is native method of trying every possible solution to see which is best.
Divide and Conquer
A divide-and-conquer algorithm repeatedly and instance of a problem to one or more smaller instances of the same problem (usually recursively*) until the instances are small enough to solve easily.
A simpler variant of divide and conquer is called a decrease-and-conquer algorithm, which solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem. Divide and conquer divides the problem into multiple subproblems and so the conquer stage is more complex than decrease and conquer algorithm.
Search and enumeration
Many problems (such as playin chess) can be modeled as problems on graphs. A graph exploration algorithm specifies rules for moving around a graph and is useful for such problems. This category also includes search algorithms, branch and bound enumeration and backtracking.
Randomized algorithm
They can be very useful in finding approximate solution for problems where finding exact solutions can be impractical. For some of these problems, it is known that the fastest approximations must involve some randomness.
There are two large classes of such algorithms:
Monte Carlo algorithms return a correct answer with high-probability.
Las Vegas algorithms always return the correct answer, but their running time is only probabilistically bound.
Reduction of complexity
This technique involves solving a difficult problem by transforming it into better-known problem for which we have asymptotically optimal algorithms.
The goal is to find a reducing algorithms whose complexity is not dominated by the resulting reduced algorithm's. The selection algorithm for finding median in an unsorted list involves first sorting the list and then pulling out the middle element in the sorted list.
Back tracking
In this approach, we have to reach to the destination from source and while doing that we have ensure that the path we travelled before to reach the destination can also be accessed by other path when the destination path is same in multiple path travelling scenario.
public class AllPaths {
public static void main(String[] args) {
boolean[][] board = {
{true, true, true},
{true, true, true},
{true, true, true}
};
int[][] path = new int[board.length][board[0].length];
allPathPrint("", board, 0, 0, path, 1);
}
static void allPathPrint(String p, boolean[][] maze, int r, int c, int[][] path, int step) {
if (r == maze.length - 1 && c == maze[0].length - 1) {
path[r][c] = step;
for(int[] arr : path) {
System.out.println(Arrays.toString(arr));
}
System.out.println(p);
System.out.println();
return;
}
if (!maze[r][c]) {
return;
}
// i am considering this block in my path
maze[r][c] = false;
path[r][c] = step;
if (r < maze.length - 1) {
allPathPrint(p + 'D', maze, r+1, c, path, step+1);
}
if (c < maze[0].length - 1) {
allPathPrint(p + 'R', maze, r, c+1, path, step+1);
}
if (r > 0) {
allPathPrint(p + 'U', maze, r-1, c, path, step+1);
}
if (c > 0) {
allPathPrint(p + 'L', maze, r, c-1, path, step+1);
}
// this line is where the function will be over
// so before the function gets removed, also remove the changes that were made by that function
maze[r][c] = true;
path[r][c] = 0;
}
}
What we do is, we initially mark the path as false while tracking it and then restoring it as it is or flag it as true so that it won't stuck into infinite recursion loop. Hence, backtracking is used.
Optimization problems
For optimization problems there is a more specific classification of algorithms; and algorithm for such problems may fall into one or more of the general categories described above as well as into one of the following:
Linear programming
When searching for optimal solutions to a linear function bound to linear equality and inequality constraints, the constraints of the problem can be used directly in producing the optimal solutions.
public class LinearSearch{
public static int linearSearch(int[] arr, int key){
for(int i=0;i<arr.length;i++){
if(arr[i] == key){
return i;
}
}
return -1;
}
public static void main(String a[]){
int[] a1= {10,20,30,50,70,90};
int key = 50;
System.out.println(key+" is found at index: "+linearSearch(a1, key));
}
}
Dynamic programming
public int fibo(int n){
dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
The main difference between dynamic programming and divide and conquer is that subproblems are more or less independent in divide and conquer, whereas subproblems overlap in dynamic programming. The difference between dynamic programming and straightforward recursion is in caching or memoization of recursive calls.
The greedy method
A greedy algorithm is similar to a dynamic programming algorithm in that it works by examining substructures, in this case not of the problem but of a given solution. Such algorithms start with some solution, which may be given or have been constructed in some way, and improve it by making small modifications.
The heuristic method
In optimization problems, heuristic algorithms can be used to find a solution close to the optimal solution in cases where finding the optimal solution is impractical. These algorithms work by getting close and closer to the optimal solution as they progress.
In principle, if run for an infinite time amount of time, they will find the optimal solution. The benefit is that they can find a solution very close to the optimal solution in a relatively short time.
That is it folks. Grateful to Google. Special thanks to Geeks For Geeks for amazing explanatory articles and Wikipedia-Algorithms for details diaspora of technical information about algorithms.
Follow me on Twitter, LinkedIn, Github.
Thanks for reading and have a great day.