# Question
Title: $k$-Opt TSP Local Search is exact when $k = |V| - 1$
I've been self-studying the book *Algorithms* by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP).

We'll say a local search algorithm is *exact* if it always returns a globally optimal solution.

Consider a local search algorithm for TSP that uses neighborhoods defined by $k$-change: two tours $T\_0$ and $T\_1$ are neighbors if one can delete $j \leqslant k$ edges from $T\_0$ and add back another $j$ edges to obtain $T\_1$. This is known as the $k$-Opt algorithm.

It's easy to see and the book itself discusses how for low values of $k$ (relative to the number $n$ of vertices), $k$-Opt may get stuck on locally optimal solutions that are not globally optimal. In other words, $k$-Opt is **not** exact for these values of $k$.

In fact, in a previous question, it was shown $k$-Opt is **not** exact for $k = \lceil n/2 \rceil$. Now, I'd like to show that

> $k$-Opt **is** exact for $k = n-1$.

I have a near solution which I describe below.

---

Given an optimal tour $T^\*$ , if some tour $T$ shares at least one edge with $T^\*$, then $(n-1)$-change can take $T$ directly to $T^\*$.

For $n\geqslant 5$, we can have a tour $T\_0$ which shares no edge with a given optimal tour $T^\*$.
Suppose there were intermediate tour $T\_1$ that uses only edges from $T\_0$ and $T^\*$, and at least one edge from each.

> It's not too hard to see that in this situation, $T\_1$ will have at least two edges from each of $T\_0$ and $T^\*$, though I couldn't make much use of this.

Now, for such a tour $T\_1$, there are three cases:

* $\text{cost}(T\_1) \< \text{cost}(T\_0)$.

This is the easiest. Either $\text{cost}(T\_1) = \text{cost}(T^\*)$ and we're done, or else in another move we can take $T\_1$ to $T^\*$ (since they now share at least one edge).

* $\text{cost}(T\_1) = \text{cost}(T\_0)$

In this case, $\text{cost}(T\_1\setminus T\_0) = \text{cost}(T\_0\setminus T\_1)$.
By construction $T\_1\setminus T\_0$ is a subset of the edges in $T^\*$, so we can remove those edges in $T^\*$ and replace them with $T\_0\setminus T\_1$. This replacement has no cost change, and hence leads to another globally optimal solution $T'$.
$T'$ is then a globally optimal solution that shares at least one edge with $T\_0$, and is hence reachable from $T\_0$ in a single move.

* $\text{cost}(T\_1) \> \text{cost}(T\_0)$

We show this case is not possible. If it were, then $\text{cost}(T\_1\setminus T\_0) \> \text{cost}(T\_0\setminus T\_1)$.
Like above, we could then remove the edges $T\_1\setminus T\_0$ from $T^\*$ and replace them with $T\_0\setminus T\_1$. This time however, $\text{cost}(T^\*)$ would decrease, contradicting the global optimality of $T^\*$.

---

The only missing piece would be to show the existence of $T\_1$. I could solve examples drawn by hand but have had trouble showing this formally.

I would also like to add that the the existence of $T\_1$ must be guaranteed (under the assumption that $(n-1)$-Opt is exact). Indeed, we can handcraft this scenario as follows.

Consider a complete graph $G = (V, E)$ with $n = |V| ⩾ 5$. Let $T^\*$ and $T\_0$ be edge-disjoint tours in $G$.
Let edges in $T^\*$ cost $0$, edges in $T\_0$ cost $1$ and all other edges in $E$ have infinite cost (or anything $\> n$).

Then any tour that improves on $T\_0$ must do so by using some edge with cost $0$ (that is, some edge in $T^\*$) and no edge with infinite cost.
Hence, if $(n-1)$-Opt is exact, it must be able to improve on $T\_0$, and must do so by taking $T\_0$ to a tour that uses only edges from $T\_0$ and $T^\*$, and at least one edge from each, as desired.

---

Of course, feel free to provide an answer that goes in an entirely different direction; it need not build on my unfinished work.

# Answer
> 3 votes
Searching more on the topic, I've found this post on Math SE with a much stronger result that in particular implies the existence of $T\_1$ as defined above. I will reproduce it here to keep things self-contained and prevent question deletions from rendering this answer meaningless.

---

It is true that

> Given two edge-disjoint Hamiltonian cycles, there is a different pair of edge-disjoint Hamiltonian cycles with the same union.

This follows from a result of Thomason, published in Section 2 of

> Thomason, A.G., *Hamiltonian Cycles and Uniquely Edge Colourable Graphs*, Ann. Discrete Math. 3, 259-268 (1978).

The rest of this answer describes how that result applies.

Given a multigraph $G = (V,E)$, possibly having loops, define a *Hamiltonian pair* to be a pair $\\{h,\bar{h}\\}$ of edge-disjoint Hamiltonian cycles in $G$. Note that there are different conventions for counting Hamiltonian cycles of multigraphs. For our purposes, the "fat triangle" consisting of three vertices, each pair of which is joined by two edges, has four distinct Hamiltonian pairs.

> A Hamiltonian cycle can be picked in $2^3$ ways (for each pair of vertices, choose one of two edges connecting them), and uniquely defines the other possible cycle in the pair (for each pair of vertices, use the edge that was not chosen).
> Since which cycle was picked first doesn't matter, the result is $2^3/2 = 4$.

Let $P\_G$ denote the set of Hamiltonian pairs of $G$.
For $e, e'\in E$, let $P\_G(e, e')$ be the set of Hamiltonian pairs of $G$ for which $e$ and $e'$ lie in the same cycle.

Note that if $x$ is a vertex of $G$ and $G$ is $4$-regular, then $x$ is the endpoint of exactly four edges, say $e\_1$, $e\_2$, $e\_3$, $e\_4$, and $P\_G = \bigsqcup\_{i=2}^4 P\_G(e\_1,e\_i)$, where the union is disjoint. It follows that $|P\_G| = \sum\_{i=2}^4 |P\_G(e\_1,e\_i)|$.

**THEOREM (Thomason):** *If $G$ is a $4$-regular multigraph with at least three vertices and $e$ and $e'$ are two edges of $G$, then $|P\_G(e, e')|$ is even.*

By our earlier observation, which is made in Thomason's paper, if one can prove that $|P\_G(e\_1, e\_i)|$ is even for all $i = 2, \dots, 4$, it will follow that $|P\_G|$, the number of Hamiltonian pairs, is even.

Now, let $G$ be the union of two edge-disjoint Hamiltonian cycles on $n$ vertices, viewed as subgraphs of $K\_n$ (the complete graph on $n$ vertices). Then $G$ is a $4$-regular graph.

One Hamiltonian pair is given by taking the two Hamiltonian cycles defining $G$. Since one can assume $G$ has at least three vertices, using Thomason's result, one can produce another Hamiltonian pair in $G$, which is necessarily a Hamiltonian decomposition of $G$ because $G$ is $4$-regular.

> **NOTE:** At this point we already have what we need: either cycle in the second Hamiltonian pair is a valid $T\_1$.

Thomason goes on to prove the stronger result that if $m \ge 1$ and $G$ is a $2m$-regular multigraph with at least three vertices, then $G$ has at least $(3m-2)(3m-5)...7 \cdot 4$ Hamiltonian decompositions. In particular, $4$-regular graphs have at least $4$ distinct Hamiltonian pairs.

> **NOTE:** In our particular case, $G$ is the union of two edge-disjoint Hamiltonian cycles. This means that for any Hamiltonian cycle $C$ in $G$ there's exactly one Hamiltonian cycle that is edge-disjoint from $C$. In other words, any two distinct Hamiltonian pairs are disjoint.
> It follows that for our $G$, there are at least $6$ Hamiltonian cycles which work as choices for $T\_1$.

Thomason also proves that for every $n \ge 10$, there is a $4$-regular graph on $n$ vertices having exactly $32$ Hamiltonian pairs.

---

I suspect there should be an easier way to go about this, since what I needed to show was much, much weaker then Thomason's result. Nonetheless, this at least confirms that things were in the right direction.

I might take a look at the publishing; if I find something more basic that works here, I will update the answer with it.

---

EDIT: The paper's proof is combinatorially existential in nature (not constructive).

It did point at an earlier work by Sloane (in *Hamiltonian Cycles in a Graph of Degree 4*) that proved exactly what we needed. However, that theorem was also proven using combinatorial machinery.

There is a hint of 'constructive' technique in the proof using contraction to obtain a Hamiltonian cycle in a graph with one less vertex. It is used primarily to convert the graph to a form ($3$-regular) in which another result applies, but that result itself was proven combinatorially, so I don't think there's much deeper to dig.

I'll leave this up for a while longer to see if someone comes up with something more concrete, or simpler even if existential. If nothing shows up, I'll mark my self-answer as accepted.

---

FINAL EDIT: I'll just mention that the reasoning above shows that $k$-Opt is also exact for $k = |V| - 2$.

---
Tags: algorithms, graphs, traveling-salesman, hamiltonian-circuit
---


# Question
Title: Uniform Cost Search with Backtracking / Additional constraint?
I am able to implement the default uniform cost search (python) to find the shortest path between two nodes (path cost). I followed this pseudocode:

Now, I want to calculate the shortest path **with fuel constraint**.

Each edge in the graph is associated with a pair of values (, ) where denotes the distance and denotes the fuel cost.

The job is to find the shortest path between and such that the accumulated fuel cost along the path does not exceed a fuel budget. Specifically, we want to find the shortest path from S to T not exceeding a fuel budget 11. We can observe that although the path S-\>2-\>T has the shortest travel distance 10, its accumulated fuel cost 12 exceeds the fuel budget 11. Thus, this path is infeasible. In this example, the path S-\>1-\>T is the shortest feasible path.

What approach should I use for my current UCS algorithm?

Following the original algorithm, it is only adding the neighbor node to the queue if it's not already in the queue, or if the one in the queue has a larger accumulative distance, then I update it with the current shorter accumulative distance. This means at any time, the queue will only have one instance of the node.

Now with this additional fuel cost budget/constraint, what should I modify? Does it seem that now there could be more than one instance of the node with different fuel costs and distance in the queue?

# Answer
The problem is known as the *constrained shortest path problem*. It is known to be $\mathsf{NP}$-hard. The proof is given in the paper: "A dual algorithm for the constrained shortest path problem" (by Gabriel Y. Handler and Israel Zang)

You may want to check this survey for solutions: "A survey of resource-constrained shortest path problems: Exact solution approaches" (by Luigi Di Puglia Pugliese and Francesca Guerriero)
> 2 votes

---
Tags: graphs, artificial-intelligence
---


# Question
Title: Find the average number of steps to sort an array by randomly selecting two elements
I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = \[7, 5, 3, 4, 2, 6, 10, 1, 9, 8\]). I can choose two random number and if the list from left number larger then right number I swap them (for example 2 and 5 list\[2\] larger then list\[5\] so I'll swap them and etc).

Need to find average number of all choosings to order the sequence.

The algorithm should executed less then 1 second.

Can anybody help me?

# Answer
> 1 votes
Construct a directed graph on the set of all permutation of $1,\ldots,n$ (in your case $n = 10$). For each permutation $\pi$, add edges from $\pi$ to permutations obtained by swapping two elements which were in the wrong order. This graph is a DAG with a unique sink, which is the identity permutation $\mathrm{id}$.

You can now compute the expected number of steps using dynamic programming. The base case is $E(\mathrm{id}) = 0$. If $\pi \neq \mathrm{id}$ has outneighborhood $N(\pi)$, then $E(\pi)$ satisfies $$ E(\pi) = 1 + \frac{\left(\binom{n}{2} - |N(\pi)|\right) E(\pi) + \sum\_{\rho \in N(\pi)} E(\rho)}{\binom{n}{2}}, $$ and so $$ E(\pi) = \frac{\binom{n}{2}}{|N(\pi)|} + \frac{1}{|N(\pi)|} \sum\_{\rho \in N(\pi)} E(\rho). $$

The running time for computing $E$ on the entire graph is proportional to $\binom{n}{2} n!$, which in the case of $n = 10$ amounts to 163,296,000.

Using this algorithm, I calculated the average number of steps to be $$ \frac{45411226589}{352546425} \approx 129.$$ This also agrees with my experiments.

# Answer
> 0 votes
The average number is hard, an upper bound isn’t.

You have n numbers, therefore n(n-1) / 2 pairs of numbers. On average half of those pairs are in the wrong order. You need to figure out the distribution for that.

Now if you have k pairs in the wrong order, the probability of picking two random numbers in the wrong order is 2k / n / (n-1). If you pick two numbers in the wrong order and exchange them, the number of incorrectly ordered pairs goes down at least by one. So you expect n(n-1)/2k picks to go from k inversions to k-1 or fewer. (The “fewer” makes it hard to analyse).

---
Tags: sorting, statistics, static-analysis
---


# Question
Title: Proof of NP-hardness of the k-means clustering problem for $k\geqslant 3$
coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems to be separately proved in various places (publications as well as some online PDFs). For instance, the article NP-hardness of Euclidean sum-of-squares clustering (link found on Wikipedia) proves the result for $k=2$ only.

What I don't understand well is that proving such a result seems to lead to an easy one-sentence generalization (see below) to any value of $k$. Knowing very little about the k-means problem, I am pretty sure I am missing something but **why not add the following claim to all these articles?**

> Having proved the NP-hardness of the k-means problem for $k=2$, we notice that any instance of the problem for some value of $k$ can be reduced to an instance of the same problem for the case $k+1$ (by adding one more point to the dataset far enough from all existing points), we easily prove the NP-hardness of the problem for any value of $k$.

For instance, say I want to solve the problem for some $k$ and $n$ points in $\[0,1\]$. I know the sum of the square is smaller than $n$. I now add the new point $1+\sqrt{2n}+\epsilon$ to the dataset, building an instance of the clustering problem for $k+1$. The solution must put this new point alone in a separate cluster (thus not changing the previous sum of squares); because in any other case the new sum of squares would be greater than $n$. Thus solving this new problem for $k+1$ clusters immediately solves the initial instance of the problem. Of course, the very same idea can be used for the plane or any euclidean space.

# Answer
> 1 votes
I think this is a matter of convention in how people communicate the results. It would be one thing to say "The k-means problem is NP-hard \[when k is allowed to be any number up to $n$, the number of data points\]". People might still then hope that there was, say, a $O(n^k)$ algorithm. Subsequently someone may prove that there is some finite $k$ such that the k-means problem is NP-hard, but that this required $k \ge 10^5$. Then people would surely try to modify the approach to show hardness for smaller and smaller values of $k$, until the end of the race: that for all $k \ge k\_0$ it is NP-hard, and for all $k \< k\_0$ it's in $P$.

Each of those improvements, where they reduce $k\_0$, would often write their result as "We show that k-means is NP-hard even when $k=2$". They certainly could write $\ge$, but that feels like a given, and to them their theorem might "really" be saying, "We've shown $k\_0 \le 2$". And they'll be focused on their own particular reduction, where $k=2$.

In short: you're right, yes, $k=2$ could be replaced with $k\ge 2$. But to the people writing that theorem, and most reading it, those really just feel like the same thing.

---
Tags: reductions, np-hard, clustering
---


# Question
Title: Why we can not define factorial in lambda calculus
I came across factorial semantics using lambda calculus:

$$fact = \lambda n. if(iszero~n) (1) (mult~n(fact(pred~n)))$$

I am not sure why the above **does not make sense**. Why we just can not keep substituting $fact $ please?

Other semanticss of $if, iszero, mult, pred$ are defined as follows:

$$ \begin{align\*} if = (\lambda n.n)\\ iszero = if~n==0~~then~~return~~True~~else~~return~~False~~end\\ mult = \lambda n.\lambda m. m (add~n) 0\\ add = \lambda n.\lambda m.\lambda f. \lambda x. nf(mfx)\\ pred~0 = 1 \end{align\*} $$

**Edit**: it does not make sense as we can not use the function itself in its definition.

# Answer
The language doesn't really allow definitions of the form $\text{name}=\textit{expr}$. That's just a shorthand for readability. All of these definitions have to be eliminated by substitution to get a real λ-calculus term.

You can substitute the definition of $\text{fact}$ into itself, but the result will still have an occurence of $\text{fact}$ in it. No matter how many times you substitute, you can't get rid of the self-reference.

You can't substitute it infinitely many times to get an infinite term with "turtles all the way down". Terms have to be of finite length.

The usual solution is to introduce a fixed-point combinator to eliminate the self-reference. That's probably what your teacher will do next.
> 5 votes

# Answer
$\lambda$-calculus has a very restricted set of symbols. You can't refer to a variable by a variable name. You can't refer to something by itself in the definition because there is no way to "refer" to anything. There is only $\lambda$, $.$, well-balanced parentheses $(,)$ and a countably infinite number of variables (e.g. $x,y,x\_0,x\_1,...$). There is nowhere you can refer to another $\lambda$-term, let alone the term itself.

$iszero = if~n==0~~then~~return~~True~~else~~return~~False~~end$ is *not* the language of $\lambda$-calculus. It is a shorthand *outside* the language of $\lambda$-calculus for the $\lambda$-calculus term found by a certain composition of $\lambda$-calculus terms: $True$ is $\lambda xy.x$, $False$ is $\lambda xy.y$, etc.

If $\text{fact}$ was a $\lambda$-calculus term with length $k$ then $\lambda n. if(iszero~n) (1) (mult~n(fact(pred~n)))$ would have length $\>k$, so the two could not possibly be the same set of symbols (they cannot be equal under $\alpha$-conversion). So, the $=$ in the equation must indicate equality under $\beta$-conversion (or even $\beta\eta$-conversion), and you have not defined a term in the $\lambda$-calculus if you have just specified its $\beta$ properties, not its literal symbolic definition (up to $\alpha$-conversion). Specifying what properties you want it to have is not acceptable, otherwise you could specify paradoxical properties.

You say in a comment that $Y\equiv(\lambda x. \lambda y. y(xxy))(\lambda x. \lambda y. y(xxy))$ "is calling itself twice", but no such thing is true. The RHS makes no reference to the variable $Y$. That it is the application of two identical $\lambda$-terms is not really relevant: it is a string that can be obtained by repeated applications of the variable rule ($x,y$ are $\lambda$-terms), application rule ($xx,xxy,y(xxy),...$ are $\lambda$-terms) and abstraction rule $\lambda y.y(xxy),...$ are $\lambda$-terms).
> 5 votes

---
Tags: lambda-calculus
---


title: Name of this graph family?

text:
# Question
Title: Name of this graph family?
Suppose I start with a directed chain graph of length $n$:

And then I add $k$ edges, with a restriction that the result is a planar DAG:

Is there a name for this graph family?

# Answer
> 1 votes
Your graph class coincides with the class of Hamiltonian planar DAGs. See \[1\] for the undirected version of the equivalence. See also \[2\] for an account of the directed version.

Proof sketch: given a directed Hamiltonian path, the vertices can be moved continuously to a straight line so the planar embedding is preserved.

The underlying undirected graphs are called *book thickness 2*, *2-page* or *2-stack*. This class is equivalent to the subhamiltonian graphs.

* \[1\]: Frank Bernhart and Paul C Kainen. "The book thickness of a graph." *Journal of Combinatorial Theory* Series B 27.3 (1979).
* \[2\]: Binucci Carla et al. "Upward book embeddings of st-graphs." arXiv preprint arXiv:1903.07966 (2019).

---
Tags: graphs, dag
---


# Question
Title: Solve the recurrence $3T(n) = T(n/3)+ \sqrt{\log n}$
How can you solve the recurrence $$3T(n) = T(n/3)+ \sqrt{\log n}$$ using the master theorem?

I am lost in this question.

# Answer
Asymptotically, T(n) ≈ sqrt (log (n)) / 2. That's the answer to your question. It's very unlikely that it is the answer to the question you wanted to ask.

I didn't use the master theorem to solve this, but a spreadsheet :-)
> 0 votes

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


# Question
Title: "Guess the number" Problem on Turing machines
I am currently learning about the concept of Turing Machines and trying to relate it with my knowledge on the application of the Binary Search algorithm.

The problem I am working on is to write an algorithm that can find an unknown natural number between two given natural numbers by guessing.

A solution would look like the following code in JavaScript.

```
// fixed structure "generateAsk" is always provided to the problem
let generateAsk = function() {
    let guess = window.prompt("Guess: ");
    return function(x) {
        return ((x < guess) && "<") || ((x > guess) && ">") || "="
    };
};

let ask = generateAsk();

let low  = window.prompt("Low: ")
  , high = window.prompt("High: ");

function find_unknown_number(low, high, ask) {
    // uses Binary Search to search the unknown value
    // and returns the unknown value when found or -1 otherwise
}

let result = find_unknown_number(low, high, ask)
console.log(result);

```

My question is not meant to ask for how to ***solve*** this problem, but to ask the ***practical use*** of any algorithm that can be introduced above.

To be clearer, as I know, mostly any program can be debugged. Isn't anyone able to just stop the program written above, during its execution, with a debugger and then just filter the body of the "ask" function parameter and extract the unknown value?

