Diehr and Faaland developed an algorithm that finds the minimum sum of key length pagination of a scroll of n items, and which uses O(n lg n) time and O(n) space, solving a problem posed by McCreight. An improved algorithm is given which uses O(n) time and O(n) space.

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.

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.

Several algorithms are presented 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 Lindstrom marking algorithm uses bounded workspace. Its time complexity is O(n^2) in all cases, but it has been assumed that the average case time complexity O(n lg n). It is proven that the average case time complexity is H(n^2). Similarly, the average size of the Wegbreit bit stack is shown to be H(n).

For an optimal binary search tree T with a subtree S(d) at a distance d from the root of T, we study the ratio of the weight of S(d) to the weight of T. The maximum possible value, which we call ρ(d), of the ratio of weights, is found to have an upper bound of 2/F_d+3 where F_i is the ith Fibonacci number. For d = 1, 2, 3, and 4, the bound is shown to be tight. For larger d, the Fibonacci bound gives ρ(d) = O(ϕ^d) where ϕ ~ .61803 is the golden ratio. By giving a particular set of optimal trees, we prove ρ(d) = Ω((.58578 ... )^d), and believe a similar proof follows for ρ(d) = Ω((.60179 ... )^d). If we include frequencies for unsuccessful searches in the optimal binary search trees, the Fibonacci bound is found to be tight.