Sebastian Research Teaching Blog About mainpage — COMP 526AppliedAlgorithmics
Programming Puzzle: Exam- Cheating 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.
Exam Cheating Codes
Final exams are fast
approaching. While
you are perfectly well
prepared and are
eagerly awaiting
examination day,
your significant other
is much less relaxed
about an upcoming
exam. Actually,
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, what is the worst mark you can guarantee for your sweetheart?
Formalization
Clearly, the correct answers to the 20 Yes/No questions of the exam can be given as 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 an 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 length 20.
Inputs
Your protocol has to work for any possible set of correct answers , and it will be tested on all of them.
B
01}1 ,0{ → 02}1 ,0{ : e
)B,))B(e(d(Hd Bxam
e d 02}1 ,0{ → 01}1 ,0{ : d
0 = ]i[B i 91,…,0 = i 1 = ]i[B )02..0[B
Hd
)01..0[H
Design as good a protocol as you can find!
Code template
We prepared a Python implementation of the exam sitting that you will use to evaluate your protocol:
Python sources
Obey the comments! Once you have downloaded the code, replace the marked sections in examCheatingCode.py with
1. codeforyourencodingfunctionand 2. codeforyourdecodingfunction.
python3
sitExam.py
examCheatingCode.py
To run the simulation, extract the zip archive to a folder and run
there. The output is the worst mark (minimal number of correctly answered questions) that your loved one could achieve with the help of your protocol.
Deliverables
Submissions are due 12 May on SAM.
This is an individual project; each student has to submit his or her own
solution comprising the following:
1. The sourcefile.
2. Adocumentdescribinghowyouarrivedatthesolution(notmore
than two pages), which also clearly states your achieved best guaranteed mark. Report also on dead ends that you tried (what did not work), as well as on arguments why a solution of a certain quality is not possible.
Marking
The overall mark will consist of a weighted average. 60% for the description.
▸
▸
40% for the quality of the achieved solutions. The baseline is the solution that Ben 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 solutions. When you have a code tried in the simulation, use the below form to share your achievement with the rest of the class!
▸
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.
Exam-cheating code leaderboard
Enter the your mark guarantee (number of correct questions, as output by the simulation) you were able to achieve.
*
MWS user name *
Grade guarantee *
Google
。码密交提单表 过通勿切
答回的您
答回的您
交提
填必
Sebastian Wild
ORCID: 0000-0002-6061- 9177
Google Scholar profile DBLP publication list Semantic Scholar Author Page
arXiv Author ID
GitHub profile LinkedIn profile
Website at UoL intranet site at UoL (Old) website TU KL
sebawild at gmail ⋅ PGP wild at liv.ac.uk ⋅ PGP
wild at uwaterloo.ca ⋅ PGP
wild at cs.uni-kl.de
Quick links:
my publications my library
▸ ▸
▸
▸
▸ ▸ ▸
▸ ▸▸
▸ ▸ ▸
▸ ▸
▸