# Question
Title: Why is a threshold determined for Byzantine Fault Tolerance of an "Asynchronous" network? (where it cannot tolerate even one faulty node)
In following answer (**LINK:** https://bitcoin.stackexchange.com/a/58908/41513), it has been shown that for **Asynchronous Byzantine Agreement**:

> "we cannot tolerate 1/3 or more of the nodes being dishonest or we lose either safety or liveness."

For this proof, the following conditions/requirements has been considered:

> 1. Our system is **asynchronous**.
> 2. Some participants may be malicious.
> 3. We want safety.
> 4. We want liveness.

A fundamental question is that:

With considering the well-known paper titled: **"Impossibility of Distributed Consensus with One Faulty Process"** (**LINK:** https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

showing that:

**no completely asynchronous consensus protocol can tolerate even a single unannounced process death**,

Can we still assume that the network is asynchronous ? As in that case the network cannot tolerate even one faulty node.

# Answer
The answer has to do with tracking the precise assumptions that are made in these different results. In short, while both results assume asynchrony, the "impossibility of distributed consensus with one faulty process" requires a stronger form of liveness and determinism, and that makes consensus impossible.

### 1. Impossibility of Distributed Consensus with One Faulty Process

This seminal result (of Michael Fischer, Nancy Lynch, and Michael Paterson) is about distributed consensus where the system is not just asynchronous, but also satisfies:

* **Determinism.** The consensus algorithm does not use any randomness.
* **Liveness under message delays.** Not only may messages be delayed arbitrarily, but we also must guarantee liveness even in the presence of such continued delays.

Let us see why tehse properties are too strong, and make distributed consensus impossible.

Consider an example: Alice, Bob, and Charlie are friends and want to decide on where to meet for dinner. It is possible that one of them unexpectedly goes AWOL (or decides they are not interested in being friends anymore) and stops responding to messages. In this case, the other two can still decide on a place to meet. Now what should they do?

The obvious approach would be that:

> Alice just decides where to go, and tells Bob and Charlie.

But this does not work because Alice may be the one who goes AWOL. So to fix this, the next most obvious approach might be:

> Both Alice and Bob tell everyone else where to go. If everyone hears from Alice, then they will go where Alice says; otherwise, they will go where Bob says.

But this has a new problem. Suppose you are Charlie. If you hear from Alice, you know where to go. If you hear from neither of them, you wait to hear. The problem is when you have heard from Bob, but not Alice. Because there are arbitrary message delays, you cannot commit to go where Bob said: Alice might have said where to go, and you just have not received it yet! So you are completely stuck, and if it happens that Alice has gone AWOL, you will just keep waiting forever.

The problem here is that we have no way to abort the transaction; no way to say, "OK, this isn't working, it's been too long and I haven't received a delay -- let's try again." Real-world consensus algorithms (the best known being Paxos) have the possibility that rounds fail due to network delays, and in this case they just try again, hoping for shorter network delays. Additionally, it is possible to get around the problem by using randomized protocols which *usually* work, and only go on forever with small (or even zero) probability.

### 2. Asynchronous Byzantine Agreement where less than $1/3$ of the nodes fail

The bitcoinSE post you link glosses over the issue of liveness, saying only that it is "the ability to continue to make forward progress". In fact, the above result shows that the strongest form of this is impossible, so we have to relax our requirements / assumptions.

Let's consider two examples. In Miguel Castro and Barbara Liskov's "Practical Byzantine Fault Tolerance", they achieve practical liveness with less than a third of nodes being faulty by *assuming that message delays do not continue to grow indefinitely*. As the authors state:

> We guarantee liveness, i.e., clients eventually receive replies to their requests, provided at most $\frac{n-1}{3}$ replicas are faulty and $delay(t)$ does not grow faster than $t$ indefinitely...This is a rather weak synchrony assumption that is likely to be true in any real system provided network faults are eventually repaired, yet it enables us to circumvent the impossibility result in \[9\].

Here \[9\] is the impossibility result discussed above. In plain terms for our example, they avoid the above problem with Charlie by requiring a weak form of synchrony: Charlie does not simply have to keep waiting forever, as we know that message delays can only grow termporarily, and not indefinitely. (Of course the actual algorithm gets a lot more complex, but that is partly the conceptual idea of why liveness is possible.)

In Ran Canetti and Tal Rabin's "Fast Asynchronous Byzantine Agreement with Optimal Resilience", they use randomness to get liveness with less than $n/3$ Byzantine node failures. From their paper:

> In this setting, we describe an $(\lceil\frac{n}{3}\rceil- 1)$-resilient Byzantine Agreement protocol. With overwhelming probability all the non-faulty players complete the execution of the protocol. Conditioned on the event that all the non-faulty players have completed the execution of the protocol, they do so in constant expected time.

Here $(\lceil\frac{n}{3}\rceil- 1)$-resilient just means less than a third of nodes are Byzantine. Note the key words *with overwhelming probability.* So they have a probabilistic algorithm which has many possible "runs", and overwhelmingly most of them work. Note that the above impossibility result implies that there must always be *some* runs where liveness does not occur, i.e. there is no consensus:

> Fischer, Lynch and Paterson’s \[FLP\] seminal impossibility result for deterministic protocols implies that any (randomized) protocol reaching BA must have nonterminating runs.
> 2 votes

---
Tags: distributed-systems, security, consensus, fault-tolerance, byzantine
---


# Question
Title: Can the KenKen puzzle be solved using the same ideas as for Sudoku?
There are many ways of solving Sudoku puzzles, however two good approaches are the Algorithm X and solving using Linear programming. Is it possible to solve the KenKen puzzle using Algorithm X (turning the problem into an exact cover problem) or using Linear programming and how could that be done if possible?

Edit: Like the Sudoku, the KenKen puzzle has an NxN grid. Each row and column contain the numbers from 1 to N, so that a number can appear only once per row and per column (similar to the standard Sudoku). We define a "cage" to be a group of cells that are connected together and have a target and an operation. The idea is that all the numbers in the cage must be able to produce the target after applying the operation in between the numbers in the cage. There could be more than one instance of a number in a cage. The operations are +, \*, -, /. At the beginning the cages are divided from the other cages by thicker lines on the field and the target, together with the operation is shown for each cage. The cages are wmpty, meaning that no of the grid entries are filled. There could exist a cage with only 1 entry - then the cage has no operation and has to be filled with that number. You have to solve this puzzle for a given cages with targets ans operations.

A link to the Wikipedia page of the puzzle, where an example could be seen: https://en.m.wikipedia.org/wiki/KenKen

# Answer
> 1 votes
I don't think there's a simple way to express KenKen as an exact cover problem, although it's certainly possible since exact cover is NP-complete.

I think it would probably be easiest to express it as a SAT instance. Expressing Sudoku as a SAT instance is not hard, and the arithmetic constraints can just be expressed as the disjunction of all of the possible values which would satisfy the constraint (which you would then need to convert to CNF).

---
Tags: algorithms, optimization, linear-programming
---


# Question
Title: Can the same node appear twice in a tree?
Can the same node appear twice in a tree?

I'm asking about the node object itself, not the node's value. For example, in the following code, `a`'s left and right are the same node, `b`.

```
a = new TreeNode(1);
b = new TreeNode(2);
a.left = b;
a.right = b;

```

Is this valid? Why or why not?

# Answer
> 7 votes
A tree is *defined* to be a set of nodes, with a parent-child relationship that satisfies certain properties. Thus, it doesn't make sense to ask whether a node can "appear" twice.

In your code snippet, you have constructed a DAG, not a tree.

# Answer
> 4 votes
> Is this valid? Why or why not?

Mathematically it's not a tree. However, it would be allowed in some programming languages as a valid *representation* of a tree.

### Short answer

The reason it is not mathematically a tree is that the node `a` has two children, `b` and `b`, which are the same. This is not allowed in a tree. If you have multiple children they must all be different.

In general, a tree is a set of nodes, where each node is either a leaf, or it has some children. If it has children, then the two children must all be distinct, and all their descendants must be distinct. Also, there must be some "root" node which all other nodes are descendants of. This does not qualify for this definition.

### However...

There is a difference between a *tree* and a *representation of a tree*. In a programming language, a mathematical tree is represented in a certain way. So for example, in your code it is represented with some `TreeNode` objects which have a `left` and a `right` field.

Some programming languages would allow this code. It would represent the following tree:

```
   a
 /   \
b     b

```

Notice that this is a tree with *three* nodes, not two. That is why it is mathematically a tree: the two children in the above diagram are distinct. But they are *represented* in the same way, since they are both the same object `b`, i.e. they are both the same `TreeNode` object.

### Just for fun: infinite trees

Here is a fun consequence of what you have done, in programming languages that allow it: infinite trees! Consider this code:

```
a = new TreeNode(1);
b = new TreeNode(2);
a.left = b;
a.right = b;
b.left = a;
b.right = a;

```

The result of this innocent-enough seeming sequence of statements is that we get the following monstrous infinite data structure:

```
                   a
            /             \
         b                   b
     /     \            /       \
    a         a         a         a
  /   \     /   \     /   \     /   \
 b     b   b     b   b     b   b     b
...   ... ...   ... ...   ... ...   ...

```

This is a bit of a mess, so that is one reason programming languages might want to guarantee that all the nodes of a tree are represented distinctly, and so they might want to disallow the code that you wrote.

# Answer
> 1 votes
A (rooted) tree is a structure composed of a set of nodes (note: *set* has no "repeats", by definition), one of which is the root of the tree, and the others are arranged as trees, whose roots are children of the root. Note that we have a direction (from root to children, down to leaves --nodes with no children). There is exactly one path from the root to any node.

A somewhat related structure is a DAG (directed acyclic graph), where you have nodes connected by edges with a direction (one-way streets, in other words). Again,nodes are unique, but in a DAG several edges can end at the same node. What distinguishes a DAG is that there are no cycles, sequences of edges that start at a node and lead back to it.

Then there are directed graphs, nodes connected by directed edges, but no other restrictions.

What comes naturally in a program is to have nodes (structures in memory) that reference others (thus directed edges, this node references that one). The result isn't always a tree, not even a DAG.

---
Tags: programming-languages, trees, binary-trees
---


# Question
Title: "If A is nonregular, then there exists a nonregular language B such that A ∩ B is finite."?
Is the statement true?

I feel that the statement is true. I want to prove it but I don't know how to start the proof.

Any help would be appreciated.

# Answer
> 3 votes
Clearly if $A$ is non-regular, its complement is non-regular as well. Can you finish it now?

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


# Question
Title: What is the connection between the logic and the logic programming?
As I understand, then logic (i.e. particular theory of logic with some theory's axioms and some possible assignments of the variables) describes some specific world (in the non-modal case) or some set of related worlds (in the modal case) and deduction just explores this one world (this set of related worlds) and discovers/constrains the possible values of the variables (SAT problem).

But logic programming with its quite confusing implication relation (I still don't understand how the implication of the logic programming is related to the implication connective in the logic - those seem to be two completely different notions and different signs - am I right?) allows traveling among worlds (in modal case - among sets of related worlds): if variables {x} has some values in the one worlds, then those variables {x} has some different values in the other world. And it is the (one) semantics of the logic programming, that set of clauses that allow such traveling among worlds, at the end lands the traveller in one world that is fix-point for this set of clauses (of logic programming statements).

Computation is state transition: from one state to the other, from one world-state/world to the other world-state/world. But logical inference is just exploration of one world - be it discovery of the new relations among variables or statements (discovery of theorems) of be it discovery of the consistent set of assignments to the variables (discovery of the solution to SAT problem).

Am I right? What else can be added to this understanding between logic and logic programming?

Maybe there is some logic which allows to deduce the logic programs? To do the reasoning about the logic programs?

# Answer
> 4 votes
First, all this "worlds" stuff is unnecessary. It's a notion used in some semantics of modal logic. You don't need it to understand modal logic, let alone non-modal logics. This isn't to say it can't be useful, it's just that "worlds" is not some fundamental constituent of logic or their semantics, and, regardless, is not typically used outside of modal logics. As common logic programming languages (i.e. Prolog) are not based on modal logic, there's not much reason to bring it up nor concepts sometimes used in its semantics. You can have modalities in a logic programming language, e.g. LolliMon does. The notion of worlds doesn't really map well onto variable assignments. The problem, among other things, is that you can want multiple different assignments to the same variable at the same time.

Sticking to (pure1) Prolog, due to the restrictions on where you can place connectives, it turns out that it can be understood as operating in a logic with *no* connectives. Let's consider a fairly general example of a Prolog rule:

```
p(X,Y) :- q(X,Z), r(W); t(Y).

```

This corresponds to the logical formula: $$\forall X,Y.(t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\to p(X,Y)$$

First, we can eliminate the universal quantifiers and simplify things by considering entailments between open terms where the free variables will behave like constants. This more or less corresponds to $\forall$ introduction. So $\vdash \forall x.\varphi(x)$ becomes just $\vdash\varphi(x)$. Our example becomes: $$\vdash (t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\to p(X,Y)$$ We can use the $\to$ introduction (aka the deduction theorem) to eliminate the sole occurrence of $\to$ in any particular rule producing for our example: $$(t(Y)\lor(\exists Z.q(X,Z)\land r(W)))\vdash p(X,Y)$$ We can use the $\lor$ left rule of the sequent calculus **LK**/**LJ** to handle the disjunction. Alternatively we could have used the equivalence $(P\lor Q)\to R\equiv (P\to R)\land(Q\to R)$ before eliminating $\to$ and then used $\land$ introduction, then eliminate $\to$ to produce the same result. We could also eliminate disjunctions (';') via a standard source-to-source transformation of the Prolog that is based on these rules. Our example becomes a pair of entailments: $$t(Y)\vdash p(X,Y)\qquad \exists Z.q(X,Z)\land r(W)\vdash p(X,Y)$$ We can eliminate the existential with a $\exists$ left rule a la **LK**/**LJ** which is basically the dual of $\forall$ introduction and works the same way. That is, we just drop the existentials and the bound variables become free and are treated as constants. Alternatively, this could be understood in terms of the equivalence $(\exists x.\varphi(x))\to\psi\equiv\forall x.\varphi(x)\to\psi$. The relevant entailment of our example becomes: $$q(X,Z)\land r(W)\vdash p(X,Y)$$ Finally, we can use the $\land$ left rule to eliminate conjunctions, producing: $$q(X,Z),r(W)\vdash p(X,Y)$$ For an arbitrary (pure) Prolog program, the end result is that we have a collection of rules with a list of premises which consist of atomic formulas entailing a single atomic formula. All connectives can be eliminated. If you don't like this, you can easily go from here to the program corresponding to a series of axioms of the form $\forall\vec{X}.(p\_1(\vec{X})\land\cdots\land p\_n(\vec{X}))\to q(\vec{X})$, which are Horn clauses, or curry this to get rid of $\land$ producing $\forall\vec{X}.p\_1(\vec{X})\to(\cdots(p\_n(\vec{X})\to q(\vec{X})\cdots)$. This would mean you only need to understand universal quantification and implication, but even then neither ever occurs in a negative position, so you don't need their full generality which is part of why they can be eliminated. If you want to inject classical logic unnecessarily, you can use material implication and write $\forall\vec{X}.\neg p\_1(\vec{X})\lor\cdots\lor\neg p\_n(\vec X)\lor q(\vec X)$, and, instead of Cut below, we'd talk about Resolution.

Sticking to the connective-free version, how do we actually prove things? Well, we still have the structural rules. In particular, we have Cut which states (for our purposes): $$\dfrac{\Gamma\vdash P\qquad\Delta,P\vdash Q}{\Gamma,\Delta\vdash Q}$$ where $P$ and $Q$ are atomic formulas and $\Gamma$ and $\Delta$ are lists of atomic formulas. Cut corresponds to calling a subgoal.

For the top-level call that kicks off the execution of a Prolog program, we aren't trying to show whether the universal closure of the top-level goal is true, but rather listing all the bindings to free variables that makes the goal derivable. This can be seen as enumerating the derivations of $\vdash\exists\vec X.q(\vec X)$ if $q(\vec X)$ is the top-level goal.

For the connection to execution, I recommend getting familiar with the concept of an abstract logic programming language as defined in Uniform Proofs as a Foundation for Logic Programming. This shows how we can interpret connectives as instructions to proof search. By constraining the logic, we can make it so this operational interpretation of the connectives (and atomic formulas), can give a complete proof search procedure (for our highly restricted logic). The elimination of connectives that I've done shows that for Prolog (but not $\lambda$Prolog), the only operational interpretation we need is that of atomic formulas. Non-determinism arises from choosing which rule to use to derive the atomic formula and how to instantiate its free variables. Implementation-wise, the former is usually handled by backtracking and the latter by unification.

If you recorded the steps of the execution of a (pure) Prolog program, the result would be a derivation, i.e. a formal proof. There is no "satisfaction" involved. A Prolog program like `p :- q, r` does not try assigning different truth values to `q` and `r`. There's no way to express a contradiction in (pure) Prolog, so every (pure) Prolog program corresponds to a satisfiable formula.

Datalog is usually analyzed with a more semantic approach, but it has additional restrictions over (pure) Prolog to make this well behaved. Datalog is often implemented in a bottom-up manner where we generate a series of single-step deductions and grow the set of derived facts until we reach a fixed point. Prolog, however, is almost always implemented in a top-down manner where we backchain so that we only derive the facts that are relevant for our goal.

1 This excludes this like `assert`/`retract`, cut (`!`), and the negation-as-failure thing.

# Answer
> 1 votes
While @DerekElkins provided a proof theory perspective on Prolog, I want to provide a model theory perspective and contest the claim that no “satisfaction” is involved.

Prolog is connected to logic via its *denotational semantics* \[1\]. For example, the Prolog rule in another answer

```
p(X,Y) :- q(X,Z), r(W); t(Y).

```

is expressed in traditional logic notation as

$$\forall X (\forall Y (\forall Z (\forall W (p(X,Y) \impliedby q(X,Z)\land r(W)\land t(Y))))).$$

A Prolog program is expressed as the conjunction of all rules and facts which is a formula without free variables, in other words, a sentence in first-order logic. Hence we can talk of its models.

A simple model of every Prolog program that immediately comes to mind is the **greatest** model, in other words, the model where every predicate is true at every possible value of its arguments. This model is not interesting. The model that is sought for in logic programming is the **least** model. There is a theorem that such a model exists for every Prolog program. Logic programming offers a solution that is a little different to what mathematicians seek for.

Your “traveling among worlds” is a computation of this model or its part. Answering to a Prolog query is searching for variable assignments satisfying the conjunction of the Prolog program and the query. We need to implement a solution search of some kind if we wish to call this “programming”. This search algorithm is the *operational semantics of Prolog* and can define its semantics, but it does not offer a clear connection of Prolog to logic.

It is the nature of the problem that a Prolog variable has different value in different worlds (I guess that you mean worlds created by disjunction). Because Prolog has disjunctions. Actually, something similar happens in every programming language with variables. If a function has one parameter (a variable) and is called with arguments `0` and `1`, that parameter has different values in different invocations.

\[1\]: Lloyd, John W. *Foundations of Logic Programming*. 1st ed. Springer, 1987. Print.

---
Tags: logic, prolog
---


# Question
Title: What is Herbrand interpreration and model?
I was reading the book "Foundations of Logic Programming" written by J.W. Lloyd. In the book, there were definitions of interpretation and model, and when it comes to herbrand interpretation and model, I am having difficulties. It provided an example, but I did not understand it.

Example. Let $S$ be $\\{ p(a), \exists x \lnot p(x) \\}$. Note that the second formula $S$ is not a clause. We claim that $S$ has a model. It suffices to let $D$ be the set $\\{ 0,1\\}$, assign 0 to $a$ and assign to $p$ the mapping which maps 0 to true and 1 to false. Clearly this gives a model for $S$. However, $S$ does not have an Herbrand model. The only Herbrand interpretations for $S$ are $\emptyset$ and $\\{ p(a)\\}$. But neither of these is a model for $S$.

In my understanding, by assigning 0 to $a$ and 1 to $x$ to the formulas of $S$ make them true:

$$ p(0) = true $$

$$ \exists x \lnot p(x)\[x/1\] = \lnot p(1) = true $$

Therefore, $\\{ 0,1\\}$ is a model for $S$ But I did not really understand how do we know $\[a=0,x=1\]$ is not a herbrand model for $S$.

I asked the question in Theoretical Computer Science section, however was advised to post in CS. Could anyone explain it to me? Thanks in advance.

# Answer
Herbrand models have special domains. The domain of every Herbrand model for $S$ (which is a set of formulas of $L$) is the *Herbrand universe* $U\_L$ for $L$. The set $U\_L$ cannot be $\\{0, 1\\}$, it has a totally different form, see the definition of Herbrand universe in Chapter 1 “Preliminaries”, §3 “Interpretations and models”. The set $U\_L$ can contain $p(a)$, $p(b)$, $p(f(g(a)))$ where $a$ and $b$ are constants of $L$, $p$ is a predicate symbol of $L$, $f$ and $g$ are function symbols of $L$, such things. It cannot contain $0$ or $1$.
> 2 votes

---
Tags: logic, logic-programming
---


# Question
Title: 3-Approximation for General position subset
I am currently studying for an exam and stumbled upon the following task: Given the following problem:

**Input** A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$

**Question** Find the maximum subset $S \subseteq P$ such that no three points in $S$ are collinear.

The task is to find a polynomial time 3-approximation algorithm that is an algorithm that deletes at most $3$-times as many points as an optimal solution. Unfortunately, I am totally clueless here. How would such an algorithm look like?

# Answer
Find any line containing $\geq 3$ points. Delete all points on this line. Repeat.

This is a $3$-approximation, since on any line containing $m\geq 3$ points we must delete at least $m-2\geq 1$ points and we delete at most $2$ points too many. Meanwhile, the objective value decreases by at least $m-2\geq 1$.

If we know that the true objective value is $K$, then the instance obtained by deleting all points on this line will have objective value $\leq K-(m-2)$ and thus the recursive application will, by induction, return a solution removing at most $3(K-(m-2))$ points. Thus, we remove at most $3(K-(m-2))+m=3K-2m+6\leq 3K$ points.
> 3 votes

---
Tags: computational-geometry, approximation
---


title: Energy consumption off CNN models

text:
# Question
Title: Energy consumption off CNN models
I want to calculate/estimate the energy consumption for the different convolutional neural networks. Is there any possibility to measure the energy consumed by AlexNet for example with a tool or with Keras or something else?

# Answer
> 2 votes
The energy usage will vary depending on the machine, but as long as all of your results are from the same setup there's a comparatively low-tech, simple solution: Hook up your computer to an electricity meter and take some measurements with the computer "at rest", to get a baseline of its energy consumption. Then, run several trials with each model you're testing, and adjust the readings by the baseline to get the net difference in energy consumption when the model is running.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Will irrational parameters make a problem not well-defined on complexity
Given a set $=\\{\_1,⋯,\_\\}$ where all $\_$s are rational positive numbers and $\sum\_{i\in N}a\_i=1$, find a subset ⊆ such that $(\sqrt{2\sum\_{i\in S}a\_i}-1)^2$ is minimized. Does the appearance of √ make the problem ill-defined with regrading to complexity?

# Answer
The appearance of square roots does not make this an ill-defined problem.

Note that $(\sqrt{2\sum\_{i\in S}a\_i}-1)^2=0$ if $\sum\_{i\in S}a\_i = 1/2$ and $(\sqrt{2\sum\_{i\in S}a\_i}-1)^2\>0$ otherwise. Therefore, the problem is easily seen to be NP-hard by reduction from subset sum.
> 3 votes

# Answer
In this case, minimizing your expression (given that the sum is positive!) is just to minimize the sum, the square root and square are red herings ($(\sqrt{x} - 1)^2$ is monotone).
> -1 votes

---
Tags: complexity-theory
---


# Question
Title: What is cold-start penalty ? What are some ways to reduce it?
when a new process is created using a fork() function, there is a cold start penalty, what is this and why does it happen?

# Answer
"Cold start penalty" is the penalty for starting a process that has never run. The operating system has to read the code from disk, page tables have to be set up, caches filled in as instructions are executed/data fetched, and so on. If the process has run before, some of the above will already have been set up (and perhaps not fully evicted).
> 1 votes

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


title: What are GPUs bad at?

text:
# Question
Title: What are GPUs bad at?
I understand that GPUs are generally used to do LOTS of calculations in parallel. I understand why we would want to parallelize processes in order to speed things up. However, GPUs aren't always better than CPUs, as far as I know.

What kinds of tasks are GPUs bad at? When would we prefer CPU over GPU for processing?

# Answer
GPUs are really good at doing the same simple calculation many times over in parallel. They're usually good at spawning millions of short-lived "threads" that perform the same instruction on multiple bits of data (Same Instruction, Multiple Data, or SIMD). They excel at SIMD situations. They have less memory than the CPU has access to and are not meant as omni-purpose computing units like the CPU is.

# Being fast in serial applications

Standard desktop CPU speeds are on the order of several GHz. High-end GPUs are barely over 1 GHz. If you have one task that needs to be computed in serial, you won't get a raw speed benefit from a GPU. A GPU only shines when it computes things in parallel.

# Branching Code

If you have a lot of places in your GPU code where different threads will do different things (e.g. "even threads do A while odd threads do B"), GPUs will be inefficient. This is because the GPU can only issue one command to a group of threads (SIMD). If the even threads are told to do one thing while the odd threads are told to do another, the GPU will wait to give the even threads their code to run until the odds have completed their instruction (or vice-versa).

# Situations requiring lots of RAM

Good GPUs can have many gigabytes of RAM, but they still lag behind CPUs in terms of how much memory they can access. Compare Nvidia's (currently) high-end Titan V GPU with 12 GB of RAM to a high-end desktop with 64, 128 or even 512 GB of RAM. GPUs cannot dip into the hard drive for more RAM if needed, but CPUs can.

When the code requires that each thread on a GPU have access to large amounts of RAM, this can add up.

# Situations requiring networking

To my knowledge, there are no GPUs that can spawn lots of network connections. Because networking is a serial task, it is best done on a CPU.

# Situations requiring lots of inter-thread communication

In massive simulations, threads need to frequently and regularly communicate with specific other threads. This involves a lot of branching, which as mentioned above, slows GPUs down tremendously.

# Talking to hardware or running an operating system

Ironically, while GPUs excel at rendering the pixels on computer screens, they're not designed to manage a window, get data from the mouse or keyboard, or other things. CPUs are meant to do anything and everything a computer could possibly want to do. A GPU is designed to do one thing really, really well.

GPUs do not currently have the flexibility or power to run an operating system. They do not talk directly to the operating system via system calls in the same way that a CPU can.

# File I/O

GPUs are designed to aid the CPU in doing lots of computations, but if you want to load or write data to/from a file, let the CPU do this. Because GPUs spawn millions of "threads", they are not well-suited for situations requiring serial I/O.

# User I/O

If you want the user to enter a number, ask the CPU to ask the user instead of the GPU. Some GPUs *may* be able to handle some user I/O, but this is generally a serial interaction, and therefore is not where the GPU shines.

# Summary

CPUs are designed to do a lot of different things and have a ton of different capabilities. GPUs are designed with a much more narrow goal. Because of this, they excel in certain tasks and perform poorly (if at all) for others.
> 30 votes

# Answer
GPUs are bad at doing one thing at a time. A modern high-end GPU may have several thousand cores, but these are organized into SIMD blocks of 16 or 32. If you want to compute 2+2, you might have 32 cores each compute an addition operation, and then discard 31 of the results.

GPUs are bad at doing individual things fast. GPUs only recently topped the one-gigahertz mark, something that CPUs did more than twenty years ago. If your task involves doing many things to one piece of data, rather than one thing to many pieces of data, a CPU is far better.

GPUs are bad at dealing with data non-locality. The hardware is optimized for working on contiguous blocks of data. If your task involves picking up individual pieces of data scattered around your data set, the GPU's incredible memory bandwidth is mostly wasted.
> 143 votes

# Answer
# Branching

One piece of hardware that pretty much no GPU has is a Branch Predictor. That's because their primary function is to compute simple functions over large sets of data. The only "branching" that a typical GPU does is the jump at the end of a loop body. CPUs, on the other hand, typically run code that executes branches quite frequently (about 20% of the time), which is why so much die is dedicated to branch prediction on modern CPUs. A branch is one of the most expensive operations because it usually causes a pipeline flush. For deep pipelines (which is typically how you get high clock rates), this can be a massive delay.

As others have noted, random access is also detrimental to GPU workloads. Combining these two are one of the most ubiquitous problems in software engineering: sorting. Or basically, the majority of what a database server does.
> 64 votes

# Answer
First, not every problem is easily amenable to a parallel solution. If it's not possible to formulate your problem as such, you might not gain anything from using a GPU or any parallel approach to begin with.

Second, it takes time to move data from the host to the device (i.e., the GPU). You can waste time doing many such transfers and the potentially fast execution on the device won't result in speedups over CPU computation. You want enough data so that the fast execution on the GPU will outweigh the time spent on transfers.

Finally, the modern x86 CPU has specialized instructions for certain (low level) problems the GPU architecture doesn't. One such example is carry-less multiplication for which the CPU tends to be a lot faster (unless you do a massive amount of such multiplications in parallel with a good GPU implementation, but this requires some work).
> 28 votes

# Answer
Leaving aside specifics of CPUs vs GPUs, let's simplify the discussion to a single powerful processor (or a handful of them, i.e. multicore) vs an array of 1000s of "slower" processors.

Some workloads are classified *embarrassingly parallel* since they consist of many tasks that are pretty much independent. These are ideal for GPUs.

Some workloads have *irregular parallelism*, which is when parallel tasks of irregular lengths branch and merge based on the results of earlier tasks (thus the branching and merging cannot be predicted and scheduled in advance). These are much harder to parallelise and there are problems like many cores being idle while waiting for tasks, or a lot of overhead scheduling small tasks. Good solutions have been found for the most important/common algorithms (like Delaunay mesh refinement), but it's hard.

Some workloads are fully sequential which means that they don't benefit from parallelism at all (except instruction-level parallelism which CPUs have super-mega-crazy optimisations for and GPUs do not). For instance, certain parsing tasks are very challenging to parallelise since every step is highly dependent on the context created by previous steps.

In "very sequential" workloads that can for instance only run on one core, the choice is between a beefy CPU core and a modest GPU core. The CPU core might be an order of magnitude faster, or even more! Those beasts pack mind-boggling optimisations.

The Tao of Parallelism is a good read.
> 17 votes

# Answer
Perhaps a prime example would be cryptographic functions such as KDFs, which are specifically designed to benefit as little as possible from parallelization that GPUs and special cracking hardware offers.

There's a whole class of so-called *sequential memory-hard functions* which make it difficult to benefit from parallel computing (a) in a single computation scenario due to data dependencies and (b) in multiple computation scenario due to memory requirements. A typical algorithm looks like this

1. Generate a large pseudo-random array $H$ with password as a seed. This occupies a large portion of RAM and covers the case (b)
2. Starting with a given index $I\_k$, compute $I\_{k+1}$ based on $H\[I\_k\]$ and the password. This introduces a data dependency between every two steps to cover the case (a).
3. Repeat step 2 a large number of times: $k=1..N$
4. Use the $H\[I\_N\]$ to construct an encryption key or a password hash

The idea is that an attacker trying to guess a password from a known key / hash will have to spend a significant time checking one password after the other no matter how many GPU cores they have at their disposal, while a legitimate user will compute a key/hash relatively quickly using a single core because they have to do it only once.
> 11 votes

# Answer
To augment @Juho’s answer a little: for workloads which are easy to multi-thread, there may also be significant instruction level parallelism that a multi-core superscalar CPU can take advantage of; current GPUs typically run at a lower clock speed than their CPU counterparts; GPU threads are not truly independent, implemented as 16 or 32-way SIMD, and divergent code will slow down GPU performance significantly.
> 10 votes

# Answer
GPUs are bad at linear/quadratic programming:

> Gurobi is watching GPUs closely, but up to this point all of the evidence indicates that they aren't well suited to the needs of an LP/MIP/QP solver. Specifically:
>
> GPUs don't work well for sparse linear algebra, which dominates much of linear programming. GPUs rely on keeping hundreds or even thousands of independent processors busy at a time. The extremely sparse matrices that are typical in linear programming don't admit nearly that level of parallelism.
>
> GPUs are built around SIMD computations, where all processors perform the same instruction in each cycle (but on different data). Parallel MIP explores different sections of the search tree on different processors. The computations required at different nodes in the search tree are quite different, so SIMD computation is not well suited to the needs of parallel MIP.
> 10 votes

# Answer
**Integer arithmetic**

GPUs are optimised for doing 3D rendering calculations. Following the history of OpenGL, these are traditionally done using 32-bit floating point numbers arranged as either vectors of four floats or quaternion matrices of 4x4 floats. So that's the capability GPUs are very good at.

If you want to do floating point with more bits, or 64-bit integer arithmetic, you may find it unsupported or slow.
> 9 votes

# Answer
Expanding a bit more on Juho's answer, it's true that GPUs are generally bad at branching, but it's also important to point out *why*. It's not just a matter of less die space dedicated to branch prediction (though that is part of it.) It's also a matter of less die space dedicated to *instruction decoding and sequencing in general*.

What we call a "core" on a GPU is not at all what we normally think of as a "core" on a CPU. A GPU "core" is really mostly just a glorified floating-point ALU (Arithmetic Logic Unit, that is, the part of the processor that does arithmetic like addition, multiplication, etc.)

A CPU will almost always have (at least) one instruction decoder per "core" and each core can follow code paths completely independent of what other cores are doing with no penalty (aside from maybe more cache misses if they have shared cache.)

A GPU, on the other hand, typically only has one or two instruction decoders per *at least a few dozen* "cores." As such, a given group of cores can only be executing one or two different code paths at any given time. If different cores within the group need to follow different paths through the code, then the whole group has to take all of those paths and each "core" only commits the results from the instructions on the code path it was supposed to take.

So, GPUs are very good at "Single-Instruction, Multiple-Data" math, where you're doing the exact same set of computations on a large number of different data points. SIMD is well-suited to the task of matrix multiplication, which happens to be the primary job GPUs were designed to do, since that's the majority of the work in 3D rendering algorithms. Conveniently, matrix multiplication and other SIMD-friendly tasks also happen to be very common in science and engineering, so that's why GPUs are commonly used as computational accelerators in supercomputers.

If your algorithm is not SIMD (that is, if you're needing to follow significantly different code paths for each data point,) then it probably won't be very efficient on a GPU.

And, of course, as with any multi-core system, single-threaded sequential code will be a total waste of all but one core.
> 7 votes

# Answer
GPU works well or not mainly depends on computing instruction/IO instruction ratio. Here "IO instruction" includes any instruction that send/receive data through the boundary of the basic computation unit in GPU. "Basic computation unit" commonly have like 8-32 ALUs that need to execute instruction together and 16-128KB of registers/RAM and some instruction cache/RAM.

If the inner core of your program mainly fits in the instruction cache in the basic computation unit and the temporary data your proram need to read/write can mainly fit in to the registers/RAM in the basic computation unit, and the data to be feed in/processed and result to be exported is small enough , then you can utilize most of the computation power of GPU.

If not, then the grid/loop network connects the basic computation units and the GDDR memory interface and the PCIe CPU interface will soon render the GPU a CPU or even worse.

For example, each basic computin unit have 16 ALU, each need 2 register/RAM reader and 1 write with 32bit data, then each cycle need 3\*16\*2GHz\*4bytes=384GB/s. The GDDR bandwith is only 300GB/s - not even enough to feed a single basic computin unit, and the GPU may have 100+ such basic computin units. **All the magic from GPU is based on this, you need the 400GB/s\*100+ bandwidth to make GPU work like magic. Once you need more "IO" bandwith, there is just not enough bandwith and the GPU magic vanish**.

As @Bulat said, indeed this is the magic of any \**U based on, you need to fit your temporary data mainly in L0 cache and don't let the IO bandwidth be the bottleneck to get nearer to the peak performance. L0 cache means multi-ported register or RAM that support through output of 1 instruction/circle which often need 2 read and 1 write.

Common programs for CPU which is commonly logic code instead of computing kernels mainly doesn't work at L0 cache speed, but at L2 or L3 or bus/DDR speed, this is the common working mode for CPU program and you don't think it is a bad thing for your program not to work at L0 speed on CPU.

But for GPU computing kernel working at L0 speed is the target. If the program doesn't work mainly at L0 speed, the program is less fit for GPU. But even so some program that doesn't fit can still work better on GPU than CPU, the final factor is how IO bandwidth is limiting the program.

CPU's L0 cache is the 8-16 32-64bit registers which is only 128 bytes. Although modern CPU have renaming register like 100+\*64 bit, it is still jusg ~1KB and it is only utilized on specific instruction sequences. This is why for most time CPU doesn't work at the L0 speed, the L0 cache is very small only very special computing kernel can keep working at L0 speed. For CPU most code is control logic, you can never let control logic code mostly work at L0 even with more L0 cache so that is just a waste. And more L0 cache mean more registers then longer instructions to encode more registers then equally less instruction cache which is important for logic code. Larger L0 cache also means slower L0 speed - perhaps from 5GHz to 2GHz.

In contrast GPU provide 32-128KB L0 cache in each basic computing unit - hoping the code can run at L0 speed as much as possible, this is possible for small computing kernels.

Another factor of the GPU magic is GPU use more die size for basic computing unit. For example, CPU have 16MB L3 cache, GPU use this for 64KB L0 cache for 256 basic computation units (should be less since L0 cache cosume more area due to more port and control logic overhead). And GPU have lesser control logic to boost single thread performance.

**Conclusion: CPU- fit for control code that work with 10MB code/data at L2/L3 speed. GPU - fit for computing kernel that work with 100KB data at L0 speed.**

Note: the 100KB GPU L0 cache is devided into several ALUs. For example, 16ALU and 128KB L0 cache, then 8KB for each ALU, that is what your program can use to fit in L0. This introduces another pattern GPU need - your program have to be executing the same task on N different set of data then it can utilize N ALUs of the GPU at the same time. N at least should be larger than the number of ALUs in one basic computing unit.
> 5 votes

# Answer
GPU cores can perform the same operations as CPU ones (f.e. it implements all C operations over SIMD registers). The difference is that each core is ~10x slower, and there is almost no speculative execution. This makes GPU more power-efficient.

To compensate for the lack of speculation, GPU can run 10–20 threads per core, so overall we can have ~100x more threads per GPU than per CPU. At the same time, GPU caches are almost 10x smaller than CPU ones. That results in 1000x smaller cache per thread. It’s OK for graphics code (and it’s why they use this config), but only a few CPU algorithms are keeping their efficiency when caches are essentially non-existant.
> 1 votes

# Answer
GPU are 1) highly parallel architectures, with additional limitation that 2) are organized in blocks which must perform same operation on different data at the same time.

Therefore, the performance of GPUs is due to extensive and quite constrained paralelism, but their clock rates are not particularly high. So, whenever you have an algorithm where **the next step** depends on **the current step** then very little actual(!) parallelism is possible.

Examples of such algorithms: iterative algorithms, many optimization methods.

Side note: you may do speculative calculation in iterative algorithms as well if you have discrete solution space (e.g. if previous step has 16 possible outcomes, you can precalculate the next step in parallel). But this are mostly special cases.

Side note 2: Same limitations apply to FPGAs. Just that clock rates are even lower (e.g. hundreds of Mhz, not Ghz), and penalty for not having parallelism even higher.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Prove that a set A is semi-decidable if and only if there is a polynomial time relation R(x,y)
I know if there is a decidable relation R(x,y) for x in A, then A is semi-decidable. But how can I prove the relation is polynomial time?

For R(x,y), x is where M is a TM, y is the accepting configuration of M. Is this a polynomial-time relation?

# Answer
> For $R(x,y)$, $x$ is where $M$ is a TM, $y$ is the accepting configuration of $M$. Is this a polynomial-time relation?

Yes that is the right idea. Except $y$ should be a *sequence* of configurations that starts in the initial configuration and ends in the accepting configuration.

To see why this works, we have to consider the running time of the TM that accepts $R(x, y)$. First the TM looks at the input $x$, and then it looks at the sequence of configurations $y$. The sequence of configurations looks something like a table:

```
Tape at time 0: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
                ^HEAD, state q0
Tape at time 1: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
                   ^HEAD, state q1
Tape at time 2: x1  1 x3 .... xn 0 0 0 0 0 .... 0
                       ^HEAD, state q2
...

```

and so on. So how does our TM check if this is in $R(x, y)$? We should check to make sure that the initial configuration has $x$ on the tape. How long will this take? And then we should check that $y$ is a valid sequence of configurations of according to the transition behavior of $M$. How long will that take? Finally, we need to check that the last configuration in $y$ is accepting. How long will that take?
> 1 votes

---
Tags: turing-machines
---


# Question
Title: The characterization of a problem as PSPACE-complete is ...?
Let's assume that you found out that some problem $\mathit{\Pi}$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-known and very different PSPACE-complete problems, this characterization doesn't tell you much about the real hardness of deciding membership in $\mathit{\Pi}$ (and you determine to refine the hardness of membership in $\mathit{\Pi}$ further by some other means, i.e., different from the good old standard complexity classes). Now, how do you express in plain English the unsatisfactory fact that the PSPACE-completeness of $\mathit{\Pi}$ doesn't tell you too much? Do you say that the PSPACE-completeness characterization of $\mathit{\Pi}$ is

* coarse
* coarse-grained
* coarsely grained
* coarsely granular
* crude
* gross
* grainy
* granular
* rough
* unrefined
* ... (your choice goes here) ...

?

Which word is idiomatic?

# Answer
Several are idiomatic: "coarse", "coarse-grained", "crude", "rough", "unrefined". These all (roughly) mean 'lacking in \[fine\] detail'.

"Coarsely grained" and "coarsely granular" don't work well in this case (though the meaning would not be lost, it just reads strangely). These two imply that you're talking about properties of the object (in this case the characterisation - the first that it has a grain of some kind which is coarse, the second that it comes in rough lumps).

"Gross", "grainy" and "granular" don't work at all, and would require the reader to guess that you actually meant to write something else. The "grain" in "coarse-grained" refers to meaning 5, not meaning 1 as described here, so the adjective granular is incorrect. "gross" at its root means "large", so doesn't give the right intent here either.

As an alternative with a different core meaning, you could say that it's "unenlightening", or "unilluminating", suggesting that it doesn't tell you much, rather than it's rough.
> 0 votes

---
Tags: terminology, space-complexity
---


# Question
Title: Relationship between circuit size and formula size in Sipser text
The Sipser text (3rd edition) contains a proof that 3-SAT is NP-Complete based on Boolean circuits. Part of the proof contains the remark that the reduction from the circuit to the Boolean formula can be done in polynomial time.

First question: is it correct to say that if a circuit C of polynomial size exists, then there must exist a formula $\varphi$ of polynomial size where C is satisfiable if and only if $\varphi$ is satisfiable?

Second question: is the Boolean formula $\varphi$ still of polynomial size if C is of polynomial size and C is derived from a *deterministic* Turing machine M? This seems to be described in the proof of the earlier theorem in Sipser where (by building C from a tableau of M) it is shown that if $\mbox{A $\in$ TIME$(t(n))$ for $t(n) \geq n$ and $n \in \mathbb{N}$}$ then A has circuit complexity $O(t^2(n))$.

# Answer
> 1 votes
Yes, that's correct. See the Tseitin transform, which describes how. It doesn't matter how the circuit $C$ was constructed.

---
Tags: complexity-theory, circuits, boolean-algebra
---


# Question
Title: Approximating Deep Neural Networks (DNNs) with Binarized Neural Networks (BNNs)
I am working currently as a research intern on Binarized Neural Networks where the weights and the activations of the network are binary. The architecture of this type of networks makes them memory efficient and computationally efficient, which makes them ideal for resource constrained environments, like embedded devices and mobile phones.

The interesting part about BNNs is that we can encode a binarized network as a CNF formula (Boolean Formula). Using this formula, we can verify some properties of the network like Robustness against adversarial examples (carefully crafted samples looking similar to usual inputs but designed to mislead a pre-trained model). We can also extract explanations that support neural network decisions, hence make the neural network explainable.

Currently, I am trying to make a DNN explainable by verifying its decisions using BNNs. The first direction of research is to reduce a DNN to a BNN. Of course the two networks should be equivalent. I am researching ways to make this reduction but I haven't found any works in the subject. Is it possible to carry out this transformation ? Is there any techniques that can "binarize" a DNN ?

Thanks :)

# Answer
I expect you'll run into two challenges in this line of research: (1) there are no known ways to construct a BNN that exactly matches an ordinary neural network; (2) verifying a BNN with a SAT solver won't scale to the size models needed for most interesting tasks.

Since you asked specifically about (1), no, I don't know of any way to do that. Probably you won't find exact equivalence. You might be able to train a BNN that has a very high agreement with the ordinary neural network on the training set; I don't know whether it will have the same adversarial examples or not.
> 1 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


title: Prove that a language is regular

text:
# Question
Title: Prove that a language is regular
I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible to remove zero or more symbols from w so that just the string x remains. For example, the following strings can all be obtained from 0110 by deleting symbols:

λ, 0, 1, 00, 01, 10, 11, 010, 011, 110, and 0110.

Let Σ = {0, 1} and let A ⊆ Σ ∗ be an arbitrarily chosen regular language.

Define B = {x ∈ Σ ∗ | there exists a string w ∈ A such that x is obtained from w by deleting symbols}.

In words, a string is in B if you can obtain that string by first choosing a string from A and then deleting zero or more symbols from that chosen string. **Prove that B is regular**.

I'm not able to prove it. Any help would be appreciated.

# Answer
Hint 1: As $A$ is regular, it is recognized by finite automata. Try to modify this automata to make it recognize $B$.

Hint 2: Skipping "deleted" symbols might be handled by adding $\epsilon$ \- transitions to the original automata in a proper way.
> 3 votes

# Answer
Use closure properties of regular languages: Apply substitution $\sigma(x) = \\{x, \epsilon\\}$. This replaces symbols by themselves or nothing.
> 2 votes

# Answer
$A$ has a regular expression. Can you modify the expression so it will express the optional deletion of arbitrary characters?
> 2 votes

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


# Question
Title: Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e
An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^\*$, where $\Sigma$ is the alphabet. Call this language $CFG\_{all}$

But the above language is also not computably enumerable. There can be a reduction from $CFG\_{all}$ to $\bar{A\_{TM}}$, where $\bar{A\_{TM}}$ is the language s.t. the input $TM$ does not accept any input. $\bar{A\_{TM}}$ is not computably enumerable.

But could we say that whether or not a type 3 grammar generates $\Sigma^\*$ is also not c.e. ? (since type 3 grammars are a subset of context-free grammars). While it is true that a finite automaton can recognize $\Sigma^\*$, this language is different right from whether a type 3 grammar generates $\Sigma^\*$?

Just to clarify the source of my confusion, in summary, it is decidable for a $TM$ to decide whether a pushdown automaton recognizes $\Sigma^\*$ or accepts any input, but it is not decidable or even computably enumerable for a $TM$ to recognize that a CFG generates $\Sigma^\*$. Similarly, it is decidable for a $TM$ to check if a finite automaton accepts $\Sigma^\*$, but it may not be decidable for a $TM$ to check if a type 3 grammar generates $\Sigma^\*$. It's somehow the difference between recognizing and generating.

EDIT: apparently for a pushdown automaton to recognize $\Sigma^\*$ is not decidable

# Answer
> 1 votes
To see if a type 3 grammar (regular) generates $\Sigma^\*$ just build the minimal DFA accepting the language, and check if it is just initial = final state, with loop on all symbols. All constructions involved are effective.

---
Tags: formal-languages, regular-languages, undecidability
---


# Question
Title: Why MIT lecture breadth-first search algorithm is so complicated?
I watched a video for BFS from MIT and the algorithm the lecturer presented was really complicated compared to what I came up. My solution seems to work fine and walk through the vertices in the correct order. Am I missing something?

```
public static void BFS(GraphNode currentNode, GraphNode searchedNode) {
    if (currentNode.index == searchedNode.index) {
        System.out.println("Found!");
        return;
    }

    if (visited[currentNode.index]) {
        return;
    }

    visited[currentNode.index] = true;

    for (GraphNode child : currentNode.children) {
        if (!visited[child.index]) {
            nodeQueue.add(child);
        }
    }

    if (!nodeQueue.isEmpty()) {
        BFS(nodeQueue.poll(), searchedNode);
    }
}

```

One drawback is that it keeps running after finding a node, but that could be fixed easily by clearing the queue when element is found.

# Answer
I think this is best handled by contacting the lecturer, but here are four reasons.

A Kain0\_0 remarks, your solution is recursive, while his isn't.

Didactic considerations behind this might be:

1. Recursion is hard for some students. Perhaps it hasn't been taught at this point in the course, or is considered an unnecessary burden.
2. Most BFS implementations in practice do not use recursion. Programmers need to spot algorithms in other peoples' code all the time. There is value in presenting algorithms in their most common form.

Furthermore,

3. You're sweeping some stuff under the carpet. He makes his data structures explicit, because he wants to show how much time and space his algorithm uses. You don't: you leave the recursive call stack implicit, and you don't show how `.children` and `.index` are represented or created.
4. He's doing more. He can report the level at which the node was found. You don't keep that information.
> 2 votes

---
Tags: breadth-first-search
---


title: Recurrence relation chip and conquer

text:
# Question
Title: Recurrence relation chip and conquer
Can anyone explain how to find the $\Theta()$ of this equation... $$T(n) = 3T(n-4) + cn$$ When I solve this problem I get this using the $k$ -th iteration... $$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) + 3^{k-2}c(n-2(k-2)) + ... + cn$$ I factor out c and get this... $$T(n) = 3^{k}T(n-2k) + c(3^{k-1}(n-2(k-1)) + 3^{k-2}(n-2(k-2)) + ... n)$$ I'm not sure if we need to find an upper and lower bounds or solve the geometric series. Any suggestions? I need to find $\Theta()$ and we didn't cover master theorem so this is how my class was taught to approach these.

# Answer
> 2 votes
The answer should be $\Theta(3^{n/4})$. You can go both ways you suggest – find an exact formula, or estimate the sum, using an integral or in more devious ways. There is no loss in generality if you take $c = 1$. If you replace $n$ with $1$ (so we get a lower bound), then we have $$ 1 + 3 + 3^2 + \cdots + 3^{n/4} = \Theta(3^{n/4}), $$ using the formula for summing a geometric series. If you bring back the $n$, the calculation becomes a bit more difficult, but you should still be able to get a matching upper bound: $$ n + 3(n-4) + 3^2(n-8) + \cdots + 3^{n/4}(0) = O(3^{n/4}). $$ There are in fact closed formulas for this kind of sum (try Wolfram alpha), but you can also try to bound without them, say by looking at ratios of consecutive terms and comparison to a geometric series: $$ 3^{n/4} \left(0 + 4\frac{1}{3} + 8\frac{1}{9} + 12\frac{1}{27} + \cdots \right) = O(3^{n/4}), $$ since the *infinite* series $4\sum\_{m=0}^\infty \frac{m}{3^m}$ converges.

# Answer
> 0 votes
If that isn't a typo, you can separate that into 4 recurrences (for starting points 0, 1, 2, 3) by the change of variables $r = \lfloor n / 4 \rfloor$, $k = n \bmod 4$:

$\begin{equation\*} t\_k(r + 1) = 3 t\_k(r) + 4 r + k \qquad t\_k(0) = T(k) \text{ for } 0 \le k \< 4 \end{equation\*}$

They are all first order linear recurrences. Solutions are of the form:

$\begin{align\*} t\_k(r) &= t\_k(0) \cdot 3^r + \frac{r + 2}{2} \cdot 3^r - \frac{4 r + k + 2}{2} \\ &= \Theta(r \cdot 3^r) \\ T(n) &= \Theta(n \cdot 3^{n/4}) \end{align\*}$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Not sure if my solution to following recurrence is correct
I have a recurrence relation, it is like the following:

$T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm.

To solve this and find a $\Theta$ bound, I tried the following: I put $k=e^n$, and the equation transforms into:

$$T(k)=2T(k/e)+k$$

Then, I try to use the Master Theorem. According to Master Theorem, $a=2$, $b=e\gt 2$ and $f(k)=k$. So, we have the case where $f(k)=\Omega(n^{\log\_b a+ε})$ for some $ε\gt 0$, thus we have $T(k)=\Theta(f(k))=\Theta(k)$. Then put $k=n$, we have $T(n)=\Theta(n)$. Does my solution have any mistakes?

# Answer
$c=1\gt \ln 2\approx0.7$. That's case 3 of the master theorem. It follows that:

$$T(n)=\Theta(n)$$

Your solution is fine.
> 1 votes

# Answer
Just use the change of variables $t(n) = T(e^n)$, you get $t(n) = t(n - 1) + e^n$. Linear, first order recurrence, solution is:

$\begin{equation\*} t(n) = t(n - 1) + e^n \end{equation\*}$

Solution is:

$\begin{align\*} t(n) &= t\_0 - \frac{e}{e - 1} + \frac{e^{n + 1}}{e - 1} \\ T(k) &= (t\_0 - \frac{e}{e - 1}) + \frac{e^2}{e - 1} k \\ &\sim \frac{e^2}{e - 1} k \end{align\*}$
> 0 votes

---
Tags: algorithms, time-complexity, recurrence-relation, master-theorem, check-my-answer
---


# Question
Title: How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?
This question is specifically related to

https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits of $x,y$, and $T(n)$ is the time to multiply two $n$ bit numbers, as described in

How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

so when it reads "if you're dealing with big integers, you must account for the fact that the modulus operations within each iteration don't have a constant cost. Roughly speaking, the total asymptotic runtime is going to be $n^2$ times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log\*n). "

Isn't this the same thing as stating "the fastest $gcd(x,y)$ is solved in n^2 lg(n) 2^O(log\* n)"? If so, then

**How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?**

If the $gcd(x,y)$ is solved in $O(T(n) log n)$, shouldn't this be true no matter how large $n$ is?

# Answer
> 1 votes
It is just that the first expression doesn't count the cost of the divisions, that is factored in later.

# Answer
> 2 votes
Based on your comments, I recommend go back to basics and first understand running time, bit-complexity, and the running time for multiplication well. Focus on that before you try to tackle any of the topics in this post, or you're going to get confused.

Here is a suggested syllabus:

1. First, study big-O notation. Understand what it means. Work through the definitions. This is well covered in standard algorithms textbooks, so work through that material patiently. See also, e.g., How does one know which notation of time complexity analysis to use?, How to come up with the runtime of algorithms?. Try to understand why your "shouldn't this be true no matter how large n is?" question is meaningless (hint: big-O notation relates two functions, not two numbers).
2. Understand bit complexity as a measure of running time for algorithms that work with large numbers. See, e.g., Precise runtime of the algorithm to find number of digits in an integer, Relationship between an integer N and the number of bits n required to represent the integer
3. Understanding the bit complexity of addition. This will be a good test whether you understand bit complexity. See, e.g., Time complexity of addition.
4. Understand the bit complexity of multiplication. Understand why it is an open problem how fast we can multiply two integers. See, e.g., Complexity of multiplication, https://en.wikipedia.org/wiki/Multiplication\_algorithm, Complexity of a recursive bignum multiplication algorithm, What is the fastest algorithm for multiplication of two n-digit numbers?.
5. Understand the bit complexity of division and modular reduction. See, e.g., Complexity of Integer Division, Complexity of taking mod.

If there is any of these steps you are unclear on, ask a question about that specific aspect until you understand it well. Then, go back and study the material on gcd's. This background material will probably help you make it further through that material.

---

Remember that just because there is an algorithm to solve some problem in time $O(f(n))$, doesn't necessarily mean that that is the *fastest* algorithm to solve that problem. It doesn't mean that is the fastest that the problem *can* be solved. For instance, bubblesort can be used to sort numbers; it has a $O(n^2)$ running time. That doesn't mean that $O(n^2)$ is the "fastest that numbers can be sorted".

---
Tags: time-complexity, runtime-analysis, modular-arithmetic
---


# Question
Title: Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?
So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring something in nature that can be considered essentially "random" like the 50th binary digit after the decimal point in wind speed at some location recorded in miles per hour. Or maybe quantum outcomes observed that can be considered truly random. Whatever. So we do the following: We generate $k$ "truly" random bits and then we re-use these $k$ bits over and over by using a pseudo-random number generator to permute them. In terms of $k$ (the number of initial truly random bits) and in terms of the total count of numbers to be sorted, $n$, and assuming the permutation algorithm of the $k$ initial random bits repeated over and over is known to an adversary, can we assert that an algorithm like quicksort will have good worst-case expected running time, assuming that "random" bits are used in the algorithm in the natural way to choose a pivot? How do $k$ and $n$ play into the worst-case expected running time? If we need $k = \Omega(n \log n)$ initial truly random bits to assure good worst case expected running time, that isn't very interesting. But maybe we can do somewhat ok with asymptotically fewer initial random bits?

# Answer
The question you're asking deals with the topic of *derandomization*, and you're proposing a specific technique for derandomization, namely using pseudorandom number generators. There are other techniques suck as using k-wise independent distributions and the method of conditional expectations. The holy grail in the field is proving the conjecture P=BPP, which states (informally) that we can always get rid of randomness, though the resulting algorithm could be slower; more precisely, it states that if you have a randomized polytime algorithm for something, then there exists a deterministic polytime algorithm for the same problem.

In your particular case, you don't need random bits at all, since you can use the linear time median algorithm to guarantee a running time of $O(n\log n)$ for quicksort. The AKS deterministic primality test is likewise a specific derandomization of randomized primality testing. P=BPP, in contrast, gives a general derandomization technique that works for *every* (polytime) algorithm; ad hoc derandomizations are still meaningful, since they could be more efficient (like in the quicksort example).
> 4 votes

# Answer
If your adversary knows the $k$ input bits and your PRNG, they can apply the techniques used in McIllroy "A Killer Adversary for Quicksort", Software: Practice & Experience 29:4 (1999), pp. 341-344, and you are toast. How large $k$ has to be to make this infeasible to brute-force is another question.

No, "randomized quicksort" doesn't guarantee anything, it just makes the bad case(s) shift around at random (so it is very unlikely to hit them repeatedly with somewhat repeatable input permutations, as are common in "real world" uses). If you want some sort of guarantee, look for Musser "Introspective Sorting and Selection Algorithms", Software: Practice & Experience 27(8) (1997), pp. 983-993 (Introsort). Most standard C/C++ libraries use some variant of this for sorting.
> 0 votes

---
Tags: randomized-algorithms, quicksort, pseudo-random-generators
---


# Question
Title: What is the difference between rateless and online encoding?
Definitions of Rateless encoding and Online encoding are as follows.

Error-correcting codes that employ no fixed block length are called rateless or fountain codes.

Online encoding refers to the property that a symbol is encoded at once and without knowledge of previous encodings.

Do both properties indicate the same thing? Are Fountain codes both rateless and online?

# Answer
> 2 votes
They are not the same thing. The difference is *when* you know the message to encode.

In fountain codes, you **know** the message at the onset. The code allows you to keep generating more and more redundancy. The message, however, is fixed.

In online codes you **do not** know the entire message at the beginning, but you learn it as time goes by. Each time you learn an additional part of the message you can encode this part in a coherent way to the encodings of the (prefix of the) message you have already obtained or sent.

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


# Question
Title: What is the algorithmic complexity of this?
I'm practicing leet code questions and want to understand more fully how to determine Big O notation. What is the algorithmic complexity of my solution to the following problem?

**O(n^2) ?** For every item in n I could loop an additional n\[i\] times. Or is it **O(n)** ?

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Input: \[2,3,1,1,4\]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

```
var canJump = function(nums) {

  let validIndices = {};
  for(let i = nums.length - 1; i >= 0; i--) {
    let currentNum = nums[i];
    if(currentNum + i >= nums.length - 1) {
      validIndices[i] = true;
    } else {
      while(currentNum > 0) {
        if(validIndices[i + currentNum]) {
          validIndices[i] = true;
        }
        currentNum--;
      }
    }
  }

  return !!validIndices[0];
};

```

# Answer
> 1 votes
Your algorithm has O(n^2) worst case complexity. You have a for loop of O(n). Inside your for loop you have a while loop which is O(currentNum). So if your currentNum is O(n) (ex nums\[i\] = length.nums for each i) then the complexity is O(n\*n) = O(n^2).

Hint

Try not to recalculate things. You could use Dynamic programming technique. You need:

```
def canJump(i):
    if valid[i] has been assigned a True or False value:
        return valid[i]
    #else calculate valid[i]
    if i + nums[i] > len(nums):
        valid[i] = True
        return valid[i]
    for jump in range(1, len(nums[i])):
        valid[i] = any(False, canJump(i + jump))
    return valid[i]

print(canJump(0))

```

This is just a pseudocode. I have not tried it. This way you only visit an element of nums once so it’s O(n).

\[EDIT\]
Actually I am wrong. My code is also O(n^2). Here is an O(n) solution.

```
at_least = n
for i from n-1 to 0:
    if nums[i] + i >= at_least:
        at_least = i
if at_least == 0: True else False

```

Now I think this is right. Sorry for the confusion. I got confused too.

---
Tags: algorithm-analysis
---


# Question
Title: Is this set semi-decidable? A set of all <M> that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M
$A$ is a set of all $\langle M \rangle$ that $M$ is a TM halting on all input strings $w$ such that $\lvert w \rvert \le q(M)$ where $q(M)$ is the number of states in $M$.

Is $A$ semi-decidable? Is a complement of $A$ semidecidable?

I think $A$ is semi-decidable. We can construct $M1$.

$M1$ = "On input $\langle M \rangle$ where $M$ is a TM

Simulate $M$ on input with all of the string whose length is less than $q(M)$. If it halts for all, accept"

The complement of $A$ is not semi-decidable. But I'm not sure how to prove it.

# Answer
To show that $\overline{A}\notin RE$ you want to show that another language $B\notin RE$ is reducible to it.

First, the complement of $A$ is the set of all $\left\< M \right\>$, where $M$ is a Turing machine, and $\exists w$, $|w|\<q(M)$ s.t. $M$ doesn't halt on $w$.

Remember that you can add unreachable states to a Turing machine, therefore increasing $q(M)$. The next step would be picking a language who is known to be not decidable (e.g. the complementary of the halting language $\overline{H}$), and think of a reduction to $\overline{A}$.
> 0 votes

# Answer
The logical idea is take $M, w$ for the halting problem (here in the sense halt is accepting), and manufacture $M'$ that *only* accepts $w$, and has more than $\lvert w \rvert$ states, if $M$ accepts $w$.... but that is easy, just checking that the input is $w$ takes that many states. If we could decide if $M'$ accepts any string of length at most its number of states, we'd be deciding the halting problem.
> 0 votes

---
Tags: turing-machines
---


title: Recurrence Relations

text:
# Question
Title: Recurrence Relations
I am starting to learn recurrence relations in class and I am having issue with this example:

T(N) = 2N - 1 + T(N-1)

I am bit confused as to get the base case. I'm sorry if this seems elementary, but I am having a difficult time grasping this concept.

Thank you for your help!

# Answer
> 1 votes
In applications to time complexity of algorithms, you are often only interested bounding the growth (i.e., $O(), \Omega()$ asymptotics), and often the initial values incide as multiplicative factors to the solution (or their influence is swamped by the growth of terms that don't include them). So you'll often see sloppy statements that omit initial values.

---
Tags: time-complexity, runtime-analysis, recurrence-relation, recursion, discrete-mathematics
---


# Question
Title: A Guess Turing Machine that accepts a random Binary number
I'm trying to construct a turing machine that accepts any random binary numbers. From the theory (and partial example) in this video, I understand (correctly?) that this is something that is more easily doable with a Non deterministic turing machine.

So I have come up with a concept as such that I start with state Q1 (from the left side of the band) and upon reading a zero I move right, and upon reading a One 1 move right and the machine enters the same state, again and again until the complete word is read.

I understand that this is a way I can accept an input. What I dont understand is how to include accept and reject states on the machine? I would appreciate all help on the matter.

# Answer
There can't be "random numbers", each number is exactly that one, not at all "random". You can talk about getting a number at random from a set, perhaps according to some distribution. You might talk about a stream of bits, each of which is selected at random. But then the sequence 010101... is perfectly possible as an outcome (if it can't appear, it isn't random!).
> 2 votes

---
Tags: turing-machines
---


# Question
Title: Time complexity for the 'Restore IP Addresses' problem
There's a programming problem 'Restore IP Addresses' where given a string containing only digits, restore it by returning all possible valid IP address combinations. Example, "25525511135" returns \["255.255.11.135", "255.255.111.35"\].

My solution basically breaks up the string (upto 3 chars at a time) and moves to the remaining part of the string. This way we build a list of valid ip addresses using recursion. I've pasted my solution below.

If the input is number of characters (n) what would the time complexity of this solution be (with an explanation)? Also, would memoization help in this case?

```
/**
 * @param {string} s
 * @return {string[]}
 */

function isValid(s) {
  if (s.length === 0) return false;
  if (s.length > 1 && s[0] === '0') return false;
  if (s > 255) return false;
  return true;
}

function breakString(s, parts) {
  if (parts === 1 && !isValid(s)) return [];
  else if (parts === 1) return [s];

  let ret = [];

  //break into 3 pieces
  for (let i = 1 ; i <= 3 ; i++ ) {
    let part1 = s.slice(0, i);
    let part2 = s.slice(i);
    if (!isValid(part1)) continue;
    let tmp = breakString(part2, parts-1);
    if (tmp.length === 0 ) continue;
    tmp = tmp.map((str) => part1 + "." + str);
    ret = ret.concat(tmp);
  }

  return ret;

}

var restoreIpAddresses = function(s) {
    return breakString(s, 4);
};

```

# Answer
> 1 votes
The time complexity here is exponential in `s` or `parts`, whichever is smaller.

You have a recursive function, and it calls itself three times (after removing 1, 2, or 3 characters from the beginning). Thus, if $n$ is the size of $s$ and $k$ is the number of parts, your time complexity $T(n, k)$ satisfies $$ T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1) $$ We can roughly replace this by $T(n, k) = 3 T(n-3, k-1)$ (a lower bound) which leads to $$ T(n, k) = \min(3^{n/3}, 3^{k}). $$

---

For IP addresses, this exponential time complexity is likely not a huge problem. It's exponential in the number of parts, but the number of parts is only $4$, so that is not huge.

However, conceptually, your solution is pretty inefficient. Notice that you are duplicating a lot of work: you might call your `breakString` function on the tail of the same string several times, in different recursive calls.

To get a more efficient algorithm, try dynamic programming instead of recursion. For instance, can you keep track of, for each prefix and possible # of parts, whether it is a valid IP address or not? What complexity would that give?

---

**NOTE:** In the above idea to try dynamic programming, I assumed that the goal was just to return one valid IP address, not return all of them. When we have to return all of them, the time complexity changes somewhat, because the time complexity is now *at least* the time it takes to output all the answers, and there could be exponentially many answers.

Specifically, the time complexity in the worst case is bounded below by the number of decompositions of `s` in the following example: let `s` be a string of length $4n$ `1`s, and let `parts` $= 2n$. Then there are at least $3^n$ decompositions: this is the number of decompositions where there is a `.` after every block of $4$ characters.

Here is an example: for $n = 2$, `11111111` into $4$ parts has the following $3^2 = 9$ decompositions:

```
1.111.1.111
1.111.11.11
1.111.111.1
11.11.1.111
11.11.11.11
11.11.111.1
111.1.1.111
111.1.11.11
111.1.111.1

```

Again, this includes only those decompositions with a `.` after every block of $4$ characters, so there are actually more than $3^n$ total. But maybe you get the idea of why it blows up exponentially.

---
Tags: time-complexity, space-complexity
---


# Question
Title: Algorithm to save state of array as it changes
There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be retrieved upon querying.

For ex -

```
Initially, the array is [7, 8, 9]. This is version 1.
Next, 90 was added. Version 2 is [7, 8, 9, 90].
Next, 23 was added. Version 3 is [7, 8, 9, 90, 23].
Next, 90 was deleted. Version 4 is [7, 8, 9, 23].

```

And so on.

I need to write a function, `get_version(ver_num)`, which returns the state of the array for each version. So, running `get_version(3)` should return `[7, 8, 9, 23]`.

I have thought of saving incremental changes to the array in each iteration, in the form of an array maybe.

For ex -

```
[("add", [7, 8, 9]), ("add", [90]), ("add", [23]), ("subtract",[90])]

```

This will save space but in order to recreate the array for a specific version, I have to iterate over this array until I reach the required version. Is there a way better than this?

Thanks

# Answer
In the following we assume that whenever we make a delete-operation, the value to delete is guaranteed to exist in the array, and if multiple copies of it exist, we should remove its leftmost appearance.

The problem can be solved in $\mathcal{O}(\log n)$ per update, and in linear time (with respect to the output size) per query with standard persistent trees (tree traversal is linear time). The only issue is that since our ordered set is ordered by index, not value, we need a map (that doesn't have to be persistent) that translates from index to value. To not degrade the complexity, add a two-way link between nodes representing the same value in the current persistent tree and the map. These links are easy to maintain with no overhead.

If the input values are bounded, since the only query we are interested in is outputting the entire list at a specific time, we can improve on this. If the values are at most $m$, and we can use $\mathcal{O}(n + m)$ memory, we can make $n$ operations in $\mathcal{O}(n)$ time, and answer queries in linear time (with respect to the output size). To do this, we store snapshots of the array and the incremental changes between them.

Let $k$ be the highest amount of elements that have been on the current list since we last took a snapshot. We will take a new snapshot when we have deleted at least $\lceil\frac{k+1}{2}\rceil$ elements. This way we only need to apply a linear number of operations (in output size) to produce any array: if the output size is $n$, we apply at most $n+1$ deletions (since $\frac{n + (n+1) + 1}{2} = n+1$), and thus at most $2n+1$ insertions.

How to then produce the array? Start from the latest snapshot before it, then apply all of the insert-operations. Then, for each delete-operation, increment the delete-count of its respective value (stored in an array of size $\mathcal{O}(m)$. Replacing this with a map would give a $\mathcal{O}(\log n)$ overhead to both operations and queries). Then loop through the array produced after all insertions, at each point checking if the delete count of the value there is nonzero. If it is, we delete that value and decrement the count. Otherwise we proceed as normal. This takes linear time in the size of the snapshot and the number of operations we apply, which is linear in the size of the output.

It remains to show that this method of storing snapshots only uses $\mathcal{O}(n)$ memory. We show this by induction: After $n$ operations, the total size of snapshots up to that point is at most $n$. This holds initially, since we have no operations and one snapshot of size $0$. Say the previous snapshot was at time $n\_0$ and was of size $s\_0$, and now after $a$ insertions and $b$ deletions, we are taking another snapshot. The size of this new snapshot is then $s\_0 + (a - b)$, and by induction the total size of snapshots at most $n\_0 + (s\_0 + (a - b))$. Thus it suffices to prove that $n\_0 + a + b \geq n\_0 + s\_0 + (a-b)$, but this is equivalent to $2b \geq s\_0$, which trivially holds, since $2b \geq 2\lceil \frac{s\_0 + 1}{2} \rceil \geq s\_0 + 1$.
> 1 votes

# Answer
The key observation is the fact that **only** a single value will be changed in every operation.

For each element maintain an array of the form `[(snap_id, value)]`.

Every time you need to snapshot the array, find out which elements have changed since their last snap\_shot and update only those elements.

If you are asked to retrieve the value of any element at any given snap\_id then you can simply `binary_Search` over the array of `(snap_id, value)` and return the value corresponding to the `snap_id` that is the **closest but lesser**(lower\_bound in CPP) than the requested id.
> 0 votes

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


# Question
Title: binary search terminating condition (left != right) vs (left <= right)
I have seen several implementations of binary search where they can use either (left != right) or (left \<= right). For example, in normal binary search where you check if target value is in the array, using inclusive right bound (right initially set to array size-1), you will use left \<= right. When you want to find the first element larger or equal to target value, you use (left != right). I think my problem is I don't understand the difference between the two. Can someone tell me the intuition of when to pick one condition over the other?

# Answer
> 3 votes
With the `left != right` condition, like in the following code sample, where `vec` is a sorted array and `val` is the value we are looking for,

```
int left = 0, right = (int)vec.size();
while(left != right) {
    int mid = (left + right) / 2;
    if (vec[mid] < val) left = mid + 1;
    else right = mid;
}

```

Both `left` and `right` will in the end denote the least index where `vec[i] >= val` (possibly outside the bounds of the array).

With the `left <= right` condition, like in the following code sample,

```
int left = 0, right = (int)vec.size() - 1;
while(left <= right) {
    int mid = (left + right) / 2;
    if (vec[mid] < val) left = mid + 1;
    else right = mid - 1;
}

```

`left` will in the end denote the least index where `vec[i] >= val`, and `right` the greatest index where `vec[i] < val` (either possibly outside the bounds of the array).

In my subjective opinion, the difference is so small that it is best to choose one and only ever use it. My preference is the former, as I find it easier to reason about just one value rather than two.

---
Tags: binary-search
---


# Question
Title: Selecting vertices in a graph in an order to keep border vertices as few as possible
I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white regions is minimal. Is there an algorithm to find an optimal order for that?

More formally. We are given an undirected, connected graph $G = (V,E)$ consisting of $n$ vertices. I am looking for a sequence of increasing subsets of vertices $V\_0, V\_1, ..., V\_n$, where $V\_0 = \emptyset$, $V\_{i+1} = V\_i \cup \\{v\\}$ for some $v\in V$, and $V\_n = V$. For any subset $W \subset V$ we define a cost function $c(W)$ as the number of "border" vertices, i.e. size of $\\{w\in W : \exists m\in V\setminus W: (w,m)\in E \\}$. I am looking for such a sequence where $\max\_i(c(V\_i))$ is minimal.

I feel my problem is somehow related to maximum flow algorithms, the same way as minimum-cut problem is. I think there must be a name for this (or similar) problem. However, as I was mixing "minimal cut" in various ways in the search engines, I was unable to find it.

A bit of context: I have a series of tasks to perform (edges), each loading two files from a disk (vertices). In order to speed up the process, I don't want the reload every pair of files every time. Instead, I want to keep some files in memory so that I can reuse them when another task uses the same file. But I cannot keep all files that there are because of memory constriants. The above sequence would help me select an optimal processing order, keeping the number of active files to minimum.

# Answer
At first I didn't see how the problem underlying your actual application of using file buffers optimally matched your formulation. But as you mentioned in a comment, they are in fact two equivalent ways of describing the same problem, which amounts to generating a valid maximum-buffer-size-minimising sequence of *operations*, with each operation being one of "Load file $x$ to a free buffer slot", "Discard buffered file $y$ from its buffer slot" or "Process edge $(u, v)$" with $u$ and $v$ both being currently-buffered files:

* **Order vertices** (your sequence of larger-by-one sets is equivalent to a vertex ordering) so as to minimise the maximum number of "border" vertices, which correspond to files already loaded into the buffer and which cannot be discarded yet because they are still needed in the future. A sequence of operations can be generated from this vertex order as follows: After choosing a vertex to blacken, load it to a free slot and immediately process all edges it has to existing black vertices (which we know by induction to be still in the buffer) in some arbitrary order, and then (again in arbitrary order) discard from the buffer any of them that have no more white neighbours.
* **Order edges** so as to minimise the maximum number of "live" vertices, where a vertex becomes live the first time an edge it is incident on appears, and ceases to be live just after the last such edge. A sequence of operations can be generated from this edge order as follows: Load any vertices necessary for the current edge (in either order if neither is in the buffer yet), process the edge, discard from the buffer any vertex that is no longer live (again in arbitrary order).

I see now that your "border" is the same as my "live".

# It's NP-hard

## Fewest buffer slots needed to avoid reloading

If you want to know the smallest number of buffer slots required to process every file-pair (edge) without ever reloading a file (vertex), this problem is equivalent to the Vertex separation number problem, in which the goal is to choose, from all possible vertex orderings, an ordering that minimises the maximum number of "live" vertices, where a vertex is live at time $i$ iff it appeared before position $i$ in the sequence and has an edge to any vertex at position $\ge i$ in the sequence. Basically, a live vertex at some point in time is a file that has been loaded already but can't be discarded from the buffer yet because it is needed again in the future.

The vertex separation number is another name for the pathwidth of a graph, which is known to be NP-hard to compute. (And finding an actual solution -- a sequence of loads that meets this bound -- is at least as hard as this, of course.) No one knows how to solve an NP-hard problem exactly in subexponential time w.r.t. its size, so any algorithm to solve this problem will be likely be very slow for $n \> 20$ vertices or so. The only bright side here is that you don't have to feel bad about using a brute-force solution, like trying all possible vertex orderings. Some tricks may give good speedups in practice, like branch and bound (noticing when your sequence of vertices so far is already worse than a complete solution found earlier, and halting recursion early).

## Fewest loads needed for given buffer size

If you have a fixed number $b$ of buffer slots and want to know the smallest number of loads that would be needed using that many slots, this problem is at least as hard as the former one: Any algorithm that answers this question can easily be changed to answer the former one, by binary-searching on $b$ until you find that the answer is equal to the number of vertices (files), $n$. (Again, finding a sequence of loads meeting this bound is at least as hard as this.)

# Heuristics

The above explains why you can't expect to solve large instances of this problem quickly *and* optimally. If you don't care too much about optimality, many heuristics are possible.

Probably the simplest, and what I would try first, is just trying many different random orders, measuring each, and returning the best. Alternatively, start from a random order and look for local improvements, like swapping each pair of vertices, and greedily take the new solution if it is better. When no better solution can be found, restart with a fresh random order. Repeat this as many times as you feel like.

Alternatively you could repeatedly choose a vertex of minimum degree, and process all edges incident on it that have not already been processed. A minimum-degree vertex can be chosen in constant amortised time, and this approach bounds the number of loads by $kn$, where $k$ is the degeneracy of the input graph -- a number that is likely to be low on sparse graphs. Often there are multiple elimination orderings, which may require different numbers of reloads, so this basic strategy could probably be improved quite a bit by tracking which vertices currently have all their neighbours already in the buffer, immediately processing all edges incident on them, and then discarding them.
> 4 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Why doesn't the recursion theorem prove there is an undecidable finite set?
I created something similar to Sipser's proof for the undecidability of $A\_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't figure out why for the life of me.

> $A\_R := \\{\langle M \rangle | M = R \land M \text{ accepts "foobar"}\\}$
>
> Assume $D$ decides $A\_R$. $R:=$ On any input:
>
> 1. By the recursion theorem, get own description $\langle R \rangle$
> 2. Run $D$ on $\langle R \rangle$
> 3. Do the opposite of what $D$ says. If it rejects, accept. If it accepts, reject.
>
> $R$ contradicts what $D$ says about $R$. So $D$ can't be a decider. (i.e. If $D$ accepts $R$, $R$ should accept "foobar", but $R$ will reject all strings. If $D$ rejects $R$, $R$ should reject "foobar", but $R$ will accept all strings).

But because $A\_R$ can only contain $R$, $A\_R = \emptyset \lor A\_R = \\{\langle R \rangle\\}$. Either way, it's finite, so $A\_R$ is decidable.

So what's wrong with the first argument? A few ideas cross my mind:

* I'm losing an important detail by making an informal argument.
* Something odd in the recursive relationship between building $A\_R$ and referencing $D$. (this could possibly be avoided by narrowing it to the subset of TMs with the length of R, which we could "guess" before R is created - and it would still be finite)
* Logic shenanigans (a la the Liar Paradox)

But I just don't see exactly what the problem is.

**Elaborating on my interpretation of the error for additional reference**:

The argument looks like this:

1. Given an arbitrary decider for $A\_R$, we can construct a TM $R$.
2. Given $R$, we construct $A\_R$.
3. Then we can obtain a contradiction. So there is no decider for $A\_R$.

That's circular, and hopefully more obviously wrong. And guessing the length of $R$, as previously suggested, doesn't work either - because an arbitrary decider has an arbitrary length.

# Answer
> 5 votes
**Your argument "goes backwards."**

Note that your definition of $R$ depends on $D$ (step $2$). This means you can't conclude that *no* machine decides $A\_R$, merely that $D$ specifically doesn't.

Basically, what you've written looks like this:

* CLAIM: there is some $x$ such that no $y$ does \[task involving $x$\].
* PROOF: picking some $y$, we build an $x$ such that $y$ does not do \[task involving $x$\].

**And this isn't valid**.

---

It may help to consider an argument of the same "shape" but about a more concrete topic.

* CLAIM: there is a natural number $n\>1$ which isn't divisible by any prime $p$.
* PROOF: fixing a prime $p$, let $n=p+1$. Then $n$ isn't divisible by $p$.

The subtle nature of decidability often makes questions about it appear more complicated than they are, and I think this is such a situation.

---

It's worth noting that the recursion theorem can be applied here to show **something** \- specifically, that the $A\_R$s are not *uniformly* decidable.

Specifically, suppose I have some total computable function $f$. By the recursion theorem I can whip up a machine $R$ such that $R$ behaves as you describe for $D=f(R)$, and so $f(R)$ cannot decide $A\_R$. This means:

> While for each $R$ there is some $D$ which decides $A\_R$, there is no **computable** way to find such a $D$ given $R$.

This isn't surprising - the same result follows more simply from the unsolvability of the halting problem - but it is an important example of how the recursion theorem can be used to prove non-uniform decidability results even when each of the languages in question is decidable.

# Answer
> 4 votes
It's your second bullet point - something odd in the recursive relationship.

The argument is trying to show a contradiction by exhibiting a finite language that is undecidable.

In other words, the argument needs to show that there exists a finite language $L$ such that for every decider $D$, there is some input $w$ such that $D$ incorrectly decides whether $w \in L$.

The problem is that you are switching quantifiers: you are picking a decider $D$ first, and then you are exhibiting a language (by specifying $R$ that depends on $D$) and saying that $D$ does not decide $A\_R$ correctly. To obtain a contradiction, your language cannot know in advance the decider it will be tried on.

I'd like to add that while $A\_R$ is decidable for every fixed $R$ (as it is a finite set), if you make $R$ an input parameter, the resulting set is no longer decidable.

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