Graph Theory is used in modelling and solving a lot of real world problems, games and puzzles. Here we discuss a very famous puzzle " The Instant Insanity " problem.
The goal of this post is to demonstrate that such complicated problem statements can be so easily modeled and solved using Graph Theory. Also I would like to build some more interest into Graph Theory. If you want to feel more comfortable with the basics of Graph Theory, here is a list of primers you might like to read once.
Problem Definition - The Instant Insanity Puzzle
There are four cubes such that the six faces of ea...

Read More
## Priority Queues

Introduction
You have N distinct jobs to process, and you are given the responsibility to schedule them on the only available job processor.
New jobs keeps on getting added into the set of available jobs. Not all the jobs are to be executed as they come.
There might be few which needs to be executed immediately and few can be postponed for some time.
You have an efficiently algorithm to decide the priority of an incoming job. The task at hand is as follows:
To schedule available jobs based on the priority assigned to them.
Add new jobs to the set after assigning a priority to it.
...

Read More
## Count Triangles formed by the elements of array

Problem Statement
Given a sorted array of distinct integers, each of these integers can represent a length. The task at hand is to count the number of possible triangles which can be made through these lengths.
Of course, if you chose one length to be one side of the triangle, you cannot use that length again in the same triangle. This means, no triangle contains the same length more than once.
Important Note: For given sides of lengths a, b and c. A triangle can only be formed if sum of any two sides is greater than the third side. This is called the triangle inequality. The sum of any...

Read More
## Understanding Heap Sort

[nextpage title="Introduction"]
Heap Sort is one of the efficient sorting algorithms with a guaranteed worst case running time of O(NlogN). This is an in place sorting algorithm but it does not offer stable sorting.
In place Sorting: A sorting algorithm which sorts the input using very small or no extra space. It means that the input data is overwritten by the resulting output data.
Stable Sorting: A stable sorting algorithm is one, in which the relative order of equal keys is preserved. It means if there are non unique keys in the input data, then their relative order of occurrence in ...

Read More
## Find the Relative Salary

Puzzle Statement
Steve would like to determine the relative salaries of three coworkers using two facts:
First, he knows that if Fred is not the highest paid of three, then Janice is.
Second, he knows that if Janice is not the lowest paid,, then Maggie is paid the most.
Is it possible to determine the relative salaries of Fred, Maggie and Janice from what Steve knows? If so, who is paid the most and who the least?
Quick Solution
Fact 1 says that if Fred is not the highest paid, then Janice is. This results in two situations:
Fred is not the highest paid
Janice is the hi...

Read More