Applications of a strategy for designing divide-and-conquer algorithms
type: Item
instance of: scholarly article
title: Applications of a strategy for designing divide-and-conquer algorithms
zbMATH Open document ID: 0616.68045
DOI: 10.1016/0167-6423(87)90034-7
author: Douglas R. Smith
published in: Science of Computer Programming
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 3999292
zbMATH Keywords: algorithm design
zbMATH Keywords: divide-and-conquer algorithms
MaRDI profile type: Publication
full work available at URL: 0167-6423(87)90034-7
OpenAlex ID: W2051228988
description: scientific article; zbMATH DE number 3999292