Physical Sciences and Mathematics Commons^™

A Simulated Annealing/Tabu Search Algorithm For The Vehicle Routing Problem, Jeffrey Dale White, Billy E. Gillett

Computer Science Technical Reports

The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. …

Process Driven Software Engineering Environments, John Hayes Lampkin, T. Lo, Daniel C. St. Clair

Computer Science Technical Reports

Software development organizations have begun using Software Engineering Environments (SEEs) with the goal of enhancing the productivity of software developers and improving the quality of software products. The encompassing nature of a SEE means that it is typically very tightly coupled with the way an organization does business. To be most effective, the components of a SEE must be well integrated and the SEE itself must be integrated with the organization.

The challenge of tool integration increases considerably when the components of the environment come from different vendors and support varying degrees of “openness”. The challenge of integration with the …

Subsumption In Modal Logic, Dirk Heydtmann, Ralph W. Wilkerson

Computer Science Technical Reports

Subsumption has long been known as a technique to detect redundant clauses in the search space of automated deduction systems for classical first order logic. In recent years several automated deduction methods for non-classical modal logics have been developed. This thesis explores, how subsumption can be made to work in the context of these modal logic deduction methods.

Many modern modal logic deduction methods follow an indirect approach. They translate the modal sentences into some other target language, and then determine whether there exists a proof in that language, rather than doing deduction in the modal language itself. Consequently, subsumption …

The Difficulty Of Approximating The Chromatic Number For Random Composite Graphs, Jeffrey Wayne Jenness, Billy E. Gillett

Computer Science Technical Reports

Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are NP-complete and it is not known if efficient algorithms exist to solve these problems. Even approximation with guaranteed results can be just as difficult. Recently, many generalized search techniques have been developed to improve upon the solutions found by the heuristic algorithms.

This paper presents results for CGCP. In particular, exact and heuristic algorithms are presented and analyzed. This study is made, to …

A Syntax-Directed Editor For Borland’S Turbo Pascal, John Gatewood Ham, Thomas J. Sager

Computer Science Technical Reports

This study details the design and implementation of the LSD program, a syntax-directed editor for use in editing the source code for Borland’s Turbo Pascal. LSD is a dual-mode editor which allows both traditional text editing and also grammar-based editing. LSD promotes better programming for novice users by allowing the user to edit the program with a graphical representation of a parse tree. A list of syntactically correct choices is displayed at each point where a choice must be made in the structure of the program. Since only these choices are available, no syntax errors are possible. For more advanced …

Fault-Tolerant Ring Embeddings In Hypercubes -- A Reconfigurable Approach, Jun-Lin Liu, Bruce M. Mcmillin

Computer Science Technical Reports

We investigate the problem of designing reconfigurable embedding schemes for a fixed hypercube (without redundant processors and links). The fundamental idea for these schemes is to embed a basic network on the hypercube without fully utilizing the nodes on the hypercube. The remaining nodes can be used as spares to reconfigure the embeddings in case of faults. The result of this research shows that by carefully embedding the application graphs, the topological properties of the embedding can be preserved under fault conditions, and reconfiguration can be carried out efficiently.

In this dissertation, we choose the ring as the basic network …

Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis

Computer Science Technical Reports

In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in $O(\log^2 n)$ parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf $l$ of the tree is represented by rectangle $l_x \times l_y$ (the dimensions of which are part of the input). For …

Asynchronous Parallel Schemes: A Survey, Eric Jui-Lin Lu, Michael Gene Hilgers, Bruce M. Mcmillin

Computer Science Technical Reports

It is well known that synchronization and communication delays are the major sources of performance degradation of synchronous parallel algorithms. It has been shown that asynchronous implementations have the potential to reduce the overhead to minimum. This paper surveys the existing asynchronous schemes and the sufficient conditions for the convergence of the surveyed schemes. Some comparisons among these schemes are also presented.

On-Line And Dynamic Shortest Paths Through Graph Decompositions, Hristo N. Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis

Computer Science Technical Reports

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only $O(\log n)$ time, where $n$ is the number of vertices of the digraph. We also describe the first parallel algorithms for solving the dynamic version of the shortest path problem. Our …

Parallel Max Cut Approximations, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis

Computer Science Technical Reports

Given a graph with positive integer edge weights one may ask whether there exists an edge cut whose weight is bigger than a given number. This problem is NP-complete. We present here an approximation algorithm in NC which provides tight upper bounds to the proportion of edge cuts whose size is bigger than a given number. Our technique is based on the methods to convert randomized parallel algorithms into deterministic ones introduced by Karp and Wigderson. The basic idea of those methods is to replace an exponentially large sample space by one of polynomial size. In this work, we prove …

Using Temporal Subsumption For Developing Efficient Error-Detecting Distributed Algorithms, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Distributed algorithms can use executable assertions derived from program verification to detect errors at run-time. However, a complete verification proof outline contains a large number of assertions, and embedding all of them into the program to be checked at run-time would make error-detection very inefficient.

The technique of temporal subsumption examines the dependencies between the individual assertions along program execution paths. In contrast to classical subsumption, where all logical expressions to be examined are true simultaneously, an assertion need only be true when the corresponding statement in the distributed program has been executed. Thus, temporal subsumption based on the set …

A Run-Time Decision Procedure For Responsive Computing Systems, Grace Tsai, Matt Insall, Bruce M. Mcmillin

Computer Science Technical Reports

A responsive computing system is a hybrid of real-time, distributed and fault-tolerant systems. In such a system, severe consequences will occur if the logical and physical specifications of the system are not met. In this paper, we present a logic, Interval Temporal Logic (ITL), to specify responsive systems and give decision procedures to verify properties of the system at run-time as follows. First, we collect, during execution, events occurring in the system to represent a distributed computation. Next, we specify properties of the system using ITL formulas. Finally, we apply the decision procedures to determine satisfaction of the formulas. Thus, …

Comparative Study Of Louville And Symplectic Integrators, Daniel I. Okunbor

Computer Science Technical Reports

In this paper, we construct an integrator that conserves volume in phase space. We compare the results obtained using this method and a symplectic integrator. The results of our experiments do not reveal any superiority of the symplectic over strictly volume-preserving integrators. We also investigate the effect of numerically conserving energy in a numerical process by rescaling velocities to keep energy constant at every step. Our results for Henon-Heiles problem show that keeping energy constant in this way destroys ergodicity and forces the solution onto a periodic orbit.

Constructing An Interval Temporal Logic For Real-Time Systems, Grace Tsai, Matt Insall, Bruce M. Mcmillin

Computer Science Technical Reports

A real-time system is one that involves control of one or more physical devices with essential timing requirements. Examples of these systems are command and control systems, process control systems, flight control systems, and the space shuttle avionics systems. The characteristics of these systems are that severe consequences will occur if the logical and physical timing specifications of the systems are not met.

Formal specification and verification are among the techniques to achieve reliable software for real-time systems, in which testing may be impossible or too dangerous to perform. This paper presents a modal logic, Interval Temporal , built upon …

Wavelet Localization Of The Radon Transform, Tim Olson, Joe Destefano

Computer Science Technical Reports

In this paper we develop an algorithm which significantly reduces radiation exposure in x-ray tomography, when a local region of the body is to be imaged. The algorithm uses the properties of wavelets to essentially localize the Radon transform. The algorithm differs from previous algorithms for doing local tomography because it recovers an approximation to the original image, not the image modulo the nullspace of the local tomography operator, or the Lambda transform of the image. This is possible because we do not truly invert the interior Radon transform, but rather sample the Radon transform sparsely away from the local …

Implicit Methods On Parallel Processors, Larry Reeves

Computer Science Technical Reports

Since most partial differential equations (PDEs) do not have exact solutions, they are usually solved by some type of numerical method. Since a numerical method is commonly built from finite difference approximations derived from Taylor series expansions, such a development is derived. Stability and convergence of these methods is defined and the rate of convergence is defined and shown for a few simple methods. Of particular importance is the difference between implicit and explicit methods. Finally, the current applications and adaptations of implicit methods on parallel processors are examined and their strengths and weaknesses discussed.

Formal Model And Specification Of Deadlock, Pei-Yu Li, Bruce M. Mcmillin

