\documentclass[a4paper,11pt,oneside]{article}
\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{\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}~}
\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 1.2}
\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 -3pt
\let\oldLa=\La
\let\oldLb=\Lb
\let\oldLc=\Lc
\def\La{\item[\oldLa]}
\def\Lb{\item[\oldLb]}
\def\Lc{\item[\oldLc]}
}{
\end{itemize}
}

\begin{document}
\title{The International Olympiad in Informatics Syllabus}
\maketitle

\section{Authors and Contact Information}

The original proposal of the IOI Syllabus was co-authored by:

\begin{itemize}
\item Tom Verhoeff \\
(TU Eindhoven, The Netherlands, t.verhoeff at tue.nl)
\item Gyula Horv\'ath \\
(University of Szeged, Hungary, horvath at inf.u-szeged.hu)
\item Krzysztof Diks \\
(Warsaw University, Poland, diks at mimuw.edu.pl)
\item Gordon Cormack \\
(University of Waterloo, Canada, gvcormac at uwaterloo.ca) 
\end{itemize}

\noindent
The current maintainer of the Syllabus is

\begin{itemize}
\item Michal Fori\v sek \\
(Comenius University, Slovakia, forisek at dcs.fmph.uniba.sk) 
\end{itemize}
                
You are welcome to send any feedback on the Syllabus to the current maintainer's e-mail address. 

\section{Introduction}

This Syllabus has two main purposes.

The first purpose is to provide 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.

The second and closely related purpose is to help 
the organizers of national olympiads prepare
their students for the IOI.

The goal of this Syllabus is to give a classification of topics and concepts 
from mathematics and computer science. The Syllabus
specifies which of these concepts are suitable to appear in the competition
tasks and/or their solutions.

Issues related to the usage of suitable terminology and notations in competition tasks
are beyond the scope of this document. (These issues are discussed in~\cite{verhoeff:04}.)

\bigskip
\bigskip

\noindent
This Syllabus classifies each topic into one of three categories:
\begin{description}
\item[Included] This is the default category.
  It means that the topic is relevant for the IOI competition,
  that is,
  it could play a role in the description of a competition task,
  in the contestant's process of solving the task,
  or in the model solution.
  Included topics are further qualified as:
  \begin{description}
  \item[\La Unlimited]
    The topic concerns prerequisite knowledge,
    and can appear in task descriptions without further clarification\footnote{%
Danger of confusion (e.g.\ Fibonacci numbers)
must always be avoided by further clarification.}.

    Example: \emph{Integer} in~\S\ref{subsubsec:NG}

  \item[\Lb 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 Not for task description]
     It will not appear in tasks descriptions,
     but may be needed for developing solutions
     or understanding model solutions.

    Example: \emph{Asymptotic analysis of upper complexity bounds\/}
    in \S\ref{subsubsec:AL}~AL1
  \end{description}
  
\item[Not needed]
  This means that although the topic may be of interest,
  it will not appear in task descriptions or model solutions,
  and that it will not be needed to arrive at a solution.
  However, see also the note below about possible promotion to \emph{Included}.

  Example: \emph{Binomial theorem\/} in~\S\ref{subsubsec:DS}~DS4

\item[Excluded]
  This means that the topic falls outside the scope of the IOI competition.

  Example: \emph{Calculus\/} in~\$\ref{subsubsec:other-mathematics}
\end{description}
The classifications under \emph{Not needed\/} and \emph{Excluded\/} are not intended to be exhaustive,
but rather serve as examples that map out the boundary.
Topics not mentioned in the Syllabus are to be treated as \emph{Excluded}.
However,
topics not classified for use in task descriptions,
including topics not mentioned,
could be promoted to \emph{Included~\Lbb},
provided that they require no special knowledge and
will be defined in terms of included non-\Lc~concepts,
in a precise, concise, and clear way.
Special cases of non-included topics can be good candidates for such promotion.
For example, planar graphs are excluded, but trees (a special case) are in fact included.

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.
Of course, each task or the Competition Rules can impose binding restrictions,
which are to be considered as part of the problem statement
(e.g.\ that no threads or auxiliary files are to be used).

