«Sports programming and Algorithms» elective course

Goals:

Preparing KhAI entrants and students for various competitions and Olympics on programming, algorithmic improvement of practical training of young programmers, and the fundamental teaching of theoretical training in the algorithms to the best American and European universities level.

The list of potential competitions:

  1. International Student Olympiad «ACM ICPC», http://icpc.baylor.edu
  2. International open student programming contest named after S.A. Lebedev and V.M. Glushkov «KPI-Open», http://kpi-open.org
  3. Open Cup on programming named after E.V. Pankratiev, http://www.opencup.ru
  4. Winter School on programming at KNURE, http://wschool.kharkov.ua
  5. Marathons and other competitions at TopCoder, http://topcoder.com/tc
  6. Individual tournaments as the "Google Code Jam", http://code.google.com/codejam/
  7. Sports programming open championship of Kharkov, http://khcup.qbit.org.ua

Event format:

  1. Weekly lecture meeting that includes thematic homework analysis. Lectures may be alternated with seminars, where students present their solutions and the results.
  2. Weekly lecture meeting that includes thematic homework analysis. Lectures may be alternated with seminars, where students present their solutions and the results «online judge» resources such as http://acm.timus.ru, http://uva.onlinejudge.org and others.
  3. Practical competition is being held every two weeks. Students are organized in groups of up to 3 people and compete on the basis of archives such as http://codeforces.com, https://icpcarchive.ecs.baylor.edu and others. 
  4. Monthly individual project as a task to find interesting assignments from olympiad archives and solution collections and its presentation to the class, which includes the analysis and comparison of solution options.

Supervisors:

  1. Starov, Aleksey Aleksandrovich – online supervisor (lectures and training materials preparation, decision analysis, monthly remote presentations).
  2. Rusin, Dmitriy Olegovich – on-sight supervisor (meetings on the KhAI basis, educational process organization, assistance with lectures and solutions).

The plan of the topics:

  1. Introduction to sports programming, examples of various Olympiad problems, communication algorithms with practical programming
  2. Classification of Olympiad problems with examples, necessary sections of mathematics for repetition - 2 sessions
  3. The concept of algorithms complexity, O-notation and others.
  4. Algebra and Number Theory (from the Sieve of Eratosthenes to Length arithmetic) - at least 3 lectures
  5. The paradigm of "divide-and-rule", practical application - at least 3 lectures
  6. Simple graph algorithms - at least 2 lectures
  7. Use of algorithms on graphs - at least 2 classes
  8. Flows in graph theory and in olympiad problems
  9. Examples of complex algorithms on graphs (RMQ, Hungarian algorithm and others)
  10. Search tasks in terms of artificial intelligence and game theory - at least 2 lectures
  11. “Greedy” algorithms
  12. "Dynamic programming" paradigm - at least 3 classes
  13. Introduction to combinatorics
  14. Computing geometry basics- at least 2 classes
  15. More complex algorithmic problems
  16. Numerical methods
  17. Strings and sequences - at least 2 classes
  18. Smart data structures - at least 3 classes
  19. NP-completeness and how to fight it
  20. Review of programming tricks

These topics will be dealt with at the intersection, and the full cycle - repeated iteratively being bound by theory, and complexity. It is important that the novice contestant's knowledge and experience developed in parallel in each direction. This list isn't final (some of the topics will be given up during a year, while others may be added, some of the topics hours may be cut and vice versa).

Literature:

  1. Algorithms. Design and Analysis - T. Kormen., Charles Leiserson, R. Rivest
  2. Algorithms on C ++ / Algorithms to Java - R. Sedgewick
  3. Olympiad programming tasks / Algorithms. Guide to development - S. Skiena
  4. Algorithms and programs. Olympiad problems solution - I.N. Porublev, A.B. Stavrovskiy
  5. KNURE Winter programming School materials.
  6. KhAI Algorithms http://ostarov.github.io/Algorithms_KhAI/

This list is only the basic list of books and it will will be majorly expanded during the course.