During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Rust, Scala. We assume that you already know how to write simplest programs in one of these.
Summary
Loading...
Do curso por Saint Petersburg State University
Competitive Programmer's Core Skills
13 classificações
Na lição
Dynamic Programming 2
We continue applying dynamic programming technique to various problems.
Conheça os instrutores
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Alexander LogunovCompetitive Programming Co-coach at SPbSU
Kirill Simonov
Now, when we've seen several examples, let's summarize.
So we've discussed already several times
the most important and probably the most creative step in
designing a dynamic programming solution is defining the subproblem,
and writing down a recurrence relation allowing us to
express a solution for a subproblem through solutions to smaller subproblems.
There are two common ways of doing this.
The first way is by analyzing the structure of an optimal solution.
And the second way is by, first,
implementing a brute force solution and then optimizing it.
Let me also remind you how subproblems look like
for all the problems that we can see relating to these two modules.
So the first one is the longest increase in subsequence.
In this case, we defined the subproblem as specified by parameter I,
to be the length of an optimal increase in subsequences.
The longest increase in subsequences ending is the I's element.
In the edit distance problem where we need to
find the edit distance between two given strings,
the subproblem was essentially the same problem,
computing the edit distance between two prefixes of a given two strings.
For the knapsack problem where our goal was to fill in the bag of capacity W with items.
Optimally, we were solving subproblems for bags of smaller capacities.
Finally, for the chain matrix multiplication where we are given
N matrices and we need to multiply them optimally,
I mean in an optimal cost,
our subproblems were multiplying some contiguous subsequences of our N matrices.
So in general, when you have a problem
specifying a sequence or two sequences or three or something,
in many cases the subproblem is defined by considering
subsequences or prefixes or subtrees of the initial sequence.
Still it requires creativity, of course,
and practice to define the right notion of a subproblem.
So when the recurrence relation on subproblems is written down,
it is a technicality to convert it into a recursive algorithm.
So, for this you store the result of all subproblems in some table,
and before computing the result for
a particular subproblem you first check whether it is already stored in the table or not.
If it is stored you return it immediately.
So you start computing it only if you haven't computed it so far.
The next natural step is to convert a recursive algorithm into an iterative one.
This usually requires just initializing the table and
then fill going from smaller subproblems to larger subproblems.
In particular, this usually requires one to specify an order on all subproblems.
Right? The next step is proving an upper
bound on the running time of the result in the algorithm.
In many cases, a reasonable estimate is just to compute the number of subproblems and to
multiply it by the time taken to compute the solution for each subproblem.
The next step is to also implement unwind solutions.
So in many cases,
your first dynamic programming solution only computes cost of an optimal solution.
And to find an optimal solution itself,
you usually use a table to unwind an optimal solution.
You use a table of solution of all subproblems.
The next step is actually exploiting the structure
of the table of your iterative solution in order to check whether you can save space.
For example, as you remember in case of the knapsack problem,
or in case of the edit distance problem,
instead of storing the whole table one can store
just the current row and the previous row or the current column and the previous column.
This reduces the space requirement from quadratic to linear.
Finally, let's discuss advantages of recursive and iterative approach.
So the first advantage of an iterative approach is
that there is no recursion overhead in this case.
So instead of making recursive calls,
we're just filing in where there is a table.
And we're also using simpler data structure
just arrays instead of dictionaries, for example.
Another advantage is that just by looking at
the table and the way it is filled in you can actually save space.
Again, the example is the edit distance problem and the knapsack problem, for example,
where instead of storing the whole table it is enough to
store the current row and the previous row, for example.
At the same time, the advantages of the recursive approach are the following;
a recursive approach can still be faster and that
happens in cases where not all the subproblems need to be solved.
A good illustration of such a situation
is the knapsack problem as we've discussed already.
In the case when all the weights are divisible by some common factor, for example 100,
we are only interested in subproblems where the capacity of a bag is divisible by 100.
And, the recursive approach will only solve
such subproblems while the iterative approach
in this case will solve just all possible subproblems,
not only those where the capacity are divisible by 100.
In this case the recursive approach might be faster.
So this depends on the data set but still.
Another advantage is that sometimes it is easier to
implement a recursive approach just because in this case,
you did not need to specify the order of subproblems explicitly.
So the recursion will find its way to the answer itself.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2019 Coursera Inc. Todos os direitos reservados.
