Physical Sciences and Mathematics Commons^™

Complete Randomized Cutting Plane Algorithms For Propositional Satisfiability, Stephen Lee Hansen

CCE Theses and Dissertations

The propositional satisfiability problem (SAT) is a fundamental problem in computer science and combinatorial optimization. A considerable number of prior researchers have investigated SAT, and much is already known concerning limitations of known algorithms for SAT. In particular, some necessary conditions are known, such that any algorithm not meeting those conditions cannot be efficient. This paper reports a research to develop and test a new algorithm that meets the currently known necessary conditions.

In chapter three, we give a new characterization of the convex integer hull of SAT, and two new algorithms for finding strong cutting planes. We also show …

The Feasibility Of Developing A Computer Based Expert System To Mitigate Nuclear Power Plant Accidents, Jesse E. Smith

CCE Theses and Dissertations

This study investigated the feasibility of developing a rule-based expert system to support nuclear plant operators in the mitigation of accidents. Human error in the use of Emergency Operating Procedures (EOPs) was the problem to be addressed. The goal was to determine if the Nuclear Plant Information System (NPIS) at one specific power plant would support development of an EOP operator aid to reduce the number of human errors.

A review of the literature confirmed that human error is a recurring problem. This is particularly evident during high stress situations, such as accidents. A rule-based operator aid can reduce human …

An Efficient Algorithm To Determine The Periodic Steady-State Solutions Of Nonlinear Systems Using Extended Spectral Analysis, Gülay Tohumoğlu

Turkish Journal of Electrical Engineering and Computer Sciences

A new method for the solution of nonlinear periodic systems was developed. It avoids the time domain calculations of the whole network equations. In the proposed method, by forming the augmented network as linear and nonlinear subnetworks these subnetworks are formulated in complex frequency and time domain respectively. Using spectral analysis the steady-state periodic solution of the whole nonlinear network is reached by an iterative approach. The method can be applied efficiently to weak and strong nonlinear circuits equally well. When we divide the network into a large linear subnetwork and a small nonlinear subnetwork, this method can be applied …

A Pseudo Spot Price Algorithm Applied To The Pumped-Storage Hydraulic Unit Scheduling Problem, Sali̇h Fadil, Celal Yaşar

Turkish Journal of Electrical Engineering and Computer Sciences

A lossy electric power system that contains thermal units and a pumped-storage hydraulic unit is considered in this paper. The total cost of thermal units in an operation cycle is minimized under some possible electric and hydraulic constraints of the units. The operation cycle is divided into time intervals where the system loads are assumed to remain constant. The proposed solution technique has two main parts. In the first part, the active thermal generations and active generation or pumping power of the pumped-storage unit in all time intervals are determined by using units' active generation incremental costs and pseudo spot …

Distance Spectra For Trellis Coded Modulation Schemes On Channels With Intersymbol Interference, Sabi̇re Haciömeroğlu, Melek D. Yücel

Turkish Journal of Electrical Engineering and Computer Sciences

The effect of intersymbol interference on distance spectra for trellis coded 8-PSK, 16-QAM and 32-AMPM modulation schemes is evaluated using the methods proposed by Schlegel. Distance spectra of 16-state 8-PSK scheme are computed for different intersymbol interference channels. It is seen that on channels with intersymbol interference the spectral lines are spread into a nearly continuous spectrum and the minimum Euclidean distance between codewords decreases severely. Hence, although the main contribution at large signal to noise ratios comes from the minimum Euclidean distance ( d_{free} ) , higher spectral components also become very important at moderate values of the signal …

Solving A Supply Chain Optimization Problem Collaboratively, Hoong Chuin Lau, A. L. C. Lim, Q Liu

Research Collection School Of Computing and Information Systems

We propose a novel algorithmic framework to solve an integrated planning and scheduling problem in supply chain management. This problem involves the integration of an inventory management problem and the vehicle routing problem with time windows, both of which are known to be NP-hard. Under this framework, algorithms that solve the underlying sub-problems collaborate rigorously yet in a computationally efficient manner to arrive at a good solution. We will then present two algorithms to solve the inventory management problem: a complete mathematical model integrating integer programming with constraint programming, and an incomplete algorithm based on tabu search. We present experimental …

A Java Graphical User Interface For Large-Scale Scientific Computations In Distributed Systems, X Shen, George K. Thiruvathukal, Wei-Keng Liao, Alok Choudhary, A Singh

Computer Science: Faculty Publications and Other Works

