We develop a new class of algorithms for losslessly compressing integer sequences that are monotone or quasi-monotone. We combine aspects of standard entropy codes as expressed in binary adaptive sequential coding (BASC) and monotone length (MOL) coding, with an aspect of binary interpolative (BI) coding.

We study practically efficient methods for performing combinatorial group testing. We present efficient nonadaptive and two‐stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two‐stage algorithm matches the information‐theoretic lower bound for the number of tests in a combinatorial group testing regimen.

We study parallel algorithms for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC). Our approach involves the development and application of new group-testing algorithms, where we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items. In the standard group-testing problem, the result of a test is binary--the tested subset either contains defective items or not. In the versions we study in this paper, the result of each test is non-binary. For example, it may indicate whether the number of defective items contained in the tested subset is zero, one, or at least two (i.e., the results are 0, 1, or 2+). We give adaptive algorithms that are provably more efficient than previous group testing algorithms (even for generalized response models). We also show how our algorithms can be implemented in parallel, because they possess a property we call conciseness, which allows them to be used to solve dead sensor diagnosis and conflict resolution on a MAC. Dead sensor diagnosis poses an interesting challenge compared to MAC resolution, because dead sensors are not locally detectable, nor are they themselves active participants. Even so, we present algorithms that can be applied in both contexts that are more efficient than previous methods. We also give lower bounds for generalized group testing.

Off-chip bus transitions are a major source of power dissipation for embedded systems. In this paper, new adaptive encoding schemes are proposed that significantly reduce transition activity on data and multiplexed address buses. These adaptive techniques are based on self-organizing lists to achieve reduction in transition activity by exploiting the spatial and temporal locality of the addresses. Also the proposed techniques do not require any extra bit lines and have minimal delay overhead. The techniques are evaluated for efficiency using a wide variety of application programs including SPEC 95 benchmark set. Unlike previous approaches that focus on instruction address buses, experiments demonstrate significant reduction in transition activity of up to 54% in data address buses and up to 59% in multiplexed address buses. The average reductions are twice those obtained using current schemes on a data address bus and more than twice those obtained on a multiplexed address bus.

Off-chip bus transitions are a major source of power dissipation for embedded systems. In this paper, new adaptive encoding schemes are proposed that significantly reduce transition activity on data and multiplexed address buses, that do not add redundancy in space or time and which have minimal delay overhead. These adaptive techniques are based on self-organising lists to achieve reduction in transition activity by exploiting the spatial and temporal locality of the addresses. Unlike previous approaches that focus on instruction address buses, experiments demonstrate significant reduction in transition activity of up to 54% in data address buses and up to 59% in multiplexed address buses. The average reductions are twice those obtained using current schemes on a data address bus and more than twice those obtained on a multiplexed address bus. 1.

Systolic array architectures for self-organizing linear lists under the transpose update heuristic are presented. The first model has linear delay and restricts input on every other system cycle. The second system combines a systolic array with trees to provide logarithmic delay and input on every clock cycle. These preliminary designs can be the basis of hardware used to achieve high-speed lossless data compression for data communication and storage. On large files (greater than 40 kilobytes), our designs provide better compression than other systolic list compression schemes.>

Parallel algorithms for lossless data compression via dictionary compression using optimal and greedy parsing strategies are described. Dictionary compression removes redundancy by replacing substrings of the input by references to strings stored in a dictionary. Given a static dictionary stored as a suffix tree, the authors present a parallel random access concurrent read, concurrent write (PRAM CREW) algorithm for optimal compression which runs in O(M+log M log n) time with O(nM/sup 2/) processors, where it is assumed that M is the maximum length of any dictionary entry. They also describe an O(M+log n) time and O(n) processor algorithm for greedy parsing given a static or sliding-window dictionary. For sliding-window compression. A different approach finds the greedy parsing in O(log n) time using O(nM log M/log n) processors. Their algorithms are practical in the sense that their analysis elicits small constants.>

The authors present systolic array implementations of transpose coding, which uses an alternative self-organizing list strategy but otherwise is similar to move-to-front coding. They present implementations for fixed-length word lists which provide improved system bandwidth by accelerating transpose coding.>

While context-modeling algorithms provide very good compression, they suffer from the disadvantages of being slow and requiring large amounts of main memory. A context-model-based algorithm is described that runs significantly faster, uses much less space, and provides compression ratios close to those of earlier context modeling algorithms. These improvements are achieved through use of self-organizing lists.>

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, the complexity of three-dimensional extensions of these problems is investigated. This is one of twelve research directions suggested by Knuth in his book on the stable marriage problem. It is shown that these problems are NP-complete, and hence it is unlikely that there exist efficient algorithms for their solutions. The approach developed in this paper provides an alternate NP-completeness proof for the hospitals/residents problem with couples—an important practical problem shown earlier to be NP-complete by Ronn.

