Managing Dependencies

Loading...

Из курса от партнера Saint Petersburg State University

Competitive Programmer's Core Skills

1 оценки

Saint Petersburg State University

Competitive Programmer's Core Skills

1 оценки

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, Scala. We assume that you already know how to write simplest programs in one of these.

Из урока

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

Познакомьтесь с преподавателями

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

Hi everybody. My name is Aleksandr Logunov.

I am a competitive program inter-coach at St. Petersburg State University.

Experienced programmers know that programs almost never work correctly on the first try.

For this reason, be prepared to test and debug your program when you are done with it.

In this video, we will learn some of the basic practices

of writing code that will allow you to cage a box at early stages.

Imagine that your mobile phone or laptop doesn't work,

for example, the device doesn't turn on.

This usually happens because only one of it's parts gets out of order,

battery, motherboard, one of cables,

power bottom, and so on.

And more often, you are unable to understand what particular detail has broken down.

If you have a good understanding of the structure of your device,

you will disassemble the device,

inspect each parts separately,

and this will probably help you to resolve the issue.

But if your device is just like a sort of Greek for you,

the most likely end of the story is bringing it to service center.

And now, imagine that you complete a code that will solve a complex problem.

And you suddenly realize that your code doesn't work.

If it is difficult to break the code apart according to it's logic,

you will have to explore every line of the whole code.

Conversely, if your code is divided into

several blocks and you have a good understanding of the dependencies between the blocks,

you can analyze each block individually.

And besides, your code will be

clearer to another programmer who may need it in the future.

Let's illustrate this with a two example.

You have information about n people.

Assume that the information is stored at text file,

format is not important.

Your goals are, to compute the number of people that are employed at this moment,

and to compute the sum of ages of all people.

What you see here is a possible solution.

Here, we actually [inaudible] ,

compute required values and print them.

But don't you think that this code is not perfect?

It is not a well-structured codes.

The data is read and the number of employed people is computed at the same time.

The variables are initialized and the answers output practically.

Just imagine that a much more complicated task is written in the same style.

If there is a bug somewhere it will be very hard to locate it.

It makes sense to change this code to make it clear.

And this is an example of well structured code.

Logical thoughts are not mixed,

the dependencies between the parts of the codes are clearly visible.

Each part solves its own sub problem.

It is very natural to declare a separate function for each block.

The name of every function corresponds to the block,

so it help to understand what is happening in this block.

Initializing, reading, getting first value,

getting second value begins on this values.

Let's see how the code looks after this.

It makes sense to try to make each block to be responsible for its own simple task,

and to avoid tasks shared between blocks.

Otherwise, it becomes very difficult for you to track the progress of the task execution.

It is better to think how each sub problem

is interconnected with the other parts of the problem.

It is a good strategy to allocate

a special block or a sequence of blocks for each sub problem.

If your code is well structured,

it will make your life a lot easier.

For example, it will be easier to locate the bug.

Also, if sometime later you decide to improve your algorithm,

it will be easier for you to locate parts of your code that need to be adjusted.

Note, that the structure of blocks depends on many things.

There is no general recipe for breaking your code into blocks.

Another important thing is avoiding code copy pasting.

The reason is straightforward,

it's possible that a copied block of code is

bugging and by copying it you increase the number of bugs.

Each time when you have

two almost identical code blocks it is better to merge them into one.

For example, by defining a new function.

For example, when you have to display

variables of the same time in a very complicated format,

it is better to make a function for it and calls this function five times.

Of course your perfect code structure is not unique.

There are many ways of structuring a code reasonably.

After all, this is a matter of taste.

For example, you can choose a structure that is more natural for you,

or a structure which can be most conveniently

extended if the task becomes more complicated.

Sometimes, the only problem with code is that it's idea is wrong.

This can happen when you misunderstand the statement of the task,

or when you use algorithm incorrectly.

This is the most dangerous mistake for a competitive programmer.

Probably there are no bugs in your code but it will not work anyway.

When the code is well structured,

you have more confidence in itself.

This will allow you to switch to codes about

the correctness of your ideas at the right moment.

If you find problems with ideas,

it sometimes turns out that it's enough to change

atleast only some blocks without affecting others.

It's safe for you and saves your time.

Well written code is easier to manage,

sometimes the task may change.

For example, in the case of considered problem,

you may be asked to calculate not the sum of ages but the maximum of ages.

If you make miscalculations in fixed part of code you will only need to change this part.

Actually, the most important thing is to understand your code.

If you feel that something strange is happening in your code,

most likely you'll need to add more structure to it.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play