4 UP FAMNIT, DSA 2021/22 - First midterm 211203 subtrees A, B, C and D are black as well as the black heights of the subtrees are the same. 1 QUESTIONS: A) How, if necessary, should the shape of the tree be transformed in Figure 1? Draw and justify your answer. B) Write down the pseudocode that performs the mentioned transformation. C) B tree. Our friend Peter Puzzle has reviewed the code for deleting from a B tree and it seemed to him that it could be more efficient if he would allow in each node instead of at least 2 elements 3 elements. Comment his idea. Focus on the complexity of the code, the size of occupied memory and operational efficiency. 4. task: Even and odd. We extend common operations on a dictionary D with the operations Odd (D, a, b) and Even (D, a, b), which return the number of odd or even elements in the dictionary D that are greater than or equal to a and less than or equal to b. For example, if D = {665, 963,330, 851, 334, 424, 696, 620, 706, 957}, then Odd (D, 505, 864) returns 2 and Even (D, 505, 864) returns 3. On the other hand both Odd (D, 864, 505) and Even (D, 864, 505) re- turn 0. QUESTIONS: A) (i.) Implement such an extended dictionary D using ordinary linked list and ordered linked list. (ii.) What is the time complexity of both operations in each of implementations? Justify your answer. HINT: Describe the data structure and describe how it is maintained with operations. Write down a pseudocode for both new operations. B) (i.) Implement such an extended dictionary D using skip list. (ii.) What is the time complexity of both operations in this implementation? Justify your answer. HINT: See the hint in the first question. Otherwise, the expected time com- plexity should be O(logn) in principle. C) Describe an example of a situation, if any, when it makes more sense to use one of the implementations with a linked list rather than with a skip list. Justify your answer. 1The black height of a subtree is the number of black nodes from the root to any leave. 2 UP FAMNIT, DSA 2021/22 - First midterm 211203 Page 2 of 4 UP FAMNIT, DSA 2021/22 - First midterm 211203 3 1. task: Introduction and basics. And again, Peter Puzzle has found a piece of paper with the following code: int FooBar (A, i) { n= len(A); if (i == n-1) return A; for (j= (i + 1); j < n; j++) { } } if (A[i] < A[j]) { temp= A[i]; A[i]= A[j]; A[j]= temp; } return FooBar (A, i+1) QUESTIONS: A) (i.) What is the loop invariant for the for loop based on which you can show what the function actually returns? (ii.) Show that it remains invariant throughout the execution of the function. B) (i.) What does the array A returned by the function FooBar (A, i) contain? Justify your answer. (ii.) What does the array A returned by the function FooBar (A, 0) contain? Justify your answer. HINT: Use induction. C) (i.) What is the time complexity of the function FooBar if we count the number of comparisons over the elements of the array A? Justify your answer. HINT: You will earn more points, if you compute the precise number of com- parisons and not only give a family of functions O(). 2. task: Tries. We have the following strings/keys over the alphabet Σ = {0, 1}: x1010101 x501001 X2111111 x6 = 110111 X3 101101 x710111111 ^4= 0111111 B) (i.) Write down the pseudocode of the query Find (T, xq) which answers whether xq is in the Patricia trie T. (ii.) Show how it works for queries x5, x and x7. (iii.) Suppose that there are n elements in a trie and let a query xq have size |xq = m of letters. What is the time complexity of the query? Justify your answer. C) Leaves of a Patricia trie can be stored in an array which is in our case A = [x1,x4, x3, x2]. The same holds in general, when we have n elements in a Patricia trie and we store leaves in an array A = [x1, x2, ..., xi, Xi+1, ..., : ‚xn], where xi < xi+1 for i = 1, ..., n − 1 in |x¿| = m¿. In other words, the array A is lexicographically sorted and we can use bisection for searching. (i.) Write down the pseudocode of implementation Find (A, xq), which finds in an array A an element x; whose prefix is xq. (ii.) What is the time complexity of your algorithm? Justify your answer. HINT: The more efficient your solution the more points you will earn. For really efficient solution augment the array A with a support data structure. 3. task: Dictionary. In this task, we consider red-black trees. In Figure 1 there is a D Ꭰ QUESTIONS: A) Initially, we have an empty Patricia trie T. (i.) Insert in turn the keys x1, x2, x3 and x4. Draw the corresponding tree after each insertion and justify the change. (ii.) Compress the final trie by level with at least a = of array cells occupied. Justify your steps and the final result - draw the final tree. HINT: Also write down what is stored in leaves of Patricia trie and what in internal nodes. B Slika 1: A red-black tree after inserting into the subtree B. the configuration of RB tree after we have inserted an element into the subtree B and where nodes a and b are red while node c is black. Furthermore the roots of