Monday, January 30, 2012

The education system is broken, and here's how to fix it

As most of you know, I'm a high school student (freshman).

This year I complete my 10th year of being a full-time student (including kindergarten), and, I must say, I am sick and tired of the way people are "educated".

Take your typical mathematics class (my favorite subject inside and out of school) in the United States.

The teacher starts by checking the night before's homework (most of the time checking if people have done it), asks people if they're having any difficulties with it. If so, then he/she does that problem on the board and explains it. Then, introduces a topic like "rational functions", "imaginary numbers" or "the Pythagorean theorem", from the "textbook" which has a few examples in it.

The lesson usually consists of beginning by showing the formula for that chapter or section or unit or whatever the heck its called, and then having the students see a simple exercise in which they plugin a few numbers into this magical formula which then spits out the answers. 

Then, the teacher then picks a more "difficult" problem, in which the same formula is used, but, its a "real world application", in which students find things like the distance between two campsites or figure out how long it will take Bob to run around the track if he's going at so and so miles per hour.

And, the homework is handed out, which are exactly the same problems, just redressed with different numbers, and the cycle begins once again the next day.

So, what do people learn at the end of the chapter?

Absolutely Nothing.

Here's the problem.

First of all, the students are never given the idea about what how the formula actually came into existence. 

Basically, the current system dictates that it doesn't really matter where it came from, for all your concerns, someone just thought about it one fine day and wrote it down, you have a test coming up next week, so you'd better stop getting distracted and get the formula memorized or you'll fail.

So, this causes students to go about the "textbook" skipping everything but the formulas, and then memorizing those. Then, when the test comes along, those who had time to memorize their formulas do excellent, and those that had something going on get low grades.

Then, as soon as they're done with the test, they put in all of their efforts into memorizing the next set of formulas and have nothing left from the last set that they memorized except "I love *whatever the topic is*, I got a 96% on that test".

And, the "textbooks" have "real world applications", which involve doing things that people would never even DREAM about doing (there are an incredible amount of problems about outdoor activities), because they're just plain stupid (do you measure the distance between the department stores in your town with the Law of Cosines?). 

So, this causes students to think "when am I going to use any of this stuff anyway?", which is something I would think about very often if I hadn't taken the time to read a bit more about math.

These facts need to change. 

First of all, you might have noticed that I keep saying textbooks in quotes, and there's a reason for that. 

The textbooks suck.

Pick up any standard, run-of-the-mill textbook about "Algebra II" or "Precalculus", and you'll see a very similar picture.

The chapter begins, promising incredibly lackluster "real world applications". Then, goes into the first section, in which it tells you the formula in a conveniently highlighted box, which basically tells students not to read the rest of the passage, since its only there to make the book fatter anyway. 

Then, there are pictures of people doing sports and things considered "fun", and are related to the subject of matter extremely lightly, but, the publishers and authors assume that if you put in some pictures about sports, the students will "learn better" (a.k.a memorize formulas in a shorter amount of time). 

Then, there are a few examples in which the formula is used (again, no explanation of where it came from, or why it is needed), and ends with a horribly stale application, and then commences onto the exercises.

There are 110+ exercises in each section, about five of which are actually worth doing, since all the others are just slight deviations from the examples. 

At the end of it all, you haven't solved a single problem by thinking it out yourself, all you've done is plug in some numbers.

The biggest thing that these textbooks and curriculum lack are real problems. 

Right now, almost every high paying job (with a good success rate; e.g. you cannot count football players, since less than 1% of them make a high pay) in the world deals with solving problems.

Developers/Engineers?  
We solve general problems like "An easy way to share pictures is needed; we have to build it", but, we also solve problems like "The search results are taking way to long, is there some kind of way we can speed them up?"

Obviously, these are difficult problems, and there's no general "formula" to plug things into that'll spit out the right solution. 

We have to invent things as we go along.

Doctors? 
When a patient comes to you, you don't have a set method of identifying "he has so-so, and he needs this to fix him up". 

First of all, he gives you about 98 different things that are happening to him, and from there, you need to understand which ones are important and then find out what's wrong with him (assuming that the symptoms you said are important really are important)

You have to take a small amount of information given to you, and synthesize a solution.

Lawyers?

You have a set number of rules you have to follow, and some conditions given with some more information, you need to derive a conclusion. 

All of these things are what the current curricula lack.

There are no difficult problems that one must think about in order to find the solution, they are just things that as long as you don't make any mistakes, you'll be perfectly fine.

This makes students entirely neglect the point of mathematics!

