Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We focus on the expected number of color comparisons when the c n colorings are equally probable. We analyze an obvious algorithm, showing that its expected performance is c 2 + c − 2/2 c n − O ( c 2 ), with variance Θ( c 2 n ). We present and analyze an algorithm for the case c = 3 colors whose average complexity on the 3 n equally probable inputs is 7083/5425 n + O (√ n ) = 1.3056… n + O (√ n ), substantially better than the expected complexity 5/3 n + O (1) = 1.6666… n + O (1) of the obvious algorithm. We describe a similar algorithm for c =4 colors whose average complexity on the 4 n equally probable inputs is 761311/402850 n + O (log n ) = 1.8898… n + O (log n ), substantially better than the expected complexity 9/4 n + O (1) = 2.25 n + O (1) of the obvious algorithm.

Given a set of n elements, each of which is colored one of c colors, we must determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We prove that ( c − 1)( n − c )/2 color comparisons are necessary in the worst case to determine the plurality color and give an algorithm requiring (0.775 c + 5.9) n + O ( c 2 ) color comparisons for c ≥ 9.

Given a set of n elements, each of which is colored one of c ≥ 2 colors, we have to determine an element of the plurality (most frequently occurring) color by pairwise equal/unequal color comparisons of elements. We derive lower bounds for the expected number of color comparisons when the c n colorings are equally probable. We prove a general lower bound of c /3 n − O (√ n ) for c ≥ 2; we prove the stronger particular bounds of 7/6 n − O (√ n ) for c = 3, 54/35 n − O (√ n ) for c = 4, 607/315 n − O (√ n ) for c = 5, 1592/693 n − O (√ n ) for c = 6, 7985/3003 n − O (√ n ) for c = 7, and 19402/6435 n − O (√ n ) for c = 8.

We consider the problem of constructing multiple description scalar quantizers and describing the achievable rate-distortion tuples in that setting. We model this as a combinatorial optimization problem of number arrangements in a matrix. This approach gives a general technique for deriving lower bounds on the distortion at given channel rates. This technique is constructive, thus allowing an algorithm that gives an upper bound. For the case of two communication channels with equal rates, the bounds coincide, thus giving the precise lowest achievable distortion at fixed rates. The bounds are within a small constant for a higher number of channels. To the best of our knowledge, this is the first result involving systems with more than two communication channels.

Given a set of n elements each of which is either red or blue, it is known that in the worst case $n-\nu(n)$ pairwise equal/not equal color comparisons are necessary and sufficient to determine the majority color, where $\nu(n)$ is the number of 1-bits in the binary representation of n. We prove that $\frac{2n}{3} - \sqrt\frac{8n}{9\pi} + O(\log n)$ such comparisons are necessary and sufficient in the average case.

A function $f:\Re \to \Re $ is k-modal if its kth derivative has a unique zero. We study the problem of finding the smallest possible interval containing the unique zero of the kth derivative of such a function, assuming that the function is evaluated only at integer points. We present optimal algorithms for the case when k is even and for $k = 3$ and near-optimal algorithms when $k \geqslant 3$ and odd. A novel generalization of Kraft’s inequality is used to prove lower bounds on the number of function evaluations required. We show how our algorithms lead to an efficient divide-and-conquer algorithm to determine all turning points or zeros of a k-modal function. Unbounded k-modal search is introduced and some problems in extending previous approaches for unbounded searching to the k-modal case are discussed.

Bounds are obtained for the solution to the divide-and-conquer recurrence \[ M( n ) = \max \limits_{k_1 + \cdots + k_p = n} ( M( k_1 ) + M( k_2 ) + \cdots + M( k_p )+ \min ( f ( k_1 ), \cdots ,f ( k_p ) ) ), \] for nondecreasing functions f. Similar bounds are found for the recurrence with “min” replaced by “sum-of-all-but-the-max.” Such recurrences appear in the analysis of various algorithms. The bounds follow from analyses of partition trees.

A function is unimodal if it strictly increases to a unique maximum and then strictly decreases. The problem of determining the smallest possible interval containing the maximum of a unimodal function, by probing only at integer values is studied. In the finite case, the search takes place over the range 0 to N, while in the infinite case the search takes place over the nonnegative integers. The analyses are based on an unusual Fibonacci version of Kraft’s inequality.

