Algoritmika 2022/23 sügis

HW10. Dynamic Programming, time warping, choice of essay topic (7th of Nov, 23.59)

Update: Small change from the initial version, highlighted in red. Reduced a and b in ex2.

EX1. This exercise is to get you started with working on your essays.

Essay guidelines can be found here ( https://courses.cs.ut.ee/2022/Algorithmics/fall/Main/Essays ), note that the first deadline is 14th of November! Developing reading and writing skills are an essential part of the course. The idea is to read at least one paper and write a 2-page essay/summary about that paper aiming at describing that content to your fellow coursemates. We have selected 8 papers for you to choose from. Your first task is to choose a paper that you will write an essay about. First, skim all them through (do it quickly). Write in the report which article you are choosing. Attempt to summarise in a few sentences why you think it will be the most interesting article for you to choose. You don't have to necessarily make your essay on the choice of this homework, but it might give you a good start.

EX2. You are given the following recursive function:

def calculate_magic_number(a, b):
    if a == 0:
        return b
    if b == 0:
        return a

    return calculate_magic_number(a, b-1) + calculate_magic_number(a-1, b) + calculate_magic_number(a-1, b-1)

Draw a recursion call tree (a directed acyclic graph) for a=2 b=2 (calculate_magic_number(2, 2)), which demonstrates dependencies of calculations. How many overlapping calls to the function (function calls with the same arguments) are there?

How can you solve this recursion using bottom-up DP approach? Provide a DP solution to the problem.

What is the time complexity of initial recursive implementation? What is the time complexity for DP solution?

EX3. Implement edit distance with following operations (insertion, deletion, substitution, transposition) calculation procedure.

Costs

• Insertion 1
• Deletion 1
• Transposition 1 (switching 2 characters next to each other, ab <->ba).
• Substitution costs (substituting one character with other): t<->d = 0.5, k<->g = 0.5, b<->p = 0.5. Everyhing else is 1.

Demonstrate with a few examples that your code works as intended. Confirm at least one result by hand.

Questions: What is the time and memory complexity of Edit Distance algorithm (consider that you want to reconstruct the sequence of operations)?

Hint

• Check slides!

EX4. Implement the Dynamic Time Warping algorithm and compare the following 6 sequences:

s1: 2 5 5 7 9 1 6 6 8 9 1 6 6 8 9 
s2: 1 1 1 1 3 3 3 3 1 1 1 1 7 7 8 7
s3: 4 2 1 4 8 8 9 3 2 3 2 2 6 9 2 1 1 6 1 
s4: 1 5 7 3 7 2 8 9 9 2 2 3 7 8 
s5: 3 2 2 1 1 8 3 2 6 9 1 6 1 
s6: 1 1 1 3 3 2 1 1 7 7 7

Calculate pairwise DTW distances between all 6 sequences, you should end up with 6x6 matrix, where matrix[i,j] is the distance between s_i and s_j.

Take the most similar pair of sequences (DTW result is minimum) and visualise the DTW calculation in some way. Draw lines, where data points between two sequences are aligned.

EX5. Demonstrate the 1/0 knapsack problem on the following data (choosing the weight constraint as 11, maximizing the cost):

Name Cost Weight
O1 1 1
O2 7 4
O3 14 7
O4 3 2

Explain what is a knapsack problem. Solve it using the dynamic programming approach. Draw the table and explain how it is filled. Show how to get the selected elements. Make an example of a practical problem that can be solved with this approach. What is the space complexity of this solution?
This video might help you get started:

EX6. (Bonus, 2p) Design an efficient algorithm (using dynamic programming, of course) to a) maximise and b) minimise the arithmetic expressions by adding missing *, +, (, ). I.e., given a list of numbers, e.g. 2 1 3 4, calculate the maximizing placement of operations. E.g. (2*1)+(3+4)=9, and (2+1)*3*4=36. Implement it and optimise the possible value of an arithmetic expression with *, +, (, ) for the following sequence where they had been "removed":
[2, 2, 2, 2, 0.4, 1, 0.2, 1, 10, 7, 8, 0.6, 2, 5, 4, 0.1, 1, 1, 7, 1, 0.2, 10, 3, 1, 1, 2, 4, 1, 1, 1, 2, 0.8, 3, 1, 2, 0.1, 2, 1, 2, 0.3, 1, 7, 2, 0.6]
Start by writing down the recurrence you base your solution on. Draw/show a small example (e.g. 3/4 numbers) using your recurrence. Draw the recursion/dependency graph on the small example. Discuss how you can solve it using DP. Now actually solve it (find min and max values of the given longer sequence).

EX7. (Bonus, 4p) Liza Pover and her little brother Lie Pover want to share a round pizza pie that has been cut into 2n equal sector slices along rays from the center at angles α_i = iπ/n for i ∈ {0, 1, . . . , 2n}, where α₀ = α_2n. Each slice i between angles α_i and α_{i + 1} has a known integer tastiness t_i (which might be negative). To be “fair” to her little brother, Liza decides to eat slices in the following way:

• They will each take turns choosing slices of pizza to eat: Liza starts as the chooser.
• If there is only one slice remaining, the chooser eats that slice, and eating stops.
• Otherwise the chooser does the following:
  • Angle α_i is proper if there is at least one uneaten slice on either side of the line passing through the center of the pizza at angle α_i.
  • The chooser picks any number i ∈ {1, . . . , 2n} where α_i is proper, and eats all uneaten slices counter-clockwise around the pizza from angle α_i to angle α_i + π.
  • Once the chooser has eaten, the other sibling becomes the chooser, and eating continues.

Liza wants to maximize the total tastiness of slices she will eat. Describe an O(n³)-time algorithm to find the maximum total tastiness Liza can guarantee herself via this selection process.