Large-scale scientific applications present great challenges to computational scientists in terms of obtaining high performance and in managing large datasets. These applications (most of which are simulations) may employ multiple techniques and resources in a heterogeneously distributed environment. Effective working in such an environment is crucial for modern large-scale simulations. In this paper, we present an integrated Java graphical user interface (IJ-GUI) that provides a control platform for managing complex programs and their large datasets easily. As far as performance is concerned, we present and evaluate our initial implementation of two optimization schemes: data replication and data prediction. Data replication …

A Systolic Image Difference Algorithm For Rle-Compressed Images, Fikret Erçal, Mark Allen, Hao Feng

Computer Science Faculty Research & Creative Works

A new systolic algorithm which computes image differences in run-length encoded (RLE) format is described. The binary image difference operation is commonly used in many image processing applications including automated inspection systems, character recognition, fingerprint analysis, and motion detection. The efficiency of these operations can be improved significantly with the availability of a fast systolic system that computes the image difference as described in this paper. It is shown that for images with a high similarity measure, the time complexity of the systolic algorithm is small and, in some cases, constant with respect to the image size. A formal proof …

Recognition And Verification Of Design Patterns, Michael P. Plezbert, Ron K. Cytron

All Computer Science and Engineering Research

In this paper we consider the automatic discovery of design (programming) patterns. While patterns have surfaced as an effective mechanism for authoring and understanding compelx software, popular languages lack facilities for direct specification of patterns or verification of pattern usage in program specifications. Static analysis for patterns is provably undecidable; we focus on discovery and verification of patterns by analyzing dynamic sequences of method calls on object. We show a proof-of-concept of our approach by presenting the results of analyzing a Java program for Iterator patterns.

Codeweave: Exploring Fine-Grained Mobility Of Code, Cecilia Mascolo, Gian Pietro Picco, Gruia-Catalin Roman

All Computer Science and Engineering Research

This paper explores the range of constructs and issues facing the designer of mobile code systems which allow for the unit of mobility to be finer-grained than that of execution. Mobile UNITY, a notation and proof logic for mobile computing, provides for this research a clean abstract setting, i.e., unconstrained by compilation and performance considerations traditionally associated with programming language design. Within the context of Mobile UNITY, we take the extreme view that every line of code and every variable declaration is potentially mobile, i.e., it may be duplicated and/or moved from one program contxt to another on the same …

A Rate-Based End-To-End Multicast Congestion Control Protocol, Sherlia Shi, Marcel Waldvogel

All Computer Science and Engineering Research

Current reliable multicast protocols do not have scalable congestion control mechanisms and this deficiency leads to concerns that multicast deployment may endanger stability of the network. In this paper, we present a sender-based approach for multicast congestion control targeted towards reliable bulk data transfer. We assume that there are a few bottleneck links in a large scale multicast group at any time period and these bottlenecks persist long enough to be identified and adapted to. Our work focus on dynamically identifying the worst congested path in the multicast tree and obtaining TCP-friendly throughput on this selected path. We device novel …

Plugin Management For Active Network, Sumi Y. Choi

All Computer Science and Engineering Research

The purpose of this document is to present the overview of tte plugin management architecture and the description of the software developed for the scalable, high performance active network node project in Washington University, St. Louis. The plugin management is a user space daemon program that runs at the code(plugin) server and at the active network component of a router or a switch port processor. The running programs cooperate to load plugins from the code server to the active network component. This software is intended to be used among multiple platforms.

Lime: A Middleware For Physical And Logical Mobility, Gian Pietro Picco, Amy L. Murphy, Gruia-Catalin Roman

All Computer Science and Engineering Research

LIME is a middleware supporting the development of applications that exhibit physical mobility of hosts, logical mobility of agents, or both. LIME adopts a coordination perspective inspired by work on the Linda model. The context for computation, represented in Linda by a globally accessible, persistent tuple space, is represented in LIME by transient sharing of the tuple spaces carried by each individual mobile unit. Linda tuple spaces are also extended with a notion of location and with the ability to react to a given state. The hypothesis underlying our work is that the resulting model provides a minimalist set of …

Data Archiving With The Srb*, Jinghua Zhou

All Computer Science and Engineering Research

We use the SRB (Storage Request Broker) middleware to design and implement a storage archival system which will be used to archive Neuroscience data. As part of the design process, we developed and used an experimenter's workbench to measure SRB performance. These experiments improved our understanding of both the functionality and the performance of the SRB. This technical report describes the scripts in the experimenter's workbench, the archiving scripts, and performance measurements.

Coordination And Mobility, Gruia-Catalin Roman, Amy L. Murphy, Gian Pietro Picco

All Computer Science and Engineering Research

