As I managed to understand, When we are dealing with some dynamic data structure which has an average cost of O(1) Amortized Analysis in push and pop operations like vector in c++, the vector takes constant time per each push till it reaches to the Nth push (N = current size reserved), in the Nth push it takes linear time to allocate a new space typically with double the old size, and pretty the same done in pop operations.

Now assume that we have a vector of N current reserved space with N — 1 elements, every time we push a new element into the vector then pop it again, is this done in a linear time to change the allocated space ? it seems not, but why ?

Given positively weighted undirected graph G find a Spanning tree T which has the smallest possible diameter. (Tree diameter :is the maximum path over all the Shortest paths in the tree) Example Problems :

http://www.spoj.com/problems/PT07C/

http://www.spoj.com/problems/MDST/

I couldn't find any proper explanation for a solution to this problem, However i observed some cool stuff; if the graph we are dealing with was unweighted graph then we can solve this problem by bruteforcing every possible node and edge(cutting it with dummy node) and assume it as the center of our MDST then get SPT(shortest path tree) from this node and calculate it's diameter, The true MDST will be the one SPT which has the smallest diameter.

But in the Weighted Graph, things will be a little bit different when we try to cut an edge to place our dummy node, Where we should place it to get our MDST ? and is there more than a MDST or just a unique one ?

Note : i found this code by chance, but i couldn't manage to understand it

https://github.com/Malatawy15/Algorithms-Library/blob/master/Libraries/Minimum%20Diameter%20Spanning%20Tree.cpp

on 2D cartesian coordinate system.. Does the quadrilateral which has maximum area must have three overlapped points with one of the triangles which also have maximum area ? please provide a proof/counter example