[algogeeks] Re: Loop in a linked list
But If there is no loop in the original list then this code will give incorrect result. the algo should hav been somethin like if loopispresent return the looping node else return NULL --~--~-~--~~~---~--~~ 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 All
greetz On 4/5/07, maverick [EMAIL PROTECTED] wrote: I'm Vikram, a new member to this group. -- You can contact me by : msn messanger: [EMAIL PROTECTED] yahoo messanger: [EMAIL PROTECTED] ICQ: 443443043 Google Talk: [EMAIL PROTECTED] Skype: halfas.online.now IRC: HalFas` (irc2.omnitel.net) Home page: http://www.revidev.com/halfas/ One's leisure project: http://rvision.gamedev.lt/RVengine --~--~-~--~~~---~--~~ 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: solution to maximal clique problem
Hi Raja, There is an algorithm in SIAM Journal of Computing, vol. 6, no. 3, 1977 A New Algorithm for Generating All the Maximal Independent Sets. Finding maximal cliques is equivalent to finding maximal independent sets from a graph with all egdes replaced by non-edges and vice versa. If you don't want to read the whole paper, which in my opinion is actually not easy to read, you can read part of it to get familiar with the symbols, and then implement the algorithm outline in Fig 2 in your own way. On Mar 24, 1:20 am, Raja simman [EMAIL PROTECTED] wrote: Hi all, I'm trying to solve a problem involving maximal clique. If there is a better solution than brute force, please let me know.. --~--~-~--~~~---~--~~ 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] Block processing
Hi all,
I am writing an image processing algorithm that goes across an image
first row-wise and then column-wise. For illustration purposes,
imagine that for every pixels, the output is computed as the sum of
the input and its previous neighbourg. In the horizontal pass (i.e.
row-wise), the previous neighbourg is defined as the pixel on the
left. This is followed by a vertical pass, whereby the previous
neighbourg is defined as the pixel on top.
I quickly encountered a problem with the column-wise path, as
processing pixel in a vertical fashion was _very_ slow (0.31 vs. 0.009
for the horizontal). I since learned that it was due to cache misses.
Indeed, the image is stored row by row, so vertically-neighbouring
pixels are actually far away in memory, which entails all kind of
speed problems.
I was suggested to try a block processing approach, whereby the image
is stored by blocks rather than by rows. A block is typically 32x32,
so in memory, the first line of the block is followed by the second
line of the block, followed by the third, until we move on to the
next block, and the pattern is repeated. This has the advantage of
ensuring locality, i.e. both horizontal and vertical neighboring
pixels will be close, hence there should be less cache misses. Both
horizontal and vertical passes should be approximately as fast.
This is all well and good, but things are not that perfect in
practice. Accessing pixels is now significantly slower, even for
horizontal pass. For an image structured in blocks, an horizontal pass
is 0.030 sec. whereas with the original memory structure (row after
row, lets call it linear), the horizontal pass was only 0.009, 3 times
faster! This cannot be due to cache misses, as locality is pretty good
in both cases. The code to access a pixel is more costly in the case
of block processing. Compare the following, which is copied from my
implementation:
// linear access to pixel
// img: pointer to start of array in memory
#define PIXEL(img, width, row, col) ((img) + ((row) * width) +
(col))
// block access to pixel
#define PXL(img, width, col, row) \
((img) + (((row) (~BLOCK_Y_MASK)) * (width)) + (((col)
BLOCK_X_SHIFT) * BLOCK_SIZE) \
+ (((row) BLOCK_Y_MASK) BLOCK_X_SHIFT) + ((col)
BLOCK_X_MASK))
with enum
{
BLOCK_X_SHIFT = 5,
BLOCK_Y_SHIFT = 5,
BLOCK_X_MASK = (1 BLOCK_X_SHIFT) - 1,
BLOCK_Y_MASK = (1 BLOCK_Y_SHIFT) - 1,
BLOCK_WIDTH = (1 BLOCK_X_SHIFT),
BLOCK_HEIGHT = (1 BLOCK_Y_SHIFT),
BLOCK_SIZE = BLOCK_WIDTH * BLOCK_HEIGHT
};
Accessing a pixel is thus obviously much slower, and I was not able to
speed things up despite all my efforst. Does someone have any ideas or
suggestions that may help, or know of any good references discussing
the problem? Thanks in advance
Angus
--~--~-~--~~~---~--~~
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] Pumping lemma. Where I go wrong?
Question: Try with Pumping Lemma the language 0^2a1^2b i.e. String beginning with even number of 0s and ending with even number of 1s. Solution: 1)Choose n. 2)Choose 0^2n1^2b. 3)Choose x = 0, y = 0^n-1, z = 1^2b 4)First iteration: xy^0z should belong to the language, xz=01^2b. It contains only one 0, its odd. So 0^2a1^2b is not RE. But I know I can write the corresponding RE as (00)*(11)*. --~--~-~--~~~---~--~~ 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: Pumping lemma. Where I go wrong?
You've made some very fundamental mistakes. Pumping Lemma is used as an _adversarial_ argument. This has the following implications, 1) _You_ as the one who is trying to prove that a language is NOT regular will not be choosing `n'. The adversary chooses `n'. 2) Once the adversary has chosen `n', you choose a string longer than n, in order to ensure there is a loop (the pumping property). 3) The adversary then chooses the split up, that is, the part of the string you've given him that loop. The way you've defined it, xyz, subject to the constraint that |xy| = n. 4) You pump as many times as you wish to disprove his statement. On 4/6/07, Ravi [EMAIL PROTECTED] wrote: 3)Choose x = 0, y = 0^n-1, z = 1^2b So this is where you go wrong. A _smart_ adversary will not choose x and y the way you have. He could quite easily have choosen x=0^n-2, y=0^2, z=the rest. The basic flaw is that you've ignored the fact that the pumping lemma is used as an adversarial dialogue, between, you, the person trying to prove a language is not regular, and someone, who claims to have a finite state machine that accepts that language. -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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: Pumping lemma. Where I go wrong?
He could quite easily have choosen x=0^n-2, y=0^2, z=the rest. But may choose it my way instead to prove me wrong. I took the roles of both to get both the sides of the problem. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
