# Question
Title: Call by name, lambda calculs. Multiplication
How to multiply in CBN strategy?

```
mul = \m.\n.\f. m(n f)
two = \f.\x. f (f x)

mul two two = (\m.\n.\f. m(n f)) (\f.\x. f (f x)) (\f.\x. f (f x)) =
= \f. (\f0.\x0. f0 (f0 x0)) ((\f1.\x1. f1 (f1 x1)) f)

```

As I understand, after that, calculations in the CBN strategy stop, because in CBN no reduce under abstractions.

is it possible to get 4 in my example after multiplying in the CBN strategy?

# Answer
I don't consider this a full answer because the tool I used to demonstrate the result may not work the same as you seek. Although if it is not what you seek then please clarify.

Using Lambda Calculus Calculator

In the left column add your two definitions separately (copy and paste works). It will convert `\f` to `λf` upon entry.

Below that select the `Active Strategy`.

I will take it that the `call by name` strategy and the option `Outermost First` work the same.

In the upper right enter your expression

Click `Start`

The first reduction will be displayed and show the button

click the button.

The normal form at the end is

Looks like `4` in Lambda Calculus to me.

Again, you will have to decide if that answers your question.

---

Notice that on the right not all of the reductions are beta-reductions, some are delta-reductions.

As those are just helping to simplify the display I think of those as just syntactic sugar substitutions, they do not change the final outcome. In other words they translate to/from the rewrite rules, E.g instead of seeing `two` in the derivation it would show `λf.λx.f (f x)`.

If at the start you use `(\m.\n.\f. m(n f)) (\f.\x. f (f x)) (\f.\x. f (f x))` instead of `mul two two` and click `Start` you will get the same result without the delta-reductions.

---

Your last variation `\f. (\f0.\x0. f0 (f0 x)) ((\f1.\x1. f1 (f1 x1)) f)`  results in `λf.λx0.f(f(f(fx)))` which is not the same as the others. I don't know where you picked up the `0`s in that expression but it is the source of why the output is different.
> 0 votes

---
Tags: lambda-calculus
---


# Question
Title: Remove left recursion from a grammar without necessarily removing epsilon production
> Consider the grammar
>
> $$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$
>
> Construct an equivalent grammar with no left recursion and with minimum number of production rules. $\tag {GATE-CS-1998}$

---

While solving this question, based on the term "minimum number of production rules", I tried as follows:

First removed indirect left recursion and the grammar becomes:

$$S →Aa∣b$$ $$A →Ac∣Aad∣bd∣ϵ$$

Then using the simple method of removing left recursion based on the following :

> $$A \rightarrow A\alpha\_1, |A\alpha\_2| ... | A\alpha\_m | \beta\_1 | \beta\_2 | ... | \beta\_n$$
>
> where no $\beta\_i$ begins with an $A$. Then, we replace the $A$-productions by
>
> $$A \rightarrow \beta\_1A' | \beta\_2 A'| ... | \beta\_nA'$$ $$A' \rightarrow \alpha\_1A' |\alpha\_2A'| ... | \alpha\_m A'| \epsilon$$

Assuming $\beta\_1=bd$ and $\beta\_2=\epsilon$, I get,

$$S →Aa∣b$$ $$A \rightarrow bdA'∣A'$$ $$A' \rightarrow cA'|adA'|\epsilon$$

A rough analysis shows that this grammar worked out by me, is equivalent to the original grammar.

---

Now if we consider the algorithm given in the *Compilers* text by *Ullman et. al*

>

---

In the algorithm above, the authors are assuming the input grammar to be free from $\epsilon$ productions. Is it strictly necessary? Is there any specific case, where not following the algorithm strictly shall lead to wrong answers.

Application of the Ullman algorithm is easy, but it is increasing the number of productions, mainly due to the removal of the $\epsilon$ production

# Answer
If a grammar includes nullable productions, then it may have *hidden left recursion*; a production such as $A\to N A \beta$ where $N$ is nullable. Such a production won't be removed by Ullman's algorithm, but it is nonetheless left-recursive. So it's usual to start by removing $\epsilon$ productions, thus guaranteeing that there are no nullable non-terminals and therefore that all left-recursion is visible.

There is no hidden left recursion in the grammar you are working on, but the easiest way to prove that is to remove the $\epsilon$ productions :-).

Sometimes it is possible to remove nullable productions without increasing the number of productions. You could do that with your grammar if you wanted to, but the easiest algorithmic solution is unlikely to find that modification.
> 2 votes

---
Tags: context-free, formal-grammars, compilers, left-recursion, gate-cs
---


# Question
Title: Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?
I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean function, say sum of products, the minimal SOP expression is somehow related to the Kolmogorov Complexity of the binary string representation. I've done some searching but can't find anything. If you don't know of a relationship but know of related references, please share.

# Answer
The relationship is that a short SOP expression implies a low Kolmogorov complexity, but not vice versa. If you have a short SOP expression, then that is a concise way to compress the string, hence Kolmogorov complexity is low. However, there might be strings that can be compressed in another way even though the SOP expression is long, and those strings would have a low Kolmogorov complexity but a large SOP expression.
> 1 votes

---
Tags: complexity-theory, boolean-algebra, kolmogorov-complexity
---


title: Solving time of large TSP instances

text:
# Question
Title: Solving time of large TSP instances
The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities.

According to Wikipedia, the largest instance solved so far consists of $n=85,900$ cities and that it only took 1.5 years in 2006 to solve it.

How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller $n$ it would take million of years to find an optimal solution via brute force. How can $2^{85,900}$ tours be checked in 1.5 years?

# Answer
> 2 votes
You are asking about a very specific instance of the problem and the solution was published as a paper. If you're really interested you should read that.

The solution itself was done with linear programming relaxation techniques and branch-and-bound. There is also a proof which is 32 MB in size when not compressed.

The proof itself basically gives you a lot of inequalities for the LP instance and then for some of them proves (even by brute force) the soundness in this example. This should give you a lower bound of about 142,381,678.2 and you can relax the original problem to just 265,259 edges. Then using branch-and-bound you just need to check this much smaller instance and you can cut anything with the path being longer than the original solution, 142,382,641.

The paper is from 2008 and the authors checked the proof (just checked, not solved the original problem; solution took 136 CPU years) in about 570 hours, so if you have a reasonably strong computer this should be computable in a few days now.

To exactly answer your question, you can use LP and its dual problem to make upper *and* lower bounds on the solution. If you get good enough equalities for a given problem, you can reduce the instance dramatically.

# Answer
> 1 votes
They didn't use brute force to solve it. They used a smarter method than brute force. I think they used algorithms that don't have any theoretical guarantee that they'll work well on all graphs, but happened to be good enough on that particular graph.

Taken literally, the notion of "the largest instance of travelling salesman problem ever solved" is nonsense. I can easily invent an instance of TSP with one million nodes where I already know the answer, and then solve it immediately (because I know the answer); or invent an easy instance on one million nodes, and then solve it immediately. So I suspect Wikipedia's summary is leaving out important details. As always, don't rely on secondary sources (like Wikipedia or an encyclopedia); instead, follow their citations to the primary source where that claim comes from, and read it to understand more about what is being said.

---
Tags: traveling-salesman
---


# Question
Title: Bound the sum of leaf depth on a complete binary tree of $n$ leaves
A complete binary tree is defined as a tree where each node has either 2 or 0 children.

For a complete binary tree with $n$ leaves, there can be different arrangements of nodes, let's define the maximum depth of such a tree as $d$, it's clear that $d \ge \log\_2n$.

The quantity I'm interested in is, the sum of depth of all leaves: $D$. What's the upper and lower bound of $D$ given $n$ and $d$?

# Answer
> 1 votes
When you construct such a tree and to add two more nodes as offspring to a leaf at depth $x$, what happens to $D$ is you subtract $x$ and add $2(x+1)$, therefore $D\_{new} = D\_{old} + x + 2$.

From this you can see that the best strategy to maximize $D$ is to always add nodes to the lowest node (furthest from root), therefore obtaining a tree that has one leaf on every level (except the 0th where the root is) and two leaves at the lowest level. The depth of this tree will be $(n+1)/2$ ($n$ is always odd for these trees). Therefore $$ D \le \frac{n+1}{2}-1+\sum\_{i=1}^{\frac{n+1}{2}-1}i=\frac{n^2+4n-5}{8}$$ is your upper bound.

On the other hand if you want to minimize $D$ you want to always add children nodes to be closest to the root. Then your depth is $\log\_2(n+1)$ (the last level is one less than depth) and you have again $(n-1)/2$ leaves. Therefore the lower bound is $$D \ge\frac{n-1}{2}\cdot\log\_2(n+1)-1$$ for trees with $2^k -1$ nodes. For nodes with different number of leaves the bound still holds, but it won't be equal.

---
Tags: trees, binary-trees
---


title: Is $\Sigma^*$ countable or uncountable?

text:
# Question
Title: Is $\Sigma^*$ countable or uncountable?
Consider $\Sigma = \\{a,b\\}$. Now $\Sigma^\*$ represents the collection of all possible strings over alphabet $\Sigma = \\{a,b\\}$. As there exists an enumeration procedure for $\Sigma^\*$, it is countably infinite. As $\Sigma^\*$ consists of strings of all lengths, it also consists of strings of infinite length. Let us consider a subset $S$ of $\Sigma^\*$, namely

$$ S = \\{\text{Set of all strings of infinite length}\\}. $$

From Cantor’s diagonalization argument, it can be proved that $S$ is uncountably infinite. But we also know that every subset of a countably infinite set is finite or countably infinite. This leads to a contradiction.

Where did the above argument go wrong?

# Answer
The argument went wrong at the point where you said that $\Sigma^\*$ includes strings of infinite length. Specifically your set $S$ is an empty set. $\Sigma^\*$ includes just an infinite number of strings of arbitrarily large but finite lengths.

As some commenters pointed out infinite strings are in $\Sigma^\omega$ which is uncountable.
> 2 votes

---
Tags: uncountability
---


# Question
Title: Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free
Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \\{w \in \Sigma^\*\mid xw \in L$ for some $x \in R\\}$ is context free.

Hi I've been struggling quite a lot with this question. There's a similar quesion already answered here (Closure of CFL against right-quotient with regular languages)

But the difference here is that we have $xw \in L$ and not $wx \in L$.

Can anyone give some ideas/help?

Thanks in advance.

# Answer
> 1 votes
The *reverse* of a language $L$ is the language $L^R = \\{ w^R : w \in L \\}$, where $w^R$ is obtained from $w$ by reversing the orders of the letters.

The reverse of a context-free language is context-free. This can be shown by starting with a grammar and reversing all production rules, that is, replacing $A \to \alpha$ by $A \to \alpha^R$. Similarly, the reverse of a regular language is regular. This can be shown in many ways: by reversing the arrows in an NFA, by reversing the production rules in a regular grammar, by reversing regular expressions, and so on.

