Tags

, , , ,

Teaching students programming and computer science one hour of code at a time.  Here is the official site where you can learn how to become involved.   I thought I would take an opportunity here to make my contribution.  In this lesson, I will use as my guide, a great introductory to Computer Science (CS) text, often referred to as the “purple” book, or the “wizard” book.

What is Computer Science?

Computer science is really a misnomer.  It is not a science.  We don’t study a system, observe phenomena, and run experiments to validate a hypothesis.  Computer science is not a study of computers anymore than biology is the study of microscopes.  A computer is simply a tool.  And computational devices come in many different forms.  There are the silicon-based binary gadgets that you use everyday, like laptops, tablets, and smart phones.  But they are poor imitations of the most powerful computing device ever created: the human being.  We are a bio-mechanical machine, performing our computations in base 10.  And of course, we are capable of much, much more.

Declarative and Imperative Knowledge

Computer science is not a science; it is more of an art — an engineering practice.  Computer science is really about knowledge.  The knowledge of how to do something: solve a problem, perform a task in a methodical, mechanical process.  This process is called imperative knowledge.  It is the knowledge of how to do something.  Declarative knowledge, on the other hand, deals with the facts.  Let me illustrate with an example found in the purple book.

Example: Square Roots by Newton’s Method

An example of declarative knowledge:

The above is a fact about square roots.  You can find it in any basic math text.  In words: the square root of any number x, is a number y, where y is a positive number, and if I multiply y by itself.  I get x.  For example: let x be 4, then y must be 2 because 2 times 2 equals 4.  You can reason the same for 16, or even 625.  Larger numbers are harder.  You may have to make some educated guesses before you stumble upon the correct answer.
Well, that is all fine and dandy.  But what if you were given: \sqrt{2} ?  How can we use the above declarative knowledge to figure that out?  And that is the problem of declarative knowledge.  It doesn’t tell you how to calculate the square root of 2 — or how to find the square root of any number.  The declarative statement can only tell you how to recognize a square root if you saw one.

Newton’s Method

To solve the square root of any number, we will use a very old algorithm called Newton’s method.  Ironically, the method starts with a wild-ass guess (a WAG, we call it in the scientific and engineering community).  Then we refine our guess with successive approximations until we get to an answer that is good enough for government work.  Let’s construct our algorithm based on Newton’s method:

To find the approximation of the square root of x:

  1. Make a guess G
  2. Improve guess G by averaging G and x/G
  3. Keep improving until the guess is good enough.

Simple, right?  Don’t take my word for it.  Try it out.

table

Compare the 1.4142 with your calculator’s square root button.  You should see the 1.4142 plus a bunch of other numbers.  We solved out to four decimal places (to the 10-thousandths place), and that is good enough for us.

Now let us write this out as a recipe of instructions:

Square Root X:

  1. Make a guess G
  2. Is it good enough?:  absolute_value(G*G – X) < 0.0001 then G is the answer and we can stop; otherwise go to next step
  3. Improve guess G: G = (G + X/G)/2
  4. Repeat step 2.

So let’s step through our recipe.  First make a Scientific Wild-ass Guess.

Next we test our guess by, first squaring our guess and subtracting that guess with X.  We take the absolute value because your guess may be less than the square.  For example, in the square root of 2, our first guess was 1.  1 – 2 = -1 and we don’t want a negative number because we are measuring the distance between our guess and the perfect square X.  And since negative distances don’t make sense, we take the absolute value, which means we first remove the negative sign, and then see if the answer is within some threshold of tolerance.  In this case, less than one-ten-thousandths.  Or put another way, we will keep refining our guesses until we calculate the square root to four decimal places.  If our guess is less than our threshold, then we stop and G is our answer.  If not, we go to step three to improve our guess and repeat the process.

Try our recipe above out with a piece of paper and a calculator and see if you get the same results as in the table above, if you let X = 2.

If you made it this far, my dear reader, I want to congratulate you.  Together we wrote a computer program.  Our program is not in a traditional computer language like C, or C++, or even Python.  But it is in the language of English and math.  Any reasonably intelligent human computer, with some knowledge of middle school, or high school math should be able to follow our recipe (algorithm) and effectively become the square root button on a calculator.

I hope the above example gives you an idea of what programming and computer science is about.  Now, if you really want to learn a programming language, first pick a language and a site you can learn from.  I recommend code academy and the language of Python.  Python is very easy to learn.  Once you get the basics and the syntax down, see if you can take our little recipe above and translate it into your new language, and get a computer to do all this hard math stuff for us.

Related articles