Informatics \ CS

Mathematics

 Arithmetic :
 Integers, operations (incl. exponentiation), comparison
 Basic properties of integers (sign, parity, divisibility)
 Basic modular arithmetic: addition, subtraction, multiplication
 p Prime numbers
 Fractions, percentages

 Geometry :
 Line, line segment, angle, triangle, rectangle, square, circle
 Point, vector, coordinates in the plane
 Polygon (vertex, side/edge, simple, convex, inside, area)
 q Euclidean distances
 p Pythagorean theorem

 SET, Functions, Relation :

 q Functions (surjections, injections, inverses, composition)
 q Relations (reflexivity, symmetry, transitivity, equivalence relations,
total/linear order relations, lexicographic order)
 q Sets (inclusion/exclusion, complements, Cartesian products, power set

 Basic Logic:
 First-order logic
 Logical connectives (incl. their basic properties)
 Truth tables
 Universal and existential quantification (Note: statements should avoid
definitions with nested quantifiers whenever possible.)
 p Modus ponens and modus tollens

 Proofs Techniques :
 q Notions of implication, converse, inverse, contrapositive, negation, and
contradiction
 p Direct proofs, proofs by: counterexample, contraposition, contradiction
 p Mathematical induction
 p Strong induction (also known as complete induction)
 Recursive mathematical definitions (incl. mutually recursive definitions)
 Basics of Counting :
 Counting arguments (sum and product rule, arithmetic and geometric
progressions, Fibonacci numbers)
 q Permutations and combinations (basic definitions)
 q Factorial function, binomial coefficients
 Inclusion-exclusion principle
 p Pigeonhole principle
 p Pascal’s identity, Binomial theorem
 Solving of recurrence relations

 Graphs & Trees :

 q Undirected graphs (vertex/node, edge, degree, adjacency, vertex and edge
labels)
 q Directed graphs (in-degree, out-degree)
 q Multigraphs, graphs with self-loops
 q Paths in graphs (undirected and directed path, cycle, tour, walk; Euler tour;
Hamiltonian path/cycle)
 q Reachability (connected component, shortest distance)
 q Trees (leaf, diameter, center, centroid, forest)
 q Rooted trees (root, parent, child, ancestor, subtree)
 q Spanning trees (subgraph)
 q Traversal strategies
 q Bipartite graphs
 q Directed acyclic graphs
 p Planar graphs
 p Basic combinatorial properties of graphs9

 Other areas in Mathematics :

 Number Theory
 Combinatorics
 Basic Algebra
 Game Theory
 Graph Theory
 Probability & Expectation
 Basic Calculus
 Computational Geometry
 Programming Fundamentals (PF)
 Fundamental programming constructs :
 Basic syntax and semantics of a higher-level language { C++} (at
least one of the specific languages available at an IOI, as announced in
the Competition Rules for that IOI)
 Variables, types, expressions, and assignment
 Simple I/O
 Conditional and iterative control structures
 Functions and parameter passing
 p Structured decomposition

 Algorithms & Problem Solving :

 Problem-solving strategies (understand–plan–do–check, separation of concerns,
generalization, specialization, case distinction, working backwards, etc.)
 p The role of algorithms in the problem-solving process
 p Implementation strategies for algorithms (also see §7 SE1)
 p Debugging strategies (also see §7 SE3)
 q The concept and properties of algorithms (correctness, efficiency)

 Fundamental Data - Structures :

 Primitive types (Boolean, signed/unsigned integer, character)
 Arrays (incl. multicolumn dimensional arrays)
 Strings and string processing
 q Static and stack allocation (elementary automatic memory management)
 q Linked structures
 q Implementation strategies for graphs and trees
 q Strategies for choosing the right data structure
 p Elementary use of real numbers in numerically stable tasks
 p The floating-point representation of real numbers, the existence of precision
issues.11
 p Pointers and references ? Data representation in memory, ? Heap allocation, ?
Run time storage management, ? Using fractions to perform exact calculations.

 Recursion :
 The concept of recursion
 Recursive mathematical functions
 Simple recursive procedures (incl. mutual recursion)
 p Divide-and-conquer strategies
  p Implementation of recursion
 p Recursive backtracking

 Algorithms & Complexity (AL)

 Algorithmic analysis :
 Algorithm specification, precondition, postcondition, correctness, invariants
 p Asymptotic analysis of upper complexity bounds (informally if possible)
 p Big O notation
 Amortized analysis.
 p Standard complexity classes: constant, logarithmic, linear, O(n log n),
quadratic, cubic, exponential, etc.
 p Time and space tradeoffs in algorithms
Empirical performance measurements. ? Identifying differences among best, average,
and worst case behaviors, ? Little o, Omega, and Theta notation, ? Tuning parameters
to reduce running time, memory consumption or other measures of performance

 Algorithmic Strategies :
 Simple loop design strategies ✓
 p Brute-force algorithms (exhaustive search)
 p Greedy algorithms
 p Divide-and-conquer
 p Backtracking (recursive and non-recursive), Branch-andbound
 p Dynamic programming13 ? Heuristics ? Finding good features for machine
learning tasks14 ? Discrete approximation algorithms ? Randomized algorithms.

 Algorithms :
 Simple algorithms involving integers: radix conversion, Euclid’s algorithm,
primality test by O( √ n) trial division, Sieve of Eratosthenes, factorization (by
trial division or a sieve), efficient exponentiation Simple operations on arbitrary
precision integers (addition, subtraction, simple multiplication)15
 p Simple array manipulation (filling, shifting, rotating, reversal, resizing,
minimum/maximum, prefix sums, histogram, bucket sort)
 p Simple string algorithms (e.g., naive substring search)
 p sequential processing/search and binary search
 p Quick-sort and Quickselect to find the k-th smallest element.
 p O(n log n) worst-case sorting algorithms (heap sort, merge sort)
 p Traversals of ordered trees (pre-, in-, and post-order)
 p Depth- and breadth-first traversals
 p Applications of the depth-first traversal tree, such as topological ordering and
Euler paths/cycles
 p Finding connected components and transitive closures.
 p Shortest-path algorithms (Dijkstra, Bellman-Ford, FloydWarshall)
 p Minimum spanning tree (Jarn´ık-Prim and Kruskal algorithms)
 p O(V E) time algorithm for computing maximum bipartite matching.
 p Bi-connectivity in undirected graphs (bridges, articulation points).
 p Connectivity in directed graphs (strongly connected components).
 p Basics of combinatorial game theory, winning and losing positions, minimax
algorithm for optimal game playing

 Data Structures :
 Stacks and queues
 p Representations of graphs (adjacency lists, adjacency matrix)
 q Binary heap data structures
 p Representation of disjoint sets: the Union-Find data structure.
 q Statically balanced binary search trees. Instances of this include binary index
trees (also known as Fen wick trees) and segment trees (also known as interval
trees and tournament trees).16
 p Balanced binary search trees17
 q Augmented binary search trees
 p O(log n) time algorithms for answering lowest common ancestor queries in a
static rooted tree.18
 p Decomposition of static trees (heavy-light decomposition, separator structures
such as centroid decomposition)
 p Creating persistent data structures by path copying.
 p Nesting of data structures, such as having a sequence of sets.
 q Tries
 Data structures for dynamically changing trees and their use in graph algorithms.
 ✗ String algorithms and data structures (KMP, Rabin-Karp hashing, suffix
arrays/trees, suffix automata, Aho-Corasick)
 ✗ Complex heap variants such as binomial and Fibonacci heaps,
 ✗ Using and implementing hash tables (incl. strategies to resolve collisions)
 ✗ Two-dimensional tree-like data structures (such as a 2D statically balanced
binary tree or a treap of treaps) used for 2D queries.

 Geometric Algorithms :
 Representing points, vectors, lines, line segments.
 p Checking for collinear points, parallel/orthogonal vectors and clockwise turns
(for example, by using dot products and cross products).
 p Intersection of two lines.
 p Computing the area of a polygon from the coordinates of its vertices.19
 p Checking whether a (general/convex) polygon contains a point.
 p Coordinate compression.
 p O(n log n) time algorithms for convex hull
 p Sweeping line method
 Some Additional Topics :
 Basic Software Engineering
 Information Theory
 Basic Computability
 Complexity theory
 Automata & Grammars