Problem Detail: 

I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all non-computable functions grow asymptotically larger than computable ones?

Edit:

Great answers below but I would like to explain in plainer english what I understand of them.

If there was a computable function f that grew faster than the busy beaver function, then this means that the busy beaver function is bounded by f. In other words, a turing machine would simply need to run for f(n) many steps to decide the halting problem. Since we know the halting problem is undecidable, our initial presupposition is wrong. Therefore, the busy beaver function grows faster than all computable functions.

Asked By : hollow7

Answered By : Carl Mummert

If you take any noncomputable set of natural numbers, the characteristic function of the set takes only the values $\{0,1\}$ and is noncomputable. So it is not the case that every noncomputable function grows very quickly, they can even be bounded.

The Busy Beaver function grows more quickly than every computable function because it is constructed to do so. The proof that it is noncomputable proceeds by first proving that it grows faster than any computable function.

More generally, say that a set $A \subseteq \mathbb{N}$ has "hyperimmune-free degree" if every function computable from $A$ is bounded by a computable function. Certainly every computable set has hyperimmune-free degree. It is known that there are also many noncomputable sets that have hyperimmune-free degree. So it is not the case that everything noncomputable will have to compute some fast-growing function.

However, it is also the case that an r.e. set that is noncomputable will not have hyperimmune-free degree. If $B$ is r.e., and enumerated by index $e$, the function $f$ such that $f(n) = k$ if $e$ enumerates $n$ in $k$ steps, and $f(n) = 0$ if $e$ does not enumerate $n$, is computable from $B$ but this function is bounded by a computable function if and only if $B$ is computable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2939

Problem Detail: 

Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?

Asked By : chibro2

Answered By : hengxin

Although 3SAT problem is NP-complete, there is a polynomial algorithm making use of the beautiful SCC (Strongly Connected Component) directed graph algorithm.

Suppose there are $n$ variables and $m$ clauses in the 2SAT instance $\mathcal{I}$. The parameters $n$ and $m$ represent the size of $\mathcal{I}$

The 2-SAT instance is modeled by a directed graph $\mathcal{G_I}$, with

• $2n$ vertices: for each variable $x$ in $\mathcal{I}$, there are two vertices $v_x$ and $v_{\bar{x}}$ (i.e., variable and its negation).
• $2m$ edges: for each clause $x \lor y$, there are two directed edges $\bar{x} \to y$ and $\bar{y} \to x$. Note that the latter two implicative forms are equivalent to $x \lor y$.

The polynomial algorithm (it is actually a linear algorithm) proceeds as follows:

1. Obtain the SCCs of $\mathcal{G_{I}}$ in linear time $O(n + m)$;
2. Assign True to each literal (Notice: not the variable) in the destination SCC (denoted $SCC_d$);
3. Delete $SCC_d$ and its corresponding source SCC ($SCC_s$). (Note the symmetry in the graph $\mathcal{G_{I}}$);
4. Repeat (2) and (3) until $\mathcal{G_{I}}$ is empty.

For example:

$\mathcal{I} = (x_1 \lor x_2) \land (\bar{x_2} \lor x_3) \land (\bar{x_1} \lor \bar{x_2}) \land (x_3 \lor x_4) \land (\bar{x_3} \lor x_5) \land (\bar{x_4} \lor \bar{x_5}) \land (\bar{x_3} \lor x_4)$

The graph $\mathcal{G_{I}}$ is:

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35425

Problem Detail: 

I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.

I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" [1] by Hans L. Bodlaender which return a tree-decompsiton with the optimized tree-width and as the name says, the algorithm runs in linear time but since there are no (translation: I have not found ) any implementations, I am not sure if it's being used in practice or not.

Is the paper by Hans L. used in practice or does the constant factor make the algorithm useless?

[1] http://dl.acm.org/citation.cfm?id=167161

[2] http://www.treewidth.com/docs/libtw.pdf

Edit: Linked http://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding

Asked By : Niclas Jonsson

Answered By : Luke Mathieson

The first caveat is that deciding whether the treewidth of a graph is at most $t$ is NP-complete, but it is FPT (which is what Bodlaender's paper shows). So for small $t$, we can (in principle) solve the problem exactly (and actually spit out the decomposition as well), but for graphs with large treewidth, then things can get a bit slow.

Having said that, you're right, the hidden constants in Bodlaender's algorithm are prohibitive, but there are more practical ways of getting at least a good tree decomposition. A useful place to start is with another of Bodlaender's papers, "A tourist guide to treewidth", which is now a bit old, but still has some valuable information and references to algorithms for generating tree decompositions, particularly in various restricted graph classes (sometimes the algorithms work in general, you just don't get a nice upper bound on the running time outside of the restricted class). John Fouhy's master's thesis "Computational experiments on graph width metrics" includes a number of way of obtaining tree decompositions (you can find it here under the link "John's thesis").

Probably most useful though is if you can get a copy of Downey and Fellow's new book "Fundamentals of Parameterized Complexity" (Springer, 2013), in which they devote Chapter 11 to heuristics for finding tree decompositions. This is probably the most recent survey in covering this material. They also note that the handful of attempts at implementing Bodlaender's algorithm have not been successful because it was impractically slow, so your lack of success in finding implementations is no coincidence. Bodlaender's algorithm works via recursive application of an FPT algorithm, the problem being that the recursion depth depends on the treewidth, (checking Downey & Fellows, the recursive depth is $O(t^8)$) which just becomes too prohibitively slow too quickly.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41651

Problem Detail: 

I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the following array which it said was a Max-Heap.

BookArray [] = {45,10,11,3,2,7,9,1,0} 

I then decided to shuffle the elements (so they are no longer in binary heap) and got this.

Shuffled[] = {11,1,0,7,9,3,2,10,45} 

I then decided to write a program that would sort the elements in the array in Min-Heap so I got this array

Sorted[] = {45,11,3,10,7,0,2,1,9} 

My question is if my sorted array is also a valid max-heap ? since my array does not match the bookArray

Asked By : Rajeshwar

Answered By : tanmoy

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree, the tree is completely filled on all levels except possibly the lowest.

Min Heap has the property:for every node i (except root node) Array[parent(i)]<=Array[i]. So the smallest element in a min-heap is at the root.

Max Heap is organized in opposite way, i,e. it has the property: for every node i (except root node) Array[parent(i)]>=Array[i]. So the largest element in a Max-heap is at the root.

You can check if the array is maintaining the heap property by the following algorithms.

Algorithm 1

Parent(i)         return floor(i/2)   

Algorithm 2

Left(i)       return 2*i 

Algorithm 3

Right(i)      return 2*i+1 

Now you can check on your own that if your array maintaining Max heap property or not.

It is not mandatory that two heaps with same elements have same arrangement.The thing you have to be conform that if all elements are maintaining the heap property or not.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22941

Problem Detail: 

The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

I don't completely comprehend why this is? is it because it is easier to traverse?

Asked By : cmehmen

Answered By : David Richerby

It doesn't make any sense at all to implement a heap as a linked list. Heaps are inherently binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at position K live at positions 2K and 2K+1. It's massively more efficient to find the Kth element of an array than the Kth element of a linked list.

Advantages of storing a heap as an array rather than a pointer-based binary tree include the following.

• Lower memory usage (no need to store three pointers for every element of the heap).
• Easier memory management (just one object allocated, rather than N).
• Better locality of reference (the items in the heap are relatively close together in memory rather than scattered wherever the allocator put them).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41719

Problem Detail: 

I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and sparse matrix storing methods. All methods are realized sequentially and in parallel using MPI.

I was very glad for creaters of PETSc. I downloaded it and installed. However, when I start reading user's guide I encountered following text:

PETSc should not be used to attempt to provide a "parallel linear solver" in an otherwise sequential code. Certainly all parts of a previously sequential code need not be parallelized but the matrix generation portion must be parallelized to expect any kind of reasonable performance. Do not expect to generate your matrix sequentially and then "use PETSc" to solve the linear system in parallel. 

I was surprised! Did PETSc developers really parallelize only matrix generating part? What is a benefit of using PETSc as parallel solver if linear system solving part runs sequentially?

Asked By : Nurlan

Answered By : Wandering Logic