The way my question is related to the Turing Machines is that, for what I know, the Turing Machines receive input on a tape (so any character introduced on the tape may very well be "visible" from the outside during any execution phase of the algorithm).

Therefore, the questions that I present to you are:

> How the implementation of a solution to this problem on a Turing Machine ***would not be pointless*** from the perspective in which one can stop the program, read the "ask" function body by reading the corresponding tokens on the Turing Machine and then return the "unknown" value?

> Is there any concept of "privacy" of tokens in the world of Turing Machines or some structure that can be used to implement "privacy" in some specific tokens written on a Turing Machine?

# Answer
> 17 votes
Yes, it is pointless and absurd to implement an algorithm to "guess the number" using the most common kind of Turing machine, whose head can read any cell on the tape, since, as you pointed out, there is no way to enforce the condition that the algorithm/the machine should not read "the number", which must be a part of the input.

Of course, that does not mean an algorithm that can "guess the number" (efficiently) without reading the number is not useful. For example, the binary search algorithm is used in many places in real life such as git-bisect or binary-search routines in the built-in libraries of many programming languages.

Rather, that just means that kind of Turing machine is not the right model of computation for that particular problem.

### What is a model of computation?

> In computer science ... a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how units of computations, memories, and communications are organized.

### Which model of computation is for "guess the number"?

One suitable choice for "guess the number" is an oracle machine.

> An oracle machine ... can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation.

A version of the problem of "guess the number" can be stated as the following.

A number has been chosen between integer $low$ and integer $high$. There is an oracle which, given integer $k$, answers the question "is the chosen number smaller than $k$?". How can we design an oracle-machine with that oracle that will find the chosen number given input $low$ and $high$? The less number of times the oracle is used, the better the oracle-machine is.

Beside enabling a solution, the oracle above is used to, in your words, ensure 'the 'privacy' of tokens".

### There are many models of computation

There are many different kinds of computational problems. There are also many models of computation. A problem/proposition/argument makes sense only in some models of computation.

Among all models of computation, (that common kind of) Turing machine is the simplest that "can" compute anything that is "effectively computable", basically. That is why you are directed to learn it. However, that does not imply we should/may express and solve every algorithmic problem with it. For another example, it does not make much sense to implement quantum computation on a conventional Turing machine.

### Exercise. What is the most popular model of computation?

By "the most popular model of computation", I mean the one that is used, implicitly or explicitly, when big $O$-notations representing time-complexity or space-complexity are mentioned on almost all millions of web pages on programming. It is certainly not Turing machine.

# Answer
> 5 votes
In casual words, a Turing machine can do anything computational, but *nothing else*; especially there's no IO. No keyboard, no mouse. It just takes a tape as input and runs a predefined program on it.

This means that you cannot use `window.prompt` or similar (anything that asks for user input) in the middle of your program, and therefore there is no equivalent of "Guess the number" program for TM. So, if you want to stick to the TM as the model of computation, you basically need a different problem that can be solved with binary search, without user input in the middle of the program.

Some examples of such problems include:

* An array of integers is given in strictly increasing order. Determine if a given number exists in the array.
* An array of integers is given, so that all odd numbers come before all even numbers. Find the first even number in the array.
* Given a polynomial and a range (upper and lower limits of the value of x), find a zero of the polynomial within the given range.

# Answer
> 4 votes
Here is how this kind of program could be useful. Suppose that you have a graph, and you are trying to find its chromatic number $\chi$, that is, the minimum number of colors needed to color the vertices of the graph so that each edge connects vertices of different colors.

Given a target number of colors $C$, you can attempt to color the graph using $C$ colors in various ways. This corresponds to an algorithm for answering the question \`\`is $\chi \leq C$?''. Using binary search, you can use such an algorithm to find $\chi$ exactly.

In this example, $\chi$ isn't written anywhere. Rather, we can check whether $\chi \leq C$ for any given $C$. This suffices for finding $\chi$ using only $\log n$ queries of this form, where $n$ is the number of vertices.

# Answer
> 2 votes
The way I understand your question, you are wondering why there is a need to do some extra computation (binary search in your case) if the TM can simply read the input, and it will already know the number to be searched, thus performing binary search is not necessary. This might not always be the case.

Consider, the situation, such that the input is the hash value $x'$ of the number that the TM will guess, instead of the actual number $x$. Here we assume that the hashing algorithm used to produce $x'$, is built internally to the TM, that is the TM can perform a hash. Now, as you might imagine, simply reading $x'$ will not help the TM to know what $x$ is. We will force it to actually guess. Although at this point, binary search might not be possible since the TM will not be able to know if the number is less than or greater than the middle value of the range. But instead it must perform the guessing brute-force, trying all values from the range. That is, the TM will start with the lowest value, compute its hash, test if it is equal with the input. If it is, then the TM guessed the number, otherwise it moves to the next number in the range and repeat until it found the right value or exhaust the range.

As a side note, the idea here is very much similar to what you would expect from log-in systems. Even though they can validate the password you enter when logging-in, they actually do not know your actual password, since they only store the hash of the password you initially set.

---

As @jaxad0127 in the comment suggested, you can change the hash function to be some other function $f()$ that is difficult to invert but preserves order. That is, for any two numbers $x\_1$ and $x\_2$ such that $x\_1 \lt x\_2 $, it is always guaranteed that $f(x\_1) \lt f(x\_2)$. This would now allow you to perform binary search. But still, reading the input $x'=f(x)$ will not give the TM any idea as to what the $x$ is and would be better-off performing binary search.

# Answer
> 2 votes
> Is there any concept of "privacy" of tokens in the world of Turing Machines or some structure that can be used to implement "privacy" in some specific tokens written on a Turing Machine?

There is a concept of obfuscation. A software code is obfuscated to make it difficult to analyze the behavior of the program, even if the source code of the program is given. This concept is mostly applied to practical programming languages or machine codes but can be applied to more computation models, including Turing machines.

A theoretical concept of obfuscation is black-box obfuscation. Informally speaking, with such obfuscation, no one with a "debugger" can inspect the program to get more information than just running the program. It is proven no such scheme exists.

# Answer
> 2 votes
When you find X, you don't just find X but also any other information in the same location as X.

Imagine you have n pages, on each page is written a name and address. The pages are sorted alphabetically by name and numbered from 1 to n.

You wish to find the address for Drew Lee.

You could start at page 1 and just go page by page, but that will take a really long time if n is large.

Or you could do binary search, go to n/2, check if *the name on page n/2 is greater than or less than Drew Lee*, and then proceed...

So you are trying to find X where X is the number of the page that has Drew Lee on it. You can't just say you already know the name Drew Lee, because you actually need the page (to get the address). But the page isn't anywhere in the question to "peek" at, you can only find the page by searching.

This is a real problem that is really solved all the time, although usually by using a library/database/etc. that already has binary search (or even faster searches) implemented. (But a database isn't a Turing Machine, I hear you cry... Yes, but the search algorithm itself functionally is, you have some static input--the search term, the information to search--and it does it's thing and gives you some output.)

---
Tags: algorithms, turing-machines, algorithm-analysis, search-algorithms, binary-search
---


# Question
Title: What are other alternatives to version control on structured or large and highly volatile data?
Say you are editing a document like a 1000 page book. There are 20 authors all working furiously to edit the book. Every day they are merging their changes 2 or 3 times with the main branch. According to my understanding of git snapshots, this would create a new copy of the document every merge, so by the end of a year there would be $20 \times (2..3) \times 365 = 9125$ copies of that 1000 page file, each with their own snapshot. If that file was 50MB, that could potentially be ~450 GB of storage required (if I am calculating correctly). I am not sure yet how packing would help, it might though, but still this is a lot of extra data, when the change set might be fairly small relatively speaking, only a few lines or paragraphs here and there for each commit.

Same with editing structured data. Say you have one "file" which is 1 million records in a CSV or indexed data structure, and thousands of records are edited every day. This would explode the amount of disk usage required for git to keep versioned snapshots of the file.

What are solutions to this problem? Ideally only focusing on structured tree data like XML files, but if I could ask for one more it would be arbitrarily large text files like a book. But most important for my current task is diffing on trees. I found *Precise Version Control of Trees with Line-based Version Control Systems* and other XML related tree-versioning systems, but I wonder why they are not mainstream (or why I have missed them if they are).

I would like to build a sort of versioned XML database and wondering what the cutting edge is in terms of getting git-like branching/merging, to commit history and navigating to old folder hierarchies, to the performance/speed of doing a commit or clone (instant for all intents and purposes, compared to subversion). Have these problems been solved in one way or another, or is it still an open research question?

My wishlist would be:

1. Fast reads and writes to the "package" or central data repository.
2. Fast commits.
3. Compact data representation to avoid the disk space explosion problem of git on these types of data.
4. Fast navigation between commits and branches.
5. Many people could be branching and merging at the same time as easily as git.

# Answer
> 4 votes
With Git, you have to distinguish between three different things:

* The Abstract Git Object Model which sits at the core of Git.
* The Storage Format which sits *underneath* the Object Model.
* The surface *interpretation* of that Object Model by the Git command-line tools.

# Git Object Model

The Git Object Model is very similar to the design of the Unix filesystem, which is not surprising given that Git was designed by the author of a Unix-like Operating System. The major difference to a traditional filesystem is that Git is *content-addressable*.

## Adress space

All Git Objects live in the same address space. The address of an object is a hash of its content. Hence, two objects with the same content have the same address and are thus indistinguishable … or in other words, they aren't two objects, they are one and the same.

At the moment, that hash is SHA-1, but a design for moving to SHA-256 was created in 2017 and the implementation is now in an alpha-stage.

## Content address

Each Git Object has an *Object Header*. The Object Header is

1. An ASCII string describing the type of the object, e.g. `blob`, `tree`, `commit`, etc. followed by …
2. An ASCII space character followed by …
3. The length of the content in octets, encoded as a series of ASCII digits followed by …
4. a `NUL` octet.

This is then followed by the actual content of the object.

The address of the object is the hash of the whole thing, i.e. the header followed by the content.

## Blob

The simplest kind of object in the Git Object Model is the *blob*. A blob is just an un-typed un-structured sequence of octets. It is the equivalent to a *file* in Unix.

Its structure is extremely simple: it is just the object header (with type `blob`) followed by the octet sequence.

## Tree

A *tree* associates names with blobs (and trees). A tree is a set of name→object mappings. Trees in Git are the equivalent to *directories* in Unix and the name→object mappings are the equivalent of a *hardlink*.

In addition to the name→object mapping, a tree also stores some metadata about the mapping, in particular, *permissions*. This is *different* from Unix, where the permissions are a property of the file, not the link!

For the purpose of hashing the content of the tree, the content is encoded into a well-defined format with a well-defined ordering of the mappings.

## Commit

A *commit* records a specific state of a tree at a specific time by a specific person and associates a descriptive message with that state.

A commit consists of the following:

* Exactly one tree.
* Zero or more parent commits.
* A committer name.
* A commit timestamp.
* An author name.
* An authoring timestamp.
* A commit message.
* An optional digital signature.

The address is again based on a well-defined encoding of those fields.

## (Annotated) Tag

An *(annotated) tag* gives a human-readable name and description to a commit.

A tag consists of the following:

* A commit.
* A tagger name.
* A tag timestamp.
* A tag name.
* A tag message.
* An optional digital signature.

## References

References are actually *not* part of the object model. They are just names assigned to objects (mostly commits). This applies for example both to *branches* and (non-annotated) *tags*.

# The Storage Format

## Loose

A naïve way of storing Git Objects would be to just store each object as a separate file with the address as the name. And in fact, a slight variation of this naïve format (which uses the first two characters of the hexadecimal encoding of the address to create a directory tree in order to avoid having too many files in a single directory) was the original storage format for Git and it is still in limited use today. Nowadays, it is called the *loose object format* as opposed to the newer *packed object format*.

As you rightly pointed out in your question, this format could potentially waste a lot of space. Although it does not actually take up as much space as you would think:

* Remember that two objects which have the same content are *the same object*. So, a file that is not changed between two commits is only stored once.
* In fact, this does not only apply to different versions of a single repository. Two files *anywhere in the world* in completely unrelated repositories which have the same content will have the same address. If you think about a service like GitHub which stores many different unrelated repositories, there will for example only be *one* copy of the license text of the GPL in the entirety of GitHub, since the text is always the same in every version of every repository that contains the GPL license, the address will always be the same. (Modulo things like Unix vs. DOS line endings or whether or not the file ends with an empty line.)
* Only blobs are big, all other objects are *tiny* since they mostly contain just addresses of other objects. (Unless you write a 100000 word commit message …)
* All objects are stored deflate-compressed. This means that anything which compresses well, such as text (that means both your book as well as your hypothetical 100000 word commit message) will not use much storage space.

## Packed

However, that is not actually how Git stores objects long-term. Whenever you perform an operation which adds new objects to the object storage, Git will check a number of statistics and compare them against a set of configurable thresholds. If it finds that one of the statistics (e.g. number of loose objects) is higher than the threshold, it will *pack* the loose objects into a *packfile*.

A packfile is simply all content of the loose objects concatenated together and then xxdelta-compressed. Next to the packfile, there is an *index* which maps addresses to offsets within the packfile so you can find your objects again.

At some point, you will then find yourself with a small number of loose objects and a growing number of packfiles and indices, but you can again apply some statistics and *repack* those individual packfiles and loose objects into a single packfile containing your entire repository.

Since there are lot of similarities between the objects (e.g. two consecutive versions of a blob will be almost identical, or many commits will have the same committer), there is a lot of redundancy in the packfile, and it compresses very well. In fact, Git uses some additional heuristics to optimize the placement of the objects inside of the packfile to make it easier on the compression algorithm and keep runs of octets that are likely to be similar closer together.

Note! I am not actually sure whether all of these heuristics are used, but I am going to list some examples of what *could* be useful:

* Blobs which are assigned the same name in trees are kept close together, under the assumption that they are all the same file with only small changes between them.
    + This is further optimized by also taking into account how many commits there are in between the two versions, putting consecutive versions closer together.
* Blobs which are assigned names with the same file extension are kept closer together, under the assumption that e.g. C files will be similar to each other (e.g. by all beginning with the same copyright statement or a documentation comment), HTML files will be similar to each other, etc.
* Objects of the same type are kept closer together, under the assumption that e.g. commits will only contain the names of a small number of committers over and over again, or trees will point to mostly unchanged blobs with mostly the same names, etc.

Based on these heuristics and the packfile format, Git can often eliminate redundancies between consecutive versions of files (as a difference-based SCM would) but even between similar runs of content in totally unrelated files (such as identical copyright statements at the top of every source file). As a result, Git repositories are often *smaller* than the equivalent repository in a different, difference-based SCM. For example, when I converted all my old Subversion repositories back in 2005, I got a significant reduction in storage space.

## Aside: network protocol

The network protocol is also based on packfiles. The client can request from the server a certain set of objects, e.g. based on a range of references or commits, and the server will send all of the objects needed to reconstruct everything within that range to the client. What it is actually sending is one or more packfiles which contain (at least) those objects. Theoretically, the server could just always keep the repository fully packed and blindly send the full packfile on every request (since it will by definition include all objects the client asked for because it contains *every* object in the repository), but that would be inefficient. In reality, there is a balancing act of tradeoffs whether or not and how much the server repacks the data so that it only contains what the client needs.

## Abstraction

Note that in the standard implementation(s) of Git (the original Git CLI tools and libgit2) as well as in many alternative implementations (e.g. JGit, Git#, etc.), the storage format and the object model are kept well abstracted from each other. This allows companies like GitHub to completely replace the storage format with a custom one that is more suited for their application and scale.

For example, I have seen people replace the storage backend with a database. There are browser-based Git implementations which use HTML5 Local Storage. And of course, GitHub's secret sauce when it comes to performance is their completely custom storage backend.

# Interpretation

You might have noticed that I talked about for example *blobs* and *trees* in very abstract terms. I never wrote they are files and directories, because as far as large parts of Git are concerned, they don't know anything about files or directories. The storage backend isn't even necessarily concerned about trees or blobs or commits! It only cares about objects.

The only thing in the entire object model that breaks this nice conceptual separation are the permission bits in the trees.

It is only the high-level surface tools like `git checkout` which then *interpret* trees as directories and blobs as files. But that is only an *interpretation* of the object model, and just like the storage backend is neatly abstracted, so are the high-level surface tools. You can replace the tools with your own, and thus supply your own interpretation.

For example, there are Wikis which use Git as their backend. Here, blobs are *pages*, not files, and trees represent *page nesting*, not directories. Some Smalltalk systems use Git as a versioned object database.

Within Git itself, there are *Git Notes* which are a kind of versioned metadata for Git objects.

So, in your world, you could interpret blobs as *paragraphs* and trees as *chapters*, for example. I myself have experimented with interpreting blobs as *methods* and trees as *classes*.

# Summary

So, in short: Git has solved all your problems already, you just need to change your viewpoint of what "Git" is a little bit.

At its core, Git is a content-addressable versioned object database with a space-efficient storage backend (that can be swapped out if needed) and only a thin (and optional!) veneer on top that interprets those objects as files and directories.

---
Tags: trees, database-theory
---


# Question
Title: How would my parsing functions look for this grammar?
Suppose we have the grammar

$$S \to aA | BA $$ $$A \to a | bB | \epsilon $$ $$ B \to cB | d$$

I know that I need to write four different functions in order to parse this grammar.

They are

`parse_input()`,

`parse_S()`,

`parse_A()`, and

`parse_B()`

However, I am having trouble coming up with a parser for this short grammar. Does this look right?

```
parse_input():
    if (peek(1) = a AND peek(2) = A)
        parse_S()
    else if (peek(1) = a OR peek(1) = B)
        parse_A()
    else if (peek(1) = c or peek(1) = D)
        parse_B()

