Suppose you are given three strings of characters: X, Y and Z where jXj = n, jY j = m, and
jZj = n + m. Z is said to be a shue of X and Y i Z can be formed by interleaving the
characters from X and Y in a way that maintains the left-to-right ordering of the characters
from each string.
Give an ecient dynamic-programming algorithm that determines whether Z is a shue
of X and Y. Hint: The values of the dynamic programming matrix you construct should
be Boolean, not numeric.
Class name has to be Shuer and it has to have a method named as isShue which takes
three Strings as input; X, Y and Z respectively and returns Boolean value.
Write a program that computes the percentage of red nodes in a given red-black BST. Test
your program by running at least 100 trials of the experiment of inserting N random keys
into an initially empty tree, for N = 104, 105, and 106, and plot the results. X-axis should
be N and Y-axis should be average percentage of red nodes after 100 trials for each N.
Class name should be PlotRBT.