NBSIR 75-753(^1?)

Programmatic Coverage of Computer

Science Topics Within the Institute

for Computer Sciences and Technology

of the National Bureau of Standards

Joseph 0. Harrison, Jr.

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D. C. 20234

June, 1975

Final Report

U.S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS

NBSIR 75-753

PROGRAMMATIC COVERAGE OF COMPUTER

SCIENCE TOPICS WITHIN THE INSTITUTE

FOR COMPUTER SCIENCES AND TECHNOLOGY

OF THE NATIONAL BUREAU OF STANDARDS

Joseph 0. Harrison, Jr.

Institute for Computer Sciences and Technology

National Bureau of Standards

Washington, D. C. 20234

June, 1975

Final Report

U.S. DEPARTMENT OF COMMERCE, Rogers C.B. Morton, Secretary

John K. Tabor, Under Secretary

Dr. Betsy Ancker-Johnson, Assistant Secretary for Science and Technology

NATIONAL BUREAU OF STANDAPtOS, Ernest Ambler, Acting Director

FOREWORD

The material in this paper is taken from two reports on computer science

in ICST submitted to the Director, ICST, Dr. Ruth M. Davis in April 1975. This

report will serve to make it available to the NBS staff.

In compiling the material a number of prominent members of the academic

community were interviewed regarding their views on a definition of computer

science. In particular, discussions were held with the following persons:

Dr. Bruce Arden

Dr. William F. Atchison

Dr. Richard Austing

Dr. John W. Hamblen

Dr. Donald E. Knuth

Dr. Jack Minker

Dr. Steve Yau

Princeton University and Principal

Investigator of NSF Study to Classify

Computer Science

National Institute of Education Program

for Productivity and Technology

Former Chairman of the ACM Curriculum

Committee That Developed ACM Curriculum

68

University of Maryland and Chairman of

ACM SIGCSE Under Whose Auspices ACM

Curriculum 68 Is Being Revised

University of Missouri

Stanford University

University of Maryland

Head of Computer Sciences Department

Northwestern University

and President IEEE

In addition, the definition of computer science was discussed with the

following persons within ICST:

i
J. Albus

J. Berg

R. Butler

J . Evans

E. Fong

M. Fox

M. Henderson

E. Istvan

S. Jeffery

G. Lindamood

T. Lowe

The definition finally selected is based largely on the subject classification

