Search

The design and evaluation of accessibility technology is a core component of the computer science landscape, aiming to ensure that digital innovations are accessible to all. One of the most prominent and long-lasting areas of accessibility research focuses on motor impairments--deficiencies that affect the ability to move, manipulate objects, and interact with the physical world. In this survey article, we present an extensive overview of the past two decades of research into accessibility for people with motor impairments. Following a structured selection process, we analyzed the study details as reported in 177 relevant papers. Based on this analysis, we critically assess user representation, measurement instruments, and existing barriers that exist in accessibility research. Finally, we discuss future directions for accessibility research within the computer science domain. [ABSTRACT FROM AUTHOR]

Genome sequencing technology has advanced at a rapid pace and it is now possible to generate highlydetailed genotypes inexpensively. The collection and analysis of such data has the potential to support various applications, including personalized medical services. While the benefits of the genomics revolution are trumpeted by the biomedical community, the increased availability of such data has major implications for personal privacy; notably because the genome has certain essential features, which include (but are not limited to) (i) an association with traits and certain diseases, (ii) identification capability (e.g., forensics), and (iii) revelation of family relationships. Moreover, direct-to-consumer DNA testing increases the likelihood that genome data will be made available in less regulated environments, such as the Internet and for-profit companies. The problem of genome data privacy thus resides at the crossroads of computer science, medicine, and public policy. While the computer scientists have addressed data privacy for various data types, there has been less attention dedicated to genomic data. Thus, the goal of this paper is to provide a systematization of knowledge for the computer science community. In doing so, we address some of the (sometimes erroneous) beliefs of this field and we report on a survey we conducted about genome data privacy with biomedical specialists. Then, after characterizing the genome privacy problem, we review the state-of-the-art regarding privacy attacks on genomic data and strategies for mitigating such attacks, as well as contextualizing these attacks from the perspective of medicine and public policy. This paper concludes with an enumeration of the challenges for genome data privacy and presents a framework to systematize the analysis of threats and the design of countermeasures as the field moves forward. [ABSTRACT FROM AUTHOR]

This paper is a study of the unique problems posed by the use of computers by composers and performers of music. The paper begins with a presentation of the basic concepts involved in the musical interaction with computer devices, followed by a detailed discussion of three musical tasks: music manuscript preparation, music language interfaces for composition, and real-time performance interaction. Fundamental design principles are exposed through an examination of several early computer music systems, especially the Structured Sound Synthesis Project. A survey of numerous systems, based on the following categories, is presented: compositions and synthesis languages, graphics score editing, performance instruments, digital audio processing tools, and computer- aided instruction in music systems. An extensive reference list is provided for further study in the field. [ABSTRACT FROM AUTHOR]

This paper presents an overview of the problem of testing semiconductor random access memories (RAMs). An important aspect of this test procedure is the detection of permanent faults that cause the memory to function incorrectly. Functional-level fault models are very useful for describing a wide variety of RAM faults. Several fault models are discussed throughout the paper, including the stuck-at-0/1 faults, coupled-cell faults, and single-cell pattern-algorithms. Test procedures for these fault models are presented and their fault coverage and execution times are discussed. The paper is intended for the general computer science audience and presupposes no background in the hardware testing area. [ABSTRACT FROM AUTHOR]

Cache memories are used in modern, medium and high-speed CPUs to hold temporarily those portions of the contents of main memory which are (believed to be) currently in use. Since instructions and data in cache memories can usually be referenced in 10 to 25 percent of the time required to access main memory, cache memories permit the execution rate of the machine to be substantially increased. In order to function effectively, cache memories must be carefully designed and implemented. In this paper, we explain the various aspects of cache memories and discuss in some detail the design features and trade-offs. A large number of original, trace-driven simulation results are presented. Consideration is given to practical implementation questions as well as to more abstract design issues. Specific aspects of cache memories that are investigated include: the cache fetch algorithm (demand versus prefetch), the placement and replacement algorithms, line size, store-through versus copy-back updating of main memory, cold-start versus warm-start miss ratios, multicache consistency, the effect of input/output through the cache, the behavior of split data/instruction caches, and cache size. Our discussion includes other aspects of memory system architecture, including translation lookaside buffers. Throughout the paper, we use as examples the implementation of the cache in the Amdahl 470V/6 and 470V/7, the IBM 3081, 3033, and 370/168, and the DEC VAX 11/780. An extensive bibliography is provided. [ABSTRACT FROM AUTHOR]

The "alpha-beta" algorithm forms the basis of many programs that search game trees. A number of methods have been designed to improve the utility of the sequential version of this algorithm, especially for use in game-playing programs. These enhancements are based on the observation that alpha-beta is most effective when the best move in each position is considered early in the search. Trees that have this so-called "strong ordering" property are not only of practical importance but possess characteristics that can be exploited in both sequential and parallel environments. This paper draws upon experiences gained during the development of programs which search chess game trees. Over the past decade major enhancements to the alpha-beta algorithm have been developed by people building game-playing programs, and many of these methods will be surveyed and compared here. The balance of the paper contains a study of contemporary methods for searching chess game trees in parallel, using an arbitrary number of independent processors. To make efficient use of these processors, one must have a clear understanding of the basic properties of the trees actually traversed when alpha-beta cutoffs occur. This paper provides such insights and concludes with a brief description of our own refinement to a standard parallel search algorithm for this problem. [ABSTRACT FROM AUTHOR]

Modem computer configurations are often designed to share a host of resources among many users who may be simultaneously competing for their utilization. A substantive issue in computer management focuses on how to effectively allocate computing resources and subsequently charge for them in this competing environment. The issue is generally made more complex by the dependencies in resource availability stemming from the hardware configuration. This paper surveys significant charging mechanisms which have been proposed. The paper does not discuss specific commercial software available to implement charging approaches, but rather is written as a basic survey for readers with an interest in both computers and management science. An elementary understanding of probability and statistics will be helpful to the reader of this paper and essential to one who pursues the bibliography. [ABSTRACT FROM AUTHOR]

The article focuses on the journal ACM Computing Surveys. The main difference between a survey paper and tutorial paper published in the journal are emphasis and audience. A survey paper assumes its audience has a general knowledge of the field. A tutorial assumes its audience as inexpert. Most of the papers published in the journal combines the two approaches. The journal prefers papers that meet the minimum standards. A standard of first importance is technical accuracy, quality and clarity. The format for typing the manuscripts have been provided. The journal's policy is to own the copyrights in its technical publications. This protects its authors and employers and facilitates the proper use of the material by others. Each author of an accepted paper is required to sign the journal's copyright form as a condition of publication. Private authors retain all proprietary rights other than copyright such as patent rights. They retain the right to use any part of the article with proper acknowledgement to the journal.

This paper is an introduction to the main features of ALGOL 68, emphasizing the novel features not found in many other programming languages. The topics, data types (modes), type conversion (coercion), generalized expressions (units), procedures, operators, the standard prelude, and input/output, form the basis of the paper. The approach is informal, relying heavily on many short examples. The paper applies to the Revised Report, published in 1975, rather than to the original report, published in 1969. [ABSTRACT FROM AUTHOR]

This paper deals with the history and definitions common to data-base technology. It delimits the objectives of data-base management systems, discusses important concepts, and defines terminology for use by other papers in this issue, traces the development of data-base systems methodology, gives a uniform example, and presents some trends and issues. [ABSTRACT FROM AUTHOR]

Well adapted to the loosely coupled nature of distributed interaction in large-scale applications, the publish/subscribe communication paradigm has recently received increasing attention. With systems based on the publish/subscribe interaction scheme, subscribers register their interest in an event, or a pattern of events, and are subsequently asynchronously notified of events generated by publishers. Many variants of the paradigm have recently been proposed, each variant being specifically adapted to some given application or network model. This paper factors out the common denominator underlying these variants: full decoupling of the communicating entities in time, space, and synchronization. We use these three decoupling dimensions to better identify commonalities and divergences with traditional interaction paradigms. The many variations on the theme of publish/subscribe are classified and synthesized. In particular, their respective benefits and shortcomings are discussed both in terms of interfaces and implementations. [ABSTRACT FROM AUTHOR]

The article introduces the March 1973 issue of the journal ACM Computing Surveys. The journal received various contributions from outstanding authors mostly computer professionals. The journal helped computer people to catch up on the latest ideas concepts and advances in the field. The effect of this change has created new opportunities and challenges for the authors of survey. An increasing number of readers are capable of benefiting from tutorial and survey papers presented at advanced levels. The author provides the characteristics of a paper acceptable by the magazine. A good tutorial paper covering an area of the computer field that has recently become important and better understood will get top priority. The body of the paper should be interesting. The text of the survey can be brief, letting the bibliography that attends it and the index into it be as long and up-to-date as required. An excellent survey article is likely to be given preference over a tutorial that is rated only good.

New direction in Artificial Intelligence research have led to the need for certain novel features to be embedded in programming languages. This paper gives an overview of the nature of these features, and their implementation in four principal families of AI languages: SAIL; PLANNER/CONNIVER; QLISP/INTERLISP; AND POPLER/POP-2. The programming features described include: new data types and accessing mechanisms for stored expressions; more flexible control structures, including multiple processes and backtracking; pattern matching to allow comparison of data item with a template, and extraction of labeled subexpressions; and deductive mechanisms which allow the programming system to carry out certain activities including modifying the data base and deciding which subroutines to run next using only constraints and guidelines set up by the programmer. [ABSTRACT FROM AUTHOR]

Authors of this article have mourned the passing of a creative and thoughtful colleague, Paris C. Kanellakis, who was respected for his many contributions, both technical and professional, to the computer science research community. In mourning Kanellakis' tragic death, his technical facility, his broad knowledge, his insight, his commitment and his humor are missed. To write a research paper with Kanellakis was also an opportunity to observe his indefatigable attention to detail and to engage in vigorous debate with his editorial voice. To his technical ability in solving problems, Kanellakis added a mature editorial voice. These authors have taken this opportunity to present some of Kanellakis' contributions to database theory, including deductive, object-oriented and constraint databases, as well as his work in fault-tolerant distributed computation and in type theory. In each of these areas, they have recognized Kanellakis' research contributions that were examples not merely of good problem solving, but also of insightful problem formulation.

Fringe analysis is a technique used to study the average behavior of search trees. In this paper we survey the main results regarding this technique, and we improve a previous asymptotic theorem. At the same time, we present new developments and applications of the theory that allow improvements in several bounds on the behavior of search trees. Our examples cover binary search trees, AVL-trees, 2-3 trees, and B-trees. [ABSTRACT FROM AUTHOR]

In 1973 Dijkstra introduced to computer science the notion of self-stabilization in the context of distributed systems. He defined a system as self-stabilizing when "regardless of its initial state, it is guaranteed to arrive at a legitimate state in a finite number of steps." A system which is not self-stabilizing may stay in an illegitimate state forever. Dijkstra's notion of self-stabilization, which originally had a very narrow scope of application, is proving to encompass a formal and unified approach to fault tolerance under a model of transient failures for distributed systems. In this paper we define self-stabilization, examine its significance in the context of fault tolerance, define the important research themes that have arisen from it, and discuss the relevant results. In addition to the issues arising from Dijkstra's original presentation as well as several related issues, we discuss methodologies for designing self-stabilizing systems, the role of compilers with respect to self-stabilization, and some of the factors that prevent self-stabilization. [ABSTRACT FROM AUTHOR]

The goal in computer vision systems is to analyze data collected from the environment and derive an interpretation to complete a specified task. Vision system tasks may be divided into data acquisition, low-level processing, representation, model construction, and matching subtasks. This paper presents a comprehensive survey of model-based vision systems using dense-range images. A comprehensive survey of the recent publications in each subtask pertaining to dense-range image object recognition is presented. [ABSTRACT FROM AUTHOR]

In this paper various techniques for optimizing queries in distributed databases are presented. Although no attempt is made to cover all proposed algorithms on this topic, quite a few ideas extracted from existing algorithms are outlined. It is hoped that large- scale experiments will be conducted to verify the usefulness of these ideas and that they will be integrated to construct a powerful algorithm for distributed query processing. [ABSTRACT FROM AUTHOR]

A file server provides remote centralized storage of data to workstations connected to it via a communication network; it facilitates data sharing among autonomous workstations and support of inexpensive workstations that have limited or no secondary storage. Various characteristics of file servers and the corresponding implementation issues based on a survey of a number of experimental file servers are discussed and evaluated in this paper. Particular emphasis is placed on the problem of atomic update of data stored in a file server. The design issues related to the scope of atomic transactions and the granularity of data access supported by a file server are studied in detail. [ABSTRACT FROM AUTHOR]

