Exercise 3.1. Why is it not possible to use a dummy node in an SLList to avoid all the special cases that occur in the operations push(x),pop(), add(x), and remove ()? Exercise 3.2. Design and implement an SLList method, second last(), that returns the second-last element of an SLList. Do this without using the member variable, n, that keeps track of the size of the list. 78 Discussion and Exercises 3.4 Exercise 3.3. Implement the List operations get(i),set(i,x), add (i,x) and remove( i ) on an SLList. Each of these operations should run in O(1+i) time. Exercise 3.4. Design and implement an SLList method, reverse() that reverses the order of elements in an SLList. This method should run in O(n) time, should not use recursion, should not use any secondary data structures, and should not create any new nodes. Exercise 3.5. Design and implement SLList and DLList methods called check_size(). These methods walk through the list and count the number of nodes to see if this matches the value, n, stored in the list. These methods return nothing, but throw an exception if the size they compute does not match the value of n. creates a node, u, and adds it in a DLList just before the node w. Do not refer to this chapter. Even if your code does not exactly match the code given in this book it may still be correct. Test it and see if it works. The next few exercises involve performing manipulations on DLLists. You should complete them without allocating any new nodes or temporary arrays. They can all be done only by changing the prev and next values of existing nodes. Exercise 3.7. Write a DLList method is palindrome() that returns true if the list is a palindrome, i.e., the element at position i is equal to the element at position ni1 for all i{0,,n1}. Your code should run in O(n) time. Exercise 3.8. Implement a method rotate(r) that "rotates" a DLList so that list item i becomes list item (i+r)modn. This method should run in O(1+min{r,nr}) time and should not modify any nodes in the list. Exercise 3.9. Write a method, truncate( i, that truncates a DLList at position i. After executing this method, the size of the list will be i and it should contain only the elements at indices 0,,i1. The return value is another DLList that contains the elements at indices i,,n1. This method should run in O(min{i,ni}) time. Exercise 3.10. Write a DLList method, absorb (l2), that takes as an argument a DLList, l2, empties it and appends its contents, in order, to the receiver. For example, if l1 contains a,b,c and l2 contains d,e,f, then after calling l1.absorb (l2),l1 will contain a,b,c,d,e,f and l2 will be empty. Exercise 3.11. Write a method deal() that removes all the elements with odd-numbered indices from a DLList and return a DLList containing these elements. For example, if l1, contains the elements a,b,c,d,e,f, then after calling l1, deal(), l1 should contain a,c,e and a list containing b,d,f should be returned. Exercise 3.12. Write a method, reverise(), that reverses the order of elements in a DLList. Exercise 3.13. This exercise walks you through an implementation of the merge-sort algorithm for sorting a DLList, as discussed in Section 11.1.1. 1. Write a DLList method called take_first (l2). This method takes the first node from l2 and appends it to the the receiving list. This is equivalent to add (size(), l2.remove(0)), except that it should not create a new node. 2. Write a DLList static method, merge (l1,l2), that takes two sorted lists l1 and l2, merges them, and returns a new sorted list containing the result. This causes l1 and l2 to be emptied in the proces. For example, if l1 contains a,c,d and l2 contains b,e,f, then this method returns a new list containing a,b,c,d,e,f. 3. Write a DLList method sort() that sorts the elements contained in the list using the merge sort algorithm. This recursive algorithm works in the following way: (a) If the list contains 0 or 1 elements then there is nothing to do. Otherwise, (b) Using the truncate(size()/2) method, split the list into two lists of approximately equal length, l1 and l2; 3. Write a DLList method sort() that sorts the elements contained in the list using the merge sort algorithm. This recursive algorithm works in the following way: (a) If the list contains 0 or 1 elements then there is nothing to do. Otherwise, (b) Using the truncate(size()/2) method, split the list into two lists of approximately equal length, l1 and l2; (c) Recursively sort l1; (d) Recursively sort l2; and, finally, 80 Discussion and Exercises 3.4 (e) Merge l1 and l2 into a single sorted list. The next few exercises are more advanced and require a clear understanding of what happens to the minimum value stored in a Stack or Queue as items are added and removed. Exercise 3.14. Design and implement a MinStack data structure that can store comparable elements and supports the stack operations push (x), pop(), and size(), as well as the min() operation, which returns the minimum value currently stored in the data structure. All operations should run in constant time. Exercise 3.15. Design and implement a MinQueue data structure that Exercise 3.15. Design and implement a MinQueue data structure that can store comparable elements and supports the queue operations add (x), remove(), and size(), as well as the min() operation, which returns the minimum value currently stored in the data structure. All operations should run in constant amortized time. Exercise 3.16. Design and implement a MinDeque data structure that can store comparable elements and supports all the deque operations add_first (x), add last (x) remove_first () , remove_last () and size(), and the min() operation, which returns the minimum value currently stored in the data structure. All operations shojld run in constant amortized time. The next exercises are designed to test the reader's understanding of the implementation and analysis of the space-efficient SEList: Exercise 3.17. Prove that, if an SEList is used like a Stack (so that the only modifications to the SEList are done using push (x)add(size(),x) and pop()remove(size()1) ), then these operations run in constant amortized time, independent of the value of b. Exercise 3.18. Design and implement of a version of an SEList that supports all the Deque operations in constant amortized time per operation, independent of the value of b. Exercise 3.19. Explain how to use the bitwise exclusive-or operator, , to swap the values of two int variables without using a third variable