[algogeeks] Re: A problem related to palindromes
hi daizi, I was expecting a solution that does not use suffix trees. Using suffix trees the problem can be solved easily, but I was just wondering if it is mandatory to use complex data structures like suffix trees to solve this problem. thx aj --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Is there any other way to find factorial of number except multiplication
well to find the factorial of very large numbers u can use linkedlist
or some other datastructure to hold the digits of the product and
manipulate the linked list..because the size of the linked list can
grow at runtime. I guess this will solve ur problem...
u need a linked list because the size of the integers on computers is
fixed and can hold up certain numbers (max int) so we need to tackle
that also
#includeiostream.h
#includeconio.h
#includeprocess.h
#define null 0
struct node {
int value;
node* next;
node() {
next=null;
}
};
void adjustList(node* p) {
node* count=p;
int temp;
int carry=0;
while(1) {
count-value += carry;
temp = count-value;
count-value = temp%10;
carry = temp/10;
if(count-next==null)
break;
count = count-next;
}
while(carry!=0) {
count-next = new node();
count = count-next;
count-value = carry%10;
carry /= 10;
}
}
//prints the factorial recurssively this reduces the range of the
factorial
void printFactorial(node* p) {
if(p==null)
return;
printFactorial(p-next);
coutp-value;
}
void main() {
clrscr();
int num;
node* head = new node();
node* count;
coutEnter the number whose factorial is to be found: ;
cinnum;
if(num0) {
coutNegative number factorial not defined;
exit(1);
}
for(int i=0;i=num;i++) {
count=head;
while(1) {
if(i==0) {
count-value=1;
break;
}
else {
count-value *= i;
if(count-next==null)
break;
count=count-next;
}
}
adjustList(head);
}
printFactorial(head);
getch();
}
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Chord Intersection
W Karas wrote:
wade wrote:
The algorithm is based on the recursive reduction:
intersections = intersections with chord with min(end - start) +
remaining intersections
It doesn't matter if the chord with min(end - start) is the shortest
chord or not.
I missed that. I didn't catch the fact that your algorithm works
correctly, if I name a chord (0,10), or if I name it (10,360).
The AVL tree is perhaps more complex than necessary. You can build
your tree balanced to begin with (its contents are the integers from 0
to N-1). Each node contains its descendant count.
So you mean sort all the points, then construct a fully balanced
tree? I think this might be slower than building an AVL tree
insert by insert, but that may be more than canceled out by
the faster searches.
When logical
deletions occur, don't actually remove any nodes. Just update the
descendant counts so that they reflect only living descendants.
This would reduce deletion time, but increase average search time.
I would guess you are right that, at least in the average case,
it would be an optimization. But it would take some complex
analysis to prove this.
But with a full tree you don't need to store or update pointers.
Consider the full balanced tree with three levels. The logical
structure is:
3
15
0 2 4 6
Define the level of a node as its distance from the leaves. (So
0,2,4,6 are at level zero).
The level of a node is also the number of trailing '1' bits in its
binary representation (something you can obviously compute in log n
time). The parent of a node, k, is
k + parent's level, if k/2 is even
k - parent's level if k/2 is odd.
So I can actually store my tree in an array, indexed by
endpoint-number. The only contents of each node are the population of
that node, and its children.
void DeleteEndpoint(unsigned int k)
{
unsigned int t = k;
int level = 0;
while(t 1)
{
++level;
t = 1;
}
while(k N)
{
--tree[k];
++level;
k += level - ((k1)1)*2*level;
}
}
which, I believe, will be fast compared to AVL deletion, except for the
last few deletions, where the AVL tree has gotten quite small.
Building my tree is a fast (O(N)), but I've also got to sort the
endpoints. However, I'd expect a heapsort to be faster than an AVL
build from unsorted data.
I may need some extra nodes (if there are 9 elements, I need node 11,
which is 8's grandparent). On the other hand, each node holds only a
count. In an AVL tree, each node will hold a count, two pointers, and
a flag.
Anyway, your algorithm is fine. You were lamenting about the need for
a complex AVL tree, so I was presenting an alternative, which I felt
was simpler. Of course if you know AVL, and you have to learn my
structure, the simplicity is debatable.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: A problem related to palindromes
linear worst case time. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A problem related to palindromes
aj wrote:
linear worst case time.
The best I can do is:
bool is_palin(const char x[], unsigned len)
{
if (len 2)
return(true);
for (unsigned i = 0, j = len - 1; i j; i++, j--)
if (x[i] != x[j])
return(false);
return(true);
}
unsigned prefix_palin(const char x[], unsigned len)
{
unsigned i;
if (len 2)
return(len);
i = len - 1;
for ( ; ; )
{
while (x[0] != x[i])
i--;
if (is_palin(x + 1, i - 1))
break;
i--;
}
return(i + 1);
}
But I think the time complexity would be quadratic on
a string such as xaaa
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