parse_S()
    if (peek(1) = a)
        expect(a)
        parse_A()
    else
        parse_B()

parse_A():
    if (peek(1) = a)
        expect(a)
    else if (peek(1) = b)
        expect(b)
        parse_B()
    else if (peek(1) = $\epsilon$)
       expect($\epsilon$)

parse_B():
    if (peek(1) = c)
        expect(c)
        parse_B()
    else if (peek(1) = d)
        expect(d)
    else
        syntax_error()

```

but after that, I am stuck.

# Answer
> 1 votes
$peek(i)$ (presumably) returns the $i^{th}$ next token from the input stream. $A$ is not a token; it's a non-terminal, aka *grammar variable*, which denotes the result of a recursive parse of a substring of the input. So $peek(2)$ cannot return $A$.

But in some sense that doesn't matter, because the goal is to parse without ever peeking beyond the next token, and that's certainly possible for this grammar. Once you know that the next token is $a$, you know to predict $S\to aA$, and you know what you must do: match the $a$ and then parse the $A$. Of course, it's possible that parsing $A$ will fail, but that error will be noted in the course of the parse.

Equally, $peek(1)$ cannot return $B$, so you are asking the wrong question in that line. What you want to know is whether the next token could be the first token of a substring derived from $B$; in other words $peek(1)\in FIRST(B)$, where $FIRST(B)$ is the set of tokens which could be at the start of a derivation of $B$. Given a grammar, it's easy to compute the $FIRST$ set for each non-terminal.

Since $a$ is not in $FIRST(B)$, it's not totally necessary to test whether $peek(1)\in FIRST (B)$. You could just call $parseB()$, which will fail if the first token is wrong. Using default actions can simplify parsers but it can also lead to unexpected side effects before errors are discovered, if the parse actions have side effects. So your implementation of $parseS()$ is fine.

But your implementation of $parseA$ attempts to check whether $peek(1)$ is $ε$, which is non-sensical. $ε$ is not a token. It's an empty sequence of tokens. In other words, it's nothing. If you were to ask "can $A$ start with nothing?", the answer would be immediately be "yes, of course". You don't need to know anything about $A$ other than that it derives at least one possible string, because the empty sequence is a proper prefix of every possible sequence, even the empty sequence itself. So if you get to that point in the control flow, you can just return; the parse of $A$ succeeded by successfully matching nothing.

I could go on, but I think you would find it more valuable to read a chapter in some introductory parsing text about top-down parsing, and make sure you understand the basic concepts: terminals and non-terminals, derivations, FIRST and FOLLOW sets. None of it is complicated.

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


# Question
Title: From a directed graph (A), produce an undirected graph (B) with an edge for at least one outgoing edge for every vertex in A, minimizing edges
**Problem:** Given a directed graph $A$, produce an undirected graph $B$ with the same vertices and minimum number of edges satisfying the following constraint:

* For each vertex in $A$, at least one outgoing edge must be replaced by an undirected edge in $B$. If an edge in $A$ is bidirectional, then it can be replaced by a single edge in $B$.

The worst case is randomly creating one edge in $B$ for a random outgoing edge for every vertex in $A$. This would yield $|V|$ edges. However, the constraint allows for optimization by replacing bidirectional edges with a single undirected edge in $B$, resulting in as low as $|V|/2$ edges. However, if a vertex in $A$ already has an outgoing connection replaced in $B$ then replacing another bidirectional edge is not optimal. This mutual exclusion causes a need to examine the optimal way to pair vertices.

**Source:** Interestingly, this problem comes from trying to fix cases the Mark Bayazit algorithm fails for convex decomposition. Reflex points are given a range. Any line within the range will resolve the reflex point and thus increase how convex the shape is. Connecting two reflex points which have each other in their ranges is most optimal: it eliminates two reflex points with a single line. However, simply connecting reflex points leads to constrained choices down the road. You can find the full Algorithm here: https://mpen.ca/406/bayazit

# Answer
Thinking more about it, I may have found a solution. Temporarily simplifying the representation led me to some algorithms on Google, and the remainder is trivial.

If we create an undirected graph $C$ which has an edge for every bidirectional edge in $A$, then we need to find a "Maximum Matching" of the graph. I found some algorithms to do this at iq.opengenus.org.

Let us include all edges of a maximum matching in $B$. Next, for each vertex in $A$ which does not have any outgoing edge created in $B$, pick a random outgoing edge and create it in $B$.

Now, to actually solve the cases the Mark Bayazit algorithm fails, additional issues like if the resulting edges intersect need to be evaluated as well, so I wont be choosing randomly in my implementation.
> 1 votes

---
Tags: graphs, optimization
---


# Question
Title: Choose combinations of similar value, without repeating first or second coordinate
**Motivation**

In a particular board game, players start the game with a country and a special ability. Two players cannot have the same country or the same special ability. Analysis has shown that certain country-ability combinations are better than others. The combinations have been evaluated with an integer where higher integers are better. I want an algorithm to randomly sample a possible game with a certain number of players and that is "balanced", i.e., no two players' combination value difference exceeds a certain delta threshold.

**Problem Statement**

You are given $X=\\{x\_1, \dots, x\_n\\}$, $Y=\\{y\_1, \dots, y\_n\\}$, and $T=X \times Y \rightarrow \mathbb Z$.

Given $k$ and $d$, randomly sample a set $\\{(a\_1, b\_1), \dots, (a\_k, b\_k)\\} \subset X \times Y$ such that $a\_1, \dots, a\_k$ are pairwise distinct, $b\_1, \dots, b\_k$ are pairwise distinct, and $|T(a\_j, b\_j)-T(a\_i, b\_i)| \leq d$ for all $i,j$.

# Answer
All solutions have the following form: pick a lower limit $\ell$; let $E = \\{(x,y) : x \in X, y \in Y, \ell \le T(x,y) \le \ell+d\\}$; finally pick a subset $S$ of $E$ of size $k$ with no repeats in the first coordinate or second coordinate. The latter step can be viewed as the problem of finding a matching of size $k$ in a bipartite graph, where we view $X,Y$ as the two vertex sets and $E$ as the set of edges.

So, if you want to find one solution, there is a polynomial-time algorithm: enumerate all possible values $\ell$ of $T(X,Y)$; for each such $\ell$, form a graph with edges $E$ as above, find a maximum-cardinality matching in this bipartite graph using standard algorithms, and check whether its cardinality is at least $k$.

If you want to find all solutions, then you'll need an algorithm to find all cardinality-$k$ matchings in a bipartite graph. I don't know how to solve that problem efficiently. (Note that there can be exponentially such matchings, so the best you could hope for is a polynomial-delay algorithm.) A trivial but extremely slow algorithm is to enumerate all subsets of $k$ edges and check whether it is a matching (with early pruning), but there might be much better algorithms.

Perhaps the reason you are asking for all solutions is that you have some other constraints you want to impose on a solution, and your thought was to enumerate all solutions and look for one that meets your other constraints. If so, it might be better to formulate this as a constraint solution problem that includes all constraints from the start.

Your subsequent clarification indicates that you want to sample a random solution. I don't know whether there is an efficient algorithm to sample uniformly at random from a matching of cardinality $k$. I would not be surprised if there are sophisticated algorithms, that sample approximately uniformly at random, based on MCMC or other techniques, but this is now an advanced area of the field that is beyond my knowledge. I believe it is known that there are efficient algorithms that can approximately count the number of perfect matchings, and from this it should follow that there are efficient ways to sample approximately uniformly at random from these matchings (pick an edge $e \in E$, count the number of perfect matchings that do include $e$ and the number that don't include $e$, and then randomly choose whether to include $e$ via a biased coin flip with heads probability chosen based on those two numbers, and continue from there). I don't know if this extends to approximately counting the number of cardinality-$k$ matchings or approximately randomly sampling from these matchings.

I can give you a heuristic method for randomly sampling a matching that might work well enough in practice, but I don't think it comes with any theoretical guarantees. Pick a random hash function $h:E \to \[0,1\]$ that hashes each edge to a real number in the range $\[0,1\]$. Pick a threshold $t \in \[0,1\]$. Set $E' = \\{e \in E : h(e) \le t\\}$. Check whether there is a cardinality-$k$ matching in $E'$. Now do binary search on $t$ to find the smallest $t$ that $E'$ contains a cardinality-$k$ matching, and output this matching. If you're lucky, this might work well enough: it should always find a cardinality-$k$ matching, and I suspect that the resulting matching might be random enough for your purposes (but there are no guarantees of randomness, and I think the resulting distribution on matchings is not uniform).
> 1 votes

---
Tags: constraint-satisfaction, selection-problem
---


# Question
Title: How to determine if clause will change the satisfiability of the 3SAT formula?
I have satisfiable 3SAT formula like: `(x1 or x2 or x3) and (not x1 or x2 or not x3)` and some clause which is not in this formula `(not x1 or x2 or x3)`. Are there any methods to find out if this clause will turn formula in unsatisfiable state? Without obviously appending them and solving new formula. Or maybe some method to generate such type of clauses that won't affect satisfiability?

I am not necessarily looking for polynomial-time algorithms. But something better than brute force would be great. Probabilistic methods ideas are also welcome.

# Answer
The best you can do is append the clause and test satisfiability. There is no hope for anything better. (Proof: if there *was* a good method, then we could use it to solve 3SAT faster: if we had an arbitrary 3CNF formula $\varphi$, we could apply this method to a formula containing all but the last clause of $\varphi$ and the last clause of $\varphi$.)

Maybe what you really want to do is solve this problem repeatedly, with the same formula but a different clause. In other words, you want to test satisfiability of $\varphi \land c\_1$, $\varphi \land c\_2$, etc., where $\varphi$ is a 3CNF formula and each $c\_i$ is a single clause. If so, some SAT solvers support the ability to "push" a clause and then "pop" it, exactly for this use case. This is sometimes known as "incremental solving". See, e.g., https://theory.stanford.edu/~nikolaj/programmingz3.html#sec-incrementality, https://stackoverflow.com/q/18269016/781723. You could explore the literature to see what ideas they use for incremental solving.
> 1 votes

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


title: Enumeration of a class of languages

text:
# Question
Title: Enumeration of a class of languages
Can you enumerate a class of languages in such a way that the description of every language/ machine enumerated encodes where it was in the enumeration?

Ex:if you are given the description of the bth machine/language enumerated you could quickly check, by some tag or marker in the description of the bth machine / language, that it was indeed the bth machine/language in the enumeration by an enumerator E.

Can you modify any enumerator for a class of languages so that it does this? Or can such an enumerator E be rigged up to do this for any enumerable class of languages?

To give context, my goal is for a verifier to accept, as one part of its input, the machine/language enumerated, and be able to see, quickly, what position that machine/language was in the enumeration by the enumerator E.

Thank you!

# Answer
Given any enumeration $E$ of the language, here is a way to describe a language: "the 5th language in the enumeration".

If you use that as the description, then yes, your condition is trivially true. Given the description of a language ("the 5th language in $E$"), you can quickly find its position in $E$ (5).
> 0 votes

# Answer
Consider a language $L$ which can be enumerated by a Turing machine, and let $w\_1,w\_2,\ldots$ be the words of $L$ in order of enumeration. Suppose that to every word $w$ in $L$, you can associate some other word $w'$ of length $\mathrm{poly}(w)$ such that given $w$ and $w'$ you can find in polynomial time where $w$ should appear in in the enumeration, and verify that it indeed does. In particular, given $w'$, you can verify in polynomial time that $w\in L$. Thus, $L\in NP$.

Because $NP$ is a proper subset of the set of recursively enumerable languages, the answer to you question is no.
> 0 votes

---
Tags: complexity-theory, enumeration
---


# Question
Title: Analytic combinatorics and less-precise running times
Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the analysis of algorithms, e.g. in books by Knuth and (his student) Sedgewick. However, the results tend to be very precise -- they might give a running time as $c n \log(n) + O(n \log(n)^2)$ for example. Running times in Introduction to Algorithms on the other hand generally require simpler math are more likely to be stated as $\Theta(n \log(n))$. **My question is whether there are examples where the advanced mathematics of analytic combinatorics is necessary even to get a rough Big-Theta running time.**

---

After all, a commonly-applied version of singularity analysis is a statement about Big-Oh bounds:

This is from chapter 13 of Selected Papers on Analysis of Algorithms:

In chapter 26 Knuth uses complex analysis to find that "the average carry propagation time to add n-place numbers" is

Whereas in Introduction to Algorithms we find this:

# Answer
> 2 votes
The analysis of Heapsort's average case time does not yield the constants involved. This is a fundamental issue with algorithms of this nature relying on dynamic updates. The analysis, establishing the optimality of heapsort's average-case time, inevitably proceeds by contradiction for instance using a Kolomogorov complexity incompressibility argument. The reason is that the precise analysis of the selection phase cannot be done by standard means and remained an open problem. The problem is inherent in all heapsort variants to date with one more recent exception (Percolating Heasport).

Heapsort provides the requested example where more advanced techniques are required to obtain $\Theta(n \log(n))$. Note that Sedgewick and Schaffer's original work go the analytic route is still by contradiction (involving a longer argument than the incompressibility method) and facing the same issues.

The following references contain the relevant material

1. Sedgewick, Schaffer, The analysis of Heapsort
2. Li and Vitanyi "An Introduction to Kolmogorov Complexity and Its Applications" discusses the incompressibility argument for Heapsort.
3. Knuth, TAOCP, Vol III (Sorting and Searching), discusses the open problem on the selection phase.
4. Schellekens, A Modular Calculus for the Average Cost of Data Structuring discusses the history and root of the problem and the alternative of Percolating Heapsort.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, combinatorics, discrete-mathematics
---


# Question
Title: Proof that using residual network from Ford-Fulkerson will get you min-cut
So I'm following this article and they use the following algorithm to find the min-cut.

**Algorithm:**

1. Run Ford-Fulkerson algorithm and consider the final residual graph.
2. Find the set of vertices that are reachable from the source in the residual graph.
3. All edges which are from a reachable vertex to non-reachable vertex are minimum cut edges. Print all such edges.

Is there a proof showing this finds the min-cut?

# Answer
> 1 votes
Yes, this is proved in any standard source that proves the max-flow min-cut theorem. You can find one proof on Wikipedia.

---
Tags: linear-programming, network-flow
---


# Question
Title: Bellman Ford may not update distance correctly by termination?
Consider the example shown in the above figure. Let's consider two orders (1) S, A, B and (2) S, B, A for traversing the graph and updating the distance d (numbers in circle are distance d):

1- start with S -\> B = -2, A = 5; Then A -\> D = 7; Then B -\> A = -1. Algorithm terminates.

2- start with S -\> B = -2, A = 5; Then B -\> A = -1; Then A -\> D = 3. Algorithm terminates.

In case 1, D = 7 by the time algorithm terminates (It is not updated by the time the algorithm is over). In case 2, D = -1 and it is correctly updated .

What am I missing here?

Thanks

# Answer
Nevermind. I just figured that bellman ford has nothing to do with vertices. I was using adjacency list as the graph representation and I was mixing things up. In other words, I used

```
for(node: graph.nodes) {
   for (adjNode: child.adj) {
       Relax(child, adjNode);
   }
}

