title: Use Fact to decompose a given number

text:
# Question
Title: Use Fact to decompose a given number
Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\in$ P then there is an algorithm that given $n$, it produces its decomposition into prime factors in polynomial time in the length of $n$.

---

I have tried to create this algorithm as follows: Given $n\in\mathbb{N}$, if $\mathrm{Fact}(2,n)=1$ then $2\mid n$, in which case we take $n\_1=\frac{n}{2}$, if $\mathrm{Fact}(2,n)=0$ then we see what happens with $\mathrm{Fact}(3,n)$ and we continue like this, my problem is that this algorithm is done in a time $O(2^n)$ which is not polynomial and all the algorithms that occur to me end in this problem is it possible to do this in polynomial time?

# Answer
> 1 votes
Use binary search to find the smallest factor, divide and repeat.

---
Tags: algorithms, polynomial-time, number-theory, factoring
---


title: Is this set computable?

text:
# Question
Title: Is this set computable?
Let be $B$ a Busy Beaver function and set $W=\\{\langle M \rangle :\text{$M$ stops in less than $B(10^{1000})$ steps on an empty tape}\\}$. Is this set computable?

---

I'm not sure how to approach this question. I suspect that this set is computable and have tried to see if it is finite, but haven't reached anything.

# Answer
Your function is computable. Just run the input machine on the empty input for $B(10^{1000})$ steps. Note that $B(10^{1000})$ is just a constant which can be hardcoded into your code.
> 2 votes

---
Tags: computability
---


# Question
Title: Finding the closest visible vertex among line segments
Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in this case, it means that the line segment $pq$ does not intersect with any other line segment in $S$.

I am trying to implement an efficient algorithm in CGAL. I have explored the nearest-neighbor and visibility structures from CGAL but could not conclude anything.

# Answer
> 2 votes
I only noticed after posting that my first answer does not directly address your specific question. So now my answer is in two parts.

(1) As suggested by @HEKTO, to find the *closest segment*, you could first compute the Voronoi diagram: CGAL 2D Segment Voronoi Diagrams. Then next you need to perform point location within the (non-rectilinear) cells of the diagram. That is also discussed, using "the segment Voronoi diagram hierarchy, a data structure suitable for fast nearest neighbor queries..."

---

<sup> CGAL figure. </sup>

---

(2) You specifically ask for the *closest segment endpoint*, which is not necessarily an endpoint of the closest segment:

---

<sup> Point $x$ is closer to segments $1,2,3,4$ than to the closest endpoint $y$. </sup>

---

For this you might need to look at "visibility constrained Voronoi diagrams":
> Aurenhammer, Franz, Bing Su, Y-F. Xu, and Binhai Zhu. "A note on visibility-constrained Voronoi diagrams." *Discrete applied mathematics* 174 (2014): 52-56. Elsevier link.

I haven't studied this paper enough to be certain it solves your problem. And perhaps there is a way to efficiently move from the closest segment to the closest segment endpoint.

---
Tags: computational-geometry
---


title: Block matching pattern matching problem

text:
# Question
Title: Block matching pattern matching problem
I've struggling with this problem for a while.

Given text $T=t\_1t\_2\ldots t\_n$ and pattern $P=p\_1p\_2\ldots p\_m$ over alphabet $\Sigma=\mathbb{N}$, we say there's a block matching of $P$ in index $i$ if there exist $m$ successive blocks $S\_1,\ldots,S\_m$ such that $$p\_1=\sum\_{s\_1 \in S\_1}s\_1 \land p\_2=\sum\_{s\_2 \in S\_2}s\_2 \land \cdots \land p\_m=\sum\_{s\_m \in S\_m}s\_m. $$
For example:
$T=\text{1 2 3 5 1 2 3 2}$
$P=\text{6 5}$

Then we have block matching in index 1 because $1+2+3=6$ and $5=5$.
Schematically it looks like: $\text{|1 2 3||5| 1 2 3 2}$

We also have a block matching in index 4 because $5+1=6$ and $2+3=5$.
Schematically it looks like: $\text{ 1 2 3 |5 1||2 3| 2}$

The task is to find all indices where we have block matching.

I couldn't do better then a $\mathcal{O}(mn)$ but I believe there's a FFT application here.

Any hints?

# Answer
If the numbers are all integers at most $k$, then you can apply a fast algorithm for substring matching with don't-care symbols (see below) to solve the problem in $O(kn(\log m + \log k))$ time by applying the following transformation:

* Map each text character $t$ to $t-1$ zeros followed by a 1.
* Map each pattern character $p$ to $p-1$ don't-care symbols followed by a 1, and also prepend a 1 to the overall pattern.

Basically, 1s represent "boundaries" in both strings, and we look for a way to make each boundary in the pattern line up with some boundary in the text.

This paper describes an $O(n+m+\alpha)$-time algorithm, where $\alpha$ is "the total number of occurrences of the subpatterns" (I didn't read the full paper, so I'm not sure exactly what that means). In any case it mentions the 1974 algorithm of Fischer and Paterson, "String matching and other products", which solves the problem in $O(n\log m\log \Sigma)$ time -- though that link is behind a paywall, googling should find other information on it.
> 2 votes

# Answer
Since you asked for a hint: because the problem is phrased in terms of sums of a contiguous segment of numbers, prefix sums look helpful. Can you reduce it to some other problem you already know how to solve?
> 0 votes

---
Tags: algorithms
---


# Question
Title: What does canonicity property mean in Type Theory?
The "Computational Component" section of the Type Theory - Wikipedia (as well as a few papers about cubical type theory and 2d type theory) talk about *canonicity* property.

* Would you please explain exactly what this property is and what does it mean in type theory?
* Why and how is it lost in the Homotopy Type Theory with the univalent axiom?

# Answer
There are potentially multiple ways of presenting canonicity (and I think complications depending on the theory). However, I think the simplest way to think about it is from the perspective of a programmer wanting to use the type theory to compute something. For instance, we might want to compute some natural number satisfying some specification we've come up with. So we define:

```
data ℕ : Type where
  zero : ℕ
  suc : ℕ → ℕ

```

These constructors we've used have meaning to us, and we want the answer to be written in terms of them. So, for instance, `suc (suc (suc zero)))` is a valid, meaningful result of our computation.

Canonicity says essentially that every closed computation of type  we write is able to be reduced to such a meaningful numeral. Or, if we don't want to talk about 'reduction', it is "convertable" or "judgmentally equal" to such a numeral, or similar. But of course, if we're programmers, we probably want that convertability to eventually turn into reduction for at least some stuff.

The reason homotopy type theory (at least, at the time of the book) does not have this property is that there was no known computational behavior for univalence; it was just added to the theory as an 'axiom,' and you could then use it in ways where computations would just get stuck. So, in that situation, you can sometimes write closed terms of type  that might look like

```
J (...) (ua ...) ...

```

But do not compute further than that, because `J` has no way of reducing when applied to `ua ...`. So you can write terms that don't give you a meaningful answer.

A simpler example is, I think, also mentioned in that article. You can add some variety of excluded middle to have a 'classical' type theory. To do this, we can add an axiom like:

```
exm A : A + ¬ A

```

that says that every type either has a value or is empty. However, unless your types are quite simple, it is impossible to accurately decide such a thing, so this axiom will not be able to compute to either `inl x` or `inr y`, and case analysis on it will just get stuck.

This may not be a problem if you are just using type theory in a way analogous to formal logic. You can add axioms that get stuck, and add more axioms about the things that get stuck to prove specific things you desire, but those will also get stuck. For instance perhaps we could add:

```
uaId : ua id ≡ refl
uaAp : subst (λ A → A) (ua f) x ≡ f x

```

And so on. These will allow us to manually *prove* certain reduction rules, so that we can manually prove that some expression we've written is (according to our axioms) the same as some concrete number. However, for someone who desires to treat type theory more like executable mathematics that will automatically compute answers, canonicity is an important property.
> 13 votes

---
Tags: type-theory, dependent-types, homotopy-type-theory, cubical-type-theory
---


title: Software management of TLB misses?

text:
# Question
Title: Software management of TLB misses?
I'm reading an OS textbook and it was talking about TLB misses being handled by software. I'm very new to all this by the way. So there's a context switch to some kernel procedure. But surely in this case the TLB is not flushed, and the kernel code doesn't itself use the TLB, since that would defeat the purpose? But then how exactly does it work? I don't know why the text wouldn't address such a seemingly obvious question.

Plus you're still using virtual memory, right? So you would be doing two context switches, a bunch of page table lookups in memory, in addition to the actual kernel instructions, per missing TLB entry. It just seems counterintuitive to do all that work to make use of something that's supposed to save you work. Sorry if I'm getting something completely wrong here. Thank you in advance.

# Answer
Textbooks don’t have to include everything. There should be room for you to figure out things yourself. Otherwise, how would we ever create things not found in today’s textbooks?

Maintaining the TLB is a tiny bit of code in the operating system. But every single instruction accessing memory relies on the TLB. Do you think the TLB does NOT save enormous amounts of work? 99.99% of all memory accesses are fast because the TLB tells you immediately where the data is. Having to update the TLB sometimes is a very small price to pay.
> 1 votes

---
Tags: computer-architecture, operating-systems, virtual-memory
---


# Question
Title: An example of a computable problem that is not in P
I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set are very artificial

# Answer
As Yuval Filmus already mentioned in the comments, because of the time hierarchy theorem, we know $\mathsf{P} \neq \mathsf{EXP}$. Hence, any $\mathsf{EXP}$-complete problem is an example. These include, for instance, generalized chess and checkers.
> 3 votes

# Answer
This isn't really a natural example, but a natural technique *(which I'm leaving as an answer instead of a comment since I think it's still valuable, and it's clearly too long)*: we can use a **diagonal argument**. Specifically, while we can't tell whether a Turing machine runs in polynomial time, we can whip up a list of polynomial-time Turing machines such that every polytime machine is equivalent to one on the list.

Namely, let $(M\_e)\_{e\in\mathbb{N}}$ be your favorite enumeration of Turing machines, let $(p\_e)\_{e\in\mathbb{N}}$ be your favorite enumeration of polynomials, and let $\langle\cdot,\cdot\rangle$ be your favorite pairing function on $\mathbb{N}$. Then we let $N\_{\langle i,j\rangle}$ be the machine "$M\_i$ cut off by $p\_j$" - on input $k$, $N\_{\langle i,j\rangle}$ simulates $M\_i$ for $p\_j(k)$-many steps, and (say) halts and ouptuts $0$ of $M\_i(k)$ doesn't halt in that time. The key point is that if $M\_i$ really does run in polynomial time, there is some $j$ such that $N\_{\langle i,j\rangle}$ is "equivalent to" $M\_i$ in the obvious sense.

Now let $X=\\{n: N\_n(n)=0\\}$ \- intuitively, $X$ is the set of $n$ which aren't in the $n$th polynomial-time-computable set. More generally, this technique lets us diagonalize out of any complexity class which is effectively describable - the reason we can't diagonalize out of REC (= the set of all computable sets) is that we have no way to "cheat" in the above manner and whip up an enumeration of those Turing machines which correspond to computable sets (= those which always halt - put another way, the set $Tot$ of always-halting Turing machines is not c.e. in a very strong way).
> 1 votes

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


# Question
Title: Could following be a counter example to Church-Rosser (Confluence) theorem?
According to the "Type Theory and Formal Proof" book, Church-Rosser theorem (confluence) is as follow:

> Suppose that for a given term $M$, we have $M \twoheadrightarrow\_\beta N\_1$ and $M\twoheadrightarrow\_\beta N\_2$. Then there is a $\lambda-term$ $N\_3$ such that $N\_1\twoheadrightarrow\_\beta N\_3$ and $N\_2\twoheadrightarrow\_\beta N\_3$.

But if we take $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ expression as $M$, then it will reduce to $v$ if we start with the left sub term and reduces to $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ if we start with the right sub term. And they would never reduce to equal terms if we keep reducing the sound one using the right sub term since it would keep converting to itself for ever.

Isn't the above example a refutation of the CR theorem, or I have missed a point somewhere?!

