Algorithms 3027 Assignment 3 The University of Sydney 2019 Semester 1 School of Computer Science
This assignment is for COMP3027 students only. If you have printed this using a black-and-white printer, look at the PDF on a computer to see the colors below.
Description
Congratulations! You have been hired as the lead developer of the new Dance Dance Remix game. In this game, the player is given a sequence of dance moves and is scored based on how well he/she executes the move. The key feature of this game is that instead of using a fixed bank of sequences, it has a dance generation engine that generates them on-the-fly by remixing existing sequences. More precisely, the engine takes two move sequences A and B and remixes them into a single sequence R by interleaving the moves of A and B. The resulting sequence R is called a remix of A and B. Note that the moves of A have to appear in R in the same order that they appear in A, and the same for the moves of B. For example, suppose the sequences A and B are as follows
A = (spin, dab, dab, moonwalk, clap, moonwalk) B = (dab, dab, spin, clap, clap, moonwalk).
then the following are remixes of A and B:
spin, dab, dab, moonwalk, clap, moonwalk, dab, dab, spin, clap, clap, walk
dab, spin, dab, dab, dab, spin, moonwalk, clap, clap, clap, walk, moonwalk
(Note that the colors above are to help distinguish between moves that come from A and moves from B, dab and dab is the same move.)
Some sequences are better than others in terms of the amount of strain it causes the player. Repeating the same moves over and over causes repetitive strain injury and certain moves such as spin are worse than others. To model this, each dance move di is associated with a non-negative strain factor s(di) = si. Given a move sequence T , a repetition of di is a contiguous subsequence of T with at least 2 moves, and the entire subsequence consists of only di. The strain of this repetition is the length of the repetition times si. The strain of a move sequence T is the total strain of all repetitions in T and is denoted RSI(T). For example,
RSI((dab, spin)) = 0
RSI((dab, spin, spin))
RSI((dab, spin, spin, spin))
RSI((dab, spin, spin, spin, dab)) RSI((dab, spin, spin, spin, dab, dab))
In the above, the repetitions are underlined.
= 2s(spin) = 3s(spin) = 3s(spin)
= 3s(spin) + 2s(dab)
Formal specification. In the DDR problem, we are given as input:
• the number of possible dance moves k,
• a list of k possible dance moves D = (d1,d2,…,dk)
• a list of non-negative strain factors S = (s1, s2, . . . , sk) where si is the strain factor of the i-th move (i.e. s(di) = si).
• a sequence A of n moves chosen from D (possibly with repetition).
• a sequence B of m ≤ n moves chosen from D (possibly with repetition).
The goal is to find a remix R of A and B with minimum RSI, and then output both the RSI(R) and the remix R.
1
Task 0: [20 marks]
As a warm up, consider the following problem where we are given as input k dance moves (d1 , d2 , . . . , dk ) and a non-negative strain factor si for each move di, together with a sequence A of n moves.
(a) Describe an algorithm that computes RSI(A).
(b) Argue that your algorithm is correct.
(c) State and explain the complexity of you algorithm (in big-Oh notation).
(d) Implement your algorithm (submit this part to Ed). The input and output format is identical to
task 4, except the last line of input (B) is ignored, and the output is just a number.
Task 1: [20 marks]
Describe an algorithm for the DDR problem (“in plain English”). Your description needs to include
(a) A definition of the subproblems needed by your algorithm (i.e. what does the function OPT(…) represent and what are its parameters).
(b) A definition of the recurrence(s) and base case(s) (i.e. what is the relationship between OPT(. . .) for a subproblem in terms of OPT(. . .) for some other subproblems).
Task 2: [20 marks]
Justify the correctness of your algorithm. In particular, take care to prove that • the recurrence is correct, and
• the base case(s) are correct and sufficient.
Task 3: [20 marks]
State and explain the complexity of your algorithm (in big-Oh notation). Consider both: (a) Time complexity
(b) Space complexity
Make sure you justify the answers you give, do not merely state the values.
Task 4: [20 marks]
Implement your algorithm (in Ed). Each instance is given via standard input using the following format:
4
spin dab moonwalk clap
2513
spin dab dab moonwalk clap moonwalk dab dab spin clap clap moonwalk
In this example,
k = 4 s(spin) = 2 s(dab) = 5 s(moonwalk) = 1 s(clap) = 3
(the number of unique moves)
A = (spin, dab, dab, moonwalk, clap, moonwalk) B = (dab, dab, spin, clap, clap, moonwalk)
The output is a number indicating the RSI of a minimum RSI remix as well as a minimum RSI remix. The output should be printed to screen.
2
For this instance, there is an optimal remix which contains no repetitions at all:
(dab, spin, dab, spin, dab, clap, dab, moonwalk, clap, moonwalk, clap, moonwalk)
Therefore we can output:
Consider a second example:
In this instance there are two optimal remixes, so we could output either:
or we could output:
We do not need to output both. Both remixes have RSI of 3 ∗ s(worm) = 3 ∗ 4 = 12, because the only repetition was of worm and had length 3.
Submission details
• Submission deadline is Sunday 28th April, at 23:59. Late submissions without special consideration will be subject to the penalties specified in the first lecture (5% per day; 0 marks after 10 days late).
• Submit your answers to all tasks as a single document to Canvas. Your work must be typed (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.
• The implementation parts of Tasks 0, 4 must be submitted to Ed.
• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as parts as the precise algorithms, examples, proofs, writing, or code.
• To facilitate anonymous grading, please do not write your name on your submission.
0
dab spin dab spin dab clap dab moonwalk clap moonwalk clap moonwalk
2
bounce worm
34
worm bounce worm worm worm
12
worm bounce worm worm worm
12
worm worm worm bounce worm
3