Topics literally copied from~\cite{acm-ieee-cs-jctf:01}
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 Properties of integers (positive, negative, even, odd, divisible, prime)
\La Fractions, percentages
\La Point, vector, Cartesian coordinates (on a 2D integer grid)
\Lb Euclidean distance, Pythagoras' Theorem
\La Line segment, intersection properties
\Lb Angle
\La Triangle, rectangle, square, circle
\La Polygon (vertex, side/edge, simple, convex, inside/outside, area)
\end{myitemize}

\emph{Excluded\/}:
  Real and complex numbers, 
  general conics (parabolas, hyperbolas, ellipses),
  trigonometric functions
  % FIXME
  %\footnote{There may be
  %exceptions for simple applications of trigonometric functions, such as
  %sorting points by a polar angle.}
\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)}
  \La\CC{Sets (Venn diagrams, complements, Cartesian products, power sets)}
  \Lb\CC{Pigeonhole principle}
  \end{myitemize}

  \emph{Excluded\/}:
    \CC{Cardinality and countability} (of infinite sets)

\item[DS2. Basic logic] ~

  \begin{myitemize}
  \La\CC{Propositional logic}
  \La\CC{Logical connectives} (incl.\ their basic properties)
  \La\CC{Truth tables}
  \La\CC{Predicate logic}
  \La\CC{Universal and existential quantification}\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{Not needed\/}:
    \CC{Validity},
    \CC{Normal forms}

  \emph{Excluded\/}:
    \CC{Limitations of predicate logic}

