Problem 1. (Bead chain) You are given a long chain of colored beads. At rst the chain looks random to you, but after looking at it for a little bit you see some patterns emerge. Specically, you notice that there are parts in the chain that are symmetric; the order of colors from left to right is the same as right to left. Excited by your discovery you decide to cut up your beads into shorter symmetric chains. Your goal is to do so using as few cuts as possible so that each segment is symmetric. (Note that a single bead is considered to be a symmetric chain.) You cannot change the order of heads. 1. (Not to be handed in) Here is an example of chain of beads, try to nd the optimal cuts. [red, blue, green, blue, red, red, red, red, red, red, red, red, blue, yellow, blue, red] 2. As input you are given the sequence of n beads in an array B. To make your life easier you are also given an n X n table 8 of True/ False values. S [2H3] is True if the chain starting from bead 2' to j is symmetric, false otherwise. Note that only half of S is lled as i g 3'. Design a DP algorithm that nds a division of the chain into symmetric chains using the minimum number of cuts. Your algorithm should return both the number of cuts as well as the subchains them- selves (i.e. the location of the cuts). 3. In the previous part we said that S is given as part of the input. Now we ask you to nd an algorithm that given B computes the values of S. (This problem can be solved by an iterative algorithm, you don't have to use DPfor if.)