# Question
Title: number of connected induced subgraph in a tree
Let G be a tree-structured graph. A connected induced subgraph is an induced subgraph from G that is connected. (Since the original graph is a tree, any connected induced subgraph is also a tree)

My question: Given a tree G of n vertices, how many connected induced subgraph can be obtained from G?

An example: n = 4, G looks like 1---2---3---4 (I name those four vertices by 1, 2, 3, 4). Then we have 10 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4} where I represent a connected induced subgraph by a set of their vertices.

Another example: n = 4, G looks like 1---2---3, 1---2---4 (node 2 directly connects 3 and 4. forgive my poor way of drawing it in text) In this case, we have 11 connected induced subgraph. Namely, they are {1}, {2}, {3}, {4}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,2,4}, {2,3,4}, {1,2,3,4}.

From those two little examples we can see that the actual number depends on the exact structure of the tree, so, I am hoping you can help me further determine what is the factor that influences the result (I guess the maximal degree?).

Thank you!

# Answer
> 2 votes
Let $T$ be a tree rooted at $r$. Let the children of $r$ be $r\_1,\ldots,r\_\ell$, and let the corresponding subtrees be $T\_1,\ldots,T\_\ell$.

Consider a connected induced subgraph of $T$. There are two cases:

* The subgraph doesn't contain $r$. In this case, the subgraph is a connected induced subgraph of some $T\_i$.
* The subgraph contains $r$. In this case, for each $i$, either the subgraph contains no vertices of $T\_i$, or its intersection with $T\_i$ is a connected induced subgraph of $T\_i$ containing $r\_i$.

Let us denote the number of subgraphs of the first type by $A(T)$, and those of the second type by $B(T)$. You are interested in $A(T) + B(T)$. The description above translates to the following recurrences: $$ \begin{align} A(T) &= \sum\_{i=1}^\ell (A(T\_i) + B(T\_i)) \\ B(T) &= \prod\_{i=1}^\ell (1 + B(T\_i)) \end{align} $$ Using this, you can calculate the number of connected induced subgraphs of a tree in linear time (ignoring the cost of arithmetic).

---
Tags: graphs
---


# Question
Title: Consequences of the Time Hierarchy Theorem
The form of the Time Hierarchy Theorem that I have is this:

> If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$.

We want the consequences of this to be that $\text{P} \neq \text{EXP}$ and $\text{EXP} \neq \text{2-EXP}$ etc. But I can't see how this follows.

I have $\text{P}$ defined as $\text{P} := \bigcup\_{c=0}^\infty \text{DTIME}(n^c) $ and $\text{EXP}$ as $\text{EXP} := \bigcup\_{c=0}^\infty \text{DTIME}(2^{n^c}) $.

I know that $\text{DTIME}(n^c) \subsetneq \text{DTIME}((2n+1)^c)=\text{DTIME}(2^c(n+0.5)^c)$. But $c$ is a constant, so surely the RHS is just another polynomial class.

Additionally, even if I had, say, $\text{DTIME}(n^c) \subsetneq \text{DTIME}(2^{n^c})$, how would I know that the limit of infinitely many of these classes still preserves the "not equal to" relation? (For instance, $\\{n\\} \subsetneq \\{n, n+1\\}$ but $\bigcup\_n \\{n\\} = \bigcup\_n \\{n, n+1\\} = \mathbb{N}$.)

# Answer
Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$.

(Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f\_C(n) = Cn^{\log n}$ and sum over all integer $C\>0$.)
> 2 votes

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


# Question
Title: Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken
Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot.

Given that we do not know the starting position of a player on this grid.

Given that the player can move 1 step in any cardinal direction every turn.

Given that the player cannot visit tiles he has already visited.

Given that we are told every turn in which direction the player has moved.

What would be a computationally efficient algorithm to pinpoint the player's location in the least amount of turns?

One way that comes to mind that would give me good results but would probably be computationally intensive is to try to apply the player's path to every possible starting position. If we can traverse the path without hitting an island or going off the map, then the end tile is a valid possible position for the player. At first we would have a lot of possible positions for the player but eventually, after several turns, we'd end up with only one possible position.

I don't very much like that approach as it seems computationally heavy.

Instead, I've implemented a simple solution using a bounding box. At the beginning of the game, the player could be anywhere. But as soon as he moves, we can narrow the bounding box. For instance, if the player's first move is north, we now know that he can't be in the bottom row of the map. All that is needed is to keep track of the top left and bottom right coordinates of that box and update them every turn according to the enemy's movement until the box is eventually narrowed down to the player position.

I like this solution because it is simple and computationally light. The problem is that it doesn't take into account the islands and the players' previously visited cells. Therefore, only when the bounding box hits the grids' limits can we narrow it down. If the player starts in the middle of the map and tends to stay there, it can take a long time before narrowing down his position.

Is there a way to refine my solution (bounding box) in a way that would at least account for the islands and at best for the player's visited tiles as well? If not, what other algorithm could I use?

# Answer
Don't be so quick to reject your approach! Your approach is a great solution. On a $15\times 15$ grid, you'll only have to try 225 different options. Checking each option is very fast, so it should be extremely fast to try all 225 different solutions -- I'd imagine it will finish in microseconds.

As Knuth supposedly said once, "premature optimization is the root of all evil". My advice: Try that solution, implement, and measure its performance, before you even consider anything else.
> 1 votes

---
Tags: algorithms, graphs, square-grid
---


title: Raptor algorithm: find next best paths

text:
# Question
Title: Raptor algorithm: find next best paths
I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to destination)? I have few ideas about it:

