# Question
Title: Examples of processes / problems that cannot be tackled by Turing Machines
I know that there are problems that cannot be solved by any algorithm, such as the Halting problem. I also know that some processes cannot be even adequately approximated by any Turing Machine (equivalently, any digital computer), meaning that some property of the process cannot be simulated due to its intrinsic nature. An example of this would be Chaos, and its non-periodicity.

My question is: are there any other interesting processes in nature that really are outside the realm of what Turing Machines / digital computers can tackle? Any other interesting problems (outside from the well-known textbook ones) that Turing Machines cannot solve?

The reason why I ask for this is that I'm teaching to computer science students, and I want to make sure they understand that computers are not all-powerful machines, but there are problems and phenomena that lie *fundamentally* outside the realm of possibilities of any digital computer. What powerful examples could I use, other than Chaos and the Halting problem, to support my argument?

Thank you!

# Answer
> 3 votes
I'll address as answer only part of the question (see my comments for why not all of it). The interesting phylosophical part of the question is basically asking if the Church-Turing thesis (CTT) describes all that happens in the universe. This is much more a physics question than it really is a CS question. CTT has been extended to the Church–Turing–Deutsch principle to account for quatum computers; it basically states that a quantum computer can simulate any physical process in the universe.

So what about continuous processes that we normally model over $\mathbb{R}$? Well, there are two aspects of this:

* Models of computation with infinite-precision real-numbers have been devised. Whether you think such a model is the "right" one for physical processes, depends on physics and...
* There are tough issues like the Bekenstein bound, which limit the amount of information that can exist in a finite region of space as we currently understand it. For details on this latter issue, it's much better to ask on our physics sister site.

A bit more info with pointer to additional readings is found at https://mathoverflow.net/questions/54820/physics-and-church-turing-thesis

# Answer
> -1 votes
it is known some problems in theoretical physics are undecidable. have not found a nice simple list/ survey. see eg these two refs.

---
Tags: turing-machines, church-turing-thesis
---


# Question
Title: What is the meaning of undecidability in Rice Theorem?
Rice theorem says **every non-trivial property of languages of Turing machines is undecidable**. what is the meaning of undecidability here? is it semi-decidable?

As an example the following language is R.E but it contains a non-trivial property

$A = \\{x | \phi\_x$ is defined for at least one input$ \\}$

this language equals to $Empty$ $Complement$ and it is clearly r.e.(m-complete in fact) while non-emptiness property is non-trivial.

# Answer
> 7 votes
Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many problems but, since each decidable or semi-decidable problem corresponds to a Turing machine, there are only countably many decidable and semi-decidable problems.

---
Tags: terminology, computability, undecidability, semi-decidability, rice-theorem
---


title: Rubik Cube Algorithm for general n

text:
# Question
Title: Rubik Cube Algorithm for general n
I am not sure if this is the right place , but:

Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots \times n$ ($d$ times) rubic cube , is there an algorithm that works effiecently for this case?(of course now it depends also on $d$ and not just on $n$)

I haven't found anything online/on wikipedia and I was just wondering.

# Answer
Algorithms for Solving Rubik's Cubes by Demaine et al. shows that an $n\times n\times n$ Rubik's Cube can be solved in $O(\frac{n}{\log n})$ moves and this is (asymptotically) optimal.

I am not certain on the complexity of actually computing such a solution but I suspect that (by closely following the steps in the proof) it can be done in polynomial time (probably $O(n^2)$ or $O(n^2\log n)$).

There likely isn't anything out there on higher-dimensional cubes. If there was, they would certainly have cited the Demaine paper. There is a trivial way to solve a $n\times n\times n$, since there exist move sequences that solve an individual cubie in $O(1)$ time. Therefore, if such sequences also exist for higher-dimensional cubes, they could be solved in $O(n^{d-1})$ steps since that is how many cubies are on the surface. And perhaps by extending Demaine's technique you could get that down to $O(\frac{n^{d-1}}{\log n})$ by solving multiple ($O(\log n)$) cubies in one go.

You might be able to find more information here: http://www.superliminal.com/cube/solution/solution.htm
> 6 votes

---
Tags: algorithms, board-games
---


# Question
Title: Generate algorithmically all grid points inside a hypercube
$\def\R{\mathbb{R}}\def\Z{\mathbb{Z}}\def\n#1{\\|#1\\|\_\infty}$The problem comes directly from computational mathematics, and can be stated as follows:

Given a regular matrix $M\in\R^{d\times d}$, find effectively all vectors $v\in\Z^d$ such that $\n{Mv}\leq1$, where $\n{Mv}$ is the maximal component of the vector in modulus.

I give an algorithm below, but it's very inefficient, since it has much more steps than the number of grid points. It is still bearable for $d=5$ in my case, but it fails completely for $d=6$, I don't have that much time; moreover, I'd like to make some work on higher dimensions as well.

---

My current algorithm is based on the following (disclaimer: contains more math): First, compute $\n{M^{-1}}$. Then, we observe that $\n{v}\leq\n{M^{-1}}\n{Mv}\leq\n{M^{-1}}$. This means that we can compute $L=\operatorname{floor} \n{M^{-1}}$ and then try all vectors $v\in\lbrace-L,-L+1,\dots,L-1,L\\}^d$; there is exactly $(2L+1)^d$ of them. (And here lies the problem: if $d=6$ and $L=18$, I get $2.5{\rm\small E}9$ iterations, which is orders of magnitude larger than the number of points I think there are.)

# Answer
> 3 votes
Here's another way of looking at the problem: You have a lattice generated by the columns of $M$. Use the Lenstra–Lenstra–Lovász (LLL) algorithm to obtain a reduced basis of this lattice. If you replace $M$ by a new matrix formed by the output of LLL, then the columns of $M$ will still generate the same lattice, but the basis vectors will be closer to being orthogonal to one another, and the entries of $M^{-1}$ should have smaller magnitude.

From there, it would also help to bound each component of $v$ separately: i.e., you can bound the $i$th component $|v\_i|$ by $\sum\_{j=1}^d |(M^{-1})\_{ij}|$. (By the way, the bound $\\|v\\|\_\infty \leq \\|M^{-1}\\|$ is not correct; we need to use the sum of the elements on each row, not the maximum.)

For values of $d$ up to about 30, the LLL algorithm will finish practically instantly. Asymptotically, it takes $O(d^6)$, so it will slow down for very large $d$, but at the same time the number of points we need to check grows exponentially in $d$, so the run-time of the LLL is not really the bottleneck. On the other hand, the savings in the number of points needing to be checked can be enormous. I wrote some GAP code to generate a random regular (stochastic) matrix $M$ and compare the bounds on the components of $v$ that we obtain using the original basis, compared to the LLL-reduced basis (By the way, we do not need to assume that the matrix is regular; I made this restriction only because this was the case in your application):

```
d:=8;
M:=IdentityMat(d);
for i in [1..d] do
  for j in [1..d] do
    M[i][j]:=Random([-10^8..10^8]);
  od;
  M[i]:=M[i]/Sum(M[i]);
od;
L:=LLLReducedBasis(M).basis;
MM:=M^-1*1.0;
LL:=L^-1*1.0;
for i in [1..d] do
  for j in [1..d] do
    MM[i][j] := MM[i][j]*SignFloat(MM[i][j]);
    LL[i][j] := LL[i][j]*SignFloat(LL[i][j]);
  od;
od;

Print("Bounds for original basis: ");
ones:=[1..d]*0+1;
v:=MM*ones;
for i in [1..d] do
  v[i]:=Int(Floor(v[i]));
  Print(v[i]);
  Print(" ");
od;
Print("\n(");
Print(Product(v*2+1));
Print(" points to check)\n");

Print("Bounds for LLL basis: ");
v:=LL*ones;
for i in [1..d] do
  v[i]:=Int(Floor(v[i]));
  Print(v[i]);
  Print(" ");
od;
Print("\n(");
Print(Product(v*2+1));
Print(" points to check)\n");

```

The following output (based on the default random seed, with $d=8$) is not atypical:

```
Bounds for original basis: 9 23 24 4 23 16 23 4
(258370076349 points to check)
Bounds for LLL basis: 3 3 2 2 3 4 2 3
(2701125 points to check)

```

**Edit**: This problem is a special case of the general problem of enumerating lattice points in convex polytopes, which it turns out is a well-studied problem, and there are more efficient algorithms than the one described above. See this this paper for a survey.

---
Tags: algorithms, linear-algebra, enumeration
---


# Question
Title: Did 'Eugene Goostman' really pass the Turing test?
It is being said that 'Eugene Goostman', a computer programme developed to simulate a 13-year-old boy, managed to convince 33 per cent of the judges that it was human, and thus passed the Turing Test.

The computer programme, aka a chatbot, was pretending to be a 13-year-old Ukranian boy for whom English was a second language – something very different indeed.

For me, Eugene sounds exactly like a mediocre chatbot should: repetitive, nonsensical, and littered with non-sequiturs. I don't know how it convinced the judges (which seem unprofessional).

Many people have criticized Eugene like Prof Stevan Harnad who said "It's nonsense" and "We have not passed the Turing test. We are not even close."

Opinions differ, but I would really like to know if it officially passed the test?

It is also being said that:

> Two one-time-only prizes that have never been awarded. 25K is offered for the first chatterbot that judges cannot distinguish from a real human and which can convince judges that the human is the computer program. $100,000 is the reward for the first chatterbot that judges cannot distinguish from a real human in a Turing test that includes deciphering and understanding text, visual, and auditory input. Once this is achieved, the annual competition will end.

