HW8. Dynamic Programming, time warping, choosing essays (4th of Nov, 23.59)
EX1. 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. Note, that you may still change the article later if you wish - but usually, it is better to stick to the choice.
The guidelines and articles can be found via https://courses.cs.ut.ee/2019/algorithmics/fall/Main/Essays
Note, that your first submission will be read by two co-students who will give feedback about your writing. Based on that feedback you should improve your essay and submit a final version for grading. Thus, giving constructive feedback to other students that will help them improve their writing is yet another important skill that you will learn. You can find the essay timeline on the HW page.
EX2. Implement the dynamic time warping algorithm and compare the following 6 series:
s1: 2 5 5 7 9 1 6 6 8 9 1 6 6 8 9
s2: 1 2 5 6 7 2 6 9 9 9 2 6 7 8
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 4 6 8 8 2 1 2 7 9 2 7 9 9 9 9 9 9
Visualise pairs of sequences by “stretching time” (dynamic time warp) in some way, so that with three pairs all 6 sequences are “covered”. Start from the most similar pair of them all, then the most similar pair where neither sequence is among the first pair, and finally the last (third) pair. Provide visualisations and calculated pairwise distances for the pairs.
EX3. Implement a simple edit distance calculation procedure (you can also use the spreadsheet if you want, especially for tracing of operations manually). Calculate edit distance between 'abracadabra' and 'abarcababbra'. Reconstruct the alignment or set of operations to get the second sequence from the first.
EX4. Demonstrate the knapsack problem on the following data (choosing the weight constraint as 6):
Name Cost Weight
O1 2 3
O2 7 2
O3 5 1
O4 8 4
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:
EX5. In EX4 we discussed how to solve the knapsack problem using the NxM matrix, where N is the number of items and M is the number of units of the capacity of our bag. In practice, however, not all N rows are necessary at every step of the algorithm. Discuss ways to make the solution from EX4 more memory efficient. Demonstrate how your new memory-efficient version of the algorithm will solve the knapsack problem from EX4.
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 1 2 1 1 3 6 10 1 2 2 1 6 1 2 2 1 7 2 1 8 2 1 1 4 7 8 10 7 3 1 4 4 5 2 1 2 2 2 1 1 1 2 3. \\ Make sure to write down the recurrence relation you based your solution on.