
Accession Number : AD0748762
Title : A New Proof of the TC 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 TC 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