Digital Commons Network^™

Analyzing Regression Test Selection Techniques, Gregg Rothermel, Mary Jean Harrold

School of Computing: Faculty Publications

Regression testing is a necessary but expensive maintenance activity aimed at showing that code has not been adversely affected by changes. Regression test selection techniques reuse tests from an existing test suite to test a modified program. Many regression test selection techniques have been proposed; however, it is difficult to compare and evaluate these techniques because they have different goals. This paper outlines the issues relevant to regression test selection techniques, and uses these issues as the basis for a framework within which to evaluate the techniques. We illustrate the application of our framework by using it to evaluate existing …

On Integrating Existing Bibliographic Databases And Structured Databases, Ying Lu, Ee Peng Lim

Research Collection School Of Computing and Information Systems

It is widely accepted that future digital library applications have to be built upon different kinds of database servers to draw different forms of data from them. These data include bibliographic data, text data, multimedia data, and structured data. We address the problem of integrating existing bibliographic and structured databases which reside at different locations in the network. To integrate bibliographic data and structured data, we extended the well-known SQL model to represent bibliographic related attributes and queries. In particular, we have added a new data type to model attributes in the bibliographic database. We have also designed specialized predicates …

A Declarative Approach To Understanding Program Behavior Through Program Visualization, Aggie Yee-Chun Sun, Bruce M. Mcmillin

Computer Science Technical Reports

A method is proposed to analyze the behavior of sequential algorithms. Most current methodologies are in the form of semantic analysis, domain decomposition or fixed point approximation. These tools, though useful in design, verification and testing, are not general enough to characterize the behavior at run-time without the aid of a correct set of specifications. In addition, a thorough understanding of the program and of the mathematical notations are necessary to use these tools effectively. The methodology described in this thesis is a general purpose tool which addresses and alleviates the problem of having to be an applications expert by …

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time …

Mri On The Fly: Accelerating Mri Imaging Using Lda Classification With Ldb Feature Extraction, Y Joy Ko, Michael B. Taylor

Dartmouth College Undergraduate Theses

To improve MRI acquisition time, we explored the uses of linear discriminant analysis (LDA), and local discriminant bases (LDB) for the task of classifying MRI images using a minimal set of signal acquisitions. Our algorithm has both off-line and on-line components. The off-line component uses the k-basis algorithm to partition a set of training images (all from a particular region of a patient) into classes. For each class, we find a basis by applying the best basis algorithm on the images in that class. We keep these bases to be used by the on-line process. We then apply LDB to …

Efficient Heuristic Search Algorithms For Soft-Decision Decoding Of Linear Block Codes, Ching-Cheng Shih, C. R. Wulff, Carlos R.P. Hartmann, Chilukuri K. Mohan

Electrical Engineering and Computer Science - Technical Reports

This paper deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. In this paper we present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. This algorithm consists of three new decoding algorithms: M A*, H*, and Directed Search. It hybridizes these three algorithms to take advantage of their strengths and make the decoding more efficient. The first algorithm, M A*, is a modified Algorithm A* that conducts a heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search …

Neural Generalized Predictive Control For Real-Time Control, Donald I. Soloway

Electrical & Computer Engineering Theses & Dissertations

In this thesis a computationally efficient Generalized Predictive Control (GPC) algorithm is presented and implemented. The algorithm is more efficient than others because the number of iterations needed for convergence is significantly lower with Newton-Raphson. The main additional cost with Newton-Raphson algorithm is the calculation of the Hessian. This overhead is not a problem because of the reduced number of iterations, making the algorithm suitable for real-time control. For nonlinear control applications, a neural network is used as a dynamical system predictor leading to a Neural Generalized Predictive Control (NGPC) algorithm which is presented in detail in this thesis. An …

Exploring Knowledge Processes For Technology Assimilation, Rochelle K. Young

Engineering Management & Systems Engineering Theses & Dissertations

