# Question
Title: How do we formally regard a function that takes a lookup set as a parameter?
I have a function that takes a set as a parameter. The function $\phi$ maps a general $x \in R$, where $R$ is a commutative ring with $1$, to a $\phi(x) \in \Bbb{N}$ representing the "grammar size" of $x$. $R$ one-to-one represents grammars generating a single string $s \in \Sigma^\*$.

$$ \phi(x, A) = \begin{cases} 0, \text{ if } x \in A \\ |x\_t^\*| + n(x) - \sum\limits\_{i=1}^{n(x)} \phi(x\_i, A), \text{ if } x \notin A, \text{ and, } \\ \text{ also ensure, } A := A \cup x \end{cases} $$

So as you can see the value of successive calls to $\phi$ depend on the contents of the set $A$. $A$ is passed-by-reference (not by value copy).

Was wondering if math has a formalism for dealing with such functions that depend on a persistent set parameter.

It's true that if we let $|0^\*| = |\epsilon| = 0$ that the size of a grammar $x + y$, for $xy = 0$ (empty intersection), is $$\psi(x + y) = |s| - \phi(x + y, \\{\\}) = \\ (\text{init } A:=\\{\\})\\ |s| - (\phi(x, A) + \phi(y, A))$$.

So that $\phi(z, A)$ acts a like a measure for disjoint elements $xy = 0$ of $R$. But as you know, measure functions don't usually take a lookup set as a parameter. So was wondering about the best formalization.

# Answer
> 1 votes
Your $\phi$ is stateful; the value of $\phi(x,A)$ depends on what parameters you have previously evaluated it with. As such, it is not a mathematical function. Mathematical functions are stateless.

Formalization serves a purpose: to describe clearly and precisely. It's not to blindly follow rules, but to serve as an aid to communication. As long as you have described what you want clearly and precisely, in a way that a reader is likely to understand, you are good. So, don't call $\phi$ a function, as that will confuse readers; but you can describe the intended semantics of what you want the procedure $\phi$ to return, in terms of its parameters and its state.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Find a truth assignment of 2SAT that has the most number of true variables?
Given a 2SAT instance in CNF where each clause has at most two literals. Let $m$ be the number of clauses and $n$ be the number of variables et let $k$ be a positive number.

Question: Is there a truth assignment such that the number of variables that are true is $k$ or more?

I cannot find the name of this problem, if it was already studied? If so, is it NP-hard?

# Answer
Your problem is known as Weighted-2-satisfiability, and is known to be NP-complete. The easiest way to see that is by reduction from Vertex Cover (exercise).

Note that the link above is about whether there is a satisfying assignment having *at most* $k$ true variables. This is equivalent to your problem (exercise).
> 4 votes

---
Tags: complexity-theory, np-complete, satisfiability
---


# Question
Title: Explain this Neural Network used for Knowledge Graph Embedding
I am interested in better understanding the neural network used in the paper LogicENN A Neural Based Knowledge Graphs Embedding Model with Logical Rules. To my knowledge this is the most advanced and complex knowledge graph embedding.

The neural network is described as follows:

Entity pairs, $\[h,t\]$ , are input and relations are output.

The score of a given triple $(h, r, t)$ is $f^r\_{h,t}$ and is given by:

The beta vector are the embedding of relations.

The phi vector is the feature mapping of the hidden layer of the network which is shared between all relations.

This neural network works with a single hidden layer.

The first problem is: when I look at the picture, I think this neural network should have multiple hidden layers but in the text it's written "we use a single hidden layer".

The second problem is: when I look at the picture, I think that there is no direct relation between the outputs and the hidden layers but in text it's written "the feature mapping of the hidden layer of the network which is **shared** between all relations".

Please, explain this neural network. Any help is appreciated.

# Answer
Well basically, without loss of generality, they use a single hidden layer for the neural network to show theoretical capabilities of those networks. Practically, sometimes it is better to use more hidden layers and sometimes, on the other hand, adding more hidden layers only adds complexity and it is more time consuming for a model to be trained. if your data is linearly separable (which you often know by the time you begin coding a NN) then you don't need any hidden layers at all. Of course, you don't need an NN to resolve your data either, but it will still do the job.

In their experiment, they are using 3 hidden layers. People usually come up with the best number of hidden layers by experiment. There is no magic formula for selecting the optimum number of hidden neurons. However, some thumb rules are available for calculating the number of hidden neurons. A rough approximation can be obtained by the geometric pyramid rule proposed by Masters (1993). For a three layer network with n input and m output neurons, the hidden layer would have $ \sqrt{n \times m} $ neurons.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Are chaotic systems computable in polynomial time
Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed.

Say, for instance, as input we have a start configuration of the chaotic Rule 30 cellular automata and a time-step $t$, and as output, we require the configuration at time-step $t$.

What can be said about the computational complexity of such a computation?

# Answer
> 1 votes
Wolfram's rule 30 is a one dimensional cellular automaton. If you want to know the state of the *CA* at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of *if*'s, so the time complexity of such *CA* is linear in $t$.

---
Tags: time-complexity, polynomial-time
---


# Question
Title: Turing machine that applies homomorphism on input string
I really need some help with this problem. I'm running into the issue that the input is running out of space to append the 11 or 10. I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Change the original input with a 1 into 11 and 0 into 10. You must also append a 01 to the start of the input once it is finished. for instance, if the input was 10110, then the output would be 011110111110.

# Answer
> 1 votes
> I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Turing Machines are formal logical models that can express computation. You can think of them as mechanical machines that perform *read* and *write* operations on one or more tapes containing symbols. These operations are not performed randomly but based on a table (called the *transition function*) which is the true essence of the Turing Machine, without it the machine could not even move from the initial state. This table specifies what the machine must do in each state, based on the 'settings' of the "*machine world state*", for example:

1. If the machine is in state $q\_1$ and it reads a '$1$' on the input tape, then write a '$0$' on the working tape and move left on the same tape.
2. If the machine is in state $q\_3$ and it reads a '$0$' on the input tape, then go to state $F$ (*HALT*).

These are some basic description of a *TM*, if you want to know them better (and I believe it is mandatory to **master** them if you want to continue with this discipline). Then you need to open a textbook and dig into these concepts. Now going back to your problem, you might find it useful to throw down a high-level description of an algorithm (turing machine) that performs the required transformations on the input string; then you can proceed from here, after you have learned how to formally define a turing machine, and draw your model.

Possible algorithm:

1. start reading input tape
2. if input at position $i = 1$, then write a $1$ on the working tape at position $i$ and a $1$ at position $i+1$, then move right on the input tape.
3. if input at position $i = 0$, then write a $1$ on the working tape at position $i$ and a $0$ at position $i+1$, then move right on the input tape.

To this you need to add the implementation for adding '$01$' at the start of the string.

# Answer
> 1 votes
If you have a single tape Turing machine then your main conceptual problem is separating input from output. You could approach this problem as follows:

Initial configuration:

* We will assume the tape is filled with spaces apart from a single input string which consists of a non-empty sequence of $0$s and $1$s.
* We will assume the Turing machine starts at the first character (left hand end) of the input string.

Intermediate configuration:

* We will construct an output string which is a sequence of $0$s and $1$s.
* The output string will be to the right of the input string, with a single space between them.
* We will erase the input string one character at a time from the left, and build the output string by adding two characters at a time to its right hand end.

Final configuration:

* When the Turing machine stops we will have erased the whole input string, and the tape will contain spaces and the output string.
* The Turing machine will stop at the first character of the output string.

Outline algorithm:

1. Read the first character of the input string and "remember" whether it is a $0$ or a $1$ (short term "memory" in a Turing machine consists of defining different states).
2. Erase the first character of the input string by writing a space.
3. Move right until you find a space (so you have gone past the end of the input string).
4. Move right until you find another space (so you have gone past the end of the output string). Write $1$.
5. Move right. If the first character of the input string was $0$ write $0$; if it was $1$ write $1$.
6. Move left until you find a space (so you have gone past the beginning of the output string).
7. Move left until you find another space (so you have gone past the beginning of the input string).
8. Move right. If there is a $0$ or a $1$ here then there is more input to be processed so go to step 1.
9. The input string is now empty and you are at the space before the start of the output string. Write $1$.
10. Move left, write $0$, and stop.

As you will find, designing a Turing machine for even a simple task is very laborious, and it takes practice to break down a task into very small steps. You will need between $15$ and $20$ states for this Turing machine.

---
Tags: turing-machines
---


# Question
Title: Fastest algorithm to find whether a list contains a word?
Given an unordered list of words, what's quickest way to test whether a certain word is in that list?

I can't think of another way to do this other than just going through each element in the list and checking whether it's the word I want.

# Answer
If you are given an unordered list and asked to test whether just *one* item is in the list then a sequential check of each item in the list is the best you can do.

If you want to carry out *multiple* tests (but you do not know all the test items in advance) then it is worth the initial overhead of sorting the list, creating a hash table, or creating a search tree.
> 1 votes

# Answer
It really depends on what data structure you want to use. If you are using an array, one way is to sort it in $O(n\log(n))$ and then you can check whether an item exists using binary search in $O(\log(n))$. One other way is to use hash tables data structures like dictionaries in Python where you can answer such question in $O(1)$. Check Python Dictionaries or C++ Maps.
> 0 votes

---
Tags: search-algorithms, strings, search-problem, search
---


# Question
Title: Prove, that $A^+\subseteq A^*$ where $A$ is a formal language
> Prove, that $A^+\subseteq A^\*$, where $A$ is a formal language.

The definition of $A^+$ is $\bigcup\_{i\in\mathbb{N}\setminus \\{0\\}}A^i$, which would be $A^1 \cup A^2 \cup \dots \cup A^i$. Likewise, $A^\*$ is $\bigcup\_{i\in\mathbb{N}}A^i$ and therefore $A^0 \cup A^1 \cup \dots \cup A^i$.

Suppose, $x\in A^+$. By definition $x\in A^+ \land x\in A^\*$ for all $x\neq A^0$, which is the set of the empty word. We can conclude, that $A^1\cup A^2\cup \dots \cup A^i \subseteq A^0\cup A^1\cup \dots \cup A^i$ and $\bigcup\_{i\in\mathbb{N}\setminus \\{0\\}}A^i \subseteq \bigcup\_{i\in\mathbb{N}}A^i$, that's why $A^+\subseteq A^\*$.

Is this "proof" ok?

# Answer
It seems you have hit the reasoning correctly: A set $S$ is a subset of another set $A$ *if* $w\in S\implies w\in A$. Since you are trying to show that $\forall w \in A^+ \implies w \in A^\*$, you are proving that $ A^+ \subseteq A^\*$.

