Use Java

1. Implement a queue on the singly linked list of Item #1, with the following operations: enqueue, dequeue, front, size, isEmpty. Note: both operations, enqueue and dequeue, must run in O(1).

2. Practical application 2:

The merge problem. Given two sorted lists of integers, A and B, the aim is to merge A and B, producing a sorted list S.

(a) Write an algorithm that stores A and B in two queues (one in each queue), merges A and B, and outputs a sorted list S in O(n) worst-case time. Note: your algorithm must use queues for A, B and S.

(b) Implement your algorithm in your favorite programming language.

(c) Explain how your algorithm runs in O(n), where n is the length of S.

(d) [2 bonus marks*] Run your algorithm on randomly generated sorted lists A and B of different sizes: 100, 200, 300, , 2000 and record the CPU time taken by the algorithm. Create a table (or a plot) and explain how your algorithm runs in O(n) by inspecting your results. Run the Merge algorithm with the following inputs:

(i) A = 1,3,5,7,9 B = 2,3,6,8,10

(ii) A = 1,2,3,4,5 B = 6,7,8,9,10

(iii) A = 2,4,8,16,32 B = 1,3,5,7,9

(iv) A = 10,11,12,13 B = 1,2,3,4