EduBhogi Video Demo

Stolen

"Three minutes to the train," thought Rakesh. It had been a tiring day for him. His job at the dockyard, which was initially hard on him, had gotten easier with time. Earlier, it was a strange caricature of decay and resurrection, but after his first salary was credited a few days ago, the same structure turned into the sweaty smell of hope. Somehow, he had found a home in the blood-metal sound of machines and the ocean's blue water and skies. He did not particularly enjoy coming to the railway station, though. The railway station always made him envious of the lives other people had—families saying affectionate goodbyes, girlfriends holding hands with their boyfriends, and a group of young men cackling with laughter and merriment. It was this envy that made him buy an expensive new smartphone with his first salary. He wanted to feel more confident among the crowd around him. He had already imagined himself standing beside the pole of the Mumbai local train, earphones in his ears, and the wind blowing through his hair. The fact that he owned such an expensive piece of technology made him beam with happiness and joy. He had touched his front pocket jeans countless times, partly because he wanted to be sure that he had one and partly just to enjoy its feel in his pocket. 

"Pooooo..." whistled the train. Rakesh looked up toward the arriving train. Finally, he was going home. He raised his suitcase over his head so that he could fight his way into the general coach of the train. It's amazing to see how quickly people coalesce to get into the general coach of the train. Rakesh nudged around with his elbows as he tried to get on board. In the midst of elbow-kicking and chest foreplay, he saw the familiar face of Mr. Patloo. Mr. Patloo was a 40-year-old man with five strands of hair on his head. He wore a colorful T-shirt and tight-fitted jeans. You did not have to look closely to understand that he was a textbook example of midlife crisis. Oblivious to his bizarre sense of fashion, Mr. Patloo greeted Rakesh with a wide, affectionate smile as both of them fought their way through the crowd. Somehow, they were lucky enough to be inside the train. The general coach of the bogie is a different type of caricature in itself. As you pass, you can smell the different body odors mixed on the bogie.

Dynamic Programming

In this blog post we will discuss various dynamic programming questions. The idea is to have a same template to understand all the dynamic programming problems. All the problems that we discuss will be divided into four parts:-

• What is the question?  (read * 2 times) 
• Why this problem can be solved with the help of Dynamic Programming? (read once)
• What does dp[i][j] or dp[i] mean with respect to the question? (read once)
• What is the solution if the assumed dp array is to be constructed? (read once)
• How the dp[i] or dp[i][j] will be formulated? Along with the help of an example. (read twice)
• Variations to the questions 

Once these algorithms are done, we will observe that even the new problems can be solved with the help of this template. I have used same terminology to make the questions easier. 

1. Longest Common Subsequnce

QUESTION : Given two sequences, find the length of longest subsequence present in both of them. In the code given below we assume X,Y to be strings.

WHY DP:  Notice that given problem can be broken down as smaller chunk problem. Let us just take the first character of both the strings and compare them. Then we take the next character of string 1 and compare it with string 2 and so on.

DP[i][j]: 
for the string s1[0..i] and string s2[0..j] what is the length of longest common subsequence with those specific substrings.  Example let string 1 be  "abcdefg" anf string 2 be "abcdgk"

SOLUTION:   dp[n][m] (initialized as  dp[n+1][m+1]

CODE:
https://github.com/vaibhavgeek/tompetitive/blob/master/dynamicProgramming/lcs.cpp

        if (i == 0 || j == 0)  
            dp[i][j] = 0;  

        else if (X[i - 1] == Y[j - 1])  
            dp[i][j] = dp[i - 1][j - 1] + 1;  

        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

Variations:- 

• Printing Longest Common Subsequence
• Longest Common Subsequence with at most k changes allowed

 2. Maximum Sum Subarray

Tha maximum sum subarray is the task of finding the largest possible sum of a contagious subarray, within a given one-dimensional array A[1..n]. (No length specified)

    dp[i] = max(dp[i-1] + a[i] , a[i])

The maximum subarray problem is the task of finding the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers with k length.

    dp[i] = dp[i-1] + a[i] - a[i-k-1]

3. Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

    if(arr[j] < arr[i])
        dp[i] = max(dp[i], dp[j] + 1)

4. KnapSack Problem

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property)
In this problem we define dp[i][j] as i value and for j knapsack capacity. That is for j capacity how much maximum value it can store.

if( j < wt[i]) 
        dp[i][j] = dp[i-1][j];
    else 
        dp[i][j] = max(dp[i-1][j - wt[i]] + val[i] , dp[i-1][j]);

5. Coinchange Problem

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

    if(j >= coin[i])
     {
        dp[i][j] = min(1 + dp[i][j-coin[i]] , dp[i-1][j]);
     }
     else
     {
           dp[i][j] = dp[i-1][j];
     }

5. Wordbreak Problem

Vending Cook Update : 19th March

VIM Tutorial - Everything you need to know #1

