HW 03 09.10 (16-18) Multi-pattern matching, 2D, Edit distance

1. Study the pattern matching with duels. Try to illustrate it on 1-D pattern exact matching. What kind of preprocessing and data structures would be needed?

2. Think of 2-D pattern matching of rectangles with exactly 90,180,270 degree rotations. Sketch an algorithm for such pattern matching.

3. Create a program or spreadsheet version of the edit distance calculation algorithm. Calculate distance between S=IMAGINAATION, T=MEGANATIOON

4. Provide a list of actual edit operations for one valid trace of operations. (work backwards along any "minimizing path" - each path is valid)

5. Construct an example of sequences for which there are many valid potential traces for achieving certain edit distance. How many such valid “paths” can you identify as measured by the length of the sequence(s), n. Try to create as many as possible such equal alternative traces.

6. (Bonus, 3p) Study some literature and describe briefly which basic ideas have been proposed for 2D pattern matching where arbitrary rotations have been applied.