|
Afaik it might be NP-hard so bad luck there with the simple part.
As in you'll never get optimal result in a polinomial time so very fast your program will have to be running for months to get a full result.
|
|
|
|
|
that would be my concern as well. I have no way to prove it but making that sort of schedule seems reminiscent of the knapsack problem which is NP-Complete.
Otherwise [Microsoft is] toast in the long term no matter how much money they've got. They would be already if the Linux community didn't have it's head so firmly up it's own command line buffer that it looks like taking 15 years to find the desktop.
-- Matthew Faithfull
|
|
|
|
|
wrote: making that sort of schedule seems reminiscent of the knapsack problem which is NP-Complete.
I remember my Algorithms Analysis professor talk about this very thing.
"I guess it's what separates the professionals from the drag and drop, girly wirly, namby pamby, wishy washy, can't code for crap types." - Pete O'Hanlon
|
|
|
|
|
|
Hmmmm, interesting....
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
|
|
|
|
|
About Floyd's Cycle Detection,
It can only "detect" a loop in a Linked List right?
it can't tell where the loop exists...
The Only Solution i got to "fix Loops" in Linked list is O(n^2)
(involves creating a newlist, nodes are added if searching them in the new list fails...if node is found then adding prcedure stops..)
is there anything more effiecient?
Also Can Someone explain Brent's Algorithm (wiki confused me) 
modified 20-Oct-19 21:02pm.
|
|
|
|
|
Seriously?? No one can help me??
modified 20-Oct-19 21:02pm.
|
|
|
|
|
OK, I'll give it a shot. The basic algorithm moves two pointers through a linked list. One pointer takes single steps and the other takes double steps. If there's a cycle, the two pointers will eventually point to the same node. The algorithm doesn't tell where the loop is.
Here's my extension to Floyd's Algorithm. You mentioned O(n^2) so I assume time is more important to you than space.
1. Count the number of times the single-step pointer is advanced. When the loop is detected you know its length is definitely less than or equal to this counter.
2. When the loop is detected, you know the node both pointers reference is definitely in the loop. Save this pointer.
3. At this point create a hash table big enough to hold pointers to all nodes in the loop. (You can do this because the counter gives you an upper bound on the loop size.)
4. Continue chaining through the loop in single steps. Add each node pointer to the hash table. Compare each node pointer to the saved pointer. When you find a match, you know the whole loop is in the hash table.
5. Go back to the start of the list, and chain through it again, checking if each node pointer is in the hash table. When this happens, you've identified where the cycle begins.
Alternative: If you have a tiny loop at the end of a very very long linked list and you want to optimize space, after Step 2 go through the loop again and count the number of nodes in the loop. The hash table only has to hold this number of pointers, which is much smaller than the count from Step 1. (It will be a bit slower because you have to traverse the loop an extra time to count its length.)
The running time is O(n). We can call this the Floyd-Balkany Algorithm.
|
|
|
|
|
Hi,
if you have the memory for a big hash table, you probably can also add a single bool to each
node (call it "visited"); initialize at false, test for false and set true on each visit,
until a true is revisited. No need for two pointers, and certainly not O(n^2).
However, not reentrant.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
But then you have to carry the overhead for the extra bool throughout the whole use of the linked list, instead of a one-time test.
|
|
|
|
|
bools aren't that expensive nowadays; of course they don't generate revenue when compared
to a sophisticated algorithm that carries your name...
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
What if, we want to reinitialize the boolean (to false),we'll need to traverse the list (hence getting caught in the loop)....it's like a Catch-22 situation...
Also, as mentioned,we have a large overhead...
here's a page i found... http://ostermiller.org/find_loop_singly_linked_list.html discussing some Incorrect "Solutions" (including the Boolean Method)...
But, still no Brent's Algorithm?? eh?  
modified 20-Oct-19 21:02pm.
|
|
|
|
|
st0le wrote: if we want to reinitialize the boolean (to false),we'll need to traverse the list
if you need it more than once, use one of the following:
1. a collection that allows you to iterate all the nodes without following the normal links;
2. a generation number that increments every time you start a cycle test; it gets initialized
only once (at node creation time), and it gets compared and stored during a cycle test.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Making 'b' the subject
square root( ( b+1 ) / b )= a
We know the answer is
1/(a<sup>2</sup> - 1)
Our workings
Get rid of square
(b+1) / b = a<sup>2</sup>
Then - get rid of single b
b+1 = b.a<sup>2</sup>
Then the 1
b = (b.a<sup>2</sup>) - 1
then..... stuck. No idea.
we tried
(b / a<sup>2</sup> -1 ) = b which is as near as I got.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
modified on Sunday, February 24, 2008 8:40 AM
|
|
|
|
|
|
Hi Malcolm,
Malcolm Smart wrote: My boys (not mine - honest!!)
Seems to me the difference is only a matter of time.
Malcolm Smart wrote: b+1 = b.a2
almost there. It is hard to believe you get stuck at this point.
Move all the terms containing b to one side, all other to the other and you get
b.a2 - b = 1
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Hi Luc! Had a sneeky feeling you might turn up.
Luc Pattyn wrote: Seems to me the difference is only a matter of time.
 Can't believe how much I've forgotten (or never knew!)
