# Question
Title: Counting the number of satisfied models - given mathematical constraints
## Question

There are plenty of algorithms for solving the #SAT problem, with one being the DPLL algorithm and is implemented for all kinds of programming languages. As far as I've seen, they all take a boolean formula on CNF as input and outputs the number of satisfied interpretations.

Mathematical constraints, on the other hand, is another way defining an instance of SAT-problem and is often used in discrete optimization, where one tries to optimize some function with respect to these constraints. **Is there a program taking mathematical constraints as input and outputs the number of satisfied interpretations?**

## Example

We represent the boolean formula $Q = (a \lor b) \wedge (c \lor d)$ as constraints as $$a + b \geq 1 \\ c + d \geq 1$$ or as a matrix $A$ and support vector $b$ $$ A= \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix} \\ b = \begin{bmatrix} 1 & 1 \end{bmatrix} $$

where all variables $a,b,c,d \in \\{0,1\\}$. We know there are programs taking $Q$ as input and outputs the number of interpretations but are there programs taking $A$ and $b$ as input (or similar construction) and outputs the same number of interpretations?

# Answer
> 1 votes
I know of two reasonable approaches.

**Approach #1**: *Count the number of integer points inside a convex polytope.*

The set of linear inequalities you provided, together with the inequalities $0 \le a,b,c,d \le 1$, defines a convex polytope. Now, you want to count the number of integer points that fall within this polytope.

There are standard algorithms for doing that, which you could apply directly. If you search on "counting integer points in polytope" or "counting lattice points in polytope" you'll find many research papers. See, e.g., https://cstheory.stackexchange.com/q/22280/5038, Finding all solutions to an integer linear programming (ILP) problem.

**Approach #2**: *Convert to CNF, then use a #SAT solver.*

You can always convert your constraints to a CNF formula. Each linear inequality can be converted to a set of CNF clauses. A linear inequality of the form $x\_i + \dots + x\_j \ge 1$ corresponds immediately to the CNF clause $(x\_i \lor \dots \lor x\_j)$. For a more general linear inequality of the form $x\_i + \dots + x\_j \ge c$, you want to express the constraint that at least $c$ out of the $k$ variables $x\_i,\dots,x\_j$ are true. There are many standard ways of encoding that. See https://cstheory.stackexchange.com/q/23771/5038, Reduce the following problem to SAT, Encoding 1-out-of-n constraint for SAT solvers,

(One approach is to convert a Boolean circuit that computes $x\_i + \dots + x\_j$ and compares it to $c$, then convert the Boolean circuit to CNF using the Tseitin transform. You can create such a Boolean circuit by using standard adder and comparator circuits. However, there are many other ways as well.)

Once you have a CNF formula that is equivalent to the set of constraints, then you can use any off-the-shelf #SAT solver to count the number of solutions to that CNF formula.

---

It's hard to say which of these two approaches will work better; you might need to try them both on the kinds of instances you're dealing with, to know for sure. I'd expect that if you have linear inequalities of the form $x\_i + \dots + x\_j \ge c$ where $c$ is large, then Approach #1 may be superior; but if $c$ is typically small, then Approach #2 may be superior.

# Answer
> 0 votes
You can implement DPLL using directly using the constraints instead of clauses. This requires modifying the data structure and the propagation algorithm, but it works all the same.

As soon as all the variables of the constraint are set except one, unit propagation may occur.

As soon as all the variables of the constraint are set, a conflict may occur.

The rest of the algorithm remains the same.

A constraint over boolean variables is just a collection of hidden CNF clauses (potentially exponentially many clauses depending on the constraint).

# Answer
> 0 votes
The question has been answered on or.stackexchange for Mixed-Integer Programming software, with examples of existing software and scripts (CPLEX, SCIP, ...).

This is more similar to the CDCL algorithm than to DPLL: when a new solution is found, a new constraint is added to forbid it and the search resumes, until the problem becomes infeasible.

---
Tags: satisfiability, constraint-satisfaction
---


# Question
Title: Constrain traveling salesman: visit a given city within a given distance from start
I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say `100`) from start. Is there a way to do this? My question is related to this unanswered CS question.

I have a mixed integer program using the R package `CVXR` that find the shortest route without subroutes (see below). The city order is represent in the vector `node_order`. The strategy I've pursued so far is:

1. Re-organize `node_order` so that the index is the order and the value is the city id
2. Look up the associated distances in `distances`
3. Compute a vector with the cumulative sum of these distances.
4. Add the constraint that city `i` must occur before the first index in (3) exceeding the distance constraint for that city.

The issues I've encountered with this approach is that I have not found a way to include finding-index-by-value into the optimization in `CVXR`. This is needed in both step (1) and (4) above. Maybe this is possible after all, or there is another approach? I am willing to use other packages than `CVXR` and other software than `R`.

---

# Current program

```
library(CVXR)

# Make distances
N = 10
distances = matrix(1:(N*N), ncol = N)

# Flag 1 iff we travel that path. 0 otherwise
do_transition = Variable(N, N, boolean = TRUE)

# Minimize the total duration of the traveled paths.
objective = Minimize(sum(do_transition * distances))

# Only go one tour. Order is 1:(N-1)
node_order = Variable(N-1, integer = TRUE)
ii = t(node_order %*% matrix(1, ncol = N - 1))  # repeat as N rows
jj = node_order %*% matrix(1, ncol = N - 1)  # repeat as N cols

# Constraints
constraints = list(
  do_transition * diag(N) == 0,  # Disallow transitions to self (diagonal elements)
  sum_entries(do_transition, 1) == rep(1, N),  # Exactly one entrance to each node
  sum_entries(do_transition, 2) == rep(1, N),  # Exactly one exit from each node
  (jj - ii) + N * do_transition[2:N, 2:N] <= N - 1,  # One tour constraint (no subtours)
  node_order >= 1,   # This interval represents order as ranks (1 to N-1)
  node_order <= N-1
)

# Find optimum
solution = solve(Problem(objective, constraints))

```

# Unsuccessful attempt

A bit of code pertaining to my current (unsuccessful) attempts:

```
# Get tour order
#tour = order(c(NA, result$getValue(node_order)))  # R solution
tour = rep(NA, N-1)
tour[result$getValue(node_order)] = 2:N

# Get tour distances
distances_optim = diag(distances[tour, tour[2:N]])

# Tour cumulative distances
distances_cumul = cumsum_axis(distances_optim)

```

# Answer
> 1 votes
You can easily impose the constraint that a given city should be visited before a given *location* in the sequence. I.e., that city 5 should be one of the three first visited:

```
node_order[5 - 1] <= 3

```

Or that city 7 should be visited as the third, fourth, or fifth:

```
node_order[7 - 1] <= 5,
node_order[7 - 1] >= 3

```

This does not exactly impose the constraint on *cumulative distance*, though.

---
Tags: optimization, linear-programming, traveling-salesman
---


# Question
Title: Are all prefix codes uniquely decodable?
I can't think of any counterexample but I can't find any such statement on the internet or my textbook either. I know that for each uniquely decodable code, there exists a prefix code with the same average length.

# Answer
You can prove by induction on the length of the encoding that any string is uniquely decodable.

Let $s=s\_1...s\_n$ be some string encoded with a prefix free code. Since our code is prefix free, there exists a unique prefix of $s$, $s\_1...s\_j$ which is a code word. $s\_{j+1}...s\_n$ is also a valid encoding (we removed a single codeword from a concatenation of codewords), so by our inductive hypothesis, $s\_{j+1}...s\_n$ is uniquely decodable, which completes the proof.
> 3 votes

---
Tags: encoding-scheme
---


# Question
Title: How does a cache handle overwriting between 2 addresses in the same block?
Consider a byte-addressable cache with block size 16 bytes, bytes 0-15 form one block. First I write an int(let's say 7) to address 0, so now bytes 0-3 contain the int 7. Now if I try to write another int(9) to address 2, then how does the cache handle this? Also if i try to read from byte 1, what effect does that have?

The lectures I'm watching suggest treating a block as the atomic unit in a cache, because keeping track of all the unwritten and written bytes will be a resource heavy task. So how will the above situation pan out? Will every block contain only 1 instance of data, with every write beginning from byte 0? because that is the only possible solution i can think of.

# Answer
> 1 votes
Your program will work exactly as if there was no cache, and as if each single memory operation was completed before the next one is started.

Typical implementations will first make sure that the complete data for a cache line is stored in the cache. So for example writing four bytes may first read the complete 64 byte line from memory.

With a line of data in cache, accessing it can be done very quickly. If there are multiple instructions reading or writing, you can expect one to be executed completely in each cycle. If instructions access different cache lines, a powerful processor may allow simultaneous access to two different cache lines. A powerful processor may also allow simultaneous access to clearly separate parts of a cache line. 4 bytes at location 2 and 4 bytes at location 6 may not count as “clearly” separate.

If you access different cache lines, the one that is accessed by a later instruction may be available in the cache earlier, and the actual access may happen earlier.

# Answer
> 0 votes
> The lectures I'm watching suggest treating a block as the atomic unit in a cache

This is true when you are writing the contents of a cache block back to memory. However, when you write to a cache block, you usually only overwrite part of it (x86 has 64-byte cache blocks). You can assume the cache writes are similar to memory writes.

> ... how does the cache handle this?

This is implementation-specific. When you do two back-to-back STORE\_WORD instructions, say storing 7 and 9 to address 0x0 and 0x2 respectively (this is forbidden on many platforms like ARM because your memory accesses are not alligned), a cpu may just do two writes, while some other cpu may do the overwritting internally and only one write to the cache. You can argue that the latter probably will never happen because it increases hardware complexity without much performance gain, but in theory some one can do this.

> ... if i try to read from byte 1, what effect does that have?

You will get the "correct value", i.e. the byte from the first-written 7. This is because your program SPECIFIES the behavior. In other words, the second write must happen at least effectively after the first write has finished. How the processor manages the cache is implementation detail and no matter how it is implemented, you should see the behavior defined by the ISA.

---
Tags: computer-architecture, memory-management, cpu-cache, cache
---


title: Proving decidability of language

text:
# Question
Title: Proving decidability of language
Prove or disprove: The following language $L$ is decidable:

$\\{ \langle M, t\rangle: M \text{ is a Turing machine and } \forall w \in \\{0,1\\}^\* \[M(w) \text{ halts in at most } t \text{ steps} \]\\}$

So for proving I need to construct a TM $U$. If it accepts $L$, so L is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, t\rangle$:

1. $i:=1$;
2. Simulate one step of $M$ on $w$.
3. If $M$ accepted $w$ then $U$ accepts.

If $M$ rejected $w$ then $U$ rejects.

If $i ≥ t$ then $U$ rejects.
4. Else $i:=i+1$; goto step 2."

Because $U$ is the decider machine (finite number of steps) $\longrightarrow$ $L$ is the decidable language.

Is this solution correct? Or I should do it in another way?

# Answer
I have not fully understood the algorithm, as it didnt state what $w$ is.

Although, the language $L$ is decidable:

Build the TM for the following algorithm: (assuming input of form $\<M,t\>$)

1. For every $w\in\Sigma^\*$ **with** $|w|\le t$: 2. Emulate $M$ on $w$ for $t$ steps. If $M$ did not halt in that time, **reject**.
2. If for all such $w$, $M$ halted within $t$ steps - accept.

This algorithm always halts - as there are a finite number of $w$ with $|w|\le t$ (and it does not simulate $M$ for more than $t$ steps)

The algorithm is right:

1. If $\langle M,t\rangle\in L$ then $M$ will halt within $t$ steps on every $w$ we will check, therefore the algorithm will accept.
2. If $\langle M,t\rangle\notin L$, then there is some $w\in\Sigma^\*$ where $M$ doesnt halt on him within $t$ steps. Notice, that if we define $\hat w=w\_{1,...,t}$ to be the first $t$ letters of $w$, then also $M$ wouldnt halt on $\hat w$ within $t$ steps, as if it would have been - then $M$ didnt read move its head right more that $t$ times - and therefore for every $y\in\Sigma^\*$, $M$ halts on $\hat wy$ within $t$ and specifically $w$ too. The algorithm can find the $\hat w$ (since $|\hat w|=t$) and will reject because of it.
> 1 votes

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


# Question
Title: Dynamic Programming - Thief Variation Probem
I've encountered a Dynamic Programming problem which is a variation of the thief one.

Say you are a thief and you are given a number of houses in a row you should rob :

$$House\_1,House\_2 \dots House\_N$$

with each house having the following values : $$(x\_i \geq y\_i \geq z\_i \gt0)$$

You profit **X** if you rob a house but **none of the adjacent** houses.

You profit **Y** if you rob a house and **exactly one of the adjacent** houses.

You profit **Z** if you rob a house and **both of the adjacent** houses.

Cases with houses A-B-C would be :

$$Profit(001)=0+0+C\_x$$ $$Profit(101)=A\_x+0+C\_x$$ $$Profit(110)=A\_y+B\_y+0$$ $$Profit(111)=A\_y+B\_z+C\_y$$

**Where 1 stands for robbing the house and 0 for not robbing the house**

Obviously you can't utilize the **Z** value for the first and the last house and each set of values is random.

Now the question is : Which houses should you rob to get the maximum profit?

My main issue is that i can't establish a base case for this problem.

At first i thought of creating a **N\*M array with M being the maximum amount of houses i can rob from 0-N when every house is not robbed** and think like : Rob it - Don't rob it but came up with nothing.

Any tips or directions would be appreciated.

Thanks in advance.

# Answer
> 4 votes
For $i=1,\dots,N$, and $r \in \\{S,R,B\\}$ define $OPT\[i,r\]$ as the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints:

* If $x=S$ (as in **S**kip) then house $i$ must not be robbed.
* If $x=R$ then house $i$ must be **R**obbed while house $i+1$ will not be robbed (to avoid a case distinction later we pretend that house $i+1$ exists even when $i=N$).
* If $x=B$ then **B**oth house $i$ and house $i+1$ need to be robbed.

For $i=1$ you have $OPT\[1,S\] = 0$, $OPT\[1,R\] = x\_1$, $OPT\[1,B\] = y\_1$.

For $i\>1$ you have: $$ OPT\[i, S\] = \max\\{ OPT\[i-1, S\], OPT\[i-1, R\] \\}, $$ $$ OPT\[i, R\] = \max\\{ x\_i + OPT\[i-1, S\], y\_i + OPT\[i-1, B\] \\}, $$ $$ OPT\[i, B\] = \max\\{ y\_i + OPT\[i-1, S\], z\_i + OPT\[i-1, B\] \\}. $$

The optimal profit is then: $\max\\{OPT\[N, S\], OPT\[N, R\] \\}$ and can be computed in $O(N)$ overall time using the above formulas.

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


# Question
Title: Complement of $0^n1^n | n \in \mathbb{N}$
I know why A is irregular by Closure properties of irregular language. I also know the complement of $ \\{ 0^n 1^n | n \in \mathbb{N}\\}$ is $A = \\{ 0^i 1^j| i \neq j\\} \cup (0 \cup1)^\*(1)(0 \cup1)^\*0(0 \cup1)^\*$, but I don't see how $A^\* = \sum^\*$. Any help would be appreciated!

# Answer
Since $0 \in A$ and $1 \in A$, any word $w \in \Sigma^\*$ can be written has a concatenation of $n=|w|$ words $w\_1, \dots, w\_n$ such that each $w\_i \in A$ (showing that $w \in A^\*$). In order to do so it suffices to pick $w\_i$ as the $i$-th character of $w$, i.e., $w\_i$ is either $0$ or $1$.
> 4 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


title: How does the NegaScout algorithm work?

text:
# Question
Title: How does the NegaScout algorithm work?
On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting \[Alpha,Beta\] to \[Alpha,Alpha-1\].

I do not understand the whole process of NegaScout.

How does it work? What is its recovery mechanism when its guessing failed?

# Answer
> 8 votes
NegaScout is a very simple algorithm. To understand we should first review **iterative deepening negamax (minimax)**.

Iterative deepening is a technique to search for depth i, then i+1, then i+2, etc. This is an example of dynamic programming. During each iteration we have our best guess of what the best move would be. Most programs would keep this move in a hashing table.

Imagine we are now at iteration i+1, and we have the best move from the last iteration i. Also assume we have 5 nodes to search from here, what should we do?

If we assume we have done a reasonably good job of scoring during our last iteration, the best move from the last iteration (which we get from the hash table) **should** also be the best move for that depth in the current iteration.

If our assumption is correct, we can then save time by searching every move other than the best move (the four moves not in the hash table) with a `null window`. For example:

`score := -pvs(child, depth+1, -α-1, -α, -color)`

Note that Negascout is also known as Principal-Variation Search hence the `pvs`. And also note `-α-1` and . They are the alpha and beta values, respectively, we are passing to the next call / depth. Since the width of the window is only 1 (-α-1 - (-α)), essentially null, this enables cutoffs to be produced very quickly, since the greater the gap between alpha and beta, there's more moves that can fit between them and not get cutoff. So the search will return the following:

* If it fails below α, the move is worse than what we already have, so we can ignore it
* If it fails above β, the move is too good to play, so we can also ignore it
* Otherwise, if it doesn't fail, we need to do a new search properly to get the exact value of that child

Of course, we will still search the best move (the one we get from the hash table) with a proper alpha and beta window. We need to do this because we need to know the exact value of the best node.

Everything I've said is implemented in the following pseudocode which can also be found **here**. The pseudocode specifies `if child is not first child` but this is a way to check whether the move is also the best move in the previous iteration since it orders the children based on how good it is. Furthermore, it also displays depth in reverse order, starting at a depth i and ending at 0.

```
function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            # search with a normal window
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # alpha-beta cut-off
        if α >= β
            break

    return α

```

# Answer
> 4 votes
In order to understand NegaScout, it is necessary, at first, to be very clear on what the parameters $\alpha$ and $\beta$ mean.

Given a chess position to evaluate. All of the legal moves have their own *scores* (relative to a given *depth*). The better the move, the higher its score is. Some moves have the highest score - these are *the best* moves; they all have the same score.

The NegaScout function **must** find one of the best moves, and **must** calculate its score. This is the purpose of the function. Such is the formal description of the task NegaScout solves. The key feature is NegaScout does not have to return the computed values.

Whether NegaScout returns a best move itself, depends on the function's implementation. What makes this algorithm (and also the classical AlphaBeta algorithm) faster than brute force is the return value. If $depth = 0$, then NegaScout evaluates the position *statically* by making a call to a special function and returns the obtained estimation - brute force does the same in this case; static evaluation is a separate task out of NegaScout's scope. Suppose $depth \> 0$. Then three cases are possible (relatively to the given depth!). Note $\alpha \< \beta$ (otherwise the return value is undetermined).

*Case 1: there are no moves stronger than $\alpha$*. In this case NegaScout **must** return any number $\xi\le\alpha$ such that the score of any legal move in the current position satisfies the condition $score \le \xi$.

*Case 2: the score of the best moves belong to the interval $(\alpha,\beta)$*. In this case NegaScout **must** return the score of the best moves (remember all best moves have the same score, by definition).

*Case 3: there is a move stronger than $\beta$*. In this case NegaScout **must** return any number $\xi \ge \beta$ such the score of that *at least one* move satisfies the condition $score \ge \xi$.

Pay attention at the empathized word "must": don't try to prove these statements by analyzing an implementation of the method. Instead, *assume* what is written above as the formal definition of NegaScout; i.e. if a function does not return a value satisfying the conditions given above, then assume such a function not to be an implementation of NegaScout, according to the definition. After this, look at the pseudocode given above by the user HelloWorld and make sure this implementation really satisfies our formal definition of NegaScout.

As soon as you understand this formal definition, NegaScout will become evidence. It is obvious NegaScout coincides the brute force in case $(\alpha = -\infty) \\;\\&\\, (\beta = +\infty)$.

And the last remark. The classical AlphaBeta algorithm may return any $\xi \le \alpha$ and any $\xi \ge \beta$ (without any restrictions) in the cases 1 and 3, respectively: this is the only its difference from NegaScout.

---
Tags: algorithms, algorithm-analysis, search-algorithms
---


# Question
Title: How to decide whether a language is decidable when not involving turing machines?
For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no luck. How to prove that this is undecidable?

# Answer
It might come as a surprise to you, but the language $$L=\\{k\in\mathbb N :\text{the binary expansion of} \sqrt2\text{ contains $k$ consecutive $1$s}\\}$$ is decidable, even if we could not *construct* an *algorithm* that can demonstrate whether the binary expansion of $\sqrt2$ contains $k$ consecutive $1$s or not given arbitrary $k$.

As Yonatan N indicated, let us take a closer look at $L$. There are two disjoint cases.

* $L$ is $\mathbb N$. Then $L$ is trivially decidable. For any given $k$, just return "Yes".
* $L$ is not $\mathbb N$. Then there are some numbers in $\mathbb N$ that is not in $L$. Let $m$ be the minimum of such number. Then $L$ must be $\\{1, 2, 3, \cdots, m-1\\}$. Why?

+ Since $m\>2$ is the minimum number that is not in $L$, $m-1$, which is a number smaller than $m$, must be in $L$. That is, $\text{bin}(\sqrt 2)$ contains $m-1$ consecutive $1$s. So it also contain $k$ consecutive $1$s for all $k\le m-1$.
    + Since $\text{bin}(\sqrt 2)$ does not contains $m$ consecutive $1$s, it does not contain $k$ consecutive $1$s for any $k\gt m$. That is, $k\not\in L$.

Now we can construct an algorithm that decides $L$. For any given $k$, check whether $k\lt m$. If yes, return "Yes". Otherwise, return "No".

In either case, there *exists* an algorithm that decides $L$. Hence $L$ is decidable.

---

Most people, I believe, felt a bit disoriented the first time when this kind of proof/conclusion was encountered. Or at least myself.

The essential point is we do not have to identify/construct/bind to one algorithm that decides $L$. We do not have to understand fully what is $L$. All we need is there *exists* an algorithm that decides $L$, whatever $L$ turns out to be. This deviates from "the naive sense of decidability" that you might have even before you encountered the theory of computation/decidability/computability.

In particular, I do not know whether $L$ is $\mathbb N$ or not. Some people claimed to have proved that $L=\mathbb N$. I have not checked their proof, yet. Although it is certainly interesting to find whether $L=\mathbb N$, its result will not change the fact that $L$ is decidable.
> 4 votes

---
Tags: undecidability
---


# Question
Title: is co-NP-hard contained in EXPTIME-hard or vice-versa?
is **co-NP-hard** contained in **EXPTIME-hard** or vice-versa?

# Answer
It is known that co-NP $\subseteq$ PSPACE $\subseteq$ EXPTIME, so every EXPTIME-hard problem, must also be a co-NP-hard problem (as there is a polynomial time reduction from every $L\in$ EXPTIME to it, and therefore also from every $L\in$ co-NP)

Therefore EXPTIME-hard $\subseteq$ co-NP-hard.

Note that this argument **does not hold** for co-NP-complete and EXPTIME-complete. This is still an open problem (i believe).
> 3 votes

---
Tags: complexity-theory, co-np
---


# Question
Title: How to show that Language is not Context Free?
There is a question to show that $L=\\{a^{n!} \mid n \geq 0 \\}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the snapshot of the answer which I could not figure out. Could anybody correct it so that the puzzle could be solved?

# Answer
> 1 votes
There is a pumping lemma for context free languages too.

In you case, if $L$ was context free, then there would be some constant $n\_0$ such that all words $a^{n!}$ with $n! \ge n\_0$, $a^{n!}$ could be decomposed as: $$ a^{n!} = a^x a^y a^v a^w a^z $$ such that $y+v+w \le n\_0$, $y+v \ge 1$, and for all $i \ge 0$: $$ a^x a^{yi} a^v a^{wi} a^z \in L. $$

Calling $\ell = y+w$ and simplifying, the above can be rewritten as: $ a^{n!} = a^\ell a^{n! - \ell} $ such that, for all $i \ge 0$, $a^{n!+(i-1)\ell} \in L$.

This cannot be true. To see this pick, e.g., $n=n\_0+2$, and $i=0$. Then $a^{n!+(i-1)\ell} = a^{(n\_0+2)!-\ell}$, where $ (n\_0+2)! - \ell \le (n\_0+2)! - 1 \< (n\_0+2)! $ and $ (n\_0+2)! - \ell \ge (n\_0+2)! - n\_0 = (n\_0+1) \cdot (n\_0+1)! - n\_0 \> (n\_0+1)! $, showing that $n!-\ell \in ((n\_0+1)!, (n\_0+2)!)$ and hence it cannot be expressed as a factorial.

# Answer
> 0 votes
A unary language $L$ is context-free iff it is regular iff it is eventually periodic, that is, if the set $N = \\{n \in \mathbb{N} : a^n \in L\\}$ satisfies the following property: there exist $m \geq 0$ and $r \geq 1$ such that for all $n \geq m$ we have $n \in N$ iff $n + r \in N$.

In particular, any unary language which has zero limiting density (i.e., $\min\_{n\to\infty} |N \cap \\{1,\ldots,n\\}/n = 0$) must be finite. Your language has zero limiting density, yet is infinite.

---
Tags: context-free, pumping-lemma
---


# Question
Title: How to prove semi-decidable = verifiable?
A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y)

A language is semi-decidable iff there is some Turing machine that accepts every string in L and either rejects or loops on every string not in L.

How can we show that the class of semi-decidable problems is equivalent to the class of verifiable problems? Or are they not?

# Answer
Its obvious why a semi-decidable language is verifiable ($w$ would be the machine's computation history on $x$). Now, we will show the other way:

Let $V(x,w)$ be a verifier for $L$. Define $M(x)$ as the following algorithm:

1. Let $S$ be an empty array (of turing machine emulations)
2. For every $w\in\Sigma^\*:$
    3. Add a new emulation of $V(x,w)$ to $S$.
    4. For every emulation $E\in S:$
        5. Compute one step for $E$. If, $E$ accepted, then **accept.**

This algorithm is correct, since if $x\in L$ then there is some $w\in\Sigma^\*$ with $V(x,w)=True$ and therefore the algorithm will accept.

If the algorithm accepted, then there must be some $w\in\Sigma^\*$ where $V(x,w)=True$ and thus $x\in L$ by definition
> 2 votes

---
Tags: semi-decidability
---


# Question
Title: check if a binary tree is a binary search tree
I have some doubts about this algorithm which checks if a binary tree is a binary search tree:

```
isAbr(x)
    {
            if(x == NULL)
                    return <true, -∞, +∞>;
            if(x.left == NULL && x.right == NULL)
                    return <true, x.key, x.key>;

            <abrLeft, minLeft, maxLeft> = isAbr(x.left);
            <abrRight, minRight, maxRight> = isAbr(x.left);
            abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);
            min = MIN(minLeft, minRight, x.k);
            max = max(maxLeft, maxRight, x.k);

            return <abr, min, max>
    }

```

in particular, it is not clear to me what happens when a node has only one child:

for example, here, the node with the value 6 returns $\<true, 6, 6\>$, and the NULL node to the right of the root returns $\<true, -∞, + ∞\>$; but with the instruction `abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);`don't we get FALSE $(8 \< -∞)$?

# Answer
1. `abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);` should likely be comparing with `maxLeft` and `minRight`, not `maxLeft` and `minLeft`
2.

```
if(x == NULL)
    return <true, -∞, +∞>;

```

I'm guessing the point of returning infinities here is to make a NULL vertex NEVER fail the `>` and `<` comparisons above, in which case in makes more sense to return `<true, +∞, -∞>;`
> 1 votes

# Answer
The algorithm as is is incorrect because ±∞ is really just a moniker for "less/greater than everything else", and it's not useful to claim that a null node has these as its min and max subtree values because it doesn't actually exist.

Using these special values as placeholders for the min and max in nonexistent subtrees therefore makes very little sense because when we consider that every finite BST has null nodes beneath its leaves, that implies that those special values are the min and max in every finite BST; this statement is patently untrue.

In addition and as an expansion on the previous point, this behavior is inconsistent with the way the algorithm handles leaf nodes; both of the children for these nodes are null, so why don't the leaves also have ±∞ as min and max values?

To fix this one would need to ensure that null children (and their relationship with the current node) are automatically considered valid. Something to the effect of:

abr = abrLeft and abrRight and (x.left == nil or x.key \> maxLeft) and (x.right == nil or x.key \< minRight)

should do the trick.
> 0 votes

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


title: Is this language L regular?

text:
# Question
Title: Is this language L regular?
Let's say we have the language L = {w $\in$ {a,b}$^\*$ : ($\exists n \in \mathbb{N} $)\[$w|\_b = 5^n$\]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar with the Myhill-Nerode theorem but I don't know how to apply it.

# Answer
> 2 votes
You don't need the Myhill-Nerode theorem. Suppose that $L$ was regular and let $c\>0$ be its pumping length.

The word $b^{5^c}$ is in $L$ and therefore there is some positive constant $k \le c \< 5^c$ such that $b^{5^c + ik} \in L$ for all integer values of $i \ge -1$. For $i =1$ you must have $b^{5^c + k} \in L$ which implies that $5^{c} + k$ is a power of $5$.

This is a contradiction since $ 5^ c \< 5^c + k \< 5^c + 5^c = 2 \cdot 5^c \< 5^{c+1}. $

If you still want to use the Myhill-Nerode theorem you can proceed as follows: Pick any two non-negative integers $i,j$ with $i\<j$ and consider the two words $x= b^{5^i}$ and $x = {5^j}$. Let $z = b^{4 \cdot 5^i}$. Notice that $xz = b^{5^i + 4 \cdot 5^i} = b^{5^{i+1}} \in L$ while $yz = b^{ 5^j + 4\cdot 5^i} \not\in L$ since $5^j \< 5^j + 4 \cdot 5^i \< 5^j + 4 \cdot 5^j = 5^{j+1} $. Therefore $z$ is a distinguishing extension for $x$ and $y$ and they cannot belong to the same equivalence class for the relation $R$ defined by $\alpha R \beta$ iff $\alpha \in \Sigma^\*$ and $\beta \in \Sigma^\*$ have no distinguishing extension. This shows that the number of equivalence classes in the quotient set $L\_{/R}$ is not finite and, by the Myhill-Nerode theorem, $L$ is not regular.

---
Tags: regular-languages
---


# Question
Title: one for loop wraps 2 indexof method, what is the time efficiency?
I'm confused about how to know the time / space efficiency.

1. If there is an array whose size is `n`, do a for loop on this array, so that time efficiency should be O(n) = n, where n is array size. then if I have two indexof methods in the loop, indexOf and lastIndexOf, should the O(n) become n\*(2n)? because each of the indexof methods has the time efficiency of n as well just like a for loop?
2. how to know the space efficiency of this method?

```
char firstNotRepeatingCharacter(String s) {

    char[] str = s.toCharArray();
    // n
    for (int i = 0; i < str.length; i++) {

        char item = str[i];
        // 2n
        if(s.indexOf(item) == s.lastIndexOf(item)) return item;

    }
    // 2n2

    return '_';
}

```

# Answer
> 1 votes
Yes, you are correct. But time complexity we measure **only** in big-O notation.

So the code above has time complexity $\mathcal O(n^2)$

The space complexity depends on `indexof`'s space complexity. Assuming it was done with a for loop and a simple comparison, the space complexity would be $\mathcal O(log(n))$ \- as the storing the array length $n$ required $log(n)$ bits, and therefore keeping in memory the index `i` will take at most that much space.

---
Tags: time-complexity, space-complexity, big-o-notation
---


# Question
Title: How to find the square with the highest total sum
I have an integer matrix of size `4n x 4n`. I need to select a part of the matrix of size `n^2` from which adds up to the most.

For example if `n = 3`. I have a matrix of size `12 x 12`. In the below picture, you can clearly see that `n^2` square (outlined in red) adds up to the most. For simplicities sake, I made all the numbers 5, expect for 9 of the boxes which are `9999` so its clear that that is the `n^2` squares that add up to the most.

My approach to solving this problem was to essentially create a `n^2` square and brute force the entire `4n x 4n` matrix. However, that runs in `O(n^4)` time complexity. How can I do it in `O(n^2)`?

# Answer
Try building a summed area table—a table where the value in each cell is the sum of all the values above and to the left, inclusive, of the cell in the original table. See if you can figure out an $O(n^2)$ solution from that.
> 2 votes

---
Tags: algorithms, complexity-theory, time-complexity, matrices, big-o-notation
---


# Question
Title: Can a non-deterministic machine merge its branches?
Does an NDTM have the power to combine computational branches ie. can a result from branch A be used in the next step in the computation along branch B? Can branches use each others' results, diagrammatically 'merging'?

Example:

Branch i arrives at the number b after n steps, branch j arrives at the number c after 2n steps. After we have waited for both to arrive at their respective values, the computer, on the next step, multiplies those values 3\*5 (effectively merging the different branches). Can it do this?

# Answer
One view, explained by Tom here, is that nondeterministic branches work in parallel.

A more standard view, I think, is to view nondeterminism the way it is treated in physics, in logic, and in Dijkstra/Hoare style algorithm specification: at certain points, multiple continuations are possible, one of which will be taken. The 'multiple possible universes' do not exist in parallel, but they are alternative potential states of the world, alternative ways for the algorithm to continue, one of which will become reality.

So no, steps taken in one branch are not available in another branch. You either follow one branch or the other.
> 4 votes

# Answer
No, that's not how non-determinism work.

You can think about non-determinism as parallel universes. All the branches runs concurrently, in a different plane, and to itself it seems like it's the only run in the world.

The language accepted by a non-deterministic turing machine is every word that there exists a universe (or respectively a run) such that it gets accepted in it. So in that sense, non-determinism means run all the possibilities, and choose the best one.
> 3 votes

---
Tags: nondeterminism
---


# Question
Title: Proving undecidability for a language which contains string with certain syntax
Lets say we have the following problem:

$$\mathcal{L}\_1 = \\{\langle \mathcal{M} \rangle | \mathcal{M}\ \text{is a Turing machine and $\mathcal{L}(\mathcal{M})$ contains a string with exactly three zeros}\\}$$

We would like to prove that $\mathcal{L}\_1$ is undecidable. I would generally use Rice's theorem to prove that a language is undecidable, but in the present case, we aren't dealing with a semantic property of the language but rather its syntax. In cases where we have to prove based on the language's construction, how would the process look like and differ from proving with Rice's theorem?

# Answer
> 0 votes
It can be thought of a semantic property of the language, and its **ok** to use Rice's theorem here.

Define $C=\\{L|\text{there is a string with exactly 3 zeros in }L\\}$

So, $L\_1=\\{\<M\>|M \text{ is a turing machine and } L(M)\in C\\}$ and because $C\neq\emptyset$ and $C$ is not every language, then by Rice's theorem, $L\_1\notin R$.

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


# Question
Title: Order notation subtractions in Fibonacci Heap
Can order notation on its own imply:

$O(D(n)) + O(t(H)) - t(H) = O(D(n))$

My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is \> 0.

Well, this is actually the case, but there are underlying factors. This equation appears in Fibonacci heap analysis in CLRS (518). The justification for this step comes from the underlying potential function. According to the authors, "we can scale up the units of potential to dominate the constant hidden in $O(t(H))$". I want to know how this happens, but don't really know how to ask this complicated question.

# Answer
> 2 votes
As you point out your first equation is not necessarily correct.

Let me rewrite it by explicitly adding the multiplicative constants: $\alpha D(n) + \beta t(H) - \gamma t(H) = O(D(n))$, where $\gamma =1$. Here the problem is that $\beta$ might be larger than $\gamma = 1$.

What the authors are saying is that instead of thinking that one unit in the value of your potential function $\Phi(H)$ contributes one unit of potential, you can imagine that it is actually representing $\gamma$ units of potential. This amounts to redoing the analysis with a new potential function $\Phi'(H)$ defined as $\Phi'(H) = \gamma \cdot \Phi(H)$. If you do so, then you are able to control the value of $\gamma$ in the above equation, while $\beta$ stays the same.

Picking a value of $\gamma \ge \beta$ ensures that $\alpha D(n) + \beta t(H) - \gamma t(H) = \alpha D(n) - \underbrace{(\gamma -\beta)}\_{\ge 0} t(H) \le \alpha D(n) = O(D(n))$, as desired.

---
Tags: algorithms, algorithm-analysis, heaps, big-o-notation
---


# Question
Title: How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language
I found this How do I verify that a DFA is equivalent to a NFA? but as it states it is not really a good question more of how can I check myself during an exam. Because as you might know to do this by hand for \< 5 states is really hard to do without any mistake and I only get credit for a correct construction and not understanding that REGΣ = NEAΣ = DEAΣ

# Answer
> 1 votes
Proving such a claim rigorously can be usually done with induction on word length $|w|$.

---
Tags: finite-automata, regular-expressions
---


# Question
Title: Generate a random magic square on a large field
If consecutive natural numbers 1 .. n^2 are placed in a n\*n grid so that sum of numbers in each column and in each row is a constant then we call it a magic square. I would like to generate magic squares of size 16x16 and 256x256 for not skewed byte mapping. Maps arranged as magic squares tend to have better distribution properties. Algo should produce a map that depends on the seed, rather than yield the same result each time.

`expectedSum = ((1+n*n)*n)/2)`. I can shuffle an array using some form of `SecureRandom` that accepts a seed. Then in case of a small square I can go for a brute force `for` loop.I can just brute force 3x3 magic square. Considering symmetries I need to check less than 8\*(7!) or about 40k possibilities.

This approach wouldn't work for 16x16 board because 256! \> 10^500 is quite large. My best guess is to find two row\_column pairs such that sums along row and column are greater than the expected sum in first pair and lower in second pair. If shared element in first pair is greater than in the second pair - swap elements. This algo seems better than bruteforce (can complete in reasonable time), but there is no guarantee that it halts. Consider 2x2 square to see how it fails.

What is a good Monte-Carlo approach to solve a large magic square?

# Answer
> 2 votes
Here's a decent algorithm that will quickly generate large magic squares.

First Step: Establish Rows

1. Put all numbers in a bucket.

2. Loop through the rows, 0 to n.

3. Take out n (where n is the size of row) numbers randomly from the bucket.

4. Sum those numbers. If they don't equal the solution sum, goto 3.

5. If they do equal the solution sum, stick them into your grid at the row you are on, remove the numbers used from the bucket, and goto 2.

You'll now -- very quickly -- have a square with each row having the correct sum.

Second Step: Establish Columns

1. Loop through the columns, 0 to n.

2. Shuffle the elements in each row from the beginning of the row + the column you are on, to the end of the row. (That is, if we are working on the first column, shuffle all the elements in each row. If we are working on the second column, shuffle all the elements but those in the first column, etc.)

3. Sum the column. If it doesn't equal solution sum, goto 2.

4. Goto 1 and proceed to the next column.

Now, in this step, you'll need a bail counter... that is, after 1000 tries or so, give up and return to the First Step. The number of attempts needs to increase as n increases... For a 25x25 grid, for example, let it try 100,000 times or so before giving up and creating a new set of rows.

Third Step: Establishing Diagonals

1. Swap any two rows and swap any two columns.

2. Check diagonals sums.

3. If the sum equals solution sum, you're finished. If not, go to 1.

Once again, stick in a bail counter... after 10,000 tries or so, go back to First Step.

---
Tags: monte-carlo
---


# Question
Title: Show that a decidable language is not decided by a decider in a given set
M.Sipser's Introduction to the Theory of Computation offers the following problem in its chapter on decidability:

*Let A be a Turing-recognizable language consisting of descriptions of Turing machines, {⟨M1⟩,⟨M2⟩, ...}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)*

