Information-Theoretical Design of Algorithms
ENG EC 730
Recently developed information-theoretical approach to the analysis and design of computer algorithms. Previous knowledge of information theory or the theory of algorithms is not required, though desirable. Main topics include the complexity of algorithms; P, E, NP, and NP?hard problems; basic concepts of information theory, optimal coding; information-theoretical approach to sorting, order statistics, binary search, decision trees, hashing, minimization of Boolean functions, test, and similar problems; and design of efficient computer algorithms.