🚀 go-pugleaf

          Technical Report List File TRlist/tech.smu92A 

From dorothy@mickey Tue Apr  7 14:47:32 1992
Received: from seas.smu.edu by uxa.ecn.bgu.edu (5.65c/IDA-1.4.4)
	id AA00276; Tue, 7 Apr 1992 14:47:28 -0500
Received: by seas.smu.edu (/\==/\ Smail3.1.24.1 #24.1)
	id <m0lYM7d-000R0yC@seas.smu.edu>; Tue, 7 Apr 92 12:46 EDT
Received: by mickey (/\=-/\ Smail3.1.18.1 #18.1)
	id <m0lYM9L-0006RmC@mickey>; Tue, 7 Apr 92 12:48 PDT
Message-Id: <m0lYM9L-0006RmC@mickey>
Date: Tue, 7 Apr 92 12:48 PDT
From: dorothy@smunews.smu.edu (Dorothy Volk)
To: trlist@uxa.ecn.bgu.edu
Status: RO

\documentstyle{article}
\setlength{\topmargin}{-0.6in} %-0.3 before
\setlength{\oddsidemargin}{-0.1in}
\setlength{\footheight}{1.5in}
\setlength{\footskip}{0.5in}    %1.5 before
\setlength{\textheight}{9in}  %7.5 before
\setlength{\textwidth}{7in} %6.5 6.8 5

\begin{document}

\begin{center}
{\bf SOUTHERN METHODIST UNIVERSITY\\
Department of Computer Science and Engineering\\
Dallas, TX  75275-0122\\

\bigskip
Technical Report Announcement List\\
 January-December 1991}
\end{center}

Quantities are limited.  Postage has been included for Continental U.S.
Delivery only.  Please add an additional 20\% on all foreign orders.
Checks payable to Southern Methodist University.  Mail orders to:

\begin{center}
Technical Report Secretary\\
Department of Computer Science and Engineering\\
Southern Methodist University\\
Dallas, TX  75275-0122
\end{center}

(No charge to educational institutions with a reciprocal gratis 
agreement with exceptions of 91-10 and 91-15A \& 91-15B,
which have a reduced charge.)

\pagebreak

\noindent {\bf 91-CSE-1.  (\$1.75)}
\begin{center}
{\bf The Singly Constrained Assignment Problem*}\\
Jeffery L. Kennington and Farin Mohammadi
\end{center}

This manuscript presents new heuristic algorithms to find near optimal
integer solutions for the singly constrained assignment problem.  The
methods are based on Lagrangean duality theory and involve solving a 
series of pure assignment problems.  The software implementation of these
heuristics successfully solved problems having one-half million binary
variables (assignment arcs) in less than fifteen minutes of wall clock
time on a Sequent Symmetry S81 using a single processor.  In no case
did our heuristics fail to obtain a feasible integer solution guaranteed
to be within 10\% of an optimum.  In computational comparisons with MPSX and
OSL on an IBM 3081D, the specialized software was from one hundred to one
thousand times faster.  Our software proved to be very 
robust as well as fast.  The robustness is due to elaborate scheme used to
update the Lagrangean multipliers and the speed is due to the fine code used
to solve the pure assignment problems.
\newline-------
\newline
*This research was supported in part by the Air Force Office of Scientific 
Research under Contract Number AFSOR 91-0028, and the Office of Naval
Research under Contract Number N00014-87-K-0223.

\bigskip
\noindent {\bf 91-CSE-5.  (\$1.00)}
\begin{center}
{\bf A Distribution-Free Upper Bound on the Expected Payoff of the
Maximum of Two Risky Assets}\\
Jos\'{e} Dul\'{a} and Guangping Zhang
\end{center}

We introduce an upper bound on the expected payoff of a complex European call
option on the maximum of two underlying risky assets.  The bound is 
distribution-free in the sense that the only information required is the 
expected value of the commodities at maturity along with the sum of the two
variances.  Moreover, under special circumstances, it is the best upper
bound if the only information available are these expected values and sum of
variances.  It is not necessary to assume independence between the price of
the two assets.  Implementation is immediate since the bound has a simple
closed form analytical formula.  Tests indicate that the bound performs well
especially under low variance values.

\bigskip
\noindent {\bf 91-CSE-6.  (\$1.00)}
\begin{center}
{\bf S12 User's Guide}\\
Richard V. Helgason, Jeffery L. Kennington, Douglas Stewart
\end{center}

S12 is a FORTRAN code that solves the one-to-one shortest path problem.
It is based on two algorithms, Nicholson's two-tree Dijkstra algorithm
(1966) and Dial's algorithm (1969) as implemented by Dial, Glover, Karney,
and Klingman (1979).

\bigskip
\noindent {\bf 91-CSE-7.  (\$1.25)}
\begin{center}
{\bf Peaceful Queens and Magic Squares}\\
O. Demirors and Murat M. Tanik
\end{center}

Peaceful queens problem (PQP) is to place N chess queens on an $N \times N$
board in such a way that no queen can attack any other queen.  A solution
of PDP is a $N \times N$ board configuration in which N chess queens are not
able to attack each other.  A magic square is a $N \times N$ square matrix 
of $N^2$ numbers arranged so that the summation of the N numbers on each
row and on each column are the same.  Both problems have practical
applications in Computer Science and Electrical Engineering, like
obtaining deadlock free paths [Tanik, 1978] and image reproduction
[Ollerenshaw, 1985].  At first glance these two problems seem quite
different but it can be observed that both are problems of arranging objects
on a square with restrictions concerning rows and columns.  In this report
we will demonstrate the relations between these problems.  We will introduce
a method to obtain solutions of PQP from a special magic square and we will
present a method to construct a magic square from a solution of PQP.  In
addition, we will discuss invariant peaceful queen solutions and demonstrate
forming magic rectangles from these invariant solutions.

\pagebreak
\noindent {\bf 91-CSE-8.  (\$8.00)}
\begin{center}
{\bf N-Queens Problem and Its Algorithms}\\
Cengiz Erba\c{s} and Murat M. Tanik
\end{center}

N-Queens problem, originally introduced as 8-Queens problem has been studied
for more than a century.  Ever since 1850, the problem attracted the attention
of several famous mathematicians including Gauss and Polya.  Various
approaches have been used to solve this problem.  Recently, a number of
algorithms have been developed.  The focus of this paper is the algorithms
related to the N-Queens problem.

\bigskip
\noindent {\bf 91-CSE-9.  (\$2.25)}
\begin{center}
{\bf A Specification Experience: Dual Drilling Supply System Built with
MicroSTEP}\\
David J. Key and Murat M. Tanik
\end{center}

Dual Drilling Company is primarily engaged in leasing oil rights and operating
offshore oil drilling platforms in several foreign locations.  Headquartered
in Dallas, Texas, the company does not employ personnel with training to write
computer software.  Dual Drilling became aware of a program offered by 
Southern Methodist University whereby a student solves a business computer
problem as part of a class project.  One such problem was the supply system
used by the company.

\bigskip
\noindent {\bf 91-CSE-10.  (\$9.50 - \$3.50 to reciprocal universities)}
\begin{center}
{\bf Application Development with MicroSTEP: Member Information
System}\\
Kersasp D. Shedhdar, Ismail Bayraktar, Murat M. Tanik
\end{center}

This report is not a MicroSTEP tutorial.  It assumes familiarity with the
essentials of this CASE tool.  The application presented in this report,
Member Information System, is a refinement of an earlier prototype which
had several shortcomings.  In the current version, we have made numerous
improvements, however, some odd design decisions remain.  The future 
improvements should bring the application closer to the original 
specifications and refine it further.  For this purpose we have included
a ``Critique and Suggestions'' section.

\bigskip
\noindent {\bf 91-CSE-13. (\$1.25)}
\begin{center}
{\bf Improved Algorithms for Two Dimensional Grid Routing}\\
Dinesh Bhatia, Tom Leighton,* Fillia Makedon**
\end{center}

This paper addresses the problem of routing two terminal nets on a two
dimensional $N \times N$ grid.  Each net length is bounded by $k$, where
$k$ is a small constant or a small function of $N (k \ll N)$.  Tight
bounds for the worst case channel width needed to route on an $N \times N$
two dimensional grid are shown.  In addition, we show a polynomial time
solution to the routing problem that achieves a channel width of
$OPT+O(log^2 k)$.  We also extend our work to find better solutions for 
routing on a two dimensional $N \times N$ grid without any restriction on
the length of the net.  Our results are deterministic and perform better
than previous work on the similar problem.
\newline-------
\newline
Institute of Technology, Cambridge, MA 02139.\\
**Computer Science Program, University of Texas at Dallas, PO Box 0688,
MS: MP 3.1, Richardson, TX 75083.
  
\pagebreak
\noindent {\bf 91-CSE-14.  (\$1.00)}
\begin{center}
{\bf Enhancing Incomplete Policy Research Databases Via Fuzzy
Record Matching*}\\
Richard S. Barr,{ Betty L. Hickman,\dag} J. Scott Turner\ddag 
\end{center}

This paper explores a procedure for extending a research database obtained by
sampling from a large population.  One approach to enhancing such a dataset
is to map its member observations to members of a second dataset containing
the desired variables, a procedure sometimes referred to as microdata {\it
merging} or {\it record matching}.  A mapping function is used to compare
members based on common attributes to guide the choice of mated pairs, with
the objective of finding an overall best match.  When an exact 
one-for-one match cannot be established, the mapping function is used to 
mate ``similar'' records.

We present a model to identify the optimal mapping, given a pairwise 
mapping function that yields either crisp or triangular fuzzy numbers.
The structure of the model is that of a large-scale network problem.
We describe this approach's application, with ordinary numbers, in
microsimulation models at the U.S. Department of the Treasury, and show
extensions reflecting the inherent uncertainties in non-exact matching.
\newline-------
\newline
*Prepared for the North American Fuzzy Information Processing Society 1991
Workshop, Columbia, MO.\\
\dag Dept of Mathematics and Computer Science, University of Nebraska,
Omaha, NE.\\
\ddag College of Business Administration, Oklahoma State University, 
Stillwater, OK. 

\bigskip
\noindent {\bf 91-CSE-15A.  (\$15.00 -- \$7.50 to reciprocal universities)}
\begin{center}
{\bf Advanced Programming Techniques in Turbo Pascal\\
(Includes Object Oriented Programming with Version 5.5)}\\
Murat M. Tanik, Kyle Townsend\\
Southern Methodist University\\
Udo W. Pooch\\
Texas A\&M University
\end{center}

Generally, this book is for people who already have some Turbo Pascal
programming experience and who want to learn more.  We have tried to look
back on our past experiences with Turbo Pascal, pick out the things that
really proved elusive, like working with sets, manipulating linked lists,
sorting information, and doing snazzy graphics, then write a cohesive book
about how to solve these types of problems.  We reiterate fundamentals
along the way.  If you are a programmer with experience in some other
procedural language, such as {\bf C}, you should be able to learn
Turbo Pascal from this book.  We differentiate ourselves from other
Turbo Pascal books in that our emphasis is concentrated on the more
difficult concepts embodied in Turbo Pascal and on algorithms which the
beginner programmer would be unlikely to employ.

\bigskip
\noindent{\bf 91-CSE-15B.  (\$20.00 -- \$10.00 to reciprocal universities)}
\begin{center}
{\bf Advanced Programming Techniques in Turbo Pascal\\
(Programs and Sample Executions)}\\
Murat M. Tanik, Kyle Townsend\\
Southern Methodist University\\
Udo W. Pooch\\
Texas A\&M University
\end{center}

\pagebreak
\noindent{\bf 91-CSE-16.  (\$1.75)}
\begin{center} 
{\bf Effective Memory Access Time in a Hierarchical Memory Organization}\\
Jen-Tien Yen, Milan Milenkovic,* Behrooz Shirazi**
\end{center}

{\it Effective memory access time} is the average time a processor needs
to wait from the time of issuing an address of an item (instruction or
data) until the time the desired item is returned to the processor from
the memory hierarchy.  It is determined by two main factors: address
translation and memory access times.  In literature when calculating the
effective memory access time, emphasis is put on the latter factor, while
neglecting the former one.  In this paper, we attempt to give a more 
complete measure of the effective memory access time by including both
the address translation and memory access times in our calculations.
The analysis we present comprises two major memory designs in a single-cache,
uniprocessor environment:  (1) address translation needs to be done before 
the cache access, and (2) address translation is only necessary when the
cache lookup fails.  In addition to this analysis, we present a detailed
discussion of the parameters which affect both address translation time
and memory access time.  Finally, the proposed effective memory access times
are used to compare and evaluate these two memory designs.
\newline-------
\newline
* IBM Corporation, P.O. Box 1328, M.S. 5226, Boca Raton, FL 33429-1328.
\newline
**University of Texas at Arlington, Department of Computer Science
Engineering, Box 19015, Arlington, TX\\ 76019-0015.

\bigskip
\noindent{\bf 91-CSE-17.  (\$1.75)}
\begin{center}
{\bf A Combined Cache Management and Address Translation Model}\\
Jen-Tien Yen and Behrooz Shirazi*
\end{center}

In this paper we first introduce a new, combined Cache Management and
Address Translation (CMAT) model, which utilizes the working set algorithm
as the cache replacement policy.  The model also incorporates the address
translation scheme into the cache management model so that two operations can 
be done at the same time.  This method reduces the effective memory access
time and simplifies the address translation as well as alleviating cache
intrinsic and extrinsic interference problems.  A dedicated hardware and
coprocessor is employed in this model to efficiently control the management
of the cache blocks and the main memory pages in a uniform fashion. 

Using a trace-driven simulation, the performance of the CMAT is compared
against the conventional cache management techniques using fully 
associative, set associative and direct mapping as the cache management 
policies.  Both single and multiple programming environment traces are used.
The simulation results show that the CMAT model has a better performance
in terms of cache miss ratio, effective memory access time, and good
utilization of the limited cache space, compared to the conventional 
approaches. 
\newline-------
\newline
*University of Texas at Arlington, Department of Computer Science 
Engineering, Box 19015, Arlington, TX\\  76019-0015.

\bigskip
\noindent
{\bf 91-CSE-18.  (\$4.00)}
\begin{center}
{\bf Implementing Specifications with Building Blocks: Insurance Tracking
System}\\
Ismail Bayraktar and Murat M. Tanik
\end{center}

Our purpose in this report is to show how to define specifications in
MicroSTEP.  We assume that you are already familiar with MicroSTEP's user
interface and basics.  Our previous technical report will provide sufficient
information to learn fundamentals [1,5,6].  You can learn more from MicroSTEP
manuals [2,3,4].

We used an insurance tracking system application as an example throughout
the report.  A new concept has been introduced in each chapter.  Every
chapter has five sections.  First section expresses general concept,
example from insurance tracking system and MicroSTEP features used in the
example which are specified as GENERAL, EXAMPLE and FEATURES.  We outline
the STEPS to give insights for defining a specification.  The underlined
portion in every step gives simple English definition of the specification,
the italic portion gives the details for defining the specification in 
MicroSTEP.  The second, third, fourth and fifth sections are flow diagram,
structure, format and activity to show how to define the specification in 
MicroSTEP.  When we described a portion of FEATURES in the chapter, we
emphasized it in bold so that if you just want to know how and when to 
use the feature, you can easily and quickly find it.

\pagebreak
\noindent{\bf 91-CSE-19.  (\$7.50)}
\begin{center}
{\bf Rule Based Expert Systems:  A PC+ Experience}\\
E. Demirors, C. Erba\c{s}, M. Kayaalp, O. Demirors, U. Tanik, M.M. Tanik
\end{center}

Personal Consultant Plus (PC+) is one of the commercially available expert
system shells which provide a user friendly environment on IBM compatible
personal computers.  This study gathers the experience gained during the
studies carried out by our group on using PC+ as an experimental tool in
different types of problems.  Before discussing the applications created, 
a brief introduction to expert systems and their fundamental principles
is given.  In addition, a summary of PC+ features and commands, which can
be used as a quick reference to the system, and detailed analysis of the
applications developed are provided.

\bigskip
\noindent{\bf 91-CSE-20.  (\$1.75)}
\begin{center}
{\bf On Reporting the Speedup of Parallel Algorithms: A Survey of Issues and
Experts}\\
Richard S. Barr and Betty L. Hickman*
\end{center}
Perhaps the most commonly used performance measure for implementations of
parallel algorithms is {\it speedup}, a ratio of the serial to parallel
solution time for a given problem.  We probe the difficulties in using this
statistic for computational reporting, including:  definitional ambiguities,
testing biases, machine influence, and the effects of tuning parameters.
Some of these difficulties were explored further in a survey sent to leading
computational mathematical programming researchers for their reactions and
suggestions.  A summary of the survey and proposals for conscientious
reporting are presented.
\newline-------
\newline
*Dept of Mathematics and Computer Science, University of Nebraska,
Omaha, NE 68182.\\Internet: hickman@zeus.unomaha.edu 

\bigskip
\noindent {\bf 91-CSE-21.  (\$6.50)}
\begin {center}
{\bf N-Queens Problem and Its Connections to the Polygons}\\
Cengiz Erba\c{s} and Murat M. Tanik
\end{center}

The purpose of this paper is to show the connections between the N-Queens
problem and polygons, each of which were studied by famous mathematicians such
as Kepler, Gauss, and Polya.  Before demonstrating the connections, the
definitions related to polygons are given from the geometrical point of
view.  Among different types of polygons, uniform polygons, which includes
the generalized regular polygons and regular compound polygons, are taken
as the focus.

Both polygons and the N-Queens solutions can be represented by permutations.
Two different mappings between permutations and polygons are presented, one
from stellated polygons, and one from uniform polygons.  Circulant matrices
are shown to be a useful tool for the representation of polygons.  The 
linear congruence representation of generalized regular polygons are given.

The connections between star polygons and the N-Queens problem are
given.  It is shown that if positive integer $N = 1 + 6 \alpha$, or
$N = 5 + 6 \alpha$, then some of the solutions of the N-Queens problem can be
generated by means of star polygons.

The connections between regular compound polygons and the N-Queens problem
are demonstrated.  If $N = 6 \alpha$, or $N = 4 + 6 \alpha$, there are 
regular compound polygons that provide a solution to the N-Queens problem.
The correspondence between the solutions obtained from star polygons and
the solutions obtained from compound polygons are demonstrated.
\pagebreak

\noindent{\bf 91-CSE-24.  (\$7.50)}
\begin{center}
{\bf Catalogue for the Solutions of the N-Queens Problem}\\
A. Chandy, W. Hafiz, T.A. Donald, C. Erba\c{s}, M.M. Tanik
\end{center}

Chapter 1 - Statistics (1.1-The Number of Solutions and the Run-Time
Statistics; 1.2-Starting Row Number Statistics; 1.3-Queen Distribution
Statistics; 1.4-Queen Distribution Statistics (modulo N)).

Chapter 2 - Stellated Polygon Representation (2.1-Grouped According to the
Board Rotations; 2.2-Grouped According to the Polygon Rotations).

Chapter 3 - Solution Listing.

\bigskip
\noindent{\bf 91-CSE-25.  (\$1.75)}
\begin{center}
{\bf Magic Squares Constructed by the Uniform Step Method\\
 Provide Solutions
to the N-Queens Problem}\\
Cengiz Erba\c{s}, Nader Rafraf, Murat M. Tanik
\end{center}

We analyzed the connections between the N-Queens problem and magic squares
constructed using uniform step method.  After demonstrating how to 
decompose a magic square constructed by the uniform step method into two
orthogonal latin squares, we demonstrated that rows, columns, positive and
negative diagonals of those latin squares can be used to generate solutions to
the N-Queens problem.

\bigskip
\noindent{\bf 91-CSE-26.  (\$1.00)}
\begin{center}
{\bf Concurrency Control for Data and Procedures*}\\
Margaret H. Eich and Priti Mishra
\end{center}

Two of the features of Object Oriented Databases (OODB) are the encapsulation
of data and procedures and the sharing of procedures between classes.  This
paper argues for a unified data/procedure level concurrency control approach
in OODB systems.  Examples are included which motivate this idea by 
identifying problems encountered if an OODB system does not coordinate
access (read/write/execute) to methods.  A solution, Execute Locking, to 
this OODB concurrency control is proposed.  One of the novel features of 
this technique is procedure level nesting using {\it Primitive Executable
Objects}.

\noindent
-------\\
*This material is based in part upon work supported by the Texas Advanced
Research Program (Advanced Technology Program) under Grant No. 2265 and by
the National Science Foundation under Grant No. IRI-8713654.

\bigskip
\noindent{\bf 91-CSE-29.  (\$1.00)}
\begin{center}
{\bf Functional Completeness in Object-Oriented Databases}\\
Priti Mishra and Margaret H. Eich
\end{center}

A definition of completeness in the context of Object Oriented Databases 
(OODBs) is proposed in this paper.  It takes into account the existence of
various categories of functions in OODBs, each of which must be complete in
itself.  The functionality of an OODB can be divided into sets of related
functions.  For example, functions needed to perform all schema evolution
operations or all version management operations belong in two distinct sets.
Further, each set of functions must include all functions needed to perform
all operations defined for that set.  Thus, for an OODB to be functionally
complete, it must support a certain number of sets (or categories) of 
functions and each such set must be complete in itself.  The purpose of 
this paper is not to give a precise definition of the categories of
functions but rather to define a framework within which such categories
should be examined.

\pagebreak
\noindent{\bf 91-CSE-30.  (\$2.25)}
\begin{center}
{\bf DARMS Component Developer Domain Environment Construction and Installation
Manual\\
Version 1.1}\\
S.N. Delcambre and M.M. Tanik
\end{center}

Application software development in DARMS can be customized by establishing
an environment specific to a problem domain.  This document describes those
activities required to construct a problem domain environment for use in the 
DARMS programming environment.  Topics covered include constructing
transformable components and defining an attribute hierarchy and browser
directories.  Installation of these constructs into the DARMS environment is
also described.

\bigskip
\noindent{\bf 91-CSE-31.  (\$1.75)}
\begin{center}
{\bf Algorithmic and Constructive Approaches to the N-Queens Problem}\\
Cengiz Erba\c{s}, Seyed Sarkeshik, Murat M. Tanik
\end{center}

The N-Queens problem is a commonly used example in computer science.  There
are numerous approaches proposed to solve the problem.  The objective of this
paper is to present a comprehensive survey of the various algorithmic and
constructive approaches to the N-Queens problem.  After introducing several
definitions of the problem, the group property of the problem is discussed,
and the concepts of fundamental and isomorphic solutions are described.
The algorithms are grouped into three categories: generating all solutions,
generating fundamental solutions, and generating some solutions.  The 
constructive approaches capable of generating some solutions for every N
are surveyed.  Other interesting relationships between N-Queens problem and
other problems are also discussed. 

\bigskip
\noindent {\bf 91-CSE-32.  (\$5.75)}
\begin{center}
{\bf A Case Study in MicroSTEP HITS\\
(Hospital Inventory Tracking System)}\\
Robert M. Bender, Jr., Thomas L. Reeck, Ismail Bayraktar, Murat M. Tanik
\end{center}

The objective of this project is to create a software solution for the
current inventory tracking system at Mother Frances Hospital in Tyler,
Texas.  This software program will be used to track medical equipment, 
mainly IMED-PCs, used by patients on a day-to-day billing basis.  This will
replace the current inventory system which relies heavily on updated and
accurate paperwork.  Simply stated, a computerized system is needed because
manual tracking is prone to human error and some records may fail to be
updated at the proper time.  By computerizing the inventory tracking system,
the required paperwork will be reduced to a minimum in addition to reducing
the time expenditures associated with manually updating the paperwork,
thus contributing to an increase in overall productivity.

\bigskip
\noindent {\bf 91-CSE-33.  (\$2.75)}
\begin{center}
{\bf A Data-Driven Processor Architecture For Real-Time Computing}\\
William G. Farquhar and Paraskevas Evripidou
\end{center}

Future real-time systems are expected to require processing and throughput
rates at supercomputer levels of performance.  This paper presents the 
design of a data-driven processor architecture, designated as the DART
processor, that specifically addresses the requirements of high performance
real-time computing.  The basic dataflow principle of execution, 
{\it execution-upon-data-availability,} is utilized to permit large-scale
multiprocessing and programming ease.  While dataflow principles offer
specific advantages to multiprocessing, they do not adequately support the
requirements of high performance real-time applications.  The DART design
philosophy is to modify the basic dataflow model to overcome these 
limitations.  The design specifically implements hardware mechanisms to 
schedule processes on a pre-emptive priority-driven basis, minimize the 
``critical path'' scheduling overhead and provide fast interrupt response
times.  The DART processor is designed to be the key building block in a
multiprocessor system that is suitable for a wide variety of high performance 
real-time applications. 

\end{document}