Форум DL

My Profile

Competitions' Tasks in Informatics for the ``Pre-Master'' Group of School Students

Emil KELEVEDJIEV, Zornitsa DZHENKOVA
Institute of Mathematics and Informatics,
Bulgarian Academy of Sciences Akad. G. Bonchev str., block 8, 1113 Sofia, Bulgaria
Ivan Vazov High School 54 Mitko Palauzov str., 5300 Gabrovo, Bulgaria

In Bulgaria since 2001, several age group systems have been applied to divide school
students for the national informatics competitions (the Autumn, Winter, and Spring Tour-
naments, as well for the three rounds of the National Olympiad in Informatics). Starting
in 2002, groups were introduced with letter names: A, B, C, and D, which comprised 11–
12, 9–10, 7–8, and 4–6th school grades, respectively. Now, we have a slightly modi?ed
system with 5 age groups A, B, C, D, and E, that cover 11–12, 9–10, 7–8, 6, and 4–5th
school grades, respectively.

1) Graphs (20 tasks). From the widely developed algorithmic area of the theory of
graphs, prevalent methods in considered tasks are for finding the shortest path, determining the connectivity, cycles, topological sorting and minimum spanning trees. A part of
these tasks relate to geometrical graphs, and methods of solving are dynamic programming, divide and conquer, and etc.

2) Dynamic programming (20 tasks). In this section we treat tasks, which are directly
related to this basic approach to the compilation of algorithms. We mention that tasks of
the other sections can also often be solvable with this approach.

3) Combinatorics (12 tasks). Contains tasks related to non-equivalent con?gurations,
coding, representation of numbers, etc. One of the tasks requires ”only an output ?le”.

4) Geometry (12 tasks). Covers topics related to polygon’s area, convex hull, crossing
line segments, etc. Some of these tasks are solved with the approach of recursion and
with elementary numerical methods.

5) Search and sorting (10 tasks). This group is related to a broad theme, containing
binary search, exhaustive search, application of greedy approaches and some elementary
numerical methods.

6) Arithmetic (5 tasks). These tasks require knowledge for divisibility of numbers,
fractions, numerical systems, etc.

7) Games (4 tasks). Small group containing tasks to search for strategies in games
with used the tabular methods, odd-parity methods, etc.

8) Data Structures (4 tasks). Here are allocated tasks, in whose solution the main approach is aimed at organizing the data, with which to improve response time for necessary operations. We see that in the given tasks are used the following data structures: Queue, Pyramid, Priority Queue and System of Disjoint Sets (“Union-Find”).

Curriculum for the Bulgarian National Training Camps, group B

  
        1 year

 1 STL containers and iterators. 
 2 Permutations. 
 3 Combinatorial configurations. Encoding and decoding. 
 4 Data structures for set presentations. 
 5 Algorithmic geometry. Intersections of points and lines. 
 6 Algorithmic geometry. Polygons. Convex hull. 
 7 Hash tables. 
 8 Graphs. Bi-connectivity. Strong connectivity. 
 9 Graphs. Euler’s and Hamilton’s cycles. 
10 Graphs. Minimum spanning trees.
11 Graphs. Critical paths. 
12 Catalan’s numbers. 
13 Dynamic programming tasks.
14 Games. Min-max strategies. 
15 Recursion tasks. Recurrences. 
16 Strings. Searching. Distances. 
17 Data compression. Huffman’s codes. 

        2 year

18 STL algorithms. 
19 Combinatorial configurations on sets. 
20 Gray’s sequences. 
21 Data structures for string algorithms. 
22 Introduction to networks and maximal flows. 
23 Partitions of numbers. 
24 Partitions of sets. 
25 Matching in graphs. 
26 Algorithmic geometry. Closets and farthest points. 
27 Special trees. 
28 Strings. Syntax analysis. 
29 Graph coloring. Planar graphs. Geometric graphs. 
30 Introduction to formal grammars and automata. 
31 Recursion tasks. 
32 Games. Alpha-beta pruning. 
33 Dynamic programming tasks. 
34 System of linear equations.

My Profile

