Spiral (ZigZag printing) Printing the Binary Tree nodes in C

This is a variant of level order printing. In level order printing we can use iterative or a queue based approach. Iterative option is still available in this one too.But we are trying to follow a non iterative approach here. Instead of a queue we will have two stacks for implementing Sprial printing (also called ZigZag printing) of the Binary Tree. First we push the root node to stack one. Then we visit both stacks and take the top item and store it in a temp variable, then we will pop the stack from which we had pushed the binary tree node. At the same time we will push into the alternate stack the children of the temporary node we had stored. On one stack we will push in right then left child order and in the other one we will be pushing in left and then right children order.

For a binary tree like below

                                         1
                                         / \
                                        2 3
                                       /\  /\
                                     4 5 6 7

 the spiral printing order will be as below:

 1
23
7654

 Below is the implementation:

Kadanes Algorithm for finding sub-array with maximum sum

Here is the Kadanes algorithm implementation in Python. Here we pass thru the array in a linear fashion. While we pass thru the array we keep adding the elements. As we add the elements we keep track of previous largest sum ever found. We compare the present sum with so far largest sum till we finish the entire array.

Algorithm for inserting elements from the back of the Linked List to the elements on front of the array interleaving one node each.

Algorithm for printing reversing a array from mid element and inserting nodes between two nodes . 
For example

 -> 11 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null 

should be converted to 

->11 -> 1 -> 10 -> 2 -> 9 -> 3 -> 8 -> 4 -> 7 -> 5 -> 6->null

Algorithm to print combinations of elements in given order (Written in Java)

This is an algorithm to print combinations of elements in an array following the lexicographic order. For example if the given array is

{ 'a', 'b', 'c', 'd'}

then the answer should be

 ab, ac, ad, bc, bd, abc, abd, acd, bcd, abcd.


 Given below is the implementation:

Byte aligned malloc implementation

Usually when we call malloc we are returned with a address where the memory is allocated. But suppose if we want to ensure that the memory allocated is aligned with some value how can we implement such an malloc. Below is an implementation of that:

Pursuit towards finding equations and algorithms for happiness

A simple algorithm for improving your happiness index ?  Is there any such proven formula ? Because if you carefully notice, one or the other way everyone pursue what brings happiness to them. May be its different for different people at different occasions, but truth is we follow what we regard as happiness. Humans and Animals live that way and the only difference in humans is that he or she is having more perseverance than most other Animals when happiness is pursued. In Animals its most of the time instantaneous. So how smart is it to think about generic equations and algorithms which can save the world ?

Some people call that perseverance you follow as your ego or some times its treated as greed and sometimes its a  pursuit towards once objectives or relentless pursuit towards desires. But reality is you are following what you think will make you  happy and every one does. That's when I stumbled upon this strange equation.

Now lets see what is the ingredient of happiness thru this equation.

 Happiness Index = No of desires fulfilled / No of desires pursued.

This one I noted down from a a book Self-Unfoldment by Chinmaya publications, and the book is quoting from vedanta which is a pre-historic Hindu  religious ideology of thought. The immediate thing I wanted to do was to find out the math in this equation and to find out if there is a scope for algorithmic treatment to this equation.Does looping this equation under a loop algorithm create lot of happiness ?. Does this could be made scale-able or is it good enough to try a iterative approach to make it contagious to make everyone happy.

Lets examine the boundary cases by giving numerator and denominator with values as infinity, zero, positive - negative numbers etc.

Case One: Numerator(positive\negative number) Denominator (positive\negative number): Lets examine the normal case for most of the individuals. This will be some positive or negative  number at Numerator and Denominator. Your happiness will be more if the numerator in the above equation increases . If the denominator decreases then too the happiness index increases.

Case Two: Numerator(zero) Denominator (positive\negative number): If the numerator is zero and denominator is non zero number, again your happiness will be zero. So its important that you try to create some value to be seen in the numerator and that could become the basis of your happiness if  you are not able to achieve infinite happiness(like explained below)

