Re: [algogeeks] Re: Longest Palindromic Substring

[Aditya Shanker]

 The question would be complete if we know what order of notation is 
needed for solution.



On 23.08.2010 15:32, Chi Hoang wrote:
I don't think so, I've have wriiten a kart-trie: 
http://sourceforge.net/projects/kart-trie which is basically a 
patricia-tree or radix-tree. Such a tree has maximum 2 leafs at each 
branch whilst a suffix-tree can has more then 2 leafs at each branch 
(BTW. can you explain to me what does edge means when talking about 
trees?). This is my understanding of a suffix-tree so far. I'm 
awaiting your anwser!

2010/8/21 Chonku mailto:cho...@gmail.com>>

You use a trie when you want to model a number of strings. Suffix
Tree is used only when you have one string in your model. Suffix
Tree is a type of trie, but the difference lies in the intent.


On Sat, Aug 21, 2010 at 7:22 PM, Chi mailto:c...@linuxdna.com>> wrote:

Isn't that by definition a compressed trie, i.e patricia-tree,
crit-
bit tree (suffix-tree)? Or what is the difference?

On Aug 20, 5:17 pm, Nikhil Jindal mailto:fundoon...@yahoo.co.in>> wrote:
> @chonku
> As i understand, a trie is used when we have a lot of
strings (such as a
> dictionary).
> Here we just have a single string. The resultant trie will be:
>
> a
>  \
>   b
>\
> c
>  \
>   l
>\
> e
>  \
>   v
>\
> e
>  \
>   l
>\
> a
>  \
>   b
>\
> c
>
> We get a similar trie for the reverse string.
>
> So why are you using a trie here? I cant see any advantage
of it here.
>
>
>
>
>
> On Fri, Aug 20, 2010 at 8:36 AM, Chonku mailto:cho...@gmail.com>> wrote:
> > Can we use a trie here.
> > Make first pass from left to right and construct the trie.
> > Make second pass from right to left and look for the trie
branch with
> > maximum nodes that match the characters.
>
> > On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal
mailto:fundoon...@yahoo.co.in>>wrote:
>
> >> Hi All,
>
> >> Givan a string, you have to find the longest palindromic
substring.
> >> For ex: Longest Palindromic substring for abclevelabc is
level.
>
> >> What is the most optimised solution possible?
>
> >> Please access the attached hyperlink for an important
electronic communications
disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>
> >> --
>
> >> You received this message because you are subscribed to
the Google Groups "Algorithm Geeks" group.
>
> >> To post to this group, send email
toalgoge...@googlegroups.com
.
>
> >> To unsubscribe from this group, send email
toalgogeeks+unsubscr...@googlegroups.com

mailto:algogeeks%252bunsubscr...@googlegroups.com>>.
>
> >> For more options, visit this group
athttp://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 toalgoge...@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.
>
> Please access the attached hyperlink for an important
electronic communications
disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php

--
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
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 th

Re: [algogeeks] How strong is your quick sort fundamental?

[Yan Wang]

You can compute recursively as below:

We use f(n) to represent the number of comparisons which the
Quick-Sort algo needs to take running on an array of n elements.

Answer to question 1:
f(n) = 2 * f(n/2) + n
We can observe the following sequence of equations:
f(n) = 4 * f(n/4) + 2 * n/2 + n = 4f(n/4)+2n
f(n) = 8 * f(n/8) + 4 * n/4 + 2 * n/2 + n = 8f(n/8)+3n
f(n) = 16 * f(n/16) + 4n
...
So, we induce the final conclusion:
f(n) = 2^k * f(n/2^k) + kn, where n/2^k > 1
Thus
f(n) = O(n*logn)
This is really a tight boundary!

Answer to question 2:
f(n) = f(n/3) + f(2n/3) +n
Same as above, we can conclude that:
f(n) = O(n*logn)

On Wed, Aug 25, 2010 at 11:16 AM, sourav  wrote:
> The median of a set of n values is the \lceil n/2 \rceilth smallest
> value.
>
>   1. Suppose quicksort always pivoted on the median of the current
> sub-array. How many comparisons would Quicksort make then in the worst
> case?
>   2. Suppose quicksort were always to pivot on the "n/3 th" smallest
> value of the current sub-array. How many comparisons would be made
> then in the worst case?
>
> Support your answer giving mathematical proof / approach to your
> answer.
>
>
> [Note: In case quick sort always partitions the sub-array into 0 and
> n-1 elements (pivot comes to be first element or last element), then
> total of n^2 comparisions are done]
>
> --
> 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.

Re: [algogeeks] Re: Subsequence

[prasad rao]

suppose we take an array like this
 5,3, 2, 6,7, 4, 8,1, 0, 7, 9
Here 2, 6,7
4,8
 and  7,9 are non decreasing sub sequences of array and we have to find sum
of those sub sequences which is maximum.
the sum of 2, 6,7 is 15.
  sum of 4, 8 is 12,
and sum of 7, 9 is 16.
maximum sum is 16.
I think this is answer. Is it right meaning of question?

On 25 August 2010 22:04, Raj N  wrote:

> @Vikas: I want to know the same.
>
> On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar wrote:
>
>> can you define what here subsequence means?
>>
>>
>> On Wed, Aug 25, 2010 at 9:32 PM, Rahul  wrote:
>>
>>> @Jaswanth
>>> It will be really kind if you will state the algorithm rather than
>>> providing codes, as it is tedious.
>>>
>>> --
>>> 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.
>>
>
>  --
> 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: National Instruments: points separated by a distance d

[gaurav]

A quad tree will be good i suppose

-- 
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: National Instruments: points separated by a distance d

[Gene]

A kd-tree would be a good fit for this problem.  You'd want to keep a
child count in each node.

On Aug 25, 8:59 am, Raj N  wrote:
> Given location of huge number of points (you decide the data structure
> to represent them). Write a function that returns the number of points
> that are with distance D of a given point P.
> Write function, complete with what data structures, function signature
> etc.

-- 
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: National Instruments: linked list subtraction

[Gene]

This is close, but more complicated than necessary.  After you know
how many leading zeros are needed before B, just act like they're
present and use recursion to process right-to-left:

#include 
#include 

typedef struct digit_s {
  struct digit_s *next;
  int val;
} DIGIT;

DIGIT *new_digit(int val, DIGIT *next)
{
  DIGIT *d = malloc(sizeof *d);
  d->val = val;
  d->next = next;
  return d;
}

int length(DIGIT *d)
{
  int n = 0;
  while (d) {
n++;
d = d->next;
  }
  return n;
}

void print(DIGIT *d)
{
  while (d) {
printf("%d", d->val);
d = d->next;
  }
}

static DIGIT *
do_sub(DIGIT *a, int n_leading_zeros, DIGIT *b, int *borrow)
{
  DIGIT *rtn;
  int b_val, val;

  if (a == NULL) { // b is NULL, too
*borrow = 0;
return NULL;
  }
  if (n_leading_zeros > 0) {
rtn = do_sub(a->next, n_leading_zeros - 1, b, borrow);
b_val = 0;
  }
  else {
rtn = do_sub(a->next, 0, b->next, borrow);
b_val = b->val;
  }
  // Subtract including borrow from previous.
  val = a->val - b_val - *borrow;
  // See if we need to borrow from the next digit.
  if (val < 0) {
val += 10;
*borrow = 1;
  }
  else {
*borrow = 0;
  }
  return new_digit(val, rtn);
}

DIGIT *subtract(DIGIT *a, DIGIT *b)
{
  int borrow;
  return do_sub(a, length(a) - length(b), b, &borrow);
}

