A tree $t$-spanner $T$ of a simple graph $G$ is a spanning tree of $G$, such that for every pair of vertices of $G$ their distance in $T$ is at most $t$ times their distance in $G$, where $t$ is called a stretch factor of $T$ in $G$. It has been shown that there is a linear time algorithm to find a tree 2-spanner in a graph; it has also been proved that, for each $t>3$, determining whether a graph admits a tree $t$-spanner is an NP-complete problem. This thesis studies tree $t$-spanners from both theoretical and algorithmic perspectives. In particular, it is proved that a nontree graph admits a unique tree $t$-spanner for at most one value of stretch factor $t$. As a corollary, a nontree bipartite graph cannot admit a unique tree $t$-spanner for any $t$. But, for each $t$, there are infinitely many nontree graphs that admit exactly one tree $t$-spanner. Furthermore, for each $t$, let U($t$) be the set of graphs being the union of two tree $t$-spanners of a graph. Although graphs in U(2) do not have cycles of length greater than 4, graphs in U(3) may contain cycles of arbitrary length. It turns out that any even cycle is an induced subgraph of a graph in U(3), while no graph in U(3) contains an induced odd cycle other than a triangle; graphs in U(3) are shown to be perfect. Also, properties of induced even cycles of graphs in U(3) are presented. For each $t>3$, though, graphs in U($t$) may contain induced odd cycles of any length. Moreover, there is an efficient algorithm to recognize graphs that admit a tree 3-spanner of diameter at most 4, while it is proved that, for each $t>3$, determining whether a graph admits a tree $t$-spanner of diameter at most $t+1$ is an NP-complete problem. It is not known if it is hard to recognize graphs that admit a tree 3-spanner of general diameter; however integer programming is employed to provide certificates of tree 3-spanner inadmissibility for a family of graphs.

Modern smartphone operating systems (OSs) have been developed with a greater emphasis on security and protecting privacy. One of the security mechanisms these systems use is permission system. We perform an analysis of the Android permission system in an attempt to begin answering some of the questions that have arisen about its design and implementation. We developed PScout, a tool that extracts the permission specification from the Android OS source code using static analysis and analyzed 5 versions of Android spanning version 2.2 up to the recently released Android 4.1. Our main findings are that while there is little redundancy in the permission specification, if applications could be constrained to only use documented APIs, then about 18-26% of the non-system permissions can be hidden. Finally, we find that a trade-off exists between enabling least-privilege security with fine-grained permissions and maintaining stability of the permission specification as the Android OS evolves.

Application-layer overlay networks have emerged as a powerful paradigm for providing network services. While most approaches focus on providing a pre-defined set of network services, we provide a mechanism for network applications to deploy customizable data delivery services. We present the design, implementation, and evaluation of application-defined data delivery services that are executed at overlay nodes by transmitting messages marked with service identifiers. In our approach, a data delivery services is specified as an XML specification that define a finite-state machines that respond to network events, and perform a set of network primitives. We implemented a mechanism to execute these XML specifications in the HyperCast overlay middleware, and have evaluated this mechanism quantitatively on an Emulab testbed. The experiments show that our approach is effective in realizing a variety of data delivery services without incurring unreasonable performance overhead.

A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is non-computable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the n-th step, the algorithm produces four main output files: all halting strings, looping strings, run-time errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or run-time error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.

A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is non-computable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the n-th step, the algorithm produces four main output files: all halting strings, looping strings, run-time errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or run-time error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.

A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is non-computable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the n-th step, the algorithm produces four main output files: all halting strings, looping strings, run-time errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or run-time error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.

A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is non-computable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the n-th step, the algorithm produces four main output files: all halting strings, looping strings, run-time errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or run-time error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.

