Given a binary tree, find a branch whose elements sum up to a given number.

Problem Statement: You have been given a binary tree with integer values. You are supposed to find if a branch exists  (ROOT node to LEAF node) such that the sum of all the values on this branch sums up to a given number ‘x’.

Let us work on the above binary tree. Assume x=26. Now the correct branch would be 2->7->6->11. So the answer is “Yes, such a branch exists”. I hope you understand the question now.

How would you go about solving this problem? If the first thought that came to your mind was “recursion”, kudos! That is in fact the correct way to solve this question. (And usually always the technique you use in questions involving trees)

This time we go for a top->bottom recursion and keep adding the sum everytime we move down in a branch. Now as soon as you reach the leaf, check your sum and return 1 (success) or 0 (failure) accordingly. Here is the algorithm:

int Check ( Node current, int sum ) //initial call with Check ( ROOT, 0)

{

sum = sum + current->VALUE

If ( current->LEFT != NULL)

int left = Check ( current->LEFT, sum )

If ( current-> LEFT !=NULL)

int right = Check ( current->RIGHT, sum )

If (current->LEFT == current->RIGHT == NULL )

{ //in case of LEAF nodes

If (sum==x)

return 1

Else

return 0

}

return (left || right) //return 1 IFF we receive SUCCESS (1) from any branch, left/right

}

Pretty simple to understand, right? So for the first time in the blog, we have applied recursion and used it while going it from top to bottom (if you get what I mean).

Cheerio!

PS: If you are wondering why we don’t return as soon as sum exceeds ‘x’, remember that the binary tree is said to have integers, which means negative numbers are allowed. Attention to detail!

Shuffling Numbers

I recently talked about generating random numbers. What if you are given a set of numbers and asked to shuffle the numbers randomly. What are the different methods that you can think of? There is basically one method you should remember, because finally every algorithm will take you to the same basic thing, which is,

Generate a random number between 1 and n (included), where n is size of the given set. Now put the number at that position in your array in the first place. Repeat the process for the n-1 remaining places. The randomness of the shuffling here will be decided by your random number generator’s randomness.

(A method suggested by Fisher-Yates and multiple others as well. Big deal!)

That is what most algorithms to shuffle numbers are all about. You can ofcourse fine tune your method to give you your shuffled sequence in O(n). Some old algorithms tend to run for O(n*n), but those are just too stupid and you can easily figure out how to fine tune them to O(n).

Yeah, that was as simple a post as they come!

PS: I don’t have a lot of time right now to write a full-blown algorithm for some problem right now. Sorry for the gap.

Stable Marriage Problem

Please note before diving in: This is an algorithmic problem. If you land at this page looking for solution to something different, please visit a marriage counselor.

Poor jokes apart, this one is another famous problem of the computer science domain. Here is how the problem statement goes: (source: Wikipedia)

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”.

So basically you have to pair people in such a way that they have no better choice. You are given the preference list of each of the n men and n women and are supposed to give the perfect pairing. Now with no other conditions imposed, you can treat this problem as a simple greedy problem. Here is what your algorithm should do:

The algorithm will work in iterations.

For the first time, each unengaged man proposed to the woman he prefers the most (i.e., woman highest on his priority list). All the women would consider their proposals and select the proposal from the man who is higher than others on her list of preferences. They are now tentatively engaged.

Now in every iteration from now on, each unengaged man will propose to the woman who is next on his list of preferences. The women will compare all the proposals they are currently getting along with the one whom they are tentatively engaged to (if any). They will again select the proposal of the man who is highest on their list of preferences.

This process stops when all men are engaged after an iteration.

This greedy method was simple to understand and hopefully you would have got it by now. This is known as the Gale-Shapley algorithm. If anyone has any trouble in figuring it out, check out the gif animation below to see a sample case.

Brilliant! So you are now equipped with another algorithm to tackle your day-to-day marital, friendship and roommate related problems.

Have fun!

Minimizing multiplications in Chain Matrix Multiplications

Be patient and read every line. You’ll end up understanding a great problem of Dynamic Programming.

Problem Statement: Parenthesize a Matrix Chain multiplication matrix in such a way that the number of multiplications required are minimized.

First things first, how many multiplications are involved in multiplying 2 matrices?

If your 1st matrix is of dimensions mxn and your second matrix is of dimensions nxq, you will need to perform mxnxq multiplications in this matrix multiplication.

So if your matrix multiplication chain is as follows,

A x B x C x D , we have the following scenarios,

A = 50 x 20

B = 20 x 1

C = 1 x 10

D = 10 x 100

So you see how we minimized the cost of multiplications there. Now we want to develop an algorithm for the same. You can check all possibilities but as you will realize that you will have very high complexity with such a Brute Force method.

As we discussed a parenthesis problem in my previous post, your mind should jump to find an optimal substructure here. Now you can see all these parenthesizations as a binary tree with these matrices as the leaves and the root element being the final product of all matrices. For example, you can view ((AxB)xC)xD) as,

Hopefully you understood everything till here. Now for a tree to be optimal, its subtrees should also be optimal. So here we come across our optimal substructure. Hence, subproblems are of the form,

(That is the representation of any one node in some binary tree except for the leaf nodes)