In the emerging knowledge society, the ability to make the experience and expertise of those involved in and affected by new technology unconditionally available to all members of an organization is becoming increasingly important. One of the problems in developing such knowledge processes for technology assimilation is that current social structures do not easily accommodate unconditional participation. Since the implementation of modern information technology is changing the workplace and the nature of work itself, alternative social structures are needed. This research takes as given that deep questions concerning knowledge processes and social transformation are in principle undecidable; and, only questions …

Greedy Algorithms For The Shortest Common Superstring That Are Asymptotically Optimal, Alan Frieze, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

A Last Word On Pattern Frequency Occurences In A Markovian Sequence?, Mireille Régnier, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Performance Evaluation Of Mpi Implementations And Mpi Based Parallel Ellpack Solvers, S. Markus, S. B. Kim, K. Pantazopoulos, A. L. Ocken, Elias N. Houstis, S. Weerawarana, D. Maharry

Department of Computer Science Technical Reports

No abstract provided.

Numerical Methods For Derivative Securities Models, Konstantinos N. Pantazopoulos, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

Measurement Of The Mass Of The Λb Baryon, Buskulic, D.; Et Al., M. Thulasidas

Research Collection School Of Computing and Information Systems

No abstract provided.

Concept Hierarchy Memory Model: A Neural Architecture For Conceptual Knowledge Representation, Learning, And Commonsense Reasoning, Ah-Hwee Tan, Hui-Shin Vivien Soon

Research Collection School Of Computing and Information Systems

This article introduces a neural network based cognitive architecture termed Concept Hierarchy Memory Model (CHMM) for conceptual knowledge representation and commonsense reasoning. CHMM is composed of two subnetworks: a Concept Formation Network (CFN), that acquires concepts based on their sensory representations; and a Concept Hierarchy Network (CHN), that encodes hierarchical relationships between concepts. Based on Adaptive Resonance Associative Map (ARAM), a supervised Adaptive Resonance Theory (ART) model, CHMM provides a systematic treatment for concept formation and organization of a concept hierarchy. Specifically, a concept can be learned by sampling activities across multiple sensory fields. By chunking relations between concepts as …

Libsearch: A Window-Based Frontend To Remote Bibliographic Databases On The Internet, Ee Peng Lim, Soo-Yin Cheng

Research Collection School Of Computing and Information Systems

Over the past several years, a number of wide-area information navigation and discovery tools have been introduced, including WAIS[1], Gopher[2], World-Wide Web[3], etc. In this paper, we describe a graphical query interface to remote bibliographic databases that can be found on the internet. A library query client, called LibSearch, has been designed and implemented using a set of APIs based on Z39.50 protocol standard[4]. Z39.50 is an application-layer protocol within the OSI reference model designed to allow library users to remotely access the bibliographic records in the library systems. As increasing number of OPAC systems are being established as Z39.50 …

Efficient String Matching Algorithms On Reconfigurable Mesh Architectures, His-Chieh Lee, Fikret Ercal

Computer Science Technical Reports

String matching problem received much attention over the years due to its importance in various applications such as text/file comparison, DNA sequencing, search engines, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of textual information presented on the world wide web and the research on DNA sequencing, this problem deserves special attention and any algorithmic or hardware improvements to speed up the process will benefit these important applications.

In this paper, we present three algorithms for string matching on reconfigurable mesh architectures. Given a text T of length n and a pattern P of …

Fast Algorithms For Maze Routing On An Rmesh, Fikret Ercal, H. C. Lee

Computer Science Technical Reports

The routing problem is one of the most widely studied problems in VLSI design. Mazerouting algorithms are used in VLSI routing and robot path planning. Efficiency of the parallel maze routing algorithms which were mostly based on Lee's algorithm is poor. In this paper, we propose time-efficient algorithms to solve the maze-routing problem on a reconfigurable mesh architecture. The constant-time algorithms presented include: (i) testing the existence of specific types of paths between two terminals, (ii) finding an absolute shortest path (ASP) and a shortest duplex-path (SDP). In addition, fast algorithms are presented for finding the shortest triplex-path (STP) and …

