Browsing College of Engineering (COE) by Issue Date
Now showing 1 - 20 of 5669
Results Per Page
- Memetic algorithms for Spatial Partitioning problemsBiswas, 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.
- Survey of Approaches and Techniques for Security Verification of Computer SystemsErata, Ferhat; Deng, Shuwen; Zaghloul, Faisal; Xiong, Wenjie; Demir, Onur; Szefer, Jakub (ACM)This paper surveys the landscape of security verification approaches and techniques for computer systems at different levels: from a software-application level all the way to the physical hardware level. Different existing projects are compared, based on the tools used and security aspects being examined. Since many systems require both hardware and software components to work together to provide the system's promised security protections, it is not sufficient to verify just the software levels or just the hardware levels in a mutually exclusive fashion. This survey especially highlights system levels that are verified by the different existing projects and presents to the readers the state of the art in hardware and software system security verification. Few approaches come close to providing full-system verification, and there is still much room for improvement.
- The Dynamic Creation And Modification of Heuristics in a Learning ProgramClaybrook, 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.
- Generalized Structured ProgrammingMartin, 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.
- Dynamic Quantum Allocation and Swap-Time Variability in Time-Sharing Operating SystemsBhat, U. Narayan; Nance, Richard E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)No abstract available.
- A Topological Model of the Data Space for a Block Structured LanguageWesselkamper, 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.
- Lpl: A Generalized List Processing LanguageClaybrook, 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.
- Functionally Complete MachinesWesselkamper, 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.
- X‐ray diffraction approach to grain boundary and volume diffusionUnnam, Jalaiah; Carpenter, Joseph A.; Houska, Charles R. (American Institute of Physics, 1973)A generalized two‐dimensional diffusionmodel has been developed which consists of an array of boundaries coupled to the free surface and to the substrate lattice. The model makes use of three nonlinear partial differential equations which describe lattice, grain boundary, and surfacediffusion. This two‐dimensional model has been programmed for the IBM 360 computer using a finite‐difference solution to give concentrations as a function of time. An x‐ray intensity simulation program is developed to give integrated diffracted intensity for a given concentration distribution. This simulated intensity is compared with experimental intensity. Data are presented from a sample containing 8 μ of Ni on a (111)‐oriented Cu crystal diffused for various times at 900°C and a similar sample with 6.5 μ of Ni diffused at 600°C. The simulations are in good agreement with experimental intensity bands. Activation energies and frequency factors are given for volume and grain boundarydiffusion which are in good agreement with those literature values that are available. After a diffusion treatment at 600°C, it was found that pipe diffusion makes an important contribution to the volume diffusion coefficient. At 900°C this does not appear to be true. The contribution from pipe diffusion correlates with rocking curve data except for compositions close to that of the free surface.
- Fol: A Language for Implementing File Organizations for Information Storage And Retrieval SystemsClaybrook, 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.
- Microprogrammable Cellular AutomataMuzio, 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.
- A Complete Horizontal MicrolanguageWesselkamper, 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.
- On the Minimal Total Path Length of a Spanning TreeKang, Andy N. C.; Ault, David A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)The notions of a balance node and the total path length with respect to a node u of a spanning tree are defined. We show that the total path length of a spanning tree with respect to u is minimal if and only if u is a balance node. An algorithm is also given to locate a balance node. A proof of the correctness of the algorithm is given and the complexity of the algorithm is analyzed.
- Analysis of an Enumeration Algorithm for Unordered K-partitions of NKang, Andy N. C.; Kang, C. K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)In many combinatorial problems, the need to compute the number of unrestricted partitions of n or to enumerate over the set of unrestricted partitions of n occurs frequently. Let two positive integers k and n be given, the set of unordered k-tup1es (a1,a2,..., ak) of positive integers such that a1+a2+...+ak=n is called the unordered k-partitions of n. In this paper, an algorithm to enumerate the set is presented and analyzed. The running time of the algorithm is shown to be linearly proportional to the number of elements in the set. The number of unordered k-partitions of n, f_k(n), is given in a recurrence relation as a byproduct. With these results, to enumerate the unrestricted partitions of n, we need only to enumerate successfully the unordered 1- partition of n, 2-partitions of n, ... , up to n-partitions of n.
- Nonlinear analysis of the forced response of structural elementsNayfeh, Ali H.; Mook, Dean T.; Sridhar, Seshadri (Acoustical Society of America, 1974)A general procedure is presented for the nonlinear analysis of the forced response of structural elements to harmonic excitations. Internal resonances (i.e., modal interactions) are taken into account. All excitations are considered, with special consideration given to resonant excitations. The general procedure is applied to clamped-hinged beams. The results reveal that exciting a higher mode may lead to a larger response in a lower interacting mode, contrary to the results of linear analyses.
- Searching One Multiplier in GlmGreenberg, Harvey J. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)A unified approach is developed for one-dimensional GLM. The major result is a convergence theorem for interval reduction. Comparative analysis of bisection, linear interpolation and tangential approximation reveals the relative advantages of tangential approximation.
- Three Papers on the Completeness Properties of Abelian Semi groups and GroupsWesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)The three papers presented here all arise from recent research into sets of operators which are sufficient to define a horizontal microlanguage for a computer and which are (in some undefined sense) natural for human beings to use. It is this criterion of naturalness which leads us to consider dyadic operators which are commutative and associative, that is, structures which are abelian semigroups.
- Sound waves in two-dimensional ducts with sinusoidal wallsNayfeh, Ali H. (Acoustical Society of America, 1974)The method of multiple scales is used to analyze the wave propagation in two-dimensional hard-walled ducts with sinusoidal walls. For traveling waves,resonance occurs whenever the wall wavenumber is equal to the difference of the wave numbers of any two duct acoustic modes. The results show that neither of these resonating modes could occur without strongly generating the other.
- The Use of Computer Modulated Drawing in the Teaching of ArtWilliams, Charles M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)A hardware-software process is described which automatically creates computer modulated drawings from an artist's own works. The process allows a drawing to act as a constant source of data for a series of renditions of it in widely varying styles. As a result a student of art can study the effects of line structure, line quality, and pen stroking style in rendering truly constant subject material.