# Question
Title: Sorting by boolean algebra (hardware) instead of algorithm (software)
Consider there's an 5 elements list that foreach element are 2-bits. Forexample \[01,00,10,00,11\], if the list is sorted, we hope the output like this \[00,00,01,10,11\]

Maybe that case seems complicated, let's move to simple case.

Consider there's an 2 elements list that foreach element are 1-bit. Forexample \[1,0\], if the list is sorted, we hope the output like this \[0,1\].

If that simple case is written in general we can make that list like this \[A,B\] where if the list is sorted the output will be \[X,Y\] For A,B,X,and Y are 1-bit. (Only 0 and 1)

Hence, we can make this general case to truth table

```
A B X Y
0 0 0 0 (already sorted)
0 1 0 1 (already sorted)
1 0 0 1 (sorted)
1 1 1 1 (already sorted)

```

From truth table we got the boolean algebra equation X=AB Y=A+B So that we can conclude the sortened list of \[A,B\] is \[AB,A+B\]

From boolean algebra equation we can design the hardware with logic gate. We can see it only need an AND GATE and an OR GATE.

From simple case we can make it complicated again like first case i mention with 5 elements and for every elements are 2-bits also we can make the device with logic gate.

The question is, any there processing unit in computer architecture that handle sorting like this? Or it's still handled by algorithm (program/software).

If not, will be theres special processor that handle this, if so then sorting is not a problem anymore.

I'm always thinking hardware is powerful than software.

Also i'm wonder any there still time complexity when we take bussiness with boolean algebra?

As far i know we just consider about propagation delay in logic gates which it's come from the transistor technology about time efficiency.

# Answer
> 2 votes
In the 1960s and even a bit later sorting took up a lot of time. Part of the problem, back then, was the size of main memory (RAM if you like) was small and often the list of records you wanted to sort would not fit in RAM. As a result, the sort algorithm had to read and write the same record several times. Today, just about all files fit in memory.

Today you can sort a large file relatively quickly using a general purpose computer. As a result, I do not see any need for special purpose hardware to help with sorting. However, there could be one or two special cases where it would make sense. I just do not know of any.

---
Tags: algorithms, logic, sorting, boolean-algebra
---


# Question
Title: Why can't I break out of this do while loop in java?
Even though the input I type is a "Y" or "N" string, I can't break out if this while loop. Can anyone tell me why?

```
public String yesOrNo(String message) {
    String yesOrNo;

    do {
        System.out.print(message);
        yesOrNo = input.next();
    } while(yesOrNo != "N" || yesOrNo != "Y");

    return yesOrNo;
}

```

# Answer
> 1 votes
As indicated in the comments by gnasher729, you have made a mistake in your logic.

Your logic is as follows:

| Input | A: Input != "N" | B: Input != "Y" | A∨B (OR) |
| --- | --- | --- | --- |
| Y | TRUE | FALSE | TRUE |
| N | FALSE | TRUE | TRUE |
| *Anything Else* | TRUE | TRUE | TRUE |

The logic you want:

| Input | A: Input != "N" | B: Input != "Y" | A∧B (AND) |
| --- | --- | --- | --- |
| Y | TRUE | FALSE | FALSE |
| N | FALSE | TRUE | FALSE |
| *Anything Else* | TRUE | TRUE | TRUE |

---

In your code change or OR to be an AND to match the logic expressed above:

```
while(yesOrNo != "N" && yesOrNo != "Y");

```

---
Tags: loops
---


