title: Number of minimum cuts in a graph

text:
# Question
Title: Number of minimum cuts in a graph
**Situation :**

I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-96RUg). In the lecture the professor is proving largest number of minimum cut in a graph.

**My Problem :**

To prove largest number of minimum cut in a graph. Prof. first stared proving Lower Bound. To get a lower bound he took a cyclic graph. My confusion is why he took cyclic graph?

**My way of Thinking :**

To get a lower bound we need to select the best case input (like for selection sort best case input will be an sorted array) and here Prof. was selected cyclic graph as an input but it doesn't seems to be the best case input. Like if we choose a star (https://en.wikipedia.org/wiki/Star\_(graph\_theory)) we could have easily get a lower bound which is **n-1**.

# Answer
I don't know the lecture you are referring to, but I do know the topic.

In this case "lower bound" is meant in an existential sense. That is, for every sufficiently large $n$, **there exists** a graph $G$ on $n$ nodes such that the number of minimum cuts in $G$ is $\binom{n}{2}$. In particular $G$ is a cycle on $n$ nodes.

The easiest way to see why this definition of lower bound is interesting is to think of upper bounds first. It is possible to show that the number of minimum cuts in **any** graph with $n$ nodes is at most $\binom{n}{2}$. Then one natural question is whether this upper bound is tight or whether it can be improved.

Your lower bound answers the above question: it is not possible to prove any upper bound smaller than $\binom{n}{2}$ since there is always at least one graph on $n$ nodes for which there are at least $\binom{n}{2}$ minimum cuts.

Note that, in this sense, the lower bound of $n-1$ that you can obtain by considering a star is a **worse** lower bound than the one you obtain by considering a cycle.

To summarize: an existential lower bound of $f(n)$ means that, in general, there can be no better upper bound than $f(n)$. Often times you'll find that lower bounds are expressed using asymptotic notation. A lower bound of $\Omega(f(n))$ means that there can be no upper bound better than $c f(n)$ for some constant $c\>0$.
> 1 votes

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


# Question
Title: Turing machine that can move right only $O(1)$ steps beyond input
I need to prove that a Turing machine that can move only $k$ steps on the tape after the last latter of the input word is not equal to a normal Turning machine.

My idea is that given a finite input with a finite alphabet the limited machine can write only a finite number of "outputs" on the tape while a normal Turing machine has infinite tape so it can write infinite "outputs" but I have no idea how to make it into a formal proof.

# Answer
Your machine uses $n + k = O(n)$ space. As such, it can be simulated by a linear bounded automaton. The latter is known to be weaker than a general Turing machine. For example, it cannot solve the halting problem for machines using $n^2$ space, a problem that Turing machines are able to solve.
> 1 votes

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Grammar with a long derivation generates an infinite language
> Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^b$ steps, then $L(G)$ is infinite.

This question is from Sipser(Introduction to the theory of computation)

# Answer
This follows from the pumping lemma, if you examine the proof closely enough.
> 4 votes

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


title: Is co-P recursively enumerable?

text:
# Question
Title: Is co-P recursively enumerable?
P is RE, but is the complement of the class of languages decidable in polynomial time also recursively enumerable?

If both are RE then this makes P recursive?

# Answer
co-$\mathsf{P} = \mathsf{P}$. To see this, pick your favorite problem $A$ in co-$\mathsf{P}$, let $T$ be a Turing machine for the complement of $A$ (in $\mathsf{P}$) and construct a new Turing Machine $T'$ that simulates $T$, accepts if $T$ rejects, and rejects if $T$ accepts.
> 3 votes

---
Tags: polynomial-time, enumeration
---


# Question
Title: Can you share some pointers to get better at working alone in projects?
I am an ML Engineer who works alone in projects most of the time. I don't have people who are much smarter than me working alongside.

Most of the time, I feel that working alone is a tedious job,one may get stuck at a lot of problems. In such cases my only go to option is Google. What effective techniques you use while you work on a project alone, because **at the moment googling feels like looking for a needle in haystack (80% of the stuff will be useless for you)**.

Apart from that, **some answers you search for lead you to more questions related to stuff explained there and it becomes a vicious circle of googling things leading to frustration**. (And most of the developers out there suggest the top down learning methodology, where you do a problem at first and then breaking down to solve it which ends up in above problem.)

So would you like to weigh in with your experiences, like **what thinking style you adopt, what are effective search methodologies, good ways of breaking down the problem**, here you get quick help apart from SO etc. It's good if you can link to books, resources etc as well.

# Answer
ML is an extremely broad subject but generally it can be understood broadly as follows

* you formalize the problem
* you identify the domain of the problem
* you identify candidate models to solve the problem
* you evaluate the candidate models with data subsets
* you select a model and try to fit your data
* you deploy the model

You can think of it as a(n iterative deepening ) search of a tree of choices. To improve your odds of success (find a choice that solves the problem) you need the tree narrow down as quickly as possible e.g. pruning bad choices. This is only acquired through experience but having a broad understanding of models helps e.g by taking introductory courses.

Once you've narrowed down the types of models you want to apply. You want to know if you have the expertise to apply them. Given that this is a broad subject, you acquire expertise only in a limited set of models. If the model that best fits your problem is not in your domain of expertise you either refer it someone with that expertise or reject that you can solve the problem in a limited amount of time e.g. due to the complexity of the tree of choices for a non-expert.

Within your model expertise you'd have acquired a set of techniques to determine that even when you have the right model, if you do not have sufficient data, or data with sufficient quality, or the necessary computation resources you may not be able to deploy your model.
> 1 votes

---
Tags: machine-learning
---


title: Wall Climbing Dynamic program

text:
# Question
Title: Wall Climbing Dynamic program
How do i solve this? I am not sure where to start. I am trying to define a Optimum solution which i can use to create a dynamic program. I am not sure what the characteristics of the optimum should be. right now i am thinking, at any instance of the problem, we know, the person will move right , left or up.( He can't always move up, only when near a ladder) How to I follow this?? any leads would be appreciated.

# Answer
> 1 votes
I will assume $n\>0$. Let $d\_i(a)$ be the minimum number of moves needed to start from position $(a, i)$ and collect the coins at coordinates $(x\_i, i)$ and $(y\_i, i)$. $$ d\_i(a) = \min \\{ |x\_i-a| + |y\_i-x\_i|, |y\_i-a| + |x\_i-y\_i|\\} $$

Similarly, let $d\_i(a,b)$ be the minimum number of moves needed to start from position $(a, i)$ and reach position $(b,i)$ while collecting the coins on coordinates $(x\_i, i)$ and $(y\_i, i)$. $$ d\_i(a,b) = \min \\{ |x\_i-a| + |y\_i-x\_i| + |b-y\_i|, |y\_i-a| + |x\_i-y\_i| + |b-x\_i|\\} $$

For $j \in \\{1, 2\\}$, let $OPT\_j\[i\]$ be the minimum number of moves needed to start from position $(0,0)$ and reach position $(z\_j, i)$ while collecting all the coins at heights up to $i$. According to this definition $ OPT\_j\[0\] = d\_0(0, z\_j) $ and, for $i = 1, \dots, n$: $$ OPT\_j\[i\] = 1 + \min\_{h \in \\{1,2\\}}\\{ OPT\_h\[i-1\] + d\_i(z\_h, z\_j) \\}. $$

The optimal solution is then $1 + \min\_{h \in \\{1,2\\}} \\{OPT\_h\[n-1\] + d(z\_h) \\}$.

This algorithm can be implemented to run in $O(n)$ time since there are $O(n)$ subproblems and each subproblem can be solved in constant time (once the solutions to the previous subproblems are known).

---
Tags: dynamic-programming
---


# Question
Title: Under what kind of oracles are $P$ and $NP$ equivalent?
How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?

For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting problem equivalent to $NP$ equipped with an oracle to solve the halting problem)?

From Theodore Baker, John Gill, and Robert Solovay. Relativization of the P=?NP problem. Siam Journal of Computing, 4:432-442, 1975 \[219\] we know $NP^A =P^A$ for their oracle A (which is a decision algorithm for a PSPACE complete problem).

If the oracle can perform an infinite amount of computation and return back the result in one step are these classes equal with respect to an oracle of this type? How about weaker ones? What is the weakest oracle we know of where $P$ and $NP$ are equal with respect to it?

An answer I'm looking for is something like: $P^O$=$NP^O$ with respect to an oracle O and any oracle more powerful than it.

# Answer
It's not about strength: the Baker-Gill-Solovay nonrelativization result relativizes (hehehe), in the sense that

* for every $A$ there is a $B\ge\_p A$ such that $\mathsf{P}^B\not=\mathsf{NP}^B$, and
* for every $A$ there is a $B\ge\_p A$ such that $\mathsf{P}^B=\mathsf{NP}^B$.

