Data Structures & Algorithms
Coursework Assignment 1

Q1. (a) Algorithm swap(x, y): Node n head While (n.getNext () != x ) do n n.getNext() Node v y.getNext () n.setNext(y) y.setNext(x) x.setNext(v)

(b) Algorithm swap Doubly(x, y): DNode n x.getPrev() DNode v y.getPrev() n.setNext(y) y.setPrev(n) y.setNext(x) x.setPrev(y) x.setNext(v) v.setPrev(x)

(c) The run time complexity for the singled linked algorithm is O (n) and for the doubly linked algorithm is O (1). Doubly linked list has the best time complexity. Time complexity in singly linked list take more time because we have to move from head to the node before x
Q2. (b) RedBlueStack implements Stack{ protected Object A[]; Int capacity; int top = -1;

RedBlueStack(int cap)
{
A = new Object [capacity]; capacity = cap;
}

int size()
{
return (top + 1);
}
void push(Object obj) throws FullStackException
{
if (size() == capacity) throws new FullStackException("Stack is full.");
A[++top] = obj;
}

Object top() throws EmptyStackException
{
if (isEmpty()) throws new EmptyStackException("Stack is empty."); return A[top];
}

Boolean isEmpty()
{
return (top < 0);
}

Object top() throws EmptyStackException
{
if (isEmpty()) throws new EmptyStackException("Stack is empty."); return A[top]; } Object pop() throws EmptyStackException
{
Object elem; if (isEmpty()) throws new EmptyStackException("Stack is empty."); elem = A[top];
A[top--] = null return elem;
}
}

Q3. (a) To implement the Stack ADT using two queues, assume we have q1 and q2, we can simply enqueue elements into q1 when a push call is made. When a pop call is made, we can dequeue all elements of q1 and enqueue them inside q2 except for the last element which we set in a temp variable. Then we return the elements to q1 by dequeuing from q2 and enqueuing into q1. The last element that we set as a temp variable is then returned as the result of the pop method. (b) The run-time complexity for push method is O(1) and for the pop method is O(n).

Q4. (a) No, It is not possible for the post-order traversal and pre-order traversal of T with more than one node to visit the nodes in the same order. A post-order traversal node will always visit an external node first while a pre-order traversal will always visit the root node first. (b) Yes, It is possible the post-order traversal of T visits the nodes in the reverse order of the pre-order traversal of T. An example of it is a tree with only two nodes.

(c) First step: (Left sub tree) (Right sub tree) In-order: 10,30,40,50,60,70,90 (Left sub tree) (Right sub tree) Pre-order: 50,30,10,40,70,60,90

* The first element of the pre-order is the root * We mark the root in in-order result Second Step: Diagram: 50
50

In-order: 10,30,40 Pre-order: 30,10,40
70
70
30
30

Third Step: In-order: 60,70,90 60
60
40
40
10
10
90
90
Pre-order: 70,60,90

References: 1. I have read about linked and doubly lists from here and here. 2. I have read about stack and queues from here. 3. I have read about tree traversals from here.