HW10. Dynamic Programming, Time Warping (15th of Nov, 23.59)
Update: Small change from the initial version. Added EX1
EX1.
Explain the concept of dynamic programming. What are the key steps to applying dynamic programming techniques? Feel free to research materials out of the course and feel free to share some nice materials you have found. Make use of this exercise to grasp a general understanding of DP.
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. As part of the Walmart Real Estate team, You are required to understand the energy consumption pattern of different assets like refrigeration units, dehumidifiers, lighting, etc. installed in the retail stores. Below is given a time series of energy consumption of different assets during different times of the day. Any two-time series can be compared using Euclidean distance or other similar distances on a one-to-one basis on the time axis.
Implement the Dynamic Time Warping algorithm and compare the following 6 sequences:
Series 1 (Refrigeration) : 1,4,5,10,9,3,2,6,8,4 Series 2 (Humidifier): 1,7,3,4,1,10,5,4,7,4 Series 3 (Lighting): 1, 3, 4, 6, 5, 7, 5, 3, 1, 1 Series 4 (Display): 2, 2, 5, 6, 6, 7, 4, 3, 2, 1 Series 5 (Automation): 3, 2, 3, 1, 4, 7, 8, 3, 4, 3 Series 6 (Water Heating): 1, 3, 9, 7, 8, 6, 7, 2, 4, 2
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 visualize 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, 2p) Tim the Beaver needs to study for exams, but it’s getting warmer, and Tim wants to spend more time outside. Tim enjoys being outside more when the weather is warmer: specifically if the temperature outside is {$ t $} integer units above zero, Tim’s happiness will increase by {$ t $} after spending the day outside (with a decrease in happiness when {$ t $} is negative). On each of the {$ n $} days until finals, Tim will either study or play outside (never both on the same day). In order to stay on top of coursework, Tim resolves never to play outside more than two days in a row. Given a weather forecast estimating temperature for the next {$ n $} days, describe an {$ O(n) $}-time dynamic programming algorithm to determine which days Tim should study in order to increase happiness the most.
EX8. (Bonus, 2p) You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with n rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung. The natural strategy is to natural to try the binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung {$ n/4 $} or {$ 3n/4 $} depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.
Your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it {$ n $} times (rather than {$ log $} {$ n $} as in the binary search solution). The trade-off: it seems you can perform fewer drops if you’re willing to break more jars. We devise an experiment to this tradeoff works at a quantitative level, given a fixed “budget” of {$ k ≥ 1 $} jars.
- Suppose you are given a budget of {$ k = 2 $} jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most f(n) times, for some function {$ f(n) $} that grows slower than linearly. (In other words, it should be the case that limn → ∞ f(n)/n = 0
- Now suppose you have a budget of {$ k > 2 $} jars, for some given {$ k $}. Describe a strategy for finding the highest safe rung using at most {$ k $} jars. If f k(n) denotes the number of times you need to drop a jar according to your strategy, then the functions {$ f1 $}, {$ f2 $}, {$ f3 $}, . . . should have the property that each grows asymptotically slower than the previous one: limn→∞f k(n)/f k-1(n) = 0 for each {$ k $}.