tyb

Sire, there is no Royal Road to Wisdom

Posts tagged sample

0 notes &

On Realizing an Underlying Understanding of a Theory Often Contains Incorrect Impressions : Showing Halting Problem with a String-Rewrite Algorithm in the Spirit of Collatz Conjecture

I have a theory about the human mind. A brain is a lot like a computer. It will only take so many facts, and then it will go on overload and blow up.
- Erma Bombeck

From Michal Forisek’s answer to Can the Halting Problem be avoided by checking every possible input?

Emphasis Added.

*

People who learn about the halting problemoften get to the stage where they already 
(on an intuitive level) accept that it holds — given an arbitrary algorithm and an arbitrary input for that algorithm, we cannot decide whether the algorithm will terminate. 

However, people often get the incorrect impression
that the hardness of the problem lies in the infinity of possible inputs.
This seems quite plausible: who knows what the algorithm does for all of those nasty huge inputs, right?

Now,
armed with this “understanding”,
we move from theory to practice.
In practice, we usually have an upper bound on the size of the input to our program.
Suddenly, there are only finitely many possible inputs.
And this is where people tend to ask the question: “Cannot we circumvent the halting problem in this case? Isn’t it possible to check whether this algorithm terminates for each of these finitely many inputs?” (And also: “Even though it can be impractically slow, cannot we, in theory, verify the correctness of a program simply by checking that it works for all allowed inputs?”)

Now, in order to understand why we cannot do that, you need to understand where the true hardness of the halting problem lies. It has nothing to do with the size of input. In particular:
Deciding whether a program that takes no input terminates is as hard as solving the halting problem in general — that is, as answering the general question “does program P terminate on input I?”.

This is actually a very easy reduction.
If you knew how to solve the “simpler” version for programs that take no input, you could solve the “general” version as follows:
take the program P, and modify it to obtain a program Q that never reads the input.
Instead, you hard-wire the input I into Q, and whenever P would read input, Q just reads the next part of the hard-wired input I. Obviously, deciding whether Q terminates (without any input) = deciding whether P terminates on input I.

Here’s another example that very nicely illustrates where the real difficulty of deciding the halting problem lies. It’s not the size of the input. It’s the potential infiniteness of memory used during the computation, and the fact that already very simple rules can create very complex program behavior.

*

Consider the following simple string-rewriting algorithm:

rules = { ‘a’:’bc’, ‘b’:’a’, ‘c’:’aaa’ }
n = int(input())
S = ‘a’*n # a string of n ‘a’s
while len(S) > 1: S = S[2:] + rules[S[0]]

*

It doesn’t get much simpler than this: in each step, remove two letters from the beginning, and append a few new letters at the end. Here’s what the program does for n=10 if we print S after each iteration of the while-cycle:


aaaaaaaabc
aaaaaabcbc
aaaabcbcbc
aabcbcbcbc
bcbcbcbcbc
bcbcbcbca
bcbcbcaa
bcbcaaa
bcaaaa
aaaaa
aaabc
abcbc
cbcbc
cbcaaa
caaaaaa
aaaaaaaa
aaaaaabc
aaaabcbc
aabcbcbc
bcbcbcbc
bcbcbca
bcbcaa
bcaaa
aaaa
aabc
bcbc
bca
aa
bc
a

and it terminates. It also terminates for n=47 — but the process takes 40492 steps, and the longest S during the computation has 242 characters.

Now comes the question: does this particular algorithm terminate for every possible positive integer n? The answer is: we don’t know yet. Read that again. A program with four simple lines of code. A program that just repeats a single deterministic step. What do you mean, “we don’t know yet”? Well, we don’t. The question whether this particular tiny program always terminates is equivalent to the Collatz conjecture — which is a famous open problem in mathematics.

Filed under algorithms automata sample learning important computer science person

0 notes &

Adding syntax highlighting into Tumblr

  1. https://code.google.com/p/google-code-prettify/wiki/GettingStarted
  2. http://alexgorbatchev.com/SyntaxHighlighter/manual/demo/
  3. http://snippets-of-code.tumblr.com/post/6027484416/adding-syntax-highlighting-into-tumblr
  4. http://google-code-prettify.googlecode.com/svn/trunk/README.html
  5. http://stackoverflow.com/questions/8399547/how-to-add-line-numbers-to-all-lines-in-google-prettify

%include "os_dependent_stuff.asm" ; Initialize constants. mov r12, 65537 ; Exponent to modular-exponentiate with mov rbx, 235 ; Modulus to modular-exponentiate with mov r15, NPROCS ; Number of worker processes to fork. mov r14, (SIZE+1)*8 ; Size of shared memory; reserving first ; 64 bits for bookkeeping

Filed under implementation javascript syntax-highlighting parser github sample people

0 notes &

What is a practical application of being able to tell whether a graph is bipartite?

