Inductive reasoning, and why you should care

Inductive reasoning, according Wikipedia:

Inductive reasoning, also known as induction, is a kind of reasoning that constructs or evaluates propositions that are abstractions of observations of individual instances of members of the same class.

That probably conveys absolutely no value to you. The best way to understand what inductive reasoning is, is to apply it.

In order to do that, we need some kind of problem which we can solve using a bit of induction.

I'm going to a pick a math problem. Why, you say? Math is almost always the easiest way to understand reasoning, since math's primary device of "progress", so to speak, is reasoning.

So, here's the problem:

The plane is divided into regions by drawing a finite number of straight lines. Show that it is possible to color each of these regions red or green in such a way that no two adjacent regions have the same color.

If at first this doesn't strike you as a math problem, you probably haven't met this chap called graph theory, or maybe haven't been introduced to bipartite graphs.

So, how do we go about solving this?

Before reading on, try out some cases; one line, two lines, ten lines, and so on. Try and figure out some patterns.

Now, I'll show you the solution.

First we consider one line. So, we can color the regions on opposite sides of the line opposite colors (i.e. red and green), and, we're done.

So, what happens when we add one line? Think about this for a moment. Can we try the same trick?

Yes! What we can do is take one side of the new line we just put in, and swap all the colors on that side (so, red goes to green, green goes to red), and, we get a complete solution! So, every time we add a line, we can simply follow this algorithm and get the correct coloring. Of course, this isn't a fully rigorous proof, but, it shows what we're after.

Inductive reasoning is taking a method you used to solve a problem for a set constraint (we knew how to do it for one line), and then extending that method to solve the problem without the constraint.

If write code, you probably do this all the time (and just didn't know what this was called). If you've got a function that's misbehaving, you pass in a couple of values that you think are forming an edge case, and you've noticed that its going wrong for *one* of these values, you change the function definition so that the errors don't happen.

But, you should use this kind of reasoning much more often. In nearly all problems where you are stuck on something going wrong on a constraint, try inductive reasoning. Of course, none of this actually happens consciously, but, if you try doing it consciously a couple of times, it "just happens" eventually.

 

The Travelling salesman problem

The travelling salesman problem is possibly the most famous and probably the most easy to understand of the so-called "NP-hard" problems computer scientists (and mathematicians) have found.

The problem statement is quite simple.

Consider you are a salesman, and you have, say, an $n$ number of cities you've got to cover by the end of the day. But, it would be best if you could minimize the distance that you have to travel between all of the cities, and, you know the coordinates of all the cities in reference to some point known as the *origin*. Given these coordinates, define an algorithm that would give you shortest possible path between the cities.

Of course, this doesn't seem like much of a problem at all when you first start at it (like most other difficult problems); you could just try all the routes between the cities, find the route with the minimum distance covered, and, you're done!

Let's see what that entails in terms of performance/scaling. With $n=5$ (i.e. five cities to visit), we have a total of $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ ways we can trace out the route between the cities, and we have to check all of these. That doesn't seem too bad for a computer.

How about for $n=10$? Well, $10! = 3,628,800$, so, its quite a big jump from $120$, but, still manageable.

Let's go up by another five; $n=15$. That gives: $15! = 1,307,674,368,000$. Holy cow. That's a lot. But, how did it jump that quickly?!

To answer that question, we'll need a bit of math (if you understand big Oh notation, you can skip the next couple of paragraphs).

Consider this situation. You have one car that's accelerating from a low speed, whereas another car is going at a higher speed, but, the second car's speed will not change. What do you think will happen if we let the cars go on forever? Of course, the car that's accelerating will overtake the car that's at a constant speed, right?

That's what scaling algorithms is all about. You might have one algorithm that performs better at lowever "sizes" of the input, but, a second algorithm may overtake it if it can "scale better" (i.e. accelerate). So, when we say that an algorithm is $O(n)$, what we mean is that the algorithm performs *linearly*, i.e. for each unit increase in $n$, we get a certain unit increase in the time spent (or, whatever else you're measuring). Similarly, $O(n^2)$ means that for every unit increase in $n$, we get that much of change, but, squared in output.

But, all of this still seems on some shaky ground, so, let's break out the equations (warning: if you don't know how limits work, skip this). This won't be a *completely* rigorous argument (which would require more math), but, it will be much better than the argument we have in place.

