- Do Not Write Pseudocode When Describing Your Dynamic Programs Rather Give The Bellman Equation Describe The Matrix It 1 (14.97 KiB) Viewed 15 times
- Do Not Write Pseudocode When Describing Your Dynamic Programs Rather Give The Bellman Equation Describe The Matrix It 2 (47.76 KiB) Viewed 15 times
1. Kleinberg, Jon. Algorithm Design (p. 329, q. 19). We say that a string s is an interleaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequences s' and s", so that s' is a repetition of x and s" is a repetition of y. Give an efficient algorithm that takes strings s, x, and y and decides if s is an interleaving of x and y. Note: We write xk to denote k copies of a concatenated together. We say that a string r' is a repetition of x if it is a prefix of rk for some number k. So ' = 10110110110 is a repetition of x = 101.