The point of math isn't to find out the probability of Jimmy wearing red socks on Tuesday, or to memorize the Rational Root Theorem word for word, because you probably will never use those things in your entire life, but, the point of math is to show how clear headed thinking and problem-solving are executed.

Given a difficult problem, one must invent, synthesize and derive in order to find a solution, which may involve failed approaches, but, the result is much more lasting.

And, this cut-and-dried approach to math is useless, because as soon as you take advanced math courses in college, you'll realize that the "proof" sections in the book actually mattered!

Okay, so, I've stated all the problems, now, how about a solution?

First and foremost, get rid of the "Algebra II" and "Geometry" subdivision junk that's going on, its entirely useless. 

Math wasn't invented like that, and therefore should not be taught that way. 

Mathematics isn't a bunch of blocks of knowledge that you use parts of to do exercises, its this whole continuum where a problem, if not solvable by the methods in one field, can be moved to another.

Second, the textbooks are horrible and need to be rewritten.

To do that, we begin by placing a limit on the size of the textbook to 300 pages or so (sounds a bit Legalist, no?)

Then, we take out the horribly expensive and useless color pages (except for 4th grade and below; I really liked the colors then, because the textbook didn't really mean much), and replace them with black and white.

Since its all black and white, we'd might as well throw out the pictures of people surfing as well, since people draw mustaches on those anyway.  

Then, we rid ourselves of the idea of sections, since they get in the way anyway and constrict our overall "view" of mathematics too much.

Now, each chapter deals with each topic in a very conversational way, where the motivation of each step (all proofs included) is shown, and how one step leads to the next is very clearly shown.

There is one textbook that is currently in use that I would like to point out that does this incredibly well, which is Linear Algebra and Its Applications by Gilbert Strang. 
Matrix multiplication isn't just thrown out as a formula, but, its developed conversationally from the idea of linear systems (certain higher level textbooks do much better in this regard). 

And, the topics within a chapter are connected, one cannot just jump, everything is continuous. 

However, chapters can jump around math as much one would like, from Number Theory to Geometry and then to Combinatorics. 

All the exercises need to replaced with a few, well-selected sets of problems which not only extend the material, but, provide new insight as to how to take a simple idea and use it on a complex problem (Pigeonhole principle-esque stuff). 

Then, the section of textbooks would be quite solid.

Teachers need to be retrained, and paid a heck of a lot more than right now (think six figures), to make it a much more competitive field. Teaching needs to based around problems, starting lessons with problems, and then allowing the students to have a go at the problem, giving hints in between to lead them closer and closer to the solution. 

If we are able to make a large portion of these changes, we would be far better off than right now in terms of what students can take away from mathematics classes, regardless of what they study in the future.

That's my idea of how this would work, and I would love to hear yours, so, please drop it in the comment section below. 

If you liked this post, please tell me about it, so I'm encouraged to write more, and please follow (there's a button at the top right). 

Questions, comments, etc. all welcome!




Monday, January 23, 2012

Rotation Matrices for developers

Hi!

So, why the heck would you care about Rotation matrices?