One more legant way to formally do this is by finding a bijection between the two sets. Since $|A^\*|$ = $|\Bbb N|$ you need to prove that $|A^+|$ is a subset of $|\Bbb N|$. So you need to find a Bijection (left to you since we dont do Homework for the OP's) from these two sets. Note that there exists $2^{\aleph\_0}$ such functions, so you have a large selection space :)
> 3 votes

# Answer
The "$x\in A^{+}$. By definition $x\in A^{+} \wedge x\in A^{\*}$ for all $x\neq A^{0}$" is a bit weird. Not even from a computer science point of view but from a set theory or general mathematical point of view. First, you're saying the same thing again with "$x\in A^{+}$" which you shouldn't. Then, you're saying $x\in A^{\*}$ which is the desired result.

I think a better way to write would be as follows: let $w\in A^{+}$. Then, by definition, there is $i\in \mathbb{N}\setminus{\\{0\\}}$ such that $w\in A^{i}$. However, $A^{i}\in \bigcup\_{j=0}^{\infty} A^{j}=A^{\*}$ so $w\in A^{\*}$.

Conceptually not different than your answer, just written differently.
> 2 votes

---
Tags: formal-languages, kleene-star
---


# Question
Title: Does a context switch happen when a process has terminated?
I know this might sound like a newbie question but let's say we have a priority based scheduling algorithm (non-preemptive) where all processes arrive at time 0 and based on priority the order is P1, P2, P3 ...

The processes will run P1, P2, P3 without having to block one to let another one run, each processes will run until it is finished.

I am not sure here: when switching from process P1 to P2 is a context switch necessary? I know that : ***In computing, a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.*** But since we don't save P1's state do we still need a context switch? I tend to say we do since a context switch also happens when you start up a new process from scratch which will have its own context, right?

I just want to make sure I get these things straight! Any tip would be greatly appreciated!

# Answer
Yes, a context switch happens. After P1 ends the state of P2 must be loaded. The only difference with a regular context switch is that the state of P1 does not need to be saved as it is not needed for a later restore.

Whether the OS actually applies this optimization or simply performs a regular context switch and then later discards the saved context for P1 depends on the implementation.
> 2 votes

# Answer
Apparently people imagine context switching means there must be some preemption going around in the processor.But literally context switching means switching of context so even if its non-preemptive algorithm after one process terminates next scheduled process have to be loaded in the processor.So context switching occurrs from previous process info to new process info. If it had been a preemption, prev. process state has to be saved and restoration has to be done afterwards. hope it helps
> 1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?
Continuing https://tex.stackexchange.com/questions/435986/how-to-draw-the-box-of-dijkstras-guarded-command-language, what is the difference in the intended usage of ⫾ (Dijkstra choice, U+2AFE) and ⫿ (n-ary Dijkstra choice, U+2AFF) in the context of the Guarded Command Language (GCL) of Dijkstra? In other words, when do you use ⫾ and when ⫿ for typesetting GCL programs?

Related:

# Answer
> 3 votes
Non-deterministic guarded choice is an associative-commutative binary operator. My guess is that the character ⫾ U+2AFE is intended to be used as an infix binary operator and the character ⫿ U+2AFF, which is larger and described as “n-ary”, is intended to be used as a prefix operator which is typeset larger, in prefix position, and typically with a subscript and sometimes a superscript to indicate the range over which the operation is carried out.

$$⫿\_{i=1}^n c\_i \rightarrow a\_i \qquad = \qquad \mathsf{if}\\; c\_1 \rightarrow a\_1 ⫾ \cdots ⫾ c\_n \rightarrow a\_n \\;\mathsf{fi}$$

Typeset with inline math: $⫿\_{i=1}^n c\_i \rightarrow a\_i = \mathsf{if}\\; c\_1 \rightarrow a\_1 ⫾ \cdots ⫾ c\_n \rightarrow a\_n \\;\mathsf{fi}$

It's the same relationship as between $+$ (binary) and $\sum$ (n-ary), or between $\times$ (binary) and $\prod$ (n-ary) ($\prod$ is sometimes a different product such as $\cdot$). For binary operators other than the two classics addition and multiplication, the n-ary version is the same glyph, just bigger.

---
Tags: terminology, programming-languages, notation
---


# Question
Title: How do I solve these questions regarding homomorphism?
Questions:

1. Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B.
2. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and Γ, for languages A and B, respectively.

Questions to stack overflow:

* How do I give the examples above? Do I make the state diagrams? Do I show it through the tuple-definition?
* What are some examples of the questions above?

# Answer
Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$. First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^\*$$. The second is the map between words $$f':\Sigma^\* \rightarrow \Gamma^\*$$. The third is the map between languages $$f'':\mathbb{P}(\Sigma^\*) \rightarrow \mathbb{P}(\Gamma^\*)$$.

The The main point of the quote is that given $f$ there is the particular way to construct the corresponding $f'$ and $f''$. So, what one might call **homomorphisms between languages $f''$ is specified by just giving map from alphabet to words $f$**. And $f$ is usually easier to describe directly than $f''$.

Another important observation is that not all function of type $$\mathbb{P}(\Sigma^\*) \rightarrow \mathbb{P}(\Gamma^\*)$$ is a homomorphism of languages. (Because it doesn't "preserve structure" w.r.t. concatenation operation languages are equipped with.) However, the said construction is special in that given any $f$ with the correct type, $f''$ will be a valid homomorphism of languages.
> 4 votes

---
Tags: formal-languages, regular-languages, finite-automata, regular-expressions
---


# Question
Title: Trivial solution to the Continuous Knapsack problem
I am a bit puzzled as to why the continuous knapsack problem is a non-trivial problem

https://en.m.wikipedia.org/wiki/Continuous\_knapsack\_problem

Using the terminology in the Wikipedia link above,

If the Knapsack had a capacity of $W$, couldn't we just pick $W/w\_i$ of the material $i$ having the maximum value per unit weight $v\_i$?

# Answer
Briefly, the supply of each material is finite: there is only $w\_i$ of material $i$. If $w\_i \< W$, then you cannot fill the knapsack just with material $i$.

In the continuous (or fractional) knapsack problem, we are given a bunch of materials $1,\ldots,n$. Material $i$ has weight $w\_i$ and total value $v\_i$. The goal is to pick $\alpha\_1,\ldots,\alpha\_n \in \[0,1\]$ such that $\sum\_i \alpha\_i w\_i \leq W$ in a way which maximizes $\sum\_i \alpha\_i v\_i$. Your suggestion of taking $\alpha\_i = W/w\_i$ (for the best material $i$) is only feasible and optimal if $W = w\_i$. If $W \> w\_i$ then the choice isn't feasible – there is not enough of material $i$. If $W \< w\_i$, then the choice (probably) isn't optimal, since the knapsack will still have room left.
> 1 votes

---
Tags: greedy-algorithms
---


# Question
Title: Prove $\epsilon(S\cap T)\subseteq S \cap T$
> Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$.
>
> Prove $\epsilon(S\cap T)\subseteq S \cap T$

Definition of $\epsilon$\- closure for epsilon NFA is:

> $\epsilon : 2^Q \rightarrow 2^Q $
>
> a) $S \subseteq \epsilon (S)$ Base case
>
> b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case
>
> c) and nothing else is in $\epsilon (S)$
>
> And also, S is a set of all states in epsilon-NFA.

My proof:

Is this a correct reasoning?

# Answer
Since your definition of $\epsilon$-closure isn't really a definition, it is impossible to prove anything using it. Instead, let me use the following definition: the $\epsilon$-closure of a set $S \subseteq Q$ consists of all states $x \in Q$ which are reachable from a state in $S$ by a (possibly empty) $\epsilon$-path (which is a path consisting of $\epsilon$-transitions).

Suppose that $\epsilon(S) = S$ and $\epsilon(T) = T$, and let $q \in \epsilon(S \cap T)$. Thus $q$ is reachable by a state $r \in S \cap T$ via an $\epsilon$-path. Since $r \in S \cap T$, in particular $r \in S$, and so, by definition, $q \in \epsilon(S) = S$. Similarly, $q \in \epsilon(T) = T$. Therefore $q \in S \cap T$.
> 2 votes

---
Tags: automata, finite-automata, check-my-answer
---


# Question
Title: Numerical issues in solving linear systems
There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows:

> Consider the linear system
>
> $$ \begin{bmatrix} a & b \\ b & a \end{bmatrix} \times \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$$ with $a,b\>0$.
>
> a) If $a$ is very similar to $b$, what is the numerical difficulty in solving this linear system?
>
> b) Suggest a numerically stable formula for computing $z = x + y$ given $a$ and $b$.

This is a Computer Engineering course, however I am not able to answer these questions. What is the keyword to find a solution on the issue?

Thanks in advance.

# Answer
> 1 votes
The $2\times 2$ matrix has determinant close to zero, and so its condition number is very large, causing numerical instability.

The explicit solution of your system is $$ x=\frac{a}{a^2-b^2}, y=-\frac{b}{a^2-b^2}. $$ Therefore $$ x+y = \frac{a-b}{a^2-b^2} = \frac{1}{a+b}, $$ thus avoiding the numerical issues.

---
Tags: numerical-analysis, error-estimation, matrix
---


# Question
Title: Does a recursive call reset to the beginning of the method if the call is in the middle?
Or does it finish the method? Sorry for noob question.

# Answer
A recursive call is no different than any other call. Here is what happens when you call procedure X:

* The current address is pushed into the stack.
* Jump to the beginning of X.
* When X concludes, pop the return address from the stack, and jump there.

It doesn't matter whether X is the current procedure or a different one.
> 1 votes

---
Tags: recursion
---


# Question
Title: Remove x last elements of an array and reinsert them before position y
I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array with O(1) extra space and O(n) runtime.

e.g. where \*p1 = 5 and \*p2 = 3:

1 2 5 6 7 3 4

becomes

1 2 3 4 5 6 7

This is what I have so far (written in C programming language). Trouble arises when p1 reaches p2.

```
void swap(long* p1, long* p2, long* array_end) {
  long* p2_i = p2;
  while (p1 < array_end) {
    if (p2_i > array_end) {
      p2_i = p2;
    }

    // swap *p1 and *p2_i
    long* temp = p1;
    *p1 = *p2_i;
    *p2_i = temp;

    ++p1;
    ++p2_i;
  }
}

```

