DEV Community: eduAlgo

Undoing changes - Git Reset & Git Revert

kulsoomzahra — Mon, 26 Apr 2021 11:41:16 +0000

When you're working on a large opensource project, it is quite obvious for developers to create branches, add files and stage them for commits when they are ready etc.

However, in some cases, you might realize that the changes that you made are not that good or the feature you just added isn't up to the mark.
You modified some files, added and deleted a lot of lines from the code base, but NOW you want to go back and revert the changes.

Don't worry much because, Git has got your back!

Git Revert

The preferred method of undoing shared history is git revert.
A revert is safer than a reset because it will not remove any commits from a shared history. A revert will retain the commits you want to undo and create a new commit that inverts the undesired commit. This method is safer for shared remote collaboration because a remote developer can then pull the branch and receive the new revert commit which undoes the undesired commit.

You should never reset a commit which is pushed to a public repo, as it can cause serious problems for other developers of the project.

Instead use git revert

git log
#This will show the previous commits and their hashes. Copy 6 char hash of initial commit.

git revert <hash of initial commit>

You can check by running

git status 
git log

Git Reset

It is a versatile tool for developers to use.
git reset is used for undoing changes on a private branch/locally. It has three modes depending upon where you want to reflect changes in Git's internal state management mechanism's. Git has three such state managements: The Commit Tree (HEAD), The Staging Index, and The Working Directory.

--soft

This is the safest reset mode.
--soft resets the head to , just like all modes do.
It does not touch the index file or the working tree at all and leaves all your changed files as "Changes to be committed", as git status would put it.
The Staging Index and the Working Directory are left untouched so changes are not lost in either places. Only Commit Tree is altered.

git log
#This will show the previous commits and their hashes. Copy 6 char hash of initial commit.

git reset --soft <hash of initial commit>

You can check by running

git status 
git log

--mixed

This is the default operating mode.
--mixed has the following impacts:

The ref pointers are updated.
The Staging Index is reset to the state of the specified commit. Any changes that have been undone from the Staging Index are moved to the Working Directory(you can recover by git add file-1)

git log
#This will show the previous commits and their hashes. Copy 6 char hash of initial commit.

git reset <hash of initial commit>

You can check by running

git status 
git log

--hard

This is the most DANGEROUS option. Use only when you're sure that you want to delete your work.
--hard has the following impacts

The Commit History ref pointers are updated to the specified commit.
The Staging Index and Working Directory are reset to match that of the specified commit. Any changes made are lost and matches to the state of the specified commit

git log
#This will show the previous commits and their hashes. Copy 6 char hash of initial commit.

git reset --hard <hash of initial commit>

You can check by running

git status 
git log

Here's summing up the three modes, where they render changes.

Branches in Git

kulsoomzahra — Tue, 13 Apr 2021 14:58:43 +0000

Branches are no doubt, one the BEST features of Git. The Master Branch being the default of the repository is automatically created whenever you fork a new repo.
So usually when making commits, we've being committing only to the master branch.
This master branch is the stable version of your code and something you will release that's the reason why we don't really want to try out new code or features on this stable version (master branch) just in case it messes the whole code of your repo.
So we create an isolated space to experiment new code and features. If all goes good and they seem to work well, you can merge this isolated space (i.e branch) into the master branch thus eliminating the risk of messing up with the stable version of your repo.

This is why branches are a massive feature. Saving you right?

Working on a branch

Here's how you can work on branches:

1) Make a new branch
git checkout -b <branch name>

If you want to switch to an existing branch use
git checkout <branch name>

2) Open the editor of your choice and make changes

3) Add the files
git add .

4) Commit the changes and add a commit message
git commit -m "commit message"

5) Finally, push these changes to the origin
git push origin

If error occurs, it's probably because you've not set your remote properly . Try using
git remote set-url origin SSH of your repo
OR
git push --set-upstream origin <branch name>

Congrats! You've merged your branch into the master!

Renaming a branch

Rename a branch while currently not on the branch:
git branch -m oldName newName

Rename the current branch:
git branch -m newName

Deleting a branch

git branch -d <branch name>

Also delete branch from origin using

git push origin --delete <branch name>

The fractional knapsack problem

Pradeepsingh Bhati — Fri, 19 Mar 2021 18:14:07 +0000