Young Talent in Informatics.
Preliminary Findings of an IOI Survey Launched by AICA in Cooperation with IT STAR
Plamen NEDKOV
Project Coordinator of the Survey

The paper presents some preliminary results of the IOI-related Survey intended to examine the experience of several Central, Eastern and Southern European countries whose participation in competitions of the International Olympiad in Informatics is truly remarkable. It identifies several common features, which have contributed to this success. These include tradition in organizing and participating in informatics-related competitions, strong emphasis on mathematics in national education, further extra-curricular activities and individual training, early start in training and competing, dedicated and motivated individuals and organizations.

This paper (and, indeed, the survey) is based on a questionnaire related to the selection,
preparation and participation of national IOI teams of Bulgaria, Croatia, Latvia,
Poland and Slovakia. These countries were chosen in order to have a representative sample
of the whole of Eastern Europe – Latvia for the Baltics, Poland and Slovakia for
Central Europe and Bulgaria and Croatia for South-Eastern Europe. With the exception
of Poland, these countries are rather small in all counts but deliver remarkable results at
international informatics competitions.

Their overall ranking, on the basis of IOI medals, is presented in Table 1.

Their IOI achievement is striking and they were our start-up point, however, the
project is open to the experience of other countries in the region, which have done
remarkably well in IOI. We hope to have on board in the near future material concerning
Romania, 6th in the overall IOI ranking, the Czech rep. – 12th, Hungary – 15th, and other.

http://www.eduardische.com/ioi/

 
 # Country     Gold Silver Bronze Total
 1 China         57   22     12    91
 2 Russia        40   28     12    80
 3 Poland        31   27     23    81
 4 US of America 30   30     14    74
 7 Slovakia      20   32     18    70
 8 Bulgaria      18   32     30    80
14 Belarus       11   27     26    64 (в этот фрагмент таблицы строка добавлена мной)
17 Croatia       10   23     29    62
23 Latvia         5   19     33    57

Chairpersons/leaders of the national bodies and IOI teams were invited to complete
a questionnaire and to comment on such issues as the national team selection, coaching,
communication and promotion, motivation and background for success. A section of the
questionnaire was on informatics curricula in schools. In addition, personal interviews
were organized in some of the countries. This was carried-out so as to gain a deeper
understanding of the following.

On the basis of our work so far we can identify the following groupings of factors contributing to the successful participation of the national teams of these countries in IOI competitions:

• Tradition.
• Strong emphasis on mathematics in national education.
• Targeted extra-curricular activities.
• Early start and gaining experience by participating in competitions.
• Systematic management, dedicated people.
• Motivation and reward.