in ACM Curriculum 68''''""' but in addition reflects the author's discussions with

these persons.

The ICST programmatic coverage table presented in the report was developed

from various NBS program documents. The list of top scientists was compiled

largely from nominations of NBS staff members.

The author gratefully acknowledges the assistance of all of the above

persons.

The author is particularly indebted to Mr. Edwin J. Istvan, Associate

Director for Teleprocessing and Acting Chief, Information Technology Division,

ICST, for reviewing the manuscript of this document and making a number of

helpful suggestions.

T. Pyke

B. Ramsay

R. Saltman

S. Stewart

R. Stillman

Z. Thornton

J. Walkowicz

J. Wegstein

H. White

J. Wood

ii
TABLE OF CONTENTS

PAGE

FOREWORD i

ABSTRACT 1

DEFINITION OF COMPUTER SCIENCE 2

PROGRAMMATIC COVERAGE BY ICST 3

TOP COMPUTER SCIENTISTS 4

REFERENCE 5

APPENDIX 1 - DEFINITIONAL LIST OF TOPICS COMPRISING COMPUTER SCIENCE 6

APPENDIX 2 - TOPICAL DESCRIPTIONS FROM CURRICULUM 68 7

APPENDIX 3 - DESCRIPTIONS OF SUPPLEMENTARY TOPICS 9

APPENDIX 4 - ICST PROGRAMMATIC COVERAGE OF COMPUTER SCIENCE TOPICS 10

APPENDIX 5 - METHODOLOGY FOR DEVELOPMENT OF PROGRAMMATIC COVERAGE TABLE 20

APPENDIX 6 - SOME TOP COMPUTER SCIENTISTS 22

iii

PROGRAMMATIC COVERAGE OF COMPUTER SCIENCE TOPICS WITHIN THE

INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY OF THE

NATIONAL BUREAU OF STANDARDS

ABSTRACT

This paper presents three items of information relative to computer

science at NBS:

(1) it gives a definition of computer science in terms of

topical areas,

(2) it shows by examining past and present ICST project

descriptions which topical areas have been or are

presently covered by ICST programs, and

(3) it presents a list of some of the top computer scientists

in each of the topical areas included in the definition.

1
Definition of Computer Science

The computer science literature abounds with dictionary-like definitions

of computer science, but none of them is precise enough to use as a criterion

for determining whether a specific topic in the general area is or is not

Included. Accordingly, it was decided that for the purpose of this study

computer science would be defined in terms of the list of topics of which

it consists. The specific list adopted as a definition is based on the

subject classification of computer science given in ACM Curriculum 68 and

is presented in Appendix 1 of this report.

Curriculum 68 was published in March 1968 by the ACM Curriculum Committee

on Computer Science after six years of work which Included the sponsoring of

panel discussions and other sessions at various national committee meetings

and the issuing of a preliminary report on undergraduate programs in computer

science in September 1965. The committee spent two years in revising the

recommendations of the preliminary report and in extending them to graduate

programs. Many prominent computer scientists contributed to Curriculum 68.

In addition, to the twelve members of the committee, 64 other persons served

as consultants or presented written comments or otherwise assisted.

The subject classification of Curriculum 68 is widely recognized throughout

the computer community, and is the only such classification used as a basis for

instructional programs in a large number of educational institutions.

On the other hand, there have been changes in computer science in the .

seven years since Curriculum 68 was published, and a number of subjects that

are not Included in Curriculum 68 are now recognized to be important computer

science areas. For this reason, a list of additional computer topics which

2
appear to have scientific content, at least in part, have for the purpose of

this study been appended to the Curriculum 68 list as supplementary computer

science topics.

In the definition (Appendix 1) numbered topics I - V together with their

subtopics are taken from Curriculum 68 without change. Topics SI - S6 are the

supplementary topics which have been added. The descriptions of the topics from

Curriculum 68 are given in Appendix 2, which is reproduced verbatim from

Curriculum 68, and the descriptions of the supplementary topics are given in

Appendix 3.

Programmatic Coverage by ICST

ICST has some activity in virtually all areas of computer science. In many

cases, however, this activity is confined to work of a management, administrative

support or sponsorship nature. Accordingly, a criterion has been adopted for the

use of the term coverage in this study. Specifically, a topic is considered to be

covered only if ICST devoted a "major in-house technical effort" in it. The word

major is construed to mean a minimum of 1/2 man-year. ICST programmatic coverage

of computer science under this criterion is presented in Appendix 4. The appendix

consists of a table giving the coverage by fiscal year of each computer science

topic and a set of notes describing the rational for each entry in the table on

a case-by-case basis. The methodology used in developing the coverage table is

given in Appendix 5

.

In addition, ICST engages in many important activities not included in the

coverage table. They include:

management of NBS and Federal Government computer programs

dissemination of computer related information

compiling computer usage data

3
conducting computer related economic studies

sponsoring seminars in computer related subjects

producing indices of computer programs

studying legal aspects of computer related problems

Top Computer Scientists

A list of some top scientists in each of the computer science areas

included in the definition is presented as Appendix 6. The list is not intended

to be complete, nor do the order of the names on it have any significance.
REFERENCE

1. ACM Curriculum 68 , Communications of the ACM 11, 3 (March 1968).

5
APPENDIX 1

DEFINITIONAL LIST OF TOPICS COMPRISING COMPUTER SCIENCE

COMPUTER SCIENCE

I. INFORMATION STRUCTURES AND PROCESSES

1. Data Structures

2. Programming Languages

3. Models of Computation

II. INFORMATION PROCESSING SYSTEMS

1. Computer Design and Organization

2. Translators and Interpreters

3. Computer and Operating Systems

4. Special Purpose Systems

III. METHODOLOGIES

1. Numerical Mathematics

2. Data Processing and File Management

3. Symbol Manipulation

4. Text Processing

5. Computer Graphics

6. Simulation

7. Information Retrieval

8. Artificial Intelligence

9. Process Control

10. Instructional Systems

S. SUPPLEMENTARY AREAS

1. Computer Security

2. Performance Measurement and Evaluation

3. Computer Networking

4. Data Communications

5. Software Engineering

6. Analysis of Algorithms

. RELATED AREAS

IV. MATHEMATICAL SCIENCES

V. PHYSICAL AND ENGINEERING SCIENCES

* Numbered topics I, II, III, IV and V together with their subtopics are taken from

Curriculum 68 without change. Topics SI - S6 are supplementary topics which have

been added for the purpose of this study.

6
APPENDIX 2

TOPICAL DESCRIPTIONS FROM CURRICULUM 68

The scope of academic programs and curricula in computer science will necessarily vary from institu- tion to institution as dictated by local needs, resources, and objectives. To provide a basis for discussion, however, it seems desirable to have a reasonably comprehensive system for classifying the subject areas within

computer science and related fields. Although any such

system is somewhat arbitrary, it is hoped that any

substantial aspect of the computer field, unless specifically excluded for stated reasons, may be found

within the system presented here. The subject areas within computer science will be classified first; those

shared with or wholly within related fields will be

discussed later in this section.

Computer Science. The subject areas of computer

science are grouped into three major divisions: "information structures and processes," "information proc- essing systems,'.' and "methodologies." The subject areas contained in each of these divisions are given

below together with lists of the topics with-n each

subject area.

I. INFORMATION STRUCTURES AND PROCESSES

This subject division is concerned with representations and

transformations of information structures and with theoretical models for such representations and transformations.

1. Data Structures: includes the description, representation, and

manipulation of numbers, arrays, lists, trees, files, etc.: storage or- ganization, allocation, and access; enumeration, searching and sorting; generation, modification, transformation, and deletion tech- niques; the static and dynamic properties of structures; algorithms

for the manipulation of sets, graphs, and other combinatoric structures.

2. Programming Languages: includes the representation of also- rithms; the syntactic and semantic specification of lansuages: the

analysis of expressions, statements, declarations, control structures, and other features of programming languages; dynamic structures which arise during execution; the design, development and evalu- ation of languages; program efficiency and the simplirtcation of programs; sequential transformations of program structures: special purpose languages; the relation between programming languages, formal languages, and linguistics.

.'i. Models ok Compi;tation: includes the behavioral and structural analysis of switching circuits and sequential machines: the properties and classification of automata; algebraic automata theory and

model theory; formal languages and formal grammars: the classi.n- cation of languages by recognition devices; syntactic analysis: formal

154 Cumniiinicalions of llic ACM 7 Volume 11 / .Number .1 March.
specification of semantics; syntax directed processing; decidability

problems for grammars; the treatment of programming languages as automata; other formal theories of programming languages and computation.

11. INFORMATION PROCESSING SYSTEMS

This subject diuision is concerned with systems having the

ability to transform information. Such systems usually in- volve the interaction of hardware and software.

1. Computer Design and Organization: includes types of computer structure—von Neumann computers, array computers, and

look-ahead computers; hierarchies of memory—flip-Hop registers, cores, disks, drums, tapes—and their accessing techniques; micro- programming and implementation of control functions; arithmetic

circuitry; instruction codes: input-output techniques; multiprocessing and multiprogramming structures.

2. Translators and Interpreters: includes the theory and tech- niques involved in building assemblers, compilers, interpreters, loaders, and editing or conversion routines (media, format, etc.).

3. COMPITTER AND OPERATING SYSTEMS: includes program monitoring

and data management; accounting and utility routines; data and

program libraries; modular organization of systems programs; inter- faces and communication between modules; requirements of multiaccess, multiprogram and multiprocess environments; large scale systems description and documentation; diagnostic and debugging

techniques; measurement of performance.

4. Special Purpose Systems: includes analog and hybrid computers; special terminals for data transmission and display; peripheral and interface units for particular applications; special software

to support these. m. METHODOLOGIES

Methodologies are derived from broad areas of applications

of computing which have common structures, processes, and

techniques.

1. Numerical Mathematics: includes numerical algorithms and their theoretical and computational properties; computational error analysis (for rounding and truncation errors); automatic error estimates and convergence properties.

2. Data Processing and File Management: includes techniques

applicable to library, biomedical, and management information systems; file processing languages.

3. Symbol Manipulation: includes formula operations such as simplification and formal differentiation; symbol manipulation lan- guages.

4. Text Processing: includes text editing, correcting, and justification; the design of concordances; applied linguistic analysis; text processing languages.

5. Computer Graphics: includes digitizing and digital storage; display equipment and generation; picture compression and image enhancement; picture geometry and topologv-; perspective and rotation; picture analysis; graphics languages.

6. Simulation: includes natural and operational models; dis- crete simulation models; continuous change models; simulation lan- guages.

7. Information Retrieval: includes indexing and classification:

statistical techniques; automatic classification: matching and search

strategies; secondary outputs such as abstracts and indexes; selec- tive disseminatiiin systems; automatic question answering systems.

8. Artificial I.ntei,ligence: includes heuristics: brain models: pat- tern recognttio.i; theorem proving: problem solving; game playing;

adaptive and cognitive systems; man-machine systems.

9. Process Co.ntrol: includes machine tool control; experiment

control; command and control systems.

10. Instructional Systems: includes computer aided instruction.

Related Areas. In addition to the areas of computer

science listed under the three divisions above, there

are many related areas of mathematics, statistic.^, electrical engineering, philosophy, linguistics, and in- dustrial engineering or management which are es- sential to balanced computer science programs. Suitable courses in these areas should be developed

cooperatively with the appropriate departments, al- though it may occasionally be desirable to develop some of these courses within the computer science

program.

Since it is not feasible in this report to list all of the

areas which might be related to a computer science

program, let alone indicate where courses in these

areas should be taught, the following listing is some- what restricted. It is grouped into two major diWsions:

"mathematical sciences" and "physical and engineering sciences."

rV. MATHEMATICAL SCIENCES

1. Elementary Analysis

2. Linear Algebra

3. Differential Equations

4. Algebraic Structures

5. Theoretical Numerical Analysis

6. Methods of Applied Mathematics

7. Optimization Theory

8. Combinatorial Mathematics

9. Mathematical Logic

10. Number Theory

11. Probability and Statistics

12. Operations Analysis

V. PHYSICAL AND ENGINEERING SCIENCES

1. General Physics

2. Basic Electronics

3. Circuit Analysis and Design

4. Thermodynamics and Statistical Mechanics

5. Field Theory

6. Digital and Pulse Circuits

7. Coding and Information Theory

8. Communication and Control Theory

9. Quantum Mechanics

No attempt has been made to include within this classification system all the subject areas which make

use of computer techniques, such as chemistry and

economics; indeed, to list these would require inclusion of a major portion of the typical university catalog. Furthermore, the sociological, economic, and educational implications of developments in computer

science are not discus.sed in this report. These issues are undoubtedly important, but they are not the ex- clusive nor even the major responsibility of computer

science. Indeed, other departments such as philosophy

and sociology should be urged to cooperate with computer scientists in the development of courses or seminars covering these topics, and computer science

students should be encouraged to take these courses.

Volume 11 / Niiinhcr :i / .Murch. 1968 8

Comiitunicalions of tlic ACM 155
APPENDIX 3

DESCRIPTIONS OF SUPPLEMENTARY TOPICS

1. COMPUTER SECURITY: Refers to the technological safeguards and managerial

procedures which can be applied to computer hardware, programs and data to assure that organizational assets and individual privacy are protected.

2. PERFORMANCE MEASUREMENT AND EVALUATION: A technology for improving the

efficiency of computer systems and facilities. It is most often defined as the application of accounting systems, hardware monitors, software monitors,

benchmarks, resource drivers, simulators and various other tools to the

information gathering process that enables the ADP management to make rational

choices between the practical alternatives that confront him through the life

cycle of a computer system.

3. COMPUTER NETWORKING: The interconnection of two or more computers and/or terminals

by means of data communications links; includes hardware, software, rules and

policies to permit operation and interaction of network components.

4. DATA COMMUNICATIONS: Electronic transmission of digitally encoded data; includes

encoding, decoding, modulation, demodulation, multiplexing, formats, procedures,

protocols, reliability, checking and correction.

5. SOFTWARE ENGINKKRINO: Includes program quality, modular and top-down design,

structured prograiraning , proofs of correctness, testing and checkout.

6. ANALYSIS OF ALGORITHMS: Includes the study of time and space requirements for

algorithms, efficient algorithms, trade-off characteristics, proofs of correctness, and testing.

9
APPENDIX 4

ICST PROGRAMMATIC COVERAGE OF COMPUTER SCIENCE TOPICS

TOPIC FISCAL YEAR

COMPUTER SCIENCE

I. INFORMATION STRUCTURES AND PROCESSES

1. Data Structures

2. Programming Languages

3. Models of Computation

II. INFORMATION PROCESSING SYSTEMS

1. Computer Design and Organization

2. Translators and Interpreters

3. Computer and Operating Systems

4. Special Purpose Systems

III. METHODOLOGIES

1. Numerical Mathematics

2. Data Processing and File Management

3. Symbol Manipulation

4. Text Processing

5. Computer Graphics

6. Simulation

7. Information Retrieval

8. Artificial Intelligence

9. Process Control

10. Instructional Systems

S. SUPPLEMENTARY AREAS

1. Computer Security

2. Performance Measurement and Evaluation

3. Computer Networking

4. Data Communications

5. Software Engineering

6. Analysis of Algorithms

RELATED AREAS

IV. MATHEMATICAL SCIENCES

V. PHYSICAL AND ENGINEERING SCIENCES

70 71 72 73 74 75

XXX XXX

XXX

X X

X

X

X

X X X X

X X X X X

X X

X X

X X

X

X X

X X

X X X X X

X X X X

X X X X X

X X

10
NOTES ON TABLE OF ICST PROGRAMMATIC COVERAGE OF COMPUTER SCIENCE TOPICS

I. 1. Data Structures

Except for a brief excursion in FY 70, 71, this subject was recognized

explicitly in the ICST Program for the first time in FY 74 with the introduction

of a cost center to support the data descriptive language committee of CODASYL,

and in FY 75 in addition by a study of the properties of data bases independent

of particular hardware or software. These cost centers together amount to about

1/2 man year of effort and are considered to be marginally suitable for inclusion

in the ICST coverage table for FY 75. The development of data elements and their

coded representations, upon which ICST has done much work, is not included under

this topic since it is not in general concerned with the structural properties of

data nor are the technical aspects of data elements and codes carried out in-house.

I. 2. Programming Languages

This topic has received a high level of coverage in the ICST Program since

FY 70. The bulk of the effort has been on the development and standardization of

FORTRAN and COBOL although other languages have also been included from time to

time (ALGOL, BASIC and special purpose languages), and other language oriented

activities, such as the development of static and dynamic analyzers have been

undertaken. Most of the work has been on the applied level with little or no

effort expended on that portion of the topic concerned with the relation between

programming languages, formal languages and linguistics.

I. 3. Models of Computation

This subject has received no formal recognition in the ICST Program.

11
II. 1. Computer Design and Organization

Although NBS ' original entry into the computer field was based on expertise

in this area, there has been little attention paid to it during the span of time

covered by this report. Work on peripheral interface standards has been in the

program since 1970; however, this work has not generally involved broad studies of

computer design and organization, although it might have. Also, a study of manmachine organization was conducted in 1970-71, and some work on advanced system

functions is currently underway in the Computer Services Division. In addition,

much of the current work on computer networking might be considered to fall in this

area. The fact remains, however, that there is not now, and there has not since

FY 70 been any comprehensive work in computer design and organization as such.

Therefore, the topic is not included in the coverage table.

II. 2. Translators and Interpreters

Some work on compilers has been done over the years in conjunction with the

standardization of programming languages. This includes, work on both FORTRAN and

COBOL compiler validation routines. The FORTRAN compiler validation routines were

successfully completed in 1974 as an NBS in-house technical effort. The COBOL

compiler validation routines were completed several years earlier but not as an

NBS in-house technical effort. Also, some of the systems programming work in the

Computer Services Division and much of ICST's ADP standards work supports that

part of the topic concerned with media, code and format conversion routines.

The topic is considered to be qualified for inclusion in the coverage table.

II. 3. Computer and Operating Systems

This area includes a miscellany of diverse topics, but ICST has had most of

them covered, particularly since 1972. The Computer Services Division has maintained

12
a hands-on technical capability covering program monitoring for both batch and

time sharing systems, data base management and utility routines. In addition, the

Systems and Software Division has work completed and underway in program testing

aids, documentation and software quality, and the Computer Systems Engineering

Division has worked and is working with operating systems for experimental

computers. Work on the magnetic tape label - standard and source data automation

might also be considered to fall within this area. This area also includes

certain types of utility routines, particularly those involved in the conversion

of character codes and the transferability of data. This sub-area has been

emphasized in the Computer Services Division systems programming effort, and has

been the subject of many standardization studies. The area is considered to be

qualified for inclusion in the coverage table.

II. 4. Special Purpose Systems

Although there has been essentially no work on analog and hybrid computers,

the coverage of special terminals for data transmission and display, peripheral

and interface units for particular applications and special software to support them

has been extensive since FY 70. Examples include the entire output of the Office

of Automation and Control Technology, and many other agency problems such as the

IRS Remittance Processing System in the Computer Systems Engineering Division,

and AUTOCAL in the Systems and Software Division. The area is considered to be

qualified for inclusion in the coverage table.

III. 1. Numerical Mathematics

There has been little work in this area in ICST, but considerable in the

NBS Applied Mathematics Division which is not a part of ICST. Recently, a cost

center has been set up to cover computer related numerical mathematics in

addition to other topics, but the level is still below the threshold of the

coverage chart.

13
III. 2. Data Processing and File Management

ICST has a long history of practical experience in setting up and employing

computerized files both for other agencies and for carrying out its own mission.

In addition, there have been many theoretical studies of file management. The area

is considered to be covered.

III. 3. Symbol Manipulation

Considerable work in this area was undertaken before the beginning of the

period of this report. It centered mostly around the analysis of Chinese characters

and chemical diagrams and tapered off around 1971. The topic is considered to be

covered through fiscal year 71 only.

III. 4. Text Processing

This area consists of two rather distinct sub-areas. The first, linguistics,

treats the syntactic and semantic aspects of language and was a subject of inquiry

in ICST before the period of this report. Work in this sub-area tapered off in 1969.

It was in part related to the Chinese character studies. The second, text editing,

including correcting and justification, treats the mechanical aspects of text

processing. This latter sub-area was actively pursued in ICST until 1974. Many

of the outstanding problems in it have already been solved and considerable

practical use is being made of computerized composition and type setting. The

area is considered to have been covered in FY 73, 74.

III. 5. Computer Graphics

This subject has received coverage in the ICST Program over the entire period,

much of it under the classification of Computer Aided Design. A large portion of

the work was, and still is sponsored by the Army. This topic includes display

equipment, and another aspect of ICST work is the standardization of display format

functions and symbols.

14
III. 6. Simulation

There was considerable activity in simulation before the period of this

report. It consisted of simulation as a fundamental methodology and of several

applications to the simulation of communications nets. The only activity in

simulation included in the ICST Program between FY 70 and FY 75 has been the

simulation of one computer system by another which is considered to be a technique

of computer system performance measurement. Activity in this area is considered

to be below the threshold required for inclusion on the coverage chart.

III. 7. Information Retrieval

ICST has had practical experience in information retrieval over many years

through the activities of the Computer Information Section of the Information

Technology Division and its predecessors. In addition, there were NSF sponsored

studies in information retrieval related to chemical information. A study on

selective associative recall was in the program in FY 70, 71 and computer assisted

indexing in FY 73. There appears to have been no theoretical work in information

retrieval since that time. The topic is considered to be covered through FY 73.

III. 8. Artificial Intelligence

The subject of automated fingerprint classification sponsored by the FBI

began in 1968 and has continued uninterrupted since that time. This subject is

concerned for the most part with visual pattern recognition. Other aspects of

artificial intelligence (heuristics, cognitive systems, man-machine systems) are

beginning to be studied seriously in the automation technology program. Other

aspects of artificial intelligence such as game playing, theorem proving, problem

solving and brain models are not now and never have been in the ICST Program. The

15
extensive ICST work in standardizing OCR fonts is not considered as artificial

intelligence. Artificial intelligence is considered to marginally qualify for

inclusion on the ICST coverage chart since the initiation of the fingerprint

classification work, and to fully qualify with the initiation of the automation

technology work in addition, in 1974.

III. 9. Process Control

The only continuing identifiable work in process control is that associated

with NBS laboratory automation. This has gone on intermittently over the years.

There has been no work in machine tool control other than the standardization of the

APT Programming Language and a brief inquiry into methods for converting machine

tool programs from the U. S. Customary to the metric system of measurement. Nor

has there been work in command control systems in recent years. The coverage of

this topic is considered to be below the threshold for inclusion in the ICST coverage

chart.

III. 10. Instructional Systems

There has been no identifiable work in this area in the ICST Program.

S. 1. Computer Security

Work in this area began in FY 72 with a controlled accessibility study. It

was expanded to a high level in FY 74 and 75. The topic is considered to be covered

in FY 74, 75.

S. 2. Performance Measurement and Evaluation

Although it was mentioned in the ICST Program before that time, work on

performance measurement and evaluation began seriously in FY 71 and was expanded

to a high level in FY 73, 74, 75. It is considered to have been covered from

FY 71 cn.

16
S. 3. Computer Networking

There has been some work on remote computing and ADP time sharing since

before the period of this report. However, large scale work in computer networking

started with the dialog monitor, ARPA network participation, teleprocessing support

facilities and other studies in FY 72. The topic is considered to have been covered

since that time.

S. 4. Data Communications

Unlike some of the other standards efforts, data communications standards

have been pursued vigorously and in considerable technical depth from the beginning

of the period. In addition, there have been many other agency studies involving

terminal to computer and terminal to terminal data links. The effort in data

communications was emphasized further in 19 72 by the emphasis on computer networking

studies. The topic is considered to have been covered throughout the entire period

of this report.

S. 5. Software Engineering

This area was recognized as a separate topic in the ICST Program only in

the last two years. However, it is now emphasized and is considered to qualify

for coverage in FY 74, 75.

S. 6. Analysis of Algorithms

There has been no work on the analysis of algorithms identified as such

in the ICST Program.

IV. Mathematical Sciences

This area is not covered by ICST for the same reason that Numerical

Mathematics, area III. 1., is not covered — namely that the bulk of the work in this

area at NBS is in the Applied Mathematics Division.

17
V. Physical and Engineering Sciences

This area is so broad that no organization the size of ICST could do it

justice. However, considerable work has been done in the computer related physical

sciences. Projects that fall into this category include magnetic tapes, cassettes

and disks; experimental OCR devices, some of them for the Post Office Department;

optical character font evaluation; fingerprint readers, and much of the work of the

Office of Automation Technology.

18
APPENDIX 5

METHODOLOGY FOR DEVELOPMENT OF PROGRAMMATIC COVERAGE TABLE

For the past 6 fiscal years, FY 70 - 75, ICST has had approximately 100

cost centers each year. For all practical purposes cost centers had to be

treated as independent projects since records are kept not by project but by

cost center. The following information on cost centers was available for the

study:

(a) A list of the numbers, titles, and in some cases the sponsors, of

each cost center for each fiscal year, FY 70 - 75.

(b) NBS-228 project reports for each cost center, almost complete for

FY 73, 74, 75 and partially complete for FY 72.

(c) Quarterly project reports for most cost centers for FY 72, 73, 74, 75.

The problem was to derive from this data a historical record of the ICST coverage

of computer science topics by fiscal year from FY 70 through FY 75.

The numbers and titles only of cost centers for the FY 66 - FY 69 period

were also available. This information was not analyzed as was the data for the

FY 70 - FY 75 period but it is referred to several times for historical perspective in the notes to the coverage table in Appendix 4.

The following procedure was employed:

(a) Cost centers for fiscal years 70 - 75 were listed on a single multipage

work sheet in numerical order. For each cost center, the title and the

fiscal years in which it was active were listed. This resulted in a

table of 312 line items reduced from about 600 (approximately 100 cost

centers per year for each of 6 years) since the average duration of

a cost center is slightly less than 2 fiscal years.

(b) The topics of computer science were then superposed on the work sheet

as columns.

19
(c) Each cost center was then examined in turn by title and a judgment

made as to which of the topics of computer science, if any, it related

to. Checks were made in the appropriate columns of the work sheet.

In connection with this judgment, the NBS-228's, where available,

and frequently the quarterly progress reports as well, were examined.

(d) The work sheet was then inverted so as to make computer science topic

the primary entry, and to list under each computer science topic the

cost centers associated with it, together with the fiscal years in

which they were active.

(e) For each computer science topic a judgment was then made as to whether

the work done under the cost centers associated with it qualified it

by fiscal year for coverage under the "major in-house technical

effort" criterion. If so an appropriate mark was put on the

ICST coverage chart in Appendix 4. The NBS-228's and the quarterly

progress reports, where available, were consulted extensively in

connection with this process, but even so it is recognized to be

quite subjective.

20
APPENDIX 6

SOME TOP COMPUTER

Name

I. INFORMATION STRUCTURES AND PROCESSES

1. Data Structures

Charles W. Bachman

James P. Fry

Calvin C. Gotlieb

Malcomb C. Harrison

Donald E. Knuth

Jim Luching

Jean Sammet

M. E. Senko

Edgar H. Sibley

Robert E. Tarj an Robert W. Taylor

2. Programming Languages

John W. Backus

Victor R. Basili

F. L. Bauer

Edgar W. Dijkstra

Robert W. Floyd

Ivan Flores

Susan L. Graham

David J. Gries

Kenneth E. Iverson

C. H. Lindsey

Dan McCracken

Peter Naur

Alan J. Perils

Terrence W. Pratt

Val W. Pratt

John Reynolds

Jeffry D. Ullman

Joseph Wegstein

A. Van Wijngaarden

Niklaus E. Wirth

William A. Wulf

SCIENTISTS

Affiliation

Honeywell

University of Michigan

University of Toronto

New York University, Courant Institute

Stanford University

ICL, UK

IBM, Cambridge

IBM Research Labs, Palo Alto

University of Maryland

Cornell University

University of Michigan

IBM

University of Maryland

Munich

Burroughs in Holland

Stanford University

New York

University of California, Berkeley

Cornell University

IBM

Manchester University (ALGOL) UK

Consultant

Denmark (ALGOL)

Yale University

University of Texas

University Western Ontario

Harvard University

Princeton University

ICST

Holland

Zurich, Switzerland

Carnegie Mellon University

21
3. Models of Computation

Alfred V. Aho

Robert Ashenhurst

Taylor L. Booth

Patrick C. Fischer

Symour Ginsburg

Shelia Greibach

Michael A. Harrison

John E. Hopcroft

Richard M. Karp

E. D. Ritchie

Jeffry D. Ullman

INFORMATION PROCESSING SYSTEMS

Computer Design and Organization

Gene M. Amdahl

Robert Barton

C. G. Bell

Frederick P. Brooks, Jr.

Yaohan Chu

Seymour Cray

Gerald Estrin

Michael J. Flynn

Harry Huskey

David Kuch

E. J. McClusky

Allen Newell

Chittoor Ramamoorthy

Saul Rosen

Robert F. Rosin

Bell Laboratories

University of Chicago

University of Connecticut

Penn State University

University of Southern California

UCLA

University of California, Berkeley

Cornell University

University of California, Berkeley

Washington State University

Princeton University

System 360

Burroughs

Carnegie Mellon University

University of North Carolina

University of Maryland

Cray Associates

UCLA

Stanford University

University of California, Santa Cruz

University of Illinois

Stanford University

Carnegie Mellon University

University of California, Berkeley

SUNY, Buffalo

New York State University

2. Translators and Interpreters

Alfred V. Aho

Thomas E. Cheatham, Jr.

Robert W. Floyd

David J. Cries

John McCarthy

William McKeenan

Roy Nutt

Elliott I. Organick

Jeffry D. Ullman

Bell Labs

Harvard University

Stanford University

Cornell University

Stanford University

University of California, Irvine

Computer Sciences Corporation

University of Utah

Princeton University

22
3. Computer and Operating Systems

Bruce Arden

Thomas E. Cheatham, Jr.

Yaohan Chu

Edward G. Coffman, Jr.

Fernando J. Corbato

Peter J. Denning

Edgar W. Dijkstra

David J. Farber

Samuel H. Fuller

Bernard A. Caller

Durbridge Hansen

Leonard Kleinrock

Butler Lampson

Elliot I. Organick

Dave Parnas

Alan J. Perils

Tad Pinkerton

Saul Rosen

Harold Stone

Peter Wegner

William A. Wulf

Princeton University

Harvard University

University of Maryland

Penn State

MIT (MULTICS)

Pennington, NJ

Burroughs in Holland

University of California, Irvine

Carnegie Mellon University

University of Michigan

UCLA Denmark

LA, California

Xerox

University of Utah

University of Pittsburgh

Yale University

University of Wisconsin

Purdue University

University of Massachusetts

Brown University

Carnegie Mellon University

Special Purpose Systems

Robert B. Collender

Henry Hoffman

G. A. Korn

Carl Machover

Nils Nilsson

Alfred Pletz, Jr.

Stephen P. Robinson

Lockheed (Displays)

Goddard Space Flight Center

(Analog Computers)

Analog Computers

Information Displays, Inc. (Displays)

SRI (Analogue Computers)

Kaiser Aerospace (Displays)

Teledyne Camera Systems (TV Displays)

III. METHODOLOGIES

1. Numerical Mathematics

Samuel D. Conte

Gene H. Golub

Saul Corn

Richard W. Hamming

Alston S. Householder

Thomas E. Hull

Velvel Kahan

Cleve B. Moler

James M. Ortega

Anthony Ralston

Werner C. Rheinboldt

John R. Rice

Purdue University

Stanford University

University of Pennsylvania

Bell Labs

University of Tennessee

University of Toronto

University of California, Berkeley

New Mexico University

University of California, La Jolla

SITNY, Buffalo

University of Maryland

Purdue University

23
Joseph F. Traub

James S. Vandergraft

J. H. Wilkinson

David M. Young, Jr.

Carnegie Mellon University

University of Maryland

UK, National Physical Laboratories

University of Texas

2. Data Processing and File Management

Charles W. Bachman

Alfonso F. Cardenas

Vincent Y. Lum

Charles T. Meadow

Jack Minker

Ivan B. Schneiderman

Daniel Teichroew

Honeywell

UCLA

IBM, San Jose

AEC

University of Maryland

London, England

University of Michigan

Symbol Manipulation

Daniel G. Bobrow

Terry J. Frederick

W. M. Gentleman

John B. Goodenough

John McCarthy

Anthony Ralston

Jean E. Sammet

Bolt, Beranek & Newman

Purdue University (PLANIT)

University of Waterloo

Boston

Stanford University (LISP)

SUNY, Buffalo

IBM, Cambridge

4. Text Processing

T. Bar-Hillel

Harold Borko

Blanton C. Duncan

D. C. Engelbart

Charles Irby

Calvin Mooers

David E. Rice

Gerald A. Salton

Ralph W. Swanson

Andries Van Dam

Israel

UCLA

Washington, D. C.

SRI

SRI

Cambridge, Massachusetts (TRAC)

Brown University

Cornell University

University of Chicago

Brown University

24
Computer Graphics

Stephen Coons

George Dodd

J. Encarnacao

I . K. Giloi

Thomas S . Huang

Lawrence G. Roberts

Ivan E. Sutherland

Andries Van Dam

Syracuse University

GM Research Institute

Saar University

Saar University

MIT

formerly ARPA

University of Utah

Brown University

Simulation

0. J. Dahl

Geoffrey Gordon

Philip J. Kiviat

M. H. MacDougall

Harry M. Markowitz

Thomas H.- Naylor

K. Nygaard

Thomas J. Schriber

K. D. Tocher

Oslo, Norway (SIMULA)

IBM, New York

FEDSIM

Control Data

SIMSCRIPT

Duke University

Oslo, Norway (SIMULA)

University of Michigan (GPSS)

Princeton University

Information Retrieval

Harold Borko

Michael E. Lesk

Jack Minker

Noah Pr3rwes

Geral-i A. Salton

Vladimir Slamecka

Marshall C. Yovits

UCLA

Bell Labs

University of Maryland

University of Pennsylvania

Cornell University

Georgia Tech

Ohio State University

25
8. Artificial Intelligence

Daniel G. Babrow

Thomas Binford

Woodrow W. Bledsoe

Richard 0. Duda

Edward A. Feigenbaum

Jerome A. Feldman

Cordell Green

Russell A. Kirsch

Ralph L. London

Jack Minker

Marvin Minsky

John McCarthy

Allen Newell

Nils J. Nilsson

Seymour A. Papert

Bertram Raphael

J. Allen Robinson

Herbert A. Simon

Terry Winograd

Arthur Samual

Joseph Wegstein

Xerox

Stanford University

University of Texas

SRI

Stanford University

University of Rochester

Cornell University

NBS

Stanford University

University of Maryland

MIT

Stanford University

University of Pittsburgh

SRI

MIT

SRI

Syracuse University

Carnegie Mellon University

MIT

Stanford University

ICST

9. Process Control

K. J. Astroa

M. Athans

Ruth M. Davis

I. D. Landau

Jack C. Lozier

A. Nomoto

Jules I. Schwartz

Cecil L. Smith

Theodor J. Williams

Lund Inst, Sweden (Automatic Control)

MIT

ICST, Command Control Systems

Goenoble Polytech, France

IFAC

Tokyo, Automatic Control

Computer Sciences Corporation

Command Control Systems

Louisiana State University

Purdue University

26
10. Instructional Systems

Donald Bitzer

C. Victor Bunderson

Adele J. Goldberg

Seymour A. Papert

Karl L. Zinn

University of Illinois (PLATO)

Brigham Young University (TICCIT)

Stanford University

MIT

University of Michigan

S. SUPPLEMENTARY AREAS

Computer Security

Robert P. Abbott

J. P. Anderson

Peter S. Browne

Robert H. Courtney,

Daniel J. Edwards

Hilda C. Faust

Lance J. Hoffman

Robert V. Jacobson

Arthur J. Levenson

Steven B. Lipner

Jerry Loebel

Eldred C. Nelson

Donn B. Parker

Roger R. Schell

Richard Seymour

Gerald E. Short

Walter L. Tuchman

Rein Turn

Stephen T. Walker

Willis Ware

Clark Weissman

Jr,

Lawrence Livermore Laboratories

J. P. Anderson Company

General Electric Company

International Business Machines

National Security Agency

National Security Agency

University of California, Berkeley

Chemical Bank of New York

National Security Agency

MITRE Corporation

Honeywell Information Systems

TRW, Inc.

Stanford Research Institute

United States Air Force

International Business Machines

TRW, Inc.

International Business Machines

RAND Corporation

Advanced Research Projects Agency

RAND Corporation

System Development Corporation

2. Performance Measurement and Evaluati

Thomas Bell

James Brown

Gary Carlson

M. E. Drummond

Stephen Kimbleton

Kenneth Kolence

H. C. Lucas

Dudley Warner

6. Analysis of Algorithms

Alfred V. Aho

John E. Hopcroft

Donald E. Knuth

TRW, Inc.

University of Texas

Brigham Young University

International Business Machines

University of Southern California

Palo Alto, California

Stanford University

Los Gatos, California

Bell Laboratories

Cornell University

Stanford University

27

USCOMM-NBS-DC
NBS-114A (REV. 7-73)

U.S. DEPT. OF COMM. BIBLIOGRAPHIC DATA

SHEET

1. PUBLICATION OR REPORT NO. NBSIR 75-7532. Gov't Accession

No.

3. Recipient's Accession No.

4. TITLE AND SUBTITLE

pRQGRAMMATIC COVERAGE OF COMPUTER SCIENCE

TOPICS WITHIN THE INSTITUTE FOR COMPUTER SCIENCES AND TECHNOLOGY

OF THE NATIONAL BUREAU OF STANDARDS

5. Publication Date Tnno 1 one

6. Performing Organization Code

7. AUTHOR(S)

Joseph 0. Harrison, Jr.

8. Performing Organ. Report No.

9. PERFORMING ORGANIZATION NAME AND ADDRESS

NATIONAL BUREAU OF STANDARDS

DEPARTMENT OF COMMERCE

WASHINGTON, D.C. 20234

10. Project/Task/Work Unit No.

11. Contract/Grant No.

12. Sponsoring Organization Name and Complete Address (Street, City, State, ZIP)

Same

13. Type of Report & Period Covered

Final

14. Sponsoring Agency Code

15. SUPPLEMENTARY NOTES

16. ABSTRACT (A 200-word or less factual summary of most significant information. If document includes a significant

bibliography or literature survey, mention it here.)

This paper presents three items of information relative to computer science

at NBS:

(1) it gives a definition of computer science in terms of topical areas,

(2) it shows by examining past and present ICST project descriptions which

topical areas have been or are presently covered by ICST programs, and

(3) it presents a list of some of the top computer scientists in each of

the topical areas included in the definition.

17. KEY WORDS (six to twelve entries; alphabetical order; capitalize only the first letter of the first key word unless a proper name; separated by semicolons) Computer Science; Curriculum 68; ICST program; information

structures and processes; information processing systems; information processing

methodologies

18. AVAILABILITY |

' Unlimited 19. SECURITY CLASS

(THIS REPORT)

21. NO. OF PAGES

Ix For Official Distribution. Do Not Release to NTIS

UNCL ASSIFIED

1

' Order From Sup. of Doc, U.S. Government Printing

Washington. D.C. 20402. SD Cat. No. C13

Office 20. SECURITY CLASS

(THIS PAGE)

22. Price

1 ! Order From National Technical Information Service

Springfield, Virginia 22151 (NTIS)

UNCLASSIFIED

USCOMM-DC 29042-P74