Now define $L/R = \\{ w : wx \in L \text{ for some } x \in R \\}$ and $R \backslash L = \\{ w : xw \in L \text{ for some } x \in R \\}$, and notice that $R \backslash L = (L^R/R^R)^R$. Hence closure under regular right quotient implies closure under regular left quotient.

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


title: Conjuctive Normal Form

text:
# Question
Title: Conjuctive Normal Form
Let f(P,Q,R) be the truth-function defined as follows. f(P,Q,R)=1 if and only if

Q and R have different truth-values; or P and R have the same truth-values. Choose all formulas that are in conjunctive normal form (CNF) and represent the truth-function f.

(P ∨ ¬Q ∨ ¬R) ∧ (¬P ∨ Q ∨ R)

(¬P ∨ Q) ∧ (¬Q ∨ R)

(Q ∧ R) ∨ (¬Q ∧ ¬R) ∨ ¬P

(¬P ∨ Q) ∧ (¬P ∨ R)

# Answer
> 2 votes
You can learn more about CNF on wikipedia.

> In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals \[...\]

So this rules out all formulas in your example that do not satisfy this condition. As for the rest of your question, draw the truth tables of all formulas, and the truth table of f. The correct formulas will be those with the same truth table as f.

---
Tags: logic, first-order-logic, propositional-logic
---


title: Similar problem to Subset Sum?

text:
# Question
Title: Similar problem to Subset Sum?
I've been trying to search for a problem which I think could be similar to Subset Sum. The definition of the problem would be as follows:

Given k $\in$ $\mathbb{Z}$ and S = {$s\_1$,...,$s\_n$} s.t. $s\_i \in \mathbb{Z}$, how many subsets $S' \subseteq S$ exist s.t. $\sum S' \geq k$.

I don't know if this problem has been studied previously, but I can't find anything. Could someone help me?

# Answer
> 1 votes
This problem is not in NP because it is not a decision problem. Instead it would lie in #P because you want it to output the number of accepting paths of a non-deterministic machine.

You can look for some #P problems but I don't think each NP problem has a studied equivalent there.

If you changed it into a decision problem of: 'Is there more (or less) than $l$ subsets with $\Sigma\_{s\in S'}s \ge k$ then this would be a decision problem but since $l$ is bounded by $2^n$ this is still not in NP. It is surely in PSPACE, but I can't put it anywhere lower in the polynomial hierarchy right now.

---
Tags: np-complete, partitions, subset-sum
---


# Question
Title: Hash maps vs extending structs / classes
A hash map that maps keys of type $K$ into values of type $V$, is essentially equivalent to "extending" this type $K$ to also contain an `Option<V>` field.

Implementing this in practice (apart from the bad habits of adding more fields that are irrelevant most of the time), shouldn't the "extension" of $K$ be faster in practice and more memory-friendly? Since hash maps take extra redundant space, and aren't guaranteed to work in $O(1)$ worst case *deterministically* (i.e, not on average) - shouldn't this be the case?

Then how come hash-maps are used so much in practice? What am I missing here?

---

For more context, since it seems I wasn't clear enough in the question - I will provide the full scenario I'm dealing with, where both approaches work.

Lets say I have some collection `Col` of keys with type `K`. Our running example will be `Col:=Graph` and `K:=Node`.

Now, we want run some function on the graph - maybe, BFS. Notice that while running, the BFS algorithm *associates* with each node the boolean label - "was this node explored already".

Now, my question deals with the specific implementation of how we associate this label to the nodes.

We could use a hash-map, mapping between the nodes and the labels. But we could also explicitly add this label as an extra field to the `Node` struct (or class).

So my question is - what are the benefits of each approach? What would be the "better" solution in this case?

# Answer
> A hash map that maps keys of type `K` into values of type `V`, is essentially equivalent to "extending" this type `K` to also contain an `Option<V>` field.

No, it is not; for several reasons:

1. A hashmap gives you a collection of keys, and a fast way to look up a key in the collection. Extending type `K` with an `Option<V>` property won't give you a collection of `K` objects. You still need to define one.
2. Extending `K` is only possible if you actually own all of the code that uses `K` and modifying it isn't unreasonably difficult. Most professional developers are rarely in that position. `K` may be defined or used in code they don't own, and modifying it may be impossible or very hard.
3. The fundamental issue: the proposal of extending `K` for this purpose will only work if you can somehow guarantee that no existing or future code other than your BFS code will ever abuse their ability to see `V` values (e.g. by modifying them) and that no more than one instance of your BFS code will ever run on at the same time (on collections that share `K` objects).

So the fundamental issue is with visibility. The extra `Option<V>` field will be visible to code to which it shouldn't be visible, and that won't just make it irrelevant most of the time; it is much worse: it will actually require all developers who will ever work with extended `K` objects, yourself included, to keep tiptoeing and handholding around `V` values to avoid breaking their intended use, namely, keeping state for one little piece of code somewhere in the code base.

That is fundamentally broken design. That piece of state should be visible only to that piece of code, and to nothing else; not even to another concurrent instance of that very same piece of code. There is no way to enforce that. You can put in a comment and hope people will read it, or have access to the comment in the first place. (They may only be given your code in compiled form.)

The hashmap doesn't have this issue. If you make it local to the BFS code, then nothing else, not even another concurrent instance of the same BFS code, will be able to mess with it.

If you were ever taught to avoid global variables: the `Option<V>` idea is to be avoided for the same reason.
> 3 votes

# Answer
The guarantee that they work in $O(1)$ on average is better than $O(n)$ on average. Even though you don't improve worst-case, you still improve the speed if enough operations are done on the container.

If you just extend $K$ with $V$ you just made a different struct, but it is not a container. I.e. you cannot add $K,V$ pairs there, delete them, find one you're looking for.

You could extend $K$ with $V$ and then use a set and this would be almost equivalent, but not exactly, because in a map each $k\in K$ can map to only one $v\in V$ which wouldn't be the case for a set of pairs. But this depends on the semantics of what you're trying to achieve.

---

Edit for your example - yes, if you don't need the container for looking things up (e.g. because you run BFS and your nodes have references to all neighbors), you don't want to use a hashmap for storing additional data if you can just extend the node. That is not really a use-case for hashmmaps either though. Hashmap is first and foremost a container which you use for storing data and more importantly finding stored data. If you don't need to find the data (because it can be found in another way) there is no reason for you to use it.

If on the other hand your BFS example had nodes iplemented in a way where each node did not have a reference to all its neighbors, but instead had only list of identifiers of neighbor nodes, then hashmap would be a good way to go, with the identifiers being the keys and the nodes themselves (including the visited flag) would be values.

As a last note, if you have found an element in a hashmap, it's usually imlied that you have found a key value pair. Therefore if you have this pair you can get the value in constant time. Some languages even give you an object representing the pair, which is basically equivalent to what you're proposing with extending $k$.
> 2 votes

---
Tags: hash-tables
---


# Question
Title: Point Cloud Complete 3D Area Coverage Path Finding Algorithm
So I have a point cloud, of a 3D object, as an input which I received from a 3D scanner. I would like to generate a path which covers the entire object, meaning I would like to come up with a complete area coverage of the point cloud.

When I say path, I mean an array of points which according to a given dimension of a pixel will cover the entire object.

For example, if I had a robot which is designed to polish a piece of metal. The tool has a certain dimension which at every given moment covers a certain amount of area (pixel size). The robot needs a path to follow in order to cover the entire piece of metal. The metal piece is scanned, and the output of the scan is a point cloud. Now what I want to do is take the point cloud and generate a path for the robot to follow to ensure that the entire piece of metal is covered and polished. So I've read that I can take the slices of the point cloud to help, but I'm not sure what to do with them?

Ideally I would like to know the normal from the object of each point of the path as well.

Thanks a lot for all the help!!

P.S. I'm new at this, so if I'm missing something in my question please comment and I will add it in.

# Answer
> 1 votes
A plausible approach is to compute a 3D convex hull and triangular mesh that describes the surface of the object. Then, compute slices, as you recommended. A slice is the intersection between the object surface and the plane $z=c$ for some constant $c$. You can easily compute the slice from the triangular mesh (intersect the plane with each triangle). This slice is a 2D path through the plane. Now, iterate over values of $c$ from the max to the min, by some small step size, and for each slice, traverse around the slice with your polishing tool.

---
Tags: planning, robotics, path
---


# Question
Title: A query regarding Definition of Circuit Family and Languages
This is a query regarding the definition of ***Circuit Family*** and ***Language*** (in the same Context). The textbook definitions of each are:

**Language:** A function whose inputs and outputs are a finite bit of boolean strings (i.e. members of $\\{0,1\\}^\*$) is a Boolean Function. A Boolean Function f whose output is a single bit is identified as follows: $L\_f=\\{x:f(x)=1\\}⊆ \\{0,1\\}^\*$. We call such sets ($L\_f$) *Languages* or *Decision Problems*.

An alternative definition of **Language** (What is the difference between an algorithm, a language and a problem?): A language is simply a set of strings. If you have an alphabet, such as $Σ$, then $Σ^∗$ is the set of all words containing only the symbols in $Σ$. For example, $\\{0,1\\}^∗$ is the set of all binary sequences of any length. An alphabet doesn't need to be binary, though. It can be unary, ternary, etc. A language over an alphabet $Σ$ is **any subset** of $Σ^∗$.

**Circuit Family:** Let $T∶N→N$ be a function. A $T(n)$-size circuit family is a sequence $\\{C\_n \\}\_{(n∈N)}$ of Boolean circuits, where $C\_n$ has $n$ inputs and a single output, and its size $|C\_n |≤T(n)$ for every $n$. We say that a language L is in $SIZE(T(n))$ if there exists a $T(n)$-size circuit family $\\{C\_n\\}\_{(n∈N)}$ such that for every $x∈\\{0,1\\}^n,x∈L⇔C\_n (x)=1$.

**Query 1:** Do the above definition mean: Any completely unrelated and arbitrary set of circuits such that the first circuit has 1 input, the second circuit has 2 inputs, third circuit has 3 inputs and so on (each circuit having exactly 1 output) qualify as a '*Circuit Family*'? And do all the inputs that give output 1 form a '*Language*' (as a set)?

The idea i am struggling with is the definition seems to imply there need not be any overarching logical relation between the circuits of various sizes to constitute a **Circuit Family** and a **Language** as long as they satisfy this simple input output size criteria? Is that correct or i am missing something?

**Query 2:** Given two circuit families $C\_a$ and $C\_b$. Lets us create a new circuit family $C\_r$ as follows:

1. For each input size $(n, n∈N)$ toss a random coin.
2. If 0 $C\_a(n)∈C\_r$.
3. If 1 $C\_b(n)∈C\_r$ where $C\_a(n)$ and $C\_b(n)$ represents circuits for input size $n$.

Does $C\_r$ and the set of strings accepted by it represent a valid **Circuit Family** and **Language** respectively?

# Answer
> 1 votes
The magic of mathematical definitions is that they provide a complete specification of a concept. You don't need to know anything other than the definition.