In the case of Bulgaria and Latvia, private educational institutions are involved in
preparing all who wish to compete: in Bulgaria, the A&B private school in Shumen was
established with the objective to prepare pupils for national and international informatic
related competitions (Mollov et al., 2009), in Latvia, Progmeistars private school (http://www.progmeistars.lv) has similar objectives. Both institutions have developed and introduced methodologies in delivering results and a confirmation of this is that pupils who have attended their course
have won gold medals during the last IOI-2011 in Thailand.

My Profile

Comparisons of the IMO and IOI
Peter TAYLOR
Australian Mathematics Trust, University of Canberra ACT 2601 Australia

There are several International olympiads for secondary school students, but the five which are most widely recognised are those in mathematics, physics, chemistry, biology and informatics, in approximate order of founding. Most of these were originally founded under the auspices of UNESCO. Of these, the discipline most closely related to Informatics is mathematics, and in fact in several countries, for example Australia and Bulgaria (the latter of which can be credited as the founding country of IOI), the two olympiad programs are administered by the same organisation. The purpose of this paper is to compare the two olympiads in some detail, including tasks, topics, evaluation, etc. Despite the close relationship between the disciplines themselves, and the fact that there are similarities in the structure of the olympiads, in fact between all five, such as the medal structure, it is surprising also how different are the evolved traditions of IMO and IOI.

Keywords:
International Mathematical Olympiad (IMO), International Olympiad in Informatics (IOI), syllabus, task preparation, exam format, problem evaluation

http://www.imo-official.org

IMO questions ... fall into one of the categories of algebra, combinatorics, geometry and number theory.

More contemporary collections of problems and solutions can be found on the
Art of Problem-Solving site
The 2011 windmill problem referred in the text can be found at
A solution is not on this site on 11 March 2012.

My Profile

Putka - A Web Application in Support of Computer Programming Education
Jelko URBANCIC, Mitja TRAMPUS
Zavod za racunalnisko izobrazevanje Ljubljana
(Institute for Computer Education Ljubljana) p.p. 4716, SI-1001 Ljubljana, Slovenia
Jozef Stefan Institute Jamova 39, SI-1000 Ljubljana, Slovenia

In many countries the interest in pre-university computer programming education has been changed during the last decade. In the Slovenian case, the education reform, demographic and other reasons produced a big decrease of interest among young people. The paper describes our approach to increasing the interest for computer programming by integrating a web based tool ``Putka'' into the education process. Putka is, at its core, an online judge. Two facts make it stand apart from similar applications, however. First, its design and many additional features are influenced by its heavy use in support during long-term programming classes rather than only one-off competitions. Second, while its use in the classroom was the primary motivation for developing Putka, it has also hosted numerous competitions with varying rules. Out of necessity, this multifaceted nature bore what we believe to be a very flexible technical design.

Keywords:
computer programming education, web based education tool, online judge

The number of contestants fell from 3000 in the ?rst half of the 90s to less than 100 nation-wide in the period from 2005 till 2010, ?nally climbing to 200 in 2012.

We can in?uence neither the demographic factors nor the educational policy within the
country. The students’ motivation is the only factor that can be in?uenced by us. We
believed a user friendly learning tool that provided students with instant feedback and
progress reports would enhance their motivation. Although online judges with ample task
collections already existed, very few of them met even one out of our three criteria:

• a large number of entry-level tasks systematically covering the basic programming
concepts, e.g., simple loops or conditionals;
• tasks and user interface in Slovene (important for young students);
• the possibility of administering the system: creating user groups, tracking progress
of students, creating tasks and possibly contests ...

My Profile

Competitive Programming 2
Author: Steven HALIM, Felix HALIM

Publishing house : Lulu
Country          : United Kingdom
Year of edition  : 2011
Language         : English
Number of pages  : 262

The format throughout the book is generally a brief overview of a given topic, followed
by multiple algorithms, exercises, a long list of categorised problems to practise,
and a brief conclusion. Starting with the categorised problems, this is a wonderful
resource. Around 1300 problems appear in the book (almost exclusively from the University
of Valladolid [2] online judge) and the bulk of these appear in these lists. These
problems, which appear after an algorithm or group of related algorithms, typically have
multiple sections each of which list a good number of problems and also highlights three
’must t ry’ problems. For example, the graph traversal problem list contains 56 prob-
lems (18 must try problems) over 6 sections: Just Graph Traversal; Flood Fill / Finding
Connected Components; Topological Sort; Bipartite Graph Check; Finding Articulation
Points / Bridges; Finding Strongly Connected Components. The ad-hoc section towards
the front of the book contains 160 problems.

My Profile

Teaching Programming for Secondary School:
A Pedagogical Content Knowledge Based Approach
Mara SAELI

Publishing house : Eindhoven University of Technology
Country          : The Netherlands
Year of edition  : 2012
Language         : English
Number of pages  : 164
ISBN             : 978-90-386-3084-7

In this book (a PhD thesis) Mara Saeli reports her research about “teaching programming
in secondary school with the aim of portraying the Pedagogical Content Knowledge of
this subject", as is mentioned on the backside of it. The reason for a review in
this journal is that it contains a meticulous description and analysis of why teaching of
programming in secondary school is important, what should be taught, what problems
and limitations students have while learning programming and how the teaching could be
performed. All these issues have a great relevance for teachers who prepare students for
Olympiads in informatics and for researchers who investigate this Olympiads. Problem
solving, perhaps one of the most important aspects for Olympiad’s participants turns out
to be a very relevant part of the teaching and learning of programming.

four key questions:
why to teach . . .,
what to teach . . .,
learning dif?culties of . . .,
and how to teach . . .?

Saeli started to answer these questions by performing a broad literature review with
respect to programming in secondary school. She found the following answers.

– Why: programming enhances students’ problem solving skills and offers them a
learning environment which includes aspects of different disciplines, gives oppor-
tunities to use modularity and transferability of the knowledge and/or skills, and to
work with a multi-disciplinary subject.
– What: a list of concepts/aspects which a programming curriculum should include,
for instance knowledge of data, instructions and syntax of a programming lan-
guage, but also primitive expressions, means of combination and of abstraction,
strategies, and programming sustainability which refers to the ability to create user
friendly and attractive software that takes care of ethical and privacy issues.
– Learning dif?culties: dif?culty to instruct the machine about the solution of a prob-
lem, the tendency to converse with a computer as if it was human, the tendency the
students maintain a local, limited point of view, failing to ?nd a suitable solution.
– How: for instance offering a simple programming language so students can focus
on the syntax, carefully choosing a diversity of problems in order to focus the
students on algorithmic thinking.

My Profile

Olympiad in Informatics, vol.7 (2013)

My Profile

Growing Algorithmic Thinking Through Interactive Problems to Encourage Learning Programming
Belgium

... Before teaching programming to pupils, it is important to develop their ability to think algorithmically.

The three stages composing an ILPADS activity.
1. Playing (Interactive animation)
2. Organizing the steps (Flowcharts)
3. Programming (Python)

The stages drive the learner from the simple understanding of the algorithm to writing it in a programming language.

Example given - Sorting machine
Future examples - Gues Who and 15-puzzle

Journal of Applied Computing and Information

My Profile

Pushing the Boundary of Programming Contests
Michal FORISEK
Comenius University, Bratislava, Slovakia

In traditional programming contests the tasks almost always focus on design of efficient algorithms. In this paper, we discuss that this does not have to be the case in the future, and we give a significant number of concrete tasks that cover other areas of Computer Science. All of the tasks presented in this paper have actually been used in past programming contests.

My Profile

Expecting the Unexpected
Singapore

In recent IOIs, the IOI community has observed creative tasks such as `Language\!'/`Maze\!'/ `Saveit' (IOI Tasks, 2010), `Parrots' (IOI Tasks, 2011), and `Odometer'/`Supper' (IOI Tasks, 2012) that caught many contestants and their coaches off-guard. This is because it is very hard to train our students to be 100% ready for such unexpected tasks. Reading the IOI 2013 call for tasks requirements (IOI Call for Tasks, 2013) points us towards more of IOI tasks of such nature. In this paper, we share how the Singapore IOI team expects the unexpected.

I foresee that with this trend of increasing skill level of
the top students, the Scienti?c Committee of the future IOIs have no choice but to keep
surprising these brilliant students (and their coaches) by using more and more creative
tasks.

My Profile

State Competitions in Informatics and the Supporting Online Learning and Contest Management System with Collaboration and Personalization Features MENDO
Makedonia

My Profile

Computer Maintenance via Batch Execution
Martin Mares, Czech Republic

Organization of programming contests often involves maintenance of hundreds of computers. While parallel installation of operating systems is a well understood problem, further maintenance of installed systems is often cumbersome. We present a simple, yet powerful batch processing system, which makes this task easier.

My Profile

Algorithmic Results on a Novel Computational Problem
Krassimir MANEV, Bulgaria

My Profile

Latvian Olympiad in Informatics - Lessons Learned

My Profile

Where to Use and How not to Use Polynomial String Hashing
Jakub PACHOCKI, Poland

We discuss the usefulness of polynomial string hashing in programming competition tasks. We show why several common choices of parameters of a hash function can easily lead to a large number of collisions. We particularly concentrate on the case of hashing modulo the size of the integer type used for computation of fingerprints, that is, modulo a power of two. We also give examples of tasks in which string hashing yields a solution much simpler than the solutions obtained using other known algorithms and data structures for string processing.