# Question
Title: Bias or not when finding patterns using data mining techniques?
I am currently following a course on Data Mining and i am very curious about the deeper underlying method. As far as i have learned so far data mining is about finding unknown patterns that can be useful and provide new knowledge about your data.

In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case. Say if i have data for the typical example of survivors on the titanic. How would i start doing my analysis - that is: what types of questions would i be asking my self to begin with. Say if i would like to test whether the survival percentage was smaller for a male passenger, i could do some statistical analysis, and find out whether or not that would be the case. I could programme a decision tree and see what my data tells me. That would tell me HOW to use machine learning to analyse the data in order to be able to predict what chance of survival a new passenger x with specific 'properties' would have. What would the data mining perspective come into this process?

I am aware of different types of classifiers and how we can use them to check for patterns in order to do predictions, but how does one go from A (wanting to find patterns) to B (actually finding unknown patterns)) in data mining specifically?

Citing directly from the wiki page of data mining: "*Neither the data collection, data preparation, nor result interpretation and reporting is part of the data mining step, but do belong to the overall KDD process as additional steps.*" and "*Data mining is the analysis step of the "knowledge discovery in databases" process, or KDD.*"

This indicates that the actual data mining part is the analysis using mathematics, statistics and machine learning tools. Well from here, how would i start finding patterns in a large data set. Would i start from what my prior tells my could be interesting and dig deeper to see whether there actually is an interesting pattern here - and if not, i can conclude that there isn't, which in itself is insightful - and then i can try finding other patterns. OR do i make an algorithm that randomly tries to find correlations and patterns across different random combinations of attributes in my data, without me choosing ANY direction to look in? Because one thing i have been taught is that when you work with REALLY large datasets, all sorts of patterns begin to emerge, and no matter where you look, you will find some sort of patterns. The art is to find USEFUL patterns, and patterns that actually provide some kind of insight into your data! As always correlation does not necessary imply causation, but that is for the analysis part, and i guess data mining is all about just finding the patterns - so how do we actually go about and do this.

I hope my question is possible to understand. I find it hard to formulate any better. If i were to boil it all down into one sentence, it would be: If i have a large dataset which i have cleaned and prepared, then from a data mining perspective what is the following thought-process I should use to find patterns in the data?

# Answer
> In data mining, is it okay to start from expectations (bias) as to which patterns could be present and actually do statistics to see if this is actually the case

Sure. This is called hypothesis testing.

> Say if i have data for the typical example of survivors on the titanic. How would i start doing my analysis - that is: what types of questions would i be asking my self to begin with

Exploratory data analysis, see http://github.com/MartinThoma/edapy as a tool.

> how does one go from A (wanting to find patterns) to B (actually finding unknown patterns)) in data mining specifically?

You have a classification problem... So, just train the classifier you want to use.

> If i have a large dataset which i have cleaned and prepared, then from a data mining perspective what is the following thought-process I should use to find patterns in the data?

This depends very much on the context. What I happen to do at the very beginning quite often:

* Look at the general distribution of the data per single feature: min, max, mean, median, number of different values. If the number of different values is small, print a bar chart
* Null values: why are they there? Can they be replaced by a reasonable other value?
* Covariance

> What is the difference between ML and data mining?

Taken from https://stats.stackexchange.com/a/29186/25741

> Data Mining is about using Statistics as well as other programming methods to find patterns hidden in the data so that you can explain some phenomenon. Data Mining builds intuition about what is really happening in some data and is still little more towards math than programming, but uses both.
>
> Machine Learning uses Data Mining techniques and other learning algorithms to build models of what is happening behind some data so that it can predict future outcomes. Math is the basis for many of the algorithms, but this is more towards programming.
> 1 votes

---
Tags: machine-learning, data-mining, big-data
---


# Question
Title: Space complexity of boolean circuit evaluation
I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size. Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$.

Now, assuming the fan in of each vertex is at most 2, I can set 2 bits for each vertex, one for the value of the vertex, and the other for which of his sons I am currently evaluating. Where I am stuck is that I am not given any information on the fan out of each vertex, So I can't just set a value to know which parent to go back to when I finish evaluating a sub circuit.

I would like some help understanding the catch here.

thanks.

# Answer
This general question is captured by the concept of *graph pebbling*. Orient the edges of the circuit so that they point away from the leaves and toward the root. A *pebbling* of the graph is a series of moves, in the course of which pebbles are added to and removed from vertices (at most one pebble per vertex!), according to the following rules:

* A pebble can always be removed.
* A node $v$ can be pebbled (we can add a pebble to it) if all nodes $w$ such that there is an edge $w \to v$ are pebbled.

The goal is to pebble the root, and what we want to minimize is the maximum number of pebbles on the board. This minimum is called the *pebbling number* of the circuit.

If a circuit has pebbling number $p$, then it can be evaluated using roughly $p$ bits of memory. The idea is that pebbling a node corresponds to computing the its value, which is possible since all of its children are pebbled as well.

All of the above concerns the case in which the circuit is given ahead of time, and the goal is to construct a strategy to evaluate it on an unknown input. However, the same general approach can also be used to solve your problem, using the fact that the pebbling number of the complete binary tree of depth $D$ is $O(D)$. For more on pebbling, see Nordström's survey.

Finally, let me mention that the circuit evaluation problem is $\mathsf{P}$-complete. This means that assuming $\mathsf{L} \neq \mathsf{P}$, it is not possible to evaluate arbitrary circuit in logarithmic space. In contrast, the *formula* evaluation problem is in $\mathsf{ALOGTIME}$ (i.e., uniform $\mathsf{NC^1}$), and so in $\mathsf{L}$. This is due to important work of Buss.
> 1 votes

---
Tags: complexity-theory, space-complexity, circuits
---


# Question
Title: How to find a nearly-optimal covering of a set using SAT?
I have recently started thinking about application of SAT in solving different problems and how I can encode those problems into a SAT problem.

I think one of the interesting problems where SAT solvers can be used is finding a minimal representation for a logic expression. However, I have trouble encoding the problem into a SAT problem.

In very old representations of an *n*-input logic circuit, three sets `F`, `R`, and `D` are defined. `F` represents the ON-set, which corresponds to permutations of input that cause a one in the output. `R` is the OFF-set, which corresponds to permutations of input that cause a zero in the output. Finally, `D` is the DON'T CARE-set which corresponds to permutations of input where output is not specified (could be set to either one or zero during optimization).

The objective is to find a minimal conjunctive normal form (CNF) that has the minimum number of clauses and each clause has the minimum number of literals. This CNF should cover all elements of `F` and may potentially cover some elements of `D`, but should not cover any elements of `R`.

For example, assume that a 3-input function is defined in the following way:

```
A B C | Y
---------
0 0 0 | 0
0 0 1 | 0
0 1 0 | 1
0 1 1 | 1
1 0 0 | -
1 0 1 | -
1 1 0 | -
1 1 1 | -

```

where `A`, `B`, and `C` are inputs, `Y` is the output, and a `-` determines a don't care output.

In this problem, a minimal CNF that meets the objective is `O = B`, because whenever B is true, the output is either true or don't care, but never false. Without having the DON'T CARE-set, a minimal representation would be `O = ~A B`, but DON'T CARE-set has allowed a more compact representation.

Is there a method to encode this problem as a SAT problem where inputs are `F` and `R`?

# Answer
This problem is known as circuit minimization. It falls within the broad area of logic synthesis.

The problem is known to be $\Sigma\_2^P$-complete. As a result, it is unlikely to be in NP (contrary to what you wrote). And that means that it is unlikely to be solvable in polynomial time with queries to a SAT solver. (NP is basically the class of problems you can solve with a SAT solver in a single query; $P^{NP}$ is the class of problems you can solve with an unlimited number of queries to a SAT solver; and $\Sigma\_2^P$ is conjectured to be larger still, so a $\Sigma\_2^P$-complete problem is conjectured not to be in NP or $P^{NP}$.) There may still be heuristics that use a SAT solver along the way, but these heuristics either might make mistakes, might fail for some inputs, or might take exponentially long in some cases.

Anyway, there is a lot of literature on circuit minimization. As far as I know, one standard approach is to use techniques built on Quine-McClusky, Espresso, etc.

You might be interested in approaches based on interpolation. I believe those approaches use a SAT solver as a building block.
> 2 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: Using 2-opt Heuristic in a Genetic Algorithm for TSP
I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf) and I saw in the same paper that he uses the 2-opt heuristic (and the 3-opt one) on every new child, so I went ahead and did the same.

Using this definition of the 2-opt (https://en.wikipedia.org/wiki/2-opt) I implemented their following pseudo-code:

```
  repeat until no improvement is made {
       start_again:
       best_distance = calculateTotalDistance(existing_route)
       for (i = 1; i < number of nodes eligible to be swapped - 1; i++) {
           for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
               new_route = 2optSwap(existing_route, i, k)
               new_distance = calculateTotalDistance(new_route)
               if (new_distance < best_distance) {
                   existing_route = new_route
                   goto start_again
               }
           }
       }
   }

```

The problem with my class is that it takes way too much time when tested on a 51 cities instance (not to mention that 1 generation takes more than 20 minutes in the a280 instance)..

Is there a better approach to this algorithm? A faster/more robust way of improving the new children?

# Answer
> 0 votes
One optimization to your pseudo-code is to calculate the new cost of a route after performing a 2-opt move by:

```
cost = cost - d[b(i)][i] - d[i][a(i)] - d[b(k)][k] - d[k][a(k)] + d[b(i)][k] + d[k][a(i)] + d[b(k)][i] + d[i][a(k)]

```

with $b(x), a(x)$ being the node before and after node $x$ on your current route.

---
Tags: optimization, traveling-salesman, genetic-algorithms
---


title: Prove Minimum AABB Construction

text:
# Question
Title: Prove Minimum AABB Construction
Assume a point set $P\[n\]$ with $n$ points which align in one plane in the euclidean space, so $p(x,y) \in \mathbb{R}^2$. Looking for an algorithm to construct an **AABB** (*axis aligned bounding box*) I did not find anything. But I thought that the simpliest appraoch could be the best: traverse all $p \in P$ and keep track of the minimum and maximum value of each dimension. The AABB is spanned by the two points $(x\_{min},y\_{min})$ and $(x\_{max},y\_{max})$. This clearly runs in $\mathcal{O}(n)$.

Now I struggle proving this kind of obvious fact (the best algorithm runs in $\mathcal{O}(n)$). It is clear that all points of the set have to be checked for inclusion which the algorithm does, given the fact that the set is not preprocessed in any way, like ordered.

What is a good formal approach for proving this?

---

Side note: Is there a better algorithm for constructing an **AABB**?

# Answer
> 3 votes
Suppose that the points are $(x\_1,y\_1),\ldots,(x\_n,y\_n)$. You are looking for the smallest (in some sense) bounding box $\[X\_m,X\_M\] \times \[Y\_m,Y\_M\]$ containing all your points. For every $i$, we must have $X\_m \leq x\_i \leq X\_M$ and $Y\_m \leq y\_i \leq Y\_M$. In particular, $$ \begin{align\*} X\_m \leq \min\_i x\_i =: x\_{\min}, \\ X\_M \geq \max\_i x\_i =: x\_{\max}, \\ Y\_m \leq \min\_i y\_i =: y\_{\min}, \\ Y\_M \geq \max\_i y\_i =: y\_{\max}. \end{align\*} $$ Summarizing, this shows that every bounding box must satisfy $$ X\_m \leq x\_{\min} \leq x\_{\max} \leq X\_M, \\ Y\_m \leq y\_{\min} \leq y\_{\max} \leq Y\_M, $$ that is, it must contain $B := \[x\_{\min},x\_{\max}\] \times \[y\_{\min},y\_{\max}\]$. Conversely, $B$ is itself a bounding box, since $x\_{\min} \leq x\_i \leq x\_{\max}$ and $y\_{\min} \leq y\_i \leq y\_{\max}$ for all $i$. We conclude the following fact:

> $B$ is the intersection of all bounding boxes.

---
Tags: computational-geometry
---


# Question
Title: On if then condition in linear programming?
I have variables $a,b\in\mathbb R$ and if $a\>1$ I want $b=1$ or else $b=0$. Can this be encoded by linear programming (no integer variables)? Even $b\<0.5$ and $b\>0.5$ is ok.

# Answer
The if then contraints can be written equivalently as

* If $b = 0$, then $a \< 1$; and
* If $b = 1$, then $a \geq 1$.

Introduce a large number $M$ and add the following constraints:

$$b(M+1)-M \le a \< b(M+1)+1.$$

**EDIT:** I assumed that $b$ is binary. If $a$ is bounded $a\in\[L,U)$, we can write the constraints as:

$$b(-L+1)+L \le a \< b(U-1)+1.$$
> 0 votes

---
Tags: linear-programming
---


# Question
Title: What does the halting problem mean for a Babbage machine?
I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example).