What matters more - or at least, what matters more *in a way we can understand* \- is the **genericity**/**randomness** properties of the oracle. Specifically, the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ has full measure, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently random." If I recall correctly, the same is true for genericity: the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ is comeager, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently generic." Both of these notions can be made precise. For a concrete example, Chaitin's constant and its relativizations are sufficiently random to separate $\mathsf{P}$ and $\mathsf{NP}$.

---

So what about the halting problem specifically? Well, the exact structure of the halting problem is rather dependent on the way we choose to enumerate Turing machines, and we can in fact whip up an "appropriate" enumeration whose associated halting problem goes whichever way we desire. So I suspect that it's hard to say anything here.

---

This leaves open the question of how weak we can make an oracle with respect to which we have $\mathsf{P}=\mathsf{NP}$ (or $\mathsf{P}\not=\mathsf{NP}$ for that matter). The Baker-Gill-Solovay argument gives us the *non-highness* result that for any non-polytime-computable $A$ we can find $B,C$ to which $A$ is not polytime-reduciblesuch that $\mathsf{P}^B=\mathsf{NP}^B$ and $\mathsf{P}^C\not=\mathsf{NP}^C$. *(Incidentally, note that "high" and "low" are technical terms which I'm misusing here. I'm rude like that.)*

---

Now the above isn't as satisfying as one might hope since the $\le\_p$-degrees are rather "spread out." We might hope for some results "closer to home." For example, in an earlier edit I suggested examining the behavior of **minimal** degrees with respect to polynomial-time $m$-reducibility, where "minimal" means "nonzero but not strictly above any nonzero degree" (while this clashes with the standard order-theoretic meaning, it is standard in computability theory). I just realized that this is vacuous: there are no minimal polynomial-time degrees, with respect to either $m$\- or $T$-reductions, at all! This was proved by Homer, following a result of Ladner.

Just to wrap up this coda, Homer subsequently observed (and this was followed up by Ambos-Spies) that things are less trivial with respect to so-called **honest** reductions; honesty is a bit technical, but the basic idea is to rule out situations where disproportionately much of the information about a set is concentrated in a small region of the oracle computing it. It turns out that there is a tentative connection between minimal degrees with respect to honest polynomial reductions and the $\mathsf{P=NP}$-problem. To my understanding this turned out to be a red herring, but it's still very neat!
> 5 votes

---
Tags: halting-problem, oracle-machines
---


# Question
Title: When does Gaussian elimination solve exact 1-in-3 SAT?
**Terms:**

A **literal** is a *variable* or its *negation*.

A **clause** is a *set* of literals.

An **exact 3-in-1 clause** is satisfied if an assignment of values to variables results in exactly 1 `true` literal and 2 `false` literals.

**Exact 3-in-1 SAT** is the problem, given a set of **exact 3-in-1 clauses**, is there as assignment of variables that satisfies all clauses?

**Question:**

This corresponds to a linear algebra problem, sort of:

Let `true` be `1` and `false` be `-1`.

For each variable `v` and its negation `w`, add the equations:

`v + w = 0`

(This is because `1 + (-1) = 0`)

For each exact 3-in-1 clause (`a` `b` `c`), add the equations:

`a + b + c = -1`

(This is because two `-1`'s and one `1` will add up to `-1`.)

It's possible solving the equations results in a value other than `1` or `-1`. However if the solution to the system of equations is only `1` and `-1`, I suspect that's a valid solution to the original exact 1-in-3 problem.

**So, when does Gaussian elimination solve exact 1-in-3 SAT?**

Here's an example when it does:

These clauses:

(`1` `2` `3`) (`2` `3` `-2`) (`2` `3` `-3`)

Correspond to this matrix:

```
1, 0, 0, 1, 0, 0, 0
0, 1, 0, 0, 1, 0, 0
0, 0, 1, 0, 0, 1, 0
1, 1, 1, 0, 0, 0, -1
0, 1, 1, 0, 1, 0, -1
0, 1, 1, 0, 0, 1, -1

```

Reduced row echelon:

```
1, 0, 0, 0, 0, 0, 1
0, 1, 0, 0, 0, 0, -1
0, 0, 1, 0, 0, 0, -1
0, 0, 0, 1, 0, 0, -1
0, 0, 0, 0, 1, 0, 1
0, 0, 0, 0, 0, 1, 1

```

Therefore solution (via far-right column) is: (`1` `-2` `-3`)

**Does this always work on larger matrices with `2*n` rows and `2*n+1` columns where `n` is the number of variables?** (I think it may need non-redundant (linearly independent?) rows.)

# Answer
> 1 votes
> Does this always work on larger matrices with 2*n rows and 2*n+1 columns where n is the number of variables? (I think it may need non-redundant (linearly independent?) rows.)

It works but since there are assignments other than -1 and 1, how will you use the row echelon form to make any conclusions about the 1-in-3 SAT instance?

It is possible that the 1-in-3SAT formula is unsatisfiable but the corresponding reduced row echelon matrix is satisfiable (because of the possible assignments other than -1/1), therefore you won't be able to rely on the matrix in the general case

**Gaussian elimination solves exact 1-in-3 SAT when the matrix form only has solutions with variables assigned to -1 or 1, or when the matrix is unsatisfiable**

---
Tags: np-complete, satisfiability, linear-algebra, 3-sat
---


# Question
Title: Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?
Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to.

In the 2-dimensional case it's fairly trivial, you simply split the square along its diagonals:

```
if (x < y) then
    if (x + y < 0) then
        // Side 1
    else
        // Side 2
else
    if (x + y < 0) then
        // Side 3
    else
        // Side 4

```

In 3-dimensions, this becomes more complex; each face creates a 'volume' of points that are closest to it in the shape of a square based pyramid.

Visualisation of the 6 planes that form the 6 pyramids

Of course, given a point, it's possible to determine which side of the 6 planes it lands on and using that information you can determine which face of the cube is closest. However this would involve running 6 separate checks.

Moving this into higher dimensions, a similar algorithm can be run on hypercubes, however, as the number of faces on a n-cube is $2^{n-2}{n \choose 2}$, this quickly becomes computationally very expensive.

However, theoretically a perfect algorithm could cut the search space in half with every check, discarding half the faces each time.

This would give this hypothetical algorithm a runtime of $O(\log\_2(2^{n-2}{n \choose 2}))$ which can be simplified, if my rate of growth calculations worked out, to $O(n\log(n))$

Is my logic correct here; can/does such an algorithm exist?

# Answer
> 1 votes
After a bit more thinking, I realised it's actually doable in $O(n)$

If you normalise your hypercube onto the origin then to find the face the point lies on you simply need to find the axis of the point with the largest magnitude.

So, if the point is at $(0.2, 0.4, 0.7, 0.5)$, the point will be closest to the face facing in the positive z direction.

---
Tags: algorithms, time-complexity, computational-geometry, big-o-notation
---


# Question
Title: Is that true that A is decidable if A$\le_m$A complement?
A is decidable if A$\le\_m$A complement

Can i think that it is true because decidable is close under complement, so if A complement is decidable, so is A

# Answer
> 0 votes
If co-$A$ is decidable then so is $A$, as you mention in your question.

However the mere fact that $A \le\_m$ co-$A$ does not imply the dependability of $A$. See this answer.

---
Tags: formal-languages
---


# Question
Title: Virtual Memory vs Cache for block identification
Both are based on the principle of locality. Then why virtual memory uses table lookup while cache memory uses associative memory for block identification?

# Answer
> 1 votes
I think it's because when using virtual memory, you have access to disk and thus have vasts amounts of memory to store extra data structures than can help you identify each page. In cache, you don't have that much memory, so the way to do things is to add identification (tag and set) bits to each cache line so that you don't need another data structure to identify each cache block because it would be expensive memory-wise. You just iterate over each set, identify the set you're looking for, then iterate over each cache line in that set and identify the cache line you're looking for and then extract the desired bytes. Also, iterating over all cache lines is not that expensive because there aren't a lot of them, but applying this technique to pages, which can be thousands, is really inefficient.

---
Tags: cpu-cache, virtual-memory
---


# Question
Title: Number of double wedges containing a point
We have a set of $n$ double wedges on a plane. (By double wedge, I mean two lines intersecting at a point, with opposite sides of the point considered as "inside" the double wedge.) Now these $n$ double wedges can intersect each other.

Our query is as follows: given a point, we want to find how many double wedges it's contained in. We want to be able to make this query in $O(\log n)$ time, using a data structure that can be constructed (preprocessed) in $O(n^2\log n)$ time and $O(n^2)$ space.

This exercise is from the de Berg's computational geometry book in the chapter about arrangement of lines, so I was thinking we can do some kind of incremental construction by adding the double wedges one by one, but I can't seem to think of the data structure.

# Answer
The set of $2n$ lines on the plane form a well studied Arrangement of lines, which is a type of *planar subdivision*, composed of vertices, edges and faces. This planar subdivision used to be represented by DCEL. There are two types of algorithms, which can convert a bare set of lines into the DCEL - plane sweeping algorithm with time complexity $O(n^2log(n))$, and incremental one with time complexity $O(n^2)$. Both these types are described in this book (Item 8.3). The resulting subdivision will have $O(n^2)$ faces.

Given a planar subdivision with $O(n^2)$ faces we can convert it further into a hierarchical data structure, which can be used to locate a face, containing any query point, in $O(log(n))$ time. This is a topic with long history - please see the Point location page for more information.

So, if we assign a number of double wedges, containing a point, to each face of the planar subdivision - we'll solve the exercise. Let's find out how we can do just that.

Each double wedge defines four parts of the plane, and we need to define clearly, what parts are *inside* the wedge. In order to do that we'll split each boundary line into two rays - one pair of "incoming" rays and one pair of "outcoming" rays. We'll consider a part of the plane, lying to the left of each such ray, to be *inside* the double wedge.

The direction of these rays can be used to calculate the number of intersecting double wedges (called below an *intersection number*), corresponding to each face of the planar subdivision. It's easy to see, that **these numbers for adjacent faces differ by one**. Even more, if we jump from some face to another face over a boundary edge, directed from the left to the right, we'll need to increment this number. If the boundary edge is directed from the right to the left, then this number needs to be decremented. An example of two double wedges $w1$ and $w2$ with assigned intersection numbers (in red) is below.

So, the algorithm to assign intersection numbers to faces comprises of two steps:

**Step 1.** Take an arbitrary *initial* face and calculate its intersection number, using all the $n$ double wedges - it can be done in $O(n)$ time.

**Step 2**. Traverse all the faces of the planar subdivision, starting from the initial face and assigning the intersection number using boundary edges direction as described above - it can be done by the DFS in $O(n^2)$ time.
> 3 votes

---
Tags: computational-geometry
---


# Question
Title: Is there a polynomial time algorithm for this decision problem?
Is there a factor in $M$ that is $\>$ $1$, but $\<$ $M$ that is NOT a factor of $N$?

**False Result Example**

$N$ = 8

$M$ = 16

1, 2, 4, 8, 16

There is no integer that is NOT a factor of $N$ that is $\>$ $1$ but \< $M$

**True Result Example**

$N$ = 2

$M$ = 26

1, 2, 13, 26

There is an integer $13$ which is NOT a factor of $N$ that is \> 1 but \< $M$

## Question

I have found a pseudo-polynomial solution, but is there a polynomial solution for this problem in the length of input?

# Answer
> 3 votes
This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$). Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.

---
Tags: decision-problem, polynomial-time
---


# Question
Title: Matrix multiplication randomised verification - error probability
Let s say we have an algorithm that takes as input 3 matrix A,B and C

> $$ \text{Input} :A,B,C \in Mat(n\times n)$$ $$\text{Question} :\text{is } A\cdot B=C$$

the algorith works as follow ;

$$ \text{if }(A\cdot B)\_{ij}=C\_{ij} \Rightarrow A\cdot B=C $$ $$ \text{if }(A\cdot B)\_{ij} \neq C\_{ij} \Rightarrow A\cdot B \neq C $$

with random chosen $i$ and $j$ .

I have to find in this case the error probrabilty. Can someone please give me some hints.

This problem looks a bit like the freivalds algorithm, somehow i think i have to drive a trick with it so solve mine but i am not sure .

# Answer
> 1 votes
If that's the whole algorithm, only one iteration, then the only bound on the probability of error you can get is that it is smaller than $1-1/n^2$.

Hint 1) Notice that the algorithm only can fail when it enters in the first case you describe, why?

Hint 2) What is the worst possible case for A, B and C so you get the worse probability of error?

# Answer
> 0 votes
If I create the matrix C by calculating AB, then change a single entry in C, then you need to calculate x% of all entries to have an x% chance to find the incorrect entry.

If I change an entry in A or B, then you just need to calculate 2n entries ( but the right ones) to find AB != C.

So really your question is unanswerable until you get more information about A, B and C.

---
Tags: probability-theory, matrix, testing
---


title: When is Viterbi's algorithm practical?

text:
# Question
Title: When is Viterbi's algorithm practical?
Here is an excerpt from Andrew S. Tanenbaum, *Computer Networks*, 5th edition, Chapter 3 (The data link layer), Page 208:

> The internal state is kept in six memory registers. Each time another bit is input, the values in the registers are shifted to the right. For example, if 111 is input and the initial state is all zeros, then the internal state, written left to right, will become 100000, 110000, and 111000, after the first, second, and third bits have been input, respectively. The output bits will be 11, followed by 10, and then 01. It takes seven shifts to flush an input completely so that it does not affect the output. The constraint length of this code is thus $k=7$.
>
> A convolutional code is decoded by finding the sequence of input bits that is most likely to have produced the observed sequence of output bits (which includes any errors). For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973). The algorithm walks the observed sequence, keeping for each step and for each possible internal state the input sequence that would have produced the observed sequence with the fewest errors. The input sequence requiring the fewest errors at the end is the most likely message.

My question is about this part:

> For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973).

My question is how do they determine whether the value of $k$ is considered small or big? What is the threshold value for $k$? For example, length of this code is 7 and they considered it a small value. How about $10$? How about $20$? Are they considered small values or large values? I'm curious about the threshold value of $k$.

# Answer
There is no threshold of $k$. Viterbi's algorithm has a certain complexity. For small enough $k$, you will be able to run Viterbi's algorithm on the given hardware at the given speed. For larger values of $k$, Viterbi's algorithm would be too slow. The exact threshold depends on your hardware (its capabilities, and how much "space" is available to implement the algorithm), and on the required speed. Viterbi's algorithm is optimal, and so it should probably be preferred over other algorithms when the constraints allow using it.
> 2 votes

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


# Question
Title: Detect cycles of odd total weight in a graph with {0,1}-weighted edges
Given an edge-weighted digraph $G = (V, E \subseteq V^2, w \in E \to \\{0, 1\\})$, is there an algorithm that returns `TRUE` if there is a cycle in this graph whose total weight is odd and `FALSE` otherwise, which runs faster than $O((|V| + |E|)(c + 1))$ (where $c$ is the number of simple cycles in the graph, which is of course $\Omega(2^{|V|})$)?

As the question implies, I already came up with an algorithm that runs in $O((|V| + |E|)(c + 1))$ time. This algorithm involves first running Johnson's simple cycle enumeration algorithm, which gives us all the simple cycles in the graph. Since `even + even = even`, and all cycles are made by adding together simple cycles, the graph contains a cycle of odd length iff it contains a simple cycle of odd length. Thus, we just compute the parity of the simple cycles and return `TRUE` if any of them are odd, and `FALSE` otherwise.

Can anyone come up with a more efficient approach? Ideally, one that is not just "replace Johnson's algorithm with another simple cycle enumeration algorithm that has slightly better asymptotics", since the graphs I'm dealing with really aren't that large, and constant factors may well dominate as a result.

# Answer
You can solve this in $O(|V| \cdot |E|)$ time.

Construct a digraph with vertices of the form $\langle v,b\rangle$ where $v \in V$, $b \in \\{0,1\\}$, as follows: for each edge $v \stackrel{t}{\to} w$ in your graph, add the edges $\langle v,b \rangle \to \langle w,b + t \bmod 2 \rangle$ for each $b \in \\{0,1\\}$ to the new graph.

Then, for each $v \in V$, check whether there is a path from $\langle v,0 \rangle$ to $\langle v,1 \rangle$ or from $\langle v, 1\rangle$ to $\langle v,0 \rangle$ in this new graph. This can be done with two DFS searches per vertex $v \in V$; each DFS search takes $O(|E|)$ time, so the total running time is $O(|V| \cdot |E|)$ time. The search can be sped up by decomposing the new graph into strongly connected components once and then searching in the dag of components (the metagraph).
> 2 votes

# Answer
Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time.

What is happening here? Let us consider the original edge-vertex incidence matrix. Rows corresponding to cycles sum to zero, since each vertex appears in exactly two edges. Conversely, if we have a set of rows summing to zero, then the degree of each vertex is even. Starting at an arbitrary edge, we can trace a walk that will eventually close onto itself. We remove the corresponding cycle (which need not contain the original edge), and continue. In this way, we see that a set of rows summing to zero correspond to an edge-disjoint union of cycles.

By adding an additional $1$ column to the matrix, we are tracing the parity of the cycle. An odd cycles sums up to the vector $0,\ldots,0,1$. Conversely, if a set of rows sums to $0,\ldots,0,1$, then it corresponds to a set of cycles whose total length is odd, so one of the cycles is odd.

Finally, finding whether a vector is in the row space of the matrix is a standard problem in linear algebra, which can be solved using Gaussian elimination and related algorithms.
> 2 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: Algorithm for splitting an array into k sub-arrays
We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized sub-arrays (+-1), that each value in the i'th sub-array will be larger than any value in the (i-1)'th sub-array, and smaller than any value in the (i+1)'th sub-array. This method need to be applied in complexity of O(n log k).

Insert(x)- Gets a value x which isn't in our data structure, and adds it. This method need to be applied in complexity of O(k logn).

I did the init method using Medians- ofMedians QuickSelect, by dividing the array into k' sub arrays when k' equals to the closest power of 2 for k, and then I adjusted my pointers to the dividers by using Select on the smaller arrays which added me only O(n).

With the Insert part I'm having some trouble and would appreciate any help, Thanks:)

# Answer
Insert$(x)$ can be implemented in $O(k \log(n/k))$ time. I will use the terms subarray and group interchangeably.

Let $n$ be the number of elements in the data structure before the insert operation. We will maintain this invariant: each subarray contains either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$ elements. The elements of each subarray are stored in a min-heap and in a max-heap that support element deletion.

Insert $x$ into the unique group $i$ whose minimum element is smaller than $x$ and such that the minimum element of the next group (if any) is larger than $x$.

Notice that if, before the insert operation, $i$ contained $\lfloor n/k \rfloor$ elements then the operation cannot possibly violate the invariant. This means that if the invariant is violated then $\lfloor n/k \rfloor \< \lceil n/k \rceil$, $i$ contained $\lceil n/k \rceil$ elements, and there is a group $j \neq i$ that contained $\lfloor n/k \rfloor$ elements. Let $j^\*$ be the value of $j$ that satisfies the above conditions and minimizes $|j^\*-i|$.

We can restore the invariant as follows:

* If $j^\* \< i$ then all groups $h \in \\{j^\*+1, \dots, i-1\\}$ have $\lceil n/k \rceil$ elements. For each $h= j^\*+1, \dots, i$ do the following: pick the minimum element $m$ from group $h$ (this can be done in $O(\log n/k)$ time by a pop() operation on the min-heap of $h$ and a delete($m$) operation on the max-heap of $h$) and add $m$ to group $h-1$ (this amounts to adding $m$ to both the min-heap and the max-heap of group $h-1$).
* If $j^\* \> i$ then all groups $h \in \\{i+1, \dots, j^\*-1\\}$ have $\lceil n/k \rceil$ elements. For each $h= i, \dots, j^\*-1$ do the following: pick the maximum element $M$ from group $h$ and add it to group $h+1$.
> 1 votes

---
Tags: algorithms, data-structures, arrays, selection-problem
---


# Question
Title: Longest Common subsequence theorem in CLRS
In CLRS in the dynamic programming chapter, there is a theorem about the longest common subsequence prefix that states the following:

> **Theorem** Let the $X=(x\_1,x\_2,\dots,x\_m)$ and $Y=(y\_1,y\_2,\dots,y\_n)$ be sequences, and let $Z =(z\_1,z\_2,\dots,z\_k)$ be their LCS.
>
> If $x\_m = y\_n$, then $z\_k = x\_m = y\_n$ and $Z\_{k-1}$ is an LCS of $X\_{m-1}$ and $Y\_{n-1}$.

The theorem has two more points but I am interested particularly in the first point, I don't understand why we only consider $Z\_{k-1}$ to be the LCS of $X\_{m−1}$ and $Y\_{n−1}$ and **not** $Z$ to be the LCS of all of $X$ and $Y$, if already the last element in all sequences match.

# Answer
The theorem is used to construct a recurrence relation for computing the LCS of $X$ and $Y$. The first point states that if $x\_m = y\_n$, then one possible LCS of $X$ and $Y$ is an LCS of $X\_{m-1}$ and $Y\_{n-1}$ together with $x\_m$. This is one of the cases in the recurrence relation.

You ask why we are not considering $Z$ as the LCS of $X$ and $Y$. There is no need to consider this, because this is already assumed to hold in the premise of the theorem. Given that, we want to deduce *other* information, which will later enable us to compute the LCS recursively.
> 1 votes

---
Tags: algorithms, dynamic-programming, longest-common-substring
---


title: 3D intersection algorithm for cylinders

text:
# Question
Title: 3D intersection algorithm for cylinders
**The problem**

The input is a list of $N$ cylinders in 3D space, and the output should be a list of $M \leq N(N-1)/2$ pairs of cylinders that intersect. ($M$ depends on the input data, obviously.)

If it matters, the cylinders are very thin (with a diameter less than 1% of the length for all cylinders), and a solution for "rounded cylinders" would work for me (it probably simplifies the geometry calculations). A "rounded cylinder" is a cylinder with half-spheres at the extremities; formally, for a starting point $S$, an endpoint $E$ and a radius $r$, the rounded cylinder $(S, E, r)$ is defined as the set $\\{P \mid \exists Q \in \[S,E\], \\|PQ\\| \leq r\\}$.

**The obvious solution**

It is easy enough to do in $O(N^2)$ time and $O(max(M, N))$ space: the pseudocode of my current implementation is (for rounded cylinders):

```
Ncyl = length(cylinder_list)
output = {}
for i = 1, 2, ... Ncyl:
  for j = i+1, i+2, ... Ncyl:
    (S1, E1, r1) = cylinder_list[i]
    (S2, E2, r2) = cylinder_list[j]
    find P∈[S1, E1], Q∈[S2, E2] such that ||PQ|| is minimal  # this is the costly line, says the profiler
    if ||PQ|| < r1 + r2:
      add (i, j) to output
return output

```

**Better performance?**

Any algorithm will have a (time and space) worst-case in $O(N^2)$ (at least) because the output list can itself be of that length. However, the above algorithm guarantees $O(N^2)$ time even on "friendly" data because it tests all possible intersections.

In my use case, the cylinders are fairly spread apart in space (the longest cylinder is less than one tenth of the diameter of the whole set of cylinders). Furthermore, they occupy a small fraction of space and $M\sim N$ (for values of $N$ up to 2000 or so, above that it times out). This suggests to me that there could be an improvement by some "sweeping plane" algorithm similar to Bentley-Ottmann. However, I did not find a straightforward way to do Bentley-Ottmann in 3D (in 2D after sweeping you end up ordering points on a line which is easy enough, but in 3D there is no obvious ordering for a plane).

# Answer
If you could accept an approximate solution for this problem, then the following approach would help you. Your cylinders are thin, so if two of them intersect, then their axial segments **almost** touch each other. If you project such a pair of almost touching segments on each of coordinate planes you'll see that their projections **almost** always intersect.

So - project your set of segments on three coordinate planes and apply the Bentley-Ottmann (or similar) algorithm **three times** to find all the intersections. Select pairs of segments, which intersect on **all three** planes, calculate distance between them and verify the cylinders intersection.

This method can give you false negatives - for example in the case, when two cylinders are collinear with small gap between them. However, this method won't give you false positives, because you explicitly verify each suspicious pair of cylinders.
> 1 votes

# Answer
@d3m4nz3 pointed in a comment to the use of k-d trees. That is the solution for the "intersection of spheres" problem, and I suspect it is (asymptotically) optimal when the cylinders are thick. The pseudocode would be something like:

```
max_sphere_rad = max( ||SE|| + r for (S, E, r) in cylinder_list)
tree = (build kd tree of cylinders based on their center location)

output = {}
loop for (Si, Ei, ri) in cylinder_list
  potential_intersections = query tree for cylinders whose center is at most at distance (||Si Ei||/2 + r + max_sphere_rad) of (Si+Ei)/2
  loop for (Sj, Ej, rj) in potential_intersections
    if (Si, Ei, ri) and (Sj, Ej, rj) intersect:
      add (i, j) to output
return output

```

Building the kd tree is $O(N log N)$. The question is whether it really speeds up the subsequent range search for `potential_intersections`. That in turn depends on the exact way the kd tree was built vs. the distribution of cylinder center points etc., but the rough idea is that if the output is of size $K$, the query has complexity $O(K + log N)$ (for a reasonably balanced kd tree). In particular:

* if $K\leq O(log N)$ (very few potential intersection points per cylinder), the whole algorithm runs in $O(N log N)$
* If $K=O(N)$ (large portions of the dataset interact), the query will always be at least $O(N)$, making the whole algorithm run in $O(N^2)$

For a rough analysis of the impact of the cylinder distribution on the algorithm complexity, assume $N$ cylinders with constant length $L$ (and radii well below $L$), that are uniformly-distributed in a volume $V$. A typical cylinder will have $O(N L^3/V)$ neighbors in `potential_intersections`. Based on the above, such neighbors can be extracted in close to $O(N L^3/V)$ time and the whole thing runs then in $O(N^2 L^3/V)$. At constant $L^3/V$ (i.e. add more cylinders in a constant-volume space), the algorithm is quadratic in the number of cylinders; at constant $N/V$ (i.e. increase volume size and add cylinders at iso-density), it is linear.
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: Prove that AVL tree has this kind of property with Fibonacci sequence
Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$)
and has a height of $h$ this property is true:
$n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence:
$F(0) =0, F(1)=1, F(n) = F(n-1) + F(n-2) ~~~~\forall n \geq 2$

This is my go:

We know it is an AVL tree so $h = \log\_2{n}$
Thus we need to prove that $n \geq F( \log\_2{n})$

$F(\log\_2{n})= F(\log\_2{n}-1)+F(\log\_2{n}-2)$
However I am stuck from here, I don't know what this helps me with and I am clueless on what to do next..
I would appreciate your help, thank you!

# Answer
> 1 votes
Let $T$ be an AVL tree of $n \> 0$ nodes having height $h \ge 0$. You can prove that $n \> F(h)$ by induction on $h$.

For $h=0$ the claim is true since $n=1$ and $1 \> 0 = F(0) = F(h)$. For $h=1$ the claim is true since $n \ge 2$ and $2 \> 1 = F(1) = F(h)$.

For $h \ge 2$, let $r$ be the root of the AVL tree. The subtree $T\_\ell$ rooted in the left child of $r$ and the subtree $T\_r$ rooted in the right child of $r$ exist are both AVL trees. Moreover, since $T$ is balanced, at least one tree $T'$ among $T\_\ell$ and $T\_r$ must have height $h-1$, while the other tree $T''$ must have height at least $h-2$.

By inductive hypothesis the number $n'$ of nodes of $T'$ is more than $F(h-1)$, while the number of nodes of $T''$ is more than $F(h-2)$. Therefore, the number of nodes $n$ is: $$ n = 1 + n' + n'' \ge 3 + F(h-1) + F(h-2) = 3 + F(h) \> F(h). $$

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


# Question
Title: Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$
Given the language:

$MIN\_{TM}$= $\\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \\}$

I need to prove if this language is in $R$ or $RE-R$ or $coRE-R$ or $\overline{RE\cup coRE}$.

I suspect this language is in $\overline{RE\cup coRE}$ but I can't prove it. (I Tried using reduction but no help).

# Answer
> 1 votes
**Hint 1:** What happens when $k=2$?

**Hint 2:** Use a reduction from $\text{ALL}\_{\text{TM}}$.

# Answer
> 0 votes
IDK if this is the most elegant way . But consider the language L = { : M is TM and L(M) =! emptyset and L(M) =! sigma\*} lets call the above language nontrivial now its quite easy to prove the nontrivial is not in both RE and coRE with reduction from ATM for example. no that we have nontrivial we can use the following reduction : F() = from the complimentary language of nontrivial to MinTm both directions almost immediate and based on the fact that if k = 3 than M must be either empty or sigma\* (since the TM has only two states qrej and qacc)

---
Tags: turing-machines, computability, reductions
---


title: How to tell if a proof relativizes?

text:
# Question
Title: How to tell if a proof relativizes?
If I have a proof for a separation between two complexity classes (using no oracles) and I want to see if it relativizes, how do I go about doing so?

Especially in the case where there already exist proofs for these classes being equal with respect to one oracle and not equal with respect to another oracle. I'm wondering, if I have a proof of inequality with respect to no oracle can I simply reference the oracle to which these classes have been proven equal, call on that example, and be done--since there exists an oracle to which they have already been proven equal this is my proof that the inequality doesn't relativize?

Or do I have to apply oracles specifically to the machines in my proof of the inequality and see if it relativizes?

I'm confused about how proving relativization / non-relativization of a specific proof of some statement relates to the relativization of other proofs of the same statement.

How can I reference the fact that other proofs of a statement relativize / don't relativize to help me prove my own relativization result about my proof of that statement?

Thanks!

# Answer
> 2 votes
A proof relativizes if every step in the proof relativizes. You should go over your proof, and check whether each step remains valid in the presence of an oracle.

In contrast, a result relativizes *by definition* if it still holds relative to an arbitrary oracle. Hence, to show that a result doesn't relativize, all you have to do is give an oracle with respect to which it fails.

If we're interested in some specific statement, whose truth value we are not sure of, and there are both an oracle relative to which the statement holds and an oracle relative to which the statement doesn't hold, then we can conclude that no relativizing proof can either prove or refute the statement.

---
Tags: oracle-machines, relativization
---


# Question
Title: MST - algorithm to add an edge to the graph
I have some difficulty proving the correctness of my solution to the following exercise. Let $G = (V,E)$ undirected connected graph, $w \colon E \to \mathbb{R}$ weight function. Let $T$ a MST (minimum spanning tree) of $G$. Now, we add a new edge $e'$ to $E$ with weight $w(e')$. Find an algorithm that updates $T$ so it will be a MST of the new graph $G' = (V,E \cup \\{e'\\})$. The time complexity of the algorithm should be $O(V+E)$.

Intuitively, the algorithm is quite simple: add $e'$ to $T$, and then we got one cycle closed. Remove the edge with maximal weight from this cycle, and obtain a MST of $G'$.

However, I had some difficulties prove the correctness of this algorithm formally, and would appriciate some help.

BTW. I have read this post: If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? but unfortunately haven't fully got the proof there.

Update: I tried Steven's solution and it helped me a lot, thanks again. I also found this solution online (I add a picture), but didn't understand it well. I also don't understand why in this solution, $T'$ is *the* MST on $G'$ instead of *a* MST on $G'$. Can someone help me understand what is going on the proof there, please?

# Answer
Let $T$ be the MST of the original graph $G$ and let $e'$ be the newly added edge. Suppose for simplicity that all edge weights are unique (if they are not, fix any arbitrary linear order among $E(G)$ that prioritizes the edges in $E(T)$. Then break weight ties according to this order).

Let $e$ be the edge of maximum weight in the unique cycle $C$ of $T + e'$. And assume that $e \neq e'$ (otherwise the proof is trivial).

One way to prove that $T-e+e'$ is a MST of $G+e'$ is showing that no edge $f \in \\{e\\} \cup E(G) \setminus E(T)$ can belong to any MST of $G+e'$ using the cycle rule.

If $f=e$, $f$ cannot belong to any MST of $G + e'$ because it is the edge of maximum weight of the cycle $C \subseteq T+e' \subseteq G + e'$.

If $f \in E(G) \setminus E(T)$ then, since $f \not\in E(T)$, $f$ must be the edge of maximum weight of some cycle $C' \subseteq G \subset G + e'$ and hence it cannot belong to any MST of $G + e'$.
> 1 votes

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


# Question
Title: Languages A, B ∈ NP-complete such that A⋃B = Σ*
I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a complement of $A$ and therefore $B$ belongs to $coNPC$. What is my mistake? Thank you!

# Answer
> 1 votes
Hint: let $A$ be a NP-complete language and $B=\Sigma^\*$. Then $A \cup B = \Sigma^\*$. Is $B$ the complement of $A$? Does it belong to coNPC?

---
Tags: complexity-theory, formal-languages, np-complete
---


title: Enhance B-Tree with find(k) function

text:
# Question
Title: Enhance B-Tree with find(k) function
I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to be in $O(t \cdot \log\_t{n})$ time complexity. I also need to show that the function does not make the regular functions (insert, delete, split child) any different then what they used to be before ( time complexity- wise)

for example, for this tree (Only example! max degree = 3, t=2 because $MaxDeg = 2 \cdot t - 1$):

find(50) would return: 6 (because its in the sixth element of the sorted keys: 10 10 20 20 20 50 60 70 80)

I thought about storing how many keys are before each key, and thus we can actually do it in $O(1)$ but it seems unrealistic, if the question asks for $O(t \cdot log\_t{n})$

Thank you!

# Answer
First take the case when you don’t have any key repeated: you can use an ordinary Binary Search Tree (BST) and perform an inorder traversal for searching the required key. Since inorder traversal gives you the keys in sorted order, so you can simply maintain a counter which you increase every time you visit a new node.

Since, you want to allow multiple occurrences of keys, you need need to modify the node to have a integer to hold the number of times that key has been added.

It’s quite easy to fill the details.
> 0 votes

---
Tags: data-structures, trees, b-tree
---


title: encrypt with permutation ciphers

text:
# Question
Title: encrypt with permutation ciphers
I came across this question:

You are given a permutation cipher defined by the bijection t: N -\> N where,

```
t(i) = i + 10, for i < 10,
t(i) = i - 10, for 10 <= i <= 20, and
t(i) = i, for i > 20.

```

Assume that the first index is 0, given a message m = 'HELLO WORLD AND THIS IS A SECRET MESSAGE', what is the ciphertext c?

Where the answer was the following:

```
D AND THISHELLO WORL IS A SECRET MESSAGE

```

but i don't get how. That's now what we get if the message is spelled out diagonally down and up over a number of rows and then read off row-by-row.

# Answer
> 2 votes
Just apply the given permutation on the string.

Your string is : 'HELLO WORLD AND THIS IS A SECRET MESSAGE'.

Now, to apply the given permutation, we have to shift the first 10 characters rightward by 10 units, and the next 10 characters leftwards by 10 units, while leaving the rest same. Note that you also need to count the spaces.

# Answer
> 0 votes
Let the original message be $m$ and let the ciphertext be $c$. Then $$ c\_i = m\_{t(i)}. $$ (Or perhaps it's the other way around. For our $t$ it doesn't matter, since it's an involution.)

If you apply this transformation to the given message, you'll get the given ciphertext.

---
Tags: computer-networks, permutations, security, encryption
---


# Question
Title: how to formally arrive at a correct EBNF grammar of a language
I am trying to write a mini parser for a simple language whose specification is as follows:

A search term is represented by. Both `searchkey` and `searchvalue` is a word formed by using alphanumeric characters.

```
<searchkey> <searchoperator> <search value>

```

**:** represents the exact match(similar to "=").
ex :

```
response:success

```

multiple search terms can be combined with `AND` & `OR` operator. ex.

```
response:sucess AND extension:php

```

By default `AND` has higher precedence than `OR` but this can be changed by grouping the search terms in a round bracket. ex:

```
response:sucess AND (extension:php OR extension:css)

```

along with `:` other valid operators search operators are `>, >=, <, <=` . ex.

```
time >= 2020-01-09 AND response:success OR os:windows

```

A search term could be preceded with `NOT` keyword to do the negation. ex.

```
response:success AND NOT os:windows

```

I have written this grammar in ebnf notation :

```
<exp> ::= <exp> " OR " <exp> | <logical_and>
<logical_and> ::= <exp> " AND " <exp> | <logical_not>
<logical_not> ::= " NOT " <logical_not> | <term>
<term> ::= "(" <exp> ")" | <atom>
<atom> ::= <word> <op> <word>
<op> ::= ">" | ">=" | ":" | "<" | "<="
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

```

But originally I had come up with this grammar.

```
<expr> ::= <or>
<or> ::= <and> (" OR " <and>)*
<and> ::= <unary> ((" AND ") <unary>)*
<unary> ::= " NOT " <unary> | <equality>
<equality> ::=  (<word> ":" <word>) | <comparison>
<comparison> ::= "(" <expr> ")" | (<word> (" > " | " >= " | " < " | " <= ") <word>)+
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

```

is there any difference if I choose one over another? Can there exist multiple grammars for a language? Is there any formal way to generate grammar for a language? this is a small language so its easy to get the grammar intuitively by tweaking it but what if the langue specification is huge?

# Answer
> 3 votes
Your informal description of your language could certainly be made more precise, in the same way as you could make the description of any (mathematical) set more precise until you've written the description out in mathematical notation. In that sense, EBNF is similar to what you get when you recast an informal description of a language into a mathematical formalism. (EBNF doesn't quite qualify, but the BNF formalism which inspired EBNF is a precise formalism.)

In between the formal description of a language and the practical question of building a parser for the language, a number of practical issues need to be dealt with, many of them having to do with the way a string of characters is grouped into meaningful tokens in the concrete representation of the language. In other words, questions like "where can spaces and newline characters be placed?" "Can I insert comments into an expression?" and so on. It's possible to write these into a formal description of a language, but the end result is often not particularly useful for the casual reader because the high-level structure of the language is overwhelmed by pesky details.

I note in passing that your grammar requires that `AND` and `NOT` appear with precisely one space preceding and following, while no spaces are allowed around the `>=` operator (and friends). That means that several of your examples don't match the EBNF. For example, `time >= 2020-01-09` would have to be written as `time>=2020-01-09` and `response:success AND NOT os:windows` as `response:success AND NOT os:windows` (with two spaces between `AND` and `NOT`). I doubt that was your intent, and I don't say this to criticise; just to point out how tricky it can be to get the details right, so that it can actually be used to construct a concrete parser, and still make the grammar usable for human readers. The usual approach is to separately formalise the division of the text into lexemes ("tokens") and the syntactic structure of the language, which treats the inputs as a stream of tokens rather than as a stream of undifferentiated characters. That's by no means formally necessary, and a lot of the applications of EBNF do in fact attempt to be precise to the character level, but a close examination of these EBNF applications might reveal the practical limitations of this strategy.

As I said in a comment, for any language for which a context-free grammar exists, there are an unlimited number of other context-free grammars which derive the same language. However, the question of whether two context-free grammars derive the same language is undecidable; no algorithm exists which can always correctly make that determination. Consequently, it is also impossible to enumerate all the grammars which could derive a given language (however that language is given).

In addition, there are competing mathematical formalisms which could be used to describe a language. After all, a language is a set, and any mathematical expression which precisely defines a set is a possible formal language description. (Some of these will be more practically usable than others.) So there's no way to say whether a procedure exists to generate a description in one formalism from a description in another formalism without know what, exactly, the nature of the two formal systems is. Sometimes it will be possible, other times not.

If you only want to know if a given text is in a language, then any of the unknowable infinitude of possible grammars for that language will suffice, although it's better if the grammar formalism used is computationally tractable. But most of the time, you don't just want to know that a text is in a language. (A C "compiler" whose only possible output is one of the messages "yes, that is a well-formed C program" and "no, that is not a well-formed C program" is unlikely to attract many paying customers, even if its judgement is 100% correct.) In most applications, you want to parse the language in order to reveal the syntactic structure of a valid text. To do that, your grammar should reflect the syntactic structuring you have in mind, and not all of the possible grammars for the language do.

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


# Question
Title: Are all language over $\Sigma= \{0\}$ decidable?
I have problem in determine whether it is decidable or not, can somebody help me please

# Answer
A language over $\\{0\\}$ is any subset of the set S of all strings consisting of a finite number of 0s. S is countable, the set of all subsets of S is uncountable.

Any decidable language must be decided by some algorithm. The set of algorithms, no matter how you describe it, is countable, not uncountable. Therefore some subsets of S (actually almost all) are not decidable.
> 4 votes

# Answer
No. Consider any undecidable language $L$ (for example, take the language $Halt = \\{(M,x): \text{ M halts on x}\\}$), we can encode each string of this language in unary (by writing the binary number representing $(M,x)$ in unary using $0$ as the symbol) to get a language $L\_0 \subseteq \\{0\\}^\*$. It’s not hard to see that $L\_0$ will also be undecidable because $L$ is.
> 2 votes

---
Tags: formal-languages
---


title: Minimizing Trimmed Distances

text:
# Question
Title: Minimizing Trimmed Distances
I'm trying to understand what is the minimum of the following function,

$$ f(\mu) = \frac{1}{n}\sum\_{i=1}^n F\left(\frac{\pi(i)}{n}\right) (x\_i - \mu )^2 $$

where $F$ is a step function that assign $1$ to any $t \in \[0, \gamma\]$ and $0$ in $(\gamma, 1\]$, $\pi$ is a permutation that sorts the $i$s based on the ascending ordering of the losses $( x\_i - \mu )^2$ and $\mu$ and $x\_1,\ldots,x\_n$ are real numbers. I was thinking that perhaps the minumum of $f$ is achieved by the trimmed mean, namely: sort the $x\_i$s discard the first $(1-\gamma)/2$ and the last $(1-\gamma)/2$ of the $x\_i$ and compute the arithmetic mean of the remaing points. However, it isn't as a simple numeric example shows.

Any ideas or maybe suggestions (perhaps it is a known problem)? Many thanks in advance.

# Answer
Your loss function is proportional to the $\gamma n$ smallest square differences with respect to $\mu$.

This is minimized by sorting your $x\_i$ and choosing the mean of the contiguous substring $x\_k, x\_{k+1}, \dots, x\_{k+\gamma n-1}$with the smallest variance.
> 0 votes

---
Tags: optimization, statistics
---


title: Proving van Emde Boas recurrence

text:
# Question
Title: Proving van Emde Boas recurrence
I have tried to solve the following question:

> **van Emde Boas Bounds** Show that $T(u) = T(\sqrt{u}) + O(1)$ has the solution $T(u) = O(\log\log u)$. *Hint:* consider the binary representation of $u$.

In CLRS (Introduction to Algorithms), they make use of the master method case 2. They let $m = \log\_2u$ so we have $T(2^m) = T(2^{m/2}) +O(1)$. Then they substitute $T(2^m) = S(m)$ and the recurrence looks as follows:

$$S(m) = S(m/2) + O(1).$$

The above confuses me, because I don't see how $S(m/2)$ is the same as $T(2^{m/2})$. Taking half of $m$ is not the same as taking half of the exponent $m$.

# Answer
The idea is to *define* a new function $S(m)$ by $S(m) = T(2^m)$. Then *by definition* we have $S(m/2) = T(2^{m/2}) = T(\sqrt{2^m})$.
> 1 votes

---
Tags: algorithms, proof-techniques, recurrence-relation, master-theorem, van-emde-boas-trees
---


# Question
Title: Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

My question is about this part.

\[Convolutional codes have been popular in practice because it is easy to factor the uncertainty of a bit being a 0 or a 1 into the decoding.\]

Why is it easy to use convolutional codes to factor the uncertainty of a bit?

Is it because the convolutional code circuit is designed in such way as to handle uncertainty properly? I couldn't really find the exact answer. I think the answer has something related to the fact that a convolutional code is not a linear code but I couldn't really understand exactly why a convolutional code is special to handle uncertainty.

# Answer
An important idea with convolutional codes is that the output sequences of bits (of the convolutional coder) consists of sequences of bits that are correlated with one another, i.e., not independent. Hence, in the receiver side, you know that, given what the convolutional coder is, the sequence of bits can only be some sequences, out of the big set of possibilities. Imagine a big space (say, it may be easier to imagine in 2 or 3 dimensions, then just imagine it gets extended to more dimensions), that has many points in it with integer coordinates, e.g., (1,0,1,1,0), but only only a few of these are allowed possibilities. So you look for the `maximum likelihood sequence`, which you could think of as the allowed point with the highest probability of having been the input to the convolutional coder.

Having soft-decision decoding, helps when you get to the stage of decoding the sequence of bits, as now, you have the probabilities of each bit being 1 or 0 (by itself, apart from the sequence), which can be fed into the computation of the likelihood of each sequence in the maximum likelihood sequence detection.

A simple example to illustrate: imagine if there are two allowed sequences coming out of the convolutional code: 10 and 01. Now, the receiver gets a sequence that it thinks is 11, but the first 1 only with high certainty (a very likely 1, let's say) whereas the second 1 only with low certainty (maybe 1, if we have to decide between 0 and 1, we say 1). This information helps to decide that the sequence was probably 10 rather than 01. Whereas, with hard decisions, you have 11 and both 10 and 01 are equally likely (e.g., same Hamming distance).

Why is it easy to handle the uncertainty of the bit by bit decisions? This is merely a statement that the decoding algorithms like the Viterbi algorithm, are fundamentally designed to accept the uncertainty values (probabilities) of the bit by bit decisions, as inputs. You could imagine some other algorithms where this is not true. But it is very natural and easy with such maximum likelihood sequence detection algorithms like the Viterbi algorithm.
> 1 votes

---
Tags: probabilistic-algorithms, error-correcting-codes
---


# Question
Title: Constructing a rectangle of size nx2 with dominos and L-shaped trominos
The Question is from DP tiling a 2xN tile with L shaped tiles and 2x1 tiles? I want an explanation about this question or theory

# Answer
* Let $f\[m\]$ be the number of ways to cover the shape shown below, an $m$ by $2$ rectangle. Our ultimate goal is $f\[n\]$.

```
     ┌───────────┐
   2 │           │
     └───────────┘
          m

```
* Let $g\[m\]$ be the number of ways to cover the first shape shown below, an $m$ by $2$ rectangle with an extra 1x1 square at the top-right corner. By symmetry, $g\[m\]$ is also the number of ways to cover the second shape shown below.

```
           m+1                     m
     ┌─────────────┐        ┌───────────┐
   2 │           ┌─┘      2 │           └─┐
     └───────────┘          └─────────────┘
          m                        m+1

```

To find the recurrence relation, try covering the space at the rightmost boundary of the above shapes in all possible ways.

Consider $f\[m\]$. We have the following 4 ways to cover the rightmost space.

```
              ┌─────────┬─┐     ┌──────┬────┐     ┌───────┬───┐     ┌─────────┬─┐
              │         │ │     │      ├────┤     │       └─┐ │     │       ┌─┘ │
              └─────────┴─┘     └──────┴────┘     └─────────┴─┘     └───────┴───┘
What is left:   (m-1)x2         (m-2)x2            (m-2)x2+1         (m-2)x2+1

```

So, we have $\quad\quad f\[m\] = f\[m - 1\] + f\[m - 2\] + g\[m - 2\] \cdot 2 $ for $m\ge2$.

Consider $g\[m\]$. We have the following 2 ways to cover the rightmost space of the first shape.

```
                     m+1                 m+1
               ┌─────────┬───┐     ┌─────────┬───┐
               │         │ ┌─┘     │         └─┬─┘
               └─────────┴─┘       └───────────┘
 What is left:   (m-1)x2              (m-1)x2+1

```

So we have $\quad\quad g\[m\] = f\[m - 1\] + g\[m-1\]$ for $m\ge1$.

Applying the above two recurrence equations, we can compute all $f\[m\]$ and $g\[m\]$, in order of increasing $m$, starting from $m=2$, given the initial conditions, $f\[0\]=1$, $f\[1\]=1$, $g\[0\]=0$ and $g\[1\]=1$.

```
# Python program to compute the first n+1 values of f
def show_number_of_ways(n):
    f = [0] * (n+1)
    g = [0] * (n+1)
    f[0] = f[1] = g[1] = 1
    g[0] = 0
    for m in range(2, n+1):
        f[m] = f[m - 1] + f[m - 2] + 2 * g[m - 2]
        g[m] = f[m - 1] + g[m - 1]
    print(f)

show_number_of_ways(10)
# [1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255]

```

---

Here is a way to derive a simpler recurrence relation that involves $f$ only.

Glorfindel's answer explains how to compute the number of patterns by "cutting the rightmost elementary block." To recap, there are one elementary block of size $1\times2$, one elementary block of $2\times2$ and two elementary blocks of $n\times2$ for $n\ge3$. Let $f(n)$ be the number of patterns for $2\times n$. we have the following base cases and recurrence relation, $$f(0)=1,\ f(1)=1,\ f(2)=2,$$ $$f(n)=f(n-1)+f(n-2)+2f(n-3)+2f(n-4)+\cdots+2f(0),\text{ for }n\ge3 $$

The above formulas leads to an algorithm that computes $f(n)$ with $O(n^2)$ time-complexity and $O(n)$ space-complexity.

We can do better. Replacing $n$ with $n-1$, we have $$f(n-1)=f(n-2)+f(n-3)+2f(n-4)+2f(n-5)+\cdots+2f(0),\text{ for }n\ge4 $$

Subtracting the above two equations, we get $$f(n)-f(n-1)=f(n-1)+f(n-3)$$ So we have for $n\ge4$, $$f(n)=2f(n-1)+f(n-3)\tag{simple}$$ Since $f(3)=5=2f(2)+f(0)$, the above recurrence relation holds for all $n\ge3$. This leads to an algorithm that computes $f(n)$ with $O(n)$ time-complexity and $O(1)$ space-complexity.

```
# Python program to compute the first n+1 values of f
def show_number_of_ways(n):
    f = [0] * (n+1)
    f[0] = f[1] = 1
    f[2] = 2
    for i in range(3, n+1):
        f[i] = 2 * f[i - 1] + f[i - 3]
    print(f)

show_number_of_ways(10)
# [1, 1, 2, 5, 11, 24, 53, 117, 258, 569, 1255]

```

---

We can also derive the simple recurrence relation directly from the first two mutual recursive relations between $f$ and $g$.

The equality $g\[m\] = f\[m - 1\] + g\[m-1\]$ tells us $f\[m-1\] = g\[m\]-g\[m-1\]$, and, hence, $f\[m\] = g\[m+1\]-g\[m\]$ and $f\[m-2\] = g\[m-1\]-g\[m-2\]$. Applying them to eliminate $f$ away in $f\[m\] = f\[m - 1\] + f\[m - 2\] + g\[m - 2\] \cdot 2$, we get $g\[m+1\]=2g\[m\]+g\[m-2\]$.

Since $f\[m\]$ is a linear combination of $g\[m+1\]$ and $g\[m\]$, $f$ satisfies the same kind of recurrence relation, i.e., $f\[m\]=2f\[m-1\]+f\[m-3\]$. Checking the valid range of the index $m$, we see that it is value for all $m\ge3$.
> 3 votes

# Answer
One way to think of it would be elementary blocks, i.e. blocks that cannot be split by cutting them vertically.

* There's one elementary block of size 1x2 (one vertical B).
* There's one elementary block of size 2x2 (two horizontal Bs).
* There are two elementary blocks of size 3x2 (the last two shown in your figure, Example I).
* There are two elementary blocks of size 4x2 (they both appear in the final pattern of Example II).
* In general, there are two elementary blocks of size $n \times 2$, $n \ge 3$.

Now, an $n \times 2$ rectangle can be divided into two smaller blocks by cutting the rightmost elementary block. (This includes the case where the elementary block is the entire rectangle).

* A 0x2 rectangle can be tiled in **1 way**.
* From a 1x2 rectangle, we can cut the rightmost elementary block (we have 1 of them) and we're left with a 0x2 rectangle, so it can be tiled in **1 way**.
* From a 2x2 rectangle, we can either cut a 2x2 block (1 way) or cut a 1x2 block and be left with a 1x2 rectangle (1 * 1 = 1 way), for a total of **2 ways**.
* From a 3x2 rectangle:
    + cut a 3x2 block (2 ways)
    + cut a 2x2 block (1 way) and be left with a 1x2 rectangle (1 way)
    + cut a 1x2 block (1 way) and be left with a 2x2 rectangle (2 ways)
    + Total: 2 + 1 * 1 + 1 * 2 = **5 ways**.

This way, you can work all the way to 10x2.

After computing a few terms, I found the sequence is A052980 in The On-Line Encyclopedia of Integer Sequences:

> a(n) is the number of possible tilings of a 2 X n board, using dominos and L-shaped trominos. - Michael Tulskikh, Aug 21 2019

so the final answer is **1255** for $n=10$.
> 2 votes

---
Tags: algorithms, tiling
---


# Question
Title: Formal defintion of SET-PARTITION as a language
I am not quite sure howto define SET-PARTITION as a language as in Sipser. Is it

$$ \left\\{ \langle S,A,B\rangle \\;\middle|\\; (A,B) \text{ is partition of } S \text{ and } \sum\_{n\in A} n = \sum\_{n\in B} n \right\\} \quad \text{ or } \\ \left\\{ \langle S\rangle \\;\middle|\\; \text{ there exists a partition } (A,B) \text{ of } S \text{ with } \sum\_{n\in A} n = \sum\_{n\in B} n\right\\} \quad ? $$

# Answer
The set partition problem asks **whether there exists a 2-partition** of a multi-set such that sum of numbers in one set is equal to the sum of numbers in the other set.

Note the phrase *whether there exists*; if you are already being given the partition in the input $\langle S,A,B \rangle$ then the problem becomes *whether the given partition is valid and sum of elements of $A$ and $B$ are equal*. This problem is easy and can be solved in polynomial it time.

However, Set Partition is NP-Complete, which seems unlikely to be solved in polynomial time.
> 1 votes

---
Tags: complexity-theory, formal-languages
---


title: Counting occurrences of word in a text

text:
# Question
Title: Counting occurrences of word in a text
Let's say I have a long text of 1M words and I would like to create a table of all the words ordered by the number of occurrences in the text.

One approach would be populating a dynamic array with each word and linear search them to count the occurrences in $O(n^2)$ then sort the array by occurrences in $O(n \log n)$.

Another approach would be to use y priority queue and a trie. The insertion in the priority queue is $O(\log n)$ and the build of the trie is $O(n)$. But traversing the trie to build the priority queue is somehow difficult to evaluate.

Eventually using a hash map seems to be the best solution, but computing the hash could cost a little bit of time even though it is just a constant. In this you have $n$ insertion/lookup in $O(1)$ then a final sort of the hashmap by occurrences in $O(n \log n)$.

So it is clear that the former approach is the worse and the latter the best. But how can I evaluate the complexity of the second one?

# Answer
I'm not sure I understand why do you need a priority queue.

The best algorithm should be as follows (pseudocode):

```
1) count the words
2) sort them by count

```

Counting each word you can loop through each word and update the count in the hash table for each word. This is done $n$ times and you need $O(1)$ for accessing + $O(1)$ updating the hash table thus $O(n)$.

Sorting is $O(n \log n)$. Thus the complexity is $O(n \log n)$.
> 1 votes

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


title: Substitution lemma for types

text:
# Question
Title: Substitution lemma for types
TAPL (page 549) proposes the following lemma in order to prove soundness of System F type system:

**Substitution lemma for types:**

$E, X, \Delta \vdash t: T \implies E, \[X \mapsto S\] \Delta \vdash \[X \mapsto S\]t: \[X \mapsto S\]T$

**Proof of the T-TApp case:**

$ E,X,\Delta \vdash t\[A\]: \[Y \mapsto A\]T $

and by rule T-TApp we have:

$ E,X,\Delta \vdash t: \lambda Y . T $

so by induction hypothesis:

$E, \[X \mapsto S\] \Delta \vdash \[X \mapsto S\]t: \lambda Y. \[X \mapsto S\]T$

so applying the T-TApp rule we have:

$E, \[X \mapsto S\] \Delta \vdash \[X \mapsto S\]t\[A\]: \[Y \mapsto A\]\[X \mapsto S\]T$

however I should need $\[Y \mapsto A\]\[X \mapsto S\]T = \[X \mapsto S\]\[Y \mapsto A\]T$

I think I can assume that $A,S$ cannot contain $Y$.

However, what if $A$ contains $X$? Then these types do not coincide.

Assume $T$ contains $Y$. Then the lhs type leaves $X$'s in the result while the rhs type does not leave any.

**Other sources**

You can find an sketched proof in the proof of lemma 17, page 86 of the following lecture notes. But this case appears to be immediate.

# Answer
> 1 votes
The substitution lemma only holds if what you're substituting is well-formed: $S$ can only contain type variables listed in $E$. In the application of T-TApp, $Y$ is a fresh variable, not present in $E,X,\Delta$. In particular, $Y \ne X$, $Y \notin S$ and $Y \notin A$.

There several ways to model variable names and renaming.

* Shadowing allows a binder inside another binder to use the same name (e.g. $\lambda x. \lambda x. M$), and then the outer name is hidden (shadowed) in the inner construct (any occurence of $x$ in $M$ refers to the inner $x$). If you want to refer to the outer variable (which can happen to perform a beta reduction, for example), you need to first perform an explicit alpha conversion to rename one of the variables.
* Implicit renaming always uses distinct names for any two binders present anywhere in an expression (so you never write $\color{red}{\lambda x. \lambda x. M}$ or even $\color{red}{(\lambda x. M) (\lambda x. M)}$, but $\lambda y. \lambda x. M$ and $(\lambda x.M) (\lambda y.\[x \mapsto y\]M)$), and there is an implicit alpha conversion after any reduction that duplicates a term. This is called the *Barendregt convention*.
* Most literature claims to use the Barendregt convention, but in fact uses an intermediate convention where there nested binders never use the same name, but binders that don't overlap each other can use the same name, and there is an implicit alpha conversion step immediately after shadowing occurs. So for example $(\lambda x.M) (\lambda x.M)$ is allowed in writing, but the meta-notation $x$ in the two subterms are supposed to represent two different variables. As far as I remember, TAPL uses this convention.

An environment is a collection of binders, so without shadowing, it cannot define the same variable name more than once (no $\Gamma\_1,X,\Gamma\_2,X,\Gamma\_3$).

Now, let's look at the application of T-TApp. The premise is $\Gamma' \vdash t' : \forall Y. T'$ where $\Gamma' = (E, \[X \mapsto S\] \Delta)$, $t' = \[X \mapsto S\] t$ and $T' = \[X \mapsto S\] T$. From this premise, you can conclude $$\Gamma' \vdash \lambda t'\[A'\] : \[Y \mapsto A'\] T'$$ for any well-formed $A'$. You want to prove $\Gamma' \vdash \[X \mapsto S\] (t\[A\]) : \[X \mapsto S\] \[Y \mapsto A\] T$. So take $A' = \[X \mapsto S\] A$. The conclusion is $$\Gamma' \vdash (\[X \mapsto S\] t)\[\[X \mapsto S\] A\] : \[Y \mapsto \[X \mapsto S\] A\] \[X \mapsto S\] T$$ and this is indeed $$\Gamma' \vdash \[X \mapsto S\] (t\[A\]) : \[X \mapsto S\] \[Y \mapsto A\] T$$ since $Y \ne X$ and $Y \notin S$.

---
Tags: logic, type-theory, types-and-programming-languages
---


# Question
Title: What does the phrase "Simple For Loops" mean in computability theory?
I was reading a Wikipedia page on **Primitive Recursive Functions** but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me?

*The Phrase:* ***An upper bound of the number of iterations of every loop can be determined before entering the loop***

The Wikipedia page

# Answer
The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input:

```
x ← 0
for i from 1 to A(n,n):
    x ← x + 1
return x

```

This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time.

A better explanation is the LOOP programming languages. Every loop in LOOP runs $x\_i$ times, where $x\_i$ is a variable, and the number of iterations is the value of $x\_i$ before the loop is run. For example:

```
  LOOP x DO
      x ← x + 1
  END

```

is a problem that doubles $x$, and

```
  z ← 0
  LOOP x DO
      z ← z + 1
  END
  LOOP y DO
      z ← z + 1
  END

```

is a problem that assigns $x + y$ to $z$.

A function can be computed in LOOP (using a reasonable input/output convention) iff it is primitive recursive. So if you only allow loops in which the number of iterations is the value of some variable *just before the loop*, then the resulting function will be primitive recursive, and furthermore, every primitive recursive function can be computed only using such loops.
> 5 votes

# Answer
This line is quite self describing. Still, let me explain a bit. `for` loops works in a specific range of values. For example: When you iterate over an array, knowingly or unknowingly you known the `length` of that array, which means that you know the no. of iterations your loop will perform.

Take a look at the pseudo code below:

```
FRUITS = ["APPLE", "BANANA", "MANGO"]

FOR FRUIT OF FRUITS
    PRINT FRUIT

```

Above, the `for` loop will run `3 times`, hence you know the no. of iterations before you even start that.

I hope know you understood that line well.
> 2 votes

---
Tags: computability, recursion, primitive-recursion
---


# Question
Title: Determine whether removing a node on a graph will disconnect the graph
I have an undirected unweighted graph with a single component. I want to know if removing a given node will disconnect the graph. I know that I can remove the edges to the node and then use DFS to get the number of components, however this seems rather inefficient as I need to check all vertices in the graph for this. Is there a faster way to do this?

# Answer
Yes, if we know something about the given graph. For example, if we know that graph is a tree or a cycle or a star graph. Or we might be able to terminate the algorithm early, for example, if we can determine the neighborhood of that node is still connected after that node is removed.

However, an algorithm to determine whether an arbitrary node is an articulation point or not in a general graph has to visit every node in the worse case.

Suppose a clever algorithm claims a given node is an articulation point without visiting all nodes. Suppose node $\mathcal U$ is not visited. Well, it could happen that $\mathcal U$ is connected to every node. Or there might be an edge that connects $\mathcal U$ to a point in the other connected component. That is a contradiction.

To be slightly more precise, any such algorithm should visit every remaining edge in the worst case.

Any way, a DFS that goes through all edges runs in $O(|E|)$ time is pretty fast for graph without too many edges. It should not be a big performance concern usually. If a series of node will be removed one by one and you want to determine the first one that disconnects the graph, it might help to do some precomputation to decompose the graph in certain way or other kinds of tricks to reduce the amortized cost. That is another story, though.
> 4 votes

---
Tags: graphs, connected
---


title: PAC-learning definition

text:
# Question
Title: PAC-learning definition
I am new in this field. In the book Foundations of Machine Learning by Mehryar Mohri, Afshi Rostamizadeh, and Ameet Talwalkar. The authors define the generalized error of a hypothesis as

$ R(h) = \Pr\_{x \sim D}\[h(x) \neq c(x)\] = E\_{x \sim D}\[1\_{h(x) \neq c(x)}\]$

which is a number. However in the Definition 2.3 a concep class $C$ is said to be PAC-learnable if

$Pr\_{S\sim D^{m}}\[R(h\_{S}) \leq \varepsilon \] \geq 1 - \delta$

for any $m \geq poly(1/\varepsilon,1/\delta,n, size(c)) $. Since by definition $R(h) = \Pr\_{x \sim D}\[h(x) \neq c(x)\]$ is a number, What does this mean $Pr\_{S\sim D^{m}}\[R(h\_{S}) \leq \varepsilon \] $ and $h\_{S}$ in formal terms? The authors explain that $h\_{S}$ depends on the sample $S$, but the question is how?

Another reason I have this question is due to the fact that every $h$ is defined as a function $h: \mathcal{X} \to \mathcal{Y}$ and the distribution $D$ is defined on $\mathcal{X}$, not on the *hypothesis set* $H$ where for each $h \in \mathcal{H}$, $h: \mathcal{X} \to \mathcal{Y}$.

# Answer
$R(h)$ is not necessarily a number, it is a deterministic function of $h$. So, it would be a number if $h$ is deterministic, but if $h$ is a random variable, then $R(h)$ is also a random variable.

We consider $S \sim D^m$, a dataset that consists of $m$ i.i.d. samples, assumed to be drawn with respect to $D$. Accordingly, $h\_S$ denotes the function that we end up with when we observed this fixed dataset $S$ (hence the subscript $S$).

Like you said, $R(h)$ is just a number for a given *fixed* $h$. However, in the case of $Pr\_{S\sim D^m}(R(h\_S))$, $h\_S$ is NOT fixed and hence, neither is $R(h\_S)$. Notice that it depends on the random dataset $S$ and as a function of a random variable, it is also a random variable.

Here is an example I just made up to demonstrate what these concepts correspond to:

> Suppose you have a system that keeps spitting out pictures of animals and you want to classify them. Let's say, $\mathcal{Y} = \\{\text{cat, dog, rat}\\}$ and $\mathcal{X}$ is the set of all pictures that this picture generator can spit out that shows one of these three animals. Then, $D$ is defined over $\mathcal{X}$ because it describes the probability of observing a specific picture, for all possible pictures. Then, $S$ is $m$ observed pictures from this picture generator, sampled in i.i.d. fashion. These are concepts that are independent from your learning system, but only related to the nature of the problem you're dealing with.
>
> Suppose you believe the best way to classify which animal is in a picture is to use a convolutional neural network (CNN) of a specific size and architecture and is trained using a certain algorithm. Then, you are restricting your hypothesis set $H$ as the set of all CNNs of that architecture and size that can be obtained via your specified training approach. If you instead decided to use SVMs, you would have ended up with a different $H$. Since $S$ is random, the CNN you'll obtain (i.e. $h\_S$) is also random.

Notice there is an inherent randomness in $h\_S$ due to the randomness in $S$, but there can be even more randomness if your training algorithm is non-deterministic. So, depending on the training approach that takes you from $S$ to $h\_S$, $h\_S$ can be a random variable even for a fixed $S$ (think about stochastic gradient descent).

Long story short, due to these random factors at play, $R(h\_S)$ is not just a number, but a random variable.
> 2 votes

---
Tags: machine-learning
---


# Question
Title: Complexity of numerical derivation for general nonlinear functions
In classical optimization literature numerical derivation of functions is often mentioned to be a computationally expensive step. For example Quasi-Newton methods are presented as a method to avoid the computation of first and/or second derivatives when these are "too expensive" to compute.

What are the state of the art approaches to computing derivatives, and what is their time complexity? If this is heavily problem-dependent, I am particularly interested in the computation of first and second order derivatives for Nonlinear Least Squares problems, specifically the part concerning first order derivatives (Jacobians).

# Answer
The time to compute first-order derivatives (gradients) and second-order derivatives (Hessians) depends heavily on the particular function.

In general, I am aware of three approaches:

1. **Analytical**: With pencil and paper, figure out an analytical expression for the derivatives, by using the rules of calculus. Then implement those expressions. Here the running time depends entirely on how easy or hard it is to compute those expressions. In some cases, you may be able to use a computer algebra system to help with this calculation.
2. **Automatic differentiation**: Use the computer to do compute the derivatives for you, given a program to compute the function itself. See, e.g., https://en.wikipedia.org/wiki/Automatic\_differentiation. This will construct a program that evaluates the derivative at a value of your choice. The running time and ability to do this depends entirely on the program you are differentiating. Generally speaking, if you are differentiating a function $f$ that can be computed in $O(n)$ time as a straight-line expression (with loop-free code that uses only elementary operations and conditionals, but no arrays or random-access memory lookups or loops), then automatic differentiation can construct a program that evaluates the derivative at an arbitrary input in $O(n)$ time. This is true even if the function is over multiple variables and you want to compute the gradient. The Hessian is slower: if $f$ is a function of one variable, you can evaluate the Hessian at an arbitrary point in $O(n)$ time, but if $f$ is a function of $m$ variables, it will take $O(mn)$ time.
3. **Numerical differentiation**: You can use the method of finite differences to approximate the gradient, given only a black box that can compute the function (you don't even need the code of that black box). See https://en.wikipedia.org/wiki/Numerical\_differentiation. Here if you have a function $f:\mathbb{R} \to \mathbb{R}$ of one variable that can be evaluated in $O(n)$ time using some black box, you can approximate the derivative or second derivative in $O(n)$ time. If $f$ is a function of $m$ variables, you can approximate the gradient at an arbitrary point in $O(mn)$ time, and estimate the Hessian in $O(m^2n)$ time.

Finally, one more method that may be acceptible in some settings is to evaluate the function $f$ at several points, fit a model $\hat{f}$ based on those points, compute or estimate the first- or second-order derivatives of $\hat{f}$ using any of above methods, and use that as an estimate of the corresponding derivative of $f$.

Saying you are interested in "nonlinear least squares" does not narrow things down, because "nonlinear" allows a completely arbitrary function, so long as it is not linear.
> 1 votes

---
Tags: complexity-theory, numerical-algorithms
---


# Question
Title: Status on Naoki Katoh's "Rectangle Wiring Problem" (minimum length tree to cover a partitioned rectangle)?
I have found this interesting problem in graph theory and geometry which is allegedly an open problem but latest status seems to be from 01/25/02. I can't seem to find any more information about it, not even other papers describing it.

# Answer
This problem has been studied since 2002, under the name *minimum-length corridor problem*.

The problem is known to be NP-complete\[1,2\], but there is a constant factor polynomial time approximation algorithm\[3\].

There is more work on this problem, which you can find by searching the citation network of the papers below.

---

\[1\]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. *Complexity of the minimum-length corridor problem*. Computational Geometry, 2007, 37.2: 72-103.

\[2\]: BODLAENDER, Hans L., et al. *On the minimum corridor connection problem and other generalized geometric problems*. Computational Geometry, 2009, 42.9: 939-951.

\[3\]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. *Approximation Algorithms for the Minimum-Length Corridor and Related Problems*. In: CCCG. 2007. p. 253-256.
> 3 votes

---
Tags: graphs, computational-geometry
---


# Question
Title: Change the structure from 3SAT to 1in3 3SAT
There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can always be TRUE by **at least one** literal is TRUE within each clause, just like 3SAT. How can I change the variable gadgets and clause gadgets to make it no matter each variable is positive or negative, the clause can always be TRUE by **only one** literal is TRUE within each clause, just like 1 in3 3SAT?

# Answer
A 1-in-3 SAT clause (A,B,C) can be expressed with the following 5 clauses in 3SAT.

$(A ∨ B ∨ C) $

$(A ∨ \overline{B} ∨ \overline{C}) $

$(\overline{A} ∨ B ∨ \overline{C}) $

$(\overline{A} ∨ \overline{B} ∨ C) $

$(\overline{A} ∨ \overline{B} ∨ \overline{C}) $

Why? Consider the truth table over A,B,C.

```
| A | B | C |   | A | B | C |
| 0 | 0 | 0 |   | --------- |
| 0 | 0 | 1 |   | 0 | 0 | 1 |
| 0 | 1 | 0 |   | 0 | 1 | 0 |
| 0 | 1 | 1 |   | --------- |
| 1 | 0 | 0 |   | 1 | 0 | 0 |
| 1 | 0 | 1 |   | --------- |
| 1 | 1 | 0 |   | --------- |
| 1 | 1 | 1 |   | --------- |

```

There are 8 lines. Each clause eliminates 1 line. We only want to allow (0,0,1), (0,1,0), (1,0,0) and eliminate the others.
> 1 votes

# Answer
Your question is not quite clear, but I believe you are asking how to show that 1in3SAT is NP-complete via a reduction from the known NP-complete problem 3SAT.

If this is your question, then consider the following set up, using your notation: Let an instance of 3SAT be defined by a set of $n$, Boolean variables $V = \\{x\_1, ..., x\_n\\}$ and a Boolean equation of $m$ clauses $\Phi = C\_1 \land C\_2 \land...\land C\_m$ where each $C\_j = (x\_{j\_1}\lor x\_{j\_2} \lor x\_{j\_3})$.

To reduce this to 1in3SAT begin the reduction in the following manner. For each $C\_j$ create 3 new clauses $C'\_{j,1} = (\lnot x\_{j\_1}\lor \alpha\_j \lor \beta\_j) $, $C'\_{j,1} = (x\_{j\_2}\lor \beta\_j \lor \gamma\_j) $, and $C'\_{j,3} = (\lnot x\_{j\_3}\lor \gamma\_j \lor \delta\_j) $ where $\alpha\_j, \beta\_j, \gamma\_j, \delta\_j$ are new Boolean random variables. Let $\Phi'$ be the Boolean equation in your 1in3SAT instance which now the AND over your these new clauses. That is, you now have $3m$ clauses and $n + 4m$ variables.

Next, think about what would happen if we had a true assignment for the 3SAT instance, then what would happen if we had a valid assignment for the newly constructed 1in3SAT instance (this second direction will be much easier.)
> 0 votes

---
Tags: reductions, 3-sat
---


# Question
Title: Decide if a language has a word of a given size
Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable:

$$L' = \\{w \in \Sigma^\* | \text{ there exists a word } w'\in L \text{ such that } |w'| \leq |w| \\}$$

I.e., $w \in L'$ if $L$ has some word with length smaller than $|w|$.

The way I was thinking to show that is observing that $L \cap\Sigma^{|w|}$ is finite, and $(L \cap \Sigma) \cup (L \cap \Sigma^2) \cup \ldots\cup (L\cap \Sigma^{|w|})$ is finite too, hence decidable. But the main thing I am struggling with is how can any algorithm for $L'$ know if some $u \in L$? this is undecidable, so it's unclear to me how any algorithm for $L'$ can verify that indeed some word is in $L$

# Answer
> 0 votes
There are two cases:

1. $L$ is empty. In this case, $L' = \emptyset$ is trivially decidable.
2. $L$ is non-empty. Let $m$ be the minimum length of a word in $L$. Then $L'$ consists of all words of length at least $m$, and is again trivially decidable (in constant time!).

As you can see, you never actually need an algorithm for $L$.

---

Similarly, the following language is always decidable:

$$L'' = \\{w \in \Sigma^\* \mid \text{ there exists a word $w' \in L$ such that $|w'| \geq |w|$}\\}.$$

There are now three cases:

1. $L$ is empty. In this case, $L'' = \emptyset$ is trivially decidable.
2. $L$ is infinite. In this case, $L'' = \Sigma^\*$ is again triviall decidable.
3. $L$ is finite. Let $M$ be the maximum length of a word in $L$. Then $L''$ consists of all words of length at most $M$, and is again trivially decidable (in constant time).

---

These are examples of non-constructive proofs, which you might not like. Instead of starting a discussion here, I refer you to this question.

---
Tags: formal-languages, computability, undecidability
---


# Question
Title: Does the product of two functions equal the product of their Big-O's?
let's say $f(n) = O(g(n))$ and $l(n) = O(m(n))$

is it always true that $f(n) \cdot l(n) = O(g(n)) \cdot O(m(n))$ ?

# Answer
By definition, $f(n) \leq c\_1 \cdot g(n)$ and $l(n) \leq c\_2 \cdot m(n)$, for some $c\_1$ and $n \geq n\_0$, and for some $c\_2$ and $n \geq n\_0'$ respectively. Suppose we set $n\_0^\* = \max (n\_0, n\_0')$, then both inequalities are satisfied for $n \geq n\_0^\*$. Then obviously $f(n) \cdot l(n) \leq c\_1 \cdot g(n) \cdot c\_2 \cdot m(n)$ for $n \geq n\_0^\*$. So indeed the claim holds. We can go take one additional step, however. Note that we can replace $c\_1 \cdot c\_2$ by a new constant, and thus we conclude that $f(n) \cdot l(n) = O(g(n) \cdot m(n))$.
> 3 votes

---
Tags: asymptotics
---


# Question
Title: Is there an Interval Tree which supports O(1) dynamic space requirements for queries?
I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).

In general when visiting a node in an (common) interval tree you are required to visit multiple child nodes and check for results there and recurse. This requires you to (dynamically) allocate memory upon lookup.

In contrast, f.e. consider a simple binary search tree. You can easily *unroll* the recursion because you will only ever visit a single child node.

Is it possible to achieve a similar algorithm for intervals? To clarify I would like to know whether there exists an interval tree which supports finding any overlapping interval in constant required space.

# Answer
> 1 votes
Short answer yes, you can achieve this in any type of tree, if there is a pointer from child to parent node.

The purpose of the stack is to remember you have to go back and visit another branch. Without the stack, but with the ability to go back to parent nodes, you can check if there is another branch that you *should* have visited.

Then the only space you need is 1 node. The query time might be slightly longer, although still log(n). The stack is an optimization, and after you remove it, you need an extra while loop to go back and check the latest other branch.

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


# Question
Title: How should we define the behavior of a Turing machine where the head tries to move left from the leftmost tape position?
If we have a Turing machine in a model with a tape that is infinite only to the right and assume at some point the head tries to move left from the leftmost position.

How should we define the behavior in such a case? Is a machine doing so for some input not a valid Turing machine? And if so, how can we make sure when we define a Turing machine that this situation can't occur for any input?

I've read some sources about Turing machines though couldn't find the answer to this specific case, and I see no reason why this case won't happen for an arbitrary Turing machine and some input.

# Answer
There is no single accepted model of Turing machines. Different choices would lead to very similar models, which simulate each other with very small overhead. That's why we usually don't care so much about the exact model.

Here are some possibilities:

* If the Turing machine attempts to move to the left of the origin, then the head stays put. The Turing machine might or might not be notified.
* The Turing machine has a mechanism to detect that it has reached the origin, and cannot move to the left of it (the specs don't allow it).
* Same, but not the machine can move to the left, and crashes if it attempts to do so (you decide how to interpret a crash – acceptance, rejection, infinite loop).
* If a Turing machine attempts to move to the left of the origin, then instead it moves right. This makes sense if the Turing machine is guaranteed to always move at every step.

You can probably think of several other alternatives.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: What does Lambda Calculus teach us about data?
In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing?

Some context: as a software developer, I got used to the concept of data so much that I never considered its true nature. I'd very much appreciate any references that could help me deeper understand the role of data in computation.

# Answer
You should turn the question around and ask what *is not* data. After all, code is just more data, is it not?

Perhaps a useful view from a programming point of view is that of a *value*. Say that in a programming language a *value* is a piece of information or data which can be stored, passed around as arguments and results of functions, they can be dynamically generated at runtime, etc.

Typical types of values are `int`, `char`, `bool`, various arrays of these, lists, trees, etc. In many languages functions are *not* values. For instance, in C you cannot pass a function as an argument or return it as a result. (Caveat: a pointer to a function is not a function!) Programming languages in which functions are values are called *functional programming languages*. Examples include Haskell, OCaml, SML, scheme, racket, javascript, and many others.

We can reformulate "there is no difference beween code and data" as "functions are values". So it really is a *design choice* as to whether code should be considered data. In functional programming languages this is the case, while in many others it is not.
> 4 votes

---
Tags: data-structures, lambda-calculus, computation-models
---