Let <b>A</b> and <b>B</b> be finite sets with |<b>A</b>|=<i>n</i> and |<b>B</b>|=<i>m</i>. An (<i>n</i>,<i>m</i>,<i>w</i>)-<i>perfect hash</i> family</i> is a collection <i>F</i> of functions from <b>A</b> to <b>B</b> such that for any <b>X</b> &#8838; <b>A</b> with |<b>X</b>|=<i>w</i>, there exists at least one ? &#8712; <i>F</i> such that ? is one-to-one when restricted to <b>X</b>. Perfect hash families are basic combinatorial structures and they have played important roles in Computer Science in areas such as database management, operating systems, and compiler constructions. Such hash families are used for memory efficient storage and fast retrieval of items such as reserved words in programming languages, command names in interactive systems, or commonly used words in natural languages. More recently, perfect hash families have found numerous applications to cryptography, for example, to broadcast encryption schemes, secret sharing, key distribution patterns, visual cryptography, cover-free families and secure frameproof codes. In this thesis, we survey constructions and applications of perfect hash families. For constructions, we divided the results into three parts, depending on underlying structure and properties of the constructions: combinatorial structures, linear functionals, and algebraic structures. For applications, we focus on those related to cryptography.

The simple relational structures form the units, or atoms, upon which all other relational structures are constructed by means of the substitution decomposition. This decomposition appears to have first been introduced in 1953 in a talk by Fraïssé, though it did not appear in an article until a paper by Gallai in 1967. It has subsequently been frequently rediscovered from a wide variety of perspectives, ranging from game theory to combinatorial optimization. Of all the relational structures - a set which also includes graphs, tournaments and posets - permutations are receiving ever increasing amounts of attention. A simple permutation is one that maps every nontrivial contiguous set of indices to a set of indices that is never contiguous. Simple permutations and intervals of permutations are important in biomathematics, while permutation classes - downsets under the pattern containment order - arise naturally in settings ranging from sorting to algebraic geometry. We begin by studying simple permutations themselves, though always aim to establish this theory within the broader context of relational structures. We first develop the technology of "pin sequences", and prove that every sufficiently long simple permutation must contain either a long horizontal or parallel alternation, or a long pin sequence. This gives rise to a simpler unavoidable substructures result, namely that every sufficiently long simple permutation contains a long alternation or oscillation. ErdÅ s, Fried, Hajnal and Milner showed in 1972 that every tournament could be extended to a simple tournament by adding at most two additional points. We prove analogous results for permutations, graphs, and posets, noting that in these three cases we may need to extend a structure by adding (n+1)/2 points in the case of permutations and posets, and logâ (n+1) points in the graph case. The importance of simple permutations in permutation classes has been well established in recent years. We extend this knowledge in a variety of ways, first by showing that, in a permutation class containing only finitely many simple permutations, every subset defined by properties belonging to a finite "query-complete set" is enumerated by an algebraic generating function. Such properties include being an even or alternating permutation, or avoiding generalised (blocked or barred) permutations. We further indicate that membership of a permutation class containing only finitely many simple permutations can be computed in linear time. Using the decomposition of simple permutations, we establish, by representing pin sequences as a language over an eight-letter alphabet, that it is decidable if a permutation class given by a finite basis contains only finitely many simple permutations. We also discuss possible approaches to the same question for other relational structures, in particular the difficulties that arise for graphs. The pin sequence technology provides a further result relating to the wreath product of two permutation classes, namely that C â D is finitely based whenever D does not admit arbitrarily long pin sequences. As a partial converse, we also exhibit a number of explicit examples of wreath products that are not finitely based.

Planning for emergency evacuation, and, more generally, for emergency movement involving both evacuation (egress) of occupants and ingress of first responders, presents important and challenging problems. A number of the current issues that arise during emergency incidents are due to the uncertainty and transiency of environmental conditions. In general, movement plans are formulated at building design-time, and those involved, such as building occupants and emergency responders, are left to adapt routing plans to actual events as they unfold. In the context of next-generation emergency response systems, it has been proposed to dynamically plan and route individuals during an emergency event, replanning to take account of changes in the environment. In this work, an emergency movement problem, the Maximal Safest Escape (MSE) problem, is formulated in terms that model the uncertain and transient environmental conditions as a flow problem in time-dependent networks with time-varying and stochastic edge travel-times and capacities (STV Networks). The objective of the MSE problem is to find flow patterns with the a priori maximal probability of successfully conveying all supply from the source to the sink in some given STV Network. The MSE and its deterministic counterpart are proved to be NP-hard. Furthermore, due to inherent complexity in evaluating the exact quality of candidate solutions, a simulation approximation method is presented based on well-known Monte-Carlo sampling methods. Given the complexity of the problem, and using the approximation method for evaluating solutions, it is proposed to tackle the MSE problem using a metaheuristic approach based on an existing framework that integrates Evolutionary Algorithms (EA) with a state-of-the-art statistical ranking and selection method, the Optimal Computing Budget Allocation (OCBA). Several improvements are proposed for the framework to reduce the computational demand of the ranking method. Empirically, the approach is compared with a simple fitness averaging approach and conditions under which the integrated framework is more efficient are investigated. The performance of the EA is compared against upper and lower bounds on optimal solutions. An upper bound is established through the “wait-and-see” bound, and a lower bound by a naıve random search algorithm (RSA). An experimental design is presented that allows for a fair comparison between the EA and the RSA. While there is no guarantee that the EA will find optimal solutions, this work demonstrates that the EA can still find useful solutions; useful solutions are those that are at least better than some baseline, here the lower bound, in terms of solution quality and computational effort. Experimentally, it is demonstrated that the EA performs significantly better than the baseline. Also, the EA finds solutions relatively close to the upper bound; however, it is difficult to establish how optimistic the upper bounds. The main approach is also compared against an existing approach developed for solving a related problem wrapped in a heuristic procedure in order to apply the approach to the MSE. Empirical results show that the heuristic approach requires significantly less computation time, but finds solutions of significantly lower quality. Overall, this work introduces and empirically verifies the efficacy of a metaheuristic based on a framework integrating EAs with a state-of-the-art statistical ranking and selection technique, the OCBA, for a novel flow problem in STV Networks. It is suggested that the lessons learned during the course of this work, along with the specific techniques developed, may be relevant for addressing other flow problems of similar complexity.

Peptide nucleic acids (PNAs) were used as encoding tags to enable the analysis of peptide libraries by PNA/DNA hybridisation onto DNA microarrays. This allowed entire peptide libraries to be organised and sorted in a two dimensional format whereby all library members could be interrogated and analysed on a one-byone basis. In this thesis, PNA-encoded peptide libraries, generated by split-and-mix library synthesis, were screened for a variety of functions. Peptide sequences identified from the screening of a PNA-encoded library were analysed in detail as the first specific substrates for chymopapain. A new PNAencoded library consisting of D-amino acids was synthesised and screened with a number of proteases in attempts to identify novel/unusual substrates. PNA-encoded libraries were also used in the screening of peptide libraries for other activities. Thus substrates for catalyst-free Hüisgen cycloaddition were identified following the reaction between an alkyne modified peptide library and azidofluorescein, while cell-penetrating peptides were identified by hybridization of an internalized encoded library onto a DNA microarray.

Probability theory is a branch of mathematics concerned with determining the long run frequency or chance that a given event will occur. This chance is determined by dividing the number of selected events by the number of total events possible, assuming these events are equally likely. Probability theory is simply enumerative combinatorial analysis when applied to finite sets. For a given finite sample space, probability questions are usually "just" a lot of counting. The purpose of this thesis is to provide some in depth analysis of several combinatorial methods, including basic principles of counting, permutations and combinations, by specifically exploring one type of probability problem: C ordered possible elements that are equally likely s independent sampled subjects r distinct elements, where r = 1, 2, 3, …, min (C, s) we want to know P(s subjects utilize exactly r distinct elements). This thesis gives a detailed step by step analysis on techniques used to ultimately finding a general formula to solve the above problem.

