2020/5/1 Programming Puzzle: Exam-Cheating Codes
https://www.wild-inter.net/teaching/comp526/exam-cheat 1/6
back to main page — COMP 526 Applied Algorithmics
Programming Puzzle: ExamCheating Codes
This continuous-assessment exercise consists of a small applied project
with algorithmic and programming components, including a real-time
leaderboard of the competition.
Will you be able to beat your classmates, or even your demonstrator?
As for the Bamboo Trimming Problem, this assignment requires more
thinking than coding, and the focus is as much on the process of finding
solutions as on the actual outcome.
Note: This puzzle is close to the material of Unit 7 & 8 “in spirit”; however, it
does not build on any material from that unit and working on it before we cover
Unit 8 in class does not put you at a disadvantage.
Exam Cheating Codes
Final exams are fast
approaching. While
you are perfectly well
prepared and are
eagerly awaiting the
examination day,
your significant other
is much less relaxed
about the upcoming
exam. Actually,
Sebastian Research Teaching Blog About
2020/5/1 Programming Puzzle: Exam-Cheating Codes
https://www.wild-inter.net/teaching/comp526/exam-cheat 2/6
desperate is the appropriate term. You decide to help.
The most frightening test, COMP666, is a multiple-choice exam with 20
questions, and each question requires a single Yes/No answer. You are
confident that you can perfectly answer any possible question on behalf of
your better half, but of course, the main challenge is how to communicate
the answers to your loved one after you left the exam. (To your great relief,
the instructor chose not to randomize questions or shuffle answers.)
Clearly, you are not able to enter the exam hall once you have left, but you
arrange with your significant other the following code: Honking once (on
your moped parked in the side street next to the building) will mean Yes,
quickly honking twice means No. Unfortunately, as you figured out from
painful experimentation, you have only time to send 10 Yes/No answers
before campus police politely removes you (and your irritating source of
noise) from university premises.
Without knowing the possible answers in advance, can you guarantee a good mark
for your sweetheart?
Formalization
Clearly, the correct answers to the 20 Yes/No questions of the exam can be
given an array of 20 bits , where (for ) means that
the correct answer to the th question is Yes, whereas means the
answer is No.
Likewise, your honking “message” can be encoded as an array of 10 bits
.
The task now consists in finding a encoding function
and a decoding function for you respectively your
significant other to memorize. Your goal is to get the best guaranteed mark
for your sweetie, i.e., to find and so that is as small
as possible. Here, denotes the Hamming distance, and the maximum is
taken over all possible bit arrays of size 20.
Inputs
B[0..20) B[i] = 1 i = 0, … , 19
i B[i] = 0
H[0..10)
e : {0, 1} → {0, 1
20
}
10
d : {0, 1} → {0, 1
10
}
20
d e maxB dH(d(e(B)),B)
dH
2020/5/1 Programming Puzzle: Exam-Cheating Codes
https://www.wild-inter.net/teaching/comp526/exam-cheat 3/6
▸
1.
2.
1.
2.
Your protocol has to work for any possible set of correct answers , and it
will be tested on all of them.
Design as good a protocol as you can find!
Code template
We prepared a Java implementation of the exam sitting that you will use to
evaluate your protocol:
Java sources
Obey the comments! Once you downloaded the code, replace the marked
sections in ExamCheatingCode with
code for your encoding function and
code for your decoding function.
To compile the simulation, extract the zip archive to a folder and run javac
*java there. To run a simulation use java SitExam . The output is the
minimal number of correctly answered questions that your loved one
could achieve with the help of your protocol.
Deliverables
Submissions are due 4 May on SAM.
This is an individual project; each student has to submit his or her own
solution comprising the following:
The ExamCheatingCode source file.
A document describing how you arrived at the solution (not more
than two pages), which also clearly states your achieved best grade
guaranteed. Report also on dead ends you tried (what did not work),
as well as on arguments why a solution of a certain quality is not
possible.
Grading
The overall mark will consist of a weighted average.
B
2020/5/1 Programming Puzzle: Exam-Cheating Codes
https://www.wild-inter.net/teaching/comp526/exam-cheat 4/6
▸
▸
60% for the description.
40% for the quality of the achieved solutions. The baseline is the
solution that George has found; in principle you could get more than
100% for this subtask if you manage to beat his solution!
Collaboration
This programming puzzle is mainly an individual project, and you have to
submit you own solution. In particular, the description of your solution
must be a single-author document.
Collaboration in small groups (not more than five students) on the
conceptual level(discussing ideas, not sharing entire solutions) are
accepted, but they must be declared in the description document, including
proper mention of others’ contributions.
Leaderboard
We run a (voluntary, anonymous) leaderboard of the current best solution.
When you have a code tried in the simulation, use the below form to share
your achievement with the rest of the class!
2020/5/1 Programming Puzzle: Exam-Cheating Codes
https://www.wild-inter.net/teaching/comp526/exam-cheat 5/6
Highscores
The plots below show all answers over time. Recall that higher is better.
New submissions are immediately added at the right end, but might take a
few seconds and refreshing before they show up.
Never submit passwords through Google Forms.
Thi t t i ith t d d d b G l
Exam-cheating code leaderboard
Enter the grade guarantee (number of correct questions, as output by the
simulation) you were able to achieve.
* Required
vital user name *
Your answer
Grade guarantee *
Your answer
Submit
Forms
2020/5/1 Programming Puzzle: Exam-Cheating Codes
https://www.wild-inter.net/teaching/comp526/exam-cheat 6/6