Algorithms and Data Structures Assignment Solution - Desklib

This document provides a solution to an Algorithms and Data Structures assignment. The solution focuses on the brute force algorithm and its application to string matching, specifically using a DNA sequence example. The assignment involves comparing text and pattern alphabets, demonstrating the process step-by-step, and calculating the number of comparisons. The solution also includes an analysis of the time complexity, differentiating between best-case and worst-case scenarios, and explaining how the length of the string impacts the execution time. This assignment is a great resource for students studying algorithms and data structures, offering a practical example of a brute force approach and its performance characteristics.

ALGORITHMS AND DATA
STRUCTURES

The Master Theorem can be applied to the recurrence relation
where a ≥ 1 and b > 1 are called as constants and
f(n) is called as an asymptotically positive function
There are 3 cases in this theorem
2

3

Answer
Brute force algorithm follows an approach which is straightforward. This approach is used to find a
solution depending on the problem and derived concepts. The brute force algorithm is used for
finding the matching strings. In our problem, the nuclease sequence of adenine, cytosine, guanine
and thymine is considered and TACAAGCGA sequence is considered.
Text alphabet for the given DNA sequence : TACAAGCGA
Pattern alphabet for the given DNA sequence: GCGA
Pseudo-code
do if (text alphabet == pattern alphabet)
compare next alphabet of the pattern to the next text alphabets
else move the pattern down to the text one by one
while(full pattern found or end of the text alphabets)
First Attempt
T A C A A G C G A
G C G A
Text alphabet T and pattern alphabet G is compared. It does not match. Go to next attempt.
Second Attempt
T A C A A G C G A
G C G A
Text alphabet A and pattern alphabet G is compared. Does not match, so go to next attempt.
Third Attempt
T A C A A G C G A
4

G C G A
Text alphabet is C and pattern alphabet is G. Both do not match. So go to next step.
Fourth Attempt
T A C A A G C G A
G C G A
Text alphabet A and Pattern Alphabet G does not match. Go to fifth attempt.
Fifth Attempt
T A C A A G C G A
G C G A
Text Alphabet A and pattern alphabet G are not same. So next attempt is required.
Sixth Attempt
T A C A A G C G A
G C G A
Pattern found. Both alphabets are same. GCGA pattern is found. So stop scanning the String S.
Number of Comparisons made is 6. So M=6.
Complexity
The best case complexity is O(N)
The worst case complexity is O(MN)
M - Length of string
N – Number of comparisons made.
The linear complexity of the string is said to get a linear time for string match. The time varies
according to the length of the string. As the length of the string is long, the time taken is also
increased.
5

3)
a)
b)
6

4)
7