Please complete All correctly for $100.00 Using the Java programming language, i
ID: 3884772 • Letter: P
Question
Please complete All correctly for $100.00
Using the Java programming language, implement the deque ADT with a doubly linked list.
Implement an adapter class in Java programming language to support the stack interface using the methods from the array list ADT.
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.
Use pseudo-code to describe a nonrecursive method for performing an inorder traversal of a binary tree in linear time.
Illustrate the execution of the heap-sort algorithm on the following input sequence: (2, 5, 16, 4, 10, 23, 39, 18, 26, 15).
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.
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?
Use pseudo-code to describe the design algorithms for the following operations for a binary tree T. (5% each)
preorderNext(T, o): return the node visited after node o in a preorder traversal of T.
inorderNext(T, o): return the node visited after node o in an inorder traversal of T.
postorderNext(T, o): return the node visited after node o in a postorder traversal of T.
Explanation / Answer
1. Java program to implement the deque ADT with a doubly linked list :
"DoubleLinkedListNode.java" // this class creates the double linked list data structure.
public class DoubleLinkedListNode <T> {
private DoubleLinkedListNode<T> prev;
private DoubleLinkedListNode<T> next;
private T value;
public DoubleLinkedListNode<T> getPrev() {
return prev;
}
public void setPrev(DoubleLinkedListNode<T> prev) {
this.prev = prev;
}
public DoubleLinkedListNode<T> getNext() {
return next;
}
public void setNext(DoubleLinkedListNode<T> next) {
this.next = next;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
"DequeUsingDLL.java" //this class implements the deque using the double linked list created in the above class. This class contains the main method to run your program
public class DequeUsingDLL<T> {
private DoubleLinkedListNode<T> front;
private DoubleLinkedListNode<T> rear;
public void insertFront(T item) {
// add element at the beginning of the queue
System.out.println("adding at front: " + item);
DoubleLinkedListNode<T> nd = new DoubleLinkedListNode<T>();
nd.setValue(item);
nd.setNext(front);
if (front != null)
front.setPrev(nd);
if (front == null)
rear = nd;
front = nd;
}
public void insertRear(T item) {
// add element at the end of the queue
System.out.println("adding at rear: " + item);
DoubleLinkedListNode<T> nd = new DoubleLinkedListNode<T>();
nd.setValue(item);
nd.setPrev(rear);
if (rear != null)
rear.setNext(nd);
if (rear == null)
front = nd;
rear = nd;
}
public void removeFront() {
if (front == null) {
System.out.println("Deque underflow!! unable to remove.");
return;
}
// remove an item from the beginning of the queue
DoubleLinkedListNode<T> tmpFront = front.getNext();
if (tmpFront != null)
tmpFront.setPrev(null);
if (tmpFront == null)
rear = null;
System.out.println("removed from front: " + front.getValue());
front = tmpFront;
}
public void removeRear() {
if (rear == null) {
System.out.println("Deque underflow!! unable to remove.");
return;
}
// remove an item from the beginning of the queue
DoubleLinkedListNode<T> tmpRear = rear.getPrev();
if (tmpRear != null)
tmpRear.setNext(null);
if (tmpRear == null)
front = null;
System.out.println("removed from rear: " + rear.getValue());
rear = tmpRear;
}
public static void main(String a[]) {
DequeUsingDLL<Integer> deque = new DequeUsingDLL<Integer>();
deque.insertFront(58);
deque.removeFront();
deque.insertRear(78);
deque.insertRear(9956);
deque.removeRear();
deque.removeFront();
}
}
/************************************************************************************************/
2. Creating an adapter class to implement a stack using list interface
An adapter class is a class which adapts methods of another class by giving different names to essentially the same methods. For example stack originally has a default method called push and the adapter class can be created for this by giving another name "add" for push method .
First we will create an interface of stack. An interface is a class with 100 % abstract methods
"StackInterface.java" // this class contains the methods of a stack
package adapter;
public interface StackInterface<E> {
/** Pushes an item onto the top of the stack and returns
*the item pushed
*/
E push(E obj);
/**
* Returns the object at the top of the stack
* without removing it.
*/
E peek();
/**
* Returns the object at the top of the stack
* and removes it.
*/
E pop();
/**
* Returns true if the stack is empty; otherwise,
* returns false.
*/
boolean empty();
}
"ArrayListStack.java" // this class implements the interface StackInterface<E> as an adapter to the List. The override annotation tells the compiler that we are overriding the stack default methods. It is not necessary to have the override annotation
package adapter;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
public class ArrayListStack<E> implements StackInterface<E> {
/** The List containing the data */
private List<E> theData;
/**
* Construct an empty stack using an ArrayList as the container.
*/
public ArrayListStack() {
theData = new ArrayList<E>();
}
/**
* Push an object onto the stack.
*/
@Override
public E push(E obj) {
theData.add(obj);
return obj;
}
/**
* Peek at the top object on the stack.
*/
@Override
public E peek() {
if (empty()) {
throw new EmptyStackException();
}
return theData.get(theData.size() - 1);
}
/**
* Pop the top object off the stack.
*/
@Override
public E pop() {
if (empty()) {
throw new EmptyStackException();
}
return theData.remove(theData.size() - 1);
}
/**
* See whether the stack is empty.
*
* @return true if the stack is empty
*/
@Override
public boolean empty() {
return theData.size() == 0;
}
}
/************************************************************************************************/
3, Euler tour traversal for computing the number of descedents of each node of a binary tree
Psuedocode:
1. T.counter = number of nodes seen so far, Initialize T.counter = 0
2. int countEuler(T,v) // counting the number of descedents for a node v in tree T starts from root
{
3. count = T.counter; //number of nodes seen so far (not in subtree of node v)
4. T.counter++; //saw one more node, namely node v then visit on the left
5. if T.hasLeft (v) then
6. countEuler(T,T.left) //explore nodes to the left of v
7. if T.hasRight (v) then // visit on the right
8. countEuler(T,T.right) //explore nodes to the right of v
//at this point we explored all descendants of node v
9. v.numberOfdescendants = T counter – count – 1; //number of nodes seen so far – num. of nodes seen before v – 1 for node v itself
10. return v.numberOfdescendants
}
/**************************************************************************************/
4. Inorder traversal non recursive method:
1. void InOrderNonRecursiveTraversal(root)
{
2. createStack S;
3. while(1)
{
4. while(root) { // this loop keeps on adding the left subtree nodes to the stack
5. Push(S, root);
6. root = root.left; //going to the left
}
7. if(isEmptyStack(S)) then
8. break;
9. root = pop(S);
10. printf(root.data); // After popping, process the current node. This means the left subtree and current node is completed, now go to the right subtree.
11. root = root.right;
}
DeleteStack(S);
}
/**********************************************************************************************/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.