Posted: April 13th, 2023

String Data Structures, Advance Data Structures essay

Problem 1 (10 points)
Consider what the lecture notes refer to as a Patricia tree, is more formally known as a
compact prefix tree or radix trie
(Links to an external site.)
. Give a drawing of such a structure for the following list of words. Please follow the
convention given in the lecture notes in which children of a node are given in
lexicographic order.
marie
mary
monday
saint
salt
saturday
saturn
sault
Problem 2 (10 points)
The edges of suffix trees are often portrayed with associated substrings, as with this
example from the lecture notes.
Of course, in order for a suffix tree to use O(n) space, those edges cannot explicitly
store the associated substring, as each edge must use O(1) space. So a typical
representation would be to have each edge store the number of characters for that
substring, and an index at which that substring begins in the full string (though that
index may not be unique, given repeats of substrings). For example, the following
diagram shows the same suffix tree but with each edge storing an integer pair (length,
index). Notice the ‘se’ label on the rightmost edge from the root designates a substring
with length 2 beginning at index 6 of the original string (though ‘se’ also can be found
starting at index 3 of the original).
Using this new convention, draw the suffix tree for the following input string
CAAGTCAGT$
0123456789
Problem 3 (10 points)
Consider the following paragraph, which is taken from an English translation of the
excellent short story “Before the Law” by Franz Kafka:
Before the law sits a gatekeeper. To this gatekeeper comes a man from the country who
asks to gain entry into the law. But the gatekeeper says that he cannot grant him entry
at the moment. The man thinks about it and then asks if he will be allowed to come in
later on. “It is possible,” says the gatekeeper, “but not now.”
Actually building a suffix tree for this text, by hand, would be quite challenging. But even
without doing so, you can still infer much about what it would look like.
1. Without building a suffix tree or suffix array for the above text, determine
whether the suffix tree for this passage contains a node labeled with the
string ” moment” . (Here, the label on a node is the string read by tracing out
a path from the root of the tree all the way down to that node.)
2. Repeat the above exercise for the string ” man” .
3. Repeat the above exercise for the string ” gatekeeper” .
Briefly justify your answers.
Problem 4 (10 points)
Assume that you have a Suffix Tree already constructed for a string S with length n.
Explain how you can use a single traversal of the tree to compute in O(n) time the
longest substring that occurs k or more times in the string.
Problem 5 (10 points)
The following is a portrayal of the suffix array and LDP array for the nonsense$ string.
The leftmost column in yellow are the LDP values for neighboring entries, the second
numeric column is the starting index of each substring in lexicographic order. The third
column shows what the actual substring is, but that column would actually be implicit in
the suffix array, determined based on the starting index for the original string.
8 $
0
7 e$
1
4 ense$
0
0 nonsense$
1
5 nse$
3
2 nsense$
0
1 onsense$
0
6 se$
2
3 sense$
Give a similar such portrayal of the Suffix Array and LDP Array for the string
anexampleexam$
-Research paper writing service

Check Price Discount

Study Notes, Research Topics & Assignment Examples: Discussion Healthy Eating Approach Essay »MKT00720 – Marketing Assignment 2: Report