2. naloga: Tries. Peter Puzzle has got the following string T= 1000100 over the alphabet Σ = {0,1}. He would like to search for an arbitrary substring in T. A) (i) Construct a suffix tree from T. (ii) Construct a suffix array from T. B) (i) How many substrings in T start with the string q= 00? (ii) Augment the suffix tree constructed in the subquestion (A) so that you can efficiently answer the query HowMany(T, q), which returns the number of substrings in T, that start with the substring q. (iii) What is the time complexity of a query? Justify your answer. HINT: In analyzing the time complexity you can use the parameters n= |T|, m= |q|and σ= |Σ|. C) Let us go back to the suffix tree from the subquestion (A). (i) Modify it in such a way that it will be constructed from the text T′ = 10001001= T·1, where the operator ,,·“ is concatenation. (ii) Describe an efficient algorithm which modifies a suffix tree for an arbitrary text T such that the new tree will be made for the text T·w, where wis some word over an alphabet Σ. 3. naloga: Dictionary. In Butale they like to play the following memory game in which n+2 players are involved. Each of the first nplayers in turn says a random number xi. Next player, n+ 1-st one, says a random number qand the last player answers YES, if some of xi = q, otherwise NO. Let n= 5 and let xi be 39, 12, 27, 90 and 25. If q= 9, the answer is NO, and if q= 39, then the answer is YES. A) The last player must use some data structure so that he uses as little time as possible altogether for storing xi and answering to the question q. (i) Which operations should a data structure support? (ii) Suggest a data structure that is as efficient as possible. Justify your answer. (iii) What is the time complexity of each operation and what is the time complexity of all operations together? Justify your answer. B) Would you change your data structure if you know that xi ∈[1,2,...,M]? Justify your answer. HINT: In justification, consider especially (iii) in the subquestion (A). C) In Butale they slightly change the game so that now the answer to the question qis not YES or NO anymore, but the value of the first number between xi’s that is larger than q. If such a number does not exist, the answer is−1. In our case, we now have that for q = 9 the answer is 12 and for q = 39 the answer is 90. (i) Which data structure do you suggest now? Justify your answer. (ii) What is the time complexity of each operation now and what is the time complexity of all operations together? Justify your answer. 4. naloga: Extended dictionary. In NBB (National bank of Butale) at the time of enrolment each customer receives an identification number which is a unique positive integer. The oldest customer has the smallest value, while the last one enrolled has the largest value. The bank then keeps a record of how much Butale tolars (BTT) each customer has on his account. In other words, the NBB maintains a dictionary of elements (id, v), which means that the customer id has v BTT on his account. Currently, there are ncustomers at the NBB. Peter Puzzle is the author of the software and he has implemented a dictionary using AVL trees. The director believes that older customers have more funds on their accounts and so he wants Peter to add the function Sum(id), which returns the sum of funds on accounts of customers whose identification number is smaller or equal id. A) Let n = 7 and suppose that we have the following customers: (74,7344), (22,4631),(8,6888),(54,8181),(84,9356),(31,8500),(97,6169),where the first number represents an identification number of a customer and the second one a fund on his account. (i) Insert elements in turn into an AVL tree and draw a final tree with all elements inserted. B) (i) What does the call of the function Sum(74) return? (ii) Describe how did you find the answer to this question. (iii) Describe how would you augment an AVL tree to efficiently answer the query Sum(id). (iv) Now, augment nodes in the tree you got in the subquestion (A). HINT: The better your solution, the more points you will earn. C) (i) What is the time complexity of your solution? Justify your answer. (ii) From the tree you got in the subquestion (A) and you augmented it in the subquestion (C), delete the element with id = 22.
2. naloga: Tries. Peter Puzzle has got the following string T= 1000100 over the
alphabet Σ = {0,1}. He would like to search for an arbitrary substring in T.
A) (i) Construct a suffix tree from T. (ii) Construct a suffix array from T.
B) (i) How many substrings in T start with the string q= 00? (ii) Augment
the suffix tree constructed in the subquestion (A) so that you can efficiently
answer the query HowMany(T, q), which returns the number of substrings
in T, that start with the substring q. (iii) What is the time complexity of a
query? Justify your answer.
HINT: In analyzing the time complexity you can use the parameters n= |T|,
m= |q|and σ= |Σ|.
C) Let us go back to the suffix tree from the subquestion (A). (i) Modify it in
such a way that it will be constructed from the text T′
= 10001001= T·1,
where the operator ,,·“ is concatenation. (ii) Describe an efficient algorithm
which modifies a suffix tree for an arbitrary text T such that the new tree will
be made for the text T·w, where wis some word over an alphabet Σ.
3. naloga: Dictionary. In Butale they like to play the following memory game in
which n+2 players are involved. Each of the first nplayers in turn says a random
number xi. Next player, n+ 1-st one, says a random number qand the last player
answers YES, if some of xi = q, otherwise NO. Let n= 5 and let xi be 39, 12, 27,
90 and 25. If q= 9, the answer is NO, and if q= 39, then the answer is YES.
A) The last player must use some data structure so that he uses as little time as
possible altogether for storing xi and answering to the question q. (i) Which
operations should a data structure support? (ii) Suggest a data structure that is
as efficient as possible. Justify your answer. (iii) What is the time complexity
of each operation and what is the time complexity of all operations together?
Justify your answer.
B) Would you change your data structure if you know that xi ∈[1,2,...,M]?
Justify your answer.
HINT: In justification, consider especially (iii) in the subquestion (A).
C) In Butale they slightly change the game so that now the answer to the question
qis not YES or NO anymore, but the value of the first number between xi’s that
is larger than q. If such a number does not exist, the answer is−1. In our case,
we now have that for q = 9 the answer is 12 and for q = 39 the answer is 90.
(i) Which data structure do you suggest now? Justify your answer. (ii) What
is the time complexity of each operation now and what is the time complexity
of all operations together? Justify your answer.
4. naloga: Extended dictionary. In NBB (National bank of Butale) at the time
of enrolment each customer receives an identification number which is a unique
positive integer. The oldest customer has the smallest value, while the last one
enrolled has the largest value. The bank then keeps a record of how much Butale
tolars (BTT) each customer has on his account. In other words, the NBB maintains
a dictionary of elements (id, v), which means that the customer id has v BTT
on his account. Currently, there are ncustomers at the NBB. Peter Puzzle is the
author of the software and he has implemented a dictionary using AVL trees. The
director believes that older customers have more funds on their accounts and so
he wants Peter to add the function Sum(id), which returns the sum of funds on
accounts of customers whose identification number is smaller or equal id.
A) Let n = 7 and suppose that we have the following customers: (74,7344),
(22,4631),(8,6888),(54,8181),(84,9356),(31,8500),(97,6169),where the
first number represents an identification number of a customer and the second
one a fund on his account. (i) Insert elements in turn into an AVL tree and
draw a final tree with all elements inserted.
B) (i) What does the call of the function Sum(74) return? (ii) Describe how did
you find the answer to this question. (iii) Describe how would you augment an
AVL tree to efficiently answer the query Sum(id). (iv) Now, augment nodes
in the tree you got in the subquestion (A).
HINT: The better your solution, the more points you will earn.
C) (i) What is the time complexity of your solution? Justify your answer. (ii)
From the tree you got in the subquestion (A) and you augmented it in the
subquestion (C), delete the element with id = 22.
Step by step
Solved in 2 steps