Does it mean Eugene won $25,000?

# Answer
There is no "official Turing test" so there's no concept of "officially pass\[ing\] the test". Turing described a methodology that one might use to evaluate artificial intelligences. The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that sense, it passed the test.

Since there is no "official Turing test", it might be more appropriate to say that Eugene Goostman passed **a** Turing test or even passed a Turing-style test. It's unlikely that the media would pick up on such subtleties, especially given Turing's fame and the idea of "**the** Turing test" in the public conscience.
> 18 votes

# Answer
I think the prizes you're referring to are the Loebner Prize. According to the Wikipedia page (see prior link), the winner for 2014 is 'Rose' by Bruce Wilcox. That program did not win one of the one-time-only prizes, but did get $4,000 in prize money. 'Eugene Goostman' competed in 2005 and 2008, finishing second both times.

The competition 'Eugene Goostman' won was organized by Kevin Warwick of Coventry University to mark 60 years since Alan Turing's passing. I'm unaware of any prize money.

Check out Ray Kurzweil's take on both the competition and the program in question. Excerpt:

> Professor Warwick claims that the test was “unrestricted.” However, having the chatbot claim to be a 13-year-old child, and one for whom English is not a first language, is effectively a restriction. Moreover, the interactions were reportedly limited to five minutes each. There is a high likelihood of fooling naïve judges in such a brief period of time.
>
> I chatted with the chatbot Eugene Goostman, and was not impressed. Eugene does not keep track of the conversation, repeats himself word for word, and often responds with typical chatbot non sequiturs.

I also found this to be a nice commentary: WIRED--That Computer Actually Got an F on the Turing Test
> 9 votes

# Answer
Adding a Wikipedia link for more depth on the "original" Turing Test.There are many tests called "Turing test". Wikipedia mentions "at least 3 primary versions". The test passed by Eugeene is none of those 3. The test passed by Eugeene was not devised by Alan Turing, but it was a test called Turing test, inspired by Alan Turing, and Eugeene did pass it.

The part mentioning at least 3 primary versions of the Turing test:

> Saul Traiger argues that there are at least three primary versions of the Turing test, two of which are offered in "Computing Machinery and Intelligence" and one that he describes as the "Standard Interpretation." While there is some debate regarding whether the "Standard Interpretation" is that described by Turing or, instead, based on a misreading of his paper, these three versions are not regarded as equivalent, and their strengths and weaknesses are distinct.

Version 1

> Turing's original game described a simple party game involving three players. Player A is a man, player B is a woman and player C (who plays the role of the interrogator) is of either sex. In the Imitation Game, player C is unable to see either player A or player B, and can communicate with them only through written notes. By asking questions of player A and player B, player C tries to determine which of the two is the man and which is the woman. Player A's role is to trick the interrogator into making the wrong decision, while player B attempts to assist the interrogator in making the right one.

Version 2

> The second version appeared later in Turing's 1950 paper. Similar to the Original Imitation Game Test, the role of player A is performed by a computer. However, the role of player B is performed by a man rather than a woman. \[...\] In this version, both player A (the computer) and player B are trying to trick the interrogator into making an incorrect decision.

Version 3

> Common understanding has it that the purpose of the Turing Test is not specifically to determine whether a computer is able to fool an interrogator into believing that it is a human, but rather whether a computer could imitate a human. While there is some dispute whether this interpretation was intended by Turing – Sterrett believes that it was and thus conflates the second version with this one, while others, such as Traiger, do not – this has nevertheless led to what can be viewed as the "standard interpretation." In this version, player A is a computer and player B a person of either sex. The role of the interrogator is not to determine which is male and which is female, but which is a computer and which is a human. The fundamental issue with the standard interpretation is that the interrogator cannot differentiate which responder is human, and which is machine. There are issues about duration, but the standard interpretation generally considers this limitation as something that should be reasonable.

In contrast, the test passed by Eugeene had human judges chatting with a chatbot for 5 minutes, after which they had to decide if it was a bot or not.
> 2 votes

# Answer
Yes, it won "a" Turing Test which followed Alan Turing's original description as closely as possible.
This was not however the $25000 prize money version that is the Loebner Prize, whose specifications differ from Alan Turing's description.
More importantly, Alan Turing never meant this to be a genuine test in the first place, so the outcome is not proof of intelligence, if that's what you actually wanted to know.
> 0 votes

---
Tags: reference-request, artificial-intelligence, history, turing-test
---


# Question
Title: Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?
I know that for positive monotonically non-decreasing functions, f(n) and g(n),

```
f(n) = O(g(n) + c) entails
f (n) = O(g(n))

```

Why is this always true only for positive monotonically non-decreasing functions? $\Theta$

If there exists one, give a counter-example that shows that the above Big O rule is not necessarily true for functions that are *not* monotonically non-decreasing.

I'm really confused why the rule specifies only positive, monotonic, non-decreasing functions. Thanks for your help!

# Answer
Let $f(n) = 1-1/n$ and $g(n) = 1/n$, so we've violated the condition that $g$ is non-decreasing. However, it's not hard to show that $f(n) \in O(g(n)+2)$ but we also have $f(n)\notin O(g(n)$, invalidating the inference.
> 2 votes

# Answer
More generally, if $f(n) = O(g(n)+h(n))$ and $g(n) = \Omega(h(n))$ then $f(n) = O(g(n))$. If, on the contrary, $g(n) = o(h(n))$, then $f(n) = O(h(n))$. (It could also be that neither conditions hold.)
> 0 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Finding the two largest of five small integers as quickly as possible
I use a variation of a 5-cross median filter on image data on a small embedded system, i.e.

```
    x
  x x x
    x

```

The algorithm is really simple: read 5 unsigned integer values, get the highest 2, do some calculations on those and write back the unsigned integer result.

What is nice is that the 5 integer input values are all in the range of 0-20. The calculated integer value are also in the 0-20 range!

Through profiling, I have figured out that getting the largest two numbers is the bottleneck so I want to speed this part up. What is the fastest way to perform this selection?

The current algorithm uses a 32 bit mask with 1 in the position given by the 5 numbers and a HW-supported CLZ function.
I should say that the CPU is a proprietary one, not available outside of my company. My compiler is GCC but tailor made for this CPU.

I have tried to figure out if I can use a lookup-table but I have failed to generate a key that I can use.

I have $21^5$ combinations for the input but order isn't important, i.e. `[5,0,0,0,5]` is the same as `[5,5,0,0,0]`.

It happens that the hash-function below produces a perfect hash without collisions!

```
def hash(x):
    h = 0
    for i in x:
        h = 33*h+i
    return h

```

But the hash is huge and there is simply not enough memory to use that.

Is there a better algorithm that I can use? Is it possible to solve my problem using a lookup-table and generating a key?

# Answer
In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers. Lucky for us, *selection* networks have also been studied. Knuth tells us that finding the two smallest numbers out of five² can be done with $\hat{U}\_2(5) = 6$ comparisons \[1, 5.3.4 ex 19\] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle \[0:4\]\\,\[1:4\]\\,\[0:3\]\\,\[1:3\]\\,\[0:2\]\\,\[1:2\]$

which implements -- after adjusting the direction of the comparisons -- in pseudocode as

```
def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

```

Now, naive implementations still have conditional jumps (across the swap code). Depending on your machine you can cirumvent them with conditional instructions, though. x86 seems to be its usual mudpit self; ARM looks more promising since apparently most operations are conditional in themselves. If I understand the instructions correctly, the first swap translates to this, assuming our array values have been loaded to registers `R0` through `R4`:

```
CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

```

Yes, yes, of course you can use XOR swapping with EOR.

I just hope your processor has this, or something similar. Of course, if you *build* the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e. without making use of the limited domain and performing wicked intra-word magicks.

---

1. Sorting and Searching by Donald E. Knuth; *The Art of Computer Programming* Vol. 3 (2nd ed, 1998)
2. Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}\_2(5) = 7$ many in total \[1, p234 Table 1\].
> 11 votes

# Answer
Just so that it's on the table, here's a direct algorithm:

```
// Sort x1, x2
if x1 < x2
  M1 = x2
  m1 = x1
else
  M1 = x1
  m1 = x2
end

// Sort x3, x4
if x3 < x4
  M2 = x4
  m2 = x3
else
  M2 = x3
  m2 = x4
end

// Pick largest two
if M1 > M2
  M3 = M1
  if m1 > M2
    m3 = m1
  else
    m3 = M2
  end
else
  M3 = M2
  if m2 > M1
    m3 = m2
  else
    m3 = M1
  end
end

// Insert x4
if x4 > M3
  m3 = M3
  M3 = x4
else if x4 > m3
  m3 = x4
end

```

By clever implementation of `if ... else`, one can get rid of some unconditional jumps a direct translation would have.

This is ugly but takes only

* five or six comparisons (i.e. conditional jumps),
* nine to ten assignments (with 11 variables, all in registers) and
* no additional memory access.

In fact, six comparisons is optimal for this problem as Theorem S in section 5.3.3 of \[1\] shows; here we need $W\_2(5)$.

This can not be expected to be fast on machines with pipelining, though; given they high percentage of conditional jumps, most time would probably be spent in stall.

Note that a simpler variant -- sort `x1` and `x2`, then insert the other values subsequently -- takes four to seven comparisons and only five to six assignments. Since I expect jumps to be of higher cost here, I stuck with this one.

---

1. Sorting and Searching by Donald E. Knuth; *The Art of Computer Programming* Vol. 3 (2nd ed, 1998)
> 4 votes

# Answer
This could be a great application and test case for the Souper project. Souper is a superoptimizer -- a tool that takes a short sequence of code as input, and tries to optimize it as much as possible (tries to find an equivalent sequence of code that will be faster).

Souper is open source. You might try running Souper on your code snippet to see if it can do any better.

See also John Regehr's contest on writing fast code to sort 16 4-bit values; it's possible that some of the techniques there might be useful.
> 4 votes

# Answer
You can use a $21^3$ table that gets three integers and outputs the largest two. You can then use three table lookups:

`T[T[T[441*a+21*b+c]*21+d]*21+e]`

Similarly, using a $21^4$ table, you can reduce it to two table lookups, though it's not clear that this would be faster.

If you really want a small table, you can use two $21^2$ tables to "sort" two numbers, and then use a sorting network. According to Wikipedia, this requires at most 18 table lookups (9 comparators); you might be able to do with less since (1) you only want to know the two largest elements, and (2) for some comparator gates, you might only be interested in the maximum.

You can also use a single $21^2$ table. Implementing a sorting network then uses less memory accesses but more arithmetic. This way you get at most 9 table lookups.
> 3 votes

---
Tags: algorithms, efficiency, selection-problem
---


# Question
Title: How are hash table's values stored physically in memory?
## Question:

How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often?

## My current understanding (could be wrong):

Let's say I have 3 objects stored in a hash table. Their hash functions generate these values:

* 0
* 10
* 20

I would presume that the pointers of these objects would not be stored at the following memory addresses because there would be huge gaps between them:

* startOfHashTable + 0
* startOfHashTable + 10
* startOfHashTable + 20

The Wikipedia article on hash tables says that the "index" is computed as such:

```
hash = hashfunc(key)
index = hash % array_size

```

So in my example, the indices would be:

* 0 % 3 = 0
* 10 % 3 = 1
* 20 % 3 = 2

This gets rid of the huge gaps that I mentioned before. Even with this modulo scheme, there's problems when you add more objects to the hash table. If I add a fourth object to the hash table, I would need to apply % 4 to get the index. Wouldn't that invalidate all the % 3's that I did in the past? Would all those previous % 3's need to be relocated to the % 4 locations?

# Answer
> 16 votes
The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table. So, in your example, if you were storing the items in an array of size 6, the three items with hash values 0, 10 and 20 would be stored at locations 0, 4 and 2, respectively. If you added a fourth element with hash value, say, 31, that would be stored at location 1, without needing to move any of the first three items. If your hash table was becoming full and you wanted to move it into a bigger array, *then* you would need to recalculate the locations of all the items in the table and move them appropriately.

# Answer
> 9 votes
Hash-table usually do waste space. Many algorithms do, since time-space trade-offs are common, but they usually hide it better **:)**. Like other algorithms, hash-tables do it to get better time performance.

The first point is that you try to avoid collisions in your hash-table, because that keeps the access time cost constant (but collisions are usually allowed and can be dealt with, thus allowing several items to be in the same entry, at time cost). The second point is that you try to avoid large unused gaps because that costs memory. The third point is that you avoid changing your hashing function (hence also the table size) because it requires reorganizing the whole table, which has a large time cost.

Unfortunately, the less gaps you have, the more likely a new hash entry will cause a collision. A good hash function, for a given data set, will limit the likelyhood of collision even with better use of available index space.

Actually, you should consider that there are two kinds of hash tables: static ones and dynamic ones.

For static ones, the data to be hashed does not change, so you can try to find a hash function with no collision at all for that data set. That is called a perfect hash. But the best is a minimal perfect hash, which achieves the result without gaps.

But that is not feasible when the data to be hashed changes dynamically, within a large set of possibilities. Then you cannot avoid collisions, but you try to limit them by having enough gaps.

There are a variety of techniques to manage that differently, adapting the table size to the number of values being hashed, growing the table when there are many collisions, or reducing it when there are too large gaps. But this has to be handled very carefully, using exponential table variations, so as to limit the impact of table reorganization on the overall cost of using the hash-table.

This is intended as an intuitive introduction. For more technical details, and references, you may look at answers to this question: (When) is hash table lookup O(1)?. Hash-tables and hashing is an important topic, with many variations.

# Answer
> 3 votes
A good way to look at hash tables is like a lookup table with infinite index range (well, not really infinite, you're still constrained by the value limit of the key you're using).

Lets say you're trying to store some specific values of sqrt(x) in a lookup table where X is an integer, it would go something like this:

```
[1] = 1
[3] = 1.732
[10000] = 100

```

This makes for very cheap square rooting since instead of the expencive calculation, you can simply fetch the value from the array. It is however, very inefficient use of memory because \[2\] and \[4 - 9999\] are empty.

To the rescue comes the hash function, the purpose of a hash function in this context is to transform the index into something that actually fits in a reasonably sized array so, for example it could do this:

```
(1) = [5] = 1
(3) = [2] = 1.732
(10000) = [3] = 100

```

now all 3 values fit in an array the size of 6.

How does the hash function achieve this? The most basic hash function is (Index % ArraySize), the modulo operator divides the Index you chose by the size of the array and gives you the remainder which is always smaller than the array size.

But what if multiple indexes hash to the same result? This is called a hash collision and there are different ways of dealing with it. The simplest of which is storing each value along with its original Index in the array, if that array slot is taken, go forward by 1 until an empty slot is found. When retrieving the value, go to the location given by hash function and loop through the elements until the one with suitable original index is found.

This is why a good hash function is also great at dispersing the data so that whether the indexes coming in are sequential or random, the hash result should be as widely dispersed as possible to keep the cost of accessing data relatively constant.

Of course the bigger the underlying array, the less collisions you're going to get so its a tradeoff between speed and size efficiency. Modern hash tables usually fill up to ~70% while having less than 10 collisions per access. Along with the hash function, this means each data fetch costs ~20 cycles which is (for some purposes) a good compromise between speed(lookup table) and efficiency(list).

---
Tags: data-structures, hash-tables, memory-allocation
---


# Question
Title: How do I show that a DFA accepts only one word?
I want to show that

$\qquad\displaystyle O = \\{M : M \text{ is a DFA}, |L(M)| = 1\\}$.

Here $|L(M)|=1$ means the DFA contains only one state. I really don't know where to get started in this problem.

Should I do something like this?

```
M = On input (M',w) where M' is a DFA and w is a string:

 - If M' accept only one member, accept.
 - If more than one or less than one accepted, reject.

```

But this will loop the program forever for the first step as it keeps testing every member after one member is selected. First step just doesn't seem right.

I think these questions might be relating to this: ,

# Answer
> 2 votes
The approach you have given is normally used for demonstrating a language is undecidable (by using the language to decided an known undecidable language).

What you need to do is (implicitly or explicitly) construct an algorithm that decides the problem.

As I mentioned in a comment, your notation is unclear, but both possible interpretations are decidable anyway.

1. If you actually mean the property to be decided is that the language of $M$ contains one string (which is what $|L(M)|=1$ would normally mean), then you need to give an algorithm that decides whether there is exactly one, loopless path from the start state to a final state or not.
2. If the property is that $M$ has only one state (normally written something like $|Q| = 1$ where $Q$ is the set of states of $M$), then you need to give an algorithm that decides whether the DFA has one state or not.

Given that (2) is essentially trivial, I assume that (1) is the actual question you've been asked, so you need to think of how, given, for example, a state diagram sitting in front of you, you would work out that there's exactly one path from the start state to exactly one of the final states, that's essentially all an algorithm really is.

# Answer
> 3 votes
## The case of 1-state DFA

*Accepting one word is unrelated to having one state.*

If there is only one state, it is necessarily starting and accepting state, unless there is no accepting state which make the language empty.

An automaton that has only one state which is accepting is necessarily accepting a language equal to $\Sigma\_1^\*$ for some subset $\Sigma\_1$ of the input alphabet $\Sigma$.

Then the automaton accepts exactly one word if and only if it is the empty word $\epsilon$, which is the case when $\Sigma\_1=\emptyset$

## Multi-state DFA

Now, assuming you can have more than one state (I would think that you did not intend to have such a restriction).

You look at your DFA as a directed graph.

Acceptance of a word is equivalent to finding a path from initial state to a final state. Since the automaton is deterministic there is a bijection between such path and the words of the language. Furthermore, the length of the word is equal to the length of the path.

Finding one path between the initial state and a final state can be done simply by tracing, starting with the initial state. You start with a set $U$ (for untraced) containing only the initial node, and a set $T$ (for traced once) initially empty.

Then for any state $q$ remaining in $U$, you add all nodes $q'$ with a transition $q\to q'$ to $U$ unless they are already in $U\cup T$, and you transfer $q$ from $U$ to $T$. You terminate when $U$ is empty, and then all nodes in $T$ are reachable from the initial state. Note that this is the gist of tracing garbage collection algorithms. The complexity is linear if inclusion of a node in a set is checkable in constant time (for example by marking the node).

Now, in order to check for multiple paths, you modify a bit the algorithm, replacing $T$ by two sets $T\_1$ (for traced once) and $T\_2$ (for traced twice). You proceed as before, with the following changes, that depend on whether $q$ is in $T\_1$ or not.

1. When $q\notin T\_1$ ( $q$ was never traced, nor accessed from two paths), consider successively every transition $q\to q'$, *making sure you process first a transition $q\to q$ if any exists*:

* if $q'$ is already in $T\_2$, you ignore it
    * else, if it is in both $U$ and $T\_1$, you ignore it
    * else, if it is in $T\_1$, but not in $U$, you add it to $U$ (leaving it in $T\_1$ too).
    * else, if it is in $U$, but not in $T\_1$, you add it to $T\_1$ (leaving it in $U$ too).
    * else, if $q'$ is in none of the sets, you add it to $U$.

