Find increasing 3-tuple (sub-sequence)

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem: You given an array: 3, 2, 1, 6, 5, 4, 9, 8, 7 you have to find a 3 tuple which has property a < b < c, also a is before b, b is before c in array. Answer can have multiple tuples, you have to find any one. In this array, answer will be 3, 6, 9 Solution: Simple. Time complexity = O(n ^ 2) Create an array of indexes, and sort the original array keeping track of the indexes in the second array. [Read More]
maxima  kodeknight  subsequence  minima  incomplete  array  increasing-sequence 

Reducing the space for LCS lengths

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

When you’ve run out of main memory, any estimate of runtime based on big-O analysis becomes useless. The system either crashes or thrashes, paging in virtual memory. By contrast, if we can reduce the memory required by a program, the time analysis should still hold — we never have to page in more time. Once you’ve watched the dynamic programming solution a few times, you’ll realise that the LCS lengths (the numbers in the grid) are computed row by row, with each row only depending on the row above. [Read More]
Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring 

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 

Longest common subsequence : Dynamic programming

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

m: A B C B D A B yn: B D C A B A The LCS is B C B A For arbitrary inputs, it is NP-hard. For constant inputs, DP gives the solution in polynomial time ex: O(n^k). Also, there can be more than one LCSs and the solution for that is exponential time ex: O(k^n). Here we maintain an LCS matrix of m*n size. Initially, for i= 0 or j = 0, LCSij = 0. [Read More]
Algorithms  kodeknight  String  subsequence  Dynamic Programming  DP  substring