Description
1. [12 pts] Given input alphabet {A, B, C, D}, construct the DFA for the string
A B C D A B D
NOTE: The spaces in the above string and aphabet are for readability.
The spaces are not part of the pattern or alphabet.
Show a trace of the KMP algorithm and your DFA on the target string
A B C A B C D A B C D A B D
NOTE: Again, the spaces are for readability.
2. [12 pts] Regular expressions (or regexs) are often extended with
convenience operations.
Assuming the alphabet is the lower case letters a,b,c,d,e; write the regular
expression for the following convenience operations:
2.1 [3pts] Wildcard (usually the ‘.’ character): will match any character in the
alphabet
2.2 [3pts] Kleene +: Like *, but the regular expression must have at least 1
instance of the root regex
Example: (ac)+ matches “ac”, “acac”
(ac)+ does not match “” (the empty string)
2.3 [3pts] bounded closure: Match a finite set of concatenations.
Example: (ab){3,5} matches “ababab” or “ababababab”
(ab){3,5} does not match “ab” or “abab” or “abababababab”
2.4 [3pts] character range:
Example: a[b-d] matches ab, ac, or ad
3. [18 pts] Given the regex over the alphabet {A,B,C,D,E,F,G}
((A | B)* | C D* | E F G )*
NOTE: The notation for the regex above uses spaces for readability.
The space character is not part of the pattern
3.1 [9 pts] Construct the NFA state machine and digraph of etranisitons for the given regex
NOTE: The above regex *may not be* fully parenthesized.
If needed, you may add enough parentheses make the regex
fully parenthesized.
3.2 [9 pts] Show the full set of state transitions when your NFA
recognizer is applied to
A B B A C E F G E F G C A A B
NOTE: The spaces in the above string are for readability.
The space character is not part of the source string.
4. [14 pts] A contiguous subsequence of a list S is a subsequence made up of
consecutive elements of S.
For instance, if S is
5, 15, −30, 10, −5, 40, 10
then
15, −30, 10
is a contiguous subsequence.
The subsequence
5, 15, 40
is not contiguous.
Give a linear-time algorithm for the following task:
Input: A list of numbers, a1,a2,…,an
Output: A contiguous subsequence of maximum sum.
NOTE: A subsequence of length 0- has sum 0.
For the preceding example sequence,the answer would be
10, −5, 40, 10
with a sum of 55.
Hint: For each j ∈ {1, 2, . . . , n}, consider contiguous subsequences ending
exactly at position j.
5. [14 pts] You are given a string of n characters s[1 . . . n], which you believe
to be a corrupted text document in which all punctuation and whitespace has
vanished. A sample input is:
itwasthebestoftimesitwastheworst
You wish to reconstruct the document using a dictionary. The dictionary is
available in the form of a Boolean function
dict(w):
for any string w, dict(w) = true if w is a valid word in the dictionary
dict(w) returns false otherwise.
5.1 [9 pts] Give a dynamic programming algorithm that determines whether
the
string s can be reconstituted as a string of valid words.
The running tine should be no worse that O(|s|2), assuming a call to the
dict function takes O(1).
5.2 [5 pts] In the event that the string is valid, make your algorithm
output the corresponding sequence of words.
6. [16 pts] Best Matrix Multiply Order:
Let
A1A2A3A4…An
be a sequence of matrices that must be multiplied together.
Matrix Multiply is associative, so you may parenthesize the multiplication in
whatever way works best.
Some reminders: An m x p matrix can be multiplied by a p x q matrix giving an
m x q matrix. The cost of multiplying the 2 matrices is m * p * q.
Example: Given the sequence
A1A2A3
where A1=10×10, A2=10×10, A3=10×1.
Choosing (A1 * A2) * A3 gives:
cost of A1×A2=10×10×10=1000
cost of(A1×A2)×A3=10×10×1
total cost = (1000) + 100 = 1100
On the other hand, choosing A1×(A2×A3)
cost of A2×A3=10×10×1=100
cost of A1×(A2×A3)=10×10×1=100
total cost = 100 + 100 = 200
So, 2nd choice is clearly best.
Your problem: Given a sequence of matrices and their dimensions, construct
an algorithm that gives the order of matrix multiplies
that yields the lowest number of operations.
7. [14 pts] Minimum Edit Distance:
You have at your disposal 3 character editing operations:
1. d: delete a char
2. i: insert a char
3. c: change 1 char into another char
You are given 2 strings s,t.
Your problem is to always find the minimum # of operations to turn string s
into string t.
Example: s = ‘cast’, t=’cats’
Option 1: c s->t [pos 3]; c t->s [pos 4] has 2 operations
Option 2: d a [pos 2]; c s a [pos 2];i s at the end. This has 3 operations.
Option 1 is clearly better option 2.
Custom Work, Just for You!
Can’t find the tutorial you need? No worries! We create custom, original work at affordable prices! We specialize in Computer Science, Software, Mechanical, and Electrical Engineering, as well as Health Sciences, Statistics, Discrete Math, Social Sciences, Law, and English.
Custom/Original Work Essays cost as low as $10 per page.
Programming Custom Work starts from $50.
Get top-quality help now!