This thesis studies the open problem of packing rectangles. Is it possible to pack rectangles with dimensions 1/n x 1/(n+1) into a unit square? The aim of this thesis is analysis of the problem and the related algorithm. Attention will be focused mainly on the implementation of this algorithm and on study of its functioning. Powered by TCPDF (www.tcpdf.org)

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Doctor of Philosophy. Johannesburg, 2016. / In this thesis, various partition functions with respect to Rogers-Ramanujan identities and George Andrews' partitions with initial repetitions are studied. Agarwal and Goyal gave a three-way partition theoretic interpretation of the Rogers- Ramanujan identities. We generalise their result and establish certain connections with some work of Connor. Further combinatorial consequences and related partition identities are presented. Furthermore, we re ne one of the theorems of George Andrews on partitions with initial repetitions. In the same pursuit, we construct a non-diagram version of the Keith's bijection that not only proves the theorem, but also provides a clear proof of the re nement. Various directions in the spirit of partitions with initial repetitions are discussed and results enumerated. In one case, an identity of the Euler-Pentagonal type is presented and its analytic proof given. / M T 2016

In this paper we present a simple combinatorial approach for the derivation of zero avoiding transition probabilities in a Markovian r- node series Jackson network. The method we propose offers two advantages: first, it is conceptually simple because it is based on transition counts between the nodes and does not require a tensor representation of the network. Second, the method provides us with a very efficient technique for numerical computation of zero avoiding transition probabilities. / Series: Forschungsberichte / Institut für Statistik

This work was motivated by the well-known question: "Does there exist a nondesarguesian projective plane of prime order?" For a prime p < 11, there is only the pappian plane of order p. Hence, such planes are indeed desarguesian. Thus, it is of interest to examine whether there are non-desarguesian planes of order 11. A suggestion by Ascher Wagner in 1985 was made to Spyros S. Magliveras: "Begin with a non-desarguesian plane of order pk, k > 1, determine all subplanes of order p up to collineations, and check whether one of these is non-desarguesian." In this manuscript we use a group-theoretic methodology to determine the subplane structures of some non-desarguesian planes. In particular, we determine orbit representatives of all proper Q-subplanes both of a Veblen-Wedderburn (VW) plane of order 121 and of the Hughes plane of order 121, under their full collineation groups. In PI, there are 13 orbits of Baer subplanes, all of which are desarguesian, and approximately 3000 orbits of Fano subplanes. In Sigma , there are 8 orbits of Baer subplanes, all of which are desarguesian, 2 orbits of subplanes of order 3, and at most 408; 075 distinct Fano subplanes. In addition to the above results, we also study the subplane structures of some non-desarguesian planes, such as the Hall plane of order 25, the Hughes planes of order 25 and 49, and the Figueora planes of order 27 and 125. A surprising discovery by L. Puccio and M. J. de Resmini was the existence of a plane of order 3 in the Hughes plane of order 25. We generalize this result, showing that there are subplanes of order 3 in the Hughes planes of order q2, where q is a prime power and q 5 (mod 6). Furthermore, we analyze the structure of the full collineation groups of certain Veblen- Wedderburn (VW) planes of orders 25, 49 and 121, and discuss how to recover the planes from their collineation groups. / by Cafer Caliskan. / Thesis (Ph.D.)--Florida Atlantic University, 2010. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2010. Mode of access: World Wide Web.

A well-known long standing problem in combinatorics and statistical mechanics is to find the generating function for self-avoiding walks (SAW) on a two-dimensional lattice, enumerated by perimeter. A SAW is a sequence of moves on a square lattice which does not visit the same point more than once. It has been considered by more than one hundred researchers in the pass one hundred years, including George Polya, Tony Guttmann, Laszlo Lovasz, Donald Knuth, Richard Stanley, Doron Zeilberger, Mireille Bousquet-Mlou, Thomas Prellberg, Neal Madras, Gordon Slade, Agnes Dit- tel, E.J. Janse van Rensburg, Harry Kesten, Stuart G. Whittington, Lincoln Chayes, Iwan Jensen, Arthur T. Benjamin, and many others. More than three hundred papers and a few volumes of books were published in this area. A SAW is interesting for simulations because its properties cannot be calculated analytically. Calculating the number of self-avoiding walks is a common computational problem. A recently proposed model called prudent self-avoiding walks (PSAW) was first introduced to the mathematics community in an unpublished manuscript of Pra, who called them exterior walks. A prudent walk is a connected path on square lattice such that, at each step, the extension of that step along its current trajectory will never intersect any previously occupied vertex. A lattice path composed of connected horizontal and vertical line segments, each passing between adjacent lattice points. We will discuss some enumerative problems in self-avoiding walks, lattice paths and walks with several step vectors. Many open problems are posted. / by Shanzhen Gao. / Thesis (Ph.D.)--Florida Atlantic University, 2011. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.