Algorithm

Learn different algorithms with detailed explanations and diagrams.

Levenshtein Distance

Introduction Levenshtein distance between two strings is defined as the minimum number of single-digit edit operations ( Insertion, Deletion, Substitution ) required to convert one string to another. Single Digit Operations Insertion : “Sprk” -> “Spark” Deletion : “Hello” -> “Hllo” Replace : “Carry” -> “Larry” For example, Example 1 s1 = “gone” s2 = …

Levenshtein Distance Read More »

CYK Algorithm

Cocke Younger Kasami ( CYK ) algorithm is a parsing algorithm for context-free grammar. CYK algorithm only operates on context-free grammar which is in CNF ( Chomsky Normal Form ). We must convert the context-free grammar to CNF before applying CYK algorithm. CYK algorithm is a bottom-up parsing approach. It is based on the dynamic …

CYK Algorithm Read More »

Bozo-Sort

Bozo-Sort is a variation of Bogosort. It is another highly inefficient randomized algorithm based on the trial and error approach. Bozo-sort sorts the input list by repeatedly swapping 2 random elements of the list and checking if the list is sorted or not. The process is repeated till the input list is sorted. Implementation In …

Bozo-Sort Read More »

Bogosort

Bogosort is just another sorting algorithm. Bogosort is highly inefficient compared to other sorting algorithms. It is a randomized algorithm and is based on the trial and error paradigm. Bogosort basically generates random permutations of the input list and check if the list is sorted or not. This process is continued until the input list …

Bogosort Read More »

Gale Shapley algorithm

Gale Shapley algorithm is used to solve the stable matching problem. It is also known as the Deferred Acceptance algorithm. Stable Matching Problem Stable Matching Problem (also known as Stable Marriage Problem) is the problem to find stable matching between two equally sized sets. The matching is based on the given order of preferences. A …

Gale Shapley algorithm Read More »

C++ Program to Implement Insertion Sort using Templates

In this post, we will discuss how to implement insertion sort using templates. Insertion sort is an in-place sorting algorithm. The array is divided into two-part. One sorted and other unsorted. The elements from unsorted parts are inserted into the sorted part one by one. The advantage of implementing insertion sort using function templates is …

C++ Program to Implement Insertion Sort using Templates Read More »

C++ Program of Binary Search Using Templates

In this post, we will discuss binary search algorithm implementation using function templates in C++. If you don’t know how binary search works, then read Binary Search Algorithm. Program of Binary Search Using Templates Output Program of Binary Search Using Templates (recursive) Output ReadFind all subsets of an arrayProgram to count prime numbers in given …

C++ Program of Binary Search Using Templates Read More »

C++ Program to Implement Bubble Sort using Templates

In this code, we will discuss program to implement bubble sort using templates in C++. The code is self explanatory. The template function sorts the array in ascending order. The advantage of using template is we don’t have to write different function for different datatypes. Program Output ReadSquare Root Using Binary SearchPrint Diamond Pattern (recursive …

C++ Program to Implement Bubble Sort using Templates Read More »