Question

26. Consider a String pattern AATAATAC over the alphabet {A,T.C,G). For these questions, adopt the convention that Strings are O-indexed. (a) (2 points) Give the Boyer-Moore Last() function for this pattern. (b) (2 points) Give the KMP Failure() function for this pattern. (c) (2 points) Draw a suffix tree for this pattern, with leaf nodes storing the index of the where that suffix begins. its set. 27. Begin with the keys 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, each (a) (2 points) Apply the following sequence of union operations and show the resulting Union-Find data structure either in a linked node picture or as an array of parent nodes (your choice). You may choose how to break ties. Union (2,10). Union(1,7), Union (4,6), Union (3,5), Union(2,8), Union(1,3), Union (10,4). (b) (1 point) How many disjoint sets are created after these Union operations are per- formed?

**Only need to answer question 27**

Union(2,10) - So each key above is in its own set so if we perform union(2,10) im assuming it should make a set that contains both key such as s₁ = {2, 10} or using an array for example

-1	-1
2	10

-1 meaning vertices in own set then this should result in after union as

-2	2
2	10

-2 being the number of vertices, positive 2 being the parent of 10

Answer 1