Computational Science

COMPUTATIONAL SCIENCE BY BRUCE G. BUCHANAN Department of Computer Science University of Pittsburgh Pittsburgh, Pa. " The Boyer-Moore string searching algorithm is a best choice for many problems in which a pattern of length m is to be matched in a text of length n, for small alphabets or long pattems. A recent paper exploits the-space-time trade-off to improve the algorithm’s speed by 50% for long patterns. Some experimental results -are presented that also indicate the effecfiveness of

Oct 16, 1989
Bruce Buchanan

COMPUTATIONAL SCIENCE

BY BRUCE G. BUCHANAN
Department of Computer Science
University of Pittsburgh
Pittsburgh, Pa.

" The Boyer-Moore string searching algorithm is a best choice for many problems in which a pattern of length m is to be matched in a text of length n, for small alphabets or long pattems. A recent paper exploits the-space-time trade-off to improve the algorithm’s speed by 50% for long patterns. Some experimental results -are presented that also indicate the effecfiveness of the modified algorithm for large English text databases.

R.A. Baeza-Yates, “Improved string searching,” Software— Practice and Experience, 19,257-71, March 1989. (University of Waterloo, Ontario, Canada)

" For networks of computers, several measures of reliability and fault tolerance have been proposed. A new, global connectivity measure is defined that captures the intuition that a “good” network is more difficult to separate into large disjoint components than into small ones. It also highlights potential trouble spots arising when some node is not tightly connected to the rest of the network.

D.B. Skillicorn, B. Kocay, “A global measure of network connectivity,” Journal of Parallel and Distributed Computing, 7, 165-77, August 1989. (Queen’s University, Kingston, Ontario; University of Manitoba, Winnipeg, Canada)

" Modification of expert systems, as any software, often introduces errors. An experimental study shows the value of using a design/documentation tool, with structured knowledge formats, in: terms of both decreased introduction of errors and decreased time to make modifications.

K.M. Swigger, R.P. Brazile, “Experimental comparison of design/documentation formats for expert systems,” International Journal of Man Machine Studies, 31, 47-60, July 1989. (University of North Texas, Denton)

Digital video interactive (DVI) technology stores images and other presentation materials digitally and allows customized reconfiguration on personal computers. The present capabilities and future applications of DVI are presented in one of several related papers within a special issue.

G.D. Ripley, “DVI—A digital multimedia technology,” Communications of the ACM, 32, 811-22, July 1989. (Intel Corporation, Princeton, N.J.)

" Traditional memory architectures store and retrieve infomation by addressing specific memory locations. Software implementations of content-addressable and associative memories have demonstrated their value. Hardware versions are becoming commercially available and will give us new architectures.

L. Chisvin, RJ. Duckworth, “Content-addressable memory and associative memory; alternatives to the ubiquitous RAM,” IEEE Computer, 22, 51-64, July 1989. (Digital Equipment Corporation, Maynard, Mass., and Worcester Polytechnic Institute, Worcester, Mass.)

" Parallel processing promises enhanced performance, but only if programmers have the language constructs that allow them to write parallel programs. A recent article explores extensions to Common Lisp, designed for writing symbolic programs, that programmers can use on multiprocessor systems.

R. Goldman, R.P. Gabriel, “Qlisp: parallel processing in Lisp,” IEEE Software, 6,51-9, July 1989. (Lucid Inc., Menlo Park, Calif.)