Data structures and algorithms in java 6th edition by Michael T. Goodrich, Rober
ID: 3677064 • Letter: D
Question
Data structures and algorithms in java 6th edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
C-7.34
C-8.55
Give a formal proof that any sequence of n push or pop operations (that is, insertions or deletions at the end) on an initially empty dynamic array takes 0(n) time, if using the strategy described in Exercise C-7.29. C-7.32 Consider a variant of Exercise C-7.29, in which an array of capacity N is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/4. Give a formal proof that any sequence of n push or pop operations on an initially empty dynamic array takes O(n) time. C-7.33 Consider a variant of Exercise C-7.29, in which an array of capacity N, is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/2. Show that there exists a sequence of n push and pop operations that requires ohm(n^2) time to execute. C-7.34 Describe how to implement the queue ADT using two stacks as instance variables, such that all queue operations execute in amortized 0(1) time. Give a formal proof of the amortized bound. C-7.35 Reimplement the ArrayQueue class, from Section 6.2.2, using dynamic arrays to support unlimited capacity. Be especially careful about the treatment of a circular array when resizing.Explanation / Answer
C7-34- Here we need to compare satck and queue
Stack is LIFO organisation i.e.-last in first out whereas
Queue is FIFO-First in first out
ex push pop
Queue 1,2,3,4,5 1,2,3,4,5
Stack 1,2,3,4,5 5,4,3,2,1
so completely reverse and now if we reverse the stack
Reverse stack 5,4,3,2,1 1,2,3,4,5 will yield us the result which we want
So in this manner we can use two stack and just reversing a stack into another stack that is an easy task,the second stack can be used to cache the next n elements. Any new items added can just be pushed on to the first stack.
Pseudocode
Here we know push function 's complexity is The push function is just a simple push on to the first stack which is O(1). The pop function’s worst case will still be O(n), but only when the second stack is empty. If the second stack contains items however then the algorithm is O(1) and it contains item from stack one so the complexity is O(1) i.e. constant
c-8i)LCA -Lowest Common Ancestor
generally used in broadcastiing and multicansting where we need to trasfer a packet from A to G,J so first option is to use duplicacy and redundancy to transfer packet from A->C->E->G and A->C->F->H->J,here A->C path is repeated two times so why not found a lowest common ancestor like in this case and send single copy instead of two copies each time
1) Find path from root to n1 and store it in a satck
2) Find path from root to n2 and store it in another stack.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch.
public Position LCA(Tree T, Position p, Position q) // here t is the tree and position of p and q
{
Position lca;
Stack Sv = new Stack();
Stack Sw = new Stack();
Position temp1 = p;
Position temp2 = q;
while (temp1 != null)
{
Sv.push(temp1);
temp1=T.parent(temp1);
}
while (temp2 != null)
{
Sw.push(temp2);
temp2=T.parent(temp2);
};
while (!Sv.isEmpty() && Sv.peak() == Sw.peak() )
{
lca = Sv.pop();
Sw.pop();
}
return lca;
}
Here complexity
=O(h) where h is the height of the tree so anyhow
O(h)=O(n) i.e. directly propotional to the number of elements
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.