2 UP FAMNIT, DSA 2020/21 - First midterm 201125 UP FAMNIT, DSA 2020/21 - First midterm 201125 3 1. task: Introduction and basics. Peter Zmeda is really lucky. He often finds parts of code and he then asks himself if he could use them anywhere. This time he has found the following code: int FooBar (A) { n= len(A); B= newArray (n) for j 0 to n-1 { B[j]= 0 for i= j to 0 step -1 { if A[i] < A[j] { B[j]= B[j] + 1 } B) From Patricia trie from the first question build an LC trie (level compressed trie). (i.) Use a = 3. Draw the final tree. (ii.) Suppose that we have n keys in a trie. What should be their values so that there will be no vector in the trie after compression by levels for a = 3? In other words, for each compression by levels the density would be too low. C) Take the key x7. (i.) Construct a suffix tree from it. (ii.) Construct a suffix array from x7. } } return B } QUESTIONS: == A) (i) Let A = [56, 47, 66, 71, 17, 19, 92]. What does the function FooBar (A) return (compute)? (ii.) What is the time complexity of the function FooBar? Justify your answer. (iii.) Is there any difference in your result if we measure comparisons or memory probes? Comment the result. HINT: You will earn more points, if you compute the precise number of com- parisons and not only give a family of functions O(). B) (i.) What does the vector B returned (computed) by the function FooBar contain? Justify your answer. (ii.) What is the loop invariant for the inner for loop based on which you can show what the function actually returns? (iii.) Show that it remains invariant throughout the execution of the function. C) Is there a better time algorithm that computes the vector B? If yes, write it down and determine its time complexity; if not show that it does not exist. 2. task: Tries. We have the following strings/keys over the alphabet Σ = {0, 1}: x1111110 x20001010110 X3 = 0110000 ^4= 011110 x5=101 x601011 x710111111 QUESTIONS: A) Initially, we have an empty Patricia trie. (i.) Insert the keys in turn from x1, x2 to x7. Draw the corresponding tree after each insertion. (ii.) Would the final tree look any different if you would first insert x7, than x6 and so on until x₁? Justify your answer. 3. task: Dictionary. QUESTIONS: A) Draw the smallest AVL tree of height 5 - that is, an AVL tree of height 5 which has the smallest number of elements. The tree with only the root is of height 1. B) Insert into an AVL tree in Figure 1 an element with key 5. Draw the corre- 2 4 7 12 10 14 Slika 1: An example of an AVL tree. sponding tree after insertion and justify the steps. C) If we insert the keys in ascending order into an AVL tree, the height of the tree monotonically increases. Prove whether the statement is correct or not. 4 Page 4 of 4 UP FAMNIT, DSA 2020/21 - First midterm 201125 4. task: Prefix sums. Given a vector of elements a1, a2, ..., an, prefix sums are defined as S₁ = =Σ1 a, where 1 ≤i≤n. QUESTIONS: A) (i.) Fill in the bottom row of the table with prefix sums: A 60 -84 85 55 91 15 -30 S (ii.) Write down an algorithm that computes a vector of prefix sums S. (iii.) What is its time complexity? Justify your answer. B) Prefix sums can be represented as an abstract data structure that has the follo- wing operations: Create(n) : creates a data structure for n elements and the values of all elements are 0 (exm. a from the description). Set (i, v) sets the value of the i-th element to v. Sum (i) returns the sum of the first i numbers (exm. s; from the description). (i.) Suggest an implementation of the data structure and all three operations. (ii.) What is the time complexity of your operations? Justify your answer. C) Extend the abstract data structure with the following operations: Insert (i, v) : moves in the vector of elements all elements at positions j > i one position forward and inserts a new element with the value v at position i. Delete (i) deletes an element at position i and moves all the next elements on position back: aj+1 → a¡ for j > i. (i.) What implementation of the data structure do you propose this time? Describe all five operations in the new data structure. (ii.) What is the time complexity of your operations this time? Justify your answer.