A language over an alphabet $\Sigma$ is an arbitrary collection of strings over $\Sigma$. In complexity theory, we usually assume that $\Sigma = \\{0,1\\}$. A circuit family is a sequence of circuits $\mathcal{C} = (C\_n)\_{n \in \mathbb{N}}$, where $C\_n$ is a circuit with $n$ inputs and a single output. The language computed by the circuit family is $$ L(\mathcal{C}) = \\{ x \in \\{0,1\\}^\* : C\_{|x|}(x) = 1 \\}, $$ where $C\_n(x)$ signifies applying the circuit $C\_n$ to the input $x$ of length $n$.

Every sequence of circuits which satisfies this definition is a circuit family. There's nothing more to it.

---

"Circuits are a non-uniform model of computation, whereas Turing machines are a uniform model of computation." Let's try to explain what this means.

A Turing machine $T$ which always halts defines a language as follows: $$ L(T) = \\{ x \in \\{0,1\\}^\* : T(x) = 1 \\}, $$ where $T(x) = 1$ if the machine accepts the input $x$.

If we think of Turing machines as one way to specify an algorithm, then a language of the form $L(T)$ has the feature that the same algorithm is used for all input lengths. In contrast, circuit families can use different "algorithms" for different input lengths.

Turing machines can be converted to circuits: given a Turing machine $T$, we can construct a circuit family $\mathcal{C}$ such that $L(\mathcal{C}) = L(T)$. Moreover, properties of $T$ are reflected by properties of $\mathcal{C}$. For example, if $T$ runs in polynomial time, then the circuits in $\mathcal{C}$ have polynomial size. This is why one way to prove P≠NP is to show that SAT cannot be computed by polynomial size circuits.

The converse isn't possible in general. Indeed, *any* language can be computed by some circuit family (albeit possibly of exponential size), whereas *most* languages are uncomputable.

Here is a perhaps better example of how non-uniformity can help, without trivializing things. The class BPP consists of all languages $L$ for which there exists a polynomial time probabilistic Turing machine $T$ with the following promise:

* If $x \in L$ then for most choices of randomness (at least a $2/3$ fraction), $T$ accepts $x$.
* If $x \notin L$ then for most choices of randomness (at least a $2/3$ fraction), $T$ rejects $x$.

By running $T$ enough times, we can boost the acceptance probability to more than $1 - 2^{-n}$. This means that for every $n$ there is a choice of randomness $r\_n$ for which $T$ decides correctly on *every* input of length $n$. Using these randomness strings as "advice", we can construct a polynomial size circuit family computing $L$.

---
Tags: complexity-theory, digital-circuits
---


# Question
Title: Reducing a CNF formula to a DNF formula in less than exponential time
The easy way is by looking at the $\\{0,1\\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently.

My idea is based upon the following idea: lets take $2$ clausers $C\_1 = ( l\_{1,1} \vee l\_{1,2} \vee ... \vee l\_{1,k})$ and $C\_2 = ( l\_{2,1} \vee l\_{2,2} \vee ... \vee l\_{2,k})$. I construct a DNF version in the following way:

First we write this as $$ \left(( l\_{1,1} \vee l\_{1,2} \vee ... \vee l\_{1,k})\wedge l\_{2,1}\right) \vee ... \vee \left(( l\_{1,1} \vee l\_{1,2} \vee ... \vee l\_{1,k})\wedge l\_{2,k}\right)$$

Then I write this as: $$ \left( l\_{1,1} \wedge l\_{2,1}\right)\vee ... \vee \left( l\_{1,n} \wedge l\_{2,1}\right) \vee ... \vee \left( l\_{1,1} \wedge l\_{2,k}\right)\vee ... \vee \left( l\_{1,n} \wedge l\_{2,k}\right)$$

So far the amount of clauses I have is $k^2$.

If we continue the same process to the next clause, we will have $k^3$ clauses of size $3$ each.

Eventually, if we had $m$ clauses to begin with, we will construct $k^m$ clauses of size $m$ each.

This is a major blow of the size of the formula, might be even worse than simply looking at the $\\{0,1\\}$-table.

Any better attempts? Preferably something that will take less than $2^n$, even less than $2^\frac{3n}{4}$.

# Answer
Miltersen, Radhakrishnan and Wegener construct, in their paper On converting CNF to DNF, a function which has a polynomial size CNF, but whose smallest DNF has size $2^{n-\Theta(n/\log n)}$.

In particular, even if the input CNF has polynomial size, you cannot expect to do better than exponential time, since the output might be that long.
> 3 votes

---
Tags: complexity-theory, reductions, satisfiability, polynomial-time, 3-sat
---


# Question
Title: Turing machine to find maximum of an infinite set
Given a set that is infinite but still countable, does a TM exist that goes over every element in the set and finds the maximum? Is this a computable function?

# Answer
Typically, no, this is not possible. It depends on how the infinite set is represented. (I'm assuming it's a set of integers.)

The usual way to represent a possibly-infinite set $S$ is as a Turing machine $M$: $M$ enumerates all the elements of $S$. For this representation, it is uncomputable to determine the maximum element of $S$. That is, on input $\langle M \rangle$, determining the maximum element enumerated by $M$ is uncomputable. This can be proven using Rice's theorem.

There are other ways to represent possibly-infinite sets, though. The most common is using logical formulas. If the set $S$ is given by a formula $\varphi$ in some logic $\mathcal{L}$ where $S = \\{w : \varphi(w)\\}$, then determining the maximum element of the set $S$ *may* be computable if the logic $\mathcal{L}$ is simple enough. For example, if $\mathcal{L}$ is linear arithmetic (basically only addition, "and", "or", "not", $\<$, and $=$), then determining the maximum is computable (returning $\infty$ if there is no maximum). But if $\mathcal{L}$ also has multiplication, then it's uncomputable.
> 1 votes

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


# Question
Title: Is the following function computable? is it total?
I have the following function:

$f : N \to N $ and $f(n)= \max\_{i \leq w(n)} g\_{i}(n)$
with $g\_1, g\_2,...g\_{w(n)}$ being an enumeration of all computable functions $g\_i$, and $w : N \to N$ being any non-decreasing function.

Please correct me if I am wrong:

1. I don't think this is computable as the enumeration of all total computable functions is enumerable.
2. I am not sure if the function is total as the max element is not defined.
Nothing ensures that we have this maximal element, given that the "set" of all total computable functions is infinite hence again nothing ensures that we have this maximal element.
Not like it is with ordered sets for example where this is ensured via Zorns lemma.
Or am I missing something and it doesn't really matter if we know that this maximal element exists (or do we actually know that this maximal element must exist?), and merely by definition is this function total?

Thanks a lot in advance

# Answer
> 4 votes
Your function is well-defined, that is, total. The value of $f(n)$ is the maximum of the finite set $\\{g\_1(n), \ldots, g\_{w(n)}(n)\\}$. The maximum of a finite set of numbers always exists.

Your function is computable iff $w$ is bounded. Suppose first that $w$ is not bounded, and assume for the sake of contradiction that $f$ were computable. Then $h(n) = f(n) + 1$ would also be computable. Therefore $h = g\_i$ for some $i$. Since $w$ is unbounded, we can find $n$ such that $w(n) \geq i$. Therefore $f(n) \geq g\_i(n) = h(n) = f(n) + 1$, which is impossible.

Suppose next that $w$ is bounded, say $\max\_n w(n) = M$, and let $m$ be the minimal value such that $w(m) = M$. We can compute $f(n)$ as follows: if $n \< m$ then we output the hardcoded value $f(n)$, and otherwise we output $\max(g\_1(n),\ldots,g\_M(n))$.

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


title: reduction from 3SUM to 3ARR-ARITH

text:
# Question
Title: reduction from 3SUM to 3ARR-ARITH
> The 3SUM problem is defined as follows. Given an array A\[1...n\] of numbers, determine whether there exist $i,j,k\in \\{1,\cdots, n\\}$ so that $A\[i\] + A\[j\]+A\[k\] = 0$.

> The 3ARR-ARITH problem is defined as follows. Given three arrays $A\[1..n\], B\[1..n\], C\[1...n\]$ of numbers, determine whether there exist $i,j,k \in \\{1,\cdots, n\\}$ so that $B\[j\] - A\[i\] = C\[k\] - B\[j\].$

When reducing from problem P1 to problem P2, you assume you have a subroutine that solves problem P2 and use this subroutine to solve P1.

> Determine a linear time reduction from 3SUM to 3ARR-ARTIH.

> Determine a linear time reduction from 3ARR-ARITH to 3SUM.

I know a linear time reduction from 3ARR-SUM to 3SUM, where 3ARR-SUM is defined as follows: Given three arrays $A\[1...n\], B\[1...n\], C\[1...n\]$ of numbers, determine whether there exist $i,j,k$ so that $A\[i\]+B\[j\]+C\[k\] = 0$.

The reduction can be described by the following algorithm, where 3SUM is a subroutine that solves the 3SUM problem:

```
3ARR-SUM(A[1...n], B[1...n], C[1...n]):
for i = 1 to n do
    X[i] = 10 * A[i] + 2
    Y[i] = 10 * B[i] + 4
    Z[i] = 10 * C[i] - 6
let A' be an array of 3n 0's
for i = 1 to 3n do
    if (i <= n)
        A'[i] = X[i]
    else if (i <= 2n)
        A'[i] = Y[i]
    else
        A'[i] = Z[i]
if 3SUM(A'[1...3n]) returns (i,j,k) then
    sort (i,j,k) so that i <= j <= k
    return (i, j - n, k - 2n)

```

> I tried rearranging the expressions for 3SUM and 3ARR-ARITH, but it doesn't seem like that helps. I can't think of something similar to the above either. How would I obtain a single array that 3SUM can solve and for which calling 3SUM on the array will solve 3ARR-ARITH?

Also, I can't seem to figure out how to reduce 3SUM to 3ARR-ARITH. It doesn't seem like defining the arrays A,B,C as follows works: $A\[i\] = 10A'\[i\] + 1, B\[j\] = 10B'\[j\] + 2, C\[k\] = 10C'\[k\] + 3$. I have a single array $A'\[1..n\]$ and I want to obtain 3 arrays $A\[1...n\], B\[1...n\], C\[1...n\]$ so that if I call 3ARR-ARITH on these 3 arrays, I will get indices $i,j,k$ so that $B\[j\] - A\[i\] = C\[k\] - B\[j\] $ and $A'\[i\] + A'\[j\] + A'\[k\] = 0.$

# Answer
Let's rewrite the pattern we're looking for in 3ARR-ARITH: $$ A\[i\] - 2B\[j\] + C\[k\] = 0. $$ This should suggest a simple reduction from 3SUM to 3ARR-ARITH, and another simple reduction from 3ARR-ARITH to 3ARR-SUM, which combined with the reduction you mention, results in a reduction from 3ARR-ARITH to 3SUM.
> 2 votes

---
Tags: algorithms, algorithm-analysis, reductions
---


# Question
Title: How do logical and bitwise operators work on numbers? (e.g "2 and not 5")
====TLDR=============================================================

Curious about the behaviour of logical and bitwise logical operations on integers, i.e with
`and` := logical and
`&` := bitwise and
`not` := logical not
`~` := bitwise not

Can anyone explain why `(2 and not 5) = False`, `(2 and 5) = 5`,
`(2 & 5) = 0`, `(2 & ~5) = 2`, and `(2 & not 5) = (2 and ~5) = -6`

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

Today in my computer science lecture (First Year Algorithm Design & Data Abstraction) we were going over the C logical operators. We're still early on in the course, so the information was relatively brief, but the idea was that boolean types are really just integers, where 0 is defined as false, and 1 is defined as true, however, the boolean value of any nonzero integer is also true - so 0 is false and anything else is true, simple enough.

Then we were given an example of using logical operators on numbers, like `(2 && !5) = False`. This makes enough sense to me, 2 is true, and 5 is true, so not 5 is false, thus
`(2 & !5)`\<=\>`(True and False)`, which is false.

Bitwise operators are outside the scope of my course, however this got me curious, as I've been programming for 3 years now and I've never been taught about these properties of booleans, so I opened up my terminal to do some messing around with python, and got some unexpected results...

First, `(2 and not 5)` evaluates to `false`, as expected, however `(2 and 5)` evaluates to `5`. Weird... but `bool(2 and 5)` evaluates to true (evidently, as `5!=0`). So I guess this makes sense, but I don't know where the 5 is coming from, and there's more..

When performing a bitwise and `2 & 5` I get `0`, so false, and using bitwise operators to reproduce the original example "two and not five" as `(2 & ~5)` produces `2`. Combining bitwise and logical operators is even more confusing...
`(2 and ~5)` and `(2 & not 5)` both produce `-6`.

While I'm sure my confusion arises from ignorance to the mechanisms of logical and bitwise operations, I haven't been able to find an exact explanation of the behaviour I'm seeing here. If anyone could take the time to explain how this works, or point me in the direction of some reading that will help me understand, I'd greatly appreciate it.

# Answer
```
5 = 0101
~5 = 1010
2 = 0010
2 & ~5 = 0010 = 2

```

Meanwhile, when you work with logical operators, you work with booleans so you can't plug in a random integer and expect it to have a meaningful result. It's probable that the behaviour of the python interpreter or C compiler is to only look at the first bit of the integer. In C logical is &&, ||, etc.

```
2 = 0010
5 = 0101
2 and 5 = 0 and 1 = 0 = false

~5 = 1010
2 and ~5 = 0 and 1 = 0 = false

```

**edit**

It is implementation dependent. Actually, I read more and C compilers as per the C standard will look only at the values. If it is not zero it evaluates as true. So the above example is wrong but is valid considering that it is basically a choice what to do with that.
> 1 votes

---
Tags: logic
---


# Question
Title: How on-chip multithreading prevents cache misses from stalling a processor pipeline?
On-chip multithreading is considered a powerful performance enhancer technique that enables a processor to handle multiple threads at the same time. If I got the idea right, multithreading avoids pipeline stalls by processing instructions coming from different threads - since no data dependencies exist between different threads (in the textbooks, synchronization points are dropped for convenience), pipelines will never stall. However, authors like Tannenbaum state things like that (Structured Computer Organization, 6th Edition, page 562):

> "... when a memory reference misses the level 1 and level 2 caches, there is a long wait until the requested word (and its associated cache line) are loaded into the cache, so the pipeline stalls. One approach to dealing with this situation, called on-chip multithreading, allows the CPU to manage multiple threads of control at the same time in an attempt to mask these stalls. In short, if thread 1 is blocked, the CPU still has a chance of running thread 2 in order to keep the hardware fully occupied."

I do understand that a pipeline will never stall if the data dependencies of subsequent instructions are eliminated (that is what out-of-order execution does), but if a memory reference is made by an instruction, the pipeline has to stall until the necessary information is retrieved for the main memory. I mean, no further instructions can be processed until the memory is read and the associated word is loaded. However, Tannenbaum and other authors suggest the opposite: while the word in question is being retrieved, additional instructions from other threads can be issued and that makes no sense to me. Can you folks clarify that? Shouldn't memory accesses prevent the pipeline from accepting new instructions, regardless the thread they come from? Thank you!

# Answer
> 3 votes
It's called "out of order execution".

When one instruction stalls, that doesn't mean the whole pipeline stalls. All instructions that don't depend on this one instruction can continue. Sometimes there is enough work to do even with a single thread to keep all the execution units busy even if one instruction stalls for 40 cycles. But with hyperthreading, you have a whole thread whose instructions are *all* independent of the stalling instruction, and which can all continue executing.

# Answer
> 0 votes
it simply means that when one thread (say t1) blocks because of a memory stall, the system will schedule another thread (say t2) to run, while the memory stall is being resolved.

---
Tags: computer-architecture, parallel-computing
---


# Question
Title: Why is behavior included in the definition of a data structure?
When reading about ADT's and data structures it is common that the ADT Stack is implemented in at least two ways. Either based on an Array or Linked List. From these examples I tend to think that the way in which the data is organised determines the efficiency of the behaviors that work on that data. So if someone was to ask me what a data structure is, I would have to say organised data or structured data.

Goodrich and Tamassia: "A data structure is a systematic way to organise and access data"

Wiki: "a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data"

A data structure to me seems like a particular way the organise the data to enable efficient behaviors. Why is it necessary to include access to the data in the definition of a data structure?

# Answer
You have to make a distinction between abstract data structures and "data structure".

An abstract data structure (for instance the stack) is usually understood as the description of a collection of operations, and the semantic expected from those operations. It is only a specification, an interface.

A data structure (for instance a doubly-linked list) is indeed a way to organize data in memory, usually presented together with some operations on it. A data structure is thus usually given as an implementation of some ADT, but I would not say that this is necessary.

That being said, this distinction is mostly useful when learning about algorithms, as there is no theory relying on those notions. Definitions will vary depending on the teacher or the particular book you are looking at. It is useful to make this distinction because you can imagine taking any ADT and realizing it with any data structure (so I can try to implement a stack using a binary tree, say), thus giving you many potential solutions, some of them better than others.
> 1 votes

# Answer
The definition given in this Textbook says that

> A data structure is a way to store and organize data in order to facilitate access and modifications.

Again, highlighting key words:

> A data structure is a **way to store and organize data** in order to facilitate **access** and **modifications**.

---

Now, analogous to real world, if we want to store something, there are multiple ways.

**Example :** We want to store our Office Uniforms

* *One way is to pile them up, one on top of other. So, you come, keep your uniform, and at next day, pick the topmost uniform, as it is easy to pick.
What will happen? You essentially end up wearing same clothes again and again.*
* *Another way is to use Hangers, and Closet Rod. Assuming you have 7 clothes, and Office is 7-days working. So, you come, keep your uniform at one end of closet, and next day, pick clothes from another end.
What will happen? You will realize that after 7 days, you will have to wear same clothes again, but at least for tomorrow, you will have new uniform.*

So, we essentially have **Stored Data**, and in fact **organized data** in proper form. Which is Best? Well, it depends. Piling up is convenient, but Hanger One is Better for Choices. Note that even in pile up, or hanger we might want to **access** any clothes in between the pile. And may want to **modify**, maybe wash or iron that clothes.

Thus, when you are **storing** something, you should be able to **access** them.

---

In computer, we store data at different **memory locations**, if definition was limited to ***organized data or structured data,*** we missed out important point that we should be able to access data. In every data structure, you should be able to **access** each and every data, else storing them would be of not use.

By accessing, we mean that sufficient **information** and **techniques** should be there to get each and every data.

* **Array :** We should know actual length of array, and starting address, we then can traverse linearly
* **Linked List :** We should know address of head node, we then can traverse linearly
* **Tree :** We should know address of Root Node, we then can traverse in Pre-Order, Post-Order or In-Order. These techniques guarantee that each and every element will be accessed.

Thus, **accessing** itself means sufficient techniques and information are there. Moreover, this property of **accessing** should be preserved even after applying operations.

**Example :** Linked List Insertion

Here, we have three steps.

```
 - Establish link : 2 to New
 - Establish link : New to 3
 - Breaking link :  2 to 3

```

An observation will help us know that `Establish link : 2 to New` will automatically do `Breaking link : 2 to 3`

Thus, we have 2 steps only, this can be done in `2!` ways i. e. `2` ways:

**WAY1:**

```
 - Establish link : 2 to New
 - Establish link : New to 3

```

**Is this correct?**

> No!

**Why?**

> While establishing link 2 to New, we have broken link 2 to 3. Now, we can't establish link New to 3, as we have lose **access** to 3. Initially, 2 has access of address of 3. But, now we don't have.

**What's the correct way then?**

**WAY2:**

```
- Establish link : New to 3
- Establish link : 2 to New

We can get address of 3, as it is pointed by 2, and we have broken link later on.

```

Thus, you can see that **accessing** is important part of Data Structures Definition. There are Multiple way to do certain operation on Data Structures, this **access** helps us in putting restrictions on some of these way.

After doing any operation, data structure should remain a data structure. If definition was limited to ***organized data or structured data***, then after doing **Way 1**, definition of data structure was not violated. But definition get violated in **Way 1**, if we add **access** part in definition, and we came to know that this way isn't correct!

---
> 0 votes

---
Tags: data-structures
---


# Question
Title: What are the time complexities of finding kth element from beginning and kth element from end in a doubly linked list
What are the time complexities of finding kth element from beginning and kth element from end in a doubly linked list? Assume n \> k, where k is a constant and n is a total number of nodes in the linked list.

O(1) and O(n)

O(1) and O(1)

O(n) and O(1)

O(n) and O(n)

# Answer
> 0 votes
In this case, **k** can vary from **1 to n.**

## 1

> We might be interested in finding 1st from Beginning and 1st from End.

> Time Complexities of these are respectively $O(1)$ and $O(n)$.

## OR

## n

> We might be interested in finding nth Element from Beginning (Last Element of Linked List) and nth Element from End (First Element of Linked List)

> Time Complexities of these are respectively $O(n)$ and $O(1)$.

Since, we are not sure of what **k** is, we will **try to find** the **Average Case**

Now, Average Time Complexity can be calculated as Sum of Time Complexities Of All Cases divided by Total number of Cases.

## Now, **finding kth element from beginning**

$$T=\frac{1+2+3+.......+(n-2)+(n-1)+n}{n}$$

Using formula, $$T=\frac{\frac{n(n+1)}{2}}{n}$$

Simplifying $$T=\frac{n+1}{2}$$

Thus, $$T=O(n)$$

## Now, **finding kth element from end**

$$T=\frac{n+(n-1)+(n-2)+.......+3+2+1}{n}$$

Using formula, $$T=\frac{\frac{n(n+1)}{2}}{n}$$

Simplifying $$T=\frac{n+1}{2}$$

Thus, $$T=O(n)$$

Thus, **Average Case Time Complexities** in both cases will be $O(n)$

---
Tags: data-structures, linked-lists
---


title: How to reduce 3-SAT to Set Splitting

text:
# Question
Title: How to reduce 3-SAT to Set Splitting
I've been reading through Garey & Johnson's "Computers and intractability", and a problem SP4 caught my attention. It is stated as following:

Given a collection $C$ of subsets of a finite set $S$, state if there's a partition into two subsets $S\_1$ and $S\_2$ such that no subset in $C$ is entirely contained in either $S\_1$ or $S\_2$?

The book says a Not-All-Equal-3SAT should be reduced to the stated problem to prove the NP-completeness sof the latter, but I can't seem to find a way. How to reduce NAE-3SAT to this problem?

**Extra Question**: how does one write an algorithm for such a partition?

I am aware about this discussion, but I couldn't find a link between reduction such as NAE-3SAT - 3COL - Set Splitting. If you can, please explain it.

# Answer
> 0 votes
Here is a reduction from NAE3SAT to your problem.

Given an instance $C\_1 \lor \cdots \lor C\_m$ of NAE3SAT, we construct an instance of your problem as follows:

* $S$ is the set of literals.
* $C$ consists of the sets $C\_1,\ldots,C\_m$ (considered as sets of literals) together with the sets $\\{ x\_i, \lnot x\_i \\}$ for each variable $x\_i$.

A valid solution to this instance consists of a partition of $S$ into two sets $S\_1,S\_2$, which we can think of as a truth assignment to the variables: $x\_i \in S\_1$ iff $\lnot x\_i \in S\_2$. Think of the literals in $S\_1$ as true. Then each clause must contain both true literals (literals in $S\_1$) and false literals (literals in $S\_2$), i.e., is should be satisfied as NAE.

---
Tags: np-complete, 3-sat
---


# Question
Title: Can it be NP hard to calculate the value of a function?
So, I've just begun dabbling in complexity theory and I'm somewhat confused as to the relationship between NP-hardness and function computation. As far as I've understood, NP-hardness is defined for decision and search problem but I've also seen mention of functions whose values are considered NP-hard to compute.

My question is, then, are there functions $f: \mathbb{N} \rightarrow \mathbb{N}$ whose values are NP-hard to calculate? If not, what is the appropriate notion of hardness for calculating the value of a function?

# Answer
> 3 votes
Yes. For instance, define $f$ so that $f(x)=1$ if $x$ is an encoding of a 3-colorable graph, or $f(x)=0$ otherwise. Since 3-coloring is NP-hard, it is NP-hard to compute $f$. (If you could compute $f$ efficiently, you could solve 3-coloring efficiently.)

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


# Question
Title: Finding a 'short' binary sequence not contained in a given binary sequence
Let $k\>1$ be an integer, let $n = 2^k$. Let $s: \\{0, \ldots, n-1\\} \to \\{0,1\\}$ be any binary sequence of length $n = 2^k$. There are $n - k$ coherent subsequences of $s$ having length $k$, and the total number of binary sequence of length $k$ is $n=2^k$, so there are some binary sequences of length $k$ that are **not** a subsequence of $s$.

**Question.** Is there an algorithm with time $O(n)$ outputting one binary sequence of length $k$ that is **not** a subsequence of $s$?

# Answer
Construct a suffix tree for your string. If your string contained all $2^k$ substrings of length $k$, then the first $k$ levels of the suffix tree, ignoring edges labelled \\$, would be a complete binary tree, and moreover, in the first $k-1$ levels, all edge labels have length $1$. Since this is not the case, one of the following must happen:

* Some edge label in the first $k-1$ levels has length more than $1$. Take such an edge label as high up in the tree as possible. In spells a substring $p$ of length at most $k$ which does occur in the word, but if we flip the final bit, then we get a substring $p'$ which doesn't.
* All edge labels in the first $k-1$ levels have length exactly $1$. In that case, after removing edges labelled \\$, the first $k$ levels cannot form a complete binary tree. In particular, some node, corresponding to a substring $p$ of length less than $k$, has a child whose label starts with $\sigma \neq \\\\$$, but no child whose label starts with $\overline{\sigma}$. Thus $p\overline{\sigma}$ does not occur in the word.

Here is an example: Let $k = 2$, and consider the word $0011$.

After removing edges labeled \\$, the root has two outoing edges labelled $0,1$; its $0$-child has two outgoing edges lablled $011\\\\$$ and $11\\\\$$; and its $1$-child has a single outgoing edge $1\\\\$$. Thus the subtring $10$ is missing.

Here is another example: Again let $k=2$, and consider the word $0101$.

After removing edges labeled \\$, the root has two outgoing edges labelled $01,1$. Thus the substring $00$ is missing. The $1$-child has a single outgoing edge labelled $01\\\\$$, and so the substring $11$ is also missing.
> 1 votes

---
Tags: algorithms, subsequences
---


# Question
Title: How to reduce seating families at tables to maximum flow?
Problem:
We have $p$ different families with $1 \leq i \leq p$ members for the $i$-th family. We also have $q$ tables where table $t\_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a family sitting on the same table.

I need to reduce this to a maximum flow problem and came up with the following idea:

We have a source node which is connected to every family. The flow between the source and a family is the number of members the family has. On the right side we have the destination source which is connected to every table and has a flow of the table capacity.

How should we properly connect the families and tables? My idea is that every family has a connection to every table, but I am unsure what the flow capacity would be there.

# Answer
Create vertices

* $s$, $t$
* $f\_1, f\_2, ..., f\_n$ for each of the $n$ families.
* $t\_1, t\_2, ..., t\_m$ for each of the $m$ tables.

Create edges

* from $s$ to $f\_i$ with capacity the size of the $i$th family.
* from $f\_i$ to $t\_j$ with unit capacity
* from $t\_j$ to $t$ with the capacity the size of the table.

This ensures that each family sends at most one person to each table, and that each table gets at most its capacity many guests.
> 1 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Minimum number of edges to remove from a graph, so that MST contains a certain edge
Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For doing so, we are allowed to remove some edges from the graph. But I don't want to remove too many edges. Is there an efficient algorithm that can find the minimum number of edges to remove before $e$ becomes a member of MST?

I am particularly interested in that minimum value, and not the edges to remove.

I think there is a way to find a spanning tree that contains $e$. All we have to do is to insert a dummy node between the two nodes that are connected by $e$. But I doubt this helps. Any hint would be appreciated.

# Answer
> 1 votes
An edge $uv$ is in some MST if and only if it is a minimum-weight edge of some cut. So we need to find a $uv$-cut with a minimum number of edges whose weight is strictly less than $w(uv)$. Once those edges are removed, $uv$ will be in some MST.

Algorithmically, any min $st$-cut algorithm, applied on the subgraph of edges of weight less than $w(uv)$, will give us the answer. For instance you can use a max $uv$-flow algorithm to find the cut, if you don't know fancier algorithms.

---
Tags: algorithms, graphs, network-flow, minimum-spanning-tree
---


title: Computing Earley Parsing Steps

text:
# Question
Title: Computing Earley Parsing Steps
I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\\{a,b,c\\}$:

\begin{align\*} Z & \to S\\ S & \to a\\,|\\,b\\,|\\,c\\,|\\,aa\\,|\\,bb\\,|\\,cc\\,|\\,aSa\\,|\\,bSb\\,|\\,cSc \end{align\*}

For instance, the string `abcba` is derived as: $$ Z\to S\to aSa\to abSba\to abcba $$

# Answer
When I follow the algorithm steps, these are the Earley states I get:

$$ \begin{array}{|c|} \hline S\_{0}\\ \hline \begin{array}{ccc|c} (1) & Z\to\bullet S & ,0 & \text{start rule}\\ (2) & S\to\bullet a & ,0 & \text{predict from (1)}\\ (3) & S\to\bullet b & ,0 & \text{predict from (1)}\\ (4) & S\to\bullet c & ,0 & \text{predict from (1)}\\ (5) & S\to\bullet aa & ,0 & \text{predict from (1)}\\ (6) & S\to\bullet bb & ,0 & \text{predict from (1)}\\ (7) & S\to\bullet cc & ,0 & \text{predict from (1)}\\ (8) & S\to\bullet aSa & ,0 & \text{predict from (1)}\\ (9) & S\to\bullet bSb & ,0 & \text{predict from (1)}\\ (10) & S\to\bullet cSc & ,0 & \text{predict from (1)} \end{array} \\\hline \end{array} $$

$$ \begin{array}{|c|} \hline S\_{1}\\ \hline \begin{array}{ccc|c} (1) & S\to a\bullet & ,0 & \text{scan from } S\_{0}(1)\\ (2) & S\to a\bullet a & ,0 & \text{scan from } S\_{0}(4)\\ (3) & S\to a\bullet Sa & ,0 & \text{scan from }S\_{0}(7)\\ (4) & S\to\bullet a & ,1 & \text{predict from (3)}\\ (5) & S\to\bullet b & ,1 & \text{predict from (3)}\\ (6) & S\to\bullet c & ,1 & \text{predict from (3)}\\ (7) & S\to\bullet aa & ,1 & \text{predict from (3)}\\ (8) & S\to\bullet bb & ,1 & \text{predict from (3)}\\ (9) & S\to\bullet cc & ,1 & \text{predict from (3)}\\ (10) & S\to\bullet aSa & ,1 & \text{predict from (3)}\\ (11) & S\to\bullet bSb & ,1 & \text{predict from (3)}\\ (12) & S\to\bullet cSc & ,1 & \text{predict from (3)}\\ (13) & Z\to S\bullet & ,0 & \text{complete from (1) and }S\_{0}(1) \end{array} \\\hline \end{array} $$

$$\begin{array}{|c|} \hline S\_{2}\\ \hline \begin{array}{ccc|c} (1) & S\to b\bullet & ,1 & \text{scan from } S\_{1}(5)\\ (2) & S\to b\bullet b & ,1 & \text{scan from } S\_{1}(8)\\ (3) & S\to b\bullet Sb & ,1 & \text{scan from } S\_{1}(11)\\ (4) & S\to\bullet a & ,2 & \text{predict from (3)}\\ (5) & S\to\bullet b & ,2 & \text{predict from (3)}\\ (6) & S\to\bullet c & ,2 & \text{predict from (3)}\\ (7) & S\to\bullet aa & ,2 & \text{predict from (3)}\\ (8) & S\to\bullet bb & ,2 & \text{predict from (3)}\\ (9) & S\to\bullet cc & ,2 & \text{predict from (3)}\\ (10) & S\to\bullet aSa & ,2 & \text{predict from (3)}\\ (11) & S\to\bullet bSb & ,2 & \text{predict from (3)}\\ (12) & S\to\bullet cSc & ,2 & \text{predict from (3)}\\ (13) & S\to aS\bullet a & ,0 & \text{complete from (1) and }S\_{1}(3) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S\_{3}\\ \hline \begin{array}{ccc|c} (1) & \boldsymbol{S\to c\bullet} & ,2 & \text{scan from } S\_{2}(6)\\ (2) & S\to c\bullet c & ,2 & \text{scan from } S\_{2}(9)\\ (3) & S\to c\bullet Sc & ,2 & \text{scan from } S\_{2}(12)\\ (4) & S\to\bullet a & ,3 & \text{predict from (3)}\\ (5) & S\to\bullet b & ,3 & \text{predict from (3)}\\ (6) & S\to\bullet c & ,3 & \text{predict from (3)}\\ (7) & S\to\bullet aa & ,3 & \text{predict from (3)}\\ (8) & S\to\bullet bb & ,3 & \text{predict from (3)}\\ (9) & S\to\bullet cc & ,3 & \text{predict from (3)}\\ (10) & S\to\bullet aSa & ,3 & \text{predict from (3)}\\ (11) & S\to\bullet bSb & ,3 & \text{predict from (3)}\\ (12) & S\to\bullet cSc & ,3 & \text{predict from (3)}\\ (13) & S\to bS\bullet b & ,1 & \text{complete from (1) and } S\_{2}(3) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S\_{4}\\ \hline \begin{array}{ccc|c} (1) & S\to b\bullet & ,3 & \text{scan from } S\_{3}(5)\\ (2) & S\to b\bullet b & ,3 & \text{scan from }S\_{3}(8)\\ (3) & S\to b\bullet Sb & ,3 & \text{scan from } S\_{3}(11)\\ (4) & \boldsymbol{S\to bSb\bullet} & ,1 & \text{scan from } S\_{3}(13)\\ (5) & S\to\bullet a & ,4 & \text{predict from (3)}\\ (6) & S\to\bullet b & ,4 & \text{predict from (3)}\\ (7) & S\to\bullet c & ,4 & \text{predict from (3)}\\ (8) & S\to\bullet aa & ,4 & \text{predict from (3)}\\ (9) & S\to\bullet bb & ,4 & \text{predict from (3)}\\ (10) & S\to\bullet cc & ,4 & \text{predict from (3)}\\ (11) & S\to\bullet aSa & ,4 & \text{predict from (3)}\\ (12) & S\to\bullet bSb & ,4 & \text{predict from (3)}\\ (13) & S\to\bullet cSc & ,4 & \text{predict from (3)}\\ (14) & S\to cS\bullet c & ,2 & \text{complete from (1) and } S\_{3}(3)\\ (15) & S\to a S\bullet a & ,0 & \text{complete from (4) and } S\_{1}(3) \end{array} \\\hline \end{array}$$

$$\begin{array}{|c|} \hline S\_{5}\\ \hline \begin{array}{ccc|c} (1) & S\to a\bullet & ,4 & \text{scan from } S\_{4}(4)\\ (2) & S\to a\bullet a & ,4 & \text{scan from } S\_{4}(7)\\ (3) & S\to a\bullet Sa & ,4 & \text{scan from } S\_{4}(10)\\ (4) & S\to aSa\bullet & ,0 & \text{scan from } S\_{4}(15)\\ (5) & S\to\bullet a & ,5 & \text{predict from (3)}\\ (6) & S\to\bullet b & ,5 & \text{predict from (3)}\\ (7) & S\to\bullet c & ,5 & \text{predict from (3)}\\ (8) & S\to\bullet aa & ,5 & \text{predict from (3)}\\ (9) & S\to\bullet bb & ,5 & \text{predict from (3)}\\ (10) & S\to\bullet cc & ,5 & \text{predict from (3)}\\ (11) & S\to\bullet aSa & ,5 & \text{predict from (3)}\\ (12) & S\to\bullet bSb & ,5 & \text{predict from (3)}\\ (13) & S\to\bullet cSc & ,5 & \text{predict from (3)}\\ (14) & S\to bS\bullet b & ,3 & \text{complete from (1) and } S\_{4}(3)\\ (15) & S\to aS\bullet a & ,0 & \text{complete from (1) and } S\_{4}(15)\\ (16) & Z\to S\bullet & ,0 & \text{complete from (4) and } S\_{0}(1) \end{array} \\\hline \end{array}$$

Since $S\_5$ contains $Z\to S\bullet$ we conclude that `abcba` was successfully derived.
> 0 votes

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


title: Chaitin's constant is normal?

text:
# Question
Title: Chaitin's constant is normal?
According to this source, Chaitin's constant $\Omega$ is normal.

> Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Indeed, each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits.

Source (Wikipedia)

Furthermore, the definition of normal is that each digit occurs with equal probability $1/b$. And that each duets of digits occur with $1/b^2$ probability and every triplets occurs with probability $1/b^3$ and so on.

Chaitin's omega is calculated via

$\Omega = \sum\_{p \in halts} 2^{-|p|}$

Writing $\Omega$ in binary, we obtain a list of 0 and 1. For example,

```
2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

```

Clearly, we can see that the position of each bits corresponds to the halting state of the program of length corresponding to the bit.

**Here is what I am struggling with**

If $\Omega$ is indeed normal, then it means that exactly 50% of programs halt and exactly 50% do not. This seems very counter intuitive.

For example, suppose I generate java programs by randomly concatenating single characters. The majority of them, I would guess more than 99.99% would not even compile. Would this not imply that at least 99.99% of them will not halt? How do we justify that exactly half will halt and exactly half will not, by virtue of $\Omega$ being normal.

Or is wikipedia incorrect about $\Omega$ being normal?

# Answer
> 10 votes
In contrast to your example, Chaitin's constant is *not* defined as follows:

$$ \Omega = \sum\_{n\colon \text{$n$th program halts}} 2^{-n}. $$

Instead, there is a set $\Pi \subseteq \\{0,1\\}^\*$ of allowed programs which is prefix-free (no string is a prefix of another string). Each of the programs in $\Pi$ is legal (this negates your Java example). If the programs are encoding in unary then it is indeed the case that the $n$th program has length $n$, and then your definition of $\Omega$ works. But for other encodings, the definition of $\Omega$ is

$$ \Omega = \sum\_{ p \in \Pi\colon p \text{ halts} } 2^{-|p|}, $$ where $|p|$ is the length of the binary string $p$. Kraft's inequality shows that $\sum\_{p \in \Pi} 2^{-|p|} \leq 1$.

Chaitin's constant is *algorithmically random*: the (prefix) Kolmogorov complexity of the first $n$ bits is $n - O(1)$. To show this, note first that $\Omega\_n$, the first $n$ bits of $\Omega$, suffice to determine whether a program of length $n$ (under the encoding $\Pi$) halts or not. Indeed, as a fraction, $\Omega\_n \leq \Omega \< \Omega\_n + 2^{-n}$. Run all programs in parallel, and whenever $p$ stops, add $2^{-|p|}$ to some counter $C$ (initialized at zero). Eventually $C \geq \Omega\_n$ (since $C \to \Omega$ from below). At this point, if the input program of length $n$ didn't halt, then you know that it doesn't halt, since otherwise $\Omega \geq C + 2^{-n} \geq \Omega\_n + 2^{-n}$.

Given this, suppose that for some $K\>0$ and infinitely many $n$, you could compute $\Omega\_n$ using $n - K$ bits. For each such $n$, you can find a string whose Kolmogorov complexity is larger than $n$, by considering the output of all halting programs of length at most $n$. For large enough $K$, the result is a program of length at most $n$ for computing the a string whose Kolmogorov complexity is more than $n$. This contradiction proves that for some $K$, the Kolmogorov complexity of $\Omega\_n$ is at least $n-K$.

Algorithmic randomness of $\Omega$ implies, in particular, that the frequency of 0s and 1s in its binary expansion tends to 1/2. Indeed, suppose that for some (rational) $\epsilon \> 0$ there exist infinitely many $n$ such that the fraction of 1s in $\Omega\_n$ is at most $1/2-\epsilon$. Since there are only at most $2^{h(1/2-\epsilon)n}$ strings with at most $1/2-\epsilon$ many 1s, we can compress $\Omega\_n$ to size $h(1/2-\epsilon)n + 2\log n + C\_\epsilon$ (the constant $C\_\epsilon$ depends on $\epsilon$ since the program needs to know $\epsilon$). However, this is $n - \omega(1)$, contradicting the algorithmic randomness of $\Omega$.

# Answer
> 0 votes
Your mistake is on the following line:

> If $\Omega$ is indeed normal, then it means that exactly 50% of programs halt and exactly 50% do not.

Nope. That's not what "normal" means. Or, to say it another way: Define $d\_0(n)$ to be the number of bits that are a 0, in the first $n$ bits of the base-2 expansion of $\Omega$. Saying that $\Omega$ is normal implies that

$$\lim\_{n \to \infty} {d\_0(n) \over n} = 1/2.$$

In other words, "normal" is an asymptotic notion. It means that as you look far enough into the bits of $\Omega$, on average about half of them will be 0's. (Similarly, about half with be 1's.)

However, this says nothing about the first few bits of $\Omega$. For instance, there is no implication that the binary expansion $\Omega$ starts out as 0.01... or at anything else -- and there is no implication that $\Omega$ is close to 1/2. $\Omega$ might be close to 0, or close to 1, or anywhere in between; that doesn't contradict being normal, and being normal doesn't imply anything about how large $\Omega$ is.

# Answer
> -1 votes
Yeah I also found it weird when looking through Wikipedia. after reading the most upvoted response here, I looked through all references on Wikipedia, none of them mention Chaitin's constant being normal. Seems like someone misunderstood something and added that by mistake, and unfortunately Wikipedia is done by people so such things happen... Fixed the Wikipedia article.

---
Tags: halting-problem
---


# Question
Title: What would be the conseuqences of BQP = NEXPTIME?
On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly unlikely scenario that $BQP = PSPACE = NEXP$. What would the implications be? I assume this would render P vs NP completely irrelevant with a quantum computer as $NP \subset NEXPTIME$ and therefore, if $BQP = NEXP$, $NP \subset BQP$. Allowing us to not only solve $NP$ complete problems but even harder problems. I imagine this would be quite groundbreaking as that would mean things like solving chess would be very much possible. This is not at all likely but it cannot be entirely ruled out to my knowledge.

