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:

1972-06-01

Pagination or Media Count:

32.0

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 On log n operations and On 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