The way I imagine that is **there is no finite method (i.e. algorithm) which would examine the Babbage machine, possibly by testing it, but most probably by dismantling it like a watch and concludes that it *indeed* computes logarithms**.

Would that be a correct way of thinking the halting problem on the Babbage machine?

# Answer
No. The undecidability of the halting problem for a particular model of computation means that there's no algorithm that takes as input a description of an arbitrary machine $M$ in that model and an input $x$ and determines whether $M$ halts when run with input $x$.

As a consequence, there's no algorithm that takes as input a description of a machine and determines whether that machine computes logarithms. However, that doesn't mean that you can't prove that a *specific* machine computes logarithms. Indeed, people do this all the time, as exemplified by Knuth's famous quote, “Beware of bugs in the above code; *I have only proved it correct*, not tried it” (emphasis mine). Proving the code correct requires proving that it terminates and computes the thing it's supposed to compute.
> 1 votes

# Answer
I read that the Java programming language is Turing complete.

That means, I can write a Java program such that your Turing machine would not always be able to decide, in a finite number of steps, whether my Java program would terminate after reading some arbitrary input.

It does *not* mean that *every* Java program has that property. I can trivially write a Java program that always terminates, and if I do that, then you can construct a Turing machine that always says, "yes, it halts." Or, I can write a Java program that never terminates, and you can construct a Turning machine that always says "no, it doesn't halt."

I don't know the design of Babbage's Analytic Engine, but if it is Turing complete, then that means there is at least one configuration of the engine for which you can not solve the halting problem; but it does *not* mean that *every* configuration of the engine has that property.

---

I don't know what you mean exactly by "computes the logarithm of its input." Babbage's engine was a digital machine, and logarithm is a transcendental function. No digital algorithm to compute the *true* logarithm of a given number could ever terminate. In a practical configuration of the engine, it would do what my computer's floating-point hardware does: That is, it would compute only the first *n* digits of the logarithm (for some small *n*).

I haven't tried asking my computer for the logarithms of every possible `double` value, but so far, it always has delivered a result in finite time for each of the countless millions of `double` values that I *have* tried.
> -1 votes

---
Tags: halting-problem
---


# Question
Title: Number of possible sequence partitioning
Given a sequence of 1 and 0 elements, what is the number of possible partitioning of the sequence in sub-sequences (not necessarily consecutive elements, and any number of sub-sequences are allowed) so that any sub-sequence starts and ends with a 1, and can contain an arbitrary number of 0s?

For example: Given the sequence `1 0 1 1 0 1` there are only 3 ways of partitioning the sequence:

```
1.
1 0 1
      1 0 1

2.
1 0     0 1
    1 1

3.
1 0   1
    1   0 1

```

I am pretty sure the solution implies dynamic programming, since the solution requires a fast execution time (\< 1 second).

# Answer
> 2 votes
The problem formulation is not entirely clear. This answer assumes that the allowed subsequences are of the form $10^\*1$. Other variants can be solved in a similar way.

Suppose that the original sequence is $a\_1,\ldots,a\_n$. Let $b(i,x)$ denote the number of ways to partition $a\_1,\ldots,a\_i$ into any number of subsequences of the form $10^\*1$ and $x$ subsequences of the form $10^\*$ (*open subsequences*).

Initially $b(0,0) = 1$ and $b(0,x) = 0$ for $x \> 0$. Let us now consider how to calculate $b(i+1,\cdot)$ given $b(i,\cdot)$. There are two possibilities to consider:

* If $a\_{i+1} = 0$ then a partition of $a\_1,\ldots,a\_i$ extends to a partition of $a\_1,\ldots,a\_{i+1}$ by attaching $a\_{i+1}$ to any of the open subsequences. Thus $b(i+1,x) = xb(i,x)$ in this case.
* If $a\_{i+1} = 1$ then a partition of $a\_1,\ldots,a\_i$ extends to a partition of $a\_1,\ldots,a\_{i+1}$ in one of two ways: either it "closes" an open subsequences, or it forms a new open subsequences. Thus $b(i+1,x) = (x+1)b(i,x+1) + b(i,x-1)$.

The total number of partitions is then $b(n,0)$. Since $0 \leq x \leq n$, we can compute $b(n,0)$ in time $O(n^2)$ using dynamic programming.

As an illustration, here is a run of the algorithm on the sequence $1,0,1,1,0,1$. The columns correspond to $i$, and the rows to $x$:

$$ \begin{array}{c|cccccc} x/i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline 0 & 1 & 0 & 0 & 1 & 0 & 0 & 3 \\ 1 & 0 & 1 & 1 & 0 & 3 & 3 & 0 \\ 2 & 0 & 0 & 0 & 1 & 0 & 0 & 12 \\ 3 & 0 & 0 & 0 & 0 & 1 & 3 & 0 \\ 4 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \end{array} $$

---
Tags: algorithms, dynamic-programming, subsequences
---


title: Bit errors and hamming distance

text:
# Question
Title: Bit errors and hamming distance
I'm trying to learn for my exam and had the following practice question:

*Take a code with the following code words.*

* *101100010111*
* *110001001001*
* *101110111011*

*Errors of how many bits can be corrected?*

---

The answer i received was:

*The hamming distance is: 4.*

*Therefore only single bit errors can be corrected.*

---

How did they conclude that only single bit errors can be corrected just by looking at the hamming distance?

# Answer
If you need four bit changes to change from A to B, then you can make two bit changes from A to some A' followed by two more bit changes from A' to B. If you receive A' then you don't know whether it is a double bit error coming from A, or a double bit error coming from B. Therefore, you cannot fix double bit errors.

Since four bit errors are needed to go from one valid code to another, you can detect double bit errors.

You also have the choice of either fixing single bit errors and detecting double bit errors at the same time (assuming that there will be no triple bit errors), or detecting triple bit errors. You cannot both fix single bit errors and detect triple bit errors, since I can get the same result by changing a single bit in A and changing three bits in B.
> 2 votes

---
Tags: error-correcting-codes
---


# Question
Title: Bounded Quadratic Congruence Problem Variant (for some specific Residue)
**Given:** 3 positive integers $a,b,L$. **Problem:** Is there a positive integer $x\<L$ such that $x^2≡ a(mod\ b)$?

The above problem is **NPComplete** (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Is there some specific value of $a$ (say $a\_0$) such that, if we limit the original problem (the residue) to only $a\_0$, the problem ceases to be **NPComplete** (and much easily solvable than the generic case) ?

My guess is for any/each specific $a\_0$ the problem still remains **NPComplete** but I am not certain. Anyone please ?

# Answer
Yes. If $a=1$, the problem is no longer NP-complete; the answer to the problem is always "yes, there is such a positive integer".
> 1 votes

---
Tags: complexity-theory
---


title: Minimal date interval cover algorithm

text:
# Question
Title: Minimal date interval cover algorithm
The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. Here is the problem: given a collection of filtered date intervals, find a minimal collection of such intervals that cover exactly the same set of dates.

Initially, I naively assumed that this can be solved by sorting the intervals by start dates and merging consecutive intervals, if possible. Here is a counterexample to this approach. Consider the date interval given by the pattern $56712345671234$, where each number stands for a day of week. Assign zero-based indices to the dates in this pattern. The set of dates covered by intervals $\\{0-2, 567\\}$, $\\{3-9, 1234\\}$, $\\{10-13, 12\\}$ can be covered by the collection $\\{0-6, 1234567\\}, \\{7-13, 12\\}$. The merging algorithm will fail to merge any intervals and will output three intervals as the minimal cover instead of two.

Is there a well-known algorithm for this problem? Can it be solved in $O(n \log n)$ where $n$ is the number of input intervals?

# Answer
> 2 votes
This can be solved in $O(n \log n)$ time by a greedy algorithm. Take the earliest week you need to cover (that isn't covered yet). Pick the set of days-of-the-week that you need to cover in that week. Choose a filtered data interval that starts with that week, uses that mask, and extends as far as possible. Add that to your collection, and repeat.

I'll let you work out the proof that it is correct, via an exchange argument. How to prove greedy algorithm is correct may be helpful.

To make this run efficiently with a $O(n \log n)$ worst-case time, you'll need a proper data structure for storing the filtered intervals and figuring out how far you can extend an interval. I'll let you figure that out, but a hint: a balanced binary search tree provides $O(\log n)$ running time for all basic operations.

---
Tags: algorithms, algorithm-analysis, time-complexity, optimization, asymptotics
---


# Question
Title: Is every PSPACE-complete problem complete with respect to logspace reductions?
A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in *logspace*, i.e. for any $A \in \mathsf{PSPACE}$, $$ A \le\_L TQBF. $$ (See for example, comment at the end of section 7.4 in these notes.) Therefore, TQBF is complete with respect to logspace reductions. It is still possible, however, that there are some other standard PSPACE-complete problems for which this is not true. Of course, the problem would reduce in logspace to TQBF, but maybe the reduction the other way would not go through.

**Question:** If $A$ is PSPACE-complete, must $A$ be complete with respect to logspace reductions? In other words, if $A \in \textsf{PSPACE}$ and $TQBF \le\_p A$, then must $TQBF \le\_L A$?

---

**Some thoughts:**

I tried the generalized geography problem, and it seems to be true in that case. I'm not sure about universality for NFAs.

To prove it, the most straightforward idea would be to show that if $A \le\_p B$ and $B \le\_L A$, then $A \le\_L B$. But this is false for general $A, B$, assuming $\mathsf{L} \ne \mathsf{P}$. In particular, take $A \in \mathsf{P}$ and $B = \varnothing$.

# Answer
If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$.

To see why, suppose for the purpose of contradiction that the definition of completeness remains unchanged when replacing polynomial time with logspace reductions, and simultaneously $\mathsf{P=PSPACE}$. Since $\mathsf{P=PSPACE}$, every nontrivial language in PSPACE is complete under polynomial time reductions, e.g. undirected connectivity which lies is $\mathsf{L}$. Seeing that we assumed that polynomial time completeneess is equivalent to logspace completeness, undirected conectivity is also PSPACE complete under logspace reductions, which implies $\mathsf{L=PSPACE}$, contradicting the space hierarchy theorem.

This question is probably still open (though I am unaware of any important/strange implications of the negation of your statement). You can find similar discussions about NP-completeness, where it appears the same question is also open.
> 8 votes

---
Tags: complexity-theory, reductions, complexity-classes, space-complexity
---


# Question
Title: Applying a multi qubit quantum gate to specific qubits
A controlled not gate matrix looks like this:

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}$$

That works great when you only have two qubits and you want to use the first qubit as the control, and the second qubit as the input to be flipped (or not).

Is there a method to convert this matrix to use for instance if you had 3 qubits, and wanted to use qubit 1 as the control and qubit 3 as the input that is possibly flipped?

Thinking about it logically, I can come up with this:

$$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}$$

