Reduction

Get to know how to reduce a problem to a simpler one using recursion.

What is reduction?

Reduction is the single most common technique used in designing algorithms. Reducing one problem XX to another problem YY means to write an algorithm for XX that uses an algorithm for YY as a black box or subroutine. Crucially, the correctness of the resulting algorithm for XX cannot depend in any way on how the algorithm for YY works. The only thing we can assume is that the black box solves YY correctly. The inner workings of the black box are simply none of our business; they’re somebody else’s problem. It’s often best to literally think of the black box as functioning purely by magic.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy