You need to have idea about algorithm design techniques such as Greedy
method and Dynamic Programming for these kind of problems.
(1) Greedy method always selects local optima to achieve global optima.
This is very intuitive method and simple to implement, but doesn't always
yield optimal solutions.
(2) More sophisticated design method is "Dynamic Programming" - with which
we can find polynomial time solutions for many seemingly exponential
problems - especially for optimisation problems.
Dynamic Programming, however, is not the panacea for all optimisation
problems, we've to mind the fact that, there are problems which don't have
polynomial-time algorithmic solutions -- even when dynamic programming is
used. Thus, before applying dynamic programming, we need to check for
following properties in the given optimisation problem --
--> Whether the given problem exhibits the property called "Optimal
Substructure" i.e. whether the optimal solutions to sub-problems yield
optimal solution to main problem? Sub-problems are obtained by reducing the
magnitude of given problem.
The difference between dividing a problem into sub-problems in two
algorithmic design techniques -- "Dynamic Programming" and "Divide and
conquer" is .... while subproblems' sizes are almost half the size of main
problem in "divide and conquer", they differ often by 1 or 2 in "Divide and
Conquer" ... i.e. A problem of input size "n" is divided into n/2, n/2 in
"divide and conquer, in dynamic programming its divided into "n-1" and "1" .
---> Whether the subproblems itself follow some kind of left-to-right
ordering or not ?
For example, in order to find a maximal increasing subsequence of "n"
numbers, we need to find such subsequences for "x" numbers ( x< n) ( which
are subproblems of given problem) ... and finding solution for sub-problem
of "x" ( of n-1 elements) depends upon finding optimal solution for
sub-problem of "y" ( say, n-2 elements) which has lesser number of input
numbers than "x" ...
Please read extensively about dynamic programming, from any algorithms text
book. And the most important thing is do the exercises.
Following are the some example problems which can be solved by dynamic
programming:
(1) Maximum incrasing subsequnce in given sequence of numbers
(2) Maximum common subsequnce of two sequences of numbers
(3) Maximal palindromic substring of a given string
(4) Maximal palindromic subsequence of a given string
etc.
for example: see these list of problems --
http://people.csail.mit.edu/bdean/6.046/dp/
And try to write proper working programs for all the problems, instead of
just satiating yourself with writing pseudo-codes.
All the best,
Bhaskar
-Bhaskar
On Tue, May 1, 2012 at 4:26 PM, Ravi Ranjan <ravi.cool2...@gmail.com> wrote:
> We have been given a deck of cards and each combination has a rating eg 3
> As is higher than 2 As 1K etc.
> Write an algorithm such that the probability of picking 3 or 5 or 7 cards
> from the deck results in high rating
>
>
> plzzz tell how to approach these kind of problems???
>
> --
> 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.
>
--
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.
