#theoretical cs

I just....I’m constantly awed. You don’t have to be necessarily the best in a field to appreciate its beauty. To be constantly humbled by its consequences and magnitude.

I’m happy I don’t know as much as I should because every discovery or new knowledge is like uncovering a whole new treasure.

If you’ll give me a moment of your time I’ll demonstrate my favourite bit in Theoretical Computer Science/ Pure Mathematics.

Right, so. 

Have you ever thought of infinity? One man in particular did. His name was Cantor. And man did he get right into it.

So, apparently there are two kinds of infinities (More on that later)....and one is bigger than the other.

But how can one infinity be bigger than another? forever means forever, right? 

Does it? Does it really?

Imagine this, I give you a number (Say 0), and tell you to add 1 to it, write it down, and then add one to that number, and so on.....could you say, with confidence that given enough time and boredom, you would eventually reach a certain number?-----(1)

Say, 1234567890456456575676767? Could you guarantee that you will eventually reach this number if you went on with the above “algorithm” (which basically means list of steps)?

Yes.

This is called being countably infinite. Like those of natural or whole numbers.

(Question: are the number of numbers from 0 to infinity, more than the number of numbers from 1 to infinity? Is the first a smaller infinity than the second?)

But suppose I tell you starting from 1, give me all the numbers till 2. With a precision of 2. You would tell me, 1.00, 1.01,1.02,.......,1.99, 2.00.

Okay, still countable. Right?

(Is it a bigger infinity tho than the infinity we got in (1)?)

But what if I give you no precision?

If I told you, give me all numbers between 1 and 2.....what would you say? First number is easy, 1.0000.....0000000......, then what? What’s the next number?

There lie infinities between infinity.

This is called an uncountable infinity. like those of real numbers (the proof for this is cool).

Now we can all agree that uncountable infinity > countable infinity, right?

But do there exist more than these two infinities????? This is what is commonly called as the Continuum Hypothesis: there does not exist any infinity that is more than that of a countable set and less than that of uncountable

And you know what the best thing is about this??????

It has been proved that this hypothesis can neither be proved nor disproved!!!!!

This means that a mathematician can just say YOLO and chose either as a base rule (or axiom) and run with it.

And you thought comics were bad with official canon.

Lol.

But this is all the basis for my favourite thing in the world.

So, in Computer Science, everything can be written (encoded) in terms of 1s and 0s. Even letters.

For example:

01100101011101100110010101110010011110010111010001101000011010010110111001100111 0110100101110011 011000110110111101101111011011000110010101110010 0110100101101110 011000100110100101101110011000010111001001111001

is a complete sentence!

(try to convert it to ASCII)

Anyway, we can then take it a step further and see than any, and I do mean any, work of text - code, songs, poems, fanfiction, etc - can be encoded in binary.

Similarly, binary can be decoded into ASCII (the symbols we read). 

Now if I take all the possible permutations and combinations of all terminating binary strings.......like, 0, 1, 01, 10, 11,..........

and I go through them.....will it be countable or uncountable?

(Spoiler: it’s countable!!!!!)

WHAT DOES THIS MEAN?????????

This means that if have an infinite list of all terminating binary strings, and go through it one by one.......we will be able to eventually reach all the text that is either 1) ever been written, 2) is currently being written, 3) or will ever be written.

We have found a way to capture human creativity!!!!

So, suppose we had never heard of Shakespeare, we will eventually reach Romeo and Juliet in the list of finite binary strings!!!!

I just.....that’s beautiful to me.

Here’s a fun article for the day!

Essentially, graphs can be represented as two operations over a set, an ‘add’ operation (a+b is the smallest graph containing graphs a and b as subgraphs) and a ‘join’ operation (a->b is the graph created by joining all nodes from a to all nodes of b).

This quarter at Northwestern I'm taking "Mathematical Foundations of Computer Science" AKA Discrete Math. While most programmers I know personally tend to detest the more theoretical areas of computer science, I've always had a fascination with those types of problems. It just so happens that in the first class my professor (Nicole Immorlica) showed us a very elegant proof on the board. That week we also had a problem set that required a similar approach, although it was not obvious from the problem description. I figured I might as well write something about it for like-minded people and also for my own memory (can't forget the final!).

The first problem, I later figured out, is called the "mutilated chessboard" problem. The idea is that one is given a chessboard, but with two opposite corners cut out. The question is, is it possible to cover the entire board with dominoes such that every square is covered once and only once?

The mutilated chessboard.

The solution here is really a rather elegant one. Note that in the mutilated chessboard every square has a color associated with it. Also note that the "checker" pattern means that the colors are alternating—a white square never touches another white square orthogonally and vice versa. This implies that a domino covering two squares must cover one black and one white square. This also means that any number of dominoes on the board must cover an equal number of white and black squares. So can we cover the board with dominoes? No, because you'll notice that the two squares that have been removed from the chessboard are both black. This means that there are 32 white pieces on the chessboard, but only 30 black pieces, making complete coverage impossible.

The second problem we were presented with, at first glance, doesn't seem anything like the first problem. However, we will soon find that the same approaches can be used to prove a number of different suppositions about these problems. I have reproduced the problem text in full below:

Imagine an apartment complex with 3 floors, each of which contains 9 apartments arranged in a 3 × 3 grid. In each apartment there is a child who has lost a tooth. The tooth fairy must collect all the teeth, starting with the apartment on the ground floor in the southwest corner. Passing only through walls, ceilings, and floors, is it possible for her to collect the tooth of the child in the middle apartment last without leaving the building and while visiting each apartment just once?

The first trick is to represent our problems in a more generalizable form. As most computer scientists and mathematicians know, this representation is called a graph. I have built the graph for the apartment below. Each vertex in the graph represents a room, while each edge represents a path the fairy can travel. The graph is split into three separate floors for easy visualization, but simply imagine that each vertex is connected to the nodes above and below them.

Graph G.

The graph for the checkerboard is practically identical—I'll leave its creation as an exercise for the reader. The second trick is that we can actually phrase both the checkerboard and the apartment as the same type of graph, a bipartite graph.

A bipartite graph is a graph in which each of the vertices is a member of one of two disjoint sets. Moreover, each vertex must not have any edges to members of the same set. The two problems both qualify as bipartite graphs because of their orthogonal lattice structure. Since the names of the disjoint sets are arbitrary, we may as well name them "red" and "black." To reflect this, I've gone ahead and colored the graph appropriately.

Graph G.

Now that we've set up the problems as bipartite graphs, let's see what we can glean from the analysis.

The first property that we would like to study is whether or not someone can draw a given path through the graph. By noticing that every edge traversal in a bipartite graph touches a vertex from an alternate set we can derive Lemma 1.