Is there a better, more formal/generalized way to convert multi qubit gates to use any specified qubits, rather than the first $N$ in an $N$ qubit circuit?

# Answer
> 8 votes
# Expand-n-Swap

If you want to apply a gate to a subset of the qubits:

It can be tedious to do all those large matrix multiplications, but swap matrices are sparse and the idea is very straightforward.

# Controls are Easier

In the case of adding controls to an operation (which applies to the specific example you gave), there's an easier trick. Just expand the operation like normal, but then replace any parts of the matrix that correspond to control-failed inputs with what the identity matrix would be.

This is a bit easier to keep track of if you introduce a fake "control value" $c$ that overrides the tensor product's usual behavior, so that instead of $\begin{bmatrix} c \end{bmatrix} \otimes U = c \cdot U$, you have $\begin{bmatrix} c \end{bmatrix} \otimes U = c \cdot I$ (in other words: when an entry is $c$ you don't tile $U$ over the entry and scale $U$ by the entry; you use $I$ instead of $U$).

Define the "operation" of a qubit-must-be-ON control to be $C = \begin{bmatrix} c&0 \\ 0&1 \end{bmatrix}$. A no-op is $I$, and a NOT is $X$. Then the operation from your question could be computed like this (assuming big-endian order):

$CNOT\_{3 \rightarrow 1} = C \otimes I \otimes X$

$= \begin{bmatrix} c&0 \\ 0&1 \end{bmatrix} \otimes \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} \otimes \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}$

$= \begin{bmatrix} c\otimes\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix}&0\otimes\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} \\ 0\otimes\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix}&1\otimes\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} \end{bmatrix} \otimes \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}$

$= \begin{bmatrix} \begin{bmatrix} c&0 \\ 0&c \end{bmatrix} & \begin{bmatrix} 0&0 \\ 0&0 \end{bmatrix} \\ \begin{bmatrix} 0&0 \\ 0&0 \end{bmatrix}&\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} \end{bmatrix} \otimes \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}$

$= \begin{bmatrix} c&0&0&0 \\ 0&c&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \end{bmatrix} \otimes \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}$

(note: going to use a single zero to ambiguously mean a 2x2 zero matrix where convenient)

$= \begin{bmatrix} c\otimes \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} &0&0&0 \\ 0&c \otimes \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}&0&0 \\ 0&0&\begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}&0 \\ 0&0&0&\begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} \end{bmatrix}$

$= \begin{bmatrix} \begin{bmatrix} c&0 \\ 0&c \end{bmatrix} &0&0&0 \\ 0&\begin{bmatrix} c&0 \\ 0&c \end{bmatrix}&0&0 \\ 0&0&\begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}&0 \\ 0&0&0&\begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} \end{bmatrix}$

$= \begin{bmatrix} c&0&0&0&0&0&0&0 \\ 0&c&0&0&0&0&0&0 \\ 0&0&c&0&0&0&0&0 \\ 0&0&0&c&0&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&0&0&1 \\ 0&0&0&0&0&0&1&0 \end{bmatrix}$