You misread the text. The authors of PETSc are just telling you that you can't avoid Amdahl's law.

They have done their best to parallelize every aspect of the linear solver. But a real program is not just a call to a linear solver. First you generate a matrix and then you pass the matrix to the linear solver. If your matrix generator is slow, your whole program will be slow.

For example, suppose your original program spends 1000 seconds generating the matrix $A$ and vector $b$ and then you call a linear solver. Your old (sequential) linear solver took 1000 seconds to find $x$ such that $Ax = b$. Now you replace your old sequential linear solver with PETSc. Suppose the PETSc authors did such a good job that the PETSc parallel linear solver finds $x$ in just 1 second! Now how long does it take your program to run? 1001 seconds. You got less than 2x speedup! You need to do some work on your matrix generation code if you want to get a better speedup.

Pretty much the authors of PETSc are just telling you that a parallelized linear solver library is not a magic bean.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12670

Problem Detail: 

What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of 'insert'/'extract' (streams) vs. 'enqueue'/'dequeue' (queue). Are these interchangable? Do they suggest different concepts or patterns? If so, what are the differences?

---

Concrete example of 'stream insertion': http://www.cplusplus.com/reference/ostream/ostream/operator%3C%3C/

---

Potentially useful conceptual pieces?

• Stream as sequence of time-function data: http://mitpress.mit.edu/sicp/full-text/sicp/book/node69.html
• Stream as IO channel: http://en.wikipedia.org/wiki/Standard_streams

Asked By : elliot42

Answered By : Wandering Logic

A queue is an abstract data type with two operations: enqueue() and dequeue() (or sometimes push() and pop()) that have first-in-first-out semantics.

A C stream is hard (for me) to describe abstractly. My best cut at it is that it is an abstraction representing a buffered file (where "file" is understood in the Unix sense of the word as something that is usually (but not always) a sequence of bytes and a current file position.)

At it's most general a stream is like a sequence of bytes numbered from 0, that can be arbitrarily extended at the end, but that has some additional state (the current position). There are some basic operations (fread() and fwrite()) that read or write an arbitrary number of bytes starting at the current position, and then reset the current position to point just after the most recently read or written byte. The current position can also be changed with fseek() and queried with ftell().

Now here's where it gets "icky." At the time a stream is opened a variety of factors determine which of the above operations are enabled or disabled. If you open your stream only for read then calling fwrite() will cause an error. If you open your stream only for write then calling fread() will cause an error. If your stream is actually a pipe or a socket, or is opened in mode append then you are not allowed to fseek(). You are only allowed to read or write from the current file position. stdin, stdout, and stderr are pipes so you can't fseek() them. You can't fwrite() stdin and you can't fread() stdout or stderr.

