Introduction A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as Vertices, and the links that connect the vertices are called Edges. It consists of following two components: A finite set of [...]
A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem. Typically, a greedy algorithm is used to solve a problem with [...]
To search an element in a given array, it can be done in two ways Linear search and Binary search. Linear Search Given an array arr[] of n elements, to search for a given element follow below steps :- Start from the leftmost element of arr[] and one by one [...]
Assume, that both arrays are sorted in ascending order and we want resulting array to maintain the same order. Algorithm to merge two arrays A[0..m-1] and B[0..n-1] into an array C[0..m+n-1] is as following: Introduce read-indices i, j to traverse arrays A and B, accordingly. Introduce write-index k to store [...]
Sorting is a process of arranging items in ascending or descending order. This process can be implemented via many different algorithms. Following is the list of sorting algorithms : Bubble Sort Selection Sort Count Sort Insertion Sort Merge Sort Quicksort Heap Sort Time complexity of sorting algorithm [...]
Introduction Dynamic programming (DP) is a very powerful technique to solve a particular class of problems. The idea is very simple, if we have solved a problem with the given input, then save the result for future reference, so as to avoid solving the same problem again. If the given [...]
Minimum Edit distance between two strings str1 and str2 is defined as the minimum number of insert/delete/substitute operations required to transform str1 into str2. For example if str1 = "INTENTION", str2 = "EXECUTION", then the minimum edit distance between str1 and str2 turns out to be 5. Using dynamic programming, [...]
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return [...]
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1. Examples: a) For any [...]
Binary Heap A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types: Min-heap property: Value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root. Min [...]