Thus we define this sub-problem as,

C ( i, j ) = minimum cost of multiplying  

Size of this subproblem = j-i

Hence, minimum possible size is when i=j (single matrix), so C ( i, i) = 0

For j>i, we consider optimal subtree for C ( i, j ). Now, we can divide this from Ai to Ak and Ak to Aj for some k>i and k<j. The cost of the subtree is then the cost of these two partial products plus the cost of combining these. So we land with the recurrence,

C (i, j) = min { C(i, k) + C(k+1, j) + m(i-1) x mk x mj }

where i<=k<=j.

Coding this is pretty simple now and I need not (and should not) spoonfeed it to you. All you need to do is generate this 2D matrix and another one which holds details about parenthesizations and you’ll end up with your answer.

PS: If someone requires the code, sorry won’t give you that. If you need the algorithm, drop a comment or a mail. That I can write down.

 

 

Counting possible parenthesizations in Matrix Chain multiplication

Problem Statement: Given the number of matrices involved in a chain matrix multiplication, find out the number of ways in which you can parenthesize these matrices in the multiplication, i.e., you have to find the number of ways you can introduce brackets in this chain matrix multiplication. (forming groups of 2).

For example,

A x B x C can be grouped in 2 ways,

(A x B) x C

A x (B x C)

You should remember that while matrix multiplication is not commutative, it is associative. Hence both the multiplications mean the same.

How do we find the number of such parenthesizations? It becomes simple when you realize that you can derive solutions for this problem using solutions to smaller subproblems which you calculated earlier. Dynamic Programming

So for,

N=1, P(N) = 1

N=2, P(N) = 1 (easy to figure out)

N=3, P(N) = 2 (again easy)

So what we are doing here is finding out the previous solution and figuring out the different ways you can introduce one more matrix in the picture to find the next. So your function looks like,

 

I guess you understand how this is Dynamic Programming. And also the fact that this is a very simple permutations question. Not really a programming problem.

Why did I write this post? There is a genre of DP problems known as Optimal Matrix Chain multiplication. You are supposed to find the way (out of these P(n) ways) in which the number of multiplications required will be the least. We will solve this problem in the next post.

Till then, adios!

Valid Parentheses Combinations

Problem Statement: You are given a number of pairs of parentheses. You are supposed to print all valid combinations using all these parentheses.

This question is only an example of questions where you are supposed to find all the permutations of a set of elements. I am using this question to demonstrate the method to perform all such permutations.

So how do you go about finding all permutations. Here is a great method to do so. Start with a single parentheses. Now start inserting the remaining parentheses at all the possible locations. Here is how it goes if we are given 2 pairs of parentheses.

(,),(,)    //available elements

Now constructing all possibilites:

( //start — 0

()  //inserting ) to the right in 0 — 1

)(  //inserting ) to the left in 0 — 2

()( //inserting ( to the right in 1 or left of 2 — 3

(() //inserting ( either in the middle or left of 1 — 4

)(( //inserting ( in the middle of 2 — 5

()(), ())( , )()( //inserting ) at different places in 3 — 6

(()) , ()() , )(() //inserting ) at different places in 4 — 7

)(() , )()( , ))(( //inserting ) at different places in 5 — 8

Now all you need to do is find the valid combinations from those generated in 6, 7 and 8. Handy technique, right?!

PS: Leave a comment if you don’t know how to check validity of parentheses combinations and I’ll write a post on that as well.

 

Shortest Path in Directed Acyclic Graphs

Problem Statement : Given a DAG, find the shortest path to a particular point from the given starting point.

This one is a famous problem that involves dealing with graphs. I assume everyone knows what a graph is. If you don’t, this is not the place for you to be. Please visit this wiki link for knowing more about Graphs. Let us get down to talking about DAGs (Directed Acyclic Graphs). Directed means that each edge has an arrow denoting that the edge can be traversed in only that particular direction. Acyclic means that the graph has no cycles, i.e., starting at one node, you can never end up at the same node.

Now that we are clear with what a DAG is, let us think about the problem. If we have the following DAG, what kind of algorithm would you use to solve this problem.

One thing you can do is apply an O(N*N) algorithm and find the shortest distance by calculating all the distances from each node to every other node. As you can guess, a better method exists. You should notice here that there is subproblem quality that exists here. If a particular node can be reached using two nodes, you can simply find the minimum of the values at the two nodes plus the cost for reaching to the node in question. So you are extending your previous solutions. Yes, Dynamic Programming.

The reason you are able to find such an optimal substructure here is because a DAG can be linearized (Topologically sorted). For example, the above DAG is linearized as follows,

Now if we want to find the minimum distance from start S to A. All we need to do is see the minimum distances to reach the nodes from which A can be reached. In this case, these nodes are S and C. Now the minimum of these minimum distances for previous nodes (till S=0, till C=2) added with the cost of reaching from these nodes (from S = 1, from C=4), is our answer.

So let me define the recursive relation for this case,

MinDist (S to A) = minimum ( MinDist(S to S) + Dist(S to A), MinDist(S to C) + Dist(C to A) )

Generalize this recurrence and you have a simple Dynamic Programming algorithm ready to solve the problem for you in linear time! Cheers!