C++ fixed most of that mess by giving us a hierarchy of types (for example: http://www.cplusplus.com/reference/istream/basic_iostream/), so that we can do error recovery with RAII and can also tell whether the file is readable or writable by looking at the type (although I don't know offhand whether they fixed the seeking mess.)

But then there's the whole other question of formatted output. C has fprintf() which formats some stuff and puts some bytes into a writable stream (starting at the current file position). C++ replaced fprintf() with the (IMHO) really-much-too-cute operator<<(). operator<<() has the advantage of being strongly typed, but the extreme disadvantage of requiring the use of manipulators. So operator<<() puts some bytes to the output stream starting at the current file position, but formatted based on a whole bunch of state that is mutated by manipulators. So a C++ stream actually has a bunch of extra state that you need to know about. (Whether integers are going to get formatted hex or decimal from now on, how much precision floats are printed with, etc.)

So: a queue inserts and removes individual items of a well defined type from its front or its back. A stream is random access extendable array of bytes where you can read and write arbitrary numbers of bytes from the current file position (except when it isn't random access and except when you either can't read or can't write).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12237

Problem Detail: 

I want to establish that this is part of my homework for a course I am currently taking. I am looking for some assistance in proceeding, NOT AN ANSWER.

This is the question in question:

A 5-pointed-star in an undirected graph is a 5-clique. Show that 5-POINTED-STAR $\in P$, where 5-POINTED-STAR = $\{ <G>$ $: G$ contains a 5-pointed-star as a subgraph $\}$.

Where a clique is CLIQUE = $\{(G, k) : G$ is an undirected graph $G$ with a $k$-clique $\}$.

Now my problem is that this appears to be solving the CLIQUE problem, determining whether a graph contains a clique with the additional constraint of having to determine that the CLIQUE forms a 5-pointed star. This seems to involve some geometric calculation based on knowledge of a 5-pointed star. However, in Michael Sipser's Theory of Computation, pg 268, there is a proof showing that CLIQUE is in $NP$ and on page 270 notes that,

We have presented examples of languages, such as HAMPATH and CLIQUE, that are members of NP but that are not known to be in $P$. [emphasis added]

If CLIQUE is not in $P$, why five pointed star be in $P$? Is there something I'm not seeing? Remember, this is a HOMEWORK PROBLEM and A DIRECT ANSWER WOULD NOT BE APPRECIATED. Thanks!

Asked By : BrotherJack

Answered By : Ran G.

If $G=(V,E)$ is a graph, how many subsets of $V$ of size $5$ exist?

If there is a 5-clique, one of this subsets is a clique.

Spoilers below:

There are ${|V| \choose 5}$ possible subsets to check, that is, at most $|V|^5$ options, which is polynomial in the input. This is NOT the case for an arbitrary $k$, since $|V|^k$ might be exponential in the input, and this is why $\text{CLIQUE} \notin P$ (unless P=NP, agghh.).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1143

Problem Detail: 

$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other vertex), or "false" if there aren't any. If there are more than one, return one of them.

The obvious and inefficient way would be to run BFS from every vertex, checking after every run of BFS if there are vertices with distance $= \infty$. If not - that vertex has paths to every other vertex. Complexity would be $O(|E||V| + |V|^{2})$.

I can't think of any substantial improvements. If someone could point me in the right direction (pun intended), that would be great!

Asked By : Cauthon

Answered By : Tom van der Zanden

You'll need to split the graph in to its strongly connected components, and then find a component from which you can reach every other component.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35803

Problem Detail: 

Calculate the FOLLOW sets for all the non terminals:

$S \rightarrow bEx \mid Db \mid b \mid F$

$D \rightarrow EDc \mid Y$

$E \rightarrow dED \mid dDY$

$Y \rightarrow ab \mid aDx \mid \varepsilon$

So I know that:

FOLLOW($S$) = $\{\$\}$ since it doesn't appear anywhere

FOLLOW($D$) = $\{b, a, x, c\}$, since it is followed by terminal $b$ in $S$, $c$ in $D$, FIRST($Y$) in $E$ which is $\{a\}$ ($\varepsilon$ not included), and $x$ in $Y$

FOLLOW($E$) = $\{x, c, a, d\}$, since it is followed by terminal $x$ in $S$, FIRST($D$) in $D$ which is $\{a, d, c\}$

but how do I calculate FOLLOW($Y$)? It isn't followed by anything. I'm guessing since it's at the end of $D$ and $E$ its the union of their follow sets including $\$$ since there's an $\varepsilon$?

Have been stuck on this for a while, any help is HIGHLY appreciated. Thanks in advance for any input

Asked By : eyes enberg

Answered By : Luke Mathieson

For posterity, the FOLLOW set of any non-terminal can be computed with the following rules (an example using these rules can be found here):

1. $\$$ (the end of input symbol) is in FOLLOW($S$) where $S$ is the start symbol.
2. If $A \rightarrow \alpha B\beta$, then everything in FIRST($\beta$) except $\varepsilon$ is in FOLLOW($B$).
3. If we have $A \rightarrow \alpha B\beta$ as before and $\varepsilon$ is in FIRST($\beta$), then all of FOLLOW($A$) is in FOLLOW($B$).
4. If $A \rightarrow \alpha B$, then all of FOLLOW($A$) is in FOLLOW($B$).

So for $Y$, we need to apply rule $4$ (as you correctly guessed), so FOLLOW($Y$) $=$ FOLLOW($D$) $\cup$ FOLLOW($E$) $= \{a,b,c,d,x\}$ (I'm trusting your working on the two follow sets).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35739