d2jsp
Log InRegister
d2jsp Forums > Off-Topic > Computers & IT > Programming & Development > Greedy Or Not Greedy Algorithm?
Prev12
Add Reply New Topic New Poll
Member
Posts: 3,172
Joined: Nov 29 2011
Gold: 0.00
Nov 9 2012 07:57am
Quote (carteblanche @ Nov 8 2012 08:59pm)
If it doesn't have to be optimal and you dont have to actually construct it, then what's the point? you can just return length() * 2 - 1, which is the result of appending itself in reverse (minus the last character)

abcd -> abcdcba





wat


You remove the leetters to test the word, not to make a palindrome from it.
And yes, it's easy to do that but the algorithm has to be greedy otherwise it's not fit for what i want.
Member
Posts: 4,605
Joined: Sep 15 2011
Gold: 9,464.00
Nov 9 2012 12:13pm
you need to ask better questions. you still haven't even showed that your algorithm is correct in the first place.

greedy algorithm simply means picking the locally optimal choice every step of the way, and the solution must be at least locally optimal (by definition). but you haven't really quite defined the metric for what "optimal" is to begin with. is it based on the length of the word? is it based on the number of steps you take to get the word?
Member
Posts: 3,172
Joined: Nov 29 2011
Gold: 0.00
Nov 9 2012 04:52pm
Quote (irimi @ Nov 9 2012 03:13pm)
you need to ask better questions.  you still haven't even showed that your algorithm is correct in the first place.

greedy algorithm simply means picking the locally optimal choice every step of the way, and the solution must be at least locally optimal (by definition).  but you haven't really quite defined the metric for what "optimal" is to begin with.  is it based on the length of the word?  is it based on the number of steps you take to get the word?


that's what Im asking lol
I came to the conclusion that it's not greedy at all.
As you said, greedy algorithms take decisions that look better for 'em at that moment expecting to reach an optimal solition at the end, which is not always true.
My algorithm has only one decision to make, or no decision, just do one thing always.
But it does work, its isnt greedy, but works.
Member
Posts: 4,605
Joined: Sep 15 2011
Gold: 9,464.00
Nov 9 2012 05:03pm
not the way your algorithm is written. maybe your code does something different from what you described, but what you've described is incorrect according to your own example.

see post #7.
Member
Posts: 3,172
Joined: Nov 29 2011
Gold: 0.00
Nov 9 2012 05:41pm
Quote (irimi @ Nov 9 2012 08:03pm)
not the way your algorithm is written.  maybe your code does something different from what you described, but what you've described is incorrect according to your own example.

see post #7.


What I have to do, is to get a word for example, "banana" and make a palindrome from it. The fact that I remove letters from it is to compare and check if there's a palindrome at the end of it. If there is, my task is simple, i just have to add that firsts words to the end of the word.

BANANA -> has a palindrome at the end which is ANANA.
So to make a palindrome from BANANA I should just add a 'B' at the end :BANANAB .

Got it?
Member
Posts: 4,605
Joined: Sep 15 2011
Gold: 9,464.00
Nov 9 2012 06:27pm
ok. that's very different from what you described previously. and yes, that works.

and yes, that's arguably a greedy algorithm, because it assumes every step of the way that you will be creating the shortest possible palindrome out of the word.
Go Back To Programming & Development Topic List
Prev12
Add Reply New Topic New Poll