• ES Español
• EN English

5.33. Algorithms for Complex Problems (Mandatory)

5.33.1. Justification ↑ Back to top

Competitive Programming trains students to solve complex algorithmic problems under time and resource constraints. This course bridges the gap between theoretical algorithm design and high-performance implementation. It covers advanced techniques in dynamic programming, graph theory, and mathematics, fostering the analytical thinking required for top-tier software engineering interviews and international programming contests like the ICPC.

5.33.2. Generales Goals ↑ Back to top

1. Master advanced competitive programming techniques and paradigms.
2. Develop the ability to quickly analyze the complexity of potential solutions.
3. Implement efficient data structures for range queries and dynamic updates.
4. Apply specialized mathematical and geometric algorithms to solve contests problems.
5. Optimize code for execution speed and memory usage in a competitive environment.

5.33.3. Contribution to Outcomes ↑ Back to top

AG-C08) Problem Analysis: Identifies, formulates, and analyzes complex computing problems. (Usage)

AG-C12) Applies computer science theory and software development fundamentals to produce computer-based solutions. (Usage)

5.33.4. Content ↑ Back to top

5.33.4.1. Algorithmic Strategies (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Halim and Halim, 2020; Laaksonen, 2020)

Topics

1. Complete Search: Recursive Backtracking and Bitmasking.
2. Greedy Strategies: Choice property and optimal substructure.
3. Divide and Conquer: Binary Search on the answer and Ternary Search.
4. Dynamic Programming: State reduction, Digit DP, and DP on trees.

Learning Outcomes

1. Apply search pruning techniques to solve NP-hard problems in small constraints [Usage]
2. Identify the most efficient paradigm for a given problem statement [Assessment]

5.33.4.2. Foundational Algorithms (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Halim and Halim, 2020; Skiena, 2020)

Topics

1. Fenwick Trees (Binary Indexed Trees).
2. Segment Trees: Lazy Propagation and Persistent Segment Trees.
3. Square Root Decomposition and Mo's Algorithm.
4. Sparse Tables for RMQ.

Learning Outcomes

1. Implement range query structures for real-time data updates [Assessment]
2. Analyze the trade-offs between different range query data structures [Usage]

5.33.4.3. Foundational Algorithms (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Laaksonen, 2020; Halim and Halim, 2020)

Topics

1. Network Flow: Max Flow Min Cut (Dinic's and Edmonds-Karp).
2. Strongly Connected Components (Tarjan's and Kosaraju's).
3. Bipartite Matching and Heavy-Light Decomposition.
4. Centroid Decomposition on trees.

Learning Outcomes

1. For each algorithm in this unit explain step-by-step how the algorithm operates [Explain]
2. For each algorithmic approach (e.g., sorting) in this unit apply a prototypical example of the approach (e.g., merge sort) [Apply]
3. Given requirements for a problem, develop multiple solutions using various data structures and algorithms. Subsequently, evaluate the suitability, strengths, and weaknesses selecting an approach that best satisfies the requirements [Create]
4. Explain factors beyond computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data [Explain]
5. For each of the algorithms and algorithmic approaches in the KA Core topics:
6. Explain a prototypical example of the algorithm, and
7. Explain step-by-step how the algorithm operates. enumerate [Explain]

5.33.4.4. Foundational Algorithms (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Skiena, 2020; Laaksonen, 2020)

Topics

1. Number Theory: Sieve of Eratosthenes, Extended Euclidean, and Modular Inverse.
2. Combinatorics: Inclusion-Exclusion and Burnside's Lemma.
3. Computational Geometry: Cross product, Convex Hull (Monotone Chain), and Line intersection.
4. Fast Fourier Transform (FFT) for polynomial multiplication.

Learning Outcomes

1. Solve combinatorial problems using modular arithmetic [Usage]
2. Implement geometric primitives for spatial relationship analysis [Assessment]

5.33.5. Bibliography ↑ Back to top

Halim, S. and Halim, F. (2020). Competitive Programming 4: The Lower Bound of Programming Contests. Lulu.

Laaksonen, A. (2020). Competitive Programmer's Handbook. Draft.

Skiena, S. S. (2020). The Algorithm Design Manual. Springer, 3rd edition.