Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment
WARNING: To receive credit for this assignment,
you must submit the academic integrity
declaration. Do so before starting work on the
questions.
Coverage: All guides; all modules.
This assignment consists of a written component and a programming component. Please
read the course website carefully to ensure that you submit each component correctly.
All the questions in the written component should be submitted as a single pdf file with the
name a4written.pdf. Although scanned documents are acceptable, please keep in mind that
only legible writing will be marked (subject to the markers’ discretion) and that MarkUs forces
a limit of 5000 KB per file, which might be exceeded by high resolution scans.
Note: In assignment questions that specify the use of a particular paradigm, you are expected
to come up with a new algorithm using that paradigm. It is not sufficient to implement a class
example as a helper function and declare that the paradigm has been used.
Written component
For full marks, you are expected to provide a brief justification of any answer you provide.
W1. [4 marks] We can attempt to solve the Noise Elimination problem (defined in Assignment
2) by choosing the character in each position at random, where for each position, 0
and 1 are equally likely to be chosen. Using the instance {111, 011, 101, 110, 000} from the
solutions in part (b) of W2 in Assignment 2, determine the expected maximum distance.
Briefly discuss how this compares to the worst-case for Algorithm A and the optimal
solution for the example.
W2. [7 marks] In this problem we will consider the greedy algorithms for Noise Elimination
discussed in Assignment 2. The goal is to use the algorithms as approximation algorithms
for the related problem of Noise Minimization. Here the goal is to find a string that is
the minimum total distance from all input strings.