So what is the use of being able to mathematically determine if a huge graph is bipartite or not?

*

"Bipartite" is the same thing as "2-colorable". Finding that your graph is bipartite is the same as finding that its vertices can be colored red and blue, with edges connecting only vertices of different colors. 

Therefore, if the vertices represent some objects you are interested in, and the edges represent certain constraints that can be viewed as “being incompatible”, finding that the graph has low chromatic number can be seen as an efficient way of allocating the objects into a small number of internally-compatible classes. If the graph is bipartite, this is as good as you could have hoped for - two classes suffice. 

A standard concrete example is the assignment of teachers to classes: suppose you need people to teach various introductory calculus courses, the timetables have already been drawn, and various courses overlap so they cannot be taught by the same person. You’re trying to determine how many profs would be needed to cover calculus. You draw the graph (vertices = classes, edges = overlaps), and if it’s bipartite, woohoo, you can make do with just two teachers. If the graph is 3-colorable, you’ll need three, and so on. 

So, whenever you see an application of graph coloring (and, really, there are tons of these), “bipartite” is just the special case “two colors suffice”. It’s sort of a special special case, since determining 2-colorability is algorithmically way easier than determining 3-colorability or 4-colorability and so on, but that is a different story.

*

It helps adapting algorithms dealing with graphs and matrices to run in parallel.

When solving large linear systems on parallel processors, you can represent the matrix by a graph. If the graph is bipartite (two-colorable), then some of the well-known algorithms (Successive over-relaxation or SOR) are easily adaptable to run in parallel threads — vertices of each color form an independent set and can be processed in parallel. Look for “red-black SOR”, which is particularly effective on a grid (when solving linear systems arising from partial differential equations in mathematical physics). The amount of parallelism is determined by the size of the smaller set.

image

From: http://www.quora.com/Graph-Theory/What-is-a-practical-application-of-being-able-to-tell-whether-a-graph-is-bipartite?share=1

The bipartite graph structure can be used to capture a relationship between two types of objects where the distinction between the types of objects is important.

A student-applied-to-college relationship can (for example) be stored in the bipartite graph depicted above. Blue dots could be students (e.g. Mary, Jane, Joe) and Red dots could be colleges they applied to (e.g. Princeton, Cornell, MIT)

*

Bipartite  graphsare a specific kind of graphs  nodes can be decomposed into two disjoints sets such that two nodes in a same set are not connected, therefore those graphs are usually written B=(L,R,E), where L,R (left/right) are the disjoint sets of nodes and E the edges. In this context, a complete bipartite graph is a bipartite graph where every node in one set are connected to every node in the other set

*

But an easy way to understand and reason about bipartite graphs is to think of two groups of people being paired in some activity. For example, boys and girls dating. Assuming only heterosexual couples, even without monogamy, you get a bipartite graph where the vertices are people, edges represent relationships between them, and the two sets are the set of boys and the set of girls.

*

E.g.  tree is always bipartite (it doesn’t contain cycles and esp’ not odd length cycles), 
In order to split some tree’s vertices into two sets you can run the BFS algorithm and mark all the vertices that you found on any odd step as V1 and all the other vertices as V2

*

The descriptions above outline the properties, but not the utility or reason you should care.

What is it? I think of it as a search criteria over graph data, where I am looking for a very useful special case. I am looking for a data structure called an Adjacency Matrix, aka: a 2-mode matrix.  

A two mode matrix maps together instances of entities of two types. That means for example your row headers are schools, and your column headers are students. In databases these are resolver tables that enable many-to-many relations. Prathyush Kashyap’s answer illustrates this nicely.

*

Bipartite Graphs are those which have two sets of vertices which are mutually disjoint . The Relation or edges in these graphs exists only between two vertices which are not from the same set of vertices. 

Famous example :
Assigning n jobs to m persons can be modelled using  a Bipartite Graph..
The edge exists if a job i can be allotted to a person p.

Obviously this requires a Bipartite model of graph, Since an edge here can not exist between a job to another job or a person to another person.

Interesting: http://friggeri.net/blog/a-genetic-approach-to-css-compression/
*

Outside of modelling problems as matchings in a bipartite graph which is very common, I would say the best known everyday use of bipartite graphs is the stable marriage problem (http://en.wikipedia.org/wiki/Sta…).

Think of two groups - guys and girls where each guy has an ordered list of all girls and vice versa. The Gale-Shapely algorithm always outputs a stable matching - one in which there never exist two couples such that they would be happier if they swapped partners. I think its really well described in the following slides:

http://www.cs.cmu.edu/afs/cs.cmu…

But for a more standard reference, the Wikipedia page is here:
en.wikipedia.org/wiki/Stable_marriage_problem

From http://www.quora.com/Bipartite-Graphs/What-is-a-bipartite-graph

Filed under quora how to ask question term important graph theory sample