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 …

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.

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 …

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 …

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 …

The Interpolating Random Spline Cryptosystem And The Chaotic-Map Public-Key Cryptosystem, Fengi Hwu, Chung You Ho

Computer Science Technical Reports

The feasibility of implementing the interpolating cubic spline function as encryption and decryption transformations is presented. The encryption method can be viewed as computing a transposed polynomial. The main characteristic of the spline cryptosystem is that the domain and range of encryption are defined over real numbers, instead of the traditional integer numbers. Moreover, the spline cryptosystem can be implemented in terms of inexpensive multiplications and additions.

Using spline functions, a series of discontiguous spline segments can execute the modular arithmetic of the RSA system. The similarity of the RSA and spline functions within the integer domain is demonstrated. Furthermore, …

The Design, Analysis, And Implementation Of Parallel Simulated Annealing And Parallel Genetic Algorithms For The Composite Graph Coloring Problem, Brent S. Elmer, Billy E. Gillett

Computer Science Technical Reports

The composite graph coloring problem (CGCP) is similar to the standard graph coloring problem (SGCP). Associated with each vertex of a composite graph is a positive integer which represents the chromaticity of that vertex. This number is the number of consecutive integers (colors) which must be assigned to the vertex. The goal of the CGCP is to color the graph with as few colors as possible. The largest integer used in the coloring is called the chromatic number of the graph. The CGCP is proven to be NP-complete.

Exact, heuristic, and stochastic methods are analyzed and compared. Exact methods are …

Considerations For Rapidly Converging Genetic Algorithms Designed For Application To Problems With Expensive Evaluation Functions, Richard Patrick Rankin, Ralph W. Wilkerson

Computer Science Technical Reports

A genetic algorithm is a technique designed to search large problem spaces using the Darwinian concepts of evolution. Solution representations are treated as living organisms. The procedure attempts to evolve increasingly superior solutions. As in natural genetics, however, there is no guarantee that the optimum organism will be produced.

One of the problems in producing optimal organisms in a genetic algorithm is the difficulty of premature convergence. Premature convergence occurs when the organisms converge in similarity to a pattern which is sub-optimal, but insufficient genetic material is present to continue the search beyond this sub-optimal level, called a local maximum. …

Finding Fixed Point Combinators Using Prolog, Richard Rankin, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

A Powerful New Strategy, Called the Kernel Method, Has Been Developed by Larry Wos and William McCune at Argonne National Laboratories, to Study Various Fixed-Point Properties within Certain Classes of Applicative Systems. We Present a Very Simple Prolog Reasoning System, Named JIST, Which Incorporates Both Stages of the Kernel Method into a Single Unified Program. Furthermore, the Prolog Tool Has Been Extended to Run within a Distributed Environment using the Linda Protocol.

Dynamic Id3: A Symbolic Learning Algorithm For Many-Valued Attribute Domains, Roger Gallion, Chaman Sabharwal, Daniel C. St. Clair, William E. Bond

Computer Science Faculty Research & Creative Works

Quinlan's ID3 machine learning algorithm induces classification trees (rules) from a set of training examples. The algorithm is extremely effective when training examples are composed of attributes whose values are taken from small discrete domains. The classification accuracy of ID3-produced trees on domains whose attributes are many-valued tends to be marginal due to the large number of possible values which may be associated with each attribute. Attempts to solve this problem by a priori grouping of attribute values into distinct subsets has met with limited success. The dynamic ID3 algorithm improves the performance of ID3 on this type of problem …

A Hybrid Genetic Algorithm For An Np-Complete Problem With An Expensive Evaluation Function, Richard Rankin, Ralph W. Wilkerson, Geoff Harris, Jo Spring

Computer Science Faculty Research & Creative Works

In This Paper, a Non-Standard Hybrid Genetic Algorithm is Presented. the Approach is Non-Standard in that It Violates Some of the Common Attributes Associated with Genetic Algorithms in the Literature. the Algorithm Presented Uses Local Maxima to Locate the Global Maximum Value, Uses Haploid Chromosomes with Dominance Mating Instead of Crossover, Generates One Offspring Per Set of Parents, Has No Specific Mutation Operator, and is Designed for Rapid Convergence. When Applied to an NP-Complete Problem, the Results of This Hybrid Algorithm Are Shown to Be Very Successful in Reducing the Complexity of the Problem.