Interest is increasing in the transformational approach to programming and in mechanical aids for supporting the program development process. Available aids range from simple editorlike devices to rather powerful interactive transformation systems and even to automatic synthesis tools. This paper reviews and classifies transformation systems and is intended to acquaint the reader with the current state of the art and provide a basis for comparing the different approaches. It is also designed to provide easy access to specific details of the various methodologies. [ABSTRACT FROM AUTHOR]

This paper presents responses of some surveyors regarding the article "Retargetable Code Generators," published in the December 1982 issue of the journal "ACM Computing Surveys" and the corresponding response of authors. The article identified the classified techniques for automated retargetable code generation and surveyed the work on these techniques. Among the work surveyed was that of Wulf's Production Quality Compiler-Compiler (PQCC) group. The letter written by William A. Wulf and colleagues in response to the survey points out that, "Operator mismatches invoke heuristic search." Authors of the article present their clarification to this point. Readers interested in detailed information are suggested to refer to the article "A Practical Toolkit for Making Portable Compilers," published in the September 1983 issue of the journal "Communications of the ACM."

Formatting systems are concerned with the physical layout of a document for hard- and soft-copy media. This paper characterizes the formatting problem and its relation to other aspects of document processing, describes and evaluates several representative and seminal systems, and discusses some issues and problems relevant to future systems. The emphasis is on topics related to the specification of document formats; these include the underlying document and processing models, functions performed by a formatter, the formatting language and user interface, variety of document objects, the integration of formatters with other document processing tasks, and implementation questions. [ABSTRACT FROM AUTHOR]

This article, Part II of a two-part series, surveys the state of the art of computer-based interactive editing systems. This paper is a survey intended for a varied audience, including the more experienced user and the editor-designer as well as the curious novice. It presents numerous examples of systems in both the academic and commercial arenas, covering line editors, screen editors, interactive editor/formatters, structure editors, syntax-directed editors, and commercial word- processing editors. We discuss pertinent issues in the field, and conclude with some observations about the future of interactive editing. The references for both parts are provided at the end of Part II. [ABSTRACT FROM AUTHOR]

Many daily tasks, whether done with conventional tools or with computers, can be viewed as editing tasks: tasks in which the state of some target entity is changed by the user. This article, Part I of a two-part series, examines computer-based interactive editing systems, which allow users to change the state of targets such as manuscripts and programs. This paper is a tutorial that defines terms and introduces issues for the novice, and provides a reference for the more knowledgeable reader. The aim is to provide a comprehensive and systematic view of the features of typical systems, highlighting substantive similarities and differences. User and system views of the editing process are provided, a historical perspective is presented, and the functional capabilities of editors are discussed, with emphasis on user-level rather than implementation-level considerations. [ABSTRACT FROM AUTHOR]

Novel data-driven and demand-driven computer architectures are under development in a large number of laboratories in the United States, Japan, and Europe. These computers are not based on the traditional von Neumann organization; instead, they are attempts to identify the next generation of computer. Basically, in data-driven (e.g., data-flow) computers the availability of operands triggers the execution of the operation to be performed on them, whereas in demand-driven (e.g., reduction) computers the requirement for a result triggers the operation that will generate it. Although there are these two distinct areas of research, each laboratory has developed its own individual model of computation, stored program representation, and machine organization. Across this spectrum of designs there is, however, a significant sharing of concepts. The aim of this paper is to identify the concepts and relationships that exist both within and between the two areas of research. It does this by examining data-driven and demand-driven architecture at three levels: computation organization, (stored) program organization, and machine organization. Finally, a survey of various novel computer architectures under development is given. [ABSTRACT FROM AUTHOR]

The languages C and PASCAL are growing in popularity, particularly among programmers of small computers. In this paper we summarize and compare the two languages covering their design philosophies, their handling of data types, the programming facilities they provide, the impact of these facilities on the quality of programs, and how useful the facilities are for programming in a variety of application domains. [ABSTRACT FROM AUTHOR]

Empirical studies have been undertaken to measure the ease-of-use of a query language, compare two or more such languages for ease-of-use, study controversial issues in query language design, and provide feedback to designers for improving a language. Some primitive attempts at constructing abstract models related to query languages also exist. This paper discusses some of the techniques that have been used and results obtained. A primary goal is to show the reader unfamiliar with behavioral research what the results do and do not mean. [ABSTRACT FROM AUTHOR]

