# Question
Title: what is the significance of the word "Sub-problems" in Greedy Method?
With respect to Dynamic Programming we make a statement that :

> Greedy algorithm have a local choice of the sub-problems whereas Dynamic programming would solve the all sub-problems and then select one that would lead to an optimal solution.

Now in Dynamic Programming we have some problem with recursive nature which we solve by solving the sub-problems and then obtain the global optimum but in case of Greedy approach we do not solve the problem in any recursive nature rather we find a feasible solution at every stage with the hope of finding optimal solution.

So I am unable to get the notion of sub-problems in case of Greedy Approach .

# Answer
Here is a concrete example, the problem of *Set Cover*:

> **Set Cover**
>
> Input: Sets $S\_1,\ldots,S\_m$ whose union is $U$
>
> Output: Minimal-size subset of $\\{S\_1,\ldots,S\_m\\}$ whose union is $U$

The well-known greedy algorithm for this problem (which gives a $\ln n$ approximation) proceeds as follows:

* While $U \neq \emptyset$:
    1. Add to the solution the largest set $S\_i$.
    2. Remove all elements of $S\_i$ from all sets and from $U$.

Having chosen a set $S\_i$, we are effectively moving to another Set Cover instance, in which the sets are $T\_j := S\_j \setminus S\_i$, and the universe is $V := U \setminus S\_i$.

This new instance is the sub-problem mentioned in your statement. The greedy choice — largest set — is the local choice mentioned in your statement.

To check your understanding, show that this view is appropriate for other well-known greedy algorithms such as Huffman encoding and the greedy algorithm for interval scheduling.
> 1 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


title: Interpretation of for loop.

text:
# Question
Title: Interpretation of for loop.
> for every j != i in {0,....,n-1}

How to interpret this for loop? I never seen this type of definition of for loop.

Is it like - **`j=0 to n-1; j !=i ; ++j`**

# Answer
> 18 votes
Here is the probable interpretation:

> for every $j \neq i$ in $\\{0,\ldots,n-1\\}$:
>
> code

should be interpreted as:

> for every $j$ in $\\{0,\ldots,n-1\\}$:
>
> if $j \neq i$:
>
> code

This is similar to the way this kind of statement is interpreted in mathematical text.

It is also possible that the roles of $i$ and $j$ should be switched — this should be clear from context, and it's an ambiguity that also exists in mathematical texts.

As mentioned in Evil's answer, if neither $i$ nor $j$ has been defined, then the interpretation is probably

> for every $i,j$ in $\\{0,\ldots,n-1\\}$:
>
> if $i \neq j$:
>
> code

# Answer
> 13 votes
There is another interpretation, both $i, j$ might be variables, in that case it is double loop:

> for every $j$ in $\\{0,\ldots,n-1\\}$:
>
> for every $i$ in $\\{0,\ldots,n-1\\}$:
>
> if $j \neq i$:
>
> code

Simply reading it out loud helps only if we know beforehand if $i$ is fixed variable or another counter, so there is context missing.

# Answer
> 6 votes
Just read it out loud. "For every $j$ that is not equal to $i$, in $\\{0, \dots, n-1\\}$."

In my opinion, it would be better to have written "For every $j\in\\{0, \dots, n-1\\}\setminus\\{i\\}$."

---
Tags: programming-languages
---


# Question
Title: Context free Grammar for this context free language
How can I create a context free grammar for the language $\\{p^2q^mpr^nq^{2n+m}| m,n \ge 0\\}$, where $\Sigma = \\{p,q,r\\}$?

# Answer
> 2 votes
When trying to come up with a grammer for this language, there are several things one must make sure every word generated by it satisfies, including:

1. It starts with a double $p$
2. Every addition of a $q$ that comes before the middle $p$ also adds a $q$ at the end
3. Every addition of an $r$ after the middle $p$ also adds 2 $q$'s at the end
4. There is only a single middle $p$ between the $q$'s and the $r$'s

Your answer satisfies condition 1, but mixes up 2 &3 and violates 4. Therefore, my corrections to it result in the following grammer: $$S\rightarrow ppA$$ $$A\rightarrow qAq|pB$$ $$B\rightarrow rBqq|\varepsilon$$ Also, be careful with mixing up lowercase and uppercase letters!

# Answer
> -1 votes
I've come up with

$$ \begin{align} S&\rightarrow PPX \\ X&\rightarrow QXQQ\mid Y \\ Y&\rightarrow PYR\mid \epsilon \end{align} $$

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


# Question
Title: Updating an MST $T$ when the weight of an edge not in $T$ is decreased
> Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$.
> Now we *decrease* the weight by $k$ of an edge $e$ which does *not* belong to $T$.
>
> How to efficiently update $T$ to make it an MST (denoted $T'$) of $G'=(V,E,w')$, where $w'$ is the same as $w$ except that $w'(e) = w(e) - k$?

The ***algorithm*** for updating $T$ to $T'$ is easy: Adding $e$ to $T$ creates a cycle $C$ in $T$. Let $e'$ be a maximum-weighted edge in the cycle $C$. If $w(e') \> w’(e)$, then $T' = T \cup \\{e\\} - \\{e'\\}$ is the MST as desired. Otherwise, $T' = T$.

I have difficulty in ***proving its correctness*** by contradiction. Suppose $T''$ is a spanning tree of $G'$ and $w'(T'') \< w'(T')$.

* $e \notin T''$: we have $w(T'') = w'(T'') \< w'(T') \le w(T)$. Contradicts with the fact that $T$ is an MST of $G$.
* $e \in T''$: ***I am stuck here.***

---

***Two Notes:***

* The accepted answer here to the same question is too general for me to follow.
* I prefer to proofs which do not rely on any concrete MST algorithms, such as Kruskal's and Prim's algorithms. However, you don't need to prove it by contradiction or separate the two cases $e \notin T''$ and $e \in T''$ as I did.

# Answer
> 3 votes
Let $T$ be a minimum spanning tree of $G$. Let $e$ be the edge we modify to get $G'$, and let $T'$ be the tree computed according to the algorithm. We know that weight of $T'$ is less than or equal to the weight of $T$.

Firstly, $T'$ is a tree - we create exactly one cycle in the algorithm, and break it, so we have no cycles in $T'$.

Secondly $T'$ is a *spanning* tree of $G'$. Let $e'$ be the edge removed and $e''$ be the edge added in the algorithm (we have either $e'' = e'$ or $e'' = e$) . To be a spanning tree, we must have a path between every pair of vertices $u$, $v$ using only edges of $T'$. Suppose that in $T$ (which is definitely a spanning tree), the path from $u$ to $v$ did not involve $e'$, then the same path exists in $T'$. Alternatively, suppose that it did use $e'$, then there is a path (without loss of generality) from $u$ to one endpoint of $e'$ and from the other endpoint of $e'$ to $v$. There is also a path from one endpoint of $e'$ to the other endpoint via $e''$ (around the cycle), all within $T'$. Then we can construct a path from $u$ to $v$ via $e''$ in $T'$ by merging these three paths and removing the overlap (although a walk is sufficient for connectivity).

Now, the important part, we wish to prove that $T'$ is a *minimum* spanning tree for $G'$.

**Case 1**: The algorithm does not add $e$ to the tree. In this case $T' = T$. Suppose that there is a minimum spanning tree $H$ for $G'$ that is different to $T'$. If $H$ has the same weight as $T'$, we're done. Now suppose for contradiction that the weight of $H$ is less than the weight of $T'$. There must be some edge $e'$ of lowest weight that is in $H$ but not in $T'$ (there must be some edge that does better, otherwise $G$ would not be of lower weight than $T'$, moreover we can assume that the edge that does better is the lowest weight edge that's not in $T'$ - we can take any $H'$ that is a lower weight tree than $T'$ and look at the candidate for $e'$, if it is not smaller than any edge in its cycle, then either $H'$ is not an MST, or we can create a new $H'$ where we swap the $e'$ for some edge of $T'$, this process must terminate with an edge $e'$ which has the property that it is the edge that does better).

1. If $e' \neq e$, then consider the tree obtained by adding $e'$ to $T$ (note, not $T'$), and removing the highest weight edge on the cycle formed. This new tree has weight less than that of $T$ and is a spanning tree for $G$, contradicting the fact that $T$ is an MST for $G$ - so we know this can't happen.
2. If $e' = e$, consider the cycle formed by adding $e' = e$ to $T'$ (i.e. the one the algorithm considered). All other edges in the cycle have lower weight than $e'$ (otherwise the algorithm would've included $e$ as an edge), and hence must be in $H$ (as $e'$ is the lowest weight edge that is not already in $T'$), but then $H$ must contain a cycle, so isn't a tree and we have a contradiction.

**Case 2**: The algorithm adds $e$ to $T'$. Let $x$ be the edge in $T$ that is removed by the algorithm (and hence not in $T'$) Again assume we have another MST $H$ as before. If the weight is the same, we're happy. So assume for contradiction that $H$ has lower weight, and as before $e'$ is the lowest weight edge in $H$ that's not in $T'$. We can make similar arguments as before with $x$.

1. If $e' \neq x$, (note also that $e' \neq e$), then we can improve $T$ as before, but we know that $T$ is an MST, and recalling the property that we can assume $e'$ has lower weight that at least one edge in the cycle its addition induces, this gives a contradiction and $H$ can't exist.
2. If $e' = x$, then again $e'$ must have higher weight than all the other edges in the cycle, hence $H$ must contain all these edges and $H$ is not a tree, and we derive a contradiction.

So in every case we derive a contradiction, therefore there can be no spanning tree of lower weight that $T'$, hence $T'$ is a minimum spanning tree for $G'$.

# Answer
> 3 votes
Let $S$ be a spanning tree of an edge-weighted graph $G$. We call $S$ a local-minimum spanning tree of $G$ if for any edge $e$ not in $S$, $e$ is a heaviest edge in the cycle created when we add $e$ to $S$.

Let me introduce a theorem about minimum spanning tree (MST).

### A spanning tree is an MST if and only if it is a local-minimum spanning tree.

A proof of the above theorem by the OP herself/himself does not rely on any concrete MST algorithm.

In another proof of the above theorem but stated differently, you can also read the reason why such a spanning tree is called "local-minimum".

The above theorem enables us to verify an MST edge by edge although MST is defined with respect to all edges together.

---

Once we are armed with the above theorem, it becomes easy to prove the correctness of the algorithm in the question. It should be, in fact, easier to construct a proof by yourself than reading the rigorous proof below.

### A simple proof of the algorithm in the question

Let us reuse all notations in OP's definition of the algorithm.

Note that $T$ is a local-minimum spanning tree of $G$. To prove $T'$ is an MST of $G'$, we will show $T'$ is a local-minimum spanning tree of $G'$. There are two cases.

* when $w(e')\leq w'(e)$ and $T'=T$.

Since the only difference between $T$ in $G$ and $T'$ in $G'$ is the weight of edge $e$, we need to check $e$ only. Since $e'$ is a heaviest edge in $C$ with $w$, the condition $w'(e) \geq w(e')$ means that $e$ is a heaviest edge in $C$ with $w'$. We are done in this case.
* when $w(e')\gt w'(e)$ and $T' = T \cup \\{e\\} - \\{e'\\}$.

1. Let us consider $e'$. The cycle created when we add $e'$ to $T'$ is also $C$. Since $e'$ is a heaviest edge in $C$ with $w$, the new weight of $e$, $w'(e) \lt w(e')$ means that $e'$ remains a heaviest edge in $C$ with $w'$.
    2. Now let $f\neq e'$ be an edge not in $T'$. Let $D$ be the cycle created when we add $f$ to $T$. Since $T$ is an MST of $G$, $\\,f$ is a heaviest edge in $D$ with $w$.
        + If $e'\notin D$, $D$ is also the cycle created when we add $f$ to $T'$. As $w$ and $w'$ are the same on $D$, $\\,f$ remains a heaviest edge in $D$ with $w'$.
        + Now suppose $e'\in D$. If we replace $e'$ with all edges in $C$ other than $e'$, we get from $D$ a new cycle $D'$, which is the cycle created when we add $f$ to $T'$. Since $e'$ is a heaviest edge in $C$ with $w$, $f$ remains a heaviest edge in $D'$ with $w$. Since the only difference between $w$ and $w'$ is their values on $e$, for which we have $w'(e) \lt w(e') \leq w(f) = w'(f)$, we see that $f$ remains a heaviest edge in $D'$ with $w'$.
    3. Combining step 1 and 2, we are done in this case.

Note that both the algorithm and the proof above work well regardless whether the weight of $e$ is decreased, intact or increased.

### On the equal weights of edges

It is a common practice to assume distinct weights of all edges for the sake of clearer exposition. However, this post works well with possibly equal edge-weights. In particular, we have been referring to "a heaviest edge" but never "the heaviest edge".

---
Tags: algorithms, graphs, correctness-proof, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Creating Best Clusters of Objects Based on Distance Between Them
I have an array of images. And, there is a function that calculates the distance between two images.

I wish to cluster the images based on this distance. So the clusters contain images that are all at short distance to each other.

So only the distance between two images can be used to form the clusters. An image has **no** usable properties on their own. As many common clustering algorithms expect objects to have usable properties, it seems I can use these algorithms.

To limit computational complexity, I've introduced a few thresholds to decide if two images may end up in the same cluster:

* calculated distance (I want to optimize for shortest distance, but above a certain distance, images are not close enough to ever share a cluster)
* input array distance (e.g. an image at index 23 may only cluster with images up to index 123)
* creation data interval (images created more than N hours apart, may not share a cluster)

Some details:

* There can be up to 100k images.
* Roughly 25-50% of images will be 'unique' and do not end up in a cluster with others. Of the remainder, most will be expected to end up in clusters with a size below 10, with 5% outliers above that.
* The maximum cluster size is something I want to set somewhere between 10 and 50.

Given the above and the nature of the image set, a graph (image: edge, calculated distance: vertex) would consist of disjoint parts consisting of up to a few hundred images. So the algorithm needs to be able to cluster sets of well below 1000 images.

The clusters must be optimised for distance, such that closer images end up together in a cluster. I'm aware that parameters like minimum and maximum cluster size would be needed; it's a play between creating a few large clusters with a higher maximum distance, or more smaller clusters with images that are closer together.

What kind of algorithm(s) could I use?

# Answer
You *can* use Cluster Edge Deletion, however, the problem is NP-hard.

Create a graph where the vertex set is the set of your objects, and you create an edge between two objects if the distance is at most the threshold.

Now, the Cluster Edge Deletion problem is to find the set with fewest edges to delete such that the remaining graph is a cluster graph (a graph whose connected components are cliques). In this solution, every object belongs to a cluster in which the distance to every other object is bounded by the threshold.

Alternatively, you can run $k$-means (with increasing $k$) until you're satisfied with a solution. Take note that the $k$-means algorithm is randomized and gives an approximate solution (as also this problem is NP-hard), so you might want to run the algorithm several times per $k$.
> 1 votes

# Answer
There are several standard clustering algorithms you could try, including k-means and hierarchical clustering. The additional restrictions you have should make both implementable in a reasonably efficient way. In particular, build a graph with one vertex per image, and an edge between each pair of images that meet all the thresholds. Note that this can be done using at most $100 \times 100,000$ distance computations: you only need to compare each image to the 100 that precede it.
> 1 votes

---
Tags: clustering
---


# Question
Title: Is the credit assignment problem a well-posed one?
Credit assignment is the process of assigning credit (or blame) to a particular move in a sequence of moves (temporal credit assignment) or to a particular node (structural credit assignment) among many nodes, for example, in a network.

My question is somewhat philosophical: Does it even make sense to speak of credit assignment as a problem to be solved?

Take the example of a football (soccer) team. (I read in a paper that robo-soccer teams face a version of the credit assignment problem). However, even in the case of a real-life soccer team composed of humans players, it is virtually impossible to separate the performance of an individual in scoring a goal from the contribution of the rest of the team *in the most general case*. If quantifying and assigning credit to players is so difficult, does it even make sense to try to assign credit to nodes in a complex system, with many pieces that are interacting in subtle ways?

# Answer
> 1 votes
If you can do it well, it is useful. If you can accurately identify which move was to blame for bad outcomes -- or which one is to credit for good outcomes -- that is useful in helping you learn to make better moves. I'll let you decide whether that's enough for it to make sense to speak of it as a problem to be solved. I'm not very knowledgeable about philosophy, so I don't know whether that qualifies.

# Answer
> -1 votes
It depends on what the system is used for. I mean, soccer (football) has a strict set of laws and limited number of moves whereas systems with limited laws and a high number of moves credit becomes more important. Like for example, with StackExchange: https://meta.stackexchange.com/questions/17831/whats-the-incentive-to-answer-questions

---
Tags: reinforcement-learning, philosophy
---


title: What is hardware trap?

text:
# Question
Title: What is hardware trap?
Since it's called a trap I consider it caused by software, so why it's called a hardware trap? And how does it work?

# Answer
https://en.wikipedia.org/wiki/Trap\_(computing)

It is called a hardware trap because the mechanism of triggering it, and handling it, is embedded in the hardware itself and it cannot be \[fully\] controlled/disabled in software.
> 3 votes

---
Tags: operating-systems
---


# Question
Title: What are some comparative studies on program termination verification tools?
Comparative studies of tools like AProver, 2LS

# Answer
As mentioned by nekketsuuu, SV-COMP has a termination category, and the Termination Competition has been going on for quite some time (there is some overlap).

It depends on what kind of termination you are interested in. This paper on AProVE gives an overview of that tool, which covers many of the techniques involved in general program termination analysis and types of programs that can be handled, though it does not really analyze the comparative strengths of different tools.

Sadly, I'm not aware of any modern overview paper that does this, which is unfortunate. The tool description papers of the competition participants for your category of choice would be a good place to start.
> 2 votes

# Answer
How about looking at Competition on Software Verification (SV-COMP) held at TACAS? There is a category of termination. For example, here is a link to SV-COMP 2017.
> 1 votes

# Answer
As the other answerers I'm not aware of such a study although it would be nice to have some. Instead, I would point to several benchmarks that the authors of these tools produce. A comparative study should benefit from it. I will set this as a community wiki so that other people can add references to other benchmarks/studies:

**Benchmarks**

Stainless verification framework

Termination Problems Data Base

**Comparative studies**
> 1 votes

---
Tags: software-verification
---


# Question
Title: How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$?
I'm asking this, because in every exercise I check if I can relate it to one of the things I know,

like:$A\_{TM}$, $\overline{A\_{TM}}$, ${HALT\_{TM}}$,$\overline{HALT\_{TM}}$, $E\_{TM}$, $\overline{E\_{TM}}$, $ALL\_{TM}$

But in many cases I can not find the connection and then get stuck with the question.

For example:$$L = \big\\{ \langle M \rangle \mid M \text{ is TM and }M \text{ accepts only palindromes}\big\\}$$ I know the solution to this question, I am not asking for a solution to this.

I want to understand the line of thought so that I will begin to solve questions like this. What are the guidelines?

What is the first thing that should come to my mind with such questions?

My initial thought was always to look for words like `accepts` to associate it to $A\_{TM}$, $\overline{A\_{TM}}$ or `halts` to associate it to ${HALT\_{TM}}$,$\overline{HALT\_{TM}}$ but that does not help me so much.

My questions are not only related to the example but to the questions in general of this kind, that I need to determine.

Thanks.

# Answer
> 1 votes
The line of thought that I find the most fruitful is: try to come up with a (semi)algorithm for the problem. If you succeed, great. If you don’t, it’s probably impossible.

Let’s apply it to your problem: determining whether a Turing machine accepts only palindromes. The trivial way to solve this problem is to go over all non-palindromes, and check whether your Turing machine accepts any of them. This shows that your problem is co-r.e., since you can enumerate all Turing machines which accept some non-palindrome.

There doesn’t seem to be a matching algorithm for enumerating Yes instances of your problem, so your problem is probably not r.e. Indeed, Rice’s theorem shows that your problem isn’t recursive, and so we can deduce that it is not r.e.

With a bit more work, you can show that your problem is $\Pi\_1$-complete, that is, every problem in co-r.e. can be (effectively) reduced to it. To show this, it suffices to show a reduction from the non-halting problem to your problem. In this problem, given a machine $M$ and an input $x$, the goal is to determine whether $M$ does not halt on $x$. Given an instance $\langle M,x \rangle$ of this problem, construct a machine $M’$ which goes into an infinite loop (or rejects) unless the input is $10$ (an arbitrary non-palindrome), in which case it simulates $M$ on $x$, and then accepts (if $M$ ever halts). The new machine $M’$ accepts only palindromes if and only if $M$ doesn’t halt on $x$.

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


# Question
Title: Book example Profit maximization understanding
This may not be the right place to ask this kind of question and it also sound a bit stupid, but please help me understand better. I am not able to to see why on page 192 "which imposes another constrain x2 +3 x3\<= 600" come up? With the fact that Nuit and Luxe require the same packing machinery. Please take sometimes to read the book, (I understand it sounds like I am too lazy to post the more completed question, it does require reader to understand a bit more than usual question to help). Here is the link to the book

# Answer
I am not sure if this is helpful, but I think that the quote is simply introducing an additional constraint to the extension of the two-dimensional problem (two unknowns) presented on p.189 to a three-dimensional problem (three unknowns) introduced at the bottom of p.192.

The offered interpretation of the additional constraint is that it reflects a constraint of the 'packaging machine', namely the machine can package at most 600 items (inclusive). Also, the quote informs the reader that for every package related to 'Nuit' ($x\_2$) the machine can process three times as much 'Luxe' ($3x\_3$).

I don't think there's anything more to it. Hope this helps!
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Do any programming languages use general recursive functions as their basis?
This is a naïve and, therefore, possibly malformed question, so apologies in advance!

My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming languages. Similarly, the lambda calculus is the foundation for functional programming languages.

I have recently learnt that the Church-Turing Thesis also shows mutual equivalence with a third model of computation: general recursive functions. Are there any programming languages that use this as their model of computation? If not, is there a technical reason why; i.e., besides "No one's tried yet"?

# Answer
> 45 votes
Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-recursive functions due to valid reasons.

General recursive (i.e., $\mu$-recursive) functions are significantly less *expressive* than lambda calculi. Thus, they make a poor foundation for programming languages. You are also not correct that the TM is the basis of imperative PLs: in reality, good imperative programming languages are much closer to $\lambda$-calculus than they are to Turing machines.

In terms of computability, $\mu$-recursive functions, Turing machine, and the untyped $\lambda$-calculus are all equivalent. However, the untyped LC has good properties that none of the other two have. It is very simple (only 3 syntactic forms and 2 computational rules), is highly compositional, and can express programming constructs relatively easily. Moreover, equipped with a simple type system (e.g., System $F\omega$ extended with $\mathsf{fix}$), the $\lambda$-calculus can be extremely expressive in that it can express many complex programming constructs easily, correctly and compositionally. You can also extend the $\lambda$-calculus easily to include constructs that are not lambdas. None of the other computational models mentioned above give you those nice properties.

The Turing machine is neither compositional nor universal (you need to have a TM for each problem). There are no concepts of "functions", "variables" or "composition". It is also not exactly true that TMs are the basis of imperative PLs - FWIW, imperative PLs are much, much closer to lambda calculi with control operators than to Turing machines. See Peter J. Landin's "A Correspondence Between ALGOL 60 and Church's Lambda-Notation" for a detailed explanation. If you have programmed in Brainf\**k (which actually implements a rather simple Turing machine), you will know that Turing machines are not a good idea for programming.

$\mu$-recursive functions are similar to TMs in this respect. They are compositional, but not nearly as compositional as the LC. You also just can't encode useful programming constructs in $\mu$-recursive functions. Moreover, the $\mu$-recursive functions only compute over $\mathbb{N}$, and to compute over anything else you'd need to encode your data into natural numbers using some sort of Gödel numbering, which is painful.

So, it is not a coincidence that most programming languages are somehow based off the $\lambda$-calculus! The $\lambda$-calculus has good properties: expressiveness, compositionality and extensibility, that other systems lack. However, Turing machines are good for studying computational complexity, and $\mu$-recursive functions are good for studying the logical notion of computability. They both have outstanding properties that the $\lambda$-calculus lacks, but in the field of programming $\lambda$-calculus clearly wins.

In fact, there are many, many more Turing complete systems out there, but they lack any outstanding property whatsoever. Conway's Game of Life, LaTeX macros, and even (some claim) DNA are all Turing complete, but no one programs (i.e. do serious programming) with Conway or studies computational complexity using LaTeX macros. They simply lack good properties. Turing complete *per se* is nearly meaningless when it comes to programming.

Also, many non-Turing complete computational systems are very useful when it comes to programming. Regular expressions and yacc are not Turing complete, but they are extremely powerful in solving a certain class of problems. Coq is also not Turing complete, but it is incredibly powerful (it's actually considered much more *expressive* than its Turing complete cousin, OCaml). When it comes to programming, Turing completeness is not the key, as many (close to) useless systems are uninterestingly Turing complete. You're not going to claim that Brainf\**k or Whitespace are more powerful programming languages than Coq, are you? An *expressive* foundation is the key to powerful programming languages, and that's why modern programming languages are almost always based on the $\lambda$-calculus.

# Answer
> 5 votes
Typing `µ-recursive function programming language` in Google led me to this GitHub repo, so the answer to your question is:

Yes, and it's called **myopia**

It's written in Haskell, by the way.

---
Tags: programming-languages, mathematical-foundations, church-turing-thesis
---


# Question
Title: Minimum spanning tree with two minimum edge weights
Given an undirected weighted graph $G$ with two edges of minimum weight and all other edges are distinct. Does G have a unique minimum spanning tree?

I know the proof for if all edge weights are distinct (it does give a unique MST) and I am thinking that if two edges of minimum weight are in $G$ then I should be able to show a counter example. But so far I have not been able to produce one.

So my question is does it give a unique MST if the graph $G$ contains two minimum weight edges?

# Answer
Yes $G$ has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After adding the two minimum edges, you can't have a cycle, therefore both are in the MST.

Edit: As Paresh pointed out, this is not a complete proof, since there may be MSTs which cannot be produced by Kruskal's after permutating equally weighted edges in the sorted list. But Kruskal's is in fact able to produce any MST. Proof.
> 5 votes

# Answer
Yes.

To build a minimum spanning tree you will order edges by weights from smallest to largest. An edge is included as long as it does not make a cycle. If there are two minimum weight edges, then these edges are first and second. The first two edges do not make a cycle. Therefore, since all other edges are distinct, then you will end up with one minimum spanning tree. That is, whatever order of selecing the two minimum edges, the tree would be the same. QED.

A bit of clarification: Whether you are using Prim or Kruskal, the same result applies. Here is why. Kruskal order ALL edges ascendingly. In Prim, at each node $v$, the edges are ordered ascendingly in this manner $(v,u)$ where $u$ is a neighbor of $v$. Whenever an edge $(u,v)$ is selected, the edge $(v,u)$ is deleted \[note they are the same since it is an undirected edge\]. The edge with smallest minimum weight $e \_{min(1)} =(x,y)$ is the first in the global ordering. It also should be the first at node x and y otherwise it is not the smallest. The argument applies to the second minimum edge $e \_{min(2)}$.

In general, Kruskal follows a total order of edges, while Prim uses a partial order of edges.
> 3 votes

# Answer
Yes.

Here is a proof that does not rely on any algorithm such as Kruskal's algorithm or Prim's algorithm.

For any cycle $C$ in $G$, $C$ has 3 or more than edges, one of which must weigh differently from the (global) minimum weight. So the maximum edge-weight of $C$ is not the global minimum weight. Since except two edges of the global minimum weight, all other edges in $G$ weigh distinctly, $C$ must have a unique heaviest edge. Let $e$ be an arbitrary edge in $G$. If $e$ is not the unique heaviest edge in any cycle, then it is not a heaviest edge in any cycle. According to the characterization by "extreme cycle edge" of uniqueness of MST, $G$ has a unique MST.
> 0 votes

---
Tags: graphs, spanning-trees
---


title: Algorithm to compute maximum of blocks

text:
# Question
Title: Algorithm to compute maximum of blocks
We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total).

One algorithm is to compute the maximum of every $n/2$ consecutive numbers separately. This leads to an $O(n^2)$ algorithm.

Can we do better? Perhaps using a heap or an appropriate data structure?

# Answer
> 4 votes
Here some ideas:

Put the numbers in an array and repeat it. This allows to view the problem in a different light. Now you just have to compute a bunch of range maximum queries. RMQ is a well studied topic, and there are countless efficient solutions:

* Sqrt-Decomposition: $O(N)$ preprocessing, $O(\sqrt{N})$ per query.
* Segment Tree: $O(N)$ preprocessing, $O(\log N)$ per query.
* Sparse-Tables: $O(N \log N)$ preprocessing, $O(1)$ per query
* Farach-Colton and Bender: $O(N)$ preprocessing, $O(1)$ per query
* and many more

Most of them are of a more general nature, e.g. they allow modifying the array. And some (like Farach-Colton and Bender) are not very pleasant to implement. This is probably way too much for your application.

So here I want to present a very simple and short data structure, which is still capable to compute the maxima in optimal $O(n)$ time: the **Max-Queue**.

A **Max-Queue** is a queue, that functions like a normal queue (you can insert values at one end and remove values at the other), and also can compute the maximal value in $O(1)$ time. CP-algorithms.com describes a few possible implementations of min-queues, which are just the dual data structure. I'll use method 2 here:

The queue internally keeps track of how many items we have pushed and popped already, and stores the elements as pairs `(value, push_index)`. E.g. pushing the elements `[1, 6, 2, 4, 3]` leads to the queue: `[(1,0), (6,1), (2,2), (4,3), (3,4)]`. And one thing more. It will do this in such a way, so that we only store elements in a monotone decreasing way, so that it stores the maximum at the beginning, and so that after popping the maximum the next maximum is still at the beginning. This would give us the queue structure: `[(6,1), (4,3), (3,4)]`. This allows looking at the maximum in $O(1)$ time (just look at the first element), inserting in amortized $O(1)$ time (you need to delete all elements from the back that are smaller than the new value), and popping in $O(1)$.

A Min-Queue implementation can be found under the link above. Each method consists of only 1-4 lines of code.

With the Max-Queue we can find all desired maxima in $O(n)$ time. We insert the first $n/2$ numbers in the queue, and print the maximum. The pop a value, insert the next one, and print the maximum. Repeat until you printed $n$ values.

# Answer
> 3 votes
This is a variation of a problem called `sliding window maximum`. A linear time solution to the `sliding window maximum` problem is given there: https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/

In your case the window size is $n/2$ and the sequence is simply the concatenation of two copies of your original sequence.

# Answer
> 1 votes
First, try to solve it for a line.

Here's a hint. Think about what happens when you know the value for a "window" $s\_i = \sum \\{i, i+1, ..., i+n/2\\}$ and "slide" it one step to the right.

What will the sum be for $s\_{i+1} = \sum\\{i+1, i+2, ..., i+1+n/2\\}$ relative to $s\_i$?

---
Tags: algorithms, arrays
---


title: Why I can't parse factorial?

text:
# Question
Title: Why I can't parse factorial?
Given that I have a simplified Bison BNF grammar:

```
%token T_EXP '^'
%token T_NOT '!'

%right T_NOT
%right T_EXP
%right T_FAC
%nonassoc T_LPAREN T_RPAREN T_NUMBER

%type expr

%%

expr:
  T_NOT expr # logical not, e.g. !a
| expr T_EXP expr # exponent, e.g. 2 ^ 3
| expr T_NOT %prec T_FAC # factorial, e.g 3!
| T_LPAREN expr T_RPAREN { $$ = $2; }
| T_NUMBER
;

%%

```

Given a classical example, `2 ^ 3!`, it is natural to human that `3!` should be produced first, then the exponent and the answer is `2 ^ 3!` -\> `2 ^ (3!)` -\> `2 ^ 6` -\> `64`. It makes sense to assert that factorial goes before the exponent operator, so its binding power must be higher than that of the exponent.

However, in reality, the parser didn't produce a correct result. I modified the grammar production so that it shows as an AST:

```
calc eval > 2 ^ 3!
unary !!
  binary ^
    number 2
    number 3
        [expr: 40320]

```

This expression was evaluated as `(2 ^ 3)!` -\> `8!` -\> `40320`. And no matter how I move the precedences, it always produces the wrong result. If I wrap the factorial with parentheses, i.e. 2 ^ (3!), the result is correct. What's happening in here? Shouldn't `3!` be evaluated first?

At first glance, I thought this could be an ambiguity error.

```
2 ^ 3!    # Input
. 2 ^ 3!  # Lookahead is T_NUMBER(2), shift
2 . ^ 3!  # Lookahead is T_EXP(^), shift
2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -> expr T_EXP expr`?
          # But wait! There's a T_NOT behind it

```

Diverge 1:

```
2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -> expr T_EXP expr`
expr . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`?
expr ! .  # EOF reached, final stack: expr -> expr T_NOT -> (expr T_EXP expr) T_NOT // Incorrect

```

Diverge 2:

```
2 ^ . 3!   # Potential lookahead found T_NOT(!), shift
2 ^ 3 . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`
2 ^ expr . # EOF reached, final stack: expr -> expr T_EXP expr -> expr T_EXP (expr T_NOT) // Correct

```

But I considered this as a pure insanity and absurdity that comes out of nowhere in my mind, still `!` should be shifted before the number gets reduced because the binding power of T\_FAC is higher than that of T\_EXP and T\_NUMBER, so diverge 2 should have had happened, am I right?

# Answer
I have no comment on the precedence of the factorial operator; my inclination is to consider it to have higher precedence than other operators because of the almost universal rule that postfix operators bind more tightly than other operators.

When implementing that, you need to create a pseudotoken to modify the default precedence of the *prefix* operator:

```
%precedence PREFIX_OP
%right      '^'
%precedence '!'
%%
expr : '!' expr %prec PREFIX_OP
     | expr '^' expr
     | expr '!'
     | '(' expr ')'
     | T_NUMBER

```

(Using actual character constants in your grammar really makes it more readable, and it also simplifies writing the lexer. So I did that.)

To understand this, remember that precedence relations always compare the precedence of a *reduction* with the precedence of a *shift*. These are two distinct things; they only seem to be the same because (f)lex sets the precedence of a reduction (i.e. the right-hand side of a rule) to be equal to the precedence of the last non-terminal in the rule (unless it is specified explicitly with `%prec`). That's often the "right thing" but it leads to a lot of confusion because it makes it appear that the precedence comparison is between two objects of the same type.

In the resolution of `!3!`, the parser must decide what to do after seeing `!``3`. The only thing it can do with the `3` (a `T_NUMBER`) is reduce it to an `expr`; there is no ambiguity and thus no need to consult precedence relations. (Consequently, `%nonassoc T_NUMBER` has absolutely no effect, which is which I removed it from the grammar.) It then has two options:

* **reduce** `'!' expr` to `expr`
* **shift** the second `!`

To decide, it precedence-compares the reduction `expr: '!' expr` with the terminal `!`. Since the precedence of the reduction was explicitly set with `%prec PREFIX_OP` this results in a comparison between *reduction* `PREFIX_OP` and *shift* `!`; the shift wins. The same would happen with `2^3!` because the comparison will involve the *reduction* `expr: expr '^' expr` whose last terminal is `'^'` with the *shift* `!`.

In your original grammar, the precedence declaration

```
expr: expr '!' %prec T_FAC

```

had no effect whatsoever, because that reduction is never ambiguous (`3 ! 2` is a syntax error; no grammar rule applies to it.) Furthermore, the ambiguity between the *reduction* `expr '^' expr` and the *shift* `!` was incorrectly resolved because the terminal was declared as having lower precedence than the reduction. Just changing the order of the precedence list wouldn't have the desired result because that would also change the precedence of the *reduction* `expr: '!' expr`.
> 1 votes

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


# Question
Title: Longest path with limited edge traversals
Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem I'm trying to solve is given a list of words, find the longest chain of words such that the last letter of the $n^{th}$ word in the chain is the same as the first letter of the $n+1^{th}$ word in the chain. So the number of vertices would be 26 (the length of the alphabet), and each edge would represent the words that start with the letter which its from vertex corresponds to and ends with the letter which its to vertex corresponds to. The list is about 60,000 words long, so something like $O(cV)$ or $O(cV^2)$ where $c$ is the total capacity would be nice.

# Answer
In general, for a general graph with an arbitrary number of vertices, no. The general problem is NP-hard (consider the case where all edge capacities are 1; this is the longest trail problem, which is NP-hard; my thanks to Willard Zhan for pointing out the connection to the longest trail problem),. Therefore, there is unlikely to be an algorithm that is always correct and is efficient for all graphs.

In your case, it might be possible, as you can represent your problem as a graph with 26 vertices (one per letter) and 60,000 edges (one per word). Moreover, you can condense it to a graph with 26 vertices (one per letter) and $26^2$ edges (one per pair of vertices). Then, an exponential-time algorithm might suffice. I don't know of any such algorithm, but I also can't rule out the possibility, either.

How to condense the graph? Take all of the words (edges) that start with letter $i$ and end with letter $j$, sum up their corresponding capacities, and then add a new edge $(i,j)$ whose capacity is equal to that sum. That leaves you with a single edge per pair of letters. Any path through such a graph that respects the summed capacities can be transformed into a path in the original graph that respects the original capacities.

I realize this doesn't solve your problem, but maybe it is a small step towards that goal.
> 2 votes

---
Tags: graphs, eulerian-paths
---


title: What exactly (and precisely) is "hash?"

text:
# Question
Title: What exactly (and precisely) is "hash?"
I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on dictionaries it is said "Python calls them "dicts." Other languages call them "hashes."" So, are hashes dictionaries?

The other common usage of the word is in relation to encryption. I have also heard (& read) people using the word "hash" as a specific function within high-level programing.

So, what exactly is it?

Can anyone (with time and who is knowledgeable) kindly explain the nitty-gritties of "hash (or hashes)?"

# Answer
The Wikipedia article on hash functions is very good, but I will here give my take.

---

### What is a hash?

"Hash" is really a broad term with different formal meanings in different contexts. There is not a single perfect answer to your question. I will explain the general underlying concept and mention some of the most common usages of the term.

A "hash" is a function $h$ referred to as *hash function* that takes as input objects and outputs a string or number. The input objects are usually members of basic data types like strings, integers, or bigger ones composed of other objects like user defined structures. The output is a typically a number or a string. The noun "hash" often refers to this output. The verb "hash" often means "apply a hash function". The main properties that a hash function should have are:

1. It should be easy to compute and
2. The outputs should be relatively small.

### Example:

Say we want to hash numbers in the range from 0 to 999,999,999 to number between 0 and 99. One simple hash function can be $h(x) = x \mod 100$.

### Common additional properties:

Depending on use case we might want the hash function to satisfy additional properties. Here are some common additional properties:

1. **Uniformity**: Often we want the hashes of objects to be distinct. Moreover we may want the hashes to be "spreading-out". If I want to hash some objects down into 100 buckets (so the output of my hash function is a number from 0-99), then I am usually hoping that about 1/100 objects land in bucket 0, about 1/100 land in bucket 1, and so on.
2. **Cryptographic collision resistance**: Sometimes this is taken even farther, for instance, in cryptography I may want a hash function such that it is computationally difficult for an adversary to find two different inputs that map to the same output.
3. **Compression**: I often want to hash arbitrarily-large inputs down into a constant-size output or fixed number of buckets.
4. **Determinism**: I may want a hash function whose output doesn't change between runs, i.e. the output of the hash function on the same object will always remain the same. This may seem to conflict with uniformity above, but one solution is to choose the hash function randomly once, and not change it between runs.

---

### Some applications

One common application is in data structures such as a hash table, which are a way to implement dictionaries. Here, you allocate some memory, say, 100 "buckets"; then, when asked to store an (key, value) pair in the dictionary, you hash the key into a number 0-99, and store the pair in the corresponding bucket in memory. Then, when you are asked to look up a key, you hash the key into a number 0-99 with the same hash function and check that bucket to see if that key is in there. If so, you return its value.

Note that you could also implement dictionaries in other ways, such as with a binary search tree (if your objects are comparable).

Another practical application is checksums, which are ways to check that two files are the same (for example, the file was not corrupted from its previous version). Because hash functions are very unlikely to map two inputs to the same output, you compute and store a hash of the first file, usually represented as a string. This hash is very small, maybe only a few dozen ASCII characters. Then, when you get the second file, you hash that and check that the output is the same. If so, almost certainly it is the exact same file byte-for-byte.

Another application is in cryptography, where these hashes should be hard to "invert" -- that is, given the output and the hash function, it should be computationally hard to figure out the input(s) that led to that output. One use of this is for passwords: Instead of storing the password itself, you store a cryptographic hash of the password (maybe with some other ingredients). Then, when a user enters a password, you compute its hash and check that it matches the correct hash; if so, you say the password is correct. (Now even someone who can look and find out the hash saved on the server does not have such an easy time pretending to be the user.) This application can be a case where the output is just as long or longer than the input, since the input is so short.
> 47 votes

# Answer
A *hash function* is a function that takes an input and produces a value of fixed size. For example you might have a hash function `stringHash` that accepts a `string` of any length and produces a 32-bit integer.

Typically it is correct to say that the output of a *hash function* is a *hash* (aslo known as a hash value or a hash sum). However, sometimes people refer to the function itself as a *hash*. This is technically incorrect, but usually overlooked as it is generally understood (in context) that the person meant *hash function*.

The typical usage of a *hash function* is to implement a *hash table*. A hash table is a data structure that associates values with other values typically referred to as keys. It does this by using a hash function on the key to produce a fixed-sized hash value that it can use for fast look-up of the data it stores. I won't go into the full detail as to how it does that, but the key fact here is that it is called a *hash table* because it relies upon a *hash function* to produce *hash values* (hashes).

This is where some of the confusion comes in, because some people (again, somewhat incorrectly) refer to a *hash table* as a hash. As stated in other answers, sometimes a given language's implementation of a *hash table* refers to the *hash table* as a *hash* (notably Perl does this, though I expect other languages do as well). Other languages choose to refer to their implementation of a *hash table* as a dictionary. Python is one of these languages, but owing to how ingrained in the language they are, many Python users shorten the term dictionary to 'dict'.

So whilst the correct use of the term *hash* is to refer to the *hash value* produced by a *hash function*, people also sometimes use the term informally to refer to *hash functions* and *hash tables*, hence creating the confusion.
> 11 votes

# Answer
A hash function is broadly any function where the image is smaller than the domain. The output of such a function `f(x)` can be referred to as "the hash of `x`".

In computer science we typically encounter two applications of hash functions.

The first is for data structures such as hash tables, where we want to map the key domain (e.g. 32-bit integers or arbitrary-length strings) to an array index (e.g. integer between 0 and 100). The goal here is to maximise the performance of the data structure; properties of the hash function that are typically desirable are simplicity and uniform output distribution.

Perl calls its built-in associative array type a "hash", which appears to be what is causing your confusion here. I don't know of any other languages that do this. Loosely the data structure could be seen as a hash function itself (where the domain is the current set of keys), but is also implemented as a hash table.

The second is for cryptography: message authentication, password/signature verification, etc. The domain is typically arbitrary byte strings. Here we are concerned with security - which sometimes means deliberately low performance - where useful properties are collision and pre-image resistance.
> 2 votes

# Answer
Great question Basil Ajith,

Here is my perspective of what a hash is for something I am working on today.

*

> Use check sum to verify the tarball has is congruent to the download page

*

*Puts on auditor hat, I mean wizard robe*

hash is a value/string/whatever/label make sure its the same on your machine as the source of a download.
> 0 votes

# Answer
I'll try just to add a short summary of what others say.

**Hash function**

There is a special kind of functions called hash functions.

"SHA256 is a well-known hash function that is cryptographically secure"

Three main applications are * hash tables, * checksums (data integrity checks e.g. in hard drives or ADSL protocols), * and cryptography (various forms of cryptographic authentication including but not limited to digital signatures and secure password storage).

**Hash table**

Hash table is a data structure for fast search. It uses hash functions internally, hence the name.

"Databases use hash tables and search trees internally to speed up execution of search requests"

**Hash**

1. a dictionary abstract data type

"Hash" is the official name of built-in dictionaries in Perl. They are hash tables internally, hence the name. "This subroutine accept a hash as its first argument". These days can be used for any associative array, not necessarily a hash table.

2. result of applying a hash function to some input

"MD5 hashes of the .iso images are provided to check their integrity after downloading".
> -1 votes

---
Tags: terminology, hashing
---


title: Justifying regular language

text:
# Question
Title: Justifying regular language
I have been given the question "Is the language 010 ∪ 101 regular? Justify your answer."

It is regular and as it can be accepted by an NFA (Draw NFA). Is this correct?

# Answer
> 2 votes
A language is regular if it is accepted by a DFA.

It is also regular if it is accepted by a NFA (as every NFA can be converted into an equivalent DFA).

I suggest look here to know what constitutes a regular language.

# Answer
> 1 votes
A language is regular if and only if it can be written as a regular expression (the CS kind, not the Perl kind you see in most programming languages). Equivalently, if and only if it can be recognized by a DFA, or if and only if it can be recognized by an NFA; all three of these are equivalent.

In this case, the regular expression `010+101` expresses your language. Thus the language is regular.

---
Tags: finite-automata
---


# Question
Title: If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?
If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?
I think that as we know nothin about $M$, in general case we can't determine wherther a random element $m$ belongs to $M$, so we coundn't say anything about $A \cap M$. Am I right?

# Answer
If $\overline{M}$ is r.e., then we *do* know something about $M$: namely, that it's co-r.e. And the intersection of any two co-r.e. sets is co-r.e., so $A\cap M$ is co-r.e. (every recursive set is a fortiori co-r.e.). Beyond that, of course, we can't say anything: every co-r.e. set is of the form $A\cap M$ for some recursive $A$ and some co-r.e. $M$ (take $A=\mathbb{N}$ and $M=$ the co-r.e. set in question).

*This may seem a bit silly, but being the complement of an r.e. set is a very strong property, even though we think of it less than r.e.-ness. Also, lots of natural sets are co-r.e. but not r.e., like the set of (indices for) Turing machines which never halt on any input. So the conclusion "$A\cap M$ is co-r.e." is actually quite meaningful.*

---

This answers your specific question, but let me say a bit more.

We didn't really use that $A$ was recursive, merely that $A$ was co-r.e. But what if $A$ is merely r.e.? Then in general $A\cap M$ is neither r.e. nor co-r.e. This is the first step into the **difference hierarchy**: $A\cap M$ can be rewritten as $A\setminus \overline{M}$, that is, as the difference of two r.e. sets, and we can continue further and talk about more complicated Boolean combinations of r.e. sets. It turns out that this gives a proper hierarchy, even in the coarse terms of Turing degree: for each $n$ there is an $(n+1)$-r.e. set which is not of the same Turing degree as any $n$-r.e. set (I believe this was proved by Cooper but I don't have a reference on hand; it certainly followed his proof of the case $n=1$).

We can try to continue the difference hierarchy into the transfinite but one runs into some difficulties in doing so (namely, the issue of finding appropriate "names" for complicated infinite ordinals - this is where Kleene's $\mathcal{O}$ becomes unavoidably relevant). What we get winds up not being a true hierarchy: even though the ordinals are linearly ordered, we can't avoid having different "difference levels" which are incomparable. The resulting "pseudo-hierarchy" is however a quite interesting object, and is called the **Ershov hierarchy**.

For more information on this, I strongly recommend the first couple sections of the paper The Ershov hierarchy by Stephan, Yang, and Yu.
> 3 votes

---
Tags: computability
---


# Question
Title: Why Don't We Use Non-ML Artificial Evolution?
I remember reading about Tom Ray's Tierra and how amazing the results it obtained were. However as far as I know, the only "evolution" based computer technology we use now is ML, which is very limited in its abilities. Why haven't we used artificial evolution perhaps similar to Tierra for practical purposes? Is it too hard? Do we lack the technology to make it practical so far or have we decided we don't need to do it, even if we had the technology?

# Answer
Because we don't know how to make it work well to solve practical problems we care about.

If your'e asking about evolutionary algorithms in general: As a rough rule of thumb, evolutionary algorithms haven't turned out to be all that wonderful. As a starting heuristic, they're... usually OK. But, practical experience is that other methods often seem to perform better.

If you're asking about Tierra specifically: Tierra was a demo applied to a very specific, artificial situation. It doesn't seem to have generalized to allow us to solve many practical problems we care about. Also, I'm not sure, but it looks like Tierra might have been intended more to try to understand evolution, more than to apply evolution to solving practical computing problems.
> 3 votes

---
Tags: machine-learning, evolutionary-computing
---


title: IP Address CIDR Bitmask Conversion

text:
# Question
Title: IP Address CIDR Bitmask Conversion
In looking for a programming function to validate an IP address within a subnet, I had to calculate the subnet mask from a given CIDR bitmask value ie. 192.168.0.0/**24**, the value 24 in this example.

The first step is to convert the bitmask value (24) into an unsigned 32bit integer. I found this on the internet (specific to our 24 bitmask example): mask = (( 2^**24** ) - 1) * ( 2^(*32*-**24**) ). This gives me an integer value of 4,294,967,040 which is exactly the binary number I am looking for where the first 24 bits are 1, while the remaining bits are 0 11111111.11111111.11111111.00000000. Obviously, this works for any bitmask value 0-32.

I would like to understand why this works: mask = (( 2^*bitmask* ) - 1) * (2^( 32-*bitmask* ))

# Answer
> 1 votes
The binary expansion of $2^n-1$ consists of $n$ ones. This is because the binary expansion of $2^n$ consists of a one followed by $n$ zeroes. This is similar to $10^3-1 = 999$ in decimal.

If we want these $n$ bits to be the left $n$ bits out of $m$ bits, then we need to add $m-n$ zeroes to the right. This is the same as multiplying everything by $2^{n-m}$. Compare $100 \cdots 54 = 5400$. This operation is usually known as *left shift*, and many languages support it natively. For example, in C you would use the following code to generate the mask:

> `((1 << 24) - 1) << (32-24)`

---
Tags: computer-networks, arithmetic
---


title: Prove $EXP \subset E^E$

text:
# Question
Title: Prove $EXP \subset E^E$
I'm trying to prove $EXP \subset E^E$ (strictly).

I believe I need to construct my own $A \in E^E$ and show that $A \notin EXP$, but I cannot think of a smart way of doing that.

Thanks.

# Answer
The class $E^E$ contains 2E, which is the class of problems solvable in iterated exponential time. The reason is that the E oracle can be applied on a padded input of exponential size. The time hierarchy theorem separates 2E from EXP.
> 2 votes

---
Tags: complexity-theory, time-complexity
---


title: Haskell type class and initial algebra

text:
# Question
Title: Haskell type class and initial algebra
For the example below, I am trying to understand how Haskell type classes, type class instances, and data types relate to the concept of initial algebra. There are two Haskell data types sharing a pair of operations for equality and addition. From my, perhaps incorrect, understanding the instances, which include the data types, specify two non-isomorphic initial algebras. It seems to me that the type class permits the overloading of the operations and plays no role in the specification of the initial algebra. Is this a correct interpretation of the given example?

```
data Nat0 = Zero | Succ0 Nat0 deriving Show
data Nat1 = One | Succ1 Nat1 deriving Show

class PeanoNum n where
 eq :: n -> n -> Bool
 add :: n -> n -> n

-- Two different non-isomorphic algebras.
instance PeanoNum Nat0 where
 eq Zero Zero = True
 eq (Succ0 m) (Succ0 n) = eq m n
 eq _ _  = False
 add m Zero = m
 add m (Succ0 n) = Succ0 (add m n)

instance PeanoNum Nat1 where
 eq One One = True
 eq (Succ1 m) (Succ1 n) = eq m n
 eq _ _ = False
 add m One = Succ1 m
 add m (Succ1 n) = Succ1 (add m n)

```

# Answer
**tl;dr:** we can show that they are in fact isomorphic. Defining two different instances over them does not make them different. Defining two different functions over two types does not make them non-isomorphic! The instances are not describing an initial algebra structure, the `data` keyword is. As you say, the two instances play no role in the specification of the initial algebra.

---

In our example, we work with algebras for the functor $1 + -$. That is, an algebra $A$ is given by a morphism $1 + A \to A$, or, in other words, an *element* of type $A$, which can be seen as a morphism $1 \to A$, and an *endomorphism* $A \to A$.

```
data Nat0 = Zero | Succ0 Nat0
data Nat1 = One | Succ1 Nat1

```

Here, `Zero` and `One` are the elements while `Succ0` and `Succ1` are the endomorphisms. We will see that they are isomorphic as F-algebras. A morphism $f$ between two F-algebras $A$ (with element $a$ and endomorphism $u$) and $B$ (with element $b$ and endomorphism $v$) is a $f \colon A \to B$ making the following diagram commute.

$$\require{AMScd}\begin{CD} A+1 @\>f+1\>\> B+1\\ @VVa+uV @VVb + vV\\ A @\>f\>\> B \end{CD}$$

And, in fact, *we can find a pair of invertible morphisms making them isomorphic*. I will only define the first one, but the second one is analogous and checking that they are inverses should be easy.

$$\require{AMScd}\begin{CD} \mathsf{Nat0}+1 @\>f+1\>\> \mathsf{Nat1}+1\\ @VV\mathsf{Zero+Succ0}V @VV\mathsf{One + Succ1}V\\ \mathsf{Nat0} @\>f\>\> \mathsf{Nat1} \end{CD}$$

The commutativity of the diagram determines that the only possible $f$ must send `Zero` to `One` and `Succ0 x` to `Succ1 x`. This translates into code as follows.

```
f :: Nat0 -> Nat1
f Zero = One
f (Succ0 x) = Succ1 x

```

Precisely because $A$ is initial, this is the only possible $f$ making this diagram commute. We had no choice when defining $f$ (apart from `undefined` or any other of the constructions that make this kind of categorical reasoning fail in Haskell).

**What about the two instances?** They define two different functions over each one of the types, but that does not make them non-isomorphic as algebras. As you say, the instances play no role on the definition of the two algebras. The algebra structure concerns only the $1+A \to A$ morphism, not the two additional morphisms $A \times A \to A$ and $A \times A \to \mathsf{Bool}$ that define the instance. Even if we call the two different functions `add`, the second one is simply a different function. We could rename the second `add`, and we would see that they are, essentially, two different instances of the same class for (essentially) the same type.

**What if we want an "add" (a binary) function to be part of the algebra?** Then we would be looking for the initial algebra for the functor $F(X) = 1 + X + X \times X$, and neither `Nat0` nor `Nat1` (with their respective `add` functions) are *initial* algebras for this functor. The initial algebra would be the following one.

```
data Foo = Zero | Succ Foo | Add Foo Foo

```

**What if we also want an "equality" function to be part of the algebra?** There may be a better approach for this, but we can consider algebras on the category whose objects are *pairs* of types. An algebra is of the form $F(A,B) \to (A,B)$ for some endofunctor $F$, and in this case, we consider algebras of the form $(1 + A + A \times A, A \times A) \to (A,B)$. The natural numbers ($A$) and the booleans ($B$) endowed with zero $1 \to A$, the successor function $A \to A$, addition $A \times A \to A$, and the equality function $A \times A \to B$ would be *an* algebra of this form, but not *the* initial algebra. I think the initial algebra in this case could be written in Haskell as follows.

```
-- Initial algebra (where the object is a pair of types!).
data A = Zero | Succ A | Add A A
data B = Equ A A

-- Given any other algebra.
data C
data D
z :: C
s :: C -> C
a :: C -> C -> C
e :: C -> C -> D

-- There is a unique morphism (two morphisms) from the initial
-- algebra making the relevant diagram commute.
u1 :: A -> C
u1 Zero = z
u1 (Succ x) = s (u1 x)
u1 (Add x y) = a (u1 x) (u1 y)

u2 :: B -> D
u2 (Equ x y) = e (u1 x) (u1 y)

```

Where the relevant diagram is the following one.

$$\require{AMScd}\begin{CD} (1+A+A\times A,A \times A) @\>\>\> (1+C+C\times C,C \times C)\\ @V(Zero+Succ+Add,Equ)VV @VV(z+s+a,e)V\\ (A,B) @\>(u1,u2)\>\> (C,D) \end{CD}$$
> 4 votes

---
Tags: haskell
---


# Question
Title: Peterson Algorithm for process synchronisation
Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

repeat

```
flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then
exit critical section
Flag[i] = false;
Perform other non-critical section actions.

```

Until false;

For the program to guarantee mutual exclusion, the predicate P in the while loop should be

a) flag\[j\] = true and turn = i

b) flag\[j\] = true and turn = j

c) flag\[i\] = true and turn = j

d) flag\[i\] = true and turn = i

=============================================================================================

**Now, in original peterson algorith, we have -**

I'm writing just the important lines from the algorithm and not the whole algorithm -

> 1) flag \[process\] = 1;
>
> 2) turn = process ;
>
> 3) while (interested \[other\] == True && turn == process);
>
> 4) ///////\***CS///////
>
> 5) flag \[process\] = false;
>
> out of CS
>
> Now, according to given question -
>
> flag\[i\] = true; turn = j; i.e process i is interested as flag\[i\] = true, but turn = j i.e turn is of process J.

So, which process is exactly currently executing?

Question 1) Process i or Process j

Question 2) Which process are we blocking in while loop i.e stopping to enter CS?

> Also, at exit of CS - flag\[i\] = false;
>
> this means, Process i, is already in CS?

Now Pi is already in CS, this means, process j is executing and we should hold it in while loop and not let process j eneter CS.

> So, according to know peterson algo I mentioned above -
>
> line 3) while (flag \[other\] == True && turn == process);
>
> while(flag \[i\] ==true && turn = j);
>
> both are true so, while loop is true and process Pj should spin here and not go to CS.
>
> and this matches with option c. but answer is option b)
>
> Also, folks are saying that **option c)** will allow both Pi and Pj into CS.

**May you guys please explain, how option b) is answer!**

# Answer
> 1 votes
Firstly, since the program at the start the question starts with "flag\[$i$\] = true", it should be run by Process $i$. Here is the full program again formatted slightly better. Note that the I replace "Enter critical section" and "exit critical section" with comment "// inside the critical section", since there is no code that actually corresponds to them. Once the process breaks out of the "while (P) do no-op" loop, it is in the critical section (CS). The process is exiting the critical section at the exact point of time when it is executing "flag\[$i$\] = false".

> repeat
>
> * flag\[$i$\] = true;
> * turn = $j$;
> * while ($P$) do no-op;
> * Perform some actions // inside the critical section
> * flag\[$i$\] = false;
> * Perform other non-critical section actions.
>
> Until false;

The following is the full program run by Process $j$. You should be able to figure out the code represented by $Q$ once you have accepted my answer. :)

> repeat
>
> * flag\[$j$\] = true;
> * turn = $i$;
> * while ($Q$) do no-op;
> * Perform some actions // inside the critical section
> * flag\[$j$\] = false;
> * Perform other non-critical section actions.
>
> Until false;

**These two different programs together** that are run by two different processes respectively at the same time competing for (some resources inside) the critical section (CS) is Peterson's algorithm.

Secondly, there is a fatal typo in the "important lines from the algorithm" with line numbers in the question. The second line

> 2) turn = process ;

should be

> 2) turn = other ;

Indeed, this line is the key to understand how Peterson's algorithm ensures mutual exclusion. Please note "the important lines from the algorithm" are executed sequentially at the same time by **two** processes, each considering itself as the "process" and the other process as "other" in those "important lines". **By executing this line, each process tries letting the other process to have a higher priority over itself to enter CS.**.

A minor typo in OP's question is "while (interested \[other\] == True" should be "while flag \[other\] == True".

Thirdly, OP asks which process is exactly currently executing. The answer is not just Process $i$. The answer is not just Process $j$. The answer is **both processes**. In fact, we can assume both process are executing at all times, each executing a different program. That is what we mean by concurrent processes or concurrent programming. Is it surprising? Please note, however, if the question is which process is exactly executing the program written at the start of OP's question, then, as I have said at first, the answer is Process $i$.

Fourthly, OP asks "which process are we blocking in while loop i.e stopping to enter CS?". Of course, the answer is the current process, that is, the process that is currently executing that line of code. It is the other process if you write the loop uniformly as "while (flag \[other\] == True && turn == process)", which can be either Process $i$ or $i$. It can only be Process $i$ if the loop is "while (flag\[$j$\] = true and turn = $j$)". It can only be Process $j$ if the while loop is "flag\[$i$\] = true and turn = $i$)".

Lastly, the "option b) flag\[$j$\] = true and turn = $j$" should be what $P$ stands for. Here "flag\[$j$\] = true" means process $j$, the other process, is interested in entering or staying in the critical section(CS) while "turn = $j$" say that the other process is either holding CS or, if other process is interested in entering CS, it has the priority over the current process to enter CS. Both conditions together imply the current process cannot enter CS. Once Process $j$ is not interested in CS by setting flag\[$j$\] to false, or once the value of variable "turn" is $i$, meaning Process $i$ has a higher priority over Process $j$ to enter CS, the "while (P)" loop is broken and Process $i$ is in CS. (I am avoiding to say "enter CS" here, just to emphasize the fact that there is no other code that enables or represents the act of entering CS. Process $i$ enters CS by breaking out of that while loop.)

All other options, (a), (c) and (d), are apparently wrong. For more detailed analysis, please check Peterson algorithm at Wikipedia.

---
Tags: operating-systems
---


# Question
Title: Turing machine different accepting states
I want to design a Turing machine that accepts at most 3 0s. Now, I have designed one, which goes to accept state overtime it sees 1, 2 and 3 0s and rejects any further 0s. I wanted to know if it is okay for TM to go to accepting state from 3 different states?

# Answer
Of course, a Turing machine can transition to a given state from as many other states as you like. Machines used in halting problem reductions usually have an "infinite loop" state that only transitions back to itself, and many other states that transition into that one.
> 1 votes

# Answer
As Draconis says, you can go to the accept (or reject) state from as many states as you want.

However, it would make no difference if you could only go to the accept state from one state. Suppose you wanted to go to the accept states from states $S\_1, \dots, S\_k$. Then just make a new state $X$ such that you go from each of $S\_1, \dots, S\_k$ to $X$ and then from $X$ to the accepting state.

The definition of Turing machines is, in general, very flexible. You can add all kinds of restrictions to the definition without changing the power of the machines.
> 1 votes

---
Tags: turing-machines
---


title: Most space-efficient lossy dictionary?

text:
# Question
Title: Most space-efficient lossy dictionary?
**Short version:** What is the most space-efficient lossy dictionary (with given false positive and false negative rates)?

**Long version:** A lossy dictionary is a data structure $D$ that encodes a set $S$ of $n$ key-value pairs $(k\_i, v\_i)$, assorted with a query operation. Let $K = \\{k\_1,\dots{},k\_n\\}$. The query operation is defined as:

$$query\_D(k\_i) = v\_i,$$ $$query\_D(k) = \bot \text{ for } k \not\in K.$$

However, false positives (returning a $v\_i$ for a $k \not\in K$) or false negatives (returning $\bot$ for a $k\_i$), respectively occurring with probability $p\_p$ and $p\_n$, are acceptable to some degree.

Many efficient techniques exist, but I am having trouble figuring out the most efficient one. I am chiefly interested in space efficiency (as a function of $p\_p$ and $p\_n$). $query$ efficiency is not a main concern (but should remain sublinear in $n$). I assume that keys and values are of fixed size of respectively $s\_k$ and $s\_v$. I also assume that keys (both in $S$ and those queried) are uniformly distributed in $\\{0,1\\}^{s\_k}$.

I know of some examples:

* Cuckoo hashing
* Bloomier filters
* Minimal perfect hash function + signature (to alleviate false positives)

They are however not trivial to compare, and I am also not sure there isn't better out there. Any insight would be appreciated!

# Answer
> 1 votes
Let's see what we can do. Values are random and hence are incompressible, but keys can be sorted and then diffed. So, just sort the data, employ difference compression schema for keys and use binary search to find.

It will put your N keys+values into minimum amount of bits required to keep this amount of information.

May be, you can further improve compression ratio by dropping less compressible items.

~~EDIT: As mentioned here, you can compress keys to smaller values. So, f.e. you can use Bloom filter to check that probed key is included in the result set, and then use compressed 32-bit hash of the key to find it in table with 64K entries with pretty high fidelity.~~ NOTE: at more thorough analysis I realized that Bloom filter will occupy at least the same space you will economy on reducing key values stored in the sorted table.

PS: You can use any rehashing scheme, including Cuckoo hashing, to cut off rehash chains at some point, but anyway sorted sequence should be better compressible than any hashtable containing unused cells.

Perfect hashing just helps you to make hashtable without holes. I don't know what signature you mean here.

Bloom filter by itself only checks value presence, then you still need to store entire key+value pair.

---
Tags: data-structures, hash, data-compression, hash-tables, dictionaries
---


# Question
Title: Best algorithm for splitting up departments such that the least unique ones are assigned per day
I have a collection of people who need to be assigned to one of 10 dates. Each person is in a specific department. The departments have vastly varying amounts of people (from ten to thousands). Each date can accomodate a set amount of people, let's say 5000. My task is to assign each person to a date such that the amount of departments participating that day is as small as possible AND as average as possible. Basically every time you put a new department in a day it adds a lot of overhead (adding people doesn't) which means that doing a lot of departments in a single day is really bad. So for example, 1 huge department being assigned day 1 and 15 small ones being assigned day 2 is undesirable, it's better to do half of department 1 one day, and half on the other and then splitting the small ones such that its basically 7.5 one day and 8.5 on the other. But the less departments particpating in a day, the better. So if you had 3 days and 3 equal departments it would be undesirable to have 3 departments (1/3 of the employees of that department) participating each day, it would be better to have each department on a single day. The 'spots' have to be filled up, that is each day MUST have 5000 participants. Any ideas on how to approach this?

My first thought is to minimize the maximum, that is find a solution such that the highest amount of departments per day is the lowest it can be. Is this the best solution?

# Answer
The first problem to solve is defining the problem.

In general, you have an optimisation problem. What you have not yet defined is the objective function, meaning what you want to optimise (precisely).

Based on what you describe, you might define the objective function as the max number of participants, but this is not great since for example a solution (2,2,5) (2 departments on day 1, 2 on day 2, 5 on day 2) is equal to a solution (1,1,5); such an objective function doesn't distinguish, e.g., unnecessarily splitting two departments over the first two days.

Another option is sum, but that does not help in the case of distinguishing (1,15) and (7.5,8.5).

Perhaps another option that seems to go in the direction you want is to minimise, for example, the sum of the squares, which prefers (1,1,5) over (2,2,5) and (7.5,8.5) to (1,15). But why raise to the power of 2 and not some other value greater than 1?

These are all application-dependent choices that you have to make.

---

The second problem is the difficulty. You have many options and you want to find the best option according to your objective function. Your general problem is an NP optimisation problem, so you may need to consider approximations. But again, the need to consider approximations depends on the size of your data, the values you choose, how you define the optimisation function, what is the relative cost of computation versus the cost of not finding an optimal solution, and so forth.

So after you define your objective function, you will need to think about what sort of approximation (if any) is cost effective.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Applicative-order languages don't support constant time array writes? If not, why not?
I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his *War Stories* on page 155 he states:

> Efficiency is a great challenge in Mathematica, due to its applicative model of computation (it does not support constant-time write operations to arrays) and the overhead of interpretation (as opposed to compilation).

I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called). But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes. I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.

If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time? Why would the order of evaluation matter in determining array write time?

I'm also curious what the Big-O write performance *is* in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.

# Answer
Skiena didn't say "applicative *order*", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as opposed to the execution of state manipulating commands. Mathematica (at least nowadays) isn't purely functional, but it does seem that it strongly encourages a purely functional style of programming.

In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.

There is, to my knowledge, no fully satisfactory answer to this. That is, there is no purely functional data structure that provides constant time lookup and updates *to all versions*. You can make (externally) pure data structures that provide constant time lookup and update for the *latest* versions, but accesses to older versions of the array become slower. You can use monads or uniqueness types to enforce a usage of arrays that allows the compiler to use in-place updates, but this is tantamount to using an imperative approach (albeit in a controlled and contained manner). In practice, programmers in purely functional languages simply don't use arrays nearly as much as imperative programmers, and when they do use arrays, they tend to use bulk operations. If you are going to touch every element of an array anyway, then the cost of copying the array is constant per element.

While there are definitely times where the limitations of purely functional programming make efficient implementation non-obvious, most of the time it is just a matter of applying different design and implementation techniques than are typical/practical in imperative languages. Purity also affords guarantees that make many designs, optimizations, and sometimes entire technologies practical. For the first, most purely functional data structures are designed to share as much as possible. For the second, a major technique for improving performance of bulk operations is fusion which combines multiple bulk operations into one to avoid intermediates. For the last, there was an attempt to add Software Transactional Memory to C# that was given up because it relied on the programmer not using side-effecting procedures in the transactions but could not enforce this practically.
> 12 votes

---
Tags: arrays
---


# Question
Title: Length of longest arithmetic progression in an array
I was reading an article on Longest Arithmetic Progression. The solution given has S(n)=$O(n^2)$. Can't I solve it in $O(1)$ space? To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). When we found them we still keep on decreasing left and right to find llap (length of longest arithmetic progression). The other cases left are those where llap is even.. for them I will select i and (i+1)$^{th}$ element as my center two elements of AP and find elements on their right and left satisfying ap. T(n) will still be $O(n^2)$.

Is my approach correct?

# Answer
**No, your approach is wrong.** Consider the set of numbers $1, 3, 4, 6, 7, 8, 10$. The longest arithmetic progression(LAP) in it is $1, 4, 7, 10$, which is of even length. However, 4 and 7 are not adjacent items so your approach will not find that LAP.

**Yes, your approach is correct**, but to a different problem from the problem in the article you mentioned.
> 2 votes

---
Tags: dynamic-programming
---


# Question
Title: If the parent in a bridge is the root, is it a bridge cut node?
I am going through Professor Skiena's textbook and he says that there are 3 types of cut-nodes - root, bridge cut node, and parent cut node.

Now if the earliest reachable ancestor from a node is itself, it's parent and the node (if not leaf) become bridge cut nodes.

My question is that we have a simple 2-node undirected graph -\> `A --- B`.

In this case, B's earliest reachable ancestor is B itself and hence A becomes the bridge cut node. However, I am unsure that should be the case; since if I delete A, even then B exists and the `num_components = 1`?

# Answer
By definition, a graph that has only one vertex is `connected`.

That's to say if you delete `A`, the graph `B` is still connected. Clearly, `A` is not a cut-node because it can't disconnect the graph. So is vertex `B`.

A vertex is a parent/bridge cut-node *if and only if* it is not root vertex.

The concepts of these three types of cut-node are introduced by Skiena's in his own book, so these concepts are not very rigorous. An errata list may be a good supplement.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Turing machine that accepts L = {a^nb^2n : n ≥ 0}
write a Turing machine that accepts L = {a^nb^2n:n ≥ 0} where there are double the amount of b's in comparisons to the amount of a's. So aabbbb would be accepted but aabbaabb would not. I am unsure of how to check that there are twice as many b's then a's. So far i have a change it to an A move to state 1. Then check if a, move to right stay in the same state, if empty go to the reject state, if b change to B move to the right and the next state.

# Answer
For this general kind of language, the usual technique is to simulate what you'd do with a pencil and paper: make multiple passes along the tape, "crossing out" an $a$ and two $b$'s on each pass. When you run out of stuff to cross out, accept or reject as appropriate.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: What is the output of below algorithms on a disconnected Graph?
If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run Dijkstra's algorithm on it then it will return shortest path in the connected component only , but we maintain a predecessor array in all the algorithms which has information about the parent from which the node learnt the path so it will values for all the vertices , so even if we have a disconnected Graph then still other vertices will also be printed .

So output is Graph right for all the algorithms whether the graph is undirected or directed ?

# Answer
> 1 votes
No. The output of Dikstra's algorithm is a set of distances to each node. It's not a graph or a tree. This is true no matter whether the input graph is connected or disconnected. The standard algorithm for Dijkstra's algorithm sets the distance correctly for all vertices in all components (not just the ones in the same connected component as the source). The standard algorithm doesn't print anything, so if you are printing something, you're probably adding something extra to the standard algorithm, and we can't analyze that without seeing what your variation of the algorithm is.

---
Tags: graphs, algorithm-analysis
---


# Question
Title: Correct cost function of multi classification problem using neural network?
I am going through machine learning course on coursera. While going through the section on neural networks I came across the cost function for multi - classification problem using neural networks ( ignoring the regularization term ): $$\begin{gather\*} J(\Theta) = - \frac{1}{m} \sum\_{i=1}^m \sum\_{k=1}^K \left\[y^{(i)}\_k \log ((h\_\Theta (x^{(i)}))\_k) + (1 - y^{(i)}\_k)\log (1 - (h\_\Theta(x^{(i)}))\_k)\right\] \end{gather\*}$$

where $m$ is the number of training data points $\\{(x\_1,y\_1),...(x\_m,y\_m)\\}$. Each data point is classified into one of the $K$ categories ie. $1\\;\le{\\;y\_i}\\;\le{K}$ ( so $y\_k^{(i)}$ means if $\\;y\_k^{(i)} == k\\;$ ). And $h\_\Theta$ is the hypothesis function.

My doubt is why does the cost function has a summation over $K$. Why aren't there $K$ separate cost functions ( $ 1 \\; \le{k} \le K$ ), and we have different $\Theta$ when we minimize each of the $K$ cost functions separately:

$$\begin{gather\*} J(\Theta)\_k = - \frac{1}{m} \sum\_{i=1}^m \left\[y^{(i)}\_k \log ((h\_\Theta (x^{(i)}))\_k) + (1 - y^{(i)}\_k)\log (1 - (h\_\Theta(x^{(i)}))\_k)\right\] \end{gather\*}$$

In the second approach we are trying one-vs-all classification. How is it different from first approach. First approach is taking sum over all cost functions of second approach. So minimization problem being solved in both cases are different. But I am unable to pin point what the difference between the two approaches is ? Both seem intuitively correct to me. Am I doing some stupid mistake ?

# Answer
The loss function you have shown is not correct. The correct one is

$$\begin{gather\*} J(\Theta) = - \frac{1}{m} \sum\_{i=1}^m \sum\_{k=1}^K y^{(i)}\_k \log ((h\_\Theta (x^{(i)}))\_k) \end{gather\*}$$

The loss function has a summation over $K$ because we must take into account all possible classes. The neural network outputs $K$ values, $h\_{\Theta}(x^{(i)})$, and the loss function should depend on all $K$ of those. There is a single loss function because we are training a single neural network, and we need exactly one loss function per neural network; if you wanted to train $K$ neural networks, then you would use $K$ loss functions.

Define $z^{(i)}$ to be the class of $x^{(i)}$ according to the training set, i.e., we take $z^{(i)}$ to be the value of $k$ such that $y^{(i)}\_k=1$. Then the loss function above is equivalent to

$$\begin{gather\*} J(\Theta) = - \frac{1}{m} \sum\_{i=1}^m \log ((h\_\Theta (x^{(i)}))\_{z^{(i)}}) \end{gather\*}$$

which does not have a summation over $K$.

I suggest reading more about the cross-entropy loss. See, e.g., https://rdipietro.github.io/friendly-intro-to-cross-entropy-loss/

There are some errors in your notation. The training set has points $(x^{(i)},y^{(i)})$, not $x\_i,y\_i$. Here $y^{(i)}\_k$ means that $y^{(i)}=k$, not that $y^{(i)}\_k=k$ (the latter would be circular, defining $y^{(i)}\_k$ in terms of itself).
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Compute context free grammars for twice the amount
$$\\{ a^{k}b^{j} : k = 2j , k \geq 0\\}$$

I'm trying to wrap my head around CFG's but I am having trouble. From this language, there should be twice as many a's than b's. Here is my attempt.

$$S \to aSb \ | \ a Sa \ | \ \epsilon $$

$$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSabb \Rightarrow aaaabb $$

But, I can also have this arise, which I don't want: $$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb $$

How can I force the CFG to put twice as many a's as b's? Is there any general approach to solving these?

# Answer
> 2 votes
One general approach would be to try writing some initial strings and try to figure out a pattern. In my minimal experience, a lot of the times the strings I miss are of smaller lengths.

The initial strings for this would be:

$(\epsilon, aab, aaaabb, aaaaaabbb, ...)$ and so on.

Here we notice that: a) The string always has to start with an $a$ and b) Every time we generate an $b$, there should be two $a$'s corresponding to it.

So, we can write it as:

$$S \rightarrow \epsilon \ | \ aaSb$$

---
Tags: context-free
---


# Question
Title: What is the significance of negative weight edges in a graph?
I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.

So, I wonder what's the real world significance of negative weight edges? A plain English explanation would be helpful.

# Answer
Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent anything in the real world, for example, the amount of money to be transferred from one account to another account. The amounts can be positive or negative. For example, if you want to go from $a$ to $b$ in your graph while losing as less money as possible (shortest path), then you can consider negative weights. For more, see this book chapter.

Apart from that, there are many more applications. The negative weights depend on what you model it to be. For example, consider this graph

* Chemistry: The weights can be used to represent the heat produced during a chemical reaction. (Nodes: compounds, Edge $e\_{uv}$: if compound $v$ can be obtained ("chemically reduced") from $u$). In this graph: you produce $4$ kJ to convert $s$ to $a$ and $2$ kJ to convert $a$ to $t$. You need $5$ kJ to get back $s$ from $t$.
* Real Life: Think of a driver, who gets paid to drive his employer from $s$ to $t$ but he pays between $a$ and $b$ (say traveling between his home and his workplace).
* Games: Suppose you play rock-paper scissor for money. Nodes: rock, paper, scissors. Edges: any relation (clique). Weights: wager. In this graph: (forget about $b$), here, $s$ beats $a$, $a$ beats $t$ and $t$ beats $s$, and wins 4,2,-5 respectively.
> 21 votes

# Answer
I am not a chemistry guy but still I think this example will be worth to help you think out of processor , network theory and related stuff ..

Consider a graph simulating behavior of a molecule in a chemical reaction ie which paths it can take during reaction and weights represents energy absorbed or released in the transition, so if we want energy out of the reaction we represent released energy with +ve weights and absorbed energy with -ve.
> 4 votes

# Answer
A negative edge is simply an edge having a negative weight. It could be in any context pertaining to the graph and what are its edges referring to. For example, the edge C-D in the above graph is a negative edge. Floyd-Warshall works by minimizing the weight between every pair of the graph, if possible. So, for a negative weight you could simply perform the calculation as you would have done for positive weight edges.

The problem arises when there is a negative cycle. Take a look at the above graph. And ask yourself the question - what is the shortest path between A and E? You might at first feel as if its ABCE costing 6 ( 2+1+3 ). But actually, taking a deeper look, you would observe a negative cycle, which is BCD. The weight of BCD is 1+(-4)+2 = (-1). While traversing from A to E, i could keep cycling around inside BCD to reduce my cost by 1 each time. Like, the path A(BCD)BCE costs 5 (2+(-1)+1+3). Now repeating the cycle infinite times would keep reducing the cost by 1 each time. I could achieve a negative infinite shortest path between A and E.

The problem is evident for any negative cycle in a graph. Hence, whenever a negative cycle is present, the minimum weight is not defined or is negative infinity, thus Floyd-Warshall cannot work in such a case.

As an addition, you might want to take a look at Bellman-Ford Algorithm which detects whether a graph have negative cycle or not and otherwise return the shortest path between two nodes.
> 3 votes

# Answer
For example, imagine a logistic network where the weight w(i,j) of an edge ij is the cost to go from vertex i to vertex j. If you made a business agreement with other companies to transport their products, w(i,j) would be a profit instead of a cost, so you can interpret this weight as a negative cost.
> 2 votes

# Answer
Traffic congestion on a map:

One other real world example of associating weights to an edge could be the weights represent traffic conditions in a map (more negative, more unfavorable) - we could then use this representation to compute optimal distances.

We can really use the "weight" metaphor to represent anything of positive/negative value between any two points in a graph
> -3 votes

---
Tags: algorithms, graphs
---