Introductory tutorials for competitive programming

Pre-requisite: Knowledge and understanding of basic constructs of a programming language

Mathematics

1. Basic Number theory
   • Motivation and concept of modulo(mod)
   • Addition, subtraction and multiplication under modulo
   • Prime numbers(Some important properties)
   • Euclid’s GCD algorithm
   • Appendix: Division under modulo:
2. Sets
   • Venn diagrams
   • Set builder notations
   • subsets
   • Union, intersections, difference, membership
   • Set equality
   • Empty, Universal sets
   • Types of numbers and their symbols
3. Relations and Functions
   • Relations: Intuitive idea - member of set A is related to member of set B
   • Relations: Bigger picture - subsets of cartesian products
   • Concept of domain, co-domain of a relation
   • Direction in a relation
   • No pre-image can have more than one image
   • Concept of functions
   • Concept of domain, range of a function
   • Functions: Dependent and Independent variables
4. Intro to combinatorics
   • Principle of counting
   • Selection
   • Permutation
   • Factorials
   • Combinations
5. Logarithms
   • Idea of what is exactly logarithm of a number.
   • Properties.
   • Examples
6. Complexity Analysis
   • Notions of efficiency
   • How to measure efficiency - express runtime as a function of input size
   • Examples of measuring efficiency of some problems
   • Comparison of functions
   • Big-O notation

Language Constructs - C++ - 1

1. Introduction to C++
   • What is C++?
   • Why do we need another language?
   • Basic Structure of a C++ program
2. Data types
   • Recap of data types in Python
   • Declaring and initializing variables of different data types in C++.
   • Primitives datatypes in C++
     • int
     • long long
     • float
     • double
     • char
     • Bool
   • Overflow of values
   • Arrays
     • Motivation
     • Arrays in C++ including implementation
     • Difference between python lists and C++ array
3. Control flow
   • Decision Making statements
     • if
     • else if
     • else
   • and, or, not operators
   • Loops
     • for
     • while
4. I / O
   • Introduction(Motivation)
   • Concept of Streams
   • Input using cin
   • Input using getline
   • Output using cout
5. Functions
   • return types
   • Parameters
     • By value
     • By reference
6. Recursion
7. Notion of Structs
   • Basic Idea of an user defined data type.
   • Motivational Problem
   • Implementation in C++

Algorithms and data structures - 1

1. Searching
   • Motivational Problem
   • Linear Search
   • Binary Search
     • Algorithm
     • Complexity
     • Code
   • Think about implementing your own lower_bound().
2. Sorting
   • Insertion sort
     • Algorithm
     • Visualization
     • Code
     • Complexity Analysis
   • Merge sort
     • Merging two small sorted arrays to get another sorted array(Algorithm).
     • The idea of Divide and Conquer
     • Algorithm
     • Visualization
     • Code
     • Complexity Analysis

Language Constructs - C++ 2

1. STL - Containers(stack + queue + priority queue)
   • Stack(Motivational Problem, some important functions, LIFO)
   • Queues(Motivational Problem, some important functions, FIFO)
   • Priority Queues(Motivational Problem, some important functions)
2. STL - Containers(string + vector + pair)
   • Strings(Basic idea, some important functions)
   • Vector(Basic idea, some important functions)
   • Pair(Basic idea, some important functions)
   • Appendix: Iterators
3. STL - Algorithms + Set + Map
   • sort
   • upper_bound
   • lower_bound
   • set(Basic idea, some important functions of set container)
   • map(Basic idea, some important functions of map container)
4. Structs - Using them as comparators
   • Basic Idea of comparators
   • Implementation in C++.

Algorithms and data structures - 2

1. Dynamic Programming(DP)
   • Concept of Subproblem of a problem and overlapping subproblems.
   • DP as Recursion+Memoization
   • Linear DPs
   • Multi-dimensional DP
2. Graphs and Graph Algorithms
   • Modelling problems as graphs
   • Types of Graphs
     • Undirected Graphs
     • Directed Graphs
   • Representation of graphs
     • Adjacency Matrix
     • Adjacency list
   • Depth First Search(Algorithm, Code, Visualization)
   • Breadth First Search(Algorithm, Code, Visualization)
   • (Optional) Shortest Path Algorithms(Algorithms, Codes, Visualizations)
3. Sieves
   • Sieve of Eratosthenes
Credits: We would like to thank Swetanjal Dutta, Parth Mittal and Kushagra Arora from the community for preparing these tutorials. In case you would like to contribute in any kind of content, or can provide improvements in the existing one, you are most welcome. Feel free to get in touch with us on [email protected]