# Question
Title: How do I measure the reliability of a confidence value in a predictive algorithm?
Supposing I have some algorithm that is able to provide me with a confidence value for some event occurring. Let's say on day 1 it tells me that there is a 80% chance it will rain, on day 2 it tells me there is a 20% chance that the mail will be late, and on day 3 it tells me that there's a 90% chance my milk will go off.

3 days later, I measure what *actually* happened and come up with this result:

```
Confidence  Occurrence
80.000%         false
20.000%         false
90.000%         true

```

In other words, it *did not* rain on day 1, the mail was *not* late on day 2, and my milk *did* go off on day 3.

Supposing that the data set is large, but that the confidence values remain distributed and not confined to any particular range, how do I go about measuring the "reliability" of my algorithm, and what metrics could I use?

Note that the floating-point precision of the confidence value is high (say a 8-byte `double`). I know I could simply divide each confidence up and measure the samples in "buckets", but this would reduce the reliability of the result as it would require me to trade off between reducing the sample set for each range or accepting a larger error in the form of a broader test range. I want to use *all* of the information to get an accurate a result as possible.

# Answer
> 2 votes
Measuring probability given a single occurrence doesn't really make sense, because the only data that can fit such a sample is 100% or 0%. If you have many samples, that is, if you have some sample *distribution*, then you can do some measuring.

