Accession Number : AD0748762

Title :   A New Proof of the T-C Algorithm.

Descriptive Note : Technical summary rept.,

Corporate Author : WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s) : Hu,T. C.

Report Date : JUN 1972

Pagination or Media Count : 32

Abstract : An algorithm for constructing an alphabetic binary tree of minimum weighted path length was suggested by Hu and Tucker. The algorithm called the T-C algorithm needs O(n log n) operations and O(n) storage locations, where n is the number of terminal nodes in the tree. Although the algorithm is simple to state, the associated proof was extremely complicated and long. Here a more revealing and comparatively shorter proof is given. (Author)

Descriptors :   (*MATHEMATICAL LOGIC, TOPOLOGY), SEQUENCES(MATHEMATICS), BINARY ARITHMETIC, COMPUTER PROGRAMMING, ALGORITHMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE