Algorithm tutorial

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

sorting algorithm

Heap Sort

Heapsort is an efficient in-place comparison based sorting algorithm with O(N log N) time complexity and uses a data structure to achieve it. It uses a complete Binary Heap data structure to sort the elements depending on whether the heap is Min Heap (ascending) or Max heap (descending).

sorting algorithm

Radix Sort

Radix Sort is an efficient non-comparison based sorting algorithm which can sort a dataset in linear O(N) time complexity and hence, can be better than Quick Sort. It uses Counting Sort as a subroutine. It uses the fact that number of digits in an Integer is very less compared to the data

sorting algorithm

Counting Sort

Counting sort is an algorithm for sorting integers in linear time. It can perform better than other efficient algorithms like Quick Sort, if the range of the input data is very small compared to the number of input data. It is a stable, non-comparison and non-recursive based sorting

algorithm

DDA (Digital Differential Analyzer) Line Drawing Algorithm

Digital differential analyzer is a line drawing algorithm that is based on incremental method which calculates all intermediate points over the interval between start and end points. It uses the concept that rate of change in a straight line in constant and is a linear time complexity O(N) algorithm

sorting algorithm

Bucket Sort Algorithm

Bucket sort is a comparison sort algorithm that works by distributing the elements of an array into a number of buckets and then each bucket is sorted individually using a separate sorting algorithm. It is useful when the input is uniformly distributed over a range in linear time complexity

algorithm

Bresenham’s Circle Drawing Algorithm

Bresenham’s Circle Drawing Algorithm is a circle drawing algorithm that selects the nearest pixel position to complete the arc. The unique part of this algorithm is that is does only integer arithmetic which makes it faster than other algorithms using floating point arithmetic

algorithm

Cohen Sutherland Line Clipping Algorithm

Cohen Sutherland Algorithm is a linear time complexity line clipping algorithm that cuts lines to portions which are within a rectangular area. It eliminates the lines from a given set of lines which belongs outside the area of interest and clip those lines which are partially inside

algorithm

Number of arithmetic progression subsequences in a given set of numbers

The problem is that given an array of n positive integers. The task is to count the number of Arithmetic Progression subsequence in the array. This can be solved using dynamic programming in linear time complexity.

algorithm

Find the Longest Arithmetic Progression using Dynamic Programming

The problem we will solve is that given a set of integers in sorted order, find length of longest arithmetic progression in that set. This can be solved by brute force in O(N^3) while a dynamic programming approach with take O(N^2) time complexity.

algorithm

Aho Corasick Algorithm

Aho Corasick algorithm is a string algorithm to find or search occurrences of k number of Patterns: P1 ,P2 .... Pk in a string text T. It is a modification over the KMP algorithm

algorithm

Minimum operations to make GCD of array a multiple of k

We are given an array and k, we need to find the minimum operations needed to make GCD of the array equal or multiple of k. Here an operation means either increment or decrement an array element by 1.

similarity measurement

Damerau Levenshtein distance

Damerau Levenshtein distance is a variant of Levenshtein distance which is a type of Edit distance. Damerau stated that the four operations in Damerau Levenshtein distance correspond to more than 80% of all human misspellings. It adds an extra operation named transposition to its set of operations

similarity measurement

Levenshtein distance

evenshtein distance is a type of Edit distance which is a large class of distance metric of measuring the dissimilarity between two strings by computing a minimum number of operations (from a set of operations) used to convert one string to another string. It is a way of pairwise string alignment.

similarity measurement

Chebyshev distance

Chebyshev distance is a distance metric which is the maximum absolute distance in one dimension of two N dimensional points. It has real world applications in Chess, Warehouse logistics and many other fields. It is known as Tchebychev distance, maximum metric, chessboard distance and L∞ metric.

similarity measurement

Euclidean distance (L2 norm)

Euclidean distance is the shortest distance between two points in an N dimensional space also known as Euclidean space. It is used as a common metric to measure the similarity between two data points and used in various fields such as geometry, data mining, deep learning and others.

similarity measurement

Manhattan distance (L1 norm)

Manhattan distance (L1 norm) is a distance metric between two points in a N dimensional vector space. It is the sum of the lengths of the projections of the line segment between the points onto the coordinate axes. It was introduced by Hermann Minkowski. It is used in regression analysis

string algorithm

Manacher's Algorithm

Manacher's Algorithm is an efficient algorithm to find the longest palindromic substring in a given string in linear time and linear space complexity. It uses key ideas from dynamic programming to solve the problem efficiently.

genetic algorithm

Basics of Genetic Algorithms

A genetic algorithm is a search heuristic (related to making guesses) algorithm that is inspired by Charles Darwin’s theory of natural evolution. We have explained the basic concepts of genetic algorithms including initial population, fitness function, selection, crossover and mutation.

bitwise operation

Algorithm to detect whether two numbers have opposite signs using bitwise operators

We present a bitwise algorithm to detect whether two numbers have opposite signs. This is important as using comparision based operations is slow and nearly all hardware support optimizations for bitwise operations

algorithm

Maximize sum of consecutive differences in a circular array

Given an array A with values a1, a2, a3, a4, an Now, arrange all elements of array A such that sum of absolute differences of consecutive elements is maximum, i.e consider after an arrangement the array is b1, b2, b3, b4,..., bn then maximize |b1-b2| + |b2-b3| + |b3-b4| + .. + |bn-1-bn| + |bn-b1|

bitwise operation

Bitwise Algorithm to Find the Number Occurring with Odd Frequency

We have explored the bitwise algorithm to find the only number occuring odd number of times in a given set of numbers. We have used the XOR operator to solve this problem in O(N) time complexity in contrast to the native algorithm which takes O(N^2) time complexity. The space complexity is constant.