The fractional knapsack problem is a greedy-based problem and also an extension of the classic 0-1 knapsack problem. You can read about the 0-1 knapsack problem here.

Problem Description

Given n items having certain value and weight, put these items in a knapsack with given maximum capacity (maxWeight). The goal here is to find possible maximum total value in the knapsack. Here fraction of items can be used i.e we can break an item. For example :

Input:
n=3
maxWeight=50
weights={10,20,30}
value={50,40,90}

Output:
160.00

In the above example, we can fully select item 0 and item 2. This will give total value = 50+90 = 140 with total weight = 10+30 = 40. For remaining weight space of 50-40=10, we can use (1/2)th of item 1 which will have weight = 20/2 = 10 and value 40/2=20. So total value will be 50+90+20 = 160 and total weight will be 10+30+10=50 i.e. <=maxWeight. This is the possible maximum answer.

Observation

Here the key observation is that we need to use items fully until we lack weight space for the particular item. In that scenario, we can break the item to fill the left weight space.

Greedy approach

As we can break the item into any fraction and use it, we need to normalize it. Suppose we have an item of weight = a and value = b, we can break that item into 'a' number of items each of value (b/a). For eg. if we have an item of weight = 30 and value = 120, we can break that item into 30 items, each having value (120/30)=4 i.e. we have 30 items having weight = 1 and value = 4.

To maximize the total value inside the knapsack, we will sort the items with reference to (value/weight) ratio using the custom compare function in Sort(). One by one we will check for an item and as per the left weight space out of maxWeight inside the knapsack, we will use the current weight.

Case 1: If our current item is having a weight less than or equal to the left weight space inside the knapsack, we didn't need to break the item as the whole item can be accommodated inside, so we will add that item fully. If we have an item of weight 10 and the left weight space in the knapsack is 20 then we can use that item fully without breaking it.

Case 2: If our current item is having a weight more than the left weight space inside the knapsack, we will break the item and use only the fraction that is required. For eg., if we have the capacity(max weight) of knapsack = 10 and the current total weight of knapsack = 8. Current item is having weight = 30 and value = 120. In order to fill 10-8 = 2 weight space in knapsack we will use only (1/15)th of item i.e weight = (30/15) = 2 having value (120/30)*2 = 8.

struct Item{
    int weight,value;

};

class greedy_approach{

    static bool compare(Item a,Item b){
        return (double)a.value/a.weight>(double)b.value/b.weight;
    }

    public:
    double fractional_knapsack(int maxWeight,int n,Item weights[]){
        sort(weights,weights+n,compare);
        double ans = 0 ;
        for(int i=0;i<n;i++){
            if(maxWeight>=weights[i].weight){
                maxWeight-=weights[i].weight;
                ans+=weights[i].value;
            }else{
                ans+=maxWeight*(double)weights[i].value/weights[i].weight;
                break;
            }
        }
        return ans;
    }
};

Here we use Item struct to reduce code complexity and can avoid making extra vectors and maps to store weights and values.

Time Complexity : O(n*logn). We use Sort() and an O(n) loop. The sort takes approx. n*logn time.
Space Complexity : O(n).

A Beginner’s Guide To Data Science

Tanu Sharma — Sat, 06 Mar 2021 12:15:51 +0000

What is Data Science?
Data science is an interdisciplinary field that uses scientific methods, processes, algorithms and systems to discover hidden patterns from the raw data.

Why Data Science?
->Traditionally, the data that we had was mostly structured and small in size, which could be analyzed by using simple BI tools. Unlike data in the traditional systems which was mostly structured, today most of the data is unstructured or semi-structured.

Let’s have a look at the data trends in the image given below:

This data is generated from different sources like financial logs, text files, multimedia forms, sensors, and instruments. Simple BI tools are not capable of processing this huge volume and variety of data. This is why we need more complex and advanced analytical tools and algorithms for processing, analyzing and drawing meaningful insights out of it.

Let’s have a look at the below to see all the domains where Data Science is creating its notion.

Lifecycle of Data Science
Here is an overview of the main phases of the Data Science Lifecycle:

Different job roles data science offers are:

Data Scientist
Data Analyst
Data Engineer
Business Intelligence Developer and many more.

Data Science Skills

Git - Squash

kulsoomzahra — Fri, 05 Mar 2021 18:43:52 +0000