Well, a rotation matrix is a "easy" (once you're used to it) way to specify how to rotate a certain plane with reference to the origin, so, if you're doing any kind of graphics programming (WebGL is all the rage these days), you should know this stuff pretty well.

First of all, what's a matrix?

A matrix, despite how complicated it sounds, is JUST a collection of data. Developers know that better than most, since many of us use two dimensional arrays all the time, and call them matrices, but, many times we don't really do any "proper" math with them.

So, if its just a collection of data, why's it useful? Well, the idea is that if you are able to lay out your data in a sort of a table form, it makes it much easier to reason about mathematically, because you can consider rows and columns in different ways.

One very important thing to realize about matrices is that if someone gives you this matrix:


$\begin{array}{ccc}
1& 1 & 0 \\
1 & 2 & 2 \\
2 & 3 & 1 \end{array}$

You can't assume anything about it (except for a couple of very unhelpful things, like you can consider it in rows and columns), so, you must have some idea about what the matrix is about. For example, this one could be a group of simultaneous equation's coefficients.

You might have noticed that so far I haven't really explained how a rotation matrix actually works.

Before I begin, you should have a basic understanding of vectors, which are incredibly simple (just an arrow, with a point at the head and another at the tail).

Basically, what does rotation actually mean? It means that we're taking vectors on a plane, and we're moving them so that they represent different vectors (as if we rotated the plane itself).

Now, take a step back, and pretend as if, instead of moving about the vectors, we are rotating the plane in which they reside. A bit like this:


(That took me almost an hour to make, so be grateful!)

Where the red axes are that of the rotated plane.
So, how do the values map out?

What I'm asking is if we take an arbitrary point $(x,y)$ and then we rotate it about the origin by some angle $\theta$, what will the new point be, in terms of $x$ and $y$? Diagrams always help:




As you can see the original point is $D$, which have rotated around the origin ($E$) by a certain angle $\angle FED$ to the point $F$.

So, lets say that $D$ has the coordinates $(x, y)$, and we're trying to find $F$ in terms of $x$ and $y$.

Some immediate conclusions (since $D = (x, y)$):

$DH = y$
$EH = x$

To make our lives easier (mostly my life easier) let's give the angles some symbols:

$\angle{DEH} = \phi$
$\angle{FED} = \theta$

And, since we are rotating about the origin, these must be true:

$EF = ED$
Let $EF=ED=r$

So, considering $\triangle{FEG}$, we can say:

$\cos{FEG} = EG/EF = EG/r  ... (1)$
$\sin{FEG} = FG/EF = FG/r   ... (2)$

Notice that $EG$ is the $x$ coordinate of $F$ and $FG$ is the $y$ coordinate of $F$, which is what we've set out to find. 

And, we notice this:

$\cos{FEG} = \cos{\theta+\phi} = \cos{\theta}\cos{\phi}-\sin{\theta}\sin{\phi} ... (3)$
$\sin{DEH} = \sin{\theta+\phi} = \sin{\theta}\cos{phi}+\sin{\phi}cos{\theta}    ... (4)$

Equating (1) with (3), and (2) with (4):

$EG = r(\cos{\theta}\cos{\phi}-\sin{\theta}\sin{\phi})$
$FG = r( \sin{\theta}\cos{phi}+\sin{\phi}cos{\theta})$

Now, we simplify using the simple idea that $\cos{\theta}*r = x$ and $\sin{\theta}*r = y$,

And, we get:

$EG = x*cos{\phi}-y*\sin{\phi}$
$FG = y*\cos{\phi}+x*\sin{\phi}$

And, that's what we wanted!

You might be wondering: "What does this have anything to do with matrices?"
If you weren't thinking about that, please pretend you were at this point.

So, in the equations that we found above, the only parts dependent on $\phi$ (the angle by which we rotate) are the trig functions, so, what if we just represented them separately and then we'd be able to concisely represent all kinds of rotations on a plane?

Basically, what we're doing this this:

$\text{Rotated vector} = \text{Some witchcraft}\cdot \text{Initial vector}$

So, in a bit clearer terms:

$\begin{array}{cc} x' \\ y' \\ \end{array} = \text{Some witchcraft} \cdot \begin{array}{cc} x \\ y \\ \end{array}$

(where the columns of numbers are vectors, I can't get the brackets to display, sorry)

That $\text{Some witchcraft}$ is a matrix!

And, that's because matrix multiplication is defined in such a way that we can multiply a matrix and a vector together, and get equations resembling those that we got for $EG$ and $FG$!


That right there is the matrix we use (pretend that the $\theta$ is actually $\phi$), and we multiply that with the $<x, y$ vector to get the equations we got for $EG$ and $FG$, because matrix multiplication is defined that way! 

You might think this is all a "rigged game", and it is, but, the amazing thing is, despite this seemingly arbitrary operation of matrix multiplication, it works in all kinds of different places, because it is based one of the most important computations in mathematics, known as a linear combination

And, matrices are used EVERYWHERE!

From analytic geometry to simultaneous equations to economics and game theory, and that's mostly because of the fact that you are allowed to make any assumptions about the data you would like, and idea of matrices allow you to perform on math on that data with a few constructs that applicable pretty much anywhere.

I would love your feedback on this article, and ideas for new ones!

If you like this, please consider following this blog, it gives me motivation to keep writing blog posts, and you'll be notified as soon as a new one comes out.

For the people who like the abstract algebra series, I took a little break from it because I was a bit bored with it, and I couldn't think of the next topic easily. 

I'd be happy to answer questions, so, you can put them in the comments section below (I'll usually respond immediately), or email me at dhaivatpandya AT g m a i l DOT com.

And, just before I close, I'm doing a startup called NimbleNotes, which allows to write productively (this blog post was written entirely with NimbleNotes), and currently is in closed beta, with an IndieGoGo project.

Have a nice day :)


Friday, January 13, 2012

Please don't do dates and times like this!

So, you might have read my last post.

And, that covered only one website, namely http://samsclub.com/.

The problem is much, much worse than that. So, this is what happened.