# Answer
If we keep reducing the right subterm, then yes, we will never get to $v$. But noone says that we are restricted to this decision. The Church-Rosser theorem does not claim that *any* possible reduction series must lead to $N\_3$. Church-Rosser just states that $N\_2 \twoheadrightarrow\_\beta N\_3$, i.e. that there exists *some* beta reduction series that will lead from $N\_2$ to $N\_3$. And it is obvious that no matter how many times we just reduce back to $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$, at any point we can choose our next reduction step to be on the left-hand side, which will immediately get us to $v$. So it *is* possible to find a reduction series from both $N\_1: v$ and $N\_2: (\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ to $N\_3:v$ -- and that's all the Church-Rosser theorem states.
> 6 votes

---
Tags: lambda-calculus, type-theory
---


title: Network density vs connectivity

text:
# Question
Title: Network density vs connectivity
I was reading this paper where they mention about undirected networks:

> "The total connectivity of a network is defined as $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total number of nodes."

However, this is just another way of talking about network density is it not? You could just change the denominator and refer to network density for directed and undirected networks.

Or is this "total connectivity" anything different than density?

# Answer
> 1 votes
Yes, $C$ here is the density of (simple) directed graphs. You can see the Wikipedia entry on dense graphs for more details. In this context, total connectivity is just another name for density.

---
Tags: graphs
---


# Question
Title: Question about complexity of TSP Optimization problem
Is this statement true?

> Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate across the solution space.

# Answer
> 1 votes
This statement seems quite vague and confused.

NP-hardness is precisely defined, and you shouldn't loosely say "optimization TSP problems" because it doesn't specify the problem(s). In fact, it is not uncommon that seemingly small changes in a problem lead to different complexities.

Further, because NP-hardness is precisely defined, a problem is not NP-hard because "we do not have a minimum cost to compare against", but because for every problem $X$ in NP there is a polynomial-time reduction to the problem in question - by definition.

Finally, the expression "... to verify a solution is optimal, we need to iterate across the solution space" should be fleshed out more precisely. If the claim is "to verify a solution is optimal, we must inspect every possible solution of the search space", this is wrong.

---
Tags: complexity-theory, optimization, traveling-salesman
---


title: Showing that $BPP \subseteq EXP$?

text:
# Question
Title: Showing that $BPP \subseteq EXP$?
I am trying to understand why $BPP \subseteq EXP$. This question almost gives the answer (simulate $BPP$ machine on all possible toin cosses and then "act accordingly"). However, it is not clear to me what act accordingly means: I am thinking we need to count how many times the probabilistic Turing machine accepts and how many times it rejects and then act upon this information - but how exactly?

# Answer
A $\mathsf{BPP}$ machine $A$ has randomness complexity $r(n)$ which is polynomial in $n$. Hence, an $\mathsf{EXP}$ machine $B$ can loop over all $2^{r(n)}$ values of the random tape of $A$, simulating $A$ with each random input (each simulation taking polynomial time), and count how many times $A$ accepts or rejects. The overall decision of $A$, then, is whichever of the two counters contains a larger value at the end of this process.

Interestingly, the same reasoning also explains why $\mathsf{PP}$ is contained in $\mathsf{EXP}$.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Why does arithmetic left shift of negative number leads to positive number?
According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes a positive number when an arithmetic left shift is applied.

Eg.: Take a 2's complement signed integer -5 and 5 bits are used to represent it.

```
11011 ==> -5
10110 ==> -10 (-5x2)
01100 ==> +12 (?)

```

So after two arithmetic left shifts -5 became 24. I expected -20. Why is this the case?

# Answer
> 2 votes
$01100 \Rightarrow +12$, not $+24$.

And it is $+12$ because $32-20=12$. With $5$ bits and $2$s complement you can only represent numbers in the range $-16$ to $+15$. You have overflowed this range and, in effect, "run around" to the other end and into the positive number range.

---
Tags: computer-architecture, arithmetic
---


# Question
Title: How to generate all combinations given an array of elements using backtracking?
Given an array, generate all combinations

For example:

Input: {1,2,3}

Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

I am practicing Backtracking algorithms and I think I understand the general idea of backtracking. You are essentially running a DFS to find the path that satisfies a condition. If you hit a node that fails the condition, exit the current node and start at the previous node.

However, I am having trouble understanding how to implement the traverse part of the implicit tree.

My initial idea is to traverse down the left most path which will give me {1}, {1,2}, {1,2,3}. However, once I backtrack to 1, how do I continue adding the 3 to get {1,3} and {1,3,2} afterwards? Even if I have 2 pointers, I would need it to point to the 2 to eventually get {1,3,2}.

Am I approaching this problem correctly by drawing this implicit tree and trying to code it? Or is there another approach I should take?

I am not looking for code to solve this, rather I am looking for some insight on solving these kinds of questions.

# Answer
I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases.

# Combinations

So let's talk about the number of combinations. If you're trying to pick $k$ numbers from $1,2,...,n$, there's $2^n$ ways. $$\sum\_{k=0}^n{n\choose k} = 2^n$$

This is a subtle hint that you can think of a combination as a set of binary choices. Let us have $n$ levels in our search tree, not including the root level. At level $i$, we give ourselves the choice to add or not to add element $i$ to our current combination. In this way, we construct a tree of uniform depth such that any path from root to leaf constructs a unique combination **and** we also claim that all possible combinations are represented by the tree. Now we can just compute a DFS, and every time our search reaches a leaf node, we add the current path to the list of combinations (If you're wondering how to keep track of the current path, there are already many posts/resources about that). If you prefer to do it recursively, this is also trivial.

The difficult part of these problems is indeed coming up with the representation. Let's go back and take a look at your original proposal.

# Permutations

Again lets think of our choices at every step. We construct a tree to represent these choices. At a node $p$ at level $i$, we can select any of the remaining numbers *not* present in the path $root\rightarrow ...\rightarrow p$. Therefore, every root to leaf path in our tree now represents a permutation of all $n$ elements. In order to also get the permutations of subsets of $1,2,...,n$, we consider *all* paths in the tree beginning at the root as possible permutations.

This seems to be what your tree depicts, and it is a common way to view the problem. Simply performing a DFS while keeping track of the current path should be sufficient to obtain an answer.
> 1 votes

# Answer
I see two ways of doing it / thinking about it, which are essentially equivalent.

Method 1: Use recursion to implement your DFS. When at a node of your tree, you just need to recursively call the DFS on every child node, then output/store the current node (or the other way around). The backtracking will take care of itself. If you don't want to use recursion you can simulate the call stack yourself.

Method 2: Remember from where you came when backtracking. So for example, when backtracking from {1,2} to {1}, keep a variable that says "I deleted 2". That way, you know that you just came back from the branch where 2 was added, so you can go down the path where you add 3. This is essentially what recursion will do for you, except that in this particular case all the information you need is already stored in the last combination you visited, so there is no need for an additional stack or recursion.
> 0 votes

---
Tags: algorithms, algorithm-analysis, permutations, backtracking
---


# Question
Title: Query Logs and evaluation of search engines
I'm taking a course about Information Retrieval and we had a quiz involving the evaluation of search engines.

We had a problematic question regarding "Query Logs" (basically recording the queries that users searched in the past and their response for the queries e.g links clicked), and I hope you can help me figure out the answer:

Using query logs can improve the retrieval efficiency of the search engine by:

* A. Learning common typos in queries
* B. Learning the connection between pages the users clicked as the result of different queries
* C. Saving popular queries in a cache
* D. A + B + C
* E. A + B + C doesn't affect the efficiency of retrieval
* F. The Collection of query logs can't affect the efficiency of retrieval

I circled option D (A+B+C) and I was wrong.

My Lecturer refuses to reveal the correct answer - I can appeal about her decision but I want to be certain I'm correct.

The explanation for my answer: the question talked about improving the retrieval efficiency, and to the best of my knowledge retrieval efficiency is the time measured from when the user clicked "Search" until the user received the results back.

Therefore, I think A is correct because if we learn common typing mistakes in queries we can create a dictionary of those common errors and create spell correction algorithms. For example if many users typed "bast" instead of "best", we can use a data structure similar to a cache. (However, this might require an enormous amount of memory, but the question didn't mention memory efficiency)

I think C is correct because we can save the results of the popular queries in a cache instead of using the (fairly slow) posting file.

B is the only option that I'm not sure why is correct, but I assumed that if A and C are correct, B can be correct.

Could you please tell me what you think about the question and my answers?

Thank you!

# Answer
> 0 votes
I would have selected option C.

I don't think option A is correct. We probably can learn common typos, but that doesn't affect the time to process a search query, and it's not clear how you'd use that to speed up search queries. (I'm assuming that "time to process a search query" is what is meant by "retrieval efficiency".)

Similarly, I don't think option B is correct. We probably can learn the connection between different pages that a user clicked, but that doesn't appear to affect the time to process a search query, as far as I can tell.

# Answer
> 0 votes
"Retrieval efficiency" could mean time to process a query, but could it also refer to having a better precision-recall curve?

---
Tags: information-retrieval
---


title: Basic Theta-notation question

text:
# Question
Title: Basic Theta-notation question
Let $T$ be a function.

Is it true that if $\exists f\forall n,m\> 0.\\ \frac m {f(n)} \leq T(n,m)\leq m$

Then $\exists g.T(n,m)=\Theta(m\cdot g(n))$?

In words: is such a case, is there a function $g$ dependent only on $n$ that satisfies the above?

It looks to me true, but I am really stuck and don't know how to prove it rigorously.

# Answer
No. Consider, for instance, $$T(n,m) = \begin{cases} m, & \text{$m$ even} \\ \frac{m}{n}, & \text{$m$ odd} \end{cases}$$ and notice $\frac{m}{f(n)} \le T(n, m) \le m$ holds for $f(n) = n$. Suppose $T(n,m) \in \Theta(m g(n))$ for some $g(n)$, that is, there are $c, c' \> 0$ with $cmg(n) \le T(n,m) \le c'mg(n)$ for all but finitely many $m,n$. Since there are infinitely many odd $m$'s we get $g(n) \le \frac{1}{cn}$ for all but finitely many $n$. For even $m$ it then follows $$m = T(n,m) \le c' m g(n) \le \frac{c'}{c} \frac{m}{n},$$ which can only hold for finitely many $n$.
> 5 votes

---
Tags: asymptotics
---


# Question
Title: Linear programs with strict inequalities and supremum objectives
Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution. For example "maximize $x$ such that $x\<5$" does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution - the supremum is $5$.

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?

# Answer
> 4 votes
Suppose that the supremum of a continuous function $f(x)$ subject to $Ax \< b$ is $c$, and assume furthermore that the constraints imply a bound on $\\|x\\|\_\infty$. Thus there is a sequence of feasible points $x\_n$ such that $f(x\_n) \to c$. Since all points in the sequence have bounded norm, it follows that some subsequence of $x\_n$ converges to a limit point $y$ satisfying $f(y) = c$ and $Ay \leq b$. This implies that in the bounded case, your problem is equivalent to classical linear programming.

In the unbounded case this argument doesn't work. For example, the infimum of $x-y$ subject to $x-y \> 0$ is $0$, but the sequence $(n+1/n,n)$ has no limit points. Nevertheless, the answer should be the same.

---
Tags: linear-programming
---


title: How are hardware interrupts handled?

text:
# Question
Title: How are hardware interrupts handled?
I have read that a hardware interrupt is handled asynchronously by the CPU, which means that the interrupt signal may arrive at any point of time with respect to the CPU clock cycle. Now, this means that an interrupt may asynchronously hit the processor when it is in the middle of executing some instruction. So, how does the control pass to the OS in this case? For the case of software interrupts (exceptions), we know that the instruction being executed (trap instruction) itself is the cause of the interrupt. So, it will synchronously finish executing and then the control will transfer to the kernel as per the trap instruction nature. How does all this happen for hardware interrupts?

# Answer
> 1 votes
This is architecture specific so the following might not be true for all architectures.

Normally there is a special hardware in the CPU called interrupt controller that will react to interrupts. You usually program this hardware on boot time by writing a handler for each interrupt (called interrupt service routine) and giving the interrupt controller a table with the location of these handlers (the interrupt vector table https://en.wikipedia.org/wiki/Interrupt\_vector\_table).

When a hardware interrupt happens, the interrupt controller will automatically lookup the location of the corresponding handler and immediately continue execution there (on the very next assembler instruction). Depending on the architecture, there might now be a second set of registers, another stackpointer etc. that the ISR uses or it has to save the status of the interrupted program to the memory (RAM) perform it's actions and restore the state once it finishes.

The ISR is automatically run in a higher privilege mode on the CPU (if not already in a high privillege mode) and can therefore invoke other OS functionality. How the ISR is now interacting with the OS can't be answered in general. It could for example set some flags which are then checked by the OS threads.

Maybe you will also find this answer interesting: https://cs.stackexchange.com/a/85156/108759

---
Tags: operating-systems, os-kernel
---


# Question
Title: How can the initial "booting" state of a computer be different at different time points?
In my experience, sometimes a computer boots normally, and in a time span of days, the computer won't boot, then again, it will boot normally again. I am not a computer science expert so I assume that if a computer boots normally one time and then it doesn't, **it must be** due to any changes made into the computer between those time points.

My question has the motivation of understanding the booting process of a computer at a basic level as to know how to debug such a behavior.

For a concrete example, I got a new computer with Ubuntu 18.10 that presented this behavior, all the time without access to internet, so no updates/upgrades possible.

Can anything change in a computer without the user modifying something, also while not having internet connection?

# Answer
> 2 votes
> Can anything change in a computer without the user modifying something, also while not having internet connection?

Yes, definitely - computers update their own states all the time, and some of these changes will be persistent from one boot cycle to the next.

The computer itself is a complex piece of hardware, and the operating system is a complex piece of software. Both the computer (at a hardware level) and the operating system will carry out a series of self tests during the boot process. The results of some of those self tests will be stored in non-volatile memory (e.g. in some form of registry). When the computer is re-booted, the results of the self-tests from the previous boot attempt may affect the route taken through the boot process the next time around. This might avoid a problem encountered in the previous boot cycle (e.g. by loading a previous version of a corrupted driver), but it may also introduce a new problem not seen before.

In short, part of the boot process will be a check to see if the previous boot cycle was successful. If not, there may be logic in the boot process that tries a different sequence of actions, or boots into a restricted "safe" mode.

# Answer
> 0 votes
> Can anything change in a computer without the user modifying something

Yes, definitely. Most obvious example: the clock, it changes all the time!

Other examples of environmental factors that change without the user actively manipulating them, are temperature and humidity. Temperature influences the workings of electronics heavily, and humidity has an influence on the behavior of electrical connections. Another external factor that is only partially under the user's control is the quality of the mains power.

Modern high-performance CPUs and maybe even more so GPUs, to a lesser extent also RAM, are built right at the edges of what is possible given our current understanding of physics and our current level of engineering. Some might even argue that the *really highest*-performance CPUs and GPUs may already be over that edge.

Even the tiniest fluctuations in mains power can, at least with a badly designed power supply, have devastating effects on the stability of the electronic components. Modern CPUs can manage their frequency themselves, based on power and temperature, and may run at different speeds given the ambient temperature, which may in turn lead to some timers being off by a tiny amount, which can lead to an overflow happening or not happening at the right or wrong time.

The possibilities are endless.

There is also another possible explanation that is admittedly rather "out there" (literally): cosmic rays. While the probability that a cosmic ray will hit exactly one transistor in exactly your computer's RAM in exactly the right way to make exactly the most important bit flip from 0 to 1 and crash your computer, is extremely tiny, there is also an extremely large amount of computing devices in the world. If you're a sysadmin at Google, for example, you'll probably see it happen more often than you will see a car accident on your way to work.

There could also be a rather benign explanation: a counter.

For example, one of the devices my employer makes, has three copies of the OS installed in three separate partitions: user 0, user 1, and recovery. On boot up, there is a counter that is incremented, once the boot has finished, the counter is reset to 0. Once the counter hits 3, the boot sequence switches to the other user partition. If the counter hits 3 again, the boot sequence switches to the recovery partition, which has an older, more stable, stripped down copy of the OS, and attempts a self-repair. The device also calibrates its RAM during boot up, but not during runtime. So, if the temperature changes drastically between boot up and runtime, the calibration may be off, something may crash, which causes the watchdog to reboot the device, which causes a recalibration to different values.

---
Tags: os-kernel
---


# Question
Title: Weighted graph clustering with maximum size constraint
I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size `n`. I have `~80000` nodes and `~260000` edges. Each node owns a weight `w`. The sum of all node weights in one cluster cannot exceed `n`. The higher the edge weight between each node, the more **"valuable"** it is to the cluster. Therefore, nodes with a high weight connection should end up in the same cluster and the loss if a cluster is full should be minimal. The number of clusters created is not pre specified.

I've tried implementing a min cut algorithm (Stoer-Wagner) and execute it over and over again until the size constraint is met. However, the first cut of the graph finished after \>30 minutes and created sub-graph consisted of only one node.

Are there any solutions to this problem considering the size constraint? Is there a way to extend a min-cut algorithm to solve this?

Thanks in advance!

# Answer
> 0 votes
I can't think of an exact algorithm and don't know if an efficient one exists. But if you're ok with heuristics and approximate solutions you could try the following:

### Find an initial solution:

Repeat the following until every vertex is assigned to a cluster:

Pick a vertex u belonging to no cluster and create a new cluster C = {u0}. Grow a minimum weight tree from {u0} using Prim's algorithm (using only vertices assigned to no cluster) with a cost function corresponding to:

```
C[v] = minimum over (u=neighbour of v in C) of -value((u,v))/weight(v)

```

(you just have to adapt the cost update function of any efficient Prim implementation)

Stop when the weight of your Tree starts getting too big.

That's just an idea. You could also try to start with any random assignment of clusters which agrees with the weight constraint.

### Perform local optimizations:

Pick a vertex v and see if you can gain value by moving it to another cluster by computing the sum of values of the edges you gain minus the sum of the edges you loose. Pick the cluster which maximizes this sum, among the ones which are possible (i.e, weight(C) + weight(v) \<= n). You can repeat that as long as you like or as long as the solution is improving, choosing the vertices in some order or randomly.

If this doesn't work well enough, you can allow to sometimes perform swaps which make your solution momentarily worse in order to get out of a local minimum, using something like Simulated annealing or Tabu Search.

---
Tags: graphs, weighted-graphs, partitions, clustering
---


# Question
Title: Could I apply the master theorem if my $N/b$ is $\varphi(N)$?
Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$

where $\varphi(N)$ is Euler's totient function.

Can I somehow express $\varphi(N)$ as $N/b$, so I can apply the Master Theorem and resolve this recurrence?

You may assume $\varphi(N) = (p-1)(q-1)$, if it's easier that way. You may also assume, if it helps, that $p$, $q$ are safe primes, that is, $p = 2p' + 1$ and $q = 2q' + 1$. (Assume anything that makes the problem easier. For instance, you can replace the function $\lg^3(\varphi(N))$ with any other that makes the problem easier, but do so only as a last resort.)

# Answer
You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem.

First, show that $\phi(\phi(n)) \< n/2$. This can be done as such:

Let $n = \prod\_{i=1}^rp\_i^{k\_i}$ be the prime factorisation of $n$ ($p\_i$ prime, $k\_i\>0$)

* Suppose $n$ is even. Then $\phi(n) = n\prod\_{i=1}^r(1-\frac{1}{p\_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) \< n/2$.
* Suppose $n$ is odd and $n \> 1$. Then $\phi(n) = \prod\_{i=1}^r (p\_i-1)p\_i^{k\_i-1}$ is even and smaller than $n$. By the previous result $\phi(\phi(n)) \< n/2$.

So we get the desired result.

Now suppose $n\geq2$. You can write: $$T(n) = T(\phi(n))+\log(\phi(n))^3 = T(\phi(\phi(n)))+\log(\phi(\phi(n)))^3 + \log(\phi(n))^3.$$ $$T(n) \leq T(n/2) + 2\log(n)^3.$$

Now you can apply the master theorem here to get: $$T(n) = O(log(n)^4).$$
> 4 votes

---
Tags: master-theorem
---


# Question
Title: What is the difference between Babbage's analytical and difference engine?
What is the difference between Babbage's analytical and difference engine? Can they even be compared?

# Answer
> 3 votes
They would be different from each other in a very significant way. In the comments there is a link to the Wikipedia articles on both machines - which are quite informative - but I'll assume they weren't useful to you.

You can think of the Analytical Engine basically as a regular computer, which would have a program coded in punched cards, that were attached to each other forming a chain (there would actually be three kinds of cards, each with its own reader, check this out). The machine also had a control unit whose job was to decode the instructions of this program and perform them on the data that was stored in a memory capable of holding a thousand numbers.

The Difference Engine, on the other hand, would have been exactly a *calculator*, and one that could perform just one kind of operation, repeatedly, on a sequence of numbers. In the "Sketch of the Analytical Engine", authored by Luigi Menabrea, and famously translated by Ada Lovelace, the nature and general applicability of this operation is detailed:

> The theorem on which is based the construction of the machine we have just been describing, is a particular case of the following more general theorem: **that if in any polynomial whatever, the highest power of whose variable is *m*, this same variable be increased by equal degrees; the corresponding values of the polynomial then calculated, and the first, second, third, &c. differences of these be taken (as for the preceding series of squares); the *m*th differences will all be equal to each other**. So that, in order to reproduce the series of values of the polynomial by means of a machine analogous to the one above described, it is sufficient that there be (*m*+1) dials, having the mutual relations we have indicated. As the differences may be either positive or negative, the machine will have a contrivance for either advancing or retrograding each needle, according as the number to be algebraically added may have the sign plus or minus. (emphasis added)

By calculating series of values of polynomial functions many useful calculations can be approximated, including those of trigonometric and logarithmic functions. This method has its limits, though, which are explained a bit further in the document. In doing that, the justification for the construction of the new machine is given:

> We see that its use is confined to cases where the numbers required are such as can be obtained by means of simple additions or subtractions; that **the machine is, so to speak, merely the expression of one particular theorem of analysis**; and that, in short, its operations cannot be extended so as to embrace the solution of an infinity of other questions included within the domain of mathematical analysis. It was while contemplating the vast field which yet remained to be traversed, that Mr. Babbage, renouncing his original essays, conceived the plan of another system of mechanism whose operations should themselves possess all the generality of algebraical notation, and which, on this account, he denominates the Analytical Engine. (emphasis added)

# Answer
> 1 votes
According to Ada in her notes A:

"**The analytical engine, on the contrary, is not merely adapted for tabulating the results of one particular function** (which implies the difference machine is intended to tabulate the results of one particular function)**but for developing and tabulating any function whatever.In fact the engine may be described as being the material expression of any indefinite function of any degree of generality and complexity, such as for instance,<br>**

```
 ***F {x,y,z, log.r, sin (y), x^P, &c.)***
```
**which is, it will be observed, a function of all other possible functions of any other quantities."**.

Let us take multiplication of two simple equation: (5x+4), (3x+7).
In Difference Engine (DE) one cannot give it directly. The intermediate steps needs to be performed manually and the coefficient of x square will be (5\*3) = 15
the coefficient of x will be (5\*7) + (3\*4) = 35 + 12 = 47
and the constant term will be 28.
These coefficients will be placed in the **columns** (similiar to the concept of registers) of the DE and the list of x values also needs to be fed for which the polynomial equations will be directly evaluated by the principle of **Method of Difference**. But in Analytical Engine (AE) the intermediate steps are automatically computed way similar to the modern way of programming and computing whereas we cannot program DE and also we need to set specific initial state of the dials (components of DE) which is comparatively way inferior to AE.

The difference that arises between DE and AE is mainly due to the construction and the underlying principle. The design of AE contains mill and the storage which is equivalent to the concepts of CPU and memory respectively which are not present in DE . The basic arithmetic operations in AE are independent to each other but in DE other operations are realised by the addition operation.

Still DE is much faster than AE and also Difference Engines are constructed whereas Analytical Engine has not been constructed yet due to its mechanical complexities.

# Answer
> -1 votes
the main difference between those two engine is difference engine can only do one mathematical operation that is addition on the other hand analytical engine can do the four basic mathematical operation (addition,division,multiplication ... )...

---
Tags: terminology, computation-models, history
---


# Question
Title: How strong is an oracle that avoid don't-halt
Consider such an oracle:

> Given a turing machine\[1\], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.

1. How strong is a TM with the oracle?
2. Can the oracle exist(or does the question always have an answer) if change \[1\] into a TM with the oracle?

Some results I get:

1. It's as strong as a TM with oracle that compare running time of two programs, or arbitary returned value if both don't halt.
2. If the oracle returns integer the TM returns(may need to define a way it outputs integer), or arbitary integer if it doesn't halt, we can solve the halting problem by getting the runtime and check. However, currently I can't output from the oracle a string of any finite length if the length can be arbitary long, promising it's finite.

(Moved to here)

# Answer
> 2 votes
EDIT: I made a deeply silly mistake in my previous answer. Below what I've done is answered the question, then explained how two variations of the question - which I originally conflated with the actual question - yield a very different answer.

---

An oracle of the type you describe computes the halting problem (and conversely every oracle computing the halting problem computes an oracle of your type).

* Suppose $x$ computes the halting problem. Without loss of generality, we may take $x$ to literally *be* the halting problem. Then we can compute an $f$ as desired by simply taking an input $e$, asking $x$ whether $T\_e(e)$ halts, and (i) if the answer is no, halt and output $0$ and (ii) if the answer is yes, run $T\_e$ until it halts and output the result.
* Conversely, suppose $f$ has the desired property. There is a total computable function $h$ such that for all $e$ if $T\_e(e)$ halts, then $T\_{h(e)}(h(e))$ halts and gives the runtime of $T\_e(e)$. Now to tell whether $T\_e(e)$ halts we simply run $T\_e(e)$ for $f(h(e))$-many steps.

---

Now there are a couple natural variations to the above notion:

* What if we demand *inequality* instead of *equality*?
* What if we restrict attention to machines with *binary* output?

Both of these variations prevent the argument above from working, the former by preventing us from representing runtimes as outputs and the latter by preventing us from coding literally *anything* into the output.

It turns out that these notions yield a much weaker complexity class: namely the **PA degrees**. The original definition was that something is of PA degree if it computes a complete consistent extension of Peano arithmetic (which by Godel must be non-computable), but there are many equivalent definitions. Generally the simplest to work with is:

> A degree ${\bf a}$ is PA iff whenever $X$ is an infinite computable binary tree, ${\bf a}$ computes an infinite path through $X$.

PA degrees can be quite weak, computability-theoretically. While no PA degree is computable, they don't have to compute the halting problem: there are PA degrees incomparable with the halting problem, and there are PA degrees strictly weaker than the halting problem (where strength here is measured by Turing reducibility).

---

Re: relativization, the answer is **no**: the proof of the incomputability of all PA degrees relativizes, so no oracle is PA over itself.

---
Tags: turing-machines, computability, oracle-machines
---


# Question
Title: How Babbage's Analytic engine made calculations of unlimited extent?
Brian Randell, in his article The COLOSSUS, explains how computing ushered in the 20th Century, by the development of the Colossus computer. He cites a passage from the *Passages from the Life of a Philosopher*, illustrating how Charles Babbage described the Analytical Engine :

> That the whole of the conditions which enable a finite machine to make calculations of unlimited extent are fulfilled in the Analytical Engine.

I couldn't get how calculations of unlimited extent can be performed by the Analytical engine as described by Babbage. An example would be helpful too.

# Answer
> 1 votes
***tl;dr*-** The bit about **"*unlimited extent*"** is referring to being able to perform general-purpose computation rather than infinite computation. They probably thought that it was trippy for a finite device to be able to pursue any sort of computation.

---

It seems that Brian Randell was referring to how the *Analytical Engine* was meant to be a general-computing device that could, in principle, perform any sort of computation.

The fuller quote discusses the notions of Turing completeness and **"*unlimited extent*"** as two different perspectives on this topic:

> Turing thus was the first to arrive at an understanding of the universal nature of a (conceptual) digital computer which matches and indeed surpasses the philosophic understanding that I believe Babbage had attained, a century earlier, of the universality of his planned (mechanical) Analytical Engine. Babbage’s phrasing was “that the whole of the conditions which enable a *finite* machine to make calculations of *unlimited* extent are fulfilled in the Analytical Engine” \[2, p.28\], where the term “extent” encompassed both the amount and accuracy of the data to be processed, and the length and logical complexity of the algorithm to be performed. Central to the Universal Turing Machine is the idea of having data, and input data in particular, represent a program (called a “table” in Turing’s paper). A hitherto little known manuscript by Babbage \[1\] which has recently been published for the first time makes it clear that Babbage had reached an almost similar level of understanding. In the manuscript he points out that a fully detailed sequence of “formula cards” might be prepared by the Analytical Engine from a more abstract sequence. However, this is not to say that Turing’s work was in any way derived from Babbage’s – indeed there is no evidence that Turing even knew of Babbage at this time, but this topic will be returned to later.
>
> -"*The COLOSSUS*", Brian Randell, page 4

This seems to be referring to the property of the *Analytical Engine* to perform general-purpose computation, which the above quote refers to as **"*universal nature*"** and **"*universality*"**.

# Answer
> 0 votes
By conceiving the idea of how the analytical engine works this statement will become much understandable.

**Working of the Analytical Engine:**
Analytical Engine mainly contains two parts. The **Column** and the **Mill** which are equivalent to the modern concepts of **Registers** and the **CPU**. The Analytical Engine will accept any input function ranging from basic arithmetic operations (+,-,\*,/), extraction of root, exponential, polynomials, circular functions, log and even can able to solve simultaneous equations. Most of the complex function can be approximated by the polynomial functions. It will solve these input functions through intermediate steps which will be provided to it through cards (mechanical way of coding). It accepts three kind of cards

1. operators (the operations need to be performed sequentially)
2. Variables (the column number on which the above mentioned operations need to store the value)
3. Constants ( the input constants of the equation is mentioned with on which column it needs to store the value).

The two basic principles of Analytical engine are that every arithmetical calculation ultimately depends on four principal operations — addition, sub- traction, multiplication, and division ; the second, in the possi- bility of reducing every analytical calculation to that of the co- efficients for the several terms of a series. If this last principle be true, all the operations of analysis come within the domain of the engine.

Thus, with finite operations from the cards it can achieve computation to the unlimited extent.

---
Tags: history
---


# Question
Title: Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?
I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm:

But I couldn't understand what does $E(n)$ and $E(p)$ mean. I know that it has something to do with sets.

# Answer
For each state $n \in N$, we maintain a set of states $E(n)$. Eventually, $E(n)$ would contain all states reachable from $n$ via $\epsilon$-transitions.

You can think of $E$ as an array of sets. The notation $E(n)$ just means the value of $E$ at position $n$. So $E(p)$ is just the value of $E$ at position $p$.
> 0 votes

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


# Question
Title: How do web browsers find out the MAC address?
While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and connect to it. It will then transfer a copy of the web page to your computer so that you may view it.

However, my concern is... I have discovered that the IP address enables data to be sent to the device's local area network, but in order for the data to be sent to the device itself, the MAC address is needed to transfer data from the local area network to the device.

BUT, in my textbook, nowhere does it say how the computer's web browser finds out the MAC address of the web server. It says that the computer finds out the IP address of the web server by using the Domain Name System (DNS).

So, how does the computer find out the MAC address of the server?

Answers would be much appreciated.

# Answer
> So, how does the computer find out the MAC address of the server?

**It doesn't.** The MAC address only has validity inside a local area network (LAN), which, as the name says, is *local*. Unless the destination IP address resides in the same network as your machine, what it does is create a packet destined to the target IP address and forward it to its default *route*, usually your router. (To do so it must obtain the router's MAC address too using ARP—but this is a different matter.) Obtaining the server's MAC address is the task of the final hop which is in the same LAN as the server; a machine notices it is the final hop by checking if the destination IP lies in the same subnet as its own.

It is only when the destination IP is in the same local network as your machine that the MAC address needs to be obtained. (And this is done using ARP too.) In this case, your computer just happens to be the final hop in the route to the server.
> 5 votes

# Answer
Your computer sends a request to your router, and the router sends it to the IP address of the server. Included in the request is your router’s IP address. So the server sends the website to your router, and your router knows your computer (and the average cheap home router can handle a few dozen devices connected to it), and sends it on to your computer.
> 1 votes

---
Tags: computer-networks, routing, ip
---


title: Is Binary search tree in 1D?

text:
# Question
Title: Is Binary search tree in 1D?
This post says

> Binary Space Partitioning Trees are a generalization to dimensions \> 1 of binary search trees

which indicates the binary search trees lives in 1d space.

Is my understanding right?

# Answer
This just means that the elements stored in a binary search tree are one dimensional. Or more generally that they can be ordered in some meaningful way. You can think of this ordering as putting all the elements on a line, from "smallest" to "biggest" (for an appropriate notion of small and big depending on the particular case). And partitioning then always happens by cutting this line at some point. Hence the "1-dimensionality" of the binary search trees.

But in 2D space-partitioning for example, your data lives in a 2D space and you can not simply order them from "smallest" to "biggest". You need more freedom in the way you cut your space in half.

The trees themselves are just binary trees in both cases, the "dimension" comes from what the nodes represent and how the trees are used.
> 3 votes

---
Tags: data-structures
---


title: Find node that splits tree in half

text:
# Question
Title: Find node that splits tree in half
> Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \\{u\\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the complexity?

Can I please have a hint?

# Answer
Use dynamic programming to find division number of each node, For leaf nodes set it to $0$ Then recursively for parent of each leaf node set it to sum of division of it's child, and for each child because that child is not counted in division number of itself we should add its division number by one to calculate the parent division number: $$\text{division}(v) = \Sigma (\text{division}(\text{child}\_i)+1)$$ Use above recursion structure to set division number of each node, but if in some point if you have division number bigger than equal to $|V|/2$ output this node.

This is bottom up $O(|V|)$ algorithm because you will check every node at most once, and the operation which calculates division numbers is at most $\Sigma \text{ deg}(v\_i) = 2|E| = 2|V-1|$.
> 4 votes

# Answer
You might want to first compute the number of vertices in each sub-tree. Now you start at the root: if the number of vertices in both sub-trees is at most $|V|/2$ you remove the root and you are done. Otherwise, you choose the root of the sub-tree whose number of elements is $\gt |V|/2$ and try again. this has complexity linear in $|V|$. This works for binary trees only but you can binarize any tree I believe.
> 2 votes

# Answer
You problem is solved trivially in order statistic trees, where each node has an additional size attribute, and many answers have already mentioned this situation.

So what to do first is to calculate and memorize size for each node ($O(|V|)$), and then do a BST search to find the node with rank $|V|/2$, which is $O(\log(|V|))$ for balanced trees.

This works in binary trees only, but can be easily generalized to any trees.
> 2 votes

# Answer
Your graph is a tree - so removing any node will resolve in having two connected components (unless the node was a leaf, than you will still have only one component).

If you graph is a balanced tree, then you should remove the root.

If it is a generic graph than maybe finding the Jordan center of the graph and removing that one would help. You will have to pass by Djikstra over all nodes or Floyd-Warshall.

Take a look at this one
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, trees
---


title: Merge nodes in a graph to form a tree

text:
# Question
Title: Merge nodes in a graph to form a tree
I have an undirected graph which may have 2 edges that connect the same pair of nodes.

A group of nodes that don't need any bridges to go from a node to another should be merged into one node in a new tree. That tree should contains such nodes and all bridges in the original graph.

What is the algorithm to solve this problem, given that the numbers of nodes and edges in the graph are smaller than 2\*10^5?

# Answer
What you want is to find the 2-edge-connected components of your graph. When you have a simple graph, you can do that by finding all bridges in your graph in linear time, delete them and find the connected components in the resulting graph (every connected component corresponds to a vertex in the final graph).

Now to ensure that this works also in your case where you can have multiple edges between two vertices you can simply ignore when the above algorithm finds an incorrect bridge (u,v), where u and v are connected by multiple edges. Don't delete this edge from your graph when this happens. To detect when this happens you can first find all duplicate edges (either by sorting all edges first or using some hashing method), store those edges in a container where they can efficiently be searched (hashing or binary search) and then for every detected bridge, test if it is in that container.
> 1 votes

---
Tags: graphs, trees
---


# Question
Title: Estimating the range of $1$'s in an array of $0$'s and $1$'s
I have a large array $A$ that contains something like $\[0..1..0..\]$. It has a continuous range of $0$'s, followed by a range of $1$'s, and then another range of $0$'s.

This array is large and access is expensive, so I want to use a sampling algorithm to estimate the range $(i, j)$, where $A\_i$ is the first $1$ and $A\_j$ is the last $1$. Let's say I want to approximate this within an error of $\epsilon n$ where $n$ is the size of $A$, so that I get a range $(i', j')$ where $|i' - i| \leq \epsilon n$ and $|j' - j| \leq \epsilon n$.

What is an algorithm I can use to achieve this?

# Answer
> 1 votes
If c \< 0.5 then this can't be done faster than O(n). Assume the array is all zeroes, with a single 1 somewhere in the middle. You have to examine array elements at least until you find the 1, or until you are left with an unexamined subarray of size 2cn. Since you have no clue where the 1 is, it might take n attempts to find a 1, and n - 2cn attempts until you can give a result with an error less than cn in i and j. (If you are left with an interval of size 2cn you just let i = j = middle of the interval).

Obviously if c \>= 0.5 then you can let i = j = n/2, and the error is less than cn whatever the correct values are.

---
Tags: algorithms
---


# Question
Title: Proof of sparsification lemma: What exactly does the $\pi$ operator do?
In their proof of the sparsification lemma, Impagliazzo et. al describe the following operator $\pi$:

For a familiy of sets $\mathcal{F}$, let $\pi(\mathcal{F}) \subseteq \mathcal{F}$ be the family of all sets $S$ in $\mathcal{F}$, such that no other set $S'$ in $\mathcal{F}$ is a proper subset of $S$.

I am trying to understand what this operator does. So far, I thought that it could be calculated by the following algorithm:

$$ \text{While}~\exists S\_i, S\_j \in \mathcal{F}: S\_i \subset S\_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S\_i$$

By the rest of the proof seems to indicate that actually, one has to remove the superset: $$ \text{While}~\exists S\_i, S\_j \in \mathcal{F}: S\_i \subset S\_j \text{do} \\ \mathcal{F} \leftarrow \mathcal{F} \setminus S\_j$$

Which leads me to believe that I did not fully understand the description of the operator. What would be an algorithm to calculate that $\pi(F)$?

# Answer
> 4 votes
From the definition you gave, the supersets have to be removed, as you want to keep only those sets for which there is no proper subset in $\mathcal{F}$.

For example:

In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.

---
Tags: complexity-theory, sets
---


# Question
Title: Is there an algorithm to share parts of strings?
Let's say that we have the strings `Hello, World`, `Hello` and `World`. The algorithm I am thinking of would create an immutable buffer that contains `Hello, World` and the previous three would then become references or slices of that one like `buf[0,11], buf[0,4], buf[7,11]`.

A way to implement this algorithm would be to compare all new strings to the existing buffer and reuse it if possible or append the new string if that's not the case. This would be very slow, but it should work. However, it does not efficiently handle a case like `Hey, Hello` because it would either append it to the buffer, adding `Hello` again, or add `Hey,` to the beginning and update all the indices.

If saving space is the optimal solution, then the final buffer would be `Hey, Hello, World`.

**Is there any algorithm that does something similar?**

I have read about ropes, and read this article, but I do not see how these would help.

**EDIT**: this is indeed a shortest superstring problem, but the implementations I have found (,) assume that no string in the array could be a substring of another one, which is not the case here.

# Answer
It is a **shortest superstring problem** and not allowing internal substrings is just an implementation detail.
> 0 votes

---
Tags: strings, substrings, string-matching
---


# Question
Title: Sliding Window Dictionary String Matching
Consider the following problem. We are given a set of patterns (strings) $\Pi = \\{\pi\_i\\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every pattern in $\Pi$ is contained in the substring $s\[i:i+k\]$.

Can this be solved in linear- or near-linear-time? It can of course be solved in quadratic time $O(|s| |\Pi| + \sum |\pi\_i|)$ using KMP or Aho-Corasick plus post-processing.

The motivation for this problem is finding matches for a topic (represented by the set of patterns) in a text. In that context it actually makes sense to require the matches to be non-overlapping so I'm also interested in that case, but it might be easier to start with the relaxed version.

I would also be interested in generalizations of the problem that allow for approximate matches of some kind, eg, only requiring a threshold on the size of the subset of matching patterns, allowing matches within given edit distance, or something using hidden Markov models or general probabilistic graphical models. I would be surprised if any such generalization can be solved in subquadratic time though.

# Answer
> 1 votes
Since you want to detect all patterns at once, you can throw away any pattern if it is a substring of another one.

Since no pattern is a substring of another one, occurrences can neither begin nor end at the same position.

This means that when the window slides, at most one new occurrence appears and at most one disappears.

You can easily count how many times each pattern occurs inside the window, while it slides: increment the pattern’s count (and store where the occurrence begins) when detected by Aho-Corasick, decrement once the beginning is outside the window.

This should solve your problem in $\mathcal{O}(|s|+\sum{|\pi\_i|})$

# Answer
> 1 votes
The set of all $k$-length strings that contain every pattern in $\Pi$ is regular; call it $L$. (It is $(\Sigma^\* \pi\_1 \Sigma^\* \cap \dots \cap \Sigma^\* \pi\_m \Sigma^\*) \cap \Sigma^k$.) From this, you can form a nondeterministic finite-state automaton (NFA) that recognizes $\Sigma^\* L$. Next, convert this to a DFA. Finally, run the DFA across the input string $s$. You can then obtain all locations in the string where the DFA is in an accepting state; each such location is an index $i+k$ so that $s\[i:i+k\]$ matches all patterns in $\Pi$.

The running time will be linear in $|s|$ and the size of the DFA. I expect the size of the DFA to be exponential in $\Pi$ and $k$, but independent of $|s|$. So, if you only care about the dependence on $|s|$, this algorithm might meet your requirements. If you additionally care about the dependence on $\Pi$ and/or $k$, I do not expect this will meet your requirements.

---
Tags: strings, substrings, string-matching, exact-string-matching
---


# Question
Title: Average branching factor of an undirected graph
I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every spanning tree of the graph.

I know that, given a tree of $n$ nodes, an average branching factor $b\_f$ and $n\_l$ leaf nodes, these three variables are related as follow:

$$b\_f = \frac{e}{n-n\_l} \Rightarrow n\_l = n - \frac{e}{b\_f}$$

where $e = n - 1$ (the number of edges).

However, if instead of an undirected tree you have an undirected graph of $n$ nodes and $e = n - 1 + k$ edges (or with $k$ fundamental cycles), different traversals of the graph would give you different spanning trees, depending on which one of those $k$ edges are the one being ignored from the graph.

Is there any known property of graph's spanning trees that can offer an upper bound on the number of resulting leaves nodes of any traversal?

My best approximation so far is that, the maximum number of leaves must be bounded by $$n\_l \<= |\\{n\_{e^1}\\}| + 2k$$ where $|\\{n\_{e^1}\\}|$ is the number of nodes of the graph with degree 1, and $k = e - n + 1$.

That's a worst case scenario where there exists $k$ edges in the graph connecting nodes with degree 2 each, whose removal doesn't create new connected componentes, because removing them will give $2k$ nodes with degree 1 each, and thus $+ 2k$ leaves. If $k$ is very low that can be an acceptable good approximation, but the biggest the connectivity of the graph, the worst the significance of the approximation.

If someone could give a better approximation based on the average degree of the graph or something similar that can be calculated on a first traversal would be appreciated.

# Answer
Just to make it clear, the problem of finding a spanning tree with a maximum number of leaves is NP-hard. There's a simple 2-approximation algorithm due to Solis-Oba \[1\] which looks implementable with reasonable effort. In fact, I don't think anything better is known. There are other algorithmic approaches as well (e.g., FPT algorithms), but I'm not sure if these are that practical.

For a good overview of spanning trees in general, you can have a look at the survey of Ozeki and Yamashita \[2\]. Particularly, Section 6.1 is on spanning trees with many leaves and gives some combinatorial results.

---

\[1\] Solis-Oba, Roberto. "2-approximation algorithm for finding a spanning tree with maximum number of leaves." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 1998.

\[2\] Ozeki, Kenta, and Tomoki Yamashita. "Spanning trees: A survey." Graphs and Combinatorics 27.1 (2011): 1-26.
> 1 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: Number of Configurations of LBA(Linear Bounded Automaton)
The lemma is:

> Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet. There are exactly $qng^n$ distinct configurations of $M$ for a tape of length $n$.

I want know why LBA has $qng^n$ configurations.

Following is the proof:

> A configuration of $M$ is like a snapshot in the middle of its computation. A configuration consists of the state of the control, position of the head, and contents of the tape. Here, $M$ has $q$ states. The length of its tape is $n$, so the head can be in one of $n$ positions, and $g^n$ possible strings of tape symbols appear on the tape. The product of these three quantities is the total number of different configurations of $M$ with a tape of length $n$.

# Answer
> 2 votes
If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options for the first three symbols and so on. If you are not convinced, try it with for example a $3$-symbol alphabet.

Since your tape has length $n$ there are $n$ possible head positions, so you multiply the number of strings on the tape with $n$.

Finally, there are $q$ states, so for every possible string on tape and every possible head position, we can be in either of the $q$ states, making $qng^n$ configurations of the Turing machine.

---
Tags: turing-machines, automata, linear-bounded-automata
---


# Question
Title: Intuition behind this specific algorithm for time series
Going through the EPI book and I need some help understanding this part.

There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The input is given as a list of ints. The example they give is:

```
[12, 11, 13, 9, 12, 8, 14, 13, 15]

```

So here the maximum profit from a single buy-sell event is 7; buy at 8 and sell at 15. From two buy-sell events it is 10; buy at 9, sell at 12 and buy at 8, sell at 15.

The intuition for a single buy-sell is simple where we just keep track of the minimum element in the list and the difference between the minimum and the current element is the profit.

What I don't understand is how the double buy-sell formula works. The book proposes a solution where two passes are made through the data, a forward and a backward pass. The forward pass uses the same formula as above (single buy-sell), but the backward pass starts at the back of the list and keeps track of the maximum instead. The profits of the backward pass are stored in an array and added to the profits of the forward pass with $M\[i\] = F\[i - 1\] + B\[i\]$, and where $F\[-1\] = 0$.

Why does the backward pass keep track of the maximum, and how does the formula ensure that we won't buy before the second sale?

Here is the solution code given:

```
def buy_and_sell_stock_twice(prices: List[float]) -> float:
    max_total_profit, min_price_so_far = 0.0, float('inf')
    first_buy_sell_profits = [0.0] * len(prices)
    for i, price in enumerate(prices):
        min_price_so_far = min(min_price_so_far, price)
        max_total_profit = max(max_total_profit, price - min_price_so_far)
        first_buy_sell_profits[i] = max_total_profit
    # Now for the backwards pass.
    max_price_so_far = float('-inf')
    for i, price in reversed(list(enumerate(prices[1:], 1))):
        max_price_so_far = max(max_price_so_far, price)
        max_total_profit = max(
            max_total_profit,
            max_price_so_far - price + first_buy_sell_profits[i - 1])
    return max_total_profit

```

I broke down the iterator in the reverse pass and it creates:

```
[(8, 15), (7, 13), (6, 14), (5, 8), (4, 12), (3, 9), (2, 13), (1, 11)]

```

The expected backwards pass result is also provided for the sample data:

```
B = [7, 7, 7, 7, 7, 7, 2, 2, 0]

```

Looking through the code I can see how the algorithm can be used to populate B. What doesn't make sense is why this backwards pass guarantees the max profit, how it guarantees sane buys and sells, and what the intuition is for doing it this way.

I looked at similar questions but they provide different solutions which work great but don't provide any insight on the book's solution. The book is also not readily available online so there is less content on the material.

# Answer
During the forward pass, you compute `F` such that `F[i]` represents the maximum possible profit when restricting yourself to the elements with indices `0,1..,i`.

During the backward pass, you compute `B` such that `B[i]` represents the maximum possible profit when restricting yourself to the elements with indices `i,i+1,..,n-1` (where `n` is the size of your list). The reason you track the max is that because you are going backwards in time when populating `B`, you want to sell before you buy.

Now `M[i] = F[i-1] + B[i]` represents the maximum profit when doing a first buy/sell among indices `0,1..,i-1` and a second buy/sell among indices `i,i+1..,n-1`, so you are sure that the first sell will happen before the second buy (because the first sell happens at index `i-1` at the latest and the second buy at index `i` at the earliest).

Reciprocally, suppose the optimal solution has two buy/sell's happening at indices `b1, s1, b2, s2` (in increasing order). Then you know that `M[b2]` will be at least as big as the profit achieved by this solution (equal in fact, because it can't be bigger) as `b1,s1` happens before index `b2`, and `b2,s2` happens after (or at) `b2`.

Thus, by taking the maximum over all `M[i]` you will necessarily hit `M[b2]` at some point and get the maximum profit. And if the optimal solution has only one buy/sell it will be at `M[0] = F[n-1] = B[0] = M[n-1]` which you also consider.
> 1 votes

---
Tags: algorithms, optimization, python
---


# Question
Title: Is P^SAT with only one query equal to the union of NP and coNP?
I have a following problem:

Let $P^{SAT\[1\]}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle).

Assume that: $\mathrm{co}NP \neq NP \neq P$

Decide if $coNP \cup NP \neq P^{SAT\[1\]}$ or $\mathrm{co}NP \cup NP = P^{SAT\[1\]}$.

I know how to show that $\mathrm{co}NP \cup NP \subseteq P^{SAT\[1\]}$.

But I have no idea what about inverse direction. Any tips?

# Answer
> 2 votes
Under the assumption that $NP\neq \mathrm{co}NP$, we have that:

$$P^{SAT\[1\]}=NP\cup \mathrm{co}NP\implies P^{NP\[1\]}\neq P^{NP\[2\]}$$

**Proof**: Since $D^p\subseteq P^{NP\[2\]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP\[2\]}$.

Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due to $SAT\notin \mathrm{co}NP$. So, $(SAT\dot{\land}UNSAT)\notin NP\cup \mathrm{co}NP=P^{NP\[1\]}$.

We conclude that $P^{NP\[1\]}\neq P^{NP\[2\]}$.$\blacksquare$

In the above, $(SAT\dot{\land}UNSAT)=\\{(\phi\_1,\phi\_2)\mid\phi\_1\in SAT \land \phi\_2\in UNSAT\\}$.

So, though it might be tempted to push $P^{NP\[1\]}$ downto $NP\cup \mathrm{co}NP$, this result (if true) could tell us more about where the polynomial-time hierarchy $PH$ would actually collapse to. And, in this case, your proposition would save $PH$ from collapsing to $P^{NP\[1\]}$.

# Answer
> 0 votes
Hint (noting the homework tag on the other post): $P^{SAT}$, by the Cook-Levin theorem, is the same as an $NP$ oracle. Given that $\text{co-}NP \neq NP$, what does this imply?

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


# Question
Title: Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?
Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of the variables in an equation, we can deduce the missing one.

> Does there exist a set of variables $R \subseteq V$ with $|R| \leq k$ such that revealing these variables allows us to deduce all variables?

Is this problem NP-complete? What if all equations have degree $\leq d$?

I'm ultimately interested in the search version of this problem (where we actually need to find minimal $R$).

# Answer
> 1 votes
Yes, it is $NP$-complete even if $d=4$.

*Note that unless $P=NP$, we cannot prove $NP$-completeness for $d=2$ because it is merely the problem of counting the number of connected components of a given graph.*

Reduce from **Exact-Cover-by-$3$-sets** (**X3C**).

Given an instance of **X3C**, we construct an instance of our problem as follows.

The set of elements is $E=\\{e\_1,e\_2,\dots,e\_n\\}$.
The set of $3$-sets is $C=\\{s\_1,s\_2,\dots,s\_m\\}$.

This will be a **YES** instance (of **X3C**) iff there exists $C'\subseteq C$ with $|C'|=\frac n3$ that cover each element exactly once.

Now, set the set of variables $V=C\cup E\cup C^{up}$ where $C^{up}=\\{s\_j^{up}|s\_j\in C\\}$, that means each element is a varialbe and each $3$-set is also a variable. And for each set $s\_j$, we add a new variable $s\_j^{up}$.

*Note that, **X3C** remains $NP$-complete even when each element belongs to at most $2$ sets and each pair of $3$-sets shares at most one element.*

So, here come the equations.

For each $3$-set $s\_j\in C$ where $s\_j=\\{e\_a,e\_b,e\_c\\}$, add the following equations:

* $\\{s\_j,e\_a,e\_b,e\_c\\}$
* $\\{s\_j,s\_j^{up}\\}$
* $\\{s\_j,s\_j^{up},e\_a\\}, \\{s\_j,s\_j^{up},e\_b\\}, \\{s\_j,s\_j^{up},e\_c\\}$

Finally, set $k=\frac n3$.

We have done with our reduction. Now we have to prove its correctness.

**Proof of correctness:** (*sketchy*)

For one direction, if we have a solution $C'$ to our given **X3C**, it is obvious that $C'$ is also a solution to our instance.

For the other direction, note that it is w.l.o.g to assume that a (minimal) solution contains only variable in $C$. Because if it contains an element (in $E$), we can safely remove it from the solution and add one of the containing $3$-sets (that the element belongs to) to the current solution (if that set has not already been present in the current solution).

So, now a subcollection $C'\subseteq C$ is a solution to our problem. We show that it is also a solution to the original **X3C** instance.

For each $s\_j\notin C'$, it must be the case that all $3$ contained elements of $s\_j$ must be deducible. For otherwise, $s\_k$ becomes unreachable.

For each element $e\_i\in E$, it must be the case that one of the $2$ sets containing it must be included in $C'$.$\blacksquare$

---

Take @xskxzr's example: The given X3C instance is $E=\\{e\_1,\dots,e\_9\\}$, $C=\\{s\_1,\dots,s\_5\\}$ where $s\_1=\\{e\_1,e\_2,e\_3\\}$, $s\_2=\\{e\_4,e\_5,e\_6\\}$, $s\_3=\\{e\_2,e\_5,e\_8\\}$, $s\_4=\\{e\_6,e\_7,e\_9\\}$, $s\_5=\\{e\_1,e\_4,e\_7\\}$.

Our set of variables will be $V=C\cup C^{up}\cup E=\\{s\_1,\dots,s\_5,s\_1^{up},\cdots,s\_5^{up},e\_1,\dots,e\_9\\}$.

Our set of equations will be:

* $\\{s\_1,s\_1^{up}\\},\dots,\\{s\_5,s\_5^{up}\\}$
* $\\{s\_1,e\_1,e\_2,e\_3\\}$, $\\{s\_2,e\_4,e\_5,e\_6\\}$, $\\{s\_3,e\_2,e\_5,e\_8\\}$, $\\{s\_4,e\_6,e\_7,e\_9\\}$, $\\{s\_5,e\_1,e\_4,e\_7\\}$
* $\\{s\_1,s\_1^{up},e\_1\\},\\{s\_1,s\_1^{up},e\_2\\},\\{s\_1,s\_1^{up},e\_3\\}$
* $\\{s\_2,s\_2^{up},e\_4\\},\\{s\_2,s\_2^{up},e\_5\\},\\{s\_2,s\_2^{up},e\_6\\}$
* $\\{s\_3,s\_3^{up},e\_2\\},\\{s\_3,s\_3^{up},e\_5\\},\\{s\_3,s\_3^{up},e\_8\\}$
* $\\{s\_4,s\_4^{up},e\_6\\},\\{s\_4,s\_4^{up},e\_7\\},\\{s\_4,s\_4^{up},e\_9\\}$
* $\\{s\_5,s\_5^{up},e\_1\\},\\{s\_5,s\_5^{up},e\_4\\},\\{s\_5,s\_5^{up},e\_7\\}$

And $k=\frac n3=3$.

# Answer
> 1 votes
Based on Thinh D. Nguyen's answer I think I have a simpler (to understand) reduction showing the problem is at least as hard as SET COVER.

The core of the construction is a one-way deduction relationship $a \to b$. Split $a$ into two variables, $a$ an $a'$ and add equations:

$$\\{a, a'\\}, \\{a, a', b\\}$$

Then given either $a$ or $a'$ we can deduce $b$, but not the other way around. Given $b$ we can not deduce either $a$ or $a'$ unless we already knew one of them, in which case we already knew both of them and thus we deduced no new information. This can be generalized, e.g. $a \wedge b \to c$:

$$\\{a, a'\\}, \\{b, b'\\}, \\{a, a', b, b', c\\}$$

Now in SET COVER we have a universe $U$ and some collection of sets $S$ all with elements from $U$. Can we find $k$ sets in $S$ such that their union is the universe?

Let the universe of elements be $U = \\{e\_1, e\_2, \dots, e\_n\\}$ and our collection of sets $S = \\{s\_1, s\_2, \dots, s\_m\\}$. For each element $e\_i \in U$ add variables $e\_i, e\_i'$ and equation $\\{e\_i, e\_i'\\}$, and for each $s\_i \in S$ add variables $s\_i, s\_i'$ and equation $\\{s\_i, s\_i'\\}$.

We want to add the one-way reduction from the sets to their elements. For all $e\_j \in s\_i$ add equation $\\{s\_i, s\_i', e\_j\\}$.

Note that a minimal YES instance only ever has to pick out of the $s$ variables, as the $e$ variables are all implied by an $s$ variable and not the other way around. Thus we pick our $k$ sets from the $s$ variables.

To set up a one-to-one correspondence between SET COVER and the above we want to deduce everything if we manage to deduce the universe from our $k$ set choices. To do that we add equations

$$\\{e\_1, e\_1', e\_2, e\_2', \dots, e\_n, e\_n', s\_i\\}$$

for all $s\_i$. As we've seen before this equation is a one-way deduction from $e\_1 \wedge \dots \wedge e\_n \to s\_i$, and thus does not provide any information if you hadn't already deduced the entire universe of elements from your initial $k$ set choices. However if you did manage to do that, now we we can deduce every single variable and our instance is YES iff the SET COVER instance is YES.

---
Tags: graphs, np-complete, reductions
---


# Question
Title: O(1) distinct elements in an array implies?
Could someone explain the following question -

Given the following statement viz. Consider an input array a\[1..n\] of arbitrary numbers. It is given that the array has only O(1) distinct elements. What does the statement imply ?

Thanks.

# Answer
> 2 votes
Essentially, it means no matter what the size of the array is (namely, no matter what $n$ is), it will have no more than a fixed constant number of distinct elements. This assumes that you know what the term $O(1)$ means. If not, ask for clarification.

---
Tags: algorithms, asymptotics
---


# Question
Title: Ford Fulkerson maximum flow for all vertices
Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, once for each $t$. I feel like there must be a faster way to compute all $|V|-1$ max flows that makes use of dynamic programming techniques. Any ideas?

# Answer
"J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." provides an algorithm to compute the min cut for a fixed s on the source side with time-complexity $O(nm \log(n^2/m))$, by reducing the complexity of multiple s-t cuts for varying sinks to the complexity of a single call to the Push-Relabel max-flow algorithm.

This might be adaptable to a version where you can store all the intermediate min-cut values (=max-flow values) for all sinks along the way.
> 0 votes

---
Tags: graphs, dynamic-programming
---


title: Counting common values in two arrays

text:
# Question
Title: Counting common values in two arrays
> given two arrays of integers A and B of size m, with values in the range \[-n,n\]. I want an algorithm to count how many common values are in A and B , if a value is repeated we only count it once , for example : $A=\\{2,2,14,3\\}$ and $B=\\{1,2,14,14,5\\}$ the algorithm should return 2 . Problem is I need to do this in $O(m)$ time.

My attempt was to create an array $C$, of size $2n$. and increment all the values of $A$ and $B$ by $n$, and count the values of $A$ like: $C\[A\[i\]\] = 1$ that would take me $O(m)$ time , and $O(1)$ time to create the array. then going over $B$ and counting how many $1's$ I encounter in $C$.

So far it sounds good, however I have no idea what's in $C$ in the first place and it could be that there's a $1$ in there already and that would increment the counter falsely , and initializing $C$ would take $O(n)$ time.

Any ideas? Thanks ahead.

# Answer
Try the following algorithm:

1. For $1 \leq i \leq m$: $C\[A\[i\]\] = 0$
2. For $1 \leq i \leq m$: $C\[B\[i\]\] = 1$
3. Initialize *answer* to $0$
4. For $1 \leq i \leq m$:
    * If $C\[A\[i\]\] = 1$ then $C\[A\[i\]\] = 2$ and increment *answer*
5. Return *answer*
> 4 votes

---
Tags: time-complexity, arrays
---


# Question
Title: Doubt in definition of closure under concatenation operation in Recursive Enumerative languages
I recently started studying theory of computation.

Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.

Please Note - RE shortform i am taking for Recusively enumerative language

One way --\> If L1, and L2 are RE s then L1.L2 is RE then RE is closed under concatenation.

Another way if we talk interms of strings, If for all ‘a’ belongs to L1 and for all ‘b’ belongs to L2 then w=a.b belongs to L1.L2.

What about the other side? Please see if this is correct?

> For closure under concatenation, If w belongs to L1.L2 then **all** or **some** string splits of w into 2 make 1st part acceptance under L1 and 2nd string split acceptance under L2?

I was thinking, as L1 and L2 are REs we can make L1.L2 RE by concatenating L1 and L2 turing machines and make start state as start state of L1 and endstate as final state of L2. But when i am thinking in terms of string input i am getting confused

THe proof in my textbook says that we can non-deterministically split w into 2 parts so that each part accepted by Turing machines for L1 and L2 respectively. If string length is n, then we can have (n+1) kinds of 2 splits of w-string. Will the L1.L2 turing machine accepts all these n+1 types of w-splits? But this is what we need to prove right?

# Answer
> 1 votes
If $L\_1,L\_2$ are two languages over a common alphabet, then their concatenation is given by $$ L\_1 L\_2 = \\{ x\_1 x\_2 : x\_1 \in L\_1 \text{ and } x\_2 \in L\_2 \\}. $$ If $L\_1,L\_2$ are r.e. then so is their concatenation. To see this, you can use the following algorithm. Given an input $x$, consider all possible partitions $x = x\_1x\_2$. For each partition, run a machine for $L\_1$ on $x\_1$ and a machine for $L\_2$ on $x\_2$; do this in parallel for all possible partitions. Accept if for some partition $x = x\_1x\_2$, you find that both $x\_1 \in L\_1$ and $x\_2 \in L\_2$.

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


title: Find shortest paths in complement graph

text:
# Question
Title: Find shortest paths in complement graph
I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the **complement graph** (undirected). The algorithm should run in $O(V+E)$ time, where $E$ is the number of edges in the original graph (not the complement graph).

If $G$ is a graph, the complement graph is defined to be the following graph: $e$ is an edge in the complement graph, if and only if it isn't an edge in the original graph. In other words we delete all existing edges, and add all the edges that were missing from the original graph.

So first I of course thought of "building" the complement graph (replacing the vertices in the adjacency list with those that don't appear there), then running BFS on the new list, but of course that would mean that the run-time would be based on the edges in the complement graph, not the original one.

I also noticed of course that after running BFS on the original graph, any vertex that has a distance from $s$ that is greater than 1 (in the original graph) should become 1 in the complement graph (because if they weren't neighbors in the original graph, they are neighbors in the complement graph). But I couldn't get the algorithm to continue according to some specific rules as to when should the distance be updated and to what. Any suggestions?

# Answer
> -2 votes
I personally, do not see why this is left as **unanswered**.

Finding something in complement graph and finding that same thing in the graph is essentially have the same time complexity (up to constant factor).

Since swapping between edge $(u,v)$ and non-edge $(u,v)$ is just $O(1)$-time operation. We do not have to transform or convert anything just **negate every query output**.

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


title: Filler Algorithm

text:
# Question
Title: Filler Algorithm
I am curious to know if there is an algorithm that, given an array of decimals and integers, and given an integer, returns a sequence in descending order, composed of those numbers of the input array whose sum is as close as possible to the number of input, or even be identical, but not greater.

I wonder if there is something similar, and I wonder if it also has a name, this algorithm.

Thanks in advance!

# Answer
> 0 votes
There are two famous problems that are similar to what you're looking for. Yours comes closest to the subset sum problem https://en.wikipedia.org/wiki/Subset\_sum\_problem.

Similarly we have the knapsack problem which revolves around the same idea with the general restriction that items have specific values which should also be taken into account. https://en.wikipedia.org/wiki/Knapsack\_problem

Since any integer can be represented as a decimal number your problem can be transformed into either of these problems. In the case of the knapsack problem you would simply set the value of each item to its decimal value.

Both of these problems are NP-complete which means that the only way to calculate the actual maximal achievable value (at the moment) is brute force, although there are pseudopolynomial dynamic programming approaches.

The fact that the output seemingly needs to be ordered is unimportant; there are some very efficient sorting algorithms out there.

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


# Question
Title: What's an upper bound for this recurrence so I can take advantage of the Master Theorem?
Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + 2T(\sqrt{N}) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$

where $\varphi(N)$ is Euler's totient function. My objective is to find an upper bound so that I can apply the Master Theorem and find a closed-form formula.

# Answer
In order to make this answer self-contained, I will repeat the first part of my answer to your other similar question.

---

First, show that for $N\>2$, $\phi(\phi(N)) \< N/2$. This can be done as such:

Let $N = \prod\_{i=1}^rp\_i^{k\_i}$ be the prime factorisation of $N$ ($p\_i$ prime, $k\_i\>0$)

* Suppose $N$ is even. Then $\phi(N) = N\prod\_{i=1}^r(1-\frac{1}{p\_i}) \leq N(1-\frac{1}{2}) \leq N/2.$ Thus $\phi(\phi(N)) \< N/2$.
* Suppose $N$ is odd and $N \> 1$. Then $\phi(N) = \prod\_{i=1}^r (p\_i-1)p\_i^{k\_i-1}$ is even and smaller than $N$. By the previous result $\phi(\phi(N)) \< N/2$.

So we get the desired result.

---

Now, let $k\>2$ be some fixed integer, and suppose $N\geq k^2$. You can write: $$T(N) = T(\phi(N)) + 2T(\sqrt{N})+\lg(\phi(N))^3 $$ $$T(N) = T(\phi(\phi(N))) + 2T(\sqrt{\phi(N)})+\lg(\phi(\phi(N)))^3 + 2T(\sqrt{N})+\lg(\phi(N))^3$$ $$T(N) \leq T(N/2) +4T(N/k) + 2\lg(n)^3.$$ Where we used that $N\geq k^2 \implies T(\sqrt{\phi(N)}) \leq T(\sqrt{N}) \leq T(N/k)$ in the last step.

(Note that I am implicitly assuming $T(n)$ is a monotonically increasing function. One could get rid of that assumption by working on $S(n) = max(T(n),S(n-1))$, at the cost of making the argument more tedious and harder to follow)

---

Now we can apply the Akra-Bazzi method (a generalisation of the master theorem) with:

* $k = 2$
* $a\_1 = 1$, $b\_1 = \frac12$, $a\_2 = 4$, $b\_2 = \frac1k$
* $g(x) = 2\lg(x)^3$

First we need to find $p$ such that $a\_1b\_1^p + a\_2b\_2^p = 1$, that is: $$(\frac12)^p+4(\frac1k)^p = 1 \\;\\;\\; (\*)$$ Let's call $p\_0$ the solution to $(\*)$.

Then, we need to plug $p = p\_0$ into the equation: $$T(N) \in O(N^p(1+\int\_1^N\frac{g(u)}{u^p+1}du))$$ To get:

$$T(N) \in O(N^{p\_0}(1+\frac{6(N^{p\_0}-1)}{p\_0^4N^{p\_0}\ln(2)^3})) \in O(N^{p\_0})$$ (I just trusted WolframAlpha and did some simplifications for the integral, I'm too clumsy/lazy to attempt it myself if I don't have to)

Notice that in $(\*)$ we can make $p\_0$ arbitrarily close to $0$ by picking a big enough $k$. In other words, for any $\epsilon \> 0$ there exists some $k\>0$ such that $p\_0 \< \epsilon$. So let's pick any $\epsilon \> 0$ and set $k$ such that $p\_0 \< \epsilon$. Plugging that into the last result we get:

$$T(N) \in O(N^\epsilon)$$

And this is true for any $\epsilon\>0$.

In other words, $T(N)$ grows slower than any polynomial function in $N$.

---

I suspect it is asymptotically not much bigger than $\lg(\phi(N))^4$, as the square root term will vanish pretty fast, but I can't prove anything better than what I showed.

Also note that you could use the master theorem by setting $k=2$ and working on the upper bound $T(N) \leq 5T(N/2) + 2\lg(N)^3$, but this would of course lead to a much weaker result.
> 2 votes

# Answer
What is $\varphi(p)$ when $p$ is prime? Why is this the worst case?

Note that the master theorem is not going to be applicable. It handles subdivision into subproblems whose size is a fixed proportion of the original problem's size: $2T(\sqrt N)$ doesn't fit this model.
> 1 votes

---
Tags: master-theorem
---


# Question
Title: confusion with worst case for direct addressing
In CLRS there is an exercise for direct address table

> Suppose that a dynamic set S is represented by a direct-address table T of length m. Describe a procedure that finds the maximum element of S. What is the worst-case performance of your procedure?

for this question i have seen a lot of websites indicating the worst case possibility is O(m) by starting and examining every non null slot up to end and then returning the maximum index, but i think it can be done in a faster way than that. If direct addressing tables has m slots , then obviously the highest value should be in the end (i thought keys are treated as indexes in direct addressing,correct me if i am wrong) , so if we start iterating from the end then worst case would be O(m-n) where n is the number of elements examined by our iterator before reaching non null value from end of the direct addressing table

is something wrong with my approach? Can any one clear this topic?

# Answer
When iterating from start to end, you always need to examine $m$ items, which is $O(m)$.
When iterating from end to start, in the worst case you need to examine $m - |S|$ items, then the answer depends on the relationship between $|S|$ and $m$.

If $m - |S|$ is const., it takes $O(1)$ time.
Otherwise since $0 \leq |S| \leq m$, we have $m - |S| \leq m$, the upper bound is also $O(m)$.

Then in either cases, as long as $m - |S|$ is not const., both approaches have $O(m)$.
> 3 votes

# Answer
A "direct-address table" maps a subset of keys from 0 to m-1 to values. It would be nonsense if the values were equal to the indices - in that case instead of a "direct-address table" we would just use a bitmap.

So while "dynamic set is represented by a direct-address table" is not defined, I assume the set elements are the values stored in the table. So to find the largest, you need to visit all the entries used for elements of the set, and since we don't know which entries correspond to set elements without checking that they are null, we need to visit all m elements of the direct-address table.
> -1 votes

---
Tags: algorithms
---