Please ANSWER CORRECTLY: $150

1.Using the Java programming language, implement the deque ADT with a doubly linked list.

2.Implement an adapter class in Java programming language to support the stack interface using the methods from the array list ADT.

3.Use pseudo-code to describe an algorithm for computing the number of descedents of each node of a binary tree. The algorithm should be based on the Euler tour traversal.

4.Use pseudo-code to describe a nonrecursive method for performing an inorder traversal of a binary tree in linear time.

5.Illustrate the execution of the heap-sort algorithm on the following input sequence: (2, 5, 16, 4, 10, 23, 39, 18, 26, 15).

6.Draw the 11-entry hash table that results from using the hash function h(i)=(3i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by chaining.

7.What is the worst-case time for putting n entries in an initially empty hash table, with collisions resolved by chaining? What is the best-case?

8.Use pseudo-code to describe the design algorithms for the following operations for a binary tree T. (5% each)

a..preorderNext(T, o): return the node visited after node o in a preorder traversal of T.

b.inorderNext(T, o): return the node visited after node o in an inorder traversal of T.

c.postorderNext(T, o): return the node visited after node o in a postorder traversal of T.