DAA Homework 2 Section C

problem_1.cpp

#include <bits/stdc++.h>
using namespace std;
/**
 *  Reference Links
 *  https://www.geeksforgeeks.org/tiling-problem/
 **/
long long int MattingTheFloor(int n,long long int dp[]){
    if(dp[n] > -1){
        return dp[n];
    }
    if(n == 1 || n == 2){
        dp[n] = n;
        return dp[n];
    }
    dp[n] = MattingTheFloor(n-1,dp) + MattingTheFloor(n-2,dp); 
    return dp[n];
}

int main()
{
    int k;
    cout<<"Enter the k value"<<endl;
    cin>>k;
    long long int dp[k+1];
    for(int i=0;i<k+1;i++){
        dp[i] = -1;
    }
    long long int ways = MattingTheFloor(k,dp);
    cout<<"Total ways of matting the floor of 2 x "<<k<<" is "<<ways<<endl;
    return 0;
}

problem_2.cpp

#include <bits/stdc++.h>
using namespace std;
class lex
{
    set<string> base;

public:
    lex();
    lex(string filepath)
    {
        string line;
        ifstream IFStream;
        IFStream.open(filepath);
        if (IFStream.is_open())
        {
            while (IFStream >> line)
            {
                base.insert(line);
            }
            IFStream.close();
        }
        else
        {
            throw string("Unable to open " + filepath);
        }
    }
    bool isword(string word)
    {
        return (base.count(word) > 0);
    }
};

int main()
{    
    lex *l;
    try
    {
        l = new lex("lex.txt");
    }
    catch(string e)
    {
        cerr << e << '\n';
        return 1;
    }

    string search_str = "please";
    cout<<"Input string is: "<<search_str<<endl;
    
    // set of valid words in the string according to vocabulary
    set<string> words;
    
    // set of string for memorizing the substrings we have checked already.
    set<string> memo;

    // pairs of indexes which has distinct sub strings
    set<pair<int,int>> optimal_indexes;

    for(int i=0;i<search_str.size();i++){
        for(int j=0; j<search_str.size();j++){
            string substr = search_str.substr(i,j);
            if(memo.count(substr) == 0){
                optimal_indexes.insert(make_pair(i+1,j+1));
                if (l->isword(substr))
                {
                    if(words.count(substr) == 0){
                        cout<<substr<<endl;
                        words.insert(substr);
                    }
                }
                memo.insert(substr);
            }
        }
    }

    cout<<"Printing distinct substring indexes."<<endl;
    for(auto it = optimal_indexes.begin(); it != optimal_indexes.end();it++){
        cout<<"("<<it->first<<","<<it->second<<") ";
    }
    cout<<endl;
    
    cout<<"Printing Valid words based on vocabulary."<<endl;
    for(auto it = words.begin(); it != words.end();it++){
        cout<<*it<<" ";
    }
    cout<<endl;
    return 0;
}

problem_3.cpp

#include <bits/stdc++.h>
using namespace std;
/**
 
 Important Reference Links

 http://www.cplusplus.com/reference/vector/vector/
 http://www.cplusplus.com/reference/sstream/stringstream/
 http://www.cplusplus.com/reference/string/string/

 **/
int LookupChain(int **m, int **s, vector<int> p, int i, int j)
{
    // See the explanation in CORMEN book
    // Chapter 15 Dynamic Programming, Page # 388
    if (m[i][j] < INT_MAX)
    {
        return m[i][j];
    }
    if (i == j)
    {
        m[i][j] = 0;
    }
    else
    {
        for (int k = i; k <= j - 1; k++)
        {
            int q = LookupChain(m, s, p, i, k) +
                    LookupChain(m, s, p, k + 1, j) +
                    p[i - 1] * p[k] * p[j];
            if (q < m[i][j])
            {
                m[i][j] = q;
                s[i][j] = k;
            }
        }
    }
    return m[i][j];
}

void PrintOptimalPrens(int **s, int i, int j)
{
    if (i == j)
    {
        cout << "A" << i;
    }
    else
    {
        cout << "( ";
        PrintOptimalPrens(s, i, s[i][j]);
        cout << " * ";
        PrintOptimalPrens(s, s[i][j] + 1, j);
        cout << " )";
    }
}