An O ( nL )-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n , where each code string must have length no greater than L . The algorithm uses O ( n ) space.

In an instance of the stable marriage problem of size n, n men and n women, each participant 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}}),\cdots, (m_{n}, w_{i_{n}})\}$ such that no unmatched man and woman prefer each other to their partners in M. There exists an efficient algorithm, due to Gale and Shapley, that finds a stable marriage for any given problem instance. A pair $(m_{i} w_{j})$ is stable if it is contained in some stable marriage. In this paper, the problem of determining whether an arbitrary pair is stable in a given problem instance is studied. It is shown that the problem has a lower bound of $\Omega (n^{2})$ in the worst case. Hence, a previous known algorithm for the problem is asymptotically optimal. As corollaries of these results, the lower bound of $\Omega (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 $\Theta (n^{2})$ time. The results in this paper show that such an algorithm does not exist.

Presented are several algorithms whose operations are governed by a principle of failure functions: When searching for an extremal value within a sequence, it suffices to consider only the subsequence of items each of which is the first possible improvement of its predecessor. These algorithms are more efficient than their more traditional counterparts.

The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in $O(n\log n)$ time generally and, for certain weight functions, in linear time. A number of applications are given, including an optimum paragraph formation problem and the problem of finding a minimum height B-tree, whose solutions realize improvement in asymptotic time complexity.

The Lindstrom marking algorithm uses bounded workspace. Its time complexity is $0(n^2 )$ in all cases, but it has been assumed that the average case time complexity is $0(n\log n)$. It is proven that the average case time complexity is $\Theta (n^2 )$ for a wide variety of probability distributions. Similarly, the average size of the Wegbreit bit stack is shown to be $\Theta (n)$.

The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in O(n log n) time generally and, for certain weight functions, in linear time. A number of applications are given, including an optimum paragraph formation problem and the problem of finding a minimum height B-tree, whose solutions realize improvement in asymptotic time complexity.

An algorithm is presented to merge two subfiles of size n/2 each, stored in the left and the right halves of a linearly connected processor array, in 3n/2 route steps and log n compare-exchange steps. This algorithm is extended to merge two horizontally adjacent subfiles of size m × n/2 each, stored in an m × n mesh-connected processor array in row-major order, in m + 2n route steps and log mn compare-exchange steps. These algorithms are faster than their counterparts proposed so far.

The vector searching problem is, given k-vector A (a k-vector is a vector that has k components, over the integers) and given a set $\bar B$ of n distinct k-vectors, to determine whether or not A is a member of set $\bar B$. Comparisons between components yielding “greater than-equal-less than” results are permitted. If the vectors in $\bar B$ are unordered then $nk$ comparisons are necessary and sufficient. In the casewhen the vectors in B are ordered, it is shown that $\lfloor \log n \rfloor + k$ comparisons are necessary and, for $n \geqq 4k$, $k\lceil\log (n/k) \rceil + 2k - 1$ comparisons are sufficient.

AaS~ACT Two algorithms are presented that solve the longest common subsequence problem The first algorithm is applicable in the general case and requires O(pn + n log n) time where p is the length of the longest common subsequence The second algorithm requires time bounded by O(p(m + 1 -p)log n) In the common speoal case where p is close to m, this algorithm takes much less time than n ~

Parallel programs are presented that determine the transitive closure of a matrix using n3 processors and connected components of an undirected graph using n2 processors. In both cases, the desired results are obtained in time 0(log2n). It is assumed that the processors have access to common memory. Simultaneous access to the same location is permitted for fetch, but not store, instructions.The problem of determining the connected components of a graph using a parallel computer has recently appeared in the literature [1,2]. The result in [1] is based on finding the transitive closure of a matrix in time 0(log2n) which can be done using 0(n3) processors. We show that n2 processors are sufficient to solve the connected component problem in time 0(log2n).We present algorithm CLOSURE that will find the transitive closure of Boolean matrix M [n by n] using n3 processors [numbered P(0,0,0) through P(n−1 ,n−1, n−1)] each of which has local memory and each of which can access common array A [n by n].

The problem of finding a longest common subsequence of two strings is discussed. This problem arises in data processing applications such as comparing two files and in genetic applications such as studying molecular evolution. The difficulty of computing a longest common subsequence of two strings is examined using the decision tree model of computation, in which vertices represent “equal - unequal” comparisons. It is shown that unless a bound on the total number of distinct symbols is assumed, every solution to the problem can consume an amount of time that is proportional to the product of the lengths of the two strings. A general lower bound as a function of the ratio of alphabet size to string length is derived. The case where comparisons between symbols of the same string are forbidden is also considered and it is shown that this problem is of linear complexity for a two-symbol alphabet and quadratic for an alphabet of three or more symbols.

The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed n > 2, the knapsack problem with n variables can be solved in polynomial time.