```

Instead, I should have done

```
for (int i=0; i < graph.numberOfEdges() - 1; i++ ) {
  for(node: graph.nodes) {
    for (adjNode: child.adj) {
        Relax(child, adjNode);
    }
  }
}

```

The inner 2 loops simply mean all edges. So the first code traverse edges only once.

For those who happen to make the same mistake as I, remember that bellman ford traverses every edge v - 1 time. Don't think about it from a virtices perspective at all.
> 0 votes

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


title: Upper bound of sum of codewords lengths

text:
# Question
Title: Upper bound of sum of codewords lengths
I need to show that for any binary optimal code for $n$-letter source the following inequality holds: $$\sum\_{i=1}^n l\_i \leq 0.5(n + 2)(n −1).$$ By $l\_i$ denoted the length of the sequence corresponding to the letter $i$.

I know the bound for the average codelength $L\_\* \leq H(X)$. But how to apply it?

Also I know the fact that for any distribution, there exists an optimal prefix code. In my opinion, it's a key fact. So I just need to prove this fact for optimal prefix code.

Please, help me to prove the statement.

# Answer
> 1 votes
Suppose $n\>1$ (the case $n=1$ is a bit degenerate). Consider the Huffman code for your source. The associated binary tree $T$ has $n$ leafs each corresponding to the $n$ letters, every interior node has two children, and $l\_i$ is the depth of the node corresponding to $i$. Then $\sum\_{i=1}^n l\_i$ is the sum of depths of the leaves in $T$.

How large can the sum of depths over all leafs be in a binary tree with $n$ leaves? I claim that the worst case scenario is when the tree $T$ has a path of $n-1$ internal nodes starting at the root (we then have one leaf hanging of of every internal node, except for the lowest internal node on the path which has two leaf children).

Let us see why. Consider some binary tree with $n$ leaves where every internal node has two children. Consider the longest path $P$ of internal nodes which starts at the root, and let $v$ be its lowest node. Without loss of generality I assume that this path always goes to the right child (we can always swap left and right children so this is the case). We know it has length at most $n-1$ (why?). Suppose it has length strictly less than $n-1$. Then there is some node $u \neq v$ on the path such that the subtree rooted at its left child has at least two vertices. If we were to swap that subtree with one of the children of $v$, the total sum of depths of the leaves would strictly increases (why?). This means that the tree we started with didn't maximize this sum.

Now, we have a binary tree consisting of a path of internal nodes of length $n-1$ and one leaf hanging of of every internal node, except for the lowest internal node on the path which has two leaf children. Can you show that in such a tree the sum of depths of the leaves is exactly $n(n-1)/2 + (n-1)$?

---
Tags: information-theory, coding-theory, huffman-coding
---


# Question
Title: Why is finding the sign of the sum of exponentially real numbers in PP?
Aaronson mentions in here that:

> Recall that $\mathsf{PP}$ is the class of problems like the following:
>
> Given a sum of exponentially many real numbers, each of which can be evaluated in polynomial time, is the sum positive or negative (promised that one of these is the case)?

I simply do not see why this problem is $\mathrm{PP}$. The usual definition of $\mathsf{PP}$ that I know is: "If a decision problem is in $\mathsf{PP}$, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than $1/2$. If the answer is NO, the algorithm will answer YES with probability less than or equal to $1/2$."

So does he mean that there is a randomized algorithm that runs in polynomial time and can decide whether the sum of exponentially many real numbers is positive or negative? If so, what's the algorithm exactly? Can someone please explain?

# Answer
Yes, $\mathsf{PP}$ can determine the sign of the sum of exponentially many numbers. The main idea is to represent a number by the difference between the accepting probability and the rejecting probability.

Let $x$ be an input number. For now, assume $-1 \le x \le 1$ and that $2^k x$ is an integer. Consider the following machine: choose a uniform random integer $0 \le y \lt 2^{k+1}$. Accept if $y \lt 2^{k+1} (x + 1)$. Then, the difference between accepting and rejecting probabilities is $x$.

By choosing a random number from the input then accepting the input as above, the overall probability difference is the average of input numbers.

The assumption of the input number range can be relaxed by scaling all numbers by a constant depending on the input number size bound. Note that this bound is a fixed polynomial of the input size by assumption.

If an input number is not a multiple of $2^{-k}$, the number is approximated up to $2^{-k-n-1}$. The total error of the sum will be less than $2^{-k}$, so the answer doesn't change due to the promise of non-zeroness.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: For a regular language L, the language of all words such that no prefix of them are in L is also regular
Prove that for every regular language $L$, the following language is regular:

$L\_{pf}=$ $\\{x \in L | $ no proper prefix of $x$ is in $L\\}$

How should I prove this?

I understood that $L\_{pf}$ is just subset of $L$ and the words inside it are special such that no word is the prefix of other one, is this right ? it's not hard if I have the words in $L$ to prove this, but how to generalise it ?

# Answer
> 1 votes
Let $L' = \\{xx'\\,|\\,x\in L\\,\\&\\,|x'|\>0\\}$. Your language $L\_{pf} = L\setminus L'$, so constructing DFA for $L'$ solves your task, since you can use the closure properties.

Consider a DFA $A$ recognizing $L$. Let $F$ be the set of the final states of $A$. Add a new final state $q\_T$ to $A$ and for every final $q\_i\in F$ and every terminal $s$ add the transitions $(q\_i, s, q\_T)$ to your automaton. Finally, make all the states in $F$ non-final. You get an NFA recognising words with the proper prefixes in $L$, and in order to use the closure properties you need to apply a determinisation algorithm. Afterwards, construct the complement and the intersection.

# Answer
> 1 votes
Take a DFA for $L$. Make every exiting transition from a final state go to a non-final sink state instead. (Proof details left to you)

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


# Question
Title: Prove that every substring closed language L ⊆ {0, 1}* is regular
For $x,y \in \\{0,1\\}^\*$ a language $L ⊆ \\{0, 1\\}^\*$ is called substring closed, if $y \in L$ and $x \preceq y$ ($x$ substring of $y$) implies $x \in L$.

I want to prove that every substring closed language $L ⊆ \\{0, 1\\}^\*$ is regular.

Is it enough to have a $L$ such that just $x$ in it, then prove that $L$ is regular?

# Answer
There are some substring-closed languages that are not regular.

Here is an example. Let $C=\\{01^n0^n1\mid n\ge1\\}$ and $F=\\{f\mid \exists c\in C, f\preceq c\\}$, i.e., $F$ is the language of all substrings of strings in $C$.

* $F$ is substring-closed, since a substring of a substring of string $c$ is also a substring of $c$.
* The intersection of $F$ and the regular language $\\{01w01\mid w\in \\{0,1\\}^\*\\}$ is $C$, a non-regular language. So $F$ is not regular.
> 16 votes

# Answer
The result I know holds for SUBSEQUENCE closed languages, and not SUBSTRING closed. The confusion is frequent between english and french, since "subsequence" is translated into "sous-mot" which means litteraly "subword" or "substring"…

To be clear, $u=u\_1u\_2…u\_n$ is a subsequence of $v=v\_1v\_2…v\_m$ if and only if there exists $1\leqslant i\_1 \< i\_2 \< … \< i\_n \leqslant m$ such that $u = v\_{i\_1}…v\_{i\_n}$.

The proof I know is a bit long. I will add some details if necessary.

For $L$ any language, denote $\widehat{L}$ the set of words that have a subsequence in $L$: $$\widehat{L} = \\{v\in\Sigma^\*\mid \exists u\in L, u\preccurlyeq v\\}$$

The proof goes as such:

* prove that for any sequence $(u\_n)\_{n\in\mathbb{N}} \in \left(\Sigma^\*\right)^{\mathbb{N}}$, there exists two indexes $i\<j$ such that $u\_i\preccurlyeq u\_j$;
* show that for any language $L$, there exists a finite language $F$ such that $\widehat{F} = \widehat{L}$;
* prove that if $L = \widehat{L}$, then $L$ is regular;
* conclude that if $L$ is a subsequence closed language, then it is regular.

Each step uses the result of the previous one.
> 9 votes

---
Tags: finite-automata
---


# Question
Title: Why is binary search using this weird thing to calculate middle?
I noticed that in many books calculation of midpoint for binary search uses this:

```
int mid = left + (right - left) / 2;

