The design of divide and conquer algorithms

DOI10.1016/0167-6423(85)90003-6MaRDI QIDQ760206zbMATH OpenOpenAlexFDO

Authors Douglas R. Smith

Publication date 1985

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6423(85)90003-6

zbMATH Keywords

cartesian productconvex hulldivide and conquer algorithmsfunctionalityprogram schemesorting

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Algorithms in computer science (68W99)

Review text

The structure common to a class of divide and conquer algorithms is represented by a program scheme. A theorem is presented which relates the functionality of a divide and conquer algorithm to its structure and the functionalities of its subalgorithms. Several strategies for designing divide and conquer algorithms arise from this theorem and they are used to formally derive algorithms for sorting a list of numbers, forming the cartesian product of two sets, and finding the convex hull of a set of planar points.

Recommendations

• Applications of a strategy for designing divide-and-conquer algorithms
• Top-down synthesis of divide-and-conquer algorithms
• scientific article; zbMATH DE number 4009819
• Exact asymptotics of divide-and-conquer recurrences
• Pipelines for Divide-and-Conquer Functions

Cited in

(11)

• Top-down synthesis of divide-and-conquer algorithms
• Applications of a strategy for designing divide-and-conquer algorithms
• Smart stacking for import containers using customer information at automated container terminals
• From supervised instance and feature selection algorithms to dual selection: a review
• scientific article; zbMATH DE number 5568181 (Why is no real title available?)
• Pipelines for Divide-and-Conquer Functions
• scientific article; zbMATH DE number 203098 (Why is no real title available?)
• Synthesis of list algorithms by mechanical proving
• Synthesis of implementations for divide-and-conquer specifications
• A computational framework based on the dynamic pipeline approach
• Algorithm theories and design tactics

This page was built for publication: The design of divide and conquer algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q760206)