Luc Pattyn wrote: almost there. It is hard to believe you get stuck at this point.
Move all the terms containing b to one side, all other to the other and you get
b.a2 - b = 1
We've been here - we can't the get a2 - 1. You managed to tease an answer out me before regarding lemmings so I know you're not gonna give me the answer, but there is some obvious algebraic rule I am missing.
I need to get down to a single b on one side of the equation. If I take the a2 over to get 1/a2, I am left on the left hand side with b-b, which equals zero, so that seems wrong. We took the a2-b over, giving us b= 1/a2-b, which is very nearly there, except it should ne a2-1, not a2-b. (maths isn't my main thing - you can tell!)
My son is convinced the book is wrong - can you at least confirm
b = 1 / (a<sup>2</sup> - 1)
is correct?
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
|
I'll never forget those lemmings that approach a lethal ravine at high speed, suddenly
fall down strictly vertically, at a constant speed, and survive it all.
Malcolm Smart wrote: b = 1 / (a2 - 1)
is correct.
Fact: you can't "take a2-b over", taking over basically means you add something both
left and right in such a way that it cancels out something on one side. Now what would you add
to get rid of b.a2? certainly not a2!
Hint: if x.y = z how much is x? so try bringing your equation in a similar form.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
I either get b-b on the left, or b back on both sides!
(a2 = a2) <-- saves typing html tags for sup
b.a2-b=1
(b.a2)-b=1
b.a2 = 1 + b
b = (1 + b) / a2
but don't know how this then gets to
b = 1 / (a2 -1) There must be something so obvious I am missing, but I have to give up at this point (my son already has - he will learn soon that isn't an option sometimes in the real world) - my own work is pressing as I am having to work weekends at the moment. I will get this solved, but have to leave it until in the week.
Thanks Luc - appreciate your help.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
|
You can factor the lefthand side b.a2-b=1 into b and something,
then you have the form x.y=z which just requires a division.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Luc Pattyn wrote: You can factor the lefthand side b.a2-b=1 into b and something
Waheeeyyy!!! I just called him down and asked him to factorise
b.a2-b
b(a<sup>2</sup>-1) which gives
b(a<sup>2</sup>-1) = 1
b = 1 / (a<sup>2</sup> - 1) It's all about applying what he knows. He didn't think to factorise ( I didn't know you could!). Thanks a million Luc. He only has another 12 to do!! I'm going to have to really get into this stuff - it's actually quite cool.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
|
You're welcome.
Malcolm Smart wrote: It's all about applying what he knows
Of course. Don't apply what you don't know, but don't forget to apply what you do know; what is
the purpose of knowing something, if you don't apply it...
Malcolm Smart wrote: I'm going to have to really get into this stuff
Knowledge is hereditary, it will find its way up or down. 
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Of course this is probably way too late to help but...
The key here is that you need to isolate b
starting from your step:
(b+1) / b = a^2
this is equal to:
(b+1) * (1/b) = a^2
multiply out left side:
(b/b) + (1/b) = a^2
reduce (b/b):
1 + (1/b) = a^2
subtract 1 from both sides:
1/b = a^2 - 1
multiply both sides by b:
b/b = (a^2 - 1) * b
multiply both sides by 1/(a^2 -1):
(1/(a^2 - 1))*(b/b) = (a^2 - 1) * (1/(a^2 - 1)) * b
reduce both sides:
1/(a^2 - 1) = b
|
|
|
|
|
Simpler way
(b+1)/b=a^2
(b/b) + (1/b)=a^2
1 + (1/b) =a^2
(1/b)= a^2 - 1
=> b= 1/(a^2-1)
|
|
|
|
|
Thats the same thing as I posted. I just included all the steps that you left out which would be required by a math teacher who is actually teaching this stuff
Although I could have sworn that the entire other thread didn't exist from 2 weeks before walking them through it when I posted this....
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