\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 (sums and product rule, inclusion-exclusion principle,
    arithmetic and geometric progressions, Fibonacci numbers)}
  \Lb\CC{Pigeonhole principle} (to obtain bounds)
  \Lb\CC{Permutations and combinations (basic definitions)}
  \Lb Factorial function, binomial coefficient
  \Lc\CC{Pascal's identity}, \CC{Binomial theorem}
  \end{myitemize}

  \emph{Excluded\/}:
    \CC{Solving of recurrence relations}

\item[DS5. Graphs and trees] ~

  \begin{myitemize}
  \Lb\CC{Trees} (and their basic properties)
    % connected, no cycles, $\# \mbox{nodes} = \# \mbox{edges} + 1$;
    % ordered/not-ordered)\\
  \Lb\CC{Undirected graphs} (degree, path, cycle, connectedness, Euler/Hamilton 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} (defining the node order for ordered trees)
  \Lb `Decorated' graphs with edge/node labels, weights, colors
  \Lb Multigraphs, graphs with self-loops
  \end{myitemize}

  \emph{Not needed\/}:
    Planar graphs,
    Bipartite graphs,
    Hypergraphs

\item[DS6. Discrete probability] ~
  \emph{Excluded}

\end{description}

\subsection {Other Areas in Mathematics}
\label{subsubsec:other-mathematics}

\begin{quote}
\emph{Not needed\/}:
  Polynomials,
  Matrices and operations,
  Geometry in 3D space

\emph{Excluded\/}:
  (Linear) Algebra,
  Calculus,
  Probability,
  Statistics
\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}
  (the specific languages available at an IOI will 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;
  see e.g.~\cite{polya:48})
  \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.\ multidimensional arrays)
  \La\CC{Records}
  \La\CC{Strings and string processing}
  \Lb\CC{Static and stack allocation} (elementary automatic memory management)
  \Lb\CC{Linked structures} (linear and branching)
  \Lb Static memory implementation strategies for linked structures
  \Lb\CC{Implementation strategies for stacks and queues}
  \Lb\CC{Implementation strategies for graphs and trees}
  \Lb\CC{Strategies for choosing the right data structure}
  \Lb Abstract data types, priority queue, dynamic set, dynamic map
  \end{myitemize}

  \emph{Not needed\/}:
    \CC{Data representation in memory},
    \CC{Heap allocation},
    \CC{Runtime storage management},
    \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.}
%    Arbitrary-size integer arithmetic\footnote{%
%This means that tasks are solvable with the appropriate primitive integer types,
%without concern for overflow.}

  \emph{Excluded\/}:
    Floating-point numbers (see~\cite{horvath-verhoeff:03}),
    \CC{Implementation strategies for hash tables}

\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{Recursive backtracking}
  \end{myitemize}

  \emph{Not needed\/}:
    \CC{Implementation of recursion}

\item[PF5. Event-driven programming] ~

  \emph{Not needed}

%  Note~1:
  However, competition tasks could involve a dialog with a reactive environment.

%  Note~2: Some ways of using libraries may require handling of exceptions.

\end{description}

\subsection {Algorithms and Complexity (AL)}
\label{subsubsec:AL}

We quote from~\cite{acm-ieee-cs-jctf:01}:
\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}
  \end{myitemize}

  \emph{Not needed\/}:
    \CC{Identifying differences among best, average, and worst case behaviors},
    \CC{Little o, omega, and theta notation},
    \CC{Empirical measurements of performance}

  \emph{Excluded\/}:
    \CC{Asymptotic analysis of average complexity bounds},
    \CC{Using recurrence relations to analyze recursive algorithms}

\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)
  \Lc\CC{Branch-and-bound} (insofar that understanding correctness and efficiency are elementary)
  \Lc\CC{Pattern matching and string/text algorithms} (insofar that understanding correctness and
  efficiency is elementary)
  \Lc\CC{Dynamic programming}\footnote{%
\cite{acm-ieee-cs-jctf:01} puts this under AL8, but we believe it belongs here.} 
  \Lc 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}.}
  \end{myitemize}
   
  \emph{Excluded\/}:
    \CC{Heuristics},
    \CC{Numerical approximation algorithms}

\item[AL3. Fundamental computing algorithms] ~

  \begin{myitemize}
  \Lc\CC{Simple numerical algorithms} involving integers
   (radix conversion, Euclid's algorithm,
    primality test by $\mathcal{O}(\sqrt{N})$ trial division,
    Sieve of Eratosthenes, factorization, 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 Sequential processing, \CC{sequential and binary search algorithms}
  \Lc Search by elimination, ``slope'' search
  \Lc\CC{Quadratic sorting algorithms (selection, insertion)}
  \Lc Partitioning, order statistics by repeated partitioning, \CC{Quicksort}
  \Lc\CC{$\mathcal{O}(N \log N)$} worst-case \CC{sorting algorithms (heap sort, merge sort)}
  \Lc Binary heap data structure\footnote{The more complex heap data structures, such as
  binomial and Fibonacci heaps, are \emph{Excluded}.}
  \Lc\CC{Binary search trees}
  \Lc Fenwick trees\footnote{Introduced in \cite{fenwick:94}, also known as binary indexed trees.
    A 2D version of a Fenwick tree was used in the IOI 2001 task Mobiles. 
    This data structure is sometimes known as a segment/interval tree, but this name
    shall be avoided to prevent confusion with data structures that actually store
    segments or intervals.} 
  \Lc\CC{Representations of graphs (adjacency list, adjacency matrix)}
  \Lc Traversals of ordered trees
  \Lc\CC{Depth- and breadth-first traversals} of graphs, determining connected components of
  an undirected graph
  \Lc\CC{Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)}
  \Lc\CC{Transitive closure (Floyd's algorithm)}
  \Lc\CC{Minimum spanning tree (Jarn\'\i k-Prim and Kruskal\footnote{In terms of a disjoint-set ADT} algorithms)}
  \Lc\CC{Topological sort}
  \Lc Algorithms to determine (existence of) an Euler path/cycle
  \end{myitemize}

  \emph{Not needed\/}:
    \CC{Hash tables (including collision-avoidance strategies)}

  \emph{Excluded\/}:
    \CC{Simple numerical algorithms} involving floating-point arithmetic,
    Maximum flow algorithms,
    Bipartite matching algorithms,
    Strongly connected components in directed graphs

\item[AL4. Distributed algorithms] ~

  \emph{Excluded}

\item[AL5. Basic computability] ~

  \emph{Not needed\/}:
    \CC{Finite-state machines},
    \CC{Context-free grammars}
    (could be considered in the future)
  
  \emph{Excluded\/}:
    \CC{Tractable and intractable problems},
    \CC{Uncomputable functions},
    \CC{The halting problem},
    \CC{Implications of uncomputability}

\item[AL6. The complexity classes P and NP] ~

  \emph{Excluded}

\item[AL7. Automata and grammars] ~

  \emph{Excluded}

  However,
  \CC{Finite automata},
  \CC{Regular expressions}, and rewriting systems
  could be considered in the future.

\item[AL8. Advanced algorithmic analysis] ~

  \begin{myitemize}
  \Lc Basics of Combinatorial game theory, Minimax algorithms for optimal game playing
  \end{myitemize}

  \emph{Not needed\/}:
    \CC{Online and offline algorithms},
    \CC{Combinatorial optimization}

  \emph{Excluded\/}:
    \CC{Amortized analysis},
    \CC{Randomized algorithms},
    Alpha-beta pruning,
    Sprague-Grundy theory

\item[AL9. Cryptographic algorithms] ~

  \emph{Excluded}

\item[AL10. Geometric algorithms] (on 2D grids, i.e.\ integer $(x,y)$-coordinates)
 
  \begin{myitemize}
  \Lc\CC{Line segments: properties, intersections}
  \Lc Point location w.r.t.\ simple polygon
  \Lc\CC{Convex hull finding algorithms}
  \Lc Sweeping line method
  \end{myitemize}

\item[AL11. Parallel algorithms] ~

  \emph{Excluded}

\end{description}

\subsection{Other Areas in Computing Science}
\label{subsubsec:other-areas}

The following areas are all \emph{Excluded}.

\begin{description}
\item[AR. Architecture and Organization] ~

  \emph{Excluded}

  This area is about digital systems, assembly language,
  instruction pipelining, cache memories, etc.%\footnote{%
%Competition organizers should be aware of the possible consequences.}
  The basic structure of a computer
  is covered in~\S\ref{subsec:computer-literacy}.

\item[OS. Operating Systems] ~

  \emph{Excluded}

  This area is about the \emph{design\/} of operating systems, covering
  concurrency, scheduling, memory management, security, file systems,
  real-time and embedded systems, fault tolerance, etc.
  The basics of \emph{using\/} the high-level services of an operating system
  are covered in~\S\ref{subsec:computer-literacy},
  but low-level system calls are specifically excluded.

\item[NC. Net-Centric Computing] ~

  \emph{Excluded}

\item[PL. Programming Languages] ~ 

  \emph{Excluded}

  This area is about \emph{analysis and design\/} of programming languages, covering
  classification, virtual machines, translation, object-orientation,
  functional programming, type systems, semantics, and language design.
  The basics of \emph{using\/} a high-level programming language are in~\S\ref{subsubsec:PF}.

\item[HC. Human-Computer Interaction] ~ 

  \emph{Excluded}

  This area is about the \emph{design\/} of user interfaces, etc.
  The basics of \emph{using\/} a (graphical) user interface
  are covered in~\S\ref{subsec:computer-literacy}.

\item[GV. Graphics and Visual Computing] ~ 
  
  \emph{Excluded}

\item[IS. Intelligent Systems] ~

  \emph{Excluded}

\item[IM. Information Management] ~

  \emph{Excluded}

\item[SP. Social and Professional Issues] ~

  \emph{Excluded}

\item[CN. Computational Science] ~ 
 
  \emph{Excluded}
\end{description}

\section {Software Engineering (SE)}
\label{subsec:software-engineering}

We quote from~\cite{acm-ieee-cs-jctf:01}:
\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}

  \emph{Not needed\/}:
    \CC{Software architecture},
    \CC{Design for reuse}

  \emph{Excluded\/}:
    \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{Not needed\/}:
    \CC{Programming by example},
    \CC{Debugging in the API environment}

  \emph{Excluded\/}:
    \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{Not needed\/}:
    \CC{Testing tools},
    \CC{Configuration management tools}

  \emph{Excluded\/}:
    \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{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{Not needed\/}:
    \CC{Prototyping}

  \emph{Excluded\/}:
    \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{Not needed\/}:
    \CC{Validation planning}

  \emph{Excluded\/}:
    \CC{Object-oriented testing}

\item[SE7. Software evolution] ~

  \emph{Not needed\/}:
    \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{Not needed\/}:
    \CC{Software quality assurance}

  \emph{Excluded\/}:
    \CC{Team management},
    \CC{Software measurement and estimation techniques},
    \CC{Project management tools}

\item[SE9. Component-based computing] ~

  \emph{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{Not needed\/}:
    \CC{Formal verification}

  \emph{Excluded}:
    \CC{Formal specification languages},
    \CC{Executable and non-executable specifications}

\item[SE11. Software reliability] ~

  \emph{Excluded}

\item[SE12. Specialized systems development] ~

  \emph{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{Not needed\/}:
  Calculator

\emph{Excluded\/}:
  Word-processors,
  Spreadsheet applications,
  Data base 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