How can we say that a linear time algorithm (i.e. $O(n)$) will scale better than $O(n^2)$? Well, what we're informally saying is that the $O(n^2)$ grows much quicker (i.e. worse) than $O(n)$ as $n \to +\infty$. If you remember that bit about relative rates of growth from first semester calculus; $\lim_{n \to +\infty} \frac{n^2}{n} = \lim_{n \to +\infty} n = +\infty$

So, we've proved that $O(n^2)$ grows faster than $O(n)$, and therefore performs worse than $O(n)$.

What does that mean in terms of the traveling salesman problem? The traveling salesman problem brute force solution is in fact $O(n!)$ (since the number of routes goes up like that).

Why is this so bad?

Consider a polynomial time solution (i.e. $O(a_n x^n + a_{n-1} x^{n-1} ... + a_o)$). Using a bit of calculus/limits, we can say, for certain, that factorial algorithms are much worse than polynomial time solutions as $n \to \infty$.

That's what makes the travelling salesman problem interesting, because it has a non-polynomial solution, and, its something called a NP-Hard problem. What NP-Hard means is actually very complicated and heavily theoretical, but, it consitutes a very important part of the P vs NP problem, which, informally, asks (quoted from Wikipedia): "whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer" (s/quickly/polynomial time/g).

So, that's what the travelling salesman problem is, and why people care.

The new Blogger update ... sucks.

I've been using Blogger to host this site, and, frankly, its probably been one of my worst experiences with Google software, ever.

First of all, let me cover the the good things about it (i.e. why I chose it in the first place). Its very quick to get started with a blog, its easy to add AdSense if you want it, and that's about it.

What's wrong with it?

First of all, the widgets model is broken beyond all belief. All of the widgets that are provided are pretty much useless, and most things like syntax highlighting and LaTeX involve tacking on bits of Javascript onto the page, which Blogger doesn't mix with all too well. 

Secondly, the editor sucks. We're in 2012 here people, and it STILL escapes out when I hit tab. Why is this so difficult? Isn't Blogger now developed by the same company that makes Google Docs? 

Then, once Google+ came along, all of the other "social" buttons have been pushed off to the side and made quite tiny, which, is understandable when considering it from Google's point of view, but, from my point of view, it doesn't make much sense.

