Hadlock, Frank O.

There are several theorems which give the upper bounds on the number
of crossings of a graph in a plane. In this thesis we shall program certain heuristic
procedures for finding the layout of the graph with the fewest number of crossings.
We will then examine the output of these procedures to see if they always give us
a graph with the fewest number of crossings.

The object of this reaearch is to define and implement
an experimental language, Tutorial Programming Language
(TPL). Basic language concepts and definitions are introduced
initially to provide the background for defining TPL, which
is intended as a means to illustrate language concepts, and
has Type-3 grammar as a data type. A formal definition of
TPL is given in the form of an SLR(1) grammar. TPL is implemented by a syntax directed compiler and a
hypothetical machine for which the compiler provides code.
The machine is emulated by a Pascal program, making TPL
highly portable. It is also possible for the interested
user to enhance the power of TPL by writing more functions
for practical purposes.

A study was made on the feasibility of the syntactic
approach to the problem of hand printed character
recognition. The characters are represented as postfix expressions in
Picture Description Language. By comparing them with the
prototype expressions, each character is classified as the
prototype that is closest to it. Programs written in the Pascal language, which generate
the postfix expressions for the characters, and recognize
the characters, are presented.

A study was made of the problem of locating M facilities
on a connected grid graph, so that M is the minimum and so
that every demand node on the graph is within given distance
K of one of these M facilities. We call this problem briefly
the G(N,K,M) problem, with N denoting the total number
of demand nodes. An algorithm for solving this problem by using backtrack
technique is presented in this thesis. A heuristic algorithm
is also present; although the resulting M is not always minimum,
it tends to be near minimum. The advantage over the
backtrack algorithm is that the heuristic algorithm operates
very quickly. Algorithms represented in this thesis are programmed in
the Pascal language for the Univac 1100 computer at Florida
Atlantic University, Boca Raton, Florida.