Combinatorial problems in analysis of algorithms and coding theory

This thesis addresses combinatorial problems arising in the area of analysis of algorithms and error-correcting coding theory.; Many processes in communication theory and the theory of algorithms can be described in terms of distributing objects into urns, according to some predefined set of constraints and rules. Usually, the analysis of urn models runs into difficulties because the occupancy statistics are dependent random variables.; The first topic in the thesis is concerned with the construction of specialized probabilistic transforms for general urn models. These allow dependent occupancy variables to be replaced by independent ones. Several transforms and their inverses are constructed based on this general framework, and Tauberian-type conditions under which the asymptotic formulas for occupancy statistics are identical in the original and the transform domain are derived as well.; The second problem in the thesis is concerned with the average case analysis of Gosper's algorithm for indefinite summation of hypergeometric terms. This algorithm is an important component in computer algebra systems and a program package in Mathematica. The analysis of Gosper's algorithm is based on a simple, but general, combinatorial urn model for the space of input functions. Using this model, and the transform techniques described in the first part of the thesis, asymptotic formulas for the most important parameters that influence the running time of the algorithm are obtained. In the course of the analysis, some new results concerning symmetric random walks, asymptotic enumeration techniques and properties of special functions such as Bessel functions and Legendre polynomials, are derived.; The third topic in the thesis is concerned with constructing methods for counting the number of subcodes of an isodual code with a given dimension and support length. The results presented in this work include generalizing invariant theory for the enumerators of the subcodes, and proving that subcode and coset weight enumerators of a code are closely connected. The subcode and coset weight enumerators of several isodual codes are computed, demonstrating that there exist inequivalent codes with the same set of subcode and coset weight enumerators. These are the first such known examples in coding theory literature.