[algogeeks] Re: Is there any algorithm for checking whether two vetices are k-connected ?
On 12/6/06, jackyy [EMAIL PROTECTED] wrote: Let G = (V,E) be a directed graph and s and t be two specific vertices in G. We say that s and t are k-connected if there are at least k edge-disjoint paths between s and t. Therefore, is there any algorithm to decide whether s and t are k-connected? Can you explain the algorithm in details? You can run Maximum flow algorithm on graph, with source as s and sink as t. Assign weight 1 to all edges. Maximum flow from s to t means number of edge disjoint paths from s to t http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=maxFlow atamyrat --~--~-~--~~~---~--~~ 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 options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: My friend have a strange question, please help me to answer..
On 12/6/06, jackyy [EMAIL PROTECTED] wrote:
My friend has the following idea to get an algorithm for finding a
shortest path tree on
a graph whose edges may have negative length (but with no negative
cycle):
(i) Examine the edges and find the edge e with the most negative
length.
(ii) Add |ℓ(e)|, the absolute value of the length of e, to the length
of every edge.
(iii) Run Dijkstra's algorithm on the modified graph to find the
shortest path tree and return
it as the solution of the original graph.
Do you think his idea works?
I do not think so. However, I cannot raise any counter example yet. Can
you help me to think one?
Here it is:
n=3
V = {1,2,3}
E = { (1,2,10), (1,3,7), (2,3,-4) }
source = 1
We add 4 to each edge and our modified graph becomes:
E2 = { (1,2,14), (1,3,11), (2,3,0) }
Now lets find shortest path from 1 to 3.
On our original graph, shortest path is 1-2-3, 10+(-4)=6
(Dijkstra will calculate it as 7, which is wrong)
On modified graph, 1-3 (11) is shorter than 1-2-3.(14+0)
atamyrat
--~--~-~--~~~---~--~~
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 options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Problem
On 11/7/06, Malay Bag [EMAIL PROTECTED] wrote: I did not get the point:- we must calculate width and height of all of rectangles that can cover this 4 rectangles and it's area become minimum can you give some example? I think this problem is from IOI95 http://olympiads.win.tue.nl/ioi95/task/pack.html On 11/7/06, mohamad momenian [EMAIL PROTECTED] wrote: No they can't over lap thank you for your attention On 11/7/06, shisheng li [EMAIL PROTECTED] wrote: Can the 4 overlap? From: algogeeks@googlegroups.com [mailto: [EMAIL PROTECTED] On Behalf Of mohamad momenian Sent: Tuesday, November 07, 2006 4:09 PM To: algogeeks@googlegroups.com Subject: [algogeeks] Problem Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and the we must calculate width and height of all of rectangles that can cover this 4 rectangles and it's area become minimum and we can place 4 rectangle vertically or horizontally in the result rectangle --~--~-~--~~~---~--~~ 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 options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Nesting of comments in C
#includestdio.h
int main()
{
int allowed=1;
/* /* */ allowed=0; // */
printf( allowed ? yes\n : no\n );
return 0;
}
Above code is not correct ANSI C code, but I think, you can
compile it with most of compilers and check if it supports nested comments.
For example, this code compiles with GNU C Compiler and prints no.
If you want plain ANSI C code, here it is;
#includestdio.h
int main()
{
printf(no, nested comments are not allowed!\n);
return 0;
}
regards,
--~--~-~--~~~---~--~~
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 options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Nesting of comments in C
#includestdio.h
void main() {
int allowed=1;
/* /* */ allowed=0; // */
printf( allowed ? yes : no );
}
please correct me if there's smth i missed.
atamyrat
On 9/23/06, MM [EMAIL PROTECTED] wrote:
How do you write a C program which when compiled and run, prints out a
message
indicating whether the compiler that it is compiled with, allows /* */
comments to nest?
--~--~-~--~~~---~--~~
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 options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Need an algorithm to find the missing numbers.
On 8/24/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
This is a very old problem in this group.
The solution is simple. Here is an example
{1,3} missing 2
1 XOR 3 XOR 1 XOR 2 XOR 3 = 2
Please note that you need to find missing numbers, not missing number.
--~--~-~--~~~---~--~~
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 options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Is there any better solution than 0(nlgn) ?
On 8/4/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
1 #include stdio.h
2
3 int main() {
4
5 int A[] = {8,5,4,2,9}, B[] = {1,2,3,4,6};
6 static int fo[10] ,i,ret = 0 ; /* max value is stored in A
which is 9
7if we wouldn't know this, we'd
nee to rely
8on INT_MAX or some other shit */
9
10 for (i = 0; i 5; i++)
11 fo[A[i]] = 1;
12
13 for (i = 0; i 5; i++)
14 if (fo[B[i]])
15 ++ret;
16
17 return printf(%d\n , ret);
18 }
Just out of couriostiy... What's the complexity of the above code?
O(2n) ?
Memory: O(MAXINT)
Time: O(n+m)
Where MAXINT is maximum possible element of array,
n and m, sizes of arrays
--~--~-~--~~~---~--~~
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 options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Bubble breaker
On 8/4/06, ridvansg [EMAIL PROTECTED] wrote: Hi, Lately I saw an interesting game and wonder is there a good algorithem to find the best solition. You have 5 type of bubbles in a matrix. You can select 2 or more neighboring bubbles with the same color and remove them. The bubbles are neighboring if they have common border.(no diagonals) If a column of bubbles disappears the matrix is reduced to a matrix without this column. Am,n - Am,n-1. Do you mean SameGame? http://en.wikipedia.org/wiki/SameGame The best solution is the solution removeing max bubbles. I will be happy to see a solution. This is NP-Complete problem. http://theory.lcs.mit.edu/~edemaine/clickomania/ --~--~-~--~~~---~--~~ 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 options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Is there any better solution than 0(nlgn) ?
On 8/1/06, sathiya narayanan [EMAIL PROTECTED] wrote:
Given: 2 Arrays of N and M numbers in size.
We have to find how many common numbers are available ?
Eg: A={8,5,4,2,9}
B={1,2,3,4,6)
Solution is:2
Common elements are {2,4}
What i wll do is Sort the array A and then do the binary search for each
element in array B.So the complexity wll be 0(nlgn)
Actually, you do not need to do binary search after sorting.
Sort arrays and just keep two pointers i and j.
Initially, i=0, j=0
while(in jm) {
if( a[i] == b[j] ) {
common++;
i++; j++;
}
if( a[i] b[j] )
i++;
else
j++;
}
--~--~-~--~~~---~--~~
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 options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: hi...one questions
http://web.mit.edu/~mip/www/probs.html [12] Sorting by reversals (ONI'04) You are given an array A[1..N]. Your goal is to sort A by the following type of operation: pick some indices i,j and reverse the subarray A[i..j]. Such an operation costs j-i+1, i.e. the length of the portion which is reversed. Your sorting algorithm should have a total cost of O(N lg^2 N). This is a classic problem related to computational biology. To develop a solution, we first find a way to sort sequences of zeros and ones in O(NlgN) time. This is done through a variant of merge sort. First, sort the two halves of the array recursively. Then, the array will look like: 0..01..10..01..1. All we need to do is to reverse the middle two sequences of ones and zeros, which has a cost linear in N. Now we can use this solution as a subroutine to solve the general case. Our algorithm is similar to quicksort, where we partition at each level around the median. To do the partitioning step, we need to move all elements smaller than the median to the left, and all the ones bigger to the right. This is done by marking smaller elements with zero and larger ones with one, and applying the zero-one sorting subroutine. You may find it interesting to think how to use radix sort instead of quick sort for the second part. To do that, you need to find a way to make the subroutine a stable sorting algorithm. On 7/14/06, kingofcoder [EMAIL PROTECTED] wrote: An array of size N has distinct values 1...N in random order. You have only operator called rev(X) (where X is any value from 0 to N-1) which reverses all values from 0 to X (example values 2,3,1,4 and rev(2) gets you 1,3,2,4). Our objective is to sort the array using minimum number of Rev(X) functions. How many permutations of N size array require exactly N number of rev(X) operators to get sorted a. For size 3 only 1,3,2 requires 3 moves. if any body previously posted this questions...iam sorry for that... actually someone asked me this questions i got one solution..but i dont wheather it uses min no of rev func calls PSUEDO CODE initially i is n; find max no in [0-i] rev that function upto max ele position now max ele in first position now use rev (i) now max in nth position i--; now iam finding iteratively next max like that iam sorting. is it efficient solution.. if any body knows or the gets the more efficient solutions... plz tel me... Ur frnd --~--~-~--~~~---~--~~ 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 options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