Abstract Algorithmic presentations are given for three calendars of historical interest, the Mayan, French Revolutionary, and Old Hindu.

Given a lion and a man, their initial positions, and restrictions on their ranges and speeds, how quickly can the lion get within a given distance from the man? We consider the case in which the lion and man are restricted to the interior of a circle and each is limited to the same speed. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Given a function $F:N^ + \to \{ X,Y\} $ with the property that if $F(n_0 ) = {\text{Y}}$ then $F(n) = {\text{Y}}$ for all $n > n_0 $, the unbounded search problem is to use tests of the form “is $F(i) = {\text{X}}$?” to determine the smallest n such that $F(i) = {\text{Y}}$; the “cost” of a search algorithm is a function $c(n)$, the number of such tests used when the location of the first Y is n. A solution to this search problem specifies a prefix-free, binary encoding of the positive integers in which the cost $c(n)$ is the number of bits used to encode n It is shown that the “ultimate algorithm,” of Bentley and Yao [Inform. Process. Lett., 5 (1976), pp. 82–87], which is within an additive $\Theta (\lg ^ * n)$ factor of a lower bound on the cost of this problem, is “far” from optimal in the sense that it is just the second in an infinite sequence of search algorithms, each of which is much closer to optimality than its predecessor. A corresponding sequence of lower bounds is also given, based on Kraft’s inequality, each of which is much stronger than its predecessor. Diagonalizing over this sequence of search algorithms yields an algorithm, which is given explicitly in a Pascal-like notation, that is within an additive factor of $\alpha (n) + 2$ of the corresponding lower bound, where $\alpha (n)$ is a functional inverse of Ackermann’s function—an extremely slowly growing function. For each search algorithm, the corresponding prefix-free, binary encoding of the integers is given, together with the decoding algorithm. Finally, algorithms/encodings are constructed that differ from the lower bounds by only negligible amounts even for the asymmetric case in which the cost of a Y answer and the cost of an X answer are not the same. In Part II it is shown how to continue the construction to get a transfinite sequence of dramatically better algorithms/encodings and lower bounds.

Given a function $F:N^ + \to \{ X,Y\} $ with the property that if $F(n_0 ) = Y$ then $F(n ) = Y$ for all $n > n_0 $, the unbounded search problem is to use tests of the form “is $F(i) = X$?*#821; to determine the smallest n such that $F(n) = Y$; the “cost” of a search algorithm is a function $c(n)$, the number of such tests used when the location of the first Y is n In Part I of this paper it is shown how to construct an infinite sequence of algorithms, each of which is much closer to optimality than its predecessor. Diagonalizing over this sequence yields a new algorithm that is far better than any of the algorithms in the sequence: this “omega-th” algorithm is within an additive factor of $\alpha (n) + 2$ of the corresponding lower bound, where $\alpha (n)$ is a functional inverse of Ackermann’s function—an extremely slowly growing function. In this paper the construction techniques are generalized to get dramatically better algorithms and lower bounds ad infinitum. Specifically, for each ordinal $\iota < \epsilon _0 $, an algorithm is given that is dramatically closer to optimality than the algorithm corresponding to a smaller ordinal. All algorithms constructed for t Eo are proved to be optimal in a strong sense. Parallel results for the asymmetric case are also given.

Abstract We present a modification of the spring‐embedder model of Eades [Congressus Numerantium, 42, 149–160, (1984)] for drawing undirected graphs with straight edges. Our heuristic strives for uniform edge lengths, and we develop it in analogy to forces in natural systems, for a simple, elegant, conceptually‐intuitive, and efficient algorithm.

Abstract A unified, algorithmic presentation is given for the Gregorian (current civil), ISO, Julian (old civil), Islamic (Moslem), and Hebrew (Jewish) calendars. Easy conversion among these calendars is a byproduct of the approach, as is the determination of secular and religious holidays.

