IOITC

Included: Integers, operations (incl. exponentiation), comparison; Basic properties of integers (sign, parity, divisibility); Basic modular arithmetic: addition, subtraction, multiplication; Prime numbers; Fractions, percentages; Line, line segment, angle, triangle, rectangle, square, circle; Point, vector, coordinates in the plane; Polygon (vertex, side/edge, simple, convex, inside, area); Euclidean distances; Pythagorean theorem. Explicitly excluded: Geometry in three or more dimensions; Analyzing and increasing precision of floating-point computations; Modular division and inverse elements; Complex numbers; General conics (parabolas, hyperbolas, ellipses); Trigonometric functions

Included: Functions (surjections, injections, inverses, composition); Relations (reflexivity, symmetry, transitivity, equivalence relations, total/linear order relations, lexicographic order); Sets (inclusion/exclusion, complements, Cartesian products, power sets). Explicitly excluded: Cardinality and countability (of infinite sets)

Included: 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.); Modus ponens and modus tollens. Outside of focus: Normal forms. Explicitly excluded: Validity; Limitations of predicate logic

Included: Notions of implication, converse, inverse, contrapositive, negation, and contradiction; Direct proofs, proofs by: counterexample, contraposition, contradiction; Mathematical induction; Strong induction (also known as complete induction); Recursive mathematical definitions (incl. mutually recursive definitions)

Included: Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers); Permutations and combinations (basic definitions); Factorial function, binomial coefficients; Inclusion-exclusion principle; Pigeonhole principle; Pascal’s identity, Binomial theorem. Explicitly excluded: Solving of recurrence relations; Burnside lemma

Included: Undirected graphs (vertex/node, edge, degree, adjacency, vertex and edge labels); Directed graphs (in-degree, out-degree); Multigraphs, graphs with self-loops; Paths in graphs (undirected and directed path, cycle, tour, walk; Euler tour; Hamiltonian path/cycle); Reachability (connected component, shortest distance); Trees (leaf, diameter, forest); Rooted trees (root, parent, child, ancestor, subtree, binary tree); Spanning trees (and general subgraphs); Traversal strategies; Bipartite graphs; Directed acyclic graphs; Simple specific graph shapes (complete, complete bipartite, star); More general connectivity (biconnected undirected and strongly connected directed graphs); Structure of trees (center, centroid); Planar graphs; Basic combinatorial properties of graphs. Explicitly excluded: Hypergraphs; Specific graph classes such as perfect graphs; Structural parameters such as treewidth and expansion; Planarity testing; Finding separators for planar graphs

Note: Applications where everything is finite (and thus arguments about probability can be easily turned into combinatorial arguments) are ?, everything more complicated is ✗

Explicitly excluded: Linear algebra, including (but not limited to):; Calculus; Theory of combinatorial games, e.g., bitwise xor solution to the general NIM game, Sprague-Grundy theory; Statistics. Contestants may be expected to: Matrix multiplication, exponentiation, inversion, and Gaussian elimination; polynomial interpolation; Fast Fourier transform. Note: 6 Computing Science

