Comparison sort and Integer sorts

 Posted on August 4, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a “less than or equal to” operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey two of the properties of a total order: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, either a ≤ b or b ≤ a (totalness or trichotomy). [Read More]
kodeknight  sorting  insertion-sort 

Hirschberg’s linear space algorithm in C++

 Posted on August 4, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

It should work on any container type which supports forward and reverse iteration. It’s similar to the Python implementation, but note: rather than copy slices of the original sequences, it passes around iterators and reverse iterators into these sequences rather than recursively accumulating sums of sub-LCS results, it ticks off items in a members array, xs_in_lcs /\* C++ implementation of "A linear space algorithm for computing maximal common subsequences" D. [Read More]
Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring  distance  programCPP  programs 

Hirschberg's algorithm

 Posted on August 4, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Hirschberg’s algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the least cost sequence alignment between two strings, where cost is measured as Levenshtein edit distance, defined to be the sum of the costs of insertions, replacements, deletions, and null actions needed to change one string to the other. Hirschberg’s algorithm is simply described as a divide and conquer version of the Needleman-Wunsch algorithm. The Needleman-Wunsch algorithm finds an optimal alignment in O(nm) time, using O(nm) space. [Read More]
StringAlgo  Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring  distance 

Dynamic Programming Algorithm (DPA) for Edit-Distance

 Posted on August 3, 2010  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

The words `computer’ and `commuter’ are very similar, and a change of just one letter, p->m will change the first word into the second. The word `sport’ can be changed into `sort’ by the deletion of the `p’, or equivalently, `sort’ can be changed into `sport’ by the insertion of `p’. The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of: [Read More]
Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring  distance 

Dynamic Programming Practise Problem Set 3

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Calculate M = M1 × M2 × M3 × M4, where the dimensions of the matrices are M1: 10,20 M2: 20,50 M3: 50,1 M4: 1,100 a) Calculating M = M1 × ( M2 × ( M3 × M4 ) ) b) Calculating M = ( M1 × ( M2 × M3 ) ) × M4 2 Calculate the length of longest sub string in Hello and Aloha 3. Calculate longest sub sequence in houseboat and computer. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

Longest common substring problem

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given two sequences of letters, such as A = HELLO and B = ALOHA, find the longest contiguous sequence appearing in both. **One solution: ** (assume strings have lengths m and n) For each of the m starting points of A, check for the longest common string starting at each of the n starting points of B. The checks could average Θ(m) time → a total of Θ(m^2*n) time. Dynamic programming solution: [Read More]
Algorithms  kodeknight  String  Dynamic Programming  DP 

Dynamic Programming Practise Problem Set 2

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

1. Below is a dynamic programming solution for this problem to illustrate how it can be used. There is a very straightforward O(1) time solution. It can be shown that इफ n >= 50 then any solution will include a set of coins that adds to exactly 50 cents. Hence it can be shown that an optimal solution uses 2 · [n/50 ] quarters along with un optimal solution for making n/50 − bn/50c cents which can be looked up in a table ऑफ़ size 50. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

Matrix chain multiplication

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Given a sequence of n matrices _M_1, _M_2, … M__n, and their dimensions _p_0, _p_1, _p_2, …, p__n, where where i = 1, 2, …, n, matrix M__i has dimension p__i − 1 × p__i, determine the order of multiplication that minimizes the the number of scalar multiplications. We wish to determine the value of the product ∏i = 1 to n Mi, where Mi has ri-1 rows and ri columns. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP  matrix-multiplication  matrix 

Dynamic Programming Practise Problem Set 1

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Suppose we want to make change for n cents, using the least number of coins of denominations 1, 10, and 25 cents. Describe an O(n) dynamic programming algorithm to find an optimal solution. (There is also an easy O(1) algorithm but the idea here is to illustrate dynamic programming.)  Here we look at a problem from computational biology. You can think of a DNAsequence as sequence of the characters “a”,”c”,”g”,”t”. [Read More]
Algorithms  kodeknight  Dynamic Programming  DP 

Prim's Algorithm

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

This algorithm was first propsed by Jarnik, but typically attributed to Prim. It starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed, much like a mould. The algorithm halts when all the vertices in the graph have been reached. To understand the problem statement refer here. This is similar to djikstra’s algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily. [Read More]
Graph  Algorithms  kodeknight  greedy Algo