\documentclass[a4paper,11pt,oneside]{article}
\usepackage{url}
\usepackage{sectsty}
\allsectionsfont{\sffamily}
\newcommand{\B}{\bfseries}
\newcommand{\F}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\id}[1]{\textit{#1}}
\newcommand{\Set}[1]{\{\,#1\,\}}
%\newcommand{\CC}[1]{\textsf{\small #1}}% to quote from Computing Curricula 2001
\newcommand{\CC}[1]{#1}
\newcommand{\La}{{\small$\heartsuit$}~}%{$\odot$~}%{\fbox{\tiny\B 1}~}
\newcommand{\Lb}{{\small$\triangle$}~}%{$\ominus$~}%{\fbox{\tiny\B 2}~}
\newcommand{\Lbb}{{\small$\triangle$}}%{$\ominus$~}%{\fbox{\tiny\B 2}~}
\newcommand{\Lc}{{\small$\ominus$}~}%{{$\otimes$}~}%{\fbox{\tiny\B 3}~}
\newcommand{\Lcc}{{\small$\ominus$}}%{{$\otimes$}~}%{\fbox{\tiny\B 3}~}
\newdimen\digitwidth\setbox0=\hbox{\rm0}\digitwidth\wd0
% include \def~{\kern\digitwidth} within environment, so that ~ can be used
% as digit-wide space
\newcommand{\DRAFT}{ -- Version 2017}
\pagestyle{myheadings}
\textwidth 126.34 mm
\textheight 189.55 mm
\parindent 20 pt
\parskip 0 pt
\markboth{\sc The IOI Syllabus\DRAFT}{\sc The IOI Syllabus\DRAFT}
\newenvironment{myitemize}{
\begin{itemize}\itemsep 0pt
\let\oldLa=\La
\let\oldLb=\Lb
\let\oldLc=\Lc
\def\La{\item[\oldLa]}
\def\Lb{\item[\oldLb]}
\def\Lc{\item[\oldLc]}
}{
\end{itemize}
}
\usepackage{color}
\usepackage[normalem]{ulem}
\newcommand{\remove}[1]{\sout{#1}}
\newcommand{\new}[1]{{\bf \color{red}{#1}}}
%%\newcommand{\richard}[1]{{\bf \color{green} Richard: #1}}
%%\newcommand{\remove}[1]{}
%%\newcommand{\new}[1]{#1}
\newcommand{\richard}[1]{}
\begin{document}
\title{\sf The International Olympiad in Informatics Syllabus}
\date{~}
\maketitle
\section{Version and status information}
This is the official Syllabus version for \textbf{IOI 2017} in Iran.
\medskip
All additions since the 2016 version were presented at IOI 2016.
All changes are \new{in red}.
\medskip
The Syllabus is an official document related to the IOI.
For each IOI, an up-to-date version of
the Syllabus is produced by the ISC, as described in the IOI Regulations, Statue 3.13.
\section{Authors and Contact Information}
The original proposal of the IOI Syllabus was co-authored by
{Tom Verhoeff}\footnote{TU Eindhoven, The Netherlands, \url{t.verhoeff@tue.nl}},
{Gyula Horv\'ath}\footnote{University of Szeged, Hungary, \url{horvath@inf.u-szeged.hu}},
{Krzysztof Diks}\footnote{Warsaw University, Poland, \url{diks@mimuw.edu.pl}},
and
{Gordon Cormack}\footnote{University of Waterloo, Canada, \url{gvcormac@uwaterloo.ca}}.
Since 2007, the following people have maintained the syllabus and made significant contributions:
{Michal Fori\v{s}ek}\footnote{Comenius University, Slovakia, \url{forisek@dcs.fmph.uniba.sk}},
{Jakub \L{}\c{a}cki}\footnote{Warsaw University, Poland, \url{j.lacki@mimuw.edu.pl}},
and
{Richard Peng}\footnote{Georgia Tech, USA, \url{richard.peng at gmail.com}}.
The most recent batch of revisions to the Syllabus was made by the ISC between February and July 2016.
You are welcome to send any feedback on the Syllabus to
the current maintainer's e-mail address (\verb!forisek@dcs.fmph.uniba.sk!).
For people interested in contributing to the quality of the Syllabus, some additional
background on the Syllabus and other miscellaneous information can be found at
\url{http://ksp.sk/~misof/ioi-syllabus/}.
\newpage
\section{Introduction}\label{sec:intro}
During the years, the Syllabus has evolved. Currently it has the following purposes:
\begin{itemize}
\item
It specifies a small set of required prerequisite knowledge.
Below, this is given in the category ``Included, unlimited''
and to some extent also in ``Included, to be clarified''.
\item
It serves as a set of guidelines that help decide whether a task is
suitable for the International Olympiad in Informatics (IOI).
Based on this document, the International Scientific Committee (ISC)
evaluates the task proposals when selecting the competition tasks.
% Here, we would like to note that the requirements given in the Syllabus
% are not strict. It may be the case that the ISC, after careful consideration,
% decides to use a task that is partially or fully in the ``Outside of focus''
% category of the Syllabus.
\item
As a consequence of the previous item, another purpose of the Syllabus
is to help the organizers of national olympiads prepare
their students for the IOI.
\end{itemize}
The Syllabus aims to achieve these goals by providing a classification of topics and
concepts from mathematics and computer science.
% In particular, some of the easy topics are classified as \emph{included}; and on the other end, some hard topics and some unrelated topics are \emph{explicitly excluded}.
More precisely, this Syllabus classifies each topic into one of five categories:
\begin{description}
\item[\La Included, unlimited]~\\
Topics in this category are considered to be prerequisite knowledge.
Contestants are expected to know them. These topics can appear
in task descriptions without further clarification.
Example: \emph{Integer} in~\S\ref{subsubsec:NG}
\item[\Lb Included, to be clarified]~\\
Contestants should know this topic,
but when it appears in a task description,
the author must always clarify it sufficiently.
Example: \emph{Directed graph} in~\S\ref{subsubsec:DS}~DS2
\item[\Lc Included, not for task description]~\\
Topics that belong to this category should not appear in tasks
descriptions. However, developing solutions and understanding
model solutions may require the knowledge of these topics.
Example: \emph{Asymptotic analysis of upper complexity bounds\/}
in \S\ref{subsubsec:AL}~AL1
Note: This is the main category that should be of interest when
preparing contestants for the IOI.
It should be noted that this set of topics
contains a wide range of difficulties, starting from simple concepts and ending
with topics that can appear in problems that aim to distinguish among
the gold medallists. It is \textbf{not} expected that all contestants
should know everything listed in this category.
\item[Outside of focus]~\\
Any topic that is not explicitly addressed by the Syllabus
should be considered to belong to this category.
Contestants are not expected to have knowledge of these topics.
Most competition tasks will not be related to any topics
from this category.
However, this does not prevent the inclusion of
a competition task that is related to a particular topic
from this category. The ISC may wish to include such a competition
task in order to broaden the scope of the IOI.
If such a task is considered for the IOI,
the ISC will make sure that the task can reasonably be solved
without prior knowledge of the particular topic, and that
the task can be stated
in terms of \La{}and~\Lb{}concepts in a precise, concise,
and clear way.
Examples of such tasks being used at recent IOIs include :
\begin{itemize}
\item Languages (a.k.a. Wikipedia) from IOI 2010 in Canada, and
\item Odometer (a.k.a. robot with pebbles) from IOI 2012 in Italy, and
\item Art class from IOI 2013 in Australia.
\end{itemize}
\item[Excluded]
Some of the harder algorithmic topics are explicitly marked as excluded.
It is guaranteed that there will not be a competition
task that \emph{requires} the contestants to know these areas.
Furthermore, the tasks will be set with the goal that knowledge of
Excluded topics should not help in obtaining simpler solutions / solutions
worth more points.
%% \remove{In other words, each competition task will have a perfect solution
%% that can be produced without the knowledge of these topics.}
This category mainly contains hard textbook algorithms
and advanced areas in mathematics.
Still, note that the Syllabus must not be interpreted to restrict in
any way the techniques that contestants are allowed to apply in solving
the competition tasks.
Due to the the common occurrence of tasks that can benefit
from knowing excluded topics since the introduction of the syllabus,
and the differing treatments of these topics in various
national/regional competitions,
this set is further divided into two parts in this version.
\begin{itemize}
\item \textbf{Excluded, but open to discussion}~\\
This contains mostly topics that are natural extensions of topics in \La{} and \Lb{}, or ones where the boundary is difficult to draw.\\
Examples: \emph{Rabin-Karp string hashing} in~\S\ref{sec:dataStructures}\\
\item \textbf{Explicitly excluded}~\\
This contains mostly topics whose inclusion will result in
categories of problems that are unaccessible to a significant
portion of IOI participants.\\
Examples: \emph{Calculus\/} in~\S\ref{subsubsec:other-mathematics}
\end{itemize}
It is the hope that a consensus can be reached on most
topics in the \textbf{Excluded, but open to discussion}
category in the next few years.
\end{description}
\bigskip
Obviously, none of the categories can ever be exhaustively enumerated.
Instead, the list given in the following Sections should serve as examples that map out the boundary:
anything easier or similar to \emph{Included} topics is to be
considered Included as well, and anything similar or harder than the
\emph{Explicitly excluded} topics is Excluded, too.
If there is a particular topic for which you are not sure how it should
be classified, we invite you to submit a clarification request to the
current Syllabus maintainer.
Note that issues related to the usage of suitable terminology and notations in competition tasks
are beyond the scope of this document.\footnote{See
T. Verhoeff: \emph{Concepts, Terminology, and Notations for IOI Competition Tasks},
\url{http://scienceolympiads.org/ioi/sc/documents/terminology.pdf}}
\bigskip
The rest of this document contains the classification of topics.
%%Topics literally copied from the IEEE-CS Curriculum\footnote{%
%%ACM/IEEE-CS Joint Curriculum Task Force: \emph{Computing Curricula 2001: Computer Science Volume},
%%\url{http://www.acm.org/sigcse/cc2001/}}
%%are typeset in \CC{sans serif font}.
\section {Mathematics}
\label{subsec:mathematics}
\subsection {Arithmetics and Geometry}
\label{subsubsec:NG}
\begin{quote}
\begin{myitemize}
\La Integers, operations (incl.\ exponentiation), comparison
\La Basic properties of integers (sign, parity, divisibility)
\La Basic modular arithmetic: addition, subtraction, \\ multiplication
\Lc Prime numbers
\La Fractions, percentages
\La Line, line segment, angle, triangle, rectangle, square, circle
\La Point, vector, coordinates in the plane
\La Polygon (vertex, side/edge, simple, convex, inside, area)
\Lb Euclidean distances
\Lc Pythagorean theorem
\end{myitemize}
\emph{Excluded, but open to discussion}
\begin{itemize}
\item Additional topics from number theory.
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item geometry in 3D or higher dimensional spaces
\item analyzing and increasing precision of floating-point \\ computations
\item modular division and inverse elements
\item complex numbers,
\item general conics (parabolas, hyperbolas, ellipses)
\item trigonometric functions%, \new{circles, angles}
\end{itemize}
\end{quote}
\subsection {Discrete Structures (DS)}
\label{subsubsec:DS}
\begin{description}
\item[DS1. Functions, relations, and sets] ~
\begin{myitemize}
\Lb\CC{Functions (surjections, injections, inverses, composition)}
\Lb\CC{Relations (reflexivity, symmetry, transitivity, equivalence relations,
total/linear order relations, lexicographic order)}
\Lb\CC{Sets (inclusion/exclusion, complements, Cartesian products, power sets)} \end{myitemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item {Cardinality and countability} (of infinite sets)
\end{itemize}
\item[DS2. Basic logic] ~
\begin{myitemize}
\La First-order logic
\La\CC{Logical connectives} (incl.\ their basic properties)
\La\CC{Truth tables}
\La\CC{Universal and existential quantification} (Note: statements should avoid definitions with nested
quantifiers whenever possible).
%\footnote{
%In case the definition of a term in the problem statement
%contains more than one quantifier (and especially
%if the quantifiers are of both types), it is advised to split the definition
%into parts, each containing a single quantifier. E.g., don't define the
%diameter of a graph directly, use eccentricity of a vertex as an intermediate
%step.
%}
\Lc\CC{Modus ponens and modus tollens}
\end{myitemize}
N.B.
This article is not concerned with notation.
In past task descriptions,
logic has been expressed in natural language rather than mathematical symbols,
such as $\land$, $\lor$, $\forall$, $\exists$.
\emph{Out of focus\/}:
\begin{itemize}
\item \CC{Normal forms}
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item \CC{Validity}
\item \CC{Limitations of predicate logic}
\end{itemize}
\item[DS3. Proof techniques] ~
\begin{myitemize}
\Lb\CC{Notions of implication, converse, inverse, contrapositive, negation, and contradiction}
\Lc\CC{Direct proofs, proofs by: counterexample, contraposition, contradiction}
\Lc\CC{Mathematical induction}
\Lc\CC{Strong induction} (also known as complete induction)
\La\CC{Recursive mathematical definitions} (incl.\ mutually recursive definitions)
\end{myitemize}
% \emph{Not needed\/}: \CC{The structure of formal proofs}
% \emph{Excluded\/}: \CC{Well orderings}
\item[DS4. Basics of counting] ~
\begin{myitemize}
\La\CC{Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers)}
\Lb\CC{Permutations and combinations (basic definitions)}
\Lb Factorial function, binomial coefficients
\Lc\CC{Inclusion-exclusion principle}
\Lc\CC{Pigeonhole principle}
\Lc\CC{Pascal's identity}, \CC{Binomial theorem}
\end{myitemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item{Solving of recurrence relations}
\item Burnside lemma
\end{itemize}
\item[DS5. Graphs and trees] ~
\begin{myitemize}
\Lb\CC{Trees} and their basic properties, rooted trees
% connected, no cycles, $\# \mbox{nodes} = \# \mbox{edges} + 1$;
% ordered/not-ordered)\\
\Lb\CC{Undirected graphs} (degree, path, cycle, connectedness, Euler/Hamil\-ton path/cycle,
handshaking lemma%\footnote{%
%\verb"http://en.wikipedia.org/wiki/Double_counting#Handshaking_lemma"}%
)
\Lb\CC{Directed graphs} (in-degree, out-degree, directed path/cycle, Euler/Hamilton path/cycle)
\Lb\CC{Spanning trees}
\Lb\CC{Traversal strategies}
\Lb `Decorated' graphs with edge/node labels, weights, colors
\Lb Multigraphs, graphs with self-loops
\Lb Bipartite graphs
\Lc Planar graphs
\end{myitemize}
\emph{Explicitly Excluded}
\begin{itemize}
\item Hypergraphs
\item Specific graph classes such as perfect graphs
\item Structural parameters such as treewidth and expansion
\item Planarity testing
\item Finding separators for planar graphs
\end{itemize}
\richard{Added a few more items}
\item[DS6. Discrete probability] ~
Applications where everything is finite (and thus arguments about probability can be easily
turned into combinatorial arguments) are \emph{Out of focus}, everything more complicated
is \emph{Explicitly excluded}.
\end{description}
\subsection {Other Areas in Mathematics}
\label{subsubsec:other-mathematics}
\begin{quote}
%%\emph{Out of focus\/}
%% Geometry in 3D space, systems of linear equations
\emph{Explicitly excluded\/}:
\begin{itemize}
\item Geometry in three or more dimensions.
\item Linear algebra, including (but not limited to):
\begin{itemize}
\item Matrix multiplication, exponentiation, inversion,
and Gaussian elimination
\item Fast Fourier transform
\end{itemize}
\item Calculus,
\item Statistics
\end{itemize}
\end{quote}
\section {Computing Science}
\label{subsec:computing-science}
\subsection {Programming Fundamentals (PF)}
\label{subsubsec:PF}
\begin{description}
\item[PF1. Fundamental programming constructs] (for abstract machines)
\begin{myitemize}
\La\CC{Basic syntax and semantics of a higher-level language}
(at least one of the specific languages available at an IOI, as announced
in the \emph{Competition Rules\/} for that IOI)
\La\CC{Variables, types, expressions, and assignment}
\La\CC{Simple I/O}
\La\CC{Conditional and iterative control structures}
\La\CC{Functions and parameter passing}
\Lc\CC{Structured decomposition}
\end{myitemize}
\item[PF2. Algorithms and problem-solving] ~
\begin{myitemize}
\Lc\CC{Problem-solving strategies} (understand--plan--do--check,
separation of concerns, generalization, specialization, case distinction, working backwards,
etc.)\footnote{See G. Polya: \emph{How to Solve It: A New Aspect of Mathematical Method},
Princeton Univ.\ Press, 1948}
\Lc\CC{The role of algorithms in the problem-solving process}
\Lc\CC{Implementation strategies for algorithms} (also see \S\ref{subsec:software-engineering}~SE1)
\Lc\CC{Debugging strategies} (also see \S\ref{subsec:software-engineering}~SE3)
\Lb\CC{The concept and properties of algorithms} (correctness, efficiency)
\end{myitemize}
\item[PF3. Fundamental data structures] ~
\begin{myitemize}
\La\CC{Primitive types} (boolean, signed/unsigned integer, character)
\La\CC{Arrays} (incl. multicolumn dimensional arrays)
% \La\remove{\CC{Records}}
\La\CC{Strings and string processing}
\Lb\CC{Static and stack allocation} (elementary automatic memory management)
\Lb\CC{Linked structures}
% \Lb \remove{Static memory implementation strategies for linked structures}
% \Lb \remove{\CC{Implementation strategies for stacks and queues}}
\Lb\CC{Implementation strategies for graphs and trees}
\Lb\CC{Strategies for choosing the right data structure}
\Lc\CC{Elementary use of real numbers in numerically stable tasks}
\Lc The floating-point representation of real numbers, the existence of precision issues.\footnote{Whenever possible, avoiding floating point computations completely is the preferred solution.}
\Lc \CC{Pointers and references}
%% \footnote{%
%%The inessential advantage of scalable memory efficiency is outweighed
%%by the increased complexity in reasoning.
%%Static memory implementations should suffice to solve IOI tasks.
%%Pointer data structures can always be implemented statically by
%%pre-allocating large arrays},
\end{myitemize}
%%\Lb\CC{Static memory implementation strategies for linked structures}
%% \Lb\CC{Implementation strategies for stacks and queues}
%%
\emph{Out of focus\/}:
\begin{itemize}
\item \CC{Data representation in memory},
\item \CC{Heap allocation},
\item \CC{Runtime storage management},
\item Using fractions to perform exact calculations.%increase the precision of calculations.
\end{itemize}
% Arbitrary-size integer arithmetic\footnote{%
%This means that tasks are solvable with the appropriate primitive integer types,
%without concern for overflow.}
\emph{Explicitly excluded\/}:
\begin{itemize}
% \item \remove{Precision errors when computing with floating-point numbers}
\item Non-trivial calculations on floating point numbers, manipulating precision errors
\end{itemize}
Regarding floating point numbers, there are well-known reasons why they
should be, in general, avoided at the IOI.\footnote{%
See G. Horv\'ath and T. Verhoeff: \emph{Numerical Difficulties in Pre-University Education and
Competitions}, Informatics in Education 2:21--38, 2003}
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.
\richard{Can we add some type of guarantee that problems that naturally
involving floating numbers can be solved using them with round off errors
at most $1e-6$, but we also guarantee that we have solutions using 64-bit ints?}
\item[PF4. Recursion] ~
\begin{myitemize}
\La\CC{The concept of recursion}
\La\CC{Recursive mathematical functions}
\La\CC{Simple recursive procedures} (incl.\ mutual recursion)
\Lc\CC{Divide-and-conquer strategies}
\Lc\CC{Implementation of recursion}
\Lc\CC{Recursive backtracking}
\end{myitemize}
\item[PF5. Event-driven programming] ~
Some competition tasks may involve a dialog with a reactive environment.
Implementing such an interaction with the provided environment is \Lbb.
Everything not directly related to the implementation of reactive tasks is
\emph{Out of focus}
\end{description}
\subsection {Algorithms and Complexity (AL)}
\label{subsubsec:AL}
We quote from the IEEE-CS Curriculum:
\begin{quote}\sffamily\small
Algorithms are fundamental to computer science and software engineering.
The real-world performance of any software system depends only on two things:
(1)~the algorithms chosen and
(2)~the suitability and efficiency of the various layers of implementation.
Good algorithm design is therefore crucial for the performance of all software systems.
Moreover,
the study of algorithms provides insight into the intrinsic nature of the problem
as well as possible solution techniques independent of programming language,
programming paradigm, computer hardware, or any other implementation aspect.
\end{quote}
\begin{description}
\item[AL1. Basic algorithmic analysis] ~
\begin{myitemize}
\Lb Algorithm specification, precondition, postcondition, correctness, invariants
\Lc\CC{Asymptotic analysis of upper complexity bounds} (informally if possible)
\Lc\CC{Big O notation}
\Lc\CC{Standard complexity classes}
(constant, logarithmic, linear, $\mathcal{O}(n \log n)$, quadratic, cubic, exponential)
\Lc\CC{Time and space tradeoffs in algorithms}
% \Lc\new{\CC{Empirical measurements of performance, tuning parameters}}
\Lc Empirical performance measurements.
\end{myitemize}
\richard{Moved tuning up, with feedback, contestants tend to tune their codes a lot
with the current feedback system}
\emph{Out of focus\/}:
\begin{itemize}
\item \CC{Identifying differences among best, average, and worst case behaviors},
\item \CC{Little o, Omega, and Theta notation},
\item Tuning parameters to reduce running time\new{, memory consumption or other measures of performance}
%\item \remove{\CC{Empirical measurements of performance, tuning parameters}}
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item{Asymptotic analysis of average complexity bounds},
\item{Using recurrence relations to analyze recursive algorithms}
\end{itemize}
\item[AL2. Algorithmic strategies] ~
\begin{myitemize}
\Lc Simple loop design strategies
\Lc\CC{Brute-force algorithms} (exhaustive search)
\Lc\CC{Greedy algorithms} %(insofar that understanding correctness is elementary)
\Lc\CC{Divide-and-conquer} %(insofar that understanding efficiency is elementary)
\Lc\CC{Backtracking} (recursive and non-recursive), \CC{Branch-and-bound} %(insofar that understanding correctness and efficiency are elementary)
% \Lc\remove{\CC{Pattern matching and string/text algorithms.} Only basic
% algorithms are \Lcc: for instance, the Knuth-Morris-Pratt algorithm
% should already be considered \emph{Out of focus}.}
\Lc\CC{Dynamic programming}\footnote{The IEEE-CS Curriculum puts this under AL8, but we believe it belongs here.}
\end{myitemize}
%% \Lc\CC{Pattern matching and string/text algorithms}\footnote{Only basic
%% algorithms are \Lcc: for instance, the Knuth-Morris-Pratt algorithm
%% should already be considered \emph{Out of focus}.}
%%
\richard{Moved string algorithms to algorithms / data structures}
\emph{Out of focus\/}:
\begin{itemize}
\item Heuristics
\item Finding good features for machine learning tasks\footnote{E.g., finding a good way to classify images in the IOI 2013 Art class problem.}
\item Discrete approximation algorithms
%\footnote{The purpose of this item is to include
%tasks such as Xor from IOI 2002, where the contestants have to devise an approximation
%algorithm, and achieve scores based on its performance relative to other submissions.
%Textbook approximation algorithms are \emph{Excluded}.}
\item Randomized algorithms.
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item Clustering algorithms (e.g. $k$-means, $k$-nearest neighbor)
\item Minimizing multi-variate functions using numerical approaches.
\end{itemize}
\item[AL3a. Algorithms] ~
\begin{myitemize}
\Lc Simple algorithms involving integers: radix conversion, Euclid's algorithm, primality test by $\mathcal{O}(\sqrt{n})$ trial division, Sieve of Eratosthenes, factorization (by trial division or a sieve), efficient exponentiation
\Lc Simple operations on arbitrary precision integers (addition, subtraction, simple multiplication)\footnote{The necessity to implement these operations should be obvious from the problem statement.}
\Lc Simple array manipulation (filling, shifting, rotating, reversal, resizing, minimum/maximum, prefix sums, histogram, bucket sort)
\Lc \new{Simple string algorithms (e.g., naive substring search)}
\Lc\CC{sequential} processing/search \CC{and binary search}
% \Lc Search by elimination, ``slope'' search
% \Lc\CC{Quadratic sorting algorithms (selection, insertion)}
\Lc \CC{Quicksort} and Quickselect to find the $k$-th smallest element.
\Lc\CC{$\mathcal{O}(n \log n)$} worst-case \CC{sorting algorithms (heap sort, merge sort)}
\Lc Traversals of ordered trees (pre-, in-, and post-order)
\Lc\CC{Depth- and breadth-first traversals}
\Lc{Applications of the depth-first traversal tree, such as:}
\begin{itemize}
\item \CC{Topological sort}
\item {Algorithms to determine the (existence of an) Euler path/cycle}
\end{itemize}
\Lc Finding connected components and transitive closures.
\Lc{Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)}
\Lc{Minimum spanning tree (Jarn\'\i k-Prim and Kruskal algorithms)}
\Lc $O(VE)$ time algorithm for computing maximum bipartite matching.
\Lc \new{Biconnectivity in undirected graphs (bridges, articulation points).}
\Lc \new{Connectivity in directed graphs (strongly connected components).}
\end{myitemize}
\emph{Excluded, but open to discussion}
\begin{itemize}
\item Maximum flow. Flow/cut duality theorem.
\item \new{\remove{Strongly connected components, bridges and articulation points.}}
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
% \item \remove{Strongly connected components in directed graphs}
\item Primal-dual graph algorithms (e.g. minimum cost arborescence)
\item Lexicographical BFS, maximum adjacency search and their properties
\end{itemize}
\item[AL3b. Data structures] ~\label{sec:dataStructures}
\begin{myitemize}
\Lb Stacks and queues
\Lc \CC{Representations of graphs (adjacency lists, adjacency matrix)}
\Lb Binary heap data structures
\Lc Representation of disjoint sets: the Union-Find data structure.
\Lb 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).\footnote{Note that in computational geometry there are different data structures with similar names.}
\Lc {Balanced binary search trees}\footnote{Problems will not be designed to distinguish between
the implementation of BBSTs, such as treaps, splay trees, AVL trees, or scapegoat trees}
\Lb Augmented binary search trees
%% \Lc Interval trees\footnote{This is the data structure that contains a complete binary tree
%% built on top of an array; supporting queries and updates on individual elements and intervals
%% in logarithmic time. Sometimes this data structure is called a segment tree, a range tree, or a
%% tournament tree.}${}^{,}$\footnote{Note that in computational geometry there are different data
%% structures with similar names. Those are not covered by this item.}
%% and Fenwick trees\footnote{%
%% First introduced in P. Fenwick: \emph{A New Data Structure for Cumulative Frequency Tables},
%% Software -- Practice And Experience 24(3):327--336, 1994.
%% Also known as binary indexed trees.
%% A 2D version of a Fenwick tree was used in the IOI 2001 task Mobiles.
%% This can be seen as a more space-efficient version of an interval tree.}
\Lc $O(\log n)$ time algorithms for answering lowest common ancestor queries in a static rooted tree.\footnote{Once again, different implementations meeting this requirement will not be distinguished.}
\Lc Creating persistent data structures by path copying or using fat nodes.%\footnote{Gains in memory using methods such as fat-node will not be distinguished}}
\Lc Composition of data structures, e.g. $2$-D statically balanced binary trees
%% \Lc Interaction with abstract data types: priority queues; ordered and unordered sets and maps
\Lb \new{Tries}
\end{myitemize}
%%\emph{Out of focus}
%%\begin{itemize}
%%% \item \new{Behaviors of data structures under merging}
%%\end{itemize}
\emph{Excluded, but considering inclusion}
\begin{itemize}
\item String algorithms: there is evidence that the inter-reducibility
between KMP, Rabin-Karp hashing, suffix arrays/tree, suffix automaton,
and Aho-Corasick makes them difficult to separate.
\item Heavy-light decomposition and separator structures for static trees.
\item Data structures for dynamically changing trees and their use in graph algorithms.
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item Complex heap variants such as binomial and Fibonacci heaps,
%%\item \remove{Implementation of any general balanced tree (e.g., AVL, treaps, splay trees),}
\item Using and implementing \CC{hash tables} (incl. strategies to resolve collisions)
\end{itemize}
\item[AL4. Distributed algorithms] ~
\emph{Out of focus}
\item[AL5. Basic computability] ~
All topics related to computability are \emph{Explicitly excluded}.
This includes the following:
\CC{Tractable and intractable problems};
\CC{Uncomputable functions};
\CC{The halting problem};
\CC{Implications of uncomputability}
However, see AL7 for basic computational models.
\item[AL6. The complexity classes P and NP] ~
Topics related to non-determinism, proofs of NP-hardness (reductions),
and everything related is \emph{Explicitly excluded}.
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 \emph{Explicitly excluded} does not mean that an NP-hard
problem cannot appear at an IOI.
\item[AL7. Automata and grammars] ~
\begin{myitemize}
\Lb Understanding a simple grammar in Backus-Naur form
\end{myitemize}
\emph{Out of focus\/}:
\begin{itemize}
\item{Formal definition and properties of finite-state machines},
\item{Context-free grammars} and related rewriting systems,
\item{Regular expressions}
\end{itemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item Properties other than the fact that automata are graphs and that grammars have parse trees.
%% \item All textbook proofs and constructions -- e.g., the product construction
%% of an automaton for the intersection of languages, the conversion of
%% a NFA to a DFA, DFA minimization, grammar normal forms.
\end{itemize}
% \richard{`all text book proofs' seemed very vague}
\item[AL8. Advanced algorithmic analysis] ~
\begin{myitemize}
\Lc Basics of combinatorial game theory, winning and losing positions, minimax algorithm for optimal game playing
\Lc Amortized analysis.
\end{myitemize}
\emph{Out of focus\/}:
\begin{itemize}
\item {Online algorithms}
\item Randomized algorithms
\end{itemize}
\richard{What is combinatorial optimization??}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item{Alpha-beta pruning}
\item Theory of combinatorial games, e.g. NIM game, Sprague-Grundy theory
\end{itemize}
\richard{Combinatorial games / grundy theory seem more of a discrete math technique, why are they here?}
\item[AL9. Cryptographic algorithms] ~
\emph{Out of focus}
\item[AL10. Geometric algorithms]
\begin{myitemize}
\Lc Representing points, vectors, lines, line segments.
\Lc Checking for colinear points, parallel/orthogonal vectors, clockwise turns.
\Lc Intersection of two lines.
\Lc Computing area of a polygon.
\Lc Checking whether a (general/convex) polygon contains a point.
\Lc Coordinate compression.
% \Lc\remove{Convex hull finding algorithms}
\Lc $\mathcal{O}(n\log{n})$ time algorithms for convex hull
\Lc Sweeping line method
\end{myitemize}
\emph{Explicitly excluded\/}:
\begin{itemize}
\item Point-line duality
%% \richard{Explicitly banned circles due to related precision issues (they
%%often lead to fourth order predicates), is this ok?}
\item Halfspace intersection, Voronoi diagrams, Delaunay triangulations.
\item Computing coordinates of circle intersections against lines and circles.
\item Linear programming in 3 or more dimensions
and its geometric interpretations.
\end{itemize}
\item[AL11. Parallel algorithms] ~
\emph{Out of focus}
\end{description}
\subsection{Other Areas in Computing Science}
\label{subsubsec:other-areas}
Except for GV (specified below), all areas are \emph{Explicitly excluded}.
\begin{description}
\item[AR. Architecture and Organization] ~
\item[OS. Operating Systems] ~
\item[NC. Net-Centric Computing] (a.k.a. cloud computing)
\item[PL. Programming Languages] ~
\item[HC. Human-Computer Interaction] ~
\item[GV. Graphics and Visual Computing] ~
Basic aspects of processing graphical data are \emph{Out of focus},
everything else (including the use of graphics libraries such as OpenGL)
is \emph{Explicitly excluded}.
\item[IS. Intelligent Systems] ~
\item[IM. Information Management] ~
\item[SP. Social and Professional Issues] ~
\item[CN. Computational Science] ~
\end{description}
Notes: AR is about digital systems, assembly language, instruction pipelining, cache memories, etc.
OS is about the \emph{design\/} of operating systems, not their usage.
PL is about the \emph{analysis and design\/} of programming languages, not their usage.
HC is about the \emph{design\/} of user interfaces.
\emph{Usage} of the operating system, GUIs and programming languages is
covered in \S\ref{subsec:computer-literacy} and \S\ref{subsubsec:PF}.
\section {Software Engineering (SE)}
\label{subsec:software-engineering}
We quote from~the IEEE-CS Curriculum:
\begin{quote}\sffamily\footnotesize
Software engineering is the discipline concerned with the application of theory,
knowledge, and practice for effectively and efficiently building software systems
that satisfy the requirements of users and customers.
\end{quote}
In the IOI competition,
the application of software engineering concerns the use of light-weight techniques
for small, one-off, single-developer projects under time pressure.
All included topics are~\Lc$\!$.
\begin{description}
\item[SE1. Software design] ~
\begin{myitemize}
\Lc\CC{Fundamental design concepts and principles}
\Lc\CC{Design patterns}
\Lc\CC{Structured design}
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Transform an abstract algorithm into a concrete, efficient program
expressed in one of the allowed programming languages,
possibly using standard or competition-specific libraries.
\item[--]
Make their programs read data from and write data to text files
according to a prescribed simple format
%\footnote{%
%Evaluation of submitted programs will only be based on input data
%that agrees with the prescribed input format.
%Submitted programs need not check input validity.
%However, when contestants offer input data of their own design,
%then obviously no such guarantees can be made.}
\end{itemize}
\end{quote}
(See also SE2 immediately below)
\emph{Explicitly excluded\/}:
\CC{Software architecture},
\CC{Design for reuse},
\CC{Object-Oriented analysis and design},
\CC{Component-level design}
\item[SE2. Using APIs] ~
\begin{myitemize}
\Lc\CC{API (Application Programming Interface) programming}
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Use competition-specific libraries according to the provided specification.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Programming by example},
\CC{Debugging in the API environment},
\CC{Class browsers and related tools},
\CC{Introduction to component-based computing}
\item[SE3. Software tools and environments] ~
\begin{myitemize}
\Lc\CC{Programming environments}, incl.\ IDE (Integrated Development Environment)
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Write and edit program texts using one of the provided program editors.
\item[--]
Compile and execute their own programs.
\item[--]
Debug their own programs.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Testing tools},
\CC{Configuration management tools}
\CC{Requirements analysis and design modeling tools},
\CC{Tool integration mechanisms}
\item[SE4. Software processes] ~
\begin{myitemize}
\Lc\CC{Software life-cycle and process models}
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Understand the various phases in the solution development process
and select appropriate approaches.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Process assessment models},
\CC{Software process metrics}
\item[SE5. Software requirements and specification] ~
\begin{myitemize}
\Lc\CC{Functional and nonfunctional requirements}\\
\Lc\CC{Basic concepts of formal specification techniques}
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
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.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Prototyping},
\CC{Requirements elicitation},
\CC{Requirements analysis modeling techniques}
\item[SE6. Software validation] ~
\begin{myitemize}
\Lc\CC{Testing fundamentals, including test plan creation and test case generation}
\Lc\CC{Black-box and white-box testing techniques}
\Lc\CC{Unit, integration, validation, and system testing}
\Lc\CC{Inspections}
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Apply techniques that maximize the the opportunity to detect common errors
(e.g.\ through well-structured code, code review, built-in tests, test execution).
\item[--]
Test (parts of) their own programs.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Validation planning},
\CC{Object-oriented testing}
\item[SE7. Software evolution] ~
\emph{Explicitly excluded\/}:
\CC{Software maintenance},
\CC{Characteristics of maintainable software},
\CC{Re-engineering},
\CC{Legacy systems},
\CC{Software reuse}
\item[SE8. Software project management] ~
\begin{myitemize}
\Lc\CC{Project scheduling} (especially time management)
\Lc\CC{Risk analysis}
\Lc\CC{Software configuration management}
\end{myitemize}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Manage time spent on various activities.
\item[--]
Weigh risks when choosing between alternative approaches.
\item[--]
Keep track of various versions and their status while developing solutions.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Software quality assurance},
\CC{Team management},
\CC{Software measurement and estimation techniques},
\CC{Project management tools}
\item[SE9. Component-based computing] ~
\emph{Explicitly excluded\/}
\item[SE10. Formal methods] ~
\CC{Formal methods concepts} (notion of correctness proof, invariant)\\
\CC{Pre and post assertions}
In particular, contestants may be expected to
\begin{quote}
\begin{itemize}
\item[--]
Reason about the correctness and efficiency of algorithms and programs.
\end{itemize}
\end{quote}
\emph{Explicitly excluded\/}:
\CC{Formal verification},
\CC{Formal specification languages},
\CC{Executable and non-executable specifications}
\item[SE11. Software reliability] ~
\emph{Explicitly excluded\/}
\item[SE12. Specialized systems development] ~
\emph{Explicitly excluded\/}
\end{description}
\section {Computer Literacy}
\label{subsec:computer-literacy}
The text of this section is \Lc.
\medskip
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 \emph{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.
\begin{quote}
\emph{Out of focus\/}:
Calculator,
Word-processors,
Spreadsheet applications,
Database management systems,
E-mail clients,
Graphics tools (drawing, painting)
\end{quote}
%%% \begin{thebibliography}{99}
%%%
%%% \bibitem%[ACM/IEEE-CS JCTF(2001)]
%%% {acm-ieee-cs-jctf:01}
%%% ACM/IEEE-CS Joint Curriculum Task Force.
%%% \emph{Computing Curricula 2001: Computer Science Volume}.
%%% December 2001.\\
%%% {\small\verb"http://www.acm.org/sigcse/cc2001/"}
%%%
%%% \bibitem%[Fenwick(1994)]
%%% {fenwick:94}
%%% P. Fenwick.
%%% ``A New Data Structure for Cumulative Frequency Tables'',
%%% \emph{Software -- Practice And Experience},
%%% \textbf{24}(3):327--336 (1994).
%%%
%%% \bibitem%[Horv\'ath, Verhoeff(2003)]
%%% {horvath-verhoeff:03}
%%% G. Horv\'ath and T. Verhoeff.
%%% ``Numerical Difficulties in Pre-University Education and Competitions'',
%%% \emph{Informatics in Education},
%%% \textbf{2}(1):21--38 (2003).
%%%
%%% \bibitem%[IOI(2006)]
%%% {ioi}
%%% IOI,
%%% \emph{International Olympiad in Informatics},
%%% Internet WWW-site.\\
%%% \verb"http://www.IOInformatics.org/"
%%% (accessed February~2006).
%%%
%%% \bibitem%[Polya(1948)]
%%% {polya:48}
%%% G. Polya.
%%% \emph{How to Solve It: A New Aspect of Mathematical Method}.
%%% Princeton Univ.\ Press, 1948.
%%%
%%% \bibitem%[Verhoeff(2004)]
%%% {verhoeff:04}
%%% T. Verhoeff.
%%% \emph{Concepts, Terminology, and Notations for IOI Competition Tasks},
%%% document presented at IOI 2004 in Athens,
%%% 12~Sep.~2004.\\
%%% {\footnotesize\verb"http://scienceolympiads.org/ioi/sc/documents/terminology.pdf"}
%%%
%%% \end{thebibliography}
\end{document}
% vim: fdm=marker