Department of Computer Science

Permanent URI for this community

https://hdl.handle.net/10919/19035
The Department of Computer Science has an accredited undergraduate program that offers specialized ‘tracks’ of study in key areas. Undergraduates are prepared by graduation for pursuing a computing career or for graduate study. Our active corporate partners program offers internships and permanent employment to our students. Students are encouraged to participate in research experiences during their studies. Capstone courses provide significant team project experiences. The graduate program offers M.S. and Ph.D. degrees, emphasizing thesis work both at the main campus in Blacksburg and at the Northern Virginia Center. About two-thirds of the graduate students are pursuing the Ph.D. degree. The faculty, among whom there are 12 NSF or DOE CAREER Award winners, are active researchers who are visible contributors to the profession and have achieved significant honors.

Browse

Browsing Department of Computer Science by Issue Date

Filter results by year or month
Now showing 1 - 20 of 1953
  • Thumbnail Image
    Memetic algorithms for Spatial Partitioning problems
    Biswas, Subhodip; Chen, Fanglan; Chen, Zhiqian; Lu, Chang-Tien; Ramakrishnan, Naren (ACM)
    Spatial optimization problems (SOPs) are characterized by spatial relationships governing the decision variables, objectives, and/or constraint functions. In this article, we focus on a specific type of SOP called spatial partitioning, which is a combinatorial problem due to the presence of discrete spatial units. Exact optimization methods do not scale with the size of the problem, especially within practicable time limits. This motivated us to develop population-based metaheuristics for solving such SOPs. However, the search operators employed by these population-based methods are mostly designed for real-parameter continuous optimization problems. For adapting these methods to SOPs, we apply domain knowledge in designing spatially-aware search operators for efficiently searching through the discrete search space while preserving the spatial constraints. To this end, we put forward a simple yet effective algorithm called SPATIAL and test it on the school (re)districting problem. Detailed experimental investigations are performed on real-world datasets to evaluate the performance of SPATIAL. Besides, ablation studies are performed to understand the role of the individual components of SPATIAL. Additionally, we discuss how SPATIAL is helpful in the real-life planning process, its applicability to different scenarios, and motivate future research directions.
  • Thumbnail Image
    The Dynamic Creation And Modification of Heuristics in a Learning Program
    Claybrook, Billy G.; Nance, Richard E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    POLY FACT is a learning program that attempts to factor multivariable polynomials. The program has been successful in factoring polynomials (in simplified form) with a maximum of 84 terms, each term consisting of as many as five variables and a maximum degree of 67. The complexity of this learning task placed unusual requirements on the representation of heuristics. By using the first-order predicate calculus notation, we enable the creation and modification of heuristics dynamically during program execution. Constraints on the creation process are implemented in a series of tables by which one can alter the flexibility given to the program. Execution of heuristics begins with a translation of the predicate calculus representation to a reverse Polish string, followed by the interpretive evaluation of the Polish string. A general procedure for developing and implementing the predicate calculus representation is suggested.
  • Thumbnail Image
    Microprogrammable Cellular Automata
    Muzio, Jon C.; Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    This paper reports research into cellular automata with two binary inputs, two binary outputs, and an octal control variable. A set of control variables is chosen and it is shown that any function of three variables can be realized by a 2 x 2 array of cells, any function of four variables by a 2 x 6 array of cells. A construction based on the Shannon Decomposition Theorem is given for the realization of functions of more than four variables. The existence of a more efficient construction is conjectured. A definition of the circuit defining the cell is given as well as an implementation using NAND gates. A practical configuration of the cells is suggested and fault correction is discussed.
  • Thumbnail Image
    Generalized Structured Programming
    Martin, Johannes J. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    In an effort to eliminate some inconveniences connected with Dijkstra's method of Structured Programming, a generalized set of basic flow graphs for structuring programs is suggested. These structures generate the set of all flow graphs that can be fully decomposed by Allen and Cocke's method of interval reduction. It will be shown that programs Composed of the proposed basic structures have most, if not all, of the Positive characteristics claimed for programs written with the classic rules of Structured Programming. Further, by extending Wirth's programming language PASCAL a set of new control constructs has been suggested that support the proposed set of flow structures.
  • Thumbnail Image
    A Complete Horizontal Microlanguage
    Wesselkamper, Thomas C.; Nixon, Eric (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    This paper defines a data space whose points are trees with leaves which are [name,value] pairs. Over this space a substitution operator S (meaning informally "in x for y put z") is formally defined. Taken together with several auxiliary operators, S is shown to be sufficient to define a large class of high-level languages since S is known to be functionally complete for finite-valued spaces, a functionally complete language is exhibited.
  • Thumbnail Image
    Functionally Complete Machines
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    This paper defines a functionally complete machine as a machine which is capable of evaluating every two place function over its data space. Necessary conditions on memory size for completeness are developed. These conditions are applied to System/360 as modelled by the space of bytes, the space of halfwords, and the space of words. Sufficiently large (> 64K bytes) models of System/360 are shown to be complete for the space of bytes. No models of System/360 are complete for the spaces of halfwords or words. The inequalities developed and known examples of universal decision elements suggest structures for complete machines.
  • Thumbnail Image
    Dynamic Quantum Allocation and Swap-Time Variability in Time-Sharing Operating Systems
    Bhat, U. Narayan; Nance, Richard E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    No abstract available.
  • Thumbnail Image
    A Topological Model of the Data Space for a Block Structured Language
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    A space X is defined, the points of which are trees which possess a unique name property. A topology is defined for X based upon partial order. The topology is shown to be reasonably natural relative to the rationals. The topological space is shown to be neither Hausdorff nor T_1. The implications of this for program convergence are discussed with examples.
  • Thumbnail Image
    Lpl: A Generalized List Processing Language
    Claybrook, Billy G. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    The paper describes LFL, a generalized list processing language. LFL allows the user to define multiple cell structures and cell sizes at runtime, thereby allowing nonhomogeneous list structures. The paper examines the problems associated with list tracing in systems allowing multiple cell-types. Complex list tracing during garbage collection in LFL is avoided: (1) by creating a doubly-linked super list of all allocated cells and (2) by using a reference count scheme. No marking phase is required for garbage collection. The problem of developing insertion and deletion procedures for lists with cells having multiple types of pointer structures is discussed and LFL solutions are given. LPL statements can handle singly-linked, doubly-linked, left-right-linked, and some multi-linked pointer structures automatically. The design philosophy and the data organization for LPL are discussed in detail. Examples of the definition of cell structures are given, and all of the LPL list manipulation and creation statements arc examined and discussed.
  • Thumbnail Image
    Fol: A Language for Implementing File Organizations for Information Storage And Retrieval Systems
    Claybrook, Billy G. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)
    The language FOL is described. FOL facilitates the implementation of file organizations for IS & R systems. FOL is implemented in a list processing language LPL. Files in FOL are interepreted as a list of records, where each record is equivalent to a node structure. A description of LPL is also included.
  • Thumbnail Image
    The Role of Automatic Digitizers in Computer Aided-design
    Williams, Charles M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    The incorporation of facilities for automatically digitizing documents can considerably enhance the power of computer graphics in computer-aided-design. A hardware-software process is described which rapidly and economically digitizes hard-copy drawings and translates them into computer data structures which faithfully represent both their geometry (including line widths) and their topology (line connectivities). These data structures may be directly interfaced to standard computer graphic manipulation software or they may serve as a source of information for analytic routines. The system thus allows drawings to serve as an immediate source of data for existing CAD processes. The result is that the tedium and inaccuracies associated with inputting graphic information has largely been removed so that the human may better concentrate his energies in the tasks of design and analysis.
  • Thumbnail Image
    The Relationship Between the Multiplicative And Mixed Generators Modulo 2^b
    Overstreet, Claude Jr. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    MacLaren and Marsaglia [4] comment that their test results suggest that the multiplicative generator performs better than the mixed generator. We attempt to answer the above question by showing that for any sequence of real values in (0,1) produced by the multiplicative generator modulo 2^b a corresponding mixed generator exists which, for practical purposes, produces the same sequence of real values.
  • Thumbnail Image
    The Mixed Method of Random Number Generation: A Tutorial
    Overstreet, Claude Jr.; Nance, Richard E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    Several motivations are recognized for user-defined random number generators in preference to built-in generators. The mixed method of random number generation is discussed) and the conditions for achieving full period with a modulus of 2^b are explained. Implementation of mixed random number generators is affected both by the computer and language used. Guidelines are presented for realizing acceptable mixed generators on several machines using the FORTRAN, PL/l and SNOBOL4 languages.
  • Thumbnail Image
    A Process for Producing Tactually Perceptible Images of Line Drawings for Use by the Blind
    Williams, Charles M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    A working prototype computer controlled process is described for automatically converting line drawings into raised line images perceptible to the touch. The process uses an automatic digitizer for input and a milling machine for output.
  • Thumbnail Image
    First Report on Epos: Aspects of Generality And Efficiency in Programming Language Implementation
    Martin, Johannes J. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    No abstract available.
  • Thumbnail Image
    The Logical Foundations of Microlanguages
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    After the consideration of two recent examples of instruction sets for microprogrammable computers, the article sketches known and new results about complete sets of functions which appear to be applicable to microlanguage development. Some needed areas of research are pointed out. Functional completeness is linked to research in control primitives for machines.
  • Thumbnail Image
    A Note on Ledgard's Minilanguage 2 And a Proposal for an Alternative
    Lee, John A. N. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    This note reviews and discusses the concepts of assignment statements which occur within programming languages and as exemplified by Minilanguage 2 by Ledgard [3]. Observing that the description of assignment by Ledgard depends on the existence of a nominative addressing scheme, an alternative vignette of language is proposed which is based on type directed addressing systems.
  • Thumbnail Image
    On Making Bairstow's Method Work
    Ault, David A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    No abstract available.
  • Thumbnail Image
    A File Definition Facility for File Structures
    Claybrook, Billy G. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    This paper describes a file definition facility (FDF) for defining files as graph structures. The structure of the file is explicitly declared in the file definition. Primitive functions(from graph theory), operators, and the format of the definition statements are given. The combination of functions and operators appear as directives to the programming system for structuring files. Several simple examples are given to illustrate the use of the FDF. The data organization for the implementation of this facility is described in detail. Problems of considerable importance that are treated are. (1) garbage collection, (2) template construction, and (3) runtime address calculation. The external definitions are represented internally by descriptors. The format of the descriptors is given and a discussion of the items in the descriptors is presented.
  • Thumbnail Image
    Introduction to Pest Control Using the Watfiv Compiler
    Ault, David A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    The purpose of this paper is to consolidate into a brief guide procedures to aid in debugging FORTRAN programs which are being executed under the control of a WATFIV compiler.