Optimal versus randomized search of fixed length binary words

DOI10.1109/TIT.2002.801478zbMATH Open1062.68617MaRDI QIDQ4677583FDOQ4677583

Authors: Helmut Prodinger, Wojciech Szpankowski 

Publication date: 11 May 2005

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Recommendations

• The estimated cost of a search tree on binary words
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• An estimate of mean efficiency of search trees for arbitrary sets of binary words
• Bounding the depth of search trees
• Ratewise-optimal non-sequential search strategies under constraints on the tests

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (2)

• Finding passwords by random walks: how long does it take?
• Can a randomized binary search have an \(O(1)\) complexity at least in practice?

This page was built for publication: Optimal versus randomized search of fixed length binary words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4677583)