Applications of a strategy for designing divide-and-conquer algorithms (Q1821558)

A strategy for designing divide-and-conquer algorithms that was originally presented in a previous article is extended and applied to several new problems. The extension involves techniques for modifying the original specification based on specific kinds of failures that can occur during the design process. We derive several divide-and-conquer algorithms that are substantially more efficient than previously known algorithms. This paper also emphasizes the naturalness with which divide- and-conquer algorithms can be transformed into a parallel format. One problem explored is to find the maximum sum over all rectangular subregions of a given matrix of integers. For an \(n\times n\) matrix there is a straightforward \(O(n^ 6)\) enumeration algorithm. We derive a \(O(n^ 3)\) divide-and-conquer algorithm, then show that it can be executed in \(O(\log^ 2 n)\) time in parallel and, furthermore, with pipelining of inputs it can be executed with O(1) time between successive outputs.