```

Why not use

```
int mid = (left + right) / 2;

```

instead?

# Answer
> 22 votes
Because `left + right` may overflow. Which then means you get a result that is less than `left`. Or far into the negative if you are using signed integers.

So instead they take the distance between `left` and `right` and add half of that to left. This is only a single extra operation to make the algorithm more robust.

# Answer
> 8 votes
Suppose your 'low' and 'high' are 16 bit unsigned integers. That means, they can only have a maximum value of 2^16=65536. Consider this, low = 65530 high = 65531

If we added them first, (low+high) would end up being junk since that big a number (131061) cannot be stored in a your 16-bit integer. And so, mid would be a wrong value.

# Answer
> 1 votes
This answer gives a practical example of why the `l + (r-l)/2` calculation is necessary.

In case you are curious how the two are equivalent mathematically, here is the proof. The key is adding `0` then splitting that into `l/2 - l/2`.

```
(l+r)/2 =
l/2 + r/2 =
l/2 + r/2 + 0 =
l/2 + r/2 + (l/2 - l/2) =
(l/2 + l/2) + (r/2 - l/2) =
l + (r-l)/2

```

---
Tags: algorithms, binary-search
---


# Question
Title: Is there a standard or model or taxonomy of programming languages different than machine-threshold-highlevel?
I understand that there are three types of programming languages:

* Machine languages
* Assembly languages
* high-level languages

And that:

* Machine languages have no abstraction
* Assembly language have little abstraction
* High-level languages have much abstraction (data types being the difference maker?)

---

Is there a standard or model or taxonomy of programming languages different than machine-assembly-highlevel?

In other words, is this taxonomy necessary or are there more "sophisticated" or "complex" categorizations?

# Answer
> 1 votes
I've never heard of "threshold languages". I don't think that is a "thing", or at least not a terribly important thing.

Don't worry too much about taxonomies. Taxonomies are mostly not very important. They have value only insomuch as they help you understand more deeply, but real life is more complicated than any taxonomy. It is a waste of your time to try to find the ultimate taxonomy of programming languages or try to find all possible taxonomies. Taxonomies can often be very shallow, and it might be more productive to go deeper and study a few program languages concretely.

Machine languages (by which I assume you mean assembly language?) have nothing to do with machine learning.

# Answer
> 1 votes
As they say, 'all models are wrong, some are useful'. There are as many language taxonomies as your care to invent, depending on what properties you're interested in.

People often talk about functional vs imperative (vs everything else) languages, which is interesting if you have a particular preference in programming style along those lines. Likewise you can split languages according to their type systems - strong vs weak, static vs dynamic. There used to be discussion of 1st, 2nd, 3rd and possibly 4th or 5th generation languages, but that model seems to be falling out of favour. In all of those cases there are languages that don't quite fit into any one category. If you want something a little more objective you can categorise languages by their computational class, but that isn't often very useful because almost all general-purpose languages are in the same class - turing-complete.

Taxonomy is useful when it reflects an underlying structure, but programming languages are (generally) immensly complicated, so any taxonomy that reveals anything really important is likely to be similarly complicated. I find it's usually more useful to talk about specific properties a language has than try to figure out where it fits with respect to all other langauges. It seems to me that people who are particularly into programming language theory tend to be especially not keen on categorising things - I suppose when you work closely with langauges, even programming languages, it becomes difficult to avoid noticing that words don't actually have meanings.

---
Tags: terminology
---


# Question
Title: confusion about Hopcroft-Karp time complexity analysis
From Wikipedia: "Each phase increases the length of the shortest augmenting path by **at least one**: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial ${\displaystyle {\sqrt {|V|}}}$ phases of the algorithm are complete, the shortest remaining augmenting path **has **at least ${\displaystyle {\sqrt {|V|}}}$edges in it".****

Well here my confusion arises. Since Augmenting paths have odd length, how can length of augmenting path be increased by one (results in path of even length -\> not augmenting path)? Shouldn't it be **by at least two**? Then after ${\displaystyle {\sqrt {|V|}}}$ phases of the algorithm are complete, the shortest augmenting path **has at least ${\displaystyle {2\sqrt {|V|}}}$edges in it".** Am i missing something obvious?

# Answer
Yes, you are right that each phase increases the length of the shortest augmenting path by at least two since that length is always odd. (It is always odd because an augmenting path alternates between unmatched edges and matched edges, starting and ending with unmatched edges.)

1. Each shortest augmenting path in the $1$st phrase contains at least $1$ edge.
2. Each shortest augmenting path in the $2$nd phrase contains at least $3$ edges.
3. And so on.
4. Each shortest augmenting path in the $k$th phrase contains at least $2k-1$ edges.

In particular, each shortest augmenting path in each phrase after $\lfloor\sqrt{|V|}\rfloor$ phrases will contain at least $2 \lfloor\sqrt{|V|\rfloor} + 1$ edges.

---

On the other hand, that Wikipedia page is not wrong when it says "Each phase increases the length of the shortest augmenting path by **at least one**". Had it said "... by one", it would have been wrong.

Although the description "at least one" is not as strong as "at least two", it is good enough to help deduce the algorithm "takes a total time of $O(|E|\sqrt{|V|})$ in the worst case.".

Even with the strong version, "at least two", we can not lower that asymptotic complexity, although we could reduce the estimate for the hidden constant factor of that big $O$-notation.
> 1 votes

---
Tags: time-complexity, runtime-analysis, bipartite-matching
---


# Question
Title: Would 256.256.256.256 be considered a valid hostname?
We know an valid IPv4 address is each part not greater than 255, so, will `256.256.256.256` be considered a valid hostname rather an IP address?

I'm just curious how devices in various parts of the internet treat this kind of hostname?

# Answer
As Steve has already pointed out ICANN bans all numeric TLDs. One can find a list of valid TLDs here at IANA.

This could be the end of this question but if one scrolls all the way down on this wikipedia article one can find TLDs which are in fact not managed or tracked by either ICANN or IANA. While Wikipedia is a bit nebulous how they exactly work they provide their respective TLDs so I tried looking up the one that did not have a fixed URL and found something.

You only need a DNSSEC which does not technically require a TLD that is registered with IANA. So you could register 256.256.256.256 as a "legit" URL
> 2 votes

---
Tags: computer-networks
---


title: Runtime Calculation Sort-Algortihm

text:
# Question
Title: Runtime Calculation Sort-Algortihm
I'm really struggling with the following exercise and I would really appreciate your help: I have to calculate the expected runtime of a sort Algorithm with the following variants:

```
Variant   Runtime Behavior
1            n(n-1)
2              n
3            n log(n)

