As I noted in an earlier blog, even little discoveries makes one feel wonderful. Today I solved a small problem (i.e., made a little discovery) and I feel wonderful.

I am reading a wonderful book, Introduction to Graph Theory. I am at the part where it describes *complete graphs*. A complete graph is one where each vertex is connected to every other vertex. The author asks, *How many edges are in a complete graph with N vertices?* I took this as a challenge to use my reasoning skills to figure it out.

Here are three examples of complete graphs and the number of edges in each graph:

Let’s arbitrarily choose one vertex. It must connect to the other (n-1) vertices. For example, in the complete graph with 4 vertices, the vertex will connect to the other 3 vertices:

The remaining vertices must form a complete graph amongst themselves. Ah Ha! Now we have a simpler problem: find the number of edges in a complete graph of n-1 vertices.

I now switch on my programmer hat. I smell recursion (which I love):

numEdges (N) {
if (N == 2) then return 1
else return (N-1) + numEdges (N-1)

Let’s check that program:

if N = 2, then num edges = 2

if N = 3, then num edges = 2 + 1 = 3

if N = 4, then num edges = 3 + 3 = 6

if N = 5, then num edges = 4 + 6 = 10

if N = 6, then num edges = 5 + 10 = 15

if N = 7, then num edges = 6 + 15 = 21

if N = 8, then num edges = 7 + 21 = 28

Wow! That is cool.

One problem, however. What are the number of edges when, say, N = 1000?

I could implement the above program and set it to solve N=1000. But I know the mathematicians would tell me: *Find a formula.*

Okay, let’s see … to find the number of edges in a complete graph with N vertices, I must add these numbers:

(N-1) + (N-2) + (N-3) + … + 1

or equivalently:

1 + 2 + … + (N-1)

I remember from school days a formula for the sum of the first N integers:

n(n+1)/2

Of course, I want the sum of the first N-1 integers, so I substitute “n” with N-1:

(N-1)((N-1)+1)/2

= (N-1)(N-1+1)/2

= (N-1)(N)/2

= N(N-1)/2

Let’s check:

if N = 2, then 2(1)/2 = 1

if N = 3, then num edges = 3(2)/2 = 6

if N = 4, then num edges = 4(3)/2 = 6

if N = 5, then num edges = 5(4)/2 = 10

if N = 6, then num edges = 6(5)/2 = 15

if N = 7, then num edges = 7(6)/2 = 21

if N = 8, then num edges = 8(7)/2 = 28

Yea!

I am pretty proud of myself. I solved it, not because it was a homework problem or a work problem. I solved it purely for the love of learning. I figured it out by simple reasoning.

I feel wonderful.

## Why are there no comments in DNA?

December 12, 2015In Computer Science one is taught early on that sprinkling comments liberally throughout code is a good thing. Comments enable the writer to remember what was done and readers to understand the code.

If comments are so useful to understanding, then why do biological systems have no comments? For instance, there are no comments in DNA. Wouldn’t comments make it easier to unravel the mysteries of DNA?

Suppose there were comments in DNA. What language would the comments be written in? It doesn’t seem reasonable that comments would be written in English (or French, German, etc.) since those are relatively recent languages whereas DNA has been around much longer. If DNA did have comments they would likely be written in a language that we don’t understand. Unraveling that language is likely to be as difficult as understanding DNA itself. In other words, comments probably wouldn’t help.

Consider this thought experiment: suppose one day we humans receive a message from an advanced civilization from another planet. People tell me that the message will likely be in a formal language such as mathematics. Will the advanced beings include comments in their message? Or will it be written purely in a formal language? As with DNA, it’s likely there will be no comments as any comments would most certainly not be a language that we humans use or understand.

So it seems that for a thing that must span the ages, such as DNA, and for a thing that must span civilizations, such as a message from an alien planet, the thing itself must be understood and comments are useless.

The formal structure/language must speak for itself.

Tags:aliens, code, comments, Computer Science, extraterrestial, humans, Language, programming, programming language, SETI, understanding

Posted in Uncategorized | Leave a Comment »