Database management systems have evolved to the point of general acceptance and wide application; however a major problem still facing the user is the effective utilization of these systems. Important to achieving effective database usability and responsiveness is the design of the database. This paper presents a practical stepwise database design methodology that derives a DBMS-processable database structure from a set of user information and processing requirements. Although the methodology emphasizes the logical design step, the activities of requirements analysis and physical design are also addressed. The methodology is illustrated with a detailed example. Performance trade-offs among multiple users of a single integrated database are considered, and the relationship between short-term design and design for flexibility to changing requirements is discussed. Many steps in the database design process can be assisted with proper use of computer modeling techniques and other tools, such as requirements analysis software. The example design problem and its solution steps serve to point out when and where current technology can be effectively used. [ABSTRACT FROM AUTHOR]

Automated office systems are emerging as an interdisciplinary research area with a strong computer science component. In this paper office information systems are defined as entities which perform document storage, retrieval, manipulation, and control within a distributed environment. Some state-of-the-art implementations are described. The research is related to different areas of computer science and several detailed examples are provided. [ABSTRACT FROM AUTHOR]

Because of the natural way in which subsystems are cast into subproblems, resource- directive decomposition methods of mathematical programming problems have attracted considerable attention in recent years. A review of the specialized literature is presented in this paper, where the features and drawbacks of the most representative resource-directive methods are analyzed. To give an appropriate chronological and technical perspective, early general methods, such as the ones of Dantzig-Wolfe and Benders, are also included in the survey. [ABSTRACT FROM AUTHOR]

B-trees have become, de facto, a standard for file organization. File indexes of users, dedicated database systems, and general-purpose access methods have all been proposed and implemented using B-trees. This paper reviews B-trees and shows why they have been so successful. It discusses the major variations of the B-tree, especially the W-tree, contrasting the relative merits and costs of each implementation. It illustrates a general purpose access method which uses a B-tree. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to describe the concepts, definitions, and ideas of computer architecture and to suggest that architecture can be viewed as composed of three components: physical organization; control and flow of information; and representation, interpretation and transformation of information. This framework can accommodate diverse architectural concepts such as array processing, microprogramming, stack processing and tagged architecture. Architectures of some existing machines are considered and methods of associating architectural concepts with the components are established. Architecture design problems and trade-offs are discussed in terms of the proposed framework. [ABSTRACT FROM AUTHOR]

This survey paper discusses the facilities provided by hierarchical data-base management systems. The systems are based on the hierarchical data model which is defined as a special case of the network data model. Different methods used to access hierarchically organized data are outlined. Constructs and examples of programming languages are presented to illustrate the features of hierarchical systems. This is followed by a discussion of techniques for implementing such systems. Finally, a brief comparison is made between the hierarchical, the network, and the relational systems. [ABSTRACT FROM AUTHOR]

This paper presents in tutorial fashion the concepts, notation, and data-base languages that were defined by the CODASYL Data Description Language and Programming Language Committees. Data structure diagram notation is explained, and sample data-base definition is developed along with several sample programs. Advanced features of the languages are discussed, together with examples of their use. An extensive bibliography is included. [ABSTRACT FROM AUTHOR]

The proliferation of programming languages has raised many issues of language design, definition, and implementation. This paper presents a series of ten mini-languages, each of which exposes salient features found in existing programming languages. The value of the mini-languages lies in their brevity of description and the isolation of important linguistic features: in particular, the notions of assignment, transfer of control, functions, parameter passing, type checking, data structures, string manipulation, and input/output. The mini-languages may serve a variety of uses: notably, as a pedagogical tool for teaching programming languages, as a subject of study for the design of programming languages, and as a set of test cases for methods of language implementation or formal definition. [ABSTRACT FROM AUTHOR]

The article presents information about the editorial policy of the journal ACM Computing Surveys. The author provides a brief background of the journal focusing on its emergence and purpose. In the late 1960s the U.S.-based Association of Computing Machinery perceived a need to provide a journal to its members to help them discover new specialties, and to help practitioners stay abreast. The journal began publication in March 1969 with Bill Dorn as editor-in chief and Myrtle Kellington as executive editor. The difference between surveys and tutorials are analyzed in the article. The main difference is that a survey paper assumes its audience has a general knowledge of the field, it emphasizes an overall view of the literature. A tutorial assumes its audience is inexpert; it emphasizes the basic concepts of the field. The primary purpose of a survey is a guided tour through the literature in an area, while the purpose of a tutorial is explaining a topic's basic concept. The author throws some light on the choice of publications in the journal.