Computer Science Technical Reports

In this paper, we present a formal model of deadlock in a distributed system and develop the deadlock specification in terms of time-dependent predicates. Primitive activities of processes in the distributed system are specified by the predicates so that system behaviors can be described by logic operations. With the formal model, we have an insight into the definition of deadlock in local views. A rigorous proof to show the equivalence of local-time and global-time deadlock specifications is presented. The local-time deadlock specification, which defines the timing of dependence between deadlocked processes, will be useful in the correctness verification of distributed …

Parallel Genetic Algorithm For The Dag Vertex Splitting Problem, Matthias Mayer

Computer Science Technical Reports

Directed Acyclic Graphs (DGAs) are often used to model circuits and networks. The path length in such DAGs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given maximum delay δ. The problem has been proven to be NP-hard. A sequential Genetic Algorithm has been developed to solve the DAG Vertex Splitting Problem. Unlike a standard Genetic Algorithm, this approach uses a variable chromosome length to represent the vertices that split …

Parallel Algorithm Fundamentals And Analysis, Bruce M. Mcmillin, Hanan Lutfiyya, Grace Tsai, Jun-Lin Liu

Computer Science Technical Reports

This session explores, through the use of formal methods, the “intuition” used in creating a parallel algorithm design and realizing this design on distributed memory hardware. The algorithm class NC and the LSTM machine are used to show why some algorithms realize their promise of speedup better than others and the algorithm class NP is used to show why other algorithms will never be good for parallelization. Performance and correctness through cooperative axiomatic reasoning and temporal reasoning provide an additional basis for understanding parallel algorithm design and specification. Finally, the realities of algorithm design are presented through partitioning and mapping …

Parallel Algorithm Fundamentals And Analysis, Bruce M. Mcmillin, Hanan Lutfiyya, Grace Tsai, Jun-Lin Liu

Computer Science Technical Reports

This session explores, through the use of formal methods, the “intuition” used in creating a parallel algorithm design and realizing this design on distributed memory hardware. The algorithm class NG and the LSTM machine are used to show why some algorithms realize their promise of speedup better than others and the algorithm class NP is used to show why other algorithms will never be good for parallelization. The realities of algorithm design are presented through partitioning and mapping issues and models. Finally, correctness through cooperative axiomatic reasoning provides an additional basis for understanding parallel algorithm design and specification and is …

X.500 Directory Service Support For Electronic Mail, Mihai G. Sirbu, Fikret ErçAl

Computer Science Technical Reports

One of the difficult problems on the Internet is finding the electronic mail addresses of users. In practice, there are some indirect ways of finding these addresses such as the finger program in UNIX, but almost all of these methods require the user to know the exact host name of the destination. What is most desirable is an automated mechanism which provides the e-mail addresses of users if some minimal information about the destination site is known.

This thesis describes the design of such a directory service support system, based on the X.500 Series of CCITT Recommendation, for the elm …

Genetic Algorithm With 3-Parent Uniform Crossover, L. Vincent Edmondson, Billy E. Gillett

Computer Science Technical Reports

A new genetic algorithm which uses a 3-parent uniform crossover operator is developed and analyzed. Uniform crossover operators are shown to be based on the premise that all bit-level genetic information should be passed from parents to children. The 3-parent uniform crossover operator is shown to adhere to this premise. The 3-parent uniform crossover operator is shown to be better than the 2-parent uniform crossover operator on the De Jong test functions.

Two new genetic algorithms which use 3-parent traditional crossover operators are developed and analyzed. The first uses a strategy of randomly selecting 3 of the 6 children resulting …

Operational Evaluation Of Responsiveness Properties, Grace Tsai, Matt Insall, Bruce M. Mcmillin

Computer Science Technical Reports

In this paper, a new technique for ensuring run-time satisfaction of properties-specifically responsiveness property, a subset of liveness property, in responsive systems, is presented. Since whether the run-time behavior of a system is satisfied depends on the execution (operational) environment, we develop a translation which takes into account the constraints in the operational environment, and generates histories for each process in the system. Thus, every process can utilize its history to operationally evaluate the system behavior and signal errors if its history is violated. Therefore, this technique provides software safety, handles error-detection, and ensures run-time satisfaction of responsiveness property in …

