The Structure of Divide and Conquer Algorithms.

Abstract

The structure of divide and conquer algorithms is represented by program schemes which provide a kind of normal-form for expressing these algorithms. A theorem relating the correctness of a divide and conquer algorithm to the correctness of its subalgorithms is given. Several strategies for designing divide and conquer algorithms for sorting a list of numbers, evaluating a propositional formula, and forming the cartesian product of two sets. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 04, 1983
Accession Number
ADA126086

Entities

People

  • Douglas R. Smith

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Classification
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Decomposition
  • Language
  • Military Research
  • Notation
  • Parallel Computing
  • Parallel Processing
  • Programming Languages
  • Reasoning
  • Security
  • Specifications

Fields of Study

  • Computer science

Readers

  • Game Theory.
  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.