int main(void)
{
  DIGIT *a =
new_digit(5,
new_digit(4,
new_digit(2,
new_digit(0,
new_digit(0,
new_digit(9,
new_digit(0,
new_digit(0, NULL;

  DIGIT *b =
new_digit(1,
new_digit(9,
new_digit(9, NULL)));

  DIGIT *r = subtract(a, b);

  print(a); printf(" - "); print(b);
  printf(" = "); print(r); printf("\n");
  return 0;
}


On Aug 25, 8:25 am, Terence  wrote:
> 1. Calculate the length of both list (A, B).
> 2. Find the position in the longer list corresponding to the head of
> shorter list, and copy the previous digits to output list C.
>     (Or for simplicity, appending 0 to the shorter list so as to get the
> same length as the longer one)
> 3. Add the two lists into list C without performing carry.
> 4. Perform carries. For each digit x in sum C, and the previous digit px.
>      a) if x < 9, no change to x and px;
>      b) if x > 9, x = x - 10, px = px + 1;
>      c) if x ==9, continue to next digit until you come to a digit x'
> not equal to 9 (or the end of list)
>                  if x' > 9, x' = x' - 10, px = px + 1, and change all
> the 9's in between to 0.
>                 else,  keep all those digits untouched.
>
> step 3 and 4 can be merged into one pass.
>
> On 2010-8-25 17:54, Raj N wrote:
>
>
>
> > Input : Two large singly linked lists representing numbers with most
> > significant digit as head and least significant as last node.
> > Output: Difference between the numbers as a third linked list with
> > Most significant digit as the head.
> > Eg:
> > ---
> > Input:
> > A = 5->4->2->0->0->9->0->0
> > B = 1->9->9
> > Output:
> > C = 5->4->2->0->0->7->0->1
> > Required complexity :
> > O(n)
> > Constraint:
> > Reversing linked list is NOT allowed

-- 
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 strong is your quick sort fundamental?

[sourav]

The median of a set of n values is the \lceil n/2 \rceilth smallest
value.

   1. Suppose quicksort always pivoted on the median of the current
sub-array. How many comparisons would Quicksort make then in the worst
case?
   2. Suppose quicksort were always to pivot on the "n/3 th" smallest
value of the current sub-array. How many comparisons would be made
then in the worst case?

Support your answer giving mathematical proof / approach to your
answer.


[Note: In case quick sort always partitions the sub-array into 0 and
n-1 elements (pivot comes to be first element or last element), then
total of n^2 comparisions are done]

-- 
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: Subsequence

[Raj N]

@Vikas: I want to know the same.

On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar  wrote:

> can you define what here subsequence means?
>
>
> On Wed, Aug 25, 2010 at 9:32 PM, Rahul  wrote:
>
>> @Jaswanth
>> It will be really kind if you will state the algorithm rather than
>> providing codes, as it is tedious.
>>
>> --
>> 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.
>

-- 
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] National Instruments: linked list subtraction

[Raj N]

@Sharad: Ya that's fine. But the problem says msb is at the head of the
list. So you've to start subtraction from the end of the list and you don't
have previous pointer. Thats the main challenge, also you can't reverse !!
The only thing that came to my mind was divide and conquer approach and
extract every node and perform subtraction.

On Wed, Aug 25, 2010 at 9:45 PM, sharad kumar wrote:

> make use of two ptr approach.first traverse the first linkd list and fnd k
> th element from last where k is the length of subrahend then perform
> subtraction.
>
> On Wed, Aug 25, 2010 at 8:18 PM, Raj N  wrote:
>
>> My approach:
>> Use divide and conquer approach. i.e divide(a) divide(b) i.e first list
>> and divide(c) divide(d) of second list recursively (like mergesort). Then
>> apply subtract(a,c) and subtract(b,d)
>>
>> It goes this way:
>> Make both lists of equal length by appending 0s at the beginning of
>> smaller list. Assuming list1 > list2
>> struct node
>> {
>> int data;
>> struct node *next;
>> };
>>
>> void divide(struct node* root1,struct node *root2)
>> {
>> struct node *a;
>> struct node *b;
>> struct node *c;
>> struct node *d;
>> struct node *result;
>> int borrow=0;
>>
>> if(root1==NULL || root1->next==NULL)
>>   return;
>> else
>> {
>>   split(root1,&a,&b);
>>   split(root2,&c,&d);
>> }
>> if(b->next==NULL && a->next==NULL)
>> {
>> subtract(b,d,&borrow,&result);
>> subtract(a,c,&borrow,&result);
>> }
>> }
>>
>> void split(struct node* source, struct node **front, struct node **back)
>> {
>> struct node *slow, *fast;
>> slow=source;
>> fast=source->next;
>>
>> while(fast!=NULL)
>> {
>>fast=fast->next;
>>if(fast!=NULL)
>>{
>>   slow=slow->next;
>>   fast=fast->next;
>> }
>>   }
>>  *front=source;
>>  *back=slow->next;
>>   slow->next=NULL;
>> }
>>
>> void subtract(struct node *n1, struct node *n2, int *borrow,struct node
>> **result)
>> {
>>  *result=(struct node*)malloc(sizeof(struct node));
>>  if(n1->data >= n2->data && !borrow)
>>  {
>>   result->data = n1->data - n2->data;
>>
>>  }
>>   else if(n1->data > n2->data && borrow)
>>   {
>> result->data = (n1->data-1) - n2->data;
>> borrow = 0;
>>   }
>>else if(n1->data < n2->data && !borrow)
>>{
>>   result->data = (n1->data + 10) - n2->data;
>> borrow=1;
>>}
>>else if(n1->data <= n2->data && borrow)
>>{
>>  result->data = (n1->data+9) - n2->data;
>>}
>>
>> // Insert the new node result at the beginning of result list
>> }
>>
>> Tell me if there're any corrections !!
>>
>>
>>  On Wed, Aug 25, 2010 at 3:24 PM, Raj N  wrote:
>>
>>> Input : Two large singly linked lists representing numbers with most
>>> significant digit as head and least significant as last node.
>>> Output: Difference between the numbers as a third linked list with
>>> Most significant digit as the head.
>>> Eg:
>>> ---
>>> Input:
>>> A = 5->4->2->0->0->9->0->0
>>> B = 1->9->9
>>> Output:
>>> C = 5->4->2->0->0->7->0->1
>>> Required complexity :
>>> O(n)
>>> Constraint:
>>> Reversing linked list is NOT allowed
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> 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.
>

-- 
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: knight moves in chess

[Chi]

@Shrish:

A chessboard can be viewed as a graph of  2^n -
(n-1) edges is not correct, it must be n^2-(n-1) edges. By unweighted
you mean, it has no payload, or cost-function, or probability.
So you use a BFS, I guess I have to do it myself, because on the
website I can't see a solution (neither I know your nickname). At
least can you confirm me this number n^2-(n-1) edges if the knight
start-position and end-position is such that he travels all points of
the graph?


On Aug 25, 4:08 pm, SHRISH MISHRA  wrote:
> @Chi
> Have a look ofhttp://www.codechef.com/SNACKTST/problems/KNIGHT1/
> I have it solved with the approach what i already mentioned.
> For Breadth First Search and its application please 
> referhttp://en.wikipedia.org/wiki/Breadth-first_search
>
> Great Minds Discuss Ideas
> Average Minds Discuss Events
> Small Minds Discuss People
> Shrish Chandra Mishra
> CSE Mnnit,Allahabad
>
> On Wed, Aug 25, 2010 at 6:14 PM, Chi  wrote:
> > A spacefilling curve is also known as a quadtree-representation of a
> > plane. It's subdivide a plane in continuous 4 cells. My linear
> > implementations gives at each step one leaf. What do you mean with
> > unweigthed und BFS (Breadth-First-Search, perhaps?). How can you add 8
> > vertices to the queue? It makes only sense to add 4 to queue with a
> > recursive approach!? A chessboard can be viewed as a graph of  2^n -
> > (n-1) edges. Sorry, I don't know the solution.
>
> > On Aug 25, 6:11 am, SHRISH MISHRA  wrote:
> > > The question is asking for a shortest path of some sort. If we consider
> > each
> > > cell as a vertex, then the edges will be the possible knight moves. For
> > > example, the cell (2,3) would have an edge to (and from) the cell (4,4),
> > > assuming that there are no pieces occupying either cell. This graph is
> > > unweighted, so the most natural algorithm to use is BFS. Having realized
> > > this, the graph itself is not necessary anymore; we can just use the
> > board
> > > directly. S is the source, and is the first cell/vertex added to the BFS
> > > queue. At each step, at most 8 more vertices will be added to the queue.
> > BFS
> > > will stop when T is found or when the queue is empty (no path to T was
> > > found).
>
> > > Great Minds Discuss Ideas
> > > Average Minds Discuss Events
> > > Small Minds Discuss People
> > > Shrish Chandra Mishra
> > > CSE NIT,Allahabad
>
> > > On Wed, Aug 25, 2010 at 8:25 AM, Chi  wrote:
> > > > This is a spacefilling-curve. Optimal solution is a Hilbert-Curve or a
> > > > Morton-Curve. I have written one:
> > > >http://sourceforge.net/projects/hilbert-curve/files.
>
> > > > On Aug 25, 4:27 am, Algo geek  wrote:
> > > > > find the minimum no of moves by which a KNIGHT reaches the
> > destination
> > > > > from source in a 8x8 chess borad...
>
> > > > > **you will be given the starting position and ending position ..
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.> To post to this group, send email
> > toalgoge...@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.

-- 
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: Subsequence

[Jashwant Raj]

@rahul... ya .. sure... but i still don understand ur question..wat do yo
mean sub-sequence.?

On Wed, Aug 25, 2010 at 10:02 PM, Vikas Kumar  wrote:

> can you define what here subsequence means?
>
>
> On Wed, Aug 25, 2010 at 9:32 PM, Rahul  wrote:
>
>> @Jaswanth
>> It will be really kind if you will state the algorithm rather than
>> providing codes, as it is tedious.
>>
>> --
>> 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.
>

-- 
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: Subsequence

[Vikas Kumar]

can you define what here subsequence means?

On Wed, Aug 25, 2010 at 9:32 PM, Rahul  wrote:

> @Jaswanth
> It will be really kind if you will state the algorithm rather than
> providing codes, as it is tedious.
>
> --
> 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.

Re: [algogeeks] National Instruments: linked list subtraction

[sharad kumar]

make use of two ptr approach.first traverse the first linkd list and fnd k
th element from last where k is the length of subrahend then perform
subtraction.

On Wed, Aug 25, 2010 at 8:18 PM, Raj N  wrote:

> My approach:
> Use divide and conquer approach. i.e divide(a) divide(b) i.e first list and
> divide(c) divide(d) of second list recursively (like mergesort). Then apply
> subtract(a,c) and subtract(b,d)
>
> It goes this way:
> Make both lists of equal length by appending 0s at the beginning of smaller
> list. Assuming list1 > list2
> struct node
> {
> int data;
> struct node *next;
> };
>
> void divide(struct node* root1,struct node *root2)
> {
> struct node *a;
> struct node *b;
> struct node *c;
> struct node *d;
> struct node *result;
> int borrow=0;
>
> if(root1==NULL || root1->next==NULL)
>   return;
> else
> {
>   split(root1,&a,&b);
>   split(root2,&c,&d);
> }
> if(b->next==NULL && a->next==NULL)
> {
> subtract(b,d,&borrow,&result);
> subtract(a,c,&borrow,&result);
> }
> }
>
> void split(struct node* source, struct node **front, struct node **back)
> {
> struct node *slow, *fast;
> slow=source;
> fast=source->next;
>
> while(fast!=NULL)
> {
>fast=fast->next;
>if(fast!=NULL)
>{
>   slow=slow->next;
>   fast=fast->next;
> }
>   }
>  *front=source;
>  *back=slow->next;
>   slow->next=NULL;
> }
>
> void subtract(struct node *n1, struct node *n2, int *borrow,struct node
> **result)
> {
>  *result=(struct node*)malloc(sizeof(struct node));
>  if(n1->data >= n2->data && !borrow)
>  {
>   result->data = n1->data - n2->data;
>
>  }
>   else if(n1->data > n2->data && borrow)
>   {
> result->data = (n1->data-1) - n2->data;
> borrow = 0;
>   }
>else if(n1->data < n2->data && !borrow)
>{
>   result->data = (n1->data + 10) - n2->data;
> borrow=1;
>}
>else if(n1->data <= n2->data && borrow)
>{
>  result->data = (n1->data+9) - n2->data;
>}
>
> // Insert the new node result at the beginning of result list
> }
>
> Tell me if there're any corrections !!
>
>
>  On Wed, Aug 25, 2010 at 3:24 PM, Raj N  wrote:
>
>> Input : Two large singly linked lists representing numbers with most
>> significant digit as head and least significant as last node.
>> Output: Difference between the numbers as a third linked list with
>> Most significant digit as the head.
>> Eg:
>> ---
>> Input:
>> A = 5->4->2->0->0->9->0->0
>> B = 1->9->9
>> Output:
>> C = 5->4->2->0->0->7->0->1
>> Required complexity :
>> O(n)
>> Constraint:
>> Reversing linked list is NOT allowed
>>
>> --
>> 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.
>



-- 
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: Subsequence

[Rahul]

@Jaswanth
It will be really kind if you will state the algorithm rather than
providing codes, as it is tedious.

-- 
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] Subsequence

[Raj N]

@Rahul: Input: 5 4 6 7 3 2 9 8 and if k=3
should the output be 4+6+7=11 ? Is that what you mean by non-decreasing ?

On Wed, Aug 25, 2010 at 9:27 PM, Raj N  wrote:

> @Jaswanth: Your code nowhere checks the non-decreasing sequence
>
>
> On Tue, Aug 24, 2010 at 7:16 PM, Jashwant Raj  wrote:
>
>> hope i got d logic right
>>
>>
>> On Tue, Aug 24, 2010 at 9:55 AM, Rahul  wrote:
>>
>>> How to find out Non-Decreasing subsequence of length k with maximum
>>> sum in an array of n integers ?
>>>
>>> --
>>> 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.
>>
>
>

-- 
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] National Instruments: linked list subtraction

[Raj N]

@Terence: It is subtraction of 2 lists and not addition. N for your logic of
addition for x>9 you add px+1 and after that if it becomes > 9 how do you
know the previous of it as you've moved the previous pointer?

Can someone comment on my logic ?

On Wed, Aug 25, 2010 at 9:10 PM, Raj N  wrote:

> They've mentioned that they're large lists. What if it is a 15 digit
> number? Its not efficient then.
>
>
> On Wed, Aug 25, 2010 at 8:29 PM, Sathaiah Dontula wrote:
>
>> @Raj,
>>
>> How about doing like below ?
>>
>> Convert A to base 10 number, numA
>> Convert B to base 10 number, numB,
>> Then take the difference  numC = abs(numA - numB),
>> Then convert numC to linked list with the digits
>>
>> any comments ?, overflow condition is the problem here.
>>
>> Thanks & regards,
>> Sathaiah Dontula
>>
>> On Wed, Aug 25, 2010 at 3:24 PM, Raj N  wrote:
>>
>>> Input : Two large singly linked lists representing numbers with most
>>> significant digit as head and least significant as last node.
>>> Output: Difference between the numbers as a third linked list with
>>> Most significant digit as the head.
>>> Eg:
>>> ---
>>> Input:
>>> A = 5->4->2->0->0->9->0->0
>>> B = 1->9->9
>>> Output:
>>> C = 5->4->2->0->0->7->0->1
>>> Required complexity :
>>> O(n)
>>> Constraint:
>>> Reversing linked list is NOT allowed
>>>
>>> --
>>> 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.
>>
>
>

-- 
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] Subsequence

[Raj N]

@Jaswanth: Your code nowhere checks the non-decreasing sequence

On Tue, Aug 24, 2010 at 7:16 PM, Jashwant Raj  wrote:

> hope i got d logic right
>
>
> On Tue, Aug 24, 2010 at 9:55 AM, Rahul  wrote:
>
>> How to find out Non-Decreasing subsequence of length k with maximum
>> sum in an array of n integers ?
>>
>> --
>> 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.
>

-- 
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] National Instruments: linked list subtraction

[Raj N]

They've mentioned that they're large lists. What if it is a 15 digit number?
Its not efficient then.

On Wed, Aug 25, 2010 at 8:29 PM, Sathaiah Dontula wrote:

> @Raj,
>
> How about doing like below ?
>
> Convert A to base 10 number, numA
> Convert B to base 10 number, numB,
> Then take the difference  numC = abs(numA - numB),
> Then convert numC to linked list with the digits
>
> any comments ?, overflow condition is the problem here.
>
> Thanks & regards,
> Sathaiah Dontula
>
> On Wed, Aug 25, 2010 at 3:24 PM, Raj N  wrote:
>
>> Input : Two large singly linked lists representing numbers with most
>> significant digit as head and least significant as last node.
>> Output: Difference between the numbers as a third linked list with
>> Most significant digit as the head.
>> Eg:
>> ---
>> Input:
>> A = 5->4->2->0->0->9->0->0
>> B = 1->9->9
>> Output:
>> C = 5->4->2->0->0->7->0->1
>> Required complexity :
>> O(n)
>> Constraint:
>> Reversing linked list is NOT allowed
>>
>> --
>> 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.
>

-- 
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: National Instruments: linked list subtraction

[Raj N]

@Hari: But I've not reversed the lists and I think my logic works.

On Wed, Aug 25, 2010 at 6:47 PM, hari  wrote:

> I dont think it can be done without reversing the linked list!!
>
> On Aug 25, 2:54 pm, Raj N  wrote:
> > Input : Two large singly linked lists representing numbers with most
> > significant digit as head and least significant as last node.
> > Output: Difference between the numbers as a third linked list with
> > Most significant digit as the head.
> > Eg:
> > ---
> > Input:
> > A = 5->4->2->0->0->9->0->0
> > B = 1->9->9
> > Output:
> > C = 5->4->2->0->0->7->0->1
> > Required complexity :
> > O(n)
> > Constraint:
> > Reversing linked list is NOT allowed
>
> --
> 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.

Re: [algogeeks] National Instruments: linked list subtraction

[Terence]

1. Calculate the length of both list (A, B).
2. Find the position in the longer list corresponding to the head of 
shorter list, and copy the previous digits to output list C.
   (Or for simplicity, appending 0 to the shorter list so as to get the 
same length as the longer one)

3. Add the two lists into list C without performing carry.
4. Perform carries. For each digit x in sum C, and the previous digit px.
a) if x < 9, no change to x and px;
b) if x > 9, x = x - 10, px = px + 1;
c) if x ==9, continue to next digit until you come to a digit x' 
not equal to 9 (or the end of list)
if x' > 9, x' = x' - 10, px = px + 1, and change all 
the 9's in between to 0.

   else,  keep all those digits untouched.

step 3 and 4 can be merged into one pass.


On 2010-8-25 17:54, Raj N wrote:

Input : Two large singly linked lists representing numbers with most
significant digit as head and least significant as last node.
Output: Difference between the numbers as a third linked list with
Most significant digit as the head.
Eg:
---
Input:
A = 5->4->2->0->0->9->0->0
B = 1->9->9
Output:
C = 5->4->2->0->0->7->0->1
Required complexity :
O(n)
Constraint:
Reversing linked list is NOT allowed



--
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: National Instruments: linked list subtraction

[hari]

I dont think it can be done without reversing the linked list!!

On Aug 25, 2:54 pm, Raj N  wrote:
> Input : Two large singly linked lists representing numbers with most
> significant digit as head and least significant as last node.
> Output: Difference between the numbers as a third linked list with
> Most significant digit as the head.
> Eg:
> ---
> Input:
> A = 5->4->2->0->0->9->0->0
> B = 1->9->9
> Output:
> C = 5->4->2->0->0->7->0->1
> Required complexity :
> O(n)
> Constraint:
> Reversing linked list is NOT allowed

-- 
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: knight moves in chess

[SHRISH MISHRA]

@Chi
Have a look of
http://www.codechef.com/SNACKTST/problems/KNIGHT1/
I have it solved with the approach what i already mentioned.
For Breadth First Search and its application please refer
http://en.wikipedia.org/wiki/Breadth-first_search


Great Minds Discuss Ideas
Average Minds Discuss Events
Small Minds Discuss People
Shrish Chandra Mishra
CSE Mnnit,Allahabad


On Wed, Aug 25, 2010 at 6:14 PM, Chi  wrote:

> A spacefilling curve is also known as a quadtree-representation of a
> plane. It's subdivide a plane in continuous 4 cells. My linear
> implementations gives at each step one leaf. What do you mean with
> unweigthed und BFS (Breadth-First-Search, perhaps?). How can you add 8
> vertices to the queue? It makes only sense to add 4 to queue with a
> recursive approach!? A chessboard can be viewed as a graph of  2^n -
> (n-1) edges. Sorry, I don't know the solution.
>
> On Aug 25, 6:11 am, SHRISH MISHRA  wrote:
> > The question is asking for a shortest path of some sort. If we consider
> each
> > cell as a vertex, then the edges will be the possible knight moves. For
> > example, the cell (2,3) would have an edge to (and from) the cell (4,4),
> > assuming that there are no pieces occupying either cell. This graph is
> > unweighted, so the most natural algorithm to use is BFS. Having realized
> > this, the graph itself is not necessary anymore; we can just use the
> board
> > directly. S is the source, and is the first cell/vertex added to the BFS
> > queue. At each step, at most 8 more vertices will be added to the queue.
> BFS
> > will stop when T is found or when the queue is empty (no path to T was
> > found).
> >
> > Great Minds Discuss Ideas
> > Average Minds Discuss Events
> > Small Minds Discuss People
> > Shrish Chandra Mishra
> > CSE NIT,Allahabad
> >
> >
> >
> > On Wed, Aug 25, 2010 at 8:25 AM, Chi  wrote:
> > > This is a spacefilling-curve. Optimal solution is a Hilbert-Curve or a
> > > Morton-Curve. I have written one:
> > >http://sourceforge.net/projects/hilbert-curve/files.
> >
> > > On Aug 25, 4:27 am, Algo geek  wrote:
> > > > find the minimum no of moves by which a KNIGHT reaches the
> destination
> > > > from source in a 8x8 chess borad...
> >
> > > > **you will be given the starting position and ending position ..
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.> To post to this group, send email
> toalgoge...@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.
>
>

-- 
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] National Instruments: linked list subtraction

[Sathaiah Dontula]

@Raj,

How about doing like below ?

Convert A to base 10 number, numA
Convert B to base 10 number, numB,
Then take the difference  numC = abs(numA - numB),
Then convert numC to linked list with the digits

any comments ?, overflow condition is the problem here.

Thanks & regards,
Sathaiah Dontula

On Wed, Aug 25, 2010 at 3:24 PM, Raj N  wrote:

> Input : Two large singly linked lists representing numbers with most
> significant digit as head and least significant as last node.
> Output: Difference between the numbers as a third linked list with
> Most significant digit as the head.
> Eg:
> ---
> Input:
> A = 5->4->2->0->0->9->0->0
> B = 1->9->9
> Output:
> C = 5->4->2->0->0->7->0->1
> Required complexity :
> O(n)
> Constraint:
> Reversing linked list is NOT allowed
>
> --
> 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.

Re: [algogeeks] National Instruments: linked list subtraction

[Raj N]

My approach:
Use divide and conquer approach. i.e divide(a) divide(b) i.e first list and
divide(c) divide(d) of second list recursively (like mergesort). Then apply
subtract(a,c) and subtract(b,d)

It goes this way:
Make both lists of equal length by appending 0s at the beginning of smaller
list. Assuming list1 > list2
struct node
{
int data;
struct node *next;
};

void divide(struct node* root1,struct node *root2)
{
struct node *a;
struct node *b;
struct node *c;
struct node *d;
struct node *result;
int borrow=0;

if(root1==NULL || root1->next==NULL)
  return;
else
{
  split(root1,&a,&b);
  split(root2,&c,&d);
}
if(b->next==NULL && a->next==NULL)
{
subtract(b,d,&borrow,&result);
subtract(a,c,&borrow,&result);
}
}

void split(struct node* source, struct node **front, struct node **back)
{
struct node *slow, *fast;
slow=source;
fast=source->next;

while(fast!=NULL)
{
   fast=fast->next;
   if(fast!=NULL)
   {
  slow=slow->next;
  fast=fast->next;
}
  }
 *front=source;
 *back=slow->next;
  slow->next=NULL;
}

void subtract(struct node *n1, struct node *n2, int *borrow,struct node
**result)
{
 *result=(struct node*)malloc(sizeof(struct node));
 if(n1->data >= n2->data && !borrow)
 {
  result->data = n1->data - n2->data;

 }
  else if(n1->data > n2->data && borrow)
  {
result->data = (n1->data-1) - n2->data;
borrow = 0;
  }
   else if(n1->data < n2->data && !borrow)
   {
  result->data = (n1->data + 10) - n2->data;
borrow=1;
   }
   else if(n1->data <= n2->data && borrow)
   {
 result->data = (n1->data+9) - n2->data;
   }

// Insert the new node result at the beginning of result list
}

Tell me if there're any corrections !!


On Wed, Aug 25, 2010 at 3:24 PM, Raj N  wrote:

> Input : Two large singly linked lists representing numbers with most
> significant digit as head and least significant as last node.
> Output: Difference between the numbers as a third linked list with
> Most significant digit as the head.
> Eg:
> ---
> Input:
> A = 5->4->2->0->0->9->0->0
> B = 1->9->9
> Output:
> C = 5->4->2->0->0->7->0->1
> Required complexity :
> O(n)
> Constraint:
> Reversing linked list is NOT allowed
>
> --
> 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] National Instruments: points separated by a distance d

[Raj N]

Given location of huge number of points (you decide the data structure
to represent them). Write a function that returns the number of points
that are with distance D of a given point P.
Write function, complete with what data structures, function signature
etc.

-- 
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: linked list as tree

[Raj N]

@TurksHead: No its linked list to tree

On Wed, Aug 25, 2010 at 6:59 AM, TurksHead Education <
turksheadeducat...@gmail.com> wrote:

> I hope you are not talking about converting a tree into a linked list
> http://www.rawkam.com/?p=1139
>
>
>
> On Tue, Aug 24, 2010 at 7:20 AM, Raj N  wrote:
>
>> I came across this example that the leaves of the tree can be the nodes of
>> a linked list and  the inner nodes of the tree can be the number of left
>> subtrees. This kinda data structure can be used to find the kth element of a
>> linked list very easily. I was not able to implement such an idea.. Can
>> anyone help me doing that ?
>>
>>
>> On Tue, Aug 24, 2010 at 5:54 AM, Adam  wrote:
>>
>>> What do you exactly mean? You want to represent a linear structure by
>>> using a tree structure?
>>> You can imagine a linked list as a tree with all its root and inner
>>> nodes only having one descendent/child node.
>>>
>>> On Aug 23, 10:50 am, Raj N  wrote:
>>> > What will be the representation. How do you define left and right
>>> pointers
>>> > of the tree for a linked list.
>>> >
>>> > On Mon, Aug 23, 2010 at 10:35 PM, Yan Wang >> >wrote:
>>> >
>>> > > Actually, a linear data structure like a linked list is also a
>>> > > specific kind of tree structure.
>>> >
>>> > > 2010/8/23 Raj N :
>>> > > > Hi,
>>> > > > Could anyone help me representing linked list in the form a binary
>>> > > > tree ?
>>> >
>>> > > > Thanks !!
>>> >
>>> > > > --
>>> > > > 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.
>>>
>>> --
>>> 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.
>>
>
>  --
> 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.

Re: [algogeeks] Re: knight moves in chess

[Saikat Debnath]

In case of DP also, you will require to move in a BFS manner only, a neatly
written BFS will definitely make it fast.

On Wed, Aug 25, 2010 at 7:34 PM, krazee koder wrote:

> i think v can solve it by DP technique..similar to LCS prob or
> assembly line scheduling(Cormen et. al.)
>
> consider a two dimensional look up table. Each index refers to
> shortest distance taken by the knight to move that square.
> recursively try to call a fn. that changes source to the current
> square and stop till the current square reaches the destination.
> And then return the count...
>
> this is just my idea!!
>
> correct me if i am wrong...
>
> --
> 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.
>
>


-- 
Regards
Saikat Kumar Debnath
IIIrd year, Computer Science Deptt.,
Delhi Technological University,
(formerly Delhi College of Engineering)
Delhi

-- 
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: knight moves in chess

[krazee koder]

i think v can solve it by DP technique..similar to LCS prob or
assembly line scheduling(Cormen et. al.)

consider a two dimensional look up table. Each index refers to
shortest distance taken by the knight to move that square.
recursively try to call a fn. that changes source to the current
square and stop till the current square reaches the destination.
And then return the count...

this is just my idea!!

correct me if i am wrong...

-- 
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: knight moves in chess

[Chi]

A spacefilling curve is also known as a quadtree-representation of a
plane. It's subdivide a plane in continuous 4 cells. My linear
implementations gives at each step one leaf. What do you mean with
unweigthed und BFS (Breadth-First-Search, perhaps?). How can you add 8
vertices to the queue? It makes only sense to add 4 to queue with a
recursive approach!? A chessboard can be viewed as a graph of  2^n -
(n-1) edges. Sorry, I don't know the solution.

On Aug 25, 6:11 am, SHRISH MISHRA  wrote:
> The question is asking for a shortest path of some sort. If we consider each
> cell as a vertex, then the edges will be the possible knight moves. For
> example, the cell (2,3) would have an edge to (and from) the cell (4,4),
> assuming that there are no pieces occupying either cell. This graph is
> unweighted, so the most natural algorithm to use is BFS. Having realized
> this, the graph itself is not necessary anymore; we can just use the board
> directly. S is the source, and is the first cell/vertex added to the BFS
> queue. At each step, at most 8 more vertices will be added to the queue. BFS
> will stop when T is found or when the queue is empty (no path to T was
> found).
>
> Great Minds Discuss Ideas
> Average Minds Discuss Events
> Small Minds Discuss People
> Shrish Chandra Mishra
> CSE NIT,Allahabad
>
>
>
> On Wed, Aug 25, 2010 at 8:25 AM, Chi  wrote:
> > This is a spacefilling-curve. Optimal solution is a Hilbert-Curve or a
> > Morton-Curve. I have written one:
> >http://sourceforge.net/projects/hilbert-curve/files.
>
> > On Aug 25, 4:27 am, Algo geek  wrote:
> > > find the minimum no of moves by which a KNIGHT reaches the destination
> > > from source in a 8x8 chess borad...
>
> > > **you will be given the starting position and ending position ..
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.> To post to this group, send email 
> > toalgoge...@googlegroups.com.
> > To unsubscribe from this group, send email 
> > to>algogeeks+unsubscr...@googlegroups.com >  .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: linked list as tree

[Raj N]

@Yan Wang: Thanks a lot !!

On Wed, Aug 25, 2010 at 12:19 AM, Yan Wang wrote:

> I know what you mean now.
> It's not very hard to implement your idea.
>
> First, construct a usual binary sorting tree based on the original
> linked list. Notice that I also use the inner nodes to store the
> elements in the linked list rather than only using the leaf nodes. And
> the quantity feature you mentioned is considered as an affiliated
> feature of each node in the tree and can be computed recursivly. Thus
> the data structure of every node will have two domains to store. One
> is the data domain which has the node's key and the other one is the
> feature domain which maintains the node's feature.
>
> Then, compute the quantity feature of each node in the tree. According
> to your idea, the feature of a given node here is the number of nodes
> that the subtree, which roots in this given node, has. We denote this
> feature as f(n), where n represents the given node.
>
> Obviously, f(n) = f(n_lc) + f(n_rc) + 1, where n_lc represents the
> left child of node n and n_rc represents its right child. And if n is
> a leaf node, then f(n) = 1. This is clearly a recursive computational
> structure and just fits computing on a tree structure.
>
> For more detailed introduction, please refer to Chapter 14.2 "How to
> augment a data structure" of the book "Introduction to Algorithms,
> Second Edition, MIT Press".
>
> On Mon, Aug 23, 2010 at 6:50 PM, Raj N  wrote:
> > I came across this example that the leaves of the tree can be the nodes
> of a
> > linked list and  the inner nodes of the tree can be the number of left
> > subtrees. This kinda data structure can be used to find the kth element
> of a
> > linked list very easily. I was not able to implement such an idea.. Can
> > anyone help me doing that ?
> >
> > On Tue, Aug 24, 2010 at 5:54 AM, Adam  wrote:
> >>
> >> What do you exactly mean? You want to represent a linear structure by
> >> using a tree structure?
> >> You can imagine a linked list as a tree with all its root and inner
> >> nodes only having one descendent/child node.
> >>
> >> On Aug 23, 10:50 am, Raj N  wrote:
> >> > What will be the representation. How do you define left and right
> >> > pointers
> >> > of the tree for a linked list.
> >> >
> >> > On Mon, Aug 23, 2010 at 10:35 PM, Yan Wang
> >> > wrote:
> >> >
> >> > > Actually, a linear data structure like a linked list is also a
> >> > > specific kind of tree structure.
> >> >
> >> > > 2010/8/23 Raj N :
> >> > > > Hi,
> >> > > > Could anyone help me representing linked list in the form a binary
> >> > > > tree ?
> >> >
> >> > > > Thanks !!
> >> >
> >> > > > --
> >> > > > 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.
> >>
> >> --
> >> 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.
> >
>
> --
> 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://gr

Re: [algogeeks] Re: linked list as tree

[TurksHead Education]

I hope you are not talking about converting a tree into a linked list
http://www.rawkam.com/?p=1139



On Tue, Aug 24, 2010 at 7:20 AM, Raj N  wrote:

> I came across this example that the leaves of the tree can be the nodes of
> a linked list and  the inner nodes of the tree can be the number of left
> subtrees. This kinda data structure can be used to find the kth element of a
> linked list very easily. I was not able to implement such an idea.. Can
> anyone help me doing that ?
>
>
> On Tue, Aug 24, 2010 at 5:54 AM, Adam  wrote:
>
>> What do you exactly mean? You want to represent a linear structure by
>> using a tree structure?
>> You can imagine a linked list as a tree with all its root and inner
>> nodes only having one descendent/child node.
>>
>> On Aug 23, 10:50 am, Raj N  wrote:
>> > What will be the representation. How do you define left and right
>> pointers
>> > of the tree for a linked list.
>> >
>> > On Mon, Aug 23, 2010 at 10:35 PM, Yan Wang > >wrote:
>> >
>> > > Actually, a linear data structure like a linked list is also a
>> > > specific kind of tree structure.
>> >
>> > > 2010/8/23 Raj N :
>> > > > Hi,
>> > > > Could anyone help me representing linked list in the form a binary
>> > > > tree ?
>> >
>> > > > Thanks !!
>> >
>> > > > --
>> > > > 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.
>>
>> --
>> 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.
>

-- 
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: 5 pirate problem

[TurksHead Education]

A nice explaination with screenshots is given at

http://www.rawkam.com/?p=1156

On Tue, Aug 24, 2010 at 8:12 PM, Ajay Mohan  wrote:

> @ Dave
>
> Tat s really a cool solution Dave. So i thot of generalizing the solution.
> If there are 'N' pirates then
>
> * The eldest should give 1 gold coin to N/2 -1 ppl and he takes 100 -N/2
> +1
>
> Am i rite?
>
> --
> 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.

Re: [algogeeks] Re: Permutation.................

[TurksHead Education]

A nice explaination at

http://www.rawkam.com/?p=351

On Tue, Aug 24, 2010 at 6:49 PM, Chandan Balu  wrote:

