HW10. Dynamic Programming, time warping, choice of essay topic (13th of Nov, 23.59)
Update: Small change from the initial version, highlighted in red. Reduced a and b in ex2.
EX1. (1p) This exercise is to get you started with working on your essays.
Essay guidelines can be found here ( https://courses.cs.ut.ee/2023/algorithmics/fall/Main/Essays ), note that the first deadline is 20th 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. (1p) 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. (1p) 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. (1p) 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. (1p) 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, 2p) Lazy Egg Drop: The classic egg drop problem asks for the minimum number of drops needed to determine the breaking floor of a building with n floors using at most k eggs, where the breaking floor is the lowest floor from which an egg could be dropped and break. This problem has a closed form solution, but can also be solved with dynamic programming. However, if the building does not have an elevator, one might instead want to minimize the total drop height: the sum of heights from which eggs are dropped. Suppose each of the n floors of the building has a known positive integer height hi, where floor heights strictly increase with i. Given these heights, describe an O(n3k)-time algorithm to return the minimum total drop height required to determine the breaking floor of the building using at most k eggs.