Re: [algogeeks] Addition Of numbers in SLL
On Sat, Aug 14, 2010 at 12:52 PM, AlgoBoy manjunath.n...@gmail.com wrote: Add two numbers represented in a SLL. Each digit is represented as a node...the length of the lists may be more than 2000... Wat is the most efficient soln...store the added digits in another SLL...and return the head as the answer :::two numbers are the seperate link list numbers or the same list that has to been add??? -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Addition Of numbers in SLL
first reverse the both link list and than add -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: P ! = NP
On 11 Aug, 23:54, Kishen Das kishen@gmail.com wrote: http://www.telegraph.co.uk/science/science-news/7938238/Computer-scie... Check out this cool news. Kishen On 10 Aug, 06:50, Niels Fröhling spamt...@adsignum.com wrote: Up to date reactions, comments of the community/researchers (summary): http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E... Deolalikar may possibly have proven the lesser significant of either P! =NP (not the more 'unthinkable' P=NP) ... it appears New Generation Lossless Data Representations likely point the way forward to prove the 'converse' P=NP feasible ! -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Algorithm to find all subsets of size K
Most efficient algorithm to find all subsets of size K?? -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] how to implement TAIL command of unix.
I am trying using fseek but somehow its not working? -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Addition Of numbers in SLL
Reversing the lists and then adding and then reversing the final list is the most appropriate method. Bcoz the lists may contain arbitarily large numbers, so forming integers then adding is not logical here. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] a help
can anyone suggest me lectures / videos for BASICS of BITS manipulation? thanks in advance Rahul K Rai rahulpossi...@gmail.com -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] a help
http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.htmlit has all that you need. On Sat, Aug 14, 2010 at 7:53 PM, rahul rai raikra...@gmail.com wrote: can anyone suggest me lectures / videos for BASICS of BITS manipulation? thanks in advance Rahul K Rai rahulpossi...@gmail.com -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] a help
Thanks a lot , it's a life saver , i will work it out fully . 2010/8/14, Asit Baran Das asitbaran@gmail.com: http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.htmlit has all that you need. On Sat, Aug 14, 2010 at 7:53 PM, rahul rai raikra...@gmail.com wrote: can anyone suggest me lectures / videos for BASICS of BITS manipulation? thanks in advance Rahul K Rai rahulpossi...@gmail.com -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Rahul K Rai rahulpossi...@gmail.com -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Back tracking in list
explain ,if anybody known how to back tracking a Singly link list as a Doubly list with XOR -operation or any method if implementation of a Doubly link list using only one pointer . Explain with help of example -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Addition Of numbers in SLL
i think we can access numbers from last so no need to reverse it and also we can store it in linke list in stack way so again no need to reverse the linked list. On Sat, Aug 14, 2010 at 7:03 PM, Gaurav Singh gogi.no...@gmail.com wrote: Reversing the lists and then adding and then reversing the final list is the most appropriate method. Bcoz the lists may contain arbitarily large numbers, so forming integers then adding is not logical here. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Rahul singhal RnD Engineer Tejas Networks Mobile- 09916969422 -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Addition Of numbers in SLL
how can you traverse from last without reversing it. and there is no need fof using extra stack 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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Addition Of numbers in SLL
I men to say ki just traverse from last instead of reversing it and storing result in a stack in linked list form so that we dont need to reverse again.Hope,i made myself clear. On Sat, Aug 14, 2010 at 11:40 PM, Lokesh Agarwal lokesh...@gmail.comwrote: how can you traverse from last without reversing it. and there is no need fof using extra stack 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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Rahul singhal RnD Engineer Tejas Networks Mobile- 09916969422 -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Addition Of numbers in SLL
Reversing and then again reversing the answer will not be an efficient algorithm... on the fly computation of sum must be done...any ideas On 8/14/10, Rahul Singhal nitk.ra...@gmail.com wrote: I men to say ki just traverse from last instead of reversing it and storing result in a stack in linked list form so that we dont need to reverse again.Hope,i made myself clear. On Sat, Aug 14, 2010 at 11:40 PM, Lokesh Agarwal lokesh...@gmail.comwrote: how can you traverse from last without reversing it. and there is no need fof using extra stack 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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Rahul singhal RnD Engineer Tejas Networks Mobile- 09916969422 -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Back tracking in list
Part 1 of the trick is that if you know A xor B and you have either A
or B, you can get the other value. This is because A xor (A xor B) =
B and B xor (A xor B) = B.
[Incidentally, you can use subtraction rather than XOR. If you know A
- B and have A, you can compute A - (A - B) to get B. If you have B,
you can compute B + (A - B) to get A.]
Part 2 of the trick is that as you are traversing a list, you always
know the address of the node you just came from. Consequently, if you
store the xor of the next and previous pointers in a single location
within the node, you always have enough information to learn the
pointer you don't know.
I.e. if your nodes look like:
struct node {
struct node *next_xor_prev;
... other fields;
}
and you have pointers to two adjacent notes p0 and p1, you can advance
them to the successor node with
tmp = p1;
p1 = p0 xor p1-next_xor_prev
p0 = tmp
Which direction you go depends on the values of p0 and p1. If p0 =
previous(p1), then you'll advance both pointers 1 node forward. If p0
= next(p1), then you'll advance to the previous node.
To make all this work, you must represent the entire list as a head
_and_ tail pointer.
struct list {
struct node *head, *tail;
}
so a forward traversal is initialized with p1 = head; p0 = tail;
and backward traversal is p1 = tail; p0 = head.
So the price you pay for this method is that if you want to pass
around pointers into the middle of the list that allow you to start a
traversal from that point, you must pass around a pair pointers to two
adjacent list nodes rather than a single one.
The other price is that no language I know of provides a portable way
to store the xor of two pointers, so it's a risky thing to do in
production software.
On Aug 14, 11:15 am, UMESH KUMAR kumar.umesh...@gmail.com wrote:
explain ,if anybody known how to back tracking a Singly link list as a
Doubly list with XOR -operation or any method if implementation of a Doubly
link list using only one pointer .
Explain with help of example
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Generate all bit strings of length n
On 13 Aug, 17:05, Chonku cho...@gmail.com wrote:
Start with number 1. It will have a binary representation of 00...1 (Total
of n-bits)
Keeping adding 1 to it until you reach a number with all 1's in its binary
representation.
Looks correct to me,
here is a small implementation
code
#include stdio.h
int len;
void to_binary(int n)
{
int i = len - 1;
for(; i = 0; i--) {
(n 1i) ? printf( 1):printf( 0);
}
printf(\n);
}
void generate_bits(int n)
{
if(n == 0) return;
generate_bits(n-1);
to_binary(n);
}
int main(void)
{
scanf(%d, len);
generate_bits((1len) - 1);
}
/code
On Thu, Aug 12, 2010 at 2:00 PM, Raj N rajn...@gmail.com wrote:
Hi,
Can someone gimme the code to generate all possible bit strings of
length n recursively ?
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: how to implement TAIL command of unix.
Tail by default displays last 10 lines of file. 1. mmap the file 2. keep two pointers(A, B) pointing to beginning of the file 2. search for 10th \n using B, if not found i.e file has less than 10 lines, print from beginning to end 3. if found, start incrementing both A and B to the next \n. untill B reaches end of file. 4. Print from A till end of file. On 13 Aug, 23:13, amit amitjaspal...@gmail.com wrote: I am trying using fseek but somehow its not working? -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: P ! = NP
http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/ Looks like there are serious flaws with this proof but it can produce other interesting results. http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/ Kishen On Sat, Aug 14, 2010 at 7:30 AM, LawCounsels lawcouns...@aol.com wrote: On 11 Aug, 23:54, Kishen Das kishen@gmail.com wrote: http://www.telegraph.co.uk/science/science-news/7938238/Computer-scie... Check out this cool news. Kishen On 10 Aug, 06:50, Niels Fröhling spamt...@adsignum.com wrote: Up to date reactions, comments of the community/researchers (summary): http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E... Deolalikar may possibly have proven the lesser significant of either P! =NP (not the more 'unthinkable' P=NP) ... it appears New Generation Lossless Data Representations likely point the way forward to prove the 'converse' P=NP feasible ! -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Addition Of numbers in SLL
i think we can use recursion method to reverse the list -- Prashant Kulkarni On Sat, Aug 14, 2010 at 11:40 PM, Lokesh Agarwal lokesh...@gmail.comwrote: how can you traverse from last without reversing it. and there is no need fof using extra stack 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...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Shuffling a deck of cards
write a program to shuffle an pack of cards in the most efficient way. -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Shuffling a deck of cards
for(i=0;i52;++i)
{
int r=rand()%52;
swap(a[i],a[r]);
}
On Sat, Aug 14, 2010 at 11:46 PM, amit amitjaspal...@gmail.com wrote:
write a program to shuffle an pack of cards in the most efficient way.
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Shuffling a deck of cards
@Sharad: Your code does not produce equally probable shuffles. You can
see this by noting that a[0] is swapped with one of 52 cards, same for
a[1], a[2], ..., a[51]. Thus, there are 52^52 possible sets of swaps.
But there are only 52! possible outcomes, and 52^52 / 52! is not an
integer.
You can verify this experimentally by shuffling a small deck, say 3
cards. If you do so, you will find that, starting with the deck ABC,
you get ABC 4/27 of the time, ACB 5/27, BAC 5/27, BCA 5/27, CAB 4/27,
and CBA 4/27. Thus, some outcomes are 25% more likely than others.
The proper code is
for(i=1;i52;++i)
{
int r=rand()%(i+1);
swap(a[i],a[r]);
}
Dave
On Aug 14, 9:34 pm, sharad kumar aryansmit3...@gmail.com wrote:
for(i=0;i52;++i)
{
int r=rand()%52;
swap(a[i],a[r]);
}
On Sat, Aug 14, 2010 at 11:46 PM, amit amitjaspal...@gmail.com wrote:
write a program to shuffle an pack of cards in the most efficient way.
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: how to implement TAIL command of unix.
Tail works on stdin, too. Can't mmap that. The usual way is to buffer the last N lines read in a ring buffe.r On Aug 14, 4:22 pm, Prem Mallappa prem.malla...@gmail.com wrote: Tail by default displays last 10 lines of file. 1. mmap the file 2. keep two pointers(A, B) pointing to beginning of the file 2. search for 10th \n using B, if not found i.e file has less than 10 lines, print from beginning to end 3. if found, start incrementing both A and B to the next \n. untill B reaches end of file. 4. Print from A till end of file. On 13 Aug, 23:13, amit amitjaspal...@gmail.com wrote: I am trying using fseek but somehow its not working? -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Addition Of numbers in SLL
Don't reverse the list. Just store it from low to high order digits. I.e., the head points to the ones digit, which points to the tens digit, etc. That is the assumption I made with my algorithm presented in the second post of this thread, because almost all operations use the number beginning with the low order digits. Dave On Aug 14, 7:29 am, Lokesh Agarwal lokesh...@gmail.com wrote: first reverse the both link list and than add -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: how to implement TAIL command of unix.
Enter the lines into a FIFO queue as you read them. After you have enqueued n lines, dequeue a line every time you enqueue one, so that the queue will contain the last n (or fewer) lines of the file. Dave On Aug 13, 1:13 pm, amit amitjaspal...@gmail.com wrote: I am trying using fseek but somehow its not working? -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
