Kushagra's blog

Problem Statement: Given a sorted array key [0.. n-1] of search keys and an array freq[0….n-1] of frequency counts, where freq[i] is the number of searches for keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

This problem can be solved by applying Dynamic Programming.

#include <bits/stdc++.h>
using namespace std;
int sum(int freq[], int i, int j);
int optimalSearchTree(int keys[], int freq[], int n)
{

    int cost[n][n];  
    for (int i = 0; i < n; i++)
        cost[i][i] = freq[i];
    for (int L = 2; L <= n; L++)
    {
        for (int i = 0; i <= n-L+1; i++)
        {
            int j = i+L-1;
            cost[i][j] = INT_MAX;
            for (int r = i; r <= j; r++)
            {
            int c = ((r > i)? cost[i][r-1]:0) +
                    ((r < j)? cost[r+1][j]:0) +
                    sum(freq, i, j);
            if (c < cost[i][j])
                cost[i][j] = c;
            }
        }
    }
    return cost[0][n-1];
}

int sum(int freq[], int i, int j)
{
    int s = 0;
    for (int k = i; k <= j; k++)
    s += freq[k];
    return s;
}
 

int main()
{
    int keys[] = {10, 12, 20};
    int freq[] = {34, 8, 50};
    int n = sizeof(keys)/sizeof(keys[0]);
    cout << "Cost of Optimal BST is " << optimalSearchTree(keys, freq, n);
    return 0;
}

Optimization of this program:-

Time Complexity:- O(n^4)

Output of this Program should be:- 142

Problem Statement : Given a text and a wildcard pattern, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text).
The wildcard pattern can include the characters ‘?’ and ‘*’ 
‘?’ – matches any single character 
‘*’ – Matches any sequence of characters (including the empty sequence)

We could solve this problem by applying dynamic programming.

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
bool strmatch(char str[], char pattern[],int m, int n)
{
    if(m==0){return (n==0);}
    bool lookup[n+1][m+1];
    memset(lookup,false,sizeof(lookup));
    lookup[0][0]=true;
    for(int j=1;j<=m;j++)
    {
        if(pattern[j-1]=='*')
        {
            lookup[0][j]=lookup[0][j-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(pattern[j-1]=='*')
            {
                lookup[i][j]=lookup[i][j-1]||lookup[i-1][j];
            }
            else if(pattern[j-1]=='?'||str[i-1]==pattern[j-1])
            {
                lookup[i][j]=lookup[i-1][j-1];
            }
            else
            {
                lookup[i][j];
            }
        }
    }
    return lookup[n][m];
}
int main()
{
    char str[] = "baaabab";
    char pattern[] = "*****ba*****ab";
    if(strmatch(str,pattern,strlen(str),strlen(pattern)))
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}

The following code optimization is as follows:

Time Complexity: O(m x n)

Auxiliary space: O(m x n)

Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. 

We would solve this problem by using recursion as it is easier to understand but the downside is that it is not optimal.

#include <iostream>
using namespace std;
 
int max(int a, int b);
int lcs( char *X, char *Y, int m, int n )
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m-1] == Y[n-1])
        return 1 + lcs(X, Y, m-1, n-1);
    else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
int max(int a, int b)
{
    return (a > b)? a : b;
}

int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);
    cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ;
    return 0;
}
 

Time complexity of the above recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0. 

Another approach to the same problem is by using Tabulation Method.

#include<iostream>
using namespace std;
 
int max(int a, int b);
 

int lcs( char *X, char *Y, int m, int n )
{
    int L[m + 1][n + 1];
    int i, j;
    for (i = 0; i <= m; i++)
    {
        for (j = 0; j <= n; j++)
        {
        if (i == 0 || j == 0)
            L[i][j] = 0;
     
        else if (X[i - 1] == Y[j - 1])
            L[i][j] = L[i - 1][j - 1] + 1;
     
        else
            L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }
     
    return L[m][n];
}
int max(int a, int b)
{
    return (a > b)? a : b;
}
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
     
    int m = strlen(X);
    int n = strlen(Y);
     
    cout << "Length of LCS is "
        << lcs( X, Y, m, n );
     
    return 0;
}

Time Complexity of the above implementation is O(mn) which is much better than the worst-case time complexity of Recursive implementation.