What is Readability?

Loading...

En provenance du cours de Saint Petersburg State University

Competitive Programmer's Core Skills

13 notes

Saint Petersburg State University

Competitive Programmer's Core Skills

13 notes

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.

À partir de la leçon

CORRECTNESS FIRST

In this module, we'll start with the most basic things you need to actually solve algorithmic problems. First, we'll talk about structuring your code and intuition behind it — why it's very important, how to manage dependencies between parts of different purpose, how intuitive rules are enforced through formal invariants and conditions. We'll also identify a special class of solutions — brute force solutions — which are always correct, but often very slow. And we'll learn how to estimate running time of our solutions by using a powerful concept of big-O notation.

Managing Dependencies6:45

What is Readability?5:42

Rencontrer les enseignants

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

Let's consider a standard situation.

You completed a code, and you are ready to debug it.

And now you are reviewing each line of your code.

Suppose that you see this line,

p is set to q by 60 plus r. Any ideas what is meant here?

Perhaps you guessed that the code computes

time in minutes from midnight to the current time.

Q stores the current hour,

r stores the current minute,

and p stores the total time in minutes.

Note, that even in this case,

it is not so obvious.

Even if you guessed right,

maybe you've spent some time on it.

There could be surrounding lines that could help you to understand this code.

For example, you could look at input output formats,

and somehow realize the purpose of these variables.

But the point is that if these variables were given suitable names right away,

you would understand the meaning of this line faster.

Giving meaningful names to variables will not

only help your teammates to understand your codes,

it will also help you to understand it.

Have you ever found yourself in a situation that it is difficult

to get the main idea of your own code that your wrote,

say a year ago?

If yes, they probably know already that it

makes perfect sense to keep your code understandable.

At the same time, don't take it too seriously.

Of course, in some small tasks like short local loops,

single letter variables are more convenient.

A few words about code style.

Even if you don't work in team,

following some reasonable rules during coding also makes your code more clear.

That's why it's recommended to use indent,

spaces, and so on.

Consider the problem of computing the sum of

all integers closed cubes alpha one to 5,000.

The upper bound is not exclusive.

It is possible to find a formula that gives that answer,

but it is absolutely normal to write a simple loop for this task.

But what loop type to use?

There are basically two types of loops: loop with a pre-condition,

and a loop with a post-condition and there is a big difference between them.

Consider two examples.

Here we see an example of loop with a pre-condition.

The pre-condition here is i cubed is less than 5,000,

and it defines what must be true before anything in the loop.

In particular, if the condition is not satisfied from the very beginning,

the loop will not execute at all.

Here is an example of loop with a post-condition.

The post-condition here is also i cubed is less than 5,000,

and it says what must be true before continuing the loop.

It means that this loop always performs at least one iteration

because it just doesn't check the condition before the execution of the first iteration.

Both types of loops work fine,

but what if we change 5,000 to one?

There are no integers that are at most one and less than one simultaneously.

That's why the correct answer is zero.

And it is easy to see that a conditional loop remains correct.

But we can no longer use both conditions

here because a loop will perform the first iteration,

and it wants total sum.

We failed in the second case because loop invariant wasn't preserved.

Loop invariant is an assertion that must be true every time within a loop.

It is associated with a specific position in the loop.

In our task, we can come up with two examples of invariants.

First, i cubed is not greater than the one,

and is integer less than 5,000.

Second, sum equals sum of all i's seen so far.

Think which invariants are preserved in each case if we change 5,000 to one.

In the first version of task with upper bound of 5,000,

both types of loops preserve these invariants.

But when change 5,000 to one,

in the post-conditional loop first invariant fails.

Doing in the first iteration i equals one,

so i cubed is no less than the one because of

this sum is calculated incorrectly though the second invariant is preserved.

These situation tells us that we should be very careful with invariants.

Sometimes conditions in loops are more complicated than i cubed is less than 5,000,

and you need to be precise to write a loop correctly.

In other words, you should always convince

yourself that the code of your loop matches your logic.

Also be careful with common cases with empty sets.

For example, let's remember that task about the list of people.

If there are zero people in the list,

sum of age of all people is defined and equals zero.

So, we should also consider this case.

By the way our solution still works.

To summarize this lesson,

we can consider several ways to make our codes

more structured, understandable,and debuggable.

On several examples we've seen that this is a really

important and shortens the time of getting a written code.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play