Alamülesanne

alamülesanne, literally "subtask" in Estonian, refers to a smaller instance of a problem that can be solved independently and used as part of solving the original problem. The concept is common in mathematics, algorithm design, and competitive programming, where a complex problem is broken down into more manageable pieces that resemble the same type of problem.

Typically, an algorithm defines a solution in terms of alamülesanded. In recursive formulations, a solution to the original problem is obtained by solving each alamülesanne and combining their results. Depending on the task, alamülesanded may be independent or overlapping.

Dynamic programming and memoization rely on alamülesanded by computing each subproblem only once and reusing the result; this approach contrasts with naive recursion, which may recompute the same subproblems. Subproblems can be solved in a top-down (memoized) or bottom-up (iterative) manner. An example is computing the nth Fibonacci number, where F(n) is defined in terms of F(n-1) and F(n-2).

In mathematics, alamülesanded appear as lemmas or auxiliary problems that facilitate proving a larger theorem; in programming contests, problems are often framed as a main task with several alamülesanded guiding the solution.

Etymology: the word combines "ala" meaning sub- or lower and "ülesanne" meaning task or assignment.