Posts Tagged ‘mathematics’

Computer Science Algorithms are way better than Mathematical Theorems

January 24, 2015

I see a great deal of beauty in mathematics. There is much beauty in a well-described, step-by-step proof of a theorem.

Lately I have been learning algorithms for parsing and compilers from a pair of marvelous books. [1] I think the author is one of the best technical writers in the world, which makes learning very enjoyable. As I learn the parsing and compiler algorithms described in the books, the same sense of beauty rises up inside me as with a good math theorem proof.

So both Mathematical theorems and Computer Science algorithms have tremendous beauty. Nonetheless, I think that Computer Science algorithms are way better than Mathematical theorems. Here’s why:

In Mathematics there is a tightly constrained framework in which one operates. There is a limited set of building blocks (axioms) and rules that one uses to perform work. Conversely, in Computer Science algorithms there is no such finite, well-defined set of building blocks and rules. Although there are commonly used techniques – recursion, closure, induction, etc. – there are an infinite number of concepts that may be used to create an algorithm. That infinite variety provides enormous power and complexity, and requires great creativity and ingenuity, and is why I think Computer Science algorithms are way better than Mathematical theorems.

[1] “Parsing Techniques” by Dick Grune et al, “Modern Compiler Design” by Dick Grune et al.

Tags:, , , , , , , , , , , , ,
Posted in Uncategorized | 1 Comment »

Ways To Specify Things Precisely And Clearly

February 23, 2014

I am interested in hearing your thoughts on this:

Need Precision And Clearness

In work and in daily life it is important to be precise and clear. Mathematics is one way to achieve precision and clearness, if the problem is numerical in nature. However, there are many problems that require precision and clearness and are not numerical in nature. I think our educational system devotes too much time to mathematics as a way to express precision and clearness, and not enough time to the other means to express precision and clearness.

Allow me to explain please…

My Kitchen Has 10 Pieces Of Fruit

In my kitchen I always keep 10 pieces of fruit on hand. Of the 10 pieces of fruit I always have two varieties: bananas and oranges, pears and kiwis, etc. If I wanted to rigorously specify this, I could create a mathematical equation:

x + y = 10

where x represents one kind of fruit and y the other.

Equations are great for precisely and clearly specifying things that are numerical, such as the count of pieces of fruit in my kitchen.

Being able to specify things precisely and clearly is important. Mathematical equations are great for this: they are succinct, they are abstract (free of irrelevant details such as the fruit’s color, shape, and texture), and they avoid the clumsiness of the English language (“I have 10 pieces of fruit and of them I have two varieties” is clumsy compared to “x + y = 10“).

Non-Numerical Problems Need Precision And Clearness

Not everything that we want to specify precisely and clearly is numerical. For instance, it would be useful to precisely and clearly specify the format of a Web page (i.e., HTML): an HTML document must have html at the beginning (the root element) and it must contain a head element followed by a body element; the head must contain zero or more meta elements and a title element, and so forth. Some very smart people have developed a succinct, precise way of specifying the HTML format, using something called a “BNF grammar.”  A BNF grammar contains “rules” and each rule specifies the content of each element, e.g.,

<html> ::= <head> <body>
<head> ::= <meta>* <title>
<body> ::= …

That notation might look strange. That illustrates my point. Here we have something that is non-numerical and needs a precise and clear specification. The BNF grammar notation is something that our educational system should expose to students early in their education.

Students need to see that (1) things need to be specified precisely and clearly, (2) not everything is numerical, and (3) non-numerical things can be expressed as precisely and clearly as numerical things.

There are many other non-numerical things that would benefit from a precise and clear specification. For example, think about the shipping requirements of Fedex and UPS. In order to ship a package from point A to point B it may have to go through point C. But if point C is unavailable (heavy snow storm there) then the package needs to be re-routed to point D and then E. You get the idea. A precise and clear specification of the routing problem is needed. It is not a numerical problem and so mathematical equations are of limited use. Some very smart people have developed a succinct and precise formalism for this type of thing, called graphs. I won’t go into an explanation of them. The point to be made here is that this is another example of a non-numerical problem for which we need precision and clearness, and students should learn at an early age these formalisms.

Summary

Mathematical equations are great for expressing numerical problems precisely and clearly. Our educational system exposes students early to this way of specifying problems. But there are other problems that are not numerical, require precision and clearness, and for which ways have been created for  specifying them. I think that our educational system should expose students early to these other ways. I think that by the time a student is 10 years old he/she should have been exposed to BNF grammars, graph theory, Turing machines, finite automata, and probably several other things.

Tags:, , , , , , , , , , , , ,
Posted in Uncategorized | Leave a Comment »

Is pi an invented artifact or a natural phenomenon discovered ?

November 14, 2013

This is a common occurrence in mathematics: The first time a young student sees the mathematical constant π, it looks like just one more school artifact; one more arbitrary symbol whose definition to memorize for the next test. Later, if he or she persists, this perception changes. In many branches of mathematics and with many practical applications, π keeps turning up. “There it is again!” says the student, thus joining the ranks of mathematicians for whom mathematics seems less like an artifact invented and more like a natural phenomenon discovered.

                — Adam Brooks Webber

Tags:, , , ,
Posted in Uncategorized | Leave a Comment »

Learning for the sheer love of it … determining the number of edges in a complete graph

September 7, 2013

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:

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:

A vertex connects to n-1 other 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.

Tags:, , , , , , , ,
Posted in Uncategorized | Leave a Comment »