# Answer
> 2 votes
It is known that $BQP \subseteq PSPACE \subseteq EXP \subseteq NEXPTIME$.

If $BQP = NEXPTIME$ then $PSPACE = EXP $ and $ EXP = NEXPTIME $.

This would imply $L = P$ and $P = NP$.

---
Tags: complexity-theory, time-complexity, quantum-computing
---


title: Concorde time efficiency

text:
# Question
Title: Concorde time efficiency
What is the efficiency of Concorde TSP solver program. And is it have any weaknesses? I build my own exact solver and I want to compare it to Concorde. What would be the best way to do this?

# Answer
> 4 votes
In the paper "Evolving L-Systems as an intelligent design approach to find classes of difficult-to-solve Traveling Salesman Problem instances" by Farhan Ahammed and Pablo Moscato, the authors show how to build instances which causes Concorde to run in its worst-case time.

So, you may compare your solver with Concorde on instances generated that way, besides comparing on randomly generated instances and/or specific test-case instances.

Here is the paper's abstract:

> The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde \[2\], the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.

# Answer
> 0 votes
Concorde works with symmetric instances of the TSP, that is, where the distance from city A to city B is the same as the distance from B to A. To solve an asymmetric instance with Concorde one would need to reduce the problem to a symmetric instance by node splitting. Targeting the asymmetric TSP directly is one possibility to make large improvements on Concorde's performance.