Mobility entails the study of systems in which components change location, in a voluntary or involuntary manner, and move across a space that may be defined to be either logical or physical. Coordination is concerned with what happens when two or more components come in contact with each other. In this paper we put forth a working definition of coordinatoin, we construct argumetns that demonstrate that coordination is central to understanding mobility, we explore the intellectual richness of the notion of coordination, and we consider the practical implications of coordination-centered system design strategies. We develop these ideas in two steps. …

Almi: An Application Level Multicast Infrastructure, Dimitrios Pendarakis, Sherlia Shi, Dinesh Verma, Marcel Waldvogel

All Computer Science and Engineering Research

The IP multicast model allows scalable and efficient multi-party communication, particularly for groups of large size. However, deployment of IP multicast requires substantial infrastructure modifications and is hampered by a host of unresolved open problems such as reliability, flow and congestion control, security and access control. Motivated by these problems, we have designed and implemented ALMI, an application level group communication middleware, which does not rely on network infrastructure support and thus, allows accelerated deployment and simplified configuration at the cost of a relatively small increase in traffic load. ALMI is tailored toward support of multicast groups of relatively small …

The Design And Performance Of Meta-Programming Mechanisms For Object Request Broker Middleware, Nanbor Wang, Kirthika Parameswaran, Douglass Schmidt

All Computer Science and Engineering Research

Distributed object computing (DOC) middleware shields developers from many tedious and error-prone aspects of programming distribued applications. Without proper support from the middleware, however, it can be hard to evolve distributed applications after they are deployed. Therefore, DOC middleware should support meta-programming mechanisms, such as smart proxies and interceptors, that improve the adaptability of distributed applications by allowing their behavior to be modified without drastically changing existing software. This paper presents three contributions to the study of metaprogramming mechanisms for DOC middleware. First, it illustrates, compares, and contrasts several meta-programming mechanisms from an application developer's perspective. Second, it outlines the …

Configuring Sessions In Programmable Networks, Sumi Choi, Jonathan Turner, Tilman Wolf

All Computer Science and Engineering Research

The provision of advanced computational services within networks is rapidly becoming both feasible and economical. We present a general approach to the problem of configuring application sessions that require intermediate processing by showing how the session configuration problem can be transformed to a conventional shortest path problem. We show, through a series of examples, that the method can be applied to a wide variety of different situations.

Profile-Based Routing: A New Framework For Mpls Traffic Engineering, Subhash Suri, Marcel Waldvogel, Priyank Ramesh Warkhede

All Computer Science and Engineering Research

We present a new algorithm and framework for dynamic routing of bandwidth guaranteed flows. The problem is motivated by the need to dynamically set up bandwidth guaranteed paths in carrier and ISP networks. Traditional routing algorithms such as minimum hop routing or widest path routing do not take advantage of any knowledge about the traffic distribution or ingress-egress pairs, and therefore can often lead to severe network underutilization. Our work is inspired by the recently proposed "minimum interference routing" algorithm (MIRA) of Kodialam and Lakshman, but it improves on their approach in several ways. Our main idea is to use …

Design Tradeoffs For Embedded Network Processors, Tilman Wolf, Mark Franklin, Edward W. Spitznagel

All Computer Science and Engineering Research

Demands for flexible processing has moved general-purpose processing into the data path of networks. With the development of System-On-a-Chip technology, it is possible to put several processors with memory and I/O components on a single ASIC. We present a model of such a system with a simple performance metric and show how the number of processors and cache sizes can be optimized for a given workload. Based on a telecommunications benchmark we show the results of such an optimization and discuss how specialied hardware and appropriate scheduling can further improve system performance.

On Maintaining Group Membership Data In Ad Hoc Networks, Gruia-Catalin Roman, Qingfeng Huang, Ali Hazemi

All Computer Science and Engineering Research

The design of ad hoc mobile applications often requires the availability of a consistent view of the application state among the participating hosts. Essential to constructing a consistent view is the ability to know what hosts are within proximity of each other, i.e., form a group in support of the particular application. In this paper we propose an algorithm that allows hosts within communication range to maintain a consistent view of the group membership despite movement and frequent disconnections. The novel features of this algorithm are its reliance on location information and a conservative notion of logical connectivity that creates …

Programming Active Networks Using Active Pipes, Ralph Keller, Jeyashankher Ramamirtham, Tilman Wolf, Bernhard Plattner

All Computer Science and Engineering Research

Active networks allow customized processing of data traffic within the network which can be used by applications to improve the quality of their sessions. To simplify development of active applications in a heterogeneous environment, we propose active network pipes as a programming abstraction to specify transmission and processing requirements. We describe a routing algorithm that maps application session requirements onto network resources and determines an optimal route through the network transiting all required processing sites. Additionally, we propose a network software architecture to implement the functionality required to support active pipes.

Synthesizer, A Pattern Language For Designing Digital Modular Synthesis Software, Thomas V. Judkins, Christopher D. Gill

All Computer Science and Engineering Research

Synthesizer is a pattern language for designing digital synthesizers using modular synthesis in software to generate sound. Software developed according to this pattern language emulates the abilities of an analog synthesizer. Modular synthesis is one of the oldest sound synthesis techniques. It was used in the earliest analog synthesizers, like the Moog [1] and ARP [2]. These machines introduced the oscillator-filter-amplifier paradigm, where sound generated by an oscillator is passed through a series of filters and amplifers before being sent to a speaker. These first machines had physical modules through which electrical signals were passed. These modules can be emulated …

Parallel Fpga Programming Over Backplane Chassis, John Lockwood, Tom Mclaughlin, Tom Chaney, Yuhua Chen, Fred Rosenberger, Alex Chandra, Jon Turner

All Computer Science and Engineering Research

For systems with a large number of FPGAs, where a design is instantiated across multiple FPGAs in a chassis, an efficient mechanism of programming the FPGA devices is needed. The mechanism described herein allows multiple FPGAs to be programmed across a backplane. Only a single configuration PROM is required to store the configuration for the multiple instances of the design. When the system boots, all FPGAs are programmed in parallel. This design is applicable to any system which contains a multiple board system which has instances of identical FPGA implementations distributed across the boards. Signal integrity of signals is considered.

Quasi-Monte Carlo Methods In Cash Flow Testing Simulations, Michael Gene Hilgers

Business and Information Technology Faculty Research & Creative Works

What actuaries call cash flow testing is a large-scale simulation pitting a company''s current policy obligation against future earnings based on interest rates. While life contingency issues associated with contract payoff are a mainstay of the actuarial sciences, modeling the random fluctuations of US Treasury rates is less studied. Furthermore, applying standard simulation techniques, such as the Monte Carlo method, to actual multi-billion dollar companies produce a simulation that can be computationally prohibitive. In practice, only hundreds of sample paths can be considered, not the usual hundreds of thousands one might expect for a simulation of this complexity. Hence, insurance …

Computational Finance Models, Michael Gene Hilgers

Business and Information Technology Faculty Research & Creative Works

The author discusses his involvement in developing computational finance software. These computational finance models attempt to model the randomness of a stock's price. At a fixed future time, a stock's price is modeled as a random variable with a normal distribution centered about the current price adjusted with a simple growth multiplier. The standard deviation of this normal distribution depends on the length of time into the future one peers and the volatility of the market. As the market becomes more volatile and we look further ahead, the less likely the stock will have a price near the adjusted current …

A Novel Application Development Environment For Large-Scale Scientific Computations, Alok Choudhary, Mahmut Kandemir, Wei-Keng Liao, G Memik, S More, X Shen, A Singh, George K. Thiruvathukal

Computer Science: Faculty Publications and Other Works

A paper describing a novel application development environment for working with large-scale scientific data sets.

[Introduction To] Mathematics Calculus Bc, John R. Hubbard, David R. Arterburn, Michael A. Perl

Bookshelf

This book gives you the tools to prepare effectively for the Advanced Placement Examination in Mathematics: Calculus BC. These tools include a concise topical review and six full-length practice tests. Our review succinctly covers areas considered most relevant to this exam. Following each of our tests is an answer key complete with detailed explanations designed to clarify the material for you.

Design, Implementation, And Evaluation Of Virtual Interface Architecture For Power Pc Machines, Ben Mckenzie

Inquiry: The University of Arkansas Undergraduate Research Journal

The Virtual Interface Architecture (VIA) standard is a low-latency protocol that was designed for use in high-performance networks. VIA improves performance by reducing overhead in messaging. This research has two components. The first part of this research project is the development of a new tool for measuring the performance of a VIA implementation and comparing it to the more traditional high-overhead protocols used on the Internet. The development of the tool represents a significant contribution in and of itself, since the tool has been put into the public domain and will likely become useful by Lima users, both for measuring …

Designing Electronic Casebooks That Talk Back: The Cato Program, Kevin D. Ashley

Articles

Electronic casebooks offer important benefits of flexibility in control of presentation, connectivity, and interactivity. These additional degrees of freedom, however, also threaten to overwhelm students. If casebook authors and instructors are to achieve their pedagogical goals, they will need new methods for guiding students. This paper presents three such methods developed in an intelligent tutoring environment for engaging students in legal role-playing, making abstract concepts explicit and manipulable, and supporting pedagogical dialogues. This environment is built around a program known as CATO, which employs artificial intelligence techniques to teach first-year law students how to make basic legal arguments with cases. …