> Can somebody please tell me, how does the above code for permutation
> works(Algorithms behind) please?
>
>
> On Mon, Aug 2, 2010 at 4:31 AM, bujji  wrote:
>
>>
>> Here is simple code to generate permutations
>>
>> #include "stdafx.h"
>>
>> #include
>>
>>  int Permute( char *, int);
>>
>> int PrintArray();
>>
>> int swap(char *, int);
>>
>> char A[]={'1','2','3','4','5','6','7','8'};
>>
>>
>>
>> main( )
>>
>> {
>>
>>
>>  Permute(A,sizeof(A)/sizeof(char));
>>
>>  return 0;
>>
>> }
>>
>>
>>
>> int Permute(char * a, int n)
>>
>> {  if(n==1)
>>
>>  { PrintArray();
>>
>>return 0;
>>
>>  }
>>
>>  int i=0;
>>
>>  for(i=0; i>
>>  {
>>
>>swap(a,i);
>>
>>Permute(a+1,n-1);
>>
>>swap(a,i);
>>
>>  }
>>
>> }
>>
>>
>>
>> int PrintArray()
>>
>> {
>>
>>  int i=0;
>>
>>  static int Number_of_Solutions=0;
>>
>>  printf("\n  Conf: %-4d  ",++Number_of_Solutions);
>>
>>  for(i=0;i>
>>printf("%c ",A[i]);
>>
>>
>>
>>  return 0;
>>
>> }
>>
>>
>>
>> int swap( char *a, int i)
>>
>> {
>>
>>  if(i<0)
>>
>>return -1;
>>
>>  int temp=*a;
>>
>>  *a=a[i];
>>
>>  a[i]=temp;
>>
>>
>>
>>  return 0;
>>
>> }
>>
>>
>> Regards,
>> Bujji
>>
>>
>> On Aug 1, 4:00 pm, UMESH KUMAR  wrote:
>> >  Write a C  code for generate all possible Permutation
>> >  as:- 1 2 3
>> > Total no. of Per=6
>> > also print all permutation
>> > as:- 1 2 3
>> >1 3 2
>> > 2 1 3
>> >2 3 1
>> >3 1 2
>> >   3 2 1
>> > if inpute is 1 2 3 2
>> >  total no of permutation = 12
>>
>> --
>> 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.
>

-- 
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: knight moves in chess

[SHRISH MISHRA]

The question is asking for a shortest path of some sort. If we consider each
cell as a vertex, then the edges will be the possible knight moves. For
example, the cell (2,3) would have an edge to (and from) the cell (4,4),
assuming that there are no pieces occupying either cell. This graph is
unweighted, so the most natural algorithm to use is BFS. Having realized
this, the graph itself is not necessary anymore; we can just use the board
directly. S is the source, and is the first cell/vertex added to the BFS
queue. At each step, at most 8 more vertices will be added to the queue. BFS
will stop when T is found or when the queue is empty (no path to T was
found).

Great Minds Discuss Ideas
Average Minds Discuss Events
Small Minds Discuss People
Shrish Chandra Mishra
CSE NIT,Allahabad


On Wed, Aug 25, 2010 at 8:25 AM, Chi  wrote:

> This is a spacefilling-curve. Optimal solution is a Hilbert-Curve or a
> Morton-Curve. I have written one:
> http://sourceforge.net/projects/hilbert-curve/files.
>
> On Aug 25, 4:27 am, Algo geek  wrote:
> > find the minimum no of moves by which a KNIGHT reaches the destination
> > from source in a 8x8 chess borad...
> >
> > **you will be given the starting position and ending position ..
>
> --
> 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.

Re: [algogeeks] Re: 5 pirate problem

[Apoorve Mohan]

techinterview.org

On Tue, Aug 24, 2010 at 8:12 PM, Ajay Mohan  wrote:

> @ Dave
>
> Tat s really a cool solution Dave. So i thot of generalizing the solution.
> If there are 'N' pirates then
>
> * The eldest should give 1 gold coin to N/2 -1 ppl and he takes 100 -N/2
> +1
>
> Am i rite?
>
> --
> 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.
>



-- 
regards

Apoorve Mohan

-- 
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] National Instruments: linked list subtraction

[Raj N]

Input : Two large singly linked lists representing numbers with most
significant digit as head and least significant as last node.
Output: Difference between the numbers as a third linked list with
Most significant digit as the head.
Eg:
---
Input:
A = 5->4->2->0->0->9->0->0
B = 1->9->9
Output:
C = 5->4->2->0->0->7->0->1
Required complexity :
O(n)
Constraint:
Reversing linked list is NOT allowed

-- 
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: BST Problem

[Giri]

@arvind:
had i knwn would hv posted it

On Aug 23, 8:59 am, "R.ARAVINDH"  wrote:
> @giri:
>
> can u post d correct answer??

-- 
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: BFS

[Giri]

hi Chi,

I didnt mean any disrespect to others. Thought I neednt be too
formal.Anyways sorry for the language.

On Aug 22, 9:57 pm, Chi  wrote:
> Hi Giri,
>
> I don't think you can ask for help this way. By stack or recursion can
> mean you are looking for a linear solution, too. Next time you should
> be more precise in your question and I don't think this leet speech
> will help you much. Although some can graps the sound, but it is hard
> to read, and not very respectfull to the others.
>
> That's my opinion.
>
> Kind regards,
>
> Chi
>
> On Aug 22, 6:20 pm, Giri  wrote:
>
>
>
> > by stacks i meant the usage of extra space.. recursion stack is
> > handled by the OS.. so it doesnt bother.. ok
>
> > On Aug 22, 1:08 pm, "R.ARAVINDH"  wrote:
>
> > > @manohar and @giri::
>
> > > doesn recursion itself use stacks( implicitly)??
>
> > > On Aug 18, 9:26 pm, Giri  wrote:
>
> > > > @manohar: thnks man.. this solution would be apt..
>
> > > > if there's any better algo which doesn't use an extra stack or queue,
> > > > but does the purpose in recursion, do post it..
>
> > > > On Aug 18, 8:01 am, Manjunath Manohar 
> > > > wrote:
>
> > > > > Tree *node
> > > > > for(i=1;i<=height;i++)
> > > > > {
> > > > >    levelorder(node,i);}
>
> > > > > void levelorder(Tree *node,int level)
> > > > > {
> > > > >    if(level==1)
> > > > >      printf(node->value);
> > > > >   else
> > > > >      levelorder(node->left,level-1)
> > > > >      levelorder(node->right,level-1);
>
> > > > > }

-- 
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.