# Answer
> 0 votes
If anyone is interested in hard instance of TSP, I extracted the optimal tour found by Concorde from this website : http://www.or.uni-bonn.de/~hougardy/HardTSPInstances.html
There is a link to their paper in it.

Some of those instances are solved in hours by Concorde, while having less than 200 cities.

See : https://github.com/Butanium/monte-carlo-tree-search-TSP/tree/master/tsp\_instances/HARD

---
Tags: traveling-salesman
---


# Question
Title: Polynomial-time Computable $f \circ g$. What does this implies for $f$ and $g$
Suppose that $f$ and $g$ are functions and $f \circ g$ is polynomial computable.

a) is it true that $f$ is also polynomial computable

b) is it true that $g$ is also polynomial computable

c) if we replace "polynomial" by "logarithmic" would the previous questions be true?

# Answer
> 1 votes
What if $f = 0$?

What if $g = 0$ and $f(0) = 0$?

---
Tags: computability, polynomial-time
---


# Question
Title: Are there any complexity classes that can be solved in Polynomial Time that are not in PSPACE?
These would be problems solvable in Polynomial time with and only with pseudo-polynomial or Exponential Space. Do such problems exist? if so which complexity class are they? If not can you prove that every problem solvable in polynomial time is also solvable in polynomial space?

# Answer
> 0 votes
The space complexity is always bounded by the time complexity, since you cannot access more than $t(n)$ cells if you run for $t(n)$ time.

So the answer is that there aren't such problems.

# Answer
> 1 votes
No. The amount of space used is upper-bounded by the running time. Each step of the Turing machine can only move one place on the tape. Therefore, $P \subseteq PSPACE$.

---
Tags: time-complexity, space-complexity
---


# Question
Title: Range queries with O(N log N) build and O(1) query
I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this?

I know this is possible for range min and range sum. But both of these are special because min is idempotent and sum is invertible.

# Answer
> 0 votes
**Sparse Tables**

For each index i of array, we store minimum of blocks of 2 powers till block index's doesn't exceed array length.

Any non-negative number can be uniquely represented as a sum of decreasing powers of two. This is just a variant of the binary representation of a number.

E.g. $13 = (1101)\_2 = 8 + 4 + 1$.

E.g. $\[2, 14\] = \[2, 9\] \cup \[10, 13\] \cup \[14, 14\]$,

https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404

https://cp-algorithms.com/data\_structures/sparse-table.html

https://github.com/e-maxx-eng/e-maxx-eng/blob/master/src/data\_structures/sparse-table.md

Edit: Updating with codechef's link for handling general associativity, thanks D.W.

---
Tags: algorithms, time-complexity, data-structures
---


# Question
Title: Data structure for finding lowest element in range
Consider the following setting: There are tasks $T = \\{T\_i\\}\_{i=1}^n$ with priorities $p\_i$, and locations $x\_i \in \mathbb{R}^2$. Given a location $y \in \mathbb{R}^2$, I would like to find and pop the task with the highest $p\_i$ in an $L\_\infty$ ball of radius $r$ centered at $y$. What are some data structures that might make this more efficient?

One could use a ball tree to get efficient range queries, but then you have to iterate over all the tasks in range since they won't be sorted by priority. You could also maintain a sorted list of tasks, but then you might need to iterate over all of them if no tasks are in range of the query.

# Answer
> 1 votes
A plausible data structure might be a quadtree, where you augment each internal node with the priority of the highest-priority task contained within that region. This will let you do a best-first search, i.e., search first in regions that contain high-priority tasks, and avoid recursing into any region whose highest-priority task is of a lower priority than the best task found so far.

To elaborate a bit more, if $x$ is a tree node, let $p(x)$ denote the priority field associated with $x$ (i.e., the priority of the highest-priority task in the region associated with $x$). Note that $x$ has four children, let's call them $y\_1,\dots,y\_4$. Suppose we discover that the highest-priority task is under $x$, and we want to pop (delete) that task. Then this task must be under one of $y\_1,\dots,y\_4$, say $y\_i$. Now we recursively pop (delete) that task from $y\_i$, update $p(y\_i)$, and then we can update $p(x)$ using the relation

$$p(x) = \max(p(y\_1),\dots,p(y\_4)).$$

Thus updating $p(x)$ can be done in $O(1)$ time. In the end, we do one update per node along the path from the root to the highest-priority task. This means that the cost to update all of the priority fields in the tree is at most the cost to search the tree to find the highest-priority task.

---
Tags: data-structures
---


title: Swaps Used in Selection Sort

text:
# Question
Title: Swaps Used in Selection Sort
I was trying to come up with a formula for the number of swaps used in selection sort. So we know that selection sort gives the minimum number of swaps to sort an array.

The formula I came up with is given an unsorted array and it's descending or ascending order. We find the number of elements dissimilar to the sorted array. When we subtract 1 from this number we can get the number of swaps.

For example, Let the array be

\[3, 4,2 ,9,1\]

Using selection sort for descending order:

\[9,4,2,3,1\] ---\[9,4,3,2,1\] which gives a total of 2 swaps

My logic:

Descending array is \[9,4,3,2,1\]. So three elements are in incorrect position which are 9, 3 and 2. So, 3-1 = 2 swaps.

Let us consider ascending order:

Section sort:

\[1,4,2,9,3\]--\[1,2,4,9,3\]--\[1,2,3,9,4\]--\[1,2,3,4,9\] which gives a total of 4 swaps.

My logic:

Ascending array is \[1,2,3,4,9\]. So all five elements are in incorrect position from the sorted array which gives a total swap count of 5-1 = 4.

But my logic seems to be incorrect when tested on hacker rank. Could you give me an example where this logic fails. Thanks :)

# Answer
> 2 votes
Considering following array `[5,4,3,2,1]`

Now for `ascending` order, `four` elements are in incorrect position `i.e. 5,4,2 and 1`

So according to your logic, `No of swaps = No. of elements at incorrect position - 1` therefore `No. of swaps = 4-1 i.e. 3`

Now, according to `Selection sort`,

`[5,4,3,2,1] Original Array`

`1st Pass: [1,4,3,2,5] i.e. 1 swap`

`2nd Pass: [1,2,3,4,5] i.e. 2 swaps`

We are done, with `Only 2 swaps not 3 swaps`.

Similarly for `Descending` order,

Now, according to `Selection sort`,

`[1,2,3,4,5] Original Array`

`1st Pass: [5,2,3,4,1] i.e. 1 swap`

`2nd Pass: [5,4,3,2,1] i.e. 2 swaps`

We are done, with `Only 2 swaps not 3 swaps`.

Hope this helps !

# Answer
> -1 votes
The correct formula for counting the number of swaps in a selection sort algorithm is not (n-1) but it is { n\*(n-1)/2 }, where n is the length of an array.

Example: Let's consider an array of \[0,1,2,3,4,5,6,7,8,9,10,11,12,13,23,34\], which is sorted in ascending order. if we sort it in descending order, then it will experience the worst-case scenario and It will follow the following formula to count the possible number of swaps.

n=16; Swaps = ( n * ( n - 1) )/ 2 =\> ( 16 * ( 16 - 1 ) )/2 =\> 8 * 15 =\> 120

So in a worst-case scenario, there are no (n-1) swaps at all.

Algorithm:

```
function LinearSort(arr){
 for (var i=0; i<arr.length;i++){
   for(var j=0; j<i;j++){
     if(arr[i]<arr[j]){
     swap(i,j);
    //  console.log("i="+i+"\tj="+j);
     }
   }
 }
 return arr;
}
function swap(x,y){
  swaps+=1;
  var temp = myArr[x];
  myArr[x]= myArr[y];
  myArr[y]= temp;
}

```

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


title: Complexity analysis of a recursion

text:
# Question
Title: Complexity analysis of a recursion
A recursive algorithm has the following computation tree. The label on the node indicates the number of outgoing edges. This algorithm takes an input of length $n$ and at each processing, it results in $n - 1$ recursive calls. For each these calls/nodes, the size of the input decreases by $1$ from left to right. This pattern repeats.

I'm trying to figure out how to come up with a complexity analysis for this. It feels like there's some mathematical pattern/sequence here but I'm not able to figure it out.

# Answer
Vertices in your tree correspond to decreasing sequences starting at $n$. We can identify each such subsequence with a subset of $\\{0,\ldots,n-1\\}$, and consequently, your tree contains $2^n$ vertices. Consequently, assuming the processing per node is $O(1)$, your algorithm runs in time $\Theta(2^n)$.

The same method also allows us to count directly the number of vertices labelled $m$: there are $2^{n-m-1}$ of these for $m \in \\{0,\ldots,n-1\\}$, and one labelled $n$ (the root).

---

Here is another way to solve this, using a recurrence. Let $T(n)$ be the size of the tree when the root is labelled $n$. Then $T(0) = 1$ and $$ T(n + 1) = 1 + \sum\_{m=0}^n T(m). $$ This formula actually works also for $n = -1$. In order to solve this recurrence, observe that $$ T(n+1) = 1 + \sum\_{m=0}^{n-1} T(m) + T(n) = 2T(n), $$ and so $T(n) = 2^n T(0) = 2^n$.
> 1 votes

---
Tags: time-complexity
---


# Question
Title: Disambiguating grammar for Dyck language
Given the following simple grammar for a language that contains all strings with matched parentheses: \begin{align} &s \to ss \\ &s \to (s) \\ &s \to () \end{align}

Examples: $(), ()(), (()), \ldots$

Is it possible and how to disambiguate this grammar?

# Answer
Your language is very similar to the Dyck language, the only difference being that the Dyck language usually contains the empty string.

Here is an unambiguous grammar for your language: $$ S \to (S)S \mid (S) \mid ()S \mid() $$ In order to check that it generates the correct language, and unambiguously, let us consider a slightly different description of this language, replacing $($ with $\nearrow$ and $)$ with $\searrow$. We can think of a word over the alphabet $\\{\nearrow,\searrow\\}$ as corresponding to a path which starts at the origin and then "follows the arrows". Your language contains all non-empty words which do not dip below the X axis and end at the X axis.

It is easy to prove by induction that all words generated by the grammar are of this form. In the other direction, suppose that $w$ is a word in your language. It necessarily starts with $\nearrow$. Consider the first time that the path corresponding to your work returns to the X axis. This breaks your word into the general form $\nearrow x \searrow y$, where each of $x,y$ is either in your language or empty. A short case analysis shows that one of the productions allows you to generate your word.

The grammar is unambiguous since the partition $\nearrow x \searrow y$ is unique: every word in your language can be put in this form in a unique way. Indeed, the prefix $\nearrow x \searrow$ signals the first time that the walk returns to the X axis. Therefore the algorithm above gives the *unique* way to construct the word with the grammar.
> 3 votes

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


# Question
Title: Maximum independent subset for graphs with lots of edges
Consider an NP-hard graph problem, like the maximum independent set problem.

Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c \> 1$. In other words, the graphs are very connected.

