Longest increasing subsequence

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  11 minutes  |  Kinshuk Chandra

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution. Problem Input : Sequence of integers (or any comparable items) Output : Longest increasing subsequence of the sequence, which may not be contiguous. For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5. Note that the numbers are non-contiguous. [Read More]
kodeknight  Dynamic Programming  DP  Amazon  incomplete  Interview Question  google 

To find the longest substring with unique characters in a given string

 Posted on September 22, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

#include <stdio.h> #include <string.h> typedef struct { const char \*start; size\_t len; }Substring; Substring longestSubstring(const char \*s){ Substring ret = {s, 1}; Substring cur = {s, 1}; size\_t i, len = strlen(s); const char \*p = NULL; for(i = 1; i < len; ++i){ p = memchr(cur.start, sii, cur.len); if(p){ if(cur.len > ret.len) ret = cur; cur.len -= (p - cur.start) + 1; cur.start = p + 1; } cur.len++; } if(cur. [Read More]
kodeknight  String  Dynamic Programming  DP  unique  LCS 

Find longest palindrome in a string.

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

I cannot think of any that has a complexity less than O(n*n). one of the ways would be : 1. Take the string (s1) and its direct reversal (s2) 2. Slide s2 over s1 per character and count the number of similar characters starting from s2′s last character Hence, first: ———————— ABCDAMNMADGHJ JHGDAMNMADCBA Count =1 Then, ————————ABCDAMNMADGHJ –JHGDAMNMADCBA Count=0 . . . ————————ABCDAMNMADGHJ ————————JHGDAMNMADCBA Count=7 . . . ————————ABCDAMNMADGHJ Count= 0 We can exit at this point [Read More]
kodeknight  Dynamic Programming  DP  palindrome 

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 

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