Using git/github for your personal projects is pretty easy but when you're a part of an organisation or a large scale project with thousands of users you might get a tough time. One wrong move can cause mess or make the commit tree dirty or anything you don't want which in turn may fuel your Impostor Syndrome!
So hey, HANG ON! You can do it.

A Clean Commit Tree

Squashing your commits can help so here we go

Switch to the branch where the commit tree is
git checkout <branch name>
Make sure everything on your local is pushed to the branch
git add .
git commit -m "Commit message"
git push origin <branch name>
Squash n previous commits
(n is the no.of commits you want to squash)
git rebase -i HEAD~3

Now, change pick to s or squash in the last 2 commits
Press
a) Ctrl + O to write out
b) Enter to save changes
c) Ctrl + X to exit

Now you can edit the final commit message .
Repeat a,b,c

Don't forget to PUSH your changes on to the branch
git push origin <branch name>

If this doesn't work force push your changes
git push origin <branch name> -f

You're Done! Now you have a clean commit tree.

Unbounded Knapsack Problem

Pradeepsingh Bhati — Fri, 05 Mar 2021 16:34:11 +0000

The unbounded knapsack problem is a dynamic programming-based problem and also an extension of the classic 0-1 knapsack problem. You can read about 0-1 knapsack problem here.

Problem Description

Given n weights having a certain value put these weights in a knapsack with a given capacity (maxWeight). The total weight of the knapsack after adding weights must remain smaller than or equal to capacity(maxWeight). The goal here is to find possible maximum total value in the knapsack. Any weight can be selected multiple times i.e. repetitions are allowed. For example :

Input:
n=2
maxWeight=3
weights={2,1}
value={1,1}

Output:
3

In the above example, we can select weights {1} for 3 times giving knapsack total weight as 3 and total value as 3 which is the maximum possible value.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum. Here any weight can be added multiple times in the subset.

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight. We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it. If selected, we will call for the same index again because we can select a weight more than once.
Don't add the current weight. Here we will move to the next index (i.e i+1)

We will return the maximum of both operations as we have to maximize the total value. Here we will stop at index==n because there's no weight to add in the knapsack. You can see in the code that it is selecting the weight and calling the same index again to check if the same weight can be added again. Also, we are considering the possibility of not selecting the weight. So in the end, the maximum answer for a particular weight after considering both possibilities is returned. At last, we have final answer.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }
            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);
            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i, n, wt, val, maxWeight, dp));
            }
            return dp[i][curWeightSum];
        }
        int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];
                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Time Complexity : O(n*maxWeight*maxWeight). For every weight we are going till maxWeight. And every weight is selected for multiple times reaching maxweight.
Space Complexity : O(n*maxWeight). We used 2-d array dp as extra space

Dynamic Approach

Tabulation is done using a one-dimensional array(dp) in this case. Whose dimension is the same as maxWeight+1. Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) from the dp which contains solutions till current weight(included), and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2. Here the important difference from 0-1 knapsack problem is that we are iterating the dp from 0 to maxWeight(included). This is because we also need solutions for current weight till the current required knapsack weight(j) as weights can be used for multiple times.
If we don't select the weight, the value of that cell remains unchanged as it already describes the answer till now for particular j.

         int unbounded_knapsack(int n,int wt[],int val[],int maxWeight){
            int dp[maxWeight+1];
            for(int i=0;i<maxWeight+1;i++){
                dp[i]=0;
            }
            for(int i=0;i<n;i++){
                for(int j=wt[i];j<maxWeight+1;j++){
                    dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
                }
            }
            return dp[maxWeight];
        }

Here the cell value in the dp array will be the maximum of operation1 and operation2. I used 1-d array, where jth cell represents a knapsack with weight j while performing operations on a particular ith weight. Hence the array will hold results till (i-1)th weight while running for ith weight. Returning dp[maxWeight] will give the answer. Initially, all the values of the array is 0 as it will be the maximum for an empty knapsack.

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space

A snapshot on ML & DL

Abhijit Tripathy — Wed, 03 Mar 2021 02:30:02 +0000

The following blog contains brief notes on “Machine learning and Deep Learning” as a part of AI (Augmented Intelligence)

We came to know that Computers can have the vision to watch/sense and learn from humans, then try to mimic the action with utmost accuracy. So we have three queries now,

