• Articles • Previous Articles     Next Articles

Unified Approach for Developing EfficientAlgorithmic Programs

Xue Jinyun;   

  1. Computer Software Institute; Jiangxi Normal University; Nanchang 330027; Computer Engineering Department; Santa Clara University; Santa Clara; CA 95053; USA;
  • Online:1997-07-10 Published:1997-07-10

A unified approach called partition-and-recur for developing efficient and correct algorithmic programs is presented. An algorithm (represented by recurrence and initiation) is separated from program, and special attention is paid to algorithm manipulation rather than program calculus. An algorithm is exactly a set of mathematical formulae. It is easier for formal derivation and proof. After getting efficient and correct algorithm, a trivial transformation is used to get a final program. The approach covers several known algorithm design techniques, e.g. dynamic programming, greedy, divide-and-conquer and enumeration, etc. The techniques of partition and recurrence are not new. Partition is a general approach for dealing with complicated objects and is typically used in divide-and-conquer approach. Recurrence is used in algorithm analysis, in developing loop invariants and dynamic programming approach. The main contribution is combining two techniques used in typical algorithm developm…

Key words: zero decomposition; strong regular set; automated geometry theorem proving; subsidiary condition;



[1] Backhouse R C. Program Construction and Verification. Prentice-Hall, London, 1986.

[2] Dijkstra E W. A Discipline of Programming. Prentice-Hall, New Jersey, 1976.

[3] Dijkstra E W. Scholten C S. Predicate Calculus and Program Semantics. Springer-Verlag, NewYork, 1990. ……….
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. An Algorithm for Finding D-Time Table[J]. , 1992, 7(1): 62 -67 .
[2] Fei Xianglin; Liao Lei; Wang Hezhen; Wang Chengzao;. Structured Development Environment Based on the Object-Oriented Concepts[J]. , 1992, 7(3): 193 -201 .
[3] Ye Shiwei; Shi Zhongzhi;. A Necessary Condition about the Optimum Partition on a Finite Set of Samples and Its Application to Clustering Analysis[J]. , 1995, 10(6): 545 -556 .
[4] Zhang Yaoxue; Chen Hua; Zhang Yue; Liu Guoli;. SDL-TRAN-An Interactive Generator for Formal Description Language SDL[J]. , 1996, 11(1): 49 -60 .
[5] WU Jie;. Reliable Communication on Cube-Based Multicomputers[J]. , 1996, 11(3): 208 -221 .
[6] Sibabrata RAY; JIANG Hong;. Reconfigurable Optical Bus and Performance Optimization[J]. , 1996, 11(3): 296 -312 .
[7] Tang Changjie; Xiong Min;. The Temporal Mechanisms in Hbase[J]. , 1996, 11(4): 365 -371 .
[8] Yan Zongfu; Liu Mingye;. The RTL Binding and Mapping Approach of VHDL High-Level Synthesis System HLS/BIT[J]. , 1996, 11(6): 562 -569 .
[9] wang Xuejun; Shi Chunyi;. A Multiagent Dynamic interaction Testbed:Theoretic Framework, System Architecture and Experimentation[J]. , 1997, 12(2): 121 -132 .
[10] Yu Huiqun; Song Guoxin; Sun Yongqiang;. Completeness of the Accumulation Calculus[J]. , 1998, 13(1): 25 -31 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved