# Question
Title: Are intersection and union redundant? Possibility to get smaller output without negation?
I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me.

1. ∩ and ∪ (intersection and union) are in fact redundant in relational algebra and you can rewrite any expression without them.
2. You can't get a smaller result without using negation. So expressions without it are always monotone

There were no explanation for those, so I'm not sure if those are true. Could you give some examples?

# Answer
> 0 votes
Regarding the first question, as you have said in the comments, you can define a relational algebra intersection with other relational algebra operators. Anyway, relational-algebra union is usually considered a relational algebra basic operator (that cannot be defined with other relational algebra operators).

Regarding monotonicity, we say that a query is monotone if the results of the query increases with the size of the database. More formally, a query $q$ is monotone if and only if, for any given database states $D\_1$, $D\_2$, where $D\_1 \subseteq D\_2$, we have $q(D\_1) \subseteq q(D\_2)$.

For instance, a monotone query might be: "All departments with at least one employee". Indeed, if you have a database state $D\_1$ with 1 department with at least one employee (e.g. 'MarketingDepartment'), you know, for sure, that any $D\_2 \supseteq D\_1$ will still bring you such 'MarketingDepartment', and possibly more (since $D\_2$ might have more departments with at least one employee).

A non-monotone query might be: "All departments with NO employee". Indeed, if you have a database state $D\_1$ with 1 department with no employee (e.g. 'MarketingDepartment'), you can build a database $D\_2 \supset D\_1$ where 'MarketingDepartment' $\not\in q(D\_2)$. Indeed, in $D\_2$ you can add some employee for the 'MarketingDepartment', making 'MarketingDepartment' not satisfy your condition.

In relational-algebra, non-monotonic queries are defined through the set-difference operator (in the previous case: Department $\setminus$ $\pi\_{dept}$ Employee). If a relational-algebra query has no set-difference operator involved, it is mononote.

---
Tags: database-theory, relational-algebra
---


# Question
Title: Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts
From Nielsen & Chuang (page 138):

> Suppose an $n$ element list is sorted by applying some sequence of compare-and-swap operations to the list. There are $n!$ possible initial orderings of the list. Show that after $k$ of the compare-and-swap operations have been applied, at most $2^k$ of the possible initial orderings will have been sorted into the correct order. Conclude that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings into the correct order.

The `compare-and-swap(j,k)` operation is defined as:

> compares the list entries numbered $j$ and $k$, and swaps them if they are out of order

Using an inductive argument, I understand that $k$ applications of the compare-and-swap operation sorts at most $2^k$ of the possible initial orderings into the correct order. However, I have trouble drawing the final conclusion from this, specifically that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings.

$n \log n$ steps will sort at most $2^{n \log n}=\left(2^{\log n} \right)^n=n^n \gt n!$ of the possible orderings. So $n \log n$ steps might be enough to sort all possible orderings but I don't see why we need at least this many steps (which is what I think $\Omega(\cdot)$ means)? To me there seems to be a gap between $n^n$ and $n!$ and it's not obvious why there can't be an algorithm which solves the task by covering more than (or exactly) $n!$ but less than $n^n$ orderings?

# Answer
$\Omega(\cdot)$ means “at least that many steps” \_up to a multiplicative constant. There's a gap between $n!$ and $n^n$, and that gap is more than a multiplicative constant. But we aren't looking for an asymptotic bound on the number of length of the list that can be sorted in $k$ steps, but on the minimum number of steps $S(n)$ that it takes to sort a list of length $n$ in the worst case.

You've seen that after $k$ steps, it's only possible to distinguish between $2^k$ different orderings of the list. You've also seen that the total number of orderings of the list is $n!$. The number of steps must be sufficient to distinguish between all orderings, therefore $2^{S(n)} \ge n!$. This condition can equivalently be stated $S(n) \ge \lg(n!)$ where $\lg$ is the logarithm in base $2$.

You want to prove $S(n) \in \Omega(n \lg n)$. (Or maybe $\Omega(n \log n)$ for some different logarithm base, but logarithm bases are equivalent up to a multiplicative constant.) You know that $S(n) \ge \lg(n!)$. Therefore it is sufficient to prove that there is a multiplicative constant $C$ such that for large enough $n$, $\lg(n!) \ge C n \lg n$. Note that this is equivalent to $n! \ge 2^{C n \lg n}$, i.e. $n! \ge n^{C n}$, and the family of functions $n \mapsto n^{C n}$ is not the same as the family of functions $n \mapsto C n^n$.

Stirling's formula, obtained via calculus, can give you a precise approximation of $n!$ from which you can prove the desired asymptotic equality. But here we only need a weak version of it that can be proved more easily. For $n \ge 4$:

$$ \begin{align} \lg(n!) &= \lg(1) + \lg(2) + \ldots + \lg(n) \\ &\ge \lg \lceil n/2 \rceil + \ldots + \lg(n) && \text{(only sum the larger half of the terms)} \\ &\ge (n/2 - 1) \lg(n/2) && \text{(all terms are larger than the smaller term; count them and round down)} \\ &\ge \left(\frac{1}{2} - \frac{1}{n}\right) \dfrac{\lg(n) - 1}{\lg(n)} \\; n \lg(n) && \text{(algebra)} \\ &\ge \frac{1}{8} n \lg(n) && \text{(approximate the complicated factor by a constant)} \\ \end{align} $$

For large enough $n$, $\lg(n!)$ is larger than $n \lg(n)$ multiplied by the constant $1/8$. This fits the definition of $\lg(n!) \in \Omega(n \lg(n))$.
> 2 votes

# Answer
Stirling's approximation shows that $$ \log (n!) = \Theta(n\log n). $$
> 1 votes

---
Tags: complexity-theory, sorting
---


# Question
Title: Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$
I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.

$T(n)= 5T(n/4) + n^2$

Guess: $T(n) = O(n^2)$

Prove: $T(n) \leq cn^2 $

Breakdown

$ T(n) \leq 5(c(n/4)^2) + n^2 $

$ = (5/16)cn^2 + n^2 $

$ \leq cn^2 $

For the last step to hold I'm not sure what the value of c should be because of the (5/16). My guess would be c \>= 1 and I'm not sure if that would hold.

# Answer
> 0 votes
Your constant $c$ needs to satisfy $$ \frac{5}{16} c n^2 + n^2 \leq c n^2, $$ that is, $$ \frac{5}{16} c + 1 \leq c. $$ Hopefully you can determine the set of constants $c$ for which this inequality is satisfied.

# Answer
> 0 votes
$$T(n)= 5T\left(\frac{n}{4}\right) + n^2 = 5^2T\left(\frac{n}{4^2}\right)+\left(\frac{5}{16}+1\right)n^2=\\\=5^3T\left(\frac{n}{4^3}\right)+\left(\left(\frac{5}{16}\right)^2+\frac{5}{16}+1\right)n^2=\cdots=\\ =5^kT\left(\frac{n}{4^k}\right)+\left(\left(\frac{5}{16}\right)^{k-1}+\cdots +\frac{5}{16}+1\right)n^2$$ If you have some initial condition for $T(1)$ and we assume $n=4^k \Leftrightarrow k=\log\_{4}n$, then we obtain $$T(n)=5^kT(1)+n^2\frac{16}{11}\left(1- \left(\frac{5}{16}\right)^{k-1}\right) \in O(n^2)$$

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


# Question
Title: Closed form of recurrence with two inputs
This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:

"When a candle finishes burning it leaves a leftover. `m` leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.

You have `c` candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?"

So the inputs are the number of starting candles and how many burned candles can be reused recursively to make new candles.

Now, I solved this with a while loop, and the loop itself just involves division and modulo math:

```
def candles(c, m):

    burned=c
    while c>=m:
        burned+=c//m
        c=(c%m)+c//m
    return burned

```

But many of the other solutions go straight to closed form (which is obviously better in terms of complexity). I tried to figure out how they were reaching this by writing out a recurrence relation, but I can't do it... Here's an example of an accepted solution:

`return c + (c - 1) // (m - 1)`

I was hoping someone could help me figure out what techniques are used to arrive at this solution.

# Answer
> 0 votes
In order to prove the closed form you have to think in a different way about the consuming $m$ candles and adding a new one. Notice that if you break down the $(n-1)//(m-1)$ part into an iterative approach you basically subtract $m$ raise your counter of possible candles by $1$ and add $1$ back to the number you subtracted from, hence you don't subtract $m$ but actually $m-1$ (it is like taking $m$ candles and adding $1$ directly back). Now why do we use $n-1$ then? Well in order to do the above trick with subtracting $m-1$ instead of $m$ we still need to ensure that there are $m$ candles left e.g. if $m = 3$ and $n=6$ you would end up with
$6 - 3 = 3 (\text{1 candle possible});\\ 3+1 = 4;\\ 4-3 = 1 (\text{2 candles possible});\\ 1+1 = 2 (\text{finished})$.
Now if we merge the subtract 3 and add 1 operation we could just do $6 - 2 = 4 (\text{1 candle possible});\\ 4-2 = 2 (\text{2 candles possible});\\ 2 - 2= 0 (\text{3 candles possible})$
Notice that we get the wrong result cause in the last step we subtract $m-1$ instead of checking that the result is $\geq m$. To ensure that this doesn't happen we use $n-1$. You could write the closed form as iterative program and slowly transform it:

```
def candles(n,m):
  burned = n
  while n >= m:
    n -= m
    burned += 1
    n += 1
  return burned

def candles(n,m):
  burned = n
  while n >= m:
    n -= (m-1)
    burned += 1
  return burned

def candles(n,m):
  burned = n + (n-1)//(m-1)
  return burned

```

# Answer
> 1 votes
The candle burning rules are as follows: if you have `c>=m` candles, you can remove `(m-1)` of them and score `m` points while doing so. If you have fewer than `c<m` candles, then you score `c` points and are then done.

The total number of points you can score are then the points you score at the end (`c % (m-1)`), and the number of points you score before then (`m * (c // (m-1))`).

---
Tags: proof-techniques, recursion, python
---


# Question
Title: How to solve T(n)=2T(√n)+log n with the master theorem?
I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?

# Answer
Let us actually use the master theorem.

Define $S(n) = T(e^n)$ for all $n$. Then $$S(n) = T(e^n) = 2T(\sqrt{e^n}) + \log(e^n) = 2T(e^{n/2}) + n = 2S(n/2) + n$$ Now we can apply the second case of the master theorem to $S(n)$ for $a = b = 2$ and $f(n) = n$ to obtain $$ S(n) = \Theta(n\log n)$$ So for $n\gt0$, $$ T(n) = S(\log n) = \Theta(\log n \log\log n)$$
> 10 votes

# Answer
As discussed in the other answer, the Master Theorem does not apply here.

To solve this recurrence, we can follow the similar steps in Solving recurrence relation with square root.

For $n=2^m$, we have $$T(2^m)=2T(2^{m/2})+m.$$

Define $S(m)=T(2^m)$. Hence, we have:

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

Developping the recurrence (or you can apply the Master Theorem for $S(m)$), we obtain

$$\begin{align}S(m)&=2S(m/2)+m\\\&=2(2S(m/4)+m/2)+m\\\&=4S(m/4)+2m\\\&=8S(m/8)+3m\\\&\\;\\,\vdots\\\&=2^{i}S(m/2^i)+im\end{align}$$

For $i=\log m$, we have:

$$\begin{align}S(m)&=mS(1)+m\log m\\\&=mT(2)+m\log m\end{align},$$ or equivalently,

$$\begin{align}T(n)&=T(2)\log n+\log n \log\log n\end{align}$$

I think we can say that $$T(n)=O(\log n\log\log n).$$
> 4 votes

# Answer
The master theorem only applies to recurrences of the form $$T(n)=a\\,T(n/b) + f(n)\\,.$$ It says nothing about your recurrence. Our reference question on solving recurrences gives details of alternative techniques.
> 2 votes

# Answer
The Master Theorem states for $a \geq 1$, $b \> 1$ and a function $f(b)$, let the recurrence relation be defined as follows \begin{equation} T(n) = aT(\frac{n}{b}) + f(n) \end{equation} We can distinguish three cases:\\ 1- If $f(n) = O(n^{\log\_b(a-\epsilon)})$, for some constant $\epsilon \> 0$, then $T(n) = \Theta(n^{\log\_b a})$.\ 2-If $f(n) = \Theta(n^{\log\_b a})$, then $T(n) = \Theta(n^{\log\_b a} \log n)$.\ 3- If $f(n) = \Omega(n^{\log\_b(a+\epsilon)})$, for some constant $\epsilon \> 0$ and if $af(n/b) \leq cf(n)$, fpr some $c \< 1$ and all sufficiently large $n$ then $T(n) = \Theta(f(n))$.\

You have $$T(n)=2T(\sqrt{n})+\log n$$ Do a change of variable $$n = e^m$$ So $$T(e^{2m}) = 2T(e^{m/2}) + m$$ Let $$G(m) = T(e^m)$$ Then $$G(2m) = 2G(m)+ m$$ or $$G(m) = 2G(\frac{m}{2})+ \frac{m}{2}$$ where $a = b = 2$ and $f(m) = \frac{m}{2}$. Since $f(m) = O(m) = O(m^{\log\_2(2)})$, then we are at the second case, hence \begin{equation} G(m) = T(e^m) = \Theta(m^{\log\_2(2)} \log m) = \Theta(m\log m) \end{equation} Now replace $m = \ln n$ since $n = e^m$, so \begin{equation} G(\ln n) = T(e^{\ln n}) = \Theta(\ln n\log \ln n) \end{equation} Hence \begin{equation} T(n) =\Theta(\ln n\log \ln n) \end{equation}
> 0 votes

# Answer
The above question could be solved using iterative method also.

\begin{align} T(n)=2T(n^{1/2})+\log(n)\label{eq1}\tag{1} \end{align} is given.

\begin{align} T(n^{1/2})=2T(n^{1/4})+\log(n^{1/2}).\label{eq2}\tag{2} \end{align}

By substituting $T(n^{1/2})$ in \eqref{eq1} we get

\begin{align} &T(n)=2(2T(n^{1/4})+\log(n^{1/2}))+\log(n),\\ &T(n)= 2\times2T(n^{1/4})+2\log(n^{1/2}) + \log(n). \end{align}

Here it is clear that $2\log(n^{1/2})=2\times1/2\times\log(n)=\log n$. Hence $T(n)$ becomes

\begin{align} 4T(n^{1/4})+\log(n)+ \log(n)= 2^2\times T(n^{1/4})+2\log(n)\label{eq3}\tag{3} \end{align}

Also by substituting $T(n^{1/4})$ in \eqref{eq3} we get

$$T(n)=2^3\times T(n^{1/8})+3\log(n).$$

Now on generalizing \eqref{eq3} we get

\begin{align} T(n)=2^k\times T(n^{1/2^k})+k\log(n).\label{eq4}\tag{4} \end{align}

Now assuming base condition as $T(1)=2$.

For base condition we need to substitute $(n^{1/2^k} = 2)$.

Applying $\log\_2$ on both sides,

\begin{align} &(1/2^k)\times\log\_2n = \log\_2(2),\\ &\log\_2n=2^k, \label{eq5}\tag{5}\\ &k=\log\_2(\log\_2n).\label{eq6}\tag{6}\\ \end{align}

Now substituting \eqref{eq5}, \eqref{eq6} in \eqref{eq4} we get,

$$T(n)=\log\_2n\times T(1)+\log\_2(\log\_2n)\log n$$

where $T(1)=2$ by assumption.

Now we can say that $T(n)=O(\log n\log\_2(\log\_2n))$.
> 0 votes

---
Tags: recurrence-relation, master-theorem
---


title: Reducing a problem to the MST problem

text:
# Question
Title: Reducing a problem to the MST problem
Let $G = (V, E)$ be a connected, undirected graph. Given a subset of distinct vertices $S = \\{v\_1, v\_2, \ldots, v\_n\\} \subseteq V$, how can I find a forest in which each vertex $v \in V - S$ is connected to exactly one of the vertices of $S$ and is of minimum total length?

This is a problem from an algorithms book that I'm currently struggling with. I'm pretty sure the idea is to construct a graph $G'$ on which a minimum spanning tree algorithm could be used (but I might be wrong). I've thought about it for a while, and I'm not able to make much progress. Could someone please point me in the right direction?

I thought about only keeping edges of the form $(u, v)$ where $u$ is in $S$ and $v$ isn't and running an MST algorithm, but I'm not entirely sure if this is correct.

Thanks

# Answer
Hint: Add a new vertex to your graph..

Further hint:

> ...with an edge connecting to each element of $S$.
> 1 votes

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


title: Cancellation in C++

text:
# Question
Title: Cancellation in C++
I am trying to figure out what the problem with the following expression in C++ is:

```
y=std::log(std::cosh(x));

```

My first intention was that there might occure a Cancellation due to the `cosh(x)` part, because it is definde as $\frac{e^x+e^{-x}}{2}$ and the computation of $e^x$ with `double x` results in Cancellation.

Am I on the right track? Or is there something different that causes Cancellation?

# Answer
> 2 votes
Let me summarize what I wrote in the comments. It is not a complete answer, since the intervals on which to apply each formula still need to be investigated.

It is enough to assume $x\geq0$, since $\cosh(x)$ is even.

The type of cancellation that occurs when evaluating, in finite precision floating point (FP2), the expression

$$\log(\cosh(x))$$

are:

1. When $x$ is large, in which case $\cosh(x)$ makes it even larger but $\log$ would bring the value back down. FP2 is more sparse for larger values. So, one should prevent $\cosh(x)$ making the value large.
2. When $x$ is small the $\cosh(x)$ is close to $1$. This is cool on its own. FP2 is densest near $1$, but then $\log$ becomes close to $0$. In this case it is better to approximate the function $\log(1+x)$ and the function $\cosh(x)-1$ and compose those.

So, for $x$ large one can approximate $\cosh(x)$ by $\frac{e^x}{2}$. Composing with $\log(x)$ one gets $x-\log(2)$.

For $x$ small we can write $\cosh(x)=1+\frac{(e^x-1)^2}{2e^x}$ and compute $\log(\cosh(x))$ by composing $\log(1+x)$ and $\frac{(e^x-1)^2}{2e^x}$. The latter would be computed by approximating $e^x-1$ directly and not by evaluating $e^x$ and subtracting $1$. A C++ implementation could compute $\log(1+x)$ using `std::log1p(x)` and $e^x-1$ using `std::expm1(x)`.

Finally, one needs to investigate what would be good value $x\_1,x\_2$ such that one would use

1. the last computation on the interval $\[0,x\_1\]$,
2. the computation `std::log(std::cosh(x))` on $(x\_1,x\_2\]$
3. and `x-std::log(2)` on the $\[x\_2,\infty\]$.

---
Tags: numerical-algorithms, numerical-analysis, c++
---


# Question
Title: Understand the DFA: accepting or not accepting "aa" or "bb"
I want to discuss the strings accepted by couple of DFAs:

DFA in Figure 1 has 3 final states. It looks like that it accepts both the substrings "aa" (q0q3q0q1) or "bb". So this is not I want.

DFA in Figure 2 has one final state q0. Its good because it does not accept "aa" or "bb" but the problem is that it does not accept any string so its useless.

DFA in figure 3 accept a, aba. It looks like that it can accept any number of "ab" but does it accept "aa" or "aaa"? Can the start state generate any number of 'a's to be accepted by the final state? I am not sure somebody please guide me.

Somebody please guide me.

Zulfi.

# Answer
It is not clear if you actually want to construct an automaton for some language, however I can provide some help with understanding the given ones.

The first automaton is a bit complicated. The language it recognizes should be, in regular expression form, $$((ab)^\ast (ba)^\ast)^\ast (a + b + \varepsilon)$$ where $\varepsilon$ denotes the empty word. The second one, as you noted, has no edges returning to the only final state which also happens to be the initial state. Hence the language it recognizes is $\\{\varepsilon\\}$, but it surely is a complicated automaton for doing this.

The third automaton recognizes the language $a(ba)^\ast$. It does not accept any words containing substrings $aa$ or such as starting from any state, taking 2 consecutive $a$-transitions will land you in that bottom sink state from which the accepting state cannot be reached.

The fourth automaton is actually not a DFA but a NFA (but that makes no big difference). It recognizes the language $a(baa^\ast)^\ast$, which is different from the expression you gave as yours is missing the possibility for taking the loop from the accepting state through the initial state via $b$ and back to the accepting state via $a$. In particular, this loop shows that if the automaton accepts $w$, then it also accepts $w(ba)^\ast$.

In general, analyzing the language recognized by some DFA boils down to finding the paths from the initial state to a final state and then accounting for loops along the way, which sometimes can be a bit confusing, but try to do this for the third and fourth automata yourself. I am sure that you will be able to understand them that way in no time :)
> 1 votes

---
Tags: finite-automata
---


# Question
Title: What is the advantage of Rete algorithm compared to relational database engines?
Per my understanding, the Rete algorithm and relational database engines essentially solve the same problem: answering to a certain query about a (large) set of relational facts. To me, the Rete algorithm is just more special-purpose along with a fancy caching procedure; I fail to see why it is superior to any of the existing state-of-the-art database solutions such as SQL. In terms of flexibility, SQL is certainly superior. In terms of performance, it is not apparent that Rete yields better average performance.

# Answer
As you say, relational databases are designed for, essentially, answering queries. Rete, I would rather say, is designed for the specific task of materialized view maintenance (i.e., keeping updated the results of a query, once new changes to the data are applied). Of course, you can answer queries by building a materialized view of them, and this is why SQL query answering and Rete relates to each other.

With regards to efficiency, Rete has been critiziced for wasting too much time mantaining its internal data-structures. This motivated the apparison of other algorithms such as Treat.

In any case, it is worth to hightlight that Rete only deals with relational algebra queries, whereas SQL includes non relational-algebra expressions (e.g.: aggregation functions).
> 1 votes

---
Tags: database-theory, pattern-recognition, knowledge-representation, expert-systems
---


# Question
Title: Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?
This relates to an answer for this question.

The opinion said that:

> Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most part):

> asked by a person who has one specific solution in mind and is unable to recognise an alternative answer or even a better answer (Note: I actually faced this one time - the clown kept telling me I was wrong. For a metaphor of this, see  below);

> Imagine a coding question to solve traveling salesman in non-polynomial time (a stupid question because it’s not realistic but I’m going for a metaphor here). Imagine, instead, you solved a different NP-complete problem in non-polynomial time and the interviewer wouldn’t accept that solving any one NP-complete problem in non-polynomial time solves them all. If the interviewer lacks the ability to grasp a great answer, then the candidate offering the great answer is filtered out.

I've read in Geeksforgeeks that:

> The interesting part is, if any one of the NP complete problems can be solved in polynomial time, then all of them can be solved.

From what I understand, the interviewer gave a TSP problem, to be solved in brute-force approach. The interviewee solved a different problem of the same NP-completeness level in non-polynomial time (maybe using brute-force approach) too. And, literally what I quote from the Geeksforgeeks above.

My questions:

* Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?
* Are the solutions (in non-polynomial time) for NP-complete problems universal (one solution can be used for all)?
* Why would the interviewee solve another problem instead of the given problem? Or am I misunderstanding something? Is it to show that the approach is universal?

Thank you in advance for your insights.

# Answer
> 1 votes
If you solve a Problem that is NP-complete the solution to this problem can not be applied instantly to any other Problem that is NP-complete. However, the problem that you solved might be used to find a solution for other problems in NP.

For example:

* If you can solve the TSP Problem your an adaption of your solution could also solve the problem of finding a hamiltonian circle in a graph
* If you can solve the hamiltonian circle problem an adaption of your solution could also solve the long path problem
* ...

So your solution can not be directly used to solve other problems. But if you found a solution for a problem that is NP-complete this implies that there are solutions in P for every problem that was believed to be NP-complete. This is because NP-completeness is defined as follows:

> A problem P is NP-complete if it is NP-hard and the problem lies in NP
>
> Beeing NP-hard means that every other problem P' that is NP-complete can be reduced to the problem P (meaning exactly that if you could find a solution for P you could also find oune for P')

The answer to your second question is simply "No".

The only reason for a cancidate to solve another problem that is NP-complete is that he could not find a solution for the given problem but for the other problem. And in addition he knows how to modify the problem he is abel to solve in such a way that he finds a solution for the given problem.

---
Tags: np-complete
---


# Question
Title: Why does the time hierarchy theorem use a rather intricate diagonal argument?
Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$? Where am I wrong?

# Answer
> 6 votes
The output size does not scale with (time) complexity of problems in general. In fact, complexity theorists are largely interested in decision problems for which the output will either be 0 or 1.

---
Tags: algorithms, complexity-theory, algorithm-analysis
---


# Question
Title: Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?
Is this true for all $n$ and some $c\>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows:

$f(n) = c\cdot g(n)$ for all $n$ and some $c\>0$ is the definition of Big-Oh.

So, $O(g(n))$ is substitutable for $c\cdot g(n)$:

$f(n) = O(g(n)) + O(g(n))$

And by the max rule of sum:

$f(n) = O(g(n))$

# Answer
> 2 votes
Firstly let me say, that in definition of big-O, for non negative case, there is inequality(not equality, typo I think): $$O(g)=\\{f: \exists C\>0, \exists N \in \mathbb{N}, \forall n\> N, f(n)\leqslant C g(n)\\}$$

Now $f(n) = c\cdot g(n) + O(g(n))$ means, that $\exists \phi (n) \in O(g(n))$ such that $f(n) = c\cdot g(n) + \phi (n)$. From here we have $$f(n) = c\cdot g(n) + \phi (n) \leqslant c\cdot g(n) + C\cdot g (n)=(c+C)g (n)$$ so $f \in O(g)$ and your claim is correct.

The general rule can be worded as follows:

If $f \in O(g)$, then $f+O(g)=O(g)$

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


# Question
Title: Proving the L' = {w|deleting one symbol from a string in L} is regular when L is regular
I have looked up a question like this online and found this solution. I couldn't understand what the new NFA A' looks like.

Could anyone give me an example of NFA A'?

# Answer
Maybe the formal proof below will help you to understand the construction using a NFA.

Let $\mathcal{A} = (Q, A, \cdot, i, F)$ be a deterministic automaton recognising your language. For each pair of states $(p, q)$, let $L\_{p,q}$ be the language recognised by the automaton $(Q, A, \cdot, p, \\{q\\})$. Thus $L\_{p,q}$ is the set of labels of all paths from $p$ to $q$. By construction, each language $L\_{p,q}$ is regular. Let $T$ be the set of transitions of $\mathcal{A}$, that is, $T = \\{ (p,a,q) \in Q \times A \times Q \mid p \cdot a = q \\}.$ Let $$ R = \bigcup\_{(p,a,q) \in T} \bigcup\_{f \in F} L\_{i,p}L\_{q,f} $$

> **Claim**. $D(L) = R$.

Indeed, let $w \in D(L)$. By definition, there exist some words $u$ and $v$ and a letter $a$ such that $w = uv$ and $uav \in L$. Let $p = i\cdot u$, $q = p \cdot a$ and $f = q \cdot v$. By construction, $u \in L\_{i,p}$, $v \in L\_{q,f}$, $(p,a,q) \in T$ and $f \in F$. Thus $w \in R$.

Let now $w \in R$. Then there exist some states $p, q \in Q$ and $f \in F$ and some transition $(p,a,q) \in T$, such that $w \in L\_{i,p}L\_{q,f}$. It follows that $w = uv$ for some $u \in L\_{i,p}$, and $v \in L\_{q,f}$. Now $i \xrightarrow{u} p \xrightarrow{a} q \xrightarrow{v} f \in F$, which means that $uav \in L$. Consequently, $w \in D(L)$, which proves the claim.

Coming back to your question, the first copy of $\cal A$ in ${\cal A}'$ is used to accept $L\_{i,p}$ and the second one to accept $L\_{q,f}$. The $\epsilon$-transitions are used to pass from the first copy to the second one.
> 3 votes

---
Tags: automata
---


title: Is this an example of parallelization?

text:
# Question
Title: Is this an example of parallelization?
Not sure if this is the right exchange for this question. But you could definitely answer it. Note professor said this was “wrong” on their quiz.

Question: Identify a daily activity that can be speed up with parallelization.

My answer: People driving their own car vs people taking a bus. My reasoning: When people all take a bus they have to wait for all the destinations before theirs to pass. When people drive a car they go directly to their destination.

The professor said this isn’t a good example of a serial processor made parallel. I’m not convinced. Where am I wrong? I plan to argue my case..

# Answer
If I want to go from A to B, that doesn’t get faster by taking a bus. But if I want to take 50 people from A to B that actually will be done much faster.

A simple example: How do you make six boiled eggs? And how do you make 120 boiled eggs if you have an oven with four flames, that will involve some pipelining as well.
> 2 votes

# Answer
So I suppose in ur example the bus and the cars are the processors and the people going to work are the tasks the processors have to compute. I suppose the problem with your example is that the bus itself is already a parallel processors in the sense that it is capable of doing the same computation step for multiple tasks at the same time (e.g. it can load or unload multiple people at the same stop).

So your example is simply modifying an existing parallel processor into another parallel processor and is therefore not what your professors was expecting.
> 1 votes

---
Tags: parallel-computing
---


# Question
Title: Simple question about signed integer multiplication
If you have a signed integer `int x = any`

And then state that `x < 0`

Is the following statement true or false?

```
((x*2) < 0)

```

The answer is false, which seems counter intuitive. Is it because X can be any negative value, it can also be a very big negative value which will overflow if multiplied by two.

So if I have the number -30768 `1000011111010000` which multiplied by 2 is -61536 `11111111111111110000111110100000`

But because we only have 16 bits the last 16 are taken resulting in `0000111110100000` which is positive.

Is this the correct explanation? I can't seem to find a good source

# Answer
Your answer is nearly right.

So `x` is an unsigned negative value of k bits. The smalles possible value of `x` is representet by the 2's Complement number `1000....0`. If you multiply this number by 2 (or logical shifting it by 1, which is equivalent) you end up with the number `0000...0` which is 0. And therefore `(x*2)<0` is false.
> 1 votes

# Answer
This depends on the rules of your programming language, which you need to check.

For any fixed size integral type that has more than the single value zero, there are integers that can be represented in the type, for which the mathematical value 2\*x cannot be represented. So something has to give.

In C and C++, a signed integer overflow is undefined behaviour, so anything can happen. In Swift, a signed integer overflow causes a guaranteed crash. Swift also has the operator &\* which doesn't crash, and which produces the mathematical product, plus or minus some suitable multiple of 2^n if n bits are used (there is also &+ and &- with similar behaviour). Other languages may have other rules. For example, primitive operations can be saturating: If the mathematical result is too large / too small, the largest / smallest possible value is returned instead. For such a language, x \< 0 would imply 2\*x \< 0.
> 1 votes

---
Tags: arithmetic, binary, bit-manipulation
---


# Question
Title: Interpreting a proof of $2^\mathbb{N}$ being uncountable
Suppose I have the following proof:

```
open import Agda.Builtin.Equality
open import Data.Nat.Base

data ⊥ : Set where

data  : Set where
  I :
  O :

inv :  →
inv I = O
inv O = I

invNeq : ∀ d → d ≡ inv d → ⊥
invNeq I ()
invNeq O ()

data Idx : Set where
  at : ℕ → Idx

ℝ : Set
ℝ = Idx →

_≈_ : {a b : Set} → (f₁ f₂ : a → b) → Set
_≈_ f₁ f₂ = ∀ x → f₁ x ≡ f₂ x

diagEx : (f : ℕ → ℝ) → ℝ
diagEx f (at n) = inv (f n (at n))

doesn'tBelong : (f : ℕ → ℝ) → (n : ℕ) → (f n ≈ diagEx f) → ⊥
doesn'tBelong f n funEq = invNeq (f n (at n)) (funEq (at n))

```

We encode real numbers as functions from natural numbers to binary digits, then (in `diagEx`), given some mapping `f` from natural numbers to reals (or, rather, some subset of those), we build a function that doesn't belong to said mapping, and then prove (in `doesn'tBelong`) that, for any mapping `f`, there exists a function (built by `diagEx f`) that isn't equal to any real number enumerated by the `f`. This, of course, includes `f`'s claiming to be surjective, so that's largely the diagonal argument for proving uncountability of reals. Yay!

Or at least that's the intent of the proof. But what have we really proven? Could it be that we've only proven that there doesn't exist a *terminating* numbering of reals? Or a *computable* one?

My concern is that we're working in some language, and said language only allows terminating functions (modulo some irrelevant details, but even with them it's about computable functions). On the other hand, we don't rely on the computational behaviour of `f` at all, so, in theory, this `f` could be `postulate`d (or, stretching it a little, it could even go ahead and consult some external oracle about each next digit without making the system inconsistent, I guess).

So what's the power of this proof? What's the right tool to reason about this kind of questions? It feels related to model theory, but I have very passing familiarity with that subject.

# Answer
> 3 votes
There is no assumption in your proof that the functions involved are computable, so it would be quite stingy to interpret the proof that way merely because Agda allows you to compute with its terms.

Rather, yes how it should be interpreted depends on the model, and constructive (in the sense of just removing axioms) proofs like the one you've given enable an even wider range of models. So it applies to classical functions, because we can (I believe) interpret all the operations you used as operations on classical functions. It's just that when those operations are used to combine classical functions, they don't produce computable functions, even though the operations are in a sense computable.

When you *do* interpret the proof in a computable setting, what you get is actually a stronger result. The classical reading is, "the reals (or, Cantor space really for your example) are uncountable." The computable reading is, "the computable reals are computably uncountable." The latter means that we can actually compute a real that is left out of any alleged computable enumeration.

A good write up of this is here, although it applies equally well to types that aren't inductive, even though the title doesn't emphasize it. The first part of the author's thesis also gives a pretty good description of modest sets, which are a way of thinking about the 'computable operations on non-computable data' angle.

So, don't make the mistake of thinking that Agda and the like are only for reasoning about their own terms. It's an easy mistake to make coming from a computer programming background, but I think it's a mistake even there.

The reason why is your oracle example. One could imagine a model where there is an extra $^ℕ$ sequence added as a sort of brute fact (also all sequences computable from it, of course). When you ask about its bits, the computer accesses some sort of physical sensor and determines the answer based on that (and memoizes it). This bit sequence is not 'computable' in the sense of being described by some term, but as long as you haven't added axioms that depend on bit sequences being describable by terms, your proofs should hold for it. So this sort of 'open world' assumption seems to match aspects of actual computers.

# Answer
> 3 votes
Agda has an interpretation in classical set theory, as well as in realizability models.

Any proof carried out in Agda is valid in any of these models. It can therefore be interpreted in classical set theory to give a proof of uncountability of $2^\mathbb{N}$, but it can also be interpreted in the effective topos to give a proof of *computable* uncountability of computable total maps.

Just because a theory does not allow you to exhibit a non-computable map, that does not imply that it can only speak about computable maps. To give an analogy: the definition of a group only mentions the unit element specifically, but this does not mean that every group is trivial.

P.S. Please do not call $2^\mathbb{N}$ "reals" because this is not the case anywhere, except in set theory (and even there I would argue this is an abuse of terminology).

---
Tags: type-theory, formal-methods, agda
---


# Question
Title: how can i prove the following algorithm?
```
Exp(n)
  if n == 1
    return 2

  If n == 0
    Return 1
  End If

  If n%2==0
    temp = Exp(n/2)
    Return temp × temp
  Else //n is odd
    temp = Exp((n−1)/2)
    Return temp × temp × 2
  End if

```

how can i prove by strong induction in n that for all n ≥ 1, the number of multiplications made by Exp (n) is ≤ 2 log2(n).

ps: Exp(n) = 2^n or Power(2, n)

# Answer
> 1 votes
To compute $\exp(1)$ it does $0$ multiplications, since it enters the `if` and returns `2`.

Assume that, for all $k\<n$, to compute $\exp(k)$ it does no more than $2\log\_2(k)$ multiplications.

To compute $\exp(n)$ we have two cases. Either $n$ is even and the number of multiplication is $1$ more than the number done for $\exp(n/2)$, or $n$ is odd and the number of multiplications is $2$ more than the number of multiplications done for $\exp((n-1)/2)$.

In the first case we have that the number of multiplications is no more than $2\log\_2(n/2)+1=2\log\_2(n)-2+1\leq 2\log\_2(n)$. In the second case the number of multiplications is no more than $2\log\_2((n-1)/2)+2=2\log\_2(n-1)\leq 2\log\_2(n)$.

Therefore, the number of multiplications to compute $\exp(n)$ is no more than $2\log\_2(n)$.

By induction, this holds for all positive integers $n$.

---
Tags: algorithms, algorithm-analysis, logic, discrete-mathematics, induction
---


# Question
Title: Is recomnder systems part of computer science?
I want to work on a paper with one of my friends in Recommender systems. My field is programming, and I favourite part is to be more technical.

I want to know that, is field of Recommender systems a part of Computer science or field in Information technology?

# Answer
> 1 votes
The algorithmic part of the recommendation systems is more closely related to the computer science, the theoretical part of recommendation systems is mostly combination of statistics and linear algebra, thus we can think of recommendation systems as the combination of statistics and computer science, and the data science is the field that one would actually call the combination of statistics and computer science.

Thus my take on to answer the question is that the data science is the field you are looking for.

---
Tags: recommendation-systems
---


# Question
Title: can virtual address map any on virtual memory on disk?
I was reading a textbook which says that:

> If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit is not set, then a null address indicates that the virtual page has not yet been allocated. Otherwise, the address points to the start of the virtual page on disk.

My question is, does each page tabe entry(PTE) need to be match the same offset one in disk? for example, `PTE 1` has `VP 1` in physical memory, but can `PTE 1` originally mapped to `VP 3`? or `PTE 1` has to map `VP 1`, `PTE 2` has to map `VP 2`, `PTE 3` has to map `VP 3` and so on?

if `PTE x` has to map `VP x`, then why when valid bit is not set then the address points to the start of the virtual page on disk? can't we use the offset `x` in `PTE x` to infer that it maps to `VP x`?

# Answer
> 1 votes
> My question is, does each page tabe entry(PTE) need to be match the same offset one in disk?

No. They can map to anywhere in physical memory and they can map to anywhere on the disk. If they had to map to the same offset, there would be no point using virtual memory.

---
Tags: memory-management, virtual-memory
---


# Question
Title: How would I answer this? I recently started doing computer studies at school
is this format okay? this is my first time using stackexchange.

# Answer
You could just start at address `00`. The instruction that is stored there can be interpretet as load address `04`. Intrepreting the instruction at `01` you add the value stored at address `05` so the result is `9`. According to the instruction at address `02` this result gets sotred at address `06`.

So the program is basically adding the values sotred at addresses `04` and `05` and stores the result at address `06`.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Playing video games to solve SAT instances
This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to construct a Super Mario level and let experienced gamers play it. In the worst case, it might take them exponentially long; but, in some cases, there may be heuristics that experienced gamers may be able to notice, and this may lead them to quick solutions.

The main problem with this scheme is that it is one-sided: if a satisfying assignment exists, then the gamers may find it; but if no such assignment exists, then they will not find any proof for it.

So my question is: is there a way to construct a video game for solving SAT instances, such that if the instance has a solution - a gamer will eventually find it (after possibly exponentially long time), and if the instance has no solution - a gamer will eventually find an evidence for it? Can such a game be useful for solving hard SAT instances?

# Answer
Given a SAT instance *A*, another SAT instance *B* can be constructed such that if it is found satisfiable the satisfying assignment proves the unsatisfiability of *A*. But the proof is one-sided; if *B* is found to be unsatisfiable that in itself does not prove that *A* is satisfiable.

This is accomplished by crafting *B*'s clauses such that its variable assignments specify the inference steps of some proof system known to be sound and complete for propositional logic and whose starting state is *A*. Using the resolution rule as an example proof system, if there are a series of steps that starts with *A* and ends with the empty clause then *B* is satisfiable and the steps prove that *A* is unsatisfiable.

The one-sidedness of the proof comes from the fact that the length of the proof is limited by the number of inference steps that can be encoded in the variables and clauses of *B*, which is limited by the number of variables and clauses in *B*. If *B* has too few variables and clauses to write a valid proof of *A*'s unsatisfiability then *B*'s unsatisfiability says nothing about *A*'s satisfiability, it only says that any proof of *A*'s unsatisfiability is longer than what can be encoded in any satisfying assignment of *B*.

For the best chance at proving *A*'s unsatisfiability with a feasibly-sized *B*, *B* should encode a proof system strong enough to encode short proofs of *A* type problems. As an example, using the resolution rule alone would be a poor choice for pigeonhole type problems since it is known that such problems require exponentially-sized resolution proofs. Using the resolution rule along with Tseitin's extension rule is adequate to write polynomially-sized unsatisfiability proofs of such problems.

So to use video games to solve your problem you could take your target SAT problem *A* and construct another SAT instance *B* as described above, then reduce both to Super Mario Bros. games. If game experts win the game reduced from *A*, then *A* is satisfiable. If experts win the game reduced from *B*, then *A* is unsatisfiable. The bad news is that since we don't know if **NP = coNP**, *B*'s size might need to be exponentially larger than *A* to guarantee you will get a definitive answer of unsatisfiability.
> 1 votes

# Answer
No. The gamer will basically have to work out the SAT problem in their head.

Think of *any* video game puzzle you've solved that wasn't easy. You probably solved it by working out a simpler version of the problem and then solving that. If you "complexify" SAT into a video game level, the best way to solve the video game level will be to simplify it back into SAT, then solve SAT.

**Example:** Perhaps your game lets you create a level where you must collect all the coins from all the rooms but you can only enter each room once. (This is a Hamiltonian Path problem, which SAT can be transformed to). When you collect all the coins, the exit door opens. You then go to the exit door and finish the level. How would you solve it?

Well, you would start by exploring the level and drawing a map. Then you might simplify the map by drawing the rooms as circles and the connections as lines. Then you have to figure out a way to get from the start to the exit while going through every room... i.e. you have to solve the Hamiltonian path yourself. But how do you solve the Hamiltonian path? Well, you might reason that if you go this way, then you can't go that way, and if you go that way, you can't go this way, .... and write down a list of rules about where you can go. Then, you have to logically deduce a path that matches all the rules. Which is SAT. You're back to where you started except with a lot of useless extra work.
> 3 votes

---
Tags: reductions, satisfiability, computer-games
---


# Question
Title: How does a computer play a video while doing something else?
How is video playback done on a computer? It's obviously not relying purely on the CPU, since video playback continues when a user performs another activity, such as typing into a YouTube comment field. This task seems further complicated in the case of streaming video, where data presumably needs to be transferred from the network interface to the video/graphics controller.

EDIT: I should have made clear that I understand that the CPU switches among multiple processes and threads all of the time. My question was meant to be more specifically about video playback. Is the video processing done on the graphics chipset/card? Do those typically offer buffering? Or can it all be handled by a single-core CPU with time to spare for other tasks, or am I wrong to think that low-end CPUs can play back video without (not-network) delays?

# Answer
> 3 votes
A modern graphics card works more or less (somewhat) the same as a regular cpu.

On a graphics card, you will have (sometimes) multiple processors, each processor will have (sometimes) multiple multiprocessors, which each have multiple cores.

When a video is loaded into a graphics card it gets transcoded into the output buffer by a certain allocation of multiprocessor cores. This output buffer is generally globally accessible memory, which means that any core from any multiprocessor from at least one processor (but often all) has direct r/w access to it.

Usually one multiprocessor is limited to one instruction set, which means that a graphics card can only concurrently operate as many different "flavours" of threads as there are multiprocessors on the card. A "flavour" might for instance be a physics simulation, a video render, an OS render, or a cryptographic function. Naturally one multiprocessor can schedule multiple thread types to run intermittently, but this is usually not necessary.

Decoding a video is often a lot of work, considering how it's usually compressed and sometimes encrypted, so the displaybuffer isn't always busy. Thus it's relatively easy to render a mouse cursor traveling over a video frame. However, sometimes this doesn't quite work, and you will see how in some applications your cursor disappears. This is not necessarily because the application is "on top" of the os, but simply because it's hogging part of the output buffer.

# Answer
> 3 votes
This is implemented using several different techniques. Within the application (for example, the web browser), the program can execute different *threads* of execution. One thread can perform the video streaming/playback, while a different thread can handle the user typing into the comment field.

These threads, along with many other threads and processes, are in turn *scheduled* by the operating system (even if you only have the web browser open, the operating system has many background tasks running, such as the windowing manager, the print spooler, the USB device manager, etc). It is the job of the OS scheduler to determine which thread can actively run, on which processor core, and for how long. In a typical system, a thread can run for up to some threshold value, suppose 100 milliseconds, before the scheduler allows another task to run.

This task switching is fundamental to all modern operating systems (Windows, Linux, UNIX, etc), and is usually a significant portion of an undergraduate operating systems course.

# Answer
> 2 votes
Video playback isn't that special. Sure, GPU-accelerated decoding is common these days, which frees up the CPU for other work, but it wasn't always so. Smooth video playback with only a single CPU is definitely possible, as long as there's enough CPU available for the resolution and complexity of the compression algorithm, and doing it along with other tasks is just as possible, as long as there's enough CPU for both, and the OS schedules well. 30fps video is common, which allows 33ms to decode each frame. Even fairly old chips can manage that for SD-quality MPEG-2, and modern chips can manage it for HD MPEG-4; the laptop I'm typing this on requires about 20% of the CPU to playback 720p High Profile AVC.

As for buffering, there's a limited amount available. The minimum for anything that doesn't want to have screen tearing is "double buffering", where there are two frames in memory: the video card displays one while the software updates the other, and the roles of the two are swapped during the vertical refresh. With "triple buffering", there are two offscreen frames, the next and next + 1, which reduces the amount of jitter. On modern cards with large amounts of RAM it's possible to go beyond that to larger numbers of frames, with the only downsides being user-visible latency in seeking, starting playback, etc. and the fact that other apps might want that video RAM for themselves.

# Answer
> 0 votes
Let's say a computer has just one core. You ask "how can it play video while *at the same time* allowing me to type." Answer: It doesn't. Your video may play at a rate of 30 frames per second, that is 33.3 milliseconds per frame. Maybe your computer takes only 20 milliseconds to draw that frame, then it has plenty of time to handle you typing in text. It's just so fast that you don't notice that it doesn't happen at the same time.

---
Tags: computer-architecture, video
---


title: Little endian architecture,

text:
# Question
Title: Little endian architecture,
Address 0000 stores 0xde

0001 stores 0xad

0002 stores 0xbe

0003 stores 0xef

Treat the data stored as 2 16 bit integers, what are the two values stored?

I thought the answer would be 0xadde and 0xefbe but I was wrong. Why?

# Answer
> 1 votes
Let's program it and see what happens:

```
#include <stdio.h>

int main(int argc, char *argv[]) {
  unsigned char mem[4] = { 0xde, 0xad, 0xbe, 0xef };

  printf("%02hhx %02hhx %02hhx %02hhx\n", mem[0], mem[1], mem[2], mem[3]);
  printf("%04hx %04hx\n", *(unsigned short *)(mem), *(unsigned short *)(mem + 2));
}

```

Here is the output:

```
de ad be ef
adde efbe

```

---
Tags: computer-architecture
---


title: Maximization problem

text:
# Question
Title: Maximization problem
I work at a company and i got to a seminar we're they told us to solve this problem below in the picture

Is there an algorithm that can help me solve this question. I thought about a randomized algorithm after that i get stuck?

# Answer
The case $k \ge n$ is trivial as you can give different value to every variable, which satisfy all inequalities and thus is optimal. So let's consider $k \< n$.

This problem can be considered as building a paritition of the $n$ variables in $k$ subsets. All inequalities involving two variables in the same subset are unsatisfied, any other is satisfied. I would first build an efficient structure to count the number of inequalities involving each pair of variables. Basically this is a $n^2$ array, built in $O(m)$. In case $m \<\< n$, a graph may be more efficient than a sparse matrix.

Then, let's take arbitrarily $k$ variables and distribute them into the $k$ subsets (give them the $k$ different values). Any inequalities involving these first variables is satisfied (then the arbitrarily may target greedily the largest values in the array).

Then loop on the remaining variables. For each $x\_i$, evaluate $A^i\_k$, the number of unsatisfied inequalities (considering only the variables assigned so far), for each of the $k$ possible assignment. For this, one has to consider every assigned variable in the same subset, this step is $O(n)$.

Let's call $S\_i = \sum\_k A^i\_k$.

By assigning $k\_0$ to $x\_i$,

you unsatisfy $A^i\_{k\_0}$ inequalities but satisfy $S\_i - A^i\_{k\_0}$ ones.

So by picking $k\_0$ that minimizes $A^i\_{k\_0}$, you unsatisfy at most $S/k$ inequalities, satisying at least $S(1-1/k)$ others. So overall you guarantee to satisfy $m(1-1/k)$ inequalities (and clearly $(1-1/k)OPT$ ones).

This achieves $O(m + n^2)$ in time and $O(n^2)$ in space.
> 1 votes

# Answer
Your problem is known as MAX-$k$-CUT, a generalization of the well-known MAX-CUT problem. A recent paper on the topic is Alantha Newman, Complex semidefinite programming and Max-$k$-Cut.

The classic algorithm of Goemans and Williamson gives a (roughly) 0.878 approximation for MAX-CUT (the case $k=2$ of your problem), which is tight assuming Khot's Unique Games Conjecture. The best possible approximation ratio (assuming the Unique Games Conjecture) for $k \> 2$ is not yet known, as far as I understand, but it is known to be better than $1-1/k$ for all $k$.

A random assignment satisfies in expectation a $1-1/k$ fraction of the constraints, and in particular gives a $1-1/k$ approximation in expectation. This algorithm can be derandomized using the method of conditional expectations, as well as using the greedy approach outlined in Optidad's answer.
> 1 votes

---
Tags: optimization, randomized-algorithms
---


# Question
Title: How are useless states created NFA to DFA
So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, *how* and *why* are useless states created, and how can you (if there is a way) convert an NFA to a DFA without creating any useless states?

# Answer
Below a nondeterministic automaton for the language of all strings where the one-but-last letter is an $a$. If we make it determinsitic using the standard construction half of the states will be unreachable.

You ask, why does this happen? Look at the initial state $0$ of the original automaton. It has a loop for both $a$ and $b$. That means that in the powerset construction all next states will always contain state $0$ because the deterministic automaton collects the states of all paths from the original automaton. As a consequence all states without $0$ are uneachable.

It is possible "by hand" to avoid those unreachable states, by a step by step construction. Only consider staes that are reached and continue form those to the next possible states. A kind of depth-first construction will work.
> 3 votes

# Answer
If the construction method supports "negative" regular expression operators, such as set intersection or set difference, it's likely that the method will produce useless states. For example, Brzozowski's method, when given the expression $\left(a \cup b\right)^\* \setminus \left( a \left( a \cup b\right)^\* \right)$, will likely produce something like this:

The branch $q\_2$ corresponds to the "removed" subexpression $a \left( a \cup b\right)^\*$. (Note that this is a DFA.)

The typical way to eliminate useless states in real-world DFA generators is to use DFA minimisation. In the minimal DFA, all useless states map to a single state, so there's only one state to remove.
> 2 votes

---
Tags: turing-machines, finite-automata, nondeterminism
---


title: Linear Speedup and Amdahl's law

text:
# Question
Title: Linear Speedup and Amdahl's law
I'm having trouble understanding and solving the problem.

Suppose we have a program which is composed of 3 portions A, B and C and that each portion takes $t\_A$, $t\_B$ and $t\_C$ respectively to run on a single-core CPU.

Assume that $t\_A$ \< $t\_B$ \< $t\_C$

Assume we parallelize only the portion C of the code and that we run the whole program on a cluster that has up to $N$ cores. The speedup we achieve is linear to the number of cores.

I have to plot the execution time vs the number of cores

What I don't understand is, how can you have a linear speedup ? I've tried playing around with Amdahl's formula to find a way to have a linear speedup to the number of cores. I might be mistaken, but I've realized that this is only possible if the speedup is equal to the number of cores (so I don't understand how you can achieve a linear speedup).

If you could explain this to me, that would be very helpful, thank you.

# Answer
The phrase

> The speedup we achieve is linear to the number of cores.

refers only to the C portion of the program. Therefore the running time on $N$ cores is

$$ t\_A + t\_B + \frac{t\_C}{N}. $$

The speedup is

$$ \frac{t\_A + t\_B + t\_C}{t\_A + t\_B + t\_C/N} = \frac{1}{\frac{t\_A + t\_B + t\_C/N}{t\_A+t\_B+t\_C}} = \frac{1}{\frac{t\_A+t\_B}{t\_A+t\_B+t\_C}+\frac{1}{N} \frac{t\_C}{t\_A+t\_B+t\_C}}. $$ This is Amdahl's law.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Probability of loss using a binary symmetric channel
Today we talked about Information Theory and the binary symetric channel.

For newbies here is a little explanation :

For instance if I want to send a binary to someone :

The bit will be "flipped" with a "crossover probability" of p, and otherwise is received correctly.

Example :

Note that in order to reduce the probability of the "flip" we repeat the bit 2,3,4... times. Here we use a R3 encoding cause the bit is repeated 3 times. Then to decide the transmitted bit we choose the most popular in this packet of 3 bits (in this case).

Up to here it's ok but i'm struggling with a question of my homework :

> Let's suppose we use a R3 encoding, what's the probability a bit will be flipped ?

Thanks !

# Answer
R3 encoding is a pair of algorithms:

* Encoding: a bit $b \in \\{0,1\\}$ is encoded as the packet $bbb$.
* Decoding: a packet $xyz \in \\{0,1\\}^3$ is decoded as the majority bit (the bit occurring most often).

Since the situation is symmetric, in order to understand the transmission error, it suffices to consider the case $b = 0$. Suppose we encode the bit $0$. So we transmit the packet $000$. Every bit is flipped with probability $p$, and this gives us a distribution on the received packet $xyz$. Finally, a transmission error occurs if $xyz$ is decoded as $1$, that is, if the majority of $xyz$ is $1$.

Therefore, the transmission error is the probability of the following event:

> If $x,y,z \in \\{0,1\\}$ are independent identically distributed bits such that $\Pr\[x=1\] = p$, what is the probability that the majority of bits in $x,y,z$ is $1$?

You can compute this probability by brute force.
> 1 votes

---
Tags: computer-networks, information-theory, probabilistic-algorithms, entropy, binary
---


# Question
Title: Checking whether there is cycle of odd length in a k-coloring undirected graph
Also, what is the meaning of the notation used in the question- c: v-\>{0,1,2....k-1} such that c(u)!=c(v)?

# Answer
> 0 votes
Proof that a graph is bipartite if and only if the graph does not contain any cycles of odd length:

So for the $\Leftrightarrow$ relation to be true you have to show both directions:

**$\Rightarrow$:**
If your graph contains a cycle of odd length you can show by counter example that this graph can not be colored with 2 colors such that two neighbour vertices do not have the same color. E.g take a cycle with 5 vertices. You can see that you need at least 3 colors to coler this graph.

**$\Leftarrow$:**
So for this direction you have a graph wich does not contain a cycle of odd length. To show that this graph can be colored with only two colors you can start a breadth-first search from an arbitrary vertex $s$. Whenever a vertex $v$ gets visited by the breath-first search it gets colored with color 1 if its distance from $s$ denoted $d(v)$ is even, respectively gets colored with color 2 if its distance $d(v)$ is odd.
Since the graph does not contain any cycle of odd length there can not be an edge which neighbouring vertices get the same color.

This proof shows that if the options 1 and 2 of your questions are true, the option 3 has to be false. And since the option 4 is the opposite of the third option it is also true.

$c:v\rightarrow\\{0,1,2,\dots,k-1\\}$ such that $c(u)\not=c(v)$ for every edge $(u,v)$ simply means that two adjacent vertices can not be colored with the same color.

---
Tags: graphs
---


# Question
Title: Can quantum computing help solve NP-Complete problems?
i was just wondering if quantum computing has done any good so far in solving NP complete problems. I am aware that quantum computing does solve some NP problems which are classically hard in polynomial time but as far as i know none of those problems are NP complete.

So there are a few interesting questions one could ask here:

* Is there any proof or indication that such an algorithm is impossible/possible?

In this post (Why did Google not use an NP problem for their quantum supremacy experiment?) the top answer states:

> However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

But it'd be nice to hear some reasoning why that is believed to be the case when other exponential time problems have already been reduced to polynomial time.

* If such an algorithm were to be found for any NP-Complete problem would that mean that any NP problem could be solved efficiently by quantum computers just like classically finding a polynomial solution to an NP hard problem would prove P = NP?

# Answer
BQP (the quantum analog of BPP) is closed under polynomial time reductions, so if some NP-complete problem is in BQP, then all NP-complete problems are in BQP. For more arguments, check this Quora question or that Quora question.
> 2 votes

---
Tags: np-complete, np, quantum-computing
---


title: 3SAT and directed graph

text:
# Question
Title: 3SAT and directed graph
Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x\_{i}$ we have the nodes $x\_{i}$ and $!x\_{i}$; for each clause, for example $\left(x\_{a} \vee x\_{b} \vee x\_{c}\right)$, we draw the following arrows $!x\_{a}x\_{b}$, $!x\_{a}x\_{c}$, $!x\_{b}x\_{a}$, $!x\_{b}x\_{c}$, $!x\_{c}x\_{a}$, $!x\_{c}x\_{b}$.

Is it possible understand from the graph if there is a variable $x\_{i}$ such that $x\_{i}\Leftrightarrow !x\_{i}$ ($!x\_{i}$ is $not\left(x\_{i}\right)$)?

# Answer
I think you are trying to build the 2-SAT implication graph for 3-SAT.

In 2-SAT, $(x\_a \vee x\_b)$ may indeed be considered as 2 implications, $\neg x\_a \Rightarrow x\_b$ and $\neg x\_b \Rightarrow x\_a$.

The problem is that $(x\_a \vee x\_b \vee x\_c)$ is not equivalent to any of the 6 implications like $\neg x\_b \Rightarrow x\_a$, as $x\_c$ is sufficient to satisfy the clause. You may eventually have $(\neg x\_a \wedge \neg x\_b) \Rightarrow x\_c$ or $\neg x\_a \Rightarrow (x\_b \vee x\_c)$, but neither let you build such implication graph.
> 2 votes

---
Tags: algorithms, complexity-theory, graphs, np-complete, satisfiability
---


# Question
Title: Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?
When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set of functions

$$O(g(n))= \left\\{ f(n):\text{ there exist positive constants }c\text{ and }n\_0\text{ such that},\\ 0\leq f(n)\leq cg(n),\text{ for all }n\geq n\_0 \right\\}$$

This excerpt has been taken from introduction to algorithms 3rd edition. What I fail to understand is that how can algorithms with a linear runtime have an asymptotic upper bound when linear functions don't have asymptotes or is there a loophole in my thinking?

# Answer
> 1 votes
The technical meaning of *asymptotic upper bound* is given by the definition of big O. That is, $g(n)$ is an asymptotic upper bound on $f(n)$ if $f(n) = O(g(n))$ according to the definition you wrote.

The term *asymptote* may have other meanings in other circumstances. For example, in analytic geometry, an asymptote of a function $f(x)$ is either a line $\ell(x)$ such that $\lim\_{x\to\infty} \[f(x)-\ell(x)\] = 0$ (or the same with $x\to-\infty$), or a vertical line at a point $x\_0$, i.e., $\lim\_{x\to x\_0-} f(x) = \infty$ (or $x\_0+$, or $-\infty$).

The two definitions are different in several ways:

* The geometric definition (per Wikipedia) uses $f(x) - \ell(x)$, whereas big O uses $f(x)/\ell(x)$.
* The geometric definition asks $f(x)-\ell(x) \to 0$, whereas big O only asks that $f(x)/\ell(x)$ be bounded.
* The geometric definition only allows $\ell(x)$ to be linear, whereas big O allows arbitrary functions (implicitly, eventually positive).

# Answer
> 1 votes
Word "asymptotic" is used to emphasize the condition $\exists n\_0\in \mathbb{N}$ $\forall n\> n\_0$ for inequality $0\leqslant f(n) \leqslant C g(n)$ and generally does not contain any mention of limit or asymptotic. Even well known definition of O big, using $\lim\sup \frac{f}{g}$, have sense only when limit point for O big is not limit point for $g$'s zeros.

As to linear function, for example $f(n)=an+b$, then it easy to find solution for $an+b \leqslant C n $ finding $C\>a$ and taking $ n \geqslant n\_0= \lfloor \frac{b}{C-a} \rfloor+1 \>0$. So we obtain $f(n)=an+b \in O(n)$ i.e. linear function is O-big $n$.

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


# Question
Title: Type-checking function calls with functional subtyping
I'm relatively new to the topic. Suppose that you want to type-check an expression of the form `f(a)`, i.e. a function call. Assuming that all the declarations are provided explicit types, I believe that a simple type-checker would behave as follows:

1. Given the environment, compute the types of `a` and `f`;
2. Check that the type of `f` be of the form $T\to U$;
3. Check that the type of `a` be a subtype of $T$;
4. Return $U$ if needed.

But now suppose that, for all $U$, the following subtyping relation holds:

$$ \[U\]\<:\text{Int}\to U $$

where $\[\thinspace\cdot\thinspace\]$ denotes the array-type, and that computation (1) finds the types of `a` and `f` to be resp. $T$ and $\[U\]$ for some $T$, $U$. Now, $\[U\]$ is not a function-type, so check (2) fails. I'm assuming that the definition of $\<:$ is completely independent of the type-checker, so we can't just hard-code a check (2.1) for array-types, too. We could instead check that $\[U\]$ be a subtype of a least acceptable function-type $T\to\top$, where $\top$ denotes the universe-type, but what if function-types are invariant according to $\<:$?

I suspect that what I really need is a form of type-inference, rather than type-checking, even though the types of `f` and `a` are completely determined, which doesn't make sense to me. What would be the correct approach, here?

# Answer
Presumably, what Scala does (since you mentioned it) is relax your step 2. It is incorrect to check that the type of $f$ is merely 'of the form' $T → U$ because it is applied. Rather, one should check that the type of $f$ is known to be a subtype of some $T → U$.

In Scala, such subtyping 'facts' can be added by declaration when defining a type. So, arrays are declared to be subtypes of function types. You gave this as:

$$\[U\] \<: \mathsf{Int} → U$$

This is just an axiom that needs to be part of the subtyping check. Scala is actually even more complex than this, but this at least covers the subtyping part.

As Andrej mentioned in the comments, these sorts of arbitrary 'declared' subtyping axioms don't necessarily lead to the nicest behavior (principal types, decidability, etc.). There might be multiple particular strategies that you could replace your steps with to incorporate the change to step 2, and they might have different limitations on what types they can check/infer for various examples.
> 3 votes

---
Tags: programming-languages, type-checking, type-inference
---


# Question
Title: Multiple correct answers for compilation
When you are asked to hand compile into assembly language, are there multiple correct answers? For example, in https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c11/c11s3/compilation\_answers.pdf, can you get the correct solution even if your solution doesn't match the solution given?

# Answer
Yup. There are multiple sequences of assembly instructions that all do the same thing. (For instance, one trivial way to see this is to notice that you can insert a no-op instruction anywhere.) They might not all be equally good, but they'd all be correct.
> 2 votes

---
Tags: computer-architecture, compilers
---


# Question
Title: Asymptotic runtime of recursive algorithm uisng subsitution method
I need to solve this question using the **substitution method**:

$T(n) = 3T(n/2)+2n$ if $n\>1$ otherwise, $T(n) = 1$

Note: $$\sum\_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$ $$a^{\log\_b n} = n^{\log\_b a}$$

---

I made some attempts at it but I haven't been able to recognize the pattern. It looks to me that it will be $\mathcal{O}(n \log n)$ but I'm having a hard time proving it.

---

The substitution method: Substitute the right-hand side of the equation into any recursive instances that appear on the right-hand side:

$$T(n) = c + T(n-1)$$

$$T(n) = c + \[c + T((n-1)-1)\] = c + \[c + T(n-2)\]$$

$$T(n) = c + \[c + \[c + T(n-3)\]\]$$ $$...$$

$$T(n) = c+c+...+c + T(0)$$ $$T(n) = nc + T(0)$$ So $T(n) \in \mathcal{O}(n)$

# Answer
> 0 votes
Here is an argument by substitution: $$\begin{aligned} T(n) &= 3T(n/2)+2n \\\&= 3(3T(n/4)+n)+2n \\\&= 3(3(3(T(n/8)+n/2)+n)+2n \\\&= \cdots \\\&= 3^kT(n/2^k)+\sum\_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\\&= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\\&= 3^kT(n/2^k)+4n\left(\frac{3}{2}\right)^k-4n \end{aligned}$$ Here, we stop to expand terms when $n/2^k=1$, or equivalently, when $k=log\_2n$. Using that knowledge and the identity that you wrote in your question, we get that: $$\begin{aligned} T(n) &= 3^{log\_2n}T(1)+4n\left(\frac{3}{2}\right)^{log\_2n}-4n \\\&= n^{log\_2{3}}+4n\cdot n^{log\_2\frac{3}{2}}-4n \\\&= \cdots \\\&= 5n^{log\_2{3}}-4n \\\&\in\mathcal{O}(n^{log\_2{3}}) \end{aligned}$$ So as you can see, the fact that you have a factor 3 outside and a factor 2 inside makes your runtime polynomial in $n$.

---
Tags: algorithms, algorithm-analysis, asymptotics, recursion
---


# Question
Title: Is in-place run length encoding possible in O(1) space given that the output is shorter than the input?
This is inspired by a problem from here. This is the approximate form of the problem:

Given a string like "aaaa777cbb" (10 symbols long), run length encode it in-place to a string like "a473c1b2" (8 symbols long). You are guaranteed that the input will always be longer than the output.

The precise form of the problem is:

* You are given an ordered list $L$ of symbols from a set $S$. Any symbol from $S$ may appear in the list.
* $S$ contains all the positive integers up to and including $|L|$ (the length of $L$) and also some other symbols.
* Rules of manipulating the input in-place
    + You can replace one symbol in the list with another
    + You can trim the list to a length of your choice by removing symbols from the end
    + You cannot insert symbols
* You must overwrite the list of symbols with it's run-length-encoding representation and trim it to length so that it includes only the run-length-encoding representation.
    + The run-length-encoding representation replaces each series of 1 or more of the same symbol in the input with that symbol followed by the symbol representing the number of occurrences of the previous symbol.
        - For example: $\[a, a, a, a, a, a, a, a, a, a, 7\]$ becomes $\[a, 10, 7, 1\]$ meaning "$a$ ten times followed by $7$ one time"
        - Note that the length of the output list is always even
    + You are guaranteed that the length of the input list is always larger than the length of the output list
* You must do this with $O(1)$ additional working memory
    + Each "word" of working memory contains $log\_2 |S|$ bits (put another way, words may be constructed which store constant amounts of information, the position of any element in the input, or any symbol from the input)

Intuitively I don't think this is possible. The solutions provided on the original site seem to break on strings like "abccccc" (length 7) where the output should be "a1b1c5" (length 6), since they start by overwriting "b" with the "1" from "a1" before they have even checked which symbol is in the 2nd position.

I have thought about trying to start by finding the compressible runs of letters (2 or more of the same letter), but I don't know how to tell which symbols are already processed and which are from the original input without using some sort of memory that which would grow with the size of the input (like a bitmap of processed areas) and therefore put me in violation of the $O(1)$ space requirement.

I consider acceptable answers to be proofs that this problem either is or is not solvable in $O(1)$ space.

# Answer
> 1 votes
An $O(1)$ space algorithm that uses one extra symbol not found in $L$, which I will call $B$ for blank space.

I define an operation, a "shift right" at position $k$. It finds the next blank symbol $B$ after position $k$ , shifts all symbols one to the right, and sets position $k$ to $B$. For example a right shift at the third symbol:

```
abcdeBfjgB    becomes    abBcdefjgB
  ^                        ^

```

Similarly a "shift left" at position $k$ assumes there is a $B$ symbol there, and moves it all the way to the end of the string, shifting all other symbols left.

```
abBdeBfjgB    becomes    abdeBfjgBB
  ^                        ^

```

Note that you can perform both shifts in $O(1)$ memory.

Now, first we replace all runs of any symbol $x$ with length $l \geq 3$ or greater with $xlB^{l-2}$. This can be done in-place, and leaves such runs identifiable. Also note that these are all the runs that shortens the output compared to the input.

Then, move a single pointer $p$ from left to right:

1. If the string at the pointer starts with $B$, shift left.
2. If the string at the pointer starts with $xlB^+$, this is the start of a run with length at least 3. Increment $p$ by $2$.
3. If the string at the pointer starts with $xx$ replace it with $x 2$ and increment $p$ by 2. Note that $xx$ can never be the start of a run of length 3 or higher, since we already replaced those.
4. If the string at the pointer has form $xy$, increment $p$ by 1, shift right, and replace the resulting $B$ at $p$ with $1$. Increment $p$ by 1 again. Note that the shift right must succeed due to the guarantee the output is shorter than the input, and we already created all space possible when replacing all runs of length $3$.

If any space is left over at the end, the algorithm will eventually get stuck performing step 1. Detect this, strip the remaining space, and you are done.

---
Tags: space-complexity
---


# Question
Title: How can I compute logarithm when comparison is undecidable?
In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively:

```
newtype ArbReal = ArbReal {approximate :: Word -> Integer}
data ArbComplex = ArbReal :+ ArbReal