My qualm about this is that the question seems to imply finding a decidable language, the decider for which is not in the set of all deciders, which goes against the definition of decidability of languages.

Could you explain whether my doubts are justified? And if not, could you provide a proof (or a sketch of a proof) for the given problem (with or without the enumerator that is mentioned in the hint)?

# Answer
> 2 votes
Suppose that $A$ is a recognizable set containing descriptions of always halting Turing machines. We want to show that there exists a decidable language $L$ such that for any $M$ deciding $L$ we have $\langle M\rangle\notin A$.

We can construct such $L$ via simple diagonalization. Assume $A$ is infinite (otherwise the problem is trivial). We will define a Turing machine $M$ such that $L(M)$ does not have a decider in $A$. Let $M\_A$ be an enumerator of $A$. Given input $x$, $M$ executes $M\_A$ untill it outputs the $|x|'th$ word in the enumeration $\langle M\_{|x|}\rangle$. Now, execute $M\_{|x|}$ on $x$ and flip its answer.

I leave it to you to show that $M$ always halts and that $L(M)$ disagrees with $L(M\_i)$ on at least $2^i$ inputs, where $M\_i$ is the i'th Turing machine in the enumeration of $A$.

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


title: How to pronounce "P/poly"?

text:
# Question
Title: How to pronounce "P/poly"?
Another question is about the reasons for calling P/poly "P/poly". My question is instead about its (verbal) syntax rather than its compositional semantics:

How is "P/poly" pronounced (in English)?

1. Like "p polly"?
2. Like "p slash polly"?
3. Like "p given polly"? (Maybe the slash for advice is analogous to slash or vertical bar for conditional probability: $\mathsf{P}(A/B)$.)

I hope it's OK to ask such a trivial question. I'd rather not develop a bad habit during self study.

# Answer
The Complexity Zoo has a pronunciation guide by Scott Aaronson "for those who insist on communicating verbally about complexity." It recommends the "p slash polly" option.
> 6 votes

---
Tags: complexity-theory, terminology
---


# Question
Title: Reducing 3-coloring problem to trio representatives
> A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing **exactly one** member of each trio. Is such assignment possible?

My goal is to use polynomial-time reductions to transform 3-coloring of a graph into this problem. However, I'm stuck on the correct representation.

* If each vertex is a different student and edges represent being in the same trio, how do I separate trios?
* If each node represents a trio, what could be a sensible meaning of the edges?

I suspect that since a 4-clique has no adequate 3-coloring (which could also mean that 4 trios with the same three members have no possible representative assignment), the latter option could be more sensible, but I'm not sure on how to proceed with this reduction proof.

# Answer
Let $G = (V,E)$ be an instance of $3$ coloring. Construct an instance $\phi$ of 3-SAT as follows.

* For each vertex $v \in V$ create $3$ variables $v\_a, v\_b, v\_c$ representing the $3$ possible ways to color of $v$.
* For each vertex $v \in V$ create the clauses $(v\_a \vee v\_b \vee v\_c) \wedge (\overline{v\_a} \vee \overline {v\_b}) \wedge (\overline{v\_b} \vee \overline {v\_c}) \wedge (\overline{v\_c} \vee \overline {v\_a})$. This encodes the fact that $v$ must be colored by exactly one color.
* For each edge $(u,v) \in E$ create the clauses $( \overline{v\_a} \vee \overline{u\_a} ) \wedge ( \overline{v\_b} \vee \overline{u\_b} ) \wedge ( \overline{v\_c} \vee \overline{u\_c} )$. This ensures that $u$ and $v$ cannot be given the same color.

Clearly the above reduction can be performed in poylnomial-time and ensures that there is a satisfying assignment to $\phi$ iff there is a 3-Coloring for $G$.

Now transform the instance $\phi$ of 3-SAT into an equivalent of instance $\phi'$ of 1-in-3 SAT (see here for the definition of 1-in-3 sat and the reduction from 3-SAT).

We have hence shown that 3-Coloring is polynomial-time reducible to 1-in-3 SAT. It turns out that 1-in-3 SAT is exactly your problem: the set of students is the set of variables and, for each clause $\\{x\_i, x\_j, x\_k\\}$ you create a group containing students $x\_i$, $x\_j$, and $x\_k$. Setting a variable to true corresponds to selecting the corresponding student as a leader.
> 1 votes

---
Tags: complexity-theory, graphs, np-complete, colorings, polynomial-time-reductions
---


# Question
Title: Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2
If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n\_0$ such that $f(n)\<cn^2, \forall n\ge n\_0$, can I do this all in one step by putting in values of $c$ and $n\_0$ at once or do I have to put in values of c first and then get n on one side and put in values for $n\_0$, the ***for all*** $n \ge n\_0$ confuses me.

# Answer
It all depends on the case and how easy it is to search $n\_0$ or use $c$, in your case you can show that $2n + 1$ belongs to $n^2$, taking the constant $c = 1$, so that in the proof of BigO, $g (n)$ dominates $f(n)$, what is the same $2n + 1 \le c (n^2)\to 2n + 1 \le n^2$; now you can search a $n\_0$.
> 1 votes

# Answer
equation here is f(n) \< c(n^2), here we have 2 unknowns, a mathematical equation with one unknown can be solved in 1 step, but with two unknowns you have to substitute one with some value to find another one. the number of steps increase with number of unknowns. So No its not possible to do all this in one step. Also definition of big O is intuitive, by proving f(n) \< cg(n) we are proving that f(n) does not grow faster than g(n), in our case f(n) is a linear equation, while g(n) is quadratic, its obvious that a quadratic equation will grow faster than any linear equation(meaning linear equation grows like 1,2,3,4,5 while quadratic will grow like 1,2,4,8,16 so on i hope you get my point).
> 0 votes

# Answer
You have to demonstrate that there is one c and one $n\_0$ such that 2n+1 \<= c $n^2$ for all $n \>= n\_0$. In this case, 2n+1 \<= $3n^2$ for n \>= 1, 2n+1 \<= 1.25 $n^2$ for n \>= 2, 2n+1 \<= 7/9 $n^2$ for n \>= 3 etc, so there are many combinations for c, n\_0.

To prove this, you usually go the easiest way possible. For example 2n+1 \<= 2n^2 + n^2 = 3 n^2, so c = 3 and $n\_0$ = 1 works. There is no need to find the smallest possible c or $n\_0$.
> 0 votes

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


# Question
Title: Implementing Queue operations in $\Theta(1)$
We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 elements, it returns the 4th element, if the Queue has 6 elements, it returns the 3rd or the 4th) and $popMiddle$(removes the middle element). We want both of these operations and all the other Queue operations to run in $\theta(1)$. Pick a suitable data structure for representing the Queue, implement the $popMiddle$, pop and push operations and explain in short how the other operations would be implemented.

I was thinking that the linked list would be a good pick if we keep in mind also the tail. But there is a problem when popping the middle because we have to iterate until there. An array would not be good because when erasnig we have to move all the elements to the left, if not there is no suitable formula to find the middle. Does somebody have better ideas?

# Answer
> 2 votes
A linked list is indeed a good idea. In addition to keeping a linked list, add a pointer to the middle item. When you insert an item, check to see if the current list's length is even or odd. If its even - move the pointer to the middle item one forward. Do the same (but backwards) when you are popping an item.

# Answer
> 2 votes
The problem can be solved by keeping two deques $Q\_1$ and $Q\_2$ (implemented, e.g., using doubly linked lists) with the invariant that $Q\_1$ always contains the first $\lceil n/2 \rceil$ elements of the queue.

The operations are implemented as follows:

* push($x$): push $x$ at the beginning of $Q\_1$. If the invariant is violated, then pop the last element $y$ from the end of $Q\_1$ and push $y$ at the front of $Q\_2$.
* get(): return the element at the beginning of $Q\_1$.
* pop(): pop the the element at the beginning of $Q\_1$. If the invariant is violated then pop the first element $y$ from the beginning of $Q\_2$ and push $y$ at the back of $Q\_1$.
* getMiddle(): return the element at the end of $Q\_1$.
* popMiddle(): pop the element at the end of $Q\_1$. If the invariant is violated then pop the first element $y$ from the beginning of $Q\_2$ and push $y$ at the back of $Q\_1$.

---
Tags: algorithms, data-structures
---


# Question
Title: How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$
I have tried solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact solution.

By substitution I got the following (not sure if it is correct):

$$T(n) = 5^kT(1) + \sum\_{i = 0}^{k}{5^{i}\left(\frac{n}{2^{i}}\right)^{2}\lg^{2}\left(\frac{n}{2^{i}}\right)}$$

I am not sure how to proceed from this. I don't even know if this approach is correct so far. How do I solve this recurrence?

# Answer
> 2 votes
You can use the master theorem. This theorem allows you to solve some recurrences of the form $T(n) = aT(n/b) + f(n)$.

You need to compare $n^{\log\_b a}$ with $f(n)$. In you case $n^{\log\_b a} = n^{\log\_2 5}$ and $f(n)=n^2 \log^2 n$.

There are different cases depending on how the above functions compare, but I am only going to discuss the one that is relevant to you (you can find more on Wikipedia).

In your case $f(n) = O(n^{\log\_b a - c})$ for some constant $c\>0$. To see this pick, e.g., $c=0.1$ and substitute to obtain: $n^2 \log^2 n = O(n^{\log\_2 5 -0.1})$, which is true since $\log\_2 5 - 0.1 \> 2$.

The master theorem then tells you that $T(n) = \Theta(n^{\log\_b a})$, which in your case is $T(n) = \Theta(n^{\log\_2 5})$.

---
Tags: time-complexity, recurrence-relation, summation
---


# Question
Title: Tag storage when using HBM as an L4 cache
I'm reading through **Computer Architecture: A Quantitative Approach, Sixth Edition**, and I'm trying to understand the issues surrounding tag storage in using HBM as an L4 cache. The primary concern mentioned in the book is "where do the tags reside?", since the sheer capacity (1 GiB) of the HBM with a small block size (64B) results in a large amount of tag bits (96MiB).

The book first suggests that the tag data might live *outside* of HBM, in a higher level of the memory hierarchy - except there is not enough SRAM capacity to store them, even in a modern L3 cache. It then goes on to suggest that keeping the tags in HBM as a solution to this. However, in L1-L3 SRAM caches, don't the tags reside in each of the caches themselves? Why would HBM be any different? Is it because we're somehow unable to perform hit detection/tag comparison on the HBM DRAM chips themselves (as is done in SRAM caches), so they need to be processed outside of HBM?

# Answer
> 1 votes
Disclaimer: It's been a while since I last read that book. It was an edition that pre-dated HBM. So I can't really refer to the book to find out what it's saying.

The "level" of a cache refers to how many steps removed it is from the CPU's load/store hardware. It means *nothing* beyond that. You can't just say "L3" and assume that it refers to the same organisation.

In a modern machine, there is usually one L1 cache per core, split between instruction and data. It may be virtually addressed or physically addressed depending on the architecture.

L2 cache is typically unified, instructions and data. But is there one per core, or one per die?

And what does L3 cache mean? Is *that* the one shared between cores on a die? Is the GPU on the die, and the L3 is shared between the CPU cores and the GPU? Is the L3 cache off-chip? Or perhaps the tags are on-chip and the data is off-chip? Maybe this is a NUMA machine, and the L3 is shared between all processors on the same board?

I think the issue here may be that any signal that has to go off the chip is more expensive than one that stays entirely on the chip. It usually requires higher electrical currents, and more time since the tolerances of a circuit board aren't as tight as they are on a die. So if you can't fit an entire cache on a single chip or package, it can make sense to split the tags from the data.

If you are a CPU die, for example, and a different die invalidates a cache line (e.g. it changes state from Shared to Exclusive in the MESI model), then all levels of your cache need to be potentially invalidated. That is an operation that only requires accessing and modifying the tags, not the data. So keeping the tags on-chip and storing the data off-chip could make sense here. This was extremely common back when you couldn't pack quite so many transistors on a die.

I don't know if any of that helped.

---
Tags: computer-architecture, cache
---


# Question
Title: Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$
Show that $O(\text{max}\\{f(n),g(n)\\})=O(f(n)+g(n))$

Can I keep the same constant $c$ in each of the cases?

Consider two cases: $$1)f(n)\>g(n);O(\text{max}\\{f(n),g(n)\\})⇒O(f(n))\Rightarrow d(n) ≤c⋅f(n);c\>0$$ $$2)f(n)≤g(n);O(\text{max}\\{f(n),g(n)\\})⇒O(g(n))\Rightarrow e(n)≤c⋅g(n);c\>0$$ Combining the 2 cases yields: $$d(n)+e(n)≤c⋅f(n)+c⋅g(n)$$ $$d(n)+e(n)≤c⋅(f(n)+g(n))$$ Which is definition of $O(f(n)+g(n))$

# Answer
> 2 votes
I guess the proof is fine except for the fact that you have used same costant in two different eqns. Even if you use(and you must use, because the constant you choose is arbitrary) two different conts say c1 and c2, the solution will imply the same.

---
Tags: asymptotics, landau-notation
---


title: decider for a question not clear

text:
# Question
Title: decider for a question not clear
This question was asked and answered but I cannot understand the solution.

1. Why is it sufficient to test all strings of |Q| + 1 length?
2. Why should special state q be found?

the original question: Show that the set of all TMs that move only to the right and loop for some input is decidable

L2={ M | M is a TM and there exists an input w such that in the computation of M(w) the head only moves right and M never stops}

# Answer
The pigeonhole principle. If you go through $|Q|+1$ states, then there must be a state you have been in twice already. This means that because the input is $\sqcup$ almost all of the time, then we are stuck in a loop and the machine wont halt
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Computability of sequential cubic-order algorithms
I have a cubic-order algorithm which must be executed sequentially; there appears to be no way of making it parallel.

I need to come up with an estimate of maximum input size that can be solved using today's technology. So, the essential problem seems to be how to relate the cost of a single step to execution time on a "typical" hardware. Is there a gold-standard way of doing this, e.g. something an attentive peer-reviewer would like to see being done in a manuscript?

# Answer
> 3 votes
Estimate the constant of the leading term in your complexity, i.e., write your complexity as $c n^3 + o(n^3)$. You can get an idea of $c$ by a careful inspection of your algorithm and you can test it experimentally.

Then decide what "can be solved using today's technology" means. You probably want your program to terminate withing a certain amount of time $T$. Estimate how many operations $N\_T$ your machine can perform within time $T$.

Finally solve $c n^3\le N\_T$, i.e., $n \le \sqrt\[3\]{n/c}$.

Keep in mind that this is just an estimate there are a lot of thing that can go wrong: $c$ depends on a lot of practical factors (the language of your implementation, the target architecture, cache locality, ...), the complexity of the algorithm might not be uniform across different instances of the same size, the complexity of the algorithm might not scale up nicely, the asymptotic notation is... asymptotic while you're dealing with small input sizes, and more. You know the details of your algorithm so you probably have a better idea of how these factors will impact your estimate.

---
Tags: complexity-theory
---


# Question
Title: Polynomial-Time reduction from Partition to MakeSpan
**Partition Problem:**

Input: $A:=$ {$a\_{1}, ..., a\_{n} $}. $a\_{i} \in \mathbb{N}$ $\forall i \in$ $\\{1, \ldots, n\\}$.

Question: Exists a subset $A\_{1} \subset A$ with: $\sum\_{a\_{i} \in A\_{1}} a\_{i} = \sum\_{a\_{i} \in A\setminus A\_{1}} a\_{i}$ ?

Output: Yes or No.

**Makespan Problem:**

Input: Jobs $J$ and $b \in \mathbb{N}$.

Question: Exists a Schedule $S$ with $\text{FinishTime}(S) \leq b$ ?

Output: Yes or No.

---

So I have to change the Makespan Problem in a way that the Partition Problem gives me the correct answers for the Makespan Problem. $Partition \leq\_{p} Makespan$

---

**First Problem:** When the Makespan Problem has $m$ machines and not two, I don't know how I can use Partition for that scenario. I could recursive iterate the jobs (so that I split Makespan in several Partition Problems) but then I had to use the Partition Problem several times and with my understanding, I am only allowed to change the Input for a Polynomial-Time Reduction.

---

But let's say we have $m= 2$ machines. If Partition has the Output "Yes", I know that there exists an optimal solution for the Makespan, so that I have an optimal Schedule with value= $\dfrac{1}{m} \cdot \sum\_{a\_{i} \in A}$. If $b \leq \dfrac{1}{m} \cdot \sum\_{a\_{i} \in A}$, the result for Makespan is also Yes.

---

**Second problem:** But what happens if there is no optimal solution? I only receive "No" from Partition but I don't know how bad the Partition result is.

---

I would be really happy if someone has an idea for this, I don't know how to I could find a solution for this.

# Answer
> 2 votes
Given an instance of partition (i.e., a set of numbers) $\\{a\_1, \dots, a\_n\\}$ create an instance of Job Scheduling (what you call Makespan) with $2$ machines and $n$ jobs $j\_1, \dots, j\_n$, where the execution time of the $i$-th job is $a\_i$. Pick $b = \frac{1}{2} \sum\_{i=1}^n a\_i$.

If there is a solution to the partition problem, i.e., a set $A \subseteq \\{a\_1, \dots, a\_n\\}$ such that $\sum\_{a \in A} a = \frac{1}{2} \sum\_{i=1}^n a\_i$, then there is a solution for the job scheduling problem: simply assign $j\_i$ to machine $1$ if $a\_i \in A$, and to machine 2 otherwise.

If there is a solution to the job scheduling problem, i.e., a partition of jobs into $M\_1$ and $M\_2$ such that $\max\\{ \sum\_{j\_i \in M\_1} a\_i, \sum\_{j\_i \in M\_2} a\_i \\} \le b$ then there is a solution $A$ to the partition problem. The choice of $b$ implies $\sum\_{j\_i \in M\_1} a\_i = b = \frac{1}{2} \sum\_{i=1}^n a\_i$, therefore it suffices to select $A = \\{a\_i \\, : \\; j\_i \in M\_1 \\}$.

---
Tags: reductions, polynomial-time, process-scheduling, partitions, polynomial-time-reductions
---


# Question
Title: Is necessarily the following language not decideable
For A,B that are not decidable, does AB U BA not necessarily decidable?

I think that the answer is NO. Not necessarily. I thought about the following example, but it does not refute exactly:

If we take A and A complement, and without losing generality the empty word is in A, than every word in A' is also in AA' U A'A, but I can't use it to show that every word in A is also in AA' U A'A.

If someone can help me how can I show that also A is in AA' U A'A the problem will be solved.

thank you very much.

# Answer
Take some undecidable language $A$ and choose $B=A'\bigcup \\{\epsilon\\}$. $B$ is also undecidable, and the rest of the proof is just as what you have already done.
> 1 votes

---
Tags: decision-problem
---


# Question
Title: Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product
I have to determine the time complexity of a recursive enumeration in the problem of finding n-tuples $(k\_i, ..., k\_n)$ of naturals greater than 1 with product less or equal to $K$. Problem can be formally expressed as: $$\begin{align}0\<\prod\_{i=1}^nk\_i\leqslant K\in\Bbb N,\ k\_i \in \Bbb N^{+}\setminus\\{1\\}&\ \forall i\in\\{1,\ldots,n\\},\end{align}$$

The number of steps required to enumerate all n-tuples of naturals greater than 1 is: \begin{equation} f(K, n) = \sum\_{k=2}^{\lfloor \frac{K}{2^{n-1}}\rfloor} \bigg(1 + f(\lfloor \frac{K}{k} \rfloor, n - 1)\bigg) \end{equation} \begin{equation} f(K, 0) = 0 \end{equation}

I can provide trivial time complexity analysis. As every $k\_i \leq \frac{K}{2^{n-1}}$ and there $n$ factors which can be in interval $\[2, \frac{K}{2^{n-1}}\]$, we have that the maximum number of steps is $(\frac{K}{2^{n-1}} - 1)^n$. Therefore, complexity in big-O notation should be $O\bigg(\frac{K^n}{2^{n^2-n}}\bigg)$. I do not know if this observation is of any relevance to the time-complexity analysis.

# Answer
I thought about this problem a lot and I think that I devised a suitable solution. I focus here on asymptotic analysis with respect to $K$, and my aim is to provide tighter upper bound than one that I suggested in the question. Therefore, I now observe slightly different problem where $k\_i \geq 1$. In that case the number of steps $T(K,n)$ required to enumerate all n-tuples of naturals greater or equal one 1 with product less than or equal to $K$ is: \begin{equation} T(K, n) = \sum\_{k=1}^{K} T(\lfloor \frac{K}{k} \rfloor, n - 1) \end{equation} \begin{equation} T(K, 0) = 1 \end{equation} where $T(K, 0)$ is the number of elementary operations in the basic case.

For any bound $x$, we know that: \begin{equation} T(x, 1) = \sum\_{k=1}^{x} T(x, 0) = x \end{equation}

Moreover, for $T(x, 2)$ we have: \begin{equation} T(x, 2) = T(\frac{x}{1}, 1) + T(\frac{x}{2}, 1) + T(\frac{x}{3}, 1)... + T(\frac{x}{x}, 1) = \frac{x}{1} + \frac{x}{2} + \frac{x}{3} ... + \frac{x}{x} \end{equation} We can see that this is in fact finite partial sum of harmonic series: \begin{equation} T(x, 2) = x \sum\_{k=1}^{x} \frac{1}{k} = x H\_x \end{equation} where $H\_x = \sum\_{k=1}^{x} \frac{1}{k}$ is the x-th harmonic number.

Now with $T(x, 2) = x H\_x$, $T(x, 3)$ can be expressed as: \begin{equation} T(x, 3) = T(\frac{x}{1}, 2) + T(\frac{x}{2}, 2) + ... + T(\frac{x}{x}, 2) = x H\_x + \frac{x}{2} H\_{x/2} + ... + \frac{x}{x} H\_1 \end{equation} Now we can bound $T(x, 3)$: \begin{equation} T(x, 3) = x H\_x + \frac{x}{2} H\_{x/2} + ... + \frac{x}{x} H\_1 \leq x H\_x (1 + \frac{1}{2} + ... + \frac{1}{x}) = x H\_x^2 \end{equation}

By induction, we get that $T(K, n) = K H\_K^{n-1}$. Harmonic number can be approximated with integral: \begin{equation} H\_K = \int\_{1}^{K} \frac{1}{t} dt = \ln K \end{equation}

Therefore, an upper bound on complexity is given with $O(K \log^{n-1} (K))$.
> 0 votes

---
Tags: complexity-theory, time-complexity, enumeration
---


# Question
Title: Does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?
I cannot see whether the implication in my question title holds. To me, it sounds reasonable to assume that, but I cannot find any source stating that this is true, false, or unknown at the moment.

So, **does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$**?

# Answer
> 4 votes
No, *this implication is not known to be true*, however it is believed that those are all separate classes. (Unfortunately, I don't have any references to back up my claim now, but I still post this as an answer to point out the following.)

You are asking whether $\text{P} \neq \text{NP}$ implies that *the polynomial hierarchy $(\text{PH})$ does not collapse to its first level*.

The class $\text{NP}^\text{NP}$ is also known as $\Sigma\_2^P$ which is one of the classes on the *second level* of the polynomial hierarchy.

---
Tags: complexity-theory
---


title: Path uniqueness in undirected graph

text:
# Question
Title: Path uniqueness in undirected graph
Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count.

I am looking for an algorithm that decides whether there exists some path between start and finish and if it is unique. The output of the algorithm is one of the three possible answers:

* There is no path between start and finish.
* There is exactly one path between start and finish.
* There are two or more paths between start and finish. The two paths need not be disjoint. They just must not be identical.

Currently, I have the following algorithm implemented: I run breadth-first search from start vertex to find the shortest path from start to finish. If the finish vertex is unreachable, I am done. If I find a path, I iterate over its vertices except start and finish. I remove the vertex and run BFS from start vertex again. If the finish vertex can be reached, I am done as I have found another path from start to finish. If the finish vertex is unreachable, I undo the vertex removal and continue with another vertex. If the finish vertex is always unreachable during this loop, the initial path is unique.

I wonder if there is some more efficient algorithm than running BFS for each vertex of the initial path.

**EDIT**: As mentioned in the comment, I am interested only in simple paths, i.e. paths without repeating vertices.

# Answer
> 3 votes
I am assuming that you are interested in simple paths only. Otherwise the answer is trivial.

You can solve your problem in time $O(n)$. Let $s$ be your start vertex and $t$ be your target vertex. Consider the graph as weighted where every edge has weight $0$.

Find any path $P$ from $s$ to $t$ in $G$. This takes time $O(n)$. If $P$ does not exist then there is no path from $s$ to $t$. Otherwise set the weight of each edge in $P$ to $1$ and find a shortest path $P'$ in the modified graph. This takes time $O(n)$ using a straightforward modification of Dijkstra's algorithm.

If $P' = P$ then there is a single path from $s$ to $t$ in $G$. Otherwise there are at least two distinct paths from $s$ to $t$ in $G$.

---
Tags: algorithms, graph-traversal
---


# Question
Title: Finding the shortest path in a grid which has walls
The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a magic wand which you can use $k$ times to destroy a wall. How do we find the shortest path from the top left corner to the bottom right?

# Answer
Let $w$ be the width of the grid and $h$ be its height. Let $n = w \cdot h$. The following solution requires $O(n k)$ time and works regardless of whether there are restrictions on the direction of movement. If the movement is allowed only downwards and rightwards then there is a solution with a running time of $O(n)$, which is better whenever $k$ is not a constant (see Nir Shahar's answer).

Assume that there is no wall on the upper-left cell (otherwise remove it, and decrease $k$ by $1$).

Construct a directed graph $G$ as follows: the vertex set $V=\\{1,\dots,h\\} \times \\{1, \dots, w\\}$ consists of $n$ nodes. A generic node $(i,j) \in V$ represent the cell in the $i$-th row and $j$-th column of the grid.

There is an edge between vertex $u$ to vertex $v$ iff it is possible to move (in one step) from cell $u$ to cell $v$ without breaking a wall on $v$. If all directions of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is no wall on $v$.

Create a directed graph $H$ consisting of $k+1$ copies $G\_0, G\_1, \dots, G\_k$ of $G$. Intuitively the $i$-th copy represents the situation in which exactly $i$ walls have been broken.

Augment $H$ as follows: for each $i=0, \dots, k-1$ add an edge from vertex $u$ of the $i$-th copy to vertex $v$ of the $(i+1)$-th copy iff it is possible to move (in one step) from cell $u$ to cell $v$ but this requires breaking a wall on $v$. Again, if all direction of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is a wall on $v$.

Finally, add a new vertex $t$ and all the edges from vertices $(\ell, \ell)$ in all of the $k+1$ copies of $G$ to $t$. Notice that the number of vertices is $O(nk)$ and that the number of edges is linear in the number of vertices.

It now suffices to find a shortest path $P = \langle v\_0, v\_1, \dots, v\_h \rangle$ from vertex $(0,0)$ in $G\_0$ to $t$. This can be done in time $O(nk)$ using, e.g., a breadth first search from $(0, 0)$ in $G\_0$. The sought shortest path on the grid has length $h$ and is obtained by traversing the cells corresponding to vertices $v\_0$ to $v\_{h-1}$.
> 3 votes

# Answer
***Note: This solution assumes you cannot move left or up.***

---

Have you heard about dynamic programming? With a little bit of work, Im pretty sure it can help you find a solution for the question!

An actual solution (using dynamic programming. Please, try to do it yourself first):

let $m$ be the board width (or height). Then $n=m^2$.

Build an empty matrix $M$ of size $m\times m$.

Now, run the following algorithm:

1. For $i$ from $m$ to 1:
    2. For $j$ from $m$ to 1:
        3. Set $M\[i,j\] = min\\{M\[i+1,j\],M\[i,j+1\]\\} + C$ where $C=k$ if there is a wall and $C=1$ otherwise. (also $M\[m+1,j\]=0=M\[i,m+1\]$)

This matrix will contain the costs of the shortest paths between the node $(i,j)$ to the bottom right. To find the actual path, just traverse the lowest valued path between $(0,0)$ and $(m,m)$ in the matrix.

This will cost $O(m^2)=O(n)$
> 1 votes

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


# Question
Title: Clarification in the proof for the Bellamn-Ford algorithm
While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma:

> After k (k \>= 0) iterations of relaxations, for any node **u** that has at least one path from **s** (the start node) to **u** with at most **k** edges, the distance of from **s** to **u** is the smallest length of a path from **s** to **u** that contains at most **k** edges.

We prove this lemma using mathematical induction as follows:

1. Base case: After 0 iteration, all distance values are **infinity**, but for **s** the distance is **0**, which is correct!
2. We assume the lemma is true for **k** iterations and now we have to prove it for **k+1** iterations!
3. Before **k + 1**th iteration, dist\[u\] (which is the distance of **u**, from **s**) is the smallest length of a path from **s** to **u** containing at most **k** edges. Each path from **s** to **u** goes through one of the incoming edges **(v, u)**. Relaxing by **(v, u)** is comparing it with the smallest length of a path from **s** to **u** through **v** containing at most **k + 1** edges -- this proves it!

Now, I have doubt in the 3rd point. Let us say that in the **k+1**-th iteration the node **u** has got a new distance after some edge relaxations, now according to the above lemma, this distance must be the shortest of the distances of all the paths with at most **k+1** edges from **s** to **u**. Now, consider another node **w**, that has an edge to it, from **u**. Now, the length of the path form **s** to **w** via **v** will have at most **k+2** edges, but if this edge is relaxed to reduce the dist\[w\], then in **k+1**-th iteration itself, we will have included a path (to **w**) that has almost **k+2** edges right? Is it not a contradiction? Can it not happen?

To be more precise I am unable to reason the fact that, the lemma holds true throughout the **k+1**-th iteration -- I am not convinced with the 3rd step of the proof.

If someone can explain to me the 3rd step or whole proof more clearly, it would be really helpful! If someone can share a proof that does not use mathematical induction will also be really helpful!

# Answer
The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion.

> The correct claim is the following: Consider the values of $\text{dist}\[\cdot\]$ computed at the end of the $k$-th iteration of Bellman-Ford. For any vertex $u$, let $d^{(k)}\_u$ be the length of the shortest path from $s$ to $u$ that uses at most $k$ edges (if no such path exists then $d^{(k)}\_u = +\infty$). It holds that $\text{dist}\[u\]\le d^{(k)}\_u$.

**Notice the $\le$ sign!**

The above claim implies that, after the $(n-1)$-th iteration all distances stored in $\text{dist}\[\cdot\]$ are **smaller than or equal to** the true distances in the graph.

Clearly, it also holds that all the distances stored in $\text{dist}\[\cdot\]$ are **larger than or equal to** the true distances in the graph (since every time you a distance is updated, the new distance is always the length of some path from $s$).

Combining the previous two properties, you can conclude that $\text{dist}\[\cdot\]$ stores the exact distances from $s$, i.e., that the Bellman-Ford algorithm is correct.

---

Let me prove my claim formally. To avoid confusion this is the pseudocode of the Bellman-Ford algorithm I will be using:

```
Bellman-Ford(G=(V,E; w), s):
  For u in V:
    dist[u]=+infinity

  dist[s]=0
  For k=1,..., n-1:
    For (v,u) in E:
      dist[u] = min(dist[u], dist[v] + w(v,u))

```

The proof is by induction on $k=0, \dots, n-1$ (where the end of the $0$-th iteration corresponds to the state of the algorithm just before the first iteration of the outer for loop).

The base case is $k=0$. There is only one vertex $u$ such that the path from $s$ to $u$ uses $k=0$ edges, namely $u=s$. The claim holds for $s$ since $\text{dist}\[s\] = 0 = d\_s^{u}$. For $u \neq s$, the claim holds since $\text{dist}\[u\] = +\infty = d\_u^{(k)}$.

Suppose now that the claim holds for $k-1 \ge 0$. We will prove that it also holds for $k$. Consider any vertex $u \in V$, let $P$ be the shortest path from $s$ to $u$ that uses at most $k$ edges, let $w(P)$ be the (weighted) length of $P$, and let $|P|$ denote the number of edges of $P$. We distinguish two cases:

If $|P| \< k$ then $d\_u^{(k)} = d\_u^{(k-1)}$ and, by inductive hypothesis, at the end of the $(k-1)$-th iteration of the outer for loop we had $\text{dist}\[u\] \le d\_u^{(k-1)} = d\_u^{(k)}$. The claim follows since the values of $\text{dist}\[\cdot\]$ never increase during the execution of the algorithm.

If $|P|=k$ then $|P| \ge 1$. Let $(v,u)$ be the last edge of $P$ and let $P'$ be the subpath of $P$ from $s$ to $v$. Let $\delta$ be the value of $\text{dist}\[v\]$ at the end of the $(k-1)$-th iteration of the outer for loop. By the suboptimality of shortest paths we know that the (weighted) length $w(P')$ of $P'$ is exactly $d\_v^{(k-1)}$. Moreover, the inductive hypothesis ensures that $\delta \le d\_v^{(k-1)}$. Consider the situation at end of the iteration of the inner for loop that considers edge $(v,u)$, during the $k$-th iteration of the outer for loop. Since values of $\text{dist}\[\cdot\]$ never increase, we must have: $$ \begin{align\*} \text{dist}\[u\] &\le \text{dist}\[v\] + w(v,u) \\ &\le \delta + w(v,u) \\ &\le d\_v^{(k-1)} + w(w,v) \\ &= w(P') + w(v,u) = w(P) = d\_u^{k}. \end{align\*} $$ Once again, since the values of $\text{dist}\[\cdot\]$ never increase, the above inequality must also hold true at the end of the $k$-th iteration of the outer for loop.
> 2 votes

---
Tags: graphs, algorithm-analysis, shortest-path, correctness-proof, weighted-graphs
---


title: Shortest path in BST

text:
# Question
Title: Shortest path in BST
Given a Binary Search Tree and two elements $e1$ and $e2$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked representation with dynamic allocation without an attribute for parent or height). Implement the required operation and specify its complexity. Hint: try to find first the Least Common Ancestor of the nodes, the first node which is an ancestor for both nodes.

I thought that for finding the Least Common Ancestor we have to make a preorder traversal for example having the while loop : $while(!(e\_1\<a == e\_2 \< a))$, but I don't know how to count the length between them. How should I count them?

# Answer
> 1 votes
There is a unique shortest path $P\_T(u,v)$ between two nodes $u$ and $v$ in a tree $T$. Such a shortest path goes from $u$ to the lowest common ancestor (LCA) $z$ of $u$ and $v$ in $T$, and then goes from $z$ to $v$. Notice that it might be possible for $z$ to coincide with $u$ or $v$.

To find the length $d\_T(u,v)$ of $P\_T(u,v)$ is therefore sufficient to find the LCA $z$ of $u$ and $v$ in $T$.

There are several ways to do this. One straightforward way that requires time $O(n)$, where $n$ is the number of nodes of $T$, is the following:

* Initially all the vertices of $T$ are unmarked.
* Start from $u$ and iteratively walk towards the root of $T$. Mark all the encountered vertices.
* Start from $v$ and iteratively walk towards the root of $T$. The LCA of $u$ and $v$ is the first marked vertex encountered during this walk.

An easy way to reduce the running time to $O(d\_T(u,v))$ is that of alternating the steps of the walk from $u$ with those of the walk from $v$. Assume that $u \neq v$ (otherwise the answer is trivial) and do the following:

* Initially all the vertices of $T$ are unmarked except for $u$ and $v$.
* Let $p\_u = u$, and $p\_v = v$.
* Repeat the following:
    + If $p\_u$ is not the root of $T$:
        - Move $p\_u$ to its parent in $T$.
        - If $p\_u$ is marked, return $p\_u$ as the LCA of $u$ and $v$. Otherwise mark $p\_u$.
    + If $p\_v$ is not the root of $T$:
        - Move $p\_v$ to its parent in $T$.
        - If $p\_v$ is marked, return $p\_v$ as the LCA of $u$ and $v$. Otherwise mark $p\_v$.

Once the LCA $z$ of $u$ and $v$ is known, it takes time $O(d\_T(u,v))$ to find the distances from $z$ to $u$ and from $z$ to $v$ in $T$. Therefore $d\_T(u,v)$ can be found in time $O(d\_T(u,v)) = O(n)$.

If you have to frequently report the distance between pairs of vertices in a static tree then you can do so in constant time per query after a linear time preprocessing:

* Build a LCA oracle: a data structure that can report the LCA between two vertces in $T$ in contant time. This data structure can be constructed in time $O(n)$. The construction is very clever and elegant. See this paper for the details.
* Augment each node $v$ in the tree by storing its depth depth($v$) in $T$.
* Answer a query for the distance between $u$ and $v$ in $T$ by: 1) finding the LCA of $z$ of $u$ and $v$ using the oracle; 2) returning $(\text{depth}(u) - \text{depth}(z)) + (\text{depth}(u) - \text{depth}(z))$.

---
Tags: algorithms, trees
---


title: Inexact cover, or cover with gaps

text:
# Question
Title: Inexact cover, or cover with gaps
*Dancing Links*: wikipedia article, research paper is an implementation of algorithm X for exact cover problem.

In the Knuth's research papaer, linked above it is shown how Polymino problem (that is covering a given shape with given sets of Polymino) is translated to exact cover problem, so that dancing links can be used to solve it.

Exact Cover problem goes like this:

> Given a matrix of 0s and 1s, find a subset of rows with exactly one 1 in each column.

For example the matrix

is solved by choosing rows 1, 4 and 5.

Knuth explains in the paper, how the Polymino problem can be translated into exact cover problem on example of the famous case of Polymino problem where we are trying to cover chess board (8x8) with 12 pentominoes. The 12 pentominoes occupy 60 squares in total, so 4 spaces on the 64 squares chessboard are left unaccounted.

Here is Knuth's explanation, of how the problems are translated into each other:

> Imagine a matrix that has 72 columns, one for each of the 12 pentominoes and one for each of the 60 cells of the chessboard-minus-its-center. Construct all possible rows representing a way to place a pentomino on the board; each row contains a 1 in the column identifying the piece, and five 1s in the columns identifying its positions. (There are exactly 1568 such rows.)

If this is not very clear please refer to the original paper for further details.

This makes sense. Latter in the paper Knuth uses a 2x2 tetromino to account for the 4 squares mentioned earlier. This also makes sense.

Now imagine that you have a different shape of the board. This is easy. You still translate each square into a matrix column as explained above.

What I'm having problems though is when I need to find solution for "inexact" cover, or cover with gaps.

In the chessboard problem above, imagine, that you do not want to settle for nicely defined 2x2 tetromino in the centre, like Knuth does. Instead you want to find all solutions no matter where the four "missing" squares go onto the board.

My initial idea was model this with 4 separate "monomino" one square each. Unfortunately this does not work so well. There are over 6 millions combinations of how 4 squares can be selected from 64 square keyboard.

If we assume that for a particular solution the monominoes occupy square A, B, C and D, then there are 4! of indentical solutions that the algorithm need to wade through, where monomino 1 goes to square A, monomino 2 goes to square B, etc **or** monomino 1, goes to square B , monomino 2 goes to square A, etc and all other possible combinations of fitting these 4 pieces into these 4 squares.

If we have a problem when we have more than 4 gaps, this becomes even worse. We are getting more and more identical solutions where only placement of monomino order is different, and the squares they occupy are the same.

This makes the algorithm orders of magnitudes slower, since in needs to enumerate all these identical solutions.

I cannot figure out how to efficiently model the problem of covering a shape with polymino pieces when there are many gaps as explained above.

Are there better ways to model it?

# Answer
I'd propose this idea:

Let the algorithm run almost naturally, but if it encounters a shortest column that has no options left, do not backtrack immediately. Instead, ignore that column and pick another one. Do this up to four times per iteration. Once more than 4 columns have no options, do backtrack as you normally would.

This will eventually run until a solution is found, in which 4 cells will be left unassigned.

By allowing 4 option-less columns, you place no required knowledge on which columns (cells) should be left unoccupied. The matrix is kept small and tidy as before.

Performance: The search tree probably does not grow too vast, as most of the "stupid" piece placements will trigger the limit within 1 or 2 iterations. Accordingly, the tree should only be about one order of magnitude larger than usual.
> 1 votes

---
Tags: algorithms, optimization, combinatorics
---


title: Amortized time for dynamic array

text:
# Question
Title: Amortized time for dynamic array
I'm struggling to understand one part from the book "Cracking the coding interview". The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full and we have to reallocate.

Inserting $X$ elements take $O(2X)$ (because $\frac{X}{1} + \frac{X}{2} + \frac{x}{4} + \ldots + 1 \approx 2 X$)

I perfectly understand until this point but I don't understand second sentence:

> "Therefore, $X$ insertions take $O(2X)$ time. **The amortized time for each insertion is $O(1)$**."

How did she came to this conclusion?

# Answer
You should read more precisely the definition of amortized analysis. As we have $X$ operations here, the time complexity of these operations should be divided by the number of operations to find the amortized complexity of the algorithm. Hence, $\frac{O(2X)}{X}$ is the amortized complexity of the insertion algorithm which is $O(1)$.
> 2 votes

# Answer
From this post on Mathematics stackexchange :

> $\Theta(g)$ is set of functions $\left\lbrace f: \exists c\_f,C\_f\>0, \ \exists N,\ n\>N, c\_fg \leqslant f \leqslant C\_f g\right\rbrace$. We consider only non negative functions.
>
> There are some properties outgoing from definition: $$f \cdot \Theta(g)=\Theta(g \cdot f)$$ $$\Theta(f) + \Theta(g)=\Theta(g + f)$$ And for $g\>0$ holds $\frac{\Theta(f)}{g} = \Theta \left(\frac{f}{g}\right)$

It's straightforward to demonstrate those three properties. Please let me know if you want me to add them to this answer.

Thus we can assume $\frac {O(2X)}{X} = O(\frac {2X}{X}) = O(2) = O(1)$ with $O$ \<=\> $\Theta$ in the context of computer science:

> "In industry (and therefore in interviews), people seem to have merge $Θ$ and $$ together. Industry's meaning of big $O$ is closer to what academics mean by $\Theta$, in that would be seen as incorrect to describe printing an array as $O(n^2)$. Industry would just say this is $O(n)$. "
> \- Cracking the Coding Interview
> 0 votes

---
Tags: algorithm-analysis, arrays, amortized-analysis
---


# Question
Title: Definiton of a certain symbol in a proof(The right linear languages are exactly the finite state languages)
**I want to stress that i am not looking for a proof of this question, but rather if someone(that is familiar with the proof and it's context) can explain to me what the symbol 'e' means in the context.**

the letter 'e' first appears in line 6:S $\rightarrow $e...

This is crucial for me, because i am not able to deduct from the context what its meaning and write a formal proof

# Answer
The letter $e$ stands the empty word, which is usually denoted by the symbol $\varepsilon$. A hint of this is that, according to step 6, if $S \to e$ then the initial state $S$ is also a final state.
> 2 votes

---
Tags: finite-automata, formal-grammars
---


# Question
Title: Given an array $A$ and an index $c$, prove there always exists a subarray whose sum $\pmod {i} = 0$
> Given an array $A$ of positive integers with size $m$ and an array index $c$ (indexing starts at $1$). Prove using mathematical induction over $m$ that there always exists a contiguous subarray $S$ in $A$ such that the (sum of the elements of $S$) $\pmod {i} = 0.$

I'm unable to find the correct approach to solve this. I'm sure the Pigeonhole Principle will be useful here, but I don't know how to correctly apply it within the proof. Can someone point me in the right direction?

# Answer
> 2 votes
Let's try to do it, no induction involved.

Suppose you augment your initial list $A = \[a\_1, a\_2, ..., a\_m\]$ with a new element at the beginning $a\_0 = 0$, $A' = \[a\_0, a\_1, ..., a\_m\]$.

Now build partial sums of $A'$, such that $P\_i = \sum\_0^i a\_j$. Notice that the sums of elements in the initial list from positions $b$ to position $e$ is $\sum\_b^e a\_i = P\_e - P\_{b - 1}$. Notice $P\_0 = 0$ is defined since we added $a\_0$. This is a very common trick when you care about the sums of intervals.

Back to the problem, you need to proof there exist two index $i \< j$ such that $c | (P\_j - P\_i)$. This is equivalent to say that there exist two index $i \< j$ such that $P\_i \equiv P\_j \mod c$. We only care about remainder of each element in $P$ if they are divided by $c$, and moreover we should only show that at least two elements have the same remainder.

Now notice the number of different remainders given $c$ is at most $c$ and the length of the list $P$ is $|P| = m + 1$. Since $c \le m \< |P|$ by the Pigeonhole principle you can guarantee at least two elements in $P$ have the same remainder.

# Answer
> 1 votes
Let `P(m)` denote the statement we are trying to prove: Given a positive-integer array `A` of size `m` and a `c` in `[m]` there is a (contiguous) subarray whose sum modulo `c` is 0.

Let us say that such subarrays `satisfy` P(m).

P(1) is trivial since c = 1.

Assume P(m). Let's try to prove for P(m+1).

If `c <= m`, then ignore the last element of the array and notice that any subarray that satisfies P(m) also satisfies P(m+1).

Assume `c == m+1`.

Consider the `m+1` sums: `S1 = A[1]%(m+1), S2 = (A[1] + A[2])%(m+1),.... S_(m+1) = (A[1] + A[2] + ... + A[m+1])%(m+1)`

If one of the `S_i == 0`, then, sub-array `A[1..i]` satisfies P(m+1).

If none of the `S_i` are 0, each `S_i` can only take on one of the `m` values in the range `{1,2,...,m}`. By Pigeonhole Principle, there must be indices `i < j` such that `S_i == S_j` and `A[i+1 ... j]` satisfies P(m+1).

---
Tags: proof-assistants
---


# Question
Title: QuickSelect with Median of Medians runtime
I know that Median of medians itself is $O(n)$. With a good pivot, QuickSelect is $O(n)$, too -- but with a bad one, it's $O(n^2)$. But if I now were to use the element gotten through median of medians as the pivot for QuickSelect, what would the new worst-case runtime of QuickSelect be? Would it be $O(n)$ guaranteed too?

Why would it not be $O(n\log n)$? I'm a bit confused, I guess. Since we have to choose the median of medians, which takes $O(n)$, for each subproblem, and we have $\log n$ subproblems (always recursing on one side of the median).

# Answer
> 2 votes
The medians of medians algorithm will return a pivot with a rank between $\frac{3}{10}n$ and $\frac{7}{10}n$ in time $O(n)$.

You can then describe the worst-case computational complexity of Quickselect on an instance of $n$ elements with the following recurrence relation: $$ T(n) = T\left(\frac{7}{10}n\right) + O(n), $$ where $O(n)$ accounts both for the work needed to run the median-of-medians algorithm an for the partitioning of the input.

Unrolling the recursion shows that (you can prove this formally by induction): $$ T(n) \le c n \sum\_{i=0}^{+\infty} \left( \frac{7}{10} \right)^i = cn \cdot \frac{1}{1-\frac{7}{10}} = \frac{10cn}{3} = O(n),$$

where $c\>0$ is a suitable constant (hidden in the $O(n)$ notation of the recurrence relation).

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


# Question
Title: Why is channel capacity of AWGN infinite?
My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2) $. There is no constraint on input signal. I don't understand how the professor can directly say the channel capacity is infinite. Don't we need to maximize mutual information between input and output to get the channel capacity? How to do that for continuous variables?

# Answer
> 2 votes
Here is a coding scheme that demonstrates the main idea:

**Encoding:** Let the power constraint $P$ be fixed and suppose we want to transmit one information bit a time. We set our coding scheme as $X(0) = \sqrt{P}, X(1) = -\sqrt{P}$, where $X$ is the encoding function.

**Decoding:** Let $Y$ denote the received signal and $Z$ the additive Gaussian noise like you defined. We set the decoder as $\hat{X} = \mathbb{1}\_{\\{Y \> 0\\}}(Y)$, where $\mathbb{1}\_A(w)$ is the indicator function that yields $1$ if $w \in A$ and $0$ otherwise.

**Probability of error:** Let $P\_e$ denote the probability of error. We assume the information bits are equally likely, since otherwise we could simply use optimal source coding to ensure they are. Then,

\begin{align} P\_e &= \frac{1}{2}P(Y\>0 | X = -\sqrt{P}) + \frac{1}{2}P(Y \leq 0 | X = \sqrt{P}) \\ &= \frac{1}{2}P(Z \> \sqrt{P} | X = -\sqrt{P}) + \frac{1}{2}P( Z \leq -\sqrt{P} | X = \sqrt{P}) \\ &= P(Z \> \sqrt{P}) = 1 - \Phi\left(\sqrt{\frac{P}{\sigma^2}}\right), \end{align}

where $\Phi(t) = \int\_{-\infty}^t \frac{1}{\sqrt{2\pi}}e^{-\frac{-t^2}{2}}$ is the Gaussian cdf. The key observation here is that, as a cdf, this is a non-decreasing function that converges to $1$ in the limit. By increasing $P$, we can make it arbitrarily close to $1$. In other words, let $\epsilon \> 0$, for large enough $P$, $P\_e \< \epsilon$. Without a power constraint, we can send one bit of information with arbitrarily small probability of error. This coding scheme proves a rate of $1$ is achievable.

Ok, so how do we get from an achievable rate of $1$ to $\infty$? Let's see what happens when we increase our rate from $1$ to $2$, by encoding two information bits at a time. Let $$X(b\_1, b\_2)=\begin{cases} \sqrt{P}, &\text{ if } (b\_1,b\_2) &= (0,0) \\ \frac{\sqrt{P}}{2}, &\text{ if } (b\_1,b\_2) &= (0,1) \\ -\sqrt{P}, &\text{ if } (b\_1,b\_2) &= (1,0) \\ -\frac{\sqrt{P}}{2}, &\text{ if } (b\_1,b\_2) &= (1,1) \end{cases}$$

Now, if you follow the same procedure as above, you'll find out that $P\_e = P\left(Z \> \frac{\sqrt{P}}{2} \right) = 1 - \Phi\left(\sqrt{\frac{P}{4\sigma^2}} \right)$. Therefore, we can again find a (larger) $P$ that allows us to squeeze $2$ information bits into $1$ coded bit with an arbitrarily small probability error. As you can imagine, if $P$ is unbounded, we can simply keep doing this to encode more and more information bits to in a single coded bit without sacrificing from $P\_e$.

**Moral of the story:** Without a bound on transmission power, we can pick a set of coded bits (codewords of length 1) that achieve arbitrarily small $P\_e$ and we can do this for an arbitrarily large set of code bits to squeeze as many information bits into 1 as we want. So, the achievable rates is unbounded and since the capacity is the smallest upper bound on the set of achievable rates, it is $\infty$.

---
Tags: information-theory, coding-theory, encoding-scheme, gaussian-noise
---