Question

A Queue is a linked list with pointers to both the head of the list as well as the tail (or the last element) of the list. Given a queue Q, Q.head gives the head of the queue and Q.tail gives the tail of the queue. Give O(1) time algorithms for the following tasks. Enqueue • Input: A queue Q of distinct integers and a queue element a not in Q. 1 • Output: Q with the element a added to the end of the list. Dequeue • Input: A queue Q of distinct integers. • Output: If the queue is not empty, the algorithm should return the first element of the queue and remove it from the queue. Otherwise, the algorithm should just return NIL.

Given an array A of real numbers, an index i is said to be a local minimum in A if A[i] is smaller than all of its neighbouring elements in A. For example, if A = (5, 7, 3, 10, 12, 2, 19, 10, 13, 4), then the indices 0, 2, 5, 7, and 9 are all the local minima in A. We want to solve the following problem: • Local minimum – Input: an array A of real numbers – Output: any one local minimum of A Give an algorithm for this problem that runs in O(log n) time.

Answer 1