# Question
Title: Shortest walk with alternating colors in a directed graph
Let $G$ be a directed graph such that every edge is colored (red, yellow or green). I want to compute the shortest walk (possibly with repeated vertices) with the restriction that the colors are alternating: red, green, yellow, red, green , ..., etc (the starting color doesn't matter).

So far my idea is to create a new graph $G'$ such that is has a copy of each vertex (for each color). Then, by adequately placing every colored edge in the new graph I should be able to just run DFS/BFS in the new graph and get the answer. However, I don't know exactly how to correctly place the edges in the new graph $G$, or if this idea works.

# Answer
Let $G=(V, R \cup G \cup Y)$, where $R$, $G$, and $Y$ are the sets of red, green, and yellow edges, respectively. I assume you want to find the shortest walk **between a pair of given vertices**. Let these vertices be $s$ and $t$.

Create the graph $G'=(V', E')$ where $V' = \\{s', t'\\} \cup \bigcup\limits\_{v \in V} \\{v\_r, v\_g, v\_b \\}$ and $E'= \\{ (u\_r, v\_g) \mid (u,v) \in G \\} \cup \\{ (u\_g, v\_y) \mid (u,v) \in Y \\} \cup \\{ (u\_y, v\_r) \mid (u,v) \in R \\} \cup \\{ (s', u\_r) \mid u \in V\\} \cup \\{(v\_r, t'), (v\_g, t'), (v\_y, t') \mid v \in V\\}$.

Let $\ell$ be length of the shortest color-alternating path between $s$ and $t$ in $G$, and let $\ell'$ be the length the length of the shortest path between $s'$ and $t'$ in $G'$. You have than $\ell' = \ell + 2$. Therefore it suffices to find a shortest path from $s'$ to $t'$ in $G'$. This can be done in linear time in the size of $G'$ (and $G$).
> 1 votes

---
Tags: graphs, discrete-mathematics, directed-graphs
---


title: Filling in the image by the brain

text:
# Question
Title: Filling in the image by the brain
The Cones and rods are not evenly or precisely sensitized on the retina by incoming light. Because of this, the image is formed with distortions. But the brain corrects these deformations through a calculation that tries to form a uniform image, which is the end product we see. I would like to know if there is any algorithm that has already proposed to model how this probabilistic correction that the brain makes.

Does anyone know anything about this? It would be amazing

# Answer
> 1 votes
The brain works as a hierarchical distributed network of networks (hence heuristics).
We attach meaning and prototype of objects as abstract concept.

DNN was created to reconstruct images using fMRI.

But this is not the whole story, you have to know three additional things to make a connection.
Various networks or blending functions are individual on person basis. Everything starts from the first day of life.
We try our senses, here touch and vision. We see 3D, but to do that, we would require 3 eyes. So depth of image is also created in kind of brains distributed DNN using additional info, like shade or object recognition (cognitive function tells us that e.g. car has depth, so this part is purely cognitive).

The distribution of rods and cones is not uniform and not the same among people, but yet, we see the same things?
This is not entirely true, people who never seen buildings (experiment on native tribes) when go up, to the roof, they do not feel anxiety looking down.
People who never seem triangle are immune to optical illusion, They see three bitten apples and pictogram of three birds.

Getting back, people who share knowledge, say starting from primary school, will see it.

The missing part: how people can see the same things with the different distribution of rodes and cones?
First, they see small differences, but are able to infer it. Second, crucial point, when we learn to use sight, we also use touch as training set. Being able to touch something and remember shape, calibrates perception. Based on other senses and continuous training (brain consolidates every new piece of information all the time), the distribution of sensors doesn't matter, as we check out the world and surroundings for something like first five years, and then start to infer and learn abstract ideas, with calibrated sight.

This is solely based on senses and experience.

This is the same as with neural network classifier that gets different modified versions of the same image, as far as it is used consistently the same convolution function, the results won't change much. People change this convolution function in the first years of life after touching enough objects and byproduct is depth sensing.

---
Tags: algorithms, reference-request
---


# Question
Title: How to determine the finite or infinite number of words in a formal language
**Let be**:

* Uppercase letters — non-terminal symbols.
* Lowercase letters — terminal symbols.

**Possible cases**:

1. The number of words is 0 (infinite substitutions). Examples: $$\\{S \rightarrow aS\\}, \\ \\{S \rightarrow aF, F \rightarrow aS \\}, \\ \\{S \rightarrow aA, S \rightarrow A, A \rightarrow FS, F \rightarrow t\\}$$
2. The number of words is finite and $\ge 1$. Examples: $$\\{S \rightarrow a\\}, \\ \\{S \rightarrow aF, F \rightarrow a \\}, \\ \\{S \rightarrow aA, S \rightarrow A, A \rightarrow FP, F \rightarrow k, P \rightarrow t \\}$$
3. The number of words is infinite. Examples: $$\\{S \rightarrow a, S \rightarrow aS \\}, \\ \\{S \rightarrow aF, F \rightarrow a, F \rightarrow aS \\}, \\ \\{S \rightarrow Sb, S \rightarrow aA, A \rightarrow Sb, A \rightarrow Ab, A \rightarrow b \\}$$

**Is it possible to create a universal algorithm that determines which of these cases a given grammar belongs to?**

Any grammar can be represented as a directed graph (right?). However, a graph can have several connectivity components. And this leads me to a dead end.
Example: $$\\{ S \rightarrow a, S \rightarrow aS, bbbbS \rightarrow b \\} \\ \space \mathrm{infinite} \space \mathrm{for} \space S, \\ \mathrm{but} \space \mathrm{finite} \space \mathrm{for} \space bbbbS.$$

Hence, it is clear that the algorithm must take the start word and rules as input.

# Answer
In order to decide whether a context-free grammar generates the empty language or not, you can compute the set of *productive nonterminals*. A nonterminal $A$ is productive if there is a rule $A \to \alpha$ where all nonterminals in $\alpha$ are already known to be productive. The set of productive nonterminals can be computed iteratively using the definition. The grammar generates the empty language iff the start symbol is not productive.

In order to determine whether the language generated by a context-free grammar is infinite or not, you can use the pumping lemma. First you need to convert the grammar into Chomsky normal form. Then, there are thresholds $n\_1,n\_2$, depending on the number of nonterminals, such that the language generated by the grammar is infinite iff it contains a word whose length is between $n\_1$ and $n\_2$ (in the case of regular grammars, you can take $n\_1 = n$ and $n\_2 = 2n-1$, where $n$ is the number of nonterminals, but for general context-free grammars, $n\_1,n\_2$ are exponential in $n$); this is a consequence of the pumping lemma. This is not a very efficient algorithm, unfortunately, but it shows that the problem is decidable.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Do Turing machines have memory registers?
I am working on chapter one of the textbook Computational Complexity: a modern approach by Arora, S., & Barak, B. They begin by defining a turing machine (TM) and then prove equivalence between variations of TMs. They make the following claim.

**Claim 1.6** Deﬁne a single-tape Turing machine to be a TM that has only one read-write tape, that is used as input, work, and output tape. For every $f : \\{0, 1\\}^∗ → \\{0, 1\\}$ and time-constructible $T : \mathbb{N} → \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5kT(n)^2$ by a single-tape TM $M'$.

I understand how to "compress" the $k$ tapes $M$ has into $M'$ single-tape. However, when they describe how to simulate one step of $M$ on $M'$ I get confused. More specifically, they describe it as follows:

1. First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by “$ˆ$”.
2. Then $M'$ uses $M$’s transition function to determine the new state, symbols, and head movements and sweeps the tape back in the right-to-left direction to update the encoding accordingly.

How can a TM have a register? I thought it was a finite automata with a tape and head only. They also mention TMs having a state register.

How much data can a register hold? In the proof, they imply the register can hold $k$ symbols. Are the registers typically stored on some separate tape or somewhere else?

# Answer
Yes a TM also has states. Formally, one can define TMs as $(Q, \Sigma, \Gamma, \square, \delta, q\_0, \bar{q})$ with states $Q$, input alphabet $\Sigma$ not including the blank symbol $\square$, tape alphabet $\Gamma$, transition function $\delta$, initial state $q\_0$ and terminal state $\bar{q}$. It might be differently defined but essentially it is all the same (what is of course the whole point of the chapter you are reading right now).

The following explanations are definitely handwavy but I hope the message is still clear.

The positions marked with ^ in 1-tape $M'$ store the current head positions in the $k$-tape TM $M$ which is in some state $q$. By sweeping once through the whole tape on $M'$, $M'$ stores the symbols on each tape marked with ^ in some state that depends on $q$ that "somewhat" looks like $q' = (q, a\_1, \ldots, a\_k)$, where $a\_i \in \Gamma$ is the symbol under the head of tape $i$. The actual state is a bit more involved (e.g. $M'$ needs to store whether it is still in the sweeping process or is already updating the tape according to the transition function, which is tedious but straight-forward) but this is essentially the information you want for $M'$. As the state set, number of tapes, and the set of tape symbols are all finite, this information contained in $q'$ can be stored in a finite state set $Q'$ for $M'$.
> 8 votes

# Answer
A TM does not have a register, but a register has a fixed capacity.

Any amount of fixed capacity storage can be emulated by multiplying your states: your new states become $ \langle q, v \rangle$ where $q$ is an old state and $v$ a value stored in the register.

So a "TM with a register" is not a TM, but trivially equivalent to a normal TM, and I would expect your course notes to have this spelled out at some point.
> 19 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Why does bottom-up parsing of right-recursive grammars require unbounded O(n) stack space?
I keep reading that while bottom-up parsing of a left-recursive grammar can be done in constant O(1) stack space, for a right-recursive grammar, we have to push the entire input stream onto the stack before popping any of them off. Why is this?

Let's say that I consider a simple right-recursive grammar List -\> elt List | elt , and I consider the string elt elt elt. When the parser pushes the first elt onto the stack, why doesn't it just immediately reduce it to List and then continue parsing?

# Answer
The question is: given the grammar $$\begin{align}\textit{List}&\to \textbf{elt}\ \textit{List}\\ \textit{List}&\to \textbf{elt} \end{align}$$ and the input $$\textbf{elt elt elt}$$ Why doesn't the parser immediately reduce $$\textit{List}\to \textbf{elt}$$ Suppose that it did. You would then have $$\textit{List}\textbf{ elt elt}$$ Now what? No production starts with $\textit{List}$ so the parser is stuck.

The only way the parser can parse the entire input is to assume that the $\mathbf{elt}$ is the first symbol in $\textit{List}\to\textbf{elt}\textit{ List}$ and proceed from there, but that necessarily uses a stack slot to record the incomplete production.

To put it another way, if you use right-recursion, the unit production $\textit{List}\to\textbf{elt}$ applies to the *last* $\mathbf{elt}$ in the $\textit{List}$. In contrast, in a left-recursive grammar for the same language, the unit production would apply to the *first* $\mathbf{elt}$. Whether or not there is a semantic difference depends on your attribute actions; if there is no semantic difference, the left-recursive grammar will normally be prefered.

However, in many languages, there are also syntactic constraints which might suggest using a right-recursive grammar even though it uses up stack space. For example, the simplified grammar for a parameter list with optional unnamed trailing arguments (C99 varargs macros, for example): $$\begin{align}\textit{Parameters}&\to \textbf{ID , }\ \textit{Parameters}\\ \textit{Parameters}&\to \textbf{ID}\\ \textit{Parameters}&\to \textbf{. . .}\\ \end{align}$$ Since the $\textbf{. . .}$ can only be at the end of the parameter-list, it's easiest to write the grammar as right-recursive.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Why doesn't master theorem solve $T(n) = 2T(n/2) + n\lg\lg n$?
Given two recurrences:

1. $T(n) = 2 T(n/2) + n \lg \lg n$
2. $T(n) = 4 T(n/2) + n \lg \lg n$

I'd think that both works for master theorem, but the solution is that the first one cannot use masters theorem while the second one works with masters theorem. The only difference here is the $a$ value (2 vs 4).

# Answer
> 1 votes
Here is the statement of the master theorem on Wikipedia. Consider a recurrence $$ T(n) = aT(n/b) + f(n). $$

1. If $f(n) = O(n^c)$ for $c \< \log\_b a$ then $T(n) = \Theta(n^{\log\_b a})$.
2. If $f(n) = \Theta(n^{\log\_b a} \log^k n)$ for $k \geq 0$ then $T(n) = \Theta(n^{\log\_b a} \log^{k+1} n)$. (Extensions handle all $k$.)
3. If $f(n) = \Omega(n^c)$ for $c \> \log\_b a$ and $f$ is "reasonable" then $T(n) = \Theta(f(n))$.

In your case, the function $f$ satisfies neither of the three cases, and so the master theorem does not apply. It almost satisfies the second case, but instead of $f(n)$ scaling like $n^{\log\_b a} \log^k n$ for some constant $k$, it scales like $n^{\log\_b a} \log\log n$.

We can use the Akra–Bazzi theorem instead to conclude that $T(n) = \Theta(n\log n\log\log n)$.

---
Tags: asymptotics, master-theorem
---


# Question
Title: Stuck with shift-reduce conflicts on yacc on grammar to generate palindromic strings on {0,1}
I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below:

```
%%
program: expr NL { printf("Valid string.\n"); exit(0); }
;
expr: ZERO expr ZERO
| ONE expr ONE
| ZERO
| ONE
|
;
%%

```

Here `ZERO` is the token representing 0, `ONE` is the token representing 1, and `NL` represents `\n`. Using yacc on the above grammar, I'm given the following warnings.

```
yacc -dt --verbose 7b.y
7b.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
7b.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]

```

To the best of my knowledge, the grammar above seems to be unambiguous. My questions are:

1. Why is yacc giving me this error?
2. What should I change to resolve this?

Here are the complete lex and yacc programs if they should help:

Lex:

```
%{
#include <stdlib.h>
void yyerror(char *);
#include "y.tab.h"
%}
%%
[0] { yylval = 0; return ZERO; }
[1] { yylval = 1; return ONE; }
\n { return NL; }
. yyerror("invalid character");
%%
int yywrap(void) {
return 1;
}

```

Yacc:

```
%{
#include <stdio.h>
#include <stdlib.h>
int yylex(void);
void yyerror(char *);
%}
%token ZERO ONE NL
%%
program: expr NL { printf("Valid string.\n"); exit(0); }
;
expr: ZERO expr ZERO
| ONE expr ONE
| ZERO
| ONE
|
;
%%
void yyerror(char *s) {
fprintf(stderr, "Invalid string.\n");
}
int main(void) {
yyparse();
return 0;
}

```

Thanks for your help in advance.

# Answer
> 3 votes
The grammar is, as you say, unambiguous. But it is not *deterministic*. LR parsers with bounded lookahead can only recognise deterministic languages; since not all unambiguous context-free languages are deterministic, LR parsers cannot recognise all unambiguous context-free languages.

Intuitively, palindromes are non-deterministic because the parser must switch states precisely at the middle of the input, but there is no way to tell where the middle of a sentence is until you know where the end is, which is obviously not possible with bounded lookahead.

Proving that the language of palindromes is not deterministic is a bit of work. You probably won't find the proof in a textbook oriented towards writing compilers, such as the Dragon Book, but if you are studying formal language theory you might be working with a more theory-oriented textbook (such as Hopcroft and Ullman.) There is a proof that the language of even-length palindromes is non-deterministic here, and extending the proof to the language of all palindromes is not that difficult.

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


# Question
Title: What is the Runtime of this recursive algorithm?
I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in recursive function.

`my_func` takes an array parameter `A` of length $n$. Runtime of `some_func()` is constant.

```
def my_func(A):
  if (n < 4):
    some_func(); /* O(1) time */
  else:
    [G1, G2, G3, G4] = split(A) /* split A into 4 disjoint subarrays of size n/4 each */
    my_func([G1, G3]); /* recurses on size n/2 */
   my_func([G1, G4]); /* recurses on size n/2 */
   my_func([G2, G3]); /* recurses on size n/2 */
   my_func([G2, G4]); /* recurses on size n/2 */
   some_other_func(); /* split() and some_other_func() take O(n) time */

```

**Questions**

1. Can I say the asymptotic runtime of `my_func` is
$$T(n) = 4T(n/2) + O(n) \text{ with } T(1) = O(1)$$because `my_func` is called recursively $4$ times for $(n/2)$ size, then split is $O(n)$ and `some_other_func` is $O(n)$. The base case keeps $T(1) = O(1)$
2. What is the total number of steps performed by `my_func(A)`?
I know that if there are nested for loops then simply multiply. How to calculate in this case? I was trying use Google search and it point to $\Omega(n^3)$. Is that correct?

Now what if I rewrite this function as

```
def new_func(A): /* A is array of length n 8/
  if (n < 4):
    some_func(); /* O(1) time */
  else:
   [G1, G2, G3, G4] = split(A) /* split A into 4 disjoint subarrays of size n/4 each
   new_func([G1, G2]); /* recurses on size n/2  */
   new_func([G2, G3]); /* recurses on size n/2  */
   new_func([G3, G4]); /* recurses on size n/2  */
   some_other_func(); /* split() and some_other_func() take O(n) time */

```

**Questions**

1. What is the number of steps now?
I guess it will be $\Omega(n^3)$
2. Is `new_func` faster than $n\log(n)?$
I think no because Merge sort is $T(n) = 2T(n/2) + n$ and `new_func` is $T(n) = nT(n/2) + n$

# Answer
In `my_func(a)`, **Recurrence Relation** will be

$T(n) = \begin{cases} 4T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\ 1 & \quad \text{if } n \<4 \end{cases} $

In `new_func(a)`, **Recurrence Relation** will be

$T(n) = \begin{cases} 3T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\ 1 & \quad \text{if } n \<4 \end{cases} $

You can solve Both of these **Recurrence Relations** using **Master Theorem** as explained in link.

The **Time Complexity** of `my_func(a)` will be $\theta(n^2)$ since $\log\_24 = 2$

The **Time Complexity** of `new_func(a)` will be $\theta(n^{1.5849})$ since $\log\_23 = 1.5849$

You can solve both of these questions by **Substitution Method**, which is Time Consuming. One of the Example using this method is attached.

The `new_func(a)` will be slower than `Merge Sort`, and faster than `my_func(a)`.
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, asymptotics, recurrence-relation
---


# Question
Title: Bin packing problem and optimality proof
Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w\_i\in W$ is stored before $w\_j\in W$ then necessarily $w\_i \> w\_j$), and the original order of the weights in $W$ is preserved ($w\_i \in W$ cannot be stored before $w\_j \in W$ if $i\>j$). There is no restriction on the maximum value of the weights or capacity of the bins.

I have come up with the following greedy algorithm: for every weight $w\_i$ in $W$, store it in the first bin available that is compatible with the restrictions given. For example, for the entry $\[47, 27, 33, 5, 13\]$, the algorithm's output would be $\[47, 27, 5\]$ and $\[33, 13\]$. How can I prove that this algorithm is optimal?

# Answer
Your solution is not optimal. Take for example, the following list of weights: $\[1,4,3,2\]$. In this example, your algorithm will place only $1$ in the bins, whilst a different solution could place $4,3$ and $2$ instead (which is obviously a better solution).

However, you can create a dynamic programming solution for this problem:

Consider the graph $G$, with vertices corresponding to the weights in $W$, and edges $(w\_i,w\_j)$ if $j\>i$ ($w\_j$ is after $w\_i$) and $w\_i\>w\_j$ ($w\_j$ must be lighter than $w\_i$ for us to place it after $w\_i$). We will also place an edge-weight on every such edge equal to the weight in $w\_j$ (which intuitively means that if we traverse this edge, we add $w\_j$ to the bins).

This graph is a DAG, and the optimal solution for your problem can be proven to be the longest (in terms of edge-weights) path in this graph. Since this is a DAG, you can construct a dynamic programming solution for it.
> 1 votes

---
Tags: algorithms, algorithm-analysis, greedy-algorithms, packing
---


# Question
Title: Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
I am trying to solve the recurrence $$T(n) = T(n-1) + (-1)^nn, \quad T(0) = 1.$$

I'm stuck in the summation: \begin{align} T(n) &= T(n-1) + (-1)^n n \\ &= T(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ &= T(n-3) + (-1)^{n-2}(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ &= \\ &\cdots \\ &= T(n-k) + (-1)^{n-(k-1)} (n-(k-1)) + (-1)^{(n-(k-2))} (n-(k-2)) + \cdots + (-1)^nn \\ &= T(0) + \sum\_{k=1}^n (-1)^k k. \end{align} How do I evaluate the sum?

# Answer
Here are the first few values of the expression $\sum\_{k=1}^n (-1)^k k$, starting with $n = 1$: $$ -1, 1, -2, 2, -3, 3, -4, 4, -5, 5,\ldots$$ Hopefully you can spot the pattern.
> 3 votes

---
Tags: recurrence-relation, discrete-mathematics, mathematical-analysis
---


# Question
Title: How can I modify this detail in the article ""Extending Multi-Sense Word Embedding to Phrases and Sentences for Unsupervised Semantic Applications"?"
This question is about de paper Extending Multi-Sense Word Embedding to Phrases and Sentences for Unsupervised Semantic Applications.

I am interested in the transformer part of the paper and the main structures of the algorithm is represented in the following image:

Before the main questions I have other questions which perharps will help the main question:

What is the role of the DECODER? Why do I need a encoder/decoder?

Main question:

In the paper the authors replace the transformer encoder by an bi-LSTM and the transformer decoder with LSTM.

What are the other options for replacing the encoder/decoder part of the algorithm? Is it possible to replace the encoder/decoder at once by a single structure?

# Answer
> 1 votes
Thanks for being interested in our work.

The role of the decoder is to model the dependency between the codebook embeddings. For example, in this case, outputting an embedding close to sings might be correlated to outputting an embedding close to microphone.

There are several reasons that we choose to use a seq2seq (encoder/decoder) architecture. For example, we want to compare with the related work such as skip-thought. In addition, the sentence length varies but we want to output a fixed number of embeddings.

If you want, you can input a fixed number of multiple special tokens into a transformer encoder and use the corresponding hidden states as the codebook embedding. We find that this encoder-only architecture is more likely to output almost identical embeddings (i.e., multiple embeddings collapse into a single embedding), especially when a transformer with many layters such as BERT. We are investigating some solutions to this problem now.

---
Tags: neural-networks
---


# Question
Title: Merging sorted arrays stored as linked lists
I have $k$ sorted arrays stored as linked lists. I need an algorithm to merge them into one single sorted array, also stored as a linked list. How can I do that?

My Code:

```
Function merge(A[k])
Begin:

// A is array of list to merge.
Array result;
temp //array to save element in each list
For (i=0:i<k:i++):
Temp.add(A[i].head.value);

While(result.size<n):
 Minvalue, index = temp.pop()
 Result.add(minvalue)
 Value = 0
 If( A[index].head.next==Null):
   Value = maxInt
 Else :
  A[index].head = A[index].head.next
  Value = A[index].head.key Temp.add(value)
 Return result;

End

```

# Answer
> 3 votes
When $k = 2$, you can use the classical *merge* routine of Merge Sort, which fits the linked list data structure well. In this routine, you repeatedly compare the smallest elements of both arrays, adding the smaller one to the new array, and removing it from its own array.

You can use the same idea for general $k$. Instead of comparing the $k$ smallest elements at every step, you can use a priority queue that stores the smallest elements of each array, thus improving the running time of every step from $\Theta(k)$ to $O(\log k)$.

---
Tags: algorithms, arrays
---


# Question
Title: Designing a NFA that accept the set of strings that contain an even number of substrings 01
I'm new in theory of computation. Here {0,1} set of input symbols. I tried to make the NFA from L(M)= set of all accepted strings, but unable to complete it. Can someone give some hints that how should I attack this problem? . It will be very helpful.

# Answer
> 1 votes
This answer assumes that by *substring* you mean *consecutive substring*.

There is no need to use the power of NFAs. You can construct a DFA which remembers the following information:

* The last symbol seen (either $0$, $1$, or blank).
* The parity of number of occurrences of $01$ seen so far.

Maintaining the last symbol seen is easy. If the last symbol seen is $0$ and the current symbol is $1$, then you flip the parity of number of occurrences of $01$. A state is accepting if the parity of number of occurrences of $01$ seen so far is even.

I'll let you convert this description into an automaton.

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


# Question
Title: Reduction from undecidability, decidability to decididabilty
If given any two language both $L\_1$ and $L\_2$ are decidable then why both $L\_1\leq\_m^\mathsf{}L\_2$ and $L\_2\leq\_m^\mathsf{}L\_1$ are false. Please provide easy explanation with any counterexample for both cases.

Any language $L\_3$ is given as Undecidable and $L\_4$ is decidable then $L\_3\leq\_m^\mathsf{}L\_4$ is false. But $L\_4\leq\_m^\mathsf{}L\_3$ is true. What's the reason behind it?

I can't differentiate between above two concepts. Please explain with example.

# Answer
If $L\_1$ is decidable and $L\_2$ is decidable then it is not necessarily true that $L\_1 \le\_m L\_2$. Consider for example any $L\_1$ distinct from $\emptyset$ and pick $L\_2 = \emptyset$.

In general, if $A$ and $B$ are languages, $A$ is decidable, and $B$ is non-trivial (i.e., distinct from $\emptyset$ and $\Sigma^\*$) then $A \le\_m B$ holds. The actual reduction is easy:

* Let $y \in B$ and $n \not\in B$ be some *fixed* words. Their existence is guaranteed by the fact that $B$ is non-trivial.
* Given a word $x$, check whether $x \in A$. This can be done since $A$ is decidable by hypothesis.
* If $x \in A$ return $y$. Otherwise return $n$.

This shows that for any pair of non-trivial decidable languages $L\_1, L\_2$ you have both $L\_1 \le\_m L\_2$ (by picking $A=L\_1$ and $B=L\_2$) and $L\_2 \le\_m L\_1$ (by picking $A=L\_2$ and $B=L\_1$).

Let's now consider whether $L\_3 \le\_m L\_4$ holds when $L\_3$ is undecidable and $L\_4$ is decidable. This is false since it would imply that $L\_3$ is decidable. Indeed, if we suppose towards a contradiction that $L\_3 \le\_m L\_4$, we have that the following algorithm decides $L\_3$:

* Let $f$ be any fixed many-one reduction from $L\_3$ to $L\_4$. Notice that $f$ exists by hypothesis.
* Given a word $x$, compute $z=f(x)$. This can be done because $f$ is a total computable function by definition of many-one reduction.
* Check whether $z \in L\_4$. This can be done since $L\_4$ is decidable.
* If $z \in L\_4$ return "yes". Otherwise return "no".

Finally, let's consider $L\_4 \le\_m L\_3$. This is true since $L\_3$ is necessarily non-trivial because it is undecidable (and all trivial languages are decidable by either the algorithm that always returns "yes" or by the algorithm that always returns "no"). Then we can use the reduction discussed above by picking $A=L\_4$ and $B=L\_3$.
> 1 votes

---
Tags: np-complete, undecidability, np-hard, polynomial-time-reductions, decidability
---


# Question
Title: Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?
I have a question that says that the complement of a regular language given as: $L\_1=\\{a^nb^m|(n+m)\<5\\}$ is $L\_2=\\{a^nb^m|(n+m)\geq5\\}$ over $\Sigma=\\{a,b\\}$, and therefore, we can simply construct finite automaton (FA) of $L\_2$ by simply interchanging the accepting and non-accepting states of $L\_1$ .

However, as per my understanding if I define the complement as: $$\bar{L}=\Sigma^\*-L$$ where $\sum^\*$ is every possible string, then $L\_2$ can't be a complement of $L\_1$ as there must also be strings that do not have order $b$ after $a$.

The given approach may work for languages like $L\_3=\\{w|w~\text{has an odd number of a's}\\}$ and $L\_4=\\{w|w~\text{has an even number of a's}\\}$, as disjoint sets lead to $\Sigma^\*=L\_3+L\_4$. However, as per my understanding, this logic will not work to derive FA for $L\_2=\\{a^nb^m|(n+m)\geq5\\}$ from FA of $L\_1=\\{a^nb^m|(n+m)\<5\\}$.

Am I correct? Or the definition of complement is different from my understanding.

# Answer
> 1 votes
You are correct. The definition of the complement is exactly what you wrote, and indeed it is not true to say that $L\_2$ is the complement of $L\_1$. However, changing the accepting and non-accepting states **is** in fact a correct way to generate a finite automaton for the complement language, so I think whoever wrote $L\_2$ just miss-typed. It won't make a difference for the solution, so just substitute the correct complement instead of $L\_2$ wherever you need to.

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


title: what precisely do linear types prevent?

text:
# Question
Title: what precisely do linear types prevent?
"A theory of type polymorphism in programming" introduced the Hindly-Milner type system whose punchline can be summarized "well-typed terms don’t get stuck". They do this by creating a relatively simple language with just enough features that an untyped stuck expression is possible. For instance, `true false` is stuck (`true` is not a function, so it cannot take the argument `false`). Stuck expressions would not be possible without non-functions in the language.

Linear Types can encode some additional practical properties. They are often justified with examples using references, memory or file handles. Has anyone constructed a minimal system with a pithy summary like “Linearly-typed terms don’t \___”? If so, what is the simplest additional construct that makes linear types relevant (as bool does in the Hindly-Milner case)?

Linear types don’t prevent anything problematic in pure systems. My impression is that linear typing only makes sense relative to some effect system, but it is unclear to me exactly what that effect system looks like. References, file handles and memory are fairly complicated constructs, is there a simpler linear construct? I think a minimal dynamic system that could fail would help clear that up.

# Answer
> 1 votes
It's somewhat misleading to say that linear types don't prevent anything in 'pure' systems, because some things that are not considered pure become so when restricted with linear types. An example would be Fillinski's Linear Continuations. Normally, control operators are considered effectful, and results are non-deterministic depending on evaluation order. However, putting linearity restrictions on the use of continuations restores determinism, and makes the control operators an additional way of decomposing the control flow of the program.

A way of conceptualizing what is going on in this sort of framework is that the non-linear (exponential) parts have some stable, copyable representation. An $\mathsf{Int}$ is just a few bits that may be copied or discarded. And a *function* with type $A → B$ is given by some code that may be copied, or a reference thereto.

However, the continuations, which must be used linearly, are ephemeral things that actually represent particular control flow points in a running program. You can conjure a continuation with type $A \multimap ⊥$ together with an $A$, and send them to separate portions of the program that may run concurrently. When one portion applies the continuation, it specifies the corresponding $A$ value in the other portion. It is important for this to happen linearly, because if a continuation is applied *twice*, then the specification of the correpsonding value is ambiguous, and may depend on evaluation order, and if the continuation is not used at all, then the corresponding value is never specified, and the portion of the program that uses it will be essentially deadlocked.

So, in some sense, continuations are a way of treating ephemeral control flow points of the program as if they were first class values, and linearity is preventing you from doing things that might make sense for normal, stable values (copying and discarding), but don't make sense for particular program control flows. This perspective can also be applied to other uses of linearity. For instance, if you have linearly typed mutable arrays, the discipline is covering for the fact that it is not a stably specified array of values, but an ephemeral memory region. It is not a fixed value, but a reification of the operations of reading from/writing to a runtime location at a particular point in time, which doesn't make sense to occur more than once.

---
Tags: reference-request, type-theory
---


title: Point in Polygon on the sphere

text:
# Question
Title: Point in Polygon on the sphere
I'm looking at geometric objects on the sphere and need to determine if a point on the sphere is inside a spherical polygon.

In our case a spherical polygon is a an ordered set of vertices $v\_1v\_2...v\_n$ and the edges $v\_iv\_{i+1}$ are given by great circle arcs. The polygon is uniquely defined by a counterclockwise walk through the ordered set (hence we do not have the problem which of the two possible polygons is the one we are talking about).

I had a look at similar questions/problems:

1. The Paper: Locating a Point on a Spherical Surface Relative to a Spherical Polygon of Arbitrary Shape. Essentially they implement the classic rayshooting algorithm, but because of the spherical nature they need an anchor point $S$ which is guranteed to lie in the polygon. (In my application this would not be possible)
2. The question: Is a point inside or outside a polygon which is on the surface of a globe. The accepted answer suggests, that we can use the standard ray tracing algorithm with a great circle, but I do not see how that would work. In the Image the dotted line is the part that wraps around the sphere. If we now count the number of intersections it is even in both cases since we always intersect all lines on the great circle.

Any ideas how I could solve point in polygon without the anchor point would be appreciated or of cause a correction about my thoughts with respect to 2) would also be nice.

A visualization of the answer given by John L.:

# Answer
> 1 votes
What is the meaning of "the polygon is uniquely defined by a counterclockwise walk through the ordered set" of vertices?

To define what is a "counterclockwise" walk, what do we need to know besides the edges of the spherical polygon?

* An immersion of the (2-dimensional) sphere in some 3-dimensional space.
* A point that is inside the a spherical polygon. Or a point that is outside the spherical polygon.

If that is how "counterclockwise" is defined, then we should not have any problem applying the classic ray-shooting algorithm as described in the paper mentioned if we have been given a "counterclockwise walk" on the vertices.

---

However, it looks like that you are not given a point that is inside the given spherical polygon explicitly. Here is another possible way to define a "counterclockwise" walk.

Suppose we have a spherical polygon $P$ with vertices $v\_0v\_1v\_2\cdots v\_n$, where $n\ge3$, $v\_n=v\_0$ and, for each $0\le i\lt n$, $v\_i$ and $v\_{i+1}$ are two adjacent vertices. A "counterclockwise" walk on the edge $\\{v\_i,v\_i+1\\}$, is an ordered pair $(a,b)$, which is either $(v\_i, v\_{i+1})$ or $(v\_{i+1}, v\_i)$, such that when you, as a human, will find the inside of $P$ is to your left when you walk from $a$ to $b$ following that edge with your feet between your head and the center of the sphere (a.k.a. the center of the ball). So, "a counterclockwise walk" will specify which side of each edge faces the inside of $P$ (facing inwards). This definition of "counterclockwise" is consistent with the situation when we are looking at a mechanical clock on a sphere that faces outwards from outside of the sphere, considering the hour numbers on the clock are the vertices of $P$.)

