Algorithm tutorial

Sleep Sort

Sleep Sort is time-based sorting technique. We create different threads for each individual element present in the array. The thread is then made to sleep for an amount of time that is equal to value of the element for which it was created. Time complexity is O(NlogN + max(input))

algorithm

Distance between two points in 2D space

Distance between two points is calculated by creating a right-angled triangle using the two points.The line between the two points is the hypotenuse (the longest side, opposite to the 90° angle). We used the Distance formula derived from Pythagorean theorem with a time complexity of O((log N)^2)

algorithm

Area of Polygon: Shoelace formula

Given coordinates of vertices of polygon, Area of Polygon is calculated using Shoelace formula described by Mathematician and Physicist Carl Friedrich Gauss where polygon vertices are described by their Cartesian coordinates in the Cartesian plane. The time complexity is O(N) with O(1) space

algorithm

Extended Euclidean Algorithm

We will demonstrate Extended Euclidean Algorithm. We will see how you can calculate the greatest common divisor in a naive way which takes O(N) time complexity which we can improve to O(log N) time complexity using Euclid's algorithm. Extended Euclidean Algorithm takes O(log N) time complexity

algorithm

Multiple array range increments in linear time O(N)

Given an array a containing N integers, we perform M queries. Each query has three values START, END and a value D. For each query, the problem is to increment the values from the start to end index(both inclusive) in the given array by the given value d. An efficient algorithm takes O(N+M) time

algorithm

Sieve of Atkin

Sieve of Atkin is an algorithm used to find all prime numbers upto a given number (say N) and does so in O(N) time complexity. With a modified version with enumerating lattice points variation, the time complexity goes to O(N / log log N). It is computationally efficient than Sieve of Eratosthenes

algorithm

Area of Triangle: Heron's formula

We take a look at Heron's formula which will enable us to calculate the area of any triangle given the length of the three sides of that triangle. The advantage is that the area is calculated using arithmetic operations and hence, the time taken can be assumed to be constant,

algorithm

Circle Sort

Circle sort is a sorting algorithm in which diametrically opposite elements are compared to each other and swapped with an average time complexity of O(N log N) and space complexity of O(1). It is an unstable, recursive, parallelizable, in place sorting algorithm

algorithm

Conversion of Infix to Postfix Expression using Stack

To convert Infix expression to Postfix expression, we will use the stack data structure. By scanning the infix expression from left to right,if we get any operand, simply add it to the postfix form, and for the operator and parenthesis, add them in the stack maintaining the precedence of them.

algorithm

Binary Lifting with k-th ancestor and lowest common ancestor (LCA)

Binary Lifting is a technique used to find the k-th ancestor of any node in a tree in O(log N). This also leads to a faster algorithm in finding the lowest common ancestor (LCA) between two nodes in a tree. The technique requires preprocessing the tree in O(N log N) using dynamic programming.

algorithm

Bipartite checking using Graph Colouring and Breadth First Search (BFS)

The algorithm to determine whether a graph is bipartite or not uses the concept of graph colouring and BFS and finds it in O(V+E) time complexity on using an adjacency list and O(V^2) on using adjacency matrix. It is used to decode codewords and model situations in cloud computing and big data

algorithm

Topological Sorting using Depth First Search (DFS)

We will implement Topological sorting using Depth First Search in linear time O(V+E). Topological Sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. It is useful in instruction scheduling and other

algorithm

String hashing

Hashing is an important technique which converts any object into an integer of a given range. Hashing is the key idea behind Hash Maps which provides searching in any dataset in O(1) time complexity. An efficient algorithm to hash a string is used to compare strings in O(1) time complexity

algorithm

Fermat's little theorem, a Probabilistic test for Primality

One of the most popular probabilistic algorithm for determining if a number is prime or not is based on Fermat's little theorem. The complexity of the algorithm is O(K log N) and fails only for Carmichael numbers which are composite numbers satisfying fermat little theorem starting with 561

algorithm

Expectation Maximization Clustering Algorithm

Expectation Maximization Clustering algorithm is much more robust than K-Means, as it uses two parameters, Mean and Standard Deviation to define a particular cluster. This simple addition of calculating the Standard Deviation, helps the EM algorithm do well in a lot of fail cases of K-Means

algorithm

Mean Shift Clustering Algorithm

Mean Shift clustering is an unsupervised clustering algorithm that groups data directly without being trained on labelled data. It is hierarchical in nature. It starts off with a kernel, which is basically a circular sliding window. The bandwidth the radius of this sliding window is pre-decided

algorithm

Cartesian tree sorting

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence

algorithm

Activity Selection Problem using Greedy algorithm

For activity selection, Dynamic Programming Approach takes O(n^3) time while Greedy Approach takes O(n) time when unsorted and O(n log n) when sorted. It follows Greedy approach as at every step, we make a choice that looks best at the moment to get the optimal solution of the complete problem

algorithm

Tarjan's Algorithm to find Strongly Connected Components

Tarjan's Algorithm is an efficient graph algorithm to find the strongly connected components in a directed graph in linear time by utilizing Depth First Search traversal of a graph. The key idea used is that nodes of strongly connected component form a subtree in the DFS spanning tree of the graph.

algorithm

Cycle Sort

Cycle sort is a comparison based sorting algorithm which forces array to be factored into the number of cycles where each of them can be rotated to produce a sorted array with O(N^2) time complexity It is an in-place and unstable sorting algorithm and is optimal in terms of number of memory writes

algorithm

Fibonacci Search

Fibonacci search is an efficient search algorithm based on divide and conquer principle using Fibonacci series that can find an element in the given sorted in O(log N) time complexity. It is better than Binary search as it is more cache friendly and uses only addition and subtraction operations.

algorithm

Bresenham Line Drawing Algorithm

Bresenham line drawing Algorithm is a Line Drawing Algorithm which calculates all intermediate points over the interval between start and end points, implemented with integer numbers and integer arithmetic such as addition, subtraction and avoids heavy operations like multiplication and division

dynamic programming

Longest Palindromic Subsequence: Reducing complexity from O(2^N) to O(N^2)

The longest palindrome subsequence problem (LPS) is the problem to find longest subsequences of a string that is also a palindrome. We will see two solutions one which is a naive solution and the other is a dynamic programming approach where we will reduce the time complexity from O(2^N) to O(N^2)

sorting algorithm

Comb Sort

Comb sort is a comparison based sorting algorithm and is an improvement to Bubble Sort by using the idea of killing the turtles. In Bubble Sort algorithm, the gap between the elements that are compared is always 1. Comb sort works on the same principles as Bubble Sort but uses a larger gap.

dynamic programming

Longest Bitonic Sequence

The problem we will solve is given a sequence an array of positive integers and have to find the length of longest bitonic subsequence. Using dynamic programming ideas, we will solve this on O(N^2) time complexity