Describe how to optimize quicksort so that the Qn2 worstcase

Describe how to optimize quicksort so that the Q(n^2) worst-case run time behavior does not occur. Describe how do vector lists and linked lists differ. What would make you choose to implement one over the other in your programs? What are the conditions that can cause rotations in AVL Binary Search Trees? What is the difference between Prims and Kruskal\'s algorithms for generating minimum spanning trees? Design an implementation of a queue using two stacks. What are the time complexities of the push and pop operations?

Solution

4)

what is the difference between prims and kruskla\'s algorithm for generating minimum spanning tree

kruskals algorithm:
i) In this graph theory we use a connected weighted graph to find minimum spanning tree
ii)it will add edges one at a time and the next line will be shortest only

prism\'s algorithm:
i) In this graph theory we use a connected weighted undirected graph to find minimum spanning tree
ii)it builds spanning tree by adding at a time one vertex .and coming or next vertex will be the
nearest vertex

******************************************************************************************************

what are the conditions that can cause rotations in AVL Binary search Trees
sol: the condition for avl tree is it checks the height of the left subtree and height of the right
sub tree and compare both and difference should not be greater than one . thsi is also calles balance
Factor

*****************************************************************************************************

describe how do vector lists and linked lists differ

sol:

i)vector:

it is very much helpfull accessing random data and also good for insertion and deletion at end
,but it is not that much helpful while inserting and deleting front and at any other postion

ii)it will have contiguously memory .so the traversing is easy and efficient

Linked list:
i)there are good at inserting and deleting both front and back .
ii)it will take constant time for inserting and deleting data at particular node which we cannot do in vector
iii) it will not have contiguosly memory

i would prefer linked list while implementing the program . beacause
i)it is very handy and easy to implement
ii)the reason why i didnt choose vector is it is outdated and we didnt get support from the source
to implement it