Udemy

Platform

English

Language

Software Engineering

Category

Competitive Programming

Master the Theory and Application of Algorithms and Data Structures to Excel in Programming Contests

4.74 (25 reviews)

Students

11.5 hours

Content

Sep 2021

Last Update
Regular Price


What you will learn

Competitive Programming

Algorithms

Data Structures

Programming

Merge Sort, QuickSort, Count Sort, Bucket Sort

Linear Search, Binary Search, QuickSelect, Two Pointer Technique

Stacks, Queues, Hash Tables, Hash Sets, Heap-Based Structures, Binary Search Tree-Based Data Structures, Coordinate Compression, Custom Comparators

Hash Functions, Collisions, Rabin-Karp, Sliding Window Technique

Greedy Algorithms

Iterative Complete Search, Backtracking, Permutations, Subsets, Pruning

Divide and Conquer, Binary Search the Answer, the Bisection Method

Dynamic Programming: Competitive Approach, Top-Down and Bottom-Up DP, Space Optimisation, Prefix Sums, Backtracking to Find Solutions

Graph Representation: Adjacency Lists, Adjacency Matrices, Edge Lists, Weighted and Unweighted Graphs

Graph Exploration: Breadth-First Search (BFS), Depth-First Search (DFS), Connected Components, Multi-Source BFS

Directed Graphs and Cycles: Topological Sort, Strongly Connected Components, BFS for Single-Source Shortest Paths

Shortest Paths: Dijkstra, Floyd-Warshall's, Bellman-Ford and Negative-Weight Cycles, Arbitrages and the Logarithm Trick

Trees: Special Properties, Faster Shortest Paths, Diameter, Minimum Spanning Trees

Union-Find Disjoint Sets: Optimised Implementation, Kruskal's Algorithm, Minimum Spanning Tree Variants

Strings: Dynamic Programming on Strings, Longest Common Subsequence, Edit Distance, Longest Palindromic Substring, Tries, Suffix Tries

Game Theory: States and Transitions, Minimax for Optimal Game Playing, Dynamic Programming To Recover Optimal Strategies

Approaching Interactive Problems


Description

Ready to take your programming skills to the next level? In this course, which will help both novice and advanced programmers alike, you will dominate the algorithms and data structures necessary to do well in contests and to gain a competitive edge over other candidates in software interviews.

There are many tricks which are gained through experience and competitive programmers have a sixth sense when it comes to breaking problems down into the building blocks that make up a solution and which many are reluctant to share. Here I will let you in on the techniques and the applications that are useful for the field, focusing on real problems and how they are solved, while giving you an intuition on what is going on under the hood and why these ideas work.

From dynamic programming to graph algorithms and backtracking, you will get to practise and feel confident about many topics, learning advanced concepts such as union-find disjoint sets, tries and game theory without feeling lost, and to apply new content as soon as you learn it, with over 100 suggested problems, both from past olympiads and online judges and some created by me specifically for this course. All of them come with detailed solutions. With this course, you will be ready to participate in online contests and informatics olympiads, and will have the experience necessary to continue advancing in this field. Are you ready to take this big step in your journey?


Screenshots

Competitive Programming
Competitive Programming
Competitive Programming
Competitive Programming

Content

Introduction

About the Instructor

Course Prerequisites

Course Structure

What is an Online Judge?

Online Judge Verdicts

Types of Problem in Programming Contests

I/O for Competitive Programming

Welcome Contest

Hints and Solutions

Sorting

Introduction to Section 2 and the Horse Race Problem

Sorting in C++ Using Custom Comparators

Structs and Overloading Comparison Operators

Merge Sort

QuickSort

DNA Sorting Problem

Count Sort

Football Problem

Bucket Sort

Bucket Sort Solution to the Football Problem

Problem Set 1

Hints and Solutions

Searching

Linear Search

Binary Search

QuickSelect

Two Pointer Technique: Start+End

Two Pointer Technique: Different Paces

Problem Set 2

Hints and Solutions

STL Data Structures: Stacks, Queues and BST- and Heap-based Structures

