Offered By

Saint Petersburg State University

About this Course

4.4

7 ratings

•

1 reviews

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....

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 5-8 hours/week...

Subtitles: English...

Start instantly and learn at your own schedule.

Reset deadlines in accordance to your schedule.

Suggested: 5-8 hours/week...

Subtitles: English...

Week

1We'll begin with introduction to the world of competitive programming — the rules, specialties and helpful tips on taking part in competitions in general. In a separate lesson, we'll learn how to test programs: what kinds of test cases there are, how to organize the search for a bugtest, and particularly a method of automating testing called stress-testing....

9 videos (Total 74 min), 2 readings, 2 quizzes

Specifics of Programming Competitions11m

Problem Example8m

Steps in Solving a Problem6m

Soft Skills4m

Competitions Review8m

Testing, Sample Tests, Min/Max Tests11m

Custom Cases and Testing Workflow7m

Stress-testing10m

Welcome!4m

Solution to Problem 1-4: Straight Flush10m

Inventing Tests8m

Week

2In 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....

9 videos (Total 66 min), 1 reading, 2 quizzes

What is Readability?5m

Intuitive "Proofs" are wrong5m

Defining solution set7m

Recursive backtracking7m

Worst cases6m

Big-O notation10m

From theory to practice7m

How to make a solution faster9m

Solution to Problem 2-4: Expression Evaluation10m

Time complexity6m

Week

3In competitive programming, there are a lot of things to stumble upon — if you don't know them first! We'll delve into how numbers are represented in computers, identify the most common issues with integer and floating point arithmetic, and learn to overcome them. We'll also discuss how to get stuck less in general, especially when debugging solutions....

11 videos (Total 78 min), 1 reading, 3 quizzes

Dealing with Overflow5m

Non-integers8m

Fixed Point Numbers and Errors7m

Floating Point Numbers6m

Where and How to Use Doubles10m

More on Floating Point8m

Debugging Small Programs5m

Simplifying Code7m

Double-checking5m

Upsolving7m

Solution to Problem 3-4: Binary Knapsack10m

Numbers10m

Upsolving2m

Week

4We continue considering common struggles arising in competitive programming. We start by learning how to prove that a natural greedy algorithm is correct. We also discuss programming languages: what features are most helpful on competitions, and what are the advantages and pitfalls of several frequently used languages. Finally, we study an essential and easy-to-implement data structure: the segment tree....

14 videos (Total 97 min), 1 reading, 2 quizzes

Warmup7m

Proving Correctness7m

Activity Selection9m

Maximum Scalar Product6m

Greedy Ordering6m

Segment Tree Structure4m

Summing a Segment7m

Modifying an Element4m

Basic Data Structures5m

Advanced Data Structures and I/O7m

C++11m

Java5m

Python8m

Comparing Languages4m

Solution to Problem 4-4: Maximal Sum Suba10m

Segment Tree6m

The Saint-Petersburg University (SPbU) is a state university, located in Saint-Petersburg, Russia. Founded in 1724, SPbU is the oldest institution of higher education in Russia. At present, there are more than 30 000 students in SPbU studying 398 programmes...

When will I have access to the lectures and assignments?

Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

What will I get if I purchase the Certificate?

When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

What is the refund policy?

Is financial aid available?

More questions? Visit the Learner Help Center.

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