1:
Top of stack of Stack 1 represents
the rear end of the queue.So enqueue(e) operation just push(e) to
this stack.
The running time of enqueue is
O(1).
For dequeue() operation ,
pop elements from Stack 1 and push that into stack2 till stack 1 is empty.Now
the top of stack of Stack 2 contains the front element of the queue.So
do pop operation on Stack2.Then pop elements from Stack2 and push that
to Stack1 till stack2 becomes empty.Each set of push() operation takes
O(n) times and each set of pop operation takes O(n) time where 'n' is the
no size() of the queue before dequeue() is called.So the running time of
dequeue is O(4n) which is equal to O(n).
isEmpty() checks whether the stack1 is empty or not.If
the Stack1 is empty then returns true otherwise returns false.
size() method calls the size() method of Stack1.
2:
Algorithm ConcatenateList(L,M)
//input Singly
linked lists L and M.
//output : header
of concatenated list
//headerl - header of the list L
last <- headerl.next;
//find the tail node
in the list L
while last !=
null
do last <- last.next;
//headerm - header
of list M
last.next <- headerm.next;
return headerl;
ConcatenateList(L, M) searches all the nodes starting from header in list L and find the tail node in the list.It gets the head of the list M from the next value of header of list M.Then assigns the next value of tail node in list L to head node in list M.There are 'n' number of nodes in List L and ''m' number of nodes in list M. The running time to find the last node of List is O(n).Other operations takes constant amount of time.So the running time of ConcatenateList is O(n);
3:
To implement the Vector ADT we can use the circular
array based implementation.There are two pointers p and q.
p always points to the element at rank 0
and q points to the element at at the highest rank in the vector.In this
implementation the vector can contain no more than N - 1 objects where
N is the array size.
To insert or remove elements from rank 0 and and at the end of the vector doesn't need any shifting of the elements.So the time for these opearations is O(1).To insert an element at any rank other than rank = 0 and at the end of the vector, all elements having rank higher or equal to this rank is moved one position forward.While removing the element , all elements having rank higher than this is moved one position backward.p and q always poits to the index of element at rank 0 and index of the last element in the vector respectively.
Algorithm size():
if p <= q
s <- p -q + 1
else
s <-
(N - p) + (q + 1)
return s
Algorithm insertAtRank(r, e):
if size
= N - 1 then
throw VectorFullException
if r = 0
then if p = 0
then V[ N -1] <- e
p <- N -1
else V[ (p - 1) mod N ] <-
e
p <- (p -1) mod N
else if r
= size
then V[ (q + 1) mod N) ] <- e
q <- (q + 1) mod N
else
j <- 0;
t <- q
while j < (size - r)
do V[(t + 1) mod N] <- V[t]
t <- t -1
if t < 0
then t = N -1
V[t - 1] <- e
q <- (q +1) mod N
Algorithm removeAtRank(r ):
if size
= 0 then
throw VectorEmptyException
if r = 0
then V[p] <- null
p <- (p + 1) mod N
else
if r = size - 1
then V[q] <- null
q <- (q -1) mod N
else
if p <= q
then t <- p+ r
else t <- r -(N - p)
v[t] <- null
j <- 0
while j < r
x <- t -1;
if x = 0
then x = N -1
V[t] <- V[x]
t <- x
Algorithm elemAtRank(r):
if size = 0 then
throw VectorEmptyException
if p <= q
then e <- V[ p+r]
else
e <- V[r -(N - p)]
return
e
4:
public int rankOf( Position p) {
DNode
node;
try{
node = checkPosition(p);
} catch
(InvalidPositionException ie){
System.out.println("Invalid Position :" + ie);
}
int
rank = 0;
while(node.getPrev()
!= header){
rank ++;
node = node.getPrev();
}
return rank;
}
5:
Using the Sequence ADT to implement the
game , each element in the game indicates the participants in the game.To
pass the potato among children , we start traversing the sequence
from some element in the sequence , say start .If the end of the sequence
is reached we will continue from the beginning of the sequence.One pass
means traversal from one node to the next node.After k such passes we stop
that round.Then we delete the k + 1 th element which corresponds
to the child with the potato at the end of one round. In the next round
traversing starts from the k + 1 the element in the sequence.This is repeated
till only one element remains in the sequence.
Suppose we are implemneting the Sequence
ADT with doubly linked list. There are n -1 rounds.In each
round we have make k traversals which takes a total time of O(k)
and one remove which takes time O(1).So total time taken for one
round is O(k + 1).Since there are n-1 rounds the total time for this algorithm
is O(n(k +1)).
If we are implementing the Sequence
ADT with circular array , the time taken for the traversal is order O(1),
but the time taken for remove() is O(n).Total time taken for traversal
in one round is O(k). But the size of the sequence is decreasing
by one in each round.So the running time for remove is varying from
O(n),O(n-1) , O(n -2 ) , O(n-3 ) .................O(2);So the total running
time for each round can be written as O(k + n),O(k + n-1) , O(k + n -2)
, O(k + n -3) ,......O(k +2)
So the total running time for the algorithm is
the summation of total time taken in the n - 1 rounds. So it is O(nk +
n²).
6.
Algorithm ReverseList(L)
//head(L) gives the head of the list L.
prev <- head(L);
curr <- prev;
key <- curr.next;
curr.next <- null;
while key != null
do curr <- key;
key <- curr.next;
curr.next <- prev;
prev <- curr;
return L