Optimal versus randomized search of fixed length binary words

DOI10.1109/TIT.2002.801478MaRDI QIDQ4677583zbMATH OpenFDO

Authors Helmut Prodinger, Wojciech Szpankowski

Publication date 11 May 2005

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

Full work available at URL https://doi.org/10.1109/TIT.2002.801478

Mathematics Subject Classification ID

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

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

Cited in

(3)

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

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)