Is the maximum independent set problem still hard for these graphs?

# Answer
The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ and $V'$ forms a complete graph. Also, there are no edges between $V$ and $V'$. Let the new graph be $G' = (V' \cup V, E')$ which is also a hard instance. And, $|V' \cup V| = 2n$ and $|E'| = \Theta(n^2)$.

Formally, it holds that $G$ has an independent set off size $k$ if and only if $G'$ has an independent set of size $k+1$.

---

Even if you add edges between every vertex of $V$ and every vertex of $V'$, the reduced instance would be a hard instance. Then, it holds that $G$ has an independent set of size $k$ if and only if $G'$ has an independent set of size $k$.
> 3 votes

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


# Question
Title: Designing a Queue that efficiently tracks position
Suppose we want to construct a queue with the following properties:

1. The priority of each member of the queue must be known. For example, for the head node, their priority is 1, for the next node, their priority is 2, etc. Then *given a node*, we must be able to determine its priority efficiently.
2. It must support deletion operations from any point in the queue
3. It must support addition operations to any point in the queue
4. It must be possible to move a member of the queue up or down

We want an efficient design. Properties 2, 3, and 4 are trivially solved with a Doubly Linked List. But property 1 adds a significant challenge: now, every time an element is removed from or added to the middle of the list, all the other elements have to have their rank updated as well. The O(1) properties of a DLL are lost, and all the operations are now O(n).

Is there a way around this? Is there some other data structure that would allow me to compute the position of a member in the queue more efficiently?

My mind is going toward heaps or other tree-based data structures where it may be possible to know the sizes of subtrees so you can readily compute the rank of a given member of the queue. In reading around, this seems to come close to priority queues, but I'm not sure if a PQ describes accurately the properties I laid out above.

# Answer
One simple data structure is a balanced binary tree, with members stored in the leaves, and augmented so that each internal node also stores the number of leaves under it. Now you can implement all of your operations in $O(\log n)$ time.

Operation 1 can be implemented by finding the leaf where the member $m$ resides (either add a pointer to the member struct to point to the leaf, or use a hash table to map from member to the appropriate leaf), then traverse parent pointers to get to the root; you can count the number of leaves to the left of $m$ by looking at the field in the nodes on the path from $m$ to the root, and their siblings.

To learn more, read about order statistic trees.

Conveniently, the extra information in each node is enough to ensure the tree remains balanced: see weight-balanced trees.
> 3 votes

---
Tags: priority-queues, queues, ordering
---


title: Is THEADS the same as FIRST?

text:
# Question
Title: Is THEADS the same as FIRST?
I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph:

> We will first of all briefly review the *LR(1)* parsing and parser construction algorithms. In this paper the symbols of a grammar are denoted by Roman letters while Greek letters are employed to denote strings. $\epsilon$ is the null-string. $\alpha \Rightarrow^\* \beta$ means $\beta$ is derivable from $\alpha$ (which is considered to be true if $\beta = \alpha$). By *THEADS($\alpha$)* we refer to the set $\\{b \mid b \text{ is the head of a terminal string derivable from $\alpha$}\\}$.

From what I can see *THEADS* here is what is usually called *FIRST*. Is this correct? Does *THEADS* predate *FIRST*?

# Answer
> 2 votes
I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. Quoting that paper:

> The concepts of state, configuration and theads(α, k) used here are equivalent to “item set”, “item” and FIRSTk(α) correspondingly in some other literature.

Note that a lot of good references on Pager (and Chen's) work can be found at the HYACC web site.

As for why Pager uses his own terminology in his papers, I don't have an adequate explanation, but it does indeed appear that *THEADS* and *FIRST* are the same.

---
Tags: terminology, formal-grammars, parsers, lr-k
---


# Question
Title: How can we process these types of queries on trees?
CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS

I recently thought of this interesting Tree problem:

Given a tree with $N$ nodes, let $val\_i$ = the "value" for each node. Process $Q$ queries of two types: the first consisting of a single node $i$. For this type of query, $val\_j += dist(i, j)$ for every other node $j$, where $dist(i, j)$ = the distance between nodes i and j in the tree. The second type of query just asks for $val\_j$ of some node $j$.

It seems to me that would be a well-known problem, but I have not been able to find any reference or mention of this problem online. Currently, my best approach is to simply brute-force; when given a query $i$, just run a DFS from node $i$ and update all the other nodes manually in $O(N)$. Of course, I am hoping for a more efficient algorithm.

Can anyone suggest one such algorithm/strategy?

Some more ideas: Lazy Propagation (to avoid having to update $O(N)$ values immediately), Heavy-Light Decomposition/Centroid Decomposition (not really any ideas for how these will be applied)...

# Answer
> 0 votes
There are two ways this problem can be solved. I really like these solutions.

1. Square Root Decomposition

Keep a set of at most O(sqrtN) "active nodes". When you have a query of type 2, just loop through all these active nodes and add the distance between each one to the queried node. When you have a query of type 1, add the new node to the set if the size does not exceed sqrtN. When the size of this set exceeds sqrtN, we need to basically somehow empty the set and update all nodes with their total distance to all active nodes. *But this can be easily done in O(N), not O(NsqrtN)*. The idea is that let's say the root of the tree is node 0, and first find the total distance sum of all active nodes to the root in O(N). Then, consider a node n and its child c, and let ans\[n\] = the total distance sum of all active nodes to node n. When we move from node n to its child c, we move one closer to every active node in the subtree of c, while moving one further from every other active node in the rest of the tree. So dp\[c\] = dp\[n\] - (sub\[c\]) + (total number of active nodes - sub\[c\]), where sub\[c\] is the number of active nodes in the subtree of c (and all sub\[..\] can be precomputed in O(N), with the same approach one would use to find subtree sizes). So this transition is O(1), meaning that we need O(N) time to simultaneously apply all updates (note that this works for any number of active nodes). In the end, the total time complexity is O(QsqrtN) (since each query of type 2 is O(sqrtN) in the worst case, and queries of type 1 are O(Q/sqrtN * N) = O(QsqrtN) amortized). BUT: Overall, this is quite slow for me, taking 5 or 6 seconds to process 200k queries over a tree with 100k nodes.

One example of this sort of reasoning: https://cses.fi/problemset/task/1133 https://usaco.guide/problems/cses-1133-tree-distances-ii/solution

2. Heavy Light Decomposition

Use the same recurrence as above with the same definitions: dp\[c\] = dp\[n\] + sz - 2 * sub\[c\], where sz = total number of active nodes in the whole tree. Now, what happens if we substitute the recurrence in for dp\[n\]? Then we get dp\[c\] = (dp\[parent of n\] + N - 2 * sub\[n\]) + N - 2 * sub\[c\]. Reapplying this recurrence until we reach the root (say, node 0) gets us

dp\[c\] = dp\[0\] + (depth of node c) * sz - 2 * (for every node i on the path from c to the root, **except for the root itself**) sub\[i\].

IN OTHER WORDS WE NOW HAVE AN EPIC CLOSED-FORM EXPRESSION FOR THE ANSWER TO ANY NODE

It's clear that dp\[0\] is easy to maintain (when we get a type 1 query with a new node, just add its distance from the root, which just equals its depth, to dp\[0\]). sz is also trivial to maintain (it's just the total number of type 1 queries received up to a given point).

But how can we efficiently find 2 * (for every node i on the path from c to the root, **except for the root itself**) sub\[i\]?

Heavy Light Decomposition. Basically we need to support two types of queries:

1. Update every value on a path to the root by 1
2. Find the sum of all values on a path from the root (and then subtract out sub\[root\] since remember we don't count that in the expression)

And this can be done with Heavy-Light Decomposition incorporating a Lazy Segment Tree.

For the same bounds as above (200k queries on a tree of 100k nodes), I had a runtime of less than 300ms.

---
Tags: algorithms, graphs, trees, graph-traversal
---


# Question
Title: Abstract Interpretation: Connection between soundness relation and a Galois connection
I am currently studying the paper "Abstract Interpretation Frameworks" by Cousot and Cousot from 1992 (https://doi.org/10.1093/logcom/2.4.511) to gain an understanding of the theory behind abstract interpretation.

One concept in abstract interpretation is the "soundness relation" (local page 6 in above paper). As I understand it, the soundness relation specifies if some object in the abstract domain $\mathcal{D}$ is a valid abstraction of some object in the concrete domain $\mathcal{C}$.

For special cases, you can describe an abstract interpretation using a Galois connection having an abstraction function $\alpha$ and a concretisation function $\gamma$. These form a Galois connection iff: $$ \forall c \in \mathcal{C}: \forall d \in \mathcal{D}: \alpha(c) \sqsubseteq\_{\mathcal{D}} d \Leftrightarrow c \sqsubseteq\_{\mathcal{C}} \gamma(d) $$ Compare: equation 4.12 in above paper.

Now the paper states right below that equation that:

> The soundness relation is $\langle c, d\rangle \in \sigma \stackrel{def}{=} \alpha(c) \sqsubseteq\_{\mathcal{D}} d \Leftrightarrow c \sqsubseteq\_{\mathcal{C}} \gamma(d)$

where $\sigma$ is the soundness relation. This really puzzles me now. Doesn't this say that for a Galois connection that $\sigma = \mathcal{C}\times\mathcal{D}$ since due to equation 4.12, the right hand side of the definition holds for any combination of objects from the abstract and concrete domains? Do we want that?

It would make some sense to me if we defined $\langle c, d\rangle \in \sigma \stackrel{def}{=} \alpha(c) \sqsubseteq\_{\mathcal{D}} d \wedge c \sqsubseteq\_{\mathcal{C}} \gamma(d)$, so only if both sides are true. Yet this appears not to be the way to go.

---

As a side node, if you know another resource that covers these topics on abstract interpretation and is available online freely, please let me know :)

# Answer
> 3 votes
It appears like I have simply misunderstood the expression: $\langle c, d\rangle \in \sigma \stackrel{def}{=} \alpha(c) \sqsubseteq\_{\mathcal{D}} d \Leftrightarrow c \subseteq\_{\mathcal{C}} \gamma(d)$.

What I read is: $\langle c, d\rangle \in \sigma$ is defined to hold if and only if $\alpha(c) \sqsubseteq\_{\mathcal{D}} d \Leftrightarrow c \subseteq\_{\mathcal{C}} \gamma(d)$. In this interpretation all concrete and all abstract elements are in relation with each other.

What the paper probably is trying to say instead is: $\langle c, d\rangle \in \sigma \stackrel{def}{=} \alpha(c) \sqsubseteq\_{\mathcal{D}} d$, so a concrete and an abstract element are in relation if the abstract element "contains" the abstraction of the concrete element.

The second part $\Leftrightarrow c \subseteq\_{\mathcal{C}} \gamma(d)$ then refers to that expression saying that $\langle c, d\rangle \in \sigma$ is also equivalent to saying that $c \subseteq\_{\mathcal{C}} \gamma(d)$, following from equation 4.12.

---
Tags: formal-methods, model-checking, order-theory
---