I downloaded the free Camtasia Studio trial for 30 days, and I really, really enjoyed it. But, like all other trials, its time came, it prompted me to drop some Franklins or it wouldn't let me use it. And, I was about to close out the application (hey; I didn't actually need it), when I thought maybe I would try making my system time go back a bit, and see if that did anything.

And it did.


It happily pretended like it was 1/7/12 instead of 1/13/12, and I could continue to use my trials for another 6 days (and, after that I could repeat the same trick again, or, I could just sent it farther back to begin with). That struck me that maybe a lot of other applications depend on system time.

And, I promise you, there are a LOT of them.

Skype is a big one, if you move your time back, and look at Skype conversations and enter in a new one, it goes back onto old conversations.

So, please, please don't get dates and times from the system! You need to get them from a synchronized UTC timeserver.

Thursday, January 5, 2012

Stupid coding errors

This funny thing occurred, and I thought it might be interesting.

I was watching someone make a monthly payment on some financed item on Sams Club, and was having some trouble.

The problem was, the computer had a incorrectly configured clock, which had the date set as February 6th, 2012 (this took place on January 5th, 2012).

And, Sams Club's website was using that date as the default value for the payment date.

I thought "Okay, that's not too bad, I can probably just change the date on it". Wrong.

Since SamsClub.com was using Javascript (bad idea) to get the date, it was also setting it as the MINIMUM date, which meant you cannot put in a date before that!

Now, what's the problem with that?

Well, say I'm a week late on my payment. To make that payment on time, all I have to do is set my system's clock to one week ago, and Sam's club will happily take the payment as if it was delivered a week ago.

Lessons learned:

Never, ever use Javascript to figure out the current date.

Atleast check the date before inserting it into the database.

Hopefully this will reach someone at Sam's Club, and they'll fix it...

Sunday, January 1, 2012

Abstract Algebra presented in a non-intimidating way (esp. for developers) - cryptography


Hi!

Hopefully you read the last post, and if you didn't, you really should (http://poincare101.blogspot.com/2011/12/abstract-algebra-presented-in-non.html), because I'll be building on that stuff this time around.

This time, we'll be going over an very interesting and applicable subject (if you've ever used a computer, you've experienced it in action), called cryptography, and more specifically, public-key cryptography.

Let's get started.

From the dawn of humans, there's always been one human who wants another one dead, and as time as gone has gone by, we have invented better and better (or, worse and worse) of accomplishing this.

One of such inventions was cryptography.

Communication is incredibly important in war, and Caesar (yes, that Caesar, the guy from Rome you learned about in history class and promptly forgot about after the test) needed a way to communicate with his generals spread out throughout the Roman empire in way such that even if the messenger was captured, the bad guys wouldn't be able to read the message.

So, he (and presumably his team of scholars he kept handy) developed the Caesar cipher. I won't go into a ton of detail here, mostly because I wrote an entire blog entry about it (http://poincare101.blogspot.com/2011/10/encryption-and-ciphers-part-1-this-is.html).

Basically, you shift over the alphabet over the message by a certain amount (that certain amount is called the key) to get the encrypted message, and, the person who wants to decrypt it shifts back the message by that certain key.

There worked for a little bit, but, it involved the fact that the people who Caesar sent his messages to had to be told of the key and Caesar didn't trust them enough for that, so this system was abandoned, and Caesar most likely returned to the time-tested and expensive method of sending a messenger with soldiers armed to the teeth.

People entirely overlooked this (rather important, as we'll see later) problem, and instead concentrated on the fact that the Caesar Cipher was easily cracked with statistical methods (all of this is explained quite thoroughly in the blog post I linked above).

Slowly, cryptography turned into a pastime for amateurs and enthusiasts, and it was not much of a subject by itself, until more and more developments followed, and the subject was looked upon by mathematicians.

One of these new and better ciphers is called the Vigenere (I refuse to take the time to put the accents in the right places) Cipher.
The basic idea was that it no longer kept the frequency of the original text (often called plaintext) intact, making it immune to the statistical methods that could be used on the Caesar Cipher, but, there were other methods it was vulnerable to.

One very large problem was still overlooked: both parties need to transact the key before hand, or this procedure wouldn't work.

Finally, some clever chap came up with the revolutionary (like, really revolutionary) idea of public key cryptography.

The concept is quite brilliant.

Say, you have Alice and Bob and they want to transact encrypted messages. In public key cryptography, both Alice and Bob each have a public key and a private key. 

The public keys are published somewhere that *everyone* can access them (not necessarily only Alice and Bob).
Now, Alice wants to send Bob a message. She finds Bob's public key and encrypts her message with it, and the sends off this encrypted message to Bob, who then decrypts it with his private key.

That means that the key that is used to decrypt the messages is never transacted, and Alice never needs to know it!

That means that if Caesar had used public key cryptography, he wouldn't have faced the problem he had, because his generals would never have to know his private key!

Of course, there's a problem (actually, a few of them) with that (otherwise there wouldn't be a NSA). 
The private key and the public key must somehow be related to each other, so, theoretically, given as much time as needed, it would be possible to derive the private key from the public key, so, the solution to that is to use a computationally hard problem to generate the public and private keys, so it would take much too long to get the private key from the public key for it to be practical.