Stacks: bracket matching

Queues

Hash Tables and Hash Sets Introduction

Unordered (Hash) Sets and Maps in C++

Ordered Sets and Maps

Dictionaries

Coordinate compression

Custom Comparators for STL Data Structures

Problem Set 3

Hints and Solutions

Hashing

Hash Functions

Extra: Handling Collisions

Rabin-Karp Case Study: Pattern Search

Rabin-Karp Case Study: Polynomial Rolling Hash Functions

Rabin-Karp Case Study: Sliding Window Technique

Sliding Window Technique: Subarray Sums

Problem Set 4

Hints and Solutions

Greedy Algorithms

What are Greedy Algorithms?

Greedy Coin Change

Demonstrating Correctness Under Contest Time Pressure

Timetable Problem

Interval Covering

Sort -> Solve

Problem Set 5

Hints and Solutions

Complete Search

Complete Search Introduction

Backtracking Introduction

Backtracking: Permutations

Backtracking: Subsets

Pruning: Card Game

Iterative Complete Search

Problem Set 6

Hints and Solutions

Divide and Conquer

Revisiting Sections 2 and 3

Binary Search the Answer

The Bisection Method

Problem Set 7

Hints and Solutions

Dynamic Programming

Top-Down Fibonacci

Bottom-Up Fibonacci

How to Recognise and Approach DP Problems

Maximum One-Dimensional Range Sum

Space Optimisation

Optimal Coin Change 1

Optimal Coin Change 2

Backtracking to Find Solutions

Prefix Sums

Horses Problem Revisited

Horses Addendum

Problem Set 8

Hints and Solutions

Graphs 1: Graph Exploration

Graph Terminology

Graph Representation

Depth-First Search

Breadth-First Search

Farthest Node: BFS Application

Graph Sums: DFS Application

Connected Components

Labyrinth Problem Part 1: Single-Source BFS

Labyrinth Problem Part 2: Multi-Source BFS

Problem Set 9

Hints and Solutions

Graphs 2: Directed Graphs and Cycles

Exploring Directed Graphs

Topological Sort

Strongly Connected Components

Single-Source Shortest Paths: BFS

Problem Set 10

Hints and Solutions

Graphs 3: Shortest Paths

Weighted Graphs

Single-Source Shortest Paths: Dijkstra

All-Pairs Shortest Paths: Floyd-Warshall's

Bellman-Ford and Negative-Weight Cycles

Case Study: Arbitrages and the Logarithm Trick

Problem Set 11

Hints and Solutions

Trees

What Makes Trees Special

Shortest Paths

Tree Diameter

Minimum Spanning Trees: Prim's Algorithm

Problem Set 12

Hints and Solutions

Union-Find Disjoint Sets

UFDS Introduction

Speeding Up UFDS

UFDS VS Finding Connected Components

Example Application: Kruskal's Algorithm

Minimum Spanning Trees: Variants

Problem Set 13

Hints and Solutions

Strings, Tries and Trees

DP on Strings: Longest Common Subsequence

DP on Strings: Edit Distance

DP on Strings: Longest Palindromic Substring

Suffix Tries

Representing a Dictionary Using a Trie

From Suffix Tries to Suffix Trees

Suffix Trees: Insertion

Suffix Trees: Other Operations

Problem Set 14

Hints and Solutions

Game Theory: Minimax and Optimal Game Playing

States and Transitions

How to Always Win in 1-2-3

Tic Tac Toe AI 1: Introduction to the Project

Tic Tac Toe AI 2: Program Structure

Tic Tac Toe AI 3: Helper Functions

Tic Tac Toe AI 4: Minimax

Tic Tac Toe AI 5: Recovering the Optimal Move

Problem Set 15

Hints and Solutions

Extra: Interactive Problems

How To Approach Interactive Problems

Problem Set 16

Hints and Solutions

Farewell and Next Steps


Coupons

DateDiscountStatus
9/14/2021100% OFFExpired

3955152

Udemy ID

4/2/2021

Course created date

9/10/2021

Course Indexed date
Bot
Course Submitted by