# Question
Title: Effects of parity bit on odd code length regarding its size after alternation
I am trying to understand code distance, but I am not sure regarding the following scenario:

Assume that you have an information word M with m bits, that You code into a coding word using the following procedure:

1. You take M and code it using a code you know nothing about. But you do know that its distance(code's distance) is k, and that k\>2.
2. You add to the word obtained in the last step a parity bit.

If you know that k is odd, does it necessarily mean that the distance of the code constructed by those two steps is necessarily k+1?

Well, I am not sure here. Code distance is basically the number of different bits, and the meaning of the second step in the procedure(adding a parity bit) is, according to my understanding, allowing the detection of any odd number of errors. Does it necessarily mean that the code constructed by those two steps is necessarily k+1?

# Answer
Normally a code's hamming distance is limited to some maximum message length. For example in the case of a 32 bit CRC, for Hamming distance = 3 (2 bit error detection), the maximum length for a message is 2^32-1 bits (including the 32 bits of CRC), depending on the CRC used. With a larger message, a 2 bit error can fail. For a parity check or Hamming distance = 2 (1 bit error detection), there is no maximum length limit.

If the message length is \<= maximum message length for that Hamming distance, and k is odd (maximum # of error bits detected is even), then adding a parity check in addition to the CRC should increase Hamming distance to k+1.

For example, CRC16 based on polynomial x^16 + x^12 + x^5 + 1 (0x11021) is the product of 2 irreducible polynomials : (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) (0xf01f) and (x + 1) (0x3). For message length (including CRC bits) CRC poly (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) Hamming distance is 3 for message length up to 32767 (2^15-1) bits, and the (x + 1) term increases this to Hamming distance 4. As mentioned above, it can detect any odd number of bit errors for any length message.
> 0 votes

# Answer
Let $m\_1,m\_2$ be any two different codewords of $M$, and let $m'\_1,m'\_2$ be the codewords after adding a parity bit. Since $M$ has minimum distance $k$, the distance between $m\_1,m\_2$ is at least $k$. If their distance is at least $k+1$, then $m'\_1,m'\_2$ are at distance at least $k+1$. If the distance between $m\_1,m\_2$ is exactly $k$, then they have different parities (since $k$ is odd), hence the distance between $m'\_1,m'\_2$ is exactly $k+1$. This shows that the minimum distance of the new code is exactly $k+1$.
> 0 votes

# Answer
You know that two different valid codes have a distance of at least three bits, so you need at least three bit changes to turn a valid code into a different valid code.

But making exactly 3 changes gives a different parity. 4 changes = same parity, 5 changes = different parity etc. So if you add the parity bit, the code + parity has a minimum distance of 4 bits, not 3. This means you can either detect all three bit changes instead of all two bit changes, or you can correct all single bit changes and at the same time detect all double bit changes (risking that a triple error is “corrected” in the wrong way) instead of correcting all single bit changes (and risking that a double bit change is “fixed” incorrectly).

If you had started with a code with even Hamming distance then I can’t quite see how adding a parity bit would be very useful.
> 0 votes

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


title: Proving bounds for a function

text:
# Question
Title: Proving bounds for a function
I'm kinda confused by Asymptotics, the exercises in the book I'm reading say to prove for example $f(n) = \Omega(g(n))$, and there is something I don't understand about these kind of proofs. Do I have to prove them algebraically or is it possible to find some constant ($c$) such that this statement holds?

For example would it be correct to write $(n + a)^b = \Omega(n^b)$ since $ (n + a)^b \gg 1 \cdot n^b$?

Any help would be much appreciated.

# Answer
> 2 votes
By definition it's enough to show existence of $c\>0$, and, also existence of $N \in \mathbb{N}$, for which $f(n) \geqslant c g(n)$, when $n \gt N$. Of course, if it's possible to find $c$, then proof is also done.

In case of $(n + a)^b = \Omega(n^b)$, assuming $a,b\>0$, then choice $c=N=1$ fulfills definition, as we have $(n + a)^b \geqslant n^b$.

BTW, holds also $(n + a)^b = O(n^b)$, so $(n + a)^b = \Theta(n^b)$.

---
Tags: asymptotics
---


# Question
Title: Algorithm for solving a mixed integer programming problem in polynomial time?
I have the following mixed integer programming (MIP) problem:

$$ \begin{array}{rll} \text{Maximize } & z=k \\ \text{subject to } & a\_ik - m\_i \geq 0 & (i=1,\dots,n) \\ & b\_ik - m\_i \leq 1 & (i=1,\dots,n) \\ \text{where} & k \in \mathbb{R}\_{\geq 0}, m\_i \in \mathbb{N}\_0 & (i=1,\dots,n), \end{array} $$

where $a\_i,b\_i$ are non-negative real numbers such that $0 \leq a\_1 \< b\_1 \< a\_2 \< b\_2 \< \dots \< a\_n \< b\_n$ (defining $n$ "forbidden intervals" $(a\_i,b\_i)$), $k$ is an unknown repetition frequency, and $m\_1,\dots,m\_n$ are unknown integers (telling how many repetitions will occur before the different intervals).

(Alternatively, the MIP-problem can be rephrased as "Find the minimal $x \in \mathbb{R}\_{\>0}$ such that $mx\not\in(a\_i,b\_i)\ \forall\ m\in\mathbb{N},i\in\\{1,\dots,n\\}$". It is by defining $k=1/x$, and $m\_i$ as the largest non-negative integer for which $m\_i x \leq a\_i$, that the MIP formulation can be obtained.)

I need to either come up with an algorithm to solve this problem in polynomial time, or prove that the problem is NP-hard (or NP-intermediate if not NP-hard, I guess). I have tried to come up with a poly-time algorithm but not been successful, but I don't really know how to prove NP-hardness either.

How can I prove that this problem is NP-hard, or alternatively, is there some algorithm with a polynomial (in terms of the input size, i.e., the size required to store the input in memory) worst-case time complexity that can solve it?

In general, how do one prove NP-hardness? What I understand, for a given problem H, if every problem in NP problem can be reduced H in polynomial time, then H is NP-hard. But how do I prove that this is the case? There has to be close to infinitely many problems in NP, so is it enough to show for one of the problems that are NP-complete that it can be reduced to H in polynomial time? Is there some list of NP-complete problems that I can look at to try to prove that this MIP problem is NP-hard?

# Answer
> 0 votes
Finding an upper limit for k is trivial. Let d be the minimum of $b\_i - a\_i$ over all i, then k ≤ floor (1 / d).

And for each k up to the upper limit, it is trivial to check that floor ($a\_i \cdot k$) = floor ($b\_i \cdot k$).

# Answer
> 0 votes
Here is a simple algorithm based on the alternative formulation ("Find the minimal $x \in \mathbb{R}\_{\>0}$..."), for which I have not been able to bound the running time by a polynomial. Briefly, we start at a lower bound and keep increasing $x$ by the minimum "useful" amount (meaning: all smaller increases are known to fail) until we get a feasible solution:

1. Begin by setting $x = \max\_i (b\_i-a\_i)$. (This is a lower bound, since any smaller choice of $x$ would necessarily cause the longest interval to be hit at least once.) If this choice of $x$ avoids all intervals, we are done; otherwise continue.
2. Set $x':=x$. We maintain the invariant that all solutions smaller than $x'$ are known to be infeasible.
3. For each interval $i$:
    1. Determine whether the $i$-th interval is hit by computing $c\_i=\lfloor a\_i/x\rfloor + 1$ and testing whether $c\_ix \< b\_i$.
    2. If so, set $x\_i$ to $x+(b\_i-c\_ix)/c\_i$ and update $x'$ to $\max \\{x', x\_i\\}$. Note that $x\_i$ is certainly feasible *for the $i$-th interval*, because there is at most 1 hit within this interval with the current $x$ (by our initial choice of $x$, and the fact that we only ever increase it), and $x\_i$ is the result of increasing $x$ by the smallest amount necessary to slide the hit location to the right endpoint of the interval, which is not enough to introduce a new hit on this interval from the left-hand side.
4. If any intervals were hit in the previous step, set $x := x'$ and go to 3, otherwise $x$ is the optimal solution.

Where this could be slow is if all intervals are very narrow, and far to the right. It seems plausible to me that some such problem instance could necessitate a long initial sequence of small rightward nudges, each of which produces an $x$ that alleviates the hit for one interval, but reintroduces a hit on some other interval.

# Answer
> 0 votes
Since the value of each $m\_i$ doesn't matter (you can assign $m\_i=\lfloor a\_ik\rfloor$ as far as the $\[b\_ik-1, a\_ik\]$ contains an integer), your problem can be re-formulated as:

$$ \begin{align} \max~~& k\\ \text{s.t.}~~& b\_ik-1\le \lfloor a\_ik\rfloor & \forall i=1, ..., n\tag{1}\\ & k\in\Bbb R\_{\ge 0}\\ \text{where}~~& a\_i,b\_i\in\Bbb R\_{\ge0}, ~a\_i\lt b\_i & \forall i=1,..., n \end{align} $$

The restriction (1) generates a sequence of valid values for each interval $i$, defined by a sequence of disjunt **ranges** with **gaps** between them (I use range instead of interval to differentiate from the input):

$$ \def\int#1#2#3#4{\left\[\frac{#1}{#2},~\frac{#3}{#4}\right\]} %% k\in\mathcal I\_i=\int{0}{a\_i}{1}{b\_i}\bigcup\int{1}{a\_i}{2}{b\_i}\bigcup\cdots\bigcup\int{q\_i^\*-1}{a\_i}{q\_i^\*}{b\_i}\bigcup\int{q\_i^\*}{a\_i}{q\_i^\*+1}{b\_i}\\ \\ ~\text{where}~q\_i^\*=\left\lfloor\frac{a\_i}{b\_i-a\_i}\right\rfloor $$

and where the maximum $k\_i^\*$ for any $i$ is $$ k\_i^\* = \frac{q\_i^\*+1}{b\_i} = \frac{\left\lfloor\frac{a\_i}{b\_i-a\_i}\right\rfloor+1}{b\_i} $$

Given any $\mathcal I\_i$, the length of each range in its sequence decreases by $\frac{1}{a\_i}-\frac{1}{b\_i}$ respect to the previous one, while each gap increases by the same amount. The sequence ends when a next range would give an empty interval, and the size of the sequence is $q\_i^\* + 1$.

I haven't been able to find any NP-complete problem reducible to yours, but I would go for NP-complete problems related to congruences or algebra. There must be something related there.

Respect to a solution algorithm, just take

$$ k^+=\min\_i\left\\{k\_i^\*\right\\}=\min\_i\left\\{\frac{\left\lfloor\frac{a\_i}{b\_i-a\_i}\right\rfloor+1}{b\_i}\right\\} $$

as initial upper bound, and then, if for some $j$ the restriction (1) is not satisfied, assign

$$ k^+\leftarrow \frac{\left\lfloor\frac{k^+}{b\_j}\right\rfloor}{b\_j}\tag{2} $$

and repeat (that assignment will give the maximum feasible $k\lt k^+$ for the interval $j$).

This algorithm will run in $O(n\sum\_i^n q\_i^\*)$ in the worst case, which is the size of the input multiplied by the total number of gaps, and thus exponential in the size of the input if codified in binary, or quadratic when codified in unary (each time the algorithm updates $k^+$ is because it falled in some gap, and to know it you have to do $O(n)$ checks; the worst case being when $k^+$ visited all gaps).

In practice, you could improve this algorithm a lot by sorting the intervals by $\frac{1}{a\_i}-\frac{1}{b\_i}$ in decreasing (non-increasing) order, so when checking the feasibility of $k^+$ you check intervals with bigger gaps first so that the jumps given by (2) are the biggest as possible the sooner as possible (if $a\_1=0$ you can just remove the first interval, because the initial $k^+$ will already be $\le\frac{1}{b\_1}$).

**NOTE:** The definition of $\mathcal I\_i$ for each interval $i$ can be obtained by calculating the valid values of $k$ so that $\lfloor a\_ik\rfloor=q$ and $b\_ik-1\leq q$ for some natural number $q$, and $q\_i^\*$ is the maximum $q$ so that $\frac{q}{a\_i}\le \frac{q+1}{b\_i}$ holds. Respect to the first equation, consider that $\lfloor a\_ik\rfloor=q$ implies $a\_ik\le q\lt a\_ik + 1$.

---
Tags: algorithms, np-hard, proof-techniques, np, integer-programming
---


# Question
Title: Which has optimum performance? raw core or multithreaded
Let's say there's a single process performed in the machine which utilizes all available processors (whether physical or logical processors). The process use 100% processor utilization most of the time on all processors.

Which machine will perform better?

* Machine with 2 cores, 1 thread per core (2 physical processors); or the
* Machine with 2 cores, 2 threads per core (4 logical processors)

This is assuming everything (memory, clock speed, etc) is the same and the only thing that differ is the number of threads.

My initial thoughts would be that the former -- machine with 2 raw cores (1 thread) -- will perform better because it doesn't have context switching. Whereas the latter would have overhead on the context switching.

Which machine will perform better?

# Answer
> 3 votes
There's no real way to answer this without a lot of details about both the code to be executed, and the micro-architecture of the CPU executing the code.

A CPU that can execute multiple threads per core will typically start with a pool of instructions, decoded and ready to execute. As instructions enter the pool, a scoreboard1 gets updated to reflect inputs to an instruction, execution resource(s) needed by that instruction, and the output of the instruction.

So you might have an instruction like `add r0, r1, r2`, meaning add register 0 to register 1 and put the result in register 2. The inputs are registers 0 and 1, the execution resource needed is an integer adder, and the output is register 2.

Then there's a scheduler that looks at the resource usage and tries to find instructions that don't conflict, and each clock cycle, tries to find as many of those as possible to execute. As it does so, it updates the scoreboard so the next clock cycle, it'll know what resources are in use now.

That all leads to the basic question: given the parallel resources provided by this CPU, and the instructions in the streams to be executed, what is the average level of conflict between instructions?

The drastically simplified answer is that more often than not, executing two independent streams of instructions will result in more instructions that can execute with fewer conflicts, so overall speed will increase much more often than not. It's rarely a question of which is faster--only of how much speed you'll gain by executing more threads in parallel, and whether that gain is enough to justify the extra labor to make that work, or whether you'd have gained more by expending more the CPU budget on other things that could have made an even bigger difference (e.g., bigger cache, better branch prediction, etc.)

### Goal

There's also room for a bit of question about your goal here. A single core executing two threads will typically execute each thread a *little* slower than that thread would execute on a core by itself. On the other hand, the overall throughput of the system will be somewhat *greater* than if you ran only one thread at a time.

For example, if you had a CPU that was split almost perfectly between two threads, each might run at 60% of the speed it would if it was the only thread running on a core.

So, if you really care almost exclusively about the performance of one thread, then running only one thread per core may well improve the speed of a thread when it is running.

At the same time, if you have two threads each running at 60% the speed it would on its own, your overall speed is 120% of what it would be with each thread running on its own, meaning you're getting about 20% more work done per unit time.

In a game (for one example) it's pretty common to have one thread that really matters, so you really want to optimize performance for one thread. If that's your case, you probably only want one thread per core.

On the other hand, with something like a server you often have *lots* of requests happening all the time, and one major concern is maximizing overall throughput. In such a case, more threads per core can make a lot more sense (but also note that total throughput isn't usually the *only* concern even in this case).

### CPU Utilization

Since "CPU Utilization" was mentioned in a comment, I'll comment on it a bit as well. Generally speaking, when an operating system reports something like percentage of CPU utilization, it's basically irrelevant to questions like this.

An OS is basically just reporting what percentage of CPUs have threads assigned to execute on them at any given time. For example, if a single-threaded CPU executes an instruction to read from main memory, it could easily take 50-100 clock cycles to execute a single instruction. According to the OS, that's keeping the CPU 100% busy for those clock cycles--but most of the CPU's actual resources would be available, so it could perfectly well execute other instructions during that time.

---

1. Well, the early versions were called "scoreboards". More recently there are more complex structures with other names, but I'm going to call all of them scoreboards to keep things simple.

# Answer
> 1 votes
The machine with 2 threads per core will have always have more throughput than a machine with a single thread per core. A machine with more threads will be able to execute more threads concurrently and it reduces the idle time spent by a CPU's resource (example: Arithmetic Logic Unit). It does this by switching to a different thread if the current thread is stalled.

In the unlikely event that there are no threads to switch, there will neither be a performance gain nor a performance penalty since it uses the single thread and there is no context switching overhead. So a machine with more threads per core can never be slower than a machine with lesser threads per core.

Multithreading will be done only when there are multiple **independent** threads.

Conclusion: A multithreaded core will have better performance than a single-threaded core.

---
Tags: computer-architecture, parallel-computing
---


# Question
Title: Show that $L$ and $\overline L$ cannot be both finite
> Let $L$ be any language on a nonempty alphabet. Show that $L$ and $\overline L$ cannot be both finite.

This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz.

My attempt: $L$ is a subset of $\Sigma^\*$, so it can be either finite or infinite. If $L$ is finite, then $\overline L$ is infinite. If $L$ is infinite, that is, $L = \Sigma^\*$, then $\overline L = \Sigma^\* - L = \Sigma^\* - \Sigma^\* = \emptyset$. Therefore, $L$ and $\overline L$ cannot be both finite.

Is it correct? I tried to write a direct proof. Thanks in advance.

# Answer
> 1 votes
If $L$ and $\overline{L}$ were both finite, then so would $\Sigma^\* = L \cup \overline{L}$ be, which we know is false.

This is a qualitative statement. We can make it quantitative by considering densities. Let us say that a language is *dense* if for infinitely many $n$, it contains at least half the words of length $n$. It is easy to check that at least one of $L,\overline{L}$ is dense.

# Answer
> -1 votes
Your **intuition** is correct, however I wouldn't call it a "formal" proof. A *really* formal proof (but seriously, its *too* formal) can be stated like that:

If $L$ is infinite, we are done. Otherwise, $|L|\<\infty$. In particular, there is some $w\in L$ such that $|w|\ge |w'|$ for every other $w'\in L$ \- that is, $w$ is the longest in $L$. Denote $n:=|w|$, and notice that $\\{w'\in \Sigma^\*\mid |w'|\>n\\} \subseteq \Sigma^\* \setminus L = \bar L$. Define $f:\Sigma^\*\rightarrow \\{w'\in \Sigma^\*\mid |w'|\>n\\}$ by $f(w)=0^{n+1}w$ (instead of $0$, you can choose some other letter from $\Sigma$). Clearly, $f$ is injective, and therefore $|\Sigma^\*|\le |\\{w'\in \Sigma^\*\mid |w'|\>n\\}|\le |\bar L|$. Since $\Sigma^\*$ is infinite, then $\bar L$ is infinite as well, just as required.

Once again, this is a formal solution to the question. Your solution is still definitely valid, but note that $L$ being infinite **does not automatically imply** that $L=\Sigma^\*$ (Thanks Dmitry for pointing this out in the comments).

---
Tags: formal-languages
---


# Question
Title: Insertion sort on small arrays in Merge Sort
Quick question on the wording of the question from CLRS Ch2 Problems. The question goes as follows:

> Although merge sort runs in $\Theta(n\lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)$ worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which **$n/k$ sublists** of **length $k$** are sorted using insertion sort and then merged using the standard merging mechanism, where $k$ is a value to be determined.

My question is: shouldn't there be $k$ sublists each of length $n/k$? The other way around is stated in the question. Because in merge sort, we keep halving the array, thus producing twice the number of arrays as in the previous level. Hence, each sublist is of length $n/k$ and we have $k$ of such sublists. Why does the question mention this the other way around?

# Answer
The idea most probably is to chose sublist size $k$ such that merge sort likely is faster for bigger problem instances and insertion sort for smaller ones.
$\lceil s = n/k\rceil$ sub-lists may be suboptimal for merging lists of disparate size later on.
One alternative is splitting into $2^{\lfloor\log\_2{n/k}\rceil}$ lists.
> 1 votes

# Answer
The proposed algorithm has the following structure. On an input of length $n$:

* If $n$ is large, then divide the input into two parts of sizes $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$, sort of each of them recursively, and then merge them.
* If $n$ is small, then instead use insertion sort.

When should we switch to insertion sort? When the list size is smaller than some constant $k$.

If you think of the entire recursion tree, then we switch to insertion sort when having $n/k$ sublists of length $k$, and not the other way around. Switching when we have $k$ sublists of length $n/k$ would mean switching at a constant recursion depth, which makes little sense here.
> 0 votes

---
Tags: algorithms, sorting
---


# Question
Title: Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$
> Let $\Sigma = \\{a, b\\}$ and $L = \\{aa, bb\\}$. Use set notation to describe $\overline L$.

This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. The author provides the following answer: $\overline L = \\{\lambda, a, b, ab, ba\\} \cup \\{ w \in \\{a, b\\}^+ : |w|\geq 3\\}$. Mine on the other hand is the following: $\overline L = \Sigma^\* - L = \\{w \in \Sigma^\* : w \neq aa, w \neq bb\\}$. Is my answer wrong? Thanks in advance.

# Answer
You already got your answer in the comments: both the solutions provided solve the task. The only thing in which they differ is from which angle the attempt to solve the task. The author one goes from an empty set and adds only words that satisfy the given constraints (bottom-up approach). Yours goes from the set of all possible words and removes the ones that do not satisfy the constraint (top-down approach).

I would say his is more accurate **IF** you are not allowed to use $L$ or $\Sigma$, as it is often the case in exercise text books.
> 1 votes

---
Tags: formal-languages, strings
---


# Question
Title: A double recursive function (ping-pong) between function to itself complexity analysis
```
def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc( RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2) )

```

How should I start if it is nested inside? I know how to solve it without the outer `RecFunc` (with a recursive tree I assume) - But here there is an outer `RecFunc` and I don't know what to do!

---

Thanks to Steven for noticing a mistake I made (Misread the question and made it so `RecFunc(4)` will not halt)

# Answer
> 2 votes
Notice that the outer `RecFunc` call is just a "decoy" thrown in there to make the exercise seem more complicate than it is. Indeed, it is irrelevant as far as the **asymptotic** time complexity is concerned. This is because every call to `RecFunc` eventually returns $1$ (that's the only possible returned value, you can prove by induction that `RecFunc` eventually returns), and therefore the last (outer) call to `RecFunc` will just be `RecFun(3)`, which terminates in constant time. We can charge this constant time to the caller function. Since the caller is going to spend $\Theta(1)$ time anyway, this doesn't change anything.

Then you want to analyze:

```
def RecFunc(n):
   if n <= 3:
      return 1

   return RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2)

```

Whose running time is described by the recurrence equation: $$ T(n)=2T(n/2) + T(n/3) + \Theta(1), $$

which can be solved using the Akra–Bazzi method. Let $p$ such that: $ 2 \cdot \frac{1}{2^p} + \frac{1}{3^p} = 1. $ Clearly $p\>0$. Then: $$ \int\_{u=1}^n \frac{1}{u^{p+1}} \mathrm{d}u = \int\_{u=1}^n {u^{-p-1}} \mathrm{d}u = -\frac{1}{p} \cdot \left| u^{-p} \right|\_{u=1}^n = \frac{1}{p} \cdot \left( 1 - \frac{1}{n^p} \right) = \Theta(1), $$ and you have: $T(n) = \Theta(n^p)$. An approximation of $p$ is $1.3646$.

The space complexity is clearly $\Theta(\log n)$ since this is the maximum recursion depth.

# Answer
> 0 votes
It’s obvious that recfunc(n) + 1 if n \<= 3, then if n \<= 6, n \<= 12 etc. So recfunc(n) = 1 for all b, so we can calculate it in O(1).

---
Tags: time-complexity
---


# Question
Title: Must an optimization problem with a greedy algorithm belong to P?
If it is known that for some optimization problem there is a greedy algorithm that solves it and the solution includes sorting of input at the preliminary stage, is it necessarily true that the problem belongs to P?

I was told it is true that problems of this type must belong to P, but I have questions about whether this is true.

It seems to me that there should be many examples of optimization problems with non-deterministic greedy algorithms.

Are there in fact counterexamples to this claim or is it necessarily true?

# Answer
> 2 votes
If the greediness here means moving on the input based on a specified score, and **computation of the input item's score is polynomial**, the answer is yes. It is correct. Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the problem in polynomial time (by the greedy algorithm).

Notice that, the polynomial computability of the score is vital here. For example, if the computation of the score for each item will be an NP-complete/hard problem (for example if it is the minimum vertex covering of a graph), the statement will not be valid anymore.

---
Tags: complexity-theory, optimization, np-hard, greedy-algorithms, p-vs-np
---


# Question
Title: Alternatives for finding sources in a DAG
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of *Algorithms* by Dasgupta et al. states:

> ***Property*** Every dag has at least one source and at least one sink. The guaranteed existence of a source suggests an alternative approach to linearization:
>
> * Find a source, output it, and delete it from the graph.
> * Repeat until the graph is empty.

However, we can linearize the DAG by arranging the post numbers in decreasing order. Isn't this the alternative above the same thing? How else can we find sources if we don't have to pick the largest **post** number, which is the source?

Isn't deleting the source an extra step and therefore unnecessary? I assume that we have already run depth-first search to obtain the **pre** and **post** numbers.

# Answer
Use a priority queue to keep a list of all vertices with prioritization on in-degrees.

Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$.

Repeat until empty.

If the input graph is a DAG, this will give you a topological ordering.
> 1 votes

---
Tags: graphs, dag, depth-first-search
---


# Question
Title: Can a Turing machine or Push Down Automaton construct languages of type 3?
I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a language of type 3? The same for turing machine?

# Answer
The set of languages of type $3$ is a proper subset of the of languages of type $2$. In other words, a language of type $3$ is also a language of type $2$.

If some automaton can recognize languages of type $2$, then it can also recognize languages of type $3$.
> 0 votes

---
Tags: turing-machines, pushdown-automata, chomsky-hierarchy
---


# Question
Title: Is the calculation of infinite sums solvable by a computer?
The question is: I give the computer a sum, such as $\sum\_{n=1}^\infty\frac{1}{n^3}$, the computer is expected to return an elegant closed-form solution, because the answer may be irrational. Has this problem been solved using a computer? Or, has it been proved to be undecidable? Or is it open?

# Answer
> 2 votes
It's complicated. Some very broad classes have been solved completely, but that's still one way of saying that it's only been done for special cases. The book A=B by Wilf, Zeilberger and Petrovšek would probably interest you: it describes algorithms for some of these broad classes.

# Answer
> 1 votes
In the general case, this is undecidable, and it turns out the answer has nothing to do with being rational or irrational.

Consider a Turing Machine with state set $Q$ with a single halting state $H$. Let's define $isHalting(H) = 1$ and $isHalting(q) = 0 $ for $q \neq H$. Define $state(n,w)$ to be the state of the Turing Machine starting on input $w$ after $n$ steps.

Then consider the infinite sum $\sum\_{n=1}^\infty isHalting(state(n,w))$. If this sum is $0$, then the Turing Machine does not halt. If it's $\infty$ then the machine halts.

Now, if you're skeptical about the $state$ and $isHalting$ functions, that's fair, but it turns out that you can encode these steps, or any logical formula, in arithmetic using something called Gödel numbering.

So even without using any irrational numbers, it's undecidable to determine not only the result of an infinite sum, but just whether that sum is 0 or not.

Of course, like @PeterTaylor says, there are plenty of specific cases where you can compute it, and this is one thing thefield of computer algebra is trying to determine. But this is normal for undecidable problems: there are also plenty of *specific* times that we can figure out whether a given Turing Machine halts, or whether a program has a given property, etc.

# Answer
> 0 votes
There is a closed form solution if and only if the exponent is an even integer.

# Answer
> -3 votes
Given a general infinite series, the most a computer can do is calculate the partial sums (the sum of the first thousand terms or the first million terms, for example). And even then it can only calculate the approximate values of those partial sums, to some finite degree of precision.

Showing that an infinite series converges to some closed-form expression (such as

$\displaystyle \lim\_{k \rightarrow \infty} \sum\_{n=1}^k \frac{1}{n^2}= \frac{\pi^2}{6}$

for example) can only proved by mathematical reasoning. We do not know how to create a computer algorithm that will *originate* that reasoning (although a proof-checking algorithm could possibly validate the proof once it was found).

At best, a program can compare the partial sums of the series to values of combinations and functions of mathematical constants such as $\pi$, $e$ or $\sqrt{2}$ and *suggest* a closed-form solution if it finds a close match. This field of research is called experimental mathematics.

---
Tags: computability, real-numbers
---


# Question
Title: Does exponential time always beat polynomial time? $n^{\frac{1}{2}}$ vs $2^{\sqrt{log \,n}}$
I was told that exponential time **always** beats polynomial time but doesn't this not work for:

$n^{\frac{1}{2}}$ vs $2^{\sqrt{log \\,n}}$?

If we take $log\_2$ on both of them we get:

$\frac{1}{2}log \\,n \> \sqrt{log \\,n}$

which seems that what I was told is incorrect.

* Did I not hear the caveats?
* Have I mislabelled exponential and polynomial functions?
* If this view is wrong. What's greater $n^{\frac{1}{2}}$ or $2^{\sqrt{log \\,n}}$? How would you show it?

# Answer
> 2 votes
"exponential time **always** beats polynomial" we understand as for $a\>1$ and any $k\in \mathbb{R}$ we have $n^k \in O(a^n), n\to \infty$.

But if you consider substitution of $n$ with some arbitrary function, then, of course, generally, $n^{f(n)} \in O(a^{g(n)})$ will be wrong. We can even reverse functions with appropriate substitution: $n^{f(n)}=n^{\log\_na^n} = a^n $ and $a^{g(n)} = a^{\log\_a n^k} = n^k$.

Your example $\sqrt{n}$ vs $2^{\sqrt{\log\_2 n}}$ is not polynomial vs exponential, but polynomial vs some elementary function.

**Addition.** Now let's compare $\sqrt{n}=2^{\log\_2 \sqrt{n}}$ and $2^{\sqrt{\log\_2 n}}$. As exponential with base $2$ is strictly increasing, then it is equivalence to compare $\log\_2 \sqrt{n}$ and $\sqrt{\log\_2 n}$. Considering function $f(x)=\log\_2 \sqrt{x} - \sqrt{\log\_2 x}$, for $x\>1$, we have $$f'(x)=\frac{1}{2x\ln 2}-\frac{1}{2x\ln 2\sqrt{\log\_2 x}} = \frac{\sqrt{\log\_2 x}-1}{2x\ln 2\sqrt{\log\_2 x}}$$ So $f$ is decreasing on $(1,2)$ and increasing on $(2,+\infty)$. As it easy to see, that $f(1)=f(16)=0$, then we can conclude that on $(1,16)$ function is negative and on $(16,+\infty)$ function $f$ is positive, so $$\sqrt{n}=2^{\log\_2 \sqrt{n}} \gt 2^{\sqrt{\log\_2 n}}$$ for $n \gt 16$. This gives $2^{\sqrt{\log\_2 n}} \in O(\sqrt{n})$.

Additionally, if we consider $g(x)=\frac{\log\_2 \sqrt{x}}{\sqrt{\log\_2 x}}$, then $$\lim\limits\_{x \to +\infty}\frac{\log\_2 \sqrt{x}}{\sqrt{\log\_2 x}}= \lim\limits\_{x \to +\infty}\sqrt{\log\_2 x}=+\infty$$ which gives $2^{\sqrt{\log\_2 n}} \in o(\sqrt{n})$.

# Answer
> 1 votes
What does it mean "beat"? From the context, I'm deriving that in computational complexity it is said that a polynomial time is always better than an exponential time.

Now, if you look here a polynomial time is defined as $O(n^c)$, while an exponential time is defined as $O(c^n)$, where $c$ is a positive constant, and $n$ increases without bound.

Your example does not involve really an exponential and a polynomial. It is a polynomial and "something else". Since the $\log$ balances the exponential. Therefore it is not an exponential.

In order to see which function grows larger, you can even draw them. Just for the sake of the argument let's consider the inputs: 1, 10, 100 for $n$.

**Case $n = 1$**

Then you have that $n^\frac{1}{2}$ is $1$, while $2^\sqrt{\log n}$ is $1$.

**Case $n = 10$**

Then you have that $n^\frac{1}{2}$ is $3.16$, while $2^\sqrt{\log n}$ is $3.53$.

**Case $n = 100$**

Then you have that $n^\frac{1}{2}$ is $7.8$, while $2^\sqrt{\log n}$ is ~$6$.

So $n^\frac{1}{2}$ grows significantly faster. That is mainly due to the logarithm over the $2$.

So to reply to the question: which one of the two function is greater? It is up to which $n$. The first function grows faster, but for small values of $n$, the second function is bigger. The more $n$ grows, the more the first function will grow, therefore being greater than the second one.

# Answer
> 1 votes
You will easily see that the $\sqrt n$ function dominates (or "beats", in your words) the $2^{\sqrt \log n}$ function when $n \to \infty$ if you make the following substitution: $$n = 2^{k^2}$$ Then: $$\sqrt n=2^{\frac{k^2}{2}}$$ $$2^{\sqrt \log n}=2^k$$ So, the first one is larger than the second one when $k \to \infty$.

---
Tags: asymptotics, polynomial-time
---


# Question
Title: How can I implement a data structure which calculates the number of nested intervals in sub-linear time?
Is there a data structure which can maintain a list of intervals and the following operations?

```
insert(l, r): Inserts an interval [l, r] into the list
query(l, r): Return the number of intervals in the list which are completely nested in [l, r]

```

I need the data structure to handle inserting and querying without brute force (which would take linear time).

I saw this algorithm for counting the number of nested intervals for each interval here: https://stackoverflow.com/questions/12946497/sub-on2-algorithm-for-counting-nested-intervals but it appears to only calculate the answer for a static array of intervals.

# Answer
> 2 votes
Expanding on Dmitry's comment, you can maintain a balanced tree with the left endpoints of the intervals as the keys, and at each node store a balanced tree with the right endpoints as keys, and at each node of each of those trees store a count of intervals.

This requires $O(n\log n)$ space. Lookups are $O(\log^2 n)$. Insertions are tricky because when rebalancing the outer tree you have to rebuild the inner trees, but I think it can be made amortized polylog(n) if you rebalance sufficiently rarely, using a scapegoat tree for example.

If you know that the endpoints will belong to a set of size $k$, and you don't mind factors of $\log k$ in the insertion and lookup times, then you could use a radix tree for the outer tree and avoid the rebalancing logic.

---
Tags: data-structures, intervals
---


# Question
Title: Fast software pipelining for stream processing
I have a pipelined stream processing situation, where a number of streams is linked in the computational process `S0 -> S1 -> S2 -> ...`. You can understand "stream" as a list of numbers.

In this process, S0 is initially given in totality. S1 is a mapped result from S0 according to function `f`; S2 is the result from S1 by the same `f`, so on and so on. `f(S)` works by traversing stream `S` linearly and produces the resulting stream as it goes. Hence, `f` can work on a stream "partially": that is, for example, we don't need the totality of stream S1 in order to begin producing S2. The processing `S0->S1` can occur concurrently with `S1->S2` in a pipelined fashion.

I attempted implementing this pipeline using C. In my code, I use an atomic variable to synchronize progress between each pipeline stage $S\_i\quad\overrightarrow{\small f\_i}\quad S\_{i+1}$: basically, thread $f\_i$ constantly polls progress from the previous pipeline $f\_{i-1}$ to see if new tokens are written into $S\_i$. If so, it continues its own work. Otherwise, it spins and waits. Of course, this assumes each $f\_i$ is responsible for reporting its progress to $f\_{i+1}$. It turns out that this synchronization is too costly. I wasn't able to gain any speedup using multiple threads. In fact, it makes the code much slower than a single-threaded implementation.

My question is, what is a better approach to implement this construction in order to actually take advantage of multi-threading? This seems to be very hard because the $f$ in my scenario is computational-bound. It seems to me highly unlikely to extract parallel performance unless there is a very low-cost synchronization scheme. Thanks in advance for any comments and advice.

# Answer
> 1 votes
Do the work in batches. Have a separate buffer for each stream that stores the unprocessed items. When you invoke $f$ for stream $S\_i$, invoke 100 times on the 100 oldest items in the buffer for $S\_{i-1}$, then remove those items from the buffer. This basically increases the granularity of operations, and should reduce the overhead from synchronization by about 100x. You can of course tune the number 100 to adjust throughput vs latency.

---
Tags: parallel-computing, concurrency
---


# Question
Title: How page table base register (PTBR) is used to locate the correct frame using Page Number?
I was reading about paging in OS , and one of the things I saw was the page table base register (PTBR).

If the CPU generates a logical address (Consists of Page number + Offset) it needs to be mapped to Physical address (Consists of Frame number + Offset).

In the mapping process there must be first a lookup in the Page table of the process to get the Frame corresponding to that page.

Now to get to the page table we need to get the location of the page table of that process in the main memory.

The starting location of the page table is stored in a register called page table base register (PTBR).

Now the page number part of the logical address is added with the value in the PTBR and the corresponding frame is found in the table as the following:

Since the PTBR stores the base physical address of the page table in memory (e.g. 14000), and the logical address contains the page number that the CPU wants to read data from. Now here is my question:

> Is the page number part of the logical address is the starting address of the page?

For example: the virtual address is 16 bit and the size of each page is 1KB

page 0 ---\>starts at virtual address 0

page 1 ---\>starts at virtual address 1024

page 2 ---\>Starts at virtual address 2048

and so on ...

So if the CPU wants to read data from page 1, then the page number is "1024" and then this value is added to the value in the PTBR?

OR

The page number itself is added for example: if the CPU wants to read data from "page 1", then the number "1" represents the Page number value and when it is added to PTBR value? in other way does the CPU deal with page Number or Starting address?

I know this is silly for a lot of you, but it really got me confused because I couldn't find any real example about it.

# Answer
I'll take x86 32 bits PCs as an example. On 32 bits x86 PCs, the CR3 register is used as the PTBR. The CR3 register contains the 4KB aligned address of the page directory. The page directory contains addresses of the different page tables. The x86 processors have virtual addresses which are separated in 3 parts. The 10 most significant bits are the offset in the page directory, the 10 bits in the middle are the offset in the page table and the 12 last bits (to the right) is the offset in the physical page in RAM. Let's look at an example. Let's take address 0x12345678. This is a 32 bits address which translates in binary to 0001 0010 0011 0100 0101 0110 0111 1000. Now let's look at the different parts of this address.

```
Page directory offset        Page table offset        Physical page offset
   00 0100 1000                11 0100 0101             0110 0111 1000

```

So in the end this virtual address will translate to page directory entry `0b0001001000 = 0x72 = 114 decimal`, page table entry `0b1101000101 = 0x345 = 837 decimal` and the offset in the physical page will be `0b011001111000 = 0x678 = 1656 decimal`

Depending on what is the content of each selected entries by this virtual address, the actual physical address can be anywhere in RAM. In this example we have entry 114 in the page directory. If at entry 114 is written 0x1234, the MMU of the CPU will look there for the page table. It will use address 0x1234 as the bottom of the page table and then find entry 837 which could contain 0x12345. So the final physical address translated will be `0x12345 + offset_in_physical_page = 0x12345 + 0x678 = 0x129BD`. This will be the final physical address once translated using the example that we have here.

On more modern processors you will have 4 levels of page tables so the virtual address will be split in 5 parts. 4 parts of 9 bits to the left and 1 part of 12 bits. Only 48 bits are used for now with the leftover bits to be used later (once there are more page table levels).
> 1 votes

---
Tags: paging
---


# Question
Title: Why is crossing paths bad in Traveling Salesman?
I'm learning about Traveling Salesman in an online course (sorry I can't share the link it's paid only) and the first step to solving it then just state "as a heuristic we avoid crossed paths" and never really explained why. Why are crossed paths bad in traveling salesman?

# Answer
> 1 votes
The statement is for *Euclidean TSP* only, and as you mention yourself, it is only used as a heuristic.

But try to create an example yourself and see what happens when you have crossing links as part of your solution:

From Urban OR:

**Property 1:** The optimum traveling salesman tour does not intersect itself.

---
Tags: np-hard, np, traveling-salesman
---


# Question
Title: On the definition of Error-Correcting Codes
Let us start with the following well-known definition:

> ***Definition 1.*** Let $C\subseteq A^n$ be a code over $A$ and let $t\in \Bbb Z^+$ be a positive integer. We say that the code $C$ is $\boldsymbol t$**-error correcting** if nearest neighbour decoding is able to correct at most $t$ errors, assuming that if a tie occurs in the decoding process, a decoding error is reported. That is, if whenever $x \in C$ and $y\in A^n$ such that $\mathrm{d}(x,y)\leq t$, then $y$ is decoded to $x$ using nearest neighbour decoding.

Now let us make an observation.

> ***Remark.*** Recall that when there is no unique nearest codeword to $x\in C$, then nearest neighbour decoding *fails*. So, a code $C\subseteq A^n$ is $t$-error correcting if and only if whenever $y\in A^n$ is a word within distance $t$ of a codeword $x\in C$ (that is, $\mathrm{d}(x,y)\leq t$), then $$\mathrm{d}(x,y) \< \mathrm{d}(z,y), \quad \text{for all } x\neq z \in C.$$

The Remark gives us a more ***abstract** way to state the definition* of $t$-error correcting without mentioning nearest neighbour decoding.

However, I stumbled on another statement of the definition (which I found on some lecture notes on the web):

> ***Definition 2.*** The code $C$ is $t$**-error correcting** if there do not exist $x,z \in C$ such that $x\neq z$ and $y\in A^n$ such that $$\mathrm d(x, y)\leq t, \quad \mathrm d (z, y)\leq t.$$

**My question is why the last definition is equivalent to the first one (given with the form of the remark).**

*Could you please give me a hand?*

---

UPDATE: My attempt: Definition 1 tells us that $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x \implies d(x,y)\<d(z,y)).$$

Definition 2 tells us that $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(d(z,y)\leq t \implies z=x).$$ Equivalently, $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)\>t ).$$ Equivalently, $$(\forall x\in C)(\forall z \in C)(\forall y\in A^n)(d(x,y)\leq t)(z\neq x\implies d(z,y)\>t\geq d(x,y)).$$ So the Def2 $\implies$ Def 1. Is that correct? How about $\Longleftarrow$?

# Answer
Here is what the remark says:

> A code $C \subseteq A^n$ is $t$-error-correcting if for all $x \in C$ and $y \in A^n$ such that $d(x,y) \leq t$, all $z \in C$ other than $x$ satisfy $d(x,y) \< d(z,y)$.

When is a code *not* $t$-error-correcting according to this remark?

> A code $C \subseteq A^n$ is *not* $t$-error-correcting if there exist $x,z \in C$ and $y \in A^n$ such that $x \neq z$ and $d(z,y) \leq d(x,y) \leq t$.

Given $x,y,z$, either $d(z,y) \leq d(x,y)$ or $d(x,y) \leq d(z,y)$, and so, since the other constraints on $x,z$ are symmetric in $x,z$, the above definition is equivalent to

> A code $C \subseteq A^n$ is *not* $t$-error-correcting if there exist $x,z \in C$ and $y \in A^n$ such that $x \neq z$ and $d(x,y),d(z,y) \leq t$.

This is exactly Definition 2.
> 1 votes

---
Tags: coding-theory, error-correcting-codes, algebra, definitions
---


# Question
Title: Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program
I am trying to solve an LP in which one of the constraints is mentioned below, $$\max(x\_1,x\_2) \ge q,$$ where $x\_1 \ge 0$ and $x\_2 \ge 0$.

Is it possible to do in linear programming?

# Answer
> 4 votes
No. If you could do that in linear programming then you could force a variable to have binary values, so you'd be able to solve integer linear programs using LP solvers.

Indeed, we can simulate $x \in \\{0,1\\}$ with:

$$ \max\\{x, 1-x\\} \ge 1, \\ x \ge 0, \\ x \le 1. $$

---
Tags: discrete-mathematics, linear-programming, integer-programming
---


# Question
Title: The concept of the creation of a trapdoor in NP-complete or NP-hard problems
I am reading the book *An Introduction to Mathematical Cryptography*. In its chapter 7, there is the following statement:

> In real world scenarios, cryptosystems based on NP-hard or NP-complete problems tend to rely on particular subclass of problems either to achieve efficiency or to allow the creation of a trapdoor.

**Questions:**

Is is possible to explain what does it mean the phrase "*to allow the creation of a trapdoor*"?

Thanks for any help

# Answer
> 1 votes
A "trapdoor" function is a function which is hard to compute, but will become very easy (or a lot easier) to compute if you have some specific knowledge.

The classical example is solving y = x^3 (modulo n) where n is the product of two very large primes; it is the basis of RSA encryption and practically impossible to solve given x and n, unless you are given the two primes p, q such that n = pq.

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: Check if a relation is reflexive, symmetric and transitive
I want to better understand how this actually works, as my solutions are sometimes not 100% correct.

I have the following relation:

> Check if the following relation is reflexive, symmetric, and/or transitive:
>
> $$ R\_1 = \\{ (x,y) \mid x,y \in \mathbb{R}, x=0 \land y \geq 0 \\}. $$

so by that

$$ R\_1 = \\{ 00, 01, 02,03,04,05,06,07,08,09,010, \dots, 0R\_+ \\} $$

Basically $R\_1$ is 0 and any $R\_+$ number.

It is not reflexive, as $(a,a)$ is not in $R\_1$. I only have 00, but not 11 or 22 and so on.

It is also not symmetric, as I don't have 01 and 10 or 02 or 50 and 05. So $xRy$ and $yRx$ are not true for $R\_1$.

As for the transitivity, well, if $xRy$ and $yRz$ then $xRz$. Well, this one is hard to understand. I could use 00 as an example: If $y = 0$ and $z \geq 0$ then $xRz$ would work. So I would say it is transitive.

Can anybody confirm if this would be correct? If not, i would really appreciate a correct approach then for this task.

# Answer
> 1 votes
"If xRy and yRz": Look at the definition of R. You have x = 0 and y ≥ 0 because xRy. You have y = 0 and z ≥ 0 because of yRz. If you have xRy and yRz then you have x = 0 and z ≥ 0, therefore xRz. So R is transitive.

In total you know that x = 0, y = 0 and z ≥ 0, so you also have yRx, although nobody cares much about that.

---
Tags: relational-algebra, transitivity, relational-calculus
---


# Question
Title: PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:

$$L = \\{ncm \mid n,m\in\\{a,b\\}^\* \text{ and } n \ne m^R\\}.$$

Where $L \subseteq ({a,b,c})^\*$

So $n$ and $m$ are both a combination of any number of $a$'s and $b$'s, but $n$ is not the reverse of $m$.

Does anyone have some tips or advice, would be much appreciated!

# Answer
> 1 votes
If you want to read a word $w$ with a PDA, and know if $w\in L$ or not, then you could:

1. put the letters of $w$ in the stack of the PDA until you read a $c$;
2. read the $c$ without changing the stack. If there is no $c$, then $w\notin L$;
3. read the remaining of $w$:
    * if you read another $c$, then $w\notin L$;
    * if the stack is empty before the end of $w$, then $w\in L$;
    * if you reach the end of $w$ before the stack is empty, then $w\in L$;
    * if you reach the end of $w$ and the stack is empty, then $w\notin L$;
    * if the letter read in $w$ is different than the letter on the top of the stack, then $w\in L$;
    * if these letters are the same, then remove it from the stack and continue reading $w$.

# Answer
> 0 votes
This answer is for the original version of the question, in which "$k$" was missing.

Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.

# Answer
> 0 votes
Suppose that $w = ncm$, where $n \neq m^R$, say $n$'th $i$-th letter from the left, $\sigma$, differs from $m$'s $i$-th letter from the right, $\tau$. Then $$ w \in \Sigma^{i-1} \sigma \Sigma^\* c \Sigma^\* \tau \Sigma^{i-1}, $$ where $\Sigma = \\{a,b\\}$. Conversely, every $w$ of this form is in your language. You take it from here.

---
Tags: regular-languages, automata, finite-automata, pushdown-automata
---


# Question
Title: What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine?
As the question implies, can you mention any difference between Hidden Markov Model and Non-deterministic Finite-State Machine? Are they different or the same?

# Answer
Deterministic Finite State Machines have at most one trace for a given input. Nondeterministic Finite State Machines may have many traces for a given input. A Hidden Markov Model in some sense fits "in between" these extremes as the traces are probabilistic. With a Hidden Markov Model we do not have complete freedom to choose which trace to follow as we are governed by probabilities. A Hidden Markov Model is essentially a transducer-style Finite State Machine having outputs & transitions governed by a random process; the outputs generated at states are per a random variable model of what happens at that state, e.g., "if the weather is cloudy then 20% it will turn rainy / 80% it will turn sunny".
> 3 votes

---
Tags: finite-automata, hidden-markov-models
---


# Question
Title: How to show independence and uniform distribution of hash codes from k-wise independent hash functions?
Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x\_1, x\_2,\dots, x\_k \in D$ and $y\_1, y\_2,\dots, y\_k \in R$,

$$\mathbb{P}\_{h \in H}(h(x\_1) = y\_1, h(x\_2) = y\_2, \dots, h(x\_k) = y\_k) = \frac{1}{|R|^k}$$

The Wikipedia article on k-wise independent hash functions (which uses the above definition) claims that the definition is equivalent to the following two conditions:

(i) For all $x \in D$, $h(x)$ is uniformly distributed in $R$ given that $h$ is randomly chosen from $H$.

(ii) For any fixed distinct keys $x\_1, x\_2,\dots, x\_k \in D$, as $h$ is randomly drawn from $H$, the hash codes $h(x\_1), h(x\_2), \dots, h(x\_k)$ are independent random variables.

It is not obvious to me how one proves (i) from the above definition without explicitly assuming (ii) in the definition as well (and vice-versa). **How is the definition sufficient for proving both (i) and (ii)?**

# Answer
> 1 votes
Throughout, we assume that $|D| \geq k$.

Suppose that $H$ satisfies, for all distinct $x\_1,\dots,x\_k \in D$ and all $y\_1,\ldots,y\_k \in R$, $$ \Pr\_{h \in H}\[h(x\_1)=y\_1,\ldots,h(x\_k)=y\_k\] = \frac{1}{|R|^k}. $$ Now let $x \in D$ be arbitrary. Since $|D| \geq k$, we can find $x\_2,\ldots,x\_k \in D$ such that $x,x\_2,\ldots,x\_k$ are distinct. For each $y \in R$, $$ \Pr\_{h \in H}\[h(x)=y\] = \sum\_{y\_2,\ldots,y\_k \in R} \Pr\_{h \in H}\[h(x)=y,h(x\_2)=y\_2,\ldots,h(x\_k)=y\_k\] = \\ \sum\_{y\_2,\ldots,y\_k \in R} \frac{1}{|R|^k} = \frac{|R|^{k-1}}{|R|^k} = \frac{1}{|R|}. $$ This proves (i). To see (ii), let $x\_1,\ldots,x\_k \in D$ be distinct. Then for all $y\_1,\ldots,y\_k$, $$ \Pr\_{h \in H}\[h(x\_1)=y\_1,\ldots,h(x\_k)=y\_k\] = \frac{1}{|R|^k} = \prod\_{i=1}^k \frac{1}{|R|} = \prod\_{i=1}^k \Pr\_{h \in H}\[h(x\_i) = y\_i\]. $$

In the other direction, suppose that (i) and (ii) hold. Then for all distinct $x\_1,\ldots,x\_k \in D$ and $y\_1,\ldots,y\_k \in R$, $$ \Pr\_{h \in H}\[h(x\_1)=y\_1,\ldots,h(x\_k)=y\_k\] = \prod\_{i=1}^k \Pr\_{h \in H}\[h(x\_i) = y\_i\] = \prod\_{i=1}^k \frac{1}{|R|} = \frac{1}{|R|^k} . $$

---
Tags: probability-theory, hash
---


# Question
Title: How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{\**} \cong G$. However, all those references either say that this fact is trivial, or give the proof as an exercice.

I am ok that this is clear on a small graph, with a nice embedding, but how can we prove this property rigorously?

# Answer
> 2 votes
**Work In progress.**

Feel free to contribute filling up the arguments that are incomplete.

---

## Definitions:

Before proving anything we need to make it precise what is it what we are trying to prove.

* **Planar graph:** A graph that can be embedded in $\mathbb{R}^2$.(1)
* **Plane graph:** A planar graph together with a particular embedding $G\hookrightarrow\mathbb{R}^2$. I will call a plane graph just by the name $G$ of the graph itself. We call **faces** of a *plane graph* to the connected components of the complement $\mathbb{R}^2\setminus G$. We can also assume the *plane graph* embedded in the two dimensional sphere $S^2$. That way we don't need to distinguish one of the faces which will be unbounded in the plane.
* **Polygon:** A simple closed path in a graph without a proper closed subpath.
* **Cut-set:** A minimal set of edges of a graph that, if removed, would increase the number of connected components of the graph.
* **Combinatorial dual:** A graph $G^\*$ is said to be a combinatorial dual (sometimes also called algebraic dual) of another graph $G$ if there is a bijection between their edges such that the polygons of one of them correspond to the cut-sets of the other, and vice versa. A graph can have no combinatorial duals, or it can have multiple non-isomorphic combinatorial duals.
* **Geometric dual:** A geometric dual $G^\*$ of a *plane graph* $G$ is a graph obtained by placing a vertex on each face of $G$. There is going to be an edge of $G^\*$ for each triple $(f\_1,f\_2,e)$ where $f\_1,f\_2$ are faces of $G$ such that their closures contain the edge $e$ of $G$. The edge corresponding to this triple will be embedded in such a ways that it connects the vertices of $G^\*$ inside $f\_1$ and $f\_2$. It will be contained in $f\_1\cup f\_2\cup e$ and intersects $e$ only at one point that it is not a vertex of $G$. For this definition to make sense a couple of results from topology are needed. In particular, two results that are quite intuitive, but very hard to prove. These are Jordan curve theorem and Jordan-Shoenflies theorem. Using these results it can also be proven that the geometric duals of a plane graph are isomorphic. So, we can talk about *the* geometric dual of a *plane graph*.

It is a theorem of Whitney that a graph is planar if and only if it has a combinatorial dual. Moreover, each combinatorial dual of a planar graph arises as a geometric dual of an embedding of the graph in the plane.

---

## $G^{\**}=G$

As you see above, this statement can mean different things. It could mean that $G$ is a connected *plane graph* and we are taking geometric dual a couple of times. It could also mean that $G$ is a *planar graph* and we are taking geometric dual a couple of times after fixing an embedding. Finally it could mean that we are taking combinatorial dual a couple of times of a connected *planar graph*.

**Note:** We also need to use the modern definition of connected in which the empty graph $0$ is not connected. Note that the dual of the empty graph is $K\_1$ and the dual of $K\_1$ is itself. So, $0^{\**}=K\_1\not\cong 0$. I am making the clarification because although it is becoming more widespread defining the empty graph as not connected, still not everyone does that.

---

## Geometric double dual.

I think this one is the simplest, assuming that we leave the topological results as known. Assume that $G$ is a *plane graph* and $G^\*$ is its geometric dual. We assume $G^\*$ to be a *plane graph*, which embedding satisfies the properties that we mentioned in the definition above. Let's do induction.

If $G=K\_1$ we have that $G^\*=K\_1$, just another point of the plane, and therefore $G^{\**}\cong G$. Then $G^{\**}\cong G$.

We want to assume that the theorem is true for all graphs that have smaller number of vertices or edges than $G$. The following two lemmas allow use to construct the isomorphism by removing vertices of $G$ of degree $1$ or edges that are not cut edges. Then we just extend or modify the isomorphism that we have from the inductive assumption on the smaller graph. The lemmas below are quite intuitive, but they make use of Jordan's curve theorem. So, the main annoying thing to write down the arguments is to make it as explicit as possible the point in which this big theorem is used.

**Lemma 1:** Assume $G$ is connected plane graph with an edge $e$ that is not a cut edge of $G$. Assume that $(G\setminus e)^{\**}\cong G\setminus e$. Then $G^{\**}\cong G$.

**Proof:** Since $e$ is not a cut edge, the two faces2 of $G$ incident with $e$ are different. Call those faces $f\_1$ and $f\_2$. Deleting $e$ from $G$ fuses $f\_1$ and $f\_2$ into a single face $f$. Faces of $G$ that are adjacent to $f\_1$ or $f\_2$ become adjacent to $f$ in $G\setminus e$. In the dual, the vertices $f\_1^\*$ and $f\_2^\*$ of $G^\*$ get replaced by a single vertex $f^\*$ of $(G\setminus e)^\*$. Any vertex of $G^\*$ that is adjacent to $f\_1^\*$ or $f\_2^\*$ is adjacent to $(G\setminus e)^\*$. Therefore, the function sending $f^\*$ to the identification of $f\_1^\*$ and $f\_2^\*$ in $G^\*/e^\*$ and that is the identity on all other vertices is an isomorphism. ... $\square$

**Lemma 2:** Assume that $G$ is a plane graph that has a vertex $v$ of degree $1$ and that $(G\setminus v)^{\**}\cong G\setminus v$. Then $G^{\**}\cong G$.

**Proof:** Since $v$ has degree $1$, then it is adjacent to only one face $f$ of $G$. If $e$ is the edge of $G$ incident on $v$ and $f^\*$ is the vertex in $G^\*$ that is in $f$, then there is a loop $e^\*$ incident on $f^\*$ that contains in its interior $v$ and no other vertex of $G$. Here we are implicitly using Jordan's curve theorem. By assumption $(G\setminus v)^{\**}\cong G\setminus v$. By jordan's curve theorem the interior of $e^\*$ is a face $v^\*$ of $G^\*$ and this face is adjacent to exactly another face. Therefore, extending the isomorphism of $(G\setminus v)^{\**}$ and $G\setminus v$ by sending $v$ to $v^\*$ and $v^\*$ to $v$ give us an isomorphism of $G^{\**}$ and $G$. ... $\square$

To complete the induction observe that we can apply Lemma 1, if the graph has some non cut-edge. If $G$ has no non cut-edges, then it must be a tree. So, we can apply Lemma 2, as long as $G$ has more than one vertex. If it is a tree and has one vertex, then it is $K\_1$, which is the base case.

---

### Combinatorial double dual

For this we use Whitney's theorem. If $G$ is a connected *planar graph* and $G^\*$ a *combinatorial dual*, then there is an embedding of $G$ and $G^{\*}$ such that $G^\*$ is the geometric dual of $G$. From the proof above it follows that $G$ is a geometric dual of $G^\*$ and therefore a combinatorial dual of $G^\*$. Now assume that $G^{\**}$ is a combinatorial dual of $G^\*$. Consider an embedding of $G^\*$ and $G^{\**}$ such that $G^{\**}$ is a geometric dual of $G^\*$. Using Jordan-Shoenflies theorem we can extend ... \[This one seems harder. I don't have a complete plan yet. We probably need to extend the new embedding of $G^{\*}$ (in which $G^{\**}$ is a geometric dual) to embed also $G$ and show that it is also a geometric dual of $G^{\*}$ in this embedding.\]

### Footnotes:

1. The topology on the graph is that of a CW-complex.
2. There are at most two faces incident on an edge. This follows from Jordan-Shoenflies theorem.

# Answer
> 1 votes
You can probably locate a copy of Bondy and Murty's book *Graph Theory with its Applications*. While they don't prove it either, they give the following intuition:

Let $G$ be a (connected) plane graph and $G^\*$ its dual. There is a natural embedding of $G^\*$ in the plane that corresponds to $G$, namely that each vertex $f^\*$ in $G^\*$ is placed in the corresponding face $f$ of $G$, and each edge $e^\*$ is drawn such that it only crosses the corresponding edge $e$ in $G$ and it crosses it exactly once.

---
Tags: graphs, planar-graphs, connected, duality
---


# Question
Title: Applying Akra–Bazzi with an unbounded number of summands
The Akra–Bazzi method handles recurrences of the form $$ f(n) = \sum\_{l=1}^k a\_l f(n/b\_l). $$ Does it work when then number of $a \cdot f(n/b)$ is not finite, meaning that we have a sum that depends on our input $n$?

What about this:

$$ f(n) = \sum\_{l=1}^{n} f(n/3^l) $$

Can I say that we need to find the $p$ so that

$$ \sum\_{j=1}^{n} (\frac{1}{3^j})^p =1,$$

and because $n \rightarrow \infty$ we can say it is an infinite geometric sum? Or because $n$ is our input we can't say that, and the Akra–Bazzi method fails to deal with this kind of stuff? There is no internet site I found that says $k$ (which in Wikipedia is the number of $f(n/b)$) needs to be finite.

# Answer
> 2 votes
Quoting from Wikipedia, the Akra–Bazzi method applies to recurrences of the form $$ T(x) = g(x) + \sum\_{i=1}^k a\_i T(b\_i x + h\_i(x)) $$ where $a\_i,b\_i$ are constant, $a\_i\>0$, $0\<b\_i\<1$, $g$ is polynomially bounded, and $h$ is "sublinear enough".

Your recurrence is not of this form, so you cannot apply the Akra–Bazzi method. It could be that the techniques used to prove the Akra–Bazzi theorem also apply to your case, but you will have to look at the proof.

---

Notice that $$ f(n) - f(n/3) = \sum\_{i=1}^{\log\_3 n} f(n/3^i) - \sum\_{i=1}^{\log\_3 (n/3)} f(n/3^{i+1}) = f(n/3), $$ and so $f$ satisfies the recurrence $$ f(n) = 2f(n/3). $$ In particular, $$ f(n) = 2^{\log\_3 n} f(1) = n^{\log\_3 2} f(1). $$ (Throughout, we are assuming that $n = 3^k$.)

---
Tags: recurrence-relation
---


title: What are skew arithmetic circuits?

text:
# Question
Title: What are skew arithmetic circuits?
I am trying to understand the definition of skewed circuits in these slides which is given as follows:

> A circuit is *skew* if in each product gate, at least one product has degree $\le 1$.

I think author wants to say that each product gate is either a leaf node or one level above the leaf node.

# Answer
Skew arithmetic circuits are usually defined a bit differently: in every multiplication gate, one of the inputs of the gate is a constant or an input of the circuit (we assume that multiplication gates are binary).

This is very similar to your definition, if *linear* is interpreted as *syntactically linear*. That is, one of the inputs of any multiplication gate is either a constant, an input of the circuit, or the output of an addition gate whose inputs are inputs of the circuit or constants. Using the distributive rule, we can take a circuit satisfying this definition and turn it into a circuit satisfying the usual definition.

Another interpretation would be that one of the inputs of any multiplication gate is a linear function of the inputs, that is, it is *semantically* linear. For example, $(a+b)^2-(a-b)^2$ is semantically linear but not syntactically linear. This is probably not the interpretation which is meant here.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Detecting errors changing an odd number of bits using CRC
I was studying CRC from lecture notes of Schwarzkopf but I am stuck at this statement:

> If $G(x)$ is a factor of $E(x)$, then $G(1)$ would also have to be $1$.

What does this statement means? It is the third point in the third last block of the article whose link is given. I know a similar question is asked but that is a specific question. I want to understand this particular statement.

# Answer
Recall that we are working modulo $2$. Thus $E(x)$ is a polynomial whose coefficients are $0,1$, and $E(1) \in \\{0,1\\}$.

By definition, $G(x)$ is a factor of $E(x)$ if there exists a polynomial $H(x)$ such that $E(x) = G(x) H(x)$.

In this case, we assume that $E(1) = 1$. Since $E(1) = G(1) H(1)$, this forces $G(1) = 1$.
> 1 votes

---
Tags: crc
---


# Question
Title: Is it possible to make a grammar LL($1$) which recognizes palindroms?
Is it possible to make an algebraic grammar LL($1$) which recognizes palindroms for an alphabet $\\{a,b\\}$?

# Answer
> 3 votes
No. The language of palindromes over any alphabet with at least two elements is not deterministic, and thus has no LR or LL grammar.

The language of even-length palindromes $L\_{epal}=\\{ww^R \mid w\in\Sigmạ^\*\\}$ is a classic example of a non-deterministic context-free language, and you can find the outline of a proof in Hopcroft & Ullman (and other standard texts). The restriction to even-length palindromes simplifies the proof, but it can be extended to the language of all palindromes $L\_{pal}=\\{w \mid w=w^R, w\in\Sigmạ^\* \\}$. Without doing more work, though, it's evident that $L\_{epal}=L\_{pal}\cap (\Sigma\Sigma)^\*$, and deterministic CFLs are closed against intersection with regular languages.

---
Tags: formal-grammars
---


title: Bin packing when items can be broken

text:
# Question
Title: Bin packing when items can be broken
In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break some items then it becomes easy, since each bin can be filled completely.

What if we are allowed to break (to as many pieces as we like) only $k$ items of our choice, where $k$ is a fixed constant - is the problem still NP-hard?

# Answer
Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can subtract a small enough constant from this item's size.

Consider an instance of $3$-partition in which $3n$ positive integers $x\_1, x\_2, \dots, x\_{3n}$ of total sum $S$ need to be partitioned into $n$ triples $t\_1, \dots, t\_n$, each with total sum at most $T=\frac{S}{n}$, where $T$ is also an integer.

Assume that $x\_i \ge \frac{2T}{7}$ (it is known that the problem remains strongly NP-complete in this case). Furthermore assume that $n \> \max\\{8,T+1\\}$ (if this is not the case, multiply each integer in the instance by $10$, add many copies of the integers in $\\{10T-2, 1, 1\\}$ to the input, and then convert the resulting instance into an instance that satisfies $x\_i \ge \frac{2T}{7}$. This conversion multiplies the new value of $T$ by $7$).

Consider the instance of your version of bin-packing in which $k=1$ and you need to pack the set of elements $Y = \\{y\_1, \dots, y\_m\\}$ into the fewest number of bins of capacity $n T$ (you can set the capacity of each bin to $1$ by a suitable scaling of all the involved quantities). Let $m=3n+1$, $y\_m = nT$ and $y\_i = (n-1) x\_i$ for $i=1,\dots,3n$.

**If the $3$-partition instance is a yes-instance then $Y$ can be packed into $n$ bins.**

Create a bin $b = (y\_i, y\_j, y\_h)$ for each triple $t = (x\_i, x\_j, x\_h)$ of a solution of $3$-partition. Notice that $y\_i + y\_j + y\_h = (n-1) (x\_i + x\_j +x\_h) = (n-1)T$, leaving $b$ with unused capacity of $T$. The only element not assigned to a bin is $y\_m$. Split $y\_m = nT$ into $n$ pieces of size $T$ each, and add a piece to each of the $n$ bins.

**If $Y$ can be packed into $n$ bins then the $3$-partition instance is a yes-instance.**

Notice that $\sum\_{i=1}^m y\_i = (n-1) \sum\_{i=1}^{3n}x\_i + nT = (n-1)nT + nt = n \cdot nT$, showing that each each of the $n$ bins must be completely full.

We can assume w.l.o.g., that if some element is split into pieces, this element is $y\_m$. Indeed, if an element $y' \neq y\_m$ is split, there must be one bin $b'$ that is used entirely for $y\_m$. We can then swap each piece of $y'$ with a piece of $y\_m$, so that $y'$ is now entirely contained in $b'$.

Notice now that each bin $b$ must contain exactly $3$ elements from $\\{ y\_1, \dots, y\_{3n}\\}$. Indeed, if this was not true there would exist a bin that contains at least $4$ elements from $\\{ y\_1, \dots, y\_{3n}\\}$ and its used capacity would be at least $$ 4(n-1)\left(\frac{2T}{7}\right) = \left( \frac{8}{7}n - \frac{8}{7} \right)T \> nT. $$

We construct a solution for the $3$-partition instance by creating a triple $t = (x\_i, x\_j, x\_h)$ for each bin $b$ containing $y\_i, y\_j, y\_h$ with $i,j,h \le 3n$. The total weight of $t$ is at most: $$ x\_i + x\_j + x\_h = \frac{y\_i + y\_j + y\_h}{n-1} \le \frac{nT}{n-1} = \frac{(n-1)T+T}{n-1} = T + \frac{T}{n-1} \< T+1, $$ i.e., $x\_i + x\_j + x\_h \le T$.
> 4 votes

---
Tags: optimization, np-hard, combinatorics, packing
---


# Question
Title: What is a "negative function" withing algorithms?
I am currently studying the book 3rd edition CLRS Algorithms textbook, Chapter 3. I had the exact same question as this post but I have one more question now:

**What is a negative function?**

These functions are estimates that describe the time it takes to perform a function (an algorithmic sequence) onto a list. How can the function be negative if it describes the time it takes to do work? Can an algorithm sort a list 10 seconds before it starts?

# Answer
> 1 votes
The big-O notation (and also similar notations, such as big-Omega) are not inherently limited only to describe running time of algorithms. Indeed, when the context is the running time of some algorithm, there are no negative functions since algorithms cannot run "negative time".

That being said, the big-O notation is a general mathematical definition. It could be used for other things as well, as shown in this Wikipedia page.

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


# Question
Title: Problem on finite state machines in the feynman textbook
I'm currently reading Feynman Lectures on Computation and got stuck in problem 3.1 which says

> Suppose we feed a sequence of 1's and 0's - a binary number - into a machine. Design a machine which performs a pairwise sum of the digits, that is, one which takes the incoming digits two at a time and adds them, spitting the result out in two steps. So, if two digits come in as 00, it spits out 00; a 10 or 01 results in a 01 (1+0 = 10+11!); but a 11 results in binary 10: 1+1 = 2, in decimal, 10 in binary. I will give you a hint: the machine will require four states.

I don't ask you the answer. Just I don't understand what this is asking. For example, when the input sequences are `(00)(01)(10)(11)(10)(00)`, output sequences should be what?

Thanks in advance.

# Answer
The numbers are encoded LSB first. In your example, $(00)(01)(10)(11)(10)(00)$ corresponds to the addition $011100 + 001010$, and the answer should be $011001(0)$, corresponding to the binary answer $(0)100110$. The bit in parentheses is the carry bit, which I don't think Feynman intended you to output.

More generally, Feynman wasn't very accurate, so you should think of a reasonable concrete interpretation of the problem which will result in an automaton which has a small number of states; I can think of several, some of which requiring less than four states. (It depends whether $(00)$ is a *single* digit or a *pair* of consecutive digits.) I don't think it's very important to guess what Feynman intended exactly.
> 3 votes

# Answer
I agree that Feynman was not very accurate. But I am not sure Yuval's interpretation is correct, particularly because in problem 3.3 in the same section Feynman asks for the binary adder Yuval describes.

For problem 3.1, it isn't clear to me if the sequence (00) is entered as a single digit or two consecutive digits. It is also unclear to me if the input is (11) that the output (10) needs to be output over two states (e.g. output '1' at t=n, and then '0' at t=n+1) or over a single state (output '10' at t=n). If the sequence is entered 1 digit at a time, and the output must also be 1 digit at a time, then there is no way to make this machine using 4 states and not incorporating a delay.

The question RFP was asking remains ambiguous...
> 0 votes

---
Tags: automata, finite-automata
---


# Question
Title: What's the difference between a stream and a queue?
What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of 'insert'/'extract' (streams) vs. 'enqueue'/'dequeue' (queue). Are these interchangable? Do they suggest different concepts or patterns? If so, what are the differences?

---

Concrete example of 'stream insertion': https://www.cplusplus.com/reference/ostream/ostream/operator%3C%3C/

---

Potentially useful conceptual pieces?

# Answer
> 5 votes
A `queue` is an abstract data type with two operations: `enqueue()` and `dequeue()` (or sometimes `push()` and `pop()`) that have first-in-first-out semantics.

A C `stream` is hard (for me) to describe abstractly. My best cut at it is that it is an abstraction representing a buffered file (where "file" is understood in the Unix sense of the word as something that is usually (but not always) a sequence of bytes and a current file position.)

At it's most general a stream is like a sequence of bytes numbered from 0, that can be arbitrarily extended at the end, but that has some additional state (the current position). There are some basic operations (`fread()` and `fwrite()`) that read or write an arbitrary number of bytes starting at the current position, and then reset the current position to point just after the most recently read or written byte. The current position can also be changed with `fseek()` and queried with `ftell()`.

Now here's where it gets "icky." At the time a stream is opened a variety of factors determine which of the above operations are enabled or disabled. If you open your stream only for read then calling `fwrite()` will cause an error. If you open your stream only for write then calling `fread()` will cause an error. If your stream is actually a pipe or a socket, or is opened in mode append then you are not allowed to `fseek()`. You are only allowed to read or write from the current file position. `stdin`, `stdout`, and `stderr` are pipes so you can't `fseek()` them. You can't `fwrite()` `stdin` and you can't `fread()` `stdout` or `stderr`.