```

Given is, that the runtime for variant 1 is 1000 elements(n) is 20ms. With the calculation for the other elements from variant 1, I have no problem because it's O(n^2) but I really don't know how to calculate the values for variant 2 & 3.

```
Variant    Length n    expected runtime in ms
   1        500          20ms * 0.5^2 = 5ms
   1        4'000        20ms * 4^2   = 320ms
   2        2'000'000    ?
   3        4'096        ?

```

Thanks for your help in advance

Kind Regards

# Answer
> 0 votes
Do not even mention big-O here because that is for asymptotic behaviour and f(1000) doesn’t give you the slightest clue what f(2000000) would be.

You are given that the runtime is f(n) = c x g(n) for three different functions c. Given the value of c x g(1000) for the first function g, you calculate c. Then you substitute c and n for all the cases.

# Answer
> 0 votes
The times are

$$\begin{align}&c\\,n(n-1)\\ &c\\,n\\ &c\\,n\log n\end{align}$$

So as soon as you know $c$, you can compute all cases for any $n$.

> $$c=\frac{20\text{ ms}}{1000\cdot999}.$$

---
Tags: runtime-analysis, sorting
---


# Question
Title: Solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I am trying to solve the recurrence

$T\left(n\right)\\:=\\:3T\left(n-1\right)\\:+\\:3n^2$

I tried method I saw but I do not fully understand which looks like:

$T\left(n-1\right)\\:=\\:3T\left(n-2\right)\\:+\\:3\left(n-1\right)^2$

$T\left(n\right)\\:=\\:3\left\[3T\left(n-2\right)\\:+\\:3\left(n-1\right)^2\right\]\\:+\\:3n^2$

$T\left(n\right)\\:=\\:3\left\[3(3T\left(n−3\right)+3\left(n−2\right)^2)\\:+\\:3\left(n-1\right)^2\right\]\\:+\\:3n^2$

But I am not sure if this is the right way and how do I continue.

# Answer
> 1 votes
Let $S(n) = T(n)/3^n$. Then $$ S(n) = \frac{T(n)}{3^n} = \frac{T(n-1)}{3^{n-1}} + \frac{3n^2}{3^n} = S(n-1) + \frac{n^2}{3^{n-1}}. $$ You take it from here.

# Answer
> 1 votes
You can continue unrolling the recurrence until you see the pattern, and you are able to write a general formula. Then instantiate it in a way that results in writing $T(n)$ as a function of the base case (which I'm going to assume being $T(1)=1$).

$$ \begin{align\*} T(n) &= 3 \cdot T(n-1)+ 3n^2 \\ T(n) &= 3^2 \cdot T(n-2) + 3^2(n-1)^2 + 3n^2 \\ T(n) &= 3^3 \cdot T(n-3) + 3^3 (n-2)^2+ 3^2(n-1)^2 + 3n^2 \\ & \vdots \\ T(n) &= 3^i \cdot T(n-i) + \sum\_{j=1}^{i} 3^j (n-j+1)^2. \tag{\*} \end{align\*} $$

Therefore, choosing $i=n-1$: $$ T(n) = 3^{n-1} \cdot T(1) + \sum\_{j=1}^{n-1} 3^j (n-j+1)^2 = 3^{n-1} + 3^{n+1} \sum\_{j=2}^{n} 3^{-j} \cdot j^2. $$

Since $\sum\_{j=2}^{n} 3^{-j} \cdot j^2 \le \sum\_{j=2}^{\infty} 3^{-j} \cdot j^2$, and the latter series is convergent, you have $T(n)=\Theta(3^n)$.

Notice that the above argument involves some "magic" dots, where you are claiming that after unrolling the recursion $i$ times you get $(\*)$. To get a formal proof you need to proceed by induction.

# Answer
> 0 votes
Now, **Initial Conditions** of Recurrence Relation are **not** given.

Still, We can use **Master Theorem** to find asymptotic bound of given recurrence relation without any initial condition(s).

*(For **Solving the Recurrence Relation**, we need **initial conditions**, which are **not** mentioned in problem)*

If a **Recurrence Relation** is of the Form

## $$T(n)=aT\big(n-b\big)+{f(n)}$$

Then, as per **Master Theorem**, we have **Three Conditions** depending on value of $a$

* If $a=1$
Answer is $O(nf(n))$
* If $a\>1$
Answer is $O(a^{\frac{n}{b}}f(n))$
* If $a\<1$
Answer is $O(f(n))$

In any problem, our main motive is to find $a, f(n)$ and $b$. Moreover we can replace $f(n)$ by it's asymptotic equivalent.

**In Given Problem**

* $a=3$
* $b=1$
* $f(n)=n^2$

Now, $a\>1$ Therefore, Answer is $O(3^{n}n^2)$

## $$O(3^{n}n^2)$$

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


# Question
Title: Is "Mutation" Cheaper than "Calculating Derivatives"?
When it comes to optimizing objective functions belonging to Statistical and Machine Learning Models, there seems to be a general rule:

* High dimensional objective functions with many parameters are "computationally expensive" to optimize

As such, there tends to be two general types of algorithms that are used to optimize objective functions:

* **Gradient Descent:** Gradient Descent tries to find the minimum point (i.e. "optimize") of these objective functions by repeatedly calculating the derivatives of these objective functions, and moving in the direction of these derivatives.
* **Evolutionary Algorithms:** Evolutionary Algorithms (e.g. Genetic Algorithm) also try to find the minimum point of these objective functions, but instead of repeatedly evaluating the derivatives of the function, they work by "randomly moving in many directions at the same time, and probabilistically moving more in those directions that are producing lesser values of the function". This is called "mutation and crossover" - I have greatly simplified the process.

**My Question:** As the number of dimensions in the objective function increases, it becomes more and more computationally expensive to repeatedly evaluate the derivatives of the objective function- since Evolutionary Algorithms do not need to repeatedly evaluate these derivatives, they are said to be "computationally cheaper" compared to Gradient Based Methods. Although there have been no major results established on the convergence of Evolutionary Algorithms (whereas many theoretical results have been established on the convergence of Gradient Based Methods) : **For the exact same objective function - do we know precisely how much cheaper "Crossover and Mutation" costs us compared to "Evaluating Derivatives"?**

There still seems to be some costs associated with "Crossover and Mutation" (e.g. randomly storing, sorting and permuting well-performing "chromosomes" i.e. past solutions) - but do we know how much cheaper this costs us compared to evaluating derivatives (e.g. can we bound this using some Big-O Landau Notation or using Linear vs. Polynomial Time)?

Thanks!

**Extra:** Comparison of Gradient Descent and Genetic Algorithm for Optimizing the Rastrign Function using the R Programming language

**1) Genetic Algorithm**

```
library(GA)