Binary search trees with costs α and β, respectively, on the left and right edges (lopsided search trees) are considered. The exact shape, minimum worst-case cost, and minimum average cost of lopsided trees ofninternal nodes are determined for nonnegative α and β; the costs are both roughly logp(n+ 1) wherepis the unique real number in the interval (1. 2] satisfying 1/pα+ 1/pβ= 1. Search procedures are given that come within a small additive constant of the lower bounds. Almost-optimum algorithms for the lopsided case of unbounded searching are also obtained. Some extensions to nonconstant costs are briefly sketched.

The solution of the divide-and-conquer recurrence\[ M(n)\mathop {\max }\limits_{1 \leqq k < n} (M(k) + M(n - k) + \min (f(k),f(n - k))) \]is found for a variety of functions f. Asymptotic bounds on $M(n)$ are found for arbitrary nondecreasing f, and the exact form of $M(n)$ is determined for f nondecreasing and weakly concave. As a corollary to the asymptotic bounds, it is shown that $M(n)$ remains linear even when f is almost linear. Among the exact forms determined: For $f(x) = \lfloor {\lg x} \rfloor $, the solution is $M(n) = (M(1) + 1)n - \lfloor {\lg n} \rfloor - \nu (n)$ where $\nu (n)$ is the number of 1-bits in the binary representation of n. For $f(x) = \lfloor {\lg x} \rfloor $, the solution is $M(n) = (M(1) + 1)n - \lceil {\lg n} \rceil - 1$, while for $f(x) = \lceil {\lg (x + 1)} \rceil $, thesolution is $M(n) = (M(1) + 2)n - \lfloor {\lg n} \rfloor - \nu (n) - 1$.

A new methodology for the automatic layout of integrated circuits is presented. The methodology, based on a hierarchical description of the circuit, is a hybrid between standard cell and fully custom, having the advantages of both. It has the ease of placement and routing of standard cell, combined with the ability to handle large numbers of diverse cells as in fully custom. The methodology has been implemented and applied to several circuits, with very encouraging results.

Abstract The expected costs of the matchings found by various divide‐and‐conquer heuristic algorithms are calculated, under the assumption that the vertices to be matched are uniformly distributed in the unit square. The expected times of the algorithms are calculated as well.

We consider the following problem: Given n points in a unit square in the Euclidean plane, find a matching of the points such that the cost (i.e., the sum of the lengths of the edges between matched points) is minimum. In particular, we present a class of linear time heuristic algorithms for this problem and analyze their worst case performance. The worst case performance of an algorithm is defined as the greatest possible cost, as a function of n, of the matching produced by the algorithm on a set of n points. Each of the algorithms studied here divides the unit square into a few smaller regions, and then is applied recursively to the points in each of these regions.

We show that the cost (length) of the shortest traveling salesman tour through n points in the unit square is, in the worst case, $\alpha _{{\text{opt}}}^{{\text{tsp}}} \sqrt n + o(\sqrt n )$, where $1.075 \leqq \alpha _{{\text{opt}}}^{{\text{tsp}}}\leqq 1.414$. The cost of the minimum matching of n points in the unit square is shown to be, in the worst case, $\alpha _{{\text{opt}}}^{{\text{mat}}} \sqrt n + o(\sqrt n )$, where $0.537 \leqq \alpha _{{\text{opt}}}^{{\text{mat}}} \leqq 0.707$. Furthermore, for each of these two problems there is an almost linear time heuristic algorithm whose Worst case cost is, neglecting lower order terms, as low as b Bible.

From its obscure beginnings in the 1950s, the evaluation of the Polish postfix form of arithmetic expressions has been the ne plus ultra of programming examples requiring a push down stack. In this note, which has primarily pedagogical interest, I respond to a suggestion by Deshowitz (1980) that recursion ought to yield a reasonable algorithm without a stack. Of course, the general techniques of Chandra (1973, Theorem 2.19) or Mayoh (1972) could be applied to the usual stack algorithm to eliminate the stack in favour of recursion. That is an unsatisfying approach, however, because it requires a very powerful tool to resolve an elementary problem and because it requires an unnecessary understanding of the stack mechanism. Here a different tack is pursued, one that yields an extremely simple and elegant recursive algorithm almost directly from the definition of Polish postfix.