For example, you could take the KL-Divergence as a measure (although it's not symmetric).

Once you have a certain reliability measure on your algorithm, you can update this data every time you have an additional sample, in an on-line manner.

If you have more details regarding the specific algorithm, or the specific type of predictions, you can probably tailor something that suits better your scenario.

# Answer
> 1 votes
You may calculate a confidence interval for your probabilities (I'm gonna use the term 'probbility' instead of 'confidence' in this answer) s.t. you could say 'for this yes/no decision, with a confidence of e.g. 95%, the probability for 'yes' is $80\\% \pm 1.1\\%$:

* Use N-fold validation for each yes/no decision. E.g. if you have 100 samples regarding the 'rain'/'no rain' decision pick e.g. 80 samples and calculate the probability of 'rain' $p(rain)\_n = \frac{\\#rain}{\\#rain+\\#no\ rain}$. Then repeat the calculation by picking a different set of 80 samples. (Picking can be done randomly or systematically.) Repeating this N times will give N probabilities $p\_n$ for the 'rain'/'no rain' question.
* Calculate the mean $\hat{p}$ of the N probabilities. $\hat{p} = \frac{1}{N}\sum{p\_n}$
* By approximating the deviation of the N probabilities by a Gaussian probability density function (PDF), you can use the following confidence interval: $\hat{p} \pm z \cdot \sqrt{\frac{\hat{p}(1-\hat{p})}{N}}$, where $z$ is the $(1-\frac{\alpha}{2})$ Quantile of Gaussian PDF: $z = \Phi^{-1}(1-\frac{\alpha}{2})$ (You can look up $z$ in an according table, e.g. here: http://www.mathnstuff.com/math/spoken/here/2class/90/htest2.htm#2ztest). E.g. for a confidence interval of $95\\%$, $z = 1.96$.
* Example: Let's say for the 'rain'/'no rain' decision you calculated $\hat{p} = 80\\% = 0.8$ from 50 folds (i.e. 50 times picking e.g 80 samples out of 100 and calculating $p\_{1\dots50}$), therefore $N = 50$. Then, for a confidence interval of $95\\%$, your upper and lower boundaries calculate to $0.8 \pm 1.96 \cdot \sqrt{\frac{0.8(1-0.8)}{50}} = 0.8 \pm 0.111$. Thus, you can say that with a certainity of 95%, the probability of 'rain' is between 78.89% and 81.11%.

Alternatively, you could calculate the variance of all $p\_n$ as quality measure: $\sigma^2 = \frac{1}{N-1}\sum\_{n=1}^N(p\_n - \hat{p})^2$

---
Tags: algorithms, machine-learning, statistics, testing
---


# Question
Title: Does interpreter for language L1 have to be written in lower level language L0?
While reading A.S. Tanenbaum's book "Structured Computer Organization", I had come to this paragraph. The text is about how interpretation of a program works.

> The other technique is to **write a program in L0** that takes programs in L1 as input data and carries them out by examining each instruction in turn and executing the equivalent sequence of L0 instructions directly. This technique does not require first generating a new program in L0. It is called interpretation and the program that carries it out is called an interpreter.ote

My question is; does this program have to be written in L0 Language, by means of lower level language? Can this program(interpreter) be written in L1 language and have its output to be L0 language?

# Answer
> 3 votes
I think the implication of your Tanenbaum quote is that there is no compiler for L1. In which case yes, the interpreter does have to be written in another language (how else would you run the interpreter?).\[1\] It doesn't have to be lower-level; you could write an interpreter for Haskell in ML, say, or vice-versa. You usually want to use a lower-level language, though, since interpretation is going to impose an order of magnitude speed (and size) overhead you need to win back in the speed of your interpreter for the language to be competitive.

In general, no. You can write an interpreter for any language L1 in L1, provided you also write a compiler for L1. Lisps are traditionally bootstrapped by: write an interpreter (a) for Lisp in some other language, then write a compiler (b) for Lisp in Lisp, executed by (a), then write an interpreter (c) for Lisp in Lisp, compiled by (b). Now you have a Lisp interpreter written in Lisp.

Having said that, a program that takes a program in L1 and produces a program in L0 is a compiler; it compiles to L0. All compilers compile to some other language\[2\] which in turn may be compiled some number of additional times, and then is interpreted either by hardware or by another program.

\[1\] Again, there are techniques for bootstrapping interpreters interpreted by themselves, but they all involve hand-written code in another language (or in the same language but compiled) and are a bit beyond this level.

\[2\] This is an over-simplification; optimization passes can be written as 'compilers' that compile to their source language and there are other uses for compilers that compile to the same language as the input. But for your purposes, think of a compiler as compiling to a different language than the source.

# Answer
> 2 votes
The output of an interpreter is not a program in any language. An interpreter executes the input program. Its output is the program's output. In contrast, a compiler produces a program in some assembly language, for an actual or a virtual computer (for example, Java compilers generate code for the Java virtual machine).

When writing interpreters, you don't want to use assembly language, since programs are harder to write in assembly language. Rather, you want either a higher-level language like Python or Ruby, or if you care about performance, a systems language like C or C++.

---
Tags: programming-languages, interpreters
---


# Question
Title: Counting inversions in a list of integers using divide and conquer techniques
This is a homework. It looks easy, but not really.

A list of integers $a\_n$, for every $i\<j$, if $a\_i\>2a\_j$, then it is an inversion. Count the inversions in the list, and return the count and the ordered list. Note, here the order is defined by the condition, not just sort the integers.

The easiest way is double loop, but it will be a $O(n^2)$ algorithm. So I think I should try divide and conquer, by modify the merge sort algorithm. I think I could get a $O(n \log n)$ algorithm. But I found, while merging and counting cross-halve inversions, I have to scan all the elements in both *left* halve and *right* halve. Equivalent to a double loop.

For example:

```
[8] [6, 3]

```

*8 and 6* are not inversion, *6 and 3* are not inversion, but *8 and 3* are **inversion**. I have scan all the elements to make sure there's no exception.

Another example:

```
[2, 7] [1, 5]

```

There no inversion in either halve, but *7 and 1* are inversion.

I am thinking may be there's a function, and I can define $b\_n=f(a\_n)$, then I can treat $b\_n$ as normal merge sort problem. But I could not figure it out.

# Answer
The "Merge and Count" step with more explanations. You have two **sorted** lists - left one and right one. You need to merge them and concurrently count inversions. I'll be talking about *regular* inversions, not yours - your job is to extend this description. You have a current position in each list. Initially this position is 0 (the beginning of the list), and it can also point *after* the end of the list.

* if both current positions are inside their lists, then we have two cases: the left current element is less than the right current element and vice versa. In the first case we just copy the left current element into the resulting list and increment the left position. In the second case we copy the right current element into the resulting list and increment the right position **and** increment the inversions count by the number of remaining elements in the left list (including the left current element).
* else if there are no left elements anymore, then we append the remaining right list to the resulting list
* else we append the remaining left list to the resulting list

So, sometimes this algorithm adds more than one inversion to the inversions count - this allows it to work faster than $O(n^2)$.
> 1 votes

# Answer
You can do the counting in linear time for each merge step by iterating over the right list and keeping track of the following information regarding the left list:

* pointers to the first and last element that formed an inversion with the previous element of the right list
* the number of elements between those pointers

Since this is homework, I'll leave it to you to work out the details and analysis.
> 2 votes

# Answer
THE same problem was discussed by Tim Roughgarden in Coursera algorithms course, see the lecture slides analysis and design of algorithms1 suppose array A = \[1, 3, 2, 9,5, 8, 4, 6, 7\] split the list into two part using divide and conquer paradigm

```
count(array A,length n){
  count inversions and then sort
  x=count(1st half of array,n/2);//O(nlogn) count inversions and then sort
  y=count(2nd half of array,n/2);//O(nlogn) count inversions and then sort
  z=countsplitinversions(A,n);//implement this in O(n) time of merging the two sorted lists and count inverions
  return x+y+z;
}

countsplitnversions(array A,length n)
{
  D=output[length=n]
  B=1st sorted array(1st half of array)
  C=2nd sorted array(2nd half of array)
  i=1,j=1
  for k= 1 to n//for merging
    if B[i]<C[j]
      D[k]=B[i];
      i++
    else[C[j]>B[i]]
    D[k]=C[j];
    j++
  end
}

```

consider \[1,3,5\] and \[2,4,6\] so while merging ,due to 2 copied to output there will be 2 inversions(2,3) and (2,5) and when 4 copied to output the split inversion discovered is (4,5)
> 1 votes

---
Tags: algorithms, counting, divide-and-conquer
---


# Question
Title: Decide if a specific Turing machine halts on a specific string
Can you always decide if a specific Turing machine accepts a specific string?

I started thinking about this after reading an answer to this question, Rice's theorem vs Turing completeness, which seams to you can.

If this is true, intuitively, it seams it would be implied that HALT could be decided, which is obviously not true. Otherwise what is the difference?

# Answer
> 5 votes
The problem you are referring to is sometimes known as the Acceptance problem. It is indeed undecidable.

Let me attempt to find the source of your confusion. I assume by linking the other thread you are referring to the following decidable language:

$$ L\_{HP-M'-x} = \begin{cases} 1 & \text{M' halts on x} \\ 0 & \text{otherwise} \end{cases} $$

The reason this language is decidable is because, given any $M'$ and $x$, this language must be either $\\{1\\}$ or $\\{0\\}$. In particular, this MUST be a finite language, and ALL finite languages are decidable.

Note that this doesn't mean we can solve the Acceptance problem. Using classical logic, we deduce that either a machine accepts a string or it does not. The hard part is figuring out which case it is! We know that the language is decidable, but we do not know what a machine that accepts this language looks like because we don't know what the language itself looks like.

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Algorithm to merge two incomplete lists of symbols (strings) into a complete one
I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution.

Let's say we have two ordered lists of symbols (strings):

```
A = "foobarquuz123"
B = "foobar456quuz"

```

my goal is to have a way to merge the two incomplete lists into the following, completed with parts from both:

```
C = "foobar456quuz123"

```

As you can see there is no intrinsic "sorting value" associated to the symbols, only their position, which is just a relative measure. Moreover, the symbols might be also repeated in arbitrary points of the strings.

Maybe the algorithm I am looking for might have been used in bioinformatics, for example for DNA or protein sequence alignment, but I am no expert of this.

What would you recommend? Do you have some pointers to algorithms that may solve this problem? I think that someone should already have figured out a solution with upper-bound computational complexity $O(k(n+m))$ where $k$ is a constant and $n$ and $m$ are the lengths of the strings.

I would be very happy to get also suggestions for books that illustrate this and similar problems.

# Answer
The problem is called shortest common supersequence. For an arbitrary number of strings it is NP-hard, but for two strings it can be solved efficiently:

First find the longest common subsequence of the two strings with dynamic programming, then insert the remaining characters.
> 2 votes

---
Tags: algorithms, strings, subsequences
---


# Question
Title: Remove minimum number of vertices to disconnect the graph
Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.

Can we do this using say a max-flow, min-cut algorithm?

# Answer
(This answer was originally given as part of the question, with the goal of it being verified.)

My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem:

1. Replace each of the undirected edges with a pair of directed edges.
2. Replace each vertex $v$ with two vertices $v\_\text{in}$ and $v\_\text{out}$ connected by an edge. all the incoming edges of $v$ will be connected with $v\_\text{in}$, all the outgoing edges of $v$ will be connected with $v\_\text{out}$.
3. Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.
> 6 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Proving number of calls made in cut-rod algorithm
I was reading dynamic programming chapter from famous book Introduction To Algorithm

In rod cutting problem it gives simple algorithm as follows:

```
    cutRod(p,n)
    {
       if (n == 0)
       {
          return 0
       }
       q = -∞
       for (i=1 to n)
       {
          q = max(q,p[i]+cutRod(p,n-i))
       }
       return q
    }

```

It then says:

> `T(n)` be the total number of calls made to `cutRod()` when called with its second parameter equal to n. T(n) equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus,

T(0) = 1 and

T(n) = ${\sum\limits\_{j=0}^{n-1} T(j)}$

Exercise at the end of this chapters asks to prove from above two that in fact

T(n) = 2$^n$

How can we go about proving this?

# Answer
You can easily prove this by induction.

Base Case T(0) = 2^0 = 1.

Say T(k) = 2^k. is true for some k.

```
Hence T(k+1) = T(k) + sum(Ti) {i = 0 to k-1}
             = T(k) + T(k)
             = 2*2^k = 2^(k+1)

```

Note: By looking at the code, it seems that if you use dynamic programming and memo-ize the T(i)'s from bottom-up, you can make this algorithm into a O(n^2) algorithm.
> 2 votes

---
Tags: algorithms, algorithm-analysis, recurrence-relation
---


# Question
Title: NP-hardness proof, what is wrong with it?
My question is the following: If we have a problem divided into two versions, weighted and unweighted. Can we prove that the unweighted problem is NP-hard from the fact that the weighted problem is NP-hard ?

For example let say I have the knapsack problem (the weighted version):

$$\max \sum\_{i}^n w\_i x\_i$$ $$\text{s.t.} \sum\_{i=1}^n p\_i x\_i\leqslant W,\quad(WP)$$ $$x\_i\in\\{0,1\\}.$$

This problem is know to be NP-hard problem. However, the unweighted version of this problem is given by: $$\max \sum\_{i}^nx\_i$$ $$\text{s.t.} \sum\_{i=1}^n p\_i x\_i\leqslant W,\quad(P)$$ $$x\_i\in\\{0,1\\}.$$ is not NP-hard since the optimal solution is to sort the items in the ascending order with respect to $p\_i$ and start filling the bag until the capacity $W$ is reached.

The problem is the following: I used the unweighted version of this problem as a special case of the weighted version and I showed that unweighted is an NP-hard problem. What is my mistake? Here is my steps: I will reduce $(WP)$ to $(P)$ in polynomial time. So, an instance of $(P)$ is constructed easily by taking $w\_i=1$. And I am done and hence $(P)$ is NP-hard which is obviously wrong.

Thank you to correct me and give me if possible some good references that deal with such weighted and unweighted problems?

# Answer
No, you cannot prove that the unweighted problem is NP-hard in this way. The error is that you cannot reduce WP to P in polynomial time (without proving P=NP).

Remember what the input to each problem is. For WP, you are given a list of $w\_i$ and $p\_i$ and must choose a setting of the $x\_i$. So once I am given a fixed list of $w\_i$ and $p\_i$, I would need to come up with an instance of P (which is just a list of $p'\_i$) so that the solution tells me the solution to WP.

The key point is that you seem to say that we can just take all $w\_i = 1$ to reduce WP to P, but we can't change the $w\_i$: They are given as part of the input. It is true that P is the special case of WP where all $w\_i = 1$, but the issue is, when we are given an instance with $w\_i \neq 1$, we have to solve this instance and we can't change the $w\_i$ we are given.
> 3 votes

---
Tags: complexity-theory, optimization, np-hard
---


# Question
Title: Teaching NP-completeness - Turing reductions vs Karp reductions
I'm interested in the question of how best to teach NP-completeness to computer science majors. In particular, should we teach it using Karp reductions or using Turing reductions?

I feel that the concepts of NP-completeness and reductions are something that every computer science major ought to learn. However, when teaching NP-completeness, I've noticed that the use of Karp reductions has some downsides.

First of all, Karp reductions seem to be unnecessarily confusing for some students. The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too". That's very intuitive -- but it maps much better to Turing reductions than to Karp reductions. As a result, I see students who are trying to prove NP-completeness get led astray by their intuition and form an incorrect proof. Trying to teach both kinds of reductions and emphasizing this aspect of Karp reductions sometimes feels a little bit like needless formalism and takes up unnecessary class time and student attention on what feels like an inessential technical detail; it's not self-evident why we use this more restricted notion of reduction.

I do understand the difference between Karp reductions and Turing (Cook) reductions, and how they lead to different notions of NP-completeness. I realize that Karp reductions give us a finer granularity of distinctions between complexity classes. So, for serious study of complexity theory, Karp reductions are obviously the right tool. But for computer science students who are just learning this and are never going to go into complexity theory, I'm uncertain whether this finer distinction is critical is critical for them to be exposed to.

Finally, as a student, I remember feeling puzzled when I ran across a problem like "tautology" -- e.g., given a boolean formula, check whether it is a tautology. What was confusing was that this problem is clearly hard: any polynomial-time algorithm for it would imply that $P=NP$; and solving this problem is obviously as hard as solving the tautology problem. However, even though intuitively tautology is as hard as satisfiability, tautology is not NP-hard. Yes, I understand today why this is the case, but at the time I remember being puzzled by this. (What went through my head once I finally understood was: Why do we draw this distinction between NP-hard and co-NP-hard, anyway? That seems artificial and not very well-motivated by practice. Why do we focus on NP rather than co-NP? They seem equally natural. From a practical perspective, co-NP-hardness seems to have essentially the same practical consequences as NP-hardness, so why do we get all hung up on this distinction? Yes, I know the answers, but as a student, I remember this just made the subject feel more arcane and poorly motivated.)

So, my question is this. When we teach NP-completeness to students, is it better to teach using Karp reductions or Turing reductions? Has anyone tried teaching the concept of NP-completeness using Turing reductions? If so, how did it go? Would there be any non-obvious pitfalls or disadvantages if we taught the concepts using Turing reductions, and skipped the conceptual issues associated with Karp reductions?

---

Related: see here and here, which mentions that the reason why we use Karp reductions in the literature is because it enables us to distinguish between NP-hardness and co-NP-hardness. However, it does not seem to give any answer that's focused on a pedagogical perspective of whether this ability is critical for the learning objectives of an algorithms class that should be taken by every CS major. See also here on cstheory.SE, which has a similar discussion.

# Answer
I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model.

Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or try to discuss the subject with anyone who wasn't taught by you.

I agree that Cook reductions are in several ways more sensible and that there's no distinction between NP-hardness and coNP-hardness in practical terms, in the sense that they both mean "This problem is pretty hard and you're not going to get a general, efficient, exact algorithm that can cope with large instances." On the other hand, the distinction between NP and coNP isn't entirely an artifact of a theory based on Karp reductions: you don't often talk about graphs that are non-3-colourability or in which every set of $k$ vertices contains at least one edge. Somehow, the "natural" version of the problem often seems to be in NP rather than coNP.
> 12 votes

# Answer
It is better to teach *both*! A computer science major should know about both of them.

I don't know anyone who uses Cook reductions for teaching NP-completeness, complexity theorists obviously don't, non-complexity theorists typically follow what is the standard definition since Karp's paper and is used in all textbooks (that I know of). It will cause a lot of confusion for them later if you do not follow the standard terminology.

Cook reductions are essentially solving problems using black-box subroutines. They are easy to explain and motivate if your students have some programming experience. They are essential since without Cook reductions you cannot discuss reductions between search problems, optimization problems, etc.

I introduce Karp reduction after Cook reductions and as a special kind of Cook reductions. I think they are *essential* for the study of $\mathsf{NP}$. This is the distinction between $\mathsf{NP}$ and $\mathsf{P}^{\mathsf{NP}}$. I think it is clear that $\mathsf{NP}$ is much more natural considering its verifier definition.

When we view $\mathsf{NP}$ and $\mathsf{coNP}$ with the goal of finding (deterministic) algorithms to solve them there is not any difference between them. I think this view is the reason you feel Karp reductions are not that important. But that is not the right way to think about $\mathsf{NP}$. The right way to think about $\mathsf{NP}$ is as a very powerful and natural problem *specification* language. If you take the efficiently verifiable and problem specification language view seriously then you cannot get away with replacing Karp reductions with Cook reductions and $\mathsf{NP}$ with $\mathsf{P}^{\mathsf{NP}}$.

(I also mention Levin reductions in passing, though not always by name, by pointing out that the reduction examples we see throughout the course have this property that given a proof for $x\in A$ we can efficiently compute a proof for $f(x) \in B$.)
> 10 votes

# Answer
> The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too".

an interesting way to approach this particular teaching issue is to realize that NP completeness has similarities and analogies to undecidability which is also unintuitive. students enter class only ever having heard of algorithms that halt. but the principle theorem of TCS is that problems exist for which there is no guaranteed solution, ie the halting problem. and in fact undecidable problems can begin to look far from contrived, and are apparently somewhat ubquitious.

so, the theory is telling us the way to view computation fundamentally as a process that *may* return an answer under some circumstances. in other circumstances, it may not. for NP completeness and decidability, the fundamental and most general question is, "is there an algorithm that return `Y` in P time". but this says nothing about an algorithm that returns `N` in P time. an algorithm could return `Y` in P time for one instance but not return an answer on other instances. the theory is telling us that there really is a distinct difference here that we have to pay close attention to. if its unintuitive, it means our fundamental intuitions need to be readjusted (as is often the case in theoretical teaching).
> -2 votes

---
Tags: complexity-theory, np-complete, reductions, education, didactics
---


# Question
Title: Performing Transitive Reduction via neighbourhood and strongly connected components
I am trying to learn(self-study, not homework) how to perform transitive reduction according to what what Prof. Leskovec explains in section 10.8.6 in Mining Massive Datasets. The book is free to access online.

The section is actually talking about a way to perform transitive closure for a graph randomly choosing a node and determining it's strongly connected component(SCC). Though there are further steps on what to do next for using the above to calculate transitive closure, I want to focus on the SCC determination and its role in transitive reduction.

SCC is found for a node v with the following formula, Given a

* graph $G$ and it's reverse graph $G'$
* $N\_G(v,\infty)$ indicates the neighbourhood of a node $v$ with radius $\infty$ i.e. all the nodes in the graph which can be reached by $v$

then the SCC with $v$ in it is given by $N\_G(v,\infty) \bigcap N\_{G'}(v,\infty)$

Once you find the SCC, collapse it to a single composite node( composite in the sense that information on which original node was collapsed is still retained) and then modify all the previous edges to point in or out to this single composite node. One repeats the above until the graph size is small and then we use that graph(and the SCC info to find transitive closure). That is the context of this question.

What I don't understand is below. It is mentioned that

> We can iterate the above steps a fixed number of times. We can alternatively iterate until the graph becomes sufficiently small, or we could examine all nodes v in turn and not stop until each node is in an SCC by itself; i.e., NG(v, ∞) ∩ NG′ (v, ∞) = {v} for all remaining nodes v. If we make the latter choice, the resulting graph is called the transitive reduction of the original graph G.

I don't understand, for transitive reduction, how one can reduce to {v} without losing valid paths which can't be reduced.

P.S - My way of reducing the graph , is for every node v, delete $edge(v,a)$ if there exists $edge(n,a)$ for n in $N\_G(v,\infty)$. There is 'currently' no need for SCC.

P.P.S - I am trying to implement this in Apache Spark for parallel computing. If you know of a more suitable algorithm, I would be happy if you could leave some pointers

EDIT: EXAMPLE 1 Consider a cycle with 4 nodes a,b,c,d. For $v=a$, $N\_G(v,\infty) \bigcap N\_{G'}(v,\infty)$ is ${a,b,c,d}$ According to the text, for transitive reduction, I have to reduce $N\_G(v,\infty) \bigcap N\_{G'}(v,\infty)$ to ${a}$. If I take out any of the edges,e.g. from $d$ to $a$ so that $N\_G(v,\infty) \bigcap N\_{G'}(v,\infty)$ is ${a}$ , it won't be a transitive reduction any more as there is no path from $d$ to $a$ as in the original path. Is my interpretation correct?

# Answer
The standard definition of the transitive reduction of a graph $G$ says that we delete as many edges as possible, to retain the same reachability relationships. However, the vertex set is unchanged: no vertices may be deleted.

The procedure you describe appears to involve deleting vertices. Therefore, it does not appear to match the standard definition of transitive reduction. (Perhaps your book has a non-standard definition of transitive reduction; if so, you might need to edit your question to ask about it.)

That said, a related construction does appear to correctly provide the transitive reduction. In the related construction, instead of collapsing all vertices in a SCC into a single vertex, we replace the SCC with a directed cycle; then we apply transitive reduction to the dag of SCCs. It is possible that your textbook actually uses the following procedure: (1) shrink each SCC to a single vertex, (2) apply transitive reduction to the resulting graph (which is the dag of SCCs), (3) now take each shrunken vertex and restore all of the original vertices and turn it into a directed cycle. That should provide a correct algorithm for transitive reduction. If that is what the book had in mind, your mistake was that you failed to perform step (3): you performed steps (1) and (2) and stopped there. Of course, you have to perform the full procedure to get the full transitive reduction.

You might also be interested in the notion of a minimum equivalent graph, which involves deleting both edges and vertices; however, finding it in general is NP-hard.
> 1 votes

---
Tags: graphs
---


# Question
Title: Are there established complexity classes with real numbers?
A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of:

> I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with a poly-time many-one reduction), so $P$ is NP-hard.

My answer was basically:

> Since $P$ has instances with values from $\mathbb{R}$, it's trivially not Turing-computable so you can skip the reduction.

While formally true, I don't think this approach is insightful: we'd certainly like to be able to capture the "inherent complexity" of a real-valued decision (or optimisation) problem, ignoring the limitations we face in dealing with real numbers; investigating these issues is for another day.

It is, of course, not always as easy as saying, "the discrete version of Subset Sum is NP-complete, so the continuous version is 'NP-hard' as well". In this case, the reduction is easy but there are famous cases of the continuous version being easier, e.g. linear vs. integer programming.

It occurred to me that the RAM model naturally extends to real numbers; let every register store a real number and extend the basic operations accordingly. The uniform cost model still makes sense -- as much as in the discrete case, anyway -- while the logarithmic one does not.

So, my question boils down to: are there established notions of complexity of real-valued problems? How do they relate to the "standard" discrete classes?

Google searches yield some results, e.g. this, but I have no way of telling what is established and/or useful and what is not.

# Answer
> 8 votes
Yes. There are.

There is the real-RAM/BSS model mentioned in the other answer. The model has some issues and AFAIK there is not much research activity about it. Arguably, it is not a realistic model of computation.

The more active notion of real computability is that of higher type computation model. The basic idea is that you define complexity for higher type functions and then use higher type functions to represent real numbers.

The study of complexity of higher type functions goes back to at least to \[ 1 \]. For recent work check Akitoshi Kawamura papers on complexity of real operators.

The classical reference for complexity of real functions is Ker-I Ko's book \[ 2 \]. The 6th chapter the more recent book by Klause Weihrauch \[ 3 \] also discusses complexity of real comptation (but it is more focused on computability than a complexity).

* \[ 1 \] Stephen Cook and Bruce Kapron, "Characterizations of the basic feasible functionals of finite type", 1990.
* \[ 2 \] Ker-I Ko, "Computational Complexity of Real Functions", 1991.
* \[ 3 \] Klaus Weihrauch' "Computable Analysis", 2000.

# Answer
> 8 votes
The model you describe is known as the Blum-Shub-Smale (BSS) model (also Real RAM model) and indeed used to define complexity classes.

Some interesting problems in this domain are the classes $P\_R$, $NP\_R$, and of course the question of whether $P\_R$ = $NP\_R$. By $P\_R$ we mean the problem is polynomially decidable, $NP\_R$ is the problem is polynomially verifiable. There are hardness/completeness questions about the class $NP\_R$. An example of an $NP\_R$ complete problem is the the problem of $QPS$, Quadratic Polynomial System, where the input is real polynomials in $m$ variables, and $p\_1, ..., p\_n$ $\subseteq$ $R\[x\_1, ..., x\_n\]$ of degree at most 2, and each polynomial has at most 3 variables. The question whether there is a common real solution $R^n$, such that $p\_1(a), p\_2(a), ... p\_n(a) = 0$. This is an $NP\_R$ complete problem.

But more interestingly there has been some work on the relationship between $PCP$,(Probalistically Checkable Proofs), over the Reals, ie the class $PCP\_R$, and how it relates to the algebraic computation models. The BSS model pans to all of $NP$ over reals. This is standard in literature, and what we know today is that $NP\_R$ has "transparent long proofs", and "transparent short proofs". By "transparent long proofs" the following is implied: $NP\_R$ is contained in $PCP\_R(poly, O(1))$. There is also an extension which says, the the "Almost (approximated) Short Version" is true too. Can we stabilize the proof and detect faults by inspecting considerably less many (real) components than $n$? This leads to questions about existence of zeros for (system of) univariate polynomials given by straight line program. Also, by "transparent long proofs" we mean

1. "transparent" - Only, $O(1)$ to be read,
2. long - superpolynomial number of real components.

The proof is tied to $3SAT$, and sure one way to look at real valued problems is how it might be related to Subset Sum - even approximation algorithms for the real valued problems would be interesting -as for optimization - Linear Programming we know is in the class $FP$,but yes it would be interesting to see how approximatability might impact the completeness/ hardness for the case of $NP\_R$ problems. Also, another question would be the $NP\_R$ $=$ $co\text{-}NP\_R$?

While thinking of the class $NP\_R$, there are counting classes also defined to allow for reasoning about polynomial arithmetic. While $\\#P$ is the class of functions $f$ defined over $\\{0,1\\}^\infty$ $\rightarrow$ $\mathbb{N}$ for which there exists a polynomial time Turing machine $M$ and a polynomial $p$ with the property that $\forall n $$\in$$ \mathbb{N}$, and $x$$\in$$\\{0,1\\}^{n}$, $f(x)$ counts the number of strings $y \in$$\\{0,1\\}^{p(n)}$that the Turing Machine $M$ accepts $\\{x,y\\}$. For reals we extend this idea there are additive BSS machines - BSS machines that do only addition, and multiplications (no divisions, no subtractions). With additive BSS machines(nodes in computation only allow addition, and multiplication) the model for $\\# P$ becomes one in which the count is over the vectors that the additive BSS machines accepts. So, the counting class is $\\#P\_{add}$ this class is useful in the study of Betti numbers, and also the Euler characteristic.

---
Tags: complexity-theory, reference-request, complexity-classes, real-numbers, computable-analysis
---


title: Complexity of Pythagorean triples

text:
# Question
Title: Complexity of Pythagorean triples
We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$.

In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit iff $b\>a$.

---

Let $\mathcal P$ be the set of all legit Pythagorean triples.

We define a lexicographic order $\prec$ on $\mathcal P$, such that $$\langle a\_1,b\_1,c\_1\rangle\prec\langle a\_2,b\_2,c\_2\rangle\iff (a\_1\< a\_2)\vee ((a\_1=a\_2)\wedge(b\_1\<b\_2)$$

Let $$L\_\mathrm{PT}=\\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P\text{ w.r.t.}\prec\\}$$

> What can we say about the complexity of $L\_\mathrm{PT}$?

We say that a triple $\langle a,b,c\rangle$ is minimal if $gcd(a,b,c)=1$. Let $\mathcal P\_\mathrm{M}$ be the set of all legit, minimal triples.

We define $$L\_\mathrm{PT}'=\\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P\_\mathrm{M}\text{ w.r.t.}\prec\\}$$

> What can we say about the complexity of $L'\_\mathrm{PT}$?

# Answer
This is not a full answer, but I think it is very useful.

Euclid's formula generates all primitive triples in a fairly linear fashion. Using all integers $m, n$ with $m \> n$, $m, n$ coprime and $m-n$ is odd, all primitive triples can be generated as

$$a=m^2-n^2, b=2mn, c=m^2 + n^2$$

I don't have any knowledge on complexity, but hopefully this will help
> 2 votes

---
Tags: algorithms, complexity-theory, linear-algebra, number-theory
---


# Question
Title: Known lower bounds on halting for finite machines?
It's possible to determine whether a deterministic machine with finite memory will halt in O(n) time if the machine has n possible states. You simply run the machine until it halts or visits the same state twice, which is guaranteed to happen in no more than n steps.

Can any other algorithm do this in fewer steps? Is there a proof that no such algorithm can exist?

# Answer
It seems that your machine runs without any further input once it is started. Whatever input it has is encoded in its starting state. Since your machine is deterministic, there is at most a single transition from each state. So the state-transition graph of your automaton is a directed graph composed of paths that either are isolated cycles or are simply open linear path from an initial node/state to a final node (corresponding to a halting state without transition). There may be any (positive) number of such paths, possibly only one. Actually, only one of these paths is relevant, the one containing the initial state.

Depending on whether the initial state of your automaton is on a cyclic path or on an open path, the automaton will run for ever or halt at the end of the open path. The former is identified by checking whether a state is visited twice. The latter is identified by the fact that a halting state (without transition) is encountered.

In the question, you do not give any constraint or information on the way states and transitions are defined, other than the following:

* from a given state, there is a transition function that gives you the next state;
* you can know whether two states are the same or not.

So the only way you can map the graph structure to reason about it is to follow the transition function from state to state, even when knowing the total number of states $n$.

With $n$ states, you can have a graph $C\_n$ composed of one cycle of $n$ states. You can also have a graph $L\_n$ composed of one open linear path of $n$ states starting with the initial state and ending with a halting state. The former is non-halting, while the latter is halting.

Still assuming you know the number of states, and using only the gven primitives, the only way to find a difference is to follow $n-1$ transition. Then you are either in a halting or a non-halting state. The former tells you that computation halts, while the latter tells you it does not halt.

You clearly will not do better when you do not know $n$ in advance. Actually, you then need only one more transition to detect that the computation is not halting.

So there is no way to decide whether your automaton halts in fewer steps, unless you have other means for analyzing the state-transition graph.

In other words, the only way you can have a faster algorithm is to have some formalism that structures the state-transition graph with properties that can be used to analyze it without having to follow the transitions.
> 1 votes

# Answer
You can do it in constant time. We already know that the machine halts. So we just output "YES".

The issue is that you have to explain what is the domain of the inputs to the problem. If the domain of the inputs only contains machines which halt then the problem is trivial: all of them halt, there is nothing to check.

(You have to specify what is given as input if you want another answer.)
> -1 votes

---
Tags: complexity-theory, halting-problem
---


# Question
Title: What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?
**Background:**

The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half).

**Pool Ball Problem:** Given $n$ pool balls where exactly 1 weighs more than the rest, find that pool ball using a scale.

The common approach is to split the balls into two groups, then weighing each group. You can narrow it down to one ball in roughly $\log\_2(n)$ rounds. You can modify the algorithm to change the resulting base of the logarithm. This can be done by changing how many groups the scale can weigh. For example, if you had a scale that determined the heaviest of 4 groups (plus sign shaped on a pivot), then you would only need roughly $\log\_4(n)$ rounds.

---

**Problem:** Consider the pool ball weighing problem but allow us to grow the number of groups we can split the set of pool balls into.

Instead of using a scale that compares a predetermined constant number, $k$, of pool ball groups, suppose we are allowed to vary and modify it during execution. For example, you are allowed to start with a split into 2 groups, then 3 groups next round, then 4, etc. It is not bounded apriori. Let's say that comparing $k$ groups takes $O(k)$ time. As a result, we know the heaviest of the $k$ groups or know if they weigh the same. If we grow the number of splits with each successive round, then we would require much fewer than $log(n)$ weigh-ins. There are divisibility issues that come up when doing the splits, but assume they are trivial to resolve.

$f(i) = \text{# of splits in $i^{\text{th}}$ round}$ (This is a positive, increasing function. We are required to spend the time/space to compute this.)

Let $t\_f(i)$ be the time complexity of computing $f(i)$ given $\langle f(1), \dots, f(i-1)\rangle$ or subset of.

$N(i) = \begin{cases} n & \text{if } i = 0 \\ \frac{N(i-1)}{f(i)} & \text{if } i \geq 1 \end{cases} = \text{# of pool balls after round $i$}$

We narrow our search down to one ball in $j$ rounds when: $N(i) = 1 \geq \frac{n}{f(1)\cdot f(2)\cdot \dots \cdot f(j)}$

Or alternatively:

$\prod\_{k=0}^{j}f(k) \geq n$ for some $j(n)$ dependent on $f$

**Question:** What can we say for the optimal time complexity of this algorithm? What are some properties of an optimal $f(i)$ we should expect? I realize this heavily depends on which models of computation we use (computing a fast growing $f$ can be expensive on some models while cheap on others). I'm willing to be reasonably flexible and not picky about it. Perhaps you guys could suggest a fruitful/interesting choice. For instance, the undergrad version of the problem trivializes the complexity by ignoring the complexity of grouping the balls together and probably considers $+, \times$ to take constant time.

The tricky part here is to pick a fast growing $f(i)$ that does not end up becoming too expensive to compute. The faster a chosen $f$ grows, the more that the time complexity decreases. On the flip side, the longer $f$ takes to compute, the longer the algorithm ends up running. We're looking for ways to balance these two.

**Example:** I could simply increment the number of groups I split the pool balls into each round. Here, $f(i) = i + 1$. The total number of uses of the scale is $O(\Gamma^{-1}(n))$ (inverse factorial). The overall asymptotic time complexity is $(2+3+\dots+\Gamma^{-1}(n)) + \Gamma^{-1}(n) = O\left( \binom{\Gamma^{-1}(n)}{2} \right)$ (this takes into account the time complexity of handling the k-scale and incrementing the number of rounds each time). I'm assuming integer addition is a constant time operation.

# Answer
The asymptotically optimal algorithm is to split in 2 groups at each step. In other words, the ability to split into more than 2 groups does not allow us to find an asymptotically more efficient algorithm.

Suppose we split into $k$ at each step. Then we get an algorithm whose running time is given by the following recurrence relation:

$$T(n) = T(n/k) + O(k).$$

We do $\lg(n)/\lg(k)$ recursive calls to reach the base case, so the solution to this recurrence relation is

$$T(n) = O(k \lg(n)/\lg(k)).$$

Now the function $f(k) = k / \lg(k)$ attains its minimum at $k=2$; for larger $k$, it is strictly increasing. Therefore, the optimal choice of $k$, if we split by the same ratio at each level and disregard constant factors, is $k=2$.

Splitting by a different amount at each level doesn't help. The above argument applies to all $n$, so it applies no matter the number of balls -- i.e., no matter what level we split at.

---

Here is another way to think about it. Suppose we split into $k\_1,k\_2,k\_3,\dots,k\_m$ groups at each level ($k\_1$ groups in the first call, $k\_2$ in the second recursive call, and so on). Let's count the number of bits of information we've gained.

How many bits of information do we get after applying the scale when we've split into $k$ groups? $\lg k$ bits of information, since there were $k$ possibilities. So, we get $b\_i$ bits of information at the $i$th call, where $b\_i= \lg k\_i$.

Now we need a total of $\lg n$ bits of information to uniquely identify the ball. Therefore, we need to select $b\_1,\dots,b\_m$ so that

$$b\_1 + b\_2 + \dots + b\_m \ge \lg n.$$

What is the running time for any particular choice of $b\_1,\dots,b\_m$? Well, in the $i$th call, we split into $k\_i = 2^{b\_i}$ groups, and the time to use the scale is $O(k\_i)$, i.e., $O(2^{b\_i})$. Therefore, the total running time for a particular choice of $b\_1,\dots,b\_m$ is

$$O(2^{b\_1} + 2^{b\_2} + \dots + 2^{b\_m}).$$

Now we want to find the optimal choice of $b\_1,\dots,b\_m$. This requires us to minimize $2^{b\_1} + + \dots + 2^{b\_m}$ subject to the constraint that $b\_1 + \dots + b\_m \ge \lg n$. One can compute that the minimum is attained for $b\_1= \dots = b\_m = 1$.

---

At the end of your post, you propose an algorithm that increments the number of splits at each step. You didn't compute the asymptotic running time of your algorithm or compare it to binary search, but if carry through that analysis, it turns out that your algorithm is asymptotically slower than binary search. Therefore, your proposed algorithm is worse than straightforward binary search. It does not contradict any of the above analysis.

Details: By Stirling's approximation, $\Gamma^{-1}(n) = O(\lg n)$ (roughly, ignoring log-log factors), so your proposed algorithm's running time is something like $O((\lg n)^2)$ (roughly, ignoring log-log factors), i.e., worse than binary search.
> 1 votes

---
Tags: algorithm-analysis, time-complexity
---


title: Entropy sources: Weaver (1949) typo?

text:
# Question
Title: Entropy sources: Weaver (1949) typo?
In *Recent Contributions to The Mathematical Theory of Communication* (Weaver 1949), aka *The Mathematics of Communication* (Weaver 1949) (various copies exist online), and also published as Part I of *The Mathematical Theory of Communication* (Shannon and Weaver 1949), Weaver says:

> We are now in a position to state the fundamental theorem, produced in this theory, for a noiseless channel transmitting discrete symbols. This theorem relates to a communication channel which has a capacity of *C* bits per second, accepting signals from a source of entropy (or information) of *H* bits per second. The theorem states that by devising proper coding procedures for the transmitter it is possible to transmit symbols over the channel at an average rate\* which is nearly *C*/*H*, but which, no matter how clever the coding, can never be made to exceed *C*/*H*.
>
> * We remember that the capacity *C* involves the idea of information transmitted per second, and is thus measured in bits per second. The entropy *H* here measures information per symbol, so that the ratio of *C* to *H* measures symbols per second.

I have not managed to find published errata for this text.

Am I correct to think the phrase "*H* bits per second" ought to read "*H* bits per symbol"? If not, why not?

# Answer
> 0 votes
Yes, your understanding is correct. The theorem is indeed talking about the entropy of the source, in terms of the amount of information in each symbol. Since entropy is measured in bits, the units are bits per symbol.

---
Tags: information-theory
---


# Question
Title: Describe in English the pattern in the following regular expressions
Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible

```
#1 (x (yyy + x)*)*
#2 (c (cc)*d(dd)*)*

```

for number 1 I got all words in which when y is in the word it can only appear in blocks that are divisible by 3(0,3,6,9, etc.)

the second question I can not see any type of pattern.

I would like to know if the first one is correct, and if what pattern is on the second one?

Thanks

# Answer
> 3 votes
The first one is very close, but not quite right. Your phrasing technically allows strings that start with $yyy$, but the language contains no such string. There are lots of ways to fix what you have to incorporate this. For instance, you might try "all strings in which $y$s appear only in blocks of length divisible by $3$ preceded by at least one $x$." You'll want to check that to make sure it's right, of course.

The second one isn't too bad. Notice that a description of the regular expression inside the outermost parentheses might be "an odd number of $c$s followed by an odd number of $d$s." By applying the Kleene star, we allow this to be repeated an arbitrary number of times. Something like "All strings which, if non-empty, start with a $c$, end with a $d$ and alternate blocks of $c$s and $d$s of odd lengths," should be close.

Some general pointers:

1. Work from the inside out. Describe the subexpressions first, and use those descriptions to describe expressions.
2. If you're not seeing a pattern, it never hurts to write out some representative strings.
3. Pay special attention to boundary cases, especially around the empty string. Natural language tends to be a little unclear when it comes to things existing, satisfying properties vacuously, etc.

# Answer
> 0 votes
2) An empty string, or a series of arbitrary length made of subseries consisting of cs necessarily followed by ds, where within each subseries the number of cs and ds can never be divisible by 2.

And actually for the other one I think:

1) An empty string, or a series of arbitrary length made of subseries beginning with an x followed by any number of xs and ys, where within each subseries any occurrence of y must be in a contiguous group of ys whose length must be divisible by 3.

When I turned your rendition of 1) into a regular expression I got this:

(. + yyy)\* where . is ANYTHING.

---
Tags: regular-expressions
---


title: Combining multiple HMM models

text:
# Question
Title: Combining multiple HMM models
Is there any way to combine multiple Hidden Markov Models trained from different sets of data? For example, I want to detect the phases of a sequential activity. I collect two sets of data by using two types of sensors: accelerometer, and video stream. I create two HMM models from the accelerometer and video stream, respectively. To increate accuracy, can I combine the two models?

# Answer
Yes. Construct the product automaton.

The "product construction" is a standard construction from automata theory class (e.g., typically taught in the context of finite-state automata). It can be applied to HMM's as well, and it will do exactly what you want.

For your example, the resulting HMM will have 9 states. Each state in the resulting HMM will a pair $(s,t)$, where $s$ is a state of the accelerometer HMM and $t$ is a state of the video stream HMM. Transitions between them and probabilities are derived in the obvious way. For instance, if there is a possible transition $s \to s'$ in the accelerometer HMM and a possible transition $t \to t'$ in the video stream HMM, then the product HMM will have a transition $(s,t) \to (s',t')$ (and its probability will be the product of the probabilities of the underlying transitions). The output distribution is obtained by multiplying probabilities: if $p(x|s)$ denotes the probability of outputting $x$ when in state $s$ in the accelerometer HMM, and $p(x|t)$ the probability of outputting $x$ when in state $t$ in the video stream HMM, then we use $p(x|(s,t)) = p(x|s) p(x|t)$ as the probability of outputting $x$ when in state $(s,t)$ in the product HMM.

This assumes that the internal states of the two HMM processes are independent. That's something you'll need to verify yourself, to see whether the independence assumption seems reasonable in your particular application domain.
> 5 votes

# Answer
I would just use product states/transitions and probabilities.

Say accelerometer has states A, B...

Say video steam has states 1, 2...

Then we denote probability of transition from state 'foo' to state 'bar' while emitting character baz as P(foo,bar,baz).

Introduce a new HMM with states A1, A2, B1 etc. and then combine outputs from accelerometer and video stream into a product space of events such than an output in the new HMM is a pair (!,@) where ! is an event in accelerometer and @ is an event in video stream.

Then P(A1,B2,(!,@)) = P(A,B,!) * P(1,2,@).

I would then continue training it to capture any lack of independence however.
> 2 votes

---
Tags: machine-learning, hidden-markov-models
---


# Question
Title: Why can't we detect infinite loops in the busy beaver problem?
I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at each new machine state to see if it exactly matches a state we've previously seen. That ought to tell us there's an infinite loop, no? Then following this, shouldn't we be able to solve the problem for any given Turing machine, instruction set and tape?

# Answer
The state of a TM includes its tape contents. Since the tape is infinite, the number of different tape contents we may encounter is infinite as well. So a TM is not required to repeat a state in order to never halt.

As a very simple example, consider the TM that will in each step write a character on the tape and move to the right. -- It will never halt but also never repeat a state.
> 2 votes

---
Tags: algorithms, busy-beaver
---


# Question
Title: Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$
could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$

# Answer
$S \rightarrow$ $aSb$ | $J$

$J \rightarrow aJbb$ | $ε$

This has only one derivation tree for a word in that language.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars, ambiguity
---


# Question
Title: Understanding the time-complexity of Insertion Sort
From my textbook, I am studying the time-complexity of the insertion sort algorithm (shown below).

```
INSERTION-SORT(A)                         cost     times
1  for j <- 2 to length[A]                c1       n
2      DO key <- A[j]                     c2       n - 1
3         ▷ Insert A[j] into the sorted
          ▷          sequence A[i..j-1]   0        n - 1
4         i <- j-1                        c4       n - 1
5         while i > 0 and A[i] > key      c5       sum_{j=2}^2 t_j
6            do a[i+1]<-A[i]              c6       sum_{j=2}^2 (t_j-1)
7                i <- i-1                 c7       sum_{j=2}^2 (t_j-1)
8         A[i+1] <- key                   c8       n - 1

```

The algorithm above shows the times that each statement is executed. But wait, why is `line 1` executed `n` times?

Shouldn't `line 1` be executed `n-1` times since insertion sort starts making comparisons at the second element at the list.

Thanks in advance.

# Answer
As I see this, it is clear that the array is indexed from 1 to length\[A\] instead of the usual 0 to length\[A}-1.

The first statement *is* executed n times. It is just that (n-1) times it enters the loop and the last time n'th time when j \> length\[A\] it exits from the loop.

Hence it is correctly mentioned that the internal statements get executed n-1 times.
> 3 votes

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


# Question
Title: Difference between end carry and overflow
I am confused with end carry and overflow. When will an end carry be the overflow? How to identify whether the end carry is overflow or not? Are they both same?

Sometimes end carries obtained are simply discarded and sometimes the end carries are considered as overflows. What is the exact method to find an overflow?

In the case of **unsigned numbers**, if the addition causes end carry, then the end carry should not be discarded because it is the part of result number. In this case, is the end carry an overflow? In the case of **signed numbers**, if the addition causes end carry, then the end carry represents sign bit. In this case is the end carry an overflow?

# Answer
> 2 votes
I'm assuming we are talking about Two's Complement integers (positive and negative of course). You need to first understand the boundaries:

The largest positive value is:

$$ 2^{n - 1} - 1 = 0111\ 1111\ 1111\ ... $$

The "largest" negative (most negative value) occurs at:

$$ -2^{n - 1} = 1000\ 0000\ 0000\ ... $$

Adding *any* positive value to $2^{n - 1} - 1$ will result in an overflow! Likewise adding *any* negative value to $-2^{n - 1}$ will *also* result in an overflow (or perhaps more precisely and underflow--but that has a different meaning when it comes to floating point values).

It should be *clear* that adding anything "above" $1000\ 0000\ 0000\ ...$ ($-2^{n - 1}$) to $0111\ 1111\ 1111\ ...$ ($2^{n - 1} - 1$) will result in a carry! Yet by the above we *know* that adding *any* of these values $\geq 1000\ 0000\ 0000\ ...$ will simply be subtracting a value that results in a valid (possibly negative if it's $-1$) result. On the contrary, if we attempt to add a *positive* value such that the first digit is $0$, then we get *no* carry and yet we get overflow.

When we try to add two negatives ($1...$ and $1...$) we are bound to have a carry but this always results in $1\ 0000\ 0000\ ...$ added to some two's complement value.

The algorithm for determining overflow is very simple: if you add two positive numbers then you should get a positive and if you add two negative numbers then you should get a negative (and if you add a positive and a negative, you will *never* get the "wrong" result).

I don't know if that helps or not because I'm not too sure what you mean by "end carry".

---
Tags: digital-circuits
---


# Question
Title: How is Rice's theorem applicable to this decision problem?
I recently had a test in introduction to computability and I got the following question wrong.

## The question

**Input:** A classical Turing machine $M$ with a 2-dimensional tape.

**output:** Does there exists a Turing machine $H$ that runs in polynomial time such that for any input $x$, if $M$ halts then $M(x)=H(x)$

**Which of the following is correct?**

(a) This decision problem is trivial.

(b) This decision problem is decidable, but not trivial.

(c) This problem is undecidable, according to Rice's theorem.

(d) This problem is undecidable, but Rice's theorem is not applicable.

## My answer

I chose option (d) because the polynomial time requirement is not semantic, but the professor marked option (c) as the correct answer. Could anyone explain this?

## Background

Rice's theorem and the terms "trivial" and "semantic" are explained here.

# Answer
> 2 votes
As you correctly mention, polynomial running time is not a semantic property.

However, the property required here is not polynomial running time (of $M$), but functional equivalence to a TM with polynomial running time (on those inputs where $M$ halts). It is of no importance, how long $M$ runs on those inputs. This is a semantic property, since every other TM $M'$, that computes the same function as $M$ will have the property as well: $M'$ halts on exactly the same inputs $x$ as $M$ and on these inputs $M'(x) = M(x) = H(x)$.

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


# Question
Title: What is my error in reasoning about the complexity class $n^{o(1)}$
I'm almost sure I understand $o(1)$ (a class of functions that converge to zero in their limit), but the way I understand it, that would seem to imply that functions in $n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

Certainly the limit of $n^{1/n}$ is 1.

But it can't mean that, because the next question (and yes, this is homework) is to find a function in $n^{o(1)}$ such that its limit is infinity.

So clearly I'm making an error in my reasoning. What am I doing wrong?

# Answer
> 6 votes
Your error is to assume that the convergence from the exponent will always dominate the divergence of the base.

As an instructive example, consider the composition $f^g$, where $f(n) = a^n$, $a\>1$ and $g(n) = \frac 1n$. As in your example, $f$ diverges and $g$ converges to 0. So your reasoning would imply that $f^g$ converges to 1.
But, as you easily see, $f^g$ actually converges to $a$. (And by choosing $f(n) = a^{n^2}$, you get an example that diverges.)

# Answer
> 7 votes
> $n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

You can't take the limit of one part without taking the limit of the other part, that doesn't give any useful information. If you take the limit of both parts, you get $\infty^0$, which is an indeterminate form.

It's easier to reason about exponentials with a constant base. $$n^{o(1)} = e^{o(1) \cdot \ln(n)}$$ This way you can see that what matters is how fast the $o(1)$ function converges to $0$ relative to a logarithm.

---
Tags: asymptotics
---


# Question
Title: Is there any hope to use a computer to guess combinatorial formulas for a sequence of integer values, given some initial terms?
So sometimes in combinatorics, you are computing the count $a\_n$ of something that depends on a natural number parameter $n$. Either by hand or using a computer, you can often compute some initial terms in the sequence $(a\_n)\_n$. Now, you can enter those initial terms into the Online Encyclopedia of Integer Sequences, and if you are lucky you can get a match with a formula and info that will help you prove that your sequence satisfies that formula. But what if your exact sequence is undocumented but is directly related to a known sequence? Like if your sequence is double or the square of another known sequence? Or if your sequence can be expressed either directly or as a summation involving hypergeometric terms? If a computer could propose formulas for a sequence given some initial terms, it might help the mathematician immensely because when they finally look at the correct formula, it might become clear to them why the formula is true based on the structure of the problem and the formula. Has there been any progress in enabling computers to "guess" succinct formulas for integer sequences given some initial terms?

# Answer
An exact solution to this problem is of course impossible (for example is $3,5,7$ the sequence of odd integers or of primes?) but there are ways to get answers when the sequence is not in oeis but its "related" to some sequence in the database.

One way to do so is to use superseeker. Basically you send the sequence that you got to superseeker@oeis.org and then the server tries some algorithms in order to find a relationship between your sequence and the ones in oeis.

Hence a good start is to check what kind of tests/algorithms are used by superseeker (iirc there is a description about that somewhere on the site)
> 6 votes

# Answer
this is actually implemented in a relatively new mathematica function called FindSequenceFunction and succeeds in basic cases. it can be regarded as a model and nearly state of the art in the area.

however the general problem is very crosscutting and touches on many fields/ techniques such as Machine learning, automated theorem proving, mathematical induction, & Kolmogorov complexity (where the very similar problem solution is based on "finding the smallest TM that generates a sequence") and even croscutting into philosophy as "the problem of induction". all these fields have active research in the area. it also shows up in curve fitting and statistics/big data but there the sequences are more approximate, although generally same abstract principles apply.

the general problem is not decidable, but neither is it exactly accurate to call it "undecidable". it is always subject to "false positives" (sequences that match on the limited # of inputs but not further) and "false negatives" (sequences that have formulas but which arent discoverable by "the" or *any* algorithm). it is safe to say that research in this area will continue for decades into the future and actually, probably as long as there is mathematical research done by humans.
> 2 votes

---
Tags: combinatorics
---


# Question
Title: Can you explain this improvement to this frequency distribution algorithm?
I came across the following in a text book:

> Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting. To find out how often an arbitrary element k occurs, look up k using binary search in a sorted array of keys. By walking to the left of this point until the first the element is not k and then doing the same to the right, we can find this count in O(log n + c) time, where c is the number of occurrences of k. **Even better, the number of instances of k can be found in O(log n) time by using binary search to look for the positions of both k − ε and k + ε (where ε is arbitrarily small) and then taking the difference of these positions.**

The part I don't understand is the part I have emphasised in bold text - I can't understand how you might choose 'ε' and how you would know that the list even contains this 'ε'..

# Answer
> 2 votes
You don't really choose $\epsilon$. Rather, you (virtually) add $k-\epsilon$ and $k+\epsilon$ to your linear order at the correct spots, a feat which you accomplish by modifying your comparison function. Binary search requires you to answer queries of the form $x \< y$. When looking for $k-\epsilon$ (or $k+\epsilon$), either $x$ or $y$ could be $k-\epsilon$ (or $k+\epsilon$), and so we have to extend the definition of the comparison function, as follows: $$ k-\epsilon \< y \text{ if } k \leq y \\ x \< k-\epsilon \text{ if } x \< k \\ k+\epsilon \< y \text{ if } k \< y \\ x \< k+\epsilon \text{ if } x \leq k $$ The comparison functions on the *right* are the original ones (with $x \leq y$ being shorthand for $x \< y$ or $x = y$), and the ones on the *left* are the new ones.

# Answer
> 0 votes
The value of ε is a positive number that is smaller than difference of two possible values in the sequence. For example if you have a sequence of integer values, the value of ε is any number \<1 but \>0

---
Tags: algorithms, search-algorithms, efficiency
---


title: Compute Lazily - Model checking

text:
# Question
Title: Compute Lazily - Model checking
What is meant by lazily computing online? For example, in context of synthesis, that uses model checking.

http://www.cs.colostate.edu/~france/CS614/Readings/Readings2011/Model-checking-Survey-a21-jhala.pdf

The above paper also mentions the concept in page 21:29.

Thanks in advance

# Answer
> 1 votes
In computer science, "lazy" means "just in time": in other words, you defer doing a computation until the last possible moment (e.g., until when the output is needed).

In computer science, "online" means that you are processing a bunch of input in a streaming fashion. For instance, you might be given a sequence of queries. An online algorithm would immediately answer each query. In contrast, an offline algorithm might wait until it has seen all the queries before answering any of them.

---
Tags: formal-methods
---


title: Inequality to be disproved

text:
# Question
Title: Inequality to be disproved
Suppose that a search for a key in a binary search tree ends up in a leaf. Consider three sets : A,the keys to the left of the search path B,the keys on the search path C, the keys to the right of the search path.

Any 3 keys a,b,c belonging to A,B,C respectively must satisfy a\<=b\<=c.

How can I disapprove it? I am trying to generate a counter example, but could not find

# Answer
Search for 20 in

```
     5
    / \
   3   8
      / \
     6   11

```

$6 \in A$ and $5 \in B$ but 6\>5
> 0 votes

---
Tags: trees, binary-trees
---


# Question
Title: connected components - determining "groups" in Go
I would like to write an analysis of go positions. Part of it requires me to determine the "groups" on the board and count their "liberties".

Any Go "position" is a collection of black `x` white `o` and empty `.` on the board. So I using an 2D array.

```
o.x.xxx..x
xoo.xoxxoo
....x...ox
.ox.o.o.o.
xox..xx...
.xox.x.xx.
o..oxxoooo
..o..xxo.o
.o...oxoo.
.xo..oxxox

```

I need to identify the components of the same type (`o`, `x` or `.`) *connected* by horizontal or vertical moves. Diagonal does not count.

```
...o...    vs    .x.x
oo...oo          x.x.

```

Once I have identified a group, I need to count the *liberties* or empty spaces around that group.

Here is a group of `x` pieces with 9 spaces around it

```
 234       ..ox
1xxx5     .xxxo
 89x6      o.xo
   7         .

```

However, 4 of them are covered with `o` pieces, and 5 of them have empty spaces `.` around it. So our gropu of `x` pieces only has **5** liberties.

`.` should count as 1 liberty, the `o` pieces should not count (contribute 0) and the `x` pieces should have been included in the group to begin with.

---

Is there a systematic way to identify connected groups on the board? And then to count the liberties.

# Answer
> 2 votes
## To count connected groups

Form an undirected graph, with one vertex per location on the board, and an edge between each two locations are are adjacent (horizontally or vertically). Then, use any standard algorithm for connected components. See https://en.wikipedia.org/wiki/Connected\_component\_%28graph\_theory%29 or your favorite CS algorithms textbookk.

You'll probably want to run the algorithm twice: once for `x`'s (build a graph where you retain just the vertices with `x`'s on them, and find all connected components), and once for `o`'s (build a graph where you retain just the vertices with `o`'s on them, and find all connected components).

## To count liberties

If I understand the definition, this looks like a simple matter of programming. Find a connected component of `x`'s, look at each cell which is adjacent to it, and count how many are empty. That's straightforward programming -- no fancy algorithms needed. Programming questions are better on StackOverflow, but make sure you show your effort.

---
Tags: algorithms, graphs
---


title: Extension of Rice's theorem

text:
# Question
Title: Extension of Rice's theorem
How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable")

# Answer
> 2 votes
Any property $P$ of a pair of RE sets becomes a property $P\_{1,B\_0}$ of the first component alone, if we fix the second RE set to a set $B\_0$. As such, by Rice theorem, the property $P\_{1,B\_0}$ must be trivial or undecidable. If it is undecidable, then the property $P$ is undecidable for $\\{(A,B\_0)\mid A\in RE\\}$, and is thus also undecidable for $\\{(A,B)\mid A,B\in RE\\}$. If it is trivial, it is either true or false for all $A\in RE$, and thus $P$ is either true for all pairs in $\\{(A,B\_0)\mid A\in RE\\}$, or false for all of them.

We assume that it is trivial, and *without loss of generality* that it is true for all pairs $(A,B\_0)$.

There are then two possibilities:

* There is some RE set $A\_0$ such that the property is undecidable for the set of pairs $\\{(A\_0,B)\mid B\in RE\\}$, where $B$ is any RE language. This implies, as before, that it is a fortiori undecidable for the set of all pairs of RE languages.
* For any choice of $A\_0$, the property $P$ is decidable over $\\{(A\_0,B)\mid B\in RE\\}$. Since $A\_0$ is fixed, it can be viewed as a *decidable* property $P\_{2,A\_0}$ on the second component alone, which may be any RE set. Hence by Rice theorem, it is trivial. So $P\_{2,A\_0}(B)$ is either true, or false, for all choices of $B\in RE$. Hence the property $P$ is trivial, either true or false, over the set $\\{(A\_0,B)\mid B\in RE\\}$. Since it is true for all pairs $(A,B\_0)$, it must be true for $(A\_0,B\_0)$, and since it is trivial for $\\{(A\_0,B)\mid B\in RE\\}$, it must be true for all pairs $P(A\_0,B)$. And since that reasonning is valid for any choice of $A\_0$ in RE, the property must be true for all pairs of RE sets.

Hence we see that the property is either undecidable or trivial (true for all pairs or false for all pairs).

# Answer
> 3 votes
Let $C$ be the collection of all c.e. sets. One way to understand Rice's theorem is to say that every computable map $f : C \to \mathsf{bool}$ which preserves equality of sets is constant. (By "respects equality of sets" we mean that $f$ actually accepts *codes* of c.e. sets, but it maps any two codes for the same set to equal values).

Let's answer your question. Suppose we have a computable map $g : C \times C \to \mathsf{bool}$ which respects equality of sets. We want to prove it is constant. Then for every $y \in C$, the map $x \mapsto g(x,y)$ is constant by Rice's theorem. Likewise, for every $x \in C$, the map $y \mapsto g(x,y)$ is constant by Rice's theorem. But a map $g$ which is constant in each argument separately is constant.

---
Tags: computability, turing-machines, undecidability, semi-decidability
---


title: Sort doubly linked list efficiently

text:
# Question
Title: Sort doubly linked list efficiently
How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?

# Answer
> 3 votes
Mergesort keeps its $\Theta(n\log n)$ worst case on linked lists. Double-linking can't help (except perhaps by improving the constant, though it's hard to see how), because every comparison-based sort provably requires $\Omega(n\log n)$ comparisons in the worst case.

# Answer
> 0 votes
The best way to sort doubly linked lists I'm aware of is to use natural mergesort. You start by splitting the list first to sorted sublists by traversing it once and finding sorted list sequences. These sorted sublists are linked together with backward-pointers of the elements to avoid additional memory requirement during the sort. Then just repeat merging sublist pairs until there's only one list left. In the end you traverse the list once again and fix-up the backward-pointers.

This is still $O(n\log n)$ but the additional memory requirement is optimized from $O(n)$ of iterative mergesort implementation to $O(1)$. Also finding the sorted sublist at start helps with the performance if the list elements are not completely random.

---
Tags: algorithms, time-complexity, sorting, linked-lists
---


# Question
Title: Are interrupts needed for a computer system to work?
Are interrupts needed for a computer system to work? Could you have a computer system (hardware and software, including the OS) that worked without an interrupt mechanism?

# Answer
No, they're not needed for a computer to work. For instance, you can use polling to interact with devices, instead of interrupts, and you can use cooperative multitasking for scheduling multiple processes, rather than preemptive multitasking.

(Thank you, @Paul A. Clayton!)
> 5 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: In Ada95 how many bytes does integer occupied in memory?
Also asking for float, character, ect.

# Answer
> 1 votes
Ada does not have primitives in the same way as most languages. Instead when you define an Integer or Floating Point Type you provide a range.

The compiler then ensures the Type has that range in whatever underlying type it chooses on that system.

The Standard library does however provide some predefined types...

See http://en.wikibooks.org/wiki/Ada\_Programming/Type\_System

http://www.adahome.com/rm95/rm9x-03-05-02.html

---
Tags: memory-allocation
---


# Question
Title: Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?
According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved versions.

Also according to my lecture, an approximation scheme is called *"fully polynomial time approximation scheme (FPTAS)"*, if its run time is polynomial in $1/\epsilon$ and **polynomial in the encoding length** of the instance (usually, the input size is denoted by $n$, such that the encoding length would be $\log n$).

The algorithm has running time $\mathcal{O}(n\log(n))+\mathcal{O}(n + (1/\epsilon)^2)$. I do agree on this being polynomial in $1/\epsilon$, but how is it polynomial in the encoding length of $n$?

The part $\mathcal{O}(n\log(n))$ of the run time is due to sorting the list of $n$ items. As far as I'm capable of judging this, this is polynomial in $n$, but not polynomial in $\log n$.

Where am I wrong?

# Answer
> 6 votes
The input to 0/1 knapsack is a list of $n$ items each with a weight $w\_i$ and value $v\_i$ with knapsack size $W$ and maximum value $V$. Thus the input list has size $O(n (\log W + \log V))$.

So $n \log n$ is polynomial in the input.

The problem with the traditional dynamic programming solution of knapsack is not that it is exponential in $n$, but that it is polynomial in $W$ (or $V$), which makes it exponential in $\log W$.

---
Tags: algorithm-analysis, runtime-analysis, approximation, polynomial-time, knapsack-problems
---


# Question
Title: Why is the precision of floating point numbers worse for smaller numbers?
Why is the machine error/epsilon higher between a pair of two lower numbers than a pair of two high numbers? For example, between the two smallest numbers possible in 5 bit mantissa and the two largest numbers possible in a 5 bit mantissa. The error for the smallest pair is nearly twice as much as the largest pair?

Another way to phrase this question is why does the machine error differ across an interval?

# Answer
The potential error is the same in absolute terms for the same exponent.

But since the smaller numbers are about half the size of the larger numbers, the relative error is about twice as high for the smaller numbers.
> 1 votes

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


title: Question on SR latch functionality

text:
# Question
Title: Question on SR latch functionality
Below is the diagram of SR latch

The following is the functional table as per my scrutiny .

```
Sl.no    S | R    Q(t) | Q'(t)    Q(t+1) | Q'(t+1)    Q(t+2) | Q'(t+2)   Q(t+3) | Q'(t+3)   Remark
=====   ===|===  ======|======    =======|=======    ========|========  ========|========= ========
1        0 | 0       0 | 0             1 | 1               0 | 0              1 | 1        Oscillaton
2        0 | 0       0 | 1             0 | 1               0 | 1              0 | 1        Stable(Hold)
3        0 | 0       1 | 0             1 | 0               1 | 0              1 | 0        Stable(Hold)
4        0 | 0       1 | 1             0 | 0               1 | 1              0 | 0        Oscillaton
5        0 | 1       0 | 0             0 | 1               0 | 1              0 | 1        Stable
6        0 | 1       0 | 1             0 | 1               0 | 1              0 | 1        Stable(Reset)
7        0 | 1       1 | 0             0 | 0               0 | 1              0 | 1        Stable-1(Reset)
8        0 | 1       1 | 1             0 | 0               0 | 1              0 | 1        Stable-1
9        1 | 0       0 | 0             1 | 0               1 | 0              1 | 0        Stable
10       1 | 0       0 | 1             0 | 0               1 | 0              1 | 0        Stable-1(Set)
11       1 | 0       1 | 0             1 | 0               1 | 0              1 | 0        Stable(Set)
12       1 | 0       1 | 1             0 | 0               1 | 0              1 | 0        Stable-1
13       1 | 1       0 | 0             0 | 0               0 | 0              0 | 0        Stable
14       1 | 1       0 | 1             0 | 0               0 | 0              0 | 0        Stable
15       1 | 1       1 | 0             0 | 0               0 | 0              0 | 0        Stable
16       1 | 1       1 | 1             0 | 0               0 | 0              0 | 0        Stable

```

Notation :

Stable : Stable output state

Stable-1 : Stable output state after one time unit delay

Set , Reset , Hold are as per normal usage.

My doubts :

1) If S=R=1 , output is stable and is 0,0 . Is this state undesirable or undefined or invalid ?

2) Why Q and Q' must always be complement to each other ? Is it necessary for the reason "to prevent oscillations in 1,4" ?

3) Suppose if we assume that we prevent S=R=1 and Q=Q' . But then in 7,10 why stable state(Set/Reset) not took place in next state itself ? Is this type of delay accepted ?

# Answer
In digital design we are *approximating* a digital function with a continuous function. The SR latch is one of the (many) cases where the abstraction only holds over some but not all of the possible continuous conditions.

In the case of the SR latch you need to remember that the two input signals do not transition at exactly the same time. Nor do they switch instantaneously from 0 to 1. All your questions are indeed related. The illusion of an SR latch breaks down if you look at the outputs too quickly after the inputs change, or cause the continuous (analog) circuit to oscillate, or ever get into a condition where the inputs are stable at a value close to 1/2, or get into a condition where the inputs are significantly less than 0 or greater than 1.

The 0,0 state is undesirable for several reasons. The circuit that comes next may be relying on the invariant that `Q'` = `not(Q)`. And, as you pointed out, it can lead to oscilations.

The S=R=1 input leads to a stable 0,0 output, but what happens next? If you bring S and R back down to 0 "simultaneously" any of three things could happen: (1) S could go to 0 slightly more quickly than R goes to 0, in which case it's like you did S=0, R=1, and the output will become 0,1. (2) S could go to 0 slightly slower than R goes to 0, in which case it's like you did S=1, R=0 and the output will become 1,0. (3) S and R could go to 0 sufficiently close together to make the circuit oscilate.

As to your third question about the "next state", your assumption that you are going through discrete states is not correct. You are transitioning from one state that has a stable digital interpretation to another state that has a stable digital interpretation. It takes some time for this transition to occur, and that is part of the specification of the circuit: you can't "look" at the output of the circuit too soon after the inputs change.
> 2 votes

---
Tags: computer-architecture, digital-circuits
---


# Question
Title: Proving Regularity of Languages that are 1/k of an already known regular language
There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language that is two-thirds of already known regular language is regular. I'm tempted to think that it should also hold true for any general $k\>0$ that $m/k$th ($1 \leqslant m \leqslant k-1$) portion of a regular language would also be regular. I need a mathematical proof ( or a constructive proof having mathematical verifications done on it ) for the above statement.
EDIT: For the "first half Language" which is much better formalised by David in the comments, I tried a similar argument as the answer in the link given by Hendrik. The product automaton notion was intuitively clear. But I was stuck with the transition listings for the 2nd state in the pair of states so formed by constructing the product automaton. I was flummoxed as to how I could be able to get the exact state for the corresponding word 'w' which would be the "first half" of a word accepted by the original regular language.

# Answer
> 4 votes
Let $L$ be a regular language and let $(p, q) \in \mathbb{N}^2$. Then the following language is regular: $$ L\_{p,q} = \\{ u \in A^\* \mid \text{there exist $x$ and $y$ in $A^\*$ such that $|x| = p|u|$, $|y| = q|u|$ and $xuy \in L$} \\} $$ Furthermore, for any subset $S$ of $\mathbb{N}^2$, the language $$ L\_S = \bigcup\_{(p,q,r) \in S} L\_{p,q} $$ is also regular. I would like to insist that it works for any **any** subset $S$, including non recursively enumerable subsets of $\mathbb{N}^2$, which might look a little bit suspicious at first glance...

You can try to prove these results by using automata, but it is much easier to use the fact that a language is regular iff it is recognized by a finite monoid.

Let $L$ be a regular language of $A^\*$. It is recognized by a finite monoid $M$, that is, there is a surjective monoid morphism $f:A^\* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Now $\mathcal{P}(M)$, the powerset of $M$, is also a finite monoid under the multiplication defined, for $X, Y \in \mathcal{P}(M)$, by $XY = \\{ xy \mid x \in X, y \in Y\\}$.

Let now $h: A^\* \to \mathcal{P}(M) \times M$ be the monoid morphism defined, for each letter $a \in A$, by $h(a) = (f(A), f(a))$. Then for each word $u$, $h(u) = (f(A^{|u|}), f(u))$. I claim that $L\_{p,q} = h^{-1}(Q)$ where $$ Q = \bigl\\{(R,m) \in \mathcal{P}(M) \times M \mid R^pmR^q \cap P \not= \emptyset \bigr\\}. $$ and similarly $L\_S = h^{-1}(T)$ where $$ T = \Bigl\\{(R,m) \in \mathcal{P}(M) \times M \mid \Bigl(\bigcup\_{(p,q) \in S}R^pmR^q\Bigr) \cap P \not= \emptyset \Bigr\\}. $$ Thus $L\_{p,q}$ and $L\_S$ are recognized by the finite monoid $\mathcal{P}(M) \times M$ and hence are regular.

**Proof of the claim**. \begin{align\*} h^{-1}(Q) &= \\{u \in A^\* \mid (f(A^{|u|}), f(u)) \in Q \\} \\ &= \\{u \in A^\* \mid f(A^{p|u|}f(u)f(A^{q|u|}) \cap P \not= \emptyset \\} \\ &= \\{u \in A^\* \mid f(A^{p|u|}uA^{q|u|}) \cap P \not= \emptyset \\} \\ &= \\{u \in A^\* \mid A^{p|u|}uA^{q|u|} \cap f^{-1}(P) \not= \emptyset \\} \\ &= \\{u \in A^\* \mid A^{p|u|}uA^{q|u|} \cap L \not= \emptyset \\} \\ &= L\_{p,q} \end{align\*}

# Answer
> 4 votes
Suppose we are given a regular language $L$ and integers $p, q$, and are interested in the language $M$ of all $x$ such that $axb\in L$ for some $|a|=p|x|,|b|=q|x|$.

Our starting point is an automaton for $L$. The automaton for $M$ starts by guessing two states $s, t$ of the $L$ automaton. These are supposed to be the states just before and just after reading $x$. The new automaton keeps track of the states, corresponding to the $a, x, b$ part of the purported word. They start at $s\_0,s, t$, where $s\_0$ is the initial state of the $L$ automaton. When reading a character, we update the $x$ state in the expected way. We also update the other states by guessing $p, q$ characters, accordingly. We are in an accepting state of the tracked states are $s, t, f$ for some accepting state $f$ of the $L$ automaton.

Each choice of $p, q$ controls in which possible ways we can advance the $a, b$ states. There are only a finite number of possibilities here (basically since the $L$ automaton is finite), and so we can handle arbitrary many allowed choices for the pair $p,q$, like shown in the other answer.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Why is binary search faster than ternary search?
Searching an array of $N$ elements using binary search takes, in the worst case $\log\_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'd cut away two-thirds of our search space at each iteration, so the worst case should take $\log\_3 N \< \log\_2 N$ iterations...

It seems that ternary search is faster, so why do we use binary search?

# Answer
If you apply binary search, you have $$\log\_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log\_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that: $$ 2 \cdot \log\_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log\_2(n)+ O(1) $$ Since we know that $2 \cdot \frac{\log(2)}{\log(3)} \> 1$, we actually get *more* comparisons with ternary search.

By the way: $n$-ary search may make a lot of sense in case if comparisons are quite costly and can be parallelized, as then, parallel computers can be applied.

Note that argument can be generalized to $n$-ary search quite easily. You just need to show that the function $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ is strictly monotone increasing for integer values of $k$.
> 86 votes

# Answer
DCTLib is right, but forget the math for a second.

By your logic then, ***n***-ary should be the fastest. But if you think about it, ***n***-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then you remove that item from your list, and then choose the last item in the new list, which is just the next to last value in the array. Each time, you would only be eliminating 1 value at a time until you found your value.

Instead, you should think about it like this - how do I eliminate the most values from the list each iteration? In a binary search, you always eliminate half the list. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list. in order to calculate O(n), you need to look at the worst case scenario, which is 1/3, less than 1/2. As you get closer and closer to n, it gets even worse.

Not only will the worst case scenario be improved with binary search, but your *average* time will be improved as well. Looking at expected value (what portion of the list can we remove on average), we use this formula:

$(P\_{lower}) \times \text{(portion we can remove if lower)} +(P\_{higher}) \times \text{(portion we can remove if higher)} = E$

For binary search, this is $0.5 \times 0.5 + 0.5 \times 0.5 = 0.5$ (we always remove half the list). For ternary searches, this value is $0.666 \times 0.333 + 0.333 \times 0.666 = 0.44$, or at each step, we will likely only remove 44% of the list, making it less efficient than the binary search, on average. This value peaks at $1/2$ (half the list), and decreases the closer you get to n (reverse iteration) and $0$ (regular iteration).

Ok, so I lied..there's a little math involved, but I hope that helps!
> 32 votes

# Answer
Please note the log(N) vs 2 log(N) comparisons argument is based on a naive interpretation of the algorithm. If I were to actually sit down and write this in x86 assembly the results would be inverted. The problem is the use of integers for test cases combined with an insufficiently smart compiler that can't remove the redundant comparisons. Retry with strings and an appropriate string comparison function, and code it to call the comparison function once per loop and you will find the ternary search is faster again.
> -2 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms, binary-search
---


# Question
Title: What is the difference between a problem and an algorithm?
I can say that $x * y$ is a problem, but I can also say that $x * y$ is an algorithm for finding a rectangle area.

I have been reading Wikipedia about an algorithm and a problem, but I am not sure about their definitions. Could you please explain it to me in more detail?

# Answer
"What is the product of $x$ and $y$?" is a problem, and it might model or correspond to the problem of calculating the area of a rectangle. However, how do you actually compute $x \times y$? An algorithm, informally a precise list of steps to take, for doing this would be some multiplication algorithm.

Another example, from your favorite world of satisfiability is the following *problem*.

> *Instance:* a 2-CNF formula $\phi$. *Question:* Is the formula $\phi$ satisfiable?

A method of deciding the problem is an *algorithm*, such as the truth table method (or a polynomial-time algorithm, such as the ones on Wikipedia).
> 6 votes

# Answer
A problem is a thing that needs to be done; an algorithm is a procedure for doing it.

To address your specific example, "What is $x\times y$?" is a problem and "Multiply the length by the width" is an algorithm for solving the problem, "What is the area of this rectangle?" It uses, as a subroutine, some unstated algorithm for multiplying numbers.
> 8 votes

# Answer
As Juho explained in his answer, an algorithm can be seen as a precise list of steps to solve a given problem. A consequence is that the description of the problem and of its solution frequently have to be more precise for an algorithm than for its mere mathematical formulation. Let me illustrate this difference on your example. In mathematics, you would say

**Problem**: What is the surface of a rectangle of length $x$ and width $y$?
**Answer**: $xy$

Now, depending on the size of the numbers and the way they are given, different algorithms can be proposed. In order to describe an algorithm to solve the same problem, your may need extra information on the numbers: are the numbers represented as decimal numbers or as binary numbers (as often on a computer), how many digits or bits are used to represent these numbers, etc. Next, you have to explain carefully how you perform the multiplication of two numbers. The page multiplication algorithms suggested by Juho gives plenty of examples. But again, you may need some further information: are you using a single processor or several ones? Sequentially or in parallel? Do you have any restriction on the available memory? Which kind of basic operations can your computer perform?, etc?

Thus in general, an algorithm has to include much more details than a mathematical solution.
> 3 votes

# Answer
While I do agree with the previous answers, which I will not repeat here, I feel there is a dimension that is missing, or at least left implicit. I think it should be explicited.

You could have the problem of finding the product of 222 by 333 for some purpose. In that case, all you need is an answer (73926). Why bother with complicated explanation as to why that is the product? (assuming you can trust your source for the answer)

In general, an algorithm addresses a family of problem, such as: "given two integers $x$ and $y$ (with such and such representation), how do I compute (a representation of) the product $x\times y$. The algorithm can then be used to solve all the problems in the family, one of them being the product of 222 by 333.

The interest of algorithms actually stems from the fact that they solve a whole family of problems. This is remindful of the chinese proverb "Give a man a fish he will eat for a day. Teach a man to fish he will eat for a lifetime".

The fact that algorithms address families of problems is the source of many of the concepts of the study of algorithms such as decidability (is there an algorithm that solves all the problems in the family) or complexity (what is the cost in time, memory, or some other relevant unit) of applying the algorithm, given some measure of the size of the input, i.e., of the parameters of the family.
> 0 votes

---
Tags: algorithms, terminology
---