Algorithm tutorial

Volker Strassen, the man who changed Matrix Multiplication

Volker Strassen is a Computer Scientist and Mathematician who is best known as the person who broke the strongly held belief that Matrix Multiplication cannot be done faster than O(N^3) time.

algorithm

Minimum deletions to make frequency of each character unique

The problem we will solve is that given a string s, we need to find the minimum number of characters to be deleted from s so that the frequency of each character in the string is unique.

algorithm

Find if a string is a sub-string of another string

We have presented two approaches to check whether a string is a substring of another string namely naive method which takes O(N^2) time and efficient method using the concept of Rolling Hash which takes linear time O(N).

software engineering

Round Robin Scheduling Algorithm

The key idea of Round Robin Scheduling algorithm is to allocate CPU to all processes in the same order for the same amount of time in turns. It provides real time computing experience.

algorithm

Iterative and Recursive Binary Search Algorithm

The major difference between the iterative and recursive version of Binary Search is that the recursive version has a space complexity of O(log N) while the iterative version has a space complexity of O(1)

algorithm

Rolling Hash

Rolling hash is an algorithmic technique which is used to prevent rehashing the whole string while calculating hash values of the substrings of a given string

software engineering

Approaches for implementing Autocomplete Feature

The various approaches for Text Auto-completion are Linear Search (Brute Force), Binary Search Approach, TRIE Data Structure, Ternary Search Tree Approach, Fuzzy Search, Burkhard Keller Tree Approach and Machine Learning Approach.

software engineering

Shortest Job First CPU Scheduling algorithm

Shortest Job First (SJF) CPU scheduling algorithm is a CPU scheduling algorithm which is based on the principles of Greedy Algorithms. The key idea is to allocate the CPU to the process with the smallest burst time.

algorithm

Find the number of subsets of an array having a given XOR value

We are given an array of size N and a value M, we have to find the number of subsets in the array having M as the xor value of all elements in the subset. This can be solved using Dynamic Programming in linear time.

algorithm

Longest repeating and non overlapping substring in a string

We have to find the longest repeating and non-overlapping substring in a given string. Brute force approach takes O(N^3) time while Dynamic Programming takes O(N^2) time.

algorithm

Minimum number of Fibonacci terms with sum equal to a given number N

Given a number N, we need to find the minimum number of fibonacci numbers required that sums up to a given number N. Note a fibonacci number can be repeated

algorithm

Binary exponentiation (Power in log N)

Binary exponentiation is an algorithm to find the power of any number N raise to an number M (N^M) in logarithmic time O(log M). The normal approach takes O(M) time provided multiplication takes constant time.

algorithm

Number of pairs with a given sum

We will find out how we can count the number of pairs in an array whose sum is equal to a certain number. Brute force approaches will take O(N^2) time but we can solve this in O(N) time using a Hash Map.

algorithm

Shortest Path with k edges using Dynamic Programming

Given a weighted directed graph, we need to find the shortest path from source u to the destination v having exactly k edges. Brute force approach takes O(V^k) time complexity which we reduce to O(V^3 * k) using dynamic programming

algorithm

Number of paths with k edges using Dynamic programming and Divide and Conquer

Given a directed graph, we need to find the number of paths with exactly k edges from source u to the destination v. A brute force approach has time complexity which we improve to O(V^3 * k) using dynamic programming which we improved further to O(V^3 * log k) using a divide and conquer technique.

algorithm

Must read research papers on Algorithms

We presented some of the must read research papers in the field of Algorithms. The papers come from authors like C. A. R. Hoare, D. E. Knuth, V. Strassen and many others.

data structure

Autocomplete Feature using Ternary Search Tree

Autocomplete Feature can be implemented using Ternary Search Tree as well which is a memory optimized version of trie and performs equally well.

machine learning

PageRank

PageRank is an algorithm to assign weights to nodes on a graph based on the graph structure and is largely used in Google Search Engine being developed by Larry Page

algorithm

Bozosort

Bozosort is a random sorting algorithms where the key idea is to swap any two elements of the list randomly and check if the list is sorted. The average time complexity of Bozosort is O(N!) and the space complexity is O(1).

algorithm

Number of ways to pair elements

In this article, we are going to discuss about element pairing problem where we need to find the number of ways a set of elements can be pair or kept separate. This can be solved using Dynamic Programming in linear time O(N).

algorithm

Finding number of pairs with a certain XOR value

In this article, we are going to find the number of pairs in an unsorted array, whose XOR values matches with our target value (say K). Using our efficient approach (with Hash map), we can solve this in O(N) time complexity while the brute force approach takes O(N^2) time complexity

algorithm

Check if a number is an Armstrong Number

An Armstrong number is an integer such that the sum of the digits raised to the power of the number of digits is equal to the number itself. We verify it in O(logN * loglogN) time.

algorithm

Number of ways to represent a number N as sum of K Fibonacci terms

The problem we will solve is that given a number N and K, we need to find the numbers of ways we can represent N as a sum of K fibonacci numbers. We will solve this problem efficiently using a recursive technique in O(N).

algorithm

Autocomplete feature using TRIE Data Structure

Autocomplete is a feature of suggesting possible extensions to a partially written text and is widely used in search engine, code IDEs and much more. Trie data structure is a perfect fit to implement this feature efficient in terms of memory and time [O(length of string)].

software engineering

Different ways to add 1 to a number

We compared 8 different techniques to increment a number by 1 by generating the assembly code. It depends on the compiler and language as well.