Final Remarks

Loading...

From the course by Saint Petersburg State University

Competitive Programmer's Core Skills

13 ratings

Saint Petersburg State University

Competitive Programmer's Core Skills

13 ratings

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.

From the lesson

Dynamic Programming

Dynamic programming is a powerful algorithmic paradigm with lots of applications in areas like optimisation, scheduling, planning, bioinformatics, and others. For this reason, it is not surprising that it is the most popular type of problems in competitive programming. A common feature of such problems is that a solution is usually easy to implement. This does not however mean that it is also easy to find a solution! Therefore, it is important to practice solving such problems. And this is exactly what we are going to do in this module!

Reconstructing a Solution4:03

Final Remarks6:17

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov

[MUSIC]

We conclude this part with a few final remarks.

First of all now, the running time of the design algorithm for

the edit distance problem is proportional to nm, so

the lengths of the two given words.

Also, the space requirement is also O of nm.

This is just because we need to store a 2D table.

So for spell checking programs, where we compute the edit distance

between two short words, the space requirement is not an issue at all.

It might, at the same time, be an issue in biological

obligations where we compute the edit distance between

sequences consisting of thousands or even millions of symbols.

So in this case,

storing this table would require us to allocate gigabytes of memory.

The good news at the same time is that it is not too difficult to

tweak our algorithm so that to reduce the quadratic space

requirement to just linear space requirement.

For this, note the following property.

When we filled in the table, for example, row by row, so

each time when we compute the value of a particular cell,

it totally depends on the values in this row, namely,

from the left neighbor and also from two values in the previous row,

namely, from the diagonal neighbor and from the top neighbor.

This suggests that instead of storing the whole table,

it is enough actually to store just two rows,

the current one that we are currently filling in, and the previous one.

So instead of storing all n rows, it is enough to store just two rows.

And the same trick actually applies to columns.

We can fill in the table column by column.

And instead of storing all possible columns,

we store just the two current columns, okay?

So this allows us to reduce the space requirement from O(nm) to O(min{n,m}),

so from quadratic to linear, okay?

It should be noted, however, the same time that for

reconstructing a solution, we actually need the whole table.

Because we need to trace the path from this corner of the table to that corner.

So it is not so easy to reconstruct the solution without storing the whole table.

But it is known how to do this, and

the corresponding algorithm was designed by Hirschberg.

So you can Google for Hirschberg algorithm, and

let me just give you the underlying idea.

In order to find an optimal alignment using only a linear amount of space,

we're going to do the following.

We're going to compute the edit distance between the corresponding two strings

in the same fashion as we did in our previous part.

At the same time when computing this, we're going also to compute the value k,

such that in an optimal alignment, the first half of

the word a is aligned to the first k symbols of the word b, okay?

Which also means that the second half is aligned to the last

m minus k symbols of b.

So we will first compute this value of k.

And then we will make two recursive calls, in order to compute the optimal

alignment for the first half of a and for the second half of a.

So in a sense, this is a nice combination of dynamic programming and

divide and conquer techniques.

So in general, it gets an algorithm working in, more or less, the same time,

so O(nm), and that uses only a linear amount of space, and

also is able, not only to compute the edit distance between two strings,

but even an optimal alignment, okay?

So, the last remark is that our algorithm can be

also easily transformed into an algorithm that computes

the way that edit distance between two strings.

So in this case, we do not read all aberrations as a unit cost operation.

So we might want to assign different cost to different operations.

For example, different costs to insertions, deletions, and

different costs to substitutions of some periods of samples.

So why we might want to use this?

Well, first of all, in spelling, in spell checking applications, it is natural

to assume that some substitutions are more probable than some others.

This of course depends on our keyboard layout.

Also in computational biology,

it is also the case that time substitutions are more likely than others.

Unfortunately enough,

our recurrence relations can be easily tweaked to reflect this fact.

Namely, instead of adding just one for insertions, deletions, and

substitutions, we need to add the cost of the corresponding deletions, the cost

of the corresponding substitution, or the cost of the corresponding insertion, okay?

So this concludes the part on the edit distance problem.

In the next part, we are going to design algorithms for

the well known knapsack problem.

This is a classical problem in combinatorial optimization, then for

the chain metrics multiplication problem.

And we will then review the whole part on dynamic programming.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play