int MemoizedMatrixChain(vector<int> p, int size)
{
    // See the explanation in CORMEN book
    // Chapter 15 Dynamic Programming, Page # 388
    int n = size;
    int **m = new int *[n];
    int **s = new int *[n];
    for (int i = 0; i < n; i++)
    {
        m[i] = new int[n];
        s[i] = new int[n];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            m[i][j] = INT_MAX;
            s[i][j] = 0;
        }
    }
    int r = LookupChain(m, s, p, 1, n - 1);
    // Main Algorithm ends here with a return statement, although we also want to print the m table before returning
    // So store the result in a variable and return once you are done with printing

    // Additional work, not a part of algorithm
    cout << "Output of m table:" << endl;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (j < i)
            {
                cout << "-\t";
            }
            else if (j + 1 == n)
            {
                cout << m[i][j] << endl;
            }
            else
            {
                cout << m[i][j] << "\t";
            }
        }
    }
    cout << endl;
    cout << endl
         << "Output of s table" << endl;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (j < i)
            {
                cout << "-\t";
            }
            else if (j + 1 == n)
            {
                cout << s[i][j] << endl;
            }
            else
            {
                cout << s[i][j] << "\t";
            }
        }
    }
    cout<<"Optimal Parenthesization Order is :";
    PrintOptimalPrens(s,1,n-1);
    return r;
}

int main()
{
    // for storing unique dimensions of metrices
    vector<int> vec_d;
    // no of unique dimensions
    int n;
    // variable for reading line from a file
    string line;
    // variable for storing original array dimensions string
    string dimensions;
    /**
     ==== NOTE ==== 
     FORMAT OF FILE IS MANDATORY
     Very first line must be the no of unique dimensions from all metrices followed by line seperator
     Valid formats : 5 or 6 or 10 or any whole number
     Invalid formats : 5.6 or 5/2 or 5- or number with any special character
     Second line must be the dimensions of metrices followed by comma
     Valid formats : 2x10,10x7,7x18,18x1,1x6 OR 2x10 , 10x7 , 7x18 , 18x1 , 1x6 OR 2x10 , 10x7 , 7x18 , 18 x 1, 1 x 6
    **/
    string fileName = "a2p3input.txt";
    ifstream IFStream;
    IFStream.open(fileName);
    if (IFStream.is_open())
    {
        int lno = 0;
        while (getline(IFStream, line))
        {
            if (lno == 0)
            {
                // very first line which is the no of unique dimensions
                n = stoi(line);
            }
            else
            {
                // second line which is the dimensions of array
                // Optional: store original string of dimensions
                dimensions = line;
                // Required: remove any whitespace character
                line.erase(remove(line.begin(), line.end(), ' '), line.end());
                // iterate through every character and replace x with ,
                for (int i = 0; i < line.length(); i++)
                {
                    if (line[i] == 'x')
                    {
                        line[i] = ',';
                    }
                }
                // treat line as a stringstream see
                //for more details see http://www.cplusplus.com/reference/sstream/stringstream/
                stringstream stos(line);
                for (int i; stos >> i;)
                {
                    // check if the current number is already in our dimensions vector
                    if (find(vec_d.begin(), vec_d.end(), i) == vec_d.end())
                    {
                        // if no then push it to the vector.
                        vec_d.push_back(i);
                    }
                    // check if the next character is comma then skip the iteration
                    if (stos.peek() == ',')
                        stos.ignore();
                }
            }
            // increment the pointer so that we can check if we are on line 2
            lno++;
        }
        // Required or Recommended: always close the file once you are done.
        IFStream.close();

        cout << "Size of n is " << n << endl
             << endl;
        cout << "Size of matrices are: " << dimensions << endl
             << endl;
        cout << "Unique dimensions are : ";
        for (std::size_t i = 0; i < vec_d.size(); i++)
            std::cout << vec_d[i] << " ";
        cout << endl
             << endl;

        int result = MemoizedMatrixChain(vec_d, n);

        cout << endl
             << "Minimum multiplication : " << result << endl;
    }
    else
    {
        throw string("Unable to open " + fileName);
    }
    return 0;
}