# Question
Title: Why can't we round results of linear programming to get integer programming?
* If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed?
* If linear programming suggests we can afford only $3.7$ workers, then why can't we just round down to $3$ workers?

When can we not use this rounding technique?

# Answer
> 7 votes
If there are only constraints that place a lower bound on the number of trucks, but no constraints that place an upper limit on the number of trucks, then of course you can round up. That will still give you *a* solution.

However, there are multiple caveats:

* First, this isn't always possible. Sometimes there are both constraints that place lower limits and constraints that place upper limits. It can happen that taking a solution and rounding gives you something that is no longer a solution.
* Even if the result of the rounding is a solution, there is no guarantee that it is the *best* out of all solutions that uses integers. There may be some other way to choose integers for all the variables that is better than the solution you got by rounding.

If you want solutions that are all integer, then you have an integer linear programming problem. Integer linear programming (ILP) is harder than linear programming (LP). In particular, there are polynomial-time algorithms for LP, but ILP is NP-hard, so there is most likely no polynomial-time algorithm for ILP (unless P=NP, which is considered unlikely).

# Answer
> 9 votes
In $\mathbb R$, one can simply round *down* or round *up* to obtain an element of $\mathbb Z$. Only two choices!

However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding.

Of course, one can round all entries of an $n$-dimensional vector down or up, but do note that the Euclidean distance between the two farthest vertices of the hypercube $\[0,1\]^n$ is $\sqrt n$. If $n=100$, then $\sqrt{100} = 10$.

Unfortunately, to the best of my knowledge, there is no guarantee that the solution to the integer program will be found via one of the $2^n$ possible rounding schemes.

Fortunately, *some* linear programs have integer solutions and, thus, no rounding is required.

# Answer
> 4 votes
Here is a 2d region where rounding the optimal continuous solution (top right) will always give an invalid integer solution:

Here is a 2d region where rounding the optimal continuous solution (green vertex) may give you a valid integer solution `0,1`, but will never give you the optimal integer solution `2,1` (blue vertex). Maximizing `y+5x` for positive x, y.

---
Tags: optimization, linear-programming, integer-programming, rounding
---


# Question
Title: Simplify $R:=0^*+0^*1\left(1+000^*1\right)^*0^*$
I'm trying to simplify the following REGEX:

$$R:=0^\*+0^\*1\left(1+000^\*1\right)^\*0^\*$$

$R$ is the result of transforming a GNFA that recognizes $L:= \\{w \in \\{0,1\\}^\* | \left(\forall \ i \in \left\[1,|w|-2\right\]\cap \mathbb{N}\right)\ w\_iw\_{i+1}w\_{i+2} \neq 101\\}$

I already know that there exists $R':=0^\*\left(1+000^\*1\right)^\*0^\*$ such that $L(R)=L(R')=L$

Any hints?

# Answer
> 0 votes
$$R:=0^\*+0^\*1\left(1+000^\*1\right)^\*0^\*$$ $$R=0^\*+\left(\epsilon + 00^\*\right)1\left(1+000^\*1\right)^\*0^\*$$ $$R=0^\*+\left(\epsilon + 0\left(\epsilon + 00^\*\right)\right)1\left(1+000^\*1\right)^\*0^\*$$ $$R=0^\*+\left(\epsilon + 0+ 000^\*\right)1\left(1+000^\*1\right)^\*0^\*$$ $$R=0^\*+\left(1 + 01 + 000^\*1\right)\left(1+000^\*1\right)^\*0^\*$$

By the commutativity of $+$ in $\\{0,1\\}^\*$ $$R=0^\*+\left(1 + 000^\*1 + 01\right)\left(1+000^\*1\right)^\*0^\*$$

By the associativity of $+$ in $\\{0,1\\}^\*$ $$R=0^\*+\left(\left(1 + 000^\*1\right) + 01\right)\left(1+000^\*1\right)^\*0^\*$$

Since the concatenation is distributive over the union, then

$$R=0^\*+\left(1 + 000^\*1\right)\left(1+000^\*1\right)^\*0^\* + 01\left(1+000^\*1\right)^\*0^\*$$

$$R=\left( \epsilon +\left(1 + 000^\*1\right)\left(1+000^\*1\right)^\*\right)0^\* + 01\left(1+000^\*1\right)^\*0^\*$$

$$R=\left(1+000^\*1\right)^\*0^\* + 01\left(1+000^\*1\right)^\*0^\*$$

$$R=\left(\epsilon + 01 \right)\left(1+000^\*1\right)^\*0^\*$$

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Not CPA secure for CBC mode if some code are changed that is if we replaced a function $\pi(k,x)=k\oplus x$
Consider the CBC mode where the block cipher is replaced by a function $\pi$ where $\pi(k,x)=k\oplus x$. Show that the mode is not CPA secure.

I am not got how to proceed to solve this question. Please someone helps me out to know how to solve it.

# Answer
> 0 votes
If we choose some string of our choice, lets say we chose $s:=0^n$. Then, $\pi(k,s)$ would be the cyphertext, but $$\pi(k,s)=k\oplus s=k\oplus 0^n=k$$

Which means that we can very easily extract the (first) key. In fact, this works for any string $s$ we want:

Define $k':=s\oplus \pi(k,s)$. Notice that we know how to compute $k'$ since we chose $s$ and got $\pi(k,s)$ (we still don't know $k$). But, we can calculate the following: $$k'=s\oplus \pi(k,s)=s\oplus (k\oplus s) = s\oplus (s\oplus k) = (s\oplus s)\oplus k = 0^n\oplus k = k$$

Hence, $k'=k$ and thus we actually calculated what the key is.

---
Tags: cryptography
---


# Question
Title: Testing of Clustering of points in metric space in sub-linear time
I am trying to understand this paper, in which (k, b)-clusterability is defined like so:

A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ subsets (clusters) such that the maximum distance between any pair of points in a cluster is $b$.

The paper offers an algorithm that always succeeds to Accept (k-b)-clusterable sets which states:

Algorithm 1 (in page 4):

1. Let $rep\_1$ be an arbitrary point in $X$ (a representative for the first cluster).
2. $i=1$ $find\\\_new\\\_rep=True$
3. While $i\<k+1$ and $find\\\_new\\\_rep==True$

3.1 Uniformly and independently select a sample of size $ln(3k)/\epsilon$

3.2 If there exists a point $x$ in the sample, such that $dist(x, rep\_j)\>b$ for every $j\le i$, then $i=i+1$; $rep\_i=x$

3.3. Else (all points in the sample are at distance at most b from some $rep\_j$), $find\\\_new\\\_rep = False$
4. If $i\le k$ Accept, Else Reject.

---

I am struggling with the very first part of the proof (Theorem 1 in page 4):

> We first observe that the algorithm rejects only if it finds $k+1$ points whose pairwise distances are all greater than $b$. Therefore, if $X$ is (k, b)-clusterable, then the algorithm never rejects.

What I seem to miss is why can't the algorithm select "wrong" representatives, such that a chosen representative would not allow a clustering to $k$ clusters?

Why can't the algorithm find $k+1$ representatives? (k, b)-clusterability only means there exists a partition to $k$ clusters, why does the algorithm finds that partition?

# Answer
There are no "wrong" representatives assuming that $X$ is $(k,b)$-clusterable.

Think of it like that: $X$ can be divided into $k$ clusters. Say you chose some arbitrary node $x\in X$ to be a representative (doesn't matter which point!). Then, denote for any cluster $C$ such that $x\in C$, we know that for any two points $a,b\in C\_x$, $dist(a,c)\le b$. In particular, for any other point $y\in C$, we have $dist(x,y)\le b$. This means that all nodes in $C$ will never be a new representative.

If at the end there were $k+1$ representatives, then by the pigeon hole principle, two representatives must be in the same cluster, but this is impossible as we have just shown.

Hence, for $(k,b)$-clusterable sets, there will always be at most $k$ different representatives, and the algorithm always accepts.
> 1 votes

---
Tags: algorithms, computational-geometry, clustering, streaming-algorithm
---


# Question
Title: Is there a name for an "array with no holes"?
How would you call an array \[1, 2, 3, 4, 5, ...\] that has (and ensures) the property of not having any undefined values through all its length.

"Dense" could work but it's not exactly what I mean, as it has more to do with zero/non-zero values.

# Answer
> 2 votes
There is no standard term for this, as it's very language-specific whether your notion makes sense, or what it would mean exactly. For instance,

* Some languages have no undefined values, or no undefined values in arrays, or only undefined values for certain data types. For instance, in C, you can cast an arbitrary piece of memory to an array of integers and then read integers from it without ever initializing the array; there is no way of inspecting an array value to determine whether it has ever been initialized. In C, there is no such thing as an undefined integer.
* Some languages, e.g., Perl, support sparse arrays: they not only have undefined values, but whole regions of the array may not have been allocated in memory.
* Some languages, e.g., PHP, distinguish between an array value not being set and it being set to the undefined value. Some, e.g. R, even distinguish between different undefined values.

How will your term apply to them?

# Answer
> 0 votes
The data structure itself is unambiguously called a contiguous array. Depending on the context and language I would call it "initialized" or "having only non-null elements" or similar to describe the contents.

---
Tags: terminology, arrays
---


# Question
Title: Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem
Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$

My approach with recurrence tree:

$n \sim n\log(n)$

$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$

$\frac{n}{4} \sim 4 \frac{n}{4}\log(\frac{n}{4})$

Hence the summation must follow as:

$$T(n) = \sum\_{i=0}^{\log(n)} n\log(\frac{n}{2^i})$$ $$= \sum\_{i=0}^{\log(n)} n(\log(n) - i)$$ $$=(n\log(n) \sum\_{i=0}^{\log(n)}i) - (\sum\_{i=0}^{\log(n)} i)$$

I can not go further from here, any help is welcome.

# Answer
> 1 votes
For direct result let's use direct summation assuming $n=2^k$: $$T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)=2\left\[ 2T\left(\frac{n}{2^2}\right) +\frac{n}{2}\log \frac{n}{2}\right\]+ n\log(n) = \\ =2^2T\left(\frac{n}{2^2}\right)+n\log \frac{n}{2}+ n\log(n) =\\ =\cdots=\\ =2^kT\left(1\right)+n\log \frac{n}{2^{k-1}}+ \cdots +n\log \frac{n}{2}+n\log(n)=\\ =2^kT\left(1\right) +n\log 2 + \cdots +n\log 2^k=\\ =nT\left(1\right) +n\log 2 (1 + \cdots + k) =nT\left(1\right) + \frac{k(k+1)}{2} n\log 2 \in \Theta (n \log^2 n)$$ where, of course, $k=\log\_2 n$. Hope you can obtain from here everything what you wanted.

At end let me note also, that $n \sim n\log(n)$ and other equivalences, which you are using, are not correct, if we understand standard $\lim \frac{f}{g}=1$, for symbol "$\sim$". Correct is, for example, $n = o(n\log(n))$ etc.

# Answer
> 1 votes
From your recursion, beacuse of $T(n)$ have a term $n\log n$ we can conclude that : $$T(n)=\Omega(n\log n)$$ and from your summation :

$$T(n)=n\log(n) \sum\_{i=0}^{\log(n)}i - \sum\_{i=0}^{\log(n)} i\<n\log(n) \sum\_{i=0}^{\log(n)}i\simeq n\log^2 n$$ Finally $$n\log n\leq T(n)\leq n\log^2 n$$ Next step, we try to improve lower bound by induction: Suppose $T(n)\geq c\times n\log^2 n$ $$\rightarrow 2\times c\times\frac{n}{2}\times \log^2 \frac{n}{2}+ n\log n\geq c\times n\log^2 n$$ $$=c\times n\times \log n\times(\log n+\frac{1}{c})\geq c\times n\times \log n\times(\log n+\frac{1}{\log n})\hspace{20pt}\text{if $c\leq$ 1 }\square$$ For sufficiently large $n$ (i.e. $n\to \infty$), and base case above inequality is correct. So we conclude that as $n\to \infty$ $$T(n)=\theta (n\log^2 n)$$

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---


title: Greibach Normal Form of Linear Language

text:
# Question
Title: Greibach Normal Form of Linear Language
I was trying to get an arbitrary linear language to its GNF, and I converted it into one where all the productions were of the form $A\to Ba, A\to aB, A\to a$.

In this question, the accepted answer shows a way of converting some productions of a linear grammar to the GNF. The issue would be, what about the transitions of the form $A\to Ba$? That would be the only issue for both my procedure and the one in the answer, and I don't see any general way of getting those transitions into GNF ones.

If I discard the chance I'm not seeing something evident, I guess it's not that easy to give an explicit GNF for linear languages, and it looks like it might change a lot depending on the structure of the particular language. What should I do next?

# Answer
> 2 votes
As you note, the problem is with the productions of the form $A\to Ba$.

Consider a sequence of such productions $A\_0\to A\_1 a\_1$, $A\_1\to A\_2 a\_2$, $\dots$, $A\_{n-1}\to A\_n a\_n$, $A\_n\to bB$, where the last production is the next one that is in GreibachNF.
Thus $A\_0 \Rightarrow A\_1a\_1 \Rightarrow^\* A\_n a\_n\dots a\_2a\_1 \Rightarrow b B a\_n\dots a\_1 $.

We can summarize this sequence by adding a production $A\_0 \to bB \[{A\_0A\_n}\]$, where $\[{A\_0A\_n}\]$ is a new nonterminal that generates the left side $a\_n\dots a\_2a\_1$, but now as a right linear grammar, so basically in reverse of the original derivation:

$\[A\_0A\_n\] \to a\_n \[A\_0A\_{n-1}\]$, $\dots$ , $\[A\_0A\_2\] \to a\_2 \[A\_0A\_1\]$, $\[A\_0A\_1\] \to a\_1$.

Thus $A\_0 \Rightarrow bB\[A\_0A\_n\] \Rightarrow bBa\_n\[A\_0A\_{n-1}\] \Rightarrow^\* bBa\_n\dots a\_2\[A\_0A\_1\] \Rightarrow bBa\_n\dots a\_2a\_1$

Note that I use two variables in the new $\[A\_0A\_n\]$ as the last component recalls the position in the derivation, whereas the first component stores the initial variable, which is where the new simulation must end.

I think that with some care this can be formulated as a proper construction.

NB. Note this can partly undo your earlier preprocessing. I would not split a production of the form $A\to aBb$ into two productions $A\to aX$ and $X\to Xb$; better avoid introducing left recursive productions.

---
Tags: linear-languages
---


# Question
Title: Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time
I am trying to understand this paper, in which (k, b)-clusterability is defined like so:

A set $X$ of points in a metric space is (k, b)-diameter clusterable if $X$ can be partitioned into $k$ subsets (clusters) such that the maximum distance between any pair of points in a cluster is $b$.

The paper offers an algorithm that rejects A set $X$ if it is $\epsilon-far$ from (k-2b)-clusterable with probability \> $\frac{2}{3}$.

$\epsilon-far$ from (k-2b)-clusterable here means that at least $\epsilon |X|=\epsilon n$ points must be deleted from $X$ in order to make it (k-2b)-clusterable.

**Algorithm 1 (in page 4):**

1. Let $rep\_1$ be an arbitrary point in $X$ (a representative for the first cluster).
2. $i=1$ $find\\\_new\\\_rep=True$
3. While $i\<k+1$ and $find\\\_new\\\_rep==True$

3.1 Uniformly and independently select a sample of size $ln(3k)/\epsilon$

3.2 If there exists a point $x$ in the sample, such that $dist(x, rep\_j)\>b$ for every $j\le i$, then $i=i+1$; $rep\_i=x$

3.3. Else (all points in the sample are at distance at most b from some $rep\_j$), $find\\\_new\\\_rep = False$
4. If $i\le k$ Accept, Else Reject.

---

I am struggling with the very last part of the proof (Theorem 1 in page 4):

> ... Hence, from now on, assume that $X$ is $\epsilon$-far from $(k, 2b)$ -clusterable ...
> Consider any particular iteration. We say that a point $x \in X$ is a *candidate representative* with respect to $rep\_1, ..., rep\_i$ if it has distance greater than $b$ from each of these points. We claim that as long as $i \le k$ there must be more than $\epsilon n$ such candidate representatives. Assume in contradiction that there are at most $\epsilon n$ such points. Then we could remove these points from $X$, and for every other point $y \in X$, assign y to a cluster $j$ such that $dist(y, rep\_j) \le b$. By the triangle inequality, the diameter of each resulting cluster is at most $2b$, **which contradicts out assumption concerning $X$**.

What I seem to miss is **what is the contradiction**?

I can see why every cluster is of diameter $2b$, but I don't see why ignoring all far points, and adding the rest to some valid clusters gives anything not OK.

Would love some direction as I have been staring at this for hours.

# Answer
From what I understand, the problem the paper is trying to solve is a gap problem of deciding whether $X$ is $(k,b)$-clusterable, or at least $\epsilon$-far from being $(k,2b)$-clusterable. Since they explained why the algorithm always accepts when $X$ is $(k,b)$-clusterable, now they move on to explain what happens when $X$ is at least $\epsilon$-far from being $(k,2b)$-clusterable.

Now, their job is to show that there are a lot of candidates in $X$ at any point in time (so the probability of choosing at least one will be high). They **assume towards contradiction** this is not the case. That is, they assume that sometime they reach a state where there are *less* than $\epsilon \cdot n$ candidates. Here comes the tricky part: They want to show this contradicts the fact we know $X$ is $\epsilon$-far from being $(k,2b)$-clusterable, so they remove the $\epsilon \cdot n$ candidates from $X$, and explain why we are left with at most $k$ clusters of size $2b$: Each $y\in X$ that is left, is not a candidate. Hence, there must be some representative $rep\_i$ such that $dist(y,rep\_i)\le b$. They define the clusters to be balls with radius $b$ around all those representatives, and overall each point $y$ must be in at least one ball. The balls have a radius of $b$, so the distance between any two points in them is at most $2b$ (the diameter of the ball). Therefore, they found a $(k,2b)$-clustering of $X$ when we remove those $\epsilon \cdot n$ points. But since $X$ was assumed to be *far* from such a clustering (you need to remove *more* than $\epsilon \cdot n$ to convert it into something clusterable), this contradicted that assumption.

Hence, they conclude that at each point in time there are at least $\epsilon \cdot n$ possible candidates.
> 2 votes

---
Tags: algorithms, computational-geometry, approximation, clustering, streaming-algorithm
---


# Question
Title: Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value
## The Problem

I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form:

$$x = A\times\frac{N}{D}$$

Where $A$ is a 32-bit integer, and $N$ and $D$ are 16-bit integers.

Typical inputs are real numbers between 1 and 1 billion.

---

## My Attempts

I first attempted to use $N$ and $D$ to represent the fractional part of the number, but I can only correct for errors less than one part in 65 thousand, not very useful.

I then looked at naively testing all the possible combinations of $N$ and $D$ to find one with the lowest remainder, even when skipping like fractions (i.e., 2/4, 3/6, etc.), and skipping values of $N$ that would result in a fraction that is too large ($N \leq \frac{x}{D}$). I still need to search more than a billion combinations.

Some test cases I have found challenging; clearly, it's pretty easy to come up with these.

* $1000\times \frac{255}{256}$
* $ 123456 \times \frac{123}{456}$

## Backround

This problem comes up as I am trying to configure a PLL to convert arbitrary input frequencies to a uniform output frequency with the lowest error possible.

## Question

Is there a much more efficient way to solve this problem? Does this kind of problem have a name that I can look up?

# Answer
> 3 votes
Generally speaking, this problem is called diophantine approximation.

However, your inputs are not just real numbers but double-precision floating point (aka `double`) numbers, which are in fact rational. Any `double` number has the form:

$$ (-1)^{sign} ( 1 . b\_{51} b\_{50} ... b\_{0}) \times 2^{e - 1023} $$ where $b$ encodes the mantissa (52 bits) and $e'=e-1023$ encodes the exponent (11 bits). You mention that your typical inputs are at least 1, so your exponent $e'$ is always nonnegative. The mantissa is always an integer multiple of $2^{-52}$, and will be an integer multiple of $2^{-\ell}$ whenever the least significant nonzero bit of the mantissa is the $\ell$-th one.
The bottom line is that to achieve an *exact* representation you could do the following:

* look at the binary representation of your floating point number $x$, isolating the mantissa bit sequence $b$ and the exponent $e'=e-1023$;
* let $\ell$ be the index of the least significant nonzero bit of the mantissa $b$;
* your number $x$ is an integer multiple of $1/D = 2^{e' - \ell}$, *and no fraction with a smaller denominator than $D$ can represent it exactly*;
* divide $x$ by $1/D = 2^{e'-\ell}$ to find $N \times A$.

In the worst case, this may however not guarantee that $N$ and $A$ satisfy your size requirement, since $\ell- e'$ could be up to $52$, while you only have $32 + 16 = 48$ bits available for $N \times A$. A practical solution (but perhaps non-optimal) would be to round the least significant $52-48 = 4$ bits in the mantissa of $x$.

If you insist on finding the best approximation given a constraint on the largest denominator $D$, we need to turn to diophantine approximation techniques and continued fractions.

A fraction $A/B$ is a *best rational approximation* to real number $x$ if $|A - Bx| \le |C - Dx|$ for all integers $C$ and $D$ where $0 \< D \le B$.

Then it is known that the best rational approximation of $x$ is a so-called *convergent* to $x$, which you can recover from the continued fraction expansion of $x$: $$ x = a\_0 + \frac{1}{a\_1 + \frac{1}{a\_2 + \ldots}} $$ The $m$-th convergent $C\_m$ is defined by the fraction $A\_m/B\_m$ where $A\_k$ and $B\_k$ are defined recursively by

$A\_{-1}=1$, $A\_0=a\_0$, $A\_{k} = a\_{k} A\_{k-1} + A\_{k-2}$

$B\_{-1}=0$, $B\_0=1$, $B\_{k} = a\_{k} B\_{k-1} + B\_{k-2}$.

In other words, for each $k=0,1,2,\ldots$:

* generate $a\_k$ by setting $a\_k = \lfloor x\_k \rfloor$, $x\_{k+1} = 1/(x\_k - \lfloor x\_k \rfloor)$, where $x\_0 = x$;
* compute $A\_k$ and $B\_k$ with the formulas above
* the $k$-th convergent is $A\_k/B\_k$.

This will give you a sequence of closer and closer approximations of $x$, each of which is a best rational approximation. In your case, you want to stop when $B\_k$ does not fit anymore into $16$ bits.

In your examples, we get the following:

First example.

$x = 1000 \times 255 / 256 \approx 996.09375$

$A\_0 / B\_0 = 996 / 1 \approx 996.0$

$A\_1 / B\_1 = 9961 / 10 \approx 996.1$

$A\_2 / B\_2 = 10957 / 11 \approx 996.0909090909091$

$A\_3 / B\_3 = 20918 / 21 \approx 996.0952380952381$

$A\_4 / B\_4 = 31875 / 32 \approx 996.09375$

Second example.

$x = 123456 \times 123 / 456 \approx 33300.63157894737$

$A\_0 / B\_0 = 33300 / 1 \approx 33300.0$

$A\_1 / B\_1 = 33301 / 1 \approx 33301.0$

$A\_2 / B\_2 = 66601 / 2 \approx 33300.5$

$A\_3 / B\_3 = 99902 / 3 \approx 33300.666666666664$

$A\_4 / B\_4 = 266405 / 8 \approx 33300.625$

$A\_5 / B\_5 = 632712 / 19 \approx 33300.63157894737$

# Answer
> 1 votes
The "best" rational approximations to a real number are given by it's continuous fraction, check that out.

---
Tags: algorithms, integer-programming, integers, numerical-algorithms, constraint-satisfaction
---


# Question
Title: When are a controller's registers loaded and ready to inform an I/O Operation?
Below, I appended a fragmented paragraph from Operating Systems Concepts on interrupts.

> To start an **I/O operation**, the **device driver** loads the appropriate **registers** in the **device controller**.

> The **device controller**, in turn, examines the contents of these **registers** to determine what action to take (such as “read a character from the keyboard”).

> The **controller** starts the **transfer** of data from the **device** to its **local buffer**.

> Once the transfer of data is complete, the device controller informs the device driver that it has finished its operation.

> The **device driver** then gives control to other parts of the **operating system**, possibly returning the data or a pointer to the data if the operation was a read.

> For other operations, the device driver returns status information such as “write completed successfully” or “device busy”.

> But how does the controller inform the device driver that it has finished its operation? This is accomplished via an **interrupt**.

My question has to do with the first and second sentences. Let's say we have an USB controller for a keyboard. When does the device driver load the controller's registers with the action they are supposed to handle? Does it happen on system startup, and the controller is just waiting to handle the subsequent data input? Or does it happen everytime the user hits a key?

# Answer
> 2 votes
## Summary

On x86-64, an eXtensible Host Controller (xHC) is responsible to interact with USB from the operating-system. The operating-system writes at conventional positions in RAM to read and write the registers of the xHC. What these registers do is explained in the xHCI specification. The keyboard is polled by the xHC at a certain interval using the Periodic Transfer Ring. When a transfer occurs, the xHC triggers an interrupt. The operating-system will then look in RAM for any change. If any change is detected, the operating-system puts a message on the message queue of the application which currently has focus.

## Long answer

I don't know much about ARM and how it interfaces to USB. I've been in the process of writing an x86-64 kernel which interacts with USB keyboards so I'll answer for x86-64. By the way, x86-64 is the CPU architecture you find in most desktop computers today.

x86 CPUs can't interact with USB directly. They need a PCI compliant device of which some registers are mapped into main memory (RAM). This PCI device is called today the eXtensible Host Controller (xHC). There once was other names but they were all provided as a way for x86 CPUs to interact with USB. The xHCI specification describes the functioning of the xHC (see https://www.intel.com/content/dam/www/public/us/en/documents/technical-specifications/extensible-host-controler-interface-usb-xhci.pdf).

When the computer boots, there is some firmware on the motherboard which probably questions the different PCI devices for the position of their memory mapped registers (I don't have more information on how). It then informs the operating-system (OS) of where these registers will land using the ACPI tables which is a conventional representation of hardware. The position of these tables is stated in the ACPI convention.

When the computer boots, firmware hands over control to the OS. The OS will look at the ACPI tables to find the base address of the PCI configuration space for the computer. Most often it will be always the same address. It doesn't even need to be actual physical memory. It can be anywhere even outside memory. On QEMU virtual machines (with 128MB of memory by default), the PCI config space is often found above the actual physical memory.

The PCI config space is then scanned with a conventional approach to device addressing. Basically, each function of each device gets a config space. There can be several buses onto which can be up to 32 devices onto which can be up to 8 functions (see https://wiki.osdev.org/PCI). To find the base address of one function you need to use a basic arithmetic formula specified in the PCI convention as such:

```
UINT64 configSpacePhysAddr = pciConfigBaseAddr + ((bus - first_bus) << 20 | device << 15 | function << 12);

```

The value pciConfigBaseAddr is often 0x80000000. It cannot be relied on so it must be retrieved in the MCFG ACPI table which is located using other tables. The first table of the ACPI table chain is the RSDP table (see https://wiki.osdev.org/RSDP). The RSDP table has a conventional location and it allows to find all the other tables.

The function is specific to one protocol. For example, on a PCI compliant device which is an WIFI card and a Bluetooth card at the same time, you'll find 2 functions. Each function does more or less a specific thing (a specific protocol). Another example is the xHC from Intel. The xHC will be a device with only one function (to interface with USB).

Every PCI function gets several IDs which allow to identify the device and what it does (or to load a proper driver for it).

The xHC will present a complex interface to software with memory mapped registers. The OS will write to these registers to set up the xHC. The xHC is compatible with MSI-X. MSI-X is a new mechanism which allows to get interrupts directly bypassing the IOAPIC of x86 computers. The interrupt acts similarly to an inter-processor interrupt (also used to bootstrap other processors from core 0 or to control other cores in general).

The xHC has event rings, transfer rings and one command ring. All rings lie in RAM. The event rings are used by the xHC to tell software something happened. Most events will be accompanied with an interrupt. The vector that will be triggered is chosen by the OS using the MSI-X table. There can be up to 2048 different interrupt vectors when using the MSI-X capability of the xHC. The transfer rings are used by software to transfer data to or from USB devices. The command ring is used by software to send commands to the xHC. The transfer ring is the only ring which allows to transfer data to or from USB devices. Every xHC has several doorbell registers which are tied to one USB device. The doorbell registers are used to "ring the bell" to tell the xHC it has pending operations on a certain transfer ring for that specific USB device. Each ring is made of Tranfer Request Blocks (TRBs) which have several formats. For the event rings there are the Event TRBs. For the transfer rings there are the Transfer TRBs. For the command ring there are the Command TRBs. The TRB informs either software or the xHC (depending on the ring) of what happened or what to do.

There can be several event rings or, sometimes, only one. It depends on the implementation (read the xHCI specification for more information). There is one transfer ring for each endpoint of each device. Each USB device has several endpoints. To communicate with these endpoints, the OS places Transfer TRBs on the transfer ring of that endpoint and writes a certain number to the doorbell register of the associated device. That number is the number of the endpoint. This is sometimes termed "ringing the bell" to the xHC.

There exists a periodic transfer ring. The periodic transfer ring is a transfer ring which allows to "program" a Transfer TRB to be executed every time an interval in milliseconds has passed. Since USB is a polled bus, USB devices never initiate any transfer. You are thus left to do some polling of the keyboard (or let the xHC do it using the periodic transfer ring). When a transfer occurs, the xHC will trigger an interrupt on the vector you specified and place a Transfer Event TRB on the event ring. The OS will thus look at the event ring for the USB endpoint for which a transfer has occurred and look at the data. For a keyboard, if the data has changed from the last poll, it means that a key was released or pressed. The OS will thus read the change and send a message to the application which has focus. The transfer will be done to a specific address which is going to be specified in the Transfer TRB placed on the transfer ring of that specific device. The software will thus read that address for the data and will act accordingly.

For a keyboard, the periodic transfer ring is quite useful. The keyboard will be polled and software will probably just put a message on the message queue of the application which currently has focus stating that a key was pressed along with the key. It is up to applications to do something depending on the key.

# Answer
> 0 votes
Every time that the computer wants to interact with the peripheral device. "every time the user presses a key" sounds about right, but I don't know enough about keyboards specifically to vouch that this is exactly how it works.

---
Tags: operating-systems
---


title: How to check $L$ is regular or not

text:
# Question
Title: How to check $L$ is regular or not
If $L=\\{w \in \Sigma^\*\mid w=uv,\text{ number of occurnce a's in $u$ equal to number of occurrence b's in $v$}\\}.$

I think $L=\Sigma^\*$ because for any string in $\Sigma^\*$, we can split it to $uv$ such that it contain equal number of a's and b's. But I can't prove it or maybe that language isn't regular. Any help for prove that is a regular language or not are welcome.

# Answer
Indeed $L = \Sigma^\ast$. Here is a proof.

Clearly, $L \subseteq \Sigma^\ast$, so it suffices to show $\Sigma^\ast \subseteq L$. Let $w \in \Sigma^\ast$. We start with an arbitrary decomposition $w = uv$. If $|u|\_a = |v|\_b$ we are done. Otherwise, wlog let $|u|\_a \< |v|\_b$. Then by moving the cutpoint one step to the right, i.e. considering the decomposition $uv\_1, v\_2 \ldots v\_m$, we increase either the number of $a$s in $u$ (if $v\_1 = a$) or decrease the number of $b$s in $v$ (if $v\_1 = b$), so the absolute value of the difference $||v|\_b - |u|\_a|$ is reduced by $1$ after such a step. Since this difference is bounded from below by $0$ the procedure terminates after finitely many steps.

(If $\Sigma$ contains more symbols than $a, b$ the argument works the same way but the difference might stay the same in some steps.)
> 2 votes

---
Tags: regular-languages, automata
---


# Question
Title: What is the best book on the theory of programing languages?
I want to learn programming.

I have knowledge of mathematical logic.

So, what I am searching is a book (or varios books) for learning to programming, but I think that a book like one which I imagine would be great. As I said, I have knowledge of mathematical logic, hence I have experience with formal languages.

So, I am searching a book where the theory of programing is developed, not a specific language, the theory of programing in a language in general, something like the foundations of programing or the theory of programing languages.

# Answer
> 2 votes
I don't know of a single book that covers what you want, but if you are genuinely new to programming but have a mathematical background, I think your first port of call should be:

SICP is out of print, but free online. This, I think, will teach you the basics of what you want to know in the way you want to learn it.

There are a lot of good books in the canon. I'm thinking of:

* Stepanov & McJones, *Elements of Programming*.
* Wirth, *Algorithms + Data Structures = Programs*.
* Dahl, Dijkstra, & Hoare, *Structured Programming*.

And there are plenty more that go deeper into the theoretical side of programming languages, but they are probably more useful to those designing programming languages or compilers.

Regardless, all of these books assume that you know the basics first. So I would recommend working your way through SICP.

# Answer
> 0 votes
I recommend Conceptual Programming with Python because it was written by mathematicians and it will get you started on a number of topics quickly.

---
Tags: programming-languages, books, meta-programming
---


# Question
Title: $\log n$ lower bound for space complexity
I am currently reading Arora and Barak's *Computational complexity*. In Chapter 4 (Space complexity), they say the following:

> Since the TM's work tapes are separated from its input tape, it makes sense to consider space-bounded machines that use space less than the input length, namely, $S(n) \< n$. This is in contrast to time-bounded computation, where $\mathbf{DTIME}(T(n))$ for $T(n) \< n$ does not make much sense since the TM does not have enough time to read the entire input. We will require however than $S(n) \> \log n$ **since the work tape has length $n$** \[my highlight\], and we would like the machine to at least be able to "remember" the index of the cell of the input tape that it is currently reading.

I doubt that the highlighted statement is true. As you can see, it says that to be able to remember the indexes of input tape, so

> “Since the work tape has length $n$

could not be true and it should be

> “Since the *input tape* has length $n$

If this is not a typo, I am confused why it mentions that the work tape has length of $n$, as we know that it may have smaller length.

# Answer
> 3 votes
Congratulations! You have found a typo in Arora and Barak's long textbook. There are likely many more.

Arora and Barak are not completely correct that the regime $S(n) \leq \log n$ is not interesting. In fact, what we do know is that the regime $S(n) = o(\log\log n)$ is not interesting, since Turing machines using that much space can only accept regular languages, and so can be modified to use no space at all. See for example this question.

The bound $\log\log n$ is tight here, in the sense that there is a non-regular language which can be accepted in space $O(\log \log n)$, namely the language consisting of all words of the form $$ 0\\#1\\#10\\#11\\#100\\#\cdots\\#\mathrm{bin}(m), $$ where $\mathrm{bin}(m)$ is the binary representation of $m$, which has length $O(\log m)$. This language can be accepted in space $O(\log\log m)$ (we only need to index words of length $O(\log m)$), whereas the input length is $\Omega(m)$. This example is taken from Michel's survey of space complexity, where it is attributed to Wagner and Wechsung, *Computational complexity*.

---
Tags: complexity-theory, space-complexity, lower-bounds
---


title: Is there a $L$-complete variant of SAT?

text:
# Question
Title: Is there a $L$-complete variant of SAT?
Many complete problem of different class of complexity has SAT variant. Like 3-SAT or $k$-SAT is $NP$-complete, Horn-SAT is $P$-complete, 2-SAT is $NL$-complete, and so on. So I was wondering if there is a $L$-complete variant of SAT?

# Answer
> 5 votes
The standard example is the variant of SAT in which each clause has the form $x$ or $y \oplus z$ (not allowing negations). For more examples, check Allender, Bauland, Immerman, Schnoor and Vollmer, The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem.

---
Tags: complexity-theory, satisfiability, propositional-logic
---


# Question
Title: Is $(L_1^c \cup L_2^c)^c$ context-free or context-sensitive
I came across the following question:

> Let $L\_1$ be a regular language and $L\_2$ be a context-free language. Let $L\_1^c$ and $L\_2^c$ be their complements respectively. What can be said about $(L\_1^c \cup L\_2^c)^c$? Is it context-free?

I tried to solve it in two different ways:

1. $L\_1^c$ is also regular because regular languages are closed under complementation, but $L\_2^c$ is not context-free because context-free languages are not closed under complementation, so, it is context-sensitive (it may also be context-free, but not definitely). Also the union of a regular language and a context-sensitive language is context-sensitive. So, $(L\_1^c \cup L\_2^c)^c$ is context-sensitive.
2. Applying DeMorgan's Law, $(L\_1^c \cup L\_2^c)^c$ becomes $L\_1 \cap L\_2$, which is clearly context-free.

Why is the discrepancy there between the two methods? What mistake am I making in the first approach (because the answer is "context-free")?

# Answer
There is no discrepancy in the two methods. The first method shows that $L := \overline{\overline{L\_1} \cup \overline{L\_2}}$ is context-sensitive. The second method shows the *stronger* result that $L$ is context-free. Both of these are consistent. Compare the following: $$ 1 + 1 \leq 1 + 2 = 3 \Longrightarrow 1 \leq 3 \\ 1 + 1 \leq 2 $$ The first inequality shows that $x := 1 + 1$ satisfies $x \leq 3$. The second inequality is stronger, showing that $x \leq 2$. There is no discrepancy here. The second inequality is simply better.

The term *context-sensitive* is somewhat of a misnomer. Being context-sensitive doesn't preclude being context-free. In particular, every context-free language is also context-sensitive.

---

Here is how to cut the slack in your first argument:

1. Since $L\_1$ is regular, $L\_1^c$ is regular.
2. Since $L\_2$ is context-free, $L\_2^c$ is co-context-free (a language is co-context-free if its complement is context-free).
3. Since $L\_1^c$ is regular and $L\_2^c$ is co-context-free, so is $L\_1^c \cup L\_2^c$.
4. Hence $(L\_1^c \cup L\_2^c)^c$ is context-free.

In this case we were lucky to find classes of languages which tightly describe all intermediate steps. Sometimes we are not as lucky, and we need to find a different of proving that a certain language, constructed in a certain way, belongs to a certain language class.
> 1 votes

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


# Question
Title: Is $\log^{*}(\log(n)) = \Theta (\log(\log^{*}(n)))$?
Which one is asymptotically larger? $\log^\*(\log(n))$ or $\log(\log^\*(n))$? I think they are asymptotically tight bounds for each other (one is $\Theta$ of the other).

# Answer
> 4 votes
Suppose that $\log^\* n = k$. This means it takes $k$ many $\log$'s to reduce $n$ below some constant. Therefore $\log^\* \log n = k-1$ (assuming $k$ is not too small), whereas $\log \log^\* n = \log k$.

# Answer
> 2 votes
Suppose $f\_1(n)=\log \log^{\*}(n)$, and $f\_{2}(n)=\log^{\*} \log(n)$.

Let $n=2^m$ then According the definition of iterated function:

> $\log^\* n$ (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

So $$f\_1(2^m)=\log \log^\*(2^m)=\log \log^\*\log(2^m)+1=\log\log^\*m+1=\theta(\log\log^\*m)$$

and $$f\_2(2^m)=\log^\*\log(2^m)=\log^\*(m)+1=\theta(\log^\*m)$$ Finally, for sufficient large $n$ (i.e. as $n\to \infty$) we conclude that: $$f\_1(2^m)=O(f\_2(2^m)).$$ Because let $\log^\*(m)=k$ then: $$f\_1(2^m)=\log k$$ and $$f\_2(2^m)=k.$$ Obviously order of growth two mentioned function follow below relation $$f\_1(2^m)=O(f\_2(2^m)).$$

---
Tags: asymptotics
---


title: Can a TM decide the binary PCP-Problem？

text:
# Question
Title: Can a TM decide the binary PCP-Problem？
I am having a little bit of a hard time distinguish between a TM which accepts a language, and a $TM$ that decides a language. To be more precise:

$L\_1 = \\{\langle M\rangle\\; | \\; M$ accepts the 10-PCP $\\}$ and $L\_2 = \\{ \langle M\rangle \\; | \\; M$ decides the 10-PCP $\\}$

I guess $L\_1$ is undecdiable, since I could potentially apply Rice's Thoerem Moreover, we know that the Problem that $M$ accepts $w$ is undecidable anyway. However, I am uncertain about $L\_2$. For me, it seems intuitive to think that we could build a TM which rejects, if the input is a $01$-PCP Problem. Thus, the TM can decide it. But that seems a little bit too easy and I guess I am on the wrong trail.

# Answer
The binary PCP is decidable. Let $T^\*$ be a Turing machine that decides the language $L\_{PCP}$ of all yes-instances to binary PCP.

We can use this fact to show that both $L\_1$ an $L\_2$ using a reduction from the halting problem.

Suppose towards a contradiction that there is a Turing machine $T$ that decides $L\_1$ (resp. $L\_2$). Given a Turing machine $M'$ we can define a new Turing machine $M$ that, on input $x$, simulates $M'$ on empty input and then (when/if $M'$ halts) simulates $T^\*$ with input $x$. If/when $T^\*$ accepts $M$ also accepts. If/when $T^\*$ rejects $M$ also rejects.

Now, $M^\*$ accepts (resp. decides) $L\_{PCP}$ if and only if $M'$ halts on empty input. In other words $M^\*$ belongs to $L\_1$ (resp. $L\_2$) if and only if $M'$ halts on empty input.

We can then use $T$ with input $M^\*$ to decide whether $M'$ halts. This is a contradiction and hence no Turing machine $T$ exists.
> 1 votes

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


# Question
Title: Substitution Method to Solve Recurrences
One approach to solve recurrences is the so called substitution method.

While practicing I encountered some recurrences, where non integer arguments can occur, e.g. T(n) = 2\*T(n/2) + n, if n is not a power of 2.

My understanding of the substitution method, is that it only works, if all arguments are integers. Is this correct? Is is it reasonable to apply the substitution method to lower and upper bounds instead, e.g. T(n) ≤ T1(n), where T1(n) = 2\*T1(ceil(n/2)) + n, in order to draw conclusions regarding T?

Thanks in advance!

# Answer
> 1 votes
Usually when we write $n/2$ we actually mean $\lceil n/2 \rceil$ or $\lfloor n/2 \rfloor$.

In terms of big-O notation, usually they are equivalent (unless you are in some extreme case like $2^{2^x}$ where subtructing or adding $1$ to $x$ could make a significant increase or decrease).

So you can just treat it like a whole number.

---
Tags: induction
---


# Question
Title: Is the maximum degree in a simple connected graph =$o(|E|)$?
I am trying to prove something, and it will help e greatly to show that the maximum degree of any vertex, $d$ is a connected simple graph, goes up asymptotically linearly along with the number of edges in the graph.

I came up with a somewhat hand-wavey "proof", and I wonder if it is anywhere near correct:

> For fixed $|V|=n$, as $m$ grows, so does $d$, linearly, with constant average $\frac{1}{n}$, as by the pigeonhole principle, for every addition of n edges, the maximum degree has to increase by at least 1.

---

The other direction is easily $m \le \frac{dn}{2}$.

---

I wonder if this is at all correct, and if so, how to improve the proof

# Answer
The idea is correct. Indeed, if $d$ is the maximal degree in the graph, $n$ is the number of nodes and $m$ is the number of edges, we can give the following bounds on $d$: Define $d\_v$ to be the degree of $v$, for any node $v\in V$.

1. $d\le \min\\{m,n\\}$
2. $\lfloor\frac{2m}{n}\rfloor \le d$

The first bound is given by the fact that $d$ has at most $\min \\{m,n\\}$ edges. This is the correct way to bound $d$ *from above*, and in fact is the tightest bound we can give.

The second bound is actually the bound you proved (which is the interesting bound), using the pigeonhole principle. The "correct" way to use the pigeonhole principle is to use its extended version. Say there are $m$ edges, then the sum of the degrees is $2m$. We distribute them into $n$ nodes, to get that at least one node has to have degree at least $\lfloor\frac{2m}{n}\rfloor$. The maximal degree has to be at least as big, hence $d\ge \lfloor \frac{2m}{n}\rfloor$.
> 1 votes

---
Tags: graphs
---


title: How Tarjan algorithm work for the 2-SAT

text:
# Question
Title: How Tarjan algorithm work for the 2-SAT
Tarjan's algorithm for 2-SAT is based on the truth:

> a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.

But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

I tried to follow the steps of the algorithm, and I was stuck here:

> For each component in the reverse topological order, if its variables do not already have truth assignments, set all the literals in the component to be true. This also causes all of the literals in the complementary component to be set to false.

Isn't it possible the variable is already assigned WRONGLY? When we keep assigning TRUE from the back, and we assign the FALSE in the middle, but the TRUE is to be assigned to the next variable. In this case, the feasibility breaks.

Of course this kind of case never happens because the algorithm is right and many people use this algorithm well. But so many post says it as the trivial things.

* I think the reason why those assignment is possible is relevant to the skew-symmetric condition of the graph, since (x -\> ~x -\> y -\> ~y) never has true assignments.

# Answer
> *a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation.*
>
> But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF?

Think of a variable assignment for some unsatisfiable 2-SAT instance. This means one or more clauses must remain unsatisfied whatever the assignment. You change the setting of one or more variables to satisfy those clauses, but this unavoidably leaves some new clause or clauses unsatisfied because the instance is unsatisfiable. The failure of your change to satisfy the instance implies that some other variable's value must change. You repeat the procedure again and again, changing other variables as implication demands, but never succeed in satisfying all the clauses. Eventually, because the number of variables is finite, a failure implies that you change the value of a variable you've already visited... and that is your circular implication from $x$ to $\bar{x}$ back to $x$. Without a circular implication you will eventually reach the end of the implication chain and have a satisfying assignment. The only way not to reach the end of the chain is for the chain to be circular between a variable and its negation.
> 2 votes

# Answer
i need to see Tarjan original prrof because i also have a question regarding the algorithm,, so who can provide a link to some original paper or some will be higly appreciatef ... now, my question, it is known / provable that all variables in a strong component must have the same boolean value TRUE or FALSE. That is because you can reach from any variable of one strong component to any other variable in the same strong component, so if you have x and y in the same strong component you will have x-\>y and y-\>x and suposing either (x=FALSE and y=TRUE) or (x=TRUE and y=FALSE) will be a contradiction because TRUE-\>FALSE is a contradiction ... so the question you rise here still stands. suppose you set a variable x=TRUE in strong component S3 which implies setting variable ~x in strong component S2 to FALSE and in S2 there exists an variable y not assigned (that CAN happen because ~y is in strong component S1 an is not yet set) When you assign variables in S2 you will set y=TRUE which will lead to a contradiction because ~x=FALSE....

... and, now, i'll answer to " your right to left" question a variable x in a strong component Si can reach a variable y in a strong component Sj if i \<j (but you cannot reach from any varible from Sj in one variable in Si i \< j ) so you assign in first place y=TRUE beforec you set x. when you reach to set x either to TRUE or FALSE you will have either TRUE -\> TRUE or FALSE -\> TRUE which is no contradiction
> 0 votes

---
Tags: algorithms, graphs, 2-sat
---


title: Pointers and Dereference Operator

text:
# Question
Title: Pointers and Dereference Operator
\*a = \*b In C, the above expression is always interpreted as the assignment of the value at the address contained in b to the value at an address in a. But, according to the precedence of operators and associativity rule, * has higher priority than the assignment operator '=', and is associative from right to left. If we interpret the given expression keeping in mind these rules, it should be interpreted as:

> \*a=\*b
>
> (\*a)=(\*b)
>
> 10=20(Supposing \*a=10 & \*b=20)

So, this must result in an error if taken as per the rules of precedence and also as per the rule that there can't be an expression on the left-hand side of an assignment operator. Then why does this work?

# Answer
I'm not sure if this is in topic here.

Anyway, `(*a)` in `(*a)=(*b)` denotes a lvalue referring to the object in `a`. On the right side of the assignment, `(*b)` also denotes an lvalue, but this lvalue undergoes lvalue conversion and is converted to the actual value stored in the object pointed by $b$ (i.e., to 20).

In the end, the value 20 is assigned to the object pointed by `a`.

See, for example, this discussion about lvalues and rvalues.
> 4 votes

---
Tags: c
---


# Question
Title: Does MIP* = RE's major breakthrough mean quantum computers are more powerful than turing machines?
Henry Yuen's youtube comment on this video https://www.youtube.com/watch?v=HL7DEkXV\_60 (should be one of the top comments) explains that with the help of quantum entanglement (or quantum computers), it is possible to solve a problem that has been proven to be unsolvable by a turing machine.

**Does that mean quantum computers are effectively hypercomputers more powerful than turing machines?**

If indeed we found out that they are, would that mean that we, humans, were able to find a way to surpass the Turing barrier, meaning the human mind is more powerful than a turing machine, making us effectively hypercomputers?

# Answer
> 6 votes
To summarize: No, this paper does not provide an example of something a quantum computer can compute that a Turing computer can't.

I believe you have misunderstood Henry's comment. The problem in question isn't the halting problem (given any Turing machine and input, will it halt). Rather, the problem is to prove that a program halts, given that it halts. As Henry describes, there is a simple means of solving this problem that Turing computers are capable of-They can list out the steps leading to the program's halting.

What the quantum computer can do that the Turing computer can't is the following. Given a Turing computer and input that halts, once the quantum computer knows that the process halts (which can take arbitrarily long to determine by itself), it can provide proof that the process halts in constant time.

Key points: This problem has no relevance to solving the halting problem, because the quantum computer needs to know that the process halts to proceed. Turing computers can also solve this problem, but the time to provide an answer can be arbitrarily long for given inputs.

To your bonus question about humans surpassing Turing computers if we solve a problem they can’t: In theory, the answer is yes, but it is quite hard to do so. To prove that a computer (Turing or human) can solve a problem, you must prove that they can solve it for all inputs. Our current rules of mathematics are describable by a Turing computer, so we would need to provide this proof with something that transcends current mathematics. Additionally, solving the problem for some inputs is not proof we can solve it for all inputs.

Secondly, a very substantial implication of the answer being yes would be that either: Turing computers cannot simulate the laws of physics, or the laws of physics do not fully describe the function of the human brain. As it currently stands, it seems that both of those aren't true - physics fully explains the human brain, and a quantum computer can simulate the laws of physics. (It is 100% true that a quantum computer can simulate our current laws of physics, while it is likely that it can simulate whatever the true laws of physics are).

---
Tags: complexity-theory, computability
---


# Question
Title: Hoare partition scheme may cause infinite recursion
Wiki states: "...partitioning algorithm guarantees lo ≤ p \< hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion."

What prevents Hoare partition from not returning j equal to hi? If our pivot is max number, we may execute j \<- j – 1 only once and exit with j=hi

```
E.g. A= [2,0]

```

Some implementations add a final swap of placing the initially chosen pivot into returned j:

```
swap A[lo] with A[j]
return j

```

What would guarantee p \< hi?

Full pseudo-code from wiki:

```
algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1 <------------- execute once
        while A[j] > pivot

        if i >= j then
            return j <------------- exit

        swap A[i] with A[j]

```

# Answer
Did you notice the outer loop, `loop forever`?

---

Let us say in the first iteration of that `loop forever` loop, we have just finished the second inner loop, `do j := j - 1 while A[j] > pivot`.

* If `j := j-1` has been executed at least twice, then `j <= (hi+1)-2 = hi-1`.
* Otherwise `j := j-1` has been executed exactly once. Then
$\quad\quad$`j = (hi+1)-1 = hi`.
Note that the first inner loop, `do i := i + 1 while A[i] < pivot` produces
$\quad\quad$ `i = lo`
since `i = lo - 1` initially and `A[lo] = pivot`.

Now we execute `if i >= j then return j`. Since the condition `i >= j` does not hold as `lo < hi` (the pseudocode for quicksort specifies that only when `lo < hi` shall partition be performed), the code `return j` will be skipped, i.e., we shall go on with the next iteration of that `loop forever` loop. In that next iteration, `j := j-1` will be executed again, causing `j < hi`.

So, we will always have `j < hi` at some point of time during the partition. Since `j` would never increase, we will have `j < hi` when we `return j`. $\quad\checkmark$

---

The analysis above holds regardless of whether our pivot is the max number or not.
> 1 votes

---
Tags: sorting, quicksort
---


# Question
Title: Given x find a polynomial such that pol(x)=a for a known a?
You are given x,a. Find a polynomial p(y) with the leading coafficent 1 such that p(x)=a. How to write an algorithem to solve this efficently? I have no idea where to start

# Answer
> 4 votes
Choose $$p(y):=y + (a-x)$$

$x$ and $a$ here are the constants you are given.

---
Tags: algorithms, polynomials
---


# Question
Title: Children of internal node in a quadtree with high dimensionality
Let's say for example we have 1000 points and 50 dimensions.

And we build a quadtree where each node represents a 50-dimensional box and is divided by splitting the box into smaller boxes that are half the size in every dimension? How would i calculate how many children each internal node has?

# Answer
> 2 votes
If you split along each dimension into two parts, then in two dimensions you have $2\cdot 2 = 4$ children (that's why it's called a **quad**tree), in three dimensions you have $2\cdot 2\cdot 2 = 8$ children (that's why three-dimensional quadtrees are called **oct**trees), and for $k$ dimensions you have $2^k$ children.

That's independent of the numbers of points in your tree - each internal node in a quadtree splits in the same way.

And for higher dimensions that's a lot of children, and therefore you don't want to use a quadtree in that case, but something else, for example a k-d tree.

---
Tags: trees, clustering
---


# Question
Title: Solution to a recurrence changing by a constant factor
We know that a recurrence relation without initial condition(s) might specify more than one solution (if it has any), but if we set some initial condition(s) the solution becomes unique. Now The book CLRS claims for a recurrence like this: $ T(n) = 2T(\lfloor n / 2\rfloor) + n$ or other divide-and-conquer-related recurrences, if we change the initial conditions the solution changes by a constant factor. What is the proof of this? And it's only true for these types of recurrences(divide\_and\_conquer\_related)? Right?

# Answer
Let $T,S$ defined using the same recurrence, but using two different initial conditions: $T(1) = 1$ and $S(1) = 2$. A simple induction shows that $T(n) \leq S(n)$.

On the other hand, consider the recurrence $R(n) = 2R(\lfloor n/2 \rfloor) + n/2$, with initial condition $R(1) = 1$. A simple induction shows that $R(n) = S(n)/2$ and that $R(n) \leq T(n)$, and so $S(n) = 2R(n) \leq 2T(n)$.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Finding the maximum sum series in time complexity of O(n)
You are given a list of prices (non-negative integers) $$ P=\<P\_1, P\_2, ..., P\_n\> $$, where the prices $P\_i$ appear in non-decreasing order. Moreover, you have access to an oracle that can be queried with an integer $a$ and returns "yes" if and only if $a \le k$ for some **unknown** integer $k$. Each query to the oracle requires constant time.

The goal is that of finding a subset $S$ of $\\{1, \dots,n\\}$ such that the quantity $\sigma(S) = \sum\_{i \in S} P\_i$ is at most $k$ and $\sigma(S)$ is maximized.

Is there a way to solve this problem in $O(n)$ time?

For example, if $$ P=\<P\_1=3, P\_2=5, P\_3=10\> $$ and the unknown integer $k$ is $16$, the best choice of $S$ is $\\{2,3\\}$ and $\sigma(S) = 15$.

# Answer
There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.

Suppose that such an algorithm $A$ exists. Then we can use $A$ to solve the subset-sum problem (which is known to be $\mathsf{NP}$-complete) in polynomial time. Let $\langle X, t\rangle$ be an instance of subset-sum where $X = \langle X\_1, \dots, X\_n\rangle$ is a collection of integers and $t$ is the target integer.

We pick $P=X$ and $k=t$ and implement the oracle that decides whether $a \le k$ in the straightforward way. Then we simulate $A$ on input $P$ using the above oracle to compute $\sigma(S)$ in polynomial time.

If there exists a subset of $X$ of total sum $t$, then clearly the returned set $S$ is such that $\sigma(S)=t$. If there is no such subset of $X$, then all choices of $S' \subseteq \\{1, \dots, n\\}$ are such that $\sigma(S')$ is either strictly smaller or strictly larger than $t$. This shows that the returned set $S$ satisfies $\sigma(S) \< t$.

We then answer "yes" to the subset sum instance if and only if $\sigma(S) = t$.
> 4 votes

---
Tags: algorithms, time-series-analysis
---


# Question
Title: disadvantages of a long time quantum in scheduling
I'm trying to understand the example showing disadvantages of a long time quantum in Tanenbaum's book in Section 2.4.3 “Scheduling in Interactive Systems”.

> To improve the CPU efficiency, we could set the quantum to, say, 100 msec. Now the wasted time is only 1%. But consider what happens on a server system if 50 requests come in within a very short time interval and with widely varying CPU requirements. Fifty processes will be put on the list of runnable processes. If the CPU is idle, the first one will start immediately, the second one may not start until 100 msec later, and so on. The unlucky last one may have to wait 5 sec before get- ting a chance, assuming all the others use their full quanta. Most users will perceive a 5-sec response to a short command as sluggish. This situation is especially bad if some of the requests near the end of the queue required only a few milliseconds of CPU time. With a short quantum they would have gotten better service.

I suppose request execution times are not known, so the order of execution of requests is chosen randomly with uniform distribution. I calculated the mean request completion times for 2 requests having execution times 1 and 2:

* infinitely small time quantum: 2.5
* infinitely large time quantum: 2.25

For the infinitely small time quantum, the 1-request completes in 2 time units since both requests are processed in parallel, then the 2-request completes in 3 time units. For the infinitely large time quantum, we have two equiprobable situations:

* the order is \[1-request, 2-request\], and the 1-request completes in 1 time units, then the 2-request completes in 3 time units
* the order is \[2-request, 1-request\], and the 2-request completes in 2 time units, then the 1-request completes in 3 time units

The mean request completion times for 3 requests having execution times 1, 2, and 3:

* infinitely small time quantum: 4.666666666666667
* infinitely large time quantum: 4

Where is the disadvantage of the infinitely large time quantum?

# Answer
> 2 votes
Try to think in practical terms what would actually happen if your computer used a big quantum:

Lets say our quantum is 1 second. Now, say you browse in a browser (for example, CS stack exchange), and want to ask a question in the CS stack exchange. Lets say, that you also got from your instructors some really annoying homework that made you need to run 20 programs at the same time, for a really long time (a few hours). While the programs run, you want to ask that question in the CS SE (because you really really need to know the answer of course). But all 20 programs use up all their quanta (and don't stop mid-quantum), so the probability that the browser gets to work every second is $\frac{1}{20}$. So, with an expected wait of $20$ seconds, the browser will be able to do work for only one second. You see the problem here? You will have to wait 20 seconds on average each time before you see anything happening in the browser: clicking a button, writing text, etc...

So the disadvantage comes from a user-experience perspective, rather than from a "total process time" perspective. Of course, if the only usage of the computer is to run 2-3 programs that only compute values (like what supercomputers do), and do not have any user interacting with them, then there is no need for such a short quantum.

# Answer
> 1 votes
I agree with you that Tanenbaum kind of biffed it here. *Arguably* if your goal was to minimize *worst case* wait time for the short jobs at the end of the queue, Tanenbaum's example would sort-of make sense. If there are 49 long jobs and 1 1msec job, the worst case wait time for the 1ms job with 100ms time slices would be 4901ms, while the worst case wait time with 1ms time slices would be 50ms.

I probably have an older edition of Tanenbaum than you (I have *Modern Operating Systems, 2/e*, 2001), and I think what he was trying to do in this section was motivate the need for *multi-level priority feedback* scheduling. This is essentially the scheduling algorithm used by CTSS in 1962. Variants of it were used in UNIX (for example as described in Bach's *Design of the UNIX Operating System*, 1986) and are used in Linux (for example as described in Bovet and Cesati's *Understanding the Linux Kernel*).

The goal of multi-level priority feedback is to try to simultaneously balance the *fairness* of round robin, with the *latency minimization* of shortest-job first (which requires you to have some way of *predicting* job lengths even though you don't really know the "true" job lengths), while maximizing the utilization of your physical disk by keeping the disk request queue as full as possible, and finally to minimize the overhead of context switching.

For the latency minimization subgoal, Bovet and Cesati specifically mention a threshold of annoyance for interactive users is somewhere between 50ms and 150ms.

The problem is that there's no formal definition of "interactive" jobs versus "batch" jobs, the operating system doesn't know which are which in any case, and we're trying to heuristically balance a bunch of mutually inconsistent goals, so there's no well-defined optimization problem to solve here. In practice multi-level priority feedback scheduling is a heuristic that qualitatively does a pretty good job.

---
Tags: operating-systems, scheduling
---


# Question
Title: Minimal number of intervals that covers $\{1,...,k\}$
Let $F$ be a family of sets of consecutive integers in $\\{1,…,k\\}$ that is closed under taking subintervals, i.e. for any $a≤b≤c≤d$, if $\\{a,…,d\\} \in F$, then $\\{b,…,c\\} \in F$ also. Find a minimum number of intervals in $F$ that covers $\\{1,…,k\\}$.

Is this a known problem? after some trial and error I do have the feeling that greedy solution (picking the longest interval each time) will work here, but will appreciate a proof for that as I do now know how to approach such.

Thanks

# Answer
Picking the longest interval is not optimal. Consider for example $k=6$, and the (closure obtained by taking subintervals of the) intervals $\[1,3\], \[4,6\], \[2, 5\]$. The longest-interval-first greedy solution will select $3$ intervals, while an optimal solution requires only $2$ intervals.

However the following algorithm is optimal: let $x$ be the smallest uncovered integer. Pick an interval $I=\[z, y\]$ such that $z \le x \le y$ and $y$ is maximized, add $I$ to your solution and repeat until $\\{1, \dots, k\\}$ is covered or no $I$ exists (in this case the instance admits no solution).

Feasibility is trivial. You can prove optimality using an exchange argument. Consider an optimal solution $O$ and let $G$ be the above greedy solution. We can assume that $|G \setminus O| \> 0$ otherwise we would have $G \subseteq O$, which immediately implies $G=O$. For each interval $\bar{I}$ of $G$ let $z\_\bar{I}$ be the integer $z$ that the greedy algorithm was trying to cover when it selected $\bar{I}$. Among all intervals in $G \setminus O$ pick the interval $I$ that minimizes $z\_I$. Since $O$ is a feasible solution, there must be some interval $I'$ in $O$ that covers $z$. By the choice of $I$, $O \setminus \\{I'\\}$ already covers all integers in $1, \dots, k-1$ (otherwise there is an interval $I''$ in $G \setminus O$ such that $z\_{I''} \< z\_I$). Moreover, by the greedy choice of the algorithm, we know that $I$ ends no earlier than $I'$. Therefore $O' = (O \setminus \\{ I' \\}) \cup \\{ I \\}$ covers everything that $O$ covers, i.e., it is still a feasible solution. Moreover $|O'| = |O|$, hence $O'$ is actually an optimal solution.

Since $|G \setminus O'| \< |G \setminus O|$ (i.e., $G$ and $O'$ share more intervals than $G$ and $O$) we either have $O' = G$ (and we are done) or we can repeat the above argument until we deduce the existence of an optimal solution that matches $G$.
> 1 votes

---
Tags: algorithms, greedy-algorithms, intervals
---


# Question
Title: why are WAW and WAR hazards not possible in mips architecture
i have read about data hazards and then came across that mips architecture doesn't allow WAR AND WAW hazards can someone please help me understand it? the reason is not given in the book the MIPS pipeline is divided into :

1.IF(instruction fetch) 2.ID(decode the instruction) 3.EX(execute instruction) 4.MEM(write or read from the memory) 5.WB(write back to the register file) for eg in case of WAW hazards :

I1: LOAD R1,0(R2)

I2: ADD R1, R2, R3

```
I1:  |IF|ID|EX|MEM|WB |
I2      |IF|ID|EX |MEM|WB|

```

The above is expected way in which the instructions execute without data hazards
but here the second instruction has to wait till the WB phase of the instruction I1 for getting the value of R1 hence it will stall till the value of R1 is available in register file i.e till WB phase of the I1. here what my doubt is in case I2 Takes less number of clock cycles than I1 for completion then can I2 access the register file going to WB phase directly in case it has nothing to do in the phase of MEM will this give rise to a hazard?

# Answer
> in case I2 Takes less number of clock cycles than I1 for completion then can I2 access the register file going to WB phase directly in case it has nothing to do in the phase of MEM will this give rise to a hazard?

I2 reads the register R1 at its ID phase. Therefore, if implemented directly, we must have **time(I2.ID)\>time(I1.WB)**. A more sophisticated solution would bypass the register file and take the values directly from the Memory output. In this case we need **time(I2.ID)\>time(I1.MEM)** and the controller becomes more involved.

If I understand your question correctly, you ask whether I2 must take 5 clocks although it doesn't use the MEM phase. The answer is YES or otherwise, it may conflict with other instructions that would try to use MEM at the same time (unless the pipeline controller stalls them when congestion appears).
> 3 votes

# Answer
The actually executed codes are:

```
lw $R1, 0($R2)
nop
add $R1, $R2, $R3

```

Therefore the space diagram should be:

```
|IF |ID |EX |MEM|WB |   |   |
|   |   |IF |ID |EX |MEM|WB |

```

With forwarding from MEM of I1 to EX of I2, the hazard would be eliminated
> 0 votes

# Answer
The answer is that, in MIPS, the data is not written to the actual register $R1 until the WB phase for each instruction.

You are confusing what is in the register with what data is available to be forwarded. So while an add function may have its data available to be forwarded after the EX stage, it doesn't write to the register until the WB stage. It does forward the data to the phase registers to be used, but that also requires a control on whether or not they are used.
> 0 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Why are so many internet protocols text-based?
From what I have found, a **very** large amount of protocols that travel over the internet are "text-based" rather than binary. The protocols in question include, but are not limited to HTTP, SMTP, FTP (I think this one is all text-based?), WHOIS, IRC.

In fact, some of these protocols jump through some hoops whenever they want to transmit binary data.

Is there a reason behind this? Text-based protocols obviously have a bit of an overhead as they require sending more data to transmit the same amount of information (see example below). What benefits outweigh this?

---

By **text-based**, I mean most of the characters used in the protocol are between `0x20` (space) and `0x7E` (`~`), with the occasional "special character" used for *very special purposes*, such as the newlines, null, ETX, and EOT. This is opposed to transmitting raw, binary data over the connection.

For instance, transmitting the integer `123456` as text would involve sending the string `123456` (represented in hex as `31 32 33 34 35 36`), whereas the 32-bit binary value would be sent as (represented in hex) `0x0001E240` (and as you can see, "contains" the special null character.

# Answer
> 46 votes
When the world was younger, and computers weren't all glorified PCs, word sizes varied (a DEC 2020 we had around here had 36 bit words), format of binary data was a contentious issue (big endian vs little endian, and even weirder orders of bits were reasonably common). There was little consensus on character size/encoding (ASCII, EBCDIC were the main contenders, our DEC had 5/6/7/8 bits/character encodings). ARPAnet (the Internet predecessor) was designed to connect machines of any description. The common denominator was (and still is) text. You could be reasonably certain that 7-bit encoded text wouldn't get mangled by the underlying means to ship data around (until quite recently, sending email in some 8-bit encoding carried a guarantee that the recipient would get mutilated messages, serial lines were normally configured as 7-bit with one bit parity).

If you rummage around in e.g. the telnet or FTP protocol descriptions (the first Internet protocols, the network idea then was to connect remotely to a "supercomputer", and shuffle files to and fro), you see that the connection includes negotiating lots of details we take as uniform,

Yes, binary would be (a bit) more efficient. But machines and memories (and also networks) have grown enormously, so the bit scrimping of yore is a thing of the past (mostly). And nobody in their right mind will suggest ripping out all existing protocols to replace them with binary ones. Besides, text protocols offer a very useful debugging technique. Today I *never* install the telnet server (better use the encrypted SSH protocol for remote connections), but have to telnet client handy to "talk" to some errant server to figure out snags. Today you'd probably use netcat or ncat for futzing around...

# Answer
> 25 votes
One advantage that might be overlooked is the ability to *experiment*. If you're shoving bits down the tube, you're going to need to write some utility that translates `EHLO` into `0x18` or the like. Instead of doing that, you can simply telnet into a mail server, send `EHLO` and be on your way.

Nothing is preventing you in this day and age from writing code in Assembly or Brainf\*ck, and you might very well save some bits by doing so. However, explaining what exactly you've done to someone else so they can understand and interact with your code is not going to be easy if you do so.

With protocols, it's important that users would be readily able to learn how to use them, as most people back in the day which were using ARPAnet or the beginnings of the Internet were people that felt comfortable behind a terminal.

Similar arguments, by the way, are held in companies today. Should we serialize to JSON or BSON (binary representation of JSON)? If you serialize to BSON, you shed some overhead, but you now need a translator to convert your BSON into JSON and vice-versa, as a human is going to have to read that data at some point when something inevitably goes wrong.

# Answer
> 10 votes
It's not that many internet protocols are text based. In fact, if I were to guess I'd say that text based protocols are in the minority. For almost every text based protocol you see on the internet there are at least two binary protocols that people have invented to send the same or similar data.

But it's true that the majority of internet **traffic** use text based protocols. This fact is interesting if you assume that there are many more binary protocols than text but many more text traffic than binary. It means that most of the **successful** protocols on the internet are text based. Except for a small number of applications (bittorrent is one example) binary protocols tend to die.

In the early days of the internet, corporations tended to design and use binary protocol (MSN for example, not the MSN website of today, the original proprietary MicroSoft Network that was supposed to replace HTTP) while the military, research institutes and academics tended to design and use text based protocol. Part of the reason was that building and debugging binary protocols was hard and corporations can afford to pay people to do it while the military, researchers and academics were doing it in their spare time for no pay (most of the people who developed the internet had jobs not related to developing the internet).

When you're writing code on weekends as a hobby and are not paid for doing what you do you tend to chose the simpler solution - text. So text based protocols got used by more people than binary protocols.

But that's not the full story. Building a network is hard. Really hard. We're so used to the internet today that we don't fully realize what a miracle of engineering it is. Almost every aspect of the internet evolved out of a bug fix. For example, we use IP address instead of MAC address because it allows us to build routers with just kilobytes (or these days megabytes) instead of terabytes of RAM for the routing table. The more and more problems we tried to solve, the more we tend to prefer text based protocols to debug them. Once we had enough experience developing the low-level network protocols, when it came time to develop application protocols most of the experienced programmers and engineers tended to prefer text protocols.

From personal experience, I've worked for a company building routers and I've also worked for a company building telemetry equipment so I've got a lot of experience working with binary protocols such as TCP/IP, ARP, IEC60870-5-101 and DNP3. I've also worked with text protocols such as HTTP, POP3 and NMEA. I've also worked with binary data formats such as ASN.1 and text data formats such as JSON and XML. If I were to choose I'd choose text almost every time. The only time I'd choose binary is if the protocol is really low-level (then I'd implement just enough so that I can plonk a text based protocol on top or it) or the data is naturally binary (like audio files).

# Answer
> 4 votes
Structured binary also has limitations in expanding it. It my days of working with FidoNet and building a gateway between it and UUCP/USNET, Fidonet's message headers were a structured binary. Expanding it by even just trying to add a byte someplace means breaking everything out there that is trying to work with it. Having a text header or protocol means you can expand something w/o breaking things.

# Answer
> 4 votes
Your question can be interpreted in three ways:

1. Why is numerical data transmitted in textual representation, as if it had been printed with e.g. `printf()`?
2. Why do the classical application layer protocols — e.g. the ftp control channel, smtp, http — traditionally all use a 7-bit ASCII character set? (7 bit ASCII can be considered "text" because most bytes correspond to printable glyphs or text control codes like newline and from feed.)
3. Why are blobs of binary data often converted to 7 bit ascii when they are sent over the internet, e.g. as a mail attachment?

The answer to the first one is interoperability. Integers and floating point values have different binary representations on different machines, or even compilers, or even with just different compiler options. Transmitting them effectively via `printf/scanf` makes interoperability easy. Note that this choice was only made for the higher level protocols of which a few are mentioned above; on the network layer data is transmitted binarily. For this, TCP/IP defines a binary integer representation, and libraries implementing TCP/IP provide means to convert between host and network representations with `htonl` and friends.

The answer to the second question is probably that RFC 206 (note the low number — 1971!) describes the telnet protocol, on which many application layer protocols are based, as a direct teletype replacement

> whose function is to make an Online System terminal *appear* to any teletype-compatible, time-sharing system in the Network *as if it were directly connected to that system*.

(Emphasis in the original text.) At least some teletypes and in particular teletype networks used 7 bit ASCII as the character set which must have made it a natural choice.

The answer to the third one is simply that because the application layer protocols are telnet based, and telnet is 7 bit ascii, much soft- and hardware was not prepared to deal with 8 bit data. Sending binary attachments could be considered a misuse of email; hence the hoops. Today that's usually not true any longer and the protocols are continuously extended (or simply used) to directly handle binary data.

# Answer
> 3 votes
Another reason for this is that textual protocols are easier to interoperate with, and a lot more flexible for the future. Older generations, especially the folks behind Unix, already went through the dilemma between binary and textual. They ended up preferring textual for good reasons. It became, in fact, a programming best practice for Unix.

https://www.arp242.net/the-art-of-unix-programming/#ch05s01

> Pipes and sockets will pass binary data as well as text. But there are good reasons the examples we'll see in Chapter 7 are textual: reasons that hark back to Doug McIlroy's advice quoted in Chapter 1. Text streams are a valuable universal format because they're easy for human beings to read, write, and edit without specialized tools. These formats are (or can be designed to be) transparent.
>
> ...
>
> Designing a textual protocol tends to future-proof your system. One specific reason is that ranges on numeric fields aren't implied by the format itself. Binary formats usually specify the number of bits allocated to a given value, and extending them is difficult. For example, IPv4 only allows 32 bits for an address. To extend address size to 128 bits (as done by IPv6) requires a major revamping.\[51\] In contrast, if you need a larger value in a text format, just write it. It may be that a given program can't receive values in that range, but it's usually easier to modify the program than to modify all the data stored in that format. ...

There are exceptions where binary makes a lot more sense.

Just a recent example: I needed to collect Vault audit logs and filter some of them to send alerts to an email address, and send all of them to a remote sys log server.

Vault can send audit logs via TCP in JSON format separated with new lines, which is plain text. Fluentd can open a TCP port and receive JSON format elements separated by new lines, again, plain text. The email server SMTP protocol is, guess what, plain text. The Remote sys log server speaks plain text following RFC5424 formatting, on a TCP or UDP port.

I was able to hook them all to do the job, and all those components are from different companies and ages. Also, while working on the interoperability, I was able to fake some of the senders and receivers with a simple TCP python program.

---
Tags: computer-networks, communication-protocols, protocols
---


# Question
Title: Binary Plane Partition: do we have to split a line segment?
I'm considering the planar BSP problem, where we are required to partition a set of disjoint line segments in the plane, such that every region in the partition contains at most one line segment or a portion of one line segment.

My question is: is there a way of partition these line segments such that no line segment is split into more than one region?

# Answer
> 3 votes
The answer is "No". Please see a counterexample below:

---
Tags: computational-geometry
---


# Question
Title: Enumerate all connected components that could be created from removing k edges?
I have a simple connected undirected graph $G=(V, E)$ and I would like to enumerate all possible connected components that arise from removing $k$ edges in $E$. A naive way is to remove each $k$-tuple of edges (of which there are $\binom{|E|}{k}$ total) and then run a connected components algorithm, but this feels incredibly wasteful. I know there are dynamic decremental connectivity algorithms but these appear optimized for on-line (dynamic) use, which again seems wasteful.

# Answer
You might be optimizing on the wrong end. Finding connected components for a fixed graph can be done in $O(|V|+|E|)$ time. With the dynamic decremental algorithm you link to, you can reduce that to $O(|V|)$. And you still consider it wasteful.

My primary concern would be the number ${|E|}\choose k$ which, contrary to all the above, is not polynomial in the input. One observation that might help here: If you can identify an $l$-edge-connected subgraph, then you only need to consider $k$-tuples of edges that have either at least $l$ edges from the subgraph or none at all.
> 1 votes

---
Tags: graphs, connected-components
---


# Question
Title: What's the error about the definition of NP?
Many sources (including Wolfram's MathWorld) say that NP problem is defined as a decision problem "verifiable in nondeterministic polynomial time" (check Google to see more sources).

But accordingly Wikipedia tells that NP are problems that can be solved in non-determnistic polynomial time.

From conjunction of these two statements it follows that $\mathrm{P}=\mathrm{NP}$, because any algorithm verifies itself.

So, apparently MathWorld and many others are wrong in their definition of NP? Or what do I misunderstand?

If "verifiable in nondeterministic polynomial time", is not a definition of NP, then how is it indeed called?

# Answer
If a problem $A$ is verifiable in polynomial-time by a non-deterministic Turing machine $T$ (given an instance of the problem and certificate of length polynomially bounded in the size of the instance) then it is also solvable in polynomial-time by a non-deterministic Turing machine $T'$.

The Turing machine $T'$ simply (non-deterministically) guesses the certificate (among all certificates having a polynomially-bounded length) and then (non-deterministically) checks whether each certificate candidate is valid using $T$.

This shows that $A \in \mathsf{NP}$.

Conversely, if a problem is in $\mathsf{NP}$ then it is verifiable in polynomial-time by a deterministic Turing machine $T$. Clearly, $T$ is also a non-deterministic Turing machine.
> 3 votes

# Answer
The class $\mathsf{NP}$ can be defined either as

1. the class of languages that can be *verified by a deterministic polynomial time algorithm*;
2. the class of languages that can be *solved by a nondeterministic polynomial time algorithm*.

Regarding 1), a verification algorithm is a two-argument algorithm $A$, where one argument is an ordinary input string $x$, and the other argument is a binary string $y$ called a *certificate*. The algorithm $A$ verifies $x$ if there exists a $y$ such that $A(x,y)=1$. The language verified by a verification algorithm *A* is $L=\\{ x \in \\{0,1\\}^\* |$ there exists $y \in \\{0,1\\}^\*$ such that $A(x,y)=1$.

Regarding 2), defining

$\operatorname{NTIME}\_{\operatorname{TM}}(T(n)) = \\{R: \exists$ a nondeterministic Turing Machine with time complexity $O(T(n))$ on *any computation path* that accepts $R\\}$

then $\mathsf{NP} = \operatorname{NTIME}\_{\operatorname{TM}}(n^{O(1)})$

Regarding Wolfram's MathWorld, it is worth noting here that the same web site (see their definition of NP-Problem) reports that "A problem is assigned to the $\mathsf{NP}$ (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine."
> 1 votes

---
Tags: reference-request, definitions
---


title: Prove decidable

text:
# Question
Title: Prove decidable
> L={⟨M⟩: M is a DFA and for each string in L(M) the number of 1s is more than or equal to the number of 0s }

T = "On input where M is encoded DFA"

```
1. Construct another DFA D such that L(D)={x|x has more or equal 1s than 0s}
2. For each input x
   a. if( x is accepted by DFA M){
          if(accepted by D){
           "accepted" and return;
          }
3. "rejected"

```

Is this proof true?

# Answer
No, this proof is not correct. You can't iterate through all inputs $x\in \Sigma^\*$ since it would take you "infinite time".

The correct way to do this is to construct the complement of $D$ (as a pushdown automaton! as @Steven mentioned), which we will call $D^c$, then construct the intersection PDA $D^c\cap M$ (notice that this can be done since $M$ is a DFA), and test if its language is empty. If it is, you can be sure that $L(M)\subseteq L(D)$, hence all words in $M$ have more $1$'s than $0$'s
> 1 votes

---
Tags: turing-machines, decidability
---


# Question
Title: Question regarding the total cost of a tree for a code proof
The question is: "Prove that we can also express the total cost of a tree for a code as the sum, over all internal nodes, of the combined frequencies of the two children of the node."

I found an answer here (16.3-4): https://walkccc.me/CLRS/Chap16/16.3/, but I'm confused about one part of it.

Specifically I'm confused about this part of the proof:

$$ \begin{aligned} B(T) & = \sum\_{\text{leaves }l \in T} f(l)d\_T(l) \\ & = \sum\_{l \ne c\_1, c\_2} f(l)d\_T(l) + f(c\_1)(d\_T(c\_1) - 1) + f(c\_2)(d\_T(c\_2) - 1) + f(c\_1) + f(c\_2) \\ & = \sum\_{\text{internal nodes }i'\in T'} f(\text{child}\_1\text{ of }i') + f(\text{child}\_2\text{ of }i') + f(c\_1) + f(c\_2) \\ & = \sum\_{\text{internal nodes }i\in T} f(\text{child}\_1\text{ of }i) + f(\text{child}\_1\text{ of }i). \end{aligned} $$

How do we get from here:

$$\sum\_{l \ne c\_1, c\_2} f(l)d\_T(l) + f(c\_1)(d\_T(c\_1) - 1) + f(c\_2)(d\_T(c\_2) - 1) + f(c\_1) + f(c\_2)$$

to here:

$$\sum\_{\text{internal nodes }i'\in T'} f(\text{child}\_1\text{ of }i') + f(\text{child}\_2\text{ of }i') + f(c\_1) + f(c\_2)$$

# Answer
Here is a different proof. Denote the frequency of a node $x$ by $w(x)$ and its cost by $c(x)$, and let $x \prec y$ denote that $x$ is a leaf which is a descendant of the internal node $y$. Thus $$ w(y) = \sum\_{x \preceq y} w(x). $$ The sum of all frequencies is $$ \sum\_{\text{internal }y} w(y) = \sum\_{\text{internal }y} \sum\_{\substack{\text{leaf }x\text{ s.t.}\\ x \prec y}} w(x) = \sum\_{\text{leaf }x} \sum\_{\substack{\text{internal }y\text{ s.t.}\\x \prec y}} w(x) = \sum\_{\text{leaf }x} c(x) w(x), $$ since $x$ has exactly $c(x)$ internal nodes $y$ of which it is a descendant.
> 0 votes

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


title: A formal definition for amortized time

text:
# Question
Title: A formal definition for amortized time
Several (tutoring) students have asked me for a formal definition of amortized time and I've never been able to find one online. All the literature I've found usually outlines the three most common methods for doing the actual analysis and no more. In a few places there are explanations of why the amortized time for $op$ is **not** $O(f(n))$ by presenting a series of operations whose combined $op$s take $\omega(f(n))$ on average, but nowhere I've looked provides an unambiguous definition.

The definition I've settled on is:

For some data structure $S$ and operation $op$ of $S$, the amortized time for $op$ is $O(f(n))$ if and only if for every sufficiently large $m$ and any series of $m$ operations on $S$, if $k$ of those operations were $op$ then the sum of actual times for those $k$ operations in the series is $O(k\cdot f(n))$.

The amortized time for $op$ is $\Omega(f(n))$ if and only if there exists such a series where the sum of actual times of the $op$s is $\Omega(f(n))$.

The above can be applied to $o(f(n))$ and $\omega(f(n))$ respectively.

My question is whether this is a good definition of amortized time for operations in a data structure and if not, what would a better definition be?

# Answer
> 5 votes
Consider a data structure with operations $o\_1,\ldots,o\_k$. We say that these operations have amortized time $t\_1,\ldots,t\_k$ if any sequence of operations which contains $m\_i$ operations of type $o\_i$ runs in time at most $\sum\_i m\_i t\_i$. This is essentially the same definition as yours, in a more general setting.

We often allow $t\_1,\ldots,t\_m$ to depend on some promise on the data structure. One common example is $t\_1,\ldots,t\_m$ being a function of $n$, where $n$ is a bound on the total number of elements in the data structure. We will consider this example as we go on.

If there is only one operation $x$, then its amortized time is $\Omega(s(n))$ if whenever $t(n)$ is a valid amortized time for $x(n)$, $t(n) = \Omega(s(n))$. This can be proved by exhibiting, for each $n$, a sequence of $m$ operations, maintaining the promise on the data structure, which take time $\Omega(m s(n))$. Sometimes we want to prove such lower bounds for *every* implementation of an abstract data structure. The amortized time is $\Omega(s(n))$ if it is $\Omega(s(n))$ in any valid implementation of the ADT.

If there is more than one operation, then it's more difficult to talk about amortized time lower bounds, since now we're dealing with asymptotics of several operations at once. When dealing with concrete data structures, you can show, for example, that $t\_1(n),\ldots,t\_k(n)$ is a valid amortized time, but if you replace a single $t\_i(n)$ (or perhaps all of them) by a function which is $o(t\_i(n))$, then you don't get a valid amortized time.

For abstract data structures, you can prove lower bounds on individual operations, as well as tradeoffs. One example is a statement of the form $t\_1(n) = \Omega(s\_1(n))$ or $t\_2(n) = \Omega(s\_2(n))$. Another is a statement of the form $t\_1(n) t\_2(n) = \Omega(s(n))$.

---
Tags: data-structures, amortized-analysis
---


title: Writing efficient code

text:
# Question
Title: Writing efficient code
I am new to programming and trying to get better at writing efficient code.

The obvious thing to do is practice and gain experience.

I did learn a few general pointers through exercising, but in most cases, the only option is to simply think of a better algorithm to solve a given problem.

What would be a good source (free or paid) to learn from about how to "think of that better algorithm"?

# Answer
Take a look at Bentley's Programming Pearls. Not specifically about efficiency, but most of the advice in it does have an important bearing on it. A classic (sadly out of print) is his Writing Efficient Programs. Relevant is also Kernighan and Pike's The Practice of Programming.

But it is critical to design and write clean, understandable programs first. Most of the time the "efficiency" is irrelevant (i.e., shaving off a half second of execution time to have the user then thinking for half a minute what to do next is a terrible use of your time). Just think what an hour of your time is worth, and how much a second of computer time is worth. You'll have to factor in not only the development time (writing an efficient, well tuned program is harder than you think, ad it is *much* harder still to fix if something changes later on). As the saying goes, debugging is twice as hard as writing the program in the first place. If you write the cleverest program you can, you have no chance of fixing it.

Programmers are *terrible* at estimating where the program spends most resources, Bentley gives some hilarious blunders (and some instructive success stories too). Program, *measure* and then consider where the effort to make more efficient is best spent (if warranted). Note that current compilers are *extremely* good ad generating code, specially at high "optimization" levels. For most micro-optimizations you'd come up with (e.g., reuse a variable, write some expression differently --add `x + x` instead of `2 * x`, shift instead of multiplying by a power of 2--, compute a common subexpression once, and so on) you'll find that your favourite compiler has them already covered, and then some. If in doubt, ask for assembly output and check.
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Does TM $M$ exist, when $L_{\leq3} \subset L(M) \subset L_{\leq4}$
and $L\_{\leq k} = \\{\langle M \rangle : |L(M)|\leq k\\}$

The solution that I saw is:

Proof by contradiction, assume such $M$ exists.

So reduction $f$ from $\overline{HP}$ to $L(M)$, when $\overline{HP}=\\{(\langle M\rangle,x ) | M $ doesn't halt on $ x\\}$

$f(\langle M'\rangle,x ) = \langle M\_x\rangle$

When $M\_x$ on input $w$ implemented in the following way:

1. execute $M'$ on $x$
2. accept if M' halt

I can't understand the validity of it, I mean why

$M\_x \in L(M) \Leftrightarrow (\langle M'\rangle,x )\in \overline{HP}$

is true?

The next step quite simple, if $M$ exists then $L(M)\in RE$ and based on the reduction it's mean that $\overline{HP}\in RE$, contradiction.

Maybe I found wrong solution?

# Answer
To fix the solution you just need to accept any 3 elements of your choice in $M\_x$. Now, $M\_x$ will look something like that:

1. If $w$ (the input) is $0,1$ or $00$, accept .
2. Otherwise, emulate $M$ on $x$.
3. Accept if $M$ halted.

Now, you are guaranteed to have exactly 3 elements in $L(M\_x)$ if $M$ doesnt halt on $x$, and otherwise $L(M\_x)=\Sigma^\*$.

You can now continue with the proof as you have written.
> 1 votes

---
Tags: turing-machines
---