Given a set of n real values, each with a positive weight, we wish to find the subset of n —k values having maximum weighted average. This is equivalent to the following form of parametric selection: given n objects with values decreasing linearly with time, find the time at which the n —k maximum values add to zero. We give several algorithms showing that these problems can be solved in time O(n) (independent of k). We also show that a slight generalization of the original problem, in which weights are allowed to be negative, is NP-complete.

The stable marriage problem is a matching problem that pairs members of two sets. The objective is to achieve a matching that satisfies all participants based on their preferences. The stable roommate problem is a variant involving only one set, which is partitioned into pairs with a similar objective. There exist asymptotically optimal algorithms that solve both problems.

In this paper, we investigate the complexity of three dimensional extensions of these problems. This is one of twelve research directions suggested by Knuth in his book on the stable marriage problem. We show that these problems are NP-complete, and hence it is unlikely that there exist efficient algorithms for their solutions.

Applying the polynomial tranformation developed in this paper, we extend the NP-completeness result to include the problem of matching couples - who are both medical school graduates - to pairs of hospital resident positions. This problem is important in practice and is dealth with annually by NRMP, the centralized program that matches all medical school graduates in the United States to available resident positions.

In an instance of the stable marriage problem of size n, n men and n women each ranks members of the opposite sex in order of preference. A stable marriage is a complete matching M = {(m_1, w_i_1), (m_2, w_i_2), ..., (m_n, w_i_n)} such that no unmatched man and woman prefer each other to their partners in M.

A pair (m_i, w_j) is stable if it is contained in some stable marriage. In this paper, we prove that determining if an arbitrary pair is stable requires Ω(n^2) time in the worst case. We show, by an adversary argument, that there exists instances of the stable marriage problem such that it is possible to find at least one pair that exhibits the Ω(n^2) lower bound.

As corollaries of our results, the lower bound of Ω(n^2) is established for several stable marriage related problems. Knuth, in his treatise on stable marriage, asks if there is an algorithm that finds a stable marriage in less than Θ(n^2) time. Our results show that such an algorithm does not exist.

Context modeling has emerged as the most promising new approach to compressing text. While context-modeling algorithms provide very good compression, they suffer from the disadvantages of being quite slow and requiring large amounts of main memory in which to execute. We describe a context-model-based algorithm that runs significantly faster and uses less space than earlier context models. Although our algorithm does not achieve the compression performance of competing context models, it does provide a significant improvement over the widely-used Unix utility compress in terms of both use of memory and compression performance.

We discuss representations of prefix codes and the corresponding storage space and decoding time requirements. We assume that a dictionary of words to be encoded has been defined and that a prefix code appropriate to the dictionary has been constructed. The encoding operation becomes simple given these assumptions and given an appropriate parsing strategy, therefore we concentrate on decoding. The application which led us to this work constrains the use of internal memory during the decode operation. As a result, we seek a method of decoding which has a small memory requirement.

This paper surveys a variety of data compression methods spanning almost forty years of research, from the work of Shannon, Fano and Huffman in the late 40's to a technique developed in 1986. The aim of data compression is to reduce redundancy in stored or communicated data, thus increasing effective data density. Data compression has important application in the areas of file storage and distributed systems. Concepts from information theory, as they relate to the goals and evaluation of data compression methods, are discussed briefly. A framework for evaluation and comparison of methods is constructed and applied to the algorithms presented. Comparisons of both theoretical and empirical natures are reported and possibilities for future research are suggested.

An ordered minimal perfect hash table is one in which no collisions occur among a predefined set of keys, no space is unused, and the data are placed in the table in order. A new method for creating ordered minimal perfect hashing functions is presented. The method presented is based on a method developed by Fox, Heath, Daoud, and Chen, but it creates hash functions with representation space requirements closer to the theoretical lower bound. The method presented requires approximately 10% less space to represent generated hash functions, and is easier to implement than Fox et al's. However, a higher time complexity makes it practical for small sets only (< 1000).

We present an approach to modeling the average case behavior of an algorithm for learning Conjunctive Normal Form (CNF, i.e., conjunctions of disjunctions). Our motivation is to predict the expected error of the learning algorithm as a function of the number of training examples. We evaluate the average case model by comparing the error predicted by the model to the actual error obtained by running the leaming algorithm, and show how the analysis can lead to insight into the behavior of the algorithm and the factors that affect the error.

The ever increasing use of distributed computing as a method of providing added computing power and reliability has sparked interest in methods to model and analyze concurrent hardware/ software systems. Efficient automated analysis tools are needed to aid designers of such systems. The Distributed Systems Project at UCI has been developing a suite of tools (dubbed the P-NUT system) which supports efficient analysis of models of concurrent software. This paper presents the principles which guide the development of P-NUT tools and discusses the development of one of the tools: the Reachability Graph Builder (RGB). The P-NUT approach to tool development has resulted in the production of a highly efficient tool for constructing reachability graphs. The careful design of data structures and associated algorithms has significantly enlarged the class of models which can be analyzed.