Then you move the node/state $q$ to $T\_1$ if it is not already in $T\_1$, or to $T\_2$ if it is in $T\_1$ (you may remove it from $T\_1$ if convenient for set encoding, but it does not matter). Note that $q$ may already be in $T\_1$ if one of the transitions just processed is of the form $q\to q$.
2. When $q\in T\_1$ (there are at least two paths to $q$), consider successively every transition $q\to q'$:

* if $q'$ is already in $T\_2$, you ignore it
    * else, put $q'$ in both in both $U$ and $T\_1$ (it may be there already)

Then you move the node/state $q$ to $T\_2$ (and you may remove it from $T\_1$, if you wish).

When you terminate (with $U$ empty), you have at least two paths from the initial state to a final state if and only if you have an accepting state in $T\_2$, or two accepting states in $T\_1$. You have at least one path if $T\_1\cup T\_2$ contains an accepting state, and no path it it does not.

So the necessary and sufficient condition for the existence of exactly a single word in the language is that there is a single accepting state in $T\_1$ and none in $T\_2$.

With proper encoding of the sets, this works in linear time (in the size of the DFA), and can be quite fast.

*Note*: the conditionals have been written for better readability. They can be better organized for efficiency.

# Answer
> 3 votes
This is the lazy-person approach:

* Minimize the DFA
* The Automaton describes a 1-word language if and only if
    1. it has exactly 1 final state, and
    2. every non-final state has one outgoing transition.

Note: This is far from being the most efficient solution - its just a short one.

# Answer
> 1 votes
First, as Luke has said, if the problem is to decide that a FA (deterministic or not) has only one state, it's trivial. If I gave you a description, $\langle\\,M\\,\rangle$, of a finte auomaton $M$, could you look at that description and determine whether $M$ had only one state? Surely you could.

---

The more interesting problem is to decide, given $\langle\\,M\\,\rangle$, whether $M$ accepted exactly one string, which we would write as $|L(M)| = 1$. The design of the decider isn't immediately obvious, but we can get some help from this

**Theorem**: If $M$ is a DFA with $n$ states, then $L(M)$ is infinite if and only if $M$ accepts a string of length $l$ where $n\le l \< 2n$.

Part of this is an immediate consequence of the Pumping Lemma for regular languages: if $M$ accepts a word, $w$, of length greater than or equal to $n$, then we can pump $w$ to be as long as we wish, so $L(M)$ would contain all these (infinitely many) strings. The upper bound is a trifle more difficult to prove, but it furnishes a decider for infinite languages. Now we can use this result to make a decider for the language we might call

$\qquad\qquad SINGLETON\_{TM} = \\{\langle M\rangle \mid M\text{ is a DFA and } |L(M)| = 1\\}$

by doing this:

```
D(<M>) =
   if |L(M)| is infinite                // we can decide this in finite time
      return false
   else                                // now we know the language is finite
      count = 0
      for all strings x of length < n  // only finitely many strings to test
         if M accepts x
            increment count
      return (count = 1)

```

So $SINGLETON\_{DFA}$ is decidable, since we've built a decider for it.

# Answer
> 1 votes
A DFA accepts more than one word if and only if there is more than one path from the starting state to a final state.

Figuring out if this is the case does not require more than a graph traversal and some checks. Formulated as a decider for $O$ on input $A = (Q, \Sigma, \delta, q\_0, Q\_F)$:

1. Perform DFS from $q\_0$ and count for each vertex how often it has been reached (in an array $c$).
2. Reject if $\sum\_{q \in Q\_F} c\[q\] \neq 1$.
3. Denote with $q\_f$ the one final state with $c\[q\_f\] = 1$.
Reject if $c\[q\] \> 1$ for any $q$ on the path from $q\_0$ to $q\_f$.
4. Accept

After the first step, $c\[q\]$ is the number of simple paths from $q\_0$ to $q$ in $A$. Clearly, if any of the final states have more than one, or more than one final state have any of these paths, the automaton accepts more than one word. (If there are none at all, it accepts no word.) So, rejecting in step 2 is the right call.

If we do not reject here, there is exactly one final state for which there is exactly one simple path from $q\_0$. Now we have to check if there is a cycle intersecting this path; this is what step 3 does. Note that we get the path from the DFS in step 1.

If there is no such cycle there is indeed only one accepting path in $A$ and we can accept.

Clearly, the algorithm runs in time $O(|\Sigma| \cdot |Q|)$.

---
Tags: computability, finite-automata
---


# Question
Title: Why are comparisons so expensive on a GPU?
While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the buckets it should loop through.

More precisely:

1. each thread gets an ID, by that ID it fetches its triangle from the memory (3 integers each) and by those 3 it fetches its vertices(3 floats each).
2. Then it transforms the vertices into integer grid points (currently 8x8x8) and transforms them into the triangle bounds on that grid
3. To transform the 3 points into bounds, it finds the min/max of each dimension among each of the points

Since the programming language I am using is missing a minmax intrinsic, I made one myself, looks like this:

```
procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

```

So on the average it should be 2.5 * 3 \*3 = 22.5 comparisons which ends up eating up way more time than the actual triangle - edge intersection tests (around 100 * 11-50 instructions).

In fact, I found that pre-calculating the required buckets on the cpu (single threaded, no vectorization), stacking them in a gpu view along with bucket definition and making the gpu do ~4 extra reads per thread was 6 times faster than trying to figure out the bounds on the spot. (note that they get recalculated before every execution since I'm dealing with dynamic meshes)

So why is the comparison so horrendously slow on a gpu?

# Answer
> 10 votes
GPUs are SIMD architectures. In SIMD architectures every instruction needs to be executed for every element that you process. (There's an exception to this rule, but it rarely helps).

So in your `MinMax` routine not only does every call need to fetch all three branch instructions, (even if on average only 2.5 are evaluated), but every assignment statement takes up a cycle as well (even if it doesn't actually get "executed").

This problem is sometimes called *thread divergence*. If your machine has something like 32 SIMD execution lanes, it will still have only a single fetch unit. (Here the term "thread" basically means "SIMD execution lane".) So internally each SIMD execution lane has a "I'm enabled/disabled" bit, and the branches actually just manipulate that bit. (The exception is that at the point where every SIMD lane becomes disabled, the fetch unit will generally jump directly to the "else" clause.)

So in your code, every SIMD execution lane is doing:

```
compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

```

It may be the case that on some GPUs this conversion of conditionals to predication is slower if the GPU is doing it itself. As pointed out by @PaulA.Clayton, if your programming language and architecture has a predicated conditional move operation (especially one of the form `if (c) x = y else x = z`) you might be able to do better. (But probably not much better).

Also, placing the `c < min` conditional inside the `else` of `c > max` is unnecessary. It certainly isn't saving you anything, and (given that the GPU has to automatically convert it to predication) may actually be hurting to have it nested in two different conditionals.

---
Tags: computer-architecture, parallel-computing
---


title: Shortest path in a mutable graph

text:
# Question
Title: Shortest path in a mutable graph
I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find **any** shortest path to every other node from a root $s$. This is performed in time proportional to $V + E$, where $V$ is the number of vertices and $E$ the number of edges. I have $V= N^2$ vertices in my graph. Now suppose I remove $N$ vertices (for now lets assume at random, in reality there is a pattern). If I want to find shortest paths for my new graph, is there any information from the first computation that I can cache to speed things up?

# Answer
## A simple approach

Given that you have a DAG, and the only change you will make is to delete vertices, there is a crude but simple to implement algorithm you could use. In addition to computing the distance from $s$ to every vertex, also compute the shortest paths tree.

Now, when you want to delete a vertex $v$, mark the entire subtree rooted at $v$ (in the shortest path tree). Delete this from the shortest path tree, and process each of the nodes in that subtree to re-calculate their distance from $s$. You can process those vertices in topological sorted order, and compute the updated distance for vertex $x$ by the standard formula $d(x) = \min \\{1+d(w) : (w,x) \in E\\}$. The running time will be proportional to the size of the subtree you deleted. Whether this is efficient in practice will depend on the structure of the graph and the nodes that you delete.

## More sophisticated solutions

This kind of problem has been studied extensively in the literature. The keyword you want to use is "dynamic shortest paths". Here dynamic refers to the fact that the graph can change. In your case, you want to support vertex deletions. So, I suggest you spend some quality time with the research literature to review the known algorithms for dynamic shortest paths with vertex deletions. Alternatively, look for algorithms for dynamic shortest paths with edge deletions (since when you delete a vertex you're probably going to delete all edges incident on that vertex as well).

See, e.g., Retrieving the shortest path of a dynamic graph and How to approach Dynamic graph related problems and https://cstheory.stackexchange.com/q/17135/5038 and https://cstheory.stackexchange.com/q/11855/5038 for some entry points into the literature. Those algorithms apply to arbitrary graphs, but it might be possible to exploit the fact that your graph is actually a DAG to get even better performance.
> 4 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: What is the name for this ... (alerting when threshold is exceeded, but only if dropped enough below threshold first)
Imagine: you are monitoring a system, and want an alert when certain measured value goes over a threshold value X.

But perhaps the measured value is constantly fluctuating close to X, and you get a lot of alerts.

There's an solution to that, where you only get new alerts when the measured value has dropped to below Y (e.g. X-10%). So that you only get alerted when the value had dropped meaningfully below X.

What is the name for that?

I remember this from CS uni years, but can't remember which class it came with (queueing theory?), or what the name for it was.

I've googled with various keywords (monitoring, maximum, alerts, skewed, ...) but no useful results.

# Answer
Hysteresis is a general concept in control systems that seems relevant.

Debouncing is another specific technique used for post-processing data from switches/buttons that has a similar flavor. The term has sometimes been used elsewhere in software systems to deal with similar issues.

Finally, take a look at rate limiting for a related technique.
> 1 votes

---
Tags: algorithms, terminology
---


title: Term for index-like data structures

text:
# Question
Title: Term for index-like data structures
There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently.

That includes trivial things like sorting/hashing, less trivial things like quad trees, and includes far less trivial things such as dominator trees, interval decompositions of DAGs or distributed data structures using labelings.

I was wondering what is a common term for such data structures, and if there isn't, how to describe them best. "index-like" comes to mind, but there aren't yet any tags with the word "index" here so it does not seem to be common.

# Answer
These are sometimes called (static) *online* data structures or online query data structures. It's actually rather hard to find a definition written down and the notion is "soft", in the sense that you can reasonably argue that almost anything would qualify especially if you allow updating. Here's one definition and mini-taxonomy:

> Online data structures support query operations in a continous manner. When the data items do not change and the data strucuture can be preprocessed before any queries are made, the data structure is known as *static*. When the data structure supports insertions and deletions of items, intermixed with the queries, the data structure is called *dynamic*.

The term online algorithm is used with a related meaning. It seems to be more widespread (as a term) than its counterpart for data structures. Since the query is the stuff/input that's online in your case, "data structure for online query" is more explicit; searching this as an entire phrase doesn't find much, but as nearby terms you'll get relevant hits e.g. from books \[1\] \[2\] \[3\] \[4\] etc. Likewise one can speak of "data structure" for "online updating".
> 3 votes

# Answer
"Query-oriented" might be a reasonable modifier for data structures optimized for queries. (Using "query-optimized" may be unclear whether the data structure is optimized *by* the query — the most likely impression — or *for* the query.)

For a data structure that is optimized for queries without especially penalizing other uses, "query-aware" might be used.

(Obviously "-oriented" and "-aware" could be applied to any operation, e.g., "insert-oriented" and "insert-aware".)

Neither term seems to be firmly established (though Google Scholar provides several uses of "query-oriented" and "query-aware") and there does not appear to be any prior nomenclature. However, even if prior obscure nomenclature existed, the use of such easily understood, descriptive naming would generally be acceptable or even desirable. At worst it replaces a less familiar established name with a more wordy but accessible term.
> 2 votes

---
Tags: terminology, reference-request, data-structures
---


# Question
Title: What is the name of this size method calculating the size of a node?
My confusion is that if the recursive call calls the left nodes, and then adds with the right nodes, how are the nodes that are to to right of the left nodes and vice versa being called?

```
int size (BinaryNode t) {
  if (t == null)
    return 0;
  else
    return 1 + size(t.left) + size(t.right);
}

```

# Answer
> 1 votes
Remember that to get the actual value of `size(t.left)`, you have to evaluate the method `size` at the node `t.left`, i.e. assuming `t.left` has left and right children the algorithm with call `size((t.left).left)` and `size((t.left).right)`.

---
Tags: terminology, data-structures, trees, binary-trees, recursion
---


title: How do Computer Algebra Systems work?

text:
# Question
Title: How do Computer Algebra Systems work?
In Computer Architecture course, I have learnt how computer performs numerical computations.
While using MATLAB, I was introduced to symbolic mathematics toolbox.
I was amazed to see it manipulating trigonometric expressions, indefinite integration etc.
What sorts type of algorithms are used for doing symbolic mathematics.
Is there any text or article available of how symbolic mathematics is performed in computer algebra systems.

# Answer
> 3 votes
*Note: For this answer I chose to assume that the question was somewhat naive, since, as remarked by @D.W. in his comment, the OP should otherwise search for himself in wikipedia and other places on the web, and the spectrum of problems and techniques is far too wide for an answer here. So I am focussing on the fundamental aspects, obvious to a seasoned computer scientist, but somewhat magical for someone with less technical experience, and seeming to border artificial intelligence, when it is often just the application of appropriate recipes (well, often complex ones). One meta-remark: users who ask questions should give some information regarding their experience (or their age, as a weak indicator). It is often difficult to assess the level appropriate for an answer.*

A fundamental question is whether there is any difference between numerical computation and algebraic manipulation.

As a computer scientist (to be ?) you shold more than anyone else be aware that all that is done by the computer, or by the mathematician, is to manipulate representations of abstract entities.

You learn in "algorithmics and data structures" that to deal efficiently with a problem, you have to find a proper representation for the data (e.g. a graph, an array, a string, a hash-table, a binary-tree, etc.) and to manipulate this representation appropriately (which impacts the choice of the proper representation) to get a representation of the result.

Numerical calculation is no different. You represent numbers by sequences of symbols (though some systems use two dimensional representations). Then you define various manipulation schemes of these sequences that corresponds to numerical operations you are interested in.

The invention of the representation `0` for a number measuring the absence of any content, and of positional numeration system (i.e. representation of numbers) was a major step in mathematics, and allowed for more effective encoding techniques for numerical data, and of simpler manipulation techniques for doing the operations.

This oganization is universal: we always work on representations. The computer does nothing else, even when doing simple arithmetics.

So the answer to your question is simply, as always: choose a representation for whatever concepts you want to manipulate an design the algorithms that manipulate these representations in a way that corresponds to the abstract manipulations you are interested in.

Typically, if you want to manipulate algebraic expressions containing constants, variables (identifiers) and operators, you can just represent them as a rooted tree structures with constants and variables on the leaves, and the operators on the nodes. That is easy, though more complex representations may sometimes be useful.

Now you may consider your expression as representing a function of a variable `x`, that appears among the variables, and you want to compute the derivative of that expression for `x`. You can probably imagine the algorithm yourself, if you know the rules for computing a derivative, when you do it by hand. This is a fairly simple recursive procedure, since the derivative of an expresson can be defined from the subexpressions and their derivatives, in a way that depends on the top operator.

You can do things similarly for some trigonometric computations, applying various rules and strategies for transforming trigonometric expressions (such as: $\cos(a+b)=\cos a\cos b-\sin a\sin b$ ), that were used by hand by people (including myself) before computers were available to do it.

Now, many of these manipulation problems are actually hard to solve. But that comes from the diffculty of mathematics, not from the fact that it is mechanized in a formal calculation system. There involve a wide variety of techniques and mathematical theories, that have to be adressed individually, and certainly not together in a single question.

As a final remark, we should remember that much of the theory of computation originates with the search for answers to the Entscheidungsproblem, a challenge posed by David Hilbert in 1928 about mechanisation of mathematics, and addressed by such people as Gödel, Church, Turing, and several other pioneers of the field. The fact that computing devices are now used to do just that, mechanize mathematics, was only to be expected. It is always pleasing to see some consistency between the various branches of computer science.

---
Tags: mathematical-software
---


title: Why separate lexing and parsing?

text:
# Question
Title: Why separate lexing and parsing?
It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test production rules on those tokens? Why not have a single pass that applies production rules directly to the text?

# Answer
> 14 votes
You don't have to separate them. People combine them into scannerless parsers.

The key disadvantage of scannerless parsers appears to be that the resulting grammars are rather complicated -- more complicated than the corresponding combination of a regular expression doing lexing and a context-free grammar doing parsing on the token-stream. In particular, grammars for scannerless parsing tend towards ambiguity. It's easier to remove ambiguity for grammars working on a token-stream.

A pragmatic benefit of using a dedicated upfront lexing phase is that you don't couple the subsequent parser with lexical detail. This is useful during early programming language development, when the lexical and syntactic details are still changing frequently.

---
Tags: compilers, parsers
---


# Question
Title: Reviews of work in the field of partial evaluation (post 1993)
I'm looking for relatively new reviews of research work on partial evaluation. The most recent work I've found is "Tutorial notes on partial evaluation" by Charles Consel and Olivier Danvy (1993). The book Partial Evaluation and Automatic Program Generation (1993) also gives a comprehensive overview of the work in this field.

In particular, I want to write a brief overview of the history of this field of research. And with the sources I've found so far, I only have enough to write about it up to the early 90s.

**Terminology:** In the literature, other more-or-less interchangeable terms are sometimes used instead of "partial evaluation". Like "mixed computation" (introduced by A.P. Ershov) and, as Respawned Fluff has mentioned, "program specialization". "Partial deduction" seems to be used in the context of partial evaluation applied to logic programming.

# Answer
> 5 votes
The PEPM (Partial Evaluation and Program Manipulation) Symposium Series is still running. That'd be a good place to start to see what the current hot topics are and who is still working on Partial Evaluation.

# Answer
> 4 votes
The 1998 Partial Evaluation. Practice and Theory series of lecture notes is slightly newer and fits your desired terminology.

Like said however, the notions of *program specialization* and *partial evaluation* are often taken as synonymous (e.g. they are so on p.1 of Jones et al.), so ignore the literature using/preferring the later term at your own peril. Hopefully this passage from Marlet's book (p. 44) illustrates this point:

> the general idea that largely underlies program specialization is of a “partial execution”. When partial execution is understood in a fairly literal sense (when a term is entirely known, executing it and replacing it by its result or its effects), we speak of partial evaluation. A specializer based on this principle is therefore called a partial evaluator.
>
> This kind of specialization is so widespread that, with many authors, the terms program specialization and partial evaluation are often mistaken for one another, or used as synonyms. Other authors prefer to reserve the term specialization to express the concept, i.e. the objective (to obtain a better-performing specialized program), and only to speak of partial evaluation to refer to the means used to attain that objective (evaluating anything that can be evaluated in advance). Terms other than partial evaluation are also used, such as partial computation, which remains relatively neutral, or partial deduction, which relates only to logic programming
>
> In the rest of this book, we shall speak almost exclusively of partial evaluation, but using terminology related to specialization \[...\]

If want to survey a filed, you have to take into account the terminlogy issues...

# Answer
> 3 votes
I have not been looking at partial evaluation for a very long time. There is much stuff in code optimization techniques for compilers that can fit that framework when properly presented. Thing often become relevant when you start looking at them the right way. But people in optimizing compilers may not try to emphasize the partial evaluation view when partial evaluation is no longer fashionable. Each time has its own buzzwords to get grant money and publications accepted.

So I would suggest a good look at code optimization (unless that is dead too).

I answered recently to a question about compilers, and mentioned partial evaluation as an important issue to understand the nature of the compiling process. I doubt much you will find anything new there, but just in case ...

## Partial evaluation and formal languages

Another thing in that area is not well known (afaik), though it may be seen more as an intellectual curiosity than as an important technical view. It is a bit post-1993 (in Lang 1995 actually). This concerns parsing. You may view a grammar $G$ (for example a context-free grammar, but this applies to many other kinds of syntactic formalisms) as something that computes a parse tree for a string $w$, given an appropriate grammar interpreter (the CYK algorithm is a simple example). Actually, in the case of ambiguous languages, you do not get a single parse-tree but a whole collection forming a parse-forest. There is a condensed form for parse-forest that shares subtrees that are common to several parse-trees, in different ways. With appropriate sharing structures, this shared-parse-forest is actually nothing but another grammar $G\_w$. This grammar $G\_w$ is a specialization of the original grammars to the string parsed.

What that means is that $G\_w$ is is a grammar that generates only the string $w$ being parsed, but does it with precisely the same parse trees as the original grammars, up to a homomorphic renaming of some non-terminals. So the original grammar $G$ has been specialized to a grammar $G\_w$ generating the singleton subset $\\{w\\}$ of the language of $G$.

This is moderately exciting. The more interesting aspect is that the technique works for other subsets of the original language. If you take any regular set $R$, its intersection with the language $L(G)$ is a context-free language (assuming we are working with CF grammars). Exactly the same techniques can be used to parse the whole regular set, represented by a FSA, to produce another grammar $G\_R$, which is a specialisation of $G$ for the intersection of the CF language $R\cap L(G)$. It is a specialization in the sense that for strings in that intersection it produces exactly the same parse-trees, the same ambiguities as the original grammar $G$, up to a renaming homomorphism for non-terminals.

So the idea is that you can partially evaluate a grammar when you have some information about what should be parsed, information which is specified by a finite state automaton. This can then be extended to various games people play with grammars, such as attaching attributes or feature structures. But then one would enter more traditional partial evaluation.

These techniques have actual use in natural language processing, but could be used for programming languages too.

I have various pointers accessible following links from this answer which present an example of application in NLP amongst too many other things (but the question was a bit wide).

# Answer
> 1 votes
Caveat: I have not followed the field closely. In the early 1990s partial evaluation was fashionable as a research subject, but activity died down around the turn of the millennium. I think that's because nobody could make partial evaluation efficient.

Later some key ideas resurfaced from a different community and in warped form, this time leading to blindingly fast code. What happened? The modern variant does specialisation at **run-time** and only on "**hot code**", i.e. code that has been observed during the execution to be used a lot. It is know as **just-in-time compilation**. Some of the recent work on JIT compilation (e.g. meta-tracing) looks a lot like Futamura projections. The precise connections between partial evaluations and JIT compilation have not been explored.

---
Tags: reference-request, functional-programming, meta-programming
---


# Question
Title: undirected graph without weights and DFS
following question on undirected graph without weights can be solved by using `DFS` and in `O(|V|+|E|)` times.

1. check that G is bipartite.
2. check G has one simple cycle.
3. find number of connected component G
4. with given two vertex `u`, `v`, find a path between `u and v` with `minimum edges`

anyone can describe, how the authors of this note claim that all of them can be checked with DFS and in `O(|V|+|E|)` times?

# Answer
> 1 votes
The time complexity of DFS is O(|V|+|E|), therefore if one can solve these problems with DFS, it follows their time complexity is also O(|V|+|E|), remains only to proof that complexity, for which I should recommend a reading on Cormen.

1) To check if G is bipartite, tag each visited vertex with a color. Initially, all vertex are, say, WHITE. When you start the DFS with a vertex, tag it with RED. Everytime a RED vertex visits a WHITE vertex, tag that WHITE vertex with BLUE, and when a BLUE vertex visits a WHITE vertex, tag it with RED. If a vertex visits another vertex of the same color, then that graph is not bipartite. This is because a graph is bipartite if and only if it is 2-colorable, that is, its chromatic number is 2. In short, every pair of adjacent vertices of that graph can be colored with 2 different colors, and only 2 colors are needed to color the entire graph.

2) Here, a similar approach, but with only WHITE and BLACK. All vertices are initially WHITE. Start the DFS in a vertex and tag it with BLACK. Everytime a BLACK vertex visits a WHITE vertex, tag it with BLACK. If a BLACK vertex visits another BLACK vertex, then there is a cycle in the graph.

3) Start with a counter=1 and start the DFS. If at any point the vertices stack is empty, that is, you have backtracked all the reacheble vertices from the origin and need to access the vertex list once again, then increment the counter variable. That variable indicates the number of connected components of your graph.

4) It is NOT possible to solve this problem with DFS. It is probably a trick. Why can't DFS be used to find shortest paths in unweighted graphs?