The article presents an overview of the September 1982 issue of the journal "ACM Computing Surveys." The author says that information stored in a computer includes numerical, textual, and graphical information. Such information can be collected and ordered for presentation to the computer user. Ordered collections of information entities, such as textual paragraphs, graphical line drawings, or numerical tables, are called documents. Researchers Norman Meyrowitz and Andries van Dam delineate and illustrate the process of interactive editing. Their paper covers editing tasks that modify the textual entities used either in a manuscript or in a computer program. Document-formatting systems are concerned with the physical layout of a document for portrayal either on a computer display screen or on hard copy. The paper by Richard Furuta, Jeffrey Scofield, and Alan Shaw examines these formatting systems from a variety of perspectives. Cache memories are used to temporarily hold those portions of the contents of main memory which are believed to be currently in use.

The article presents an introduction to the May 1, 1998 issue of the journal "ACM Computing Survey." The issue includes articles on software engineering frameworks, business computing algorithms and concurrency control performance. Researcher Scott Lewandowski's article "Frameworks for Component-Based Client/Server Computing" is the first winner of the journal's student paper award. It presents an in-depth review into frameworks for client-server computing and principles. It explores frame work for distributed objects and compound documents. High standard of the paper provide a baseline for future submissions to the journal's student paper competition. Researcher Alexander Thomasian's "Concurrency Control: Methods, Performance, and Analysis" a traditional area of computer science from a new perspective. It provides a performance analysis of both standard and non-standard locking system techniques, exploring methods of improving locking performance. Techniques examined include restart-oriented locking methods, the running priority method and optimistic concurrency control techniques.

The article discusses the role of theory. The work of computer scientists Juris Hartmanis and R.E. Stearns, for which they rightly and belatedly won the Turing award, was both amazingly insightful and widely useful. It led to a long sequence of important innovations, such as work on cryptographic complexity and it is a principal justification for theoretical research today. Further, theory has had triumphs outside the computational complexity area. The theory community was not alone in its naivete. This view led to periodic, overly optimistic predictions of success that continue to trouble artificial intelligence. Thus, despite the successes as the theory field grew there was a tendency to attack problems obliquely. In the process, the real problems that spawned the original paper were forgotten and the community began to imagine that the research embodied in the papers was the ultimate goal. The author holds that there is need to reinvent theory for the next generation to have the same impact now as a generation ago.

The article presents an introduction to various articles published in this issue of the periodical. In "Gross Motion Planning-A Survey," Yong K. Hwang and Narendra Ahuja survey recent results in this important research area. They offer a classification of the types of motion planning problems and also a classification of the major approaches to motion-planning algorithms. The major part of the paper presents the available results organized in terms of these classification schemes. Boolean algebra is basic to much of computer science. The second paper in this issue, "Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams" by Randal E. Bryant, concerns the efficient representation and manipulation of symbolic Boolean functions. As noted by Bryant, most applications of this work have been in the area of digital-system design, verification and testing. However, an impressive list of additional applications is also discussed and the paper is of much broader interest. For example, it is shown that finite-state transition systems can often be efficiently represented via ordered binary-decision diagrams.

The article presents an introduction to the June 1, 1977 issue of the journal ACM Computing Surveys. According to the author this issue is unusual because of its compactness. The issue's major technical contribution is a very interesting and well-written paper by Robert Sedgewick. It also contains a statement by the author himself about the editorial policies for the journal. The statement summarizes the history of surveys and some data on what it has published, it offers definitions of survey and tutorial papers. The article also describes various kinds of papers considered to conduct the study, and has information for prospective authors, and it sets forth the questions which referees answer for each paper.

This article focuses on September 1984 issue of "ACM Computing Surveys." Two articles in this issue explore efforts to improve system performance through parallelism. The articles examine parallel sorting algorithms. They present historical developments in parallel sorting, emphasizing feasibility of algorithms rather than their theoretical aspects. Most of these algorithms employ main memory, and are, therefore, internal sorting approaches, as contrasted with external sorting, where the size of the file to be sorted makes it impossible to use main memory exclusively. Another article discusses parallel algorithms and data structures for graph processing. Graphs are widely used, both in computer science and in related science and engineering fields. The paper gives attention to the feasibility of implementation of these algorithms on parallel processors. Much of the information in this article is very compactly presented in tabular form, showing the principal results by method, model, and complexity.