Homework: Homework 9. Dynamic Programming

Assigned

• November 17, 2026

Due

• November 27, 2026 10:00pm

Collaboration

Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\) If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

1. 14.3-3 Consider the antithetical variant of the matrix-chain multiplication problem where the goal is to maximize the number of scalar multiplications. Does this problem exhibit optimal substructure?

2. 14.3-5 Suppose that the rod-cutting problem also has a limit on the number of pieces of length i allowed to be produced. Show that the optimal-substructure property no longer holds.

3. 14-1 Given a directed acyclic graph with real valued edge weights, find the longest weighted simple path from s to t.

4. 14-2 Longest Palindrome subsequence: Given a string, find the longest palindrome subsequence

5. 14.4-6 modified  Give an O($n^2$) time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers

Bonus. 14.4-6 Give an O(nlgn) algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers