# Question
Title: Find out if a path exists avoiding circular obstacles
Given

1. a rectangle defined by its corners $(0, 0)$ and $(w,h)$,
2. $n$ circles $\\{ (x\_1, y\_1), (x\_2, y\_2), \dots, (x\_n, y\_n)$ with the same radius $r$,

I need to determine the smallest possible radius *r* so that there is no way to get from $(0,0)$ to $(w, h)$ without touching those circles.

What I have tried is

1. Use binary search to determine *r*
2. But the issue is that since there is no limitations for the coordinates of the points (e.g. for them to be integers) I can't get any idea how to construct a graph and use some path finding algorithm such as DFS.

Any help would be appreciated.

---

**Examples**

Example 1, $w = 15, h = 20$; circles with coordinates $(2,7)$ and $(7,3)$; the result is $d \sim 3.2016$

Example 2 (without the right radius, but just to show what the issue is)

# Answer
Your assumption using binary search is a good assumption, that means that we can assume we know the radius, and focus only on the subproblem:

> Given a rectangle and a set of circles, is it possible to navigate in the rectangle from the top left corner to the bottom right corner without touching a circle.

If a circle is covering either the starting point or the end point, we can abort immediately, so we'll assume they don't.

We will create a graph consisting one vertex for each circle, and one vertex for the *south east* edges of the rectangle, and one vertex for the *north west* edges of the rectangle, in other words:

$$V = \\{ v\_c \mid \text{$c$ is a circle} \\} \cup \\{v\_{\text{se}}, v\_{\text{nw}} \\}$$

Then we create the edges as follows:

$$E = \\{ e = v\_{c\_1} v\_{c\_2} \mid \text{$c\_1$ and $c\_2$ overlap}\\} \cup \\{ e = v\_{c} v\_{s} \mid \text{$c$ touches side $s$}\\}$$

In other words an edge between two objects if they overlap geometrically.

If the *south east* sides are connected to the *north west* sides, then it means that **you cannot travel from the lower left part of the rectangle to the upper right part** of the rectangle.

In other words, you only need to see whether $v\_{\text{se}}$ is connected to $v\_{\text{nw}}$ in your constructed graph, which would isolate the starting point from the end point.

---

**Yes instance**

**No instance** (south is connected to west)
> 4 votes

---
Tags: computational-geometry, binary-search
---


# Question
Title: Converting a special case TM to a regular TM
So, I have been given a TM where the head can access and write both the character that the head is pointing at and the next character to the right.

So if we have a TM abbb and the head is pointing at a, it can access and write into the the next character also ie the first b. So it has access to both the first and second characters of the string abbb. How would I show that this isn't actually a special TM but can be done with a regular TM too?

# Answer
> 1 votes
You want to show that this modified Turing machine is *equivalent* to the standard definition of a Turing machine, that is for every modified Turing machine $T'$ there exists a standard Turing machine $T$ such that $L(T')=L(T)$, and vice versa.

It is easy to show that for every standard Turing machine $T$ there is a modified Turing machine which accepts $L(T)$, just don't use the modified machine's ability to read or write to the input to the right of its head. Then these modified Turing machines are *at least* as powerful as standard Turing machines.

Now if $T'$ is a modified Turing machine which can read and write to the character immediately to the right of its head, we want to show that there exists a Turing machine $T$ which recognizes the same language as $T'$. Formally this gets a bit messy but the idea is whenever $T'$ would read or write an input from the cell to its right we add a sequence of states and transitions in which $T$ will move back and forth between the cell it is currently over in $T'$ and the cell to its right in $T'$ reading and writing as $T'$ does, then $T$ will move to the position and state specified in the transition function of $T'$. Essentially, if $T'$ reads from the cell to its right, $T$ will move to the right, read the input then move to the left. If $T'$ will would to the cell to its right, $T$ will move to the right, write the same thing $T'$ would have written, then move back, and transition to the same state $T'$ would have transitioned to.

---
Tags: turing-machines
---


# Question
Title: What is the purpose of manipulating trained layers?
In my course there are a number of exercises which amount to taking a trained residual network and deleting, swapping or repeating layers (without retraining).

Is there any real application for doing this? An exercise might say to swap two specific layers and I will find that the performance will increase (on a very small test set) but if I try to swap any other two layers the performance decreases.

To me it seems that operations in the exercises are chosen to increase the performance on the specific test set that we have but I don't see how it would improve generalisation. In answering the exercises I can say that the performance increased but I can't say why (because to me it seems to be an arbitrary manipulation of the network).

# Answer
No. I've never heard of this being used for a published task. Neural nets are trained with optimization (SGD) rather than by swapping/deleting/repeating layers.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Regular language where syntactic right congruence and syntactic congruence differ
> Find an example of a regular language where the syntactic right congruence and the syntactic congruence are not identical.

I have gone through the relevant definitions and understand them, but could not figure out an example for this case.

# Answer
> 2 votes
**Definition:** An equivalence relation $\sim$ on $\Sigma^\*$ is a *right (left) congruence* if $x\sim y$ implies $xv\sim yv$ (respectively $vx\sim vy$) for every $x, y, v \in\Sigma^\*$.

**Definition:** Given a language $L$ over an alphabet $\Sigma$, the *canonical right congruence* $\sim\_L$ is defined by $x\sim\_L y$ if and only if for all $z\in\Sigma^\*$ we have $xz\in L\iff yz\in L$. Similarly, for the *canonical left congruence* $x{}\_{L}\sim y$ if for all $z\in\Sigma^\*$ we have that $zx\in L\iff zy\in L$.

**Example:** Consider the (regular) language $L=\\{ab,abb\\}$ over $\Sigma^\*$. For this language, the relations $\sim\_L$ and ${}\_L\sim$ are not the same.

In fact, according to ${}\_L\sim$ the words $x=ab$ and $y=abb$ are in the same class. This is because if we prepend any $z\in\Sigma^\*$ to $x$ and $y$, both word $zx$ and $zy$ are in $L$ or not simultaneously. In fact, for $z=\epsilon$ both $zx=\epsilon ab=ab$ and $zy=\epsilon abb=abb$ are in $L$. However, when $z\neq \epsilon$, then both $zx$ and $zy$ are not in $L$. Therefore $ab{}\_L\sim abb$.

Now, when we consider the relation $\sim\_L$, we have that $ab\not\sim\_L abb$. In fact, if we take $z=b$ we get that $xz=abb\in L$ but $yz=abbb\not\in L$.

So, the regular language $L$ is an example for which its left and right canonical congruences are not the same relation.

---
Tags: formal-languages, regular-languages
---


# Question
Title: How to prove the language L that contains all Turing machines M where L(M) is recognizable is decidable?
How to prove that $L$, where $$L = \\{\langle M\rangle: L(M)\text{ is recognizable}\\}$$ is decidable? What about $\bar{L}$?

# Answer
> 2 votes
I claim that $L$ is decidable and I will construct a Turing machine to decide $L$.

Let $M$="on input $\langle M' \rangle$
$\quad ACCEPT$ "

Why does $M$ decide $L$? $M$ takes a description of a Turing machine as input and accepts, that is $L(M)=\\{ \langle T \rangle \mid T \text{ is a Turing machine}\\}$. If the input is not a description of a Turing machine, $M$ rejects. That is, $M$ always halts\*.

Now $L=\\{ \langle M \rangle \mid L(M) \text{ is recognizable}\\}$, but *by definition* a language is recognizable if there is a Turing machine that recognizes it. Hence **$L$ is also the language of all descriptions of Turing machines**. Since $M$ always halts and $L(M)=L$, $M$ decides $L$, so $L$ is decidable.

Since $L$ is decidable, $\bar{L}$ is certainly decidable too (on any input we can run $M$ and invert the output, we accept if $M$ rejects and reject if $M$ accepts.

---

\*Note we implicitly assume that a Turing machine can determine if its input string is a description of a Turing machine or not. This is generally a safe assumption since we are free to choose the encoding of the Turing machine and it is certainly possible to choose an encoding such this is the case (e.g, enumerate all Turing machines $TM\_1, TM\_2,...$ and let $\langle TM\_i \rangle=1^i$, that is a string of $i$ ones, then any string of ones can represent a Turing machine).

---
Tags: turing-machines
---


# Question
Title: Undecidability and Unrecognizability of Language with two Turing Machines
I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the statement, and assuming that Language1 is decidable, so that there is a decider D which decides Language1. Then we construct a Turing Machine which produces a contradictory result. However, I'm not sure how to do this! Can anyone help me formalize this? The question is:

Consider the following language called Language1:

Language1 = {(⟨M1⟩, ⟨M2⟩) | L(M1) = {⟨M2⟩} and L(M2) = {⟨M1⟩}} .

i. Prove that Language1 is undecidable.

ii. Prove that Language1 is unrecognizable.

# Answer
You are going to want to use a many-one reduction for this problem. Note that $ii \implies i$ so it is sufficient to prove statement $ii$. We know that the complement to the halting problem $$ \bar{H}=\\{\langle M, w \rangle \mid M \text{ does not halt on }w\\}$$ is not recursively enumerable. We can reduce $\bar{H}$ to $Language1$

$S$ = "
$\quad$on input $\langle M,w \rangle$
$\quad$construct $M\_1$ = "
$\quad\quad$on input $x$
$\quad\quad$if $x\neq $\<$M\_2$\>, $Reject$
$\quad\quad$run $M$ on $w$
$\quad\quad$$Accept$ "
$\quad$construct $M\_2$ = "
$\quad\quad$on input $x$
$\quad\quad$if $x\neq $\<$M\_1$\>, $Reject$
$\quad\quad$run $M$ on $w$
$\quad\quad$$Accept$ "
$\quad$Output $\langle M\_1, M\_2 \rangle$ "

Notice that if $M$ does not halt on $w$, then $M\_1$ accepts string $\langle M\_2 \rangle$ and $M\_2$ accepts string $\langle M\_1 \rangle$, and both reject all other strings, that is $L(M\_1)=\\{\langle M\_2 \rangle \\}$ and $L(M\_2) = \\{\langle M\_1 \rangle \\}$. On the other hand if $M$ does halt on $w$, $L(M\_1)=L(M\_2)=\emptyset$. Then $\bar{H} \leq\_m Language1$, since $\bar{H}$ is not recursively enumerable, neither is $Language1$.
> 0 votes

---
Tags: formal-languages, turing-machines, automata, undecidability
---


# Question
Title: Practice of setting parallelism as the default behaviour
This is a soft, and probably also an opinion based question.

Suppose I am writing a library in C++ for the purposes of working with financial data. My goals are:

1. Since I work with big data, I want to make it as fast as possible by using parallel computing principle inside the functions.
2. I want my colleagues to use this library without understanding/tweaking the parallelism underneath the functions.

The resulting questions are:

1. Is this a good idea to make parallelism the default behaviour? For instance `sum(vector)` to parallelise the summation without asking the user.
2. If yes, is there any rule of thumb that would cover the default behaviour of the task split between the processors? I.e. how many processors I should use?

Thanks in advance.

# Answer
> 1 votes
Parallelism helps with response time (the time it takes to complete one run of the algorithm), but it hurts throughput (the number of times you can run the algorithm per unit of time, if you want to run a large number of instances). It hurts throughput because synchronization between the threads itself costs time. The least expensive way to parallelize “run this algorithm once on each of these N inputs” is usually to run each input in full on a single processor. (There are exceptions, in particular if there are partial results that can be shared between runs.)

So if you expect that some users will want to do other things with their computer while they're running your software, there needs to be a way to limit how parallel it goes. “Other things” includes both running instances of your software, and running different software. In practice, this can usually be handled at the level of the operating system, but it isn't always convenient, especially if your software is chained with other software for which different parallelism settings are optimal.

Another reason why users might want to limit parallelism is if it causes a bottleneck in a factor other than running time, for example in memory usage. If each thread has a non-negligible memory cost, users may run out of memory before they run on processors. You can't predict the ratio of memory to processor count, so you can't predict what range will work out.

Furthermore, parallelism hurts for small instances: it takes time to instantiate threads and let them synchronize. Just because your software is intended for “big data” doesn't mean that every run will be on a large instance.

The main conclusion of what I've written here is that parallelism definitely needs to be tunable. More is not always better and there is no one-size-fits-all. This doesn't mean that maximum parallelism isn't a good default, just that it has to be configurable. But there is a reason not to make maximum parallelism the default: if it hits a threshold for another resource such as memory, it can make the program unusable. So in most cases, the default should be to use a single CPU, with an easy way to configure the number of CPUs or to use all available CPUs.

It's typically different with GPUs because they don't have much resource contention (GPUs don't have shared RAM) and if you're using them for computation, you're usually doing a single thing at a time. There, it makes sense for maximum parallelism to be the default. But it should still be tunable, in particular for users who want to run multiple parallel instances.

# Answer
> 2 votes
Have fun. If you use multiple threads you need to make sure that the overhead doesn’t outweigh the savings. The number of processors to use depends on the number of available processors, their properties (hyperthreading, performance vs. power saving), and the usage of the machine including the OS. And making one task fast may have negative side effects on the machine as a whole. Summary: It’s difficult.

Set your priorities: First make it work. Second make it maintainable. Third if required measure to find performance problems and fix them by using code that is not stupid (in the last ten years 99% of my performance problems were caused by stupid code and fixed by using code that isn’t stupid), then by using good code, then by using optimised vector code. Using multiple threads should be your very last resort.

---
Tags: parallel-computing, software-engineering, c++
---


title: edge coloring a directed acyclic graph

text:
# Question
Title: edge coloring a directed acyclic graph
I have an edge coloring problem as follows: Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L colors from 1 to L. Is there an efficient edge coloring algorithm to color all the edges, such that every path from s to e uses all the L colors and every path must be labeled differently? I attach a picture below for illustration, where vertex 1 is s, vertex 10 is e.

# Answer
I don't know whether there is a polynomial-time solution. Since $L$ is fairly small ($L\le 10$), one possible approach is to use a SAT solver.

Suppose $L=10$. For each vertex $v\_5$ at distance 5 from $s$, we'll enforce that all paths $s \leadsto v\_5$ have a different color sequence. Then, we'll do the same for all paths $v\_5 \leadsto e$. This suffices to ensure your property holds. (In general, replace 5 with $L/2$.)

Here is a plausible way to encode this in SAT. For each edge $e$ and each color $c$, add a boolean variable $x\_{e,c}$, which captures whether edge $e$ is assigned color $c$. Also, for each pair of edges $e,e'$ at the "same level" (i.e., their start nodes are at the same distance from $s$), and for each pair of edges $e,e'$ that are part of the same path from $s$ to some vertex at distance 5 or some path from a vertex at distance 5 to $e$, add a boolean variable $y\_{e,e'}$, which captures whether $e,e'$ receive the same color. Then add constraints:

* Enforce that $y$ are transitive by adding $y\_{e,e'} \land y\_{e',e''} \implies y\_{e,e''}$.
* Enforce that $x,y$ are consistent by adding $y\_{e,e'} \land x\_{e,c} \implies x\_{e',c}$ and $x\_{e,c} \land x\_{e',c} \implies y\_{e,e'}$.
* Enforce that the $x$'s are a one-hot encoding by adding the constraints $\bigvee\_c x\_{e,c}$ and $\neg x\_{e,c} \lor \neg x\_{e,c'}$ for all $e,c,c'$.
* Enforce that each path uses all colors, by requiring $\neg y\_{e,e'}$ for all pairs of edges $e,e'$ in the same path.
* Enforce that each path uses different colors: for each pair of paths of the form $s \to v\_1 \to v\_2 \to v\_3 \to v\_4 \to v\_5$, $s \to v'\_1 \to v'\_2 \to v'\_3 \to v'\_4 \to v\_5$, add the constraint $$y\_{s\to v\_1,s\to v'\_1} \lor y\_{v\_1\to v\_2,v'\_1\to v'\_2} \lor \dots \lor y\_{v\_4 \to v\_5,v'\_4 \to v\_5}.$$ Do the same for each pair of paths of the form $v\_5 \leadsto e$.

Then use an off-the-shelf SAT solver to solve this SAT instance.

I think the number of variables and clauses won't grow *too* large, so maybe there is a hope this instance of SAT might be solvable in a reasonable amount of time. In particular, for any particular vertex $v\_5$, the number of paths of the form $s \leadsto v\_5$ will be at most $5!=120$; if there are more, then the graph cannot be colored. Why? Well, as j\_random\_hacker points out, all such paths must use the same set of 5 colors. So, each such path's color sequence is of the $5!$ permutations of that set. Also, each such path must have a different color sequence (otherwise we can pick any one path $v\_5 \leadsto e$, append it to both, and obtain two paths $s \leadsto e$ with the same color sequence), so there can be at most $5!$ such paths. This means that the SAT instance will have something like ${120 \choose 2} M + {M \choose 2}$ boolean variables and clauses, where $M$ is the max number of vertices per layer.
> 1 votes

---
Tags: dag
---


title: Why is this control flow graph correct?

text:
# Question
Title: Why is this control flow graph correct?
Given the following method written in Java:

```
private void collatz(List<Integer> values) {
     int size = values.size();
     if (size == 0 ||
              values.get(size=1) <= 1) {
              return;
     } else {
        int last = values.get(size = 1);
        if (last%2 == 0) {
           values.add(last/2);
        } else {
           values.add(3*last+1) ;
        }
        collatz(values);
   }
}

```

My textbook gives the following CFG for the code:

Where each vertex describes the corresponding line of code. Why is this correct? What I don't understand is the edge between the vertex $13$ and the end vertex, shouldn't this edge be from $13$ to $2$ instead, since we're recursively calling the function? Would really appreciate your input.

# Answer
> 0 votes
Often control-flow graphs don't include call's or other interprocedural control-flow in the graph. So, a call node does not lead to an edge from the call site to the callee, and in this case, that means there would be no edge from 13 to 2.

---
Tags: java
---


# Question
Title: Is the Jacobian matrix calculation process correctly on this energy function?
When I implemented the paper Dynamic Fusion published in 2015 CVPR, I came into the trouble with how to solve the energy function:

$$E(W\_t, V, D\_t, \mathcal{E}) = \text{Data}(W\_t, V, D\_t) + λ\text{Reg}(W\_t, \mathcal{E})$$

Where:

* `Wt` is a set of 4x4 transformation matrix at time `t`;
* `V` is a set of 3D vertices from canonical model;
* `Dt` is a depth map at time `t`;
* `ε` is used to find `Wt` matrices;
* `Data` is a point-to-plane error;
* `Reg` is a smooth term which enforce the two adjacent transformation matrix `W` to be similar.

To simplify the question, I try to solve the `Data` term and throw away `Reg` term.
$$E(W\_t, V, D\_t, \mathcal{E}) = \text{Data}(W\_t, V, D\_t)$$

Here is the `Data` term:

\begin{align\*} r &= \text{Data}(W\_t, V, D\_t)= \sum\_u n\_u^{\intercal}\cdot (v\_u-vl) \\ where,\text{v}\_u &= W\_t×\text{v}(u) \\ \text{n}\_u &= W\_t×\text{n}(u) \end{align\*}

All the information but $W\_t$ is known, use Gauss-Newton to solve the parameter:
$$\begin{gather\*} \underset{W\_t}{\text{minimize}}\ r^2 \\ W\_t^{(t+1)} = W\_t^t - (J^\intercal J)^{-1}Jr \end{gather\*}$$

It seems to me that I need to calculate the Jacobian matrix $J$, so I expand `r` in matrix form:
$where\ W\_t=$ \begin{bmatrix} 1 & -\gamma & \beta & t\_x \\ \gamma & 1 & -\alpha & t\_y \\ -\beta & \alpha & 1 & t\_z \\ 0 & 0 & 0 & 1 \end{bmatrix} $v, n, vl$ are all 4x1 vector. (sorry, I don't know how to display matrix multiplication)

If I print all of the calculation, there are about 50 values containing $(\alpha,\beta,\gamma,t\_x,t\_y,t\_z)$ to sum up for one `Data` term. My question is, can I directly do partial differential to the parameters $(\alpha,\beta,\gamma,t\_x,t\_y,t\_z)$ of a $W\_t$ matrix to get Jacobian matrix $J$? It it correct to update $W\_t$ by $W\_t^{(t+1)} = W\_t^t - (J^\intercal J)^{-1}Jr$?
I cannot believe this is a good approach because it is kind of messy, and maybe inefficient. Please give me some advice how to solve this energy function, and I am curious why researchers only give energy function without explicit deviation on how to solve the function. Because energy function deviation is a common knowledge? If so, which course teach about it? I really want to take a course. Thanks.

# Answer
> 0 votes
That is not an equation to be solved; it is an objective function to be minimized. They apparently describe how they optimize it in Section 3.3.3 of the paper. I suggest trying to understand that section.

---
Tags: optimization, computer-vision
---


title: parse datetime number in html field

text:
# Question
Title: parse datetime number in html field
This is a sample of datetime field:

```
1615717137369

```

It means 2 days ago (from 16 march, 13:24)

How can I parse the number?

P.S: These are some examples:

16 15 89 8678037    16 March 16:15 ( 5 min ago)

16 15 89 8259356    16 March 16:08 (12 min ago)

16 15 89 791 8713   16 March 16:03 (17 min ago)
16 15 89 791 4439   16 March 16:03 (17 min ago)
16 15 89 791 0813   16 March 16:03 (17 min ago)

16 15 89 210 4036   16 March 14:20 ( 2  hr ago)

16 15 64 022 8942   13 March       (3 days ago)

16 10 43 350 1644   13 Jan         (2 month ago)
```

# Answer
As Emil said, That is the number of milliseconds since the Unix epoch (1 Jan 1970 midnight UTC).
> 2 votes

# Answer
The data you have is just a large integer. So you parse it like you would parse any large integer. Now there should be documentation what the integer means - if there is none then you will guess.

If the number was days since a date X, calculate what X would be. If the number was seconds since a date X, calculate what X would be. If the number was nanoseconds since a date X, calculate what X would be. Maybe it's a different unit. Pick what unit gives the most reasonable looking date. For example, if X is the year 1582 (introduction of the Gregorian calendar), that would be quite reasonable.

PS. I hate Windows. Giving dates using milliseconds is perverted IMO.
> 1 votes

---
Tags: python
---


# Question
Title: Given CFG generates all words with equally many 0s and 1s
Here is an exercise from an introduction to computation class:

> Show that the following context-free grammar $G$ generates the language $L$ of words over $\\{0,1\\}$ with an equal number of $0$s and $1$s: $$ S \to \epsilon \mid SS \mid 0S1 \mid 1S0 $$

How should I prove that $L⊆ L(G)$ and $L(G) ⊆ L$?

I think I should start with the difference of 0's and 1's but have no clue where to start.

# Answer
> 2 votes
One direction is easy. To prove that $L(G) \subseteq L$, we prove by induction on the length of the derivation that every word generated by $G$ has an equal number of 0s and 1s. This amounts to proving the following statements:

* $\epsilon \in L$.
* If $x,y \in L$ then $xy \in L$.
* If $x \in L$ then $0x1,1x0 \in L$.

The other direction, proving that $L \subseteq L(G)$, is more challenging. We have to show that every word in $L$ is generated by $L(G)$. The proof is by induction on the length of the word. The base case, which is the empty word, is easy. Now consider any non-empty words $w = \sigma\_1 \ldots \sigma\_n \in L$. Let $\delta(i) = \\#\_1(\sigma\_1 \ldots \sigma\_i) - \\#\_0(\sigma\_1 \ldots \sigma\_i)$. The sequence $$ \delta(0), \ldots, \delta(n) $$ starts and ends with $0$, and each element differs from the preceding one by $\pm 1$. Suppose that $\delta(1) = 1$, hence $\sigma\_1 = 1$. Let $i$ be the minimal index $i \> 0$ such that $\delta(i) = 0$ (such an index exists since $\delta(n) = 0$). Then $\delta(i-1) = 1$, hence $\sigma\_i = 0$. You can check that $x = w\_2 \ldots w\_{i-1}$ and $y = w\_{i+1} \ldots w\_n$ are both in $L$. By induction, $S \Rightarrow^\* x,y$. Therefore $$S \Rightarrow SS \Rightarrow 1S0S \Rightarrow^\* 0x1y = w.$$ If $\delta(1) = -1$ then instead we use the rule $S \Rightarrow 0S1$.

---
Tags: context-free, proof-techniques
---


# Question
Title: Tightest upper bound on length of distinguishing string in Hopcroft's algorithm
Hopcroft's algorithm is an algorithm for DFA minimization that produces a table identifying which pairs of states are distinguishable.

What is the tightest possible upper bound (with proof) on the minimum length of a string that distinguishes two distinguishable states?

This question is taken directly from Hopcroft, Mowtani, & Ullman, Exercise 4.4.3. I believe that the tightest upper bound is $\frac{(n-1)(n-2)}{2}-1$, but other sources I have found indicate that the tightest bound is $n-2$.

# Answer
> 1 votes
Let $Q$ be the set of states, $|Q|=n$. Consider the equivalence relation $E\_i\subseteq Q\times Q$ of "indistinguishability by strings of length at most i".

Let $k$ be the tightest upper bound. We have a pair of distinguishable states $p,q$ for which the shortest distinguishing string $w$ has length $k$, i.e., $(p,q)\in E\_{k-1}\setminus E\_{k}$. By reading the first letter $w\_1$ of $w$ we also get a pair of states $(\delta(p,w\_1),\delta(q,w\_1))\in E\_{k-2}\setminus E\_{k-1}$ for which the shortest distinguishing word has length $k-1$ (it is the word $w\_2\dots w\_k$). We can continue the same argument down to $0$.

Therefore, $E\_0\supsetneq E\_1\supsetneq\dots\supsetneq E\_{k-1}\supsetneq E\_k= E\_{k+1}=E\_{k+2}\dots$.

The equivalence $E\_0$ has two equivalence classes (parts): the accepting and the nonaccepting states. (Assuming that there is at least one accepting and at least one non-accepting state; otherwise nothing is distinguishable and the tightest bound is $-\infty$.) And any equivalence relation can have at most $n$ parts.

By the chain of strict inclusions above, $E\_1$ has at least 3 parts, $E\_2$ has at least $4$ parts, etc., and $E\_{n-2}$ has (at least) $n$ parts which means that $E\_{n-2}$ is the identity relation. This implies that the worst-case bound is $k=n-2$.

This bound is tight: Consider a two-element automaton with one accepting and one non-accepting state. We have $n=2$ and $k=0=n-2$.

---
Tags: formal-languages
---


# Question
Title: Solving recurrence relation for running time of combination formula
I'm trying to solve the following Time complexity recurrence relation:

$T(n,k)=T(n-1,k-1)+T(n-1,k)+1$

that come from following code:

```
int C(n, k) {
  if (k == 0 || k == n) return 1;  // stop recursion.
  return C(n-1, k-1) + C(n-1, k);
}

```

Unfortunately, I have no idea to solve $T(n,k)$. Any hint that helpful be appreciated.

# Answer
Let $C(n,k) = T(n,k) + 1$. Then $$ C(n,k) = C(n-1,k-1) + C(n-1,k). $$ This is exactly the recurrence of binomial coefficients, though there are also other solutions, for example $2^n$.

You can take the initial conditions to be $T(n,n) = T(n,0) = 1$, and so $C(n,n) = C(n,0) = 2$. You can check that $$ C(n,k) = 2\binom{n}{k} $$ satisfies both the initial conditions and the recurrence relation. Hence $$ T(n,k) = 2\binom{n}{k} - 1. $$
> 0 votes

---
Tags: algorithms, data-structures, recurrence-relation
---


title: Augmenting paths of two matchings

text:
# Question
Title: Augmenting paths of two matchings
Given a graph $G(V, E)$ and two matchings $M \subset E$ and $M' \subseteq E$ with $|M'| \> |M|$, how can one prove that $M\oplus M'$ ($\oplus$ denotes the symmetric difference) must contain at least $|M'|-|M|$ augmenting paths of $M$? I know that there have to exist some $M$-augmenting paths since $M$ is not a maximum matching, but I don't really know how to prove the above.

# Answer
**Proof:** We first notice a few things about the graph $G(V(M' \oplus M), M'\oplus M)$:

1. If there exists a cycle in $G$, it will be of even length. One can easily see this because if it was of odd length, two edges of the same matching would have to be incident to the same vertex which contradicts the definition of a matching. Hence, cycles don't contribute to the difference in edges (remember, $|M'| \> |M|$)
2. There can be paths of even and odd length. The former are not of any interest since they contain the same amount of edges from both matchings, not contributing to the difference. On the other hand, paths of odd length that are $M$-augmenting contain exactly one more edges of $M'$ than of $M$. This is because the paths edges alternate between edges of $M'$ and $M$ (also for the even paths) since no two edges of the same matching can constitute a path (as they don't share common vertices). Moreover, a paths of odd length that is $M'$ augmenting isn't of much interest since it doesn't contribute to the difference in edges.

From (2.) follows that only the $M$-augmenting paths of odd length contribute to the difference $|M'| - |M| \> 0$ (those paths can also be of length 1). Since each of those paths extends the matching $M$ by one edge, there must at least exist $|M'| - |M|$ of those $M$-augmenting paths since $|M| + |M'| - |M| = |M'|$. Notice that there can be more than $|M'| - |M|$ augmenting paths of $M$ if $M'$ is not a maximum matching (why?).
> 2 votes

---
Tags: graphs
---


title: Why is memory one dimensional?

text:
# Question
Title: Why is memory one dimensional?
Addresses in system programming languages like C are one dimensional (i.e. one number). This forces the programmer to make a decision whether matrices are stored "row major" or "column major" causing the opposite access to be slower.

This is somewhat surprising, since I think I remember that physical RAM is actually a 2 dimensional structure. And looking at the free part of this article. It seems like there exists a burst mode for accessing multiple elements from the same row.

Why does this burst mode not exist for columns, and why do programming languages not allow for true two dimensional storage of data? This would allow for "row major"/"column major" agnostic designs, which would probably speed up a lot of linear algebra libraries. Which would then trickle down to statistics and machine learning.

(Crosspost from StackOverflow)

# Answer
> 2 votes
Conventional RAM is organized in rows and columns. The CPU selects one row, then the RAM hardware gathers all cells in columns within that row and delivers them to the CPU.

If you were able to also select a column and gather all cells within that column, you would get a different set of bits. No guarantee that they are ordered in any useful way for you. No guarantee that for example a 64 bit integer would come out in sequential bits, no guarantee even for a byte. And the hardware needed is at least doubled, which likely means half the memory for the same price. And I can’t see how this would help you with a 100x100 array.

Where I have seen something similar is in graphics cards. Much drawing is done in a small rectangular area, so you want a cache line not to contain a long stripe, but a rectangular area of pixels. You start with x and y coordinates, then the lower 4 bit of x and y address bytes within a 256 byte cache line, and the other bits address cache lines. As a result, a 16 pixel long line in any direction can fit into a cache line, unlike normal arrangement where for a vertical line each pixel would be in its own cache line.

# Answer
> 1 votes
You're asking multiple questions.

*Why are instruction set architectures designed to use a one-dimensional address space for memory?* Memory isn't actually one-dimensional, but providing a one-dimensional abstraction is very convenient. It makes programmer's lives simpler, it makes the CPU architecture easier to specify in a comprehensible way, and it provides a single flexible abstraction that isn't tied to a particular technology of the moment or a particular device or platform.

It's not the CPU's abstraction for memory that forces you to choose between row-major vs column-major storage, and cause the opposite way of accessing a matrix to be slower; it's the way DRAM works that forces this decision.

*Why don't RAM chips provide both a row-burst and column-burst?* Our current DRAM technology is highly optimized for cost, density, and power. Supporting additional features like that would be more expensive and more complex. It's likely that the potential performance gains you're hoping for are not worth the additional expense, and would be modest for most applications, hence not worth it.

# Answer
> 0 votes
> Why does \[burst mode (fast access to multiple elements from the same row)\] not exist for columns?\`

There are different "dimensions" involved with varying the basic rectangular semiconductor memory:

0. invest extras in one place, e.g., separate data in&out vs. shared.
1. invest extras in one line along one of the dimensions of the cell array.
This is where most of the differentiation in DRAM specs has taken place.
Not too much variance in driving the "word"-/row lines. (Or the *write part* of the "bit" circuitry.)
*A lot* of it following the "sense amplifiers".
2. invest extras in the cell (array).
This is where extra area would really hurt.
Consider exchanging the roles of row and column:
"Easy" with two extra routing layers - "just" add "word" and "bit" circuitry to the other dimension.
(Not quite as easy, but potentially not as prohibitive in cost choosing the same layer for word lines in one and bit lines in the other dimension, and vice versa.) At the cost of doubled capacity, even if area did not increase.
Or you invest a second transistor for the second dimension (the part *needing* an area not too small being the capacitor) - and hope *that* doesn't blow up cell area.
(For pretty much the same additional logic - and routing closer to standard -, you could implement a true dual ported DRAM.)

At the *benefit* side, this allows for *other dimension bursts* in multiples of the *one direction array size*, only, else you'd need compiler awareness of RAM chip array size.
For full effect, you need a different (2D?) addressing model throughout more likely than not.

---

Dual (like-)ported memory is usually built from commodity memory parts:
for one thing, that keeps component cost capped at about three times single ported, and investment cost way down instead of up.
I think the same approach and argument to apply here.

---
Tags: arrays, memory-hardware
---


title: Master theorm and epsilon value

text:
# Question
Title: Master theorm and epsilon value
I have been reading CLRS and came across a few examples of the Master theorem. I could not follow the reason that epsilon was chosen as 0.8 in the example from page 96 . Can I simply use the condition n^log(b) of a to determine the maximum value of epsilon? For example for case 3 where ()=Ω(log+) for some constant \>0. T(n) =12T(n/2)+n^2. here the answer is n^ 3.58 so I am assuming it is n^3 and therefore Case 3 which means ()=Ω(log+) : How do i choose a value for epsilon that will be the maximum allowed to make .My effort 3.58+ \<1 seems nonsense. Which is correct to this case, or does the Master theorem not apply. Can this method be also be applied to the other cases. case 1 has an epsilon, but case 2 does not. when epsilon is an integer it is staright forward, but not so obvious( to me ) when it is a decimal. help would be apprecaited

# Answer
> 0 votes
$\epsilon$ is simply a value bigger than $0$, there is no maximum possible value for it. If you can find any $\epsilon\>0$ which makes either of the cases 1 or 3 of the master theorem true, then you have found the complexity for the algorithm (though additional checks might be needed for case 3 but it's not related to the question).

Considering the example you've provided in the question, $T(n)=12T(\frac{n}{2})+n^2$, we have $a=12, b=2,f(n)=n^2$. Checking the first case of the master theorem, we have $$f(n)=n^2\in \mathcal{O}(n^{log\_{2}12-\epsilon})$$ which is true for let's say $\epsilon=\frac{1}{2}$ (since $n^2 \< n^{log\_211.5}$).

You can choose many other $\epsilon$'s that still satisfy the condition, but all you need to do is find one and you're good to go.

---
Tags: algorithms
---


# Question
Title: Number of probes in a successful search in open address hashing
> Given an open-address hash table with $\alpha$ \< 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$

I read this in a book and the proof starts by saying

> Searching for k follows the same probe sequence as inserting it. If $k$ is the $i+1$th key inserted into the table, then $\frac{1}{1-\frac{i}{m}}$ is the maximum expected number of probes for the search.

However I don't understand how $\frac{1}{1-\frac{i}{m}}$ gives the number of maximum probes needed. Imagine we have $n=5$ and $m=10$ with linear probing. Now if we want to insert the 6th key, based on the fraction above it should take us at most $\frac{1}{1-\frac{5}{10}}=2$ probes. However imagine if slots 0 through 4 were occupied in our table and we start at index 0, then I guess it would take 5 probes to find an empty slot, right?

# Answer
> 3 votes
You are almost right about "5 probes". It will take, in fact, 6 linear probes to find an empty slot if the probe starts at index 0 of a table with slots 0 through 4 occupied (and slot 5 available). They are 5 failing probes and 1 successful probe at last.

However, you are, apparently, skipping the meaning of the word "expected". That word here means "on average" basically.

---

While the number of probes can be as big as 4 sometimes, it can be as low as 1 many times as well. So it is not surprising the *expected* number of probes can be as low as 2.

To be exact and rigorous, the phrase "expected number" as in "the expected number of probes" and "the maximum expected number of probes" has a specific meaning defined in mathematical terms.

> The expected value of a discrete random variable $X$ is $E\[X\]=\sum\_xx\cdot \text{pr}\\{X=x\\}$, where $\text{pr}\\{X=x\\}$ is the probability of $X$ taking value $x$.

"The expected number of probes" is the shorthand for "the expected value of the discrete random variable that stands for the number of probes." You can understand it simply as "the average number of probes".

I would recommend you read sections in the textbook you are reading that introduce or review related concepts. Or section 3, *Discrete random variables* in *Appendix C* of the book CLRS.

# Answer
> 3 votes
Most books/notes do not tend to emphasize this point, however when talking about expected values one has to be clear about what exactly is random. Since we're talking about open addressing, we have a hash function $h: U\times \[m\]\rightarrow \[m\]$, and we're dealing with a uniformly distributed input. The standard uniform hashing assumption in this context is that every probe sequence is equally likely, i.e. when $X\in U$ is chosen uniformly at random, then $\left(h(X,1),h(X,2),...,h(X,m)\right)$ is uniformly distributed over the set of $m!$ permutations of $\[m\]$.

Now, if $X$ is chosen uniformly at random, and is inserted to a hash table with load factor $\alpha=n/m$, it makes sense to talk about the expectation of the random variable $T\_X$ which denotes the number of probes until finding an empty cell (where again, the source of the randomness is at the choice the element $X\in U$). In Cormen's introduction to algorithms, theorem 11.6, it is proven that under the uniform hashing assumption, $\mathbb{E}\[T\_X\]\le \frac{1}{1-\alpha}$. The word "maximum" is a bit misplaced, this is just an upper bound on the expectation. Your question follows immediately from applying this bound to the $i+1$ element inserted.

---
Tags: hash-tables, hashing
---


# Question
Title: Search for specific element in sorted array
> Given sorted array $A\[1..n\]$. We want to find an element such that $A\[i\]=3i+2$ in $O(\log n)$(binary search).

I trying to relate to problem finding element in sorted array $A$ such that $A\[i\]=i$, but i can't use that technique to solve mentioned problem. Any hint be appreciated.

# Answer
Define $B\[i\] = (A\[i\]-2)/3$. Now you want to find an index $i$ such that $B\[i\] = i$.
> 0 votes

---
Tags: algorithms, data-structures, search-algorithms, discrete-mathematics
---


# Question
Title: Is mutual inductive type definition essential in coq core language?
I'm studying Coq's core language and I found that mutual inductive type definition is in it. https://coq.inria.fr/refman/language/core/inductive.html#theory-of-inductive-definitions

Before I read the material, I had supposed that Coq translates mutual definitions in Gallina into nonmutual ones in its core language, since it allows the core language to be smaller. But it wasn't and then I started to wonder why.

For instance, `even` and `odd` can be defined mutually as follows.

```
Inductive even : nat -> Prop :=
| even_O : even 0
| even_S : forall n, odd n -> even (S n)
with odd : nat -> Prop :=
| odd_S : forall n, even n -> odd (S n).

```

However, one can write another definition without `with` keyword.

```
Inductive even_or_odd: (is_even: bool) -> nat -> Prop :=
    | even_O : even true 0
    | even_S : forall n, even false n -> even true (S n)
    | odd_S : forall n, even true n -> even false (S n).

Definition even := even_or_odd true.
Definition odd := even_or_odd false.

```

I agree that the former looks better than the latter. However, What I wonder is if it is always possible to rewrite any mutually defined inductive type in a nonmutual way. If then, Coq does not necessarily include the mutual definition syntax in its core language.

Does the mutual definition allow more expressions to be defined? Is there any mutually defined type that can't be translated to a nonmutual one?

Or there isn't, but my concern about minimal core language is not a big deal?

Also, I am so sure that mutual fixpoints always can be translated to nonmutual ones. It looks much more clear to me compared to the case of inductive definition. Am I right?

# Answer
> 2 votes
It is always possible, as you noted, to translate a mutual inductive family into a non-mutual family, in much the same way as you described.

A couple of difficulties though:

1. If your mutual inductives are *not* parametrized, say you have

```
Inductive Foo := foo : Bar -> Foo
with Bar := bar : Foo -> Bar

```

(with some constants if you want to make the types non-empty)

Then you have 2 non-dependent types, for which induction, recursion and pattern matching are rather straightforward. But the translation you suggest involve creating a `FooBar : bool -> Type` which now needs dependent pattern matching everywhere. It's not impossible to cope with this as well, but it makes the elaborator quite a bit more involved.

2. Even worse are mutual inductives with different parameters: Imagine now

```
Inductive Foo : nat -> Type := ...
with Bar : bool -> Type := ...

```

Now we need to define a type `FooBar : forall b : bool, I b -> Type` where `I true = nat` and `I false = nat`. I'll let you imagine the case of multiple, possibly dependent parameters.

All these complications add up to a system that is quite complicated: I think it's a reasonable decision to add special support in the core to handle mutually inductive families, and it's the decision the Coq developers have made.

The Lean developers originally made a different decision, see here for instance.

However my understanding is that the complexities outlined above, along with the difficulty of hiding all this to the user, has made them re-think their position (I believe, but at the moment I can't find the reference of how things are in Lean 4).

---
Tags: functional-programming, dependent-types, proof-assistants, inductive-datatypes
---


# Question
Title: How polynomial interpolation of polynomial multiplication algorithm works?
I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following:

> **Algorithm** \[DPV, p. 60\]
>
> **Input:** Coefficients of two polynomials. A(x) and B(x), of degree d.
>
> **Output:** Their product $C = A . B$
>
> * Selection: Pick some points $x\_0, x\_1, x\_2, ..., x\_{n-1}$ where $n\geq 2d+1$
> * Evaluation: Compute $A(x\_0), A(x\_1), ...., A(x\_{n-1})$ and $B(x\_0), B(x\_1), ...., B(x\_{n-1})$
> * Multiplication: Compute $C(x\_k)=A(x\_k) \times B(x\_k)$ for all $k=0, 1, ..., n-1$
> * Interpolation: Recover $C(x) = c\_0 + c\_1 x + c\_2 x^2 + .... + c\_{2d} x^{2d}$

Now, I took an example $A(x) = 3x^2 -4x + 1$ and $B(x) = x-2$. The output should be $C(x) = 3x^3 - 10 x^2 + 9 x -2$. Now, the algorithm first choose an arbitrary points, so I will choose the following: $x\_0 = 1, x\_1 = 3, x\_2=6,$ and $x\_3 = 9$. Now, we evaluate the A(x\_i) and B(x\_i) for $i=0, 1, 2$ and $3$. Thus, $A(x\_0) = 0, A(x\_1) = 16, A(x\_2) = 85, A(x\_3)=208, B(x\_0) = -1, B(x\_1) = -2, B(x\_2) = -5,$ and $B(x\_3)=-8$. Thus, we compute $C(x\_i)$ for $i=0, 1, 2,$ and $3$. So, we get $C(x\_0) = 0, C(x\_1) = -32, C(x\_2)=-425,$ and $C(x\_3) = -1664$.

Now, I have $x\_0=1, x\_1=3, x\_2=6,$ and $x\_3=9$ and the corresponding $C(x\_0) = 0, C(x\_1) = -32, C(x\_2) = -425,$ and $C(x\_3)=-1664$. This I will apply the polynomial interpolation to get the output. I used this page to compute the coefficients of C(x). So, I got the output as following: $-3x^3 + 7x^2 - 5x + 1$ but it should be this one: $C(x) = 3x^3 - 10 x^2 + 9 x -2$. So, **where is the problem?** Is it because finding interpolation cannot be in exact so the coefficient is an approximation to the exact one.

# Answer
For testing, you can use SageMath very easily;

you had erros on

$$A(x\_0) = 0, A(x\_1) = 16, A(x\_2) = 85, A(x\_3)=208, \\B(x\_0) = -1, \color{red}{B(x\_1) = -2}, \color{red}{B(x\_2) = -5},\color{red}{B(x\_3) = 8}$$

```
    R = PolynomialRing(QQ, 'x')
    A = 3 *x^2-4*x+1
    B = x -2
    a0 = A(1)
    a1 = A(3)
    a2 = A(6)
    a3 = A(9)
    b0 = B(1)
    b1 = B(3)
    b2 = B(6)
    b3 = B(9)
    c0 = a0*b0
    c1 = a1*b1
    c2 = a2*b2
    c3 = a3*b3

    print( a0,a1,a2,a3)
    print( b0,b1,b2,b3)
    print( c0,c1,c2,c3)

    f = R.lagrange_polynomial([(1,c0),(3,c1),(6,c2),(9,c3)])
    f

```

Outputs

```
0 16 85 208
-1 1 4 7
0 16 340 1456
3*x^3 - 10*x^2 + 9*x - 2

```
> 2 votes

---
Tags: algorithms, polynomials, fast-fourier-transform
---


# Question
Title: Row Major Vs Column Major Order: 2D arrays access in programming languages
Programmers prefer accessing a 2D array in **Row-Major Order** rather than **Column-Major Order**, Why?

Are there some advantages/benefits of accessing a 2D array in row-major as compare to column-major?

Like in C programming, programmers prefer row-major rather than column-major due to the way memory is being allocated to a 2D array when defined statically or dynamically.

# Answer
The way you access the array affects performance.

It depends on how the matrix is represented and stored in memory. Often a matrix is stored in row-major order, so that consecutive elements of a row are contiguous in memory. Reading memory in contiguous locations is faster than jumping around among locations. As a result, if the matrix is stored in row-major order, then iterating through its elements sequentially in row-major order may be faster than iterating through its elements in column-major order.

Of course, if the matrix is stored in column-major order, the reverse will be true.

See https://en.wikipedia.org/wiki/Row-\_and\_column-major\_order for more on the subject.
> 4 votes

# Answer
It's a completely arbitrary decision. In Fortran, for example, "people" prefer column-major order, whereas in C "they" prefer row-major order.

In C the row-major order is forced due to reasons of syntax and the fact that dimensions are not always known in advanced. Fortran doesn't have that problem, so according to your line of argument, column-major order is the more "natural", the other order being used in C for technical reasons.
> 2 votes

# Answer
Both Row major and column major order takes same amount of time. Since both have same number of operations. i.e. Lets take A\[m\]\[n\]. Then the corresponding row major and column major formulas are :

1. row major = \[base address + (i\*n + j) * size of the data\_type\].
2. Column major = \[base address + (j\*m + i) * size of the data\_type\].

From the above formulas we can define that both have 4 operations to perform. So no factor affects the time of accessing the data.
> 0 votes

---
Tags: computer-architecture, arrays, memory-management, memory-access, memory-allocation
---


title: PCA applicability

text:
# Question
Title: PCA applicability
I understand that PCA takes a data set with input size, with output labels, and reduces the inputs to a set of principal components size r, where r \< n.

My question is whether or not this can be applied beyond a simple classification problem where the outputs are not simply labels. For instance, in sheet metal forming of a part, the inputs could be temperature, initial thickness, applied force, etc. while the output is thickness.

Could we use PCA (or kernel PCA) to reduce the inputs to a smaller number while relating them to the output as a thickness and not a label?

# Answer
Your understanding of PCA appears to be faulty. PCA does not look at labels or outputs. Instead, it takes a dataset, where each data point is a (high-dimensional) vector; and it maps that vector to a low-dimensional vector.

When you use PCA as a preprocessing stage in a pipeline for classification, typically you do PCA on the feature vectors: so the PCA ignores the labels and just transforms the feature vectors to a lower-dimensional vector. Then, some other classifier takes the lower-dimensional vector as input and tries to predict the label from it.
> 1 votes

---
Tags: algorithms, machine-learning, statistics
---


# Question
Title: Find best value for size of the table in hashing
> Given a set of keys $\\{i^2|0\leq i\leq 100\\}$, and a hash table such that collision resolve by chaining. Our hash function is $ k \mod m$ .
>
> What is option is best for $m$ to decrease our search for items in hash table and why?
>
> a.7
>
> b.9
>
> c.11
>
> d.12

I think c is the best choice, but i can't prove it.

# Answer
They are all rather bad, since you cannot avoid having at least nine keys having the same hash value, independent of the key.

For your particular problem, calculate the possible values of i^2 modulo 7, 9, 11, 12. For example i^2 modulo 7 is 0, 1, 4, 2, 2, 4, 1. I^2 modulo 12 = 0, 1, 4, 9, 4, 1, 4, 1, 4, 9, 4, 1. In each case, count how often each hash value appears (12: five 4s, four 1s, two 9s, one 0) and how many collisions you can expect (5^2+4^2+2^2+1^2)/144 = 46 / 144 = pretty bad.

I=11 should give you 21/121 collisions on average; still pretty bad but the best of the lot. You better check the calculations.

You have the problem that none of these hash functions distributes your keys remotely evenly. Something like (k * 1.3748538) mod c will destroy the mathematical relationship and gives much better results.
> 0 votes

---
Tags: algorithms, data-structures, hash-tables
---


# Question
Title: Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform
**Definition:** Distribution $D$ on $\\{0,1\\}^n$ is called *$k$-independent* if for every random variable $X$ with distribution $D$ and for all $i\_1, \dots, i\_k \in \\{1,2,\dots,n\\}$ random variable $X\_{i\_1,\dots, i\_k}$ has distribution $U\_k$ (uniform distribution on $\\{0,1\\}^k$).

**Problem:** Consider probabilistic algorithm $A$ that has oracle access to the input of length $n$. It means that algorithm $A$ can adaptively request $k$ bits of input (in more detail, $A$ can request one bit, then based on the oracle answer request another bit and repeat it not more than $k$ times). Prove that if $D$ is $k$-independent distribution than $Pr\_{x \sim D} \[A(x) = 1\] = Pr\_{x \sim U\_n}\[A(x) = 1\] $

First of all, I don't understand how adaptivity can potentially help the algorithm to distinguish the uniform distribution from a $k$-independent one. The second question is as in the problem.

# Answer
> 1 votes
A distribution $X=(X\_1,\ldots,X\_n)$ on $\\{0,1\\}^n$ is *$k$-independent* if for every $k$ indices $i\_1\<\dots\<i\_k$ and bits $b\_1,\ldots,b\_k \in \\{0,1\\}$, $$ \Pr\[X\_{i\_1} = b\_1, \ldots, X\_{i\_k} = b\_k\] = \frac{1}{2^k}. $$ Equivalently, the marginal distribution of $X\_{i\_1},\ldots,X\_{i\_k}$ is the uniform distribution on $\\{0,1\\}^k$. A simple induction shows that a $k$-independent distribution is $\ell$-independent for all $\ell \leq k$.

More generally, two distributions $X,Y$ on $\\{0,1\\}^n$ are *$k$-indistinguishable* if for every $k$ indices $i\_1\<\dots\<i\_k$ and bits $b\_1,\ldots,b\_k \in \\{0,1\\}$, $$ \Pr\[X\_{i\_1} = b\_1, \ldots, X\_{i\_k} = b\_k\] = \Pr\[Y\_{i\_1} = b\_1, \ldots, Y\_{i\_k} = b\_k\]. $$ Equivalently, the marginal distributions of $X\_{i\_1},\ldots,X\_{i\_k}$ and $Y\_{i\_1},\ldots,Y\_{i\_k}$ are identical. If $X,Y$ are $k$-indistinguishable then they are $\ell$-indistinguishable for all $\ell \leq k$. A distribution $X$ is $k$-independent if $X,U$ are $k$-indistinguishable, where $U$ is the uniform distribution on $\\{0,1\\}^n$.

Now suppose that $A$ is a randomized algorithm which queries a black-box vector $(z\_1,\ldots,z\_n)$ in at most $k$ places. Such an algorithm is sometimes called a randomized decision tree, and $k$ is its query complexity. We would like to show that if $X,Y$ are $k$-indistinguishable then the distributions of $A(X\_1,\ldots,X\_n)$ and $A(Y\_1,\ldots,Y\_n)$ are identical.

The idea is that at any point in time, $A$ decides what to do next — which coordinate to query, or what value to return — based on the coordinates $i\_1,\ldots,i\_\ell$ seen so far, where $\ell \leq k$. Since $X,Y$ are $k$-indistinguishable, the distributions of $X\_{i\_1},\ldots,X\_{i\_\ell}$ and $Y\_{i\_1},\ldots,Y\_{i\_\ell}$ are identical, and so the distribution of $A$'s next move is identical in both cases.

Expressing this idea more formally would require formalizing the definition of a randomized decision tree, and is beyond the scope of this answer; but I encourage the reader to do that, if they are in the possession of such a definition (or can come up with one on their own).

# Answer
> 2 votes
$$ \Pr\[A(x)=1\]=\sum\limits\_{i\_1,...,i\_j \\0\le j\le k} \Pr\[A(x)=1 | \text{A requested bits $i\_1,...,i\_j$}\]\cdot\Pr\[\text{A requested bits $i\_1,...,i\_j$}\]=\sum\limits\_{i\_1,...,i\_j \\0\le j\le k} \Pr\left\[A\left(x\_{i\_1,i\_2,...,i\_j}\right)=1\right\]\cdot\Pr\[\text{A requested bits $i\_1,...,i\_j$}\] $$

Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x\_{i\_1},...,x\_{i\_j})$ has the same distribution as $A(U\_j)$. If one considers randomized $A$ then change this argument to claim that the bits requested do not depend on the input, and thus the probability of requesting a certain set of indices does not depend on the distribution of the input. For the adaptive case, try the following. Denote by $a\_i$ the index of the $i'th$ bit requested by $A$.

$$ \Pr\[\text{A requested bits $i\_1,...,i\_j$}\]=\Pr\left\[\bigwedge\limits\_{l=1}^j a\_l=i\_l\right\]=\Pr\left\[a\_j=i\_j \Bigg| \bigwedge\limits\_{l=1}^{j-1}a\_l=i\_l\right\]\cdot \Pr\left\[a\_{j-1}=i\_{j-1} \Bigg| \bigwedge\limits\_{l=1}^{j-2}a\_l=i\_l\right\]\cdot...\cdot\Pr\left\[a\_2=i\_2 |a\_1=i\_1\right\]\cdot\Pr\[a\_1=i\_1\]. $$

Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a\_l$ conditioned on $a\_1,...,a\_{l-1}$ has the same distribution as $a\_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.

---
Tags: algorithms, probabilistic-algorithms
---


title: Explaining why a grammar is not LL(1)

text:
# Question
Title: Explaining why a grammar is not LL(1)
I need some help with explaining why a grammar is not LL(1).

Let us take the following grammar:

$$ \begin{align} S \rightarrow & aB \mid bA \mid \varepsilon \\ A \rightarrow & aS \mid bAA \\ B \rightarrow & b \\ \end{align} $$

This is my attempt:

For the grammar to be LL(1) it is a necessary condition that for any strings $c\_1γ$ and $c\_2β$, derivable from $S \rightarrow aB$ and $A \rightarrow aS$ respectively, we have $c\_1 \ne c\_2$.

But, $S \rightarrow aB$ and $A \rightarrow aS$, hence $c\_1 = c\_2$ and the grammar is not LL(1).

Is my reasoning right?

Thanks in advance.

# Answer
> 2 votes
I am afraid your reasoning is not exactly right.

A grammar is LL(1) if we can predict the production used from the current nonterminal $A$ to be rewritten and the next terminal $a$ in the string. $\newcommand{\To}{\Rightarrow}$ Using $\To$ to denote *leftmost* derivation, if $S\To^\* uAv \To uax$, we must have used unique $A\to\alpha$, independent on $x$. The problem that usually arizes is when $A$ is rewitten into $\varepsilon$ and $a$ is produced by the next nonterminal.

Try to construct another example.

# Answer
> 5 votes
If the grammar is ambiguous (at least one sentence has more than one parse tree), then the grammar is not in LL(1).

In general, you compute the LL(1) parse table and use it to answer the question. Your grammar is LL(1) if each cell in the table has at most 1 grammar rule. In other words, at least one table entry has more than 1 rule implies that your grammar is not in LL(1): http://en.wikipedia.org/wiki/LL\_parser#Constructing\_an\_LL.281.29\_parsing\_table

# Answer
> 0 votes
No left recursion in an LL(1) grammar.

A grammar with A → αβ1 | αβ2 is not LL(1).

If any entry is multiply defined then G is not LL(1). Possible reasons:  If G is ambiguous  If G is left recursive  If G is not left-factored  Grammar is not LL(1)

# Answer
> 0 votes
This grammar is not LL(1) due to the production: $S\\;\rightarrow \varepsilon$. In fact, for a grammar to be LL(1) in the presence of an alternative which can drive the empty string, the others should not begin with a follower of the non terminal in the left hand of the production rule ($S$ here); But in this case, the followers of $S$ are: $FOLLOW(S) =\\{a,b,\\#\\}$, and, sadly, the two other productions begin both with a follower of $S$.
Hope this help.
Good Luck!

# Answer
> 0 votes
Grammar should follow below rules to be LL(1)

1. It should not be Ambiguous.(Remove Ambiguity)
2. It should not be Left Recursive.(Remove Left Recursion)
3. It should not be a Non-deterministic.(Apply Left Factoring)

If any of the above rule is not satisfied then grammar is not LL(1). But if grammar follows all of above rules then we have to check following thing

* Dose Parsing table have more than one entry in one cell.

How to check this then?

If there is epsilon production and first and follow have intersection then grammar is not LL(1)

In your grammar S have a epsilon production follow and first have intersection.

# Answer
> 0 votes
This grammar is ambiguous grammar, so it is not in LL(1):

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


# Question
Title: Exit quickly from a maze with a local view of the maze
How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)?

You don't know the maze configuration but you know where your player is, and which direction are opened from his position.

Another point, the player can move RIGHT/DOWN/LEFT/UP, and the exit is at the bottom right.

I tried to mainly follow RIGHT/DOWN and avoid dead ends, but I think we can do better!

# Answer
> 1 votes
The fact that the exit is in the bottom right and has coordinates $(49, 49)$, while the player has coordinates $(1,1)$ makes me think that the maze has a fixed size of $49 \times 49$. If that's the case the exit can be found in constant time.

In fact, there is a **fixed** strategy (i.e., a sequence of moves) that uses a constant number of moves and exits the maze, **regardless of the maze layout!**

You can construct this strategy as follows: enumerate all possible maze layouts $L\_1, L\_2, \dots$ (a crude upper bound on the number of mazes is $2^{49^2}$).

You can construct the sequence $S$ of moves iteratively. Initially $S$ is the empty sequence. Then, for each $L\_i$ you can extend $S$ as follows:

* Assume that the maze layout is $L\_i$, and compute the position $p$ in which the player would end up by following the steps in $S$ from position $(1,1)$ in $L\_i$.
* Find a sequence $S\_i$ of at most $49^2$ moves that make the player walk from $p$ to $(49,49)$ in $L\_i$. This sequence always exists and can be found, e.g., with a breadth first search from $p$ in the graph induced by $L\_i$.
* Append $S\_i$ to $S$.

The resulting sequence $S$ has length at most $2^{49^2} \cdot 49^2 \< 2^{2413} = O(1)$.

Notice that the above algorithm is only needed to construct $S$ once and for all. An algorithm that solves your original problem can just output the hardcoded strategy $S$, without even looking at its input.

---
Tags: graphs, optimization, maze
---


title: A problem about Huffman codeword

text:
# Question
Title: A problem about Huffman codeword
> Under Huffman Encoding, what circumstances codeword length of each character be equal?(suppose number of character is power of 2)

I think if all frequency of characters is same then codeword length of all characters be the same. Surprisingly, if there are two characters that differences between frequency of two characters be $2$, and frequency of other be equal then codeword length of all characters be the same.

Main problem is, can i say, for each constant $c$, if there are two character that difference of frequency be $c$, and all remaining of characters have equal frequency then codeword length of each character be equal?

# Answer
Assume there are 2^n symbols, n \>= 2, and the frequencies of the most common and the two least common symbols are f, g, and h. We could use a code of n-1 bits for the most common and n+1 bits for the two least common symbols. This will reduce the average code length if f \> g+h.

You were specifically asking for the frequencies 2^-n + c/2, 2^-n, and 2^-n - c/2, so that’s the case for c \> 2^-n / 2.
> 0 votes

---
Tags: greedy-algorithms, huffman-coding
---


# Question
Title: Is the following language regular; context-free but not regular; or not context-free?
Let $\Sigma=\\{0, 1, \\#\\}$.

Is the following language regular; context-free but not regular; or not context-free?

Justify your answer $$L=\\{x\\#y :\ x, y \in\\{0, 1\\}^∗\text{ and }\operatorname{bin}(x) + 1 = \operatorname{bin}(\operatorname{rev}(y))\\}$$

# Answer
Denote your language by $L$. Notice that $$ L \cap 1^\*\\#0^\*1 = \\{ 1^n \\# 0^n 1 : n \geq 0 \\}, $$ which should suffice for showing that $L$ isn't regular.

On the other hand, $$ L = \\{ 0^a1^n \\# 0^n 10^b : n,a,b \geq 0 \\} \cup \\{ 0^ax01^n \\# 0^n1x^R0^b : n,a,b \geq 0, x \in \\{0,1\\}^\* \\}, $$ which should suffice for showing that $L$ is context-free.
> 1 votes

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


# Question
Title: Amortized analysis for disjoint sets' find-set(x) function (from CLRS)
I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic discusses about the time analysis for disjoint set operations using forests with union-by-rank and path-compression heuristics. In particular, I am stuck at Lemma 21.13 (580) for which the "find-set(x)" subroutine is claimed to run at `O(alpha(n))` time where alpha(n) is the inverse Ackermann function. I cannot arrive to the conclusion that there is at most `alpha(n)+2` nodes in the find path that satisfy some specific conditions. This node count comes from the maximum number of nodes where the `level(x)` is constant across the find path if my interpretation is correct. I assume it is an obvious outcome of previously proven lemmas. Unfortunately, I am not so bright to validate this result.

Of course, without the details about the potential function, this question cannot be answered. There is a big problem, besides that I cannot elegantly type it out in latex. There is a ton of lemmas that logically weave this proof. So, I assume that you have the text with you. Just in case if all of this is obvious to you, here are the fundamentals.

A really really big function:
1st arg -\> subscript (denotes the "level" (the notation also seems to be native within the book))
2nd arg -\> superscript (denotes the number iterations of the same function)
3rd arg -\> the actual input

$A(0,1, j) = j+1$
$A(k,1, j) = A(k-1,j+1,j) \mid k \ge 1$

its inverse for j = 1:
$alpha(n) = \min\\{k : A(k,1,1) \ge n\\}$

two auxiliary functions needed to define potential function:
//note that x is the node and x.p is its parent node, x.rank is its rank (the thing that increments monotonically traversing up)

level(x) = max {k: x.p.rank \>= A(k,1,x.rank)}
iter(x) = max {i: x.p.rank \>= A(level(x), i, x.rank)}

The potential function is then defined as:
//n is node count, q is the qth operation in the system, x is the node

phi(q,x) = alpha(n) * x.rank ; if x is not a root or x.rank = 0
phi(q,x) = (alpha(n) - level(x)) * x.rank - iter(x) ; if x is not a root and x.rank \>= 1

Again, I emphasize that this question is really specific about the literature because it is not so obvious as to how all this and the $alpha(n)+2$ path length is necessary to prove the bound. But, I am open to other proofs where the `find-set(x)` subroutine (the one which compresses the path in after finding the root) is a superconstant.

# Answer
The idea is actually quite simple. Just like in the book, let us assume that the find path consists of $s$ nodes. We disregard the root (because its potential doesn't change at all after the operation) and the node we upon which `find_set` is called (because it may have rank 0, which means its potential might not change). This leaves us with $s-2$ nodes.

Now, consider any node $z$ among the remaining $s-2$ nodes. As explained on pages 576-577 (I am using the 3rd edition), we have $0 \le \operatorname{level}(z) \< \alpha(n)$. In other words, the level of $z$ must be between 0 and $\alpha(n) - 1$, inclusive. Indeed, it is the fact that we have a finite number of options for the levels of the aforementioned $s-2$ nodes that will help us prove the assertion presented by the authors.

They say one example is worth a thousand words, so let's do one. Suppose we have 8 nodes between the root and the one upon which `find_set` was called. Suppose also that $\alpha(n)$ turns out to be $4$. Here's one possibility for the levels of the nodes, given in the order they appear in the find path:

$$ 2, 0, 1, 3, 2, 3, 1, 0 $$

The book claims that there are at most $\alpha(n)$ (4 in our case) nodes $x$ for which there doesn't exist a node y later in the path such that $\operatorname{level}(x) = \operatorname{level}(y)$. Take a good look at the sequence; you'll see that the claim holds for our example.

Now, the million dollar question. Why? Think about the last $\alpha(n)$ nodes. We could assign different levels to each one (as I have done for this example) so that none of them have a complementary node higher up the find path with the same level. However, that is the most we can have; every other node will now have some ancestor with the same level. Long story short, no matter how hard we try, we cannot have more than $\alpha(n)$ nodes without an ancestor of equal level; such a scenario would require more options for the level of a node than are available.

Put it all together, and it is evident that there exists another node with the same level down the line for at least $s - \alpha(n) - 2$ of the $s$ nodes, just like the book claims.

As for why the authors have found it unnecessary to provide an explanation for their claim, you are asking the wrong guy.
> 1 votes

---
Tags: amortized-analysis, disjoint-sets
---


# Question
Title: Is the term $(\lambda x.x)(y y)$ a normal form in call-by-value reduction strategy?
I am learning λ-calculus and I have some confusion about it.

Is the term $(\lambda x.x)(y y)$ a normal form in call by value reduction strategy? (where $y$ is a free variable)

From the wikipedia, it says:

> Call by value
>
> Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or abstraction).

Here the term $(\lambda x.x)(y y)$ is a beta redex, but the argument $(y y)$ is not a value.

So the term $(\lambda x.x)(y y)$ is a normal form, because there is no further beta reduction possible.

Is my understanding correct?

Very thanks.

---

Sorry for updated the question, because I just realized that there may be 2 questions behind:

1. In λ-calculus, does the terminology "normal form" depend on the evaluation strategy? i.e. When we say a term is a normal form or not, is there any evaluation strategy behind it? For example, `CBV ⊢ (λx.x)(yy) be a normal form` and `CBN ⊢ (λx.x)(yy) be not a normal form`?
2. When we say "a λ-calculus with call-by-value", is it equivalent to say "λ\_v-calculus"? I am reading Sabry and Felleisen's paper "Reasoning about Programs in Continuation-Passing Style". That paper mentioned λ\_v-calculus and in p.8 it says `(λx.x)(yy)` has no βv-redex.

# Answer
> 1 votes
After some research, I think I can answer this question by myself now.

## Short answer

Wikipedia is correct, that is

If the $\lambda $-calculus uses call by value reduction strategy, the term $(\lambda x.x)(y y)$ is a normal form.

## Long answer

Standard $\lambda $-calculus does not distinguish reduction strategies. It only gives you some Reduction Rules (e.g. $\beta $-rule). You searching for a β-redex in a given term, as long as you find a β-redex, you can reduce one step.

This means that

1. You can reduce a $\beta $-redex inside a $\lambda $-abstraction.
2. You can reduce the operand $\beta $-redex first and then reduce the operator $\beta $-redex.
3. At any step, you can use either call-by-value or call-by-name reduction strategy.

Church–Rosser Theorem tells us that the outcome of $\lambda $-calculus (if it exists) is independent of the order in which the calculations are executed.

The benefit of Church–Rosser Theorem is that we can define an Equational Theory at top of the Reduction Rules.

Note that in the description above, I used extremely imprecise terminology, i.e. reduction strategy. Now i will fix this impreciseness:

1. I think reduction strategy and evaluation strategy mean the same thing.
2. For now, we cannot use the term "evaluation" because we have not yet defined an Evaluation Theory.

Unfortunately, there is very little literature describe how to define the Evaluation Theory for standard $\lambda $-calculus. The reason may be that:

In general, to define the Evaluation Theory, we need an abstract machine, but the use of an abstract machine means a fixed evaluation strategy, but standard $\lambda $-calculus does not depend on the evaluation strategy!

Therefore standard $\lambda $-calculus has no corresponding Evaluation Theory is logical.

OK, so far so good.

However the standard $\lambda $-calculus is not suitable to reason about programming languages. For example, Scheme/SML use call-by-value evaluation strategy, Haskell use call-by-name (or more precisely call-by-need) evaluation strategy.

To reason about these programming languages, a new $\lambda $-calculus needs to be devised. For example, Plotkin's call-by-value $\lambda $-calculus ($\lambda\_v$ for short).

As standard $\lambda $-calculus, we now need to devise Reduction Rules, Equational theory and Evaluation theory for $\lambda\_v$. I won't repeat Plotkin's formula here, but give two key points:

1. In Plotkin's paper, "value" does not mean "has no *β*-redexes", but "not a combination" (A term of form $(MN)$ is a combination).
2. Equational theory must satisfy Church–Rosser Theorem (for $\lambda\_v$ version).

### Back to the original question:

Is the term $(\lambda x.x)(y y)$ a normal form in call by value reduction strategy?

Answer:

1. The question involved "normal form" and "reduction strategy" (which is another name of evaluation strategy). It doesn't make sense, because one refers to an Equational Theory and the other refers to an Evaluation Theory.
2. The question involved "call by value", we can fix this ill-question by assuming the calculus to be $\lambda\_v$ and since the question also involved "normal form" and $(\lambda x.x)(y y)$ is not a closed term, we use Equational theory of $\lambda\_v$.

The answer is:

$(\lambda x.x)(y y)$ has been a normal form, because $(y y)$ is not a value but a combination.

> $(\lambda x.M)N = \[N/x\]M$ (if $N$ is a value) ($\beta$ -rule)

You may argue that why $(y y)$ is not a value?

Can I define my own $\lambda\_v$-calculus and let a normal form (e.g. $(y y)$) a value?

The answer is no.

For example, suppose that a normal form can be a value, then there are two ways to normal the term $(λx.(λy.z) (x (λx.xx))) (λx.xx)$.

1. $ \to (λy.z)((λx.xx) (λx.xx))$, then loop
2. $\to (λx.z)(λx.xx) \to z$

This make Church-Rosser theorem fail.

Similarly, adding $\eta$ rule also makes Church-Rosser theorem fail.

For example, suppose that we add $\eta$ rule, then there are two ways to normal the term $ (λx.y) (λx.((λx.xx) (λx.xx))x)$.

1. $ \to (λx.y) ((λx.xx) (λx.xx))$, then loop
2. $\to y $

## Reference

Call-by-name, call-by-value and the λ-calculus

Reasoning about programs in continuation-passing style

---
Tags: lambda-calculus, evaluation-strategies
---


# Question
Title: Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$
I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct a grammar for the following language:

$$\\{a^n (bc)^m \in \\{a, b, c\\}^\* \mid m, n \ge 1 \land m \< n/2\\}$$

An explanation of how to start and go through the language would be really helpful.

# Answer
Let $n = n'+1$, $m = m'+1$. Then $m \< n/2$ translates to $n'+ 1 \> 2(m+1)$, i.e. $n' \geq 2m'+2$. Therefore we can write the language as $$ \\{ a^{1+2m'+2+k}(bc)^{1+m'} : m',k \geq 0 \\} = \\{ a^3 a^k (a^2)^{m'} (bc)^{m'} bc : m',k \geq 0 \\}. $$ You take it from here.
> 1 votes

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


# Question
Title: what algorithm is used to calculate the exponential function $e^x$?
I am using Matlab daily. But I just realized that I even do not know what algorithm Matlab is using for calculating the exponential function $e^x$.

The power series expansion is obviously not appropriate for a big $|x|$.

# Answer
Let $x = n \log\_e(2) + x'$, then $e^x = 2^n \cdot e^{x'}$. You can pick n so that $- 0.5\cdot \log\_e(2) ≤ x' ≤ +0.5 \cdot \log\_e(2)$.

$e^{x'}$ is easy to calculate because $x'$ is small, and $2^n$ can be calculated easiest by producing the bit represenation of $2^n$ as a floating point number.

That's the principle. You'll want to take care that x' is calculated with the highest possible precision, and that $e^{x'}$ is also calculated with the highest precision. And you want to take care if x and x+eps use different values n, that $e^x$ and $e^{x+eps}$ fit together nicely; you wouldn't want a sitation where $e^{x+eps} \< e^x$ with eps \> 0.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Finding the two node-disjoint paths, minimizing the sum of their lengths
Given an undirected graph and a start and end node, I am trying to find two node-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, end at the end node, and no node (other than the start or end node) can be visited by both nodes. Is there an efficient algorithm to solve this problem?

I know that if I just need the shortest path, I can use Dijkstra's algorithm, but finding one path with Dijkstra's algorithm and then searching for another is sometimes not optimal at all, since nodes in the first path may have blocked a possible and way shorter path.

I have tried implementing the `node_disjoint_path` algorithm from the Python `networkx` package. But I must say that the result is very varying from okay to really bad. My network is not that big. "Only" 6000 nodes and 7500 edges.

# Answer
This can be solved by a small modification to Suurballe's algorithm, with $O(|E| + |V| \log |V|)$ running time. You might also be interested in Computing the k shortest edge-disjoint paths on a weighted graph.

Suurballe's algorithm works with directed graphs. You can convert an undirected graph to a directed graph by replacing each undirected edge $(u,v)$ with two directed edges $u \to v$, $v \to u$.
> 2 votes

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


# Question
Title: Can you substitute functions in Big-$\Theta$ notation?
Say we have some function $f(n)=\Theta(\log n)$ and another function $g(n)=\Theta(n+\log n)$. Is it valid to substitute $f(n)$ for $\log n$, giving us $g(n) = \Theta(n + f(n))$? This seems obvious to me but I'm not sure if there is a weird edge case where this isn't true.

# Answer
> 0 votes
Bit $\Theta$ gives big possibilities. Let's write down what we have, assuming appropriate conditions on constants and infinity neighbourhood: $$f(n)=\Theta(\log n) \Leftrightarrow a\_1 \log n \leqslant f \leqslant a\_2 \log n$$ $$g(n)=\Theta(n+\log n) \Leftrightarrow b\_1 (n+\log n) \leqslant g \leqslant b\_2 (n+\log n)$$ Now we combine from above inequalities $$ c\_1 (n+f) \leqslant b\_1n+\frac{b\_1}{a\_2}f\leqslant g \leqslant b\_2 n + \frac{b\_2}{a\_1}f \leqslant c\_2 (n+f) $$ which gives $g(n) = \Theta(n + f(n))$.

---
Tags: runtime-analysis
---


# Question
Title: What is the best way to merge cycles to minimise total weight?
Suppose I have a vertex-disjoint set $S$ of simple cycles in a weighted undirected graph. So no vertex $v$ is contained in more than one cycle. A cycle $c$ is a closed path with no repeated vertices: $c=(v\_1, v\_2, \ldots, v\_n)$, where $v\_n=v\_1$. Each edge $e=(v\_i,v\_j)$ has a positive weight $w(e)$. The weight of a cycle $w(c)$ is the sum of its edge weights: $w(c) = w(v\_1,v\_2)+\ldots+w(v\_{n-1},v\_n)$. The total weight of $S$ is the sum of all its cycle weights.

Naively I want to merge all the cycles in $S$ into a single cycle with the smallest total weight. I also want to somehow preserve most of the edges of the original cycles. I am not looking for an optimal solution, just an efficient heuristic.

I can merge two cycles by removing an edge from each one and connecting them up with new edges. For example, suppose I have two cycles $c=(v\_1, v\_2, \ldots, v\_n)$ and $c'=(v'\_1, v'\_2, \ldots, v'\_k)$. I can remove edges $(v\_a,v\_{a+1}), (v'\_b,v'\_{b+1})$ and add edges $(v\_a,v'\_b), (v\_{a+1},v'\_{b+1})$ to form a single cycle $(v\_1, \ldots, v\_a, v'\_b, \ldots, v'\_{b+1}, v\_{a+1}, \ldots, v\_1)$. This move is somewhat similar to 2opt and there are O(nk) such moves possible. I can continue merging cycles in this fashion until I reach a single cycle. Essentially I am building a minimal spanning tree that spans cycles.

Although the above procedure works in giving me a single cycle, it rarely gives me a cycle with a small weight. I can enhance this procedure by merging 3 cycles at once in a move similar to 3opt, but then I have to perform significantly more computations.

So here are my questions:

* Is this a well known problem?
* Can I improve the efficiency of this approach?
* Is there an efficient heuristic that produces a cycle of small weight?

Attached are some examples. In the left figure a 3opt move is optimal, while in the right figure a sequence of 2opt moves is best.

Here is a numeric example that I constructed. Using the optimal merging method we get a weight of 43, while the greedy algorithm gives us a worse solution of weight 50. Even if we join the bottom cycle by removing the new edge we added (weight 10) we would still get a worse solution (I didn't draw it for clarity).

# Answer
This is NOT an answer. This post is just to construct a concrete numeric example out of the left diagram in the picture in the question.

(This answer, too long to fit as a comment, was requested by a user who wanted to see a concrete numeric example which his greedy algorithm may fail. It was written about the same time when OP added a numeric example that is exactly the same except a slightly different weight assignment.)

Let $G$ be the complete undirected graph on 12 vertices $A\_1, A\_2, A\_3, A\_4, B\_1, B\_2, B\_3, B\_4, C\_1, C\_2, C\_3, C\_4$.

Let $S$ be the set of the following three simple circles.

* the circle $c\_A$: $A\_1, A\_2, A\_3, A\_4, A\_1$.
* the circle $c\_B$: $B\_1, B\_2, B\_3, B\_4, B\_1$.
* the circle $c\_C$: $C\_1, C\_2, C\_3, C\_4, C\_1$.

All edges in the three circles weigh 1. The edges $A\_3B\_2, A\_4B\_1, B\_3C\_2, B\_1C\_4, C\_3A\_2$ and $C\_4A\_3$ weigh 2. \- All other edges weigh 16.

We are allowed to merge two cycles by removing an edge from each cycle and connecting them up with two new edges, repeatedly until we reach a single cycle. The goal is to reach a cycle with the smallest total weight.

**A description of an optimal solution for $S$.**

1. Remove edge $A\_2A\_3$ and $B\_2B\_3$. Add edge $A\_3B\_2$ and $A\_2B\_3$.
2. Remove edge $A\_2B\_3$ and $C\_2C\_3$. Add edge $B\_3C\_2$ and $C\_3A\_2$.

We end up with the simple cycle $A\_1, A\_4, A\_3, B\_2, B\_1, B\_4, B\_3, C\_2, C\_1, C\_4, C\_3, A\_2, A\_1$, which has weight $3\* 2+ 9\*1 = 15$.

**A description of greedy algorithm on $S$ that considers all pairs of two existing cycles at a time.**

1. Since the three cycles are symmetric, WLOG, let us merge cycle $C\_a$ and cycle $C\_b$. To avoid adding an edge whose weight is 16, we have only one choice. Remove edge $A\_3A\_4$ and $B\_1B\_2$. Add edge $A\_3B\_2$ and $A\_2B\_3$. The resulting circle, named $c\_{AB}$, is $A\_1, A\_2, A\_3, B\_2, B\_3, B\_4, B\_1, A\_4, A\_1$.
2. Now it is time to merge $c\_C$ and $c\_{AB}$. To avoid adding an edge whose weight is 16, we have only two choices. We can either remove $B\_3B\_4$ and $C\_1C\_2$ and add $B\_3C\_2$ and $B\_4C\_1$, resulting with cycle $A\_1, A\_2, A\_3, B\_2, B\_3, C\_2, C\_3, C\_4, C\_1, B\_4, B\_1, A\_4, A\_1$, whose weight is $4 * 2 + 8 * 1 = 16$. Or we can remove $C\_3C\_4$ and $A\_1A\_2$ and add $C\_3A\_2$ and $C\_4A\_1$ cycle, resulting with cycle $C\_1, C\_2, C\_3, A\_2, A\_3, B\_2, B\_3, B\_4, B\_1, A\_4, A\_1, C\_4, C\_1$, with the same weight 16.

**Conclusion: A simple greedy algorithm does not guarantee the desired smallest weight.**

I have also constructed a planar graph out of that left diagram. However, it is much more messier to describe the construction and to show the algorithms and their results.

Furthemore, it is not hard to construct an example where the greedy algorithm that considers all triples of existing cycles at a time will not reach the smallest weight. I believe, with a bit of more work, we can show **a greedy algorithm that considers all combinations of a fix number of existing cycles does not guarantee the desired smallest weight.**

It is quite possible this problem does not have a polynomial solution that always yields the smallest weight. In fact, it looks like this concern is implied by the OP since the question asks for "an efficient heuristic that produces a cycle of small weight".
> 2 votes

# Answer
If you realize that you actually looking for algorithms that generate tours from cycles, then the problem amounts guaranteeing that the generated tour will contain many of the cycles' edges.

I suggest to delete from the original graph all edges that are not cycle edges but connect a pair of vertices of the same cycle, i.e. delete every cycle's diagonals, and then run any of algorithm that calculates near optimal solutions of the TSP on the resulting graph; Christofides' algorithm, Held & Karp, double tree, tour expansion, etc. come to mind for heuristics.
> 2 votes

---
Tags: graphs, minimum-spanning-tree, hamiltonian-circuit
---


# Question
Title: How to give the nearest text that the user has written
In my database I have 1500 food dishes, not all are single words, there are compound words like "cheese with dried fruit and nuts". And I have them in 5 languages (de, en, fr, es, it).

My question is how could I do it so that given a text it gives me a prediction of the 5 dishes that are closest to that text.

For example, if the user search for "roquefort with almonds" as closest would return "cheese with dried fruit and nuts" and other 4 results with other dishes.

I have thought about using the Word2Vec model but I am not sure how to start (I am quite a novice) if I should do transfer learning, or how.

Could someone guide me on how to approach the solution to this problem?

# Answer
> 1 votes
This is not an easy task. There is no simple answer; you could do something crude that might give mediocre results, or you could put a lot of effort into it; and it's not obvious to me what will work best.

One possible simple approach is to map each word (except for a few stopwords) to an encoding, using a standard word embedding (e.g., word2vec), average the vectors of the words to get an embedding of the phrase, and then compare two phrases using the L2 distance of their embeddings. I don't know how well this will work; you could try it and see.

There will probably be more sophisticated approaches, e.g., training a language-based model to compare two phrases for similarity, perhaps building on an existing model (such as BERT) and fine-tuning it. I anticipate this will require many labelled samples and a non-trivial amount of research and experimentation, so it's not a minor project to take on.

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


# Question
Title: Regarding a theorem that says a language that is Turing-Recognizable iff some enumerator enumerates it
I am reading the proof of Theorem 3.21 in Sipser's textbook.

> Theorem 3.21 A language is a Turing Recognizable iff some enumerator enumerates it.

First direction (\<==). Given an Enumerator E that enumerates language B, then we want to construct a TM M s. t. M that recognize language B. In order to do that, we do the following:

M="On input string x

1. Run E and compare each printed string with x
2. If x ever appears in the output of E, accept."

Given the following fact:

> A TM M accepts input w if a sequence of configurations $C\_1, C\_2, ..., C\_k$ exists s. t. $C\_1$ is the starting configuration, $C\_2$ to $C\_{k-1}$ is the process configuration and $C\_k$ is the accepting configuration.

My question: It is not clear how E accepts? e.g. What it does from my point of view is: It runs E without any input, if ever E printed out an arbitrary string, let's call it r, then if r==x, then we accept. I thought that we should do some processing like with given input x, then we should do some computation (moving from configuration to another) until we get to some arbitrary string that should be the output of the accepting state.

Note that I read all related answers to this question, but it didn't cover my question. For example: this and this.

# Answer
The Turing machine M is running the Turing machine E as its subroutine. In the other words, you can think of E's printer tape as another tape for Turing machine M. Although we don't know what is going on E, E's computation is part of (inside) M's computation. And of course, as nir shahr said in the comment, comparing is part of M's computation too.

I drew something maybe it can help to have some intuition.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: How to use Runge–Kutta methods in a second order ODE
Consider a second order equation $F=ma=m\ddot{x}$.

In the language of Euler's method

1. $\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$
2. $\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$
3. $x(t+dt)=x(t)+\dot x(t)dt$

Basically, the entire iteration was the second order force equation $F(t,x(t),\dot x(t))$.

However, here one wanted to apply Runge–Kutta method(standard "RK4", not Runge–Kutta–Nyström or else) to solve that equation. For notation simplicity, let $v\sim \dot x$, $a\sim \ddot x$(velocity and acceleration).

From $x(t),v(t),a(t)$:

$ka1=F(t,x(t),\dot x(t))$; $kv1=v(t)+a(t)\frac{dt}{2}$; $kx1=x(t)+v(t)\frac{dt}{2}$;

$ka2=F(t+\frac{dt}{2},kx1, kv1)$; $kv2=kv1+ka1\cdot \frac{dt}{2}$; $kx2=kx1+kv1\cdot \frac{dt}{2}$;

$ka3=F(t+\frac{dt}{2},kx2, kv2)$; $kv3=kv2+ka2\cdot dt$; $kx3=kx2+kv2\cdot dt$; and finally

$ka4=F(t+dt,kx3, kv3)$;

The final acceleration was collected to be

**Iteration Update Method 01**

$\ddot x(t+dt)=(ka1+ka2\cdot 2+ka3\cdot 2+ka4)/6$; where

$\dot x(t+dt)=\dot x(t)+\ddot x(t)dt$;

$x(t+dt)=x(t)+\dot x(t)dt$

with such loop the iteration was able to run in RK4 method and things worked very nicely and coincided with the analytical calculation for an example which Euler method was known to fail.(Tested)

However, my question arise from a mistake where it made the code fail to work. It went like this:

In addition to the $\ddot x(t+dt)$ condition, one further to average the speed directly,

**Iteration Update Method 02**

$\ddot x(t+dt)=(ka1+ka2\cdot 2+ka3\cdot 2+ka4)/6$;

$\dot x(t+dt)=(\dot x(t)+kv1\cdot 2+kv2\cdot 2+kv3)/6$; and

$x(t+dt)=x(t)+\dot x(t)dt$;

Notice that the new update method attempted to use the $\dot x(t)$ to take care of the "overflow". Intuitively, not only the acceleration $\ddot x$ was "RK4"-ed, but also, the velocity $\dot x$ was "RK4"-ed as well. However, thought still able to produce a sensible graph, the **Iteration Update Method 02** was proven to have failed after the analysis.

Question 1: Why **Iteration Update Method 01** worked? Even though it approximated $\frac{d^2y(t)}{dt}=f(t,y(t),\dot y(t))$ instead of $\frac{d y(t)}{dt}=f(t,y(t))$?

Question 2: Why **Iteration Update Method 02** failed? Shouldn't it work better since it averaged more stuff?

# Answer
I think there is a mistake in your post: the first equation should be $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$ (and not $\ddot{x}(t + dt)$).

Also, in the computation of $kv\_i$ and $kx\_i$, it should be $kv\_i = v(t) + ka\_{i-1}\Delta t$ and $kx\_i = x(t) + kv\_i\Delta t$ (where $\Delta t = dt$ or $\frac{dt}{2}$). $kv\_i$ does not use $kv\_{i-1}$ (except in the computation of $ka\_{i-1}$), and same thing for $kx\_i$.

Question 1: in the differential equation $\ddot{x}(t) = F(t, \dot{x}(t), x(t))$, if you consider the vector $Y(t) = \begin{pmatrix}x(t)\\\dot{x}(t)\end{pmatrix}$, then you have $\dot{Y}(t) = \begin{pmatrix}\dot{x}(t)\\\ddot{x}(t)\end{pmatrix} = \begin{pmatrix}\dot{x}(t)\\F(t, \dot{x}(t), x(t))\end{pmatrix} = \tilde{F}(t, Y(t)) $. That explains why the method works (since the formulas will be the same as with a first order differential equation). Actually, the approximation should be better with the corrections I proposed.

Question 2: With your formulas, a bit of simplification gets you $v(t+dt) = v(t) + \frac{dt}{6}\left(5a(t) + 2ka\_1 + 2ka\_2\right)$ which is not coherent.

Even with the corrections I proposed, it is incorrect. My guess is that you should compute $x(t+dt)$ and $\dot{x}(t+dt)$ as a whole (as in the vector $Y(t)$) instead of trying to compute them one after the other. The system $\left\\{\begin{array}{rcl}\dot{x}(t+dt) &= &\dot{x}(t) + \ddot{x}(t)dt\\ x(t+dt) &=&x(t) + \dot{x}(t)dt\end{array}\right.$ can be seen as $Y(t+dt) = Y(t) + \dot{Y}(t)dt$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, numerical-algorithms, mathematical-analysis, iteration
---


# Question
Title: Solving a recurrence of uneven subproblems without Akra-Bazzi
I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$

I observed it is possible to approach this relation with the method of Akra-Bazzi, however this method was not taught in class. Akra-Bazzi gives the result of $\theta(n^p)$ where $p$ is the unique solution to $$\frac{1}{3^p}+\frac{1}{6^p}=1$$

However, since this was not taught, I would like to ask if there's a different method to tackle this exercise, or a way to find its asymptotics more constructively.

# Answer
> 1 votes
Let us try to prove that $T(n) \geq cn^p$ by induction. For small enough $c\>0$, this would hold for the base case. For the inductive step, $$ T(n) = T(n/3) + T(n/6) + 1 \geq c(n/3)^p + c(n/6)^p + 1 \> cn^p. $$ Unfortunately, the same approach doesn't work directly for the upper bound. Instead, we will prove that $T(n) \leq Cn^p - 1$ by induction. For large enough $C\>0$, this would hold for the base case. For the inductive step, $$ T(n) = T(n/3) + T(n/6) + 1 \leq C(n/3)^p + C(n/6)^p - 1 = Cn^p - 1. $$

---

The observant reader would notice that this is a mock proof. Indeed, it is really a mock recurrence, because $n/3$ and $n/6$ in general are not integral. The Akra–Bazzi theorem shows that this doesn't really matter. Instead of finding tricks for solving such recurrence every single time, Akra and Bazzi proved a general theorem which applies in *all* cases. We should use it instead of spending our time on reproving special cases of it.

# Answer
> 3 votes
You could use "guess-and-check": guess the solution to the recurrence, then use induction to prove that it is a solution, i.e., to prove that your solution satisfies the recurrence.

In your case, since you know Akra-Bazzi, your "guess" can actually be obtained through Akra-Bazzi, but you don't have to tell anyone that's how you obtained your guess.

# Answer
> 0 votes
You can find asymptotic of $T(n)$ With finding lower bound and upper bound. So

$T(n)\geq 2T(\frac{n}{6})+1$ that according to master theorem, or recursion tree $T(n)=\Omega(n^{\log\_62})=T(n)=\Omega(n^{\frac{1}{1+\log 3}})$

and

$T(n)\leq 2T(\frac{n}{3})+1$. According to master theorem, or recursion tree $T(n)=O(n^{\log\_32})=T(n)=O(n^{\frac{1}{log 3}})$.

---
Tags: asymptotics, recurrence-relation
---