Data Structure And Algorithm 2 - open to bidding

Data Structure and Algorithm 1. Union of sorted data collections 1.1 Union of sorted arrays Let A and B be sorted arrays with all elements of A distinct and all elements of B distinct (though elements can occur in both A and B). Design an 0(n) algorithm that produces a sorted array C containing all elements of A and B without repetitions. For instance, if A = [1,2,5,7] and B = [2,5,10], C = [1,2,5,7,10]. 1.2 Union of sorted linked lists Solve the same exercise for the case where A and B are linked lists. 2.1 Intersection of sorted arrays With A and B as in exercise 1, design an 0(n) algorithm that produces a sorted array containing those elements that occur in both A and B. In the example as above C = [2,5] 2.2 Intersection of linked lists Solve the same exercise for the case where A and B are linked lists. 3. Reversing a linked list In this exercise you are asked to design an algorithm that reverse a linked list. This algorithm takes as input a linked list and returns a linked list where the elements are in the reverse order. For example, if the linked list given as input is (10,9,23,47,15) then the resulting linked list should be ( 15,47,23,9,10). 3.1 Reversing a linked list using a stack. Reverse a linked list using the following approach: a. Traverse the list from the beginning to the end and push each element onto a stack that is initially empty. b. Remove (pop) the elements from the stack one by one and insert them into a new linked list so that each new elements is inserted as the last one. 3.2 Reversing a linked list using constant memory. The previous task uses 0(n) additional memory (the stack plus extra list). Reverse a linked list in 0(n) time using only a constant amount of additional memory. That is, you are not allowed any additional data collections (e.g. arrays, lists, stacks, queues) and can only have several single variables. Hint: consider moving along the list and reversing the pointers. That is, if the current pointer is from a to be ([login to view URL] = b), change it into [login to view URL] = a. Make sure that the pointer to the new first element is correctly set. 4. Recursive algorithm for finding a specified pair of elements in an array. In this task, you are asked to design algorithms that use recursion instead of loops. That is, you are not allowed to use for or while loops and have to use the recursion instead. 4.1 Unsorted array: find two elements differing by 20. Design a recursive algorithm that checks whether the given array contains two elements whose difference is 20. 4.2 Sorted array: find two equal elements in linear time. Design a recursive 0(n) algorithm that checks whether the given sorted array contains two equal elements. Remark; one easy way to justify correctness of this particular algorithm is to design first a non-recursive algorithm and then to transform it into recursive form. 4.3 Sorted array: find two elements differing by 20. Design a recursive 0(n) algorithm that checks whether the given sorted array contains two elements whose difference is 20. The remark for the previous exercise applies.