Number of BST with n keysf(n) = [ \sum_{ i=1 to n} f(i-1)* f(n-
i) ]
Root node can be any of n keys. if it is ith ney in ascending order,
it has i-1 keys to left and n-i keys to right.
Can any one explain how/Why is it equal to catalan number?
-Thanks
Bujji
On Aug 1, 1:08 pm, Manjunath
You can use count sort or radix sort. Both are of O(n) as running time
complexity.
You can refer to the book by Introduction to Algorithms by Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
--
You received this message because you are subscribed to the Google Groups
Let us assume that the input data-structure is a matrix G[1..N;1..N]
of dimesion N*N matrix where G(i,j) = 1 if i !=j and i has won, 0
otherwise.
Note that the required sequence cannot contain 1 as 0th player does
not exists
Following algorithm may be used.
For i:=2 to N, do:
{
if ( ( G(i ,
Sub-Module: Permutation (word W)
{
Generate all the unique permutations of W taking all the letters of
W
}//End of Sub-Module.
Now you can use the sub-string matching problem for the two strings.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
@Ram and Nikhil
What kind of traversal you will use to visit each node.
How come you will get to know about teh number of nodes at each level that
needs to be connected.
RK
On Sun, Aug 1, 2010 at 2:56 AM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
@Ram Kumar: Yes. Simple and affective.
Just
You can refer the following algorithm
Let the elements be in the form of an array A[1...N]
1. Sort all the elements of A(This can take at least O(n) time).
2. For i=1 to N, do:
while( ( i+1 = N) AND (A[i] == A[i+1]) )
remove A[i+1].
3. END
--
You received this message because you
@Anand,
It looks like your algorithm takes O(log N ) time.
Repeatedly choosing one half or the other half.
Similar to binary search.
Please correct me if I am worng.
-Thanks and regards,
Bujji.
On Jul 27, 12:29 am, Anand anandut2...@gmail.com wrote:
*
*
*Using partition
Counting Sort.
On Mon, Aug 2, 2010 at 6:15 AM, Praveen praveen.yarlaga...@gmail.comwrote:
There are N numbers in an array and each number is in the range [0,
n*n -1]. Is there a way to sort the elements in O(n)?
Thanks,
Praveen
--
You received this message because you are subscribed to
you may also want to see
http://www.rawkam.com/?p=351
http://www.rawkam.com/?p=351-Kamal
On Sun, Aug 1, 2010 at 7:40 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote:
On Sun, Aug 1, 2010 at 5:20 PM, Pramod Negi negi.1...@gmail.com wrote:
driver(Tree *root)
{
node *array = malloc(sizeof(node *) *H ); /* take the height node
pointer array. this will act as source pointer of each list */
makeList(root, 0, array)
}
makeList(Tree *root, int level, node *array)
{
if(! root) return ;
/*do a Depth traversal and store the list
the calatan number can be derived using the code given above.. plz confirm
by using wiki..
try 2 find derivation of catalan number..
On Mon, Aug 2, 2010 at 11:34 AM, bujji jajalabu...@gmail.com wrote:
Number of BST with n keysf(n) = [ \sum_{ i=1 to n} f(i-1)* f(n-
i) ]
Root node can
Median can be computed in O(1) time after the element is inserted into
existing DS.
But inserting a new element in to the AVL takes O(log n) time.
Overall it takes O(log n) time including inserting new element and
median computation.
Can median be computed in O(1) time on the fly?
On Jul 28,
Here is simple code to generate permutations
#include stdafx.h
#includestdio.h
int Permute( char *, int);
int PrintArray();
int swap(char *, int);
char A[]={'1','2','3','4','5','6','7','8'};
main( )
{
Permute(A,sizeof(A)/sizeof(char));
return 0;
}
int Permute(char *
try this code guys
i think there is redundancy in condition checking.
if so correct me...
#includestdio.h
struct node
{
int data;
struct node* left;
struct node* right;
struct node* sibling;
};
void connectHorizontal(struct node* root)
{
if(root == NULL)
return
i dont think counting sort can be applied since its time cpmplexity is
O(n+k) where numbers are in the range 1...k and here k=O(n^2). so the
overall complexity will again go to O(n^2) :(
On Mon, Aug 2, 2010 at 10:22 AM, Apoorve Mohan apoorvemo...@gmail.comwrote:
Counting Sort.
On Mon,
This is a great solution.
On Jul 28, 3:09 am, janak chandar...@gmail.com wrote:
How about keeping heap?
Have two heaps 1. max heap and 2. min heap
keep them equal size all the time and shift top element from one to
other when required...
On Wed, Jul 28, 2010 at 7:46 AM, Gene
@bijju: you are correct. Here goes the code for it.
*http://codepad.org/4UgNpOKH
*
On Mon, Aug 2, 2010 at 7:29 PM, Gene gene.ress...@gmail.com wrote:
This is a great solution.
On Jul 28, 3:09 am, janak chandar...@gmail.com wrote:
How about keeping heap?
Have two heaps 1. max heap and 2.
17 matches
Mail list logo