COMP2111 Assignment
Submission is through give and should consist of:
1. A single pdf file with typeset answers, maximum size 4Mb. Prose should be typed, not handwritten.
Use of LATEX is strongly encouraged, but not required.
2. A file partner.txt with a single line on the format. z . This must be the zID of your
group partner. For individual submissions, write your own zID.
Submit your work using the web interface linked on the course website, or by running the following on a
CSE machine
give cs2111 assn3 assn3.pdf partner.txt
This assignment is to be done in pairs. Individual submissions are discouraged, but will be accepted. Only
one member of the pair should submit. Work out who will submit ahead of time—duplicate submissions
are extremely annoying to sort out.
Late submission is allowed up to 5 days (120 hours) after the deadline. A late penalty of 5% per day will
be deducted from your total mark.
Discussion of assignment material with others is permitted, but you may not exchange or view each
others’ (partial) solutions. The work submitted must be your own, in line with the University’s plagiarism
policy.
Background This assignment is an open-ended research task where you apply Hoare logic to an algo-
rithm of your choice.
This means you should start by choosing an algorithm! It’s your choice, but keep the following in mind:
The algorithm should contain at least one loop.
Your need to find an algorithm that makes the tasks below feasible in the given timeframe. If the
algorithm is longer than 10-20 lines or so, you should probably choose something simpler.
You need an algorithm that you can meaningfully specify with a Hoare triple, and reason about with
Hoare logic.
What does the last bullet point mean exactly? I’ll give some examples. You want to avoid:
Algorithms that are probabilistic, in the sense that they aren’t guaranteed to always give a correct
answer. An example is the Miller-Rabin primality test.
Algorithms that give approximate answers only, such as numerical algorithms.
Concurrent or parallel algorithms.
1
Algorithms that have fuzzy specifications, where it’s difficult to characterize precisely what it means
for the output to be correct. Examples include most algorithms in machine learning and image
processing.
Algorithms that require non-compositional control flow operators, such as goto, break or continue.
(But you can probably find an alternative way to formulate the algorithm that doesn’t require these).
A good place to start looking for algorithms is the table of contents of your favourite algorithms text-
book [CLRS09, Knu68, Knu69, Knu73, KT06], or the Wikipedia list of algorithms.1
Once you’ve found an algorithm, do ask your tutor, or Johannes, for input on your choice! We are happy
to offer advice on your choice.
1https://en.wikipedia.org/wiki/List_of_algorithms
2
Problem 1 (30 marks)
Present your algorithm, giving at least the following information:
1. The name of the algorithm
2. The origin of the algorithm. Is it known Who invented it? Cite the original paper that introduced the
algorithm, if possible.2 Also cite any other sources you’ve consulted in preparing this assignment.
3. The purpose of the algorithm. What problem does the algorithm solve? What are the requirements
that the algorithm is designed to meet?3
4. Give pseudocode for the algorithm.
5. A brief explanation of the pseudocode, to help the reader understand the algorithm.