Author Archives: AlgoPill

Horner’s Rule

August 27, 2011 – 5:08 pm

Problem Statement: Find the value of a given polynomial P(x) = a0 + a1x + a2x2 + a3x3… an-1xn-1 for a given value of x

Solution: Horner’s rule can be used to solve this problem in O(n) time where n is the maximum power of variable x in the polynomial.

this method works by evaluating the polynomial in a different form which requires reduced number of operations.

P(x) = a0 + a1x + a2x2 + a3x3… an-1xn-1

P(x) = a0 + x(a1 + x(a2 + x(a3+… +(an-2+ xan-1)  … )))

The input to this algorithm is an array of co-efficient  in the polynomial, i.e. coeff[i] = ai, and a number c which is the given value of x at which we have to calculate P(x)

The algorithm maintains a loop invariant which we state below.

Loop Invariant: at the start of the loop the variable result contains a partially calculated polynomial Qi(x)

Qi(x) = ai+1 + ai+2x + ai+3x2 ….. an-1xn-2-i

Intialization: i=n-1

Qn-1(x) = 0

Maintenance:

Qn-2(x) = an-1

Qn-3(x) = an-2 + x*an-1

Qi (x) = ai+1 + ai+2x + ai+3x2 + …. an-1xn-2-i

Qi-1(x) = ai + x*Qi(x)

= ai + ai+1x + ai+2x2 + ai+3x3 + … an-1xn-1-i

= Qi-1(x)

Termination:

Q-1(x) = a0 + a1x + a2x2 + …. an-1xn-2 +1

Q-1 (x) = a0 + a1x + a2x2 + …. an-1xn-1

which is equivalent to P(c) if we substitute  c for x.

Thus this algorithm correctly calculates

Posted in Uncategorized | Comments (0)

Number of Inversions

August 27, 2011 – 4:22 pm
Problem Statement: Given a list of numbers count the number of inversions.
Solution:Modified merge sort is used to find invesion in a list of numbers.
this resursive solution can be written as follows
inversions(i,j) = inversions(i,k) + inversions(k+1,j) + merge(i,k,j)
where
inversions routine sort subarray [i,...,j] and  returns number of inversions in it.
and k = floor((i+j)/2)
merge procedure can be easily explained as follows.
Let A be a sorted sub array {2,6,7,9}
Let B be a sorted sub array {1,3,4,10}
number of inversion in concatenated array AB i.e {2,6,7,9,1,3,4,10} can be found in linear time.
We merge the two list using same method as used in merge sort and when we pick element from second list we increment
number of inversions by the number of element remaining to be processed in first list. Let current item in first b c1
and current item in second list be c2
if B[c2] is less that A[c1] then all remaining elements in A ( from c1 to end} are larger than B[c2] because A and B are sorted lists
but as B[c2] comes after all remaining elements in A all those  elements are inversions of the AB combined list.
Posted in Uncategorized | Comments (0)

Recursive Insertion Sort

August 19, 2011 – 6:04 am

Problem Statement: Sort a given list of numbers

Solution: We use a recursive variant of insertion sort to solve this problem. the main sort function recursively sorts first n-1 elements and inserts nth element in its proper location using insert routine. Running time of this algorithm can be expressed as T(n) = T(n-1) + O(n) OR, T(n) = O(n²)

Posted in Uncategorized | Tagged , | Comments (0)

Generate Valid Parentheses

March 15, 2011 – 6:22 pm

Problem Statement: Given n pairs of parentheses, generate set of all valid parentheses permutations

Solution: Given n pairs of parentheses this solution uses a simple logic that  left parentheses can be place in the string as long number of left parentheses used so far is less than n, and a right parentheses can be place in the string as long as number of right parentheses used so far is less than the number of left parentheses used so far.

Posted in Uncategorized | Comments (0)

Number of Valid Parentheses Permutations

March 14, 2011 – 6:23 pm

Problem Statement: Given n pair of parentheses find how many different valid combination of parentheses are possible.

Solution: In order to under solution to this problem lets take an example. Assume that we are given three pairs of parentheses. A valid permutation of these parentheses will always have left number of left parentheses more than or equal to number of right p arentheses. Lets see an example

Let the pair [l,r] represent number of left parentheses and number of right parentheses encountered in the permutation so far.

a. Valid Parentheses ,

( [1,0]      ( [2,0]      ) [2,1]     ) [2,2]      ( [3,2]      ) [3,3]

b. Invalid Parentheses