a) How computer watch/sense
b) How computer learn
c) How computer mimic

The first question can be answered by the “Computer Vision and Robotics”, we use different sensors and hardware along with support precision making programs/software to correctly input data to the computer/system.

The second question starts with two things available as a parameter - The first one is the “data” that we have collected (From the solution of the first question) and the second one is “patterns and inference*”.

Now coming to the definition,

Machine Learning is the study of algorithms and mathematical/statistical models, to find out some pattern and perform a certain task without being explicitly instructed”

I have underlined four important terms, I am not going to explain them step by step, but I will explain what exactly happens and the mechanism we generally follow. (Please search for the terminology if you are unable to understand)

So we have a set of data, and we choose a random sample(most preferable Stratified Random Sample) of data as “Training Data”, now comes the actual work of designing an algorithm and feeding it to the system as some sort of “Code”. Our training data is the input of the algorithm and we get a mathematical/statistical model as output(say P). Over this core layer of data, Algorithm and output, we have a second layer of decision making and task performing programs designed for a specific work, that takes P as input and performs the task. Then comes the answer for the third question, how computers mimic, “Robotics and Expert System”

Well, arguably, an expert system is a cover layer for “Machine Learning and Deep Learning”, because that includes programs to choose between better ML Algorithm to perform the task, briefly, it emulates the decision-making ability of human expert.

So basically, we have the following outcome till this part of the text,

Before explaining that, we have a new terminology - “Neural Networks”. Most of you might know about what a neuron is, well that’s a group of cells responsible for the transfer, modification and response of information inside the human body from the human brain to another part of the organs. In a similar manner, neural networks are programs designed in such a way that the system can learn and further improve its performance like a human body does. As this is the first assignment, I am not discussing the technicalities involved in details.

Deep Learning is a subset of machine learning, focused on developing the ML Algorithm into layers of data and extract a broader sense of details(technically known as features and attributes) for a more precise and accurate prediction or learning depending upon the target attribute/feature

Forget the definition, lets make that simpler,
We are giving the system this input as an image. Let's see what ML and DL algorithms will predict.

ML Algorithm - 4 leg, 1 tail, 2 horns, 2 ears, size - X
DL Algorithm - 4 leg, 1 tail, 2 horns, 2 ears, size - X, head size: body size = P:Q, 20% black spot, 80% white , cluster of black spot near the neck is more, legs have less amount of black spot

You must be thinking, how does that even matter? ML Algorithm output is sufficient to identify it’s a cow, isn’t it?
Let's have two images to compare,

Your ML Algorithm may fail to distinguish and categorize these two as different(provided the size is the same) but the DL will definitely predict the correct answer because each of the pictures has cows with different ratio of black spot and white spot in their body.

[ Arguably and Technically this is a wrong example, it is meant to just give an idea that DL is nothing but just an extension and enhancement of ML]

Dynamic Programming

Sourav Saraf — Fri, 26 Feb 2021 05:09:22 +0000

Hello Folks,
In this blog we are trying to provide you a flavour of what actually Dynamic Programming is and how to use it.
To provide clear understanding we will be referring to a very common problem named Fibonacci Series with which we are well aware of.
There are multiple ways of solving the problem. They are:

Recursion
Top Down DP
Bottom Up DP
Space Optimised Approach.

We will be discussing each approach in details.

So, Let's Start!

1. Recursion

We know that in Recursion, a function calls itself multiple times till it hits the base case to solve a particular problem. If we initially try to understand how exactly is recursion working then it will be a problem and we may get confused and may not find a way to solve the problem. Initially we should be focusing on large problem and how it can be solved. Then we should define a function and tell it where to stop i.e specify the base case and write code to solve the larger problem and leave the rest in hands of recursion.
Like for the Fibonacci series we know that 1st term is 1 and nth term is sum of previous 2 terms i.e n-1 and n-2. So lets write that and leave the rest to recursion.

int fibonacci(int n)
{
    if(n==1 || n==0)
        return n;
    return fibonacci(n-1)+fibonacci(n-2);
}

The above function is going to work absolutely fine but is this an an optimal approach?

Lets try to understand it. Suppose using above function we are trying to find the 5th Fibonacci term. The above code will generate the following recursion tree.