Case Three : Numerator( positive\negative number ) and Denominator (zero) : Denominator becoming zero is also a problem since division by zero (http://en.wikipedia.org/wiki/Division_by_zero) is undefined and your happiness will also be undefined.

 But this case seem to be curious to me that I tried to further drill down . Because my conscience was not allowing me to think that if I don't have a desire to pursue why cannot I be happy. For example if you see animals, animals had got enough rational thought to pursue a desire per se, rather there response is always instantaneous not to be treated as a desire, but still animals show moods of happiness and sadness. But if you check division by zero the calculus way, you could see that it seems possible to define a/0 by considering the limit of a/b as b approaches 0. :










This means, say if b is approaching to zero from positive number side then the answer could be treated as positive infinity. Meaning if you are in a state where your desires pursued are approaching zero but not zero then you will have this happiness index of positive infinity. I don't know yet to correlate positive infinity to something which someone have experienced, but it seems very intriguing to know. Is it something so sublime or is it the enlightenment Or is it the real heaven ?. Buddhist believe that Gautham Buddha had enlightenment. He was a prince and he decided to pursue a life without desires after enlightenment at  Bhod Gaya.

Now if the b was approaching to zero from the negative number side then the answer could be treated as negative infinity. What does negative value of not having a desire to pursue mean ? Is that pursuing others  not pursue any desire or is it a state where it needs lot of energy to have desires ? But moving from such a state to "zero desires to pursue" results in negative infinity. What does that correlate to ? Is this "hell"  ?

Case Four : Numerator( zero ) and Denominator (zero) : Again a undefined case. But it seems this case if often termed as infinity. Does that mean the happiness index will stand at a point where ones happiness is always infinite. Now in this case as above there is no scope of positive or negative infinity, does that mean this is the safest route to pursue happiness without having the risk of falling into negative or positive infinity (by whatever good or bad definitions positive or negative infinity translate too)

Anyway applying deterministic equations and algorithms to discrete science and thoughts is always intriguing and pure fun.

Sorting - A Quicksort Inplace algorithm in Python

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n . Before discussing about the in-place version lets see how its implemented without in-place rearrangements. Here is one such implementation below:

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n^2)
Best Case Performance	O (n log n )
Average Case Performance	O(n log n)
Worst Case space Complexity		O (log n) (for in-place)

The above algorithm uses two new arrays for its implementation and thereby does a bad job with regard to space complexity. Here is an inplace quicksort algorithm implementation in Python

If you are interested in a C implementation of the below algorithm see the following link: C implementation of inplace Quicksort.

Quicksort Inplace algorithm in C

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n^2)
Best Case Performance	O (n log n)
Average Case Performance	O(n log n)
Worst Case space Complexity		O (log n) (for in-place)

There are implementations of Quicksort algorithm using new new array creation and thereby does a bad job with regard to space complexity. Here is an inplace quicksort algorithm implementation in C. If you are interested in the implementation in python please click the following link: Python implementation of inplace quicksort

Printing level order algorithim

Two types of search are popular in Binary Tree. Breadth First Search (BFS) and Depth First Search (DFS) . Printing the level order is slightly complex since you need to keep track of the height of the particular node to implement the level order printing. Its a kind of BFS node tracking using the height.
Here is a c implementation of printing level order for a Binary Tree.

Binary Tree - Depth First Search Algorithm

Here is a Binary Tree search algorithm implementation in C for Depth First Search algorithm. The preOrder , inOrder and postOrder implementation are done thru recursive call approach.

BubbleSort algorithm in python

Although Bubblesort algorithm is not an efficient one with respect to space and time complexity, its one of the easiest one to understand. Here is a bubblesort implementation in python

Asymptotic Complexity
Time Complexity	Space Complexity
n^2	1

If you would like to see how this implentation would look like in C click the following link: Bubblesort implementation in C

String to Integer Implementation

The logic for doing String to Integer implementation is rather simple. Mostly handling the corner cases is what one needs to be care full about. The code should be followed by unit tests to check the validity will help to establish credibility for the code.

Quicksort inplace algorithm in Java

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n . Before discussing about the in-place version lets see how its implemented without in-place rearrangements. Here is one such implementation below:

Asymptotic Complexity
Time Complexity	Space Complexity
n log(n)	1

If you are interested in a C implementation of the below algorithm see the following link: C implementation of inplace Quicksort.

If you are interested in the implementation in python please click the following link: Python implementation of inplace quicksort

Insertion Sort in Python

Here is an implementation of Insertion sort in python.

Here we take the first element compare with zeroth element and swap values if the zeroth element is bigger. Now we take the second element. Compare with first one swap values if first one is bigger. Then again we compare the first value again with zeroth and swap if zeroth value is bigger. Like that
we do till end of the array.

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	Swaps: O (n^2) Comparisons : O(n^2)
Best Case Performance	Swaps: O (1 ) Comparisons : O(n)
Average Case Performance	Swaps: O(n^2) Comparisons : O(n^2)
Worst Case space Complexity		Total: O (n) Auxiliary : O(1)