C++ fixed most of that mess by giving us a hierarchy of types (for example: http://www.cplusplus.com/reference/istream/basic\_iostream/), so that we can do error recovery with RAII and can also tell whether the file is readable or writable by looking at the type (although I don't know offhand whether they fixed the seeking mess.)

But then there's the whole other question of formatted output. C has `fprintf()` which formats some stuff and puts some bytes into a writable stream (starting at the current file position). C++ replaced `fprintf()` with the (IMHO) really-much-too-cute `operator<<()`. `operator<<()` has the advantage of being strongly typed, but the extreme *disadvantage* of requiring the use of `manipulators`. So `operator<<()` puts some bytes to the output stream starting at the current file position, but formatted based on a whole bunch of state that is mutated by manipulators. So a C++ stream actually has a bunch of extra state that you need to know about. (Whether integers are going to get formatted hex or decimal from now on, how much precision floats are printed with, etc.)

**So:** a `queue` inserts and removes individual items of a well defined type from its front or its back. A `stream` is random access extendable array of bytes where you can read and write arbitrary numbers of bytes from the current file position (except when it isn't random access and except when you either can't read or can't write).

# Answer
> 1 votes
In a way, they are opposites.

A stream is something you read data from or write data to, indefinitely. Yes, a stream may be closed, but you don't know whether or when that will happen.

A stream is not an entity on your system that holds, or produces, or stores data. Rather, it is a gateway, a pipe, that can be attached to such an entity.

There is a strong tradition in Unix programming to be as agnostic as possible about what's attached to it. For instance, Unix utilities typically read from standard input and write to standard output, with as few assumptions as possible regarding what that input comes from or what that output goes to. The term *stream* suggests an input source or output sink treated like that.

A queue, on the other hand, *is* an entity in your system that holds data. It can be written to and can be read from, but it is not a stream, or a pair of streams; rather, it is something that streams can connect to. A queue acts as a buffer, holding the data written to it and releasing the data when read, in FIFO order.

To use a fairly flaky analogy: when comparing software to electrical circuits, a stream is like a connector (current can flow into it or out of it, and we don't know what's going to be at the other end) while a queue is like a capacitor.

---
Tags: terminology, data-structures
---


# Question
Title: Formal Grammar: derivation form posted on Wiki?
Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step". I have a question on the condition when there are multiple productions for a single non-terminal.

Wiki defines $G = (N, \Sigma, P, S)$ and $\underset{\mbox{G}}{\implies} \subset (\Sigma \cup N)^\* \times (\Sigma \cup N)^\*$ where:

$(\underset{\mbox{G}}{x \implies y}) \iff \exists u,v,p,q \in (\Sigma \cup N)^\* : (x = upv) \land ((p, q) \in P) \land (y = uqv)$

Then $(\overset * {\underset{\mbox{G}}{x \implies y}})$ is defined as the refexive transitive closure. Therefore applying $\underset{\mbox{G}}{\implies}$ multiple times results in the language of the grammar:

$\\{w \in \Sigma^\* | (\overset * {\underset{\mbox{G}}{S \implies w}})\\}$

**QUESTION**

For the form $(\underset{\mbox{G}}{x \implies y})$ I consider the case of multiple rules $(p,q\_0), (p, q\_1) \in P$ for a non-terminal $N$. If solving for $y$, $y$ will result in the string with only a single rule applied. How should the derivation happen with multiple production rules?

I can see that supplying both arguments $(\Sigma \cup N)^\* \times (\Sigma \cup N)^\*$ to $\underset{\mbox{G}}{x \implies y}$ will yield all derivations.

# Answer
You seem to be looking for a deterministic procedure that isn't there.

With multiple production rules, you solve in every possible way. For instance, for the grammar

$S \rightarrow a \\ S \rightarrow aS$

we have

$ \underset{G}{S \implies a}, \\ \underset{G}{S \implies aS}, \\ \underset{G}{aS \implies aa}, \\ \underset{G}{aS \implies aaS}, \\ \ldots $
> 2 votes

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


# Question
Title: fastest way to identify "singular row" of a matrix
Suppose I have a matrix that I know to be singular. This means that there is at least one row in the matrix which is a linear combination of the other rows. What is the fastest way to identify which row that is or which rows they are?

I'm aware that the solution to this problem is not unique in general. The goal is to determine a set of rows which, if removed, leave only linearly independent rows. Then, more linearly independent rows can be added to get a non-singular matrix. Obviously I'm leaving out a bit of context regarding why I would be doing this, but I believe I have included everything relevant to the question.

My thinking is basically to attempt to attempt Gram Schmitt and just mark whatever step returns a zero vector. I doubt there's a faster approach than this, but suspect this problem has been studied to the point that a definitive answer exists.

Edit: To be clear, I only want to find a minimal set of rows such that, if they are removed, I get back a linearly independent set of vectors.

Also, let me give an example of the algorithm that I am proposing. I'm using an example given by nir shahar but slightly modified.

Suppose I have a matrix with rows (1, 0, 0), (0, 1, 0), (1, 0, 0)

The Gram Schmitt algorithm returns first: (1, 0, 0) second: (0, 1, 0) - 0 * (1, 0, 0) third: (1, 0, 0) - 1 * (1, 0, 0) - 0 * (0, 1, 0)

I'm not actually returning this set of vectors. All I care about is the fact that the third step returns the zero vector. So, I flag the third row as being a "problem."

# Answer
> 2 votes
This is not an answer, but a response to this comment.

Assume that $A$ is the matrix which columns are the rows that we want to test for linear independence. I am putting them are columns for no other reason than personal comfort.

Doing the row transformations required in Gaussian elimination correspond to multiplying $A$ from the left by some elementary matrices. Assume that $T$ is the product of all elementary matrices corresponding to the row transformations needed to put $A$ in echelon form. So, $TA$ is is echelon form.

If each column has an echelon then the system $TAx=0$, with $x$ a column vector of the right size, has only the solution $x=0$. Since $T$ is invertible, we have that $Ax=0$ has only the solution $x=0$. Since $Ax$ is nothing else than a linear combination of the columns of $A$ using the components of $x$ as coefficients, what we got is that the columns of $A$ are linearly independent.

Now assume that some columns of $TA$ don't have echelons. Let's call these the dependent columns. You can give any values you want to the components of $x$ corresponding to the positions of the dependent columns and then solve the resulting system $TAx=0$ for the remaining components, by backward substitution. In particular we can put non-zero values to the components of $x$ corresponding to the dependent columns of $TA$. This gives you a solution of $TAx=0$. Since $T$ is invertible, it is also a solution of $Ax=0$. For this $x$ the expression $Ax$ is a linear combination of the columns of $A$ that is equal to zero and the coefficients of the dependent columns are non-zero. So, the equation $Ax=0$ expresses each of the dependent columns in terms of all the other columns.

So, the dependent columns are linearly dependent of the columns with echelon in them (independent columns).

---
Tags: linear-algebra, numerical-algorithms
---


# Question
Title: A question about domains in Karp reductions
A basic question or request for clarification regarding Karp reducibility:

Let $\Sigma^\*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^\*$ a *language*. Let $\Pi$ denote the set of all functions from $\Sigma^\*$ into $\Sigma^\*$ that are computable in polynomial time. According to Karp, a language $L$ *is reducible to* a language $M$, also denoted $L \leq\_K M$, if there is a function $f \in \Pi$ such that $f(x) \in M \Leftrightarrow x \in L$.

For many problems, however, we are interested in the difficulty of determining membership in subsets of domains other than $\Sigma^\*$. To address this, Karp briefly discusses encodings: Given a domain $D$, there is often a natural "one-one" encoding, $e: D \rightarrow \Sigma^\*$. He then says that given a set $T \subset D$, $T$ is *recognizable in polynomial time* if $e(T) \in \mathcal{P}$. But don't we, in practice, typically consider $T$ to be recognizable in polynomial time if, for any $x \in D$, we can determine whether $x \in T$ in polynomial time? On the face of it, this doesn't seem to be the same as Karp's definition, since there is no guarantee that $e(D) = \Sigma^\*$.

Similarly, according to Karp, $T \leq\_K U$ where $T \subset D$ and $U \subset D'$ if $e(T) \leq\_K e'(U)$ where $e: D \rightarrow \Sigma^\*$ and $e': D' \rightarrow \Sigma^\*$. However, when we are actually proving $T \leq\_K U$ for some real $T$, $U$, $D$, and $D'$, don't we frequently just define an $f: D \rightarrow D'$ computable in polynomial time, confirm that $f(x) \in D'$ for any $x \in D$, and show that $f(x) \in U \Leftrightarrow x \in T$ for any $x \in D$? Again, this doesn't seem to be the same thing as Karp's definition if $e(D) \neq \Sigma^\*$.

What am I missing?

# Answer
> 1 votes
Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^\*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can recover $G$ and $k$ in polynomial time. The language $L$ consists of all encodings $e(G,k)$ of graphs $G$ containing a vertex cover of size $k$. If a string is not in the range of $e$, it is not in $L$.

Now suppose that you have a reduction $f$ from the domain $D$ of vertex cover to the domain $D'$ of SAT, and let $e\colon D \to \Sigma^\*$ and $e'\colon D' \to \Sigma^\*$ be encodings of these domains. We can construct a reduction $g$ from the language $L \subseteq \Sigma^\*$ of vertex cover to the language $L' \subseteq \Sigma^\*$ of SAT as follows. Given a string $w \in \Sigma^\*$, we first check whether it is in the range of $e$. If not, we output some fixed string not in $L$' If it is, we output $e'(f(e^{-1}(w)))$; that is, we decode $w$, apply $f$, and then encode the result.

Most of the time, such encoding details can be ignored. This is the case since we're working in a computation model which is strong enough to be oblivious to such matters. This is why we usually don't bother with these issues too much.

---
Tags: complexity-theory, formal-languages, reductions, encoding-scheme
---


# Question
Title: Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$
I tried many grammars and so far I got this one:

\begin{align} &S \to aXbZ \mid abc \\ &XZ \to Ybcc \\ &Xb \to bX \\ &bY \to Yb \\ &aY \to aa \mid aaX \end{align}

Is my grammar correct? Is there a simpler one?

# Answer
> 0 votes
Edit: my answer applies to the first post before modification.

It seems to me that your grammar is not correct. For example, if you use the first rule for $S$ and then the second rule for $S$, you get $aabcXY$ and no rule can be applied from there.

Inspired by what you proposed, it seems that the following rules are right : $$S \rightarrow aSXY | abc$$ $$cX \rightarrow Xc$$ $$bX \rightarrow bb$$ $$cY \rightarrow cc$$ The first rule guarantees that there are as many $a$'s as there are ($b$ and $X$) and ($c$ and $Y$). The third rule move $X$'s to the left until it is next to a $b$. The last 2 rules replace $X$'s with $b$'s and $Y$'s with $c$'s.

# Answer
> 0 votes
Your grammar is not correct. To see this notice that no sentence generated by your grammar can have more than two "c"s.

Indeed, the only productions that generate one or more occurrences of "c" are $S \to abc$ and $XZ \to Ybcc$.

Clearly, if $S \to abc$ is used, the resulting sentence has exactly one "c" (no production has $S$ on its right side). Moreover, at most one $Z$ can be in any sentential form $\alpha$ and, when this happens, $\alpha$ contains no "c". This is true because the only production that generates $Z$ is $S \to aXbZ$. Then $XZ \to Ybcc$ can be applied at most once from $\alpha$.

---
Tags: complexity-theory, context-sensitive, computational-linguistics
---


# Question
Title: Increasing an edge weight. Shortest time to recompute an $MST$?
I have an $MST$ tree $T$. I increase the weight of a single edge $e$ by $c$(a non negative constant).

I need to recompute an $MST$ as fast as i can. How I do this? The idea I had in mimd is to remove $e$ from $T$. Loop over all crossing edges between the two "halves" of $T$. See which one is minimal weight. Add her instead.

This will require $O(|E|)$ time. Is there a faster idea? Or does my idea requires less than $O(|E|)$?

I suspect a more efficient algorothm exists because i do not use the fact that $e$'s weight increased.

# Answer
If you're required to solve this "one-shot" problem, you're not allowed to perform any pre-processing, and you don't have any additional assumption, then a running time of $O(m)$ is the best you can hope for.

Indeed, consider an edge $e$ such that the fundamental cut $C\_e$ induced by $e$ contains $\Theta(m)$ edges. All edges in $C\_e$ have distinct weights that are strictly larger than the weight $w\_e$ of $e$. For every value of $m$, it is easy to come up with a graph $G$ , an associated MST $T$, and and edge $e$ that satisfy these properties.

Suppose that there is a (deterministic) algorithm $A$ with a running time of $o(m)$. Then, when $A$ is run with inputs $G$, $T$, and $e$ there is at least one edge $f \in C\_e$ whose weight is never read by $A$, and such that $f$ is not added to the new MST $T'$.

We can then run $A$ with inputs $G'$, $T$, and $e$, where $G'$ is a copy of $G$ in which the weight of edge $f$ has been set to $w\_e$. The returned MST must still be $T'$, but this is incorrect since the new MST must include edge $f$.
> 1 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: new language accepted by FA when new transitions are added to a FA?
found this question online and I am trying to solve this question. I have solved this question but I think I might be missing some cases. Could someone verify if my answers are correct?

Let N = (Σ ∪ {λ}, Q, δ, q0, {qf }) be a λ − NFA and let L = L(N) be the language accepted by N. For N assume q0 has no incoming transitions and qf has no outgoing transitions. For each of the following FAs that are modifications of N describe the language accepted by each in terms of L.

(a) A λ-transition is added from qf to q0.

(b) Add a λ-transition from q0 to every state reachable from q0 along a path with labels that may be λ or symbols from Σ.

(c) Add a λ-transition to qf from every state that reach qf along some path.

(d) The FA where both (b) and (c) are done.

---

a) L+

b) For this one I have defined a function `suff`, this takes all the valid strings in the original Language and generates new stings from them. For example, if L = {112,12} where alphabet is {1,2}

Then, `suff(L) means suff(112) + suff(12)`

where `suff(112) = {112,12,2}`, keeps chopping off the first symbol until u get empty string

Similarly, `suff(12) = {12,2}`

So, the final answer would be `suff(L) + the empty string`. (Is this correct?)

C) for this one, I defined `pre` which is similar to `suff` but chops off the last symbol.

```
pre(123) = {123,12,1}
pre(112) = {112,11,1}

```

So, the final ans is `pre(L) + empty string`

d) I need help with this one..

# Answer
Your answers to (a), (b), and (c) seem correct to me. Here's something to think about for (d).

**Hint for (d):** Let's say $s = s\_1s\_2...s\_k \in L$, and on input $s$ the original transition function follows the path $P = q\_0, q\_1... q\_f$. Let $q\_{s\_i}$ denote the state $q\_i$ closest to $q\_f$ in $P$ after only reading up to $s\_i$ in the original NFA. What are the strings can I generate by doing the following in the NFA defined by (d)? $\lambda$-transition from $q\_0$ to $q\_{s\_i}$, follow $P$ up to $q\_{s\_j}$ (for any $1 \< i \< j \< k$), and then $\lambda$-transition to $q\_f$ and accept.
> 1 votes

---
Tags: finite-automata, nondeterminism
---