# Answer
> 3 votes
We can assume without loss of generality that $y$ is the first position, and that the first position is zero. Suppose that there are $n$ elements in the array. Then we want to apply the permutation $\pi(i) = (i+x) \pmod n$. Two elements $i,j$ are in the same cycle of $\pi$ if $i \equiv j \pmod {(n,x)}$, which means the the cycle leaders (minimum elements of each cycle are $0,\ldots,(n,x)-1$. In other words, for each $j \< (n,x)$, we need to consider the elements $$ A\[j\],A\[j+x\],A\[j+2x\],\ldots,A\[j+(n/(n,x)-1)x\] $$ and rotate them one step to the right. This can be done using constant memory, and takes time $O(n/(n,x))$. Overall, the running time will be $O(n)$.

You don't actually need to determine $(n,x)$. Instead, you can simply count how many elements were touched. For example, you can consider the following pseudocode:

```
touched = 0
current = 0
while touched < n:
    origin = current
    element = A[current]
    repeat:
        current = (current + x) mod n
        swap A[current] and element
        touched = touched + 1
    until current = origin
    current = current + 1
end while

```

# Answer
> 2 votes
$\texttt{index1}$ is index of the first element of subarray 1, $\texttt{index2}$ is index of the first element of subarray 2 and $\texttt{array\_end}$ is index of the last element in the array.

From $\texttt{index2}$ to $\texttt{index2\_i}$ is a buffer that contains the elements to be inserted after $\texttt{index2\_i}$ reaches array\_end. From $\texttt{index2\_i}$ to array\_end are elements currently being inserted.

I fixed it by just moving $\texttt{index2}$ to $\texttt{index2\_i}$ whenever $\texttt{index1}$ catches up (subarray 2 is made smaller, so $\texttt{index2\_i}$ is not set to something less than or equal to $\texttt{index1}$). I might mark someone else's solution as the answer, but I am just including this for completeness. I am using this as a step in an $O(n \log n)$ implementation of in-place mergesort, if anyone was wondering.

Pseudo:

```
SwapSubArrays(index1, index2, array_end):
  index2_i = index2
  while (index1 < array_end):
    if (index2_i > array_end):
      index2_i = index2
      if (index1 >= index2)
        break
      end if
    end if

    if (index1 >= index2):
      index2 = index2_i
    end if

    Swap(index2, index2_i)

    index1 = index1 + 1
    index2_i = index2_i + 1
  end while
end method

```

Source:

```
void swap(long* p1, long* p2, long* array_end) {
  long* p2_i = p2;
  while (p1 < array_end) {
    if (p2_i > array_end) {
      p2_i = p2;
      if (p1 >= p2) {
        break;
      }
    }

    if (p1 >= p2) {
      p2 = p2_i;
    }

    // swap *p1 and *p2_i
    long* temp = p1;
    *p1 = *p2_i;
    *p2_i = temp;

    ++p1;
    ++p2_i;
  }
}

```

# Answer
> 1 votes
In C++ we call this algorithm rotate. It was made famous by Sean Parent's C++ Seasoning talk in 2013 (discussion of `rotate` begins at 8:53).

Here is cppreference.com's possible implementation adapted into C.

```
/**
 * @brief      Moves two ranges of elements in an array.
 *
 *             The elements in the range [first, n_first) to directly before
 *             position last. Elements in the range [n_first, last) will be
 *             moved to position first.
 *
 *             The ranges [, F) and [P, ) are unchanged.
 *
 * @param      first    The beginning of the first range
 * @param      n_first  The beginning of the second range
 * @param      last     The element directly after the end of the second range
 *
 * @return     The new location of first
 */
long* rotate(long* first, long* n_first, long* last)
{
   if (first   == n_first) { return last; }
   if (n_first == last)    { return first; }

   long* read      = n_first;
   long* write     = first;
   long* next_read = first; // read position for when "read" hits "last"

   while(read != last)
   {
      if (write == next_read) { next_read = read; } // track where "first" went

      long tmp = *write;
      *write = *read
      *read = tmp;

      read++
      write++;
   }

   // rotate the remaining sequence into place
   rotate(write, next_read, last);
   return write;
}

```

Forgive me for not using `p1`, `p2`, and `array_end` but I hope the documentation is clear enough. This code comes with no warranty, please ensure I have correctly translated the `std::iter_swap(write++, read++);`.

---
Tags: algorithms, arrays
---


# Question
Title: How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$
In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition

> \begin{align\*} \Theta(n^2) = \\{h(n) \\,|\\, \exists c\_1 \> 0, c\_2 \> 0, n\_0 \> 0 \\,\forall n \geq n\_0: 0 \leq c\_1n^2 \leq h(n) \leq c\_2n^2\\} \end{align\*}

the authors write that $n\_0 = 2\*\max(|b|/a, \sqrt{|c|/a})$.

I have difficulties proving that the value of $n\_0$ is indeed that value.

We know that $a \ge 0$ because otherwise $f$ would not be asymptotically nonnegative. Calculating the roots of $f$ gives us:

\begin{align\*} n\_{1/2} &= \frac{-b \\, \pm \\, \sqrt{b^2 - 4ac} }{2a} \\ &\leq \frac{|b| + \sqrt{b^2 - 4ac} }{a} \end{align\*}

The case $c \ge 0$ gives us:

\begin{align\*} \frac{|b| + \sqrt{b^2 - 4ac} }{2a} \leq \frac{|b| + \sqrt{b^2} }{a} = 2\frac{|b|}{a} \end{align\*}

which is two times the first argument of the $\max$ function.

But what about the case $c \< 0$? How can we find an upper bound for that? Where does the value $\sqrt{|c|/a}$ actually come from?

# Answer
CLRS is wrong. For example, the function $0n^2+0n+0$ is asymptotically nonnegative but doesn't belong to $\Theta(n^2)$. Changing "nonnegative" to "positive" doesn't help: you can consider $0n^2+0n+1$. Even requiring the function to be nonconstant doesn't help: consider $0n^2+1n+0$.

Here is a statement which is correct: if $a \> 0$ then $an^2+bn+c = \Theta(n^2)$. Indeed, when $n \geq 2\frac{|b|+|c|}{a}+1$ then $$ |(an^2 + bn + c) - an^2| = |bn+c| \leq |b|n+|c| \leq (|b|+|c|)n \< \tfrac{1}{2} an^2, $$ and so $$ \tfrac{1}{2} an^2 \leq an^2 + bn + c \leq \tfrac{3}{2} an^2. $$
> 1 votes

# Answer
So I actually found the answers I was looking for. The case $c \ge 0$ is already handled in the question above. For the case $c \< 0$ we have:

\begin{align} n\_{1/2} &= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\ &\le \frac{|b| + \sqrt{b^2 - 4ac}}{a} \\ &\le \frac{|b| + \sqrt{b^2} + \sqrt{-4ac}}{a} \\ &= \frac{2|b| + \sqrt{4a|c|}}{a} \\ &= \frac{2|b| + 2\sqrt{\frac{a^2|c|}{a}}}{a} \\ &= 2\frac{|b|}{a} + 2\sqrt{\frac{|c|}{a}} \\ &\le 2\max(\\{|b|/a, \sqrt{|c|/a}\\}) \\ &= n\_0 \end{align}

This value for $n\_0$ includes the case $c \ge 0$. If $f$ doesn't have any roots, we can instead choose $n\_0 = 1$.

For the constants $c\_1, c\_2$ the authors gave us the values $c\_1 = a/4$ and $c\_2 = 7a/4$. To check that these are correct we do the following:

Since $n \ge 2|b|/a$ and $n \ge 2\sqrt{|c|/a}$, we know that: \begin{alignat}{3} && \frac{1}{2} &\ge &\frac{|b|}{an} \quad&\text{and}\quad &\frac{1}{4} \ge &\frac{|c|}{an^2} \\ &&-\frac{1}{2} &\le -&\frac{|b|}{an} \quad&\text{and}\quad -&\frac{1}{4} \le -&\frac{|c|}{an^2} \end{alignat}

This gives us

\begin{alignat}{2} &\frac{1}{4} = 1 - \frac{1}{2} - \frac{1}{4} \le 1 - \frac{|b|}{an} - \frac{|c|}{an^2} \le 1 + \frac{b}{an} + \frac{c}{an^2} \\ \text{and therefore}\quad &\frac{a}{4}n^2 \le an^2 + bn + c \end{alignat}

and

\begin{alignat}{2} &1 + \frac{b}{an} + \frac{c}{an^2} \le 1 + \frac{|b|}{an} + \frac{|c|}{an^2} \le 1 + \frac{1}{2} + \frac{1}{4} = \frac{7}{4} \\ \text{and therefore}\quad &an^2 + bn + c \le \frac{7a}{4}n^2 \end{alignat}

which shows that the values $c\_1 = a/4$ and $c\_2 = 7a/4$ are indeed correct.
> 2 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?
On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to $\log W$, where, I believe, $W$ is the size of the knapsack. Why is the size of the input related logarithmically to $W$?

# Answer
Polynomial time means that the running time is bounded by a polynomial *in the length of the input*. The running time here is bounded by $nW$. $n$, the number of items, is surely less than the length of the input, so that part is fine. But $W$, the target weight, is a number that appears in the input, in binary. In $\ell$ bits, you can write a number up to $2^\ell$ so $W$ is potentially exponential in the length of the input, not polynomial.
> 7 votes

# Answer
Because you normally would not encode the sizes *unary*. Note that the number "100" would need 100 bit to encode unary (as opposed to the normal 7 bit), so the size of your Knapsack problem would be gigantic, and relative to the then-gigantic size the runtime would not be that bad.
> 2 votes

# Answer
Knapsack is a weakly-NP Complete problem because when one encodes it in unary, it runs in polynomial time. However, this does not imply that P=NP it just means that you have artificially increased the input length and so it gives the illusion of running in polynomial time. Also, keep in mind that on small inputs the dynamic programming algorithm appears to be polynomial.
> 0 votes

# Answer
Think about it this way. Say you want to run the algorithm on an instance with $W=1,000,000$. When the program will ask you: \`\`Please input the value of $W$'', are you going to type 7 keys on your keyboard, or 1 million keys?
> 0 votes

---
Tags: complexity-theory, machine-learning, np, knapsack-problems
---


# Question
Title: How to determine valid handle for given bottom up parser?
I came across following question:

> Consider the grammar:
>
> $E → E + n\text{ | }E × n\text{ | }n$
>
> For a sentence n + n × n, the handles in the right-sentential form of the reduction are
> (A) $n, E + n$ and $E + n × n$
> (B) $n, E + n$ and $E + E × n$
> (C) $n, n + n$ and $n + n × n$
> (D) $n, E + n$ and $E × n$

Solution given was:

> ```
> n+n×n
> E+n×n  //reduce n to E
> E×n    //reduce E+n to E
> E      //reduce E×n to E
>
> ```
>
> Hence option D

Then I came across following problem:

> Consider the following grammar:
> $A\rightarrow A(B)|B$
> $B\rightarrow B\*C | id $
> $C\rightarrow (id)$
> Which of the following can be the correct handle in bottom up parsing for the given grammar? (A) (id)
> (B) id\*C
> (C) id
> (D) none

The given solution was (A)(id)

**Doubts**

1. After thinking about the definition of the handle and two problems, I concluded following:

* If problem asks which are valid handles for given string and grammar, then we have to actually try parsing that string with given grammar and determine which handles are reduced during parsing.
    * But, if no string is given, and just the grammar is given, then following are valid handles:
    **(a)** right hand side of each production
    **(b)** those sentential forms which can be derived from start symbol by doing rightmost derivation are valid handles. For example, $B\*(id)$ is a valid handle as we can derive it by doing rightmost derivation as follows: $S\rightarrow B\rightarrow B\*C\rightarrow B\*(id)$
2. As explained in 2nd bullet point of point 1 above, answer of 2nd problem is wrong and both of $A$ and $C$ options are correct: both $(id)$ and $id$ are valid handles.

Am I correct with both conclusions above?

# Answer
A handle is a production whose right-hand side can be reduced at a specific moment during a parse. (Or, as it is usually presented, it is the production which has been expanded at a specific point in a derivation for a sentence.) Although a handle is almost always defined as a production, it's common to talk about them as though they were just the right-hand side. That's clearly not correct because you cannot reduce a handle without knowing what it will reduce to, but in many contexts (including multiple-choice exams) it's possible to get away with this informality.

So I'd disagree that $B∗(id)$ is a handle, because it is not the right-hand side of any production. That doesn't really alter your question about whether $id$ is a handle.

A production (or its right-hand side) could be a handle for a grammar if there exists a derivation which involves that production. That is not necessarily the case for every production in a grammar, since grammars can include unreachable and useless productions. However, the grammar you present does not include any such productions. There exist derivations which use each of the productions, including $B\to id$ and $C\to (id)$. On that basis, I agree that both (A) and (C) are correct answers.
> 0 votes

---
Tags: context-free, formal-grammars, compilers, parsers
---


# Question
Title: Efficient algorithm for finding optimal sum from both arrays
I have two arrays(A,B) and a sum M. I need to find one number from each array that makes the sum M. If there is no two elements that form sum M, then nearest and less than M sum is the solution. See examples below. What is the efficient way to find the solution for this?

```
eg1:
A =[200,300,600,900]
B =[1000,200,300,500]
M = 900
Output : A(2), B(2)
600 from A and 300 from B sums 900.

eg1:
A =[200,300,600,1000]
B =[1000,400,600]
M = 1500
Output : A(3), B(1)
1000 from A and 400 from B sums 1400 which is near to the sum 1500.

```

# Answer
So rewriting my answer from the comments.

Let $n$ be the size of the input (say the total size of both arrays), then $\Omega(n \log n)$ is a reasonable lower-bound on the running time of the problem. (See this paper for a similar bound).

One way to solve it is hence to sort both arrays and then using sliding window technique (two pointers) to find two elements, one from each array, with the largest sum less than or equal to $M$. The total running time of this algorithm is $O(n \log n + m \log m + n + m)$, where the sliding window technique runs in linear time getting a total running time of $O(n\log n + m \log m)$ for $n$ the size of the first array and $m$ the size of the second one.

A slightly better solution is to sort only the smaller among the two arrays, and for each element in the other array, look up the largest element in the first array such that the sum of both elements is less than or equal to the $M$. Assuming $n \leq m$, we can get a running time of the form $O((n+m)\log n)$ using binary search for the look-ups.
> 1 votes

# Answer
There are three ways how you could proceed:

If both arrays are already sorted for example in ascending order, then you start at the beginning of the first array and the end of the last array; if the sum is too small you skip to the next element of the first array, if the sum is too large you skip to the previous element of the second array, and so on.

If one array only is sorted, then you try each element x of the other array, lookup the element closest to M - x using binary search, and use the best pair.

If neither array is sorted, you sort either one or both. Calculate the runtime of either approach; it seems best to sort the smaller array, which then takes O (n log m) where m is the size of the larger array, and m the size of the smaller array.

If the larger array is already sorted, sorting the smaller array as well may be faster, because the sorting is done in O (m log m), and the first method takes only linear time. And if the arrays are of comparable size (say $m = n^{1/2}$) so log m vs. log n doesn't affect asymptotic behaviour, then what is fastest on some implementation will depend on the actual implementation.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Minimum Clique Cover - Mixed Integer Programming
I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the vertices of the graph, that is, a partition of the graph into the smallest number of cliques. A clique is a set of nodes such that each pair of nodes is connected. I also want to maximize the sum of edge weights over the cliques. I want to use an integer programming approach for this problem.

Can any one give me some hints or some references that use mixed integer linear programming for the (maximum weight) minimum clique partition?

Thank you very much.

# Answer
> 2 votes
I think I have some suggestions. You can make a binary variable $e\_{ij}$ per edge corresponding to if those two vertices are in a clique together or not. Being in a clique is a transitive property. $e\_{ij} \wedge e\_{jk} = e\_{ik}$. This "and" constraint is expressible as a MIP. This can be achieved with the constraint $e\_{ik} \<= e\_{ij}$, $e\_{ik} \<= e\_{jk}$, $ e\_{ij} + e\_{jk} - 1 \<= e\_{ik}$ link. This is the polytope generated by the truth table vertices (0,0,0) (0,1,0) (1,0,0) (1,1,1). This makes only vertex clique covers feasible. For maximizing edge weights you're good to go.

I don't have an elegant way to minimize the total number of cliques. Just maximizing the sum of all edges is a reasonable heuristic if heuristics are acceptable. Another possibility is to take the sum of all the edges coming out of a vertex. This is the size of the clique it belongs to and is bounded by the total number of edges connected to that vertex. $\sum\_j e\_{ij} = c\_i - 1$, where $c\_i$ is the size of the clique vertex $i$ belongs to. The sum over all vertices $\sum\_j \frac{1}{c\_i} = C$ is the total number of cliques $C$. I don't have a good way to perform this inversion, except by MIP brute force.

This can be done by generating as many binary variables $a\_{in}$ per vertex as it has neighbors, setting $\sum\_n n a\_{ni}=c\_i$, enforcing that only one $a\_{ni}$ is nonzero $\sum\_n a\_{ni} = 1$, and then making the objective $\sum\_{jn}\frac{1}{n}a\_{nj}$. This is rather dissatisfying to me and I hope there is a better way.

---
Tags: graphs, linear-programming
---


# Question
Title: Competitive ratio of the ski rental problem
Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ratio for a deterministic (and non- deterministic) algorithms:

Let's say that renting costs 1 dollar a day and buying costs 10 dollars.

* Buy the skis on the day before, this means that you can decide to buy the skis and never use them even once: So if you decide on an algorithm that rents for 9 days and buys the skis on the 9th day, skiing for exactly 9 days (which is the worst-case input for that algorithm) would cost (9 + 10)/9 = 2.111...
* Buying the skis on the current day: So you wake up on the morning of day N, you know already you can ski - and then decide if you want to buy or rent. This changes the competitive ratio of the algorithm in the worst case (for the input: skiing for exactly 9 days) to be: (9+10) / 10 = 1.9

The second method was presented in the Wikipedia article as well as in *Algorithm Design and Application by Michael T. Goodrich and Roberto Tamassia*. However -it is never written explicitly when does the buying of the skis occur.

My question here is - Are these 2 problems completely different from each other? and the first one can never have a competitive ratio of 2 or less ?

# Answer
I think the first approach can give an arbitrarily bad competitive ratio for any algorithm: if we ski $0$ days, the optimal would be to neither buy nor rent (pay $0$), while *any* algorithm either buys or rents the skis before the first day (pay something $\>0$).

So the problems are different, and for the first problem we cannot have a "good" algorithm.
> 0 votes

---
Tags: online-algorithms, competitive-ratio
---


# Question
Title: What is google docs solution to handling multiple users editing and reading at the same time?
I have always been curious as to how google solved the solution of real time collaboration in their google docs product where they allow multiple users to edit and read the same document in real time.

I believe this is very similar to the well known readers and writers problem.

In some of the solutions that i have seen, we would need a mutex of some kind whereby the writers will have exclusive lock to the document itself and readers will not be able to read the document at all.

But in the google docs case, it is quite interesting whereby another user can read the document in real time and two users can both edit the same document at the same time without any conflicts which is very impressive to me.

# Answer
Note: there is no way to *know* how Google does it. All we can do is speculate based on whatever information is publicly available. If you want to *know*, you have to ask them, not us.

Google Docs' collaborative features are reportedly an offshoot of Google Wave. Google Wave, in turn, reportedly used Operational Transformation.

As a very high-level basic overview, the fundamental idea behind OT is that each collaborator has their own local copy of the document, and the editor infers an *operational transformation* based on the user's inputs. These transformations can be very simple (insert character `x` at position `y`) or more complex (perform an *extract method* refactoring of the second code block in method `foo` and name the resulting method `bar`).

These transformations are then broadcast to the other collaborators and applied to their respective copies.
> 2 votes

---
Tags: algorithms, concurrency
---


# Question
Title: Why does Min-Max algorithm delays a good move indefinitely?
Consider a simple chess example:

Q is white Queen.

K, R is black King and black Rook respectively.

```
  A B
1 . Q
2 . .
3 K .
4 . .
5 . .
6 R .
7 . .
8 . R

```

1,2...8 is the rank and A and B are the files of the chessboard.

**Assume the king can only move horizontally for this example.**

Here, if we search to depth 0, the best move should be Qxb8 (queen takes rook on B8)

But if we search for **depth 2**, then one line goes:

```
1. Qa1+ Kb3 2. Qxa6 (evaluation of the position +100 as rook is taken)

```

Second line:

```
1. Qxb8 Ra4 2. Qb1 (evaluation of the position +100 as rook is taken)

```

And since both have the same evaluation we select the first variation and play Qa1+ and let's say opposing player plays Kb3.

And now, if we again search to **depth 2**, same situation arise:

One line:

```
1. Qb1+ Ka3 2. Qxb8 (evaluation of the position +100 as rook is taken)

```

Second line:

```
1. Qxa6 Rb4 2. Qa1 (evaluation of the position +100 as rook is taken)

```

And again since both lines have the same evaluation we select the first variation and play Qb1+ and let's say opposing player plays Ka3.

And this will keep repeating and the **queen will never capture the rook** and just keep checking the king **in the hope of capturing the rook in the next move** but again repeats the same idea.

I hope this example makes it much clear what I am trying to say.

# Answer
> 5 votes
In a game-theoretical sense, both of the moves you describe are equally good in the scenarios you describe, so the algorithm is "correct" in that it doesn't matter which move it picks -- you do not explicitly encode a preference for faster wins (or faster gains of $+100$) over slower scores.

Introducing a discount factor to explicitly encode such a preference, as described in ryan's answer, can be a solution... but it's not very common in game AI / minimax / alphabeta search literature, and it can also be detrimental in slightly different scenarios. For example, if we can get a score of $+100$ in one ply, or a score of $+101$ in the second ply, we would generally prefer the path leading to that delayed $+101$... but a common choice of a discount factor $\gamma = 0.9$ would lead us to prefer the suboptimal path. Note that this does not just hold for the example of $\gamma = 0.9$; **we can come up with such a counterexample for any value $0 \leq \gamma \< 1$ that will cause the solution with discount factor to break down and lead to suboptimal behaviour**.

A more robust solution is a combination of **iterative deepening** with **move ordering**. In practice, we rarely use a plain minimax search with a predetermined depth limit. In practice, we usually do something like:

* Start out with a $1$-ply search
* Proceed to run a $2$-ply search afterwards if we still have time
* Proceed to run a $3$-ply search if we still have time
* etc.

This is referred to as iterative deepening. Now, when we start a new search (with an increased depth limit), a common trick is to first **re-order the moves at the root node based on the scores found in the previous search** (with the lower depth limit).

Now, imagine that we apply this process to the scenario described in your question. The `Qxb8` line of play will first be discovered to give a $+100$ score in one of the first iterations (shallow searches). Based on this, we will sort that `Qxb8` line to be searched before the `Qa1+` line when moving on to the next iteration with a deeper search. Both lines will then be discovered to have the same $+100$ score, but now, due to clever move ordering (**not specific to this case, but clever move ordering in general thanks to iterative deepening!**), the shorter line will have been searched first and be the preferred line of play.

---

Note that the "trick" with iterative deepening + move ordering is not just useful to solve the issue highlighted in this question, but in general can also significantly increase the number of prunings that can be achieved when we extend the basic minimax algorithms with techniques like alpha-beta pruning.

# Answer
> 3 votes
This is because you are not using a discount factor in your search.

> A **discount factor** $\gamma$ is a number between 0 and 1. The discount factor describes the preference of an agent for current rewards over future rewards. When $\gamma$ is close to 0, rewards in the distant future are viewed as insignificant. When $\gamma$ is 1, discounted rewards are exactly equivalent to additive rewards, so additive rewards are a special case of discounted rewards.

The basic problem is that you are valuing taking the rook in the *next* move the same as if you took the rook in *this* move. This is not always correct, and can get you stuck like you've seen. You need to set a discount factor of the value of the next move to something like $\gamma =$ 0.9, this way your queen will value taking the rook sooner more highly. This gets multiplied by the expected reward of the next move. See Russel & Norvig's "*Artificial Intelligence: A Modern Approach*" Section 17.1 for more on discounted rewards.

There is another common case you'll come across if you work through Berkley's AI labs. Where pac man will never eat the last dot because it thinks it can always eat it in the next move so the game never ends.

# Answer
> 1 votes
In the rules of chess, one player can demand a draw when the same position is entered three times. If your opponent can demand a draw, the value of the position is 0 in the best case. So if you look forward far enough, you see that a move leading to repetition may not be that good.

(In this case, you would choose the second best move if it has a value \> 0, or you would remain in the move repetition loop if the second best move has a value \< 0. A real player in that situation would think about how confident they are to still win when breaking the loop and entering a negative value position).

You might carefully consider if you give positions with a single repetition a value of 0. There may be a good way to break the loop at some point at the start. If you realise the repetition too late, you might not get back to the start of the loop and be able to break from it but the opponent demands a draw first.

---
Tags: algorithms, game-theory, minmax-algorithm, minimax
---


# Question
Title: Space efficient representation of Regular graphs
Let $G$ be a $k$-regular graph (each vertex have a degreee $k$). It is trivial to store the graph in $O(\log n)$ space or words such that $j$th neighbour of any vertex can be found in $O(\log n)$ time. Assume that neighbours of each vertex are ordered.

Note that $k=O(\log n)$

Is there an representation of graph $G$ that takes $o(nk)$ space in words such that query can be solved in $O(1)$

# Answer
No. Even ignoring the requirement to answer queries, you can't store such a graph in $o(nk)$ space, assuming each word is $\Theta(\lg n)$ bits long (i.e., each word has space to store the index of a single vertex).

In particular, there are ${n-1 \choose k}$ ways to choose $k$ neighbors of a single vertex, so there are ${n-1 \choose k}^n$ possible $k$-regular graphs. Now

$$\lg {n-1 \choose k}^n = n \lg {n-1 \choose k} = kn \lg(n/k) + \Theta(kn) = \Omega(kn \lg(n/k)).$$

Thus, information-theoretically, you need at least $\Omega(kn \lg(n/k))$ bits to store such a graph, or equivalently, at least $\Omega(kn \lg(n/k)/\lg n)$ words. Notice that for $k=O(\log n)$, we have $\lg(n/k)/\lg n = \Theta(1)$.

Therefore, we find that we need at least $\Omega(kn)$ words just to represent all possible $k$-regular graphs, so there is no hope for a data structure with space complexity $o(kn)$, even if you ignore the query time requirement.
> 1 votes

---
Tags: space-complexity
---


# Question
Title: largest samples of set of random variables
Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF.

We know that max of two independent random variables is: if $Z = max(X,Y)$

$pr(Z = k) = pr(X = k) pr(Y \< k) + pr(X \< k) pr(Y = k) + pr(X = k) pr(Y=k)$

Where in the above figure pr(Z=3) for instance is pr(X=3)\*pr(Y=3)+ pr(X\<3)pr(Y=3)+ pr(X=3)pr(Y\<3) so (1)(1) + (1+1)(1) + (1)(1+1+1) =7.

My question how this operation has O(nm) timing complexity where n and m are the sample size of X and Y receptively or O(n^2) when both has n samples?

According to my calculations there is only 2 multiplications and n sums involve to generate each sample, so it should be o(n), right?

# Answer
> 1 votes
Yes, you are right; the PDF of $Z=\max(X,Y)$ can be computed from the PDFs for $X,Y$ in $O(n+m)$ time, using the approach you described.

In particular, it takes $O(n)$ time to compute $P(X\<x)$ for each $x$ ($n$ sums), $O(m)$ time to compute $P(Y\<y)$ for each $y$ ($m$ sums), and $O(n+m)$ time to then compute $P(Z=z)$ for each $z$ (3 products and 2 sums for each of the possible values of $z$).

Perhaps that paper was using a sub-optimal algorithm, or maybe it was just a mistake, or maybe the author didn't care about the difference between $O(n+m)$ vs $O(nm)$ and used an overly loose bound.

---
Tags: time-complexity
---


title: Does BNF terminate on a first match?

text:
# Question
Title: Does BNF terminate on a first match?
I know that the grammar

```
<expr> = <expr> + <expr> | <num>
<num> = 0|1

```

is ambiguous because it cannot decide between (1+1)+1 or 1+(1+1). However, that would also mean that

```
<expr> = <expr> + <num> | <expr> * <num> | <num>
<num> = 0 | 1

```

would also be ambiguous because it couldn't tell if 1+1\*1+1 is (1+1)\*(1+1) or ((1+1)\*1)+1. Or does it distinguish between these by terminating the interpretation as soon as it finds one match?

If it does terminate on a first match, then would 1+1\*1+1 necessarily get interpreted as the first option since it is possible to interpret the "main operation" as being +?

# Answer
You can't match `1+2*3+4` with `expr * num` because `3+4` isn't a `num`. The only possible match is `expr + num`, with `1+2*3` as the `expr` and `4` as the `num`. To make `1+2*3` an `expr`, you need to match it with `expr * num`, and then you can match `1+2` with `expr + num`. Finally, you can match `1` with `num` to make the innermost `expr`.

So the only possible parse is `((((1)+2)*3)+4)` and the grammar is not ambiguous.

It is not the grammar we usually use for algebra because it produces an undesired parse, not because it is ambiguous.
> 2 votes

---
Tags: formal-grammars
---


# Question
Title: Reducing the halting problem for a language with strings that include at least one 1
$L\_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence

$L\_2$ = Turing machines that decide $L\_1$

I think the first language is decideable, as the input string is of finite length and you can check every character in the string.

However, my intuition says the second language is undecideable. This would be like checking if a TM is equal to a TM that decides $L\_1$.

Am I correct? And if so, how should I proceed to reduce the halting problem to $L\_2$?

# Answer
**Original Question:**

$L\_1 = \\{w \in \\{0|1\\}^\* | \text{ w is a sequence of one or more 1's } \\}$

$L\_2 = \\{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \\}$

prove that $L\_2$ is undecidable.

---

**Answer:**

For first part you are correct. First language $L\_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$.

Now coming to second one $L\_2$. This language is as you said undecidable. And you can prove it by reducing halting problem which is known to be undecidable to this problem.

For doing this you have to create an instance of problem in question such that solving it gives us solution of halting problem.

Now formally we can define turing machine $\tau\langle M, w\rangle =M'$. Where $M'$ is a turing machine which started on input $x$ checks if $x$ is of form $1^+$. If no then it rejct it immediately. Otherwise it erases $x$ from it's tape then copies $M$ and $w$ on its tape and simulates $M$ on $w$. If $M$ stops then it accepts $x$(which it have erased).

Proof of validity of reduction:

$M$ halts on $w$ $\implies$ $M'$ accepts all and only strings of form $1^+$.

$M$ does not halt on $w$ $\implies$ $M'$ accepts empty set. In particular it does not accept strings of form $1^+$.

So now if there would be any turing machine that decides $L\_2$ then we can use it to find whether $M'\in L\_2$ or not? If it outputs yes then we infer that original $M$ halts on $w$. Otherwise we infer that $M$ does not halt on $w$.

And because we know that halting problem is undecidable we conclude that no such turing machine exists which can decide $L\_2$ and consequently $L\_2$ is undecidable.

Hence proved.
> 2 votes

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


# Question
Title: What does atomicity mean in distributed systems?
In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem?

Does atomicity have a different meaning in this context?

# Answer
There is one primary meaning of the word "atomicity", and one additional property that some people use on occasion.

The primary meaning is that a complex operation (usually called a "transaction"), which requires multiple parties to take action, either happens or doesn't happen. It can't happen only in part.

One classic example (because this is one domain where atomicity is more important than most other considerations) is transferring money from one bank account to another bank account at a different bank. Think of the banks as communicating agents (possibly involving other agents, like an arbitrator or broker). Conceptually, one bank needs to subtract some amount from a number held somewhere, and the other bank needs to add the same amount. The important part is that either both pieces of arithmetic happen or neither happen. What is not allowed is for money to be created or destroyed.

The additional property that some people add is that all agents, or at least the initiating agent, must be able to know in a timely manner whether the transaction happened or didn't happen. Think of a file system sync operation, for example. If that operation returns and signals that it was successful, the client can assume that any data and/or metadata written to the file system before the sync operation has been committed to secondary storage.
> 3 votes

# Answer
Atomicity is different in terms of distributed systems. An atomic operation in distributed systems is an operation whose execution is performed as an individual action.
> 0 votes

---
Tags: distributed-systems, consensus
---


# Question
Title: Does topological sort exist for any complete directed acyclic graph?
Let's assume that DAG is complete: there is directed edge among every to nodes. Does topological sort of vertices exist for any such graph? I.e. is it possible to make linear list of nodes in which the left node has edge into the right node. Maybe this is the question about existence of Hamiltonian path in every complete DAG?

# Answer
Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a linear ordering means to prove it is reflexive, asymmetric and transitive).
> 2 votes

---
Tags: graphs, sorting, dag, hamiltonian-path
---


# Question
Title: How can I determine if two vertices on a polygon are consecutive?
Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices on the polygon. Does anyone know of an algorithm that would do this, as in you would input the array of points and the two vertices as parameters and it would return a boolean?

It's given that the polygon exists and is unique.

# Answer
As the polygon is convex, it is simple! Two vertices are consecutive if all other vertices are located on the same side of the line that goes through these two points. This means that the cross product of the vector feom one of the pionts to the other one with the vector from the first point to any other one in the polygon have the same sign (all negative or all positive). For example, if those two points are called $P\_1$ and $P\_2$, you should compute all cross product of $\langle P\_1, P\_2\rangle$ with $\langle P\_1, P\_i\rangle$ ($P\_i$ here means all other vertices).

Also, as discussed in the comment, we have some *degenerate cases*. The degenerate case is a common phenomenon in computational geometry, that is mostly handled separately. Here, the degenerate case is three points are located on a line.
> 12 votes

# Answer
Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.
> 5 votes

# Answer
An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be very good if you need to work with the same polygon for many calculations as most work is done upfront but afterwards the cost of determining if two points are neighbors is very small.

So how do we sort the array?

Let's say we have an array of our unsorted points where each point contains its x and y coordinates.

```
var points = [{x:1, y:0}, {x:6, y:8}, {x:-10, y:12} ...etc]

```

First we want to find the left-most and right-most points i.e highest and lowest x-values. A function for this would look like the following:

```
//input the array of unsorted points
//also assuming a valid non-empty array
function getLeftMostPoint(points){
    //the point with the lowest x value.
    var leftMostPoint = points[0];
    for(var i = 1; i < points.length; i++){
        if(points[i].x < leftMostPoint.x){
            leftMostPoint = points[i];
        }
    }
    return leftMostPoint;
}

```

The rightmost point would be near-identical but the less-than would be swapped for a greater-than.

Next up we imagine we draw a line from our left-most point to our right-most point. Then we group all remaining points into two categories; those below the line and those above it.

```
//assuming we have left and rightmost points from above
//we are looping over the points (not shown here) and passing each one
//as the current point in this function
//this will return a number.
//If positive it means the current point is "above" the line
//negative means below the line and 0 means on the line.
function overOrUnder(leftMostPoint, rightMostPoint, currentPoint){
    return (currentPoint.x - leftMostPoint.x) * (rightMostPoint.y- leftMostPoint.y) - (currentPoint.y - leftMostPoint.y) * (rightMostPoint.x- leftMostPoint.x);
}

```

Now assuming we have stored all the points under/over into their own arrays we have all the info needed to build our sorted array or points.

1. We choose our starting point as the leftmostpoint
2. Then we add all values in the over array in x-ascending(smallest first) order.
3. Add the rightmostpoint
4. Add the values in the under array in x-descending order(biggest first)

The result is an array where each point connects to the next point in the array and the final point connects back to the first. Note that this method gives a non-intersecting polygon as its result regardless of if the input is convex or concave. The output will only be guaranteed convex if the input is guaranteed convex.

See below for more complete code

```
//Input: array of unsorted polygon points
//Output: NEW array of sorted polygon points
function sortPoints(points){
    var sortedPoints = [];

    //Get the leftmost and rightmost points
    var leftMost = getLeftMostPoint(points);
    var rightMost = getRigthMostPoint(points);

    //array to hold the points that are over/under or middle(on the line)
    var over = [];
    var under = [];
    var middle = [];

    //loop the points and put them in the appropriate array depending on where they sit relative to the line
    for(var i = 0; i < points.length; i++){
        //dont want/need to sort the left and right points
        if(points[i] != leftMost && points[i] != rightMost){
            var side = overOrUnder(leftMost, rightMost, points[i]);
            if(side < 0){
                under.push(points[i]);
            }else if(side > 0){
                over.push(points[i]);
            }else{
                middle.push(points[i]);
            }
        }
    }

    //There's an edge case with convex polygons where we don't know whether
    //points on the line, i.e in the middle array, should be assigned to the over or
    //under. The answer is we put them in the array which is empty
    if(middle.length > 0){
        if(over.length == 0){
            over = middle;
        }else{
            under = middle;
        }
    }

    //as explained above we sort one descending and the other ascending.
    over.sort(function(a, b){
        return a.x - b.x;
    });

    over.sort(function(a, b){
        return b.x - a.x;
    });

    //now build up the array like explained above
    sortedPoints.push(leftMost);
    sortedPoints = sortedPoints.concat(under);
    sortedPoints.push(rightMost);
    sortedPoints = sortedPoints.concat(over);

    return sortedPoints;
}

function getLeftMostPoint(points){
    //the point with the lowest x value.
    var leftMostPoint = points[0];
    for(var i = 1; i < points.length; i++){
        if((points[i].x < leftMostPoint.x) || (points[i].x == leftMostPoint.x && points[i].y > leftMostPoint.y)){
            leftMostPoint = points[i];
        }
    }
    return leftMostPoint;
}

function getRightMostPoint(points){
    //the point with the lowest x value.
    var rightMostPoint = points[0];
    for(var i = 1; i < points.length; i++){
        if((points[i].x > rightMostPoint.x) || (points[i].x == rightMostPoint.x && points[i].y > rightMostPoint.y)){
            rightMostPoint = points[i];
        }
    }
    return rightMostPoint ;
}

function overOrUnder(leftMostPoint, rightMostPoint, currentPoint){
    return (currentPoint.x - leftMostPoint.x) * (rightMostPoint.y- leftMostPoint.y) - (currentPoint.y - leftMostPoint.y) * (rightMostPoint.x- leftMostPoint.x);
}

```

And there we have it! and now to check if points are next to each other is easy something like:

```
//given sorted array is available
//this would return a boolean indicating whetehr point 1 and point 2 are next to each other
function(p1, p2) {
    var neighbours = false;
    var p1Index = sortedPoints.indexOf(p1);
    var p2Index = sortedPoints.indexOf(p2);

    //one index apart next to each other
    //or the edge cases where the points are at the start and ends of the array
    if (Math.abs(p1Index - p2Index) == 1) {
        neighbours = true;
    } else if (p1Index == 0 && p2Index == sortedPoints.length - 1) {
        neighbours = true;
    } else if (p1Index == sortedPoints.length - 1 && p2Index == 0) {
        neighbours = true;
    }
    return neighbours;
}

```
> 4 votes

---
Tags: algorithms, computational-geometry, polygons
---


# Question
Title: How to compute total number of subsequences of length k from a word of length N?
A subsequence of a word is obtained by dropping some letters from it. The letters that are dropped need not be consecutive. For instance, ba, bna and banaa are all subsequences of the word banana. We are interested in counting the number of distinct subsequences of a fixed length of a given word. For example, the word banana has 11 different subsequences of length 3: {aaa, aan, ana, ann, baa, ban, bna, bnn, naa, nan, nna}. Observe that the number of subsequences of length k of abcbbcaacaab that end in a ‘c’ is the same as the number of subsequences of length k−1 of abcbbcaa. In each of the following cases, you are given a word and a number N. You have to compute the number of different subsequences of length N of the given word. (a) tinnitus, 3 (b) gobbledygook, 4 (c) gargantuan, 5

# Answer
> 1 votes
Let $\Sigma$ be your alphabet, and $w \in \Sigma^\*$ be your word. Let $w\_i$ be the word consisting of the first $i$ characters of $w$ (for $i \le 0$, $w\_i$ is the empty word $\varepsilon$). For $c \in \Sigma$, let $S\[i,k,c\]$ be the number of subsequences of $w\_i$ that end with character $c$ and have length $k$. Moreover, for a word $w'$, let $\ell\_c(w')$ be the index (counting from $1$) of the last occurrence of character $c$ in $w'$, if any, and $\ell\_c(w')=0$ otherwise.

Then, for any $c \in \Sigma$, you have

$$ S\[i,1,c\] = \begin{cases} 0 & \mbox{if } w\_i \in ( \Sigma \setminus \\{ c \\})^\* \\ 1 & \mbox{otherwise} \end{cases}, $$ notice, in particular, that the above formula implies that $S\[i,1,c\] = 0$ whenever $i \le 0$, as $w\_i = \varepsilon \in ( \Sigma \setminus \\{ c \\})^\*$. In fact, for $i\le 0$, we have: $S\[i,k,c\] = 0$ regardless of $c$ and $k \ge 1$.

For $i\>0$ and $k \> 1$, the property that is hinted in your questions implies that: $$ S\[i,k,c\] = \sum\_{c' \in \Sigma} S\[\ell\_c(w\_i)-1,k-1,c'\]. $$

Since all $\ell\_c(w\_i)$ can be precomputed in $O(|\Sigma| \cdot |w|)$ time, each of the $O(|\Sigma| \cdot |w| \cdot N)$ values $S\[i,k,c\]$ can be found in $O(|\Sigma|)$ time using above equations, and this immediately yields a dynamic programming algorithm with complexity $O(|\Sigma|^2 \cdot |w| \cdot N)$, where the quantity you're looking for is exactly: $$ \sum\_{c \in \Sigma} S\[|w|,N, c\]. $$

By storing the quantities $\sum\_{c \in \Sigma} S\[i, k, c\]$ as soon as all the entries $S\[i, k, \cdot\]$ are known you can compute each entry in constant time, improving the overall time complexity to $O(|\Sigma| \cdot |w| \cdot N)$.

**EDIT**

As an example let's compute the number of subsequences of length $3$ of the word $w=banana$. Here are the values of $S\[i,1,c\]$ for $i \ge 1$, where the $i$-th row from the top contains the values $S\[i,1, \cdot\]$ is is labeled with the $i$-th character of $w$, so that $w\_i$ is the string consisting of the labels of the first $i$ rows. The values $S\[\cdot ,1, c\]$ are on the column labelled $c$. Essentially, $S\[i,1,c\]$ is $1$ if $w\_i$ contains character $c$.

$$ \begin{array}{c|c|c|c|} i \backslash c & a & b & n \\ \hline b & 0 & 1 & 0 \\ \hline a & 1 & 1 & 0 \\ \hline n & 1 & 1 & 1 \\ \hline a & 1 & 1 & 1 \\ \hline n & 1 & 1 & 1 \\ \hline a & 1 & 1 & 1 \end{array} $$

Let's now compute the values $S\[i,2,c\]$. As an example, consider $S\[5,2,a\]$. Since the last occurrence of $a$ in $w\_5 = banan$ is in position $4$, we have $\ell\_a(w\_5)=4$. Using the formula above we can write $S\[5,2,a\]$ as $$ S\[5,2,a\] = S\[3,1,a\] + S\[3,1,b\] + S\[3,1,n\] = 1 + 1 + 1 = 3. $$

Another example is $S\[2,2,n\]$, for which $\ell\_n(w\_2) = \ell\_n(ba) = 0$ and: $$ S\[2,2,n\] = S\[-1,1,a\] + S\[-1,1,b\] + S\[-1,1,n\] = 0 + 0 + 0 = 0, $$ since $S\[-1, 1, \cdot\] = 0$. Repeating this process for all $i=1,\dots,6$ and $c \in \\{a,b,n\\}$ we obtain:

$$ \begin{array}{c|c|c|c|} i \backslash c & a & b & n \\ \hline b & 0 & 0 & 0 \\ \hline a & 1 & 0 & 0 \\ \hline n & 1 & 0 & 2 \\ \hline a & 3 & 0 & 2 \\ \hline n & 3 & 0 & 3 \\ \hline a & 3 & 0 & 3 \end{array} $$

We can finally consider the values $S\[i,3,c\]$. Since we only care about the sum $S\[6,3,a\] + S\[6,3,b\] + S\[6,3,n\]$, it suffices to compute these values. Notice that $$ \ell\_a(w\_6) = \ell\_a(banana)= 6 \\ \ell\_b(w\_6) = \ell\_b(banana)= 1 \\ \ell\_n(w\_6) = \ell\_n(banana)= 5, $$
and hence we have:

$$ S\[6,3,a\] = S\[5,2,a\] + S\[5,2,b\] + S\[5,2,n\] = 3 + 0 + 3 = 6 \\ S\[6,3,b\] = S\[0,2,a\] + S\[0,2,b\] + S\[0,2,n\] = 0 + 0 + 0 = 0 \\ S\[6,3,n\] = S\[4,2,a\] + S\[4,2,b\] + S\[4,2,c\] = 3 + 0 + 2 = 5. $$.

I.e., the number of subsequences of length $3$ in $banana$ is $6 + 0 + 5 = 11$, which matches your example.

---
Tags: dynamic-programming, combinatorics, combinatory-logic
---


# Question
Title: Modeling a set of probabilistic concurrent processes
I'm looking into discrete-time Markov chains (DTMCs) for use in analyzing a probabilistic consensus protocol. One basic thing I haven't been able to figure out is how to model a set of independent processes: consider $N$ processes. These processes will concurrently execute a series of identical instructions labeled $0, 1, 2, 3,$ etc. and all are starting in instruction $0$. When probability is not involved, modeling this is simple: it's a state machine which branches nondeterministically off the start state to $N$ different states, where in each of those $N$ states a different process was the first to execute instruction $0$. What do we do when probability is involved? Do we do the same thing with $N$ states branching from the start state, where the probability of transitioning to each state is $\frac{1}{N}$? As in, it's uniformly random which process was the first one to execute instruction $0$?

Is this like taking the product of the state machines of each process?

I'm using a DTMC here, would I gain anything by moving to a CTMC if I don't care about anything beyond the global order of execution?

Bonus question: assigning probabilities to whichever action is taken first seems like a generalization of the non-probabilistic notion of fairness; if it is, what is the formal definition of this generalized notion of probabilistic fairness?

# Answer
> 1 votes
I will again refer to a lecture by Prof. Katoen.

What you need here is a way of combining the DTMCs. The problem is, that a combination of DTMCs does not give you a new DTMC. This is because you want to model the choice which of the $N$ processes proceeds nondeterministically. That is, you don't know anything about which process executes the next instruction.

For this, you have a new kind of probabilistic system - Markov Decision Processes (MDPs). In an MDP, you first choose which action in a state you will take. This action enables a probabilistic distribution (similar to DTMCs) which determines the probability of the next state. Notice that an MDP reduces essentially to a DTMC when only one action is always possible.

So to model your $N$ processes, you would combine their DTMCs, let's say $D\_i$ into an MDP where states are of the form $\langle p\_1, p\_2, \ldots, p\_n \rangle $ and in each state there are $N$ actions, denoted $\alpha\_i$. If you take action $\alpha\_i$, then you go to a state where only $p\_i$ changes to $p\_i^\prime$ according to the distribution of the process $i$. This way you compose your $N$ processes into one single system very similarly to making a product of state machines.

To analyze the resulting MDP, you can resolve the nondeterminism by all sorts of schedulers. But that this I think out of scope. Nevertheless, you could use a uniformly randomized scheduler as you hinted in you question - then every action is selected with a uniform probability.

# Answer
> 1 votes
One approach is to model it as a composition of $N+1$ processes: a scheduler process, plus your $N$ basic processes. At each time step, the scheduler process selects which basic process will execute next. Your scheduler could be randomized: for instance, at each time step, it could choose which basic process to execute next uniformly at random, if you wanted.

Now the transitions of the entire system, and their probabilities, should be easy to derive. A state of the system is of the form $\langle s\_0,s\_1,\dots,s\_N \rangle$ where $s\_0$ is the state of the scheduler and $s\_i$ is the state of the $i$th basic process. Each transition might have the form $\langle s\_0,\dots,s\_N \rangle \to \langle s'\_0,s\_1,\dots,s\_{i-1},s'\_i,s\_{i+1},\dots,s\_N \rangle$ (where $i$ is a deterministic function of $s\_0$, and with probability given by the probability of $s\_0 \to s'\_0$ in the scheduler multiplied by the probability of $s\_i \to s'\_i$ in the $i$th basic process).

There are probably other ways to model it as well, maybe better ones for all I know. This is just one possibility that occurs to me.

---
Tags: formal-methods, model-checking, markov-chains
---


# Question
Title: How can I prove the minimum pumping length of finite language?
> Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the smallest possible pumping length associated with L?

For this problem, I think minimum pumping length for this language should be 4, because if pumping length is smaller than or equal to 3, then $xy^{i}z$ may not be in the given language, because its length could be longer than 3. So, I want to prove that 4 is the minimum pumping length for the given language, but I have no idea how to prove it accurately. The explanation I wrote here is too informal, I think. Can anyone help me?

# Answer
> 3 votes
You explanation sounds good (you want to change "smaller than" in "smaller than or equal to").

Suppose towards a contradiction that the pumping length was $k \le 3$ then, since $w=000$ is a word of length at least $k$ in $L$, you could invoke the pumping lemma to conclude that $w$ can be written as $w=xyz$, with $|y|\>0$, in such a way that $xy^ik \in L$ for any choice of $i \ge 0$.

This is a contradiction since the choice $i=4$ yields a word $w'$ of length $|w'| = |x| + 4 |y| + |z| \ge 4$ for which you simultaneously have $w' \in L$ (by the Pumping Lemma) and $w' \not\in L$ (by the definition of $L$).

In addition, to show that $k'=4$ is the smallest possible pumping length, you need to argue that $4$ is a valid choice for the pumping length. In your case this is trivial as the pumping lemma gives you a property over the set of all words in $L$ of length at least $k'$. For $k'=4$ this set is empty, which makes the statement trivially true.

---
Tags: pumping-lemma
---


title: High-dimensional geometry and P vs. NP

text:
# Question
Title: High-dimensional geometry and P vs. NP
**Background:** Recently, I obtained the following equivalent problem to SAT. We are given as input a CNF formula with $n$ variables and $m$ clauses. Suppose we have an $n$-dimensional hyper-cube centered at the origin. We perform the following cut-and-color operation $m$ times, each time for a clause.

Let’s say there are $k$ literals in this clause. For the $i$th literal with variable numbered $x$ and sign $s$, we cut the hyper-cube or what is remaining with the hyper-plane perpendicular to $x$th axis and keep the $s$-signed half. After $k$ times cutting, color the remaining part red.

If, after all clauses have been processed this way, the entire hyper-cube is red, announce UNSAT. Otherwise announce SAT.

This is the problem. Basically an uncolored part corresponds to an assignment whose *reverse* is satisfiable, because no clause *covers* this assignment or, in other words, this assignment does not contain any clause when both assignments and clauses are viewed as sets.

Phrased this way, SAT is really a geometric representation problem, and the key is to keep track of colored parts with only polynomial-sized storage.

**Question:** What is known about high-dimensional geometry of a hyper-cube, especially related to this problem? My current difficulty is with visualization.

**Difficult example:** Consider the following simple CNF formula: $$(x\_1\lor x\_2)\land(x\_3\lor x\_4)\land\cdots\land(x\_{2k-1}\lor x\_{2k}),$$ or in DIMACS format

```
1 2
3 4
...
2k-1 2k

```

where $k\>0$. The challenge is to represent the colored parts by (preferably polynomially many) *non-overlapping clauses* only. Below is the best I can do:

* $k=1$:

```
1 2

```
* $k=2$:

```
1 2
-1 3 4
1 -2 3 4

```
* $k=3$:

```
1 2
-1 3 4
1 -2 3 4
-1 -3 5 6
-1 3 -4 5 6
1 -2 -3 5 6
1 -2 3 -4 5 6

```
* $k=4$:

```
1 2
-1 3 4
1 -2 3 4
-1 -3 5 6
-1 3 -4 5 6
1 -2 -3 5 6
1 -2 3 -4 5 6
-1 -3 -5 7 8
-1 -3 5 -6 7 8
-1 3 -4 -5 7 8
-1 3 -4 5 -6 7 8
1 -2 -3 -5 7 8
1 -2 -3 5 -6 7 8
1 -2 3 -4 -5 7 8
1 -2 3 -4 5 -6 7 8

```

As you can see, it's growing exponentially.

**Partial question:** Do you have a way to do this example (not the general problem) using only polynomially many clauses? This is the difficulty I can't handle right now. It's easy to see that the interactions among the original clauses grow exponentially with $k$. So if you can prove that this example is impossible to do, then this non-overlapping-clauses approach won't work and we need to find something else.

**Code:** I posted my code here. My approach was implemented but it’s still exponential without the partial problem above solved. You can observe that.

One potential weakness is that any algorithm implementing my idea can actually count the number of satisfying assignments, solving a #P-complete problem. Not only that, it remembers in memory exactly which assignments are not satisfying (one simple way to do this is to just remember the initial clauses) and it can enumerate these without much overhead, because the final clauses are non-overlapping. Is that something enough to prove my idea is always exponential-time?

# Answer
The answer to the partial question is no. It’s impossible to be so efficient by a counting argument. First, there are $2^n$ cells, each of which is either colored or not. So there are $2^{2^n}$ possible configurations, each of which has to be represented in polynomial space. This is impossible.
> 0 votes

---
Tags: complexity-theory, computational-geometry, satisfiability
---


# Question
Title: The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular
This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)

# Answer
> 0 votes
I am purposefully not going though all the steps required to solve the exercise (comment if you need more help).

You might want to have a look at pumping lemma for regular languages.

It gives you a property that all regular languages must satisfy. If you want to show that a language $L$ is *not* regular, you can show that this property cannot hold. In practice, the proof usually follows these steps:

* assume towards a contradiction that $L$ is regular
* choose a suitable word $w \in L$
* apply the pumping lemma on $w$ to conclude that a new word $w'$ must belong to $L$
* Use the language definition to show that $w'$ does not belong to $L$ (hence the contradiction).

Hint:

> Here is a string $w$ that belongs to your language: $a^n b^n$, for a sufficiently large integer $n\>0$.

---
Tags: regular-expressions
---


# Question
Title: Converting a greedy algorithm to a dynamic programming algorithm
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:

First, find a maximum indpendent set of vertices in the graph, and give it one color.

Next remove the set of vertices found in the previous case from the graph, and repeat the same process till I reach the empty set.

Now, I agree that it is hard to find the maximum independent set of an arbitrary graph. But, is there a way where this greedy sort of simple algorithm could be converted to a dynamic programming type algorithm? Say, may be we could decompose the graph into two simpler graphs and find maximal independent sets in each of the subgraphs, and then try to club the two individual independent sets to form a larger independent set by checking for adjacency. Is such a kind of 'conversion' from greedy to dynamic programming or vice-versa always possible? Can this change the complexity of the problem radically? Thanks beforehand.

# Answer
> 3 votes
The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to comment on this area, you might find the answer you are looking for among which.

The first one, which is not an answer, but an important notice, is that even though you suggested a (dynamic programming) solution of independent sets, this dynamic program has to consider all partitions of the vertices to find an optimal set. There is probably no dynamic programming solution to this problem that runs in polynomial time, since this will mean that P=NP due to the fact that the maximum independent set problem is NP-complete. However, even though we expect the running time to be exponential, you can solve the problem using only polynomial memory using for example the inclusion exclusion principle (refer to Parameterized algorithms book by Cygan et. al.).

Now back to your question, dynamic programming is usually used to solve generalized versions of greedy problems. For example maximum independent set, maximum matching and minimum dominating set can be found in linear time on trees using greedy algorithms. Greedy algorithms fail however, if the tree is weighted and we are looking for the structure optimizing the total weight. However, these problems can easily be solved in a bottom up dynamic programming manner in linear time, where the dynamic programming states are the subtrees of the given tree.

The third and probably the more interesting part, many problems (even some NP-hard ones) in general graphs admit a dynamic programming solution on the tree decomposition of the given graph. The optimal solutions still have exponential dependence on the tree width. However, they have only polynomial/linear dependence on the size of the input. Usually these problems admit greedy/dynamic programming algorithms on trees, since these algorithms use the fact that a tree decomposition decomposes the graph into small separators, which is trivial in trees. (Again refer to Parameterized Algorithms book by Cygan et. al.)

---
Tags: complexity-theory, graphs, dynamic-programming, greedy-algorithms, divide-and-conquer
---


# Question
Title: Turing Machine to return all prime numbers
My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not.

So no matter what the input is, we should ignore it. I think it would be sufficient to add another tape with cells $1^\*,2,\dots,n$. Now, I would use Sieve of Eratosthenes algorithm as follows:

1. Move a head to the right until the head encounters an unmarked symbol.
2. Mark the symbol with a star and write it down to another write-only tape representing the output, i.e. the symbol is a prime number.
3. Now, for $n$ being prime, I am supposed to mark every $n$-th symbol with a star. I am not sure how to do it.
4. Reset.

For the third step, I think I should utilize another marking mechanism to denote a gap between the beginning and the prime resolved in that round. Then, I would be moving that "window" and whenever the beginning of the "window" would reach the prime, I would mark the symbol at the end of the "window" with a star. Not sure how to express this formally.

# Answer
Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient.

The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow:

1. Start with $n=2$ \- this is prime.
2. Set $j$ equal to $n$.
3. Add $1$ to $n$
4. Set $k$ equal to $n$.
5. Subtract $j$ from $k$.
6. If $k$ is greater than $0$ go to step $5$.
7. If $k$ equals $0$ then $n$ is not prime; go to step $2$.
8. Subtract $1$ from $j$.
9. If $j$ equals $1$ then $n$ is prime; go to step $2$.
10. Go to step $4$.
> 2 votes

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


# Question
Title: Give an implementation leveldescription of a TM
L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z}

is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM that decides on L?

# Answer
There is an important gap between human reasoning ("high level") and the formal definition of a *Turing Machine* ("low level"). If you are approaching these exercises for the first time and you are not yet familiar with *TMs*, what I recommend is to write down a pseudocode description of the algorithm which is nothing more than a high level description of the Turing machine itself) and then to "break up" the algorithm into smaller entities, until the transition function of the machine is achieved.

In the case of your example you can consider $x$, $y$ and $z$ as binary encodings of integers, then you need a function that does the following:

1. Read the input $($$x$, $y$, $z$$)$
2. Compute $y \oplus z$
3. Compare $($$y \oplus z$$)$ to $(x)$

If the equality in point *3* is verified, accept the language. This *TM* will always accept membership in your language $L$.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?
I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is extremely redundant. Is there any algorithm to circumvent this?

# Answer
> 1 votes
Pathfinding algorithms that are able to recompute the best path when the graph changes without doing a full recomputation are called "Incremental".

The incremental version of Dijkstra's algorithm has the horrible name DynamicSWSF-FP.

The *much* more common algorithm which combines this with A\* is called LPA\*

# Answer
> 0 votes
You could compute a full Single Source Shortest Paths (SSSP) at the beginning for both of your vertices (s and t).

Then, whenever you add an edge, you update only the shortest paths affected, i. e. you check whether the edge uv provides an improvent for sv, su, tv or tu. If not, your SSSP is still correct. If it gives an improvement, you then also have to check the neighbors for updates. This cascades similarly as the Dijkstra algorithm.

I can't come up with an asymptotic bound right now, but unless the graph and insertion order are chosen adversially, a single edge really shouldnt often invoke a change in large parts of the graph (and when it happens, you *have to* recompute anyway).

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


title: High-level description of aTM

text:
# Question
Title: High-level description of aTM
If I have language:

```
L = {x | x = n^2 for some integer n}

```

How can I give a high-level description of Turning Machine that decides on the language?

# Answer
Perhaps the simplest way is to implement the following algorithm:

1. Initialize $y$ to 0
2. Initialize $n$ to 0
3. Compare $y$ to $x$; if $y = x$, accept; if $y \> x$, reject; otherwise, continue
4. Add $2n+1$ to $y$
5. Increment $n$ by 1
6. Jump to 3

The idea is that $y = n^2$ always. This is ensured using the formula $(n+1)^2 = n^2 + (2n+1)$.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: How complete directed graph with n-vertices is connected to the n-dimensional simplex and its triangulation?
Answer https://stackoverflow.com/a/26151549/1375882 suggests that Sperner's lemma can be used to prove the existence of index for the search Hamiltonian path in complete directed graph. But Sperner's lemma is about simplex, its triangulation and colouring. How such notions can be mapped to the complete graph with n-vertices?

# Answer
Here is what it boils down to. There are $n$ vertices $v\_1,\ldots,v\_{n-1},v$. For each $i$, there is an edge either from $v$ to $v\_i$ or from $v\_i$ to $v$. We need to show that one of the following holds:

* There is an edge from $v$ to $v\_1$.
* There is $i \< n-1$ such that there are edges from $v\_i$ to $v$ and from $v$ to $v\_{i+1}$.
* There is an edge from $v\_{n-1}$ to $v$.

Let $x\_i$ be a Boolean variable denoting that there is an edge from $v$ to $v\_i$. Then we need to show that the following DNF is a tautology: $$ x\_1 \lor (\lnot x\_1 \land x\_2) \lor \cdots \lor (\lnot x\_{n-2} \land x\_{n-1}) \lor \lnot x\_{n-1}. $$ Hopefully you can manage to prove this yourself. It just states that if we have a string of 0s and 1s, then one of the following must happen:

* The string starts with 1.
* The string contains 01.
* The string ends with 0.

The easiest way to see this is to prove the following:

> If a binary string starts with 0 and ends with 1, it must contain 01.

This is just the trivial one-dimensional case of Sperner's lemma.
> 1 votes

---
Tags: graphs, hamiltonian-path
---


# Question
Title: An example of a context-sensitive grammar for a given language
Consider this language: $L = \\{a^nb^ma^nb^m \mid n,m \ge 1\\}$. Can we give for this language a context-sensitive grammar?

# Answer
> 1 votes
## Your request is easily served!

$$\begin{array}{lcl} &S &\to &abab\\ &ba &\to &bbBa\\ &Ba &\to &aB\\ &Bb &\to &bb\\ &ba &\to &bAaa\\ &bA &\to &Ab\\ &aA &\to &aa\\ \end{array}$$

## There is some theory to help you make sense of this solution.

Let us first consider a simpler language that manifests the same difficulty: $L = \\{a^nb^ma^n ∣ n,m \ge 1\\}$. Imagine it as a sea of $b$ between the shores of $a$, if you please.

We would like to grow the shores so that they are always the same size. One immediate way is to have a collection of rules like $a + b^m + a \to aa + b^m + aa $. But we see it will not serve our needs, as, our collection being finite *(grammars are required to have a finite set of rules)*, there is always some choice of $m$ that is not accomodated. So evidently there is a trick.

The trick is to introduce a non-terminal *"ship"* that will sail across the sea and deliver the information from one shore to the other. When the left shore grows, it will send a ship to the right shore, and when the right shore receives a ship, it will also grow, thus maintaining the required equilibrium. How can we sail a ship? $Ba \to aB$ is one way to move it one unit of sea rightwards. What remains to be put in place is a shipyard $ba \to bbBa$ and a port $Bb \to bb$.

Here is what we get:

$$\begin{array}{lcl} &S &\to &bab\\ &ba &\to &bbBa\\ &Ba &\to &aB\\ &Bb &\to &bb\\ \end{array}$$

I am sure you can see how to extend this to your original language: you will need the sea people to also send some sort of messenger golems $A$ across the land to the sea on the other side of $b$.

Happy adventures in fantasy grammar land!

---
Tags: formal-languages, formal-grammars, context-sensitive
---


# Question
Title: Recurrence Question:T(n) = T(n − √ n) + T( √ n) + θ(n)
I need help to solve the recurrence T(n) = T(n−√n) + T(√n) + θ(n)

# Answer
> 2 votes
The solution is $T(n) = \Theta(n^{3/2})$.

For the lower bound, note that $T(n) \geq T(n-\sqrt{n}) + \Theta(n)$. Iterating this for $\sqrt{n}/2$ steps, the value of the parameter never drops below $n/2$, for a total contribution of $\Omega(n^{3/2})$.

For the upper bound, let us notice first that $$(n-\sqrt{n})^{3/2} \approx n^{3/2} - \sqrt{n} \frac{d}{dn} n^{3/2} = n^{3/2} - \Theta(n). $$ This allows us to prove the upper bound $T(n) = O(n^{3/2})$ by induction.

---
Tags: recurrence-relation
---