Once, Carl Friedrich Gauss said, "Mathematics is the queen of sciences and number theory is the queen of mathematics." Mathematics is a tool to prove our analogy. Here I post some of my collections that emphasis significance of mathematics in real life. Posts also include questions on computing, mathematics, Free-Open-Source-Software, Algorithms, Data Structures and computers in general. All thoughts/opinions are mine, not related to my employer.
Friday, February 25, 2011
Shortest path in connecting all vertices
Given below 4 vertices on a two dimensional plane. Connect them in shortest possible way. In other words, there are 4 cities A, B, C and D at the corner of square of side (a) units. What will be the minimum cost of connecting these cities?
Those making circuit layouts of VLSI chips need to solve the puzzle smartly. Even 0.1% gain in space is huge on miniaturized chips.
Answer: Assuming the side of square as s, the minimum cost (road connecting all four cities) is s x (SQRT(3) + 1)