A Chaitin Omega number, Ω, is the halting probability of a universal Chaitin (self-delimiting Turing) machine. Every Ω number is both computably enumerable and random. In particular, every Ω number is non-computable. In this thesis, we describe a method to compute the exact values of the first 64 successive bits of a natural Chaitin Omega number. We first describe a model of computation which has been defined and proved to be a universal Chaitin machine U. We then propose a method (procedure) which combines iterative executions of an algorithm with mathematical analysis to get the exact values of the first successive 64 bits of the corresponding Chaitin ΩU number of U. This particular defined Chaitin machine U is essentially a register machine and has been implemented in Java. We call it the canonical compressed model (or compressed model) as it allows only ‘canonical’ program strings to be processed in U. Thus, many input strings which are illegal, hence useless, are ignored and never involved in the computational process. In addition, the compressed design shortens the length of all instructions so that relatively short strings now contain somewhat complex programs. A simulator for U, written in Java, is a primary part of the project. The algorithm is executed iteratively, computing step by step an increasing sequence of rational numbers (in binary) to approximate Ω U. In the n-th step, the algorithm produces four main output files: all halting strings, looping strings, run-time errors, and prefix strings (incomplete programs). In each step, all prefix strings (of the previous step) are read and processed one by one. Each string is extended by 7 bits (ASCII code representations for symbols) to generate new strings that are examined one by one to detect any lexical, syntactic, semantic, or run-time error in each of them. Any of those strings with an error detected is discarded to save storage space and execution time. We solve the Halting Problem for all programs for U of length less than or equal to 84 bits so we can calculate an increasing sequence of exact approximations converging to ΩU. By means of a mathematical analysis the first successive 64 bits, 0000001000000100000110001000011010001111110010111011101000010000 of the 84 bits are proved to be the exact first bits of ΩU. Actually, more bits can be obtained by this procedure if the disk space is sufficient for it to go on, but this procedure cannot be extended indefinitely. In order to assure that our computing result is correct, we have proved that all input strings of length less than or equal to 84 executed in U over 100 steps are not halting programs.* *This dissertation is a compound document (contains both a paper copy and a CD as part of the dissertation). The CD requires the following system requirements: Adobe Acrobat; Microsoft Office.

Master of Science / Department of Computing and Information Sciences / Daniel A. Andresen / According to the Division of Injury Response, Centers for Disease Control and Prevention, approximately 1.4 million Americans sustain a traumatic brain injury each year. The aim of the project is to create a web interface to link survivors, family members, and caregivers of individuals suffering from traumatic brain injuries (TBI) to potentially helpful agencies or service centers within their local communities. Often the TBI service centers located in the remote places are difficult to trace hence this website mainly concentrates on small rural centers which are located in Kansas State. The portal will offer two-dimensional and basic information about traumatic brain injury centers and specifically about access of resources. Within the portal, a link to an interactive map will be provided. A form for data entry helps the service centers to publish about their presence and the regions they serve. A search distance feature is also added into the website which interactively searches the nearest latitude, longitude values (TBI service center) to the user’s location by using the haversine formula.

Master of Science / Department of Computing and Information Sciences / Rodney R. Howell / Nowadays, there is a rapid increase in the complexity of large automotive and control systems because of the integration of external software modules in them. Many of these systems are based on sampled-data control theory. And because of the different timing constraints of individual modules, each module has a different sampling rate. Typically, these systems operate with periodic task sequences and the information flows between the tasks. Generally the information propagates from tasks operating at one period to tasks operating at different periods. When this happens, unusually long information propagation delays can occur which can be disastrous because the system cannot respond to the changes until this delay has been elapsed. Although for arbitrary set of task sets the delays can be very long, Howell and Mizuno (2010) considers a set of task sequences with special constraints and some very useful bounds are derived for the worst case occurrences of them. Howell and Mizuno (2011) has laid out algorithms that compute the delays for certain special cases of task sequences considered in Howell and Mizuno (2010). The purpose of this project is to understand and implement the algorithms from Howell and Mizuno (2011). The implementation is done so that it avoids the manual computation of the delays and helps in better understanding the ideas presented in Howell and Mizuno (2011). The application can be tested against any valid input that meets our assumptions, and it constructs a schedule that exhibits the worst case behavior and from the schedule it computes the worst case information propagation delays.