You might have noticed that I've been quite vague so far; I haven't specified HOW the keys are actually generated, and the encryption is carried out to turn plaintext into ciphertext.

That's where the math begins.

I mentioned that we had to generate the keys with a "computationally hard" problem. What on earth does that mean?!

Its a pretty simple idea, it means that as you increase some parameter, the time taken to complete the problem skyrockets (not a perfect definition, but, it will suffice).

One such problem is called the Discrete Logarithm Problem (DLP, for short).

Basically, you have a prime $p$, and $g, h$ such that both are part of the $mod p$ set (i.e. between $0$ and $p-1$ inclusive).
The problem is to find an $x$ such that:

$h \equiv g^{x} \pmod {p}$

Let's see why that's so hard.

Let's set:

$p = 7$

$h = 6$

$g = 3$

Basically, the only approach to this is we try different values for $x$, find $g^x$, then find $g^x \pmod {p}$, and keep going until we find an $x$ such that

$h \equiv g^{x} \pmod {p}$

If you try this (and I highly encourage you to do this), you will find that $x = 3$ works. This is a pretty small example, but, turn up the numbers, and it becomes a pretty formidable problem.

Let's look a bit more deeply into this matter, why is this so hard?

Well, because we don't have any way find out an answer without brute-force.

Okay, why don't we have another way?

Because it deals with $\mod p$, for which we don't have a ton of tools to deal with.

Exactly! Primes often occur in such problems, because we don't have a complete picture of how primes operate, because as far as we understand it today, they don't form some kind of equation that we can plug numbers in and get (all) primes out.

Alright, now, how are we going to turn this into a key?

There's something called the Diffie Hellman key-exchange system, which is outlined as follows (with Alice and Bob trying to communicate):

1. There's a publicly listed prime number that is decided, in our example, it will be 19 ($p = 19$), and $g=2$, which is also publicly declared.
2. Alice picks a secret number (say, 6), and computes:
    
    $2^6 \equiv 64 \equiv 7 \pmod 19$
    
    and, sends this result off to Bob, and we call this result $A$.

3. Bob does the same (but, with his secret number, which is 13),
    $2^13 \equiv 3 \pmod 19$
    
    We'll call this $B$.

4. Now, Alice takes the number she received ($B$), and raises it to her secret number (call it $a$):
    
    $B^a \equiv 3^6 \equiv 7 \pmod 19$

5. Bob does similarly:
  
    $A^b \equiv 7^13 \equiv 7 \pmod 19$ 


As you can see, at the end, both of them share one key, despite having started from completely different keys, and since this is based on the DLP, it is incredibly hard to solve, even with a supercomputer for (very) large values for $p$ (200+ digits).

So, what does any of this have to do with groups?

Well, I'm glad you asked.

Groups (and abstract algebra in general), lets us generalize.

Using the definitions of cyclic groups that define only the properties we need, we can say this (quoted verbatim from Wikipedia):

  1. Alice and Bob agree on a finite cyclic group G and a generating element g in G. (This is usually done long before the rest of the protocol; g is assumed to be known by all attackers.) We will write the group G multiplicatively.
  2. Alice picks a random natural number a and sends ga to Bob.
  3. Bob picks a random natural number b and sends gb to Alice.
  4. Alice computes (gb)a.
  5. Bob computes (ga)b.

This immediately makes the system a LOT more powerful, because now, instead of dealing with just numbers, we can deal with ANY cyclic group we want, they can even be chess moves, if you can somehow wrangle them into a cyclic group.

Why is that helpful?

Well, if you're using natural numbers to do your bidding (since they form a cyclic group), you're still not fully secure, and there are other cyclic groups thought to be "more secure" (because of various properties of the groups themselves), and a popular such cyclic group are the points on an elliptic curve.

To explain *why* this actually happens, requires a great deal more knowledge, but, the idea of using groups to specify how the system works is profound; you can swap in any system you'd like to make a "cyclic group"


Hopefully you enjoyed that :)

All feedback is greatly appreciated!

If you have any questions (or feedback), please drop a comment below, and I'll do my best at answering them!