Search

Some of the major results of future goals of an automatic program synthesis project are described in the two papers that comprise this document. The first paper gives a detailed algorithm for synthesizing a computer program from a trace of its behavior. Since the algorithm involves a search, the length of time required to do the synthesis of nontrivial programs can be quite large. Techniques are given for preprocessing the trace information to reduce enumeration, for pruning the search using a failure memory technique, and for utilizing multiple traces to the best advantage. The results of numerous tests are given to demonstrate the value of the techniques. The other paper gives a brief overview of the automatic programming system within which the above algorithm is being used. This system is still under development. (Author/CH)

A review is presented of the role of algorithms in learning and instruction. The paper first describes an algorithm as a procedure guaranteed to produce a correct result and lists its features as: 1) having a reasonably finite number of unambiguously defined operations; 2) having zero or more inputs from a specified domain; 3) having outputs with a relationship to the inputs; and 4) having operations sufficiently simple to be completed in a finite period. The second section reviews the use of algorithms to describe cognitive processes in learning and problem-solving; and the third, their use in developing instructional strategies. The fourth part of the paper examines the use of algorithms in task analysis; and the following section, their application to instructional materials. The concluding segment discusses research issues related to the use of algorithms in learning and instruction, including the order in which the operations of and paths through algorithms are best taught, the demonstration of the interrelationships among an algorithm's components, and methods of teaching students to synthesize the steps of an algorithm, including the retrogression approach. (Author/PB)

Procedures for grouping students into homogeneous subsets have long interested educational researchers. The research reported in this paper is an investigation of a set of objective grouping procedures based on multivariate analysis considerations. Four multivariate functions that might serve as criteria for adequate grouping are given and discussed; a method for optimizing these functions is also described. The set of procedures is illustrated through application to data from two samples of students, each student with scores on either ten or eleven subtests of a criterion referenced mathematics inventory. The results indicate that the procedures discussed provide a promising means for grouping students to minimize classroom heterogeneity. (Author)

Two papers are included as Part Four of this report on Salton's Magical Automatic Retriever of Texts (SMART) project report. The first paper: "A Controlled Single Pass Classification Algorithm with Application to Multilevel Clustering" by D. B. Johnson and J. M. Laferente presents a single pass clustering method which compares favorably with more expensive clustering algorithms. The method is tested using the ADI collection of 82 documents and the Cranfield 424 Collection. The results are compared to full search and to results obtained by searching clusters produced by Dattola's algorithm. The second paper: "A Systematic Study of Query-Clustering Techniques: A Progress Report" by S. Worona describes an experiment using various techniques of query clustering on the Cranfield 424 document collection and gives some preliminary results. Several methods of evaluating the performance of clustered searches in the context of query-clustering are discussed. Some observations are also made concerning use of the SMART system as implemented at Cornell University. (For the entire SMART project report see LI 002 719, for parts 1-3 see LI 002 720 through LI 002 722, for part 5 see LI 002 724.) (NH)

In order to mechanize the processing of natural language, the linguist must make the machine interpret the meaning, or semantic content of the language, in some way or other. This means that the machine should extract not only syntactic but also semantic information from the source sentence through the analysis of it. In this paper, the authors describe their opinions as to the structure of language from the viewpoint of mechanical processing. Then two methods of introducing semantic information into the analysis process are proposed, followed by a brief description of the authors' method of English sentence analysis. Finally, reference is made to the system of machine translation. An example of Japanese sentence analysis is appended. (Author/FWB)

Very little material exists for utilizing the computer in the physics classroom, and even that little is not widely known. It is hoped that this monograph will provide some stimulus both to innovation and to discussion of the role of the computer in physics education. The paper describes how this might be achieved with a detailed account of one week of instruction in the physics of the harmonic oscillator, without calculus, for either physics or non-physics majors. The course is organized into three lectures, Days One to Three, and a Laboratory Session. Day One develops the basic first-order numerical integration scheme for computing velocity and position from a knowledge of acceleration and initial conditions. Day Two discusses the nature and languages of computers, and the construction of algorithms for computation, and Day Three is available in four different versions, one for each of the well-known computer languages-- BASIC, FORTRAN, JOSS, and PL-1. A Student Manual and a Teacher's Guide are included in this paper. (GO)

An operations research method to optimize the teaching-learning process is introduced in this paper. In particular, a linear programing model is proposed which, unlike dynamic or control theory models, allows the computer to react to the responses of a learner in seconds or less. To satisfy the assumptions of linearity, the seemingly complicated non-linear teaching-learning process is converted into a neat linear form. A theorem is proposed and proven which provides the theoretical basis for treating the teaching-learning process as a piece-wise linear form. By taking probability of success as a negative cost coefficient, a mathematical programing model is proposed for the local optimizations which lead to the global optimization when the theorem is applied. Through this Stage Increment Model, sound and scientific optimization of the teaching-learning process for the individual becomes a reality. (Author/MF)

This study of linguistic change is done within the "dynamic paradigm" of linguistic description, in which the strict dichotomy between diachronic and synchronic linguistics found in "static paradigms" is not maintained. The chief purpose here is to indicate how rate could be built into a linguistic description of sound change, such change being here considered as "represented in the wave-like spread of a given rule as it is borrowed from speaker to speaker." Two principal alterations to which a rule is subject in the process of spreading are considered: (1) it may become more general, i.e., simpler, increased generality resulting from the loss of environmental specifications for the operations of the rule; the fact that the rule operates in one environment earlier than in others can be viewed as a difference in the relative rate of the rule with respect to the different environments: 2) reweighting, where changes in the weight of features (in terms of markedness) influence rate of change. The first part of this paper presents the principles on which the study is based, formalizes the notion of rate, and presents evidence for reweighting. The second part considers linguistic and sociolinguistic algorithms for sound change. The final section deals briefly with the effects of overlapping waves of change from different origins. [Not available in hard copy due to marginal legibility of original.] (FWB)

298 EDUCATIONAL AND PSYCHOLOGICAL RESEARCH PAPERS PUBLISHED IN 5 JOURNALS DURING 1966-67 WERE CLASSIFIED ON THE BASIS OF SPONSORSHIP, AUTHORS' GENERAL INTENTIONS, DESIGN, ASSUMPTIONS, AND ANALYSIS. ADVANCES IN STATISTICAL THEORY (INCLUDING WORK ON GENERAL ANALYSIS OF VARIANCE DESIGNS, HYPOTHESIS TESTING IN FACTOR ANALYSIS, MULTIVARIATE ANALYSIS, FACTOR ANALYSIS, AND NON-METRIC DATA ANALYSIS) ARE DISCUSSED. BECAUSE OF THE RECENT PROLIFERATION OF STATISTICAL METHODOLOGY, RESEARCH IS SUGGESTED ON WHETHER DIFFERENT METHODS LEAD TO SUBSTANTIALLY DIFFERENT INTERPRETATIONS OF DATA, AND WHETHER ALGORITHMS ARE COMPUTED DIFFERENTLY WHEN MACHINES AND PROGRAMS OF DIFFERENT DESIGNS ARE EMPLOYED. IN GENERAL, INCREASED USE OF MULTIVARIATE METHODS IS RECOMMENDED. PAPER READ AT 1967 RESEARCH CONVOCATION OF THE EDUC. RES. ASSOC. OF N.Y. STATE (ALBANY, NOV. 1967). (AF)

Local increases in fundamental frequency (Fo) and large integrals of energy in the syllabic nucleus are known to be among the best acoustical correlates of stress. Major syntactic constituents have been shown to have archetype rapid-rise-then-gradual-fall Fo contours, with the rise into the maximum Fo often associated with the first stressed syllable in the constituent. An automatic precedure for detecting constituent boundaries and maximum Fo positions in constituents, and sonorant energy and Fo functions, provided input data for an algorithm for locating stressed syllables. The first stressed syllable of a constituent was associated with a high-energy-integral portion near the rising Fo into maximum Fo position. Other stressed syllables were associated with high-energy-integral portions near local increases in Fo above a steadily-falling "archetype line" from the maximum Fo position to the end of the constituent. For over 400 seconds of speech, including written texts, questions, commands, and declarations for man-machine interaction, over 85% of all syllables perceived as stressed by a panel of listeners were correctly located. (Author/DD)

