@senthilnathan : You are right. the growth of number is exponetial
nth Catalan number is approx Cn ~ (4^n) / ( sqrt(pi) * ( n^(3/2) ) ) :
http://en.wikipedia.org/wiki/Catalan_number
so the pruned exponential solution is the best one. We cant find algo any
less than exponential.
On Thu, Jun 3,
I think kaushik's solution of inorder traversal with hare and tortoise
technique should do the trick.
On Fri, May 21, 2010 at 3:48 PM, Koolvord Starbust kolvo...@gmail.comwrote:
Sorry, but.. why don't you..
a) compute the height of each subtree. Recusrively, takes O(n).
b) start from the
Hi ,
To add to your logic, I hope we must also be checking at the precedence of
the first operator that appears after the closing parenthesis ')' before we
can decided if the parenthesis can be removed or not .
On Thu, Jun 3, 2010 at 11:37 PM, Antony Vincent Pandian.S.
sant...@gmail.com wrote:
@jitendra: How can you say that no polynomial algo can be found. I think you
are wrong.
A simple memoized formulation will make this polynomial because of the
optimal substructure..
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science
Yup... That also makes sense
If the precedence of the operator after ) is greater than the precedence of
any of the operators within (), the parenthesis should not be removed..
Thats a nice valid point...
On Fri, Jun 4, 2010 at 11:03 AM, Algoose Chase harishp...@gmail.com wrote:
Hi ,
To
Write a C/C++ console application that connects to a MySQL server and prints
the number of aborted connects using information provided by MySQL's global
variables.
--
With Regards
Ankur Aggarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Believe it won't be simple, since its not following a language like
hierarchy. try to evolve set of solution for 4 from 3 and you will notice
that its not a straight function.
On Fri, Jun 4, 2010 at 1:40 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@jitendra: How can you say that no
@Rohit: you have to visit all valid solutions at least once, (as you are
printing it)
so the lower bound is Cn (nth catalan number)
On Fri, Jun 4, 2010 at 1:40 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote:
@jitendra: How can you say that no polynomial algo can be found. I think
you are
@rohit: Here we have to print not only number of possible valid bracket but
also how they look (eg : ()()() )
If we need to print only number of brackets then then using the recurrence
relation of catalan number we can find it easily.
According to your point, can you suggest a memoization
in quick short each time list is divided into two part ..suppose shorter one
and longer one . it is said that shorting smaller sublist first reduces
stack space . why so ?
thnx
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
Oh i am talking only about printing the total number of solutions...
If you backtrack... Obviously it would not be polynomial
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
if you short the larger one first, then the smaller one will be in the
stack for a long time. Which is wasting stack space.
Now stop shorting and start sorting ! :)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
int Max(int a[],int n)
{
int max;
if(n==1)
return a[0];
else
max=Max(a,n-1);
if(maxa[n-1])
return max;
else
return a[n-1];
}
Hi, the above is a code to find the max in an array recursively. I
int Max(int a[],int n)
{
int max;
if(n==1) ---( 1 )
return a[0];
else
max=Max(a,n-1);
---( 2 )
if(maxa[n-1])
return max;
If I've a string like It is a fine morning, the algorithm has to print
morning fine a is It and not gninrom enif a si tI
The algo has to do this in linear time. Can someone help me out in this
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
If I've a string like It is a fine morning, the algorithm has to print
morning fine a is It and not gninrom enif a si tI
The algo has to do this in linear time. Can someone help me out in this
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
Hi,
I came across this question to find the number of sequences of n
binary digits that don't contain 2 1's in a row. I wanted to know what
exactly this means. Is it like if n=3 then compute all binary numbers
having 3 digits which don't have consecutive 1's 110, 011, 111 ??
If not help me
@Prashant: Are you saying that after the base case has been reached, only
then statements 3,4 will be executed for all the recursive calls?
On Fri, Jun 4, 2010 at 7:52 PM, Prashant Kulkarni prashant.r.k...@gmail.com
wrote:
int Max(int a[],int n)
{
int max;
if(n==1)
loop recurs with array index n,n-1,..,0 as stated in this thread.
will return Max value from array, for (n-1) upon each integer of
iteration n, upon condition present element is larger than previous
element, otherwise, it will return the previous value.
the algorithm seems to provide a
i think the best way to trace is to draw a picture of the stack and put the
values and acc understand the flow
On Fri, Jun 4, 2010 at 7:22 AM, Prashant Kulkarni prashant.r.k...@gmail.com
wrote:
int Max(int a[],int n)
{
int max;
if(n==1)
if u sort the larger one first one then smaller one will be on stack for a
long time on the other hand if u sort smaller one first then larger one will
be in stack for long time. so more space is wasted is 2nd case so we shd
sort larger first. correct me if i am wrong plzzz
On 4 June 2010 18:08,
@divya:make use of bresenham circle drawing algortihm
On Fri, Jun 4, 2010 at 8:42 PM, divya sweetdivya@gmail.com wrote:
. Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
making use of any floating point computations at all. [ This one had
me stuck for quite some time
@divya,in second case longer one will be in stack for shorter time(not
longer)bcoz it will take less time to sort small sequence so stack space for
shorter one will be freed earlier,otherwise that space has to wait for the
longer time
--
You received this message because you are subscribed to
Implement an algorithm to take an array and return same array with only
unique elements in it.(in o(n) time).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from
Reverse the string first and then reverse individual tokens.
So, first we can reverse the whole string as
It is a fine morning gets converted to gninrom enif a si tI and then
reverse each token in the string so that end result would be the desired
result.
On Fri, Jun 4, 2010 at 8:01 PM, Raj N
@rajn.can it be subsequence doesnt have one's too.hence 000,001,010,100 is
required answer.
On Sat, Jun 5, 2010 at 12:13 AM, Raj N rajn...@gmail.com wrote:
Hi,
I came across this question to find the number of sequences of n
binary digits that don't contain 2 1's in a row. I wanted to know
@sharad :does it hav to be inplace solution.
ps:btw are u from MIT AERO DEPT?
On Sat, Jun 5, 2010 at 8:30 AM, sharad kumar sharad20073...@gmail.comwrote:
Implement an algorithm to take an array and return same array with only
unique elements in it.(in o(n) time).
--
You received this
Make a hashmap... Any problem doing that?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the
What precisely did you not understand??
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google
Have you posted the same question twice or i am feeling sleepy?
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are
Exactly that's what you need to do.
--
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
--
You received this message because you are subscribed to the Google
3rd International Workshop on Optical SuperComputing in Bertinoro
(OSC10)
November 17-19, Bertinoro, Italy
http://www.cs.bgu.ac.il/~dolev/OSC10
SCOPE:
OSC, the International Workshop on Optical SuperComputing, is an
annual forum for research presentations on all facets of optical
computing
32 matches
Mail list logo