Finding a minimum weighted complete matching on a set of vertices in which the distances satisfy the triangle inequality is of general interest and of particular importance when drawing graphs on a mechanical plotter. The “greedy” heuristic of repeatedly matching the two closest unmatched points can be implemented in worst-case time $O(n^2 \log n)$, a reasonable savings compared to the general minimum weighted matching algorithm which requires time proportional to $n^3 $ to find the minimum cost matching in a weighted graph. We show that, for an even number n of vertices whose distances satisfy the triangle inequality, the ratio of the cost of the matching produced by this greedy heuristic to the cost of the minimal matching is at most ${}_3^4 n^{\lg _2^3 } - 1$, $\lg _2^3 \approx 0.58496$, and there are examples that achieve this bound. We conclude that this greedy heuristic, although desirable because of its simplicity, would be a poor choice for this problem.

Various algorithms have been proposed for producing tidy drawings of trees–drawings that are aesthetically pleasing and use minimum drawing space. We show that these algorithms contain some difficulties that lead to aesthetically unpleasing, wider than necessary drawings. We then present a new algorithm with comparable time and storage requirements that produces tidier drawings. Generalizations to forests and m-ary trees are discussed, as are some problems in discretization when alphanumeric output devices are used.

The problem of finding near optimal perfect matchings of an even number n of vertices is considered. When the distances between the vertices satisfy the triangle inequality it is possible to get within a constant multiplicative factor of the optimal matching in time O(n2 log K) where K is the ratio of the longest to the shortest distance between vertices. Other heuristics are analyzed as well, including one that gets within a logarithmic factor of the optimal matching in time O(n2 log n). Finding an optimal weighted matching requires t(n3) time by the fastest known algorithm, so these heuristics are quite useful. When the n vertices lie in the unit (Euclidean) square, no heuristic can be guaranteed to produce a matching of cost less than [equation] in the worst case. We analyze various heuristics for this case, including one that always produces a matching costing at most [equation]. In addition, this heuristic also finds a traveling salesman tour of the n vertices costing at most [equation]. A different one of the heuristics analyzed produces asymptotically optimal results. It is also shown that asymptotically optimal traveling salesman tours can be found in O(n log n) time in the unit square.

This paper describes a project we have recently started for automating introductory computer science courses. Why should these courses be automated? At the University of Illinois there are currently about 2000 students per semester taking various introductory programming courses: engineers, social scientists, teachers, physical scientists, computer science majors, etc., each group having its own particular needs. These courses are taught in sections of about 100 students each, with an additional hour of discussion in groups of about 20 students. In our experience it is very difficult to organize these courses in such a way that students both learn something and are happy with the material presented. The main difficulty seems to come from the fact that a beginning programmer needs a lot of individual help, and this cannot be provided in large sections. We are now convinced that these courses cannot be improved within the current setup, and since enrollments in these courses are increasing, the situation is bound to grow worse unless something new is tried. We assume that the situation we have described is typical of many large universities.

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is only moderately longer than in completely balanced trees. Trees of bounded balance differ from other classes of binary search trees in that they contain a parameter which can be varied so the compromise between short search time and infrequent restructuring can be chosen arbitrarily.

A new class of binary search trees, called trees of bounded balance, is introduced. These trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is only moderately longer than in completely balanced trees. Trees of bounded balance differ from other classes of binary search trees in that they contain a parameter which can be varied so the compromise between short search time and infrequent restructuring can be chosen arbitrarily.

The establishment of lower bounds on the number of comparisons necessary to solve various combinatorial problems is considered.Some of the new results are : (a) given two finite sets of real numbers, A and B, where n = max ( I A I , I B I ), O(n.log n) comparisons are required to determine if A = B, even when comparisons are allowed between linear functions of the numbers; and (b) the maximum of a set of n real numbers cannot be computed in fewer than n -1 comparisons if comparisons of only linear functions of the numbers are permitted, but the maximum can be computed in Ilog2n] comparisons if comparisons are allowed between exponential functions of the numbers, KEY WORDS AND PHRASES: optimal algorithms, maximum of a set, determining set equality CR CATEGORIES: 5.24, 5.29

The permutations of the input string achievable by an algorithm which uses a single pushdown stack and M random access storage locations are characterized, and the characterization is used to show that no such algorithm can translate arithmetic expressions from infix to prefix.