Brainteaser: If you liked lab1...
David L. Rager
Some of you might like this brainteaser. I haven't solved it for the
specific case given in the writeup, yet, but I have two other
challenges (and solutions) for the problem given. Some of you may
wish to skip (A), since it's a hint for (B).
"A spy is being commissioned by the government to infiltrate a mafia
rank in order to find out who the head honcho is. There are sixteen
potential candidates and the government needs to know which one of
them is the leader. However, the spy only has one chance to pass the
information back to the government before she gets murdered.
On an previously-agreed date, the local radio station will announce
the winning lottery number. This number will be from 0 to inclusive,
and will be saved as a 15 binary digit data in that radio station’s
computer. The spy only has one chance to infiltrate the radio
station’s computer mainframe, change one bit (or none) in that number,
and leave. The broadcaster will announce the number without knowing
that the spy has changed it, and the government agents will listen to
that changed number. The government and the spy don’t know the winning
number in advance and they have no further power to rig the lottery.
To make things more complicated, the spy does not have that much time
in the radio station’s computer room. Therefore, she would not be able
to perform lengthy and complex calculations. Of course, lengthy and
complex is a relative term, but she is a sufficiently accomplished
mathematician and she needs to perform this task in less than one
minute.
What strategy can be done by the spy and the government so that she
can pass the mafia leader’s identity accurately with that one chance?"
http://dharmath.thehendrata.com/2009/10/08/spy-and-radio/
(A) With the above restrictions in mind, how can you encode the head
honcho in a 3 bit number, if you have 1 bit flip.
(B) With the above restrictions in mind, how can you encode the head
honcho in a 27 bit number, if you have 3 bit flips.
(C) With the above restrictions in mind, answer the problem given.
This solution is less like lab1.
Give people a few days to think about it, and then feel free to send
out your solution(s) for a review. There's no E.C. for this -- just
for fun discussion during parties and meals. Don't forget to
prioritize your fp lab and hw.
David
David L. Rager
> (A) With the above restrictions in mind, how can you encode the head
> honcho in a 3 bit number, if you have 1 bit flip.
(A) With most of the above restrictions in mind, except there are only
3 potential head honchos, how can you encode the head
honcho in a 3 bit number, if you have 1 bit flip.
> (B) With the above restrictions in mind, how can you encode the head
> honcho in a 27 bit number, if you have 3 bit flips.
(B) With most of the above restrictions in mind, except there are 27
potential head honchos, how can you encode the head
honcho in a 27 bit number, if you have 3 bit flips.
> "This number will be from 0 to inclusive, and will be saved as a
> 15 binary digit data in that radio station’s computer."
"This number will be from 0 to inclusive (2^15) - 1, and will be saved
David L. Rager
loosely related to the class over the next month or so. I imagine
after a month, we'll all move on, but since we have some time off, our
minds will wander. "Official communication" for CS 352 is done, so
feel free to unsubscribe
[http://groups.google.com/group/utexas-cs352-fall2009/subscribe].
> (A) With the above restrictions in mind, how can you encode the head
> honcho in a 3 bit number, if you have 1 bit flip.
bit is the "odd bit out". Six examples follow. At this point, most
of you can probably complete this function. Compare the performance
of two jump tables to the potential use of 24 conditional jumps. BTW,
due to how the puzzle is worded, I counted bits from left to right
(which is different from usual).
A natural follow up question is (B) [above] and then "how can we
encode a guilty party in 3 bits when there are four guilty
candidates?".
David
/** Returns a 3 bit value such that the guilty bit is the "odd bit out" */
int encode_3bits (int input, int guilty) {
switch(val) {
case 0b000:
switch(guilty) {
case 0:
return 0b100;
break;
case 1:
return 0b010;
break;
case 2:
return 0b001;
break;
}
break;
case 0b001:
switch(guilty) {
case 0:
return 0b011;
break;
case 1:
return 0b101;
break;
case 2:
// do nothing
return 0b001;
break;
}
break;
// and so forth
David L. Rager
In the function "switch(val)" should be "switch(input)". Also, there
need to be default case statements, and I'm sure there are some other
issues.