Run Time Security Evaluation For Distributed Applications, Cristina Serban, Bruce M. Mcmillin

Computer Science Technical Reports

Formal security specifications for a distributed application can be checked for compliance at run-time, during the execution of the application. We propose the RunTime Security Evaluation (RTSE) method which makes use of executable security assertions, histories/traces of events, and operational evaluation in the distributed environment to ensure the security specifications regarding the confidentiality and integrity requirements for the application are fulfilled at run-time. A model problem is used to aid in developing the security requirements formally, and assessment of the RTSE method is given based on the results obtained for the implementation of the model problem. The elements necessary for …

Scalability In Real-Time Systems, Ramesh Yerraballi

Computer Science Theses & Dissertations

The number and complexity of applications that run in real-time environments have posed demanding requirements on the part of the real-time system designer. It has now become important to accommodate the application complexity at early stages of the design cycle. Further, the stringent demands to guarantee task deadlines (particularly in a hard real-time environment, which is the assumed environment in this thesis) have motivated both practioners and researchers to look at ways to analyze systems prior to run-time. This thesis reports a new perspective to analyzing real-time systems that in addition to ascertaining the ability of a system to meet …

Visual Speech Recognition Using Multiple Deformable Lip Models, Devi Chandramohan

Electrical & Computer Engineering Theses & Dissertations

Motivated by the fact that human speech perception is a bimodal process (auditory and visual), several researchers have designed and implemented automatic speech recognition (ASR) systems consisting of both audio and visual subsystems, and shown improved performance relative to traditional purely auditory systems. Several visual speech reading approaches have used deformable templates to model the shape of a speaker's lips. Deformable templates are models of image objects, which can be deformed by adjusting a set of parameters to match the object in some optimal way, as defined by a cost function. Using a single deformable lip model has disadvantages such …

Ffts For The 2-Sphere-Improvements And Variations, D M. Healy, D Rockmore, Sean S.B. Moore

Computer Science Technical Reports

Earlier work by Driscoll and Healy has produced an efficient algorithm for computing the Fourier transform of band-limited functions on the 2-sphere. In this paper we present a reformulation and variation of the original algorithm which results in a greatly improved inverse transform, and consequent improved convolution algorithm for such functions. All require at most 0(N log2 N) operations where N is the number of sample points. We also address implementation considerations and give heuristics for allowing reliable floating point implementations of a slightly modified algorithm at little cost in either theoretical or actual performance. These claims are supported by …

On The Existence Of Schedules That Are Near-Optimal For Both Makespan And Total Weighted Completion Time, Cliff Stein, Joel Wein

Computer Science Technical Reports

We give a simple proof that, for any instance of a very general class of scheduling problems, there exists a schedule of makespan at most twice that of the optimal possible and of total weighted completion time at most twice that of the optimal possible. We then refine the analysis, yielding variants of this theorem with improved constants, and give some algorithmic consequences of the technique.

Needed Narrowing As The Computational Strategy Of Evaluable Functions In An Extension Of Goedel, Bobbi J. Barry

Dissertations and Theses

A programming language that combines the best aspects of both the functional and logic paradigms with a complete evaluation strategy has been a goal of a Portland State University project team for the last several years. I present the third in a series of modifications to the compiler of the logic programming language Goedel which reaches this goal. This enhancement of Goedel's compiler translates user-defined functions in the form of rewrite rules into code that performs evaluation of these functions by the strategy of needed narrowing. In addition, Goedel's mechanism that evaluates predicates is supplemented so that needed narrowing is …

Robust Optimization Using Training Set Evolution, Tony R. Martinez, Dan A. Ventura

Faculty Publications

