Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

ALGORITHMICS I (H)

COMPSCI4009 – MOCK EXAM

1. Recall that the basic operations for transforming strings are:

• the insertion of a single character;

• the deletion of a single character;

• the substitution of one character for another.

Given these basic operations, the distance between two strings a and b of lengths m and n, is defined to be the smallest number of basic operations needed to transform a into b.

Letting di,j denote the distance between the ithand jth prefix of the strings a and b respectively, then this distance is defined by the following recurrence relation for 0 < i ≤ m and 0 < j ≤ n:

subject to di,0 = iand d0,j = jfor all 0 ≤ i ≤ m and 0 ≤ j ≤ n.

(a) Construct the dynamic programming table for the two strings:

x = “saturday” and y = “sunday”

and thereby obtain the distance between x and y.

(b) Use the so-called traceback method to obtain an optimal alignment between the strings x and y of part (b) that illustrates clearly a smallest sequence of operations that transforms x into y.

2. Suppose that the Knuth Morris and Pratt algorithm is to be used to search for the first occurrence, if any, of a strings in a text t .

(a) Build the Knuth Morris Pratt (KMP) border table for the following pattern:

s = aabaab

(b) Indicate precisely which character comparisons would be made if the Knuth Morris and Pratt algorithm were used to locate the first occurrence of the strings = aabaabin the text t = aabaaabaabb.

3.     (a) Apply Dijkstra’s shortest path algorithm to the graph below to find all shortest paths between the vertex u and all other vertices.

Include in your answer the steps performed by the algorithm through the changes to the distance and predecessor for each vertex of the graph.