(now we're done with the tensor products and don't need the $c$'s anymore)

$\rightarrow \begin{bmatrix} 1&0&0&0&0&0&0&0 \\ 0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&0 \\ 0&0&0&1&0&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&0&0&1 \\ 0&0&0&0&0&0&1&0 \end{bmatrix}$

Make sense?

# Answer
> 9 votes
Don't use the swap method, it's very inefficient. And the other person's answer is specific to the CNOT gate, and to be frank, over-complicates things.

Here's a very simple algorithm that solves your problem for every single case, not just the CNOT gate, for any arbitrary bits.

The algorithm:

```
let sys = matrix representing the current state of the system
let n = number of qubits being simulated
let lgm = logic gate matrix of size 2^n by 2^n
let f = our logic gate transformation function
for i = 0 to (2^n) - 1:
    lgm[column = i] = f(i)
sys = sys × lgg

```

In classical computers, there's something known as the "decoder". Let's say I have only 3 wires, effectively, 3 bits. But I want to control 8 wires. Can that be done? Yes, because 3 bits has 8 different possibilities: 000, 001, 010, 011, 100, 101, 110, 111. So we can assign each possibility to one of our 8 output wires. This is called "decoding".

If I pass in the number 101 and we have 3 bits, we know 101=5, so then I will be setting output wire 5 to a high voltage and the other 7 output wires will be 0, which we can represent like this: decode(101) = \[0, 0, 0, 0, 0, 1, 0, 0\].

In this algorithm, I mention the "transformation function" called "f". For classical computers, the transformation function is just taking in an input value and returning the "decoded" version of the output value. So if we have 3 bits, and the output is 4, then we will be returning \[0, 0, 0, 0, 1, 0, 0, 0\]. We then assign that as the column of our matrix for that value.

Let's think of "decoding" in terms of qubits. How can we decode the qubits |101\>?

We know that for our qubit probability vectors, |0\> is \[1, 0\] and |1\> is \[0, 1\]. Decoding qubits can then be done what's called the Kronecker product.

So if we convert each bit to the probability vector equivalent and take the Kronecker product of all of them, we get...

```
|101> = |1> ⊗ |0> ⊗ |1> = [0, 1] ⊗ [1, 0] ⊗ [0, 1] = [0, 0, 0, 0, 0, 1, 0, 0]

```

This is how we'd want to decode qubits. This algorithm can be applied to qubits just the same using this.

**Let's try this algorithm on a simpler problem.**

Let's assume we have a system with only 2 qubits. If we want to apply the Hadamard gate to just 1 qubit, we can generate a logic gate for both qubits that only applies the Hadamard gate to a single qubit. Let's assume the single qubit we want to apply it to is our most significant qubit and the least significant will be unaffected.

We want a transformation function that for each of our possible inputs, produces the correct output. We have two qubits, this means there are four possible outputs.

```
f(|00>) = ?
f(|01>) = ?
f(|10>) = ?
f(|11>) = ?

```

We know the least significant qubit will be unaffected, so we can fill that in.

```
f(|00>) = ? ⊗ |0>
f(|01>) = ? ⊗ |1>
f(|10>) = ? ⊗ |0>
f(|11>) = ? ⊗ |1>

```

We also know what the Hadamard does to a qubit, such that:

```
H(|0>) = 1/sqrt(2)|0> + 1/sqrt(2)|1>
H(|1>) = 1/sqrt(2)|0> - 1/sqrt(2)|1>

```

So our transformation function is simply:

```
f(|00>) = (1/sqrt(2)|0> + 1/sqrt(2)|1>) ⊗ |0>
f(|01>) = (1/sqrt(2)|0> + 1/sqrt(2)|1>) ⊗ |1>
f(|10>) = (1/sqrt(2)|0> - 1/sqrt(2)|1>) ⊗ |0>
f(|11>) = (1/sqrt(2)|0> - 1/sqrt(2)|1>) ⊗ |1>

```

Expand this out to our normalized probability vector form...

```
f(|00>) = [ 1/sqrt(2), 1/sqrt(2) ] ⊗ [ 1, 0 ]
f(|01>) = [ 1/sqrt(2), 1/sqrt(2) ] ⊗ [ 0, 1 ]
f(|10>) = [ 1/sqrt(2), -1/sqrt(2) ] ⊗ [ 1, 0 ]
f(|11>) = [ 1/sqrt(2), -1/sqrt(2) ] ⊗ [ 0, 1 ]

```

Now let's actually solve this...

```
f(|00>) = [ 1/sqrt(2), 0, 1/sqrt(2), 0 ]
f(|01>) = [ 0, 1/sqrt(2), 0, 1/sqrt(2) ]
f(|10>) = [ 1/sqrt(2), 0, -1/sqrt(2), 0 ]
f(|11>) = [ 0, 1/sqrt(2), 0, -1/sqrt(2) ]

```

That's our transformation function.

Our logic gate matrix, "lgm", is of size 2^n by 2^n where n = number of qubits being simulated, so in this case it's 2^2 by 2^2 or 4x4. Our algorithm tells us that for each column i, set the column equal to f(i). We've defined our probability transformation function, so we can easily fill out these columns.

```
lgm =
    |00>       |01>        |10>        |11>
[ 1/sqrt(2),         0,  1/sqrt(2),          0 ]
[         0, 1/sqrt(2),          0,  1/sqrt(2) ]
[ 1/sqrt(2),         0, -1/sqrt(2),          0 ]
[         0, 1/sqrt(2),          0, -1/sqrt(2) ]

```

Now the final step in our algorithm is simply matrix-multiplying our matrix representing the entire quantum system, sys, by this logic gate, lgm.

And that does what we want. It will apply the hadamard gate only to the most qubit and leave the least significant qubit alone. If you don't believe me, you can try it yourself and see that it works.

The reason this is so powerful is because it applies to any case.

**Let's try this algorithm on your problem.**

Imagine we have a 3 qubit system and we want to apply a CNOT gate to qubit\[0\] and qubit\[2\]. If you look up the CNOT matrix on Wikipedia, that matrix only applies to a 2-qubit system. A naive solution would be to append identity matrices to it using the Kronecker product to make it work on systems with three qubits. But this fails here: qubit\[0\] and qubit\[2\] are not adjacent, so simply appending identity matrices won't work.

We *could* swap qubit\[0\] with qubit\[1\], apply the CNOT gate, then swap them back. But that's slow. Instead, we could simply generate a non-adjacent CNOT gate for our problem using the algorithm above.

We first need to come up with a transformation function for each case.

```
f(|000>) = |0> ⊗ |0> ⊗ |0>
f(|001>) = |0> ⊗ |0> ⊗ |1>
f(|010>) = |0> ⊗ |1> ⊗ |0>
f(|011>) = |0> ⊗ |1> ⊗ |1>
f(|100>) = |1> ⊗ |0> ⊗ |1>
f(|101>) = |1> ⊗ |0> ⊗ |0>
f(|110>) = |1> ⊗ |1> ⊗ |1>
f(|111>) = |1> ⊗ |1> ⊗ |0>

```

If you understand the CNOT gate, you can understand why this is our function. Think of this like a truth table. Since our control qubit is the most significant qubit, qubit\[2\], only when that qubit is |1\> will the least significant qubit, qubit\[0\], be negated.

Expand this out to our normalized probability vector form...

```
f(|000>) = [ 1, 0 ] ⊗ [ 1, 0 ] ⊗ [ 1, 0 ]
f(|001>) = [ 1, 0 ] ⊗ [ 1, 0 ] ⊗ [ 0, 1 ]
f(|010>) = [ 1, 0 ] ⊗ [ 0, 1 ] ⊗ [ 1, 0 ]
f(|011>) = [ 1, 0 ] ⊗ [ 0, 1 ] ⊗ [ 0, 1 ]
f(|100>) = [ 0, 1 ] ⊗ [ 1, 0 ] ⊗ [ 0, 1 ]
f(|101>) = [ 0, 1 ] ⊗ [ 1, 0 ] ⊗ [ 1, 0 ]
f(|110>) = [ 0, 1 ] ⊗ [ 0, 1 ] ⊗ [ 0, 1 ]
f(|111>) = [ 0, 1 ] ⊗ [ 0, 1 ] ⊗ [ 1, 0 ]

```

Now let's actually solve this...

```
f(|000>) = [ 1, 0, 0, 0, 0, 0, 0, 0 ]
f(|001>) = [ 0, 1, 0, 0, 0, 0, 0, 0 ]
f(|010>) = [ 0, 0, 1, 0, 0, 0, 0, 0 ]
f(|011>) = [ 0, 0, 0, 1, 0, 0, 0, 0 ]
f(|100>) = [ 0, 0, 0, 0, 0, 1, 0, 0 ]
f(|101>) = [ 0, 0, 0, 0, 1, 0, 0, 0 ]
f(|110>) = [ 0, 0, 0, 0, 0, 0, 0, 1 ]
f(|111>) = [ 0, 0, 0, 0, 0, 0, 1, 0 ]

```

Let's make these the columns of our lgm matrix.

```
lgm =
[ 1, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 1, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]
[ 0, 0, 0, 0, 1, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 1 ]
[ 0, 0, 0, 0, 0, 0, 1, 0 ]

```

Now if the matrix-multiply our entire system matrix, sys, by our logic gate matrix, lgm, our result will be the effect of applying the CNOT gate to qubit\[2\] and qubit\[0\] where qubit\[2\] is the control qubit.

---
Tags: quantum-computing
---


# Question
Title: Where did Don Knuth say that suffix trees were the "Algorithm of the Year 1973?"
If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this.

Is there a reference to a paper, communication, etc. where Knuth specifically says this about suffix trees?

# Answer
The source of the quote seems to be From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction by Giegerich and Kurtz.

On page 347, at the start of Section 6 (An Explanation of Weiner's Algorithm), they write

> In this section we go back to the roots and take a look at the “Algorithm of the Year 1973” (D. E. Knuth according to \[19\]).

Reference \[19\] is an unpublished manuscript:

> \[19\] V.R. Pratt. Improvements and Applications of the Weiner Repetition Finder. Unpublished manuscript, Cambridge, MA, 1973.

Apparently these are lecture notes (this is how they are referred to in the monograph Image and Text Compression by Storer).
> 7 votes

---
Tags: reference-request, suffix-trees
---


title: Is Turing machine is robust?

text:
# Question
Title: Is Turing machine is robust?
Is Turing machine is robust ? if it solved with one tape, can it solved with multi-tape? I know that TM is robust but i can't understand why

# Answer
If you can solve it with one tape, you can solve it with multiple tapes by just ignoring all but the first tape.

The other direction is covered by Universal simulation of Turing machines.
> 3 votes

---
Tags: complexity-theory, turing-machines
---


# Question
Title: In what case would bi-directional BFS have a worse asymptotic run time than regular BFS?
I am trying to prove that bidirectional BFS could have a worse run time than regular BFS. I am confused on how this would be possible, considered bidirectional BFS always divides the run time in two, since it is executing two searches. Would a specific order of nodes and vertices have to take place in order to give bidirectional a worse running time? Or is it a quantity issue?

Edit: Here is a graph I made. I'm assuming bi-directional BFS would infinitely search in this instance because if search one went right, and search two went left, they wouldn't find a path. Then, search one would go left, and search two would go right. Doesn't this mean that the search would run infinitely, because it doesn't stop until both have found the same path?

# Answer
When attempting to find a path from a source vertex $s$ to a target vertex $t$, with both BFS and bi-directional BFS, if you assume a fairly steady branching factor $b$, the number of possibilities checked (and hence the running time) is dependent on the depth. For BFS the depth is the distance from the source to the target, giving $b^{k}$ vertices visited, for bi-directional BFS the two searches meet in the middle, so it's two lots of half-distance searches - $2\cdot b^{k/2} = 2\cdot\sqrt{b^{k}}$, which is clearly better.

So to get a worse time, you need a route from $s$ to $t$ that traverses very few vertices, but the route from $t$ to $s$ would visit many vertices. Essentially you want an asymmetric branching factor.

The family of star graphs would be sufficient for this. A star graph has a single central vertex, and all other vertices are connected directly to it, and no other vertices. So if you have $s$ as one of the pendent vertices, and $t$ as the central vertex, normal BFS would take constant time, and bi-directional BFS would take linear time. You can also invent more complicated examples that share this property of a low branching factor going one way, but a high one coming the other (up to a point).
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is the language of all deciders recognizing empty language decidable?
I TA for a course in theory of computation and this came up as an interesting question.

$E\_{TM}$ is the set of TM descriptions where the machine's language is empty.

Of course, $E\_{TM}$ is undecidable for arbitrary TMs (as well as $A\_{TM}$).

Now suppose we restrict our attention to *decider* TMs (ones that always halt).

$A\_{decider}$ is the set of TM *decider* descriptions and strings such that the TM accepts that string, and $E\_{decider}$ is the same as $E\_{TM}$ except for deciders.

Of course, $A\_{decider}$ now is decidable because we just simulate the decider on the input, and it will always stop.

Is $E\_{decider}$ decidable now, or does it remain undecidable? The reduction to show that $E\_{TM}$ was undecidable originally goes in the wrong direction here.

# Answer
$E\_{decider}$ is even unrecognizable.

Suppose a TM $E$ recognizes $E\_{decider}$, we construct a TM $N$ recognizing $\overline{H}=\\{\langle\langle M\rangle, w\rangle\mid M(w) \text{ doesn't halt}\\}$, which is known as unrecognizable, thus a contradiction. $N$ works as follows.

On input $\langle\langle M\rangle, w\rangle$:

1. Construct a TM $M\_w$ working on input $x$ as follows

1. Run $M$ on $w$ with at most $|x|$ steps.
    2. If $M$ halts, *loop*; otherwise, *reject*.
2. Run $E$ on $\langle M\_w\rangle$.
3. If $E$ accepts, *accept*; otherwise, *reject*.

If $M$ halts on $w$, then there exists some $x$ such that $M\_w$ does not halt on $x$, which means $M\_w$ is not a decider. Therefore $E$ does not accept $M\_w$, so $N$ does not accept $\langle\langle M\rangle, w\rangle$.

If $M$ does not halt on $w$, then $M\_w$ halts and reject any string $x$. Therefore $E$ accepts $M\_w$, so $N$ accepts $\langle\langle M\rangle, w\rangle$.

Now the proof is complete.

---

In addition, your argument about $A\_{decider}$ is wrong, because the TM in input may not be a decider and you should reject (not loop) on such case. In fact, you can prove $A\_{decider}$ is also unrecognizable using similar technique.
> 1 votes

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


# Question
Title: How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?
You are given n integers $a\_1, \ldots, a\_n$ all between $0$ and $l$. Under each integer $a\_i$ you should write an integer $b\_i$ between $0$ and $l$ with the requirement that the $b\_i$'s form a non-decreasing sequence. Define the deviation of such a sequence to be $\max(|a\_1-b\_1|, \ldots, |a\_n-b\_n|)$. Design an algorithm that finds the $b\_i$'s with the minimum deviation in runtime $O(n\sqrt\[4\]{l})$.

I honestly have no clue whatsoever how to even begin to solve this question. It looks like a dynamic programming question to me, but the professor said that this should be solved using a greedy algorithm. It would be much appreciated if someone can point me in the right direction by giving a small hint.

# Answer
Let's start with the following observation:

> Let $max$ denote the maximum of the sequence $a\_1,...,a\_n$, and let $min$ denote its minimum. If $a\_1=max$, then choosing $b\_1=b\_2=...=b\_n=\lfloor(max+min)/2\rfloor$ is optimal.

Why is this the case? Well, since the sequence starts with the maximum, either we choose $b\_1$ large, and suffer a large deviation from the minimum of the sequence (since any subsequent $b\_i$ must be greater or equal to $b\_1$), or we choose $b\_1$ small and suffer from the deviation to $max$. The average minimizes the maximal deviation.

We can now try to generalize this observation to use on general sequences $a\_1,...,a\_n$. For instance, we can partition any sequence into subsequences, such that each begins with the maximum of the respective subsequence.

> Example: $(2,6,4,1,5,2,8,7,5,1)$ is partitioned into $(2)$, $(6,4,1,5,2)$, and $(8,7,5,1)$.

Given this partitioning, we can now solve each these subsequences separately, and obtain an assignment of the $b\_i$'s, which however might violate the non-decreasing condition. This can be fixed without losing optimality.

Observe that the last subsequence always contains the maximum $max$ of the whole sequence (otherwise, there would be another subsequence after it). Let $w\_1,w\_2,...,w\_k$ be the values we assigned to the $k$ subsequences. Now, to achieve non-decreasingness in $w\_1,...,w\_k$, we start from the back at $w\_k$ and work our way to the front. If $w\_{k-1}$ is larger than $w\_k$, we simply set $w\_{k-1}:=w\_k$. If it is smaller, we keep it. Then, we proceed with comparing $w\_{k-2}$ with $w\_{k-1}$ and so on. Note that lowering any $w\_i$ to the value of $w\_{i+1}$ never increases the deviation, since the maximium value in the subsequence assigned with $w\_i$ is always lower than the maximum in the subsequence assigned with $w\_{i+1}$.

This algorithm should be correct, I think. Concerning the running time, the key step is computing the increasing maxima for the subsequences, which is possible in $O(n)$? Not sure where $l$ contributes.
> 9 votes

# Answer
I'm going to think out loud here just working through the hints you've given. Let's go to the original hint of saying that $O(nl)$ is what you should try first. I can think of a greedy algorithm that has that time.

The $l$ part of the time complexity means you can keep a list of the count of each occurence of each value $0..l$. That, is just create a set $\text{Count} = { C\_0, \ldots, C\_l} $ which tracks the count of each $l$ in the set. You can create the initalize list by scanning the input sequence once.

You can scan this list in $O(l)$ to get the maximum and minimum value. If you were to fill the entire list of $b$ with this mid-point your variance would simply be the difference from this value and the max/min. This is basically your worst-case scenario, let's call it $b\_w$.

So work your way to $b\_i$ from the left. You can both drop this elemeent from $\text{Count}$ and get the min/max of $b\[i+1\] \ldots b\[n\]$ in $O(l)$. Now we can be greedy. We don't choose $b\_i \> b\_w$ since that forces the remaining entire list up (to meet the non-decreasing requirement) and thus increases the variance. The minimum value we can choose is $b\[i-1\]$. If $a\_i$ is in the acceptable range we select it, if below the range than use the minimum. This minimizes the variance at $b\_i$ given known constraints.

This is just an idea, perhaps I'm lucky and it points you in the right direction. This algorithm may not work (it does for my few simple tests), but it does match the hints given, so perhaps it is helpful. If correct it is easy to see that the $O(l)$ part can for sure be dropped to $O(\log l)$, about even further, I'm not sure.
> 2 votes

# Answer
Here is the professor's solution, which he calls "reduction": For each $i$ from $0$ to $l$, try to construct a solution if we know that the deviation is less than or equal to $i$. The first $i$ for which a solution can be found is the minimum deviation. We can find a solution given the deviation in $O(n)$ time. So the running time is $O(nl)$. Then, instead of using linear search, we can use binary search to determine the smallest deviation for which a solution is possible. This reduces the running time to $O(n\log l)$, which satisfies the requirement of $O(n\sqrt\[4\]{l})$.
> 2 votes

# Answer
I think this should be doable in O (n).

Take the similar problem: Given $a\_i$, 1 ≤ i ≤ n, and d ≥ 0, find $b\_i$ in non-descending order such that $|a\_i - b\_i| ≤ d$ for all i, or show that it isn't possible. This can be done in O (n), and using binary search the original problem is solved in O (n log l).

Now if there are i ≤ j such that a\_i - a\_j \> 2d, then there is no solution (because $b\_i ≥ a\_i - d, b\_j ≤ a\_j + d \< a\_i - 2d + d = a\_i - d ≤ b\_i$).

But if a\_i - a\_j ≤ 2d for all i ≤ j then I think a solution will always be found. So all we have to do is find m = max (a\_i - a\_j) for all i ≤ j, and choose d = floor ((m+1) / 2). That maximum can be found in O (n).
> 0 votes

---
Tags: algorithms, optimization, greedy-algorithms, subsequences
---


# Question
Title: What is difference between architecture and microarchitecture?
I am studying computer architecture. I would like to know the difference between the terms "computer architecture" and "microarchitecture".

# Answer
> 10 votes
The term *architecture* was popularized by the paper "Architecture of the IBM System/360", *IBM Journal of Research and Development*, 8(2):87-101, April 1964 by Gene M Amdahl, Gerrit A Blaauw, and Frederick P Brooks, Jr. They say,

> The term *architecture* is used here to describe the attributes of a system as seen by the programmer, i.e., the conceptual structure and functional behavior, as distinct from the organization of the data flow and controls, the logical design, and the physical implementation.

According to the Wikipedia page on computer architecture the terminology was probably introduced inside IBM in 1959.

Today we would use the term *instruction set architecture* to describe the syntax and semantics of the interface of a computer, including the type and size of the operands, programmer visible register state, the memory model, how interrupts and exceptions are handled, the available instructions and the meaning of each instruction. The instruction set architecture is the boundary between software and hardware, and is the contract between the programmer and the hardware designer.

The term *microarchitecture* is used to refer to the organization, or highest level of implementation, of a particular processor. The study of microarchitecture would include topics like pipelining, instruction-level parallelism, out-of-order execution, speculative execution, branch prediction and caching.

I'm not sure about the etymology of *microarchitecture*. I can find it used as early as 1975 (in the title of the EUROMICRO Workshop on the Microarchitecture of Computer Systems), but it could certainly be older than that.

Currently the term *computer architecture* or just *architecture* typically encompasses both instruction set architecture and microarchitecture, as well as broader system-level issues like network connectivity on multiprocessors.

# Answer
> 2 votes
Computer architecture is the combination of microarchitecture and instruction set.

Microarchitecture, also called computer organization and sometimes abbreviated as µarch or uarch, is the way a given instruction set architecture (ISA), is implemented in a particular processor.A given ISA may be implemented with different microarchitectures;implementations may vary due to different goals of a given design or due to shifts in technology.

Source : https://en.wikipedia.org/wiki/Microarchitecture

---
Tags: terminology, computer-architecture
---


# Question
Title: Is there a language that can be Turing-reduced from all languages?
I don't think so, because $A\_{TM} = \\{\<M,w\>\mid \text{M accepts w}\\}$ is not Turing-decidable. Is this the right way to think about?

# Answer
No. If there exists such a language, say $\Omega$, then for any language, there exists a TM $M\_L$ with the ability to query to $\Omega$ that recognizes $L$, and obviously the mapping from $L$ to $M\_L$ is an injection. However, the set of languages are uncountable while the set of TMs are countable, which leads to a contradiction.
> 2 votes

# Answer
I assume you're asking if there's a language $\Omega$ such that, for all $L\subseteq\\{0,1\\}^\*$, $L\leq\_T\Omega$. In that case, the answer is “no.”

For any language $\Omega$, the languages that Turing-reduce to $\Omega$ are those that can be decided by a Turing machine with an oracle for $\Omega$. For brevity, I'll say “$\Omega$-Turing machines” instead of “Turing machines with an oracle for $\Omega$.” $\Omega$-Turing machines are at least as powerful as ordinary Turing machines (exactly as powerful, if $\Omega$ is decidable; strictly more powerful of it isn't).

The same argument that shows the undecidability of the ordinary Turing machine halting problem also shows that any machine model that is at least as powerful as Turing machines can't decide its own halting problem. So, in particular, no $\Omega$-Turing machine can decide the halting problem for $\Omega$-Turing machines. In other words, for any language $\Omega$, the halting problem for $\Omega$-Turing machines isn't Turing-reducible to $\Omega$.

This means that there's no “hardest language” (or class of languages) to which all languages are Turing-reducible. This is related to the concept of Turing degrees, which form an infinite hierarchy of ever more difficult languages: start with the decidable languages, then the languages decided by Turing machines with an oracle for the halting problem, and then iterate by making each subsequent level be the languages decided by Turing machines with an oracle for the halting problem corresponding to the previous level.
> 2 votes

---
Tags: computability, reductions
---


# Question
Title: Computation time of a Binom matlab (or C) routine
I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum\_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$). I am trying to figure out the following:

> 1. I need to know, if it shoud work for large numbers: i.e. K=501000, N=10^6, P=0.5
> 2. Is there a way to calculate how long the computation takes?

Maybe it is possible to perform a computer routine that calculates an approximation? Like Poisson Probability

# Answer
If you can avoid it, you don't want to compute sums like that at all.

1. If you compute terms like $p^k$ directly, you'll get big errors due to floating-point precision (because your result will be almost zero).

If you haven't seen it, one common way to handle small probabilities is to apply the logarithm trick:

$\qquad \displaystyle p^k(1-p)^{n-k}\ \leadsto\ k \cdot \log p + (n-k) \cdot \log(1-p)$.
2. If possible, apply well-known closed forms for sums to eliminate them entirely. Computing *that* is less problematic, both in terms of numerical issues and running time.
3. Failing that, find an approximation that you can tune to the required precision.

And also:

* Computing running times with an algorithm is not computable in general. You will have to apply algorithm analysis yourself. After implementing an actual algorithm, that is. See a good textbook or our reference questions for starters.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, numerical-algorithms
---


title: Decide whether this language is regular

text:
# Question
Title: Decide whether this language is regular
Decide whether the language $L$, defined by the following grammar is regular or not:
$S \rightarrow aab$
$S \rightarrow aacSb$
$S \rightarrow acSab$
$S \rightarrow acSacSb$
Where should I start?
I have tried defining a new language $L' = \\{(aac)^n\ w\ b^n | w \in L\\}$, which should be non-regular, because of dependency on $n$ with different left and right sides and since $L' = L$, $L$ has to be non-regular too, but I'm not sure whether this technique is valid.

# Answer
> 1 votes
The first step is to show that $$ L \cap (aac)^\*aabb^\* = \\{ (aac)^n aab b^n : n \geq 0 \\}. $$ Given that, you argue as follows: If $L$ were regular, then $L \cap (aac)^\*aabb^\*$ would also be regular. You can show in various ways that $\\{ (aac)^n aab b^n : n \geq 0 \\}$ isn't regular. It follows that $L$ isn't regular.

---
Tags: regular-languages, context-free, chomsky-hierarchy
---


# Question
Title: Minimum number of vertices whose removal makes the graph an independent set
It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W\[1\]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent set of size greater than equal to $k$.

I was looking at the complementary problem - "**Whether or not removal of at most $k$ vertices from a graph can make the resulting graph an independent set**".

> If the input graph $G$ contains a set $W$ of size at most $k$ for which $V(G)\setminus W$ is independent set, then it can be found in $2^{O(k \log k)}\cdot n^{O(1)}$ time as follows:
>
> 1. Since vertices of independent set have degree at most $k$, we first remove from $G$ all vertices whose degree is more than $k$.
> 2. There are now only $k^2$ edges in the current graph.
> 3. Let $A$ be set of all vertices on which at least one edge is incident, then $V(G)\setminus A$ is an independent set of size at least $(n-2k^2)$.
> 4. So $W$ must be contained in set $A$ whose size is at most $2k^2$. We can scan over all ${2k^2}\choose{k}$ subsets of A to check removal of which set makes the graph an independent set.

My question is does the new problem has $2^{O(k)}\cdot n^{O(1)}$ time algorithm?

# Answer
Since complement of vertex cover is independent set, and there is $2^{O(k)}\cdot n^{O(1)}$ time algorithm for finding vertex cover of size at most $k$, it will imply $2^{O(k)}\cdot n^{O(1)}$ time algorithm for the problem considered.
> 1 votes

# Answer
Yes, and the algorithm is straight forward branching.

Suppose that you are given a graph $G$ and an integer $k$. If $k = 0$, we simply return whether $G$ is an independent set. If $G$ is an independent set, we return "yes". Otherwise, we branch. If there is an edge $uv$ in $G$, we recurse on $G-u, k-1$ and $G-v, k-1$. Since the budget drops with one for every recursive call, we call ourselves at most $2^k$ times.

The correctness is left as an exercise.
> 2 votes

---
Tags: algorithms, np-hard, clique, parameterized-complexity
---


# Question
Title: Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)
When proving a language is non regular we can use Kolmogorov complexity.

As far I know to do this we just have to use this satisfy the following conditions

Given $Y^A\_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such y's brings us to an element in the set A

> Given $A \subseteq \Sigma^\*$ has the following property, then it is not regular
>
> For every $c \in \mathbb{Z^+}$ there exits $x \in \Sigma^\*$, and $n \in \mathbb{Z^+}$ s.t. $Y^A\_{x,n}$ exits and K-Comp $C(Y^A\_{x,n}) \> c + log(n)$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity

Keeping that in mind I am trying to prove this language is not regular

---

Let us run through a simple example B = $\\{0^n1^n | n \in \mathbb{N}\\}$

Proof: Let c $\in \mathbb{N}$. Choose k $\in \mathbb{Z^+}$ such that $C(1^k) \> c$, and let x = $0^k$ then we get the following$Y^A\_{x,1} = 1^k$**\<-why**? and $Y^A\_{x,2} = 01^{k+1}$**\<- again why**

therefore $C(Y^A\_{x,1}) = C(1^k) \> c + log(1)$ QED

# Answer
> 1 votes
You are asking many questions. Let me answer your first two, regarding $Y^A\_{0^k,n}$ for $A = \\{0^k1^k : k \geq 0\\}$. Recall that $Y^A\_{0^k,1},Y^A\_{0^k,2},\ldots$ is the list of all strings $y$ such that $0^ky \in A$, arranged in some order - apparently first according to length, and then lexicographically. It is easy to see that the strings $y$ such that $0^ky \in A$ are of the form $0^m1^{k+m}$. Arranged according to length, these are $1^k,01^{k+1},0^21^{k+2},\ldots$, and more generally, $Y^A\_{0^k,n} = 0^{n-1}1^{k+n-1}$.

---
Tags: regular-languages, kolmogorov-complexity
---


# Question
Title: Distance between $u$ and $v$ is the same as distance between $v$ and $u$ in a transposed graph?
My question is what the title says. Given an weighted directed graph $G=(V,E)$ and the minimum distance between two vertexes $u$ and $v$, I want to know if the distance between $v$ and $u$ is always the same in $G^{T}$ (the graph with all edges inverted).

I did some tests and couldn't find a graph where this is false, but this proves nothing. What is the intuition behind proving this true (or false)?

**Edit:** Distance is just the sum of all weights in the path from $u$ to $v$.

# Answer
Hint: Think about the path from $u \leadsto v$ in $G$. Can you find a corresponding path $v \leadsto u$ in $G^T$?

Hint: Suppose there was a *shorter* path $v \leadsto u$ in $G^T$. Can you think of any implications this would have for the distance from $u$ to $v$ in $G$?

Perhaps you can find some correspondence between paths in $G$ and paths in $G^T$ that will help you out.
> 2 votes

---
Tags: graphs
---


# Question
Title: Get indexes of unique elements in two different arrays in linear time
I have two array of the same set of elements, say for exemple: $a\_1 = \[x\_1, x\_2, …, x\_n\]$ and $a\_2 = \[y\_1, y\_2, …, y\_n\]$ so that $i \neq j \Rightarrow x\_i \neq x\_j$

Is it possible, in linear time, to construct the array $\[(x\_1, k\_1), (x\_2, k\_2), …, (x\_n, k\_n)\]$ so that $y\_{k\_i} = x\_i$ ?

I found that with dictionnaries, I can get $O(n)$ in average and $O(n^2)$ in worst (hashtable) or $O(n\log n)$ in average and worst (balancing trees), but can't find a way to make it $O(n)$ in worst case.

We can suppose that the $x\_i$ objects are integers, since it could represent memory pointers.

I found that it is possible if the set is $\[\\!\[1, n\]\\!\]$ (just construct the array directly).

Thanks for your help.

# Answer
> 2 votes
**Given the following assumptions:**

1. Since the meaning of the $=$ operator was not defined, we assume

> $i≠j⇒x\_i≠x\_j$
>
> ...
>
> The $x\_i$ values are not necessarily integers or string, but any type of elements.

are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, *and* that each element is a single word, perhaps a distinct pointer to some arbitrary object.

2. We assume that, given an arbitrary address, reading/writing at that address takes constant time.
3. We assume that adding 2 addresses takes constant time.
4. We assume that a pointer to unbounded memory is available in n time.

Assumptions 2 through 3 hold in most modern system, up to the memory capacity of the system. 4 only considers this program's logical space.

**Then:**

Consider the following construction (pseudocode). Note the time complexity, marked by "--":

```
//Arrays are indexed starting at 1.
//"*x = y" denotes "store y at the address pointed to by x"
//"x = *y" denotes "store the value, at the address pointed to by y, to x"

//Given:
input a1        //pointer to array a1
input a2        //pointer to array a2
input n         //number of elements in set
input mem       //address of unbounded hash table
                  //in the sense of a multitape Turing Machine,
                  //this points to the first address on "another tape"
output result   //address of n-length array of Tuples

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    hashkey = mem + a2[t] //find an address for this element; is unique
                          //since each element is unique
    *hashkey = t;         //store the index $k_i$ at this address
}

//mem is now a pointer to a (collision free) hash table

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    k = *(a1[t])
    *(result[t]) = Tuple(a1[t], k)
}

return result

```

...yes this dodges the question by using the suspicious "unbounded hash table". We could be pedantic and argue that the hash table is not technically unbounded on any system we might use, but by this same pedantry we can argue that the lower time complexity bounds of *every* non-trivial parameterized problem is $O(∞)$ just because we can choose parameters that happen to be too large for the system's address space.

The time complexity of the algorithm, address space permitting, is thus bounded by $T(2n) ∈ O(n)$.

# Answer
> 2 votes
For the record, here is an $\Omega(n^2)$ lower bound when your only access to the data is using queries of the form "$x\_i = y\_j$?". The proof uses an adversary argument. We will assume for convenience that $n$ is divisible by $8$.

We will maintain a bipartite graph, initially with $n$ nodes on each side, corresponding to $x\_1,\ldots,x\_n$ on one side and to $y\_1,\ldots,y\_n$ on the other. There is an edge connecting $x\_i$ to $y\_j$ if the algorithm hasn't found out that $x\_i$ is different from $y\_j$. Initially, the graph is complete. If we answer a query of the algorithm by $x\_i \neq y\_j$ (we will soon discuss our answering strategy), then we simply remove the edge $(x\_i,y\_j)$. If we answer a query by $x\_i = y\_j$, then we remove the *vertices* $x\_i,y\_j$.

Our answering strategy will always maintain the invariant that the current bipartite graph always contains at least two perfect matchings, and so the algorithm cannot tell how to match the $x$'s with the $y$'s. We will guarantee that by ensuring that all vertices have degree at least $n/2+1$. Let us explain why this guarantees the existence of at least two perfect matchings.

First, let us show that if all vertices have degree at least $n/2$ then there is at least *one* perfect matching. According to Hall's theorem, there is a perfect matching if every set $S$ on the left-hand side has at least $|S|$ neighbors on the right-hand side. This is clearly satisfied when $|S| \leq n/2$. If $|S| \> n/2$ then *every* vertex on the right-hand side is a neighbor of $S$, since otherwise it will have degree less than $n/2$.

Suppose now that all vertices have degree at least $n/2+1$. Take any vertex $v$ on the left. If we choose any of its neighbors $u$ on the right and remove both, then the remaining graph still has minimum degree at least $n/2$. Hence there is a perfect matching in which $v$ is matched to $u$. Since $v$ has at least two neighbors, this shows that there are at least two different perfect matchings.

We now describe our answering strategy. The strategy proceeds in phases, starting with phase $0$. We move to next phase after each time we answer a query by $x\_i = y\_j$. We will maintain the invariant that in phase $t$, all vertices have degree at least $(3/4)n-t$. This implies that all vertices have degree at least $n/2+1$ as long as $t \< n/4$.

Suppose that the algorithm asks "$x\_i = y\_j$?" during phase $t$. If both $x\_i$ and $y\_j$ have degree larger than $(3/4)n-t$, then we answer $x\_i \neq y\_j$. This clearly maintains the invariant. If one of them has degree exactly $(3/4)n-t$, then we answer $x\_i = y\_j$, and proceed to phase $t+1$. This also maintains the invariant, since we have decreased each degree by at most $1$.

As we have shown above, the algorithm cannot stop until reaching phase $n/4$, since in every earlier phase there are at least two perfect matchings consistent with the known information. It remains to lower bound the number of queries needed to reach phase $n/4$. We will actually lower bound the number of queries needed to reach phase $n/8$. In order to reach phase $t$ from phase $t-1$, the degree of some vertex $v\_t$ must reach $(3/4)n-t \leq (3/4)n$. So in order to reach phase $n/8$, the degree of $n/8$ vertices $v\_1,\ldots,v\_{n/8}$ needs to reach $(3/4)n$ or below.

The degree of a vertex can be decreased in two ways. When the algorithm answers $x\_i = y\_j$, the degrees of the neighbors of $x\_i,y\_j$ decrease by $1$; let us call this a *major decrease*. When the algorithm answers $x\_i \neq y\_j$, the degrees of $x\_i,y\_j$ decreases by $1$; let us call this a *minor decrease*. Since there are $n/8$ major decreases up to phase $n/8$, they can reduce the degree of $v\_1,\ldots,v\_{n/8}$ by at most $n/8$ each. Each of these vertices has to have its degree reduced using minor decreases by at least $n/8$. Since each minor decrease affects two vertices, there must be at least $(n/8)^2/2 = \Omega(n^2)$ minor decreases. In other words, the algorithm must make at least $\Omega(n^2)$ many queries.

Conversely, the problem can be solved using $\binom{n}{2} \leq n^2/2$ queries, by finding the correct match for the vertices on the left side one by one. Is this algorithm optimal? This is an interesting question for future work.

---
Tags: algorithms, time-complexity, arrays, finite-sets
---


# Question
Title: Prove that A is non-regular using K-Complexity Non regularity theorem
Given $Y^A\_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$

> Given $A \subseteq \Sigma^\*$ has the following property, then it is not regular
>
> For every $c \in \mathbb{Z^+}$ there exits $x \in \Sigma^\*$, and $n \in \mathbb{Z^+}$ s.t. $Y^A\_{x,n}$ exits and K-Comp $C(Y^A\_{x,n}) \> c + log(n)$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity

---

$A=\\{0^{2n}1x∣n∈\mathbb{N}, x∈\\{0,1\\}^∗$, and $|x|=n\\}$ Prove that A is non-regular using KCR

All we have to do is to pick a $x$ and $y$ s.t the concatenation $xy \in A$.

If I let $x = 0^{2n}1$ and let $y = x$, then we build the set $Y^A\_{x}$ given the $x$ and $y$ from above $Y^A\_{x,1} = 001(01)$ and next element in the set $Y^A\_{x,2} = 00001(0101)$.

Here is where I get stuck since I know I need to show $C(Y^A\_{x,1}) \> c + log(1)$ would this suffice to show that because of that this language is not regular? What is the best way to split the language for $x$ and $y $

# Answer
Suppose that $A$ is regular. Then there exists a constant $c$ such that for all $x \in \Sigma^\*$ and for all $n$ such that $Y^A\_{x,n}$ exists, $C(Y^A\_{x,n}) \leq \log n + c$.

Let us take $x = 0^{2m}1$. Then $Y^A\_{x,n}$ exists as long as $n \leq 2^m$ – in fact, $Y^A\_{x,n}$ is just the $n$th binary string of length $m$. Therefore $$ C(\text{$n$th binary string of length $m$}) \leq \log n + c. $$ In particular, choosing $n=1$, we get $$ C(0^m) \leq c. $$ Clearly this fails for large enough $m$. This contradiction shows that $A$ is not regular.
> 2 votes

---
Tags: regular-languages, kolmogorov-complexity
---


# Question
Title: Infinite non-regular decompositions of regular languages
The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case?

Or, from a different perspective: Given some regular language $L$, I want to find a family languages $(L\_i)\_{i \in \mathbb{N}}$ such that

1. $L\_i \cap L\_j = \emptyset$ whenever $i \neq j$
2. $\bigcup\_{i \in \mathbb{N}} L\_i = L$
3. $\forall i \in \mathbb{N}: L\_i \notin \mathsf{REG}$

More specifically: When is such a decomposition possible (clearly, not every regular language is decomposable in this way, e.g. finite languages)?

A class of (motivating) examples is the following: Given some congruence relation $\sim$ on $\Sigma^\ast$ such that the elements of $\Sigma^\ast /\sim$ are non-regular, every language saturated by $\sim$ admits a decomposition as above. One such congruence is the congruence $\sim\_R$ generated by the identities $\\{a^2 \sim\_R \lambda ~:~ a \in \Sigma\\}$, assuming $|\Sigma| \> 1$. An example for a language saturated by $\sim\_R$ is the language consisting of words containing an even (odd) number of occurrences of some symbol from $\Sigma$. More generally, languages accepted by complete deterministic automata with symmetric transition relations (that is, $q\cdot aa = q$ for all states $q$ and symbols $a$) are saturated by $\sim\_R$.

However, I fail to see some general criterion for a language being decomposable in this way.

# Answer
We show below that every infinite language can be partitioned into two non-regular languages. Using this, let us show that we can partition every infinite language $L$ into infinitely many non-regular languages. The construction goes as follows.

Choose an arbitrary ordering of $\Sigma^\*$. Let $R\_0 := L$. We will maintain the invariant that $R\_0$ is infinite. Given $R\_i$, partition it into two non-regular languages. Let $L\_{i+1}$ be the part with the smaller minimal word, and let $R\_{i+1} = R\_i \setminus L\_{i+1}$. Note that $R\_{i+1}$ is non-regular, and so infinite.

By construction, all $L\_i$ are non-regular, and they are disjoint. Also, the $i$th word in the ordering is contained in $L\_1 \cup \cdots \cup L\_i$ by construction, and so $\bigcup\_{i=1}^\infty L\_i = L$.

It remains to show that every infinite language can be partitioned into two non-regular languages. Recall that if a language is regular, then the set of lengths of words in the language is eventually periodic, and in particular, has the bounded gap property (the gap between adjacent elements is bounded). Therefore it suffices to show that every infinite subset of $\mathbb{N}$ can be partitioned into two subsets without the bounded gap property.

We imagine the infinite subset as an increasing sequence which is presented to us element by element. We will drop the elements into two buckets $A,B$ which will not have the bounded gap property. The construction proceeds in stages. In stage $2t$, we put the first element $x$ into $A$, and then put all elements into $B$ until an element $y \geq x + t$ shows up. We put $y$ into $A$, and move to stage $2t+1$, in which we proceed similarly, with the roles of $A$ and $B$ reversed.
> 2 votes

# Answer
Your intuition does not match mine, I think this is possible for every initial (infinite) regular language. My idea is that every infinite language has an (infinite) non-regular subset, such that the complement is also infinite. You then can repeatedly find the next language which together form a non-regular decomposition.

How to prove the basic observation? Just set half of the words apart (for the complement, the set of words is countable, so order them). In the remaining words you choose a subset that has ever greater sizes, not growing linearly but at least say exponential. Such a subset cannot be regular.

How do we obtain a decomposition that way: we might omit a string in each step. This is dealt by taking the shortest remaining string in the next language. That choice does not influence any regularity.
> 3 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: variable exponent in expression of a formal language
Take a look at the following expression:

{(AnB)m|n\>0,m\>0}

Or, to put it simply: the words in the language, have repeating parts consisting of, some A's followed by a single B.

There are TWO school of thoughts about this, which can be broken down, by this question:
Is the word ABAAB, a part of the language?

I say, that it's not, as each repeating part must have the same number (n) of A's in it.
Others claim that each repeating part can have it's own number of A's

I am willing to concede, that had the expression used +, instead of n\>0, then each repeat, could have been different (although, I don't like this concession).

The question is: Is the variable in the inner part "locked", or can that variable have different values in each iteration of the part.

What I'd like, is a credible source that I can point to that explains which way is correct.

(ps, if my understanding of the expression is the correct one, it means the language is not regular; if I am wrong, it is regular).

Thank you all.

# Answer
Whenever $m,n$ are chosen, there is only a single interpretation for $(A^nB)^m$. The variables are "locked" in the set builder notation $\\{ \dots \mid m,n\>0\\}$. I mean, the string $(A^2B)^3$ equals $AABAABAAB$, there are no schools here.

If you want to have repetitions of variable length sequences of the form $A\dots AB$ then the regular expression $(A^\*B)^\*$ is appropriate.

The point here is that for each $m,n$ the $(A^nB)^m$ here is only a single object, not a set of strings (a language).

Consider the domain of natural numbers, which probably is better known. Let us analogously define the set $S = \\{ (n+1)^m \mid m\ge 2,n\>0\\}$. Here it is quite clear that every $m,n$ is a single number, the $m$th power of a specific $n+1$. We would not consider choosing another $n$ for each multiplication. So we have $(2+1)(2+1)(2+1)\in S$ and not $(2+1)(5+1)(10+1)$.

The confusion is perhaps that in formal languages we consider both powers of single words and powers of languages. The $(A^\*B)^\*$ is an abbreviation for $\bigcup\_{m\ge 0}\\{ A^nB\mid n\ge 0\\}^m$. In this case for any $m$ we compute the $m$th power of the language $\\{ B, AB, AAB, AAAB, \dots \\}$ which is the concatenation of $m$ copies of the language. Then we can choose a different string (i.e., a different $n$) in each term.

Another example that shows the difference between these confusing notations is the following. For a language $L$ its square is $L^2 = L\cdot L = \\{ uv\mid u,v\in L\\}$. This is the concatenation of two copies of $L$, and we may choose two diferent strings: $\\{aa,b\\}^2= \\{aaaa,aab,baa,bb\\}$. Squaring all words is different: $\mathrm{sq}(L) =\\{ w^2 \mid w\in L \\}$. Same example $\mathrm{sq}(\\{aa,b\\}) = \\{aaaa,bb\\}$.

But again, the formal reason is set builder notation, as in my first paragraph.
> 4 votes

# Answer
This is set-builder notation. The notation $\\{ f(x\_1,\ldots,x\_\ell) : P(x\_1,\ldots,x\_\ell) \\}$, for a function $f$ and a predicate $P$, is shorthand for the set $S$ such that $$ y \in S \Longleftrightarrow \exists x\_1,\ldots,x\_n (y = f(x\_1,\ldots,x\_\ell)) \land P(x\_1,\ldots,x\_\ell). $$ In words, an element $y$ belongs to $\\{ f(x\_1,\ldots,x\_\ell) : P(x\_1,\ldots,x\_\ell) \\}$ if and only if there exist $x\_1,\ldots,x\_\ell$ such that $y = f(x\_1,\ldots,x\_\ell)$ and $P(x\_1,\ldots,x\_\ell)$ holds. More formally, we need to specify what set the variables $x\_1,\ldots,x\_\ell$ are quantified over; in your case it is the integers.

In our quest to understand your set, we also need to know what the expression $(A^nB)^m$ means. We are working over the free monoid $\\{A,B\\}^\*$ generated by $A,B$. We denote the product of two elements $x,y$ in the monoid by $xy$. For an element $x$ in the monoid, we define $x^n$ for natural numbers $n$ inductively: $x^0 = \epsilon$ ($\epsilon$ is the unit element of the monoid) and $x^{n+1} = x^nx$. Formally, there are also rules of precedence telling us how to parse the expression $(A^nB)^m$, though there isn't really much ambiguity in this case.

Following the inductive definition, we see that $A^nB$ consists of $n$ copies of $A$ followed by a copy of $B$, and that $(A^nB)^m$ consists of $m$ copies of $A^nB$. The set $\\{(A^nB)^m : n,m\>0\\}$ consists of all words $w$ such that $w = (A^nB)^m$ for some natural $n,m$ satisfying $n\>0$ and $m\>0$. This is exactly your interpretation.

The above description is somewhat cursory - one can get even more formal. Most of this material is covered in basic courses on set theory and formal logic. The exception is the free monoid (usually not described in this way), which is covered in courses on formal languages.

For the record, I teach automata theory and formal languages in academia.
> 4 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Trying to understand interpretation and denotation in FOL
I am going through the book "Knowledge Representation and Reasoning" by Brachman and Levesque.

So an interpretation $ F $ is defined as a pair $ \langle D,I \rangle $ mapping from a set of objects $ D$ called domain of the interpretation and $ I $ is a mapping called interpretation mapping from the non-logical symbols to functions and relations over $D$.

Then it has been written that $ I $ will assign meaning to the predicate symbols as follows:

To every predicate symbol P of arity $n$, $I\[P\]$ is an n-ary relation, that is, $I\[P\]$ is contained in $ D \times D \times D \times \dots \times D$.

Now for denotation it is written that for an interpretation $ F = \langle D,I \rangle $ we can specify which elements of $ D $ are denoted by variable free term FOL.

And hence the notion of variable assignment $ \mu $ has been introduced and the following two rules have been introduced:

Given an interpretation $ F $ and a variable assignment $ \mu $, the denotation of the term $ t $ is written as $ \\|t\\|\_{F \mu} $ and defined as follows:

1. If $ x $ is a variable then $ \\|x\\|\_{F \mu} = \mu \[x\] $.
2. If $ t\_1 ,\dots,t\_n$ are terms and $ f $ is a function symbol of arity $ n $ then $ \\| f(t\_1,\dots,t\_n)\\|\_{F \mu} = G( d\_1,\dots,d\_n) $, where $ G = I\[f\] $, and $ d\_i = \\| t\_i\\| \_{f \mu} $.

I am a bit confused about how to interpret the last two rules.

So the act of choosing elements from $ D $ to represent the arguments of the function symbol is represented by $ \mu $? Will it be right to say so?

How exactly are $ f $ and $ G $ related?

The output is evaluated by computing $ G $ for values which get substituted in the argument which is represented in $ d\_i = \\| t\_i\\| \_{f \mu} $ of the second rule.

But I could not understand how are the above two rules recursive? What exactly should I conclude about the way $ I $, $ G $ , $f$ and $ \mu $ are related to each other and what exactly do they mean? Is my understanding correct?

Attaching the screenshots from the book:

# Answer
> 3 votes
Consider the expression $+(x,\times(y,y))$, which is the FOL way to write $x+(y\cdot y)$. If I substitute $x=3$ and $y=5$ and do the arithmetic over the integers, what do I get? I need to evaluate the expression recursively.

In order to evaluate $+(x,\times(y,y))$, I need to evaluate $x$, to evaluate $\times(y,y)$, and then to combine them using the function $+$.

Evaluating $x$ is easy, since $x$ is just a variable. My assignment says that $x=3$, so the value of the expression $x$ is $3$.

Evaluating $\times(y,y)$ is more difficult. First I need to evaluate $y$ (twice) - as before, this is easy, and gives the result $5$. Now I need to combine the two values $5,5$ using the function $\times$. I have a large table which, for every pair of integers $a,b$, tells me what $\times(a,b)$ is. Looking at the table, I find out that $\times(5,5) = 25$.

Now that I have evaluated $x$ To $3$ and $\times(y,y)$ to $25$, I can finally look at the table for $+$ and deduce that $+(3,25) = 28$. So $28$ is the value of the entire expression.

The formal definitions you quote in your question attempt to capture the preceeding process in an abstract form. It's best if you work out the correspondence on your own.

---
Tags: logic, first-order-logic, knowledge-representation, reasoning
---


# Question
Title: How do I calculate Instruction Per Clock?
Hi! I faced a problem with calculating IPC.

I can tell the answers were derived from IPC=instruction/number of cycles.

But I have no idea why it has to be calculated that way.

Just to understand the meaning of IPC, it seems like how many instruction can one cycle(clock) handle which obviously is not the case for this question..

Hope to get some helpful answers from here!

Thank you in advance!

# Answer
The computation of instructions per cycles is a measure of the performance of an architecture, and, a basis of comparison all other things being equal. IPC can be used to compare two designs for the same instruction set architecture, as in the question you're asking comparing two design alternatives for a MIPS architecture.

Or, IPC can be used to compare vastly different designs (like CISC vs. RISC). If the processor can execute one instruction per cycle, then the IPC=1. Especially processors in the 1970's were usually were microcoded, and instructions completed in a variable number of cycles, like some in 2 cycles or some instructions in 4. So, for these machines IPC \< 1. Some processors using VLIW or EPIC or other architectural designs might complete several instructions in one cycle.

A MIPS processor attempts to execute one instruction per cycle using its pipelined design. However, certain conditions cause it to stall:

* waiting for a result that isn't ready, like multiply or divide
* waiting for a cache miss to resolve

Other times, it does work, but the work must be thrown away — this is the case of the branch instruction. More specifically, the issue of how soon the processor can get back onto the right instruction stream.

Let's look more closely at the pipeline for the question you're asking about: Here the code sequence is

```
<x>
B trg
<a>
<b>
<c>

```

In the following, @trg represents the instruction at the target of the branch, and this is the proper instruction to execute immediately after the branch.

```
    IF       ID      EX     MEM      WB
-1  <x>
0   B trg   <x>
1   <a>     B trg   <x>
2   <b>     <a>     B trg   <x>
3   <c>     <b>     <a>     B trg   <x> <--- if the branch executes here in the MEM stage, then <a>,<b><c> are unwanted and have to be discarded.
4   @trg    <c>     <b>     <a>     B
5           @trg    <c>     <b>     <a>
6                   @trg    <c>     <b>
7                           @trg    <c>
8                                   @trg

```

The above shows the branch executing in the MEM stage. Thus, the fetches the processor did for \< a \>, \< b \>, and \< c \> are invalid and have to be discarded. Three cycles are lost or wasted.

```
    IF       ID      EX     MEM      WB
-1  <x>
0   B trg   <x>
1   <a>     B trg   <x>                 <--- if the branch executes here in the ID stage, then only <a> is lost
2   @trg    <a>     B trg   <x>
3             @trg  <a>     B trg   <x>
4                   @trg    <a>     B
5                           @trg    <a>
6                                   @trg

```

Since the ID stage is 2 stages earlier, this processor has a larger IPC. We can use the IPC to ascertain *exactly how much* faster this design would be, and this demonstrates the value of the IPC definition.

---

*(There is term in sailing and yachting called Velocity Made Good, VMG — the idea is that even though you're going a certain speed (in sailing: knots, in computing: cycles per second aka hertz), only some of that speed goes to useful work being done (in sailing: reaching the finish line, in computing: completing instructions from the program). VMG for a processor would be instructions / hertz. So, compared to VMG which includes a time component, IPC factors out the time component.)*
> 1 votes

---
Tags: computer-architecture, mips
---


title: Can we use ILP here?

text:
# Question
Title: Can we use ILP here?
Is it possible to encode $y=0\implies G=0$ else $G=x$ by Integer Linear Programming where $x,y,G$ are integer variables?

The answer mentioned below gets to the point of taking absolute value of difference of two integers $a,b$. How do we get $|a-b|$ from ILP?

# Answer
> 1 votes
If $y$ is binary, $x$ is non-negative and you know upper bound for $x$, you can calculate this as: $G = \min(y \cdot K, x)$ where $K$ is greater than the upper bound.

If you only know the upper bound for $|x|$ and $|y|$, you can generalize this solution using tricks similar to https://blog.adamfurmanek.pl/2015/10/17/ilp-part-9/ . You basically need to compare $y$ with zero and use conditional operator (which is just a multiplication).

If you don't know the upper bound then I don't know the solution.

---
Tags: linear-programming, integer-programming
---


# Question
Title: Finding the longest overlapping interval pair
Say I have a list of $n$ integral intervals $\[a,b\]$ where each represents a set $S = \\{a, a+1, \ldots, b\\}$. An overlap is defined as $|S\_1 \cap S\_2|$. Example: $\[3,6\]$ and $\[5,9\]$ overlap on $\[5,6\]$ so the length of that is 2. The task is to find two intervals with the longest overlap in $o(n^2)$ using just recursion and not dynamic programming.

Naive approach is obviously brute force, which does not hold with time complexity condition. I was also unsuccessful trying sweep line algo and/or Longest common subsequence algorithm.

I just cannot find a way of dividing it into subproblems. Any ideas would be appreciated.

# Answer
> 1 votes
Hint: Try divide-and-conquer. I can only see about two plausible ways to do the "divide" step; try both of them, and one of them should work to yield a useful algorithm.

---
Tags: algorithms, recursion, intervals
---


# Question
Title: I want to find the Time Complexity of the following code
Here Nested loops are used, the time complexity of outer loop will be O(n) but how to calculate the complexity of inner loop as it depends on the value of i

# Answer
Both inner and outer loop are $O(n)$, and the total time complexity is $O(n^2)$. This is because the inner loop will make at most $2\*n$ steps which is clearly $O(n)$.

The loop will make $$2\cdot1 + 2\cdot 2 + 2\cdot 3 + 2\cdot 4 + \dots + 2 \cdot n = \\ 2(1 + 2 + \dots + n) = \\ 2(\frac{n\cdot(n+1)}{2}) = \\n \cdot (n+1) = O(n^2)$$
> 1 votes

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


# Question
Title: How do you analyse the time complexity of a piecewise function?
Is there a method to apply when trying to finding out the time complexity of a piecewise function?

\begin{align\*} F(x) &= \begin{cases} 2^x & x \< 8, \\ x^2 & x \geq 8. \end{cases} \\ \end{align\*}

This case seems straightforward as the function is $\Theta(x^2)$ for a large enough value of $x$, but what should be done in a more complex case... for example a function that gives a result for an odd value of $x$ and another one for an even value of $x$?

# Answer
There seems to be a misconception here: every function $f$ has a "nice" asymptotic form, in the sense that $f = \Theta(g)$ for some function $g$ given by a reasonable formula. Some examples of reasonable formulas include $c^nn^k\log^\ell n$ for various values of $c,k,\ell$. However, this isn't always the case. Consider for example the function $$ f(n) = \begin{cases} n & \text{if $n$ is odd}, \\ n^2 & \text{if $n$ is even}. \end{cases} $$ There is no "nice" function $g$ such that $f = \Theta(g)$. It is apparent that $f = \Omega(n)$ and that $f = O(n^2)$, but there is no value of $k$ for which $f = \Theta(n^k)$.

In practice, such examples occur only rarely, and so usually it is the case that we can find a nice order of growth for functions that occur in practice.

This discussion is related to another misconception, that we can always compare two functions asymptotically. That is, that for any two functions $f,g$, either $f = o(g)$, or $f = \Theta(g)$, or $f = \omega(g)$. While these three possibilities are indeed mutually exclusive, there is a fourth possibility, namely, that $f$ and $g$ are incomparable. As an example, if we take the function $f$ considered above and try to compare it to $g(n) = n^{3/2}$, then we find that none of $f = o(g)$, $f = \Theta(g)$, $f = \omega(g)$ holds. However, the trichotomy does hold when $f$ and $g$ are "nice" functions (defined using only arithmetic operations, logarithm, and exponential).

Finally, there is one special case which is easy to handle: if $$ f(n) = \begin{cases} g(n) & \text{if } n \< C, \\ h(n) & \text{if } n \geq C, \end{cases} $$ Then $f(n) = \Theta(h(n))$. This is the case in your example.
> 4 votes

---
Tags: asymptotics
---


# Question
Title: Is the worst-case of this algorithm equal to $\Theta(n)$ or $\Theta(n\lg n)$?
I am trying to find the worst-case complexity of the following algorithm. The input to the algorithm is a list of positive integers $a\_1,\ldots,a\_n$ and a bound $C$.

* $S\gets$ empty set
* $k\gets0$
* for $i\gets1$ to $n$ do
    + add $i$ to $S$
    + $k\gets k+a\_i$
    + if $k\>C$
        - $j\gets\arg\max\_{i\in S}a\_i$
        - $k\gets k - a\_j$
        - remove $j$ from $S$

In the worst-case, at each iteration $i$, we go to the if condition and calculate the max. So, if the max operation requires $\Theta(n)$, then the worst-case complexity is $\Theta(n^2)$. As suggested in the comments, $\Theta(n)$ is not the best possible.

Here, I use an array to represent $S$. I can use a heap instead as a data structure to find the max in $\Theta(\lg n)$. So, the worst-case complexity is $\Theta(n\lg n)$. Am I right?

**EDIT:** I found this article https://cstheory.stackexchange.com/questions/18119/finding-smallest-k-elements-in-array-in-ok which finds the $k$ smallest elements in $O(k)$ time. My algorithm computes the $|S|$ smallest elements. Hence, it can be done in $O(|S|)$ time. **But** the $|S|$ is not given apriori. This is another issue now. Any help?

# Answer
> 1 votes
You need a data structure that supports the following three operations efficiently:

* insert an element into the set
* delete an element from the set
* find the largest element in the set

There are multiple such data structures. One reasonable choice is a balanced binary search tree, where all three operations can be implemented in $O(\log n)$ time.

---
Tags: algorithms, algorithm-analysis, asymptotics
---


# Question
Title: How does software detect if an interrupt has occurred if it cannot set it's own interrupt handlers?
I'm currently working on designing a relatively simple processor using a custom ISA . It will use interrupts for I/O .

From what i know , once the interrupt controller issues an interrupt , the processor acknowledges it and set it's PC to the IVT , from where it executes the relevant interrupt handler , which specifies what the CPU does .

These interrupt handlers are set by the OS and cannot be modified by the user-mode process.

My question is this : how does the process know when an interrupt has occurred ? the cpu might execute the handler and place the acquired controller data in a memory location , but how is the application notified ? what are the common methods of doing this ?

For example , say i have a platform game ; when i press the assigned jump key , the cpu will acquire the keyboard data , but how does it go from there to actually making the sprite jump in a video game ? does the app still have to check for controller input at regular intervals ?

# Answer
> 3 votes
The interrupt handler adds the new data to an input queue. Typically the user level process will have a thread waiting for input to appear, or will poll periodically to see if new input is available. If your process does neither, it would never notice the new data.

# Answer
> 1 votes
In your keyboard example, the operating system will receive interrupts and figure out that a key has been pressed or released. But who to tell?

Usually you will have multiple applications running simultaneously. Only one will receive the notification about the key being pressed. Usually that is an important security measure: While I type this message, I want the keys to go to the browser, not to any other application. Worse, if I type a credit card number, I most definitely don't want any random application to know about it. So the operating system will tell *one* application.

On MacOS for example, a data structure describing the event (key "X" was pressed while the shift and control key were held) will be added to a queue maintained by the application, and every time that queue is non-empty the application will have told the operating system which function to call (simplified version), and that function is called. Other operating systems will likely do very similar things.

---
Tags: operating-systems
---