In this thesis a heuristic method for factoring semiprimes by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2N graph connectivity is used to generate heuristics for multiagent search. Further analysis is presented including the requirements on choosing prime numbers to generate 'hard' semiprimes; the lack of connectivity in PG1N graphs; the counts of spanning trees in PG2N graphs; the upper bound of a PG2N graph diameter and a conjecture on the frequency distribution of prime numbers on Hamming distance. We further demonstrated the feasibility of the HD2 breadth first search of PG2N graphs for factoring small semiprimes. We presented the performance of different multiagent search heuristics in PG2N graphs showing that the heuristic of most connected seedpick outperforms least connected or random connected seedpick heuristics on small PG2N graphs of size N

The B-tree is a one of the more popular methods in use today for indexes and inverted files in database management systems. The traditional implementation of a Bâ tree uses many pointers (more than one per key), which can directly affect the performance of the B-tree. A general method of file organization and access (called Dynanic Address Computation) has been described by Cook that can be used to implement B-trees using no pointers. A minimal amount of storage (in addition to the keys) is required. An implementation of Dynamic Address Computation and a B-tree management package is described. Analytical performance measures are derived in an attempt to understand the performance characteristics of the B-tree. It is shown that the additional costs associated with Dynamic Address Computation result in an implementation that is competitive with traditional implementations only for small applications. For very large B-trees, additional work is required to make the performance acceptable. Some examples of possible modifications are discussed. / Master of Science

The main contribution of this dissertation proposes a new paradigm, called the parentheses matching paradigm. It claims that this paradigm is well suited for designing efficient parallel algorithms for a broad class of nonnumeric problems. To demonstrate its applicability, we present three cost-optimal parallel algorithms for breadth-first traversal of general trees, sorting a special class of integers, and coloring an interval graph with the minimum number of colors.

Thesis (M.S.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Systems Science and Industrial Engineering Department, 2006. / Includes bibliographical references.

Thesis (M.S.)--State University of New York at Binghamton, Department of Computer Science, Thomas J. Watson School of Engineering and Applied Science, 2007. / Includes bibliographical references.

Thesis (Ph. D.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Computer Science, 2009. / Includes bibliographical references.

Let G = (V, E) be a graph and let S ⊆ V be a subset of vertices. The set S is a defensive alliance if for all x ∈ S, |N[x] ∩ S| ≥ |N[x] − S|. The concept of defensive alliances was introduced in [KHH04], primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if any one of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, [FLG00] applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies ∀x ∈ C, |N[x] ∩ C| > |N[x] − C|. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. iii Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended. However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in [BDH07] for exactly this purpose. The non-empty set S is a secure set if every subset X ⊆ S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In [BDH07], the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if ∀X ⊆ S, |N[X] ∩ S| ≥ |N[X] − S| ([BDH07], Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N[S] = V . The cardinality of a minimum global secure set of G is the global security number of G, denoted γs(G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.

Pang Suet-Yee. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 85-87). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.1.1 --- Survival Analysis --- p.2 / Chapter 1.1.2 --- Tree、-structured Statistical Method --- p.2 / Chapter 1.1.3 --- Mortality Study --- p.3 / Chapter 1.2 --- Motivation --- p.3 / Chapter 1.3 --- Background Information --- p.4 / Chapter 1.4 --- Data Content --- p.7 / Chapter 1.5 --- Thesis Outline --- p.8 / Chapter 2 --- Imputation and File Splitting --- p.10 / Chapter 2.1 --- Imputation of Missing Values --- p.10 / Chapter 2.1.1 --- Purpose of Imputation --- p.10 / Chapter 2.1.2 --- Procedure of Hot Deck Imputation --- p.11 / Chapter 2.1.3 --- List of Variables for Imputation --- p.12 / Chapter 2.2 --- File Splitting --- p.14 / Chapter 2.2.1 --- Splitting by Gender --- p.14 / Chapter 2.3 --- Splitting for Validation Check --- p.1G / Chapter 3 --- Cox Hazard Model --- p.17 / Chapter 3.1 --- Basic Idea --- p.17 / Chapter 3.1.1 --- Survival Analysis --- p.17 / Chapter 3.1.2 --- Survivor Function --- p.18 / Chapter 3.1.3 --- Hazard Function --- p.18 / Chapter 3.2 --- The Cox Proportional Hazards Model --- p.19 / Chapter 3.2.1 --- Kaplan-Meier Estimate and Log-Rank Test --- p.20 / Chapter 3.2.2 --- Hazard Ratio --- p.23 / Chapter 3.2.3 --- Partial Likelihood --- p.24 / Chapter 3.3 --- Extension of the Cox Proportional Hazards Model for Time-dependent Variables --- p.25 / Chapter 3.3.1 --- Modification of the Cox's Model --- p.25 / Chapter 3.4 --- Results of Model Fitting --- p.26 / Chapter 3.4.1 --- Extract the Significant Covariates from the Models --- p.31 / Chapter 3.5 --- Model Interpretation --- p.32 / Chapter 4 --- CART --- p.37 / Chapter 4.1 --- CART Procedure --- p.38 / Chapter 4.2 --- Selection of the Splits --- p.39 / Chapter 4.2.1 --- Goodness of Split --- p.39 / Chapter 4.2.2 --- Type of Variables --- p.40 / Chapter 4.2.3 --- Estimation --- p.40 / Chapter 4.3 --- Pruning the Tree --- p.41 / Chapter 4.3.1 --- Misclassification Cost --- p.42 / Chapter 4.3.2 --- Class Assignment Rule --- p.44 / Chapter 4.3.3 --- Minimal Cost Complexity Pruning --- p.44 / Chapter 4.4 --- Cross Validation --- p.47 / Chapter 4.4.1 --- V-fold Cross-validation --- p.47 / Chapter 4.4.2 --- Selecting the right sized tree --- p.49 / Chapter 4.5 --- Missing Value --- p.49 / Chapter 4.6 --- Results of CART program --- p.51 / Chapter 4.7 --- Model Interpretation --- p.53 / Chapter 5 --- Model Prediction --- p.58 / Chapter 5.1 --- Application to Test Sample --- p.58 / Chapter 5.1.1 --- Fitting test sample to Cox's Model --- p.59 / Chapter 5.1.2 --- Fitting test sample to CART model --- p.61 / Chapter 5.2 --- Comparison of Model Prediction --- p.62 / Chapter 5.2.1 --- Misclassification Rate --- p.62 / Chapter 5.2.2 --- Misclassification Rate of Cox's model --- p.63 / Chapter 5.2.3 --- Misclassification Rate of CART model --- p.64 / Chapter 5.2.4 --- Prediction Result --- p.64 / Chapter 6 --- Conclusion --- p.67 / Chapter 6.1 --- Comparison of Results --- p.67 / Chapter 6.2 --- Comparison of the Two Statistical Techniques --- p.68 / Chapter 6.3 --- Limitation --- p.70 / Appendix A: Coding Description for the Health Factors --- p.72 / Appendix B: Log-rank Test --- p.75 / Appendix C: Longitudinal Plot of Time Dependent Variables --- p.76 / Appendix D: Hypothesis Testing of Suspected Covariates --- p.78 / Appendix E: Terminal node report for both gender --- p.81 / Appendix F: Calculation of Critical Values --- p.83 / Appendix G: Distribution of Missing Value in Learning sample and Test Sample --- p.84 / Bibliography --- p.85

Two related image processing problems are addressed in this thesis. First, the problem of identification of 3-D objects in real time is explored. An algorithm to solve this problem and a hardware system for parallel implementation of this algorithm are proposed. The classification scheme is based on the "Invariant Numerical Shape Modeling" (INSM) algorithm originally developed for 2-D pattern recognition such as alphanumeric characters. This algorithm is then extended to 3-D and is used for general 3-D object identification. The hardware system is an SIMD parallel processor, designed in bit slice fashion for expandability. It consists of a library of images coded according to the 3-D INSM algorithm and the SIMD classifier which compares the code of the unknown image to the library codes in a single clock pulse to establish its identity. The output of this system consists of three signals: U, for unique identification; M, for multiple identification; and N, for non-identification of the object. Second, the problem of real time image compaction is addressed. The quad tree data structure is described. Based on this structure, a parallel processor with a tree architecture is developed which is independent of the data entry process, i.e., data may be entered pixel by pixel or all at once. The hardware consists of a tree processor containing a tree generator and three separate memory arrays, a data transfer processor, and a main memory unit. The tree generator generates the quad tree of the input image in tabular form, using the memory arrays in the tree processor for storage of the table. This table can hold one picture frame at a given time. Hence, for processing multiple picture frames the data transfer processor is used to transfer their respective quad trees from the tree processor memory to the main memory. An algorithm is developed to facilitate the determination of the connections in the circuit.

In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the edge isoperimetric value of G at I be defined as be(i,G)= mins v;|s|= i | δ(S,G)|. For S V, let φ(S,G) = {u ε V – S : ,such that be the vertex boundary of S. Given an integer i, 1 ≤ i ≤ | V| , let the vertex isoperimetric value of G at I be defined as bv(i,G)= The edge isoperimetric peak of G is defined as be(G) =. Similarly the vertex isoperimetric peak of G is defined as bv(G)= .The problem of determining a lower bound for the vertex isoperimetric peak in complete k-ary trees of depth d,Tdkwas recently considered in[32]. In the first part of this thesis we provide lower bounds for the edge and vertex isoperimetric peaks in complete k-ary trees which improve those in[32]. Our results are then generalized to arbitrary (rooted)trees. Let i be an integer where . For each i define the connected edge isoperimetric value and the connected vertex isoperimetric value of G at i as follows: is connected and is connected A meta-Fibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n-1))+ a(x2(n)+ a2′(n -2)), where xi: Z+ → Z+ , i =1,2, is a linear function of n and ai′(j)= a(j) or ai′(j)= -a(j), for i=1,2. Sequences belonging to this class have been well studied but in general their properties remain intriguing. In the second part of the thesis we show an interesting connection between the problem of determining and certain meta-Fibonacci sequences. In the third part of the thesis we study the problem of determining be and bv algorithmically for certain special classes of graphs. Definition 0.1. A tree decomposition of a graph G = (V,E) is a pair where I is an index set, is a collection of subsets of V and T is a tree whose node set is I such that the following conditions are satisfied: (For mathematical equations pl see the pdf file)