```

For the `ArbReal` type, the `ArbReal` constructor labels a function that, when fed an integer $n$, computes the encoded real number to $n$ decimal digits below the decimal point, rounded. For example, when `ArbReal f = pi`, `f 0` = 3, `f 1` = 31, `f 2` = 314, and so on.

Note that there is no guarantee to the direction of rounding. Given `ArbReal g = 0.5`, `g 0` can be either 0 or 1. This is inevitable, for if there were, an interval would be decidable.

`ArbComplex` encodes a complex number by specifying its real part and imaginary part.

I've successfully implemented addition, subtraction, multiplication, and division on both types. Division by 0 falls in an infinite loop, though.

I also implemented nth root function of real numbers, square root function of complex numbers (where branch cut doesn't exist, hence multivalued), and $\pi$.

Now it's time to implement natural logarithm (on complex numbers, without a branch cut). And that's where a problem emerged. I was implementing the algorithm (namely, AGM iteration) in this paper, but:

> Finally, if $0\< x \<1$, we may use $\log(x) =−\log(1/x)$, where $\log(1/x)$ is computed as above.

This paragraph forces a comparison, which is undecidable. So it's impossible to implement the algorithm directly. Indeed, in my current version of implementation, $\log 1$ falls in an infinite loop.

Is there a tweak on the algorithm that makes the algorithm computable? Or must I implement a completely different algorithm?

# Answer
Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range.

For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right\]$, $B = \left\[\frac{1}{2},\frac{3}{2}\right\]$, or $C = \left\[\frac{5}{4},\infty\right)$ with little difficulty. Use AGM if it's in $C$, the transformation if it's in $A$, and if it's in $B$, use this transformation:

$$\log (x) = \log (2x) - \log 2$$
> 4 votes

# Answer
Logarithm is undefined for x\<0 and -infinity when x=0, that’s something you have to handle somehow. For the test x \< 1: whatever approximation you use for x \>= 1 will most likely work for x \> 0.9999. You don’t need to decide if x \< 1, just if x is small enough. For x = 0.99995 either decision will work.
> 0 votes

---
Tags: algorithms, computability, numerical-algorithms, numerical-analysis
---


# Question
Title: Calculate number of error-correcting code check bits
To design a code with $m$ data bits and $r$ check bits which allow all single-bit errors to be corrected, the formula $$(n + 1) 2^m \leq 2^n$$ with $n = m + r$ and $(m + r + 1) \leq 2^r$ is used. Why is $+ 1$ used here, doesn't $n$ contain already all possible codewords?

# Answer
Consider a binary code $C$ of length $n$ (each codeword consists of $n$ bits), containing $2^m$ codewords, and allowing all single-bit errors to be corrected.

Let $x \in C$, and let $B\_x$ denote all words at distance at most $1$ from $x$, that is $x$ itself, as well as any word obtained by flipping a single coordinate. Any word in $B\_x$ could result from a transmission of $x$ followed by at most one error. Since $C$ allows all single-bit errors to be corrected, for any $y \in B\_x$, the only codeword within distance $1$ from $y$ must be $B\_x$. In other words, the balls $B\_x$ are disjoint.

Since there are $2^m$ balls $B\_x$, each one contains $n+1$ words, the balls are disjoint, and there are $2^n$ possible words, we deduce that $(n+1)2^m \leq 2^n$. This is the so-called sphere-packing bound or Hamming bound.
> 1 votes

---
Tags: error-correcting-codes, hamming-code, hamming-distance
---


# Question
Title: How do you prove these string/number radix encoding/decoding algorithms work?
A while back I learned of these great algorithms:

```
function parseInt(value, code) {
  let x = 0
  let i = 0
  while (i < value.length) {
    const a = value[i]
    x = x * code.length + code.indexOf(a)
    i++
  }
  return x
}

function toString(value, code) {
  const radix = code.length
  let result = ''

  do {
    const digit = value % radix
    result = code[digit] + result
    value = Math.floor(value / radix)
  } while (value)

  return result
}

```

which allow you to convert `toString` any (albeit 32-bit) number to a string using a custom "alphabet" or "code", and do the reverse and parse a corresponding string to int.

```
console.log(parseInt('dj', 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// 123
console.log(toString(123, 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// dj
console.log(parseInt('a', 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// 0
console.log(toString(0, 'abcdefghijklmnopqrstuvwxyz0123456789+-'));
// a

```

How do you prove that these algorithms actually do the trick? What does the proof look like from base principles? Tangent/bonus: How would you ever go about figuring this out from scratch? To me this is pure magic and I would never have been able to figure this out "from scratch". I would like to know what I could've done to figure this out using mathematical techniques/principles.

# Answer
> 1 votes
First, you need to figure out what it is you want to prove. Here, I'd say we want to prove that

`toString(parseInt(x, code),code) = x`

and

`parseInt(toString(x, code),code) = x`

It's pretty obvious that trying to prove this is going to fail if:

* we overflow the result in parseInt, because then parseInt isn't surjective
* the input in parseInt contains characters that aren't in the code

So, our proof has to include the assumption that both are not the case.

The first proof is probably easier than the second. We can do induction on the length of \`value':

`toString(parseInt(x, code),code) = x`

Given an arbitrary code which contains all characters in `x`

If x.length == 0:

* `x == ''`
* `parseInt(x, code) returns 0`
* `toString(0, code) returns ''` \<- actually it returns 'a' so the proof breaks here, but you can do the same if you assume length 1

If x.length \> 1

* our induction hypothesis: for all prefixes y of x `toString(parseInt(y, code),code) = y`
* `parseInt(x, code) = parseInt(x[:-1], code) * code.length + code.indexOf(x[-1])` (I am using python syntax here to say everything but the last element, and the last element. This in and of itself would have to be proved I guess but it would be very easy if the algorithm was written recursively instead of iteratively)
* `toString(a * code.length + b, code) = code[b] + toString(a, code)` (again, this would be straightforward if the algorithm was recursive, but it should be convincing enough that this is the case here)
* that means `toString(parseInt(x,code),code) = toString(parseInt(x[:-1], code) * code.length + code.indexOf(x[-1]), code) = code[code.indexOf(x[-1])] + toString(parseInt(x[:-1], code), code) = (using induction hypothesis) x[-1] + x[:-1]` which breaks our proof because toString has a bug and inverts the string, as far as I can tell.

Assuming the line `result = code[digit] + result` actually read `result = result + code[digit]` like I think it should:

* `toString(a * code.length + b, code) = toString(a, code) + code[b]` (again, this would be straightforward if the algorithm was recursive, but it should be convincing enough that this is the case here)
* that means `toString(parseInt(x,code),code) = toString(parseInt(x[:-1], code) * code.length + code.indexOf(x[-1]), code) = toString(parseInt(x[:-1], code), code) + code[code.indexOf(x[-1])] = (using induction hypothesis) x[:-1] + x[-1] = x`

QED.

The other direction is similar, you can again use induction as long as you take care that your induction hypothesis is "for all y \< x: parseInt(toString(y, code),code) = y".

---
Tags: algorithms, proof-techniques, strings, correctness-proof
---


# Question
Title: Interval Scheduling problem with more than 1 machine
There are 2 machines.

Each task either requires 1 or 2 machines to run (ie, a 1-machine task can run in parallel with another 1-machine task but a 2-machine task occupies both machine

The list of n tasks are given in \[start time, end time\], both of which are on top of hours. If we were to order the tasks by non decreasing end time the maximum would be D, but the list given is not sorted.

There is no value difference (1 machine and 2 machine tasks are considered same value). Just schedule as many tasks as possible. Want to find an algorithm that runs within O(nD^2) time

I'm considering DP but can't really get my head clear on how to approach the question. Any suggestion would be helpful.

# Answer
> 1 votes
You may want to consider a solution with dp(i, j, k) where i represents the x that machine 1 is at, j represents the x that machine 2 is one, and k represents the index of the task you're considering

The state transition in this case would be O(1) because you either take the task or not, for which you can increment/decrement i/j accordingly.

I'm not sure what D and n are but if D refers to the amount of time allotted for machine 1 and 2 and n is the number of tasks, then I believe this could be the solution you're looking for

Note that "x" refers to time. Also, this solution would work if the tasks were assigned a value

Let me know if you want an implementation of this

---
Tags: dynamic-programming, scheduling
---


# Question
Title: Why isn't plus_assoc rewriting correctly?
First I have `plus_assoc` ready.

```
Theorem plus_assoc : forall n m p : nat,
  n + (m + p) = (n + m) + p.

```

for simplicity we omit the proof of `plus_assoc`.

now I want to prove `plus_swap`:

```
Theorem plus_swap : forall n m p : nat,
  n + (m + p) = m + (n + p).
Proof. intros n m p. rewrite -> plus_assoc. ...

```

the equation was rewritten into `n + m + p = m + ( n + p )`, rather than the expected `(n + m) + p = m + (n + p)`. why?

# Answer
It is rewriting correctly. Coq doesn't print redundant parentheses. The `+` operator is left-associative, so `n + m + p` is a valid way of writing the term `(n + m) + p`, and Coq prints it without the parentheses.

```
Coq < Check (n + m) + p.
n + m + p
     : nat

```

Just to be clear, `n + m +p` and `(n + m) + p` are exactly the same term, not just terms that are equal. They're different ways to use notations to write `Nat.add (Nat.add n m)`.

```
Theorem plus_swap : forall n m p : nat,
  n + (m + p) = m + (n + p).
Proof.
  intros n m p.
  Unset Printing Notations.
  Show. (* Now the goal is shown as: eq (Nat.add n (Nat.add m p)) (Nat.add m (Nat.add n p)) *)
  rewrite -> plus_assoc. (* Now the goal is: eq (Nat.add (Nat.add n m) p) (Nat.add m (Nat.add n p)) *)

```
> 2 votes

---
Tags: proof-techniques, coq
---


# Question
Title: Complete explanation of state elimination methods
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".

In other words, what is the general idea, and what is the difference to convert the NFA to RE and DFA to RE.

Online there are a lot of resources, but it is difficult to find a complete answer to understand the general idea of this method.

And, again, sorry if my question is too general, but I think that this place is a good place to meet people that understand this argument better than me, and are also able to explain it in a logical way.

# Answer
> 2 votes
I'm not an expert, but I try to answer your question with an order, and if I will say something wrong, the people can improve my answer.

In general, is possible to use the State elimination method to convert a "Deterministic state automata" (DFA) to a regular expression (RE).

From the theory, we know the information below

> If a language is regular, then it is described by a regular expression.

We also, know that if a language is regular is accepted by a DFA.

well now to convert a DFA that describes our regular language to the RE, we need to convert the DFA into a "Generalized Nondeterministic automata" (GNFA).

## Definition of GNFA

> A GNFA is simple nondeterministic finite automata (NFA) wherein the transition (arrows of the graph) can contain a regular expression.

We also need the rules about this GNFA, we need the rules below:

* The start state must behave only outgoing state and must hasn't incoming edge.
* The final/accepting state must have only incoming transition and it just hasn't outgoing edge.

Structure example

We can convert easily DFA to a GNFA with a special form, with the following step:

* If a DFA has an incoming edge to the start state A, we move the start state to new state B and we can connect the state B-\>A with an empty string (ϵ).

In addition: The start state must have only outgoing transitions. (if there is an incoming arrow/edge, it must not carry a (non-empty) label).

* if the final/accepting state A has an outgoing transition, we can move the final state to a new state B and connect the node A-\>B with an empty string (ϵ).

In addition: The final/accepting state must have only incoming transitions.

PS. The additional informations are coming from the first comment below this answer.

Now the last step is to convert the GNFA to a RE.

After the conversion of DFA to a GNFA with a special form, we know that each arrow of GNFA can contain a regular expression, and at this point, the last step consists of the following passages:

* Remove the intermediate step with an intermedia regular expression, until to remove all intermediate state. The result that we can have is `(InitState)--- RE---->(FinalState)`, and the regular expression of the transition from InitState to FinalState is the regular expression accepted from the previous DFA.

The passages can be express with the Figure below:

A complete example, that can help you to understand the process described inside this answer.

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


# Question
Title: Can you use binary files to reverse engineer cpu architecture?
I wanted to know if it was possible to add code directly to a computer without an operating system or any programming language. To do that, I thought that maybe I could use the binary files to reverse engineer the actual cpu architecture. Just a random thought but I would like to know if that is possible.

# Answer
> 1 votes
This was certainly possible with early microcomputers such as the Altair 8800. Each instruction or data value was encoded as a binary number, set up by flipping a line of toggle switches up or down, and when the switches were all set correctly another switch was used to write that number into the next memory address.

Once you have done this once or twice you realise how tedious it is. Hence the rapid development of peripherals such as paper tape readers, punched card readers and eventually keyboards, all of which require some sort of operating system, even if a primitive one. In parallel, programming aids such as assemblers, programming languages, compilers and IDEs made programming simpler and quicker, at the cost of creating distance between the programmer and the hardware.

I doubt it would be possible to write binary instructions directly into the memory of a modern laptop, partly because of all the layers of peripherals and operating system functions that stand between you and the CPU, and partly because such a feature could be maliciously misused, so there are security features that prevent it. But it is certainly possible with a microcontroller board such as an Arduino \- or you could build your own Altair 8800 !

---
Tags: programming-languages
---


# Question
Title: Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric
I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The things I know follow:

Bit reversal ring is defined as follows: We assign to each process $i$ the integer from ${0,\ldots, n-1}$ whose $k$ bit representation is the reverse of the $k$ bit representation of $i$. $n$ is also a power of two, $n=2^{k}$.

Two segments $U$ and $V$ are order equivalent if they are the same length $k$, and for all $i$ and $j$ such that $1 \leq i,j \leq k$ we have that $u\_{i} \leq u\_{j}$ if and only if $v\_{i} \leq v\_{j}$.

Ring $R$ is $c$-symmetric if for every segment $S$ of $R$ there are at least $\lfloor \frac{cn}{l} \rfloor$ segments that are order equivalent to $S$, including $S$ itself, where $l$ is length of the segment, and this holds for every $\sqrt{n} \leq l \leq n$.

So after plugging all I know into formulas I get that $\lfloor \frac{2^{k-1}}{l} \rfloor$ is formula for number of segments and $l$ is such that $2^{\frac{k}{2}} \leq l \leq 2^{k}$.

Any hint or piece of information would be much appreciated! Thank you.

# Answer
We will prove your formula for all $\ell$, with a bound of $\lceil \frac{n/2}{\ell} \rceil$. We can assume that $\ell \< n/2$, since otherwise $\lceil \frac{n/2}{\ell} \rceil = 1$, and there is nothing to prove. Also, if $n = 1$ then the result is trivial, so we can assume that $n \geq 2$.

The relative order of elements in the interval of length $n/2$ starting at $i$ is the same as the relative order of elements in the ring of length $n/2$, when read from position $i$. For example, here are all intervals of length $4$ in the ring of length $8$, and the corresponding intervals in the ring of length $4$: \begin{align} &0,4,2,6 & 0,2,1,3 \\ &4,2,6,1 & 2,1,3,0 \\ &2,6,1,5 & 1,3,0,2 \\ &6,1,5,3 & 3,0,2,1 \\ &1,5,3,7 & 0,2,1,3 \\ &5,3,7,0 & 2,1,3,0 \\ &3,7,0,4 & 1,3,0,2 \\ &7,0,4,2 & 3,0,2,1 \end{align} To see this, note first that each interval on the left doesn't contain a pair of elements which differ only in their LSB. Therefore, we can ignore the LSB of all elements on the left. One way to do it is to divide all elements on the left by two. This results in the intervals on the right.

This property immediately implies a similar property for all intervals of length $\ell \leq n/2$: the relative order of elements in the interval of length $\ell$ starting at $i$ is the same as the relative order of elements in the interval of length $\ell$ starting at $i \bmod (n/2)$ in the ring of length $n/2$. This implies (by induction) that an interval of length $\ell \leq n/2$ has at least this many order-equivalent intervals: $2\lceil \frac{n/4}{\ell} \rceil \geq \lceil \frac{n/2}{\ell} \rceil$.
> 3 votes

---
Tags: algorithms, complexity-theory, distributed-systems
---


title: Intervals Collision Detection Algorithm

text:
# Question
Title: Intervals Collision Detection Algorithm
Given a collection of non-empty intervals \[a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit some collision/overlap where the worst-case performance of the algorithm is better than O(n^2)? You can assume that intervals starting at an end of another interval do not overlap, ex \[15,22) and \[22,30) do not overlap.

For example, given this collection {\[12,16),\[8,13),\[16,34)} the result would be {0,1} because interval at index 0 intersects some interval, and interval at index 1 intersects some interval.

I have an algorithm that in worst case performs O(n^2) but can't figure out one that is faster. Mine doesn't use binary search trees, simply orders the intervals according to a, and then has a loop over all the elements with an inner loop on the remaining elements checking for intersection -- once an inner loop interval doesn't intersect the inner loop stops and the outer loop proceeds to the next element.

I am not looking for exact code, just a clear explanation of such an algorithm.

# Answer
As pointed out by the other answer, producing a list of the intersections is not doable in subquadratic time. However, counting all the intersections can be done in linear time. The rough idea for that one is to sort all coordinates (starting points and end points of intervals) into one list using counting sort (as the range of the values we are sorting is fixed) and iterate over it, maintaining a counter for the number of intervals intersecting at the current point and another one for the total number of intersections. If the current coordinate is an end point, reduce the first counter by 1. Otherwise (i.e. the current coordinate is a starting point), increase the first counter by 1 and increase the total counter by the value of the first counter.
> 1 votes

---
Tags: algorithms, intervals
---