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, March 4, 2011
How many levels?
4th, March, 2011
Tree is one interesting data structure in computer science. I like the properties of trees and graphs.
Sometimes we receive some junk mails, containing junk information something like if you don't forward the mail to next 3 people something bad will happen... bla... bla... bla... and some more BS... (these mails usually related to God, even if-at-all God exists, he might be laughing at such mails. Recently I have seen a funny mail, I will post on http://wemeanourthoughts.blogspot.com/ fun to read).
But as an Electronics and Computer Science Engineer, it fascinates me to find how many pages would go for waste because of sense-less people.
We can represent the above mail chain as an m-ary tree. Where m is the branching factor, such as 3 in the above case.
As a simple math, if the mail chain ends at L-th level, how much space would they all occupy in mail servers (ofcourse this is apart from the space on user machines, assume each mail takes few MBs since those mails contain pictures as well)?. It would be in few Giga Bytes of space.
If all the persons at X-level changes the number 3 to 6, how the output will be affected?
Reverse (Synthesis) Question:
Given there are N leaves in a binary tree, how many levels an optimally balanced binary tree can have?
Answer: log2N + 1
In general, an m-ary tree with N leaves can have logmN + 1 levels.