How to identify m numbers using m/log m checks

By Renata Czarniecka

Here’s an old trick that we found useful for proving some tight complexity lower bounds. You are given m coins, each of weight either a or b, and a modern scale that can tell you the total weight of any chosen subset of coins. How many weighings do …read more

From:: Banach’s Algorithmic Corner

Submit a post

You can use the anonymous submission form to upload information about an event, a blog post or a job posting. It will be published when it is approved by the moderator.

Calendar

October 2024
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
28293031  

Other Posts