Competitive Programming I

Recommended Prerequisites

Not applicable.

Teaching Methods

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 defences. 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.

Learning Outcomes

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.

Work Placement(s)

No

Syllabus

1. Introduction to algorithms and data structures

2. Strategies for solving competition problems

3. Algorithm paradigms

3.1. Divide and conquer

3.2. Backtracking

3.3. Dynamic programming

3.4. Greedy algorithms

3.5. Simulation

4. Applications

4.1. Search problems

4.2. Graph problems

4.3. Computational geometry

4.4. String problems

4.5. Numerical problems

4.6. Cryptography/hashing

4.7. Ad-hoc problems

4.8. Other problems

Head Lecturer(s)

Luís Filipe dos Santos Coelho Paquete

Assessment Methods

Assessment
The assessment takes into account the grades obtained in solving several programming problems and in individual defences: 100.0%

Bibliography

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.