dc.contributor.author |
BHADURI, ARITRA |
|
dc.date.accessioned |
2021-07-20T07:01:46Z |
|
dc.date.available |
2021-07-20T07:01:46Z |
|
dc.date.issued |
2020-07 |
|
dc.identifier.citation |
23p. |
en_US |
dc.identifier.uri |
http://hdl.handle.net/10263/7166 |
|
dc.description |
Thesis is under the supervision of Prof. Sourav Chakraborty, ACMU |
en_US |
dc.description.abstract |
We have n coins of two weights. We also have a balance scale to measure the weights of
the coins. The objective is to find the number of heavy coins with as few measurement as
possible. This problem is known as "coin-counting problem". A sub-problem of this problem
is, optimally find if the number of the heavy coins is even or odd. This problem is known as
"coin-parity problem". It was first proposed by "Laszlo Babai"of "University of Chicago".
There is a known adaptive algorithm which solves the coin-counting problem in O(log2n)
time. By modifying that algorithm we can also solve the parity problem in O(logn) time.
The oblivious lower bound of coin-counting problem is O(
p
n). This result was proved by
"Eric Purdy" on the paper "Lower Bound of coin-counting problem" (1). In the first section
of this thesis we have discussed about oblivious lower bound of the counting problem and
showed a tight adaptive (logn) bound on coin parity problem. All these result are based on
the eric purdy’s "Lower Bound of coin-counting problems" paper.
There is a trivial adaptive lower bound of the coin-counting problem which is logn. As we
can see adaptive coin-counting problem does not have a tight bound. The objective of this
thesis is to give an improvement on the lower bound of adaptive coin counting problem. In
chapter 4 we have given a proof of the adaptive lower bound of coin-counting problem is
log2n + loglogn. We interpreted each one of the coin configuration into a boolean-vector.
The main idea is to check which of these Boolean-vectors can go to the same leaf of the
decision tree . This creates a partition of Boolean-vectors. By counting the partitions give us
the total number of leaf nodes in the decision tree. Now taking log of this number gives us
the height of the decision tree and that’s our required lower bound. |
en_US |
dc.language.iso |
en |
en_US |
dc.publisher |
Indian Statistical Institute, Kolkata |
en_US |
dc.relation.ispartofseries |
Dissertation;;2020-12 |
|
dc.subject |
Coin Counting Problem |
en_US |
dc.subject |
Coin Parity Problem |
en_US |
dc.title |
Lower Bound of Coin Counting Problem |
en_US |
dc.type |
Other |
en_US |