([1,0]   )[1,1]   )[1,2  invalid    ]   (    (    )

Above examples demonstrate that for a permutation to be valid number of left parentheses in the permutation at any position should be more than or equal to number right parentheses

Now lets try to find out all possible permutation for 3 pairs of parentheses.  It can be noted that all permutations will have six characters , and any character can be either ‘(‘ left parentheses or ‘)’ right parentheses as long as it does not violate above property, let us represent left parentheses ‘(‘ by 0 and right parentheses ‘)’ by 1. So that a string of zeros and ones represent a permutation of parentheses

                                    

As you can see in the above tree that the tree is binary and that tree stops branching as long as number of left parentheses becomes 3 which is equal to the number of pairs of parenthesis. Thus number of valid parentheses is equal to number of node which have l ( number of left parentheses)  equal to n (number of pairs of parentheses). and for all other cases we have two choices we increment l and if r < l we can increment r also where r is number of right parentheses. The presented algorithm does exactly that

Posted in Uncategorized | Comments (0)

Modified Preorder Traversal (Recursive)

March 14, 2011 – 12:39 pm

Problem Statement: Given a binary tree find its Modified Pre-order Traversal.

Solution:  Modified Preorder Traversal (MPTT) is an implementation of Nested Set Model. In this implementaion tree is traversed in preoder traveresal, i.e. root first then , its left child and finally its right child. In MPTT each node is visited twice and two numbers associated with each node. If first number is n then second number is [n+(2*no_children)+1].  Thus while numbering a node N, with set the first number to x, then we visit all its children from left to right assigning , first and second numbers to each and keep incrementing the counter in the process, then we visi the node N again and assign the current value of counter as second number. In the given algorithm. We first start with number1 with node root and assign root.start=1, then we recursively number its left children and the its right children , then we come back and set root.second to current value of the counter.

Posted in Uncategorized | Comments (0)

FizzBuzz

March 13, 2011 – 6:24 pm

Problem Statement: Given a positive integer n, for all numbers between zero and n (inclusive) , output “Fizz” if number is a multiple of three, output “Buzz” if number is multiple of five, output “FizzBuzz” if number is a multiple of 15, otherwise output the number itself.

Solution: Solution is very simple. The only trick is to first test for 15 then for 5 and 3 because 15 is also a multiple of 3 and 5 and therefore all multiples of 15 are also multiple of 3 and/or 5.

Posted in Uncategorized | Comments (0)

Lexicographic Permutations (Iterative)

March 13, 2011 – 2:12 pm

Problem Statement : Given a string of characters generate all permutations of string in lexicographic order.
Solution: This algorithm has been taken from http://compprog.wordpress.com/2007/10/08/generating-permutations-2/

This algorithm will generate all permutations of a string in lexicographic using an iterative algorithm. The input string to this algorithm must have all the characters in lexicographic order. For example, if we want to generate permutations of “bcad” string. Then input string should be “abcd” because a<b<c<d. This algorithm cannot handle duplicate characters so all characters must be unique.

The key routine of this algorithm is the routine “next”. Given a permutation “next” routine will find another permutation that comes next in lexicographic order.  This algorithm uses “next” to generate next permutation iteratively until all the characters in the string are in reverse lexicographic order. For example give “abcd” string , it will generate all permutaion until we reach “dcba” since this is the last permutation in lexicographic order. Now the working of “next” routine  is explained below with an example.

consider a permutaion of “abcdefghij”      p1  =  ”chdafijgeb”

now lets find out next permutation in lexicographic order.

Step1. Starting with last char i.e. ‘b’ , decrease  the counter as long as characters are in increasing order and find first character that breaks this trend. In this example we started ‘b’, thus ‘e’>’b',  ’g'>’e’  ,  ’j'>’e',  but ‘i’<’j’ , thus the character that break this trend is ‘i’.

Step2 . Find the largest element starting from last element i.e. ‘b’ such that it is smaller than the element found in last step i.e. ‘i’. ‘b’<’i', ‘e’<’i',’g'<’i',’j’ > ‘i’ , therefore the character is ‘g’;

Step 3  Now swap ‘g’ and ‘i’; after this step we get    p1′  =  ”chdafgjieb”;

Step 4 now reverse the string starting after ‘g’ to the end. which gives us p1”  = “chdafgbeij”, this gives us smallest string that is larger than the input string and thus next in the lexicographic order

Posted in Uncategorized | Comments (0)

Permutations (recursive) 2

March 13, 2011 – 12:29 pm

Problem Statement:Given a string find all permutations of string. It can be assumed that string does not had repeated characters.
Solution: This is a simple algorithm for generating permutations. It uses a recursive construction. There are two points to be understood in order to this understand this algorithm
1. The recursive construction
consider finding all permutions of the string “abcd”, all permutations of this string are union of following
permutaion(“abcd”) =
1. “d” + permutations(“abc”)
2 “c” + permutations(“dab”)
3 “b” + permutaions(“cda”)
4 “a” + permutations(“bcd”);
where “+” is concatenation operator
the permutation of “abc”, “dab”,”cda”,”bcd” can be calculated similarly.

2. Rotate part
as noted above in order to generate permutations we place all characters one by at position 0. The first case where “d” is moved to first place by rotating the string such that every character’s index is increased by one and last character i.e “d” is moved to first. At second step characters are moved by one place which bring “c” in first place. This is done four times since the length of string is four.

This solution does NOT generate permutations in lexicographic order and it does NOT take care of repeated characters.

Posted in Uncategorized | Comments (0)

Post-Order Tree Traversal (Iterative)

March 6, 2011 – 5:48 pm

Problem Statement: Given a binary tree find its post order traversal.
Solution: In post-order traversal of a node’s right child is printed first then its left child and then the node and this order must be valid for all subtrees in the tree. It can be noticed that post-order traversal is reverse of the pre-order traversal of the with right children swaped with left children of the tree.
Following algorithm makes use of stack to first find pre-order traversal iteratively and it treats right child as if it were the left child , this will produce a pre-order traversal which can then be reversed to produce correct post-order traversal of the input tree . We start with having root node at the top of the stack, we drill down the tree rooted at the node at top of stack along the right most side , and output each node we encounter them. We then start poping until we find a node that has a left child. This left child is pushed onto the stack and above procedure gets repeated for subtree rooted at this node. Finally we reverse the traversal to give correct post-order traversal.

Posted in Uncategorized | Comments (0)