#theoretical cs

[satbiym]

The Beauty of Theoretical Computer Science/Pure Math

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.

Thank you for reading!

[longestpathsearch]

The roots of this work can be traced back to my CONCUR’09 conference submission that was rightly rejected. I subsequently published a few application-specific papers gradually improving my understanding of the algebra. The most comprehensive description can be found in ACM TECS (a preprint is available here). Here I’ll give a general introduction to the simplest version of the algebra of graphs and show how it can be implemented in Haskell.

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).

It’s quite nice and it does make me wonder if it’s possible to work over ‘languages’ of graphs. Thoughts?

[theturingpoint]

[commentout-blog]

On Bipartite Graphs

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.

>**Lemma 1**: Any path of *2n* length (number of vertices) will touch exactly *n* "red" vertices and *n* "black" vertices. Any path of length *2n+1* will touch *n+1* vertices of the set where the path starts and *n* vertices from the second set. Along the same lines, since we know that no two members of the same set can be adjacent vertices, we can derive some information about the start and end points of any path. >**Lemma 2**: Any path of length (number of vertices) *2n+1* will end on the same colored vertex as it started on. Any path of length *2n* will end on the opposite colored vertex. Note that since any graph cycle must start and end at the same vertex this leads to our first corollary for bipartite graphs. >**Corollary 1**: No cycles of odd length can exist in a bipartite graph. It also sets us up to solve some of the very problems we were dealing with. First we must introduce a new term: [Hamiltonian path](http://en.wikipedia.org/wiki/Hamiltonian_path). A Hamiltonian path is a path in a given graph which touches each and every vertex exactly once. Now that we have a bit more terminology, let's see if we can rephrase the homework problem to a bit more math-friendly form. >Given graph *G*, can one find a Hamiltonian path that starts at a corner vertex and ends at the middle vertex? Using Lemma 2 our answer is trivial: no. The total number of vertices in the graph is 3^3=27 (odd). Thus the Hamiltonian path will be 26 (even). Since the corner node is black and the center node is red, it is impossible for an even length Hamilonian path to exist. Hopefully this has given a little perspective on some of the elegant techniques in graph theory and also why it is so powerful. The models generated by graph theory are very generic and can thus be applied to many different problem domains, especially in computer science. One could easily write a depth-first search algorithm to test if a Hamiltonian path could exist, but rephrasing the problem first can save time and often yield unexpected results. I'll leave the reader with a simple exercise answerable from our lemmas—what can we say, if anything, about a bipartite graph with a Hamiltonian cycle?