We can see that recursion tree repeats for some elements a number of times (Highlighted in Red) i.e same work is done again and again. The number of repetition will be even more higher for large numbers. Also the above code has time complexity of O(2^n) which is exponential and is really very bad.

So the answer to above question is NO. This is not an optimal approach.

Nothing to worry about 😊. Dynamic Programming will sort it out.

So what's Dynamic Programming then?

A quote by Winston Churchill says:

Those who fail to learn from history are condemned to repeat it.

This is what Dynamic Programming does. We store the already calculated value so that it can be used as and when required and re-calculation can be avoided.

Let's Discuss them!

2. Top Down DP

When we start from large sub-problem and reach base case it is called Top Down DP Approach. In this approach we use Recursion + Memoization i.e calculate the value using recursion and store it in some array so that we don't have to re-calculate.
Lets see how can Fibonacci Series problem can be solved with this approach.

int dp[100]={0}; // I am assuming size to be 100. It can be anything
int fibonacci(int n)
{
    if(n==0||n==1)
        return n;
    if(dp[n]!=0)
        return dp[n]; //If the value has already been calculated, return it
    dp[n] = fibonacci(n-1)+fibonacci(n-2);
    return dp[n];
}

What do you say about the above code ? Far better then that of recursion (of course not in length :)).
So, the time complexity of above code is O(N) and Space Complexity of O(N) is also required.

3. Bottom Up DP

In this approach we start from base case and reach the required solution. No recursion is needed in this approach.

Have a look at the code.

