This assignment is worth a total of 50 points.
All homework will be submitted electronically, using the curator system. You may submit your homework in PDF or Postscript form, or in any format that can be opened using Microsoft Word (including plain ASCII text). Note, however, that readability is important to your grade, and that you often need to typeset mathematical equations. If you submit more than one version of your homework, we will store all submissions, but will actually grade the latest one. Make sure that your file contains at the top your name, your ID number, your email address, as well as your partner's name, ID number and email address. All submissions MUST contain the following statement exactly as written here:
I understand the answers that I have submitted. The answers submitted have not been directly copied from another source, but instead are written in my own words.
Two students may work together and jointly submit the homework assignment. If this is done, the submission MUST also contain a statement detailing the contribution of each student to the solution of each problem.
1. Manber 5.11
2. Manber 5.18
3. Let Sigma be an alphabet of symbols, and let X,Y, and Z be strings in Sigma*. Say that Z is a shuffle of X and Y if |Z|=|X|+|Y| and if X and Y occur as disjoint substrings of Z. For example, if X = close and Y = class, then cloclasess, classclose and ccllaossse are all shuffles of X and Y, but clacloesss and classosecl are not.
Describe an efficient algorithm to determine whether Z is a shuffle of X and Y. Let M be the length of X and N the length of Y. What is the time complexity of your algorithm as a function of M and N?