So you have heard way too much about vim and have given it a go but it turns out that you have given it up after trying it for two days, the reason being you just cannot get used to this new way editing software! You probably already know how to shift between "escape" and "insert" mode of VIM.


COPY PASTE COMMANDS IN VIM

yy Yank (copy) the current line, including the newline character.

dd, Delete (cut) the current line, including the newline character.

p (paste) the text after the cursor

SCREEN SPLITTING.

Ctrl+W, S (upper case) for horizontal splitting

Ctrl+W, v (lower case) for vertical splitting

Ctrl+W, Q to close one

Ctrl+W, Ctrl+W to switch between windows

Ctrl+W, J (xor K, H, L) to switch to adjacent window (intuitively up, down, left, right)

The lies we have been told

Initially, I thought of writing an article titled "things I wish I had known five years earlier" but honestly speaking most of them I had already known. Also, this article is intentionally written in Hinglish so to have a more realistic feel with the narrative.

Disclaimer: Views can be biased, keep your own judgment with you while reading it.

1.) CGPA 

I vividly remember my seniors giving this advice to me "agar job chahiye toh cg matter nahi karta but research me jaana hai toh kam se kam 8 lana padega". Everyone nodded their head in agreement as if no truer words had ever been spoken before.

For the next five years every time during the exams I asked myself the purpose of "hacking" the previous years' question paper so that I could repeat the same process during examination Hall.  Well, ideally this shouldn't have been the case. Ideally, learning should be equivalent to scoring high marks in an exam. But that's not the case. Not for anyone.

Experience tells us that the best way to study for an examination is to make the list of probable things that will come in the exam, understand them, practice enough problems to cover the range of expected questions and deliver during the examination. The problem with hacking the question paper is that knowledge often is retained just for the duration of the examination, and even if you remember parts of it later, the breadth and depth of the topic is somewhere lost. So clearly examinations aren't the best way to test if a person is learning something or not and yet we tend to study the most just before a test. Hence, order to increase the growth rate in learning there needs to be examination conducted.

You solve previous year paper, you can pass the exam. You solve the previous 5 year papers, you get a distinction. You solve the previous 10 year papers you can probably help the teacher set the question paper for your batch. The only way one can make the tests unhackable is not to increase the difficulty level of the exams (as is assumed by many) but to make them optional. If we are not compelled to study something, we won't do it out of pressure but we will do it for a higher belief system, thus ensuring contentment with our learning experience. Now, keeping students engaged and interested all the time would require newer initiatives and creative solutions in approaches to teaching which is indeed a hard task to accomplish, and I do not think it is right thing to blame teachers for that (Note that I am presenting this point of view just to discard it later is because many of the students believe in it) but instead, make CGPA matter way less than it already does. CGPA should be a metric to guide students rather than a fail-safe mechanism of promotion/demotion. Just like how a gym trainer guides its' incubees. They advise them on follow up course of action depending on the individual requirements rather than kick them out of the gym.

“Study hard what interests you the most in the most undisciplined, irreverent and original manner possible.” ― Richard Feynmann

2.) Happiness 

In the last 50 years(1970-2020), we have seen the advent of technology, and very few deaths because of famine/wars as compared to the previous 50 years (1900-1970). Fewer humans are dying because of starvation. More and more people have access to basic needs such as roti, kapda and makaan. Yet suicides rates are through the roof. Before 1950, suicide rates in countries such as Japan, New Zealand and France was one in 100,000 but today it has increased to a whopping 25 people in 100,000. The reason is pretty simple when economic prosperity happens, expectations ballon. People don't get depressed because of external happenings but from failures internally. Going forward into the century even if the government provides free food for all, cure us of all diseases, ensure world peace, free electricity and internet access to all, it will probably ballon the expectations that people have from themselves, thus leading to more misery.  According to John Stuart Mill "happiness is nothing but pleasure and freedom from pain, and that beyond pleasure and pain there is no good and no evil. Anyone who tries to deduce good and evil from something else (such as the word of God, or the national interest) is fooling you, and perhaps fooling himself too". So, we are biologically entitled to increase our pleasant sensations, the problem is pleasant sensations are like a drug that needs to upgraded with every high you have. Let's assume you feel high after eating a dessert you have craved for long. You end up having it on a regular basis, you won't feel the same high in your second, third eatings. You will crave for more. You will crave for a better dessert and that search will make you miserable.
So what should we do? Aim for less!? Doesn't that sound like losing? No. That's not my point. My point is that pleasure would only feel like pleasure if it is constrained for an aeon of time. Repeated pleasure is nothing but pain.

And when solutions are easy and plenty, we do look out for repeated pleasures.



3.) Technology 

I recently saw a video from 1989 which talked about how our world in 2020 would look like. It talked about flying cars, home automation system and voice-activated circuits. I am not sure about that but 2020 has seen a rise of mobile applications such as Snapchat, Twitter, Reddit, Youtube in ways that wasn't imagined in 1989.  

VendingCook Update