An algorithm is presented which constructs an optimal binary search tree for an ordered list of n items, and which requires subquadratic time if there is no long sublist of very low frequency items. For example, time = O(n^1.6) if the frequency of each item is at least ε/ n for some constant ε > 0.

A second algorithm is presented which constructs an approximately optimal binary search tree. This algorithm has one parameter, and exhibits a tradeoff between speed and accuracy. It is possible to choose the parameter such that time = O(n^1.6) and error = o(l).

A new O(nL)-time algorithm is given for finding an optimal prefix-free binary code for a weighted alphabet of size n, with the restriction that no code string be longer than L. An O(nL logn)-time algorithm is given for the corresponding alphabetic problem problem, which is equivalent to optimizing a dictionary of n words, implemented as a binary tree of height h

This paper defines a new sliced layout architecture for compilation of arbitrary schematics (netlists) into layout for CMOS technology. This sliced architecture uses over-the-cell routing on the second metal layer. We define three different architectures with simple folding, interleaved folding and unrestricted folding. We present a linear time algorithm for placement of components in architectures with simple folding. We prove interleaved folding is NP-hard and give an algorithm of complexity O(nbH/6) for approximating an optimal module, where n is the number of components, b is the width of the least-area module, H is the total height of the components, and 6 > 0 is arbitrarily chosen. The error of this algorithm (i.e. the difference between the area of the resulting module and the optimal one) is O (nb6). We conclude the paper with a proof that the architecture with interleaved folding is as good as the architecture with unrestricted folding with respect to area minimization of the total layout.