Tech Reports in Computer Science and Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/5

The technical reports collections in this community are deposited by the Library of the Computer Science department. If you have questions about these collections, please contact library staff at library@cs.umd.edu

Browse

Now showing 1 - 20 of 1220

Hypothesis Testing with Errors in the Variables
(1995-02-06) David, Nancy; Stewart, G. W.
In this paper we give reason to hope that errors in regression variables are not as harmful as one might expect. Specifically, we will show that although the errors can change the values of the quantities one computes in a regression analysis, under certain conditions they leave the distributions of the quantities approximately unchanged.
An Iterative Method for Solving Linear Inequalities
(1995-02-06) Stewart, G. W.
This paper describes and analyzes a method for finding nontrivial solutions of the inequality $Ax \geq 0$, where $A$ is an $m \times n$ matrix of rank $n$. The method is based on the observation that a certain function $f$ has a unique minimum if and only if the inequality {\it fails to have} a nontrivial solution. Moreover, if there is a solution, an attempt to minimize $f$ will produce a sequence that will diverge in a direction that converges to a solution of the inequality. The technique can also be used to solve inhomogeneous inequalities and hence linear programming problems, although no claims are made about competitiveness with existing methods.
A Two-Stage Iteration for Solving Nearly Uncoupled Markov Chains
(1995-02-06) Stewart, G. W.; Stewart, W. J.; McAllister, D. F.
This paper is concerned with an iteration for determining the steady-state probability vector of a nearly uncoupled Markov Chain. The states of these chains can be partitioned into aggregates with low probabilities of transitions between aggregates. The iteration consists of alternating block Gauss--Seidel iterations with Rayleigh--Ritz refinements. Under natural regularity conditions, the composite iteration reduces the error by a factor proportional to the size of the coupling between aggregates, so that the more loosely the chain is coupled, the faster the convergence.
Invariant Subspaces and Capital Punishment (A Participatory Paper)
(1995-02-06) Stewart, G. W.
The notion of invariant subspaces is useful in a number of theoretical and practical applications. In this paper we give an elementary treatment of invariant subspaces that stresses their connection with simple eigenvalues and their eigenvectors.
A Study of File Manipulation by Novices Using Commands vs. Direct Manipulation
(1995-04-13) Margono, Sepeedeh; Shneiderman, Ben
There are three basic interactive styles of control in human interfaces with computers: command, menu, and direct manipulation. In the past few years, these three styles have become the subject of many studies. However, few comparisons have been done between interfaces that use direct manipulation and command styles. This experiment compares file manipulation operations on the Apple Macintosh, which has a direct manipulation interface, with the IBM PC with MS-DOS, which has the command interface. After a brief training period, novices accomplished file manipulation tasks more rapidly, with fewer errors and greater satisfaction with the Apple Macintosh. Problems arising for both versions are discussed and suggestions for improvements are made. (Also cross-referenced as CAR-TR-264)
Thinking takes time: a modal active-logic for reasoning in time
(1998-10-15) Nirkhe, Madhura; Kraus, Sarit; Perlis, Don
Most common sense reasoning formalisms do not account for the passage of time a s the reasoning occurs, and hence are inadequate from the point of view of modeling an agent's {\em ongoing} process of reasoning. We present a modal active-logic that treats time as a valuable resource that is consumed in each step of the agent's reasoning. We provide a sound and complete characterization for this logic and examine how it addresses the problem of logical omniscience. (Also cross-referenced as UMIACS-TR-94-39)
Load Balancing for Parallel Loops in Workstation Clusters
(1998-10-15) Kim, Tae-Hyung; Purtilo, James M.
Load imbalance is a serious impediment to achieving good performance in parallel processing. Global load balancing schemes are not adequately manage to balance parallel tasks generated from a single application. Dynamic loop scheduling methods are known to be useful in balancing parallel loops on shared-memory multiprocessor machines. However, their centralized nature causes a bottleneck for the relatively small number of processors in workstation clusters because of order-of-magnitude differences in communications overheads. Moreover, improvements of basic loop scheduling methods have not dealt effectively with irregularly distributed workloads in parallel loops, which commonly occur in applications for workstation clusters. In this paper, we present a new decentralized balancing method for parallel loops on workstation clusters. (Also cross-referenced as UMIACS-TR-96-6)
Verifying Systems with Integer Constraints and Boolean Predicates: A Composite Approach
(1998-10-15) Bultan, Tevfik; Gerber, Richard; League, Christopher
Symbolic model checking has proved highly successful for large finite-state systems, in which states can be compactly encoded using binary decision diagrams (BDDs) or their variants. The inherent limitation of this approach is that it cannot be applied to systems with an infinite number of states -- even those with a single unbounded integer. Alternatively, we recently proposed a model checker for integer-based systems that uses Presburger constraints as the underlying state representation. While this approach easily verified some subtle, infinite-state concurrency problems, it proved inefficient in its treatment of Boolean and (unordered) enumerated types -- which possess no natural mapping to the Euclidean coordinate space. In this paper we describe a model checker which combines the strengths of both approaches. We use a composite model, in which a formula's valuations are encoded in a mixed BDD-Presburger form, depending on the variables used. We demonstrate our technique's effectiveness on a nontrivial requirements specification, which includes a mixture of Booleans, integers and enumerated types. (Also cross-referenced as UMIACS-TR-97-62)
User Interface Reengineering: A Diagnostic Approach
(1998-10-15) Vanniamparampil, Ajit J.; Shneiderman, Ben; Plaisant, Catherine; Rose, Anne
User interface technology has advanced rapidly in recent years. Incorporating new developments in existing systems could result in substantial improvements in usability, thereby improving performance and user satisfaction, while shortening training an d reducing error rates. Our focus is on low-effort high-payoff improvements to aspects such as data display and entry, consistency, messages, documentation, and system access. This paper provides guidelines for managers and designers responsible for use r interface reengineering, based on the experience we gained from six projects, and compiles our observations, recommendations and outcomes. (Also cross-referenced as CAR-TR-767)
On the Perturbation of Schur Complements in Positive Semidefinite Matrices
(1998-10-15) Stewart, G. W.
This note gives perturbation bounds for the Schur complement of a positive definite matrix in a positive semidefinite matrix. (Also cross-referenced as UMIACS-TR-95-38)
Logic for a lifetime
(1998-10-15) Perlis, Don
There has been an explosion of formal work in commonsense reasoning in the past fifteen years, but almost no significant connection with work in building commonsense reasoning systems (cognitive or otherwise). We explore the reasons, and especially the ideal formal assumption of omniscience, reviewing and extending arguments that this is irreparably out of line with the needs of any real reasoning agent. On the other hand, this exploration reveals some desiderata that might still be given useful formal treatment, but with a somewhat altered set of aims from what has motivated most formal work. The discussion is motivated by several examples of commonsense reasoning, involving change of belief in addition to the more usual arguments concerning resource limitations. Key to the entire discussion is the notion that real reasoners do not usually have the luxury of isolated problems with well-defined beginnings and endings, but rather must deal with evolving and ongoing problems and situations. (Also cross-referenced as UMIACS-TR-94-62)
Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks
(1998-10-15) Dube, Rohit; Rais, Cynthia D.; Wang, Kuang-Yeh; Tripathi, Satish K.
Unlike static networks, ad-hoc networks have no spatial hierarchy and suffer from frequent link failures which prevent mobile hosts from using traditional routing schemes. Under these conditions, mobile hosts must find routes to destinations without the use of designated routers and also must dynamically adapt the routes to the current link conditions. This paper proposes a distributed adaptive routing protocol for finding and maintaining stable routes based on signal strength and location stability in an ad-hoc network and presents an architecture for its implementation. (Also cross-referenced as UMIACS-TR-96-34)
Neural Learning of Chaotic Dynamics: The Error Propagation Algorithm
(1998-10-15) Bakker, Rembrandt; Schouten, Jaap C.; Bleek, Cor M. van den; Giles, C. Lee
An algorithm is introduced that trains a neural network to identify chaotic dynamics from a single measured time-series. The algorithm has four special features: 1. The state of the system is extracted from the time-series using delays, followed by weighted Principal Component Analysis (PCA) data reduction. 2. The prediction model consists of both a linear model and a Multi- Layer-Perceptron (MLP). 3. The effective prediction horizon during training is user-adjustable due to error propagation: prediction errors are partially propagated to the next time step. 4. A criterion is monitored during training to select the model that as a chaotic attractor is most similar to the real system attractor. The algorithm is applied to laser data from the Santa Fe time-series competition (set A). The resulting model is not only useful for short-term predictions but it also generates time-series with similar chaotic characteristics as the measured data. _Also cross-referenced as UMIACS-TR-97-77)
A New Deterministic Parallel Sorting Algorithm With an Experimental Evaluation
(1998-10-15) Helman, David R.; JaJa, Joseph; Bader, David A.
We introduce a new deterministic parallel sorting algorithm based on the regular sampling approach. The algorithm uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. Moreover, unlike previous variations, our algorithm efficiently handles the presence of duplicate values without the overhead of tagging each element with a unique identifier. This algorithm was implemented in Split C, the IBM SP-2-WN, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the efficiency and scalability of our algorithm across different platforms. In fact, the performance compares closely to that of our random sample sort algorithm, which seems to outperform all similar algorithms known to the authors on these platforms. Together, their performance is nearly invariant over the set of input distributions, unlike previous efficient algorithms. However, unlike our randomized sorting algorithm, the performance and memory requirements of our regular sorting algorithm can be deterministically guaranteed. (Also cross-referenced as UMIACS-TR-96-54)
A Randomized Parallel Sorting Algorithm with an Experimental Study
(1998-10-15) Helman, David R.; Bader, David A.; JaJa, Joseph
Previous achemes for sorting on general-purpose parallel machines have had to choose betwen poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhard. Moeover, unlike precious variations, our algorithm efficiently handles the presence of duplicate values without the overhead of tagging each element with a unique identifier. The algorithm was implemented in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Cray Research T3D. We ran our code useing widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of input distributions unlike previous efficient algorithms. Our results also compare facorably with those reported for the simpler ranking problem posed by the NAS Integer Sorting (IS) Benchmark. (Also cross-referenced as UMIACS-TR-96-53)
Compiler Support for Real-Time Programs
(1998-10-15) Gerber, Richard; Hong, Seongsoo
We present a compiler-based approach to automatically assist in constructing real-time systems. In this approach, source programs are written in TCEL (or Time Constrained Event Language) which possesses high-level timing constructs, and whose semantics characterizes time-constrained relationships between observable events. A TCEL program infers only those timing constraints necessary to achieve real-time correctness, without over-constraining the system. We exploit this looser semantics to help transform programs to automatically achieve schedulability. In this article we present two such transformations. The first is trace-scheduling, which we use to achieve consistency between a program's worst-case execution time and its real-time requirements. The second is program-slicing, which we use to automatically tune application programs driven by rate-monotonic scheduling. (Also cross-referenced as UMIACS-TR-94-15)
A Parallel Sorting Algorithm With an Experimental Study
(1998-10-15) Helman, David R.; Bader, David A.; JaJa, Joseph
Previous schemes for sorting on general-purpose parallel machines have had to choose between poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. This algorithm was implemented in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Cray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results are consistent with the theoretical analysis and illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of input distributions unlike previous efficient algorithms. Our results also compare favorably with those reported for the simpler ranking problem posed by the NAS Integer Sorting (IS) Benchmark. (Also cross-referenced as UMIACS-TR-95-102)
Stepwise Assertional Design of Distance-Vector Routing Algorithms
(1998-10-15) Alaettinoglu, Cengiz; Shankar, A. Udaya
There are many kinds of distance-vector algorithms for adaptive routing in wide-area computer networks, ranging from the classical Distributed Bellman-Ford to several recent algorithms that have better performance. However, these algorithms have very complicated behaviors and their analyses in the literature has been incomplete (and operational). In this paper, we present a stepwise assertional design of a recently proposed distance-vector algorithm. Our design starts with the Distributed Bellman-Ford and goes through two intermediate algorithms. The properties established for each algorithm hold for the succeeding algorithms. The algorithms analyzed here are representative of various internetwork routing protocols. (Also cross-referenced as UMIACS-TR-92-39.1)
1993 Human-Computer Interaction Laboratory Video Reports
(1998-10-15) Plaisant, Catherine (Editor)
Introduction and table of contents - Ben Shneiderman, [4:00] Dynamaps: dynamic queries on a health statistics atlas - Catherine Plaisant and Vinit Jain, [6:34], Hierarchical visualization with Treemaps: making sense of pro basketball data - Dave Turo, [10:47], TreeViz: file directory browsing - Brian Johnson, [10:04], HyperCourseware: computer integrated tools in the AT&T Teaching Theater - Kent Norman, [7:08], Improving access to medical abstracts: Grateful Med Interface prototype - Gary Marchionini, [6:08], Layout appropriateness: guiding interface desi gn with simple task descriptions - Andrew Sears, [4:00] (Also cross-referenced as CAR-TR-793)
Digital Dynamic Telepathology -- the Virtual Microscope
(1998-10-15) Afework, Asmara; Beynon, Michael D.; Bustamante, Fabian; Demarzo, Angelo, M.D.; Ferreira, Renato; Miller, Robert, M.D.; Silberman, Mark, M.D.; Saltz, Joel, M.D., Ph.D.; Sussman, Alan, Ph.D.; Tsang, Hubert
The Virtual Microscope is being designed as an integrated computer hardware and software system that generates a highly realistic digital simulation of analog, mechanical light microscopy. We present our work over the past year in meeting the challenges in building such a system. The enhancements we made are discussed, as well as the planned future improvements. Performance results are provided that show that the system scales well, so that many clients can be adequately serviced by an appropriately configured data server. (Also cross-referenced as UMIACS-TR-98-23)