Let $G(V,E)$ be an undirected weighted graph with $|V|=n, |E|=m$. Recently Thorup and Zwick introduced a remarkable data-structure that stores all-pairs approximate distance information implicitly in $o(n^2)$ space, and yet answers any approximate distance query in {\em constant} time, hence the name {\em approximate distance oracle}. Given an integer $k>1$, a $(2k-1)$-approximate distance oracle requires $O(kn^{1+1/k})$ space and answers a $(2k-1)$-approximate distance query in $O(k)$ time. Thorup and Zwick showed that a $(2k-1)$-approximate distance oracle can be computed in $O(kmn^{1/k})$ time, and posed the following question : {\em Can $(2k-1)$-approximate distance oracle be computed in $\tilde{O}(n^2)$ time ?} In this paper, we answer their question in affirmative for unweighted graphs. We present an algorithm that computes $(2k-1)$-approximate distance oracle for a given unweighted graph in $\tilde{O}(n^2)$ time. One of the new ideas used in the improved algorithm also leads to the first linear time algorithm for computing an optimal size $(2,1)$-spanner of an unweighted graph.