Week 8 Assignment 8 (09,10 April)

1. Maximize the value of an arithmetic expression by inserting parentheses (order), and + and * operators: "2 1 3 2 1 1 2" by dynamic programming method. Hint: use the method for matrix multiplications as an example.

2. Calculate the edit distance between sequences 'abracadabra' and 'abacusadabar' using spreadsheet.

3. List edit operations of task 2. How many alternative sets of edit operations are on the minimizing path in the previous example?

4. Construct an example where the nr. of alternative operations (alignments) for the minimal edit distance of two sequences is growing at exponential rate as compared to length of the input n (as n grows).

5. Draw an automaton recognising the set of all strings where every character of {a,b,c} is present an even number of times. Hint: try first on two characters, {a,b}.

6. Bonus (2p): How could shortest path (or other) algorithms for graphs be used in checking or validating different automata? Check slide 12 from http://www.cs.ioc.ee/~jaan/teorinf/konspekt/loeng2.pdf (example in todays lecture). Explain your proposed solution on the example.