1. Find best path, then exclude trips (from path) from transportation network and rerun algorithm. (It's not clear for me how to choose new departure time).
2. Find best path **P**, then rerun algorithm with adjusted departure time so it's not possible to use **P**. (I think some good paths may be missed here)

What is the way to find next best paths?

# Answer
There are standard algorithms for finding the $k$ shortest paths in a graph: you provide $k$, and it returns the shortest path, second-shortest path, ..., up to the $k$th shortest path. See https://en.wikipedia.org/wiki/K\_shortest\_path\_routing. I'd suggest that as a natural place to start.
> 2 votes

---
Tags: algorithms, shortest-path, routing
---


# Question
Title: How to shift a matrix by x rows and y columns in the most efficient way?
My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner.

x and y could be negative or positive. Negative would mean up/left and positive would mean down/right.

My current solution is something like this:

```
def rotate_columns(col, y):
    new_col_position = col+y if y < 0 else (col+n-y)
    return new_col_position
def rotate_rows(row, x):
    new_row_position = row+x if x < 0 else (row+m-x)
    return new_row_position

def shift(x,y):
    N = M.copy()
    for col in range(n):
new_col_position = rotate_columns(col)
        for row in range(m):
            N[row][new_col_position] = M[row][col]
    for row in range(m):
        new_row_position = rotate_rows(row)
        for col in range(n):
            N[new_row_position][col] = M[row][col]

```

An example: Say, a given matrix is:

```
1 2 3
4 5 6
7 8 9

```

with x = 2, y = 1, it would be:

```
6 4 5
9 7 8
3 1 2

```

Is there a better way to solve this? By better, I mean better time complexity.

# Answer
> 2 votes
I could think of a time-efficient solution which is not good in terms of memory.

We will carry out duplication of the given array.

For eg.

Initial Array:

We can have 4 duplicate copies of the same array, each attached to form a huge square.

Big Array looks like:

Within this Big Array, let me call my result as the Result Array.

Initially, when we have no rotation involved, the result array looks like:

The Blue colored box represents the result array.

The top\_left\_index of the result array = (0, 0). \[Image above\]

After that, suppose we rotate 1 row, the blue colored box shifts down as follows:

The top\_left\_index of the result array = (**1**, 0). \[Image above\]

After that, suppose we rotate 1 column, the blue colored box shifts right as follows:

The top\_left\_index of the result array becomes = (**1**, **1**). \[Image above\]

After that, suppose we rotate 1 row, the blue colored box shifts down as follows:

The top\_left\_index of the result array becomes = (**2**, **1**). \[Image above\]

After that, suppose we rotate 2 cols, the blue colored box shifts right as follows:

The top\_left\_index of the result array becomes = (**2**, **3**). \[Image above\]

This is how the entire logic works.

We just need to store the top left index of the blue box. Whenever asked for the result, we can display the elements of the blue-colored box.

So, the entire problem boils down to calculating the top left index of the blue box.

**Time Complexity of changing the index**: O(1)

**Space complexity**: O(n^2)

However, there exist corner cases that need to be handled. Once such corner case is as below:

Handling this corner case is not difficult. In case we feel that the resultant array's bounds are overflowing the boundary of the Big array, we need to reduce the value of our top\_left\_index such that the entire square fits in the array. For eg.,

In the above image, the top\_left\_index (2,4) overflows the bounds of Big Array.

We simply reduce the overflowing index by the respective dimension of our original array and make it:

(2, 4 - 3 ) = (2, 1).

Now, things look beautiful again.

---
Tags: algorithms, time-complexity, arrays, matrix
---


# Question
Title: Finding pairs of vertices which would disconnect a graph
An assignment question asks,

> Given a connected, undirected graph $G$, describe an algorithm which can determine if the removal of *any pair* of vertices would cause $G$ to become disconnected.

There is an obvious brute force solution, which is to just generate all pairs of vertices, produce new graphs with those vertices removed, and then test if that graph is connected using something like a BFS, running in $O(|V|^3)$ time.

However, I feel like this is not the intent of the question. We learned about an algorithm to find the articulation points of a graph, and it seems like something like this should be possible to determine if the removal of any pair of vertices would disconnect the graph, but I am not sure how it would be applicable.

# Answer
> 1 votes
Assume that $G=(V,E)$ does contain any articulation point (otherwise the answer is easy).

One simple approach that requires $O(|V| \cdot |E|)$ time is that of computing the articulation points of $G-v$ for each $v \in V$.

If you find any articulation point $u$ then removing the two of vertices $\\{u,v\\}$ disconnects the graph.

In practice this amounts to running the depth first search needed to compute the articulation points of $G-v$ on $G$, while ignoring the edges to $v$.

---
Tags: algorithms, graphs
---


# Question
Title: Does hiding variables work in terms of blocks or line-by-line?
Let's assume I have the following code:

```
declaration of a
declaration of b
..a..b
{
  ..a..b
  declaration of a
  declaration of b
  ..a
}

```

In this code {} represent the inner block. declaration represents binding occurrence, and .. represent applied occurrence.

So my question is that is it legal to use the outer scope variables inside an inner scope and then redeclare them ? If so how does the hiding of outer variables system work (Does it start to work when it sees a redeclaration)? Thanks in advance.

# Answer
It depends on the programming language. It's up to each language to specify whether this is legal or not, and what it means.

In many languages this would be legal. It is called variable shadowing.
> 2 votes

# Answer
It is in many languages legal to create a variable in an inner scope with the same name as a variable in an outer scope. The problem is that this may have been done by accident, and you never wanted to create a second variable, or that you use the inner variable when you wanted to use the outer one. For that reason, many compilers will issue a warning in that situation.

On the other hand, in Swift “if let x = x { ...}” is idiomatic. (It checks that the outer x is not nil, and makes its value accessible through the inner x).
> 2 votes

---
Tags: programming-languages, variable-binding
---


# Question
Title: Can an infinite regular language be decomposed in this way?
If $A$ is an infinite regular language, can there exist a finite regular language $B$ such that $A = BB^\*$?

# Answer
The first step is to clarify what is being asked: do you mean can **every** infinite regular language be decomposed in this way, or is it **possible that some** infinite regular language can be decomposed in this way? Your question does not make this clear.

* For the first version of the question, try considering the following language: $b \cup a^\*$. Can this be decomposed in this way? How could you prove it?
* For the second version of the question, try considering the following language: $a^\*$. Can this be decomposed in this way? How could you prove it?
> 1 votes

---
Tags: formal-languages, regular-languages, kleene-star
---


# Question
Title: $k$-coloring in BPP, implies $k$-coloring in ZPP
Consider the next problem:

$k$**-COL**: Given a graph $G=(V,E)$, does it have a valid $k$-coloring?

I need to prove that if $k$**-COL** is in **BPP**, then it is also in **ZPP**. In other words, show that if there is a probabilistic polytime algorithm that decides whether a graph has a valid $k$-coloring or not with bounded error, then there is also a probabilistic polytime algorithm that does that with zero error.

---

## My attempt

I've managed to prove it assuming that we are allowed to call an oracle that solves the above problem in polynomial time (see below). But is there a way to show this without assuming $k$**-COL** $\in$ **P**?

Let $\mathcal{A}$ be a polynomial time machine with access to an oracle for $k$**-COL**.

Let $G$ be a graph and let $M$ be the **BPP** NTM that makes $k$**-COL** be in **BPP**. Let's define the following NTM $M'$:

If $G \in$ $k$**-COL**, execute $M$ on $G$.

1. If $M(G) = 1$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=1$.
2. If $M(G) = 0$, output $?$.

If $G \notin$ $k$**-COL**, execute $M$ on $G$.

1. If $M(G) = 1$, output $?$.
2. If $M(G) = 0$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=0$.

## Definitions (for reference)

We define the class of languages **Bounded-error Probabilistic Polynomial-time (BPP)** as all $L \subseteq \\{ 0,1\\}^\*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t\_M=\mathcal{O}(n^c)$ and that for all $x \in \\{ 0,1 \\}^\*$:

1. $Pr\[M(x) \in \\{0,1\\}\] = 1$,
2. if $x \in L$, then $Pr\[M(x) = 1\] \geq 3/4$,
3. if $x \notin L$, then $Pr\[M(x) = 1\] \leq 1/4$.

We define the class of languages **Zero-error Probabilistic Polynomial-time (ZPP)** as all $L \subseteq \\{ 0,1\\}^\*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t\_M=\mathcal{O}(n^c)$ and that for all $x \in \\{ 0,1 \\}^\*$:

1. $Pr\[M(x) \in \\{0,1,\text{?}\\}\] = 1$ and $Pr\[M(x) = \text{?}\] \leq 1/2$,
2. if $x \in L$, then $Pr\[M(x) = 0\] = 0$,
3. if $x \notin L$, then $Pr\[M(x) = 1\] = 0$.

# Answer
This statement is to my knowledge unknown. If this is an exercise, then it is likely an error: did they mean $RP$ instead of $ZPP$?

Since $k$-coloring is NP-complete, what you are asked to show is:

> If $NP \subseteq BPP$, then $NP = ZPP$.

First, let's review what is known: the basic inclusions are the following: \begin{align\*} P \subseteq ZPP \subseteq RP &\subseteq NP \\ P \subseteq ZPP \subseteq coRP &\subseteq coNP \\ RP &\subseteq BPP \\ coRP &\subseteq BPP. \end{align\*}

That is, $P$ is contained in $ZPP = RP \cap coRP$, which is contained in $BPP$. Moreover, $RP$ is contained in $NP$ and $coRP$ is contained in $coNP$. But we don't know how $NP$ and $coNP$ relate to $BPP$ (it is conjectured that $P = ZPP = BPP$, which implies that $NP$ and $coNP$ contain $BPP$).

Now, what happens if (as in your exercise) $NP \subseteq BPP$? It follows (and is a common exercise to show) that $$ NP = RP. $$

(see e.g. here). That means that $$ coRP = coNP \\ ZPP = NP \cap coNP \\ $$ So basically in this case, we have $P$, which contains $NP$ and $coNP$, and those are both contained in $BPP$ (which also equals the polynomial hierarchy $PH$).

But there is no reason to believe that this implies that $NP = coNP$, which is what you would need to then show that your $NP$-complete language, $k$-col, is in $ZPP = NP \cap coNP$. In particular, we can imagine that $BPP$ is equal to the second level of the polynomial hierarchy (you don't need to be familiar with this, but it's just some level that contains both $NP$ and $coNP$). That would imply that $NP$ is contained in $BPP$, but it doesn't mean that $NP$ and $coNP$ are equal.

**TL;DR** The statement you are trying to show appears to be unknown.
> 3 votes

---
Tags: complexity-theory, probabilistic-algorithms
---


# Question
Title: What is the worst-case big-O time complexity for this code?
I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so I thought I'd post here.

```
def functionC(L):
    for i in range(len(L)):
        if L[i] == i:
            v = L.pop(i)
            L.insert(i, 2*v)
    return

```

I supplied the following answer:

> The above function is O(n) because the for-loop grows with the size of L. The pop and insert functions are both constant time.

the word time is crossed out, but there is no other explanation as to why I received 6/10 for the question. What did I get wrong in this and why?

Here is an image of the question and my answer to prove the quiz has already been graded and handed back.

# Answer
> 1 votes
As pointed out by Yuval Filmus, you should ask that question to your professor.

I'll just point out some possible issues. I will also assume that $L$ is a python list.

* $n$ is never defined, so it is unclear what $O(n)$ even means.
* The wording "the for loop grows with the size of L" is a bit odd. A for loop does not grow. Its number of iterations is equal to the size (or better, length) of L.
* From here, it seems that lists in python are implemented using arrays\*. The $L.\mbox{pop}(i)$ operation requires $\Theta( 1 + \mbox{len}(L)-i )$ time\** and, in your case, you can have $\Theta(\mbox{len}(L))$ iterations for which $\mbox{len}(L)-i = \Theta(\mbox{len}(L))$. The same holds for $L.\mbox{insert}(i, \cdot)$. The overall time complexity is then $O((\mbox{len}(L))^2)$. Consider, for example, the list $L = \langle 0, 1, \dots, \mbox{len}(L) \rangle$.

\*These arrays are dynamically resized when elements are appended and not enough capacity is available. This only guarantees a constant *amortized* time per operation, so even a single operation on a list $L$ that you got as a parameter could cost up to $O(\mbox{len}(L))$ worst-case time. This is not a concern in your code since the initial capacity of $L$ is never exceeded.

\**Some sources report that $L\mbox{.pop}(i)$ requires $O(i)$ time. The above argument still holds in this case.

# Answer
> 2 votes
You need to be aware that the complexity of `insert` and `pop` can be $O(n)$ in python ($n = \text{length($L$)}$). Hence, the time complexity can be $O(n^2)$.

---
Tags: algorithms, python, big-o-notation
---


# Question
Title: Explain better this new inventory for Word Sense Disambiguation
My question is about CSI (Coarse Sense Inventory), described in the paper CSI A Coarse Sense Inventory for 85% Word Sense Disambiguation (C Lacerra, M Bevilacqua, T Pasini, R Navigli).

Before the question, let me quickly describe the new CSI using phrases taken from the above paper.

CSI is a "a resource that avoids sense distinctions that are too **ﬁne-grained** for WSD, while maintaining a granularity that is still meaningful for the task".

CSI is "obtained by linking WordNet concepts to a new set of 45 **labels**".

The comparison between WordNet and CSI is given in table 7:

Question: What is a **semantically-empty** prediction? (The paper doesn't explain well what is a semantically-empty label)

# Answer
The paper says:

> "we also added the semantically-empty label named GENERAL to our inventory to cover the 135 categories that could not be included in any cluster."

I suggest you read that as though it had said

> we also added the label named GENERAL to our inventory to cover the 135 categories that could not be included in any cluster. This label is not associated with one specific semantic meaning; it is a catch-all for the categories that could not be mapped to any of the other labels.
> 1 votes

---
Tags: natural-language-processing
---


# Question
Title: Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same
Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph $G = (V, E)$ has the following property: for all $v \in V$ the weight of all outgoing edges $vu$ is the same.

How can one modify Dijkstra's algorithm so that *exactly one relaxation* is done for every vertex $v \in V$? (i. e. decreasing of current minimal path length $d\_{v}$ is done exactly once for every $v$).

# Answer
In each iteration, instead of choosing the node $u$ with smallest $\mathtt{dist}\[u\]$ in the standard Dijkstra's algorithm, we choose the node $u$ with smallest $\mathtt{dist}\[u\]+w(u)$, where $w(u)$ is the weight of outgoing edges from $u$.

The proof of the correctness of this modified algorithm is almost the same as the one of the standard Dijkstra's algorithm. As shown in the proof for the standard Dijkstra's algorithm, it also holds that for each visited node $v$, $\mathtt{dist}\[v\]$ is the shortest distance from source to $v$.

Now consider a node $v$. Let $P$ be a shortest path from source to $v$. Suppose $\mathtt{dist}\[v\]$ is first updated through $u$ (i.e., it is updated to $\mathtt{dist}\[u\]+w(u)$), and when $\mathtt{dist}\[v\]$ is first updated, $x$ is the first unvisited node on $P$, then $\mathtt{dist}\[x\]+w(x)\le w(P)\le \mathtt{dist}\[u\]+w(u)$, where $w(P)$ is the shortest distance from source to $v$. Also note at this time $u$ is chosen instead of $x$, we have $\mathtt{dist}\[u\]+w(u)\le \mathtt{dist}\[x\]+w(x)$, hence $\mathtt{dist}\[x\]+w(x)= w(P)= \mathtt{dist}\[u\]+w(u)$, i.e., $\mathtt{dist}\[v\]$ is first updated to the shortest distance from source to $v$, and it will not be updated any more.
> 1 votes

---
Tags: algorithms, graphs, shortest-path, weighted-graphs, dijkstras-algorithm
---


title: The order of ε-transitions in NFA

text:
# Question
Title: The order of ε-transitions in NFA
I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want to focus on $a$).

But when he demonstrates how to convert the NFA to an equivalent DFA, he says: state $1$ goes to $\emptyset$ on $a$ because no $a$ arrows exit it. \[...\] Note that the procedure in Theorem 1.39 \[on equivalence of DFAs and NFAs\] specifies that we follow the $\epsilon$ arrows *after* each input is read.

So, if $\epsilon$-transitions happens only after some input (as the author defines), then in the initial state $1$, when $a$ is given, the NFA should 'die' as $\delta(1, a) = \emptyset$. The transition to state $3$ never happens, the NFA doesn't accept $a$. Doesn't the author contradicts himself?

I can think of couple possible explanations: 1) the very first transition of a NFA is $\delta(1, \epsilon)$ just by definition, 2) $a\epsilon=a$, so $\delta(1, a)$ = $\hat{\delta}(1, a\epsilon)$ = $\delta(1, \epsilon)\cup\delta(1, a)$, but then again the author said state $\\{1\\}$ goes to $\emptyset$ on $a$, not ${3}$

# Answer
I think the answer is somewhat subtle and lies in Sipser's definition of what it means for an NFA to accept a string.

> Let $N = (Q,\Sigma,\delta,q\_0,F)$ be an NFA, and $w$ a string over the alphabet $\Sigma$. Then we say that $N$ *accepts* $w$ if **we can write $w$ as $w=y\_1y\_2\dots y\_m$, where each $y\_i$ is a member of $\Sigma\_\varepsilon$** and ...

Compare this with his definition of what it means for a DFA to accept a string:

> Let $M = (Q,\Sigma,\delta,q\_0,F)$ be a DFA and **let $w=w\_1w\_2\dots w\_n$ be a string where each $w\_i$ is a member of the alphabet $\Sigma$**. Then ...

Therefore, by his definitions, his NFA $N\_4$ accepts $a$ as it *can be written as* $a=\varepsilon a$, and $\varepsilon$ and $a$ are both members of $\Sigma\_\varepsilon$.
> 2 votes

# Answer
An NFA can always choose to take an $\varepsilon$-transition (if one exists) without reading any input, so your NFA would indeed accept the string $a$ by following the transitions $1 \xrightarrow{\varepsilon} 3 \xrightarrow{a} 1$ and ending up in an accepting state. This is because the NFA nondeterministically chose to follow the $\varepsilon$-transition before reading $a$ from the input.

However, when converting an NFA to a DFA we have to resolve the nondeterminism in some way. The procedure presented by Sipser in Theorem $1.39$ follows the convention that $\varepsilon$-transitions are followed after each input symbol is read, but, as he also states, a procedure based on following $\varepsilon$-transitions before each input symbol is read would work equally well. It is only a matter of the convention used to resolve the nondeterminism in the NFA.

If you look at Example $1.41$ and the DFA resulting from the conversion in Figure $1.43$, you will notice that the initial state is $\\{1,3\\}$ (the union of states $1$ and $3$ from the NFA) because the NFA have initial states $1$, but it can also go to $3$ with an $\varepsilon$-transition without reading any input. Therefore, the initial state in the DFA is the union of the two.
> 1 votes

---
Tags: automata, finite-automata, computation-models
---


# Question
Title: Matching vertex values with sum of edge weights on bipartite graph
Earlier this week I asked this question (please review):

> Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags.
>
> For example, you might be interested in running an ad with 50000 impressions on the following tags: javascipt, typescript, react, nextjs, nodejs, webpack.
>
> StackOverflow "promises" you will get 50000 impressions, but they are free to distribute them across the above tags however they desire (could even be 100% to one tag).

One of the solutions provided suggested using the Hopcroft-Karp algorithm, which I have since been able to successfully implement.

However, I'm having trouble scaling this solution to work for my use case. The bottle neck is actually in the setup of the graph more-so than the algorithm performance.

The problem is the massive number of edges that must be initialized. Take the example below:

```

==Inventory==

Tag          Units

javascipt    2
typescript   4
react        3
nextjs       3

== Subscriptions ==

Account  Units   Tags
Acme     7       javacript, typescript, react, nextjs

Stark    4       javacript, typescript

```

If we create a vertex to represent every unit, then we would end up with a graph that has 101 edges (7\*11 + 4\*6)!

The problem I'm working on is orders of magnitude larger, so this quickly becomes unrealistic.

As suggest, I can reduce the number of vertex by scaling the units, but I lose resolution and that's actually somewhat important in this case (I can maybe scale by 100x max).

I was thinking there must be a more efficient way to do this, since I'm essentially duplicating vertex for every unit. I came up with the following bipartite graph with weighted edges and vertex values:

The goal would be to to adjust the weights of the edges so that:

* On the left, the sum of edges is equal the value of the vertex
* On the right, the sum of edges is less than or equal to value of the vertex

Below is an example of one of the solutions:

I'm guessing (hoping) this is already a well known problem, for which there is also a well documented solution (ideally one that's not NP-hard)!

Maybe it's even possible to modify the Hopcroft-Karp algorithm to work for this?

# Answer
I've got bad news. There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).

Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary. The knapsack problem has a pseudopolynomial time algorithm, which means that there is an algorithm whose running time is polynomial in the numbers (but not polynomial-time in the size of the input). In your setting, that turns into an algorithm whose running time is polynomial in the size of the unweighted graph (with a massive number of edges) but not polynomial in the size of the weighted graph (with a small number of edges).

You could try expressing this as an integer linear programming (ILP) instance, and then solve with an ILP solver. It's possible that might yield a more efficient solution. The core idea is to introduce an integer variable $x\_{i,j}$ that counts the number of impressions provided to company $i$ in tag $j$; then you can introduce a few linear inequalities to capture the problem's requirements.
> 1 votes

---
Tags: algorithms, graphs, optimization, graph-traversal, weighted-graphs
---


# Question
Title: Why is this function computable in polynomial time?
Given alphabet $\\{0,1\\}$, I read that the following function $f$ is computable in polynomial time relative to input $w$

$$ f(w) = w10^{|w|^2-|w|-1} $$

i.e. $f$ can be a $TM$ that receives $w$ and outputs $w10^{|w|^2-|w|-1}$. But why is it computable in polynomial time when it has a component $0^{g(w)}$ for $g(w)=|w|^2-|w|-1$?, i.e. the size of the input is in the exponent part.

# Answer
What $0^{|w|^2-|w|-1}$ is? It is "$0$" symbol repeated $|w|^2-|w|-1$ times. What is time complexity of simply outputting $0$ $|w|^2-|w|-1$ times? Clearly it is $|w|^2-|w|-1$, what is $O(|w|^2)$, i.e. polynomial of length of input.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Proof of uniform convergence if VC dimension is finite
In the book »Understanding Machine Learning: From Theory to Algorithms«, written by Ben-David and Shalev-Shwartz, there is a proof which I do not understand. The context is proving that if a hypothesis class $\mathcal{H}$ has finite VC dimension, then it enjoys the uniform convergence property.

The proof of this implication involves Sauer's Lemma (hypothesis classes with finite VC dimension have »small effective size«) and a theorem stating that hypothesis classes with »small effective size« enjoy the uniform convergence property. The proof of the latter sub-implication involves this theorem (Theorem 6.11 in the book):

> Let $\mathcal{H}$ be a hypethesis class of binary classifiers over a domain $\mathcal{X}$ and let $\tau\_{\mathcal{H}}$ be its growth function (from Sauer's Lemma). Then, for all $m \in \mathbb{N}$, for every distribution $\mathcal{D}$ over $\mathcal{X} \times \\{0, 1\\}$ and every $\delta \in (0, 1)$: $$ \forall h \in \mathcal{H}: \mathbb{P}\_{S \sim \mathcal{D}^m}\left\[ | L\_{\mathcal{D}}(h) - L\_S(h) | \leq \frac{4 + \sqrt{\log(\tau\_{\mathcal{H}}(2m))}}{\delta\sqrt{2m}} \right\] \geq 1 - \delta $$

In the proof for this theorem it is stated, that it follows immediately from the inequality $$ \mathbb{E}\_{S \sim \mathcal{D}^m}\left\[ \sup\_{h \in \mathcal{H}} | L\_{\mathcal{D}}(h) - L\_S(h) | \right\] \leq \frac{4 + \sqrt{\log(\tau\_{\mathcal{H}}(2m))}}{\sqrt{2m}}, $$ the fact that the random variable $\theta := \sup\_{h \in \mathcal{H}} | L\_{\mathcal{D}}(h) - L\_S(h) |$ is nonnegative and Markov's inequality.

---

However, I do *not* see how it follows immediately from those facts. What am I missing?

# Answer
Let $X = |L\_\mathcal{D}(h) - L\_S(h)|$. The statement on the expectation of the supremum of $X$ implies, in particular, that for some $M$, $$ \mathbb{E}\[X\] \leq M. $$ Since $X \geq 0$, Markov's inequality implies that $$ \Pr\left\[X \geq \frac{M}{\delta}\right\] \leq \delta. $$ This implies that $$ \Pr\left\[X \leq \frac{M}{\delta}\right\] \geq \Pr\left\[X \< \frac{M}{\delta}\right\] = 1 - \Pr\left\[X \geq \frac{M}{\delta}\right\] \geq 1 - \delta. $$
> 1 votes

---
Tags: machine-learning, vc-dimension
---


title: Type inference with imports

text:
# Question
Title: Type inference with imports
I understand how a type inference algorithm infers types within a single file by building on top of already inferred types and identified constraints (e.g. in the Hindley-Milner type system).

I am wondering about how this process works/is implemented for languages where some bindings are imported from other files. I wasn't able to find any useful information elsewhere, so I figured I'd just test my luck here.

The trivial approach would obviously be to leave the imported binding type-less (e.g. substitute a type variable) and continue adding constraints. Then, when the actual definition of the binding is encountered in the other file, it is checked that the constraints and actual type can be unified. This approach has the major drawback that it basically discards all type information regarding a binding that may be present where it is defined.

Building on that first approach one could start by identifying an optimal order of analyzing files. In the case where there are no circular dependencies, this additional step would solve the problem. But in a lot of cases there are circular dependencies.

In TypeScript for example (afaik), circular dependencies are allowed without any loss of type information.

How is this problem usually handled in type inference algorithms? Are there any resources/papers that describe this problem?

# Answer
The first option is to simply process all the imports and see what is in them. This is not what you are asking, because it is equivalent to having everything in a single file, more or less. And it can be prety expensive to process all the dependencies.

What you are looking for is the notion of interface, also known as *signature*. To simplify things, an interface lists all the constants that are implemented in a given unit (file, module) together with their types. Thus, given that some file imports file `X`, all we need is an interface for `X`. Such an interface may be written by the programmer, or generated automatically and stored somewhere by a compiler, there are many ways to accomplish this.
> 2 votes

---
Tags: type-theory, type-inference, types
---


# Question
Title: Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$
The question is: For all languages $L\_1$ and $L\_2$ , if $L\_1^\* = L\_2^\*$, then $L\_1 = L\_2$.

We know that two languages are equivalent if $L(G\_1) = L(G\_2)$, where $L(G) = \\{w \in T^\* \mid S\Rightarrow^\*w\\}$. Two grammars are equivalent if the quadruple of $G\_1 = (\Sigma\_1,N\_1,P\_1,\sigma\_1)$ and $G\_2 = (\Sigma\_2,N\_2,P\_2,\sigma\_2)$ generate the same formal languages.

I think this statement is true, because they have to accept the same formal languages regardless if its called multiple times.

I'm asking this question so someone can confirm it, knows an exception, or has a proof.

# Answer
> 4 votes
Certainly not. Consider $L\_1=\\{a\\}$ and $L\_2=\\{\epsilon, a\\}$.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Induction details for proof of closure of regular languages under unions
I was reading M. Sipser, *Introduction to the theory of computation* 3ed. where he presents a proof by construction that the class of regular languages is closed under unions (Theorem 1.25). However, he omits the induction details for a formal proof of correctness. I tried filling in the details myself but it was a mess; how is this usually done?

# Answer
Given a transition function $\delta\colon Q\times\Sigma\to Q$, the standard argument proceeds by defining an *extended transition function* $\hat{\delta}\colon Q\times\Sigma^\*\to Q$ (following the notation in Sipser) that acts on strings (see J. E. Hopcroft, R. Motwani, J. D. Ullman. *Introduction to Automata Theory, Languages and Computations* 3ed., section 2.2.4 for a reference). This function is defined recursively by specifying $$\hat{\delta}(q,\varepsilon)=q \qquad\hbox{and}\qquad \hat{\delta}(q,Wa)=\delta\bigl(\hat{\delta}(q,W),a\bigr)$$ for $W \in \Sigma^\*$, $a\in\Sigma$ and $q\in Q$, and it is a simple exercise (with a proof sketched below) to show that (following the definition in Sipser) a finite automaton $M=(Q,\Sigma, \delta, q\_0, F)$ accepts a string $w\in\Sigma^\*$ if and only if $\hat{\delta}(q\_0,w)\in F$.

The heart of our desired inductive argument lies in the following result.

> Let $w\in\Sigma^\*$. Then, with notation as in the proof of Theorem 1.25 in Sipser, we have $$\hat{\delta}\bigl((r\_1, r\_2), w\bigr) = \bigl(\hat{\delta}\_{\\!1}(r\_1, w), \hat{\delta}\_{\\!2}(r\_2,w)\bigr).$$

*Proof.* We proceed by induction on $|w|$. The result follows from the definitions when $|w|=0$ as we must have $w=\varepsilon$. Suppose inductively that the result holds for all $w$ with $|w|\<n$. Then, given $w \in \Sigma^\*$ with $|w|=n$, we may write $w = w\_1\dots w\_n =: Ww\_n$, so that $$\begin{align} \hat{\delta}\bigl((r\_1,r\_2),w\bigr) &=\hat{\delta}\bigl((r\_1,r\_2),Ww\_n\bigr) \\ &=\delta\Bigl(\hat{\delta}\bigl((r\_1,r\_2),W\bigr),w\_n\Bigr) \\ &=\delta\Bigl(\bigl(\hat{\delta}\_{\\!1}(r\_1,W),\hat{\delta}\_{\\!2}(r\_2,W)\bigr),w\_n\Bigr) \\ &=\Bigl(\delta\_1\bigl(\hat{\delta}\_{\\!1}(r\_1,W),w\_n\bigr), \delta\_2\bigl(\hat{\delta}\_{\\!2}(r\_2,W),w\_n\bigr)\Bigr) \\ &=\bigl(\hat{\delta}\_{\\!1}(r\_1, Ww\_n), \hat{\delta}\_{\\!2}(r\_2,Ww\_n)\bigr) \\ &= \bigl(\hat{\delta}\_{\\!1}(r\_1, w), \hat{\delta}\_{\\!2}(r\_2,w)\bigr) \end{align}$$ as needed.

Using the above result, it is straightforward to finish the proof of correctness. Indeed, since $F = (F\_1 \times Q\_2) \cup (Q\_1 \times F\_2)$, it follows that $$\hat{\delta}(q\_0,w)\in F$$ if and only if $$\hat{\delta}\_{\\!1}(q\_1, w)\in F\_1\qquad\hbox{or}\qquad\hat{\delta}\_{\\!2}(q\_2, w)\in F\_2.$$ In other words, $M$ recognizes a string $w\in\Sigma^\*$ if and only if $M\_1$ or $M\_2$ recognizes it.

---

**Addendum.** We now sketch a proof that the two definitions of a finite automaton accepting a string are equivalent. The first definition is given on page 40 of Sipser, we repeat it here for convenience:

> Let $M = (Q,\Sigma,\delta,q\_0,F)$ be a finite automaton and let $w = w\_1w\_2\dots w\_n \in \Sigma^\*$ be a string. Then $M$ accepts $w$ if $w=\varepsilon$ and $q\_0\in F$, or if $n\>0$ and a sequence of states $r\_0$,$r\_1$, ..., $r\_n$ in $Q$ exists such that $r\_0 = q\_0$, $\delta(r\_i,w\_{i+1}) = r\_{i+1}$ for $0\le i\le n-1$, and $r\_n \in F$.

We thus have to show the following:

> A finite automaton $M = (Q,\Sigma,\delta,q\_0,F)$ accepts $w\in\Sigma^\*$ if and only if $\hat{\delta}(q\_0,w)\in F$.

**Proof sketch.** If $M$ accepts $w = w\_1\dots w\_n$, then $\hat{\delta}(q\_0,w)=\delta\bigl(\hat{\delta}(q\_0,w\_1\dots w\_{n-1}),w\_n\bigr)=\delta(r\_{n-1},w\_n)=r\_n$ by an inductive argument; intuitively this corresponds to showing that the recursive definition of $\hat{\delta}$ was defined 'correctly.' Conversely if $\hat\delta(q\_0,w)\in F$, then we may build the sequence $r\_0 = q\_0$, $\\;r\_1 = \delta(r\_0,w\_1)$, ... inductively.
> 1 votes

---
Tags: regular-languages
---


# Question
Title: Shortest path form node X to nodes A, B, C in graph
I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: `X->A, X->B, X->C` and so on. Note that the number of goal nodes will not be very big.

If I were looking for only one path I would use BFS. But I'm quite sure how I can use BFS to find all paths to goal nodes.

Time is of the essence here so I wanted to use one BFS call to find all paths at once. I basically only need their costs. But I don't really know how to do that.

Does Dijkstra's algorithm do that?

The ultimate goal is that for every source node(because there are more of them) find the shortest paths to goal nodes. All sources want to find paths to the same goal nodes. And based on every path cost I want to create a consistent bipartite graph.

# Answer
Use BFS, and keep prev pointers. Good textbooks will have a chapter on shortest-path algorithms where they describe how to reconstruct the paths themselves (not just the distances) using prev pointers; use that method, and then you'll be able to reconstruct a shortest path from $X$ to any other node. Initially the estimated distance to all nodes is $+\infty$. Whenever you update the distance to something lower, update its prev pointer to point to the node where you came from.
> 1 votes

---
Tags: graphs, time-complexity, search-algorithms, shortest-path
---


# Question
Title: Count bridging edges in a family of two component forests
I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two components $F\_1^e$ and $F\_2^e$. I am interested in the number $c(e)$ of edges in $G$ that connect $F^e$ i.e. with one vertex in $F\_1^e$ and the other in $F\_2^e$.

I would like to compute the number $c(e)$ for all $e$ in $T$ simultaneously. This can be done naively in $O(|V||E|)$. Is there a faster way to achieve this?

The graphs I am working with are small-world graphs. In particular the average distance between nodes in $G$ can be assumed to be small.

# Answer
> 1 votes
I have an idea that will efficiently get you "halfway there". Hopefully you or someone else can think of a way to extend this to get the "other half" efficiently.

For a given edge $uv$ in $T$, let me rename the two subtrees that deleting $uv$ would create as $F\_u^{uv}$ (this is the subtree containing $u$) and $F\_v^{uv}$ (the one containing $v$). Denote by $E\_u^{uv}$ the subset of $E$ for which both vertices belong to the vertex set of $F\_u^{uv}$ (i.e., the graph edges that are "completely within" the $u$-subtree of $F$), and similarly for $E\_v^{uv}$.

**For each edge $uv$ in $T$, if we can efficiently compute both $|E\_u^{uv}|$ and $|E\_v^{uv}|$ , then we can compute $c(uv)$ simply by subtracting these two counts from the total number $|E|$ of edges.**

Half of the necessary counts can be computed in $O(|E|)$ time as follows:

1. Root $T$ arbitrarily and consider all edges to be directed "down", away from the root.
2. Preprocess $T$ for fast lowest common ancestor (LCA) queries.
3. For each graph edge $uv$:
    * Increment a counter $\Delta\_x$, where $x$ is the LCA of $u$ and $v$ in $T$.
4. Compute $|E\_v^{uv}|$ as $\Delta\_v + \sum\_{c:vc\in T}|E\_c^{vc}|$ for each $T$-edge $uv$ using a single postorder DFS traversal (here $u$ is the unique parent of $v$ in $T$).

Since LCA can be computed in constant time after linear preprocessing, the above takes only $O(|E|)$ time and space to compute all $n-1$ of the $|E\_v^{uv}|$ values. (I think of $|E\_v^{uv}|$ as the number of edges "completely below" $uv$.) But it does not compute any of the $n-1$ $|E\_u^{uv}|$ values -- the numbers of edges "completely above" $uv$ -- and I can't think of an efficient way to do so.

You can of course reroot $T$ at a different vertex and repeat the exercise: The directions of some edges will be reversed, and the $|E\_v^{uv}|$ values computed for each of them can be used for the $|E\_u^{uv}|$ values in the original rooting. You could repeat this until all edges have been covered in both directions -- if you were lucky enough to be given a $T$ that is a Hamiltonian path, just 2 rootings would suffice, but in general "covering" all edges this way could require as many as $n-1$ rootings (think of a star tree), which leaves us no better off than the original method.

Ideas anyone?

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


# Question
Title: What is an algorithm to find the largest rectangle of white space in an image?
Take an image, (the Google home page) is a good example.

I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of white space containing only white space.

Do you know any algorithms that would do this?

# Answer
Subtract $254.9999999$ from all pixel values, so black corresponds to $-254.9999999$ and white to $0.0000001$.

Find the 2D subrectangle with maximum sum. There are standard $O(n^3)$-time algorithms for this problem (e.g., https://stackoverflow.com/q/19064133/781723, https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/). As long as you have no more than 10,000,000 pixels in the image, this will be the solution to your problem (since each white pixel contributes another $0.0000001$ to the sum).

Proof that this finds the optimal solution: only all-white subrectangles have a positive sum (if you have a single non-white pixel, then its contributes a negative value of $-0.9999999$ or lower to the sum, which cannot be outweighed by any number of white pixels); and the larger the all-white subrectangle, the larger its sum.
> 3 votes

---
Tags: algorithms, image-processing
---


# Question
Title: Fastest algorithm for finding the number of primes in a range
Is there an algorithm for finding the **number** of primes in a given range $\[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M is at most $2\times10^7$. I know that the sieve of Eratosthenes method works in $O(n\log\log n)$ time, but it would require calculating the number of primes up to $M$, which goes up to $10^{10}$ so it would be too slow.

# Answer
> 2 votes
Using the Sieve of Eratosthenes this takes $O((M-N) + M^{1/2}) \log \log M)$. This will be the fastest unless M is quite large and / or N is quite close to M.

If you had a case like $M = 10^{100}$, $N = 10^{100} - 10^{10}$ you would likely start with a sieve to throw out all of the 10 billion candidates that have a small divisor, leaving you with say $10^9$ candidates. Then you'd use Fermat's primality test to find all probable primes. Then you'd either say "that's good enough", or you follow it by a deterministic primality test for the remaining 43.4 million or so probable primes.

If you do a deterministic primality test then you would run Fermat's test with fewer individual tests since you don't mind a few "probable primes" that are composite. If you don't do a deterministic primality test then you would run Fermat's test for a bit longer. In practice the question would be: What is the chance that there is a "probable prime" that is really composite, vs. what is the chance that a number is reported incorrectly as prime / non-prime because of a hardware problem.

# Answer
> 0 votes
You possibly cannot do it in time linear to $M-N$. Suppose to the contrary there is such algorithm that runs in $C(M-N)$ time for $M-N\ge K$, then for any large enough integer $n$, we can use this algorithm to count the number of primes in $\[n-K,n)$ and $\[n-K,n+1)$ to check whether $n$ is a prime, in $CK+C(K+1)$ time. Note this time is independent of $n$, so we can now check whether $n$ is a prime in constant time for sufficient large $n$, which is possibly impossible.

---
Tags: algorithms, counting, primes
---


# Question
Title: Enumerate the terms resulting from decomposing a number by repeated divisions by 2
Consider a natural number $n\>1$. We express it as $\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$. We repeat the process for each of the two terms until all terms are 1 or 2. For example $9 = 4 + 5 = 2 + 2 + 2 + 3 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2$.

There will be $2^{\lfloor \log\_2 n\rfloor}$ terms because the decomposition forms a complete binary tree of height $\lfloor \log\_2 n\rfloor$.

I am looking for an iterative form of this recursive process. The enumeration $a\_0 = 0, a\_{i+1} = \left\lfloor \frac {(i+1) \cdot n} {2^{\lfloor \log\_2 n\rfloor}} \right\rfloor - a\_i$ comes close because it does satisfy the following conditions: (a) each term is 1 or 2; (b) the sum of the first $2^{\lfloor \log\_2 n\rfloor}$ terms is $n$. But the elements are not identical to the recursive decomposition form.

Any help would be welcome. Thanks!

# Answer
Let $2^m$ be the largest power of $2$ not greater than $n$, a positive integer.

As mentioned in the question, if we repeatedly replace each term $\cdot$ with $\lfloor \frac \cdot2 \rfloor$, $\lceil \frac \cdot2 \rceil$, we will change $\[n\]$ to a sequence of $2^m$ terms, each of which is either 1 or 2.

Let that sequence be $S(n)=\[S\_0, S\_1, S\_2,\cdots, S\_{2^m-1}\]$. We have $S\_0=1$ since $S\_0=\lfloor\frac n{2^m}\rfloor$.

**Formula for the general term.** For all $i$, we have $S\_i=1$ if $n-2^m \le r\\!c\_m(i)$ and $S\_i=2$ otherwise.

Here $r\\!c\_m(i)$ is the **r**everse of the **c**omplement of $m$-bit binary representation of $i$, i.e, if the binary representation of $i$ is $i\_{m-1}i\_{m-2}\cdots i\_1i\_0$, then the binary representation of $r\\!c\_m(i)$ is $(1-i\_0)(1-i\_1)\cdots(1-i\_{m-2})(1-i\_{m-1})$ .

For example, we have $$\[r\\!c\_3(0), r\\!c\_3(1), r\\!c\_3(2), r\\!c\_3(3), r\\!c\_3(4), r\\!c\_3(5), r\\!c\_3(6), r\\!c\_3(7)\]=\[7, 3, 5, 1, 6, 2, 4, 0\].$$ Since $12 = 2^3 + 4$, comparing 4 with each term $r\\!c\_3(\cdot)$, we obtain,

$$S(12) = \[1,2,1,2,1,2,1,2\].$$

**Proof**: We do induction on $m$, which is $\lfloor\log\_2(n)\rfloor$.

The base case is when $m=0$, i.e., $n=1$. The sequence $S(1)=\[1\]$. The formula holds.

Suppose the formula is true for $m$, i.e, for all $n$ and $i$ such that $2^m\le n\lt2^{m+1}$, $S(n)\_i=1$ iff $n-2^m\le r\\!c\_m(i)$.

Now consider the case of $m+1$.

Suppose $2^{m+1}\le n\lt2^{m+2}$. By definition, we have $S(n)=\[S(\lfloor \frac n2 \rfloor), S(\lceil \frac n2 \rceil)\]$, where we abuse the bracket so that $\[\cdot, \cdot\]$ means the concatenation of the two sequence, i.e., for example, $\[\[1,2,2,1\], \[1,1,1,2\]\]=\[1,2,2,1,1,1,1,2\]$. Since $2^m\le\lfloor \frac n2 \rfloor, \lceil \frac n2 \rceil\lt2^{m+1}$, we can apply the induction hypothesis to $S(\lfloor \frac n2 \rfloor)$ and $S(\lceil \frac n2 \rceil)$.

What is $S(n)\_i$? There are two cases.

* $0\le i\lt 2^m$. Then $S(n)\_i = S(\lfloor \frac n2 \rfloor)\_i$. So $$\begin{align} S(n)\_i=1&\Leftrightarrow S(\lfloor \frac n2 \rfloor)\_i=1 \\\&\Leftrightarrow \lfloor \frac n2 \rfloor-2^m\le r\\!c\_m(i) \\\&\Leftrightarrow 2(\lfloor \frac n2 \rfloor-2^m)\le 2r\\!c\_m(i) \\\&\Leftrightarrow n -2^{m+1}\le r\\!c\_{m+1}(i) \end{align}$$ where the last equivalence comes from the fact $2\lfloor \frac n2 \rfloor$ equals $n$ or $n-1$ and $2r\\!c\_m(i)=r\\!c\_{m+1}(i)-1$.
* $2^m\le i\lt2^{m+1}$. Then $S(n)\_i = S(\lceil \frac n2 \rceil)\_{i-2^m}$. So $$\begin{align} S(n)\_i=1&\Leftrightarrow S(\lceil \frac n2 \rceil)\_{i-2^m}=1 \\\&\Leftrightarrow \lceil \frac n2 \rceil-2^m\le r\\!c\_m({i-2^m}) \\\&\Leftrightarrow 2(\lceil \frac n2 \rceil-2^m)\le 2r\\!c\_m({i-2^m}) \\\&\Leftrightarrow n -2^{m+1}\le r\\!c\_{m+1}(i) \end{align}$$ where the last equivalence comes from the fact $2\lceil \frac n2 \rceil$ equals $n$ or $n+1$ and $2r\\!c\_m({i-2^m})=r\\!c\_{m+1}(i)$.

---

Once we know the above formula, we have the following simple iterative algorithm, which is a direct translation of the formula above.

Input: a positive integer $n$.
Output: the wanted sequence
Procedure:

1. Compute integer $m$ and $n\_r$ such that $n=2^m+n\_r$, where $0\le n\_r\lt 2^m$.
2. loop $i$ through 0 to $2^m-1$.

1. Compute the reverse of the $m$-bit complement of $i$, $rc\_m(i)$.
    2. Output $1$ if $n\_r \le rc\_m(i)$. Output 2 otherwise.

Note that for $i$ between $0$ and $2^m-1$, the function $i\to rc(i)$ is a bijective function, since both complement and reverse are bijective. We could optimize the algorithm by devising a way to compute the binary representation of $rc(i+1)$ directly from the binary representation of $rc(i)$. That will make the algorithm even more "iterative" as well. We can also precompute the sequence $r\\!c\_m(0), r\\!c\_m(1), \cdots, r\\!c\_m(2^m-1)$ by taking advantage of its iterative pattern, for example, with $m=4$, $$15, \underbrace{7}\_{\[15\]-8}, \underbrace{11, 3}\_{\[15,7\]-4}, \underbrace{13, 5, 9, 1}\_{\[15, 7, 11, 3\]-2}, \underbrace{14, 6, 10, 2, 12, 4, 8, 2}\_{\[15, 7, 11, 3, 13, 5, 11, 1\]-1}.$$

---

**A simple exercise.** Find the similar formula for the general sequence $S\_k(n)$, which is obtained by modifying the sequence $\[n\]$ for $k$ rounds, where every term $\cdot$ in the sequence is replaced by two terms, $\lfloor \frac \cdot2 \rfloor$ and $\lceil \frac \cdot2 \rceil$ in each round. $n$ and $k$ can be any nonnegative integer. For example, $S\_2(10)=\[2, 3, 2, 3\]$ and $S\_4(10)=\[0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1\]$.
> 2 votes

# Answer
Denote the total number of terms by $m = 2^{\lfloor \log n \rfloor}$. Suppose that $m\_1$ terms are equal to $1$, and $m\_2$ terms are equal to $2$. Thus $$ n = m\_1 + 2m\_2 = m + m\_2, $$ from which we find that $m\_2 = n-m$ and $m\_1 = 2m-n$. So if you arrange the terms in nondecreasing order, the first $2m-n$ would be $1$, and the remaining $n-m$ would be $2$.
> 2 votes

---
Tags: algorithms, recursion
---


# Question
Title: Halting problem for fixed Turing machine and fixed input
It is known that the halting problem is undecidable even when we fix *either* the Turing machine $M$ *or* the input $w$.

What if we fixed both the machine *and* the input? I.e., is it decidable for every fixed Turing machine $M\_0$ and every fixed input $w\_0$ that $M\_0$ will halt on $w\_0$ as input?

# Answer
> 4 votes
> It is known that the halting problem is undecidable even when we fix *either* the Turing machine $M$ *or* the input $w$.

You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}\_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always halts, we can easily decide $\text{HALT}\_M$ just by outputting "yes".

What you probably meant to say is the following facts, which are true:

1. *There exists* a Turing machine $M$ such that the problem $\text{HALT}\_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable.
2. *For all* words $w$, the problem $\text{HALT}\_w$ (deciding on input $M$ if $M$ halts on $w$) is undecidable.

In particular for fact 1, we can take $M$ to be the universal Turing machine.

> What if we fixed both the machine *and* the input? I.e., is it decidable for every fixed Turing machine $M\_0$ and every fixed input $w\_0$ that $M\_0$ will halt on $w\_0$ as input?

Yes, the problem becomes trivially decidable. Define the language $\text{HALT}\_{M\_0, w\_0}$ to be the problem of deciding whether $M\_0$ halts on $w\_0$. But notice that this problem no longer has any input that the answer depends on, as both things that the answer might depend on ($M\_0$ and $w\_0$) are now fixed, i.e. part of the language definition, not part of the input. That means the answer is just "yes" or "no". So we can trivially decide this problem either by using a program which always says "yes", or a program which always says "no".

This is a common pitfall about decidability: **it is only useful to ask whether a problem is decidable or not when the number of possible inputs is infinite.** If there are only finitely many possible inputs, then all problems become decidable. You have asked whether a problem with only 1 possible input (the empty input) is decidable, and the answer to that is always yes.

---
Tags: turing-machines, computability, undecidability, halting-problem
---


# Question
Title: What is the language generated by this grammar?
I'm struggling to find the language generated by the following grammar:

Any help would be appreciated.

# Answer
> 0 votes
Let's analyze this step by step. I. Let's suppose we chose the first production from the axiom: $$ S \to P$X $$ Here we encounter two new non-terminals (some call them variables. The reception of non-terminal symbols as some "entities" in the language comes in pretty handy during one's first steps into the formal grammar theory, yet it is imperative, from my point of view, to understand that at the end of the day they are just symbols. The term "non-terminal" implies that unlike the term "variable"): `P` and `X`. It is kind of no use to compose separate branches for them as they are recursive and it would lead to a pretty cumbersome solution. It is easier to analyze the ulterior meaning behind those symbols via looking at the productions (again): $$ P \to aPa \mid bPb \mid $ $$ It is easy to see that this non-terminal generates a substring of the following structure: $$ w$w^R \text{, where } w \in \\{a, b\\}^\* \text { and } w^R \text{ is the reversed } w.$$ Let's try writing a chain of relations down in order to illustrate our result: $$ P \Rightarrow aPa \Rightarrow aaPaa \Rightarrow aabPbaa \Rightarrow aabaPabaa \Rightarrow aaba$abaa $$ Now, let's move on to `X`. `X` does an even simpler thing - it generates $$ \\{a, b\\}^\* $$. E.g.: $$ X \Rightarrow bX \Rightarrow baX \Rightarrow baaX \Rightarrow baabX \Rightarrow baabbX \Rightarrow baabb$$ Summing this branch up, we get the following structure: $$ w$w^R$x \text{, where } w, x \in \\{a, b\\}^\* \text { and } w^R \text{ is the reversed } w. $$

Now, we shall proceed to the second possible production from the axiom: $$ S \to X$bTa$$ We already know what `X` does, so the only missing part of the puzzle at this point is the non-terminal `T`: $$ T \to bTa \mid $ $$ Once again, the generated structure is pretty neat: $$ b^n$a^n \text{, where } n \text{ is a whole number or zero.} $$ Summing this branch up, we get: $$ x$bb^n$a^na \text{, where } x \in \\{a,b\\}^\* \text { and } n \text{ is a whole number or zero,} $$ which is identical to: $$ x$b^n$a^n \text{, where } x \in \\{a,b\\}^\* \text { and } n \text{ is a whole number.} $$ Thus, the language couldbe written down as the following union: $$ L\_G = \\{w$w^R$x \mid w, x \in \\{a, b\\}^\* \text { and } w^R \text{ is the reversed } w\\} \text { } \text{ } \text{ }\cup \\{x$b^n$a^n \mid x \in \\{a,b\\}^\* \text { and } n \text{ is a whole number}\\}.$$

The problem situation might seem scary and/or unwieldy, yet a coherent step-by-step analysis always does the trick.

I hope I did not make any mistakes in my solution.

I can recommend some literature on the topic: "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman; "Algorithms and Programming. Problems and Solutions" by A. Kh. Shen and "The Mathematical Theory of Context-Free Languages" by S. Ginsburg.

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


# Question
Title: Equivalence of two definitions of mutual information
I am learning quantum computing and as a background study, I am currently learning fundamentals of classical information theory. I thought it best to ask my doubts here. In Nielsen and Chuang, it is stated that mutual information I(X:Y) of two random variables X and Y is the information they have in common while in some books, it is written that mutual information I(X:Y) is the information one variable(say X) has about the other(say Y). I can't understand it intuitively how the two definitions are equivalent. Also, the symmetric property of mutual information,i.e., I(X:Y)=I(Y:X) is obvious to me from the first definition but not from the second one.

# Answer
> 1 votes
You can define the mutual information as $I(X;Y) = H(X) - H(X|Y)$. This definition is symmetric in $X,Y$ since $$ H(X)-H(X|Y) = H(X) - \sum\_y \Pr\[Y=y\] H(X|Y=y) = \\ \sum\_x \Pr\[X=x\] \log \frac{1}{\Pr\[X=x\]} - \sum\_y \Pr\[Y=y\] \sum\_x \Pr\[X=x|Y=y\] \log \frac{1}{\Pr\[X=x|Y=y\]} = \\ \sum\_{x,y} \Pr\[X=x,Y=y\] \log \frac{1}{\Pr\[X=x\]} - \sum\_{x,y} \Pr\[X=x,Y=y\] \log \frac{\Pr\[Y=y\]}{\Pr\[X=x,Y=y\]} = \\ \sum\_{x,y} \Pr\[X=x,Y=y\] \log \frac{\Pr\[X=x,Y=y\]}{\Pr\[X=x\]\Pr\[Y=y\]}, $$ and this expression is symmetric in $X,Y$.

This calculation also shows that if $X,Y$ are independent then $I(X;Y) = 0$, since then $\Pr\[X=x,Y=y\] = \Pr\[X=x\] \Pr\[Y=y\]$.

Moreover, if we write $$ I(X;Y) = \sum\_{x,y} \Pr\[X=x\] \Pr\[Y=y\] \frac{\Pr\[X=x,Y=y\]}{\Pr\[X=x\] \Pr\[Y=y\]} \log \frac{\Pr\[X=x,Y=y\]}{\Pr\[X=x\] \Pr\[Y=y\]}, $$ then the convexity of $z\log z$ implies that $I(X;Y) \geq z\log z$, where $$ z = \sum\_{x,y} \Pr\[X=x\] \Pr\[Y=y\] \frac{\Pr\[X=x,Y=y\]}{\Pr\[X=x\] \Pr\[Y=y\]} = \sum\_{x,y} \Pr\[X=x,Y=y\] = 1. $$ Thus $I(X;Y) \geq 0$.

---
Tags: information-theory
---


title: Generate slice that contains element

text:
# Question
Title: Generate slice that contains element
Suppose I have the array:

```
[2, 3, 4, 5, 6, 7, 8, 9]

```

Now based on few parameters:

1. `current_item` \- currently selected item.
2. `select_size` \- selection size, always odd.

I want to get a sublist of the list that follows the conditions:

1. **current\_item** should be in middle of sublist if that is possible.
2. In case when there is not enough elements on left/right of the list, use the ones from right/left.

Examples:

```
list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 5
select_size: 3

result: [4, 5, 6]

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 2
select_size: 5

result: [2, 3, 4, 5, 6]

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 8
select_size: 5

result: [5, 6, 7, 8, 9]

```

# Answer
> 1 votes
Let the index of the central item be $c$, and the length of the list be $2r+1$. We assume that the indices of the list are $0,\ldots,n-1$.

There are four cases to consider:

* If $n \> 2r+1$, then the results are undefined (per your post).
* If $0 \leq c-r$ and $c+r \leq n-1$, then you just take elements $c-r,\ldots,c+r$.
* If $c-r \< 0$, then you take elements $0,\ldots,2r$.
* If $c+r \geq n$, then you take elements $n-2r-1,\ldots,n-1$.

In the latter two cases, we are guaranteed to be within bounds since $n \> 2r+1$.

---
Tags: algorithms, lists
---


# Question
Title: Printing values of psuedo random numbers in a range
I wanted to write a program to print the values of pseudo random numbers in a range. So, i wrote the following:

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
 int i=0,x;
 while(i!=10)
{
    srand(time(0));
    x=rand()%51;
    if(x>=30&&x<=45)
    {
    printf("%d\n",x);
    i++;
    }
}
return 0;
}

```

But this program is printing some random number between 30 and 45 10 times(the same value, say 33 ten times). Can someone please explain the flaw in this?

# Answer
While this looks like a programming question, the real misunderstanding is in how to use pseudorandom number generators.

A pseudorandom number generator is initialized using a seed (we later expand on that). Once initialized, it can be called to output a (seemingly) infinite sequence of random bits or integers (the sequence will be periodic, but the period can be huge). The interface of a pseudorandom number generator thus consists of two functions:

* Initialize with a seed – in your case, `srand`.
* Output the next number in the sequence – in your case, `rand`.

For some reason, you are initializing the seed each time you want a random number. While this is not necessarily wrong (though in your case it is!), it ignores a fundamental feature of most pseudorandom number generators: initializing is slow, and generation is fast. We can effort initialization to be slow since it is only called once, whereas you could be generating many numbers. This is why it is not recommended to initialize your generator for each generated number.

What goes wrong with your code? The problem is that `time` returns a value which only changes once a second. Since your program executes in much less than a second, it is highly likely that each time you initialize your generator, you will initialize it using the very same value. Therefore you are getting the same number each time – this is by design.

Finally, a few words on how to initialize your generator. One option is to choose a seed at random once and for all. This guarantees that your results are reproducible – each time you run the program, it will be using the same pseudorandom sequence. Another popular option is to use the current time, as you're doing (though it's better to use something with higher resolution than seconds). A third option is to use some "entropy reservoir", such as the Unix /dev/random, which is supposed to pick up entropy from key presses, mouse moves, and so on. A fourth option would be to use thermal noise – that requires specialized hardware.
> 2 votes

---
Tags: pseudo-random-generators
---


# Question
Title: How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros?
***This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3.***

$$ \text {Let }b\_i \text{ denote } i \text{ in binary without leading zeros.}$$ We need to construct a CFG which generates the following language: $$ \\{0, 1, 2\\}⁺ - \\{b\_12b\_22...2b\_n | \text{n is a whole number}\\} \text{.} $$

Firstly, I considered implementing such non-terminal $$ U \mid \forall \text{whole n}. S \Rightarrow^+ U \Rightarrow^+ b\_12b\_22...2b\_n\text{.} $$ I believe that even if this could be done, it would have a fairly cumbersome structure: $$ \\{b\_12b\_22...2b\_n | \text{n is a whole number}\\} $$ does not satisfy the Pumping lemma, therefore, is not a CFL. For the same reason, I can't see any way to apply any neat theorems like $$CFL - RL = CFL\text{.}$$

How could one construct such a grammar? I would really appreciate some hints, which could help me solve the problem, instead of a complete solution.

# Answer
Here is the idea. We can always write the string in the form $w\_1\\#\cdots\\#w\_n$, for some strings $w\_i \in \\{0,1\\}^\*$. If the input string is *not* of the form $b\_1\\#\cdots\\#b\_n$, then one of the following must happen:

* $w\_1 \neq 1$.
* One of the $w\_i$'s is empty.
* One of the $w\_i$'s has a leading $0$.
* For some $i$, $w\_i+1 \neq w\_{i+1}$.

The first three cases are easy. In the first case, the string is empty or starts with $\\#,0,10,11$. In the second case, there is a substring $\\#\\#$. In the third case, there is a substring $\\#0$.

For the fourth case, let $x = w\_i$ and $y = w\_{i+1}$. Here are some things which are not supposed to happen:

* $x$ ends with $1^m$ and $y$ ends with $10^{m-1}$.
* $x$ ends with $01^m$ and $y$ ends with $0^{m+1}$.
* $x = 1^m$ and $y = 0^m$. (Actually this is ruled out by requiring no leading zeroes.)
* $x$ starts $\\{0,1\\}^ib\\{0,1\\}^\*0$ and $y$ starts $\\{0,1\\}^i \overline{b}$.

Unless I missed some case, if none of these things happen, then $y$ is the encoding of $x+1$. Indeed, the first two constraints guarantee that if $x=z01^m$ then $y=w10^m$ (the third constraint takes care of the corner case $x=1^m$, in which case $y=10^m$), and the fourth constraint guarantees that $z=w$.

Each of these subcases corresponds to a context-free language – once again, there are some corner cases to consider (if $x = w\_1$ and if $y = w\_n$).
> 1 votes

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


# Question
Title: How to be sure of a good solution in hyperparameter optimization
I have a very expensive black-box function and at least 15 parameters that I want to explore (usually 5-6 at a time). So far I have tried Genetic Algorithms and Gaussian Process Surrogate Optimization (bayesian optimization). Both methods work fine and efficiently up to 5-6 parameters. However, I am having an issue on how can one be sure that a solution found by GA/GPSO is a good solution, without basically knowing nothing about the output space. I don't really want to go for an exhaustive grid search since even with 5 parameters, it requires incredible amounts of evaluations, yet I cannot come up with anything better.

I would also very much appreciate suggestions/keywords for literature reading, or event different methods for hyperparameter optimizations.

Thanks in advance

# Answer
The short answer: You can't. These are heuristics. There are no guarantees. They might fail badly; and there's no reliable way to detect that.
> 0 votes

---
Tags: optimization, genetic-algorithms
---


# Question
Title: Does FreeRTOS replace linux or run ontop?
I am looking into FreeRTOS, just for personal learning and I am stuck on how the fundamentals of how it works with Linux.

So for example, I am able to build FreeRTOS on my linux ubuntu machine. Now the part I am stuck on is: it must be running ontop on Ubuntu, so how do I get the real time performance from it? Wouldnt it be limited by what Ubuntu OS scheduler does behind the scenes?

Secondly, I have an embedded linux device from my company to experiment with. If I wanted to put an application/program running/using FreeRTOS does it replace the (custom) embedded linux OS that is already on this device?

# Answer
As per ghellquist, in product FreeRTOS is designed to run directly on hardware, it is the kernel, it doesn't run on a kernel. What may be confusing is that there are also Windows and Linux ports of FreeRTOS - but these are development and test environments that run the FreeRTOS kernel's core code (the code that is part of every FreeRTOS port) - so the kernel is deciding which FreeRTOS thread is running when - but does not actually implement any context switching code as such (it just starts and stops Windows/Linux threads rather than creating and managing its own). You would never actually deploy a system or in any way get real time behaviour using the Windows or Linux ports - to deploy you would use one of the many other ports.
> 2 votes

# Answer
FreeRTOS runs directly on the hardware. It replaces Linux and all other OS-s at run time. No part of the Linux scheduler is involved.

A different thing is that you might use Linux or Windows in developing and configuring A FreeRTOS system.
> 0 votes

---
Tags: os-kernel
---


# Question
Title: Is two-coloring parts of a bipartite graph so that for each uncolored vertex, the incoming edges from each color are roughly equal NP-complete?
Let's say we have a bipartite graph $G=(V\_1\dot\cup V\_2,E)$.

We're now looking for a two-coloring (red/blue) of the vertices of $V\_1$, so that for all vertices $v\in V\_2$ the sum of edges coming from red vertices differs at most by 1 from the sum of edges coming from blue vertices.

In other words, we're looking for a two-coloring $c:V\_1\to\\{-1,1\\}$ so that the following formula holds: $$ \forall v\in V\_2:\left( \sum\_{v'\in V\_1\\\\{v,v'\\}\in E}c(v')\in \\{-1,0,1\\}\right) $$

My question: Is finding such a two-coloring (or showing that no such two-coloring exists) NP-complete?

There's a (somewhat) linear algebra formulation of this problem, though it doesn't seem to be very helpful:

Let $V\_1 = \\{v\_1,...,v\_n\\}$. Then we can define for every vertex $v\in V\_2$ the row vector $(k\_{1,v},...,k\_{n,v})$ with $$k\_{i,v} =\begin{cases} 1,&\text{if } \\{v\_i,v'\\}\in E\\ 0,&\text{else}\end{cases}$$.

If we now let $c\_i\in \\{-1,1\\}$ be the color of vertex $v\_i$, then the requirements for the two-coloring can be written as: $$ \forall v\in V\_2:\qquad (k\_{1,v},...,k\_{n,v}) \cdot \pmatrix{c\_1\\\...\\ c\_n} \in \\{-1,0,1\\} $$ or equivalently with $V\_2 = \\{v'\_1,...,v'\_m\\}$: $$ \pmatrix{k\_{1,v'\_1}&...&k\_{n,v'\_1}\\\...&...&...\\ k\_{1,v'\_m}&...&k\_{n,v'\_m}} \cdot \pmatrix{c\_1\\\...\\ c\_n} \in \\{-1,0,1\\}^m $$

# Answer
> 2 votes
Your bipartite graph describes a set system whose elements are the vertices in $V\_1$ and whose sets are the vertices in $V\_2$. Your condition is the same as asking whether the discrepancy is at most $1$.

If all sets have even size (i.e., all vertices in $V\_2$ have even degree), then the discrepancy is always even, and so you are interested in whether a given set system in which each set has even size has discrepancy zero. It turns out that this is NP-hard even if all sets have size 4. This problem is known as Max-2-2-Set-Splitting.

There are much stronger NP-hardness results on discrepancy, such as Tight hardness results for minimizing discrepancy by Charikar, Newman and Nikolov. You can find pointers on Max-2-2-Set-Splitting there.

---
Tags: time-complexity
---


# Question
Title: Knapsack-like problem with profit formula
Given two sets of $N$ integers, *weights* and *reps*, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once.

The profit is given by the following formula: $$ \min(\mathit{takenweights}) \times \sum\_{i=1}^m \mathit{takenreps}(i), $$ where $m \leq M$.

For example, if $M = 3$, the weights are $3,5,6,2,4,9$, and the reps are $8,3,4,10,7,4$, then the output should be $60$, obtained by taking the third, fifth and sixth dumbbells (minimum weight $\min(6,4,9) = 4$ and total rep $4+7+4=15$).

I was thinking of using two double arrays, one for the minimum and one for the profit, where $dp(i,j)$ is the maximum profit obtained by taking $i$ dumbbells among the first $j$, and $dp\_{\min}(i,j)$ is the minimum for $dp(i,j)$.

However, I couldn't find a recursion formula.

Do you have any suggestions?

# Answer
One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $M$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).

To implement this algorithm efficiently, start by sorting the dumbbells according to weight and according to rep (separately), and find the $M$ dumbbells with maximal rep. Now go over the dumbbells in order of weight, each time removing the dumbbell with lowest weight and updating the set of $M$ best dumbbells. If you're careful you might be able to implement this in $O(N)$, so together with the initial sorting, the algorithm might run in time $O(N\log N)$.
> 1 votes

---
Tags: algorithms, optimization, dynamic-programming, knapsack-problems
---


title: Parity of number of divisors

text:
# Question
Title: Parity of number of divisors
Im pretty new here.

My question showing me an algorithm:

TRUE\_SEQ(A\[1...n\])

```
for i <- 1 to n do
 A[i] <- FALSE
for i <- 1 to n do
 k <- i
 while(k <= n) do
  FLIP(A[k])
  k <- k + i

```

FLIP(x)

```
if x = TRUE then
 x <- FALSE
else
 x <- TRUE

```

Now i need to prove that after we finish TRUE\_SEQ, the value of $A\[i\]$ is TRUE if and only if $i \in N$ is a power of a some natural number.

We learned about loop recorded sequence (Im not sure if i say it correctly in english)

Any way i would like a hint (and prefer a hint than a solution - as those are my homeworks)

Thank you for the help.

# Answer
At the end of the algorithm, the value of $A\[n\]$ is the parity of the number of divisors of $n$ (TRUE means odd parity). The divisors of $n$ come in pairs $i,n/i$. Most of these pairs consist of two distinct values, but if $n$ is a square, then when $i = \sqrt{n}$, both elements are equal. This shows that $A\[n\]$ is TRUE if and only if $n$ is a square.
> 1 votes

---
Tags: algorithms, algorithm-analysis, proof-techniques
---


# Question
Title: How can I optimise this bitmask generation algorithm?
I am emulating the left shifting of a 128-bit integer using two 64-bit integers. For this I must calculate the bits that need to be moved into the higher portion. I have the following algorithm for generating a bitmask that masks the last `until` bits.

Where `until` is an integer in the range `0..64`:

```
 ~(power(2,64-until))-1)

```

For convenience this is it in Python:

```
def mask(until): bin((~(2**(64-until)-1))&0xFFFFFFFFFFFFFFFF)

```

Is there a faster way to do the same thing by avoiding the costly use of `power()`? Or is this the most efficient way?

# Answer
You can compute a power of 2 using the operation of *left shift*, in C and related languages `<<`. For example, $2^n$ is the same as `1 << n`.

An alternative is to precompute the mask for all possible input values, and store them in the array. You'll have to try it out to see whether this is faster than the other suggestion.
> 1 votes

---
Tags: optimization
---


title: Parentheses after Typing Environment

text:
# Question
Title: Parentheses after Typing Environment
I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: `Γ(x) = k`. For example, in A Short Introduction to Systems F and F Omega:

```
Γ(a) = k
--------
Γ ⊢ a : k

```

I see the same construct in Hereditary Substitution for Stratified System F. I understand the bottom part fine. It would read something like: "In context `Γ`, `a` has kind `k`". I've not been able to find an explanation of the top part, and the sources I referenced both assume familiarity with this construct. If I had to guess, I suspect that it means something like "In context `a`, running a kind-checking algorithm on `a` gives you kind `k` as the result". Is that accurate? What online resources describe this construct?

# Answer
$\Gamma$ here is overloaded notation. The meaning of the expression $\Gamma(x) = \tau$ above the inference line here is given under the "**Type rules.**" section of A Short Introduction to Systems F and F Omega on page 5. In this setting, $\Gamma$ is an inductively-defined function sending variables (in $\Gamma$ considered as a context, i.e. a list of variables) to their types.

A more illustrative, syntactic way to write the rule you give might be: $\frac{}{\Gamma,\ x : \tau\ \vdash x : \tau}$, where $\Gamma$ ranges freely over contexts. Note that the order of variables in a context here does not matter, so this rule allows us to project any variable in a context as a term.
> 3 votes

# Answer
To add to varkor's answer:

A context is just a function sending (some) variables to their types.

So the rule is saying: "If $\Gamma$ assigns the type $\tau$ to variable $x$, then we can deduce $\Gamma \vdash x : \tau$."
> 1 votes

---
Tags: type-theory, notation
---


# Question
Title: Efficiently finding "unfounded edges" in a strongly connected graph
While implementing a debugger I've encountered a problem I need to solve concerning dependency graphs. I've simplified it as follows:

Consider a **strongly connected** graph G = (V,E).

* We define a subset of vertices S ⊆ V as *source vertices*.
* We call an edge **e** = (**a**,**b**) *unfounded* if there is no **simple path** from any source vertex to **b** that includes **e**. In other words, all paths from a source vertex that include edge **e**, must include vertex **b** at least twice.

The problem:

* Find all unfounded edges in G.

There are some obvious ways to solve this inefficiently (e.g. a depth-first traversal for each edge in G), but I was wondering if there was any **O(|E|)** approach. I've been struggling with this for a while and I keep "almost" solving it in linear time. Perhaps that's impossible? I have no idea what the lower bound on efficiency is, and I was hoping some readers here could help me discover some efficient approaches.

An illustrative example is a simple 3-cycle. Pick any one vertex as the source vertex. The edge coming into the source vertex is unfounded.

# Answer
I believe that computing graph dominators will solve your problem. This can be done in $O(|E|\log |V|)$ time (or even faster, though they describe the faster algorithm as "sophisticated") using a 1979 algorithm by Lengauer and Tarjan, which is (at least currently) described here (21 pages -- I have only read the first few pages myself).

Add a new "start" node with an out-edge to every source node, run the dominator algorithm to determine dominators for every node, and then check each edge $uv$: $uv$ is unfounded if and only if $v$ dominates $u$. (Each of these checks can be done in constant time using a lowest common ancestor (LCA) algorithm, although that may be overkill here -- for an edge $uv$, we only care about whether or not $LCA(u, v) = v$.)
> 1 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: How to generate tree variants of a tree using recursion?
I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion?

any help is appreciated.

# Answer
> -1 votes
The outline is: You start the function-call at the root vertex. For every child-vertex, you find all permutations of its sub-tree. Then you you find all combinations of these permuations of the children's sub-trees, and for each of them do all permutations of the child-vertices themselves.
The recursion happens where you need the permutations of the sub-trees of the children.
The exit-condition is the call on a leaf.

```
Set<Tree> perm(vertex x):
    if x is leaf:
        return x
    Let C be the set of all children of x.
    Set<Tree> result <- emptySet
    For all different combinations of perm(c) from the vertices c of C, now called comb:
        For all permutations p of C:
            add to result the graph you get with comb and p.
    return result

```

---
Tags: trees, recursion
---


# Question
Title: How to know if a problem belongs to NP Class?
**What I know (NOT strictly speaking):** I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we make a distinction about the space-time solvability of such problems. Also, I know that you can make reductions (of polynomial time) between problems, so if you know that a problem belongs to a certain class, then the other problem will also belong to this class. Also, I know that the Simplex algorithm solves problems for linear programming

**What I would like to know:** I would like to know how to "guess" if a problem belongs to NP Class. Does it have to do with the constraints of the problem, the number of constraints, the "type" of constraints?

An example In this link https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/ we can see an algortihm that solves "Maximum profit by buying and selling a share at most k times" with dynamic programming.

However, what if we increase the constraints. Let's say that we are limited to a net worth (we don't have unlimited money) or we can buy and sell more than one stock at a time but we are limited to the ammount of stocks we can buy or sell in the given time, or there are multiple stocks of various companies we can choose from but we are limited in the total number of stocks we can have.

How can we know what kind of constraints make the problem harder and harder "moving" it from P to NP Class ? What kind of constraints should a problem have to be sure that this problem certain belongs either to P or NP Class ?

# Answer
> 3 votes
1. Make sure you use NP correctly. To say something belongs to NP doesn't really say anything, except that a right solution of the problem can be checked fast.
2. From my experience, it's more about the type of problem than what specific constraints you give it.
For example Indipendent-Set: Including a vertex at one end of the graph may inpact if you can take a vertex at the other end of the graph. This kind of unforeseeable side-effects makes it impossible to really find an algorithm, because you can't decide anything about your solution because you don't know the implications.

On the contrary is sorting: If you use quicksort, you can pick a pivot and split the elements into 2 parts, the ones lower and the ones higher than the pivot.
This way you already made the problem easier: You only need to sort these 2 parts, and you know which of them belongs to which side of the pivot.

Getting such a handle on a NP-hard problem was not successful yet.

I know that this was pretty vague, in the end you can't generalize your question. Every change to a given problem may generally make it NP-hard, you need to look individually.

To prove that something is NP-hard, you can try to reduce an known NP-hard problem to it. This is how it's done with most of them.

An example for your question would also be:
The Maximum-Cut problem is NP-hard, but if you only ask if there exists a cut of size |E|, then it becomes easy, because it is equivalent to asking if the graph is bipartite

---
Tags: np-complete, np, p-vs-np, constraint-programming
---


# Question
Title: Find largest and second largest elements of the array
So here is a HW problem I have been working. On I was wondering if anybody could give me a hint of what I am doing wrong. I don't want to be given the answer just hints and advice on how to solve it.

I am given this simple algorithm that finds the greatest value and the second greatest value in a array.

```
  If A[1] < A[2],
        largest = A[2], Second = A[1]
    else
        largest = A[1], Second = A[2];
    For i in range 3 to n {
        If A[i] > largest {
         second = largest;
        largest = A[i];
        }
        else
            if A[i] > second
                second = A[i]
    }

```

My first task was to find the number of comparisons it makes not in big-oh terms. So I said 2n-3 because it has one in the beginning and worst case the largest element is in the first two elements of the array A so from index 3 to n it has two comparisons. So 1 + 2(n-2) = 2n - 3 comparisons.

My second task was to develop an algorithm that would use less comparisons. So I broke it down with divide and conquer and said this.

```
 // start is the first index inclusive
        // finish is the last index inclusive
        // A is an array of elements
        function getGreatestAndSecondGreatestValue(A, start, finish) {
            T[] // T is an array of size 2
            if(finish - start == 1) {
                if(A[start] > A[finish]) {
                    T[0] = A[start]
                    T[1] = A[finish]
                } else {
                    T[0] = A[finish]
                    T[1] = A[start]
                }
                return T
            }

            Array1 = getGreatestAndSecondGreatestValue(A,start, start + floor((last-first)/2))
            Array2 = getGreatestAndSecondGreatestValue(A, start + ceil((last-first)/2), finish)
            return merge(Array1, Array2);
            // The greast value will be in the 0th index of the array returned and the second
            // greatest value will be in the 1 index of the array.
        }

        // this merges two arrays keeping the greatest value on the left side of the new array and
        // keeping the second greatest value on the right side of the array
        function merge(Array1, Array2) {
            MergedArray[] // array that will hold the merged results
            if(Array1[0] > Array2[0]) {
                MergedArray[0] = Array1[0]
                MergedArray[1] = max(Array[1], Array2[0])
            } else {
                MergedArray[0] = Array2[0]
                MergedArray[1] = max(Array1[0], Array2[1])
            }
            return MergedArray
        }

```

For example this say we had the array

\[1,4,5,2,7,9,10,19\]

then is divides it

\[1, 4, 5, 2\] \[7, 9, 10, 19\]

then when it reaches a length 2 is places the highest value in index 0 for arrays the size 2

\[4, 1\] \[5, 2\] \[9, 7\] \[19, 10\]

I would then proceed to merge these

\[5, 4\] \[19, 10\]

\[19, 10\]

Then the greatest value is 19 and the second greatest was 10.

I then proceeded to find the number of comparisons with recurrences.

T(n) = 2T(n) + 2

There are n leaf nodes because $ 2^{log\_{2}(n)} = n $ where $ log\_{2}(n) $ is the height of the tree. There are then n - 1 internal nodes so n + n - 1 is 2n - 1. 2 is added to every node so then it would be 4n - 2.

For some reason after using a divide and conquer algorithm I am getting a higher number of comparisons and I am not sure why. Could somebody give me some advice on why this didn't work?

# Answer
Here I present an **optimal** solution minimizing the number of comparisons.

The thing to take advantage of is the first step of the original algorithm:

```
if A[1] < A[2],
    largest = A[2], second = A[1]
else
    largest = A[1], second = A[2]

```

We can get the largest and second largest of sets of two in one comparison! So the first thing we should do is divide our array into $n/2$ pairs of two. Namely: $$p\_1 = (a\_1, a\_2), p\_2 = (a\_3, a\_4), \ldots, p\_i = (a\_{2i - 1}, a\_{2i}), \ldots, p\_{n/2} = (a\_{n-1}, a\_n)$$ For every pair $p\_i$, we can determine it's largest and second largest value in one comparison. We'll call these $p\_i.L$ and $p\_i.S$ respectively. So it takes $n/2$ comparisons to determine all of thee values for every pair.

Let's call the overall largest and second largest elements $\mathbb{L}$ and $\mathbb{S}$ respectively. We know that $\mathbb{L}$ will be among the $\\{p\_i.L\\}$'s because it will be the largest of these. We also know $\mathbb{S}$ will be among $\\{p\_i.L\\} \setminus \mathbb{L}$ **or** it could be the second largest value in the pair that $\mathbb{L}$ came from.

An example: Let our original array be: $$A = \[1,4,5,2,7,9,10,19\]$$ We then break it up into pairs: $$P = \[(1,4)(5,2)(7,9)(10,19)\]$$ We then know $\mathbb{L}$ will be in: $$W = \forall i.\\; \\{p\_i.L\\} = \\{4, 5, 9, 19\\}$$ So now we just need to find three values: $W.\mathbb{L}$ (this will be $A.\mathbb{L}$), $W.\mathbb{S}$ (this could potentially be $A.\mathbb{S}$) and $p\_i.S$ where $p\_i$ is the pair that $W.\mathbb{L}$ came from (this could also potentially be $A.\mathbb{S}$).

From our example we see $A.\mathbb{L} = W.\mathbb{L} = 19$. We then see $A.\mathbb{S}$ is either $W.\mathbb{S} = 9$ or $10$ (from the pair containing $W.\mathbb{L}$), and it is $10$.

So this turns our problem of $A$ into a subproblem of size $n/2$, $W$. Then we can run the original algorithm on this subproblem and do some extra comparisons to get $A.\mathbb{S}$ and this totals about $\approx 1.5n$ comparisons. But we can do better!

We use recursion on this subproblem instead of just using the original algorithm. So the algorithm looks like this, and will return the indices of the $A.\mathbb{L}$ and $A.\mathbb{S}$. (assume $n = 2^k$ and this is 1-indexed). The algorithm will modify the input array so we will assume $A$ to be a copy of the input.

```
L_and_S (array of length n):
  Let A = copy of input
  // base case
  if n == 2:
    if A[1] > A[2]:
      return (1, 2)
    else:
      return (2, 1)

  // recursive case
  Let W be new array length n/2 (keeps track of largest elements)
  Let M be new array length n/2 (keeps track of swaps)
  for i in 1 ... n/2:
    // swap larger element into first position of pair
    // set M[i] to 1 if pair was swapped, else 0
    // move larger element into W
    if A[2*i - 1] < A[2*i]:
      temp = A[2*i - 1]
      A[2*i - 1] = A[2*i]
      A[2*i] = temp
      M[i] = 1
    else:
      M[i] = 0
    W[i] = A[2*i - 1]

  // now recurse on W
  (j, k) = L_and_S(W)
  // map back from W to A
  j_swap = M[j]
  k_swap = M[k]
  j = 2*j - 1
  k = 2*k - 1
  if A[j + 1] > A[k]:
    k = j + 1
    k_swap = 0 - j_swap
  return (j + j_swap, k + k_swap) // account for the swap

```

We can run through the example above:

```
L_and_S([1,4,5,2,7,9,10,19]):
  // do n/2 comparisons
  A = [4,1,5,2,9,7,19,10]
  W = [4,5,9,19]
  M = [1,0,1,1]
  (j, k) = L_and_S([4,5,9,19]):
             // do n/4 comparisons
             A = [5,4,19,9]
             W = [5,19]
             M = [1,1]
             (j, k) = L_and_S([5,19]):
                        // do 1 comparison (5 > 19)
                        return (2,1)
             (j_swap, k_swap) = (1, 1)
             (j, k) = (3, 1)
             // do 1 comparison (9 > 5)
             k = 4
             k_swap = -1
             return (3 + 1, 4 - 1) = (4, 3)
  (j_swap, k_swap) = (1, 1)
  (j, k) = (7, 5)
  // do 1 comparison (10 > 9)
  k = 8
  k_swap = -1
  return (7 + 1, 8 - 1) = (8, 7)

```

We see overall this takes $n/2 + n/4 + 1 + 1 + 1 = 9 = n + 1$ comparisons! These are comparisons of the array elements, ignoring the base case comparison in the beginning.

The exact recurrence relation for number of comparisons is the following (assume $n = 2^k$): $$\begin{align} T(2) & = 1\\ T(n) & = T(\frac{n}{2}) + \frac{n}{2} + 1\\ & = 1 + \sum\_{1}^{\log\_2 n - 1} \frac{n}{2^i} + 1\\ & = \log\_2 n + \sum\_{1}^{\log\_2 n - 1} \frac{n}{2^i}\\ & = \log\_2 n + n - 2\\ & = n + \log\_2 n - 2 \end{align}$$ So we get the total number of comparisons in the worst case is $n + \log\_2 n - 2$, which is pretty good. In fact, this is a lower bound! (see here) If you include the base case comparison it adds another $\log\_2 n$ to the comparisons. Here's a table for the first few $n$:

$$\begin{array}{|c|c|} \hline n & n + \log\_2 n - 2 & 2n - 3 \\ \hline 2 & 1 & 1 \\ \hline 4 & 4 & 5 \\ \hline 8 & 9 & 13 \\ \hline 16 & 18 & 29 \\ \hline 32 & 35 & 61 \\ \hline 64 & 68 & 125 \\ \hline 128 & 133 & 253 \\ \hline 256 & 262 & 509 \\ \hline 512 & 519 & 1021 \\ \hline 1024 & 1032 & 2045 \\ \hline \end{array}$$

---

Implementation of the code in python can be found here, with test cases at the bottom.
> 14 votes

# Answer
I couldn't think of a way to code the n + log n - 2 solution, but I did see a general algorithm which I describe as follows: It takes n - 1 comparisons to find the largest element because (assume $n=2^k$) $n/2^1 + n/2^2 + ... + n/n = n - 1.$ Now the second largest must have, at some point, been compared to the largest or it wouldn't have been eliminated. Log n is the number of elements that were compared to the largest, so we have only to find the largest of a set with log n elements. Using the same method as above we find that this takes log n-1 comparisons. Then adding the two gives $(n-1)+(\log n-1) = n+\log n-2.$
> 0 votes

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


# Question
Title: Remove range of keys from Binary Search Tree in O(s+h)
I have a binary search tree with integer keys. I have to remove a range (m, n\]eZ of keys from the BST in O(s + h)

where **s** is the number of keys to remove and **h** is the height of the tree.

Attempted solution:

The naive solution is just to find nodes in range and delete them and fix the tree one-by-one, but that doesn't meet the time complexity requirement as it would be O(s * h).

I have considered the fact that if a node is within the range and its left child is in range, all of the left child's right children are in range as well as if the right child of the node is in range, the left children of the right child are also in range. Both of these facts allow you to delete the entire subtree below those children by simply unlinking it. I'm having trouble converting this information into a useful algorithm.

# Answer
It sounds like you almost have an algorithm. Find the vertex $u$ where the successor of $m$ is stored. Similarly, find the vertex $v$ where $n$ is stored (or its predecessor if $n$ is not in the BST).

Suppose that the range of vertices to delete is not empty (that is, the key of $u$ is smaller than, or equal to, the key of $v$) and let $w$ be the lowest common ancestor of $u$ and $v$.

Proceed as follows:

* Walk from $u$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=u$) and whenever $z$ is reached from its left child, delete $z$ and its right subtree. The left subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in red in the left figure. This takes time $O(h + d\_u)$, where $d\_u$ is the number of deleted vertices.
* Walk from $v$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=v$) and whenever $z$ is reached from its right child, delete $z$ and its left subtree. The right subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in blue in the left figure. This takes time $O(h + d\_v)$, where $d\_v$ is the number of deleted vertices.
* You are now left with the task of deleting $w$ (see the figure on the right), which can be done in $O(h)$ time using the standard deletion algorithm (if $w$ is a leaf, delete it immediately, otherwise swap $w$ with its predecessor/successor and then delete it).

The overall time required is then $O(h + d\_u + d\_v) = O(h + s)$.
> 2 votes

---
Tags: time-complexity, trees, binary-search-trees, big-o-notation
---