Important!

This is the last implementation of the course. Therefore, the last day to complete all course tasks (Study plan, Screenshot from USACO, USACO task solutions, and contest participation report) is 31.7.2024. After July 2024, it is not anymore possible to study the course.

Course information

Algorithmic problem solving is a course concentrating on algorithmic programming. During the course:

• Participants study reading material and solve programming exercises in USACO server.
• After implementing required amount of programming tasks, students participate in an online programming contest (like Nordic Collegiate Programming Contest (NCPC)).

Course’s Sisu page (basic information, implementation, registration, etc).

Course staff:

• Heikki Hyyrö
• Timo Poranen

Detailed workflow to study the course

1. Sign in using Sisu-system.
2. Join course’s Moodle forum.
3. Return your study plan to the Moodle. The study plan should include:
   • Your schedule. For example, USACO tasks 1-10 in June, tasks 11-30 in July, remaining tasks in August.
   • Contest that you are going to participate.
   • Location of your USACO task solutions. This can be in your Google drive folder or in a private code repository. Do not share publicly your code, so use password or some other method.
   • Update your study plan if there are major changes.
4. Solve 40 USACO tasks and study recommended reading material.
   • Return your solutions in a .zip-file to the Moodle.
   • Return a screenshot that shows which tasks you have solved in USACO.
5. Participate in a programming contest. Possible contests include:
   • Nordic Collegiate Programming Contest
   • Croatian Open Contest in Informatics.
   • CodeChef (Montly Challenge).
   • Other contests are also possible, but contact teachers to verify suitability.
6. After the contest, return your contest participation report (experiences, certificate, link to results, etc.) to the Moodle.

Recommended reading material

• Laaksonen, A.: Competitive Programmer’s Handbook (online).

More detailed course information

Algorithmic problem solving is an advanced level, 5 ECTS course in Computer Science. The course involves studying and solving programming contest tasks, which requires good general problem solving skills, a good knowledge of some of the most common algorithms and data structures, and at least fairly fluent basic programming skills in C or C++.

The students will first practice independently by studying related reading material and solving contest-style programming tasks. As a “final exam”, the students will form 1-3 person teams and participate in some programming contest that is accessible online. The contest participation can be done anonymously (using a nickname), but you need to inform the course teachers about your contest information and results.

About programming contest tasks

A typical programming contest task requires one to implement a program that reads a problem instance (input) from a file or standard input, computes a valid solution, and writes the solution (output) to a file or standard output. The task may contain restrictions on how much time and/or memory the program can use in solving the problem. The programs may also be scored depending on their relative efficiency (speed).

The problems themselves are usually algorithmic in nature and require some degree of non-trivial problem solving. Solving a task has two aspects: how to solve the problem in general, and how to solve the problem efficiently. The problems may be difficult to solve even without any restrictions. But programming contest tasks typically require finding an efficient solution: one that does not use too much time or memory. In practice this means that the contestants need to have a good knowledge of efficient algorithms and data structures as otherwise their programs will be too slow or use too much space.

As a short example, the first task of the 2011 NCPC was roughly (but not exactly) as follows:

• Input: a grid square of size n x n, where 1 ≤ n ≤ 1000. Each grid cell is either free or has an obstacle (the input describes which cells are free and which are not).
• Task: compute how many different cell-paths there exist from the cell (1,1) to the cell (n,n), that is, from the top-left corner to the bottom-right corner. All paths start from the cell (1,1). From there on, any path may be repeatedly extended by going one step down or one step right from its current cell, but only to cells that are free.
• Output: the number of different paths from (1,1) to (n,n).