CS-B505-Applied Algorithms 3 Solved

Contents
             Problem 1: Pattern-Matching-1                                                                                                                                    2

             Problem 2: Pattern-Matching-2                                                                                                                                    2

               Problem 3: Dynamic Programming-1                                                                                                                        3

               Problem 4: Dynamic Programming-2                                                                                                                        3

           Directions                                                                                                                                                                                 3

           Appendix                                                                                                                                                                                   4

Problem 1: Pattern-matching: The brute-force
Problem 1.1: The brute-force pattern-matching algorithm 

Describe a text D and a pattern P such that the brute-force pattern-matching algorithm runs in Ω(dp) time.The lengths of D and P are d and p, respectively.

Problem 1.2: Python’s str class and pattern-matching

In this part, you are asked to modify three pattern matching programs given to you (See appendix). Run your modified programs for varying-length patterns and show your results.

The count method in Python’s str class takes a text D and a pattern P and returns the maximum number of non-overlapping occurrences of a P within D. As an example ‘cdcdcdcdc’.count(‘cdc’) returns 2.

1.    Modify the brute-force pattern-matching to return non-overlapping occurrences of a P within D.

2.    Similar to the previous question (Problem 1.2.1), do the same on the Boyer-Moore program.

3.    Similar to problem 1.2.1, modify the KMP program.

Problem 2: Experimental Analysis of Pattern-Matching Algorithms 
Perform an experimental analysis of pattern matching algorithms in terms of:

1.    Number of character comparison: Perform an experimental analysis of the efficiency of the brute-force, the KMP and Boyer-Moore pattern matching algorithms for varying-length patterns.

2.    Relative speed comparison: Perform an experimental comparison of the brute-force, KMP, and Boyer-Moore pattern-matching algorithms. Run each algorithm against large text documents using varying-length patterns and report the relative running times.

Problem 3: Matrix-chain Multiplication
The matrix-chain multiplication problem: Given a chain of < D1,D2,...,Dn > of n matrices fully parenthesize the product < D1·D2 ···Dn > in a way so that the number of scalar multiplications is minimized. Each Di has a pi−1 × pi dimension and i = 1,2,...,n.

1.    The Brute-Force: Implement a Python program to solve the matrix-chain multiplication problem by the brute force algorithm.

2.    Bottom-up Dynamic Programming : Implement a Python program to solve the matrix-chain multiplication problem using bottom-up dynamic programming approach.

3.    Dynamic Programming with Memoization: Implement a Python program to solve the matrix-chain multiplication problem using dynamic programming with memoization.

Problem 4: Longest Common Sub-sequence (LCS) Problem 
Implement a Python program to solve LCS problem using dynamic programming. Run your program to find the best sequence alignment between DNA strings. Show your results.

Longest Common Sub-sequence (LCS) problem: Given two character strings over some alphabet, find a longest string that is a sub-sequence of given two strings.

Data source: https://www.ncbi.nlm.nih.gov/genbank/



Appendix
Python program for the Brute-Force pattern-matching algorithm
 

1 # Brute force
2                        def find_brute(T, P):

3                        n, m = len(T), len(P)

4                        # every starting position 5 for i in range(n-m+1):

6                                k = 0

7                                        # conduct O(k) comparisons
8                                                          while k < m and T[i+k] == P[k]:

9                                                          k += 1

10                                                       if k == m:

11            return i 12             return -1
 

Python program for the Boyer-Moore pattern-matching algorithm
 


 
 
 

1 # Boyer-Moore
2                        def find_boyer_moore(T, P):

3                        n, m = len(T), len(P)

4                        if m == 0:

5                                 return 0
6                                         last = {}

7                                         for k in range(m):

8                                         last[P[k]] = k

9                                         i = m-1

10                                      k = m-1

11                                      while i < n: 12       # If match, decrease i,k 13 if T[i] == P[k]:

14            if k == 0: 15           return i 16             else:

17                                                                           i -= 1

18                                                                           k -= 1

19                                           # Not match, reset the positions
20                                                          else:

21                                                          j = last.get(T[i], -1)

22                                                          i += m - min(k, j+1)

23                                                          k = m-1

24                                                          return -1

Python program for the Knuth-Morris-Pratt pattern-matching algorithm
 

1 # KMP failure function
2                                                              def compute_kmp_fail(P):

3                                                              m = len(P)

4                                                              fail = [0] * m

5                                                              j = 1

6                                                              k = 0

7                                                              while j < m:

8                                                              if P[j] == P[k]:

9                                                              fail[j] = k+1

10                                                           j += 1

11                                                           k += 1

12                                                           elif k > 0: 13             k = fail[k-1] 14      else:

15                                          j += 1

16                       return fail
 

 

1 # KMP
2 def find_kmp(T, P): 3 n, m = len(T), len(P)

4                                         if m == 0:

5                                         return 0

6                                         fail = compute_kmp_fail(P)

7                          # print(fail)
8                                                             j = 0

9                                                             k = 0

10                                                          while j < n:

11                                                          if T[j] == P[k]:

12                                                          if k == m-1:

13                                                       return j-m+1
14                                                          j += 1

15                                                          k += 1

16                                                          elif k > 0: 17               k = fail[k-1] 18      else:

19                                          j += 1

20                     return -1