A General Method For Maximizing The Error-Detecting Ability Of Distributd Algorithms, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Error-detecting algorithms can determine when, at run time, a program deviates from its expected behavior due to a hardware, software or communication error. In a fixed interconnect multiprocessor system, the error detecting ability heavily depends on the number of faults, which is bounded, and their spatial distribution. Otherwise multiple fault occurrences can mask each other. This paper provides a general method for computing the overall system failure bound, the maximal fault index, from the system topology and local communication patterns. The result of the computation is used to design a mapping of processes to processor groups such that multiple processor …

Off-Line Cursive Handwriting Recognition Using Style Parameters, Berrin A. Yanikoglu, Peter A. Sandon

Computer Science Technical Reports

We present a system for recognizing off-line cursive English text, guided in part by global characteristics of the handwriting. A new method for finding the letter boundaries, based on minimizing a heuristic cost function, is introduced. The function is evaluated at each point along the baseline of the word to find the best possible segmentation points. The algorithm tries to find all the actual letter boundaries and as few additional ones as possible. After size and slant normalizations, the segments are classified by a one hidden layer feedforward neural network. The word recognition algorithm finds the segmentation points that are …

Throughput Of Existing Multiprocessor File Systems (An Informal Study), David Kotz

Computer Science Technical Reports

Fast file systems are critical for high-performance scientific computing, since many scientific applications have tremendous I/O requirements. Many parallel supercomputers have only recently obtained fully parallel I/O architectures and file systems, which are necessary for scalable I/O performance. Scalability aside, I show here that many systems lack sufficient absolute performance. I do this by surveying the performance reported in the literature, summarized in an informal table.

Diagnosis Of Malignant Melanoma Using A Neural Network, Anurag Chawla, Fikret ErçAl

Computer Science Technical Reports

Malignant melanoma is the deadliest form of all skin cancers. Approximately 32,000 new cases of malignant melanoma were diagnosed in 1991, with approximately 80 percent of patients expected to survive five years [1], Fortunately, if detected early, even malignant melanoma may be treated successfully. Thus, in recent years, there has been a rising interest in the automated detection and diagnosis of skin cancer, particularly malignant melanoma [2]. In this thesis, a novel neural network approach for the automated distinction of melanoma from three benign categories of tumors which exhibit melanoma-like characteristics is presented. The approach is based on devising new …

Cartographic Pattern Recognition Using Template Matching, Angela G. Lammers, Ralph W. Wilkerson, Fikret ErçAl

Computer Science Technical Reports

In creating digital maps from paper maps, the paper map must first be scanned to produce a raster image, and then converted into vector format. Vector format allows non-graphical cartographic information to be stored along with the graphical objects. At the United States Geological Survey, the conversion from raster to vector format is performed by a commercial software package. The package also attempts to classify the graphical objects based on shape, line patterns, and other information gained from the raster file. Since the package frequently fails to classify a significant percentage of the elements in the map, manual map analysis …

An Analysis Of Modern Cryptosystems, Thomas Gerald Sauder, Chung You Ho

Computer Science Technical Reports

Since the ancient Egyptian empire, man has searched for ways to protect information from getting into the wrong hands. Julius Caesar used a simple substitution cipher to protect secrets. During World War II, the Allies and the Axis had codes that they used to protect information. Now that we have computers at our disposal, the methods used to protect data in the past are ineffective. More recently, computer scientists and mathematicians have been working diligently to develop cryptosystems which will provide absolute security in a computing environment.

The three major cryptosystems in use today are DES, RSA, and the Knapsack …

Parallel Genetic Algorithms For The Dag Vertex Splitting Problem, Matthias Mayer, Fikret ErçAl

Computer Science Technical Reports

Directed Acyclic Graphs are often used to model circuits and networks. The path length in such Directed Acyclic Graphs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given δ. The problem has been proven to be NP-hard.

A Sequential Genetic Algorithm has been developed to solve the DAG Vertex Splitting Problem. Unlike a standard Genetic Algorithm, this approach uses a variable chromosome length to represent the vertices that split the …