Data structures Assignment
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 O(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 Intersection of sorted data collections
2.1 Intersection of sorted arrays
With A and B as in exercise 1, design an O(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 reverses 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:
- Traverse the list from the beginning to the end and push each element onto a stack that is initially empty.
- Remove (pop) the elements from the stack one by one and insert them into a new linked list so that each new element is inserted as the last one.
3.2 Reversing a linked list using constant memory
The previous task uses O(n) additional memory (the stack plus extra list). Reverse a linked list in O(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 b (a:next = b), change it into b:next = a. Make sure that the pointer to the new rst element is correctly set.
4 Recursive algorithms for nding a speci ed 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: nd two elements di ering by 20
Design a recursive algorithm that checks whether the given array contains two elements whose di erence is 20.
4.2 Sorted array: nd two equal elements in linear time
Design a recursive O(n) algorithm that checks whether the given sorted array contains two equal elements. Remark. In this module we do not systematically learn how to assess runtime of recursive algorithms. One easy way to justify correctness of this particular algorithm is to design rst a non-recursive algorithm and then to transform it into recursive form.
4.3 Sorted array: nd two elements di ering by 20
Design a recursive O(n) algorithm that checks whether the given sorted array contains two elements whose di erence is 20. The remark for the previous exercise applies.