BASIC TOPICS IN EXPERIMENTAL

COMPUTER SCIENCE

1997 Jun 24, 5:46 p.m.

Abstract

Computer science has an experimental scientific aspect—like every

other science. Experiments are made with suitable computer programs

in order to discover facts. The programs are usually not applications

but specialized to the scientific problem being investigated.

It is a

mistake to divide computer science simply into theoretical and applied

parts. Basic computer science has both theoretical and applied parts.

Applied computer science certainly has an experimental part, and

presumably it has a theoretical part also.

We wouldn’t expect to have to tell you this.

Unfortunately, many computer scientists and other people divide

computer science into theoretical and applied computer science, leav-

ing no place for basic experimental work.

This report describes basic experimental work in several domains

of computer science.

Introduction

Some computer scientists and some computer engineers mistakenly identify

basic research with theory and applied research with experiment. A recent

report by the National Research Council Academic Careers for Experi-

mental Computer Scientists and Engineers1 [Cou95] was particularly

bad about this. All the experimental work mentioned was explicitly applied,

i.e. in support of specific applied projects. This may have something to do

1http://www.nap.edu/nap/online/acesc/

INTRODUCTION

with the persistent tendency of that body to deny any distinction between

science and engineering in computing.

However, computer science also has an important basic research experi-

mental component, and our object is to describe some of this work enough to

show the important role experiment plays in basic computer science research.

At present this is only an outline.

Here are some topics:

search Richard Korf (korf@cs.ucla.edu) will write a section on this.

game playing Turing proposed a chess program in the 1940s, and recently

Deep Blue had a match with the world champion. The experimental

chess programs have taught a lot about heuristics and what computa-

tional abilities are required to match human performance. The failure

to make good Go programs illustrates that we still don’t understand

how to make a program that breaks a situation up into components

that can be analyzed separately at first, following this by an analysis

of their interaction. Jonathan Schaeffer of the University of Alberta,

(jonathan@cs.ualberta.ca) has written about the role of experiment in

game playing. There are html2 and postscript3 versions.

automatic theorem proving Again the experimental work has shown us

the strengths and weaknesses of various theoretical ideas. Alan Bundy

(bundy@edinburgh.ac.uk) has already finished a draft.

It is Experi-

mental Work in ATP4.

planning Most of the research in planning under uncertainty has a strong

experimental component. Subbarao Kambhampati (rao@asu.edu) has

agreed to write about this.

experiments with NP-complete problems Problems that are NP-completein general are often much easier in the average case. This has been ex-

plored experimentally, and a phase change phenomenon between cases

with many solutions and cases with no solutions has turned up. This

seems to be analogous to phase changes in physics.

2http://www.cs.ualberta.ca/˜jonathan/Papers/expcs.html

3http://www.cs.ualberta.ca/˜jonathan/Papers/expcs.ps

4http://www.dai.ed.ac.uk/staff/personal pages/bundy/mccarthy.ps

REFERENCES

Bart Selman (selman@research.att.com) will write about experimental

study of NP-completeness in AI including phase transitions, search and

reasoning.

Andrew Goldberg (avg@research.nj.nec.com) has written about exper-

imental algorithms. We have html5 and .ps6 versions.

Actually Goldberg and Selman will divide up their topics in a way they

will shortly specify more precisely.

natural language Fernando Pereira (PEREIRA@RESEARCH.ATT.COM)

will write about experimental research in natural language.

vision Tom Binford (binford@cs.stanford.edu) will write about vision.

neural nets Jordan Pollack (pollack@cs.brandeis.edu) will write about neu-

ral nets and evolutionary programming.

connectionism Geoffrey Hinton (hinton@cs.toronto.edu) will write about

connectionism. Hinton dropped out for lack of time, so we need some-

one to write about connectionism.

machine learning Tom Dietterich, TGD@CS.ORST.EDU has written aboutexperimental research in machine learning. We have .html7 and gzipped

postscript8 versions.

References

[Cou95] National Research Council. Academic careers for experimental com-

puter scientists and engineers, 1995.

/@steam.stanford.edu:/u/ftp/jmc/experimental.tex: begun 1996 May 23, latexed 1997 Jun 24 at 5:46 p.m.

5http://www.neci.nj.nec.com/homepages/avg/jmc/alg-perf.html

6http://www.neci.nj.nec.com/homepages/avg/jmc/alg-perf.ps

7http://www.cs.orst.edu/ tgd/experimental-research/index.html

8ftp://ftp.cs.orst.edu/pub/tgd/papers/experimental-research.ps.gz