Included: Basic syntax and semantics of a higher-level language (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; Structured decomposition

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

Included: Primitive types (boolean, signed/unsigned integer, character); Arrays (incl. multicolumn dimensional arrays); Strings and string processing; Static and stack allocation (elementary automatic memory management); Linked structures; Implementation strategies for graphs and trees; Strategies for choosing the right data structure; Elementary use of real numbers in numerically stable tasks; The floating-point representation of real numbers, the existence of precision issues; Pointers and references. Outside of focus: Data representation in memory; Heap allocation; Runtime storage management; Using fractions to perform exact calculations. Explicitly excluded: Non-trivial calculations on floating point numbers, manipulating precision errors. Note: Regarding floating point numbers, there are well-known reasons why they should be, in general, avoided at the IOI. However, the currently used interface removes some of those issues. In particular, it should now be safe to use floating point numbers in some types of tasks – e.g., to compute some Euclidean distances and return the smallest one

Included: The concept of recursion; Recursive mathematical functions; Simple recursive procedures (incl. mutual recursion); Divide-and-conquer strategies; Implementation of recursion; Recursive backtracking

Note: Some competition tasks may involve a dialog with a reactive environment. Implementing such an interaction with the provided environment is ✓ . Everything not directly related to the implementation of reactive tasks is ?

Included: Algorithm specification, precondition, postcondition, correctness, invariants; Asymptotic analysis of upper complexity bounds (informally if possible); Big O notation; Standard complexity classes: constant, logarithmic, linear, O(n log n), quadratic, cubic, exponential, etc; Time and space tradeoffs in algorithms; Empirical performance measurements. Outside of focus: 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. Explicitly excluded: Asymptotic analysis of average complexity bounds; Using recurrence relations to analyze recursive algorithms

Included: Simple loop design strategies; Brute-force algorithms (exhaustive search); Greedy algorithms; Divide-and-conquer; Backtracking (recursive and non-recursive), Branch-and-bound; Dynamic programming. Outside of focus: Heuristics; Finding good features for machine learning tasks; Discrete approximation algorithms; Randomized algorithms. Explicitly excluded: Clustering algorithms (e.g. k-means, k-nearest neighbor); Minimizing multi-variate functions using numerical approaches

Included: Simple algorithms on 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); Simple array manipulation (filling, shifting, rotating, reversal, resizing, minimum/maximum, prefix sums, histogram, bucket sort); Simple string algorithms (e.g., naive substring search); sequential processing/search and binary search; Quicksort and Quickselect to find the k-th smallest element; O(n log n) worst-case sorting algorithms (heap sort, merge sort); Traversals of ordered trees (pre-, in-, and post-order); Depth- and breadth-first traversals; Applications of the depth-first traversal tree, such as topological ordering and Euler paths/cycles; Finding connected components and transitive closures; Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall); Minimum spanning tree (Jarnı́k-Prim and Kruskal algorithms); Maximum bipartite matching (O(V E) algorithm based on augmenting paths); Maximum network flow (Ford-Fulkerson O(|flow| · E) algorithm based on augmenting paths); Duality between maximum flows and minimum cuts; Biconnectivity in undirected graphs (bridges, articulation points); Connectivity in directed graphs (strongly connected components); Basics of combinatorial game theory, winning and losing positions, minimax algorithm for optimal game playing. Explicitly excluded: Optimization problems that are easiest to analyze using matroid theory, problems based on matroid intersecions (except for bipartite matching); Lexicographical BFS, maximum adjacency search and their properties; More efficient implementations of bipartite matching and network flow algorithms; Maximum matching in polynomial time on general graphs; Minimum cost versions of maximum matchings and network flows; Alpha-beta pruning

Included: Stacks and queues; Representations of graphs (adjacency lists, adjacency matrix); Binary heap data structures; Representation of disjoint sets: the Union-Find data structure; Statically balanced binary search trees. Instances of this include binary index trees (also known as Fenwick trees) and segment trees (also known as interval trees and tournament trees); Balanced binary search trees; Augmented binary search trees; O(log n) time algorithms for answering lowest common ancestor queries in a static rooted tree; Decomposition of static trees (heavy-light decomposition, separator structures such as centroid decomposition); Persistent data structures; Nesting of data structures, such as having a sequence of sets; Tries. Explicitly excluded: 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; Fat nodes and other more complicated ways of implementing persistent data structures; Data structures for dynamically changing trees (e.g., link/cut trees) and their use in graph algorithms

Note: This entire section is ?

Note: All topics related to computability are ✗. This includes the following: Tractable and intractable problems; Uncomputable functions; The halting problem; Implications of uncomputability. However, see AL7 for basic computational models

Explicitly excluded: does not mean that an NP-hard problem cannot appear at an IOI. Note: Topics related to non-determinism, proofs of NP-hardness (reductions), and everything related is ✗. Note that this section only covers the results usually contained in undergraduate and graduate courses on formal languages and computational complexity. The classification of these topics as

Included: Understanding a simple grammar in Backus-Naur form. Outside of focus: Formal definition and properties of finite-state machines; Context-free grammars and related rewriting systems; Regular expressions. Explicitly excluded: Properties other than the fact that automata are graphs and that grammars have parse trees

Included: Amortized analysis. Outside of focus: Analysis of online algorithms, including competitive analysis; Analysis of randomized algorithms

Note: This entire section is ?

Included: Representing points, vectors, lines, line segments; Checking for collinear points, parallel/orthogonal vectors and clockwise turns (for example, by using dot products and cross products); Intersection of two lines; Computing the area of a polygon from the coordinates of its vertices; Checking whether a (general/convex) polygon contains a point; Coordinate compression; O(n log n) time algorithms for convex hull; Sweeping line method. Explicitly excluded: Point-line duality; Halfspace intersection, Voronoi diagrams, Delaunay triangulations; Computing coordinates of circle intersections against lines and circles; Linear programming in 3 or more dimensions and its geometric interpretations; Center of mass of a 2D object; Computing and representing the composition of geometric transformations if the knowledge of linear algebra gives an advantage. Note: In general, the ISC has a strong preference towards problems that can be solved using integer arithmetics to avoid precision issues. This may include representing some computed values as exact fractions, but extensive use of such fractions in calculations is discouraged. Additionally, if a problem uses two-dimensional objects, the ISC prefers problems in which such objects are rectilinear

Note: This entire section is ?

Note: Except for GV (specified below), all areas are ✗. AR. Architecture and Organization OS. Operating Systems NC. Net-Centric Computing (a.k.a. cloud computing) PL. Programming Languages HC. Human-Computer Interaction GV. Graphics and Visual Computing Basic aspects of processing graphical data are ?, everything else (including the use of graphics libraries such as OpenGL) is ✗. IS. Intelligent Systems IM. Information Management SP. Social and Professional Issues CN. Computational Science Notes: AR is about digital systems, assembly language, instruction pipelining, cache memories, etc. OS is about the design of operating systems, not their usage. PL is about the analysis and design of programming languages, not their usage. HC is about the design of user interfaces. Usage of the operating system, GUIs and programming languages is covered in §8 and §6.1

Included: Fundamental design concepts and principles; Design patterns; Structured design. Explicitly excluded: Software architecture; Design for reuse; Object-Oriented analysis and design; Component-level design. Contestants may be expected to: Transform an abstract algorithm into a concrete, efficient program expressed in one of the allowed programming languages, possibly using standard or competition-specific libraries; Make their programs read data from and write data to text files according to a prescribed simple format. Note: In particular, contestants may be expected to

Included: API (Application Programming Interface) programming. Explicitly excluded: Programming by example; Debugging in the API environment; Class browsers and related tools; Introduction to component-based computing. Contestants may be expected to: Use competition-specific libraries according to the provided specification. Note: In particular, contestants may be expected to

Included: Programming environments, incl. IDE (Integrated Development Environment). Explicitly excluded: Testing tools; Configuration management tools; Requirements analysis and design modeling tools; Tool integration mechanisms. Contestants may be expected to: Write and edit program texts using one of the provided program editors; Compile and execute their own programs; Debug their own programs. Note: In particular, contestants may be expected to

Included: Software life-cycle and process models. Explicitly excluded: Process assessment models; Software process metrics. Contestants may be expected to: Understand the various phases in the solution development process and select appropriate approaches. Note: In particular, contestants may be expected to

Included: Functional and nonfunctional requirements; Basic concepts of formal specification techniques. Explicitly excluded: Prototyping; Requirements elicitation; Requirements analysis modeling techniques. Contestants may be expected to: Transform a precise natural-language description (with or without mathematical formalism) into a problem in terms of a computational model, including an understanding of the efficiency requirements. Note: In particular, contestants may be expected to

Included: Testing fundamentals, including test plan creation and test case generation; Black-box and white-box testing techniques; Unit, integration, validation, and system testing; Inspections. Explicitly excluded: Validation planning; Object-oriented testing. Contestants may be expected to: Apply techniques that maximize the the opportunity to detect common errors (e.g. through well-structured code, code review, built-in tests, test execution); Test (parts of) their own programs. Note: In particular, contestants may be expected to

Explicitly excluded: Software maintenance; Characteristics of maintainable software; Re-engineering; Legacy systems; Software reuse

Included: Project scheduling (especially time management); Risk analysis; Software configuration management. Explicitly excluded: Software quality assurance; Team management; Software measurement and estimation techniques; Project management tools. Contestants may be expected to: Manage time spent on various activities; Weigh risks when choosing between alternative approaches; Keep track of various versions and their status while developing solutions. Note: In particular, contestants may be expected to

Note: This entire section is ✗

Included: Formal methods concepts (notion of correctness proof, invariant); Pre and post assertions. Explicitly excluded: Formal verification; Formal specification languages; Executable and non-executable specifications. Contestants may be expected to: Reason about the correctness and efficiency of algorithms and programs. Note: In particular, contestants may be expected to

Note: This entire section is ✗

Note: This entire section is ✗

Note: The text of this section is ✓ . Contestants should know and understand the basic structure and operation of a computer (CPU, memory, I/O). They are expected to be able to use a standard computer with graphical user interface, its operating system with supporting applications, and the provided program development tools for the purpose of solving the competition tasks. In particular, some skill in file management is helpful (creating folders, copying and moving files). Details of these facilities will be stated in the Competition Rules of the particular IOI. Typically, some services are available through a standard web browser. Possibly, some competition-specific tools are made available, with separate documentation. It is often the case that a number of equivalent tools are made available. The contestants are not expected to know all the features of all these tools. They can make their own choice based on what they find most appropriate. The following topics are all ?: Calculator, Word-processors, Spreadsheet applications, Database management systems, E-mail clients, Graphics tools (drawing, painting)