Competitive Programming I
Non Degree Course
Tutorial classes are used to introduce theoretical concepts and to discuss the solution to particular problems. Lab classes consist in solving programming problems, individually and in a team. The assessment takes into account the grades obtained in solving several programming problems and in individual defenses. The Mooshak system, commonly used in programming contests, is used as an automated judging tool in the programming assignments. The test cases for each problem are generated in order to test different scenarios.
To develop skills in solving programming problems that arise in the context of International Collegiate Programming Competitions (ICPC). From a description of a problem, the student should be able, individually and in a team, to relate it to other known problems, identify the most appropriate solution approach to solve it considering its run-time and space complexity, and implement it in an efficient manner.
1. Introduction to algorithms and data structures
2. Strategies for solving competition problems
3. Algorithm paradigms
1. Divide and conquer
3. Dynamic programming
4. Greedy algorithms
1. Search problems
2. Graph problems
3. Computational geometry
4. String problems
5. Numerical problems
7. Ad-hoc problems
8. Other problems.
Luís Filipe dos Santos Coelho Paquete
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 3rd ed., 2009.
S.Skiena and M. Revilla, Progamming Challenges, Springer, 2003.
A. Laaksonen, Guide to Competitive Programming, Springer, 2nd ed., 2020
J. Erikson, Algorithms, 2019
S. Halim, F. Halim, Competitive programming 4 (books 1 and 2), 2020.