---
Tags: algorithms, graphs, data-structures, trees
---


title: Runtime of a recursive algorithm

text:
# Question
Title: Runtime of a recursive algorithm
I have a simple recursive solution as below:

```
public int countPaths(int x, int y) {

    if(x == 0 && y == 0) {
        return 0;
    } else if(x == 0) {
        return 1;
    } else if(y == 0) {
        return 1;
    } else {
        int count = countPaths(x-1, y);
        count += countPaths(x, y-1);
        return count;
    }
}

```

This is to solve the following problem from the book: Cracking the coding interview

Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0,0) to (X,Y)?

I am trying to ascertain the run time complexity and I believe it is O(x+y). I arrived at this by using a recursion tree, for example if x=2 and y=2

The max depth of this tree is (x+y) and work done at each step is a constant. So max work done is (x+y) * c and hence the run time complexity is O(x+y)

**Question 1: Am I correct? I believe the upper bound I have calculated is not tight enough**

**Question 2: Next, if I were to improve the run time using memoization and hence not repeating computing sub-problems, how would the run time complexity as described by Big-o change?**

# Answer
> 1 votes
By no means, no, your solution is not linear. It is exponencial, O(2^max(x,y)). You can see in your own picture: each function call makes another 2 calls, and that stacks multiplicatively. Now, for memoization, you would probably build a matrix and keep the records on it, in such a manner that a i,j iteration will rely only on already made calculations on x,y iterations, where x \<= i and y \<= j. This will probably result into something like O(xy), if no further calculations are made per iteration.

Finally, are you sure about this problem? It is rather a combinatorial problem that does not involve any algorithm. The problem can rephrased as: how many different permutations one can get from the following string:

RRRRDDD

Where R appears x times, and D y times? This is merely a permutation with repetition: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm

---
Tags: algorithm-analysis, runtime-analysis, recursion, memoization
---


# Question
Title: Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$
I'm planning on making a fiber art $K\_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a annulus made from wood and then to string yarn between them. Since $K\_{37}$ is a complete graph, it has a Hamiltonian path. My knowledge of computational graph theory is nil, and I am aware that this is not exactly an easy problem (see wikipedia: Hamiltonian Path Problem, for instance)

# Answer
> 4 votes
It seems that you're trying to construct the graph $K\_{37}$ from string and nails without cutting the string. For this, you don't want a Hamiltonian path (a path that visits every vertex exactly once) but an Euler trail (a walk that visits every edge exactly once).

In the case of a complete graph, finding an Euler trail is trivial: start at any vertex and move from vertex to vertex without repeating an edge. As long as the last thing you do is returning to the initial vertex, you've created an Euler trail. (This is essentially Fleury's algorithm except that checking you've not disconnected the graph is trivial for a complete graph.

# Answer
> 0 votes
$K\_n$ has $(n-1)!/2$ Hamiltonian circles and it has $\lfloor(n-1)/2 \rfloor$ distinct Hamiltonian circles (I mean no edge in common), every Hamiltonian circle in a graph with $|V| = n$ has $n$ edges. By removing any of the edges in a Hamiltonian circle the result path is a Hamiltonian path so $k\_n$ has $n \times (n-1)!/2 = n!/2 $ Hamiltonian paths and it is the permutation of nodes. What exactly do you want? You can select any of these paths.

---
Tags: graphs, graph-traversal, hamiltonian-path
---


# Question
Title: Parallel algorithms on a fixed number of processors
Usual parallel algorithms require a number of processors that grow with the size of the input, usually $O(\log n)$ or $O(n)$.

This is great from a theoric point of view, but strange from a practical point of view, where the number of the processors that we can use is bounded by a constant. A corollary of the Brent Theorem allows us to simulate a parallel machine with less processors, but doesn't gurantee that the algorithm is still optimal.

Is there a branch of parallel algorithms that studies parallel algorithms that run on a number of processors bounded by a constant?

As commented below:

> If the number of processors is bounded by a constant, then any sequential algorithm will be asymptotically optimal.

I think that this fact implies that asyntotical optimality is not the best way to measure performances in real world parallel algorithms.

Is there another measure, like speedup or cost (defined as execution time multiplied by the number of processors) that can tell us how faster is an algorithm that runs on a constant number of processors?

---

A related question is: How to scale down parallel complexity results to constantly many cores?

# Answer
There are several models, widely used in practice, that might be of interest to you. Almost all of them could be viewed as generalizations of Amdahl's law. They take *two* parameters, $P$ (number of processing elements) and $N$ size of the input. Several conferences in which you are likely to find these types of analyses are the ACM Symposium on Parallel Algorithms and Architectures (SPAA), and the ACM SIGPLAN Symposium on the Principles and Practice of Paralllel Proogramming (PPoPP).

The goal with these models is generally to understand the tradeoff, for a specific algorithm, between the increased parallelism available from larger $P$ with the increased synchronization and communication costs that come along with larger $P$.

The first one that got major attention was

> Valiant, Leslie G: A bridging model for parallel computation, *Communications of the ACM*, 33(8):103-111, 1990.

Valiant assumes that your algorithm moves between phases of completely parallel work, a phase of barrier synchronization during which the processors communicate, and then the next phase of completely parallel work. For each computation phase you assume it is going to take time inversely proportional to $P$. For the synchronization phases you usually want to take into account load imbalance, and the latency of the communication phases is going to depend both on the structure of your communication network and how good a job you can do at minimizing the distance between communicating processors.

The paper

> Culler, D; Karp, R; Patterson, D; Sahay, A; Schauser, KE, Santos, E; Subramonian, R; von Eicken, T: $LogP$: Towards a Realistic Model of Parallel Computation, *ACM Symp Principles and Practice of Parallel Programming*, (PPOPP-4):1-12, 1993.

built on Valiant's model by carefully taking into account the $L$atency between nodes, the $o$verhead of sending a message, and the $g$ap required between send operations (a measure of bandwidth), in addition to $P$. This is too detailed for some uses, but can be useful in cases where it is important for the algorithm designer to choose between many small messages and fewer long messages.

Finally I'll mention

> Blumofe, Robert D; Leiserson, Charles E: Scheduling Multithreaded Computations by Work Stealing, *IEEE FOCS*, 1994.

which gives a small generalization of Amdahl's law, pointing out that execution time is bounded (below) by $T\_P = O(T\_1/P + T\_\infty)$, where $T\_1$ is the minimum serial execution time and $T\_\infty$ would be the minimum execution time with an infinite (i.e., arbitrarily large) number of processors and no communication delays. (Another way to look at $T\_\infty$ is that it is the critical path through the algorithm.)
> 5 votes

---
Tags: algorithms, algorithm-analysis, parallel-computing
---


# Question
Title: Finding the time complexity of fibonacci sequence
I tried it as follows and would like to know if it is correct.

# Answer
The analysis is not accurate although the result is correct. You could write it more accurately by replacing $=$ with $\le$

$T(n) \le c(1+2+..+2^{n-1})$ ( $\le$ since not all level have same number of children, consider the most right-handed path, n is decreasing by $2$ every step ).

Indeed a more careful analysis can get you a tighter bound as mentioned in the comment. The idea is, the time $T(n)$ is computed with $T(n-1) + T(n-2)$ the same way as the actual fibonacci $F(n)$, and since $F(n) = O(\phi^n)$ for $\phi = (1+\sqrt{5})/2$ as the closed form.

Thus $T(n) = O(\phi^n)$ which is slightly smaller than $2^n$
> 5 votes

---
Tags: algorithm-analysis, runtime-analysis, recursion
---


# Question
Title: Fine-Grain parallel algorithm for LU-decomposition
How would you understand this pseudocode of parallel algorithm for LU-decomposition ? I'm confused mostly with the

```
min(i; j) - 1,

```

because I have no idea, what the author wanted to say by it. I know that it means " choose the lesser number of 'i' and 'j' and then substract one", but I don't know what is I and J here (maybe coordinates of the current task? Or is it written from the task's point of view, so the whole pseudocode runs at every task?) etc.

The whole presentation with this code (slide 12) is here.

---

### Pseudocode and diagram of tasks

Bigger picture here.

# Answer
> 0 votes
It will be clearer if you look at 1 slide before (10/42). The algorithm does not decide on how do you assign to node. It just says that the algorithm can be consisted of many parallel tasks. Each task has identification of $(i,j)$ and each executes the algorithm in slide (12/42).

More specifically, each task is assigned an entry $a\_{ij}$ of the matrix ($n^2$ number of tasks), and at the end of the algorithm that entry becomes $u\_{ij}$ if $i \le j$ or $l\_{ij}$ if $i\>j$.

---
Tags: algorithms, parallel-computing, matrices, decomposition
---


# Question
Title: Is there a way to find path length to a node from root in a binary tree?
I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in an array. That is, an array stores the parent values from one node to the root and the same is done to the second node and finally the arrays are compared to find the first mutual parent.

I got stuck when finding the time complexity of this algorithm. I have a feeling that, it depends on the path length of a node to the root. Is there a generalised equation for the path length of a binary tree? If not, how can I compute the time complexity of this algorithm?

PS-I want to find the time complexity wrt to n=number of nodes/elements

```
Node findLCA(BT tree, Node N1, Node N2){
    Array parentsN1;
    Array parentsN2;
    while(N1.parent != null){
        parentsN1.append(N1.parent)
        N1=N1.parent;
    }
    while(N2.parent != null){
        parentsN2.append(N2.parent)
        N2=N2.parent;
    }
    for(i in parentsN1){
        for(j in parentsN2){
            if (i==j) return i;{
                return null;
            }
        }
    }

```

}

# Answer
The worst case scenario for the algorithm is when you pick two nodes, N1 and N2 that have the longest path to the root node. In your example, two nodes whose common ancestor is J. Say the length of the path of N1 and N2 is n and m. Then the first while is O(n), the second one O(m) and finally the nested loop is O(n*m). So O(n) + O(m) + O(n*m) = O(n\*m).
> 1 votes

# Answer
Your solution is $O(n^2)$ and thus your prof won't be happy with it. The followings runs in $O(n)$ (it is better when the tree is balanced and thus running time can be bounded better such as by $O(\log n)$):

```
public Node getLCA(Node n1, Node n2) {
    int heightDiff = n1.height - n2.height;
    if (heightDiff == 0) {
        if (n1 == n2) {
            return n1;
        } else {
            return getLCA(n1.parent, n2.parent);
        }
    } else {
        Node upperNode;
        if (heightDiff > 0) {
            upperNode = walkUp(n1, heightDiff);
            return getLCA(upperNode, n2);
        } else {
            upperNode = walkUp(n2, Math.abs(heightDiff));
            return getLCA(n1, upperNode);
        }
    }
}

private Node walkUp(Node node, int heightDiff) {
    Node ret = node;
    for(int i = 0; i < heightDiff; i++) {
        ret = ret.parent;
    }
    return ret;
}

```

Computing the height of a node is $O(n)$. At each recursion, the height of at least one node changes by at least one. This means the total number of recursive calls is at most the height of the tree which is $O(n)$. Each call does a constant amount of work. This means $O(n)$ running time.
> 0 votes

---
Tags: algorithms, algorithm-analysis, data-structures, binary-trees
---


title: Normalising fractional numbers

text:
# Question
Title: Normalising fractional numbers
For example $-\tfrac9{16}$.

$$\tfrac{9}{16} = \tfrac{1}{16}+\tfrac12 = 0.1001\\,,$$ which when normalised becomes $0.1001\times 2^0$. Can its mantissa be $0.0001001$ in 8 bits?

If so, as $-\tfrac9{16}$ is negative, twos' complement is done to make its mantissa $1.1110111$. How do we normalise that?

# Answer
> 1 votes
Not clear of your process, but here is how it can be done: $\tfrac{9}{16} = \tfrac{1}{16} + \tfrac12$, which gives you $0.1001$ in binary form. To normalize, take the first bit to be 1, which gives you $1.001 \times 2^{-1}$ which makes 3 bits for the mantissa $001$ and some bits for the exponent to represent $-1$ in twos' complement.

IEEE floating point formats don't use twos' complement for negative mantissas: they use an extra bit to indicate the sign (1 means negative).

So in the end, if exponent is 4 bit (and without any excess exponent): $1\\,1111\\,001$.

---
Tags: floating-point, number-formats
---


title: Type of undecidability in Rice Theorem

text:
# Question
Title: Type of undecidability in Rice Theorem
Rice theorem says every non-trivial property of languages of Turing machines is undecidable. As David Richerby said in here :

> Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

I would like to know how to find out Rice Theorem leads to semi-decidability or non-semi-decidability?

As an example Rice Theorem is applicable to this r.e. language

> $A = \\{x | \phi\_x$ is defined for at least one input$ \\}$

and also this non-r.e. language as well:

$\psi\_p = x^2$

There is no algorithm to determine $\psi\_p$ has that property at all while for $A$ we can simply run the program forever an see whether it accepts one input or not. I would like to know using Rice Theorem is there any way to determine this difference?

# Answer
> 2 votes
Rice's Theorem just says it's undecidable. Some undecidable languages are semi-decidable; some (almost all, in fact) of them aren't.

---
Tags: terminology, computability, semi-decidability
---


# Question
Title: How to prove that there is a function index t so that t³ + t + 1 is an index of the same function?
I would like to prove $\exists t\phi\_t = \phi\_{t^3+t+1}$ where $\phi\_0,\phi\_1,\phi\_2,...$ are sequence of all of the partially computable function.