The themes are also far from amazing (http://www.bloggerthemes.net/ does try to remedy this), and the selection in font is pretty much non-existent. 

And, most of all, Blogger, in general, seems to try to get in your way every single time you want to just "write a short entry", or "get this article on the internet". 

So, what did the update fix/add?

It added some analytics directly on the front page; I was surprised to find out this blog had over 50,000 page views in the past 2 weeks. 

Also, it cleaned up a editor a *tiny* bit (it still escapes out on the tab), and, the main replacement was just making the editing textarea/contenteditable larger.

The design is also much better and clearer.

But, they still completely ignored the actual problems that plague Blogger; so, I just can't keep waiting any longer, I'm going to try and pick from the enormous assortment of options (Posterous had caught by eye, but, its been acquired, so, I don't want to risk anything on it). 

Experiences in Go-ing

I've been messing around with Go for quite some time now and I wanted to share my experiences.

When I first looked at Go, I put it aside as "just another language", and moved on with whatever I was doing.

I mean, there are languages popping up every day that are worth nothing whatsoever because the ideas they bring to the table are too few to take the risk of using a language that isn't popular (less documentation, less support, less everything).

That summer, I began writing some more low-level C/C++ code to implement a Bayesian classifier stock recommend-er thing. It was a complete disaster.

Just some basic string parsing was a nightmare; C gave no utilities whatsoever, and C++ was good, until I hit an error and it gave me a 20 line long error report, and, I had to use all kinds of specialized templates for the simplest of things!

And, the worst problem I faced was of sockets. Non-blocking, multi-plexed and cross-platform socket support with C is basically non-existent (unless I wanted to use libev or libevent, which has documentation scattered across the internet in small chunks). With C++, there are many choices, such as Boost.Asio (basically no documentation), ACE and ICE (this one I'm genuinely excited about, but, I hate their specialized object format crap I have to deal with).

And, of course, there's no language support for anything so if I ever wanted to distribute my code, the client would have to have the libraries.

I couldn't sacrifice performance (lots of number crunching was involved with costs tight), so, I couldn't pick Python.

Then, I came back to Go, and looked at it again from a different perspective, and hoped it would offer me something that could rid me of all of this.

I never did in fact write the Bayesian classifier thing (the idea wasn't much good anyway), but, the project introduced me to Go, which, I must say, is an amazing language.

The first thing I immediately noticed is that they got rid of the parentheses in "if" and "for" statements. Coming from Python, I really like this.

And, here's a language that's FINALLY SUPPORTING UNICODE FROM THE START!

Closures are supported and functions can be passed around like salt shakers, its wonderful!

All of the language seems well-thought out and cohesive; there aren't really any points that I felt like didn't match with the rest of system. Its very much like a suit without any stitch marks on it.

As for the standard library, its no short of awesome. It includes a lot of things that I've frequently wanted with C/C++ as part of the runtime, such as json, xml, http, a cryptography package, even websocket support built right in.

And, when they say it feels dynamic and interpreted, they actually mean it; the type system steps out your way for most of the time.

The only thing I find lacking is that there are no books on the language as of yet, but, I expect that will be remedied once the language is "marketed" a bit more (Google hasn't put a ton of weight on it ... yet).

It also has support for RPC which makes writing distributed computations really easy and quick.

Unless I have to write some really low-level code, I refrain from using C/C++ these days and instead reach for Go; about the same speed with half the development time.

I really encourage you to go check out Go, and just play around with it; you might start using it all the time.

To all the people who say programming competitions are useless

There's been this general vibe on HN and r/programming that programming competitions (that involve problems one must solve) on the whole have little to do with programming in general.

I beg to differ.

99% of us can crunch out Javascript and some backend language pretty quickly; some ajax interaction, maybe some form validation and some Twitter and Facebook APIs. And, a lot of us can quickly learn new things when we need to. Need to learn Scala for next project? No problem. Client wants to use the Face.com API? Alright, let's do it.

But, that's not the only stuff that matters.

Your skills are *really* tested when you hit a roadblock that isn't covered by the abstractions you're working on.

For example, the database inserts aren't happening fast enough, and the company doesn't want to buy any more servers to fix the problem, so, you've go to optimize it.

Programming competitions don't test whether or not you can go about updating portions of code, they test whether you are able to write code to solve a problem you've likely never heard of under a time constraint.

And, that's what companies would like in programmers.

Math based problems are just one way of approaching timed problem solving, and they work quite well, since many of us are well versed in at least basic math, and are able to get our hands around the problem so that we can begin to think about implementing it.

So, programming competitions *do* have to do with programming and the ability to solve problems, which is what development is all about.

BIOS primer

Most of us know what a BIOS looks like, and have a some bits and pieces of an idea about what its supposed to be doing. This needs to rememdied, so, read the rest of this article!

What happens when you hit the power button on a computer?

It doesn't actually go directly to the CPU, first, the BIOS code is loaded, because that's what's able to hoist up the CPU, hard drive, display, etc.

The BIOS is contained on an external chip (that's why some of you see your motherboard's manufacturer's name when you see the BIOS).

A BIOS not only lets you set the boot order (which was was most of us have used it for), it has a couple of jobs.

First of all, it configures your hardware.

Some hardware is dependent on others, has specific settings, etc.
All of this is handled by the BIOS, so that is ready for the bootloader.

Also, all (well, nearly all) computers have a system clock, which doesn't actually tell you the "time" (again, it could), it counts ticks from a certain date, such as the epoch. The BIOS sets this up.

It also selects what devices it can use as bootable, because there are certain types of storage devices that a BIOS cannot load of off (for example, random storage, volatile memory), and it identifies which are bootable.

Then, comes the main job of the BIOS. It calls a bit of code that resides on the selected storage devices on the first 512 bytes of the first sector.

In the early days of computers, 512 bytes was enough code to load the operating system, and things worked wonderfully.

Of course, this is no longer the case considering that the Linux kernel is almost 15 million lines of code.


So, these 512 bytes (known as the MBR) usually call *another* piece of code which then loads your operating system. Or, it could hold a list of sectors on your hard drive from which another piece of is then called.

The BIOS also provides a small API for the MBR to use to write to the screen, make some interrupts, etc.

Its pretty cool stuff...