Hi,
Although, I cannot give you a complete solution right now..I will give you
the following relations (I am not sure If they are correct.discussions
welcome)
T(0, x) = 1
T(x, 0) = 1
T(1, x) = (x+1)
T(x, 1) = (x+1)
T(n, m) = Sum[i=0..n] { T(n-i, m-2) * (i+1) }
If you are looking for a progr
The farthest nodes would be pendant verices...
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, s
I guess it was a slight difference in terminology...you must have then
phrased the question as "almost complete" rather than a complete tree since
you are allowing the last level to be incomplete.
Anyways, If the last level is going to be incomplete, then the observe
this..
sum of the nodes is
1+3
Hi,
I guess he is going by the assumption that the queries will be large
enough that precomputing the all-pairs shortest paths is better.
Anyways..mukesh..this is what you need..
In the place of your output
while(cin.get(c) && c!='\n')
{
cin.unget();
Read the post again...
The adversary then chooses the split up, that is, the part of the
string you've given him that loop
you can only choose the string 'w' (>=n), the adversary can only _CHOOSE X,
Y and Z_ but ofcourse the adversary is restricted by the fact that he had
chosen a 'n' earlier and t
DFS
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more opt
Oooh...I almost forgot to add this..
notice the relation between the proof for part (ii) and the discrete
logarithm problem. The proof is no mere coincidence. This is the reason
behind using primes in encryption schemes that rely on the hardness of the
discrete logarithm problem. This will ensure
In case you are wondering about the part of the proof for k%3<>0, it
goes like this, the given number can be written as 1 + 1000 + 100
+ 10 +..and so on
now if for a given k, if we choose the string of k 1s and try to find
the modulus with each of the terms in the above expression,
for
well...its simple as given in the article..
note that the numbers are all decimal numbers (not binary..in case
misled by just 0 and 1 in the number) therefore
if you have have k copies of 001 and k%3 == 0, then the sum of the
digits is divisible by 3 hence the number is divisible by 3 - The
Standa
Now in the case of non complete BSTs it may run into trouble...I never
handled them. It will work for complete BSTs though as it is. Refer to
a previous thread in algogeeks where i had posted the thread "inplace
sorting" and look at the solution by atamurad for the explanation.
--~--~-~--
Yes...the proof is correct and this is what stone had suggested in his
earlier post.
Consider one "red" sector in the inner disk in each of the 200
different positions, it will match against exactly 100 sectors in the
outer disk since there are 100 of the red sectors in the outer disk.
Similarly f
Its not a question of reversing the hash function but given the key
again you need to be able to retrieve the data in the hash table. If a
random hash function is used every time to index into the hash table
it would not be possible to retrieve the data back cheaply (There have
been attempts to fi
RR* is RR+ is the valid assumption
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email t
sorry
RR* = R+ is the valid assumption
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send ema
Well... I think a hash function is chosen only once for each run of
the program and not for each time a value is hashed. Thereby you dont
have such issues at all.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algo
An unique BST does exist for such an array if you assume the root to
be 1, then automatically you will be able to fix the left and right
children of the root and so on.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
@alfredo:
I dint get this part:
1) Lets say that we have the outer circle painted in the following
manner: 1 red(C1), 1 white(C2), 1 red(C3), etc. We call this sections
(RWR)
2) Then if we have that the inner circle is painted in the same way we
finish.
3) if not then lets say that we have a lea
i am sorry that is a[i] = ++cnt
I made a mistake when pasting the code...
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To un
for(i=1; i<=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi && a[p]>a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are
yes...but that does not mean that you can assume that the 100 reds and
100 whites are contiguous blocks.It just says that the outer disk has
a sum of the 100 reds and 100 whites and does not say that they are
contiguous.
--~--~-~--~~~---~--~~
You received this mess
yes...but you can sort without constant space using the posted algorithm
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To uns
#include
#include
#include
#include
#define MAXN 2000
int a[MAXN];
int cnt = 0;
int log2n;
int n;
void populatetestcase(int i)
{
if(i*2<=n) populatetestcase(i*2);
a=++cnt;
if(i*2+1<=n) populatetestcase(i*2+1);
}
int calc_x(int i)
{
return (int)log2l((double)i);
}
int calc_m1(int i)
{
return 1
This code takes O(logn) steps. The first solution proposed takes
O(number of 1s)steps(which is less than O(logn) average case), the
other approach is to some of the bit hacks in the link, there are
methods to do that in O(loglogn) if n is fit within the word length of
the processor though they are
Find the longest common prefix in the path from the root to nodes u and v
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To un
The standard link
http://graphics.stanford.edu/~seander/bithacks.html
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubs
How would the median algorithm get the top k elements?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this
Yes..but in the worst case you could partition the list into 1 and
n-1...we cannot say this deterministically. The average case is O(n)
but worst case would still be O(n^2)
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Gro
well the requirement is only to sort the array
Array repr: 9,6,21,1,7,16,36 (index starting from 1)
Now on sorting the array in place gives: 1,6,7,9,16,21,36
is a perfectly valid answer to the problem.
No one is going to look at the result as a BST, it is going to be
viewed as a sorted array.
If the DFA works then it can be converted to a regular expression
using standard techniques like the one described in
http://www.cs.colostate.edu/~whitley/CS301/L3.pdf
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
A DFA is possible I guess which is interesting, see if the following
DFA works, since the existence of the DFA relates to the existence of
a Regular Expression Describing the language
State/Input 01
q00 q10 q01
q10 q20
radix sort would take O(nk) time in terms of the number of digits. And
infact sorting is a much bigger problem than what we need. All that we
need is the top k elements of an n element list.
A strategy would be to use fibonacci heaps that have O(1) Decrease
key. You can construct a heap out of t
I agree with you completely but for the problem that I posted it is
enough that we have O(n) in accessing the elements in order. Your
solution does better by calculating every element in O(1) time. The
key now is to do the actual sorting with this method
--~--~-~--~~~-
@atamyrat:
There is actually a simpler logic to perform inorder traversal in
constant space and O(n) time. Just keep track of the previous node you
have visited and the current node. Now If you are coming from the top
go left. If you are coming from left down go the right. If you are
coming from
The question is not to print out a sorted array which we can easily do
by inorder traversal. The question is to store the sorted array in the
same array with constant extra space.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Goo
the LP:
v1 <= 40
v2 <= 30
v3 <= 20
v1 + v2 + v3 <= 60
v1*2 + v2*1 + v3*3 <= 100
Maximize: v1*1000 + v2*1200 + v3*12000
Here v1, v2 and v3 are the volumes of the materials 1, 2 and 3 to be taken.
--~--~-~--~~~---~--~~
You received this message because you are subs
To make things more easier just assume a complete binary search tree
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubsc
And ofcourse radix sorts take o(nk) ...There is an O(n) algorithm for this
problem in constant space
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge
A heap is a much more relaxed data structure than a binary search tree. Note
that in a heap there is only relation between the parent and the siblings.
Whereas in a binary search tree there exists a relationship between siblings
also.
--~--~-~--~~~---~--~~
You recei
A shot at an O(nlgn) algorithm.
Do a sweep line from top to bottom. Only look at the events when a new bar
is introduced (this is accomplished by sorting the bars based on height).
When a new bar arises, if there exist values immediately to the left and
right of the bar just merge them into a new
Given a binary tree in an array in the standard representation with left and
right nodes being stored in 2i and 2i+1 for a node at position i. Assuming
that the array indices start at 1.
How do you perform a sort of the array with constant space and O(n) time.
--~--~-~--~~~
I give a try to start at an O(mn) algorithm (where m is the size of the
longest bar)
Let Maxrect[i][j] denote the width of the maximum rectangle ending at the
ith position of height j
if(height[i] >= j)
Maxrect[i][j] = Maxrect[i-1][j]+1
else
Maxrect[i][j] = 0
We can traverse this array to find
I give a try to start at an O(mn) algorithm (where m is the size of the
longest bar)
Maxrect[height][width] =
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email
Another variant...(or rather wanted to say in my previous post)
How do you find a maximum square of all ones in a binary matrix of 0s and
1s?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To
Yes, I agree that the logic that I gave only works for maximum squares from
[1][1].
On an interesting extension to the problem, special case that to squares of
maximum sum.
How to find the Square of Max sum in a 2D matrix consisting of both
+ve and -ve numbers,,,
--~--~-~--~~--
use the following logic to create a table of sums (assume that the given
array is a):
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
sum[i][j] = 0 for the boundary cases like i = -1 or j= -1
Then you can traverse the sum array to find the maximum sum.
Overall O(n^{2})
--~--~---
Have a look at this link
http://mathworld.wolfram.com/SylvestersFour-PointProblem.html
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegrou
The question as it seems is known as the "Sylvesters Question"
I quote from the paper "Random points, convex bodies, lattices" by Imre
barany.
"Show the chance of four points forming the apices of a reentrant
quadrilateral is 1/4 if they are taken at random in an indefinite plane". It
was understo
yes..thats the reasoning that i had too but let us see if anyone else sees
some thing fishy in our reasoning
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email t
(A) Hull is _not_ a quadrilateral if the 4th point lies inside the
triangle AND _many_ other points. For instance, extend the
perpendicular bisector (just as a sample case) of any one side beyond
the vertex of the triangle that it passes through.
The same triangle reasoning holds good here too rig
why is it 1 - (area of triangle)/(area of Sq.)?
why do we need a square since what would happen is that the 4th point can be
anywhere in the space but the area of the triangle is bounded. The
probability of choosing a point outside the triangle would be 1 (bound - not
exact by reasoning as in (3))
Well that is true...and at the outset the sum may appear to be 198+49 but
the truth is that if we eliminated 49 tl groups then we would not have had
to ask the 198 questions in the first place remember. The worst case
calculation of 100+50+25+(12+1)+... assumes that no group gets eliminated in
each
So it was a good idea to sign off my message saying "I am not sure if the
exact calculations are correct for each round but overall this is the logic"
:D.
True..so the first round does take 100 questions, the second round takes 50
questions and then 25 and then so on...
This results in 100 + 50
Hi,
Note that the problem is solved if you find one honest professor then you
can ask him about all the other professors and solve it 99 questions from
there on. The problem is to find one honest person in 99 questions.
This can be done as follows,
Divide the professors into groups of 2.
I dint fully get what you meant by points being perpendicular to a
planemy guess is that if you work through
http://en.wikipedia.org/wiki/Rotation_matrix
you will be able to find light.
It would help if you more clearly stated the problem.
--~--~-~--~~~---~--~
It does depend on the size of the problem you have in mind. Tries can be
expensive for names depending on the sparseness of the data set, you may
waste a lot of pointers. If you use B-Trees they may be good in such cases.
B-trees are generally a bit better when it comes to data stored in a disk
wit
On 2/14/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
>
> Hello,
>
> There is a problem in the algorithm book I'm trying to digest, that
> I'd like to discuss a bit. So, first thing first, let me state the
> problem :
> find(A, x)
> sort(A)
> i = 1
j = n
while (A[i]+A[j] != x)
>
Split the marbles into sets of 4 each
Compare the first and second sets
If both the sets are equal (the problem is in third set)
{
choose 2 of the marbles in the third set
compare with 2 marbles from the first set(which we know are good)
if comparision is equal
{
compare one of t
yes..i agree with rajiv..you seem to be generating combinations rather
than permutations..the algo that i have given generates permutations
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To
permutation (List resultSoFar, List remainingElements)
{
if(length(remainingElements)=0)
return;
for i = 1 to length(remainingElements)
{
print resultSoFar+remainingElements[i];
permutation (resultSoFar+remainingElements[i],
remainingElements-remainingElements[i]);
Hi,
You can try a similar technique...
Start at an arbitrary endpoint,
Set the number of open chords to zero,
Set the number of intersections to zero
Traverse the endpoints along the circle in one direction (made
possible by sorting radially)
{
If the endpoint is one that closes a
At first glance, I would say do an incremental search for the nth
fibonacci number...i.e set n=0, then n=1, n=2, n=4, n=8, n=16
etc..once the nth fibonacci number you can do a similar search within
the interval n/2 to n...
Ofcourse using the golden ratios to get the nth fibonacci number
May be not
You could use a B-Tree or even a simple binary tree to index into the
array, but the space will be doubled (it is justified if you store
some other object in the array other than integers).
On 11/17/06, Nik <[EMAIL PROTECTED]> wrote:
>
> Hi,
>
> I have an array in which elements are present .
> T
-- Forwarded message --
From: Karthik Singaram L <[EMAIL PROTECTED]>
Date: Nov 12, 2006 4:58 PM
Subject: Graph Partitioning
To: algogeeks@googlegroups.com
Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a
Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a graph whose nodes are bit vectors of length "n" (the graph
contains all 2^n nodes), the edges are defined to be connecting all
the pairs of nodes which differ only at one bit positi
I am not sure but an arbit way to do this would be to find
(totalsum/k) and do a bin packing for each of these , of course we
would be left with a few elements, we can put them in the bins with
max.slack space...It would be approximately correct I guess though not
sure.
Hope it helps
karthik
On
I am not sure If I got the question right
1
4
0 3 1 2 3
1 1 0
2 2 0 3
3 2 0 2
1 2
Isn't the answer that camarade 1 talks to camarade 0 who inturn talks
to 2. Isnt this shortest path algorithm? isnt Djikstra O(VlogV) which
seems feasible for the problem rite?
On 10/30/06, Pradeep Muthukrish
His code works because he calls the isIsomorphic on the left and right childs without comparing their values, which you were doing in your code before calling the isIsomorphismyour code:if(node1.leftChild.value
== node2.leftChild.value) isIsomorphic(node1.leftChild, node2.leftChild)his code:
if (node1.value != node2.value) return false; /* Accessing
node1.value and node2.value without check for nulls*/ if(node1 != null && node2 != null)
{ if(node1.leftChild.value == node2.leftChild.value)/* Null problems with left and right child*/ isIsomorphic(node1.leftChild, node2.leftChild)
/* Assume inp is the given array*/static int bitmap[N][N];int lengths[N];int currentBitmap = -1;int active = 1;int lastPos;for(i=0;i{ if(inp[i]==1) { currentBitmap++;
active=1; lastPos=i; } if(active==1) { if(bitmap[currentBitmap][inp[i]]==1) { active=0; lengths[currentBitmap
Let us say we call the following with the roots of both the treesalgo: checkIsomorphism (node1, node2){ if(node1==NULL && node2==NULL) return 1; if(node1==NULL) return 0; if(node2==NULL) return 0;
child11=node1->left; child12=node1->right; child21=node2->left; child22=node2->righ
Hi guys, A rather different approach to the problem The idea is that the number is appearing more than N/2 times is the majority. 1. Pair the consecutive elements like 1st an 2nd element, 3rd and 4th and so on
2. Now if both elements in the pair are the same choos
Wont this algo have complexity O(n lgn) whereas a simple linear search would have O(n) and it would suffice for the problem
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this grou
yes u r rite. I was trying to force the usage of BFS but it looks to perform very very bad
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@goog
Try this variation
In the previous algorithm if i am correct the complexity is O(n), that
itself shows that an important step is missing somewhere. well this is
my guess about the algorithm. check if it works. I do not think this
is exactly the standard Bentley-Ottmann
Algorithm
The precondition
of course the time complexity could be substantially reduced using the
flow model of the problem.l\
On 4/26/06, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
> Hmmm.. Interesting
> Just in case someone does want to use BFS and does not really care
> about the time complexity,
>
Hmmm.. Interesting
Just in case someone does want to use BFS and does not really care
about the time complexity,
then you could do BFS to get all the Paths ( do not remove them as
soon as you get them )
For example in the graph in the previous discussion, BFS would give
S37F, S345F and S267F
You could do the following things:-
1. Try using a file to store all the intermediate results and the
final output, rather than an array list or other class which stores
the data in the main memory. This would mean no usage of the standard
JAVA classes and low level programming but might just wo
This is the problem of dividing a set into two such that the sum of their differences is minimum.This can be solved using dynamic programming as follows:
algo:
1. Create an array of size L say Arr[L] and initialize to zeroes
2. Put Arr[0]=1
3. For each program Pi
Scan the array Arr from t
Thats the solution all right!!!
Hi Prunthaban is correct!!!
The proof goes like this
First take what he said as premises P(n) of a mathematical induction
"With n ones..
1. Use first n-1 ones to reach 2^(n-1) - 1
2. Set 2^(n-1) th one.
3. Reverse the first step.[So the premise states that we can make the first (n-1) ones 0. As
Yes you are correct!!!
I have wrongly set bit 2 without setting bit 1
Regards
Karthik
Exactly correct!!!
But for the proof and solution to be complete, we need to analyze this
for 7 the answer you have is dp[3]=3*dp[2]+1=3*[4]+1
Now can you see that for dp[2], the number of steps would be
000
010
011
That would be only 3 steps so dp[2] is only 3 . Am i correct?
Regards
karthik
Hi,
Well u state that
"With n ones..
1. Use first n-1 ones to reach 2^(n-1) - 1
2. Set 2^(n-1) th one.
3. Reverse the first step.
4. Now use the n-1 ones to set the next 2^(n-1) - 1 ones!"
According to this logic, you have set the 2^(n-1)th one alone with n ones
Now check if your logic is
Hi,
I am sorry for this late reply. The problem is more beautiful than this. First a small correction to your solution ( I hope you dont mind that :) )Look at this after setting the 2^(n-1) th one , You are left with only (n-2) ones so how you can only travel next 2^(n-2)-1 steps.
Having said
A clue ( The solution is obviuosly brute force, but look at the two optimizations that reduce the search space by ( n!*(n-1)! ) )-karthik
Hi, I am the guy who set that question :D Look at the huge amount of theory available on Latin Squares. In case you still are not able to get the solution just post it again and I will reply. -karthik
I solved this problem ( A very very interesting DP solution I guess )The key to the solution is First try to Prove that the last bit can be set using only 15 onesand you will get the solution.Keep thinking!!!
( A clue :- use Mathematical Induction for the Proof and the DP follows)-karthik
Hi, Each problem will have a Time Limit like "write an algorithm tosort an array" ( Time Limit : 5s ) ( Memory : 1Mb ) ( Input size : 20 integers). Now the rules say that you have to code a sorting solution that runs within this time limit, no need any optimizations. The point is that we are
88 matches
Mail list logo