2 UP FAMNIT, DSA 2020/21 - First midterm 201125 UP FAMNIT, DSA 2020/21 - First midterm 201125 3 1. task: Introduction and basics. Peter Zmeda is really lucky. He often finds parts of code and he then asks himself if he could use them anywhere. This time he has found the following code: int FooBar (A) { n= len(A); B= newArray (n) for j 0 to n-1 { B[j]= 0 for i= j to 0 step -1 { if A[i] < A[j] { B[j]= B[j] + 1 } B) From Patricia trie from the first question build an LC trie (level compressed trie). (i.) Use a = 3. Draw the final tree. (ii.) Suppose that we have n keys in a trie. What should be their values so that there will be no vector in the trie after compression by levels for a = 3? In other words, for each compression by levels the density would be too low. C) Take the key x7. (i.) Construct a suffix tree from it. (ii.) Construct a suffix array from x7. } } return B } QUESTIONS: == A) (i) Let A = [56, 47, 66, 71, 17, 19, 92]. What does the function FooBar (A) return (compute)? (ii.) What is the time complexity of the function FooBar? Justify your answer. (iii.) Is there any difference in your result if we measure comparisons or memory probes? Comment the result. HINT: You will earn more points, if you compute the precise number of com- parisons and not only give a family of functions O(). B) (i.) What does the vector B returned (computed) by the function FooBar contain? Justify your answer. (ii.) What is the loop invariant for the inner for loop based on which you can show what the function actually returns? (iii.) Show that it remains invariant throughout the execution of the function. C) Is there a better time algorithm that computes the vector B? If yes, write it down and determine its time complexity; if not show that it does not exist. 2. task: Tries. We have the following strings/keys over the alphabet Σ = {0, 1}: x1111110 x20001010110 X3 = 0110000 ^4= 011110 x5=101 x601011 x710111111 QUESTIONS: A) Initially, we have an empty Patricia trie. (i.) Insert the keys in turn from x1, x2 to x7. Draw the corresponding tree after each insertion. (ii.) Would the final tree look any different if you would first insert x7, than x6 and so on until x₁? Justify your answer. 3. task: Dictionary. QUESTIONS: A) Draw the smallest AVL tree of height 5 - that is, an AVL tree of height 5 which has the smallest number of elements. The tree with only the root is of height 1. B) Insert into an AVL tree in Figure 1 an element with key 5. Draw the corre- 2 4 7 12 10 14 Slika 1: An example of an AVL tree. sponding tree after insertion and justify the steps. C) If we insert the keys in ascending order into an AVL tree, the height of the tree monotonically increases. Prove whether the statement is correct or not. 4 Page 4 of 4 UP FAMNIT, DSA 2020/21 - First midterm 201125 4. task: Prefix sums. Given a vector of elements a1, a2, ..., an, prefix sums are defined as S₁ = =Σ1 a, where 1 ≤i≤n. QUESTIONS: A) (i.) Fill in the bottom row of the table with prefix sums: A 60 -84 85 55 91 15 -30 S (ii.) Write down an algorithm that computes a vector of prefix sums S. (iii.) What is its time complexity? Justify your answer. B) Prefix sums can be represented as an abstract data structure that has the follo- wing operations: Create(n) : creates a data structure for n elements and the values of all elements are 0 (exm. a from the description). Set (i, v) sets the value of the i-th element to v. Sum (i) returns the sum of the first i numbers (exm. s; from the description). (i.) Suggest an implementation of the data structure and all three operations. (ii.) What is the time complexity of your operations? Justify your answer. C) Extend the abstract data structure with the following operations: Insert (i, v) : moves in the vector of elements all elements at positions j > i one position forward and inserts a new element with the value v at position i. Delete (i) deletes an element at position i and moves all the next elements on position back: aj+1 → a¡ for j > i. (i.) What implementation of the data structure do you propose this time? Describe all five operations in the new data structure. (ii.) What is the time complexity of your operations this time? Justify your answer.