Reference no: EM133285085

a). Given a list of stock ticker prices p1, p2, . . . , pn, devise an O(n 2 ) algorithm that finds the longest (not necessarily consecutive) streak of prices that increase or stays the same. For example, given the prices 2, 5, 2, 6, 3, 3, 6, 7, 4, 5, there is the streak 2, 5, 6, 6, 7 of prices that increase or stay the same, but an even longer streak is 2, 2, 3, 3, 4, 5. Similarly, given the prices 1, 9, 2, 4, 3, 5, 8, 7, 7, 9, there can be multiple longest streaks: 1, 2, 3, 5, 7, 7, 9 or 1, 2, 4, 5, 7, 7, 9. In your solution, finding one longest streak is enough. Extra Credit Challenge: by using both dynamic programming and binary search, you can solve this problem in O(n log n) time.

b). You are given an n × m Hershey's bar. Your goal is to devise an algorithm A that takes as input (n, m) and returns the minimal number of cuts needed to divide the bar into perfect squares of either 1x1, 2x2, 3x3, . . ., jxj. With each cut, you can split the bar either horizontally or vertically. The first cut will split the Hershey's bar into two sub-bars; after that each cut splits one remaining sub-bar into two. For example, A(2, 3) = 2 because 2x3 → (2x2, 1x2) → (2x2, 1x1, 1x1).

Question 1. Hint: Notice that no matter the rectangle input n × m, it is always possible to make a perfect square in the first cut. But this strategy will fail. It is possible to find an example input size for which the strategy of picking the cut which creates the largest square leads to extra cuts in total.

Question 2. You can not have fraction, after each cut, the generated rectangles will have integer dimensions (width and height are integer values).

Question 3. Devise a DP algorithm which determines the minimal number of cuts.

Question 4. If your solution has run-time θ(n 3 ), your solution is acceptable. Discuss the runtime of your algorithm, and show that run-time is equal or below θ(n 3 ).