This study explored the effects of visual (vertical and horizontal) and oral presentation modes upon simple mathematical computations (addition, subtraction, and multiplication). Seventy-two undergraduate education majors were employed as subjects. The placement of the process sign (left, middle, right) and whether a one or two digit number appeared first in the mathematical sentence was manipulated. The results demonstrated significant differences for modality, type of computation, sign and two-digit placement. Further, it appears that for the oral presentation, the process sign placed last is superior to the first position. (Author/MM)

This paper describes a teaching method, presently in the experimental stage, that advocates the use of a programed instruction model in the language laboratory, with students working in homogeneous groups of three. The author describes the technical construction and operation of the language laboratory which allows three students to work together and to use a programed instructional format. The students study new grammar points in microunits. Diagrams illustrate the working of the program, and the author provides an explanation of the steps in its operation. An example of how the program works is presented. (VM)

This paper distinguishes several ways in which phonemic information might be employed in spelling; examines some empirical data on the consequences of using these information sources; formulates hypotheses about the underlying processes involved; and suggests possible implications for the teaching (and learning) of spelling. Included are tables of the phoneme code with graphemic options and examples, Comparisons of Spelling by Elementary School Pupils with the Hanna-Rudorf Algorithm, and figures depicting the spelling and reading errors by means of a Generator-Test Process. The simulation technique discussed may be used to identify the spelling processes used by individual children and the information they hold in memory, and to diagnose and prescribe treatment for individual spelling problems. (Author/LS)

This monograph focuses on the influence of meaning theory on elementary school mathematics programs and on mathematics instruction. Theories of arithmetic instruction up through 1935 are described, and the philosophy of meaning theory, contributions and discussions by mathematics educators, and applications to actual instruction are delineated for the period from 1935 through 1960. A discussion of the implicit concern for meaning in the modern mathematics movement from 1960 to the present concludes the first section. The second section summarizes studies that establish and affirm the importance of and need for meaning and studies that explore the effect of teaching various procedures with meaning. The final section of the paper briefly discusses the implementation of mathematically meaningful instruction. An extensive bibliography is included. (DT)

Words and word fragments from the computer-readable data bases "Chemical Abstracts Condensates" and "Biological Abstracts Previews" were analyzed in terms of length, number, and frequency of appearance to determine some parameters upon which inversion of these data bases could be predicated. Types (unique words or fragments) and tokens (all appearances of types) were counted and type:token ratios calculated. A KLIC (Key-letter-in-Context) Index was also generated from each of the data bases. The paper discusses the impact of the various counts, ratios and projections on the problem of inverting the data bases for retrospective search purposes. (Author)

This paper describes the notation and underlying organization of an augmented, recursive-transition network grammar and illustrates how such a grammar is a natural medium for expressing and explaining a wide variety of facts about the psychological processes of sentence comprehension. A general discussion of transformational grammar and psycholinguistics serves as background information. Details on the structure, characteristics, and operation of the augmented, recursive-transition network grammar are provided. There is a discussion concerning the formalization of perceptual strategies and how these strategies can be naturally represented in transition network grammars. A concluding section explains the justification of transition network models. A list of references is included, and diagrams illustrate the working of the grammar in several problem areas. (VM)

In this paper a reliable method is found for approximating the value of the Bivariate Normal Correlation Coefficient, rho, given values of the joint probability and the normal deviates, h and k, or the related areas. This technique finds useful application in the computation of the tetrachoric correlation coefficient, r, when the underlying distributions may be assumed to be normal. (Author)

The system described in this report is designed for use as a computational tool that allows a linguist to develop and study methods for generating surface strings from an underlying semantic structure. Initial findings with regard to form-determiners (such as voice, form, tense, and mood), some rules for embedding sentences, and some attention to pronominational substitution are reported. The report discusses how a particular semantic network can be used in conjunction with a grammar to generate sequences of coherent English sentences. The paper first outlines the form of the grammar and lexicon and describes a random generation algorithm that produces syntactically well-formed nonsense. It then shows how the semantic nets are used to control the ordering of grammar rules and lexical selections to generate meaningful discourse. There is also a section on some of the methods and rules for generating multi-sentence discourse. Special emphasis is given to the questions and problems that arise. A list of references is provided.For additional information, see FL 002 344. (Author/VM)