start.time <- Sys.time()

  #define function to be optimized
Rastrigin <- function(x1, x2)
{
  20 + x1^2 + x2^2 - 10*(cos(2*pi*x1) + cos(2*pi*x2))
}

x1 <- x2 <- seq(-5.12, 5.12, by = 0.1)

#run optimization through the genetic algorithm (with constraints)
GA <- ga(type = "real-valued",
         fitness =  function(x) -Rastrigin(x[1], x[2]),
         lower = c(-5.12, -5.12), upper = c(5.12, 5.12),
         popSize = 50, maxiter = 1000, run = 100)

end.time <- Sys.time()
time.taken <- end.time - start.time

```

**Results:**

```
 time.taken

Time difference of 1.266233 secs

GA@solution
                x1          x2
[1,] -4.947186e-06 3.72529e-07

```

**2) Gradient Descent**

```
library(pracma)

start.time <- Sys.time()

Rastrigin <- function(x)
    {
        return(20 + x[1]^2 + x[2]^2 - 10*(cos(2*pi*x[1]) + cos(2*pi*x[2])))
    }

 steep_descent(c(1, 1), Rastrigin)

end.time <- Sys.time()
    time.taken <- end.time - start.time

    time.taken

```

**Results:**

```
time.taken
Time difference of 0.01959896 secs

$xmin
[1] 0.9949586 0.9949586

$fmin
[1] 1.989918

$niter
[1] 3

```

**References:**

# Answer
Well, it sounds like you already know the answer: of course mutating a feature vector is faster than computing the derivative of the objective function. But that doesn't mean that genetic programming is overall more effective or more efficient than gradient descent. It is comparing the running time of one step, but ignores the number of steps you take. As a result, this fact is not very informative for helping us choose an optimization procedure.

(I don't know what second derivatives have to do with the question; gradient descent uses first derivatives, not second derivatives.)

(I've never heard a claim that evolutionary programming is "computationally cheaper" than gradient descent, so I'm not sure where that is coming from.)
> 2 votes

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


# Question
Title: How to find context sensitive grammar for words like ww?
I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the exercises on the format:

$L(G\_1) = \\{wcw^r / w\\, is\\, on\\, \\{0,1\\}^\*\\}$

Where $w^r$ is the reverse word, and whose productions are:

$S \rightarrow c\\, / \\,0S0\\,/\\, 1S1$

But I'm struggling to find CSG of the following language (maybe a difficult one?):

$L(G\_1) = \\{ww / w\\, is\\, a\\, word\\, from\\, \\{a,b\\}^\*\\}$

Almost every type of production that I tried ended up generating $ww^r$ instead of $ww$ such as:

$S \rightarrow aAa\\,/\\,bAb$

$A \rightarrow S\\,/\\, \epsilon$

Is there some kind of production that I'm not considering?

# Answer
> 0 votes
What little you write here suggests you are trying to find a context-free grammar for the language you are having difficulty with. As it happens, that language is NOT context-free, i.e no such grammar is possible for that language. If you are aware of context-sensitive grammars, I suggest you try to find one for that language.

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


# Question
Title: How does JIT compilation and hot-swapping work at the level of individual procedures?
I am trying to understand the lifetime of a procedure, from source code through to being compiled to machine code and being called. I am specifically interested in the context of "live" environments, where (re)compilation can happen at any point during runtime and the new code is seamlessly integrated into an already running program. Good examples of such systems are the SBCL Common Lisp implementation and the live coding language/environment Extempore, meant for live music or otherwise creative performance through live coding.

When a runtime supports the ability to (re)compile a procedure and hot-swap the old version with the new, I assume that involves changing a function pointer to point from one implementation to another. That must mean that the compiled function (in its machine-code form) is simply a sequence of bytes in memory.

That must also mean that the current process must have access to the memory that holds the compiled function. In the case where the compiler lives in the same process, that seems to be straight-forward, as the process already has access to the compiled code data. In the case where the compiler is an external process, the resulting data would somehow have to be loaded. Is that the same thing as dynamically linking with a pre-compiled library object, or is the process a fundamentally different one?

Lastly, what are the steps required to be able to get to a minimal PoC program like the one in the following C++ pseudocode?

```
// The type that the dynamically compiled procedure will have
using FooType = std::function<int(int)>;

// Assuming that the source code is valid,
// this would return a pointer to compiled machine code
FooType* compile_footype_proc(std::string source_code) {...}

int main()
{
    FooType* foo;

    while (!should_exit())
    {
        // Get some source, compile it, and call it
        std::string user_provided_source = getline();
        foo = compile_footype_proc(user_provided_source);
        cout << "The result is: " << foo(5) << endl;
    }
    return 0;
}

```

Any resources to learn more about this?

# Answer
> -1 votes
You asked two questions. The usual rule is to ask only one question per post, so I'll answer your first question.

JIT compilers normally run in the same process as the code that has been compiled, so the issues you identify with loading/linking don't normally arise.

---
Tags: compilers
---


# Question
Title: What are the technical reasons programs in C and C++ do not show runtime errors, but programs in Rust and Golang do?
When a runtime error occurs with a program in language likes C or C++ using GCC/G++, it just crashes the process. When it occurs with a program in language like Rust or Golang, a detailed error message will be given.

# Answer
It's a matter of design.

When a program runs (whether it is compiled or interpreted, it does not really matter), it is executed in an enveloping runtime environment. When an error occurs, the enveloping runtime environment may or may not be equipped with figuring out how exactly the program got to the error.

Two possible design choices are:

1. Keep the runtime environment minimal and do not bother printing out nice error messages when the program crashes. If the programmer wants to figure out what happened, they can run a debugger.
2. Be friendly to the programmer and equip the program with tracebacks and printing of informative error messages. This makes the runtime environment larger, and possibly incurs a small cost in efficiency and memory conspumption, but it also shortens development time, as one can often see directly from the error message what needs to be fixed.

The first choice made more sense decades ago, when computers had little memory and CPU time was more valuable than programmer time. The second choice makes more sense nowadays, when development time is precious and it usually does not matter if an executable contains extra code for handling errors.
> 3 votes

# Answer
If you compile with debugging information and have a debugger installed, the debugger will show you the line that caused the crash in context, the stack, the status of other threads, the values of local and global variables and any heap objects they may point to, etc. You may be able to set a breakpoint before the error location, restart the process, and single-step to see how the error comes about. It's much more useful than a traceback.

Printing a traceback on failure amounts to copying a limited subset of the debugger into each compiled executable. It's possible, but there's no tradition of doing it in the C and C++ world. It's assumed that if you know how to read tracebacks, you'll use the debugger.

C and C++ implementations often do show error messages (without tracebacks) for assertion failures, and sometimes for some other errors like division by zero, if there's no debugger to handle them.
> 3 votes

---
Tags: programming-languages
---


# Question
Title: What's the time complexity of $\sum_{i=1}^k {N\choose i}$
I created an algorithm that is doing $\sum\_{i=1}^k {n\choose i}$ inference calls to an ML model. Let's assume the inference calls are constant. Can I upper bound this without the binomial coefficient somehow? I would say its $\mathcal{O}\left(k {n\choose i}\right)$ but that's not a very intuitive expression. Is this expression NP-complete? It's been a while since I last did theoretical stuff, any hints are appreciated.

# Answer
$\sum\_{i=1}^n \binom{n}{i}$ is not an algorithm nor a problem, therefore it does not make sense to ask about its time complexity or whether it is NP-complete.

That said, $\sum\_{i=1}^n \binom{n}{i} = \Theta(2^n)$, which is probably what you were looking for. Indeed, $\sum\_{i=1}^n \binom{n}{i} = \sum\_{i=0}^n \binom{n}{i} - \binom{n}{0} = 2^n - 1$.
> 2 votes

---
Tags: time-complexity, upper-bound
---


# Question
Title: Questions about compilers and machine code
* When it is said that machine code is specific to a machine, is it specific to an architecture, or is it specific to a machine? Do two identical processors require different machine code? My guess is that people are referencing instruction sets/architecture when they say machine code is specific to a machine?
* If they are referencing instruction sets; how does a compiler know which instruction set to create machine code for? -Ultimately -- if I compile a C program on my computer, generating machine code, to what extent is that machine code usable on other machines?

Like, if one of the points of compiled languages is that you don't have to share the source code, how does that even work? Don't you have to, at a minimum, compile for each available architecture?

edit: Sorry if these questions seem easily googleable, believe me I have tried. It's at the point where I need to just start asking people things, which is why I've made this account.

# Answer
> 4 votes
In principle, identical processors share the same instruction set. Anyway, on modern machines some instructions can be enabled or disabled through the BIOS (UEFI) by the user.

The successive processor generations in a given architecture have an evolving instruction set, usually keeping downward compatibility, but not always.

So in principle code compiled for an old processor should still run on a newer.

For compilers to cope, there are two strategies:

* compile-time compatibility lets the developers specify the processor family that should be supported, leading to different code generation; a substantial historical example is that of the transition from 32 to 64 bit systems.
* run-time compatibility relies on querying the processor itself during program execution to know which instructions are actually supported, and switch to the relevant code to optimize the utilization of the hardware capabilities; this means that the generated code will include several instances of some functions.

# Answer
> 0 votes
For example for gcc and clang, you pass an argument -arch=x86, -arch=ppc, -arch=arm, or with x86\_64, ppc64 or aarch64. The compiler does what it can.

(The names might be slightly wrong).

---
Tags: compilers, c
---