E2 Cancel culture (6 points) Consider an abstract data type for storing a history of actions (e.g., text editor or browser navigation) with undo-redo functionality. Undo cancels an action but keeps it in memory so that the state can be restored by redo. The interface includes the following operations * insertion: add(x) appends x (# null) at the end of the non-canceled action sequence, and resets the redoables to null (no return value) * canceling: undo() returns the most recent uncanceled action, and steps back in the history (returns null if no more actions to be canceled) * restoring: redo() returns the most recently canceled action and steps for- ward in the history (returns null if no more redoable actions) Table 3: Example: undo/redo returns B returns A returns A add(A) add(B) undo () undo () redo(). add(C) redo(). undo () undo() undo() a. Two stacks (2 points) > Give an implementation based on two (LIFO) stacks. Use only the stack interface's operations. returns null returns C returns A returns null b. One structure (4 points) Give a complete implementation of the op- erations using a structure of your choice: one table, or one linked list. Justify (briefly) your choice. E3 Conquerors (6 points) Let T be a binary tree where every internal node x has an integer key stored as x.key, and the children x.left, and x.right. In this exercise, an inter- nal node x is called a conqueror if and only if x.key > y.key for all internal nodes y in the subtree rooted at x. An internal node with two external chil- dren is a conqueror by default. a. Conquerors and max-heap (1 points). Prove 10 that the tree is in max- heap order if and only if every internal node is a conqueror. 10. Hint: use he transitivity of >. You can do a formal proof by induction on the tree. b. Max-heap order (2 points). Give an algorithm that verifies if a tree (specified by its root) is in the max-heap order by .key. Give an algorithm 11 that counts the c. Conqueror counting (3 points). conqueror nodes in a binary tree. 11. Hint: do a tree traversal by recursion, returning a pair of values, including the conqueror count. E4 Dynamic array (7 points) Table 4: Example for ADT of indexed sequence In order to store a sequence (x0, X1,..., Xn-1), we need an abstract data type with the operations * add(x) appends an element at the end of the sequence ; * get(i) returns the i-th member, where index i = 0 is the first * size() returns the number of elements in the sequence The implementation could be based on a single array, with the technique of resizing (by doubling), but then add takes linear time when all elements need to be copied into the newly allocated array. But suppose that we keep the old array, and use the new array for the new elements only: no more copying! We use thus a structure based on the arrays To, T1, T2, ..., where each array Ta is of capacity 22. So, To holds one member (x0) of the sequence, T1 contains the two following ones (x1, x2), T2 contains the four elements after (X3, X4, X5,X6), and so on. add(A) add(B) get(0) get(1) size() returns A returns B returns 2 a. Capacity (1 point) We need to allocate a new array Ta for add only when the arrays To,...,Ta-1 are used fully. Give the total capacity of the arrays To, ...,Ta-1 in a closed-form expression. b. Implementation (4 points) Give a complete implementation by an array of arrays (Object[][] in Java) to store To, T1,.... c. Analysis (2 points) Analyze the running time for the operations: show that add takes at most logarithmic time, and that an arbitrary sequence of m operations takes O(m). (That is, constant amortized time.) E2 Cancel culture (6 points) Consider an abstract data type for storing a history of actions (e.g., text editor or browser navigation) with undo-redo functionality. Undo cancels an action but keeps it in memory so that the state can be restored by redo. The interface includes the following operations * insertion: add(x) appends x (# null) at the end of the non-canceled action sequence, and resets the redoables to null (no return value) * canceling: undo() returns the most recent uncanceled action, and steps back in the history (returns null if no more actions to be canceled) * restoring: redo() returns the most recently canceled action and steps for- ward in the history (returns null if no more redoable actions) Table 3: Example: undo/redo returns B returns A returns A add(A) add(B) undo () undo () redo(). add(C) redo(). undo () undo() undo() a. Two stacks (2 points) > Give an implementation based on two (LIFO) stacks. Use only the stack interface's operations. returns null returns C returns A returns null b. One structure (4 points) Give a complete implementation of the op- erations using a structure of your choice: one table, or one linked list. Justify (briefly) your choice. E3 Conquerors (6 points) Let T be a binary tree where every internal node x has an integer key stored as x.key, and the children x.left, and x.right. In this exercise, an inter- nal node x is called a conqueror if and only if x.key > y.key for all internal nodes y in the subtree rooted at x. An internal node with two external chil- dren is a conqueror by default. a. Conquerors and max-heap (1 points). Prove 10 that the tree is in max- heap order if and only if every internal node is a conqueror. 10. Hint: use he transitivity of >. You can do a formal proof by induction on the tree. b. Max-heap order (2 points). Give an algorithm that verifies if a tree (specified by its root) is in the max-heap order by .key. Give an algorithm 11 that counts the c. Conqueror counting (3 points). conqueror nodes in a binary tree. 11. Hint: do a tree traversal by recursion, returning a pair of values, including the conqueror count. E4 Dynamic array (7 points) Table 4: Example for ADT of indexed sequence In order to store a sequence (x0, X1,..., Xn-1), we need an abstract data type with the operations * add(x) appends an element at the end of the sequence ; * get(i) returns the i-th member, where index i = 0 is the first * size() returns the number of elements in the sequence The implementation could be based on a single array, with the technique of resizing (by doubling), but then add takes linear time when all elements need to be copied into the newly allocated array. But suppose that we keep the old array, and use the new array for the new elements only: no more copying! We use thus a structure based on the arrays To, T1, T2, ..., where each array Ta is of capacity 22. So, To holds one member (x0) of the sequence, T1 contains the two following ones (x1, x2), T2 contains the four elements after (X3, X4, X5,X6), and so on. add(A) add(B) get(0) get(1) size() returns A returns B returns 2 a. Capacity (1 point) We need to allocate a new array Ta for add only when the arrays To,...,Ta-1 are used fully. Give the total capacity of the arrays To, ...,Ta-1 in a closed-form expression. b. Implementation (4 points) Give a complete implementation by an array of arrays (Object[][] in Java) to store To, T1,.... c. Analysis (2 points) Analyze the running time for the operations: show that add takes at most logarithmic time, and that an arbitrary sequence of m operations takes O(m). (That is, constant amortized time.)