An algorithm for generating a structural syntactic surrogate of English text is defined in this paper. The "performance" of the surrogate is judged empirically according to adherence to the following criteria: (1) The surrogate is an organized representation of natural language text; (2) The algorithm which produces the surrogate is equally applicable to any English text; (3) The surrogate may be derived solely by computer processing; (4) The major concepts (or themes) of the text are clearly discernable and/or mechanically derivable from the surrogate; (5) The document may be derived from the surrogate; and (6) The surrogate is feasible to implement. That is, it is not inordinately expensive in computer processing time nor storage, and does not rely upon human processing, preprocessing or interpretation. Possible applications and derivations of the surrogate are explored and discussed. (Author/NH)

The European literature on algorithms for learning and instruction is reviewed in this document. The word "algorithm" is defined, the relationship between the European literature and current trends in research on learning and instruction in the United States is described, the important practical uses of algorithms are discussed, and potential high-yield research activities related to the use of algorithms are suggested. (DT)

In generating sentences by means of a transformational grammar, it is necessary to analyze trees, testing for the presence or absence of various structures. This analysis occurs at two stages in the generation process--during insertion of lexical items (more precisely, in testing contextual features), and during the transformation process, when individual transformations are being tested for applicability. In this paper the authors describe a formal system for the definition of tree structure of sentences. The system consists of a formal language for partial or complete definition of the tree structure of a sentence, plus an algorithm for comparison of such a definition with a tree. It represents a significant generalization of Chomsky's notion of "proper analysis," and is flexible enough to be used within any transformational grammar which the authors have seen. (Authors/AMM)

This study defined a type of information-processing task analysis and an index relating different instructional sequences to this analysis. One hundred sixty-four college students were taught, with computer-assisted instruction, an imaginary science by various instructional sequences or by selecting their own sequence. A program-controlled instructional sequence conforming to the sequence defined by the task analysis was most effective. Learner-controlled sequences yielded poor performance. The contributions of the cognitive abilities of induction, associative memory, and general reasoning to performance under learner and program-controlled sequence and the ability by sequence interactions were shown. (Author)

As the first of two papers delineating the design of Massachusetts' Management and Information System for Occupational Education (MISOE), these specific dimensions of MISOE structure and function are considered: (1) the distinction between economic and noneconomic analysis, (2) distinctions among census, sample, and other data, (3) the distinction between descriptive and simulative analysis, and (4) functional levels, management levels, and management scope. Information retrieval and analysis for MISOE necessitates: (1) translation of inquiries into analytic hypotheses, (2) the selection of pertinent MISOE subsystems, data types and levels, analytical operations, and models, (3) performing the analyses and interpreting their results, and (4) reporting the results to the inquiry source. Discussions of general analysis requirements and considerations precede the detailing of specific analytical models and algorithms for MISOE, such as multiple linear regression and factor analysis. Dynamic simulation, linear programing, and nonlinear programing models are discussed, in addition to specific noneconomic analysis factors to consider within and among MISOE's subsystems of static space. Technical reports on MISOE's research methodology are appended. Related documents are available in this issue as VT 018 600, VT 018 602, VT 018 809, and VT 018 810. (AG)

This paper discusses an alternate formalism for context-free phrase structure grammar. The author feels that if a grammar is stated completely explicitly it can be represented in the form of a relational network of the type proposed by Lamb. He discusses some formal properties of such networks and makes some revisions to Lamb's formulation which allow the formal properties and the structural complexity count to be kept as simple as possible. The notion of "hill climbing" on equivalence spaces defined by the formal properties and the complexity count is introduced as a model of the simplification part of language acquisition. The author suggests that using the complexity count he proposes, the process of simplification in disjunctive form is "non-uphill all the way." Thus he finds that the network approach not only gives a simpler overall system, but one which has the added advantage of starting linguists along the path of developing a detailed model of the process of language acquisition. (See related document AL 001 636.) (Author/DO)