$\phi\_t = \phi\_{t^3+t+1}$ only if $t = t^3+t+1$ and it means $t=-1$! and there is no program with number $-1$!

# Answer
This is just a special case of Rogers' fixed-point theorem which says that, for any total computable function $f$, there exists $t$ such that $\phi\_t = \phi\_{f(t)}$.
> 5 votes

---
Tags: computability
---


# Question
Title: Expected number of random interval flips needed for sorting a random array
This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort.

Assume that $A$ is an array initialized by a random permutation on the set $I\_n=\\{1,2,\ldots, n\\}$.

Consider the next algorithm:

> While $A$ is not sorted:
>
> * Pick two random numbers $i\leq j\in\\{1,2,\ldots, n\\}$ uniformly and reverse $A\[i\ldots j\]$.

For example, if the initial array was $A=1,4,2,3,5,6$ and the algorithm picks $i=2,j=5$ then the value of $A$ after the reversal would be $1,5,3,2,4,6$.

Notice that this algorithm halts after finite number of iterations with probability 1.

> **What is the expected number of iterations for the algorithm?**

# Answer
$\Omega(n!)$ is an easy lower bound: your algorithm certainly needs at least $\Omega(n!)$ iterations on average. Obviously, you need to try at least $\Theta(n!)$ different permutations of the array before you have a decent chance of getting the elements into sorted order (since you started with a uniformly random permutation).

Also, one can show that $O(n! \cdot n \lg n)$ is an upper bound on the number of iterations needed. Here's why. It's known that there is a constant $c$ such that composing $k=c n \lg n + o(n \lg n)$ randomly chosen transpositions gives you something that is close to a random permutation. So, look only at every $k$th iteration of your algorithm, and consider the permutation generated at each such time instant. Each one is approximately a random permutation (independent of all others). After checking $\Theta(n!)$ independent random permutations, with good probability at least one of them will put the array into sorted order. Therefore, your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations. Or, to put it another way, if we tested for sortedness only at every $k$th iteration of your algorithm, the result would be essentially equivalent to Bogosort, so your algorithm performs at most $k$ times as many iterations as Bogosort -- thus your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.

So we know that the answer is at least $\Omega(n!)$ and at most $O(n! \cdot n \lg n)$. Those two answers are very close (they differ only by a factor that is logarithmic in the number of iterations), so this doesn't leave much of a gap -- it almost totally resolves the question. If you wanted a more precise answer, probably a more delicate analysis would be needed to eliminate the gap -- but lacking clear motivation for studying this problem, it's not clear it's worthwhile to spend that level of energy on it.

---

How do we know that composing $O(n \lg n)$ random transpositions gives you something close to a random permutation? That was proven in the following paper:

Generating a Random Permutation with Random Transpositions. Persi Diaconis, Mehrdad Shahshahani. 1981.

See also https://paulrs.wordpress.com/2014/07/22/generating-a-random-permutation/.
> 2 votes

---
Tags: algorithms, algorithm-analysis, sorting
---


# Question
Title: Efficient computation of Kronecker product
Given matrices $A \in \mathbb{C}^{n\_1,m\_1}, B \in \mathbb{C}^{n\_2,m\_2}$ a naive way to computer the Kronecker product would be as such:

$M = \operatorname{zeros}(n\_1n\_2,m\_1m\_2)$ (initialize an empty array)
For $p = 1,2,\ldots n\_1n\_2:$
For $q = 1,2,\ldots m\_1m\_2:$
$M\_{p,q} = A\_{{\lfloor {{p}{n\_1}} \rfloor},{\lfloor {{q}{m\_1}} \rfloor}} B\_{p \bmod n\_2,\ q\bmod m\_2}$

Which will have running time $O(n\_1n\_2m\_1m\_2)$.

I was wondering if there is a more efficient way to computer $M$?

Thanks!

# Answer
> 3 votes
You cannot fill a matrix with $n\_1 n\_2 m\_1 m\_2$ entries in time faster than $\Theta(n\_1 n\_2 m\_1 m\_2)$. Some considerations:

* There may be a way to reduce the number of multiplications (FFT?) by using extra additions, but it won't improve the asymptotic complexity;
* This is easy to parallelize;
* You can do this on-the-fly, i.e. store the matrix M as "Kronecker product of A and B" and perform the multiplication only after a request for an element M\[p,q\].
* Conceptually you can forget about the rectangular shape of a matrix and think about the situation where you have two vectors $\left\[x\_1,...,x\_k\right\], \left\[y\_1,...,y\_m\right\]$ and want to compute $k \cdot m$ products $x\_i y\_j$ for each $i,j$.

---
Tags: algorithms, algorithm-analysis, linear-algebra
---


title: Kosaraju's algorithm's time complexity

text:
# Question
Title: Kosaraju's algorithm's time complexity
I've reading up on Kosaraju's algorithm to compute the strongly connected components of a directed graph and I found that

1. using an adjacency list representation gives a time complexity of $\Theta(V+E)$.
2. using an adjacency matrix representation gives a time complexity of $O(V^{2})$.

Why $\Theta$ in the first case and $O$ in the second case?

# Answer
> 2 votes
Any algorithm for computing strongly connected components must examine at least $\binom{|V|}{2}$ entries in the worst case (proof below). In particular, since Kosaraju's algorithm is correct, its (worst-case) complexity is $\Omega(|V|^2)$, and so also $\Theta(|V|^2)$. There is no particular reason why Wikipedia used big O for one and bit $\Theta$ for the reader – probably a different author.

Edit: One possible reason for using big O rather than big $\Theta$ is that sometimes the algorithm is lucky and runs faster. Whether this happens or not could depend on the particular implementation of DFS.

Suppose $A$ is an algorithm examining less than $\binom{|V|}{2}$ entries. We will show that the algorithm cannot always know what the strongly connected components are. Run the algorithm, and for each entry of the adjacency matrix queried by the algorithm, return $0$. When the argument terminates, there are more than $\binom{|V|}{2}$ off-diagonal entries not queried, and in particular there exist vertices $i \neq j$ so that neither the $(i,j)$ nor the $(j,i)$ entry are queried. We could complete the adjacency matrix in two different ways: the all zeroes matrix, or the one in which both these entires are $1$. In the former case, there are $n$ connected components, in the latter, only $n-1$.

---
Tags: algorithm-analysis, graphs, runtime-analysis
---


# Question
Title: Big-O Time Complexity of nested for loops
My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3):

```
cin >> n;
sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n * n; j++)
        sum++;

```

Can anyone provide a distinction, and why?

Thanks in advance.

# Answer
> 2 votes
Hint: What is the value of `sum` at the end of the code, as a function of $n$? If it is $s$ then the fifth line must have been run exactly $s$ times.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: How is the complexity of algorithms to solve 3CNF (decision problem) specified?
For k inputs, the complexity of naive algorithm is O(2^k). I understood this one.

What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement "The number of clauses in CNF of the boolean expression is polynomial in k"?

What should be complexity of a hypothetical efficient algorithm to solve decision version of 3CNF? Can it be called efficient if it is polynomial in the number of inputs and number of clauses?

# Answer
> 1 votes
An algorithm runs in *polynomial time* if its running time on an input $x$ is $O(|x|^k)$ for some $k$. Here $x$ is a (without loss of generality, binary) string, and $|x|$ is the length of $x$.

For 3CNF it also makes sense to consider the running time as the number of different variables. This is because if there are $n$ variables then there are $O(n^3)$ different clauses. The hardest 3CNF to solve are those in which no clause appears twice, and for such 3CNF, the size of the 3CNF (as a binary string) is polynomial in $n$. Therefore for such 3CNF, an algorithm is polynomial in the input size iff it is polynomial in the number of variables. An additional easy argument shows that 3CNF can be solved in polynomial time in the input size iff it can be solved in polynomial time in the number of variables.

---
Tags: np-complete, satisfiability, sat-solvers
---


# Question
Title: Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?
If $A$ is turing recognizable and $A \leq\_m\bar{A}$ then $A$ is recursive? If it is true how to prove it?

**Update**

It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then $A$ is recursive. but by $A \leq\_m\bar{A}$ I can't deduce that $\bar{A}$ is r.e.

# Answer
> 1 votes
**Finally I proved it this way**, first we need a few definitions:

> $co-W = \\{A | \overline{A} \in W\\}$
>
> set $W$ is called *m-closed* if for $A \in W$, and for any $B \leq\_mA$ then $B \in W$

We already knew (Davis book page 209)

> If $W$ is m-closed or 1-closed then so is $co-W$

Because the set of all $r.e.$ sets is m-closed so is $co-r.e.$,

$A \in r.e. \rightarrow \overline{A}\in co-r.e.$ *//by definition*

$A \leq\_m \overline{A}$ because $\overline{A} \in co-r.e.$ and $co-r.e.$ set is m-closed so $A \in co-r.e.$

$A \in co-r.e.$ it implies $\overline{A} \in r.e.$

$A \in r.e. \land \overline{A}\in r.e. \rightarrow A \in recursive$

and the proof is completed

---

It implies any set $\psi$ that is m-closed or 1-closed, if $A\in\psi$ and $A \leq\_m \overline{A}$ or $A\in\psi$ and $A \leq\_1 \overline{A}$, then $\overline{A}\in\psi$

# Answer
> 2 votes
Hint: If $A$ reduces to $\overline{A}$ then $\overline{A}$ reduces to $A$ (using the same reduction).

---
Tags: computability, turing-machines, reductions
---