@rahul go for programming challenges..by skienna(sponger verlag) On Sep 6, 12:26 am, Matteo Landi <[email protected]> wrote: > Why you said that? > Recursion is part of dynamic programming (top down approach), am i wrong? > > > > On Sat, Sep 5, 2009 at 6:13 PM, itissid<[email protected]> wrote: > > > Dude that factorial example is not DP!!! > > > On Sep 5, 12:43 am, Hawston LLH <[email protected]> wrote: > >> maybe you can read more on dynamic programming first, it is about how to > >> divide the problem into smaller piece of elements recursively. > > >> simple example - write a factorial function N! > > >> int factorial(int N) > >> { > >> //bounday or stopping condition > >> if (N<=1) > >> return 1; > > >> //here, try to process 1 step explicitly, and leave the > >> //remaining jobs to the recursive function > >> return N * factorial(N-1); > > >> } > > >> as you can see, to formulate a recursive function or algorithm, you need to > >> know what can be done "repeatedly" or recursively. > > >> In graph problem, sometimes the decision cannot determine on the cell > >> itself, it relies on neighbours. > >> But the decision of neighbours also relies on their neighbours.. there is a > >> repeat pattern, thus in general, you can write something like this: > > >> //pseudo code > >> void DoSomething(graph g, position p) > >> { > >> //similarly, you have boundary or stopping condition > >> if (stopping condition satisfied) > >> return; > > >> //try to process 1 step and leave the remaining jobs to > >> //the recursive function > >> for (n = neighbour of p in g) > >> { > >> //do something > >> ............. > > >> //pass on to recursive function to solve remaining > >> DoSomething(g, n); > > >> } > >> } > > >> So, you need to analyse the question and determine the part of recursion, > >> then implement the code. That is the very first step. After you know the > >> technique, then try to learn how to optimise the algorithm, since you can > >> solve the question using different ways of recursion, together with > >> suitable > >> data structure and use of memory. > > >> On Sat, Sep 5, 2009 at 2:59 PM, CodeJunky > >> <[email protected]>wrote: > > >> > thanks buddy!!!!!! > >> > im actually new in coding arena ..........well i understood the > >> > problem and sawmany implementations > >> > the thing is i have read quite a few graph algorithms but im unable to > >> > implement them in any problem > >> > since i donot have any other mentor or tutor ..........forums are the > >> > only source of learning > >> > I went through the top coder tutuorial of graph but i could not > >> > understand the problems discussed > >> > can anyone give me links to some straightforward problems so that > >> > gradually i reach a level where > >> > i can comprehend and code any graph problem > > >> > thanks and regards!!! > > >> > On Sep 5, 10:24 am, Hawston LLH <[email protected]> wrote: > >> > > 1. start from top to bottom, left to right, check each cell one by one. > >> > If > >> > > current location is already labelled, then label the locations stored > >> > > previously in the path with that label. Then clear the path vector and > >> > > continue step 1. > >> > > 2. otherwise, check north, west, east, south neighbour and get the > >> > minimum > >> > > location (x_min, y_min) > >> > > 3a. if min location is different from current location, then push/store > >> > > current location into the path vector and proceed to step 1 with the > >> > > min > >> > > location. > >> > > 3b. otherwise, meaning current location is a sink, label it with next > >> > > char C' and also label all locations stored previously in the path > >> > > vector > >> > > with C'. > > >> > > On Fri, Sep 4, 2009 at 7:37 PM, CodeJunky <[email protected] > >> > >wrote: > > >> > > > Can anyone please explain me the water shed problem and the graph > >> > > > approach > > -- > m...@http://matteolandi.altervista.org/
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
