@avi... i didn't quite fully understand the intent of the comment... u
had initially said greedy would make wrong choices 3->5->4 and hence
give wrong minimum number of jumps while DP would give 3->4... hence i
responded saying that if we go greedy on a different function, greedy
will yield the right result as well... and in a shorter time
On Jan 16, 12:28 pm, Avi Dullu <avi.du...@gmail.com> wrote:
> @svix that is precisely the reason why i gave my greedy approach first and
> then the pseudo code and then the example, also I mentioned that greedy can
> be be of different *locally optimal policies* so they *may* have a higher
> running time than the corresponding DP solution.
>
> regarding "your algorithm should be greedy on" .. it depends solely on me as
> to what I want to be greedy upon, given that I can provide a proof that the
> approach will always work. Like in interval scheduling problem there are
> numerous different greedy scheduling policies, but just one can be proved to
> work for all the cases.
>
> Programmers should realize their critical importance and responsibility in a
> world gone digital. They are in many ways similar to the priests and monks
> of Europe's Dark Ages; they are the only ones with the training and insight
> to read and interpret the "scripture" of this age.
>
> On Mon, Jan 17, 2011 at 1:52 AM, SVIX <saivivekh.swaminat...@gmail.com>wrote:
>
>
>
>
>
>
>
> > @avi
>
> > regarding ur statement...
>
> > "
> > 3, 5, 3, 4, 1, 3, 4, 5
>
> > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> > whereas DP would take 3, 4 ( 2 steps)
> > "
>
> > it depends on what you are greedy about... as i had mentioned earlier,
> > your algorithm should be greedy on how far the value you choose will
> > let you jump and not just on the size of the value... i.e, get the
> > local maximum for (currentIndex + array[currentIndex])
>
> > that is,
>
> > input: 3, 5, 3, 4, 1, 3, 4, 5
> > index 0 1 2 3 4 5 6 7
>
> > when index = 0, u can choose items at index 1, 2 and 3... go greedy on
> > f(index) = index + array[index]
>
> > so f(1) = 1 + 5 = 6
> > f(2) = 2 + 3 = 5
> > f(3) = 3 + 4 = 7
>
> > plainly, if u define ur greedy criteria right, u go for index 3...
>
> > On Jan 15, 11:15 pm, Avi Dullu <avi.du...@gmail.com> wrote:
> > > The greedy will always chose the maximum, so iff a 0 is chosen, that
> > implies
> > > one cannot reach the end of the array.
>
> > > Programmers should realize their critical importance and responsibility
> > in a
> > > world gone digital. They are in many ways similar to the priests and
> > monks
> > > of Europe's Dark Ages; they are the only ones with the training and
> > insight
> > > to read and interpret the "scripture" of this age.
>
> > > On Sun, Jan 16, 2011 at 12:16 PM, SVIX <saivivekh.swaminat...@gmail.com
> > >wrote:
>
> > > > thinkin abt this again, there may be a slight problem with
> > > > straightforward greedy...
> > > > note that reaching 0 doesn't let u move forward...
>
> > > > On Jan 15, 12:54 pm, Avi Dullu <avi.du...@gmail.com> wrote:
> > > > > @jammy Thanx for the elongated description :)
>
> > > > > Yes, I feel I probably gave a DP solution wrongly to the Greedy
> > approach.
> > > > > But just to clarify, Greedy does not solve any subproblems, it just
> > makes
> > > > a
> > > > > locally optimal choice and proceedes towards a global optimal
> > strategy.
> > > > And
> > > > > your point that greedy usually takes lesser time than DP also stands
> > > > > correct, but there are a lot of exceptions wherein the choice of
> > local
> > > > > optimal strategy may be of very high order, and thus perform worse
> > than
> > > > DP.
>
> > > > > Just to rest (and clarify) my argument, the following is the greedy
> > > > approach
> > > > > I feel, *will* fail:
>
> > > > > for i = 1; i < n; i++
> > > > > next_jump_will_be_from_index = index of max(input[ i ... i +
> > input[i]
> > > > ])
>
> > > > > i.e. after each jump, greedy strategy is to choose the next jumping
> > point
> > > > as
> > > > > the one which has maximum value
>
> > > > > 3, 5, 3, 4, 1, 3, 4, 5
>
> > > > > in the above, the greedy would take 3 -> 5 -> 4 ( 3 steps)
> > > > > whereas DP would take 3, 4 ( 2 steps)
>
> > > > > and if you notice, the implementation of this greedy (without using
> > fancy
> > > > > RMQ/segment trees) would still be O(n^2) or O(nlogn) (using
> > RMQ/segment
> > > > > trees)
>
> > > > > Programmers should realize their critical importance and
> > responsibility
> > > > in a
> > > > > world gone digital. They are in many ways similar to the priests and
> > > > monks
> > > > > of Europe's Dark Ages; they are the only ones with the training and
> > > > insight
> > > > > to read and interpret the "scripture" of this age.
>
> > > > > On Sun, Jan 16, 2011 at 1:39 AM, Jammy <xujiayiy...@gmail.com>
> > wrote:
> > > > > > @svix, I think pacific means takes i+v, But it still won't give the
> > > > > > global optimal
>
> > > > > > @Avi, I am not an expert on greedy algorithm and some problems may
> > be
> > > > > > solved by using greedy. But as far as I understand, the difference
> > > > > > between DP and Greedy is DP makes use of the solution of the
> > > > > > subproblems while greedy doesn't. DP solves current problem by
> > solving
> > > > > > subproblems first and then making the choice. Greedy solves current
> > > > > > problem by making a choice and solving subproblems. (see
> > CLRS).That's
> > > > > > why greedy gives me this idea that it usually takes less time then
> > > > > > DP.
>
> > > > > > In your latest post, it appears to me you are using DP instead
> > greedy
> > > > > > because your solution to current problem is built upon the solution
> > of
> > > > > > subproblems.
>
> > > > > > Please give me your input.
>
> > > > > > On Jan 15, 12:59 pm, SVIX <saivivekh.swaminat...@gmail.com> wrote:
> > > > > > > actually, there is a way t do this in greedy... instead of taking
> > the
> > > > > > > local maximum value v for an index i, take the local maximum f(v)
> > = i
> > > > > > > + v... this will get you the right answer...more efficient than
> > DP?
> > > > > > > that i'm not sure... but average case will be close to linear....
>
> > > > > > > On Jan 14, 9:29 pm, SVIX <saivivekh.swaminat...@gmail.com>
> > wrote:
>
> > > > > > > > @pacific..
> > > > > > > > the approach needs a little bit of tuning...
>
> > > > > > > > for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur
> > approach, u
> > > > > > > > will pick 9, 8, 7, 6 etc...
>
> > > > > > > > minimum jumps in reality is from 9 to 1 to 2.
>
> > > > > > > > On Jan 14, 8:19 pm, pacific pacific <pacific4...@gmail.com>
> > wrote:
>
> > > > > > > > > At each location if the value is k ,
> > > > > > > > > find the largest value in the next k elements and jump there.
>
> > > > > > > > > This greedy approach works in 0(n^2) and i believe it works.
> > If
> > > > not
> > > > > > can
> > > > > > > > > someone give me a counter example ?
>
> > > > > > > > > On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu <
> > avi.du...@gmail.com>
> > > > > > wrote:
> > > > > > > > > > @jammy Even I felt the same, but the greedy 'algo' u
> > suggest is
> > > > > > actually
> > > > > > > > > > IMHO not a greedy approach. You just take each arr[i] and
> > jump
> > > > > > *without
> > > > > > > > > > deciding a locally optimal policy* . SO, if u were to *see*
> > > > arr[i]
> > > > > > and
> > > > > > > > > > *decide* on the optimal policy I feel one would follow d
> > same
> > > > steps
> > > > > > as in a
> > > > > > > > > > DP solution. Its only just that the implementation would be
> > > > O(n^2).
> > > > > > Just to
> > > > > > > > > > add, this is the greedy approach I feel:
>
> > > > > > > > > > greedy_min_steps[n]
> > > > > > > > > > for i = 0; i < n; i++:
> > > > > > > > > > for (j = 0; j < input[i]; j++)
> > > > > > > > > > greedy_min_steps[ i + j ] = min(greedy_min_step[ i + j
> > ],
> > > > > > > > > > greedy_min_steps[ i ] + 1)
>
> > > > > > > > > > this is the greedy approach I build and I see this being
> > > > exactly
> > > > > > similar to
> > > > > > > > > > my DP approach. There are instances of greedy approach
> > based
> > > > > > algorithms
> > > > > > > > > > which have *optimized* DP counter parts. I feel this
> > problem is
> > > > one
> > > > > > of them.
> > > > > > > > > > More ideas ?
>
> > > > > > > > > > Programmers should realize their critical importance and
> > > > > > responsibility in
> > > > > > > > > > a world gone digital. They are in many ways similar to the
> > > > priests
> > > > > > and monks
> > > > > > > > > > of Europe's Dark Ages; they are the only ones with the
> > training
> > > > and
> > > > > > insight
> > > > > > > > > > to read and interpret the "scripture" of this age.
>
> > > > > > > > > > On Sat, Jan 15, 2011 at 2:14 AM, Jammy <
> > xujiayiy...@gmail.com>
> > > > > > wrote:
>
> > > > > > > > > >> @Avi Greedy approach doesn't work since you can't ensure
> > the
> > > > > > choice is
> > > > > > > > > >> locally optimum. Consider 3,9,2,1,8,3. Using greedy alg.
> > > > would
> > > > > > give
> > > > > > > > > >> you 3,1,8,3 while otherwise DP would give you 3,9,3.
>
> > > > > > > > > >> On Jan 14, 6:11 am, Avi Dullu <avi.du...@gmail.com>
> > wrote:
> > > > > > > > > >> > I guess u got confused with the comment I wrote, I have
> > > > added 2
> > > > > > print
> > > > > > > > > >> > statements and now I guess it should be clear to you as
> > to
> > > > why
> > > > > > the code
> > > > > > > > > >> is
> > > > > > > > > >> > O(n). The comment means that each element of the
> > > > min_steps_dp
> > > > > > will be
> > > > > > > > > >> > ACCESSED only ONCE over the execution of the entire
> > program.
> > > > > > Hence the
> > > > > > > > > >> outer
> > > > > > > > > >> > loop still remains O(n). The next_vacat variable if u
> > notice
> > > > is
> > > > > > always
> > > > > > > > > >> > incremental, never reset to a previous value.
>
> > > > > > > > > >> > #include<stdio.h>
> > > > > > > > > >> > #include<stdlib.h>
>
> > > > > > > > > >> > #define MAX 0x7fffffff
>
> > > > > > > > > >> > inline int min(int a, int b) {
> > > > > > > > > >> > return a >= b ? b : a;
>
> > > > > > > > > >> > }
>
> > > > > > > > > >> > int find_min_steps(int const * const input, const int n)
> > {
> > > > > > > > > >> > int min_steps_dp[n], i, temp, next_vacant;
> > > > > > > > > >> > for (i = 0; i < n; min_steps_dp[i++] = MAX);
>
> > > > > > > > > >> > min_steps_dp[0] = 0;
> > > > > > > > > >> > next_vacant = 1; // Is the index in the array whose
> > > > min_steps
> > > > > > needs to
> > > > > > > > > >> be
> > > > > > > > > >> > updated
> > > > > > > > > >> > // in the next iteration.
> > > > > > > > > >> > for (i = 0; i < n && min_steps_dp[n - 1] == MAX;
>
> ...
>
> read more »
--
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.