Note that once we know which side of any given edge faces inwards, then we know which side of an adjacent edge faces inwards. So, we know which side of each edge faces inwards.

Then the question becomes how we can determine if a point on the sphere is inside $P$ if we know which side of each edge faces inwards.

Suppose the query point is $X$. We can select an arbitrary point $A$ on an arbitrary edge of $P$. Draw $\alpha$, a great circle arc between $X$ and $A$. Compute all intersection points between $\alpha$ and each edge of $P$. Find the intersection point that is nearest to $X$ and the edge (or one of the two edges) it is on, say point $I$ and edge $E$. Consider $\beta$, the great circle arc from $I$ to $X$ that is part of $\alpha$.

* If $\beta$ is on the inward side of $E$, $X$ is inside $P$.
* If $\beta$ is on the outward side of $E$, $X$ is outside $P$.
* If $\beta$ is on the same great circle as $E$,
    + If $X$ is on $E$, that says $X$ is on the perimeter of $P$.
    + Otherwise, $I$ must be a vertex of $P$. We can determine which one of the two angles between the two edges that share the vertex $I$ is the "inner angle" of $P$ and whether $\beta$ is in that "inner angle", which tells us whether $X$ is inside of $P$ or not.

Once we know one particular point is inside or outside, we can also use the ray-shooting algorithm.

---
Tags: computational-geometry
---


# Question
Title: For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?
For Turing machines, if the input variables increase, will the state set Q increase ? will the tape alphabet Γ increase?

For example, for the SAT problem, the first question is whether the Boolean expression of one variable is satisfied, the second is whether the Boolean expression of three variables is satisfied. Does the latter need a larger state set Q and a larger tape alphabet Γ than the former?

The book Introduction to the Theory of Computation that I've been using for reference define a Turing machine as follows:

A Turing machine is a 7-tuple, (Q,Σ,Γ,δ,q\_0 ,q\_accept ,q\_reject ), where Q, Σ, Γ are all finite sets and

1. Q is the set of states,
2. Σ is the input alphabet not containing the blank symbol,
3. Γ is the tape alphabet, where ☐ ∈ Γ and Σ ⊆ Γ,
4. δ: Q × Γ→Q × Γ × {L,R} is the transition function,
5. q\_0 ∈ Q is the start state,
6. q\_accept ∈ Q is the accept state, and
7. q\_reject ∈ Q is the reject state, where q\_reject ≠ q\_accept .

# Answer
> 1 votes
A Turing machine is **fixed** in size. Just as a piece of code doesn't increase in size when given bigger inputs, also a TM doesn't.

The $TM$ has to be defined beforehand, and its description should not depend on the particular specific input that was given to it.

---
Tags: algorithms, formal-languages, turing-machines, satisfiability, transition-systems
---


# Question
Title: How to model an inverse "token relationship" in Petri nets?
Suppose I have the following Petri net:

I wonder whether it is possible to model an inverse relationship between $p2$ and $p3$. Basically what I want to achieve is to make either $t1$ or $t2$ fireable but never both. Currently, I just set a token in $p2$ and leave $p3$ empty if I want to make $t1$ fireable (or vice versa for $t2$). I believe there must be a way to omit one place and achieve the same result, i.e., putting one token in $p2$ activates $t1$ but not $t2$ and zero tokens in $p2$ achieves the reverse.

# Answer
> 0 votes
Without extra transitions, the best you can do is make them alternate:

Extra transitions can be used to choose between filling *p2* or *p3*:

You can do the same without the additional place:

You might even consider dropping one of the added transitions, to model the situation in which they are enabled in order.

---
Tags: modelling, applied-theory, petri-nets
---


# Question
Title: Textbook proofs for approximation algorithms for scheduling
I am planning to teach approximation algorithms for problems such as job scheduling and number partitioning. I would like to teach proofs, but the proofs I found in the original papers (e.g. this one) are quite hard to understand - they use complicated weighting schcemes, and there is no explanation of how these particular weights were derived.

I am looking for a textbook (or an article) that explains these proofs in a more 'didactic' way, that is, the proof is developed step by step, such that the reader can understand how the proof was derived, and use this understanding to develop similar proofs.

What is a good textbook for this topic?

# Answer
The textbook *The design of approximation algorithms* by Williamson and Shmoys covers many different scheduling and partition problems, and they do so with proofs that are quite accessible.
> 2 votes

---
Tags: approximation, scheduling, books
---


# Question
Title: How to convert this regular grammar into a finite state automaton?
In a French course (p. 13) there is a language of words of `{a,b,c}` containing at least one occurrence of the string `bac`.

The course provide also among other things this right-regular grammar below:

```
T = { a,b,c }
N = { S,U,V,W }
R = { S → aS | bS | cS | bU
      U → aV
      V → cW | c
      W → aW | bW | cW | a | b | c }

```

What bugs me is the first rule: `b` can be followed both by `S` or `U` but it sounds like a **non-deterministic** grammar. I tried to build a finite-state automaton from this language, starting for the description phrased at the beginning to see if I could end with something looking like the grammar. It is reproduced below (**fixed**, thanks to @rici).

I don't think it is, except if I remove `bS` in the first rule. **Where am I wrong?**

# Answer
> 1 votes
The language of a right-regular grammar is certainly deterministic, because the grammar can be written as an NFA and any NFA can be mechanically transformed into an equivalent DFA using the subset construction.

However, the grammar may well be ambiguous (i.e. capable of producing multiple parse trees for the same input.) That's the case for the grammar you show, which might transition to $U$ after any instance of $bac$, not just the first one.

Since the NFA can be transformed into a DFA and the DFA back into a right regular grammar, we can conclude that the *language* is deterministic, in the sense that a deterministic grammar exists. (And a deterministic grammar is clearly not ambiguous.) But that deterministic grammar does not use the same grammatical categories (non-terminals), so it won't produce the intended parse tree (if there was such an intention).

This distinction probably makes little difference at this point in your studies, but it may be useful to hold it in mind. Regular expressions are typically used when the internal structure of the input is unimportant, so that a machine which simply returns a yes/no indication is of practical value and the determinism of the machine's internal workings is irrelevant.

*Parsing*, on the other hand, means analyzing the input into its component *parts* (the similarity of the two words is not a coincidence). So when you later want to build parsers, you'll want a machine which transforms a correct input into a parse tree (or some other similar representation), and the question of determinism becomes more interesting.

In any case, you need always to clearly distinguish between a characteristic of a *grammar* and a characteristic of a *language*, even if the same word is used for both.

Typically we say that a language $L$ has property $P$ if and only if there exists some grammar $G$ which has property $P$ and which generates (or recognises) language $L$. That's a notational shortcut which lets us extend characteristics of grammars onto languages, but it must not be read to imply that *every* grammar for the language has the indicated property. This is a frequent cause of confusion.

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


# Question
Title: For QuickFind, which sub problem we should consider
**Question**: Suppose we have the following array where we want to find the smallest $i$th smallest element in the array using QuickFind algorithm (similar to QuickSort):

$$ QuickFind\left( A,n,i \right) =\left\\{ \begin{array}{l} QuickFind\left( A,k-1,i \right) ,\ i\<k\\ QuickFind\left( A,n-k,k-i \right) ,\ i\>k\\ x,\ i=k\\ \end{array} \right. $$

Now, we can see that we don't know which part is larger the left part where $\<x$ or the right part where elements are greater than $\>x$. So, what we do in this case is to take the largest of the two subprblems:

$$T(n) = max\\{T(k-1), T(n-k)\\} \tag{1}\label{1}$$

**Problem**: why we take the max of two subproblems? If $i\<k$, then we simply take the left part, otherwise $i\>k$ we take the right part of $x$ at the $k$th element. So, why please taking the max of 2 recursions and what does even mean?

**Problem 2**: then to calculate the expected position of $k$,

$$E\[T(n)\] = \sum\_{j=1}^{n}(Pr(k=j))E\left\[ max\\{T(j-1), T(n-j)\\}\right\] \tag{2}\label{2}$$

Also, adding to problem 2, can you please show how we get \ref{2}? I know that $E\[X\] = \Sigma\_i x\_i \times p(x\_i)$, so what quantities in \ref{2} corresponds to equation of expectation $E\[X\]$? From what I see, \ref{2} should be written if we treated $T(n)$ as a random variable that takes several values based on \ref{1}, so we should have it without $E\[\cdot\]$ around $ max\\{T(j-1), T(n-j)\\}$

$$E\[T(n)\] = \sum\_{j=1}^{n}Pr(k \in T(n) = j) \times max\\{T(j-1), T(n-j)\\} \tag{3}\label{3}$$

what do you think please about how I rewrote \ref{2}? Also should it based on expectation definition to have $Pr(X=x\_i)$ corresponds to $Pr(k \in T(n) = j)$ as this is how I interpreted $Pr(k=j)$, so what you think please?

**Edit**: I just look for please to understand $T(n)$ rule above and nothing more. Since QuickFind is given recursively, so what is the point of taking max of $T(n)$ as defined above in \ref{1} please? The justification I got was the one we should put into the recursion of $T(n)$ is because we don't know whether our element will be on the left or on the right, so we take $max$ of the two subproblems. So again, how we don't know if the ith smallest element is on the left on right given we can compare with $x$ at kth position to help us whether to go left or righ, why max $T(n)$?

# Answer
I assume $T(n)$ represents the run-time for an input of size $n$.

## Problem 1

You are right that if $i\<k$ then we take the left part, and if $k\<i$ then the right one. However, creating a recurrence relation with this way of choosing the subproblem size can be problematic - we don't know beforehand which part we will need to choose, so we can't solve the equation.

To solve this problem, we consider only giving a *bound* on $T(n)$ rather than getting the exact solution. So, if we could either take the left subproblem or the right one, we either case perform *at most* as the maximum between them.

Hence, we can write a simpler recurrence relation in the form of $T(n)\le \max\\{T(k-1),T(n-k)\\}$. This relation might be simpler to solve now, and gives a bound on the run-time of the algorithm.

## Problem 2

As you have said, $T(n)$ can be thought of as a random variable. Therefore, $\max\\{T(j-1),T(n-j)\\}$ will also be a random variable, and that should be a big red flag in equation $3$ \- since an expected value must *always* be a real number (or infinite). The expected value is simply never a random variable.

You can derive equation $2$ **without** all the expected values - from the complete probability theorem. Then, apply the expected value on both sides and use its linearity properties.

Now, as we didn't directly use the definition of expectation to get equation $2$, the term $\Pr\[k=j\]$ should make more sense to you now.
> 1 votes

---
Tags: algorithms, quicksort
---


# Question
Title: Solve $T(n) = 3T(\frac n3 + 5) +\frac n2$
Given recursive equation, $T(n) = 3T(\frac n3 + 5) +\frac n2$

$$ \begin{align} T(n) = 3T(\frac n3 + 5) +\frac n2 \tag{1} \label{1} \\ \lt 3T(n- 15) +\frac n2\\ \lt 3 \left(3T\left(\frac{(n- 15)}{3} +5 \right) + \frac{n-15}{2} \right) + \frac {n}{2} \tag{2}\label{2}\\ \lt 9T(\frac n3) + 3\frac {n-15}{2} + \frac n2 \tag{3}\label{3}\\ \lt 9d\_1(\frac n3) \log{\frac n3} + 2n - \frac {45}{2} \tag{4}\label{4}\\ \vdots\\ O(n\log{n}) \end{align} $$

**Problem**: How we got \ref{4} please unless you want to follow another approach?

# Answer
> 2 votes
Define $S(n) = T(n+\alpha)$ for some $\alpha$ to be chosen later. Then:

$$ S(n)=3T\left(\frac{n}{3} + \frac{\alpha}{3}+5\right)+\frac{n+\alpha}{3} = 3S\left(\frac{n}{3} - \frac{2\alpha}{3}+5\right) +\frac{n+\alpha}{3}. $$

Picking $\alpha = \frac{15}{2}$ we get $ S(n) = 3S\left(\frac{n}{3}\right) + \frac{n}{3} + \frac{5}{2} $ and, by the master theorem, we have $S(n) = \Theta(n \log n)$.

We can therefore conclude that $T(n) = S\left(n-\frac{15}{2}\right) = \Theta\left( \left(n-\frac{15}{2}\right) \log \left(n-\frac{15}{2}\right) \right) = \Theta(n \log n)$.

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Reduction from recursive language to recursive enumerable
If any language $L\_1$ reduces $L\_2$ in polynomial time $L\_1\leq\_p^\mathsf{}L\_2.$ If $L\_1$ is recursive then $L\_2$ is recursive and recursively enumerable, is it true? Because $L\_2$ is at least as hard as $L\_1.$

# Answer
> 1 votes
No. However, its true that $L\_2$ is at least as hard as $L\_1$. The opposite isn't true: take for example $L\_2$ being the halting problem, and $L\_1=\emptyset$.

---
Tags: turing-machines, computability, reductions, polynomial-time, enumeration
---


# Question
Title: How do I find the most similar phrase in "Extending Multi-Sense Word Embedding to Phrases and Sentences for Unsupervised Semantic Applications"?
This question is about de paper Extending Multi-Sense Word Embedding to Phrases and Sentences for Unsupervised Semantic Applications, depicted in the following picture:

I am interested in more information about the problem of given a new phrase, find the most similar phrase among **billions** of phrases.

Is it possible to formulate the above problem as a nearest neighbor in euclidean space or a dot product? What is the complexity (time and space) of the algorithm for the embedding a new phrase and for "querying" a new similar phrase? (please also add the time here in seconds because I am interested in the behaviour of the algorithm for very large applications...)

# Answer
> 1 votes
If your goal is simply to find the most similar phrases, you do not need to use the methods in this paper. As the unsupervised phrase experiments show in this paper, multiple embeddings do not improve the similarity measurement.

There are many techniques you can use to find the nearest neighbors efficiently if you represent each phrase as a single embedding. One of the popular libraries is faiss (https://github.com/facebookresearch/faiss). faiss can handle both l2 distance or dot product. You can check their documentation or paper to know how efficient those methods could be.

---
Tags: information-retrieval
---


# Question
Title: What are the chances of hash collision given large input and small hash?
I have an input of 128 bits (binary, 0s and 1s) and want to hash this input with 32 bit CRC. But I am not sure if collision rate is moderate or too high ?
Is it 2^128/2^32 = 2^98.
And does that means 1 collision after 2^98 hashes OR something else ?
I am a little bit confused with the math involved.
Is there any other 32 bit hash better (collision resistant) than CRC 32. I can not use any other hash greater than 32 bits as I have to store these values somewhere.

# Answer
> 0 votes
We don't know anything at all about the distribution of your keys, so we will assume they're random.

You are *guaranteed* to have one collision after $2^{32}+1$ hashes, by the pigeonhole principle.

You can *expect* $\frac{1}{2}$ a collision after $2^{16}$ hashes. The reason for this is not entirely obvious, but it follows from the fact that given $m$ keys and $n$ possible hash values, the distribution of "collisions" follows a Poisson distribution with parameter $\lambda = \frac{m}{n}$.

Think of a hash table with $n$ entries, and you try to insert $m$ keys. Then the probability that a given entry has $k$ keys inserted in it is:

$$\mathrm{Poiss}(k;\lambda) = \frac{\lambda^k e^{-\lambda}}{k!}$$

If you do the sum, you will find that the expected number of collisions is $\frac{1}{2}$ when $m = \sqrt{n}$. This is, of course, the famous birthday problem.

This also means, for example, that if $m=n$, you can expect $\frac{n}{e}$ hash values (i.e. about a third of them) to be unused, $\frac{n}{e}$ (again, about a third) to be used once, and $n(1 - \frac{2}{e})$ (about a quarter) to be used twice or more.

As for using CRC as a hash function, it's hard to say without testing it on your specific keys. CRC is designed for message integrity, and is especially good at detecting burst errors in a noisy channel. But it's probably not a terrible choice.

Just as a final note, "CRC32" usually refers to the polynomial used in HLDC, Ethernet, SATA, MPEG, PNG, and most compression algorithms. The other one that is in common use is Castiglioni's "CRC32C", used in iSCSI, ext4, and several other standards. (There are others, such as CRC32Q used in AXIM, but we'll ignore them.)

Both Intel/AMD (SSE4.2 and above) and ARM (NEON) CPUs have built-in instructions to compute CRC32C. So if you're free to pick the polynomial, that would seem like the best choice on performance grounds.

---
Tags: hash, binary, crc
---


# Question
Title: Adder-Subtractor Circuit With Negative Results
So, I understand how binary arithmetic works, and I understand how an adder-subtractor works for signed numbers. There is only one thing I am not sure about:

All the cases work ok in the circuit I have, except if the result of a subtraction is negative, I need to take the two's complement of the output byte to get the actual result. What can I do about it? Do I need an extra array of adders to compute the two's complement only in that specific way, or is there any smarter solution I can apply?

Thanks in advance.

# Answer
(Can't leave a comment, unfortunately.)

I'm having the same issue. Here's the diagram (sorry, it's messy):

I've also found this on the web:

> The algorithm to subtract two binary numbers using 2’s complement is explained as following below −
>
> * Take 2’s complement of the subtrahend
> * Add with minuend
> * If the result of above addition has carry bit 1, then it is dropped and this result will be positive number.
> * If there is no carry bit 1, then take 2’s complement of the result which will be negative
> 1 votes

---
Tags: arithmetic
---


# Question
Title: Is the language "substrings of a regular language that are over half the length of the superstring" regular?
We say $x$ is a majority substring of $y$ if $y \in \Sigma^\* x \Sigma^\*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular?

I was provided the following solution, but I don't understand it:

> Let M be a DFA that recognizes B. Construct an NFA $N$ that accepts its input $x$ if $x$ is a major substring of some string $y ∈ B$, that is, if $y = uxv ∈ L(M)$ for some string $u$ and $v$ where $|x| ≥ |u| + |v|$. Informally, $N$ uses its nondeterminism to guess the appropriate $y$ as follows. First, $N$ guesses the state $q\_1$ that it is in just before it reads the first symbol of $x$ and the state $q\_2$ that it is in just after it reads the last symbol of $x$. Then it reads $x$ and checks that $x$ takes $M$ from $q\_1$ to $q\_2$. In parallel with reading the symbols of $x$ and performing that check, $N$ guesses the symbols of $u$ followed by the symbols of $v$, and checks that $u$ takes M from its start state to $q\_1$ and that $v$ takes $M$ from $q\_2$ to an accept state. Because $|x| ≥ |u| + |v|$, the machine $N$ has enough time to guess both $u$ and $v$, while it is reading $x$.

What exactly is meant by "$N$ guessing the state that it's in"? Does it iterate over $Q \times Q$ and check if $x$ takes $M$ from $q\_1$ to $q\_2$? If so, is it done by parallelizing these $|Q|^2$ "lines of thought"?

How is it that $N$ can guess the symbols of $u$ and $v$? It seems to me that there are infinite possibilities for $u$ and $v$, and so iterating over these is beyond the capabilities of an $NFA$.

Lastly, how do we guarantee that the guessed $u$ and $v$ have a combined length no more than that of $x$? Counting is outside of the capabilities of an NFA, so I don't think it should be able to count $x$'s length (call it $k$) and try every $s \in \Sigma^k$.

# Answer
> 2 votes
The solution provided is pretty concise.

"First, $N$ guesses the state $q\_1$ that it is in just before it reads the first symbol of $x$ and the state $q\_2$ that it is in just after it reads the last symbol of $x$." That means $N$ is the union of $|Q|^2$ $\text{NFA}$. (That means, running $N$ will be the same as running all those $\text{NFA}$s. $N$ accepts a word iff at least one of those $\text{NFA}$ accepts the word). We can label them $N\_{q\_1, q\_2}$ where both $q\_1$ and $q\_2$ range over all states of $M$ independently. $N\_{q\_1, q\_2}$ will be constructed to accept the words $$\\{x\in \Sigma^\* \mid\text{there exist } u, v\in \Sigma^\* \text{ such that } uxv\in L(M)\\ \text{ and } |x| ≥ |u| + |v|\\ \text{ and, if starting at state }q\_1 \text{ and given input }x, \ M \text{ will go to }q\_2 \\}.$$

Here is a description of $N\_{q\_1, q\_2}$. Running $N\_{q\_1, q\_2}$ will be the same as running one DFA and one NFA *in parallel*. $N\_{q\_1,q\_2}$ accepts a word if and only if that DFA and that NFA both accept.

The $\text{DFA}$ for $N\_{q\_1, q\_2}$ is the same $M$ except that its start state is $q\_1$ and its only accept state is $q\_2$.

The $\text{NFA}$ for $N\_{q\_1, q\_2}$ has states $(r, t)$, where $s$ and $t$ range over all states of $M$ independently. (So, there are $|Q|^2$ states). $(S, q\_2)$ is the start state of this $\text{NFA}$, where $S$ is the start state of $M$. For each accept state of $M$, $(q\_1, M)$ is an accept state of this NFA. In each step, regardless of what is the current input symbol, this $\text{NFA}$ will go from its current state $(r, t)$ to either $(r', t)$ where $r'$ is some state of $M$ that is immediately reachable from $r$ or $(r, t')$ where $t'$ is some state of $M$ that is immediately reachable from $t$. However, if the current state is an accept state, this $\text{NFA}$ will remain in that accept state forever.

You can view this $\text{NFA}$ for $N\_{q\_1, q\_2}$ as running two copies of $M$, one from the start state of $M$ and one from the state $q\_2$. In each step, it will either run the first copy or the second copy, indeterministically. This $\text{NFA}$ accepts once the first copy reaches $q\_1$ and the second copy reaches an accept state of $M$, and it will not change state thereafter. So, when given input $x$ and running in parallel with the $\text{DFA}$ for $N\_{q\_1, q\_2}$, this $\text{NFA}$ for $N\_{q\_1, q\_2}$ is just checking whether within $|x|$ steps it will reach one of its accept states. That is how "$N$ can guess the symbols of $u$ and $v$" even if there might be "infinite possibilities for $u$ and $v$", as well as "guarantee that the guessed $u$ and $v$ have a combined length no more than that of $x$".

---

**Exercise**. Fix a positive integer $k$. We say $x$ is a $\frac 1k$-significant substring of $y$ if $y \in \Sigma^\* x \Sigma^\*$ and $|x| \geq\frac1k |y|$. Show that if $B$ is a regular language, the set of $\frac 1k$-significant substrings of strings in $B$ is a regular language.

# Answer
> 2 votes
The given solution is a kind of hand-waving proof, so the proof by John L. is highly preferable. Here is a different proof, which relies on the notions of *recognisable* and *rational* subsets of a monoid. See the definitions below and \[1, Chapter 3\] for more details. The proof relies on the following known facts:

1. In a finitely generated free monoid, *recognisable* and *rational* subsets coincide (and are usually called *regular*). These two notions usually do **not** coincide in arbitrary monoids.
2. Let $L$ be a regular language of $A^\*$. Then the set $$ T = \\{ (u\_1, u\_2, u\_3) \in A^\* \times A^\* \times A^\* \mid u\_1u\_2u\_3 \in L \\} $$ is a recognisable subset of $A^\* \times A^\* \times A^\*$. This result is originally due to Conway \[2\], a short proof can be found in \[3, Theorem 5.7\].
3. The set $$ S = \\{ (u\_1, u\_2, u\_3) \in A^\* \times A^\* \times A^\* \mid |u\_1| + |u\_3| \leqslant |u\_2 \\}| $$ is a rational subset of $A^\* \times A^\* \times A^\*$. Indeed $S = R^\*$, with $$ R = \\{(1, a, b), (b, a, 1), (1, a, 1) \mid a, b \in A\\} $$
4. The intersection of a rational subset and a recognisable subset of a monoid is rational. See \[1, Chapter 3, Proposition 2.6\] for a proof. Thus $T \cap S$ is a rational subset of $A^\* \times A^\* \times A^\*$.
5. Rational sets are preserved under monoid morphisms. In particular, since the projection $p\_2: A^\* \times A^\* \times A^\* \to A^\*$ defined by $p\_2(u\_1, u\_2, u\_3) = u\_2$ is a morphism, it preserves rational subsets. Thus the language $M = p\_2(T \cap S)$ is rational.
6. The language $M$ is nothing else than the set of "majority factors" of $L$ and thus it is regular.

The proof is sufficiently flexible to be adapted to solve similar questions.

**Reminder of definitions**. Let $M$ be a monoid. A subset $L$ of a $M$ is *recognisable* if there exists a finite monoid $F$, a monoid morphism $f: M \rightarrow F$ and a subset $P$ of $F$ such that $L = f^{-1}(P)$.

The set of *rational subsets* of $M$ is the smallest set of subsets of $M$ containnig the empty set and the singletons and closed under finite union, product and star (here $X^\*$ is the submonoid generated by $X$).

**References**

\[1\] J. Berstel, *Transductions and context-free languages*, Teubner, 1979.

\[2\] J.H. Conway, *Regular Algebra and Finite Machines*, Chapman and Hall, London, 1971.

\[3\] J.-É. Pin, *How to prove that a language is regular or star-free?*, LATA 2020, LNCS **12038** (2020) 68-88.

---
Tags: regular-languages, automata, finite-automata, nondeterminism
---


# Question
Title: In a sorted subarray $Z_{ij}$ elements $i$ and $j$ get compared when either $i$ or $j$ is pivot
This is related to the discussion of average case of quick sort. Given that we have a sorted sub-array $Z\_{ij} = i, i+1, \dots, j$ where $i \< j$.

**Claim**: $i$ and $j$ are compared if and only if, among all elements in $Z\_{ij}$, the first element to be picked as a pivot is either $i $ or $ j$.

**Forward direction Proof**: The **“only if”**: suppose the first one picked as pivot is some $k $ that is between $i$ and $j$, then $i $ and $ j$ will be separated into different partitions and will never meet each other.

**Problem 1**: For backward direction above, I understand that it should be that if the first element to be picked as a pivot is either $i $ or $ j$, then $i$ and $j$ are compared. So I am not sure why the "only if" part was stated as above please?

**Backward direction Proof**: The “if”: if $i$ is chosen as pivot (the first one among $Z\_{ij}$), then $ j$ will be compared to pivot $i$ for sure, because nobody could have possibly separated them yet!

Then we can proceed and define $X$ to be the total number of comparisons and so on until we have $O(n\log{n})$ complexity, which is clear once the above claim is understood, which I have some issues with please.

If $i$ that is chosen as a pivot guarantees based on the proof that we will get $O(n\log n)$ complexity based on the condition that $i$ is the first element to be a pivot and $j$ to be after $i$, then we can see that $E\[X\_{ij}\] = \Pr(i \text{ or } j)$, where $\Pr$ back means the probability that either $i$ or $j$ to be the first pivot and both at the beginning and at the end of the array.

$$E\[X\] = \Sigma\_{i}\Sigma\_{j=i+1}E\[X\_{ij}\] = \frac{2}{j-1+1}$$

**Claim 2**: Now in the randomized case, we can assume a **less clever** assumption (which I don't understand) that: Given that $n$ is the number of elements to be sorted and $T(n)$ is expected time to sort $n$ elements. First pivot chooses $i$th smallest element, all equally likely. Then:

$$T(n) = (n-1) + \frac 1n \sum\_{i=0}^{n-1}(T(i)+T(n-i-1))$$ $$= (n-1) + \frac 2n \sum\_{i=1}^{n-1}(T(i))$$

**Problem 2**: how the previous claim is less clever than the first one please? And how $T(n)$ above is formulated?

**Problem 3**: how $T(n)$ becomes $T(n)= (n-1) + \frac 2n \sum\_{i=1}^{n-1}(T(i))$

# Answer
The claim is proved as follows (in reverse order):

* If the first element among $Z\_{ij}$ to be chosen as pivot is $i$ or $j$, then $i$ and $j$ are compared.
* If the first element among $Z\_{ij}$ to be chosen as pivot is not $i$ or $j$, then $i$ and $j$ are not compared.

The forward direction is the contrapositive of the "only if" implication.

---

Being clever or not is subjective rather than technical. I would just ignore this designation.

---

Perhaps unrolling the sums would help you prove the identity:

$$ T(0) + T(n-1) + T(1) + T(n-2) + \cdots + T(n-1) + T(0) = 2(T(0) + T(1) + \cdots + T(n-1)). $$
> 1 votes

---
Tags: algorithms, quicksort
---


title: why Loop-Programm always terminates

text:
# Question
Title: why Loop-Programm always terminates
well-known that a loop-programm in Theoretical computer science always terminates, but why do that java example not?

```
for( ; ; ){ }

```

# Answer
> 2 votes
Bounded loops terminate, unbounded (as in your example) don't necessarily terminate.

# Answer
> 0 votes
In a “loop program”, the maximum number of iterations for each loop needs to be calculated before the loop starts iterating. In your example that is not the case, so you can’t draw any conclusions that you can draw for “loop programs”.

---
Tags: turing-machines, loops, java
---


# Question
Title: Lower bound for worst case running time for k-clique problem
A naive algorithm for determining whether a graph with $|V|$ vertices has a clique of size $k$ is to list all $k$-subsets of $V$, and check each one to see whether it forms a clique. Why is the running time of this algorithm $\Omega(k^{2}{|V| \choose k})$? Specifically, where are we getting $k^2$?

# Answer
> 1 votes
The $k^2$ comes from the check that a set of size $k$ is a clique.

You will need to verify that each node has all other nodes as neighbors, which takes $\Omega(k)$ time to verify that. There are $k$ such nodes, for a total of $\Omega(k^2)$ time.

---
Tags: algorithms, graphs, clique
---


# Question
Title: Bubble sort on an already sorted collection
When I look at the following algorithm, I believe I understand how bubble sort works.

```
procedure bubblesort
    for i := 1 to n − 1
        for j := 1 to n − i
            if a[j] > a[j+1]
            then
                interchange a[j] and a[j+1]
            endif
        endfor
    endfor
endprocedure

```

However I am having a little tough time understanding statements like the following:

> The only significant advantage that bubble sort has over most other algorithms, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm.

I see bubble sort having to make `n-1` passes, no matter what the sorted status of the collection is. Obviously I am missing something.

# Answer
> 2 votes
Probably that statement does not come from the same source where you got the pseudocode from. Another common way to define Bubblesort is the following:

```
procedure bubblesort
    sorted := false
    while not sorted
        sorted := true
        for j := 1 to n − i
            if a[j] > a[j+1] then
                swap a[j] and a[j+1]
                sorted := false
            endif
        endfor
    endwhile
endprocedure

```

As you can see there will be only one iteration of the outer loop when the collection is already sorted.

---
Tags: algorithms, sorting
---


# Question
Title: Can an instance of the post correspondence problem have exactly one solution?
Can an instance of the Post Correspondence Problem (PCP) have exactly one solution?

# Answer
Either the instance has no solutions or you can obtain infinitely many solutions by repeating the same sequence of selected pairs of words multiple times.

More precisely, using the definitions from Wikipedia, let a solution be: $$ \alpha\_{i\_1} \alpha\_{i\_2} \dots \alpha\_{i\_K} = \beta{i\_1} \beta{i\_2} \dots \beta{i\_K}, $$ then the following is also a solution: $$ \alpha\_{i\_1} \alpha\_{i\_2} \dots \alpha\_{i\_K} \alpha\_{i\_1} \alpha\_{i\_2} \dots \alpha\_{i\_K} = \beta{i\_1} \beta{i\_2} \dots \beta{i\_K} \beta{i\_1} \beta{i\_2} \dots \beta{i\_K} $$
> 2 votes

---
Tags: computability
---


title: How hard is random SAT?

text:
# Question
Title: How hard is random SAT?
There is plenty of research into the so-called "random SAT" problem, where we basically try to solve SAT instances with clauses chosen "at random" in some sense.

There are all kinds of variations of this problem, mostly referring to how the clauses are chosen. Typically you see it written as the random "$k$-SAT" problem, where the clauses have $k$ variables, and where we can also vary the total number of variables and the total number of clauses we will have. We can also look at different probability spaces the clauses are drawn from (is it uniformly at random or something else?).

My big-picture question is, in general, how computationally difficult it is to solve these "random" instances, given some common choices of these parameters. I would be happy to know even just for uniformly at random 3-SAT w/ $n$ variables and $m$ clauses. I have read that many "real-world" industrial SAT instances are much harder to solve than these "random" ones, indicating that perhaps the random-SAT problem is easier than the general SAT problem. There also seem to be various algorithms to solve random SAT instances (although I don't know how fast or successful they are). Also, for random 3-SAT w/ uniformly drawn clauses, it is known that the ratio of clauses to variables is important; if this ratio is less than ~4.25, instances are usually satisfiable, and if the ratio is greater than ~4.25, they are usually unsatisfiable, sometimes called the "threshold of unsatisfiability" for 3-SAT. There are similar analyses for other random k-SATs. This must mean that there is some way to determine if such random instances are satisfiable to begin with.

So my question: basically, at a high level, does this make "random k-SAT" somehow easier to solve than general k-SAT? Does this mean that it is in a different complexity class somehow and if so, what would it be?

# Answer
Theoretically, we don't know how hard *k*-SAT is; P ?= NP remains an open question. Empirically, random $k$-SAT at the critical clause/variable ratio for each $k$ seems to require exponentially more effort as the number of variables increases. As an exercise I ran glucose on thousands of random 3-SAT instances with a 4.26 clauses/variables ratio, averaged the results for each instance size and graphed the results, number of variables vs. decisions.

As expected, the trend is exponential, though the number of decisions needed as problem size increases is nowhere near the naive $O(2^n)$ expectation or the proven $O(1.321^n)$ upper bound for a particular randomized search algorithm.

In a sense all the SAT problems that SAT solvers solve are easy. Any non-trivial problem encoded as a SAT instance will involve thousands if not millions of variables, meanwhile an $n$ value of only a few hundred produces expected worst-case runtimes that dwarf the history of our species. Yet SAT solvers *are* solving such problems, involving absurdly large numbers of variables and clauses, so we must either be very lucky in the problems we encounter or SAT is easy on average.

Random $k$-SAT instances in the critical region between under- and over-constrained seem harder than "industrial" instances for a given formula size. Industrial instances can have thousands of variables and still be solved rapidly enough to be useful in human timescales, while hard random 3-SAT instances of similar size would be completely infeasible to solve on average. Note also that random $k$-SAT instances can be made considerably harder by making them slightly less uniform; see "Generating Difficult SAT Instances by Preventing Triangles".
> 5 votes

---
Tags: complexity-theory, np-complete, satisfiability, complexity-classes, 3-sat
---


# Question
Title: Is there any programming language focused on atemporality?
It seems like a lot of programming is about converting a high-level human intuition into a very precise, ordered set of steps and conditions for the computer to execute correctly. I think programming could match the way people think more if we could write instructions which refer back to previous parts of the program without having to capture them as variables ahead of time. Ideally, the language could be designed to compile the high-level, intuitive instructions into the precise order.

Is there any programming language which relates to these ideas, of being so high-level the program gets significantly reordered upon compiling?

# Answer
You are probably looking for declarative programming. There are various sorts, but most of them are (mostly) atemporal in the sense that there is no notion of order of execution.

Probably the best main-stream example is Haskell. Programs are not "sequences of instructions" but rather systems of equations. When programming in Haskell, we do not think of *how* to compute the result, but *what* equations describe the desired result. Of course, the compiler then generates sequences of instructions in machine code, as there is little else that can be done, given the constraints of the available hardware and the fact that we do happen to live in a universe governed by temporal causality.
> 3 votes

# Answer
## It depends on exactly what you mean

I can see three possibilities for what you might be asking about here.

If the problem is that, in a language like C for instance, it's not possible to write things like this:

```
int f(int x) {
  return g(x + 1);
}
int g(int x) {
  return x + 1;
}

```

because the compiler will complain that it doesn't know what `g` is during the definition of `f`, then the answer is very much **yes**. Many languages allow functions to be defined out of order, although often it comes at the cost that calls to nonexistant functions won't throw an error until they actually happen while the program is running. Python falls in this group for instance, along with most if not all lisp languages.

If, on the other hand, you want the same to apply to variables - allowing programs like:

```
x = y + 1
y = 2

```

Then the answer is also **yes**, but it comes with even stronger caveats. What you're looking for is a purely or nearly purely *functional*\[1\] language like Haskell or Prolog, which can achieve the property you seem to be asking about by virtue of not allowing any modification to a variable once it's been defined. This means the language doesn't have to care where the definition took place - since order doesn't matter, it can shuffle the lines about (kind of) freely. The following is a valid Haskell program that prints `3`:

```
x = y + 1
y = 2
main =
  print(x)

```

I don't think it's possible to have what (I think) you're asking about and also allow variables to be modified, because if a variable can be modified then the language must have some concept of time in order for there to be a 'before' and 'after' changing it.

\[1\] Strictly speaking, being a functional language is unrelated to allowing definitions out of order in this way. What is needed is not allowing variables to be changed after definition, which is one part of functional programming but not all of it. However, I don't think any general-purpose language that doesn't allow variables to be updated wouldn't describe itself as at least a bit functional.
> 1 votes

---
Tags: programming-languages
---


title: Reduction of $RE$ language

text:
# Question
Title: Reduction of $RE$ language
Suppose that the language $L\_1$ reduces to the language $L\_2$ in polynomial time, $L\_1\leq\_p L\_2$. If $L\_2$ is recursive enumerable then so is $L\_1$, but why isn't $L\_1$ recursive? Because $L\_2$ is at least as hard as $L\_1$, and so $L\_1$ could be easier than $L\_2$. Why isn't $L\_1$ recursive? Explain with an example.

# Answer
Every language reduces to itself. Take $L\_1 = L\_2$ to be any recursively enumerable language which isn't recursive.
> 2 votes

---
Tags: computability
---


# Question
Title: How can I represent this description in set builder notation?
The language that accepts strings with the number of 0s being congruent with 1%3 and an even number of 1s over the alphabet {0, 1}.

# Answer
Here is one possible way: $$ \\{ w \in \\{0,1\\}^\* : \text{the number of 0s in $w$ is congruent to 1 modulo 3, and the number of 1s is even} \\} $$
> 1 votes

---
Tags: formal-languages, automata
---


# Question
Title: Is it common to prove that some code is the simplest way to achieve something?
I have a simple program which achieves a certain functionality. I’m interested to know if it can be proven that the steps in the program are the theoretically simplest way to achieve those results. Is it an established practice in computer science to prove that an algorithm or program is the theoretically fastest way to do something, or the one with the least steps? Or is it more often that an algorithm is the fastest known, but it’s impossible to know if there’s a faster one?

# Answer
It is highly uncommon to prove that a certain algorithm is strictly optimal in any sort of sense. It's usually too much to hope for. For example, consider sorting. How many comparisons are needed to sort a list of $n$ numbers? Only a handful of values are known: this is A036604. What is known is that the optimal number is $\Theta(n\log n)$, and so algorithms such as mergesort are asymptotically optimal, that is, optimal up to a constant factor. (In the particular case of comparison-based sorting, probably more accurate bounds are known, but this is not typical.)

For general algorithms, we run into even more trouble, since it's not entirely clear how to measure the complexity of an algorithm. The number of clock cycles that an algorithm takes is highly dependent on the CPU, for example. Therefore we usually only measure the asymptotic time complexity, and we cannot expect to get optimality results which are more accurate than that, unless measuring something other than running time (for example, space complexity, or a measure such as number of comparisons).

Even worse, proving lower bounds on the complexity of problems is extremely difficult. We only know asymptotically tight lower bounds in highly restricted or structured models, such as comparison-based sorting. It is currently hopeless to determine the asymptotic complexity of any algorithm task which cannot be solved in linear time, in all but a handful of cases.
> 1 votes

---
Tags: proof-techniques
---


# Question
Title: Is classical algorithms a dead research field?
I'm starting my masters in CS soon, and I have to decide on a general research topic.

In my undergraduate studies, I've enjoyed courses regarding data structures and algorithms the most. I'm also an avid competitor in competitive programming events, which involve a fair chunk of algorithms.

I've talked to multiple professors in my university who research classical algorithms (mostly graph algorithms), and by the papers they let me read, it seems like most current research in the field is slight improvements of bounds for existing algorithms.

Is this indeed the case? The results I've seen in papers so far don't motivate me to do research in the field too much, but maybe I'm getting the wrong impression since DSA was my favorite subject in my undergraduate studies.

# Answer
Introductory courses, in most areas, don't focus on cutting-edge research. Instead, they teach you the basics. This doesn't mean that there is no cutting-edge research being done.

Once BFS and DFS have been developed, there is no need to develop them again. In that sense, you are right that currently we're in a different situation than the pioneers of computer science. But this doesn't mean that there aren't any interesting questions to think about.

Algorithms and data structures is a huge topic, whose scope ranges from the more practical (e.g., applications of Bloom filters to networking and SAT solvers) to the more theoretical (e.g., fast matrix multiplication algorithms and approximation algorithms). I suggest talking to local faculty who specializes in the area, to get a better perspective on what research is being done, and whether you find it interesting.
> 5 votes

---
Tags: algorithms, graphs, research
---


# Question
Title: Lower bound on comparison-based sorting of $k$-sorted arrays
In $k$-sorting array algorithms, every element is supposed to be $k$ positions from its correct positions. So with that in mind, if we used a randomized QuickSort, we will have $O(n\log{n})$. Now to prove a lower bound on this, we assume $k \le \frac n2$.

**Question**: Prove that you can not do better than $O(n\log n)$ on a $k$-sorted array.

**Goal**: I see here that the point is if we can prove that the lowest we can do is $\Omega(n\log n)$, then that would confirm that we can not do better than $O(n\log n)$ and that will finish the proof.

So, let us consider all possible permutations of $k$. Part of the solution reads:

> Our goal is to prove a lower bound on the number of leaves in a decision tree for an algorithm that sorts an array in which every element is within $k$ positions of its proper position. We therefore provide a lower bound on the number of possible permutations that satisfy this condition.

Next, if we break the array into blocks of length $k$ (with a last block which is possibly smaller), each element will be at most $k$ positions from its correct place. For each full block there are $k!$ possible permutations, thus we have $(k!)^{\lfloor \frac nk \rfloor}$ total permutations of the entire array.

We can then prove a lower bound based on the number of leaves in the decision tree: the lower bound is the logarithm of the number of leaves, which is

$$\ge \log{(k!)^{\lfloor \frac nk \rfloor}} = \Omega(n\log k).$$

Problems:

1. Why for proving a lower bound, we assume $k \le \frac n2$ in the first place? Why this factor specifically was taken into consideration, and why this contributes to finding a lower bound for any algorithm that works for $k$-sorted arrays?
2. So, do we want to go over all permutations of $k$ so that we prove that for each permutation we can still do better than $O(n\log n)$, is this the goal? Is this why we want to consider all permutations based on $k$?
3. How does $\ge \log{(k!)^{\lfloor \frac nk \rfloor}}$ fit in the whole analysis? Why did we start from this? We want to prove a lower bound for $k$-sorted arrays, namely that no algorithm can do better than $O(n\log n)$, so we want a lower bound that does not exceed that, thus we take permutations, which in turn corresponds to leaves in the decision tree. Can you please rephrase the whole approach in your own words? No solution is needed.

# Answer
The complexity of sorting a $k$-sorted array is actually $\Theta(n\log (k+1))$. Given a $k$-sorted array, you can use a modification of heapsort to sort it using only $O(n\log (k+1))$ comparisons. You put the first $2k$ elements in a heap, and you then repeatedly add the next element to the heap, and extract the minimum element from the heap. After exhausting the original array, you repeatedly extract the minimum element from the heap until it is empty. The extracted elements form the correctly sorted array.

The goal of your question is to provide a matching lower bound of $\Omega(n\log (k+1))$ on comparison-based sorting algorithms. This is not a lower bound only on quicksort; *any* comparison-based sorting algorithm must make at least $\Omega(n\log (k+1))$ comparisons in the worst-case. There is no need to assume that $k \leq n/2$ for this lower bound.

The idea of the proof is as follows. Suppose that there are $N\_k$ many $k$-sorted arrays consisting of the numbers $1,\ldots,n$. You can describe any comparison-based algorithm as a decision tree. Each of the $N\_k$ many arrays must end at a different leaf of the decision tree, and so the decision tree has height at least $\log\_2 N\_k$. Consequently, the number of comparisons in the worst case is at least $\log\_2 N\_k$.

Here is a construction of $(k!)^{\lfloor n/k \rfloor}$ many $k$-sorted arrays consisting of the numbers $1,\ldots,n$: the first $k$ elements are an arbitrary permutation of $1,\ldots,k$, the following $k$ elements are an arbitrary permutation of $k+1,\ldots,2k$, and so on. In fact, we can slightly improve this construction by replacing $k$ by $k+1$, obtaining $N\_k \geq ((k+1)!)^{\lfloor n/(k+1) \rfloor}$. This gives a lower bound of $$ \log\_2 ((k+1)!)^{\lfloor n/(k+1) \rfloor} = \lfloor n/(k+1) \rfloor \log\_2 (k+1)! = \Omega(n/(k+1)) \cdot \Omega((k+1)\log(k+1)) = \Omega(n\log (k+1)). $$
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?
**Corollary:1** We know that if $A\leq\_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable.

This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ then we can have a solution of $A$ as well. Hence $A$ is decidable.

We know that regular languages is always decidable.

**Corollary:2** So from (**Corollary:1**)if $A\leq\_m^\mathsf{}B$ and $B$ is regular then $A$ is should also be regular.

But I have made this wrong my taking Counterexample. For example, define the languages $A = \\{ 0^n1^n \mid n\ge 0 \\} $ and $B = \\{1\\}$ both over the alphabet $\sum = \\{0, 1\\}.$ Define the function $f : \sum^\*\to \sum^\*$ as $$ f(x) := \begin{cases} 1,& \text{if}\ w\in A,\\0,&\text{if}\ w\not\in A\end{cases} $$ Observe that $A$ is a context-free language, so it is also Turing-decidable. Thus, $f$ is a computable function. Also, $w \in A$ if and only if $f(w) = 1,$ which is true if and only if $f(w)\in B.$ Hence,$A\leq\_m^\mathsf{}B.$ Language $A$ is nonregular, but $B$ is regular since it is finite.

Above example proving that $A$ isn't necessarily regular. But according to **Corollary:1**, $A$ must be regular. I don't understand where I did make mistake during understanding of theory.

# Answer
> 2 votes
Corollary $2$ is false.

It seems that you are using the implication "$L$ is regular $\implies$ $L$ is decidable" in the wrong direction. If $A \le\_m B$ and $B$ is regular, Corollary 1 only tells you that $A$ is decidable, which does not imply that $A$ is regular.

---
Tags: turing-machines, np-complete, polynomial-time, polynomial-time-reductions
---


# Question
Title: Knapsack like problem with nonnegative weight constraint
I am dealing with a knapsack-like problem with one difference from the conventional problem: the “weights” can be positive or negative and the constraint is $\sum w\_i x\_i \ge 0$ instead of $\sum w\_i x\_i \le W$. The "values" can also be positive or negative.

Can this be transformed to a knapsack problem or is it some other type of combinatorial optimization problem?

# Answer
> 1 votes
If the values $v\_i$ of the items are non-negative you can simply "buy" all items with positive weights. Let $S = \\{i \mid w\_i \le 0\\}$, $W = \sum\_{i \not\in S} w\_i$ and $V = \sum\_{i \not\in S} v\_i$. Your problem then becomes a standard Knapsack problem:

$$ \max \sum\_{i \in S} y\_i v\_i \quad \mbox{s.t.}\\ \sum\_{i \in S} -w\_i y\_i \le W, \\ y\_i \in \\{0,1\\} \quad \forall i \in S. $$

Once a solution for the new problem is found, a solution for the original problem can be recovered by setting: $$ x\_i = \begin{cases} y\_i & i \in S \\ 1 & i \not\in S \end{cases} $$

The value of the new solution will be $\sum\_i x\_i v\_i = V + \sum\_{i \in S} y\_i v\_i$.

---
Tags: knapsack-problems
---


title: Proofs of reduction of any hard problem

text:
# Question
Title: Proofs of reduction of any hard problem
**Approach:1** To prove any unknown problem $B$ is **NPH** then take any known **NPH** problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I\_1$ of $A$, then prepare another instance example $I\_2$ of $B$, and if $I\_2$ can be solved in polynomial time then $I\_1$ can be solved in polynomial time, then we say
$$A\leq\_m B.$$

**Approach:2** Define the function $f\colon \Sigma^\*\to \Sigma^\*$ as $$ f(x) := \begin{cases} 1,& \text{if}\ w\in A,\\0,&\text{if}\ w\not\in A.\end{cases} $$ Thus, $f$ is a computable function. Also, $w \in A$ if and only if $f(w) = 1,$ which is true if and only if $f(w)\in B.$ Hence, $A\leq\_m B.$

My question is:

> Are both approaches are right for reduction? What is the difference between them? According to me, **Approach:1** is uses for hard problems, and **Approach:2** uses for decidable problem.
>
> I am struggling to understand difference between these.

# Answer
> 8 votes
The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$ in NP, there is a polytime many-one reduction from $A$ to $B$.

The second "approach" is the definition of a computable many-one reduction, which is used to define hard problems for the arithmetical hierarchy.

There are many other notions of reductions that appear in computability theory and complexity theory. The most common are oracle reductions, logspace reductions, and $\mathsf{AC^0}$ reductions.

In fact, there are two orthogonal dimensions here: one is whether the reduction is many-one or oracle, and the other is whether there are any bounds on the complexity of the reduction: computable, polytime, logspace, or $\mathsf{AC^0}$. A third orthogonal dimension is randomization: sometimes we allow our reductions to be randomized.

The notation $\leq\_m$ is usually used in contexts in which it has a clear meaning. If you are discussing both computable many-one reductions and polytime many-one reductions, you need to use two different symbols, to prevent confusion.

---

Why do we need so many different types of reductions? In order to properly define completeness, we need the reduction to be *weak* enough, to prevent the concept from trivializing. For example, all non-trivial problems in NP are NP-hard with respect to *computable* many-one reductions; in order to obtain a non-trivial concept of NP-hardness, we need to make the reductions weaker than NP.

On the other hand, if the reduction is too weak, then we might have no hard problems, or only few hard problems. Many NP-hard problems are actually hard with respect to reductions weaker than polytime, so it's not immediately clear that the "correct" definition of NP-hardness is with respect to many-one reductions.

A separate issue is whether we should use many-one reductions or oracle reductions. If we used oracle reductions, we couldn't distinguish NP from coNP, for example. Nevertheless, in some cases we are only able to prove that certain problems are NP-hard with respect to oracle reductions (usually known as Turing reductions in this context), which is better than nothing.

---

Which reduction should we "use"? If you want to prove that a language is NP-hard, you should use a polytime many-one reduction, since this is the most general type of reduction for which the proof scheme mentioned in your post works. In other settings you should use other types of reductions, depending on the setting.

---
Tags: complexity-theory, np-complete, np-hard, polynomial-time, polynomial-time-reductions
---