int fibonacci(int n)
{
    int dp[100]={0}; // I am assuming size to be 100. It can be anything
    dp[1]=1; //We need to provide starting values
    for(int i=2;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

Time and Space Complexity remains the same as above i.e O(N).

I hope that the above explanation and code gave you some idea and flavour of what Dynamic Programming is and how it works. Don't worry. I have not forgotten the 4th section. Its not something very much related to DP so I will discuss it below 😊.

So from the above discussion we can conclude that DP highly optimised the code and saves computational resources like memory.
A huge amount of practice is required for achieving expertization in Dynamic Programming and having knowledge of other algorithms may also help in reaching an optimal DP Solution.

Now its time for Space Optimised approach.

4. Space Optimised Approach
This approach may not necessarily work for all problems as it works for Fibonacci Sequence. In this approach we can find the nth element even without using any array!

Have a look.

int fibonacci(int n)
{
    int a=0,b=1,c;
    for(int i=2;i<=n;i++)
    {
        c=a+b;
        a=b;
        b=c;
    }
    return c;
}

So, lets end our blog here.
Thanks to all the readers for their time. Any feedbacks are always welcome. Hope to see all of you in my upcoming blogs as well.
Thank You 😊.

Binary Exponentiation

Rishabh Singhal — Thu, 25 Feb 2021 15:34:07 +0000

Let's say you are given two numbers a, n and you have to compute a^n.

Algorithm

Naive Approach: O(n)

The easiest approach to do this, if one knows how to use "for" loops or implement it (if it is not implemented already) in any given programming language is just a single O(n) iteration. Below is a sample implementation in C++.

int a, n;
// a, n can be initialized either by taking input or
// by assigning hardcoded values a = 3, n = 4 let's say

// expo initialized to 1 as it is the multiplicative identity
int expo = 1;

for (int i = 0; i < n; ++i) {
    expo = expo * a;
}

// now expo == a^n : true

Note
Here, the data type is "int", assuming the value of expo = a^n comes under the constraint of "int". So, any other data type can be used as per requirements.

Caveats

It can be seen that this approach would time out if n > 10^8.
If the value of a^n is very large i.e. it can not be stored in "int" or any other provided data type, it will overflow.

Possible Solutions

Algorithm of lesser complexity can be utilized in this case -- we will see O(log n) algorithm next.
This is the reason why most of the time (a^n)%(some number) is to be calculated. Most of the time that "some number" is 1e9 + 7 (which is a prime) in competitive programming problems.

Binary Exponentiation Approach: O(log n)

For achieving O(log n) complexity, the mathematical fact that any number (in decimal) can be represented uniquely in binary can be utilized.

For example,
12 = 1*8 + 1*4 + 0*2 + 0*1 = (1100)_2
15 = 1*8 + 1*4 + 1*2 + 1*1 = (1111)_2

Now, also using the fact that a^(m + n) = (a^m)*(a^n), we can calculate the values of a^1, a^2, a^4, and so on ...

int expo = a;
for (int i = 0; i < n; ++i) {
    expo = (expo*expo);
}
// it's like
// expo: a -> a^2 -> a^4 -> a^8 -> a^16 ...
// i.e. with ith step the value will be a^(2*i)

Now, let's say we need to calculate a^n, then there will exist a unique representation of "n" in binary, whose i_th bit can be checked if it is set or not by using a simple boolean expression involving bitwise operator

// (n >> i) & 1 == ith bit of n

for the proof for this refer to Link

now, it can be seen that a^n = (a^(1*b_1))x(a^(2*b_2))x(a^(4*b_3))x... and we can find if the a^(2*i) have to multiply or not by using the fact we saw above. So, by a simple modification to the previous code we can calculate a^n.

//init a, n
int expo = a;

// answer initialized to 1 as it is multiplicative identity
int answer = 1;
for (int i = 0; i < NUMBER_OF_BITS_IN_N; ++i) {
    if((n >> i) & 1) {
        // we check if the ith bit is set or not
        // if it is set then, we multiply expo = a^(2*i)
        answer = answer*expo;
    }  
    expo = (expo*expo);
}

// answer now have the value a^n

See, there is only one "O(NUMBER_OF_BITS_IN_N)" for loop, and it is easy to see that the number of bits in n = log_2(n).

Hence, the overall complexity = 0(log n)

If you are not sure of the number of bits in n, then just simply take MAXIMUM_POSSIBLE_NUMBER_OF_BITS instead which can be ~32 for the int datatype.

Modular Binary Exponentiation

Considering the second caveat described above, there can be cases where we need to find (a^n)%(some value) -- note that % is the remainder operator (as used in C++).

For this, just an easy modification of the code will work,

//init a, n, modvalue
long long expo = a;

// answer initialized to 1 as it is multiplicative identity
long long answer = 1;
for (int i = 0; i < NUMBER_OF_BITS_IN_N; ++i) {
    if((n >> i) & 1) {
        // we check if the ith bit is set or not
        // if it is set then, we multiply expo = a^(2*i)
        answer = (answer*expo) % modvalue;
    }  
    expo = (expo*expo) % modvalue;
}

// answer now have the value (a^n)% modevalue

Conclusion

So, as we saw the binary exponentiation algorithm, it can be used for exponentiating a matrix too, just by changing "*" operator with implemented matrix multiplication and taking remainder with each number in the matrix.

Further Directions

For reading more about binary exponentiation and solving some related problems to get a grasp refer to CP-Algorithms Binary-Exp

0-1 Knapsack Problem

Pradeepsingh Bhati — Tue, 23 Feb 2021 14:37:44 +0000

0-1 Knapsack problem is one of the most important problems based on the concept of Dynamic programming. Dynamic Programming(DP) is an algorithmic concept for solving optimization problems. In simple words, we try to break problems into subproblems and find their optimal solution which leads to the optimal overall solution. Let's understand the problem statement first.

Problem Description

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

In the above example, weights:{3,1} with value:{2,3} respectively will have a total value of 5 which is the maximum among any combination of weights.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum.

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight (Add element to a subset). We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it.
Don't Add the current weight (Don't add an element to a subset).

We will recursively call the next element after performing may be any one or both operations given above as per the conditions. We will return the maximum of both operations as we have to find the maximum total value. We have to stop and return when we reach beyond the array size. So in the end, we will have a maximum of all such subsets where we made choices to select the weight with a certain value or ignore it.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }

            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);

            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i + 1, n, wt, val, maxWeight, dp));
            }

            return dp[i][curWeightSum];
        }

        int knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];

                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Time Complexity : O(n*maxWeight). As we avoided most repeating calls.
Space Complexity : O(n*maxWeight). We used 2-d array dp as extra space

Dynamic Approach

Tabulation is done using a one-dimensional array in this case. Whose dimension is the same as maxWeight+1(capacity of knapsack). Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) till previous iterations and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2.
If we don't select the weight, the value of that cell in dp array will be the answer to the previous iteration for that particular j.

int dp[maxWeight+1];
for(int i=0;i<maxWeight+1;i++){
   dp[i]=0;
}
for(int i=0;i<n;i++){
   for(int j=maxWeight;j>=wt[i];j--){
       dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
   }
}
return dp[maxWeight];

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space