Training Set Evolution is an eclectic optimization technique that combines evolutionary computation (EC) with neural networks (NN). The synthesis of EC with NN provides both initial unsupervised random exploration of the solution space as well as supervised generalization on those initial solutions. An assimilation of a large amount of data obtained over many simulations provides encouraging empirical evidence for the robustness of Evolutionary Training Sets as an optimization technique for feedback and control problems.

The Panda Array I/O Library On The Galley Parallel File System, Joel T. Thomas

Dartmouth College Undergraduate Theses

The Panda Array I/O library, created at the University of Illinois, Urbana-Champaign, was built especially to address the needs of high-performance scientific applications. I/O has been one of the most frustrating bottlenecks to high performance for quite some time, and the Panda project is an attempt to ameliorate this problem while still providing the user with a simple, high-level interface. The Galley File System, with its hierarchical structure of files and strided requests, is another attempt at addressing the performance problem. My project was to redesign the Panda Array library for use on the Galley file system. This project involved …

Object Oriented Scenes For Virtual Light, Jonathan A. Moore

Dartmouth College Undergraduate Theses

Ray tracing is one of many way to use a computer to generate an image. Ray tracers produce images by simulating light. Eliminating the details that might distract one from the interesting parts of ray tracing algorithms was purpose of my thesis project. The software I have written can be divide into three parts: the virtual frame buffer, the support classes and the ray tracing abstract base classes. The virtual frame buffer class, vfb, provides a simple means of rendering and studying the final image produced by a graphical algorithm. The support classes provide an elegant notation for the equations …

Implementation And Analysis Of Software Based Fault Isolation, Scott M. Silver

Dartmouth College Undergraduate Theses

Extensible applications rely upon user-supplied, untrusted modules to extend their functionality. To remain reliable, applications must isolate themselves from user modules. One method places each user module in a separate address space (process), which uses hardware virtual memory support to isolate the user process. Costly inter-process communication, however, prohibits frequent communication between the application and the untrusted module. We implemented and analyzed a software method for isolating an application from user modules. The technique uses a single address space. We provide a logical address space and per-module access to system resources for each module. Our software technique is a two-step …

Observer: An Approach For Query Processing In Global Information Systems Based On Interoperation Across Pre-Existing Ontologies, Eduardo Mena, Vipul Kashyap, Amit P. Sheth, Arantza Illarramendi

Kno.e.sis Publications

The huge number of autonomous and heterogeneous data repositories accessible on the “global information infrastructure” makes it impossible for users to be aware of the locations structure/organization, query languages and semantics of the data in various repositories. There is a critical need to complement current browsing, navigational and information retrieval techniques with a strategy that focuses on information content and semantics. In any strategy that focuses on information content, the most critical problem is that of different vocabularies used to describe similar information across domains. We discuss a scalable approach for vocabulary sharing. The objects in the repositories are represented …

Elimination Of All-Optical Cycles In Wavelength-Routed Optical Networks, Jason Iness, Byrav Ramamurthy, Biswanath Mukherjee, Krishna Bala

School of Computing: Faculty Publications

A transparent (wide-area) wavelength-routed optical network may be constructed by using wavelength cross-connect switches connected together by fiber to form an arbitrary mesh structure. The network is accessed through electronic stations that are attached to some of these cross-connects. These wavelength cross-connect switches have the property that they may configure themselves into unspecified states. Each input port of a switch is always connected to some output port of the switch whether or not such a connection is required for the purpose of information transfer. Due to the presence of these unspecified states, there exists the possibility of setting up unintended …

Technology And Business: The Missing Link, S Chandrasekar

IIMB Management Review

Technology, despite its critical importance to business, has far too often played a secondary role compared to other major management functions like marketing, finance, human resources development, production or corporate planning. The success of many US based technology driven companies in electronics and biotechnology in the seventies and early eighties and the Japanese and German economic miracles, driven largely by technology upgradation in specific targeted industries, should serve to renew interest in the study of the role of technology in improving business performance.