# Question
Title: Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$
i need to convert this CFL to CFG

$$ L = \\{\\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\\;\\} $$

I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm gonna blow my mind..If somebody can help i will be so grateful..

# Answer
We want to generate strings of the form $1^n 0^m 1^k 0^p$ with the same number of $0$ and $1$. This language can be generated by distinguishing two cases.

The first approach is to draw a diagram what happens if we keep counting the difference between the numbers of $0$ and $1$. This difference between the cases is whether the count drops below zero or not.

The two examples correspond to $1^5 0^3 1^2 0^4 = 1^2\\; (1^3 0^3) \\; (1^2 0^2) \\; 0^2$ and $1^2 0^4 1^5 0^3 = (1^2 0^2) (0^2 1^2) (1^3 0^3) $.

The structure of the diagram indicates which pairs of $0$ and $1$ can be generated together by the CFG.

Observe that such a diagram more or less represents how a push-down automaton would keep track of the string.

Alternatively we can do the math.

Let us assume here that $m \ge n$. This means there is a number $t$ such that $m = n+t$. Since we want to have $n+k = m+p = n+t+p$ we also need $k= t+p$.

Thus this string is of the form $1^n\\, 0^m\\, 1^k\\, 0^p = 1^n\\, 0^{n+t}\\, 1^{t+p}\\, 0^p = 1^n 0^n\\; 0^t 1^t\\; 1^p 0^p $.

Strings of this form are easy to generate by a CFG. In constructing that CFG include the requirement that $n\ge 2$, and $k,m,p \ge 1$.

The case $m\le n$ is handled analogously. The two parts of the grammar can be joined in the standard way, using the construction for union of context-free languages. See the reference question.
> 2 votes

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


# Question
Title: find edges such that if decreased by one unit, the max flow decreases as well
We are given a flow network $G = (V,E,c)$, where $c$ is the capacity function as well as a maximum flow $f\_m: E\rightarrow \mathbb R$ from $s$ to $t$. The goal is to find edges such that if decreased by one unit, the value of any max flow decreases as well. The time complexity should be $O(VE)$.

I found this question in my algorithm book.

**My attempt:** I thought all saturated edges could satisfy this condition. Then I found some counterexamples.

# Answer
> 0 votes
Copied from StackOverflow:

> Each arc `u-->v` belongs to some `s--t` min cut if and only if
>
> 1. there is no residual path from `u` to `t`,
> 2. there is no residual path from `s` to `v`, and
> 3. there is no residual path from `u` to `v`.
>
> To prove the if direction, consider the cut consisting of vertices reachable from `s` or `u` by a residual path, which is an `s--t` cut by (1), has zero residual capacity and hence is an `s--t` min cut by construction, and contains `u-->v` by (2) and (3).
>
> To prove the only if direction, we can use an `s--t` min cut that contains `u-->v` to show that, for every path from `u` to `t`, from `s` to `v`, or from `u` to `v`, some arc in the path is non-residual.
>
> This gets you to `O(n m)` time fairly easily. Maybe that's good enough -- if it isn't, there is a literature on answering offline reachability queries that might be useful.

---
Tags: network-flow, ford-fulkerson
---


# Question
Title: What's wrong with the reduction from integer programming to linear programming?
I'm confused with polynomial-time reduction and NP-hardness.

Let's say that the following integer programming is NP-hard.

$\min\_{x \in K} f(x)$, where $K$ is a finite subset of $\mathbb{N}$.

But it is a special case of the following linear programming.

$\min\_{x \in X} f(x)$, where $X$ is a compact subset of $\mathbb{R}$.

Then there is a polynomial-time reduction from IP to a special case of LP, where the solution space is restricted to integer points in $X$. Then LP is NP-hard, which is wrong.

What is wrong with this logic, especially with the reduction part?

# Answer
> 1 votes
To be precise, a polynomial-time algorithm for a linear program requires $X$ to be some *convex set* in $\mathbb{R}$ (not simply a subset of $\mathbb{R}$). Since $K \subset \mathbb{N}$ is not a convex set, an algorithm for linear program might not work for an integer linear program.

---

To see why decreasing the domian of the input space might not always simplify things; consider the following simple problem:

**P1:** Given a set $S$ of $n$ positive integers, find an integer in $S$ with minimum value.

**P2:** Given a set $S$ of $n$ positive integers, find an integer in $S \cup \\{0\\}$ with minimum value.

To solve **P1**, the algorithm needs to go through every element of $S$ (in worst case). Therefore, its time complexity is $\Theta(n)$.

To solve **P2**, the algorithm can simply output $0$ without doing any operation.

---

# Answer
> 1 votes
There are many problems in your post.

One error in your reasoning is where you say "Then LP is NP-hard". That doesn't follow from your prior statements. The complexity of "LP restricted to integer points" is different from the complexity of "LP".

In addition, you are wrong to call the second program "linear programming". It would only be linear programming if $f$ is linear and $X$ is defined by linear inequalities (i.e., it is a convex polytope).

The "problem" $\min\_{x \in X} f(x)$, where $X$ is a compact subset of $\mathbb{R}$, is not even a well-defined algorithmic problem, because you haven't described how $f$ and $X$ are represented. That must be described, as it affects the problem statement itself. Not all $f,X$ can be represented in finite space, so any finite representation inevitably limits the set of $f,X$ that can occur, which in turn changes the problem itself. Similar comments apply to your first problem as well (how is $f$ represented? not all $f$ can be represented in finite space).

Finally, linear programming and integer programming relate to problems over $\mathbb{R}^n$, not $\mathbb{R}$.

---
Tags: complexity-theory, polynomial-time-reductions
---


title: Help in proving L-Completeness

text:
# Question
Title: Help in proving L-Completeness
I'm trying to prove that the following language is L-complete A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's

So far I've managed to show that it can be solved in log space using a counter that adds 2 for every '1' and deducts 1 for every 0.

I need to prove now that every language in L is predictable logarithmically to A

# Answer
> 2 votes
Can't make a comment so have to use an answer. It's a well-known fact that every non-trivial language in $L$ is complete under log-space reduction because the reduction could be used to decide the language with only two values for a mapping.

---
Tags: complexity-theory, reductions, space-complexity
---


title: Generating Isomorphic Graphs

text:
# Question
Title: Generating Isomorphic Graphs
Is there a way of generating random isomorphic graphs for the purposes of testing tools like Nauty or BLISS? Every paper I've found says the authors had a database of certain isomorphic graphs, but I don't know how they constructed them or where I find test sets for graph isomorphism algorithms. I expect the answer to this question is no.

Is there a way to generate graphs that are *likely* to be isomorphic?

# Answer
> 7 votes
1. create a graph $G = (V, E)$ as you like
2. generate a random permutation $\sigma\in \mathfrak{S}(V)$, for example with Knuth's algorithm
3. create the graph $G' = (V, E')$ where $E' = \\{(\sigma(u), \sigma(v))\mid (u, v)\in E\\}$
4. Tada! $G$ and $G'$ are isomorphic!

# Answer
> 4 votes
While Nathaniel's response answered my question perfectly, part of my question also asked about where to find testsets for graph isomorphism algorithms. As such, I thought I'd start a list.

---
Tags: graphs, graph-isomorphism
---


# Question
Title: PDA for $\{a^nb^m \mid 0 < n \le m \le 3n\}$
I have to design a PDA that recognizes the language $\\{a^nb^m \mid 0\<n\leq m\leq3n\\}$

I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character A, the second partition being the size of $2n$ with character B, and the third partition size of $n$ with character A.

I got stuck with this idea. Can anyone help me with this?

# Answer
Roughly speaking, the PDA consists of two phases.

During the first phase, the PDA reads $a$s. For each $a$ that it reads, it nondeterministically pushes either $A$, or $AA$, or $AAA$ to the stack.

During the second phase, the PDA reads $b$s, popping one $A$ per $b$ read. At the end, the stack needs to be empty.

Details left to you.
> 3 votes

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


title: Reduce-reduce conflict in SLR vs LALR

text:
# Question
Title: Reduce-reduce conflict in SLR vs LALR
**I was wondering if I could say any of the following is true.**

Given a grammar $G$,

1. If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$.
2. If the SLR parser has reduce-reduce conflict for $G$, then the LALR parser also has reduce-reduce conflict.
3. The LALR parser has reduce-reduce conflict for $G$ if and only if SLR also has reduce-reduce conflict for $G$.

Since SLR $\subset$ LALR, I think **point 1** is true. Is this wrong?

Further more, based on a few examples that I have come across it seems like **points 2 & 3** are also true. Is this correct. If so, could you please point me to the proof. If not could you please give me a counter example?

# Answer
> 1 votes
***Note:*** I'm assuming that when you wrote $SLR$ and $LALR$ that you actually meant $SLR(1)$ and $LALR(1)$.

It is certainly the case that if a grammar shows a conflict in an $LALR(1)$ automaton, that conflict will also be present in the $SLR(1)$ automaton, because the two automata have the same states and the $LALR(1)$ lookaheads for any production are a subset of the $SLR(1)$ lookaheads.

The remaining two proposals are false, as can be demonstrated by the same counter-example.

The classic example of an $LALR(1)$ grammar which is not $SLR(1)$ (taken directly from the Dragon book) is the abstraction of a grammar which attempts to discriminate between "lvalue" and "rvalue" syntaxes. (Roughly speaking, an "lvalue" is something which can be assigned to, so-named because it can appear on the **l**eft-hand side of an assignment operator; an "rvalue" is a value which cannot be assigned to, which means that it can *only* appear on the **r**ight-hand side.

It's usually convenient to include the production $R\to L$, which says that "lvalues" can also appear on the right-hand side of the assignment operator. But it is precisely this fact which leads to the conflict:

$$\begin{align}S &\to L = R\\ S &\to R\\ L &\to * R\\ L &\to id\\ R &\to L\\ \end{align}$$ As the Dragon book points out, that grammar leads to an $SLR(1)$ conflict in the state reached from $\text{GOTO}(I\_0, L)$. That state ($I\_2$ in the Dragon book exposition) contains the items $S\to L\\;\cdot = R$ and $R\to L\\;\cdot$. Since $=$ is in $\text{FOLLOW}(R)$, the state has a shift-reduce conflict. In the $LALR(1)$ automaton, that conflict is resolved.

Since that's a shift-reduce conflict, it doesn't address your question, which concerns reduce-reduce conflicts. But it's easy to modify the grammar slightly in order to turn the shift-reduce conflict into a reduce-reduce conflict. All that's necessary is to introduce a new intermediate non-terminal:

$$\begin{align}S &\to L' = R\\ S &\to R\\ L' &\to L\\ L &\to * R\\ L &\to id\\ R &\to L\\ \end{align}$$

That changes the itemset for state $I\_2$ to include the items $\\{L'\to L\\;\cdot, R\to L\\;\cdot\\}$, which is now an $SLR(1)$ reduce-reduce conflict, for the same reason that the previous example had a shift-reduce conflict. Also for the same reason, the $LALR(1)$ algorithm resolves that conflict using more precisely-computed lookahead sets.

That disproves your statement 2; since the "if and only if" in statement 3 requires both statement 1 and statement 2 to be true, it also disproves statement 3.

---
Tags: context-free, formal-grammars, compilers, parsers, lr-k
---


title: Bit times and propagation delay

text:
# Question
Title: Bit times and propagation delay
Nodes A and B are accessing a shared medium using CSMA/CD, with a propagation delay of 245-bit times between them (i.e., propagation delay equals the amount of time to transmit 245 bits). The minimum frame size is 64 bytes. Suppose node begins transmitting a frame at = 0 bit time. Before A finishes, node B begins transmitting a frame. Assume no other nodes are active.

What is the latest time by which B can begin its transmission?

Attempt: Considering that t=512 bit times is the time at which A finishes transmission, shouldn't the latest time by which B begins its transmission be at t=245 bit time? (At t=1, 1st bit is pushed on the link, and at t=245 bit time, this is the last "timing" that B can start transmitting before it senses that A is transmitting). However, the answer given is 244-bit time and I do not understand why.

# Answer
> 1 votes
I would say that at t=0 the first bit would begin getting pushed on the link, which would imply that the 245th bit would begin getting pushed at t=244. Thus you'd want to start pushing at t=244.

Disclaimer: I know nothing of networking and little of comp sci but hey, I thought I'd give the logic a whirl. I could be completely wrong.

# Answer
> 1 votes
B does carrier sensing, and, if the medium is not free, it does not transmit.

Since A sent its bit at t=0, at t=245 this bit should reach B, and B would sense that the medium is not free anymore. So I would say 244 is the last time B would sence the medium as free.

---
Tags: computer-networks
---


# Question
Title: How to find the maximum number of square groups in a board
I'm stuck with the following problem:
Given an n\*m board, find the maximum number of square groups that can be positioned on the board.
What are square groups?

* They contain 4 distinct squares named: a, b, c, d
* a should be the neighbor of b
* b should be the neighbor of c
* c should be the neighbor of d
* Two squares are considered neighbors if they are adjacent to each other vertically or horizontally **but not diagonally**.
* Each square can belong to only one square group

I guess the problem should be handled by max flow network algorithms but I don't know how to model it to a graph.
Any help would be appreciated.

**EDIT**:
The answer is ⌊mn/4⌋, but we need to prove it with Max Flow Network.

# Answer
First of all, since each square consists of $4$ cells and an $n \times m$ matrix contains $nm$ cells, you can clearly fit at most $\lfloor nm/4 \rfloor$ many different cells.

If $n,m$ are both even, then you can fit $nm/4$ different square-shaped squares. In all other cases, you have to be more cunning. I won't ruin the joy of the puzzle by explaining how to handle the other cases.
> 1 votes

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


title: Check Welzl's algorithm time complexity

text:
# Question
Title: Check Welzl's algorithm time complexity
From the wiki this is the algorithm and we know that final complexity is O(n) but how we reached to this , is my problem :

```
algorithm welzl is
    input: Finite sets P and R of points in the plane |R| ≤ 3.
    output: Minimal disk enclosing P with R on the boundary.

   part 1: if P is empty or |R| = 3 then
                  return trivial(R)
   part 2: choose p in P (randomly and uniformly)
   part 3: D := welzl(P − {p}, R)
   part 4: if p is in D then
                  return D

   part 5: return welzl(P − {p}, R ∪ {p})

```

**My try:**
Easiest one, part 1 has O(1) time.
part 2 has O(1) time.
part 3 is something like T(n) = T(n-1).
part 4 is in O(1) time.
part 5 is something like T(n) = T(n-1) because we eliminate 1 point and increase R but we will work more with P so that would be the recursive equation.

If I writed correctly my analysis(and I'm sure it have incorrect parts) I don't know how to combine this 5 parts time complexity inorder to reach O(n).is the final equation like this?:$$T(n) = 2T(n-1)$$
but the final answer will be exponential .
If I made any mistake can someone help me please?

# Answer
Note that the expected running time analysis is $O(n)$. It is given in the original paper itself (Section 2).

Here, I am simply analyzing the worst-case time complexity of the algorithm. Note that Part $3$ and Part $5$ are not the same.

Let $T(n,r)$ denote the complexity of algorithm when $|P| = n$ and $|R| = r$. Then, Part $3$ corresponds to $T(n-1,r)$ and Part $4$ corresponds to $T(n-1,r+1)$.

\begin{align} T(n,r) &= T(n-1,r) + T(n-1,r+1) + O(1) \\ &= T(n-2,r) + T(n-2,r+1) + T(n-1,r+1) + O(1) \\ &= \dotsc \\ &\leq n \cdot T(n,r+1) + O(1) \quad \textrm{(since $T(0,r) = O(1)$)}\\ &\leq n^2 \cdot T(n,r+2) + O(n) \\ &\leq n^3 \cdot T(n,r+3) + O(n^2) \\  \end{align}

At the start of the algorithm, we have $r = 0$. Also, $T(n,3) = O(1)$ corresponding to Part $1$. Therefore, $T(n,0) = O(n^3) $ is the worst case time complexity of the algorithm.
> 2 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, randomized-algorithms
---


# Question
Title: Can I reduce from the recognition version of one probem to another without knowing the exact parameter?
I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(2), 135-139" and from what I understand, they prove that SET-ECC is NP-complete by constructing a graph G' and showing that (G, k)$\in$ SET-NCC iff (G', k') $\in$ SET-ECC, with $k'= k(e + 1) + e$. However, the size of the ECC of G' could be smaller than k', and in fact, we don't know exactly what it is. I just want to confirm that I understood the paper correctly, so my question is, for a reduction of this type, is it enough to have an upper bound of k', as long as k' depends on k?

# Answer
> 1 votes
A mapping $f$ from instances of a decision problem $A$ to instances of a decision problem $B$ is a *reduction* if $x \in A$ iff $f(x) \in B$.

In your case, instances of both problems are of the form $(G,k)$. Such instances are Yes instances if there is a clique-cover of $G$ of size at most $k$.

Thus a function mapping $(G,k)$ to $(G',k')$ is a reduction between SET-NCC and SET-ECC if the following holds: $G$ has a node-clique-cover of size at most $k$ iff $G'$ has an edge-clique-cover of size at most $k'$.

---
Tags: complexity-theory, reductions, decision-problem, polynomial-time-reductions
---


# Question
Title: Height of AVL tree with balance condition of 2
The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed imbalance condition between two child nodes would be 2), how could I find the maximum height of such a tree. Would I need to solve some kind of recurrence relation or fibonacci sequence. Is there an easier way of figuring out the maximum height of a tree with a balance condition of 2 by using what we already know? Thanks.

# Answer
Let $T\_h$ denote the minimal number of nodes that a standard AVL tree of height $h$ could have.

If $h\>0$, then there's the root and two subtrees. One of the subtrees must have height $h-1$. The other must have height at least $h-2$, otherwise it's not a valid AVL tree. So we have the recurrence:

$$T\_h = T\_{h-1} + T\_{h-2} + 1$$

And we can throw in $T\_0 = 0$ and $T\_1 = 1$ for obvious reasons.

The easy way to solve the recurrence is to denote $F\_h = T\_h + 1$. Then:

$$\begin{align\*}F\_0 & = 1 \\ F\_1 & = 2 \\ F\_h & = F\_{h-1} + F\_{h-2}\end{align\*}$$

That is, they're Fibonacci numbers with the sequence offset by 3.

Since:

$$F\_h \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{h+3}$$

Inverting this, we get:

$$h \approx \frac{1}{\log \left( \frac{1 + \sqrt{5}}{2} \right)} \log \left( T\_h \right) + 3$$

And that is where the 1.44 comes from.

So what you need is to solve the recurrence:

$$U\_h = U\_{h-1} + U\_{h-3} + 1$$

with suitable initial conditions.

If you can't think of a clever way to do this, you can do it the not-clever-but-always-works way by observing that:

$$\begin{bmatrix} U\_h \\ U\_{h-1} \\ U\_{h-2} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix} U\_{h-1} \\ U\_{h-2} \\ U\_{h-3} \\ 1\end{bmatrix}$$

Therefore:

$$\begin{bmatrix} U\_{h+2} \\ U\_{h+1} \\ U\_{h} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}^{h} \begin{bmatrix} U\_{2} \\ U\_{1} \\ U\_{0} \\ 1\end{bmatrix}$$

Next, perform eigendecomposition on the matrix. Let:

$$M = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$$

Suppose you can find a matrix $Q$ and a diagonal matrix $\Lambda$ such that $M = Q \Lambda Q^{-1}$. Then:

$$M^h = Q \Lambda^h Q^{-1}$$

Taking the power of a diagonal matrix is trivial, and this should give you a closed form. You will then need to find an approximate inverse to solve your problem.
> 2 votes

# Answer
We can solve this **mathematically** as :

## **Defining Worst Case**

Now, in any `Binary Tree`, time complexity of `searching` is $O(h)$ where $h$ is ***height*** of the `Binary Tree`.
Now, for worst case, we want to find ***Maximum Height.***

> In case of simple `Binary Search Tree` with no Balancing Factor Condition on Nodes, this maximum height can be $n$ or $n+1$ *(depending on convention whether height of single node tree will be 1 or 0)* where $n$ is number of nodes.

Thus, we can say that `given number of nodes, worst case is maximum height`.

Interestingly, we can also say that `given height of a tree, the worst case is minimum nodes`. As even for such minimum number of nodes, we might have to traverse down the tree of height $h$, which we also have to do for maximum number of nodes.

Thus, the intuition should be clear that **Given Height of Tree, the worst case is minimum number of nodes.**

## **Applying this Concept on GIVEN Tree**

1. Let us try to construct **Given Tree** of Height $H$ such that **number of nodes** in the tree is **minimum**.

> Here we will exploit the fact that Binary Tree is a Recursive Data Structure (A Binary Tree can be defined in terms of Binary Tree)

2. We will use the notation **$N\_H$** to denote Minimum Number of Nodes in **Given Tree** of height $H$
3. We will create a **Root Node**
4. To **Left** (or Right) of Root, add a **subtree** of height `H-1` (exploiting Recursive Property). So that number of nodes in entire tree is minimum, the number of node in **Left** (or Right) **subtree** should also be minimum. Thus **$N\_H$** is a function of **$N\_{H-1}$**
5. Do we need to add anything to **Right** (or Left)?
Yes! *Because there is restriction of Balancing Factor on Nodes.*
We need to add subtree on **Right** (or Left). **What should be it's height?**

**$H?$**

> **No,** then height of entire tree will become $H+1$

**$H-1?$**

> **Permitted!** since Balancing Factor of Root will become $0$

**$H-2?$**

> **Permitted!** since Balancing Factor of Root will be $1$

**$H-3?$**

> **Permitted!** since Balancing Factor of Root will be $2$

**$H-4?$**

> **Not Permitted!** since Balancing Factor of Root will become $3$

We want minimum number of nodes, so out of `H-1`, `H-2` and `H-3`, we will choose $H-3$. So that number of nodes in entire tree is minimum, the number of node in **Right** (or Left) **subtree** should also be minimum. Thus **$N\_{H}$** is **also** a function of **$N\_{H-3}$**
6. Thus, to construct **Given Tree** of Height $H$ such that **number of nodes** in the tree is **minimum**, we can have LEFT subtree as **Given Tree** of Height $H-1$ such that **number of nodes** is **minimum** and can have RIGHT subtree as **Given Tree** of Height $H-3$ such that **number of nodes** in it is also **minimum**, and can add one root node. Our tree will look like

Thus, we can form **Recurrence Relation** as

$$N\_{H} = N\_{H-1} + N\_{H-3}+ 1$$
with **base condition** as $$N\_{0} = 1$$ $$N\_{1} = 2$$ $$N\_{2} = 3$$

> To create BST of height 0, we need to add one node. Throughout the answer we will use this convention

7. Now, this **Recurrence Relation** is **Difficult** to Solve. But courtesy to this answer, we can conclude that $$N\_{H} \gt (\sqrt2)^H$$
8. Now, let $n$ be the number of nodes in the **Given Tree** Then, $$n \geq N\_H$$ $$n \geq (\sqrt2)^H$$ $$\log\_{\sqrt2} n \geq H$$
$$H \leq \log\_{\sqrt2} n$$ $$H \leq 2\log\_{2} n$$

Therefore, $H=O(\log(n))$
Or $O(H) = O(\log(n))$

Thus, **Worst Case Time Complexity** for **Searching** in this Given Tree will be **$O(\log(n))$**

Hence, Proved Mathematically!
> 0 votes

---
Tags: binary-trees, discrete-mathematics
---


# Question
Title: Looking for a proof on why my algorithm in codeforces works
I'm trying prove the correctness of my algorithm.
This is the problem in codeforces: https://codeforces.com/contest/1428/problem/C

Here's my code in C++ which was accepted:

```
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
    int num, ans, top;
    string s;

    cin >> num;

    for (int i = 0; i < num; i++)
    {
        cin >> s;

        ans = s.size();

        top = 0; // meaning no characters behind

        for (int j = 0; j < s.size(); j++)
        {
            if (top == 0) top++;
            else if (s[j] == 'A') top++;
            else { ans -= 2; top--; }
        }

        cout << ans << endl;
    }
    return 0;
}

```

It's easy to see that if the string still contains B as the "middle character", we can always make more deletions. And in order to make this string as short as possible, we will always try to delete B with an A(So, we still have more B(s) to continue the delete process).

So, the idea to solve this problem is simple: While tracing through the string, we have a variable called *top* which "collects" all the A(s) and the first character of the string(the original one or the string after some deletion when top = 0). And whenever we encounter a B, it's always nice if we have collected at least one A(top \>= 2) or we have to reluctantly erase this B with the first character of the string without knowing whether it's an A or B.

An algorithm correctly solves this problem if and only if:

1. It delete all middle B(s)
2. It makes the string as short as possible

But how do we prove the correctness of this algorithm? Clearly, my algorithm does the "right thing" when top \>= 2. But when top = 1, how do I prove that the behavior of erasing B **with the first character of the string without knowing whether it's an A or B** is correct?

My further reasoning goes like this:
In other words, are there any other algorithms that erase the same amount of AB(s) without confronting this reluctance?

Here's what I've tried to come up with:

We only consider the case when the "real reluctance" happens. What I mean is when the first character of the string is B.

So let's say, there was such "better" and correct algorithm(call it X). In other words:

1. X erases all AB(s) that our old algorithm erases.
2. There exists moments when our old algorithm encounters a "real reluctance" but X finds an AB to erase.

Question: The thing is where do all those AB(s) lie ?

> (First character A)A...A B A...A B ... B\*(characters of the original string)
> -------------------^----------------^
> -------------------|----bound Y----|

B\* is where the reluctance happens.

What has to be pointed out first is that according to condition 1, X is not allowed to erase a B outside bound Y with an A inside bound Y. Because otherwise, there exists some B inside bound Y that can't be erased which proves X a wrong algorithm. (\*)

Returning to our question, if for every such moment, AB lies entirely inside bound Y, then our old algorithm erases all the AB(s) that X does. So, X can not be better.

So, there exists a moment where AB lies outside Y and statisfies (\*). But this AB will, surely, soon be erased by our algorithm(this can be easily imagined and proved).

B\*...A...B...(this A will collected by top and will be matched with the latter B).
So, X can not be better.

Therefore, our algorithm is correct. There're no other algorithms that will make the string shorter.

# Answer
> 1 votes
An easy-to-see algorithm that is potentially much simpler than yours but runs on the same idea is just to simply remove all "AB" pairs first, then remove all "BB" pairs.

As you observed, we must have a B in the center of our string in order to keep making it shorter -- and to keep the most B's in the center as opposed to just erasing them all, we erase all of the "AB" pairs first. We can also observe that removing a "BB" pair before an "AB" pair can cause us to return the wrong answer (ex. "AAABB" -\> "AAA" instead of "A") but removing an "AB" pair before a "BB" pair cannot increase out answer, as for every optimal solution that removes a "BB" pair in the center (with at least one A before it) we can create another optimal solution by simply removing the "AB" instead of the "BB".

That being said, your solution does work for when top = 1, as, if it's an "AB" pair, it obviously should be removed in accordance to the above statement, and if it's a "BB" pair, there will be no "AB" pairs before it to remove in order to create another optimal solution (as there are no A's before it), thus removing the "BB" must be part of the optimal solution.

My solution that also got accepted:

```
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <chrono>

using namespace std;

void remove_substr(string& s, string t) {
    for (int i {}; i < (int)s.size()-1;)
        if (s.substr(i, 2) == t) {
            s.erase(i, 2);
            if (i != 0) i--;
        } else i++;
}

int main() {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        remove_substr(s, "AB");
        remove_substr(s, "BB");
        cout << s.size() << "\n";
    }
    return 0;
}

```

---
Tags: correctness-proof, c++
---


# Question
Title: Is there a way to show that if the description of a language depends on some kind of global structure, then it isn't a CFL?
So I've been reading Sipser's theory of computation book, and I've come across the pumping lemma for context-free languages, which as a reminder says that if a language is context-free, then there is some length p such that all strings longer than p can be represented in the form

$s = uv^i x y^i z$

and be pumped and remain in the language.

He then goes on to show that the languages $a^n b^n c^n$, as well as $a^i b^j c^k$ (for $i \leq j \leq k$) are both not context-free, using the pumping lemma.

While the proofs for both are just casework, to me the conceptual point here is that if your language relies on some kind of global structure in its description, then it's very unlikely to be context-free (since CFGs are just applying rules locally).

Is there some way to formalize this idea?

# Answer
> 1 votes
No, because the idea is wrong (or at very least, too vague and imprecise to be useful in its current form). As Yuval Filmus hints, the language $\\{a^n b^n \mid n \in \mathbb{N}\\}$ appears to have "global structure", yet is context-free.

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


# Question
Title: Logic foundation for formal verification
What types of logic should one study as foundation before diving into the area of software verification? What I can think of are:

1. Hoare Logic (for proving correctness of imperative programs)
2. Linear Temporal Logic (to model-check programs)

What can be others?

# Answer
> 2 votes
It is helpful to know basic mathematics and logic. But I would suggest that you go ahead and study software verification now, and learn additional logical background as needed. There is an unending literature on logic that one could potentially learn, but I think better to learn it on demand.

---
Tags: formal-methods, software-verification, linear-temporal-logic, hoare-logic
---


title: Queue for two types using 2 queues?

text:
# Question
Title: Queue for two types using 2 queues?
I'm reading the book Cracking the Code.

The answer for this question suggests a solution using timestamps and two separate queues. This is straightforward and involves simply enqueuing into the appropriate queues. Dequeuing oldest involves checking timestamps of front of both queues and removing the oldest.

I'm wondering if there is a way to do this without using an additional timestamp field.

My approach is to use two queues, `main` and `backup`

## Enqueue

I simply push into `backup`

## Dequeue Dog/Cat aka. specific type dequeue

I check if front of `main` has this type. If not or if `main` is empty, then I go to `backup`.

If `backup` contains the right type, `dequeue` it

If `backup` does not contain it, then shift from `backup` to `main` i.e. `dequeue` from `backup` and `enqueue` to `main`

## Dequeue oldest pet

`dequeue` from `main` if `main` has elements

If `main` is empty, `dequeue` from `backup`

# Answer
> 2 votes
Your solution seems to have higher time complexity than needed. If you have $n$ dogs and then $n$ cats then dequeuing all cats will cost you $O(n^2)$ as you need to go through dogs first.

I'd go with three queues: all animals, dogs, cats.

Enqueue: Create an instance of dog/cat, push into all animals queue. Next, push the same instance to the dog/cat queue appropriately.

Dequeue Dog/Cat: just dequeue from dog/cat queue. Do not touch all animals queue.

Dequeue oldest: dequeue from all animals queue. If it's a dog then peek a dog from the dog queue. If those are the same instances - dequeue from dog queue and return. Otherwise discard the dog from the all animals queue and repeat.

Time complexity: each animal is inserted exactly once to each queue and removed exactly once so amortized time is $O(1)$ for enqueue and $O(1)$ for dequeue.

---
Tags: data-structures, algorithm-design, queues
---


# Question
Title: Removing and adding edges from spanning tree
Let $T\_1$ and $T\_2$ be two spanning trees. If $a$ is an edge in $T\_1$ that is not in $T\_2$, and $b$ is an edge in $T\_2$ that is no in $T\_1$. I want to prove that $T\_1 - \\{ a\\} + \\{ b\\}$ is a spanning tree. I have an idea of what is happening but I don't know exactly how to write the proof. I know that $T\_1 - \\{ a\\}$ creates a partition of the vertices, but how can I conclude that adding $b$ to $T\_1 - \\{ a\\}$ is necessarily a spanning tree?

# Answer
> 1 votes
You want to prove a false statement. Its possible that T -{a} + {b} is not spanning tree. Consider the below example

Lets say T1 is-

```
       1
      / \
     2   3
    /    /
   5    4
  /
 6

```

Lets say T2 is-

```
        1
         \
      2   3
     /|\  /
    5 6  4

```

both are spanning tree but if we replace edge 1-2 in T1 with edge 2-6 in T2 then it will not be spanning tree anymore. QED

---
Tags: algorithms, graphs, trees, discrete-mathematics
---


# Question
Title: EM algorithm - What happens with the standard deviation?
# What have you tried?

So I watched this video. According to the video, we've to calculate the variance $\sigma^2$ as follows: $$ \sigma\_{k}^{2} = \frac { p\_{1} \left(x\_{1} - \mu\_{k\_1}\right)^{2} + \ldots + p\_{n} \left(x\_{n} \- \mu\_{k\_n}\right)^{2} } { p\_{1} + p\_{2} + \ldots + p\_{n} } $$

Where

* $k$ is the index of the current Gaussian class.
* $p$ represents the possibility of one point of the set
* $n$ is the amount of points in the set

# So what's your question?

I don't understand, why we have to use $\mu\_{1}$, $\mu\_{2}$, $\ldots$, $\mu\_{n}$. I expected to calculate it follows: $$ \sigma\_{k}^{2} = \frac { p\_{1} \left(x\_{1} - \mu\_k\right)^{2} + \ldots + p\_{n} \left(x\_{n} \- \mu\_k\right)^{2} } { p\_{1} + p\_{2} + \ldots + p\_{n} } $$

Because why do I have to use the "current-calculated" mean of the Gaussian and not the "final" one?

# Answer
Here's the answer of @plop:

> At the very time point in the video that your link takes you the speaker mentions that there is a typo.
> 1 votes

---
Tags: algorithms, mathematical-programming, statistics
---


# Question
Title: Compute the edit distance between two words in which substitution is not allowed
How do I compute the edit distance between two words in which substitution is not allowed?

The allowed operations include insertion (with cost 1) and deletion (with cost 1), but not substitution.

How is this supposed to be computed without substitution?

# Answer
You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.

Let $u=u\_1…u\_n$ and $v=v\_1…v\_m$ be two words. We want to build a $(n+1)\times(m+1)$ matrix $M$ such that for $0\leq i\leq n$ and $0\leq j \leq m$, $M\[i\]\[j\]$ is the edit distance between $u\_1…u\_i$ (or $\varepsilon$ if $i = 0$) and $v\_1…v\_j$. The answer is then $M\[n\]\[m\]$.

Now note that for $0\< i\leq n$ and $0\< j \leq m$:

* if $u\_i = v\_j$, then $M\[i\]\[j\] = \min\left\\{\begin{array}{rl}M\[i-1\]\[j\]+1 & (\text{deletion of }u\_i)\\M\[i\]\[j-1\]+1&(\text{insertion of }v\_j)\\M\[i-1\]\[j-1\] & (\text{no modification})\end{array}\right.$
* otherwise, $M\[i\]\[j\] = \min\left\\{\begin{array}{rl}M\[i-1\]\[j\]+1 & (\text{deletion of }u\_i)\\M\[i\]\[j-1\]+1&(\text{insertion of }v\_j)\end{array}\right.$
> 1 votes

# Answer
This is a straighforward modification of the classical dynamic programming algorithm.

Let the first string be $s = s\_1 s\_2 \dots s\_n$ and the second string be $t = t\_1 t\_2 \dots t\_m$. In the dynamic programming algorithm you define $D\[i\]\[j\]$ as the edit distance between $s\_1 s\_2 \dots s\_i$ and $t\_1 t\_2 \dots t\_j$. As a consequence, the edit distance between $s$ and $t$ will be $D\[n\]\[m\]$.

The bases cases are $D\[0\]\[j\]=j$ and $D\[i\]\[0\]=i$ (for any $i = 0, \dots, n$ and $j=0, \dots, m$), and the recursive formula (for $i\>0$ and $j\>0$) is:

$$ D\[i\]\[j\] = \min \begin{cases} 1 + D\[i-1\]\[j\] & \mbox{ deletion of $s\_i$};\\ 1 + D\[i\]\[j-1\] & \mbox{ insertion of $t\_j$};\\ 1\_{s\_i \neq t\_j} + D\[i-1\]\[j-1\] & \mbox{ substitution of $s\_i$ with $t\_j$}. \end{cases}, $$ where $1\_{s\_i \neq t\_j}$ is $1$ if $s\_i \neq t\_j$ and $0$ otherwise.

You can simply modify the above formula by not contemplating the last case when $s\_i \neq t\_j$, i.e.: $$D\[i\]\[j\] = \min \begin{cases} 1 + D\[i-1\]\[j\] \\ 1 + D\[i\]\[j-1\] \\ D\[i-1\]\[j-1\] & \mbox{only if $s\_i = t\_j$}. \end{cases} $$
> 0 votes

# Answer
According to wikipedia, deletion, insertion, and substitution can assign separate costs. We can simply set substitutions cost to deletion plus insertion, which is 2 if deletion and insertion are both 1.

Here is the java code:

```
public static int deleteAddEditDistance(String s1, String s2) {
    if (s1 == null) {
        return 0;
    } else if (s2 == null) {
        return 0;
    } else if (s1.equals(s2)) {
        return 0;
    } else if (s1.length() == 0) {
        return s2.length();
    } else if (s2.length() == 0) {
        return s1.length();
    } else {
        int[] v0 = new int[s2.length() + 1];
        int[] v1 = new int[s2.length() + 1];

        int i;
        for (i = 0; i < v0.length; v0[i] = i++) {
        }

        for (i = 0; i < s1.length(); ++i) {
            v1[0] = i + 1;
            for (int j = 0; j < s2.length(); ++j) {
                int sub_cost = 2; // substitute cost
                int add_cost = 1;
                int del_cost = 1;
                if (s1.charAt(i) == s2.charAt(j)) {
                    v1[j + 1] = v0[j];
                } else {
                    v1[j + 1] = Math.min(v1[j] + add_cost, Math.min(v0[j + 1] + del_cost, v0[j] + sub_cost));
                }
            }

            int[] vtemp = v0;
            v0 = v1;
            v1 = vtemp;
        }
        return v0[s2.length()];
    }
}

```
> 0 votes

---
Tags: natural-language-processing, edit-distance
---


# Question
Title: Set of Pareto-optimal paths, in a graph where edges have both length and cost
Suppose I have a graph $G=(V,E)$, where each edge $e$ has both a non-negative length $\ell(e)$ and a non-negative cost $c(e)$. Given a start node $s$ and a destination node $t$, I want to find a set of Pareto-optimal paths $s \leadsto t$. In other words, for each budget $b$ in some set (say $\\{0,1,2,\dots,B\\}$), I want to find the shortest path $s \leadsto t$ whose cost is at most $b$. The length of a path is the sum of the lengths of its edges, and the cost of a path is the sum of the costs of its edges.

Is there an efficient algorithm to solve this problem?

# Answer
I will outline two solutions. Both have the same asymptotic worst-case running time, namely $O(B \cdot |E| \cdot \log (B\cdot |V|))$, but the second might be slightly more efficient in practice.

# Increase the size of the graph

Create a new graph $G'$ where edges have only lengths, not costs. Each vertex is of the form $\langle v,b \rangle$ where $v \in V$ is a vertex in the original graph and $b$ is a cost (the "cost so far"). For each edge $(u,v) \in E$ in the original graph and each $b$, add an edge $\langle u,b \rangle \to \langle v,b+c(u,v) \rangle$ whose length is given by $\ell(u,v)$.

Now, for each $b$, find the shortest path from $\langle s,0 \rangle$ to $\langle t,b \rangle$. This can be done all at once by using Dijkstra's algorithm in $G'$, starting at $\langle s,0 \rangle$; it will compute the distance to every vertex of $G'$ in time linear in the size of $G'$, and thus will compute the length of the shortest path to $\langle t,b \rangle$ for each $b$. The distance to $\langle t,b \rangle$ is then the length of the shortest path $s \leadsto t$ in $G$ that uses budget $b$.

# Modify Dijkstra's algorithm

Normally, Dijkstra's algorithm maintains a distance $d\[v\]$ to each vertex $v$, which records the length of the shortest path $s \leadsto v$. We will maintain a "distance map" $d\[v\]$, which maps a budget $b$ to the length of the shortest path $s \leadsto v$ that uses budget $\le b$. We'll ensure that the "distance map" keeps only the Pareto-optimal entries in the map (e.g., if you have two entries $b\_1 \mapsto \ell\_1$ and $b\_2 \mapsto \ell\_2$ in the distance map where $b\_1 \le b\_2$ and $\ell\_1 \le \ell\_2$, then we delete the second entry). Also, we'll delete any entries in the distance map where the budget $b$ is greater than $B$.

Now, run Dijkstra's algorithm on $G$. Dijkstra's algorithm performs operations on distances, and we will convert them to operations on distance maps:

* Where standard presentations of Dijkstra's algorithm write $d\[u\] + \ell(u,v)$, we will instead create a new distance map. For each entry $b \mapsto \ell$ in $d\[u\]$, the new distance map has an entry $b + c(u,v) \mapsto \ell + \ell(u,v)$.
* Where standard presentations of Dijkstra's algorithm write "if $d' \le d\[v\]$, set $d\[v\] := d'$", we will instead merge the two distance maps, as $d\[v\] := \min(d\[v\], d')$. In particular, we just add all the entries of $d'$ to $d\[v\]$, and then reduce $d\[v\]$ to be Pareto-optimal.

Hopefully with these two ideas, it will be clear how to create the modified Dijkstra's algorithm. You might notice that this is doing more or less the same thing as the first algorithm, but now bundling a whole bunch of vertices of $G'$ together into a single distance map.

The primary benefit of the second algorithm is that reducing each distance map to only include Pareto-optimal entries at each point might decrease the amount of computation you need to do, since we prune paths that we already know are worse than some other path we've previously explored.

What data structure can you use to represent distance maps, so that all operations are efficient? One plausible choice is a balanced binary search tree, keyed on $b$. Then all operations mentioned above can be performed efficiently.
> 2 votes

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


# Question
Title: Find repeated patterns in a string via lossy compression
## Description

The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the string (information loss VS description length). For simplicity, I'll be using a binary string, though the solution should tolerate at least the English alphabet \[a-zA-Z\]. The output of the algorithm is "compressed" and "error" columns as shown below. If neither the compression ratio (length) nor the error is improved, the candidate should not be included in the output. In other words, the output should be the Pareto-optimal front: e.g., for each length, I want the encoding of that length that has the fewest errors. The "error" corresponds to the Hamming distance between the original and decoded strings.

This problem is similar to searching repeated substrings in a string indicated in this question: Algorithm to find repeated patterns in a large string. But my approach is (1) **lossy** and (2) not parametrized by the minimum and maximum chunk lengths (all candidates are to output).

## Examples

Let's consider the string `100100100` of length 9. Special symbols `[` and `]` are also counted (otherwise, how the decoder would know the beginning and the end of a "repeat N times" program?).

| compressed | length | errors | description |
| --- | --- | --- | --- |
| \[100\]3 | 6 | 0 | repeat 100 three times |
| \[0\]9 | 4 | 3 | repeat 0 nine times; it will make three substitutions (errors) of `1 -> 0`. |
| \[1\]9 | 4 | 6 | repeat 1 nine times; it has the same length as `[0]9` but with more errors and therefore must be excluded from the output |

The string `1001001000100` of length 13 can be decomposed into:

| compressed | length | errors | description |
| --- | --- | --- | --- |
| (\[100\]3)0100 | 10 | 0 | Don't count `()`: an elaborate version of the "repeat N times" instruction can perhaps avoid unnecessary brackets |
| \[100\]4 | 6 | 1 | `0` is omitted |
| \[0\]13 | 4 | 4 | For simplicity, assume the count `13` as a single byte |

## What I've tried

I've thought of the Run-length coding but (1) it's lossless by design and (2) the problem lies in identifying the pattern (inside the `[]` brackets) to repeat. The LZ77 algorithm is somewhat similar but it's not optimal - it starts compressing right from the beginning and goes in online fashion: run the string only once and output the result without returning back and re-iterating. Also, LZ77 has a fixed-size dictionary and the look-ahead buffer.

Probably, suffix trees suit well here but I don't know how to extract the repeated patterns from the edges of a suffix tree. An online resource to play with suffix trees is here: https://visualgo.net/en/suffixtree. And it's also lossless by design.

---

## Motivation

This section is for curious readers.

The task is not to compress a string as much as possible but rather make use of compression techniques in AI.

The problem is motivated by an example of an agent moving in a circular Turing Tape only in the right direction and trying to predict the next *k* symbols (where the agent might expect some reward).

### Why lossy?

You haven't probably spotted an extra `0` in the second example above the first time you read the string, have you? This is because the context to the left and to the right - `100` \- soaks up an extra zero in the middle `1000`. Our ability to simplify (read "to compress lossy") is crucial in inferring in noisy environments. The word "context" implies the use of the neighborhood at each cursor position (like in a convolution operation), and perhaps parsing a string only from left to right won't yield a fruitful solution.

Ideally, the algorithm shall indicate where and what kind of substitution is taken place in each lossy output. For example, the lossy-compressed representation `[100]4` of a string `1001001000100` shall indicate that the omission of `0` is taken place at position 10. This is possible if the compression algorithm employs graphs.

---

## Answer to comments and updates

1. Do you want the Pareto-optimal front: e.g., for each length, you want the encoding of that length that has the fewest errors? - Yes. Thanks, I didn't know the terminology.
2. Do you want a list of all possible encodings? - Not precisely. The Pareto-optimal front should be in the output. I don't think there will be exponentially many since a candidate that improves neither the length nor the error is not added to the output list, and therefore I expect O(L) candidates in the output, where L is the string length. If I'm wrong and it does grow polynomially or worse, let's constrain the output list to contain at most M=1000 elements. In such a case, these top M candidates are not guaranteed to be the best top M encodings of a string - that's fine.
3. How are you measuring the number of "error"s? Are you using the Hamming distance here? - Yes, the Hamming distance is used, although the edit distance fits the task as well.

# Answer
> 1 votes
You can solve this using dynamic programming. I will describe it in terms of constructing a graph and finding shortest paths in the graph, which is roughly equivalent.

Let $A\[1..n\]$ be the input string you are trying to encode. Let's construct a graph where each vertex is identified by an integer $i$, with $i \in \\{0,1,2,\dots,n\\}$. Each edge will have both a length, which represents the length of the encoding so far, and a cost, which represents the number of errors so far. The length of a path is the sum of the lengths of its edges, and same for cost. The intended meaning of a path $0 \leadsto i$ is that it represents an encoding of $A\[1..i\]$ with a length given by the length of the path, and a number of errors given by the cost of the path. We will add edges to the graph as follows, for each $i$:

* Add an edge $i \to i+1$ of length 1 and cost 0. This represents an encoding where we append $A\[i+1\]$ to the encoding for $A\[1..i\]$.
* Add an edge $i \to i+jr$ of length $j+3$, for each $j$ and $r$ such that $i+jr \le n$. This represents an encoding where we append something of the form $\[x\_1 x\_2 \cdots x\_j\]r$ to the encoding for $A\[1..i\]$. For a given $j,r$, choose the $x$'s by taking a majority vote among $r$ characters: $$x\_k = \text{majority}(A\[i+k\],A\[i+j+k\],A\[i+2j+k\],\dots,A\[i+(r-1)j+k\]).$$ The cost of this edge is easily computed (it is the number of items that differed from their majority vote, summed across all $k$).

Now the goal is to find the set of all Pareto-optimal paths from $0 \leadsto n$ in this graph. This can be solved using the algorithm at Set of Pareto-optimal paths, in a graph where edges have both length and cost.

If you need to solve this in practice, there are various optimizations that can be applied to reduce the memory consumption of this algorithm. For instance, there is no need to build the entire graph up front; instead, it can be constructed on demand, as whenever you visit a vertex you can identify all edges out of that vertex on demand. There are a number of other fancy optimizations possible, e.g., to extract the encoding (not just its length) in a memory-efficient way. Ask if you need them, but I suggest you start simple to see if this meets your needs, before trying to optimize.

---
Tags: search-algorithms, data-compression, substrings, suffix-trees
---


# Question
Title: Prove that $L =\{ a^n b^m c^{n\times m} \mid n, m\geqslant 0\}$ is not context free
I looked at all possible options for $vx$ when you look at $z = uvwxy$ and can't find a contradiction in the case where $b$'s and $c$'s are in $vx$.

# Answer
Hint: if $v\in b^+c^+$, what would $v^2$ look like? (same thing for $x$)
> 1 votes

---
Tags: context-free
---


# Question
Title: Retrieving the cheapest path of a graph with time-dependent edge weights
There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient algorithm to find the path of graph with the lowest cost, where weights of edges depend on what time the edge is being walked through. I need to take into account how the situation changes during the path traversal after each passed edge. How can I do this? Maybe there are ways to at least try to optimize the cost to be as low as possible?

Somewhat formal definition:

> Given a graph $G=(V,E)$, time-based edge cost function $w\_{v\_i,v\_j}(t)$ and a constant time to walk through an edge $t\_{v\_{i},v\_{j}}$, find path from starting point $v\_s$ to finish point $v\_f$, $P=(v\_1, v\_2, ..., v\_n)$, where $v\_1 = v\_s$, $v\_n = v\_f$, such that $\sum\_{i=1}^{n-1}w\_{v\_{i},v\_{i+1}}(T\_{P}(i)) = min$, where $T\_{P}(n) = \sum\_{i=1}^{n-1} t\_{v\_{i}, v\_{i+1}}$ (time passed since the start of the path)

Basically, the graph is a collection of pedestrian roads of a city area and the cost function is a factor that a pedestrian might want to avoid at the cost of a possibly longer path, such as sun illumination (wants to walk in the shadow) or noisiness/crowdedness (wants to avoid public places).

# Answer
This is solvable using a product construction. You construct a new graph $G'=(V',E')$ where each vertex in $V'$ has the form $\langle v,t \rangle$, to keep track of both which vertex you're at ($v$) and the current time ($t$). Then, find a shortest path in $G'$.

To learn more about this approach, for some other examples of a product construction, see, e.g., Shortest path given correct order of colours?, https://stackoverflow.com/q/5370902/781723, Restricted traversal on an undirected graph, Dijkstra's algorithm to compute shortest paths using k edges?, How hard is finding the shortest path in a graph matching a given regular language?.
> 0 votes

---
Tags: algorithms, graphs, data-structures, shortest-path, efficiency
---


# Question
Title: Why use private IP addresses in a LAN instead of MAC address
Why do we use a private IP address instead of using the MAC address in a local network?

It makes sense that we have IP addresses for large networks where packets have to be routed because the IP address is location-dependant. Meaning routers can just route a packet to a location. But if routers had to route a packet to a MAC address, this would mean the router had to figure out where this current MAC address is since it isnt location-dependant.

But why dont we use MAC addresses in LAN's. Nothing has to be routed in a LAN, so why dont we just translate an incoming packet into its MAC address instead of its private IP address(and vice-versa).

# Answer
> 3 votes
It's not an "instead". Every packet that is sent using IP contains *both* a MAC address and an IP address. You need both, because the IP-layer protocol stack understands only IP addresses, and the link layer understands only MAC addresses.

For instance, if you send an IP packet over Ethernet, then the packet needs to contain an Ethernet destination address (so that the recipient host's Ethernet card can tell it is destined for them) and an IP destination address (because it's possible that ultimate destination is a host not on this Ethernet link, in which case the Ethernet destination address will be a router on this Ethernet link and the IP destination address will be the ultimate destination).

Each protocol is simpler if it has its own address space, that does not depend on that of any other protocol.

---
Tags: routing, ip
---


title: Randomized Algorithm Log-Space Exp-Time

text:
# Question
Title: Randomized Algorithm Log-Space Exp-Time
I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the size of the input.

# Answer
> 2 votes
If I understand you correctly, I don't think such an algorithm exists. Any algorithm that uses only log space and halts could not run in exponential time, because there is at most polynomial number of unique configurations of the machine. This applies to randomized algorithms (i.e. probabilistic Turing machines) as well, because every branch of the probabilistic TM has to halt in polynomial time before running out of possible configurations for that branch.

---
Tags: time-complexity, space-complexity, randomized-algorithms
---


title: Another proof of a codeforces problem

text:
# Question
Title: Another proof of a codeforces problem
Link to the problem: https://codeforces.com/problemset/problem/1221/A.

The problem:

> You are playing a variation of game 2048. Initially you have a multiset $S$ of $n$ integers. Every integer in this multiset is a power of two.
>
> You may perform any number (possibly, zero) operations with this multiset.
>
> During each operation you choose two equal integers from $s$, remove them from $s$ and insert the number equal to their sum into $s$.
>
> For example, if $s =\\{1,2,1,1,4,2,2\\}$ and you choose integers $2$ and $2$, then the multiset becomes $\\{1,1,1,4,4,2\\}$.
>
> You win if the number $2048$ belongs to your multiset. For example, if $s=\\{1024,512,512,4\\}$ you can win as follows: choose $512$ and $512$, your multiset turns into $\\{1024,1024,4\\}$. Then choose $1024$ and $1024$, your multiset turns into $\\{2048,4\\}$ and you win.
>
> You have to determine if you can win this game.
>
> You have to answer $q$ independent queries.

Here's my code that got accpeted:

```
Define sum = 0;

For all elements x in S such that x <= 2^{11}:
    sum += x;

If(sum >= 2^{11})  Print "YES";
Else Print "NO";

```

I've already had a proof myself and I like to share it but I don't think it's formal enough. I'm looking for a proof that is more formal than mine or if you could spot any mistakes, please feel free to point it out for me.

---

The idea to this problem is simple: We don't care about elements that are greater than $2^{11} = 2048$. Instead, we sum up all the elements that are less than or equal to $2048$. Two obvious cases will happen:

1. The sum $\geq 2^{11}$
2. The sum $\< 2^{11}$

It's easy to see why case 2 will lead to a NO answer: If we can pick some elements and can sum those up to $2^{11}$(nothing's repeated because we just keep merging elements) then why the sum $\< 2^{11}$ at the very start ? So, by contradiction, we prove that case 2 leads to a NO answer.

Let us prove case 1 leads to a YES answer.

# Answer
Consider a multiset $A = \\{ a\_1, a\_2, a\_3,..,a\_n\\}$, each of which has the form of $2^{t\_i}$ and $\leq 2^{11}$ where $1\leq i\leq n$.

Now we design an algorithm to prove the above fact.

Step 1: If $2^{11} \in A$. We stop.
Step 2: Pick two equal elements in $A$ and merge them. But how do we make sure there exists such two elements? Suppose the reverse.
If they're all distinct, because all elements are less than $2^{11}$(we've found no $2^{11}(s)$ in step 1), the largest sum we can get is: $2^0 + 2^1 + 2^2 + ... + 2^{10} = 2^{11} - 1$. Again, no matter how many iteration the algorithm's taken, the original sum remains the same(nothing repeats here). So, it cannot be less than $2^{11}$(Remember that we're in case 1 of the proof).

So, such two elements exist and in step 2, we merge them.

Step 3: Go to step 1

---

Without step 1, the number of elements decreases by one after each iteration. And at the end, we're left with a number $2^T \geq 2^{11}$. And after each iteration, some $t\_i$ increases by one(no "sudden change"). So, it is true that with step 1 comes into play, the above algorithm will find a way to sum up to $2^{11}$. We're done.

I don't think this proof is formal enough but interesting and somewhat "close to formality". I would like to hear more formal proofs from you. Thank you for reading :D.
> 2 votes

---
Tags: correctness-proof, check-my-answer
---


# Question
Title: Linear having two different connotations?
When we discuss data structures, linear typically means that we can iterate through the data sequentially. For example, a linked list or array can fall into this category while a binary search tree is a non-linear data structure.

On the other hand, when we discuss mathematical functions, a linear function $f(x)$ satisfies two properties.

1. $f(u + v) = f(u) + f(v)$
2. $f(cu) = cf(u)$

Can someone explain to me how these two ideas relate or does the word "linear" map to two different definitions?

# Answer
The word linear has several, related, meanings in the English language, for example:

* Made, or designed to be used, in a step-by-step, sequential manner: this is the meaning most related to the data structure one. It is also used when talking about linear narratives, for example.
* Of, or relating to, a class of polynomial of the form $y = ax+b$: this is where your linear algebra example comes from.
* Of, or relating to, lines: this is where the names for the Linear A and Linear B scripts come from.

(List taken from wiktionary.)

The various meanings are obviously related on some level — perhaps by a line of metaphors – but they are not related in any formal sense, any more than simple groups are related to simple roots. Mathematical terms are arbitrary, and their names should not be construed as dictating their meanings.
> 1 votes

# Answer
Linear for data structures typically refers to an O(n) algorithm. I.e. the time is bounded by c.n for some constant c \> 0. The function f(n) = c.n when represented in the Cartesian plane forms a straight line.

If you purely view linear as "iterating through the data sequentially" then this presumably refers to the fact that the data can be represented on a straight line, reflecting that one element can be accessed from another via a \`\`successor" function that fits the straight line order.

The term linear function f(x) satisfying 1) and 2) in your question can determine a straight line in 2 dimensions. A linear function is used in linear algebra and can represent more general \`\`linear structures", for instance a plane.

All of these are likely to be related to this last interpretation of linear parts of vector spaces.
> 1 votes

---
Tags: data-structures
---


# Question
Title: What edges are not in a Gabriel graph, yet in a Delauney graph?
It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{DG}(P)$.

A Gabriel graph is defined as:

> The Gabriel graph $\mathcal{GG}(P)$ of a point set $P \subset \mathbb{R}^2$ is defined as follows. The vertex set is $P$ and two vertices $p, q$ in $P$ are connected by an edge if and only if the interior of the disk with diameter $\overline{pq}$ is empty and $p, q$ are the only two points on its boundary. In particular, this implies that $\overline{pq}$ is also an edge in the Delaunay graph of P.

However, I am struggling to visualize or understand in what cases an edge $(p, q)$ would be in $\mathcal{DG}(P)$ but *not* in $\mathcal{GG}(P)$. Could someone give me an example? It seems to me as, by the empty-circle property of Voronoi edges, and their duality with the Delaunay graph, every edge in the Delaunay graph should satisfy the definition of a Gabriel graph. It is obvious that I am missing some edge case.

# Answer
From my answer to a similar question:

> A Delaunay edge $(x,y)$ won't be a Gabriel edge, if the set of all the possible empty disks with $x$ and $y$ on their boundaries doesn't contain the disk with minimum possible radius (which is the half-length of this edge). In other words, this will happen when the Delaunay edge $(x,y)$ **doesn't intersect** the segment (or ray), separating sites $x$ and $y$ in the Voronoi diagram.
> 2 votes

# Answer
Ah, I think I figured it out, thanks to the help from Discrete Lizard.

See the following image of a Delaunay triangulation, where I've highlighted one example where the edges would be included in DT, but not GG.

.
> 6 votes

---
Tags: graphs, computational-geometry, planar-graphs, voronoi-diagrams
---


# Question
Title: How could you encode such a function in lambda calculus?
I just read the definition of lambda calculus. Apparently it's Turing complete, but I tried writing a very simple function and I couldn't:

```
f(a)=b
f(b)=a
f(x)=x otherwise

```

so it just swaps the variables a and b.

Functional languages already have conditions which makes it easy, but how do you do it using only abstraction and application?

# Answer
It's impossible. And this doesn't contradict Turing completeness.

To say that a computation system is Turing-complete doesn't mean that you can express every computation you might like to express inside the system. It means that there is an encoding of Turing machines and their computation rule. If you perform the system's computation on encodings of Turing machines, it does the same thing as Turing machine computation. This doesn't imply anything about how the system behaves on objects that are not encodings of Turing machines.

An equivalent definition is that a computation system is Turing-complete if there is an encoding of natural integers such that every computable function corresponds to a computation on the encodings of the integers. Once again, this doesn't imply anything about how the system behaves on objects that are not encodings of integers.

In mathematical notation, the lambda calculus is Turing-complete because there is a function $E : \mathbb{N} \to \Lambda$, where $\Lambda$ is the set of all lambda terms, such that if $f : \mathbb{N} \to \mathbb{N}$ is computable then there is a lambda-term $F\_f$ such that $\forall n \in \mathbb{N}, F\_f E(n) \equiv\_\beta E(f(n))$. If $M$ is a lambda term that cannot be expressed as $E(n)$, there is no particular reason why $F\_f M$ would reduce to anything remarkable.

An example of encoding of integers into the lambda calculus, which does demonstrate the lambda calculus's Turing completeness, is the Church numerals, which encode a natural number as the function that maps an integer $n$ to the $n$-times repetition function: the function that maps every function $f$ to $f$ iterated $n$ times. That is, $E(0) = \lambda x. \lambda f. x$, $E(1) = \lambda x. \lambda f. f(x)$, $E(2) = \lambda x. \lambda f. f(f(x))$, etc. The lambda terms that are of the form $E(n)$ are called Church numerals. I'll write $\mathscr{C}$ for the set of Church numerals.

If $A$ and $B$ are two Church numerals, there is indeed a lambda term $S\_{A,B}$ such that $S\_{A,B} A \equiv\_\beta B$, $S\_{A,B} B \equiv\_\beta A$, and $\forall X \in \mathscr{C} \setminus \\{A,B\\}, S\_{A,B} X \equiv\_\beta X$. I will leave finding an expression for $S\_{A,B}$ as an exercise. It's tedious, but not difficult once you've played a bit with Church encodings.

If $X$ is not a Church numeral, there is no particular reason why $S\_{A,B} X$ would be beta-equivalent to $X$. And there is no particular reason to believe that the construction of $S\_{A,B}$ can be generalized to the case where $A$ and $B$ are arbitrary lambda terms. I will prove that the second property in fact cannot be generalized to variables at all. I believe that the first property also cannot be true of any encoding, but this requires non-elementary theorems.

Suppose that $M a \equiv\_\beta b$ and $M b \equiv\_\beta a$. Since $M a$ is not a normal form, $M$ must reduce to an abstraction: $M \to\_\beta^\* \lambda x. N$. Then $M a \equiv\_\beta (\lambda x. N) a \to\_\beta N\[x \leftarrow a\]$. Since we assumed $M a \equiv\_\beta b$, we have $N\[x \leftarrow a\] \equiv\_\beta b$. Now apply another renaming substitution: $N = N\[x \leftarrow a\]\[a \leftarrow x\] \equiv\_\beta b\[a \leftarrow x\] = b$. But we also have the assumption $M b \equiv\_\beta a$, hence $N\[x \leftarrow b\] \equiv\_\beta a$ and $N = N\[x \leftarrow b\]\[b \leftarrow x\] \equiv\_\beta a\[b \leftarrow x\] = a$. So $a \equiv\_\beta N \equiv\_\beta b$, which is impossible since $a$ and $b$ are distinct normal forms.

Intuitively speaking, in the lambda calculus, all variables are indistinguishable. This is an indirect consequence of alpha conversion and of the fact that variables can be substituted by arbitrary terms through abstraction and beta reduction: to make the “identity” of a variable disappear, put it under a lambda, and it becomes a bound, renamable variable.

Programming languages based on the lambda calculus are different because they have objects other than functions. As soon as you add constants, and rules to calculate on those constants (called delta rules), the shape of the possible computations changes. To start with, in the lambda calculus, the normal forms (i.e. values) have a simple characteristic: they're all functions applying a variable, i.e. $\lambda x\_1. \cdots \lambda x\_n. y M\_1 \cdots M\_m$ for some $(n,m) \in \mathbb{N}^2$. As soon as you add constants, the shape of values is much more complicated, since an application of a constant to a term may or may not be reducible depending on what delta rules involve this constant. It is trivial in virtually every programming language to define a function $f$ such that $f(c\_1) = c\_2$ and $f(c\_2) = c\_1$ for two *constants* $c\_1$ and $c\_2$. But if you apply this function to *variables* ($f(x)$), you won't get another variable: you'll get at most a partially evaluated term still involving the variable.
> 6 votes

---
Tags: lambda-calculus, turing-completeness
---


# Question
Title: Q: Defining Markov-Chain Probability Matrix States | Specific Academic Paper
I am working on a uni project, for which i will model synthetic electricity consumption time series using Markov-Chains. I am reading through current academic literature on that topic and came across an interesting paper (link below).

The authors use a 24x24 probability matrix for the different states that a household can be in, in terms of energy consumption. This makes sense, as there are 24 hours within a day. I *think* the values of the matrix describe the probability that a certain household is going to move from the current state of a given hour to the mean state of all datasets in the next hour. I am not completely sure on this though. So the unit of the matrix elements should be probably in kWh.

My question is how did they generate the matrix? I am not sure if the next sentence has something to do with it: "*Bin sizes for sampling were chosen based on standard deviation (0.0837) and mean electricity consumption (0.5525kW) for a sample of 4,500 Irish dwellings*"

The filled out 24x24 Matrix is not given in the paper, only the final results of the model.

If you want to take a look within the paper, ctrl+f this phrase: "*Markov chain model using a 24x24 probability*" and it should lead you to the part of the paper on page 5.

Citation: Duffy, Aidan & McLoughlin, Fintan & Conlon, Michael. (2010). The Generation of Domestic Electricity Load Profiles through Markov Chain Modelling.

link to the paper

direct pdf download

# Answer
> 0 votes
I find the paper unclear: it just doesn't seem to explain very clearly where they got the Markov chain from or what the meaning of states or transitions are. I find their explanation of the Markov chain (the paragraphs where they explain their model) confusing and unclear. The only recourse I can see is to contact the authors to ask them for more information.

---
Tags: algorithms, markov-chains, data-sets
---


title: define the head expressions

text:
# Question
Title: define the head expressions
List $\[E1,E2,...,Ek\]$ in lambda expression can write as

$$λc.λn.cE1(cE2(...(cEkn)...))$$

Based on this, how to define `head` and `empty` lambda expressions

So that

$head\[M..\]$ can be beta reduce to M

and

$empty\[\]$ can be beta-reduce to True

$empty\[N..\]$ can be beta-reduce to False

So far I only figured out the True and False in lambda expression are

$$T=(λx.λy.x)$$ $$F=(λx.λy.y)$$

Any tips or hints would be very appreciate

# Answer
Based on your definition of a list, we can define emptyList as $λcn.n$ (same as your above $F$). Then we can simply define your head and empty test functions as $head:=λl.l(λab.a)M, empty:=λl.l(λab.False)True$, where $M$ is an arbitrary expression.

Now you'll have below as expected (here I use a list containing only $h$ as an example of nonempty list):$$head(λcn.chn) \to\_\beta (λcn.chn)(λab.a)M \to\_\beta (λab.a)hM \to\_\beta h \\ empty(emptyList) \to\_\beta empty(λcn.n) \to\_\beta (λcn.n)(λab.False)True \to\_\beta True \\ empty(λcn.chn) \to\_\beta (λcn.chn)(λab.False)True \to\_\beta (λab.False)hTrue \to\_\beta False$$
> 0 votes

---
Tags: lambda-calculus
---


# Question
Title: Probabilistic Turing Machine Transition Relation vs Transition Function
In wiki, PTM are defined with two transition functions and a fair coin toss which determines which one is used at each step. One can also define them, much like NDTM, using a transition relation where in each step the machine chooses from its next possible configurations using a fair probabilistic choice. My question is: how are these equivalent? If there is, say 10 possible next configurations at a given step how could you encode this in a PTM which only has 2 transition functions?

# Answer
The translation is a bit subtle because it doesn't preserve worst-case running time, but does preserve expected running time up to a constant. I'll consider your example of a state with 10 possible transitions. To simulate this transition in a coin-flip (binary) model, we essentially need to use a fair coin to generate a random number between 1 and 10.

There are many ways to do so, but the most obvious is to repeatedly generate a number between 1 and 16 (the next power of 2), using 4 coin flips. If the number is between 1 and 10, terminate the sub-procedure and transition to the next state as appropriate. If it's between 11 and 16, try again. This sub-procedure requires only a constant number of states (at least 16 to record the 4 coin flips, perhaps more as the Turing machine has to stay in place after each flip and if the model does not allow a Stay instruction, we need to move Left and then back Right again to stay in place). But it is guaranteed to terminate in **expected** finite time.

It is impossible to generate a random number uniformly between 1 and 10 using coin flips using **worst-case** finite time. To see this, note that if the worst-case running time is bounded by, say, $k$, then there are $2^k$ possible coin flips, so $2^k$ possible outcomes, which is never a multiple of $10$, so we can never assign numbers between $1$ and $10$ to the $2^k$ outcomes in a uniform (fair) manner.

In practice, the definition of running time we care about for probabilistic Turing machines is one of two possibilities:

1. **Expected running time** -- this definition is used in the complexity class ZPP. For this possibility, the above translation will be valid.
2. **Worst-case finite running time** -- this definition is used in the complexity class BPP. In this case, the above translation is not good as it will not preserve worst-case running time. Here we need a different translation which instead tolerates some error: we cut off the procedure to generate a random number between 1 and 10 after a certain constant $k$ number of iterations, and we keep track of the error involved. Since $k$ can depend on the input, we can make it large enough that the error is small enough that we don't care, at least for the purposes of the complexity class BPP, which is defined to be problems that can be solved to within a small probability of error.
> 2 votes

---
Tags: definitions, probabilistic-turing-machines
---


# Question
Title: what are good data structure algorithm for fast 3D coordinates search?
I want to form data structure for nearby neighbor search for 3D coordinates. What is the best way to do so?

# Answer
There are lots of standard ones, such as:

Which one you choose would depend on the properties of your data (e.g. how "clustered" the points are, whether the set of points is static or dynamic) and what queries you wish to perform (e.g. k-nearest-neighbour search).
> 5 votes

---
Tags: data-structures, search-algorithms, search-trees
---


# Question
Title: Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.

$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of insertion sort, it implies that $O(n^2)$ is upper bound of algorithm no matter what type of input is, means it doesn’t matter whether input is sorted, unsorted, reverse sorted, have same values, etc the upper bound will be same $O(n^2)$. But this is not the case of insertion sort. Insertion sort running time depends on type of input used. So when the input is already sorted, it runs in linear time and doesn’t take more that $O(n)$ time.

Therefore to write insertion sort running time as $O(n^2)$ is technically not good.

**We use $\Theta$-notation to write worst case running time of insertion sort. But I’m not able to relate properties of $\Theta$-notation with insertion sort, why $\Theta$-notation is suitable to insertion sort.If $f(n)$ belong to $\Theta(g(n))$ we write it as $f(n)= \Theta(g(n))$, then $f(n)$ must satisfies the properties. And properties state that there exits constants $c\_1$, $c\_2$ and $n\_0$ such that $0$$\leq$$c\_1\cdot g(n)$$\leq$$f(n)$$\leq$$c\_2\cdot g(n)$ For all $n\>n\_0$. How does the insertion sort function lies between the $c\_1\cdot n^2$ and $c\_2\cdot n^2$ for all $n\>n\_0$.**

Running time of insertion sort as $\Theta(n^2)$ implies that it has upper bound $O(n^2)$ and lower bound $\Omega(n^2)$. I’m confused as to whether the lower bound on insertion-sort is $\Omega(n^2)$ or $\Omega(n)$.

# Answer
You are confusing two different notions. The definition of $\Theta$ that you give is correct, and indeed the running time of insertion sort, in the worst case, is $\Theta(n^2)$, since it has a quadratic running time.

The fact that this is the worst running time is somewhat irrelevant here. You have some function, and you are classifying it as $\Theta(n^2)$, because you can.

Indeed, the runtime of the algorithm in the best case can be a different function, which may or may not be $\Theta(n^2)$.

It may make more intuitive sense to just say that in the worst case, the runtime is $O(n^2)$, which implies that in all the cases the runtime is $O(n^2)$, but observe that this is also implied by the stronger $\Theta$ notations.

As an illustrative example, consider this: You can get home in two paths, one takes 10 km, and the other 3 km, but the 3 km is only open on certain hours of the day.

You can say the following: when you walk home, in the worst case you will walk **exactly** 10 km. This is true, and it implies that you *always* walk **at most** 10 km. But the former is a stronger claim, so why not use it?
> 11 votes

# Answer
So, before going ahead, just let me clarify one thing. Theta - Θ(g(n)) indicates asymptotic tight bounds. Your function(insertion sort running time) is sandwiched between constant factors of g(n).

Big O - O(g(n)) indicates asymptotic upper bounds. So, no matter what your function is, if it is a O(g(n)) it is bound to be less by a constant factor of g(n).

Coming to the insertion sort running time, O(n²) and Θ(n²) are both the worst case scenario i.e. when the array is in a decreasing order.

But in the best case scenario i.e. when the array is sorted, it is not Θ(n²) but Θ(n). But if you want to represent the same it can be both O(n²) and O(n).

So, O(n²) holds true for both the worst and the best case where as Θ(n²) holds only for the worst case. That's the reason, Big O can be used to make blanket statements i.e. for any kind of input, it holds. Hope it helped.
> 3 votes

# Answer
You are correct that $\Theta$ cannot be used to describe the runtime of insertion sort on arbitrary input, because its performance varies too dramatically.

However, we're talking worst case, not general case; e.g. for every $n$, we let $A\_n$ be the input that takes the longest for insertion sort to sort. Then the assertion that the running time of "call insertion sort with input $A\_n$" is given by $\Theta(n^2)$.
> 1 votes

# Answer
Short answer: $O(n^2)$ states an *upper* bound on the worst case complexity. I'd be quite right to say it is $O(n^3)$, or even $O(2^n)$ (check your definitions!). Saying the worst case complexity is $\Theta(n^2)$ says it is an *upper and lower* bound (within a constant factor, it is $n^2$ for large enough $n$). That is much stronger.
> 0 votes

# Answer
> In simple words, the running time of a programs is described as a function of its input size i.e. f(n).

The `=` is asymmetric, thus an+b=O(n) means f(n) belongs to set O(g(n)). So we can also say an+b=O(n^2) and its true because f(n) for some value of a,b and n belongs to set O(n^2).

Thus Big-Oh(O) only gives an upper bound or you can say the notation gives a `blanket statement`, which means all the inputs of a given input size are covered not just the worst case once. For example in case of insertion sort an array of size n in reverse order.

So n=O(n^2) is true but will be an abuse when defining worst case running time for an algorithm. As worst case running time gives an upper bound on the running time for any **input**. And as we all know that in case of insertion sort the running time will depend upon how the much sorted the input is in the given array of a fixed size. So if the array is sort the running will be linear.

So we need a tight asymptotic bound notation to describe our worst case, which is provided by Θ notation thus the worst case of insertion sort will be Θ(n^2) and best case will be Θ(n).
> -1 votes

# Answer
In general you don't use the theta function for the worst case, but for an average one.

The *insertion sort* algorithm has a linear time when the array is already sorted: `Ω(n)`; and a quadratic time when it's sorted in the opposite order: `O(n^2)`.

An average case won't have many already sorted elements so it will be next to the worst case\[\*\]; a better one, but within the same quadratic order: `Θ(n^2)`.

As a conclusion, you should always use both Ω and O function for describing the algorithm but, if the majority of the cases is around a Θ function, is ok to use only it.

---

\[\*\]: That's because is the inner cycle that bears on the resulting time.
> -5 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, asymptotics
---


# Question
Title: Maximum I/O Data Transfer if DMA is used
I was reading lecture notes of Universiti Malaysia Perlis when I am came across following question:

> A computer consists of a CPU and an I/O device $D$ connected to main memory $M$ via a shared bus with a data bus width of one word $(16-bits)$. The CPU can execute a maximum of $10^6$ instructions per second. An average instruction requires $five $ processor cycles, $three$ of which use the memory bus. A memory read or write operation uses $one$ processor cycle. Suppose that the CPU is continuously executing *“background”* programs that require $95$% of its instruction execution rate but not any I/O instructions. Now very large blocks of data are to be transferred between $M $ and $D$.
>
> **Estimate the rate if DMA transfer is used.**

P.S. Assume that one processor cycle equals one bus cycle.

The answer says:

$$10^6 * (0.05 * 5 + 0.95 * 2) = 2.15 * 10^6$$

**Can someone explain the reasoning behind the answer ?**

I could understand that $0.05$ is percent of time devoted by CPU and $0.95$ is the percent of time devoted by DMA, but what about $5$ and $2$ ? If it has something to do with cycles, then I did not understand the logic.

# Answer
> 1 votes
After reading more about it and reading the question again and again, I understood the logic

> The question says that on an average an instruction requires $5$ $cycles$ and the CPU is busy $95$% of the time in executing those instructions. Out of these $5\ cycles$, $3\ cycles$ are needed for memory operations. During this time $DMA$ cannot access the memory.

So only $2\ cycles$ are left for $DMA$ to use for 95% of the time. For 95% time DMA uses $$0.95 * 2\ cycles$$

For rest 5% time, CPU isn't executing instructions, so all cycles are available, so DMA uses $$0.05 * 5\ cycles$$

Total cycles available for DMA $$(0.05 * 5 + 0.95 * 2)\ cycles$$

In $1 second$, CPU can execute $10^6$ instructions. So rate of transfer is

$$ 10^6 * (0.05 * 5 + 0.95 * 2) = 2.15 * 10^6 $$

# Answer
> 0 votes
we can see it like-wise also (I guess), i made it like a reasoning maths questions :P

In DMA , we don't need direct intervention of CPU , its DMAC which helps in controlling the data transfer.

let us take , CPU is fed with 100 instructions (replace those 10^6, as it says , cpu can execute - MIPS). For 100 instns it will require ~500 cycles . Now divide this into two sections so for 95 * 5 cycles , DMA will use 95 * 2 cycles (as during 3 cycles mem bus is busy ), and the remaining cycles 25 (=500-95 * 5) will be consumed by the IO device. now sum up (95 * 2)+(5instn * 5cycles)=2.15 (words per second) just multiply it with 10^6 for the case when 10^6 instn are fed.(2.15 * 10^6)

---
Tags: operating-systems, memory-hardware
---


# Question
Title: Trying to understand 3-SAT self-subsuming process
Trying to understand 3-SAT self-subsuming process

I've been studying solver theory and am trying to understand some of the basic concepts that I've been reading. In particular, the idea of self-subsuming (if I have the correct terminology here) is confusing me. It appears that it's possible to come to different conclusions based upon the order of processing - but I'm pretty sure that this possibility is wrong, so I'm trying to understand what I'm doing wrong and where my thinking is incorrect.

To make it simple, if we start with the following 8 clauses, we know that it's UNSAT

```
a + b + c
a + b + !c
a + !b + c
a + !b + !c
!a + !b + c
!a + b + c
!a + b + !c
!a + !b + !c

```

But, if I use self-subsuming logic, it appears to be SAT based on the following:

Clause 1, Clause 2 (resolve on) = Resolution

```
a + b + c,  a + b + !c   (c) = a + b  [Use resolution for next step of process]
a + b,      a + !b + c   (b) = a + c
a + c,      a + !b + !c  (c) = a + !b
a + !b,     !a + !b + c  (a) = !b + c
!b + c,     !a + b + c   (b) = !a + c
!a + c,     !a + b + !c  (c) = !a + b
!a + b,     !a + !b + !c (b) = !a + !c

```

But, using a different process, it does become UNSAT. Here, the resolutions are kept separate until all 8 clauses have been reduced.

```
a + b + c,   a + b + !c   (c) = a + b
a + !b + c,  a + !b + !c  (c) = a + !b
!a + !b + c, !a + b + c   (b) = !a + c
!a + b + !c, !a + !b + !c (b) = !a + !c

```

Finally, use the 4 remaining clauses and you end with a contradiction - which we know is the correct answer.

```
a + b,       a + !b       (b) = a
!a + c,      !a + !c      (c) = !a

```

However, using the same remaining 4 clauses, processed differently it again appears SAT

```
a + b, !a + c   (a) = b + c
a + !b, !a + !c (a) = !b + !c

```

Can someone explain what I'm doing wrong to come to different conclusions?

# Answer
> 1 votes
In the Resolution proof system, at any given point in time, we have a set $S$ of clauses. If $S$ contains two clauses $\alpha \lor x$ and $\beta \lor \lnot x$, we can *resolve* to obtain the new clause $\alpha \lor \beta$, which we add to $S$. *We do not remove the original clauses.* Rather, they stay in $S$.

A given collection of clauses is either satisfiable or unsatisfiable — this is a concept that has nothing to do with Resolution: a set of clauses is *satisfiable* if there is a truth assignment that satisfies all clauses; otherwise, it is *unsatisfiable*.

Resolution is *sound*: starting with a set $S$ of clauses, any clause $\alpha$ which is produced by Resolution is logically implied by $S$, in the sense that any truth assignment satisfying $S$ also satisfies $\alpha$. In particular, if $S$ is satisfiable, Resolution would not derive the empty clause.

Conversely, Resolution is *complete*: if a set $S$ of clauses is unsatisfiable, then using Resolution, you can derive from it the empty clause, thus proving that $S$ is unsatisfiable. The proof could be rather long — there are many explicit examples which require exponentially long proofs, though in practice, in many cases much shorter proofs work.

One way to deduce the empty clause given an unsatisfiable $S$ is to repeat the following algorithm: while there exist two resolvable clauses in $S$ whose resolvent is not in $S$, resolve the two clauses and add the resolvent to $S$. This process *must* work. Furthermore, any Resolution proof can be framed as a particular instantiation of this algorithm; the culprit is that at any given point in time, there could be many different pairs of clauses which could be resolved, and finding the optimal pair is hard.

Finally, a bit about *clause learning*. Above I wrote that when we resolve two clauses, we do not remove them from the set of clauses. But in fact, early SAT solvers did erase the resolved clauses, *unless they were axioms*. The corresponding proof system, treelike Resolution, is known to be exponentially weaker than general Resolution; that is, there are instances which have short refutations (proofs of the empty clause) in general Resolution, but only long ones in treelike Resolution. Modern SAT solvers use a technique known as *clause learning* which allows them to harness the power of general Resolution.

---
Tags: algorithms, satisfiability, 3-sat
---


# Question
Title: Relation between $P$ vs $\mathit{NP}$ and $P^{\mathit{NP}}$ vs $\mathit{NP}^{\mathit{NP}}$ questions?
Given that both $P \subset \mathit{NP}\ ?$ and $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}\ ?$ are open questions.

Is it possible that $P \subset \mathit{NP}$ and $P^{\mathit{NP}} =\mathit{NP}^{\mathit{NP}}$?

Or is it the case that $P \subset \mathit{NP}$ iff $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}$?

# Answer
> 4 votes
We know that $\mathsf{P} \subseteq \mathsf{NP}$ and that $\mathsf{P}^{\mathsf{NP}} \subseteq \mathsf{NP}^{\mathsf{NP}}$; this follows directly from the definitions.

More interesting are the two reverse inclusions, $\mathsf{NP} \subseteq \mathsf{P}$ and $\mathsf{NP^{NP}} \subseteq \mathsf{P^{NP}}$. The former implies the latter: indeed, if $\mathsf{NP} \subseteq \mathsf{P}$ then $\mathsf{P} = \mathsf{NP} = \mathsf{P^{NP}} = \mathsf{NP^{NP}}$. The latter is not known to imply the former, and moreover, there are relativized worlds with respect to which the former is false but the latter is true. This means that there is an oracle $O$ (constructed by diagonalization) such that if all Turing machines have additional oracle access to $O$, then $\mathsf{P} \neq \mathsf{NP}$ but $\mathsf{P^{NP}} = \mathsf{NP^{NP}}$. Such an oracle was constructed by Heller, Relativized Polynomial Hierarchies Extending Two Levels.

---
Tags: complexity-theory
---


# Question
Title: Factorial Formulae proof (from Algorithm Design Manual)
I'm going through Algorithm Design Manual and it didn't take long before I hit a proof I don't understand. Can anyone point me in the right direction?

From the book:

> *Problem*: Prove that $\sum\_{i=1}^n i * i! = (n + 1)! - 1$ by induction.
>
> *Solution*: The inductive paradigm is straightforward. First verify the basis case (here we do n = 1, although n = 0 would be even more general):
>
> $\sum\_{i=1}^1 i * i! = 1 = (1 + 1)! - 1 = 2 - 1 = 1$
>
> Now assume the statement is true up to n. To prove the general case of n + 1, observe that rolling out the largest term
>
> $\sum\_{i=1}^{n+1} i * i! = (n+1) * (n + 1)! + \sum\_{i=1}^n i * i!$
>
> reveals the left side of our inductive assumption. Substituting the right side gives us
>
> $\sum\_{i=1}^{n+1} i * i! = (n+1) * (n + 1)! + (n+1)! - 1$
>
> = $(n+1)! * ((n+1) + 1) -1$
>
> = $(n+2)! - 1$

I can follow this until the last line few lines.

I understand that he proves that it is indeed true for the base case of `n=1` that

$$\sum\_{i=1}^n i * i! = (n + 1)! - 1$$

Once he proves that he then takes the `n+1` case and expands out the summation to sum that plus the new upper bound

$$\sum\_{i=1}^{n+1} i * i! = (n+1) * (n + 1)! + (n+1)! - 1$$

but then I don't understand how he then simplifies that

$$(n+1) * (n + 1)! + (n+1)! - 1$$

down to

$$(n+1)! * ((n+1) + 1) -1$$

what just happened there? how does $(n+1) * (n + 1)! + (n+1)! - 1$ equal $(n+1)! * ((n+1) + 1) -1$ ??

nor do i understand how he then simplifies that to

$$(n+2)! - 1$$

how does $(n+1)! * ((n+1) + 1) -1$ equal $(n+2)! - 1$ ??

Any help here is appreciated, my brain is hurting!

# Answer
for any two numbers $a,b$, it is true that $ab + b = (a+1)b$ which is derived from simple algebra.

Now substitute $(n+1)!$ instead of $b$ and $(n+1)$ instead of $a$.

For the second problem you have, note that $(n+1+1) \cdot (n+1)!=(n+2)\cdot (n+1)!=(n+2)!$ by definition of the factorial function.
> 0 votes

---
Tags: correctness-proof, summation
---


# Question
Title: Why is $E_{LBA}$ undecidable if $A_{LBA}$ is decidable
A linear bounded automaton (LBA) is a restricted TM with finite tape.

Let $A\_{LBA} = \\{\langle M, w \rangle | M$ is an LBA that accepts string $w \\}$. It can be shown that $A\_{LBA}$ is decidable: since an LBA has only finite number of configurations, therefore an LBA does not halt iff it cycles. A cycling in the computation history of LBA can be detected.

Let $E\_{LBA} = \\{\langle M \rangle | M$ is an LBA such that $L(M) = \emptyset \\}$. Sipser (Theorem 5.10) proved that $E\_{LBA}$ is not decidable.

Here is where my question arises: since an LBA has finite space on the tape and its input alphabet is finite, the number of possible input string must be finite. Why can we not just enumerate every input $w$ and check if LBA accepts $w$? What am I missing?

# Answer
> 2 votes
I suspect the word "finite" is confusing you. Every integer is "finite", yet the set of all possible integers is not finite, and there is no finite number that is an upper bound on all possible integers. Or maybe it is the order of quantifiers.

For any fixed string $w$, there is a number $n$ (which depends on $w$) we can compute, so that the LBA has at most $n$ states.

However, there is no single number $n$ that works for all $w$. The longer the string $w$ is, the larger you need to make $n$.

That is what is wrong with your reasoning in the last paragraph of your question. There is no single number $N$ that is an upper bound on the number of states, that works for every input string $w$. And, it's not possible to enumerate every input $w$, because there are infinitely many possible strings $w$, so such a procedure might never halt.

---
Tags: undecidability, linear-bounded-automata
---