# Question
Title: Is there any recursive function f whose code is unique?
I am doing some reviewing for the term final on computability and found out this simple exercise. I am very fresh on theoretical computer science so if you do have an answer please make it simple.

The question is fairly simple: Is there any recursive function f whose code is unique? That is $comp(p\_1, ) \doteq comp(p\_2,) \doteq f $ implies $p\_1=p\_2$.

$comp$ is the universal recursive function. That is, the function that for every recursive function $ f: \mathbb{N}^m \rightarrow \mathbb{N} $, exists a code $p\_f$ such that $f \doteq comp(p\_f, \<x\_0,x\_1,...,x\_{m-1} \> )$. And $\doteq$ designates equality in Kleene sense.

I found in my notes Rice's theorem in the following form.

Let $k$ be an arbitrary natural number and $ g: \mathbb{N} \rightarrow \mathbb{N} $. If g satisfies the following conditions, the $g$ is not recursive.

1.Totality: For any $p\in\mathbb{N}$, the value $g(p)$ is defined and $g(p)\in {0,1}$

2.No constant: $g$ is not constant. There exists two natural numbers $p\_0,p\_1\in\mathbb{N}$ such that $g(p\_0)=0 $ and $ g(p\_1)=1$

3."Reflects equivalence of codes" If p,q are codes for the same recursive function $\mathbb{N}^k \rightarrow \mathbb{N}$ then $g(p)=g(q)$

I know the answer must be No there is not by property 3 but how can I formally write it.

# Answer
> 6 votes
No. The Padding Lemma states that there is a primitive recursive function $\sf pad$ such that, if $n$ is a code for $f$, then ${\sf pad}(n)$ is another code for $f$ which is larger than $n$.

Therefore, if $f$ has a code, it has infinitely many.

The intuition is: if you have a TM $M$ computing $f$, you can modify the TM so that it starts with some useless steps (e.g. move right, then left), and then behaves as $M$. The modified TM has a few more states, and under the "usual encoding" it will have a larger code than $M$.

# Answer
> 4 votes
Rice's theorem is indeed applicable. Remember the intuitive meaning of Rice's theorem: any nontrivial property of partial computable functions either always holds, always fails, or is nonrecursive - in the sense that the set of natural numbers with that property is nonrecursive. This isn't how you've phrased it but it's a bit easier, in my opinion, to think in terms of properties: besides matching what we think about normally, they correspond to total functions (set $g(x)=0$ if the property fails for $x$ and $g(x)=1$ if the property holds for $x$) and this makes condition (1) trivial.

Now in our case, the property we care about is "is an index for $f$." It's easy to check that (2) and (3) hold for this property: some but not all natural numbers are indices for $f$ *(note that this doesn't assume what you're trying to prove - you just need that $f$ has at least one index, and that there is more than one recursive function)*, and if $a,b$ are indices for the same partial recursive function $h$ then either $h\cong f$ in which case the property holds of both $a$ and $b$ or $h\not\cong f$ in which case the property fails for both $a$ and $b$.

So by Rice's Theorem, the set of naturals with this property - that is, **the set of indices for $f$** is non-computable.

---

It's worth noting that Rice's theorem doesn't hold in all situations you might imagine! Specifically, we can whip up recursive numberings of partial recursive functions *which don't satisfy the padding lemma*; these are called **Friedberg numberings**, and see this paper of Kummer for a simple proof that they exist.

* Note that as an immediate consequence there is no effective way to translate from the usual numbering to a Friedberg numbering *(it's a good exercise to make this precise and prove it)*. As a consequence you can think of a Friedberg numbering as a hilariously awful programming language F - in which every program $\pi$ you can write in your favorite non-stupid langauge has a corresponding program $\hat{\pi}$ in F, but you can't find it!

Basically, the existence of *good* numberings of partial recursive functions is something we should all be nontrivially happy about.

---
Tags: computability, recursion
---


title: Is the following a AVL tree?

text:
# Question
Title: Is the following a AVL tree?
I have a tree as

Is it an AVL tree? it seems to balanced for me.

# Answer
> 3 votes
No, it is not an AVL tree.

A binary tree is defined to be an AVL tree if $${\text{BalanceFactor}}(N)\in {\\{-1,0,1\\}} $$ holds for **every** node $N$ in the tree, where $$\text{BalanceFactor}(N):=\text{Height(RightSubtree(N))} - \text{Height(LeftSubtree(N))}$$

Consider Node 2. Its left subtree is a degenerated tree of height 2. Its right subtree is empty. Whether the height of an empty tree is 0 or -1 is up to debate. In the context of AVL trees, I would prefer to define the height of an empty tree to be -1. $$\text{BalanceFactor}(\text{Node 2}) = (-1) - 2 = -3\not\in\\{-1,0,1\\}.$$ So the tree in the question is not balanced, although we can say it is balanced at the root.

In fact, every kind of definition of a balanced (rooted) tree (that I know) requires all of its subtrees be balanced of the same kind. So, the tree in the question is unlikely to be considered balanced for any definition of a balanced tree. For example, it is not a $1/2$-weight balanced tree.

In summary, the subtree whose root is node 2 does not look balanced, which makes the tree not balanced.

---
Tags: data-structures, avl-trees
---


# Question
Title: Polysize bounded depth circuit for modified MAJORITY problem
I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x\_1,\ldots, x\_n)$ that gives $1$ if $\sum x\_i \geq n/2 + n/\log n$ and $0$ if $\sum x\_i \leq n/2 - n/\log n$. This is a modified form of the MAJORITY problem.

I want to use the probabilistic method but I cant seem to get it to work. I found a way to get a circuit that was not of bounded depth, iterate a bunch of random layers of gates that compute the MAJORITY function for three randomly selected inputs. This will, for $\mathcal{O}(\log n)$ depth, give the right result with overwhelming probability, so one such circuit is always correct.

I think I should have layers of alternating AND and OR gates, but since the $n/\log n$ factor is so small, even when we should get a $1$ for instance, the probability that a random input is a $1$ is only $1/2 + 1/\log n$, not really so high. I cannot seem to amplify this enough to take care of both cases.

Any help?

# Answer
> 1 votes
This task is known as approximate counting or approximate majority. The first to construct such a circuit was Ajtai in his celebrated 1983 paper $\Sigma\_1^1$-formulae on finite structures, which also proves the first switching lemma. You can check out Section 3 for the construction. For a more modern account, see Section 2 of Viola's Randomness buys depth for approximate counting.

---
Tags: complexity-theory, circuits, probabilistic-algorithms
---


# Question
Title: graph theory conventions, difference between a PATH and a GRAPH?
Consider this example, I did my pseudocode in python

```
findCycle(G):
    for each edge e in E(G):
        if isThereCycle(G-e):
            G = G - e
    return G

```

assume isthereCycle returns whether the graph $G$ has a cycle.

Input is a graph $G$ that contains a cycle, and the function should return a path of that cycle.

We go through each edge then remove it and see if a cycle still exists without that edge, until we are left with a graph with a single path that is a cycle. (Assume removing the edge (G - e) doesn't mutate the graph unless we do G = G - e).

I want to return a path. Is what I'm returning a path?

# Answer
Your algorithm returns a cycle rather than a path.

Here is a cycle:

Here is a path:

(Both images taken from Wikipedia.)

To get a path from the cycle, simply remove one edge (this is my best guess for what *return a path of that cycle* means).

Let me also mention that your algorithm is very inefficient. A much better choice is to use BFS/DFS.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?
According to this source,

> If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to the given problem. This reduction thus gives a lower bound for the complexity of B.

Now consider the following scenario: X is an NP-hard problem. It is polynomial-time many-one reducible to problem Y. This makes Y NP-hard. My question is, it could be possible that X has a better solution like NP or P, which we could not find. Then why should Y be NP-hard? It could be NP or P. If Y turns out to be P (assume) then X becomes P.

# Answer
All NP-complete problems are "equally hard", in the sense that if one of them is in P, then all of them are in P. Similarly, if one NP-complete problem can be solved in quasipolynomial time (that is, time $e^{O(\log^C n)}$ for some constant $C$) then all of them can be solved in quasipolynomial time.

Some NP-hard problems are harder than others, but all of them are at least as hard as all NP-complete problem. That is, if some NP-hard problem is in P, then all NP-complete problems are in P. Similarly, if some NP-hard problem can be solved in quasipolynomial time, then the same holds for all NP-complete problems.

However, some NP-hard problems are *provably* harder than others. For example, the halting problem is NP-hard, but in contrast to all NP-complete problems, it cannot be solved in exponential time; in fact, it cannot be decided at all!

---

> My question is, it could be possible that X has a better solution like NP or P, which we could not find.

There are two problems with this statement. The first is the assumption that NP is a better complexity class than NP-hard. In fact, all NP-complete problems are both NP-hard and in NP (that's the definition of NP-completeness), so it's in fact common for problems to be both. NP-hardness is a *lower bound* on complexity, whereas being in NP is an *upper bound*. The two are not contradictory in any way.

The second problem is the assumption that it could be possible that X is in P. As explained above, that would imply that P=NP, which most people consider unlikely. An NP-hard problem cannot be "easy" – it's at least as hard as any problem in NP, and in particular at least as hard an any NP-complete problem.

---

> Then why should Y be NP-hard?

You can prove that Y is NP-hard if you can reduce, in polynomial time, another NP-hard problem X to it. I won't repeat the proof here, since it can be found in textbooks, lecture notes, and even here on Computer Science.

---

> If Y turns out to be P (assume) then X becomes P.

That's correct, but there is no contradiction here. This is actually the point of NP-hardness. We don't believe that Y is in P, since that would imply that X, as well as many other problems, are also in P.
> 4 votes

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


# Question
Title: Calculate minimum and maximum Ethernet (IEEE 802.3) frame size from frame format
According the frame format of Ethernet

Minimum Frame Size should be :

```
7Bytes + 1Bytes + 6Bytes + 6Bytes + 2Bytes + 46Bytes +4Bytes = 72Bytes

```

Maximum Frame Size should be :

```
 7Bytes + 1Bytes + 6Bytes+ 6Bytes + 2Bytes + 1500Bytes + 4Bytes = 1526Bytes

```

But it is said that the minimum frame size is $64Bytes$ while the maximum frame size is $1518 Bytes$.

How the frame sizes are calculated ?

# Answer
> 0 votes
The preamble and SFD do not count towards the frame size since they are only part of the Ethernet *packet* (i.e., layer 1), not of the Ethernet *frame* (i.e., layer 2); see here, for instance. Recall that Ethernet is not a pure layer 2 protocol but actually a mix of layers 1 and 2.

---
Tags: computer-networks
---


title: What types are propositions?

text:
# Question
Title: What types are propositions?
In the propositions-as-types paradigm, we are still faced with the question : what types are propositions ? I currently know 3 different answers :

* Coq's sort `Prop` and its typing rule that asserts it is closed under products indexed by abtirary types $$\frac{A : \mathsf{Type}\_i \qquad x : A \vdash B(x) : \mathsf{Prop}} {\prod\_{x : A} B(x) : \mathsf{Prop}}$$
* HoTT's `HProp`, which are types where all elements are equal, together with the `HProp` truncation `fun A:Type => ∥A∥`, which assigns an `HProp` to each type `A`.
* Coq's new `SProp`. As far as I understand, `SProp` is almost the same as `HProp`, but instead of explicit rewrites, the type checker will be happy to implicitely convert any element of an `SProp` into another. So I won't discuss `SProp` anymore here.

I see some common points between `Prop` and `HProp`, the main one being that Coq is compatible with the axiom of proof irrelevance, which asserts that all `Prop`s are `HProp`s. Also there is the similar guarded `match`. Coq accepts to `destruct` a proof of a `Prop` only when it is proving a `Prop`. Likewise, the recursion principle of the `HProp` truncation accepts to lift `∥A∥ -> B` into `A -> B`, only when `B` is an `HProp`. Another common point is seen via Coq's extraction mechanism : all proofs of `Prop`s will be discarded, because they map to singleton types.

However I don't clearly see how either of these definitions captures the concept of a proposition. A `HProp` makes some sense to me, because uniqueness allows to interpret inhabitants as mere proofs that the `HProp` is true. But then one can argue that a proposition does have different proofs, some being simpler than others for example. Or some using more or less axioms than others (constructive proofs versus classical proofs for instance). Concerning Coq's `Prop`, I understand that it is impredicative, but I don't think it explains enough. And why didn't Coq take proof irrelevance as a hard typing rule (where 2 proofs are the same `Prop` would be judgementally equal, rather than propositionally equal) ? I think it would be compatible with HoTT, if we redefine `eq` in sort `Type` rather than `Prop`.

Part of the answer might come from the function extensionality axiom. If it is not there, then it is very hard to prove that a type is a `HProp`. So Coq's `Prop` might be a way to handle propositions without assuming funext. For instance, the closure of `HProp` by the `forall` quantifier needs funext, so `Prop`'s typing rule might be seen as an instance of funext.

Are there other definitions of propositional types ?

# Answer
The original conception of propositions-as-types did not distinguish propositions and types at all: all types are propositions. Under this view, we may indeed speak of different proofs of a proposition.

One way to understand the differences between different conceptions of propositions-as-types is to view them as capturing different notions of provability and truth:

* If we say that `Prop = Type` then the elements of a proposition are the proofs, so we are capturing **proof constructions**. We may analyze proofs, and for instance distinguish them according to their size, the assumptions they use, etc.
* If we say that `Prop = HProp` then the elements of a proposition witness existence of proofs (but are not specific proofs), so we are capturing **provabillity**. We can still discern the reason for a proposition being true, because we can analyze the proof as lons as further constructions do not depend on the choice of proof.
* If we use the strict `SProp` which makes all proofs judgmentally equal (or simply erases proof altogether), then inside type theory we can never "discern" the reasons for a proposition being true, so this is more like **truth**, i.e., an external reason for something being the case. We do have soundness in the sense that type theory can express semantic entailment, e.g., if $p$ and $q$ are true then so is $p \land q$.

Coqs `Prop` is *conservative* in the sense that it makes no commitment as to what `Prop` is supposed to be. Coq is compatible with the view that `Prop` is an (impredicative) `Type`, as well as that it is something like `HProp`, or even just `bool`. This is a design decision.
> 6 votes

---
Tags: coq, homotopy-type-theory, calculus-of-constructions
---


title: is FIND WORDS in P?

text:
# Question
Title: is FIND WORDS in P?
**FIND WORDS** is the following decision problem:

Given a list of words *L* and a Matrix *M*, are all words in *L* also in *M*? The words in *M* can be written up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-righ-down. To be specific this is the classic game that can be found in the puzzling week: **FIND WORDS**

Now this decision problem clearly is in **NP** because, given a certificate with the positions of the words in the matrix (indexes), a verifier can check it in polynomial time.

My question is this: are we aware of Turing Machines that decide this language in polynomial time?

# Answer
> 16 votes
Your language is in P. Suppose that the matrix is $n\times n$ and that the words have total length $\ell$. Each word can start at at most $n^2$ positions and be written in $O(1)$ many orientations, for a total of $O(n^2)$ possible placements. Checking each one costs at most $O(m)$, where $m$ is the length of the word. In total, we obtain an algorithm whose running time is $O(\ell n^2)$, which is quadratic in the input length.

Using a trie or similar data structure, you can probably improve this to linear time $O(n^2 + \ell)$.

# Answer
> 5 votes
Let $M$ be a $n \times n$ matrix. And I am searching a word $l\_ll\_2 \dots l\_k $ of length $k$. Now first we search $l\_1$ in $M$. It takes $O(n^2)$ time. For each successful search, we look at all eight direction (up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-right-down) and check if $l\_2 \dots l\_k $ exists or not. At one direction it takes $O(k)$ time. So overall running time is $O(kn^2)$.

---
Tags: np, decision-problem
---


title: How Reduction works in proving NP-Hard?

text:
# Question
Title: How Reduction works in proving NP-Hard?
A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq\_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq\_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.

I also found that, for a given X, say TSP, to prove it is $NP$-Hard, we often find a ($NP$-Complete) Z say $HAM-CYCLE$ (Hamiltonian-Cycle), and try to show that $HAM-CYCLE$ can be reduced to a $TSP$ in polynomial time.

My confusion is, why don't we try to show that for each instance of $TSP$, there exists a corresponding instance of $HAM-CYCLE$. Specifically, what if there exists an instance of $TSP$, for which there is no corresponding instance in $HAM-CYCLE$! In this case, how can the prior knowledge about the hardness of $HAM-CYCLE$ help in inferring on TSP's hardness!

Note: I also had similar concerns with proving $NP$-complete class. However, since all $NPC$ are also $NP$, I felt, similar reduction of a known NPC problem to a given problem, say Q, works. However, for $NP$-hard case, a given problem X need not to be $NP$ at all.

# Answer
Apparently, you are expecting the reduction between any two $\mathsf{NP}$-complete problems $X$ and $Y$ to be a one-to-one map (e.g., a bijection). The idea of a reduction, however, is irrelevant to having instances "correspond" to others. What reductions do give us is a *hardness relation* between problems (and not between individual instances). If $A$ and $B$ are problems and $A$ is reducible to $B$, then we expect $B$ to be harder than $A$; the idea is that, if there is an efficient algorithm which solves $B$, then we can also solve $A$ by reducing it to $B$ and running said algorithm. Completeness, then, corresponds to the notion of *hardness equivalence*: $A$ is reducible to $B$ and $B$ is reducible to $A$; that is, if $A$ is hard (resp., easy), then so is $B$, and vice-versa.

To give an example why we cannot generally expect reductions to be injective, surjective, or even bijective, let again $X$ to be $\mathsf{NP}$-complete and consider the problem $Z = \\{ (0, x) \mid x \in X \\} \cup \\{ (1, y) \mid y \in \\{ 0,1 \\}^\ast \\}$. Naturally, we can reduce $X$ to $Z$ by mapping each instance $x$ of $X$ to $(0,x)$; this does not give us a surjective map. Further, note $Z$ is also reducible to $X$: map $(0,x)$ to $x$ and $(1,y)$ to $x'$ where $x' \in X$ is a fixed (i.e., hard-coded) instance. This reduction is surjective, though not injective. As you can see, there is really no relation between what we expect from a reduction and injectivity or surjectivity.
> 2 votes

# Answer
> My confusion is, \[when proving that TSP is NP-hard by reduction from HAM-CYCLE\] why don't we try to show that for each instance of TSP, there exists a corresponding instance of HAM−CYCLE.

Because it doesn't matter. Being able to solve TSP allows you to solve HAM-CYCLE. The fact that it also allows you to do some other stuff (solve the TSP instances that don't correspond to translations of HAM-CYCLE instances) isn't an issue.

For example, if I tell you that multiplying numbers allows you to compute yearly salary from monthly salary, you don't object that $13\times 11$ doesn't correspond to any such calculation.
> 2 votes

# Answer
If one has access to a polynomial algorithm solving $X$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$.

Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances of $X$ are hard, even if they don't have any corresponding instances in $Z$.
> 0 votes

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


title: Langton's Ant Periodic Behavior

text:
# Question
Title: Langton's Ant Periodic Behavior
I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

# Answer
> 8 votes
The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–*Kung* theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

1. The path of the ant is (ultimately) periodic if and only if it is bounded. (Clearly, an unbounded path cannot be periodic. Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)
2. Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical. To return to a particular square after once leaving it, the ant must travel an even number of steps. Thus, if the ant once enters a given square horizontally (or vertically), it must *always* enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant *never* visits during its periodic path. (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can. Since the ant's path is, by assumption, bounded, this process will always terminate.) Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left. But this means that the ant would have to always turn in the *same* direction after entering this square, which is impossible by definition.

---
Tags: cellular-automata
---


# Question
Title: Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess?
The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and pick the best sequence of moves so far.

Let's suppose we remove this limit, and we search for the whole tree. Would this techinque always win? If the answer is no, would it ever lose? (so, would it only win+draw, or also lose?)

A good answer would include theoretical underpinnings of why or why not this would work, both from the game-theoretic aspects of chess and from the proprieties of the minmax algorithm.

# Answer
By definition, minmax chooses the move that results in the best possible outcome if the adversary plays optimally, but within the bounds of what the evaluation function takes into account. More precisely, minmax results in the best outcome that can be guaranteed no matter how the adversary plays, as long as the adversary's behavior is no worse than what the evaluation function predicts.

If minmax searches on the whole tree, then it never calls the evaluation function, and therefore it models the adversary perfectly. So in this case, minmax achieves the best guaranteed outcome that can be guaranteed against an arbitrary adversary. This is true regardless of the game.

For chess, there are three possible outcomes: win, draw, loss (from best to worst). We don't know what the best *guaranteed* outcome for each player is. But whatever it is, if you can run minmax on the whole tree, you'll get that outcome or better (the outcome can be better if the adversary plays suboptimally). Of course, this is only practical near the end of the game when there are few pieces remaining in play.
> 2 votes

# Answer
Nobody knows if chess is a forced win for white, or even a forced draw for white.

If it is a forced win, then white with optimal gameplay will always win. If it is a forced draw, then white with optimal gameplay will always at least draw, and may win if black doesn't play perfectly. If it is neither a forced win nor a forced draw, then white with optimal gameplay will lose unless black makes a mistake.

If both white and black examine the complete game tree and always play optimally, then the outcome will always be the same (but we don't know if it will be white win, draw, or black win).

The answer to your question is quite trivial, nothing deep to see here or required.
> -1 votes

---
Tags: artificial-intelligence, game-theory, board-games, minmax-algorithm
---


# Question
Title: In-place matrix transposition using rotations
Some time ago I invented an algorithm for in-place matrix transposition using rotations.

A matrix of size N×M is represented as a one-dimensional array of size N\*M, which is also the future storage for the corresponding transposed M×N matrix.

The algorithm moves an element to its proper position in the representation for the transposed matrix rotating the sub-array of the array 1 element right, starting at the correct and ending at the current position of the element.

Let `matrix` be the array of size `N*M`, where `N` and `M` are the number of rows and columns in the original matrix (and the number of columns and rows in the transposed). Array indices are from `0` to `N*M-1`.

Let `dst` be the proper position for the element in the array for the transposed matrix, `src` — its current position, `src_inc` is the value addet to `src` to point to the "current position" of the next element to be moved. The algorithm starts with `dst = 1`, `src_inc = M` and `src = dst + src_inc - 1` (which is equal to `M`) (The element at the `0`-th position is already in its right place). After the first rotation, we increment `dst` by `1` and `src` by `src_inc` (which is `M`) **until** `dst` points to an element which should not be moved. This happens when `(dst + 1) % N` is `0`. In this case we skip the element (incrementing `dst` again), decrease `src_inc` by one and restore the initial relation between `src` and `dst``src = dst + src_inc - 1`.

Let me, instead of writing a pseudo-code, show the C++ code and add a state of the array before each rotation (plus the final result)

```
#include <algorithm>

template<typename T>
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    int dst = 1;
    int src_inc = M;
    int src = dst + src_inc - 1;

    while (src < N*M && dst < src)
    {
        std::rotate(matrix + dst, matrix + src, matrix + src + 1); // rotate right for 1 position
        if ((dst + 1) % N != 0) {
            dst += 1;
            src += src_inc;
        } else {
            dst += 2;
            src_inc -= 1;
            src = dst + src_inc - 1;
        }
    }
}

```

(https://wandbox.org/permlink/XAWE1Fn64SxvEvth)

Original `3×5` matrix:

```
11 12 13 14 15
21 22 23 24 25
31 32 33 34 35

```

The trace (the first row is indices, the matrix is represented linearly, `dst` and `src` to the right are shown **before** the rotation, the result of the rotation is on the next line):

```
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
11 12 13 14 15 21 22 23 24 25 31 32 33 34 35 | dst = 01, src = 05
11 21 12 13 14 15 22 23 24 25 31 32 33 34 35 | dst = 02, src = 10
11 21 31 12 13 14 15 22 23 24 25 32 33 34 35 | dst = 04, src = 07
11 21 31 12 22 13 14 15 23 24 25 32 33 34 35 | dst = 05, src = 11
11 21 31 12 22 32 13 14 15 23 24 25 33 34 35 | dst = 07, src = 09
11 21 31 12 22 32 13 23 14 15 24 25 33 34 35 | dst = 08, src = 12
11 21 31 12 22 32 13 23 33 14 15 24 25 34 35 | dst = 10, src = 11
11 21 31 12 22 32 13 23 33 14 24 15 25 34 35 | dst = 11, src = 13
11 21 31 12 22 32 13 23 33 14 24 34 15 25 35 | final array

```

(the code producing the trace https://wandbox.org/permlink/3nhlwYoSz5GnWuUP)

And transposed matrix (reinterpretation of the array as a representation for a `5×3` matrix):

```
11 21 31
12 22 32
13 23 33
14 24 34
15 25 35

```

The algorithm is not optimal, it does  swaps (assuming the rotation is implemented as a chain of swaps), but it is short and seems to work.

However, I couldn't prove why it should work. I was just curious to try to transpose a matrix using rotations instead of chain of swaps following cycles and discovered that there is a relatively simple law how to select the next sub-array for rotation. Is this algorithm published anywhere?

# Answer
After the array is rotated with `dst == N - 1` (so the condition `(dst + 1) % N == 0` is about to fire), the tail of the array starting from index `N` looks like a representation of a N×(M-1) matrix with the values of the original matrix without the first column:

```
11 21 31 12 13 14 15 22 23 24 25 32 33 34 35
         ^ starting from here

```

looks like a representation of the

```
12 13 14 15
22 23 24 25
32 33 34 35

```

matrix

which immediately suggests how to simplify the algorithm:

```
template<typename T>
void inplace_transpose_using_rotations(T* matrix, int N, int M)
{
    if (N == 1 || M == 1)
        return;

    for (int dst = 1; dst != N; dst++)
        std::rotate(matrix + dst, matrix + dst * M, matrix + dst * M + 1);

    inplace_transpose_using_rotations(matrix + N, N, M - 1);
}

```

This explains how the algorithm works: rotations move first elements of each row into their proper position in the transposed matrix and at the same time shift the other elements to the right forming a representation of a smaller N×(M-1) matrix in the right side of the array. Then this smaller matrix is transposed, until we get a N×1 matrix.
> 1 votes

---
Tags: correctness-proof, matrices, check-my-answer, in-place
---


# Question
Title: Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal
Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one.

A greedy algorithm for this would keep removing digits such that the resulting integer is the smallest. For the above example:

```
Step 1: Remove 2 => 114532
Step 2: Remove 5 => 11432
Step 3: Remove 4 => 1132
Step 4: Remove 3 => 112

```

Can you prove that this algorithm is optimal (i.e. the final integer is the smallest possible)? Or if it is not, show a counterexample?

Thanks!

# Answer
> 5 votes
The greedy algorithm is optimal.

The simple observation is that any optimal $k$ digits to remove must contain the rightmost digit in the initial non-decreasing digits of A, or one of its equivalents.

---

Given an $n$-digit number $A=a\_{n-1}a\_{n-2}\cdots a\_1a\_0$, where each $a\_i$ is a digit, let $a\_t$ be the rightmost digit of $A$ such that $a\_n, a\_{n-1}, \cdots, a\_t$ is non-decreasing. Let $r$ be the number of all digits that are equal to $a\_t$ from $a\_t$ to its left. In other words, the digits of $A$ are classified as displayed in the following illustration for some integer $t$ and $r$, where $ a\_t\>a\_{t-1}$ and $a\_{t+r}\<a\_{t+r-1}=\cdots=a\_{t+1}=a\_t$. Note that if there is only one digit in $A$, it is $a\_t$ with $t=0$ and $n=r=1$. $$\begin{aligned} A&=\overbrace{a\_{n-1}a\_{n-2}\cdots a\_{t+r}\ \underbrace{a\_{t+r-1}\cdots a\_{t+1}a\_t}\_{r\text{ copies of }a\_t}}^{\text{longest non-decreasing}}\ a\_{t-1}\cdots a\_0\\ \mu(A)&=a\_{n-1}a\_{n-2}\cdots a\_{t+r}\\{r\text{$-$}1\text{ copies of }a\_t\\}a\_{t-1}\cdots a\_0\\ \end{aligned}$$

Define integer $\mu(A)$ as shown above, which is $A$ but with one of $a\_{t+r-1},\cdots,a\_{t+1}, a\_t$ removed. For example, $\mu(1214532)=114532$, $\mu(112)=11$, $\mu(40012)=0012$ and $\mu(0012)=001$. Note that the value of $\mu(A)$ does not depend on the number of leading $0$'s in $A$. For example, $\mu(001332)=00132$${}=\mu(1332)=132$.

**Lemma.** $\mu(A)$ is the smallest number that is $A$ with one digit removed.
**Proof.** Easy.

---

Let $G$ be the greedy algorithm. The lemma above says $G(A,k)=\mu^k(A)$.

**Claim.** For all non-negative integer pairs $(A,k)$, $G$ is optimal, i.e., $G$ returns the smallest number.
**Proof.** Let $P(k)$ be the proposition that $G(I,k)$ will return the smallest number for all integer $I$ of more than $k$ digits. The claim is $P(0)$, $P(1)$, $P(2)$, $\cdots$ are true.

Use induction on $k$. The base case, when $k=0$, is trivially true.

Assume $P(k)$, the induction hypothesis, is true. Let $A$ be an integer and $S$ be some $k+1$ digits of $A$ such that $B$, which is $A$ with digits in $S$ removed, is as small as possible. We will prove $G(A,k+1)\le B$, i.e, $P(k+1)$ is true, thus completing the induction.

Let us reuse the classification above of the digits of $A$, i.e., they start with the non-decreasing sequence $a\_{n-1}, a\_{n-2}, \cdots, a\_{t}$ with $a\_{t}\>a\_{t-1}$ and $ a\_{t+r}\<a\_{t+r-1}$.

* $S$ does not contain any digit in that sequence.

This cannot happen, since we can get a number smaller than $B$ by removing $a\_{t}$ and arbitrary $k-1$ digits to the right of $a\_{t-1}$.
* $S$ does contain one of the digits in that sequence, say, $a\_\ell$.

+ $S$ does not contain any one of $a\_{t+r-1}$, $\cdots$, $a\_{t+1}$, and $a\_t$.

    We can modify $S$ by substituting $a\_t$ for $a\_\ell$. The removal of the digits in the modified $S$ will return a number smaller than $B$. So this case cannot happen, either.
    + Otherwise, WLOG, let $a\_\ell$ be one of $a\_{t+r-1}$, $\cdots$, $a\_{t+1}$, and $a\_t$.

    The lemma above tells us that $A$ with $a\_\ell$ removed is $\mu(A)$. Let $S\_-$ be $S$ without $a\_\ell$. So $S\_-$ are some $k$ digits of $\mu(A)$. We have the following diagram, where the arrow reads "become". $\require{AMScd}$ \begin{CD} \mu(A),k@\>\text{greedy algorithm}\>\> G(\mu(A), k)\\ @| \\ \mu(A),k@\>{\text {remove elements in }S\_-}\>\> B\\ \end{CD}

    The induction hypothesis ensures $G(\mu(A), k)\le B$. Since $G(A,k+1)=G(\mu(A), k)$, we are done.

---

**Exercise.** (A couple of minutes or more) Given two positive integers $k\lt n$ and an $n$-digit integer $A\>0$, how can you remove $k$ digits from $A$ such that the resulting integer is the biggest one? Explain the greedy algorithm. Prove it is correct.

The exercise shows that the greedy algorithm is still optimal in the original problem when $A$ is negative.

---
Tags: algorithms, correctness-proof, greedy-algorithms
---


# Question
Title: Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons
I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons.

There are some instructions on this page (see the heading entitled "Decompose into Simple Pieces") however my current implementation is falling short (see img below).

While I'm able to find all the self-intersecting points I'm not able to construct the desired outputs when there are multiple self-intersections on a single segment.

Here is what I'd expect to get

I'm struggling to find any other papers which describe the process or required data structures in any more detail. The blog post references a linked list which could mean a Doubly Connected Edge List although I'm not 100% sure, the other challenge with that is that I don't think there is a suitable js implementation of that data structure.

Any advice on how I might reconstruct the desired output would be appreciated

# Answer
> 3 votes
Here is a thesis on exactly this topic:

> Subramaniam, Lavanya. "Partition of a Non-simple Polygon Into Simple Polygons." Master's thesis, University of South Alabama, 2003. PDF download.

---

<sup> Fig.10f, p.23. </sup>

---

---
Tags: computational-geometry
---


# Question
Title: Basic complexity theory (in Oracle Separation of BQP and PH)
I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that **BQP**$^O\nsubseteq$ **PH**$^O$. Aaronsons paper was helpful, but I still have some questions left.

1. Raz and Tal derive Corollary 1.5 from 1.4 "by the relation between *black-box* separations and *oracle* separations", but aren't those the same thing? I thought the following all mean the same:

* black-box model
    * oracle model
    * relative/relativized problem
    * query complexity

It would make more sense to me if Corollary 1.5 follows from 1.4 by the relation between *promise* problems and *decision* problems in the *black-box* model.
2. I am not sure how to interpret the fact that there is randomness in the problem. I think of a class such as **BPP** as languages solvable by a regular Turing machine with access to a random tape, which can make an error with a constant probability *over its random bits*. However we need to consider the worst case instantiation of the problem (right?). For a language to be in **PH**, there needs to be a **PH**-machine (without access to randomness) that does not fail on any input. Now for any oracle-output coming from one distribution there is a non-zero probability that it was actually generated by the other distribution, so the **PH**-machine will be wrong sometimes. Why is that argument not sufficient to show that the problem is not in **PH** (or any other "zero-error" class for that matter)?
3. What exactly is meant by an **AC**$^0$ circuit with access to an oracle? I've seen this described as "a circuit with access to the oracle's truth table", which I could understand if the oracle solved a decision problem $f: \\{0,1\\}^n \rightarrow \\{0,1\\}$, then the circuit input nodes are $x\_i = f(i)$ for $i \leq 2^n$. However, here the oracle samples from one of two distributions on $\\{\pm 1\\}^{2N}$ and the circuit is defined as $A: \\{\pm 1\\}^{2N} \rightarrow \\{\pm 1\\}$. Does that mean the circuit only gets access to a single query output?

# Answer
> 2 votes
Let me answer your questions one by one.

**Black-box separations versus oracle separations**

Black-box algorithms are given access to a black box. For example, an algorithm might get black box access to a function $f\colon \\{0,1\\}^n \to \\{0,1\\}$. This means that the algorithm can obtain the value of $f(x)$ for any given $x \in \\{0,1\\}^n$, but is not otherwise given any explicit description of $f$.

As an example, consider the following promise black box problem: given a function $f$ which is either the constant $0$ or balanced (that is, half its values are $0$ and half are $1$), determine which of these two cases $f$ belongs to. There is a very simple randomized algorithm which makes a constant number of queries and outputs the correct answer with constant probability; but every deterministic algorithm must make exponentially many queries in the worst case. This is an example of a black-box separation between promise versions of $\mathsf{P}$ and $\mathsf{BPP}$.

Oracle separations also pertain to black-box algorithms, but now we want to *fix* the black box. In order to separate two relativizable complexity classes $A$ and $B$, we need to find a *specific* oracle $O$ such that $A^O \neq B^O$ (or prove that one exists). For every oracle $O$, the classes $A^O$ and $B^O$ consist of languages decided by algorithms with *no* auxiliary input. Rather, these algorithms have access to an $O$-oracle. But in contrast to the situation in the preceding paragraph, here the oracle is not part of the input. Rather, it is fixed.

The standard example is Turing machines with access to an oracle to the halting problem. In contrast to the example given above for black-box algorithms, here the oracle is not an *input* but rather an additional *mechanism* that the machine can make use of.

**On randomness**

A language $L$ is in $\mathsf{BPP}$ if there is a randomized polytime machine $T$ such that:

1. If $x \in L$ then $\Pr\[T(x) = 1\] \geq 2/3$.
2. If $x \notin L$ then $\Pr\[T(x) = 1\] \leq 2/3$.

When considering the black box version of $\mathsf{BPP}$, the definition remains exactly the same. The black box is not randomized; only the algorithm is randomized. As an example, consider the promise problem of determining whether an input black box is the constant zero function or is balanced. This problem can be solved in $\mathsf{BPP}$ by sampling a few points, or in $\mathsf{E}$ by querying the first $2^{n-1}+1$ values of the black box.

Randomization is part of the algorithm, not the decision problem.

**Oracle circuits**

The paper you are reading doesn't actually use these — the oracles are only applied to $\mathsf{BQP}$ and $\mathsf{PH}$. But for completeness sake, let me mention that the most common model uses *oracle gates*, which are gates that provide access to the oracle.

**An advice**

Let me close with an advice. The paper you are trying to read is at the forefront of research. It would be extremely hard to appreciate it without having some background. This paper is probably not a good entry point into complexity theory. I suggest familiarizing yourself with complexity theory first, for example by reading parts of the textbook by Arora and Barak.

---
Tags: complexity-theory, quantum-computing, oracle-machines
---


title: Algorithm Analysis of Insertion Sort

text:
# Question
Title: Algorithm Analysis of Insertion Sort
Why is the recurrence formula for insertion sort is `T(n-1) + n`?

I understand the `T(n-1)` part but the why does the cost for merging results is n or linear. Do we have to merge in insertion sort?

# Answer
Here is a recursive version of insertion sort:

Input: array $A\_1,\ldots,A\_n$

1. If $n = 1$, output $A\_1$. Otherwise, continue.
2. Recursively sort $A\_1,\ldots,A\_{n-1}$ into $B\_1,\ldots,B\_{n-1}$.
3. Insert $A\_n$ into $B$.
4. Output $B$.

If we denote by $T(n)$ the running time for arrays of length $n$, then step 2 takes time $T(n-1)$, whereas step 3 takes time $O(n)$. Combined, we get the recurrence $T(n) = T(n-1) + O(n)$, with base case $T(1) = O(1)$, corresponding to step 1.
> 2 votes

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


title: Probabilistic halting problem

text:
# Question
Title: Probabilistic halting problem
I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing to me:

Suppose we number the probabilistic Turing machines and define the probabilistic halting function $h\_p(x)$ to be 1 if machine $x$ halts on input of $x$ with probability at least 1/2 and 0 if machine $x$ halts on input of $x$ with probability less than 1/2. Show that there is no probabilistic Turing machine which can output $h\_p(x)$ with probability of correctness strictly greater than 1/2 for all $x$.

I'm sure we're supposed to assume that there is a probabilistic Turing machine that does this, and then show that we can solve the deterministic halting problem using this machine, thus obtaining a contradiction. I don't have a clue how to go from this probabilistic Turing machine to a deterministic one, though.

# Answer
Let $A$ be a randomized procedure which outputs $h\_p$ with success probability larger than $1/2$.

Consider the following code, with input $x$:

* Let $y$ be the machine corresponding to machine $x$ running on itself as input.
* If $A(y) = 1$, go into an infinite loop, otherwise halt.

Denote this program by $B$. What happens if we run $B$ on itself? Let us consider two cases. In both cases, let $y$ be the machine corresponding to $B$ running on itself.

Case 1: $B$ halts on $B$ with probability at least $1/2$. In this case, $h\_p(y) = 1$, and so with probability more than $1/2$, $A(y) = 1$. Therefore $B$ goes into an infinite loop with probability more than $1/2$, contradiction.

Case 2: $B$ halts on $B$ with probability smaller than $1/2$. In this case, $h\_p(y) = 0$, and so with probability more than $1/2$, $A(y) = 0$. Therefore $B$ halts with probability more than $1/2$, contradiction.

(This generalizes the usual proof of uncomputability of the halting problem via diagonalization.)
> 3 votes

---
Tags: undecidability, halting-problem, probabilistic-turing-machines
---


# Question
Title: How to find an algorithm's complexity from actual running times
I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of instances, which grow in size as a function of $n$.

Now, I have collected running times from $n = 1$ up to $n = 5000$, which is as far as my computer can go in a reasonable amount of time.

I have plotted my data using Python and I have made some simple regression (exponential, cuadratic, cubic...), but I still can't get to decide which function best fits the algorithm. Obviously, if I try regression with a polynomial of higher degree, I will get a tighter curve, so in case the running time is a polynomial in $n$, I don't know how I could decide which is the one that really fits.

With instances up to $n = 1000$, it seems like the cubic polynomial is the best approximation. However, when I plot the instances up to $n = 5000$, things become less clear (in the second graph I compare the actual running times against the approximations obtained for up to $n =1000$, while the first one compares against the the approximations up to $n = 500$)

(in addition, I feel there is something off with float point calculations, as two of the curves below get really messy)

Any suggestions?

A bit of context: I am working on a particular class of hard Quantified Boolean Formulas (QBF) and I want to test their running times on different available QBF-solvers. These formulas verify a certain interesting property: they have linear size proofs in the QU-resolution proof system. However, QBF-solvers act as block boxes for me, and, altough I can see from data that they do not have the "predicted" linear running times, I would like to know how is the growth in complexity in these particular instances. Particularly, it would be great to give some approximate bound or even confirm that they do not seem to have an exponential growth. Thanks.

# Answer
You can do regression on the whole data to get a better fit.
> -1 votes

---
Tags: time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Karatsuba Multiplication Rule in dividing a Number in two parts
In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example:

```
x= 1234
y= 2456

```

Then a = 12, b = 34, c = 24 , d = 56

What if the digits in each number are not even, or the same? What is the rule in dividing it into two parts?

Example:

```
 x = 12345
 y = 2478

```

or

```
 x = 12456778
 y = 241

```

Please help.

# Answer
The most common approach is to take the longest number, and divide it in half (rounding an odd number of digits arbitrarily). So for

```
x = 12345
y = 2478

```

you would get `a=12`, `b=345`, `c=2`, `d=478`. Since the number of digits in `x` is not even, we are free to choose whether to split into `a=12` and `b=345` or `a=123` and `b=45`; it makes no difference to the running time. For your second example

```
x = 12456778
y = 241

```

you would get `a=1245`, `b=6778`, `c=0`, `d=241`.
> 3 votes

# Answer
I think in this case we should pad with zeros up to an even degree of the largest of the two numbers. Suppose that $x \ge y$ and $2^n \le x \< 2^{n+1}$. Then one should represent $x, y$ as $$x = x\_1\cdot 2^{\lceil \frac{n}{2} \rceil} + x\_2, y = y\_1\cdot 2^{\lceil \frac{n}{2} \rceil} + y\_2$$ and then apply Karatsuba Rule. The total complexity is still $O(n^{\log\_23})$
> 2 votes

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


# Question
Title: Time complexity of rotation array m times using temporary array
I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the space complexity is `O(m)` where m is the number of times the array needs to be rotated. But the time complexity is given as O(n) where n is the size of the array. But I found that the time complexity should be O(n+m)

```
Input arr[] = [1, 2, 3, 4, 5, 6, 7], m = 2, n =7
1) Store d elements in a temp array
   temp[] = [1, 2] // It takes m iterations to copy the array
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7] // n-m iteration for shifting
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2] // m iterations for storing the elements back

```

Here is how I calculated time complexity

```
=> m+(n-m)+m

=> O(n+m)

```

Can anyone help me to figure out what I am doing wrong?

# Answer
$O(n+m)$ and $O(n)$ are the same. $m$ can never be more than $n$, so $n+m\leq 2n =O(n)$.
> 2 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Computational complexity of calculating mean vs median?
Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions).

I am curious which is more computationally intensive to calculate, the mean or the median?

Naively, I would suppose calculating the mean involves summing up the $N$ numbers and then dividing by $N$, hence it has linear $O(N)$ complexity.

Computing the median would need to perform some sort of sorting algorithm, https://en.wikipedia.org/wiki/Sorting\_algorithm, it seems the best algorithm performs at $O(n\log n)$ complexity.

Hence, for general $N$, it is more computationally intensive to calculate median? Is my reasoning correct?

Thanks for any help.

# Answer
You can find the median in linear time using the linear time selection algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest.

The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.
> 10 votes

# Answer
Just quickly saying how can get find the median in linear time: Say you have a million items 0 .. 999,999 then the median is the average of items 499,999 and 500,000.

Run the quicksort algorithm. But after each partitioning, you don't sort both halves, you only sort the half (or two halves) containing elements #499,999 and 500,000.

The average would be O(n) if you just add all the values and divide by n. The problem is you get rounding errors. At the extreme, you could get a result that is less than the minimum or greater than the maximum of all values (especially if all items are equal to the same value x; due to rounding errors it's quite unlikely that your result is exactly x).

A reasonably precise method for large n is this: Add the numbers in pairs. Say $b\_0 = a\_0 + a\_1$, $b\_1 = a\_2 + a\_3$ etc. Then $c\_0 = b\_0 + b\_1$, $c\_1 = b\_2 + b\_3$ and so on, until only one number is left. Since the results are smaller than if you added sequentially, the errors are smaller. So you get a better approximation for the average.

That approximation is still not good. If the average you calculated is A, you then calculate the average of $a\_i - A$. This is more precise since the values involved are smaller (the sum should in theory be 0 but isn't due to rounding errors), so you just add that average to A to get a better result.

It's still linear time, but it's a bit slower than just adding all the numbers.
> 2 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Is the infinite program Turing-recognizable/decidable?
Imagine we have a program which does an infinite loop: `while(true){loop}`

We run the program on a linux machine(assume the compilation is ok), then this linux machine becomes an universal turing machine which run the program.

Questions are :

1.Does the linux machine recognize the infinite program? Why?

2.Does the linux machine decide the infinite program? Why?

The definition of Recognizable and Decidable(https://math.stackexchange.com/a/25808/677513):

> A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.
>
> A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.

According to the definition of 'recognizable', the linux machine does not recognize the loop program, so the linux machine loop forever on the program. But this is counter-intuitive.

# Answer
> 2 votes
The question doesn't make sense. Recognizability and decidability don't apply to a program. You're confusing several different concepts: languages, strings, programs.

A Turing machine operates on a *string*. A string is a finite sequence of *symbols*. A symbol is a member of a finite alphabet, for example the alphabet of 8-bit bytes (binary programs are written in this alphabet), or the alphabet of ASCII characters (most programming language source code is written in this alphabet).

A Turing machine recognizes a *language*. A language is a set of strings. This set can be finite or infinite. Some example languages are: the set of every string; the empty set; the singleton set containing only one particular string; the set of strings of length 3; the set of ASCII strings where the characters `(` and `)` are balanced; etc.

> Imagine we have a program which does an infinite loop: `while(true){loop}`

Ok. This is not an “infinite program”. `while(true){loop}` is a 17-character ASCII string, which presumably has a meaning in some fictional programming language. The meaning of this string is a program that runs forever without consuming any input or emitting any output. So it's a *non-terminating* program.

If you compile it for a computer, you'll get a new string which is a binary executable. This is still a string, i.e. a finite sequence of symbols, this time on the alphabet of 8-bit bytes (assuming an 8-bit computer).

> We run the program on a linux machine(assume the compilation is ok), then this linux machine becomes an universal turing machine which run the program.

Ok. You can consider the computer as a Turing machine that takes binary programs as inputs and whose behavior is to run the program. On *this* particular program, the Turing machine does not halt. The Turing machine does not accept or reject this particular program.

The Turing machine is not fully defined because you haven't defined which inputs it accepts. Here are a few examples of complete definitions of Turing machines that fit this mold. (I haven't fully formalized these definitions, but they're complete in the sense that I'm fully describing what the machine does. Note that they're still incomplete in the sense that each of them could be *implemented* in many different ways.) All of these machines take a program as input and run it without passing it any input (and don't halt if the program doesn't), then do something else.

* Accept the program. This machine accepts all inputs that encode terminating programs, and does not halt on inputs that represent non-terminating programs.
* Accept if the program emitted any output, and reject otherwise.
* Accept if the program emitted a prefix of the decimal representation of $\pi$, and reject otherwise. Note that since the program halted, it can only print a finite sequence of digits. If the input is program that keeps printing digits forever, the Turing machine doesn't halt.
* Accept if the program ran for an even number of clock cycles, and reject if the program ran for an odd number of clock cycles.
* After running the program, loop forever. This machine doesn't halt on any input.

Each of these machines recognizes a different language: the language of terminating programs; the language of programs terminate and don't produce any input; the language of terminating programs that print a finite prefix of the decimal representation of $\pi$; the language of programs that run for an even number of clock cycles; the empty language. None of these machines decide any language, since they don't halt on every input.

Where things get really interesting is when you consider Turing machines that take (an encoding of) a program as input, and do things other than run it. That's the only way of getting interesting results about non-terminating programs. Here are a few possible behaviors for a Turing machine that takes a program as input:

* Run the program for 1,000,000,000 clock cycles at most, and accept it iff it terminates before the timeout. This machine decides programs that terminate within a certain time.
* Run the program for 1,000,000,000 clock cycles at most, and accept it iff it doesn't print any output. This machine decides programs with empty output that terminate within a certain time.
* Accept the program iff its length is even. This machine decides the language of even-length programs.
* Search for a termination or non-termination proof for the program. Accept the program if a termination proof is found, reject it if a non-termination proof is found. Don't halt as long as the search hasn't found anything — since there are infinitely many potential proofs, there's no guarantee that the search will ever terminate. Such a machine recognizes the language that is composed of programs that terminate. The unsolvability of the halting problem states that such a machine cannot halt on every input: the language of terminating programs is not Turing-decidable.

---
Tags: turing-machines, computability, programming-languages, turing-completeness
---


# Question
Title: Converting a Recurrence Relation to its Closed Form
I have a recurrence relation of the form given below (taken from Analysis of Algorithms - An Active Learning Approach by Jeffrey J. McConnell):

$T(n) = 2T(n - 2) - 15 $

$T(2) = T(1) = 40 $

I am asked to find a closed-form for the recurrence relation i.e. to remove the recursive nature of the equations.

**Working:** My professor said it would be easier if you could see the patterns taking form if you expand the equations up to a few steps. So,

$T(n) = 2T(n - 2) - 15 $

$= 2(2T(n - 4) - 15) - 15$

$= 4T(n - 4) - 2\times 15 - 15 $

$ = 4(2T(n - 6) - 15) - 2\times15 - 15$

$ = 8T(n - 6) - 4 \times 15 - 2\times15 - 15$

I observe that the coefficient of $T$ in each step is a power of 2. The size of the problem during each recursive call decreases by 2. Also, there is a -15 term multiplied by the next power of 2.

But I am stuck here and do not know how to proceed further i.e. to obtain a closed-form. The book says to consider cases when $n$ is odd and even. But I do not get it at all. Any help would be appreciated.

Note: The material hasn't covered advanced topics like solving recurrence relations yet.

# Answer
> 0 votes
It might be helpful if N is assigned a range of values from 1 to say 7 and evaluated till the recursion end is reached. also summing together terms with 15 multiples separately and 40 multiple separately, because they are the building blocks from the base case and recursion.

T(1) = 40.

T(2) = 40.

```
....

```

T(6) = 2 * ( 2 * 40 - 15 ) - 15 = 4 * 40 - 3 * 15

T(7) = 2 * ( 2 * ( 2 * 40 - 15 ) -15 ) - 15 = 8 * 40 - 7 * 15

i think this can help to find the closed form. But i am not an expert in this area.

# Answer
> 0 votes
Hint: Consider $Q(N) = T(N) - 15$. Derive a recurrence relation for $Q(N)$.

---
Tags: recurrence-relation
---


# Question
Title: Is there a unit of measurement that can express code execution speed in absolute terms?
I've always seen code execution speed measured either in units of time (e.g. *t* milliseconds), or using asymptotic analysis (e.g. O(*n* log *n*)). Execution speed will vary depending on hardware performance, and asymptotic analysis can tell us how code will perform relative to the size of the input, but they're not absolute terms.

For space performance, we have asymptotic analysis, but we can also measure performance in bytes, which allows us to express (and predict) space performance in both relative and absolute terms. e.g. algorithm X's space complexity is O(*n*) or n * 32 bytes of memory for implementation Y in language Z.

For example we can look at this code:

```
for i in n:
    pass

```

And if we know this will be executed using a 64-bit build of CPython, we can say this for loop will take up 72 + n * 8 bytes for the integer array and 8 bytes for each reference (independent of context/overhead).

My question is: Is there a unit of measurement we can use to express a piece of code's execution speed (or CPU usage) in absolute terms, similar to how we can with bytes for memory?

# Answer
I think the comparison is a bit clouded actually. Some unspoken concerns are that you can't claim python will compile to precisely 72+8n bytes by reading the high-level code. There's a virtual machine with untold optimization and overhead heavily dependent on memory layouts, CPUs, your OS, even your version of Python. Memory blocks might be allocated in fixed increments: 1KB page even if all you need is 100 bytes. Then within your fancy hyperthreaded CPU it might decide to pack bytes together, or rip them apart to run someone else's code along side yours. So how many physical bytes you use in the program can be far more than you expect you need. I think those issues seem to hit at the same ambiguity you considered with time.

In the literature on complexity these concerns are usually given with footnotes. That is we accept that asymptotics are necessary for modeling time and space because we cannot quantify the really fine details, and if we could, the results would be unusable.

So I think the answer to your question is no, there is no such unit, but that there isn't one for space either. It is important to remember that the role of modeling an algorithm is to know its behavior in broad strokes. If you model it so precisely that you can predict it to the fine detail chances are your model is as complex to evaluate as the thing it is modeling. We need models that simplify so we can get at identifying the big bottlenecks and not get stuck in the weeds. (Probably that is a theorem whose proof is basically the same as the proof that there exist Kolmogorov random sequences -- but I only speculate on that point.)

---

As a side remark, there are time-space complexities which measure the two together and these can come closer to modeling resource use in real life. These can be quantified with units of "power" (Watts) or in economic models as "cost" ($$ spent to run).
> 1 votes

# Answer
Yes, and AFAIR you can find it even in classic Knuth book. It's the number of operations performed, usually split by operation type. For example, number-crunching algorithms are measured in terms of FP adds and multiplications performed. Sorting algorithms are measured in terms of comparisons and swaps, and so on.
> 1 votes

# Answer
**Number of CPU cycles** When evaluating the speed of (cryptographic) procedures its common to refer to the absolute number of cycles of the CPU E.g. BIKE Cipher Specification (see page 30).

In terms of complexity all procedures are supposed to be polynomial in the input length. Additionally, the input lengths vary a lot, so any asymptotic notion would be quite imprecise. In terms of speed in *seconds*; this depends a lot on the underlying architecture. Since you want these applications to run on various systems, also not a good measurement. Thus the number of CPU cycles seems a good option. However, I do not know if this unit of measurement is used in other areas.
> 0 votes

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


# Question
Title: A push-down automaton with two stacks which is equivalent to a linear-bounded automaton
It is known that a PDA with two stacks is equivalent to a TM.

On the other hand a PDA with one stack is capable to recognise only context-free languages.

Hence there is a kind of a gap between the class of PDA with one stack and the class of PDA with two stacks which should be capable to recognise only **context-sensitive** languages.

I feel like it should be already an examined question, but I couldn't find an answer: what restrictions should we apply to a PDA with two stacks in order to make it equivalent to a Linear-bounded automaton?

# Answer
A 2-stack PDA with a linear bound on both stacks is equivalent to a LBA.

What happens if *only one of the two stacks is linear bounded* and the other is unlimited? I optimistically wrote a quick comment that the LBA equivalence holds also in this case ... but ...

It's easy to see/prove that a 2-stack PDA with a linear bound only on one stack can simulate a LBA with one stack; and *it is an open problem* if a LBA with one stack is more powerful than a standard LBA.

For further details see T.Klimpel's answer to the question Is a LBA with stack more powerful than a LBA without?

This is a sketch of the proof that a *PDA + 1 linear bounded stack + 1 unbounded stack (PDA+1B+1U) can simulate a LBA + 1 unbounded stack (LBA+1U)*

Given a LBA+1U build a PDA+1B+1U in which the bounded stack is used to store the leftmost tape portion (reversed) and the unbounded stack stores the rightmost portion plus the unbounded content of the LBA stack.

A particular configuration of the LBA+1U:

```
    # x a y # stack: [b w   ]
        ^head

```

(where $\\#$ are the endmarkers of the linear space, the head is on symbol $a$, the content of the tape is $xay$, the stack contains $bw$, $b$ is the top)

is represented into the PDA in this way:

```
    stack 1: [ > a x^R #  ]  (bounded stack)
    stack 2: [ y # b w       ]  (unbounded stack)

```

(where $\>$ is a marker for the head position, $x^R$ is the reverso of $x$.

Suppose the LBA pops the b, change $a$ into $c$, moves left and pushes $d$ into the unbounded stack reaching this configuration:

```
    # x c y # stack: [ d w   ]
      ^head

```

The PDA can simulate that behavior in this way: it checks and pops the content of the unbounded stack using stack 1 as temporary storage:

```
    stack 1: [# y^R >a x^R # ]  (bounded stack)
    stack 2: [b w    ]  (unbounded stack)

```

Then it goes back to the head marker (storing "b" in its internal state)

```
    stack 1: [>a x^R # ]  (bounded stack)
    stack 2: [y # w    ]  (unbounded stack)

```

Then it moves left (and push c in the second stack simulating the a-\>c write operation):

```
    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # w    ]  (unbounded stack)

```

"goes" to the stack marker and push d:

```
    stack 1: [# y^R c >x^R # ]  (bounded stack)
    stack 2: [d w    ]  (unbounded stack)

```

then "goes back" to the head position:

```
    stack 1: [>x^R # ]  (bounded stack)
    stack 2: [c y # d w    ]  (unbounded stack)

```

**Addendum**

The proof that a PDA+2bounded stacks (PDA+2B) can simulate a LBA is similar.

For the other direction (a LBA can simulate a PDA+2B) the idea is to use two symbols to mark the top of both stacks $b\_1, b\_2$, and use the linear space to store the two bounded stacks "overlapped" (just use an expanded $\Sigma \times \Gamma \times \Gamma \times \\{ b, b\_1, b\_2 \\}$ alphabet).

By further expanding the alphabet you can store in the same (linear) space the original input, the head position of the PDA+2B, and an enumeration of the nodeterministic choices (there are at most $c|x|$ of them, one for each symbol of the initial input. Where $c$ depends only on the size of the transition table).

Then you can scan all the nondeterministic choices and simulate the behaviour of the PDA+2B using the top stack markers.

Note that if you allow epsilon transitions you must run two enumerations in parallel in order to check if the PDA+2B enters the same configuration due to $\epsilon$ transitions (i.e. detect if it loops forever)
> 6 votes

---
Tags: turing-machines, context-free, pushdown-automata, context-sensitive, linear-bounded-automata
---


# Question
Title: Linear codes : why has the parity check matrix dimensions $(n-k)*k$?
I am studying Quantum error correction that is based on some aspects on classical error correction.

I am reading some very basics around linear error correcting codes.

I consider a linear code \[n,k\]: thus it encodes k bits of information into n bits.

**My question: I don't understand why the parity check matrix has $n-k$ lines.**

---

What I understand from the topic.

If I call $x$ the column vector of the information bits I want to encode in the n-bits, I define $G$ the generator matrix such that:

$$ y = G x $$

Where $y$ is my encoded information.

The $H$ matrix is built such that its kernel is the code space. Thus, its kernel must be composed of the column vectors of $G$ as the code space is spanned by the column vectors of $G$.

All this means that the line vectors of $H$ must be orthogonal to the column vectors of $G$.

But why do we have to take $n-k$ lines in $H$, why not $n$ lines, or $2$ lines ? I guess it is a way to ensure us that the Kernel of $H$ is **exactly** the code space but I don't understand why this number of lines ensure this.

# Answer
You can have as many rows in $H$ as you like, but they will be linearly dependent after you reach $n-k$ independent rows. You can apply the rank-nullity theorem. If you like, think of the rank of $H$ as the number of pivots you get, when you row reduce. It is the same number you get when you column reduce. Now for $H$ is a $s\times n$-matrix with kernel of dimension $k$. That means by the rank-nullity theorem that $\mathrm{rank}~H+k=n$. So $\mathrm{rank}~H=n-k$ but rank is just the number of pivots (either from row or column reducing). Said another way, $s\geq n-k$ and if $s\>n-k$ then after row reducing you get just $n-k$ nonzero rows. So the most compact $H$ is $(n-k)\times k$.

Usually one thinks of generator and parity check matrices as having been row/column reduced with 0 rows serving no purpose so omitted. That forces your dimensions. But yes in principal you could repeat yourself, it just wouldn't help or be what anyone expects. But no, you can't choose just 2 that will make for a larger kernel in general.
> 2 votes

# Answer
If you have `k` input bits and `n` output bits, you need to compute only `n-k` extra bits, so the matrix should be `k * (n-k)`. You multiply the input vector by the matrix and get the extra bits vector.
> 0 votes

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


# Question
Title: Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem
We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:

* Let $L\in NPSPACE$.
* Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that accepts $L$.
* For every input word $w$, the number of vertices in the configuration graph of $M$ is exponential in $|w|$.
* Nevertheless, using the algorithm from Savitch's proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $|w|$.

My problem is the memory required to store the graph. How can we store the graph using space polynomial in $|w|$?

# Answer
> -2 votes
I had the same thoughts when i did Complexity course myself. Its a very simple answer - the graph is stored on the tape and even though it is part of the input, its not calculated as part of the space complexity of the machine. This is by definition of space complexity analysis.

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


# Question
Title: Polynomials - using Newton's method, or not?
I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed.

I can use general Newton's method for all degrees, or only for 5th+, and for 2,3 and 4 I can use algebraic formulas that solve quadratic, cubic and quartic equations. Since algebraic formulas need to use sqrt, acos and similar functions - does it make sense at all to use algebraic formulas - or is it better to use Newton's method for all degrees? I guess the latter will actually be faster?

This is my equation:

$$\frac{1}{(b\_1x + 1)} + \frac{1}{(b\_2x + 1)} + ... + \frac{1}{(b\_nx + 1)} -k = 0$$

and constraints:

$$1 \leq k\<n \\ b\_n\>0 $$

e.g. for $n=3$:

$$b\_1 b\_2 b\_3 (-k)x^3 +\left(b\_1 b\_2+b\_3 b\_2+b\_1 b\_3- b\_1 b\_2 k-b\_3 b\_2 k-b\_1 b\_3 k\right)x^2 + \left(2 b\_1+2 b\_2+2 b\_3-b\_1 k-b\_2 k-b\_3 k\right)x + 3-k =0$$

which can be written as

$$\sum\_{i=0}^n(n-i-k)\binom{\\{b\_1,...,b\_n\\}}{i}x^i=0.$$

# Answer
> 1 votes
The sum goes to infinity at x = -1 / $b\_i$. Between $b\_i$ and $b\_{I+1}$ it is continuous. So each of these intervals contains a point wher the sum of fractions equals k. Go from there.

---
Tags: complexity-theory, floating-point, polynomials
---


# Question
Title: How can the union of two 'context-free but not regular' languages be regular?
I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:

> If $L\_1$ and $L\_2$ are 'context-free but not regular' languages, defined over the same alphabet $Σ$ then, the union $L\_1∪L\_2$ can be a regular language.

I can't find an example to prove that this statement is true because by definition the context-free languages are closed under union operation.

Could someone please provide an example?

# Answer
Let $L$ be a context-free but not regular language over $\\{0,1\\}$ such that its complement language $\overline L$ is also context-free. Then $\overline L$ is not regular and $L\cup\overline L=\Sigma^\*$ is regular.

In particular, let $L=\\{a^nb^n\mid n\in\Bbb N\\}$.

---

The previous example requires you to verify that both $L$ and $\overline L$ are context-free. Here is an example with less burden.

Let $\Sigma=\\{a,b,c,d\\}$. Let $F\_1$ be a context-free but not regular language over $\\{a,b\\}$. Let $F\_2$ be a context-free but not regular language over $\\{c,d\\}$. Then both $F\_1\cup\\{c,d\\}^\*$ and $\\{a,b\\}^\*\cup F\_2$ are context-free but not regular. The union of them, $\\{a,b\\}^\*\cup\\{c,d\\}^\*$ is regular.

In particular, Let $F\_1=\\{a^nb^n\mid n\in\Bbb N\\}$ and $F\_2=\\{c^nd^n\mid n\in\Bbb N\\}$.

---

**Exercise 1.** If $R$ is a regular language and $F$ is context-free but not regular such that $R\setminus F$ is context-free, then $F\cup (R\setminus F)$ is a desired example. Show that we can take $R=a^\*b^\*$ and $F=\\{a^nb^n\mid n\in\Bbb N\\}$.

**Exercise 2.** If $L\_1$ and $L\_2$ are 'context-sensitive but not context-free' languages, defined over the same alphabet $Σ$ then, the union $L\_1\cup L\_2$ can be a context-free language. In fact, the union $L\_1\cup L\_2$ can be a regular language as well.
> 3 votes

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


# Question
Title: Confusion about assignment axiom in Hoare logic
I wanted to know if we are given the f.f.g. Hoare triple:

{x = 43}x := x + 1{x = 44}

How do we show that this is a valid Hoare triple?

My attempt was:

Using the assignment axiom: {x + 1 = 43} x := x + 1 {x = 44}

But this doesn'the make sense. I also want to know what went wrong in my attempt?

# Answer
The assignment axiom in standard Hoare logic says:

|- {P\[e/x\]}x:=e{P}

If you choose P\[e/x\] to be x+1=44 (that is e is x+1) you get:

|- {x+1=44} x:=x+1 {x=44}

By the consequence rule, since: |= x=43 --\> x+1=44, and |= x+1=44 --\> x+1=44, and
|- {x+1=44} x:=x+1 {x=44}

you know that |- {x=43} x:=x+1 {x=44} .

By soundness: |={x=43} x:=x+1 {x=44}
> 2 votes

---
Tags: logic, correctness-proof, hoare-logic
---


# Question
Title: Representing partialled/curried functions in postfix notation?
I'm working on a small query language in JSON. A query consists of a JSON array of JSON elements, such as strings, numbers, booleans, etc. Strings starting with a `'$'` or `'@'` represent postfix unary or binary operators, respectively.

I want to include some functional aspects to my query language (e.g. a `map` operator that takes a function and an array, and produces a new array). However, I'm having trouble representing these "functions-as-arguments" in postfix notation! As an example, let's say I want to add a fixed number to each element of an array. I would instinctively want to write something like this:

```
[[0, 2, 4, 6, 8], 1, "@add", "@map"]

```

However, this would be interpreted as "perform an `add` operation on `1` and `[0, 2, 4, 6, 8]`, and then call `map`". This would produce an error in my query! Instead, I want to interpret the query as "perform a `map` operation using `add(1)` on `[0, 2, 4, 6, 8]`". Is it possible to achieve this, given the use of postfix notation?

# Answer
> 6 votes
The distinguishing quality of the postfix notation, a.k.a. reverse polish notation is that for its usual left-to-right evaluation strategy, just before an operator is feed from the notation, all of its operands (a.k.a as parameters or arguments) are on the top of the stack right next to each other in the expected order. Then the operator are applied to its operands immediately. The postfix notation thus has the following distinct advantages.

* No operator precedence or associativity rules are needed to evaluate the notation.
* Formulas can be expressed with the notation without parentheses.
* The memory needed to evaluate the notation is smaller.
* It is very easy to code the evaluation of the notation.

---

Here is one simple solution.

Instead of `[[0, 2, 4, 6, 8], 1, "@add", "@map"]`, we will use

```
[[0, 2, 4, 6, 8], [1, "@add"], "@map"]

```

Here is how it will be processed. `[0, 2, 4, 6, 8]` and `[1, "@add]` are pushed onto the stack. When the operator "@map" is encountered, we will pop off `[1, "@add"]`, treating it as a function object. Then with the array `[0, 2, 4, 6, 8]` popped off the stack, we will apply the function to the array, leaving `[1, 3, 5, 7, 9]` on the top of the stack.

We can simplify further.

It is quite likely that an array can be recognized conveniently and efficiently as a function object at the time when it is read as the next element of the input. For example, we should be able to detect that whether an element is an array, and if it is, check whether the last element of that array is a binary operator or not. If it is, then the array represents a function object. Otherwise, the array consists of pure data. We can then use

```
[[0, 2, 4, 6, 8], [1, "@add"]]

```

so that we can do away with the entry "@map". Semantically, we are recognizing `[1, "@add"]` as a unary operator on an array without the presence of "@map". Upon applying `[1, "@add"]` to the array `[0, 2, 4, 6, 8]`, we will push the result `[1,3,5,7,9]` to the stack. Similarly, upon processing the following JSON input,

```
[[0, 2, 4, 6, 8], [1, "@add"], [2, "@multiply"]],

```

we will leave `[2, 6, 10, 14, 18]` on the top of the stack.

---

The solution above upholds that distinguishing quality of the postfix notation. It could be extended to function objects of multiple arguments and higher order naturally and unambiguously. It can be read easily—an array of two elements whose last element is a binary operator like `"@add"` is a function object.

However, this solution is only one minor technique/hack to extend the primitive postfix notation. It might be helpful to study literature on postfix notation and stack-based languages for more complete and systemic usage of postfix notation. For example, check the syntax of Forth language, where new functions/words can be defined.

# Answer
> 2 votes
I think that a “function”, meaning “a thing which applies *itself* to its arguments” and a “function”, meaning a thing which *something else* (eg. `map`) takes and applies to things” have to be two completely different things.

How about making `@add` by itself do nothing, other than pushing itself on the stack, and then having an operator called something like `apply-once` which takes the thing at the top of the stack (in this case `@add`) and applies it to the next two stack values below?

Thus every function is a function-as-argument, and there is no ambiguity.

---
Tags: functional-programming
---


# Question
Title: Recover boolean vector from dot products
**Question:**

I want to determine a boolean vector $b \in \\{0,1\\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product of $b$ with a real-valued vector $v \in \mathbb{R}^n$ of my choosing. I.e., access to $b$ is available through evaluation of the map $$v \mapsto b^T v.$$ How can I recover all of the entries of $b$ using as few of these dot products as possible? (maybe even just 1 dot product?)

Below I detail a couple ideas I had which might work in theory, but which don't work in practice (I think). For concreteness, one may assume that $n \approx 1 \text{ million}$, and arithmetic is done in double precision floating point format. This question arose as a subproblem in a machine learning application.

---

**Idea 1:**

One idea I had is to use a vector with fast growing entries. Say, for example, $n=9$. Then we could use the vector $$v=\begin{bmatrix}1 & 10 & 100 & 1000 & \dots\end{bmatrix}^T.$$ One could then read off $b$ as the digits of $b^T v$. The problem with this solution is that the numbers grow so fast, that in finite precision computer arithmetic it will not work for large $n$.

---

**Idea 2:**

Another idea I had was to use a vector with entries that are algebraically independent. Then determining $b$ from $b^Tv$ is a subset sum problem.

For example, if $n=3$ and $$v = \begin{bmatrix}\pi & e & 1\end{bmatrix}^T,$$ then $b^T v$ will take on one of a finite number of possibilities, $$b^T v \in \\{\pi,~e,~1,~\pi+e,~\pi+1,~e+1,~\pi+e+1\\}.$$ We can determine which of these is the case, thereby determining $b$.

But this seems quite combinatorial, and therefore unfeasible for large $n$.

# Answer
Here is an variant of the idea 1 in the question, where a factor of 2 is used to replace the original factor of 9.

1. Let $v=\[2^0, 2^1, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots\]^T$. Obtain $b^Tv$, which will determine the first 64 entries of $b$.
2. Let $v=\[0, 0, 0, \cdots, (64 \text { zeros}), 1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots\]^T$. Obtain $b^Tv$, which will determine the next 64 entries of $b$.
3. Let $v=\[0, 0, 0, \cdots, (128 \text { zeros}), 1, 2, 2^2, 2^3, \cdots, 2^{62}, 2^{63}, 0, 0, 0, \cdots\]^T$. Obtain $b^Tv$, which will determine the next 128 entries of $b$.
4. And so on, until we have determined all entries of $b$. There may be less than 64 positive numbers in $v$ in the last round.

The above scheme is the best possible if the number of effective bits in $b^Tv$ is 64 and we have no prior knowledge about $v$ except the number of its entries. This can be seen easily from information theory, as each query against the black box can provide at most 64 bits of information.
> 1 votes

---
Tags: machine-learning, combinatorics, linear-algebra, subset-sum
---


# Question
Title: Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?
Determining whether or not an array has duplicate entries has two straightforward solutions:

* Build a hashset of entries, then search for elements in this hashset. This takes $\mathcal O(n)$ time and $\mathcal O(n)$ extra space.
* Sort the array, then search for consecutive elements that are the same. This takes $\mathcal O(n \log n)$ time and $\mathcal O(1)$ extra space.

Is there an algorithm that can solve this problem with the best of both approaches, using only $\mathcal O(n)$ time and $\mathcal O(1)$ extra space?

Question Finding duplicate in immutable array in linear time and constant space is similar, but the solution to that question only works when the values come from the set $\\{1, ..., n\\}$; my values are large integers. Also unlike that question, I allow the input array to be modified and used as a workspace.

One strategy might be to attempt to turn the array into a kind of hashtable. However, this seems like it won't work because of the lack of empty space (which makes both moving objects into place hard, as well as getting $\mathcal O(1)$ queries.).

However, I suspect that this cannot actually be done, but I'm not sure how to go about proving it.

# Answer
Suppose that your elements come from a domain of size $n^2$. Any algorithm using time $T$ and space $S$ corresponds to a branching program having depth $T$ and containing at most $T \cdot 2^S$ nodes. Theorem 6.13 of Time-space tradeoff lower bounds for randomized computation of decision problems shows that $$ T = \Omega\left(n \sqrt{\log \tfrac{n}{S + \log T}/\log\log \tfrac{n}{S + \log T}}\right). $$ In particular, if $S$ is $O(\log n)$ (which corresponds to your $O(1)$ extra space, *assuming you cannot modify the input*) then $T = \Omega(n\sqrt{\log n/\log\log n})$.
> 2 votes

---
Tags: algorithms, sorting, arrays
---


# Question
Title: sequential consistency is not composable
I am studying for my exam in Distributed Systems course. And i have one question that i do not really understand. This is the question:

```
Is sequential consistency compositional? if yes explain why, if no give an example.

```

Now this is the only two slides that we have that explains why it is not composable.

And i am having trouble understanding why just from that example. I tried searching on the web for a better explanation but i could not find it. If you have a good example that you can describe and explain or if you have a good link or both please do provide it.

# Answer
> 1 votes
Composable means we can check for each object separately and exactly if the property applies to all of them separately then it applies to the whole of them at once.

To show that sequential consistency is not composable we can use an example where the ordering implied by the projections on one object contradicts the ordering implied by the projection on an other object.

Consider a history

```
A p.enq(x)
B q.enq(y)
A p:void
A q.enq(x)
B q:void
B p.enq(y)
A q:void
A p.deq()
B p:void
B q.deq()
A p:y
B q:x

```

when simply written down as code. Or visualized:

```
A: ---*1: p.enq(x)*---*3: q.enq(x)*---*5: p.deq()=y*---
B: ------*2: q.enq(y)*---*4: p.enq(y)*---*6: q.deq()=x*

```

where the operations start and end at the * and are arbitrarily numbered. Note that this looks like time axes, but that's not how it's necessarily executed. Now when you look at the object p, there must be an order 4-1-5 and for q it's 3-2-6. If the history is sequentially consistent, we also need order 1-3-5 and 2-4-6. But this is not possible, all possible interleavings of 4-1-5 and 3-2-6 contradict either of 1-3-5 or 2-4-6.

(example taken from private slides of a lecture I attended)

---
Tags: distributed-systems
---


# Question
Title: Algorithm for placing circles of Diameter d around the edge of another circle with diameter D
Hi i'm struggling with what i think may be simple maths. I need to place circles of a small size around the edge of larger circle.. is there an algorithm to calculate the angle for each small circle from the x-axis, counter clockwise? then using this angle i can find the Cartesian coordinates (x,y) of the enter of each circle.

# Answer
> 0 votes
Circles centers form isosceles triangle with base of length $2r$ and arms of length $R+r$, so $ \tan (\frac{\beta}{2}) = \frac { r}{ r+R} $ hance $\beta = 2\arctan(\frac{r}{r+R}) $

---
Tags: algorithms, graphs
---


title: Routing algorithm for train network

text:
# Question
Title: Routing algorithm for train network
I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges represent the time taken to travel from one station to another.

For any particular vertex, there might be multiple edges going from that vertex to another (as there could be, for example, a scheduled service that departs from A to B hourly each day - meaning 24 journies in a day and 24 edges between the two vertices for this one journey).

In terms of my analysis, I want to be able to find the shortest path from all stations to all other stations. I can then use algorithms such as BetweennessCentrality on the resultant data to find the most "important" vertices. This type of analysis obviously lends itself to using Dijkstra’s algorithm to find the shortest paths.

However, using Dijkstra’s algorithm will mean that real-life constraints are ignored. For example, Dijkstra’s algorithm won’t take into consideration you can’t set off from station A at 10:00, arrive at B at 10:30 and then take a train from B to C at 8:00 (you are not a time traveller!).

Dijkstra's algorithm also won't take into account time spent waiting in a station for a train to arrive in a situation where a passenger would have to change trains.

I have looked into modifying Dijkstra's algorithm to take these factors into account but as these factors change on a case by case basis you are unable to apply them to the network as a whole.

The ConnectionScanAlgorithm does take real-life constraints into account and scans through a network’s nodes and edges with a given start and end node in mind (I believe this is how train ticket websites find a quickest route).

However, since I need the routes from all stations to all other stations, to make use of the ConnectionScanAlgorithm I have to pass through every combination of station pairings (for me, this is some 36 million combinations) which is far too time expensive.

Are there any algorithms out there which are applicable to this problem?

If not, what is the best way to go about forming a solution?

# Answer
> 3 votes
Here is a list of algorithms that might help you:

You might also wanna take a look at OpenTripPlanner's algorithms **bibliography**

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


# Question
Title: How many combinations will be generated if below conditions are put?
I need a generalized formula for a set having size(s) having below restrictions,

for ex. X = 2,7,11,17,26

I want only the first combination 2+7 & ignore all of the combinations that start from 2+? (2-num combinations only) same for 3-num consider 2+7+11 & ignore all 2+7+?

Formula should be applicable for any set X without size restriction.

# Answer
$2^{n-1}-1$

Hint: 1) if you are summing with $k$ numbers $x\_1,x\_2,.., x\_k$ note that once you choose upto $k-1$, last selection is forced on you as the next ascending number to $x\_{k-1}$. 2) You are allowed to choose first $k-1$ numbers from n-1 numbers
> 1 votes

# Answer
First, let's count the number of 2-combinations. You already mentioned one combination: $(2,7)$, and then there are ${4 \choose 2}$ combinations for the remaining set $\\{7, 11, 17, 26\\}$:

$$S\_2 = 1 + {4 \choose 2}$$

With 3-combinations you said you should include $(2, 7, 11)$. Then, there are ${4 \choose 3}$ combinations for choosing triplets from $\\{7, 11, 17, 26\\}$ and ${4 \choose 3}$ combinations for choosing triplets from $\\{2, 11, 17, 26\\}$.

But with the last two numbers, we have counted some stuff twice. Concretely, we need to subtract the number of 3-combinations made from $\\{11, 17, 26\\}$, which is ${3 \choose 3} = 1$.

$$S\_3 = 1 + {4 \choose 3} + {4 \choose 3} - 1 = 2 {4 \choose 3}$$

---

In the end, you have $$S = 1 + {4 \choose 2} + 2 {4 \choose 3} = 1 + 6 + 8 = 15$$ combinations.
> 0 votes

---
Tags: algorithms, complexity-theory, polynomial-time, mathematical-programming
---


title: One-way Trapdoor Function

text:
# Question
Title: One-way Trapdoor Function
Do the functions of the collatz conjecture and their inverses model a Trapdoor Function?

If given a, b, a^-1, b^-1 and your choice of f(x), is it “hard in the average case” to find some secret x?

I propose that the probability: Pr\[f(F(f(x)))=f(x)\] \< n^-c =Pr\[(2^-n)^2\] \< (n^-(n-1)) Simplifies to: 1 \< (log(2)) * ((log(n))^-1) * (e^(n+1))

Looking at the picture from Wikipedia that others are referencing. Let D be the domain of all natural numbers that I can choose x from. Let R be the domain of all natural numbers that you can choose f(x) from. The arrow marked “easy” is the promise that I am choosing a natural number that can be calculated by applying functions A and B to 1.(c(x) exists) It is hard on average for you to calculate how to apply given functions A,B A^-1 and B^-1 to f(x) to return x.(Sometimes this time is less than the verification process) However, I can quickly apply A^-1 and B^-1 to x until 1 is returned, retain and reverse the order the operations applied and pass you this information (t) making finding x trivial by finding the shortest path to collision.

# Answer
In order to break a one-way function, it suffices to be able to find a single preimage. Given $x$, $f(2x) = x$, so finding a preimage of an *arbitrary* input is easy. Hence it's not a one-way function at all.
> 5 votes

# Answer
It looks like you were intuiting too fast.

---

Let $f\_0(x)=3x+1$ and $f\_1(x)=x/2$. Their inverse functions are $g\_0(x)=(x-1)/3$ and $g\_1(x)=2x$, respectively. The operations in Collatz conjecture is to perform $f$ repeatedly or, in other words, perform $f\_1$ as long as we have an even number and $f\_0$ otherwise.

Given integer $n\ge2$ and $i\ge0$, suppose $f^{k+1}(n)=1$ where $k$ is the smallest such integer. Suppose $f^{i+1}(n)=g\_{c\_i}(f^{i}(n))$ for all $i$, i.e., $c\_i=1$ if $f^{i+1}(n)=f^{i}(n)/2$ and $c\_i=0$ if $f^{i+1}(n)=3f^{i}(n)+1$. Define function $$c:\Bbb N\_{\ge2}\to\Bbb N,\ c(n)=(c\_kc\_{k-1}\cdots c\_0)\_2$$

For example, since $42\stackrel{f\_1}{\to}21\stackrel{f\_0}{\to}64\stackrel{f\_1}{\to}32\stackrel{f\_1}{\to}16\stackrel{f\_1}{\to}8\stackrel{f\_1}{\to}4\stackrel{f\_1}{\to}2\stackrel{f\_1}{\to}1$, we have $c\_0=1, c\_1=0, c\_2=1, c\_3=1, c\_4=1, c\_5=1, c\_6=1, c\_7=1$ and $c(42)=(11111101)\_2$.

You are asking whether $c$ might be a good candidate for a trap-door function.

---

However, it is easy to compute $n$ given $c(n)$. All we need to do is to perform the inverse operations to the operations encoded in the binary representation of $c(n)$.

For example, given $(11111101)\_2$, we simply perform $1\stackrel{g\_1}{\to}2\stackrel{g\_1}{\to}4$$\stackrel{g\_1}{\to}8\stackrel{g\_1}{\to}16$$\stackrel{g\_1}{\to}32\stackrel{g\_1}{\to}64$$\stackrel{g\_0}{\to}21\stackrel{g\_1}{\to}42$ to recover $42$.
> 2 votes

# Answer
Your function isn't a one-to-one function. For many y, there are two different x such that f(x) = y:

If y modulo 6 = 4, then x = (y - 1) / 3 is an odd number, and f((y-1) / 3) = y.

For all y, x = 2y is an even number, and f (2x) = y.

As you see, whatever y is, the set of values x with f(x) = y is very easy to calculate. And by the definition of a one-way function, this means f(x) is *not* a one-way function. For a one-way function, finding *any* x with f(x) = y must be hard.

It is also not a "one-way trapdoor function", which would be a function where any x with f(x) = y is hard to calculate *unless you know some secret*. No secret needs to be known to find any x, given y.
> 0 votes

---
Tags: complexity-theory, p-vs-np
---