Approximation Algorithms (Introduction)

Abhijit Tripathy — Tue, 23 Feb 2021 02:28:43 +0000

In this article, we will be exploring an interesting as well as a deep overview of Approximation Algorithms, but before that, we will be discussing some important terms.

Optimization Problems

In computer science many a time we come across optimization problems, where we have to optimize a certain variable in accordance with some other variables. Optimization means finding a maximum or minimum.
For example,

Finding the shortest path between two vertices in a graph.
Finding the minimum number of colours needed to colour a graph, etc.

Decision Problems

These are a little bit different from the Optimization problems. In this type of problems, the main target is to find whether a solution exists or not, just like a typical yes or no question.
For example,

Checking if a graph is Hamiltonian
Checking whether a cycle exists in a Linked List, etc.
Programming and mathematical problems that we have observed in daily life can be categorized into two classes problems,
P class
NP class

P class

The class P consists of those problems that are solvable in polynomial time by the turing machine, i.e. these problems can be solved in time O(n^k) in worst-case, where k is constant.These problems are also known as tractable.

An algorithm A is a polynomial time algorithm, if there exists a polynomial p(n) such that the algorithm can solve any instance of size n in a time O(p(n)).
Algorithms such as Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree, etc. run in polynomial time.

NP class

NP is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. NP consists of those problems that are verifiable in polynomial time. Hence, we aren’t asking for a way to find a solution, but only to verify that an alleged solution really is correct.

Every problem in this class can be solved in exponential time using exhaustive search.
Problems such as travelling salesperson, optimal graph colouring, Hamiltonian cycles etc for which no polynomial-time algorithms is known, are classified as NP-complete problems.

Approximation Algorithms

The formal definition says,

Given an optimization problem P, an algorithm A is said to be an approximate algorithm for P, if for any given instance I, it returns an approximate solution i.e. a feasible solution.

An Approximation Algorithm is a way of approach NP-completeness for any optimization problem. This does not guarantee the best solution. The main purpose of an approximation algorithm is to come as close as possible to the optimum value at the most polynomial time. Such algorithms are called approximation algorithms.

For example -For the travelling salesperson problem, the optimization problem is to find the shortest cycle, and the approximation problem is to find a short cycle.

Some famous problems of Approximation Algorithms

Let's discuss some famous Approximation Algorithms with their problem statements,

The Vertex Cover Problem

Problem Statement
Given an undirected graph, the vertex cover problem is to find a minimum size vertex cover.
As the name suggests, A vertex cover of an undirected graph is a subset of its vertices such that for every edge (x, y) of the graph, either x or y is in the vertex cover.
This problem is an NP-complete problem and can be solved approximately i.e. no polynomial time solution(unless P = NP).

1) Initialize the result as an empty list {}
2) Consider a set of all edges in a given graph.  Let the set be E.
3) while E is not empty
    a) Pick an arbitrary edge (x, y) from set E and add x and y to result
    b) Remove all edges from E which are either incident on x or y.
4) Return result

The time complexity of the above algorithm is O(V+E) where V is the number of vertices in the graph and E is the number of edges.

The Travelling Salesman Problem

Problem Statement
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

This problem can be converted into a graph problem, which has V nodes(i.e. number of cities) and the cost matrix will hold the edge weights(i.e. the distance between any two cities).
The problem is a famous NP-hard problem. There is no polynomial-time to know a solution to this problem.

A naive approach to solve the problem can be,

1) Consider city 1 as the starting and ending point.
2) Generate all (V-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.

The above algorithm works in O(V!) time complexity, where V is the number of vertices in the graph.

There are other approaches using Bitmasking and Dynamic Programming to solve in O(V^2 * 2^V) time complexity.
Branch and Bound can be one approach in finding a solution for this NP-Hard problem.

This problem can be easier to approximate if the edge weights of the graph follow a triangle inequality, which means w(u,v) <= w(u,x) + w(x,v), i.e. distance of city u to city v is less than the sum of the distance of city u to city x and city x to city v. This problem is also known as Metric TSP, which is an approximate version of the problem. This is still NP-Hard, but we can approximate the solution.

The Bin Packing Problem

Problem Statement
Given n items of different weights and bins each of capacity c, assign each item to a bin such that number of total used bins is minimized. It may be assumed that all items have weights smaller than bin capacity.
In computational mathematics, this problem is a NP Hard problem and the decision problem version of the same is NP Complete.

This problem has been studied widely and can be solved in many approximation techniques like - Next-Fit (NF), Next-k-Fit (NkF), First-Fit (FF), Best-Fit (BF), Worst-Fit (WF), First Fit Decreasing (FFD) etc.

The best time complexity can be O(NlogN) for this.

Examples of Approximation Algorithms

The approximation algorithms return us a legal solution that may not be optimized, let's have a look at the below examples,

The vertex cover problem -

Given an undirected graph, the vertex cover problem is to find minimum size vertex cover, this is an optimized return type, i.e. we need to minimize the size of the vertex cover.
But the approximation version can be compiled as,Given an undirected graph, the vertex cover problem is to find the vertex cover, you may notice that there is no optimization(min/max requirement).

The Travelling Salesman Problem

Given a set of cities and distance between every pair of cities, the problem is to find the possible route that visits every city exactly once and returns to the starting point.
Notice that we don't need to find the shortest(i.e. minimum) possible root, instead we just need to find a legal route for our salesman.

Conclusion

The above problems are some of the examples to deliver the idea of what an Approximation Problem looks like. There are several other problems as well which are NP-hard and NP-complete.
The best thing about approximation algorithms is that, you can cross proof your approach in order to know if that's a feasible one.
And the probable worst thing is, these are approximations not exact.
Algorithms rule the world even if that is approximate or exact. Hence let's utilize these rules to build a better world for everyone.

Original Article Source - https://iq.opengenus.org/approximation-algorithms-intro/

Sum of N Fibonacci Numbers

Kartik Bhatia — Mon, 22 Feb 2021 12:15:19 +0000

If you read the title and you have that feeling for algorithms you already know the way to Sum Up Fibonacci Numbers. But let's see it the other way round , Let's do it today in a more Mathy way ( ofcourse the optimal ).

(If you don't Know Fibonacci Numbers)
Fibonacci numbers is a series of numbers created in such a way that the current term in the series is the sum of previous two terms, ofcourse the first two Terms in Fibonacci are 0,1-> and then it continues this way after 0,1,-> 1,2,3,5 or you can generalize this as ...

F[0]=0
F[1]=1
F[i]= F[i-1]+F[i-2].

Now when you think about some algo to to Sum Up N fibonacci Numbers, what you can attempt is Find ALL Fibonacci up till N numbers, and now how to do this , as you saw the pattern here that i th fibonacci is sum of (i-1)th and (i-2) th Fibonacci,so let's throw some light on it You can begin with your F[0]=0 and F[1]=1 and Find All Fibonacci Up Till Nth Fibonacci, this is just some easy Dynammic Programming stuff where we have the results for the previous two fibonacci and we create our next out of it.
Here is a pesudu-code for it as well

int F[N];
F[0]=0;
F[1]=1;
for(int i=2;i<N;i++)
{
      F[i]=F[i-1]+F[i-2];
}

And Once you have All Fibonacci up till Nth Fibonacci we will be planning to sum them up and this again is a simple while loop

int sum=0;
for(int i=0;i<N;i++)
{
      sum=sum+F[i];
}
return sum;

Now think about Time Complexity We have two loops which are going up till N , So Asymptotically this completely Boils down to O(N).
Can We do it Better ?
Yes Now comes some beautiful Math along with it , Previously we were depending upon All the N terms to Sum Up N terms of Fibonacci , This time It ain't needed Let's derive a formulae for it.

As this is the recurrence for Fibonacci,

So it can be re written as this by some LHS RHS shifts.

Also this holds true,

, So Similarly we can write these equations going this way

ans so till N-> 0

If we add up all the equations we will get this result

Now I think YOu observe that what we are trying to demystify.
S[N] IS SUM OF N TERMS OF FIBONACCI

AND WE HAVE A CONCRETE EXPRESSION FOR IT NOW,

We No Longer Need N elements of Fibonacci to Sum N terms of Fibonacci , ALl we need now is N+2 th term of Fibonnaci to sum up till N.

How to Do it ? Optimally ?

Hint-> Use Some Linear Algebra to find any Fibonacci Term in O(LOG(N))