title: Distributed vs parallel computing

text:
# Question
Title: Distributed vs parallel computing
I often hear people talking about *parallel* computing and *distributed* computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty easily, while I believe it is very different:

* *Parallel* computing is more tightly coupled to multi-threading, or how to make full use of a single CPU.
* *Distributed* computing refers to the notion of divide and conquer, executing sub-tasks on different machines and then merging the results.

However, since we stepped into the *Big Data* era, it seems the distinction is indeed melting, and most systems today use a combination of parallel and distributed computing.

An example I use in my day-to-day job is Hadoop with the Map/Reduce paradigm, a clearly distributed system with workers executing tasks on different machines, but also taking full advantage of each machine with some parallel computing.

I would like to get some advice to understand how exactly to make the distinction in today's world, and if we can still talk about parallel computing or there is no longer a clear distinction. To me it seems distributed computing has grown a lot over the past years, while parallel computing seems to stagnate, which could probably explain why I hear much more talking about distributing computations than parallelizing.

# Answer
This is partly a matter of terminology, and as such, only requires that you and the person you're talking to clarify it beforehand. However, there are different topics that are more strongly associated with parallelism, concurrency, or distributed systems.

**Parallelism** is generally concerned with accomplishing a particular computation as fast as possible, exploiting multiple processors. The scale of the processors may range from multiple arithmetical units inside a single processor, to multiple processors sharing memory, to distributing the computation on many computers. On the side of models of computation, parallelism is generally about using multiple simultaneous threads of computation internally, in order to compute a final result. *Parallelism* is also sometimes used for real-time reactive systems, which contain many processors that share a single master clock; such systems are fully deterministic.

**Concurrency** is the study of computations with multiple threads of computation. Concurrency tends to come from the architecture of the software rather than from the architecture of the hardware. Software may be written to use concurrency in order to exploit hardware parallelism, but often the need is inherent in the software's behavior, to react to different asynchronous events (e.g. a computation thread that works independently of a user interface thread, or a program that reacts to hardware interrupts by switching to an interrupt handler thread).

**Distributed computing** studies separate processors connected by communication links. Whereas parallel processing models often (but not always) assume shared memory, distributed systems rely fundamentally on message passing. Distributed systems are inherently concurrent. Like concurrency, distribution is often part of the goal, not solely part of the solution: if resources are in geographically distinct locations, the system is inherently distributed. Systems in which partial failures (of processor nodes or of communication links) are possible fall under this domain.
> 61 votes

# Answer
As pointed out by @Raphael, Distributed Computing is a subset of Parallel Computing; in turn, Parallel Computing is a subset of Concurrent Computing.

*Concurrency* refers to the *sharing* of resources in the same time frame. For instance, several processes share the same CPU (or CPU cores) or share memory or an I/O device. Operating systems manage shared resources. Multiprocessor machines and distributed systems are architectures in which concurrency control plays an important role. Concurrency occurs at both the hardware and software level. Multiple devices operate at the same time, processors have internal parallelism and work on several instructions simultaneously, systems have multiple processors, and systems interact through network communication. Concurrency occurs at the applications level in signal handling, in the overlap of I/O and processing, in communication, and in the sharing of resources between processes or among threads in the same process.

Two processes (or threads) executing on the same system so that their execution is interleaved in time are concurrent: processes (threads) are sharing the CPU resource. I like the following definition: two processes (threads) executing on the same system are concurrent if and only if the second process (thread) begins execution when the first process (thread) has not yet terminated its execution.

Concurrency becomes parallelism when processes (or threads) execute on *different CPUs* (or cores of the same CPU). Parallelism in this case is not “virtual” but “real”.

When those CPUs belong to the same machine, we refer to the computation as "parallel"; when the CPUs belong to *different machines*, may be geographically spread, we refer to the computation as "distributed".

Therefore, Distributed Computing is a subset of Parallel Computing, which is a subset of Concurrent Computing.

Of course, it is true that, in general, parallel and distributed computing are regarded as different. Parallel computing is related to tightly-coupled applications, and is used to achieve one of the following goals:

1. Solve compute-intensive problems faster;
2. Solve larger problems in the same amount of time;
3. Solve same size problems with higher accuracy in the same amount of time.

In the past, the first goal was the main reason for parallel computing: accelerating the solution of problem. Right now, and when possible, scientists mainly use parallel computing to achieve either the second goal (e.g., they are willing to spend the same amount of time $T$ they spent in the past solving in parallel a problem of size $x$ to solve now a problem of size $5x$) or the third one (i.e., they are willing to spend the same amount of time $T$ they spent in the past solving in parallel a problem of size $x$ to solve now a problem of size $x$ but with higher accuracy using a much more complex model, more equations, variables and constraints). Parallel computing may use shared-memory, message-passing or both (e.g., shared-memory intra-node using OpenMP, message-passing inter-node using MPI); it may use GPUs accelerators as well. Since the application runs on one parallel supercomputer, we usually do not take into account issues such as failures, network partition etc, since the probability of these events is, for practical purposes, close to zero. However, large parallel applications such as climate change simulations, which may run for several months, are usually concerned with failures, and use checkpointing/restart mechanism to avoid starting the simulation again from the beginning if a problem arise.

Distributed computing is related to loosely-coupled applications, in which the goal (for *distributed supercomputing*) is to solve problems otherwise too large or whose execution may be divided on different components that could benefit from execution on different architectures. There are several models including client-server, peer-to-peer etc. The issues arising in distributed computing, such as security, failures, network partition etc must be taken into account at design time, since in this context failures are the rule and not the exception.

Finally, *Grid* and *Cloud* computing are both subset of distributed computing. The grid computing paradigm emerged as a new field distinguished from traditional distributed computing because of its focus on large-scale resource sharing and innovative high-performance applications. Resources being shared, usually belong to multiple, different administrative domains (so-called *Virtual Organizations*). Grid Computing, while being heavily used by scientists in the last decade, is traditionally difficult for ordinary users. Cloud computing tries to bridge the gap, by allowing ordinary users to exploit easily multiple machines, which are co-located in the same data center and not geographically distributed, through the use of *Virtual Machines* that can be assembled by the users to run their applications. Owing to the hardware, in particular the usual lack of an high-performance network interconnect (such as Infiniband etc), clouds are not targeted for running parallel MPI applications. Distributed applications running on clouds are usually implemented to exploit the Map/Reduce paradigm. By the way, many people think of Map/reduce as a parallel data flow model.
> 17 votes

# Answer
I'm not sure I understand the question. The distinction between parallel and distributed processing is still there. The fact that you can take advantage of both in the same computation doesn't change what the concepts mean.

And I don't know what news are you following, but I'm quite sure parallel processing is not stagnating, especially since I think it's useful much more often.

If you need to process terabytes of data, distributed computing (possibly combined with parallel computing) is the way to go. But if you need to compute something on a desktop or smartphone, parallel computing alone will probably give you best results, considering that internet connection might not be available always and when it is, it can be slow.
> 7 votes

# Answer
Here is a recent paper that is worth reading:

Michel Raynal: **"Parallel Computing vs. Distributed Computing: A Great Confusion?"**, *Proc. Euro-Par 2015*, doi:10.1007/978-3-319-27308-2\_4

Abstract:

> This short position paper discusses the fact that, from a teaching point of view, parallelism and distributed computing are often confused, while, when looking at their deep nature, they address distinct fundamental issues. Hence, appropriate curricula should be separately designed for each of them. The “everything is in everything (and reciprocally)” attitude does not seem to be a relevant approach to teach students the important concepts which characterize parallelism on the one side, and distributed computing on the other side.
> 7 votes

# Answer
In the Introduction section of the book \[1\], the authors provide another perspective (different from the ones in other answers) on the comparison between distributed computing and parallel computing.

> In broad terms, the goal of parallel processing is to employ all processors to perform one large task. In contrast, each processor in a distributed system generally has its own semi-independent agenda, but for various reasons, including sharing of resources, availability, and fault tolerance, processors need to coordinate their actions.

From this perspective, the Map/Reduce paradigm mainly falls into the parallel computing context. However, if we want the nodes involved to reach a consensus on a common leader, by using, for example, the Paxos (wiki) algorithm, then we are considering a typical problem in distributed computing.

\[1\] Distributed Computing. Fundamentals, Simulations, and Advanced Topics. Hagit Attiya and Jennifer Welch. 2004.
> 4 votes

# Answer
There is the answer which is more appropriate here. Basically, `parallel` refers to `memory-shared multiprocessor` whereas `distributed` refers to its `private-memory multicomputers`. That is, the first one is a single multicore or superscalar machine whereas another is a geographically distributed network of computers. The latter implies less coupling and, thus, more availability and fault tolerance at the cost of less performance. The performance is suffered because you need data (de-)serialization in every round-trip and its delivery over longer distances whereas you can simply refer an in-memory object to pass it to another CPU in parallel processor.
> 0 votes

# Answer
Well Everyone described it before I'll try to answer it as simple way.

**Parallel Computing**

Processors Communicate with other processors with having common shared memory between them. As the number of processors increases as per computation they are capable of performing well than a sequential systems (Remember these processors have common local allocated memory inside them which may not be shared with other processors).Memory is tightly coupled shared. Parallel computing is mainly used for performance, scientific computing.

**Distributed Computing**

Distributed systems have multiple processors having their own memory connected with common communication network. Distributed systems are more scalable, economic ,resource sharing ,reliable, modular . Distributed systems are prone to more unauthorised vulnerabilities and attacks.
> 0 votes

# Answer
I find it surprising that none of these answers use the abbreviations SIMD and MIMD, which have been core architectural concepts for parallel processing since the origin of that term.
> 0 votes

---
Tags: terminology, distributed-systems, parallel-computing
---


# Question
Title: Sequent calculus and vs comma: $a \land b \implies ...$ vs $a, b \implies ...$
I was reading "Open Logic book", "Sequent Calculus". Given the fact that all antecedents must hold for at least one succedent to hold, I can't get rid off the impression that using a "comma" on the left side doesn't bring anything new, and I could simply replace it with "$\land$".

For example, let's take:

What prevents me from treating the bottom part as if it was "$-\varphi \land \Gamma \implies \Delta$"?

In another case,

Here "$\psi$" is introduced out of thin air, and is "$\land$-appended" to existing context. Which looks extremely similar to "weakening-left" rule which also introduces a new proposition out of nothing, but now prepending it with a comma:

Which even further blurs the distinction for me.

# Answer
> 4 votes
> What prevents me from treating the bottom part as if it was "$-\varphi \land \Gamma \implies \Delta$"?

Nothing prevents you! In fact, this is exactly the right idea. You can think of the symbols in sequent calculus as follows:

* comma on the left means $\land$
* comma on the right means $\lor$
* $\implies$ means $\to$ (if then)

In fact, we could go further: we could develop all the rules of sequent calculus using only $\land$ and $\lor$ in place of commas The negation left rule, for example, would look like this: from the formula $\Gamma \to \Delta \lor \varphi$, deduce $\Gamma \land \lnot \varphi \to \Delta$.

So why don't we do it that way? There are a few reasons:

* First and most importantly, using meta-symbols gives us the following property: **each logical symbol can only be introduced by the introduction rules for that symbol, and by no other rules.** If comma were not a meta-symbol, then for example, the negation left-introduction rule would *remove* the symbol $\lor$ and *add* the symbol $\land$. This would defeat the whole point of sequent calculus: to give an account of each logical operator alone in isolation, without reference to the other logical operators. The goal is to give every logical operator a meaning solely in terms of the syntax of commas and $\implies$.
* A second key property of sequent calculus is that a logical symbol (like $\land$ and $\lor$) can only ever be *introduced*, and never taken away. So we use commas for the meta-symbols since they can be both introduced and taken away (and also reordered).
* Another advantage of comma is that it reveals a fundamental symmetry between conjunction $\land$ on the left, and disjunction $\lor$ on the right, since they are both represented by comma. It shows that, for example, the left-rules for conjunction match the right-rules for disjunction and vice versa; this wouldn't be clear if we didn't use the same symbol for both.

In summary: yes, comma is just conjunction on the left and disjunction on the right! But it's used as a *meta-symbol*, rather than a symbol in the logic itself, and this has very important implications. Using meta-symbols is what allows us to claim sequent calculus is a structural, syntactic *theory of proofs* and not just an arbitrary collection of rules about semantic implication.

---
Tags: logic, propositional-logic
---


# Question
Title: Comparisons using Quicksort with the median as the pivot
## Background

Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm:

> **Quicksort($a$):**
>
> * (1) If length($a$) $\> 1$, then
>
> > * 1.1) pivot $← a \[1\]$.
> > * 1.2) less $← a\[a \<$ pivot\].
> > * 1.3) equals $← a\[a ==$ pivot\].
> > * 1.4) greater $← a\[a \>$ pivot\].
> > * 1.5) $a ←$ concat(Quicksort(less), equals, Quicksort(greater)).
>
> * (2) Output $a$.

It is clear to see that the total number of comparisons will follow the recurrence equation:

$$C(n) = C(n-1) + (n-1) \space \space \text{ where } \space C(2) = 1$$

From here we see that $C(n) = \Theta (n^2)$

Here is the context under which this came up:

>

## Question

The above is clear to me, however, I have now read that if we use the median as a pivot (which can be identified in $\Theta (n)$ time), then we get the following recurrence inequality:

$$ C(n) \leq 2C ( \lceil n/2 \rceil -1) + Mn $$

And this gives the result that $C(n) = \Theta (n \log n)$.

---

How have these two results been derived (the recurrence inequality and time complexity for the updated algorithm)? The only difference is that we are computing the median each time. This is achieved in $\Theta (n)$ time each time that it is calculated but it still isn't entirely clear where this inequality comes from or why the new time complexity is $\Theta(n \log n)$ for the entire algorithm.

---

Here is the exact context under which it came up:

>

# Answer
The genuine Quicksort is an in-place algorithm, and your version with concatenations uses extra memory and is much less efficient for this reason \[$\Theta(n^2)$ instead of $O(n^2)$ with best case $O(n\log n)$\]. Also, it is a waste of time to apply the trichotomy \<, =, \>, which costs two comparisons where you can do with a single.

This said, the behavior of Quicksort relies on the "balancing" of the pivot: it every pivot generates a partition with a single element on a side and the rest on the other side, the total complexity is indeed proportional to $n+(n-1)+(n-2)+\cdots $, which is $\Theta(n^2)$.

But if every pivot splits the array in two equal halves, the total complexity is like $n+\dfrac n2+\dfrac n2+\dfrac n4+\dfrac n4+\dfrac n4+\dfrac n4+\cdots$, which equals $n\log\_2n$.

---

Note that Quicksort is *never* implemented with the median taken as the pivot, because the linear-time median algorithm is complicated and much slower than the partitioning process itself. If one needs an algorithm with *guaranteed* worst-case complexity $O(n\log n)$, Heapsort is a better choice.
> 2 votes

---
Tags: algorithms, time-complexity, asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: How to show that any computable function is bounded above by Busy Beaver Function?
Despite the endless hours of googling, pretty much all of them used an alternative definition of Busy Beaver function. The definition BB(k) I'm interested in is the maximum number of 1's that can be written by k-state before it halts, but the other definition they used was the maximum number of steps, and they're not equivalent.

And one of the techniques they used is by reduction from halting problem, that if there was any computable function f(x) bounding above the function BB(k), you can solve halting problem in a finite amount of time using the alternative definition, but this argument doesn't work for the definition of BB(k) I am interested in. How do we show that BB(k) is asymptotically larger than any computable function f(x)?

# Answer
I think a sketch of the proof could be as follows.

First prove BB(k) is uncomputable. Assume it is computable, then it means there is some machine with some number of states m that can compute this value. Show that there exist a larger machine with some number of states M that calls this function on BB(M) and outputs BB(M)+1 1s, and then halts. Therefore there is a contradiction since it outputed more 1s than predicted by BB(M). It's easy to see M = m + C for some constant.

Now regarding the growth.

Assume G(k+1) \>= BB(k+1) - BB(k) is computable for k \>= K0.

Now, if the above is true then there must exist a machine with m states that computes G(k).

And there must also exist a machine, with a larger number of states M, that guesses BB(K0) and then computes UBB(M) = sum(K0..M)G(k) + BB(k0) and output UBB(M)+1 1s.

So this machine outputs more 1s than our assumed computable upper bound.

Therefore G(k) can not be computed for any K0.
> 1 votes

# Answer
Suppose you have a computable function that dominates the busy beaver function. Then you immediately get that the busy beaver function is computable: given a machine of n states, simply run the machine for f(n) cycles, where f is your dominating computable function. If it quits note that number of cycles. If it does not stop in f(n) cycles then it never will. Take the max over all n state machines. You have computed B(n).
> 0 votes

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


# Question
Title: What is the complexity of theorem proving?
I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex as the Halting Problem, i.e., knowing if a TM halts? Where can I learn more of this (subjects, books, articles)?

Let me know if my question is wrong. Regards.

# Answer
In general, the complexity of theorem proving in a particular logical system (such as ZFC) is recursively enumerable (RE), and is complete for this class -- that is, equally as hard as solving the halting problem. To see this, we can show a reduction both ways:

* First, to show that theorem proving is RE: the statements provable in any known logical system can be listed out recursively, by enumerating all the axioms and all the possible proofs from those axioms. (This applies to any theory where the axioms are recursively enumerable, which includes ZFC, Peano arithmetic (PA), first-order logic, and any other familiar logical system). Therefore, theorem proving reduces to the halting problem and is RE.
* Second, to show theorem proving is complete for the class RE, we can reduce the halting problem to theorem proving. For this, it requires that the logical system is sufficiently expressive to state and prove properties about Turing machines; for example, this is true for ZFC and PA. Additionally, the encoding of properties has to be *faithful* (doesn't prove anything false about natural numbers); technically, it should be either omega-consistent or arithmetically sound. These properties most likely hold for ZFC if it is consistent, and certainly hold for PA.

Then the way the reduction work is, given a Turing machine $M$, encode the property "$M$ halts" as a formula in ZFC. The formula says, roughly, "there exists a finite sequence of configurations of the tape and sequence of states of $M$ such that each pair of adjacent states are a valid transition of the Turing machine and the last state in the sequence is halting." It turns out we can express all of that in ZFC (or indeed, in PA). If $M$ halts, the formula is provable; and if $M$ does not halt, arithmetical soundness (or $\omega$-consistency) implies the formula is not provable. So this reduction shows that theorem proving is at least as hard as the halting problem.

It may be interesting to note that the facts we used in the above two reductions are exactly the requirements about a logic that are necessary for Gödel's incompleteness theorems to apply to that logic: i.e. (i) the logic's axioms must be recursively enumerable, and (ii) the logic must be strong enough to (faithfully) encode properties about arithmetic and Turing machines.

Finally, I will note that if either of (i) or (ii) does *not* hold, then we get a different situation. Typically, (i) holds in any reasonable logic; no one studies logics that are not recursively enumerable. But many researchers look at logics that are *weaker* than ZFC and PA, for which (ii) does not hold; for example, satisfiability in linear arithmetic, or satisfiability of Boolean formulas. For these, we get much weaker complexity than RE that is often not just decidable, but in PSPACE, or NP, or a similar complexity class. For more on this topic, you can read about automated theorem proving and satisfiability modulo theories (SMT).
> 16 votes

---
Tags: complexity-theory, halting-problem, automated-theorem-proving
---


# Question
Title: Are there any radical approaches in CPU development?
I have a desktop PC with the CPU Intel I7-12700F with **180 TDP**, the CPU fan Zalman CNPS10X extreme, and Windows 11 and my problem is that The CPU cooling causes much noise when simple tasks are being performed; opening directories or windows, opening or closing small programs such as Notepad, Calculator, web browser, or when taking the PC out of sleep mode.

I am not a CS student, just a layman trying to understand if the desktop CPU development field is somewhat "stuck" in the past decades.

If desktop CPUs of the 2020's generally use more power than those of previous decades hence get hot faster and require more extensive and noisy cooling, I'd carefully assume that desktop CPUs of 2020's aren't essentially very different than those of the 90's and 80's.

Are there perhaps different **paradigms** to create essentially differently desgined desktop CPUs which may allow similar capabilities but with **fanless cooling** / passive cooling?
Currently, fanless cooling is nearly nonexistent when it comes to desktop CPUs. A notorious CPU cooling model, *Nofan CR-80EH* is aimed for desktop CPUs of no more than **80 Watt TDP** and I don't know if such CPUs are still manufactured.

I am coming to ask this ignorantly and by a possible false analogy to electricity production. If I am not mistaken, electricity production has had some radical engineering shifts from coal burning, such as producing electricity from water flow, wind flow, nuclear reaction (such as fission), solar panels (also heat but still a radical change) and who knows what future holds?

Is there any radical approach to develop desktop CPUs at least in theory or currently in research labs, that will allow completely silent / fanless desktop computers with CPU capabilities similar to those of current desktop CPUs?

By the way, why not creating a motherboards with several small general processers, each one with passive cooling?

# Answer
Two areas of research to consider:

* Reversible logic, and in particular, adiabatic circuits. The idea here is to increase energy conservation as much as possible by not destroying information most of the time.
* Asynchronous logic. The theory behind this is that the best CPU clock speed is no clock at all.
> 1 votes

# Answer
This already exists. Mobile processors meet all of your requirements.

There is a fundamental, unavoidable tradeoff between power consumption and processing speed. You can already buy CPUs that lie at different points along that tradeoff. Companies like Intel, AMD, etc., market high-end CPUs that maximize processing speed, at the cost of consuming more power; these are typically called "desktop CPUs" for marketing purposes. Companies like Apple, ARM, Intel, AMD, etc. also make CPUs that are designed to reduce power consumption, at the cost of somewhat lower processing speed; these are typically called "mobile CPUs" for marketing purposes. If you build a CPU for desktops that achieves lower power consumption, low enough to build a desktop CPU, then it is considered a mobile CPU, for marketing purposes.

So the CPUs that are marketed as "mobile CPUs" already are exactly what you are looking for.

You can already build a fanless desktop, by using a mobile processor and other parts that have lower power consumption, and there are plenty of them that you can already buy today. For instance, if you search for "fanless PC", you'll find many systems that you can buy right now.
> 3 votes

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


title: !(ab)*(!a+b)(!b+b)=!a Boolean Algebra

text:
# Question
Title: !(ab)*(!a+b)(!b+b)=!a Boolean Algebra
How can I prove that ***!(ab)*(!a+b)(!b+b)=!a*** in boolean algebra? This is an exercise from a past paper of my teacher but I can't really find the way to the answer. I would appreciate some help.

# Answer
The third factor is always $1$. Then

$$\begin{align}&a=0\to &1\\,(1+b)&=1,\\\&a=1\to &!b\\,b&=0.\end{align}$$
> 1 votes

# Answer
**!** is a negation and will be replaced by **¬** in this answer. This would transform your equation to **¬(ab)(¬a+b)(¬b+b)**. "True" has a value of 1 and "False" has a value of 0. The operations are applied on these numbers in **mod 2** arithmetic. The negation of 0 would be 1 and vice versa, so **(¬b+b)=1**. Since multiplication by 1 does not do anything, this can be removed to transform the equation to **¬(ab)(¬a+b)**. Adding 2 booleans together will give "True" only if they have different values, so negating one of them will mean it will return "True" if they have the same value. Multiplying 2 booleans together will return "True" only if both of them are true, so the negation of that will return "True" only if at least one of them is "False". Putting this into coding notation, this becomes `(not (a and b)) and (a=b)`. So to return "True", a and b have to have the same value, and one of them have to be "False", so they both have to be "False" to return "True". This is equivalent to `not (a or b)`. So the final equation (in traditional boolean algebra) is **¬(a∨b)=¬a**. Let's make a truth table:

```
--------------------------------
| a | b | not (a or b) | not a |
--------------------------------
| 1 | 1 |      0       |   0   |
| 1 | 0 |      0       |   0   |
| 0 | 1 |      0       |   1   |
| 0 | 0 |      1       |   1   |
--------------------------------

```

We find that this equality is untrue in boolean algebra.
> -2 votes

---
Tags: boolean-algebra
---


# Question
Title: How to prove this simple randomized algorithm is 2-approximate for MAS?
The Maximum Acyclic Subgraph (MAS) problem is:

> Given a directed graph $G = (V, E)$, find the largest subset of edges which are acyclic.

In this paper the authors state the following algorithm:

> A simple randomized algorithm achieves a factor 1/2 for this problem: Simply pick a random ordering of the vertices. In fact, one can achieve factor 1/2 by an even simpler algorithm: Pick an arbitrary ordering of the vertices $\pi$ and its reverse $\pi^R$. One of them has at least 1/2 fraction of the edges in the forward direction.

How can we prove that this is indeed a 2-approximation algorithm? I'm having trouble understanding what a reverse of an ordering could be, and what a "forward" direction is (since we're not dealing with network flow).

# Answer
> 1 votes
To prove the approximation guarantee for any algorithm, we mostly aim to find a lower bound on the optimal value (for *minimization problem*) or an upper bound on the optimal value (for *maximization problem*).

Since yours is a maximization problem, a trivial upper bound is $|E|$ for the optimal value since any solution is a subset of $E$ and thus contains less than $|E|$ edges.

Now, let us see how we get $2$-approximation. Take any arbitrary ordering of vertices: $v\_1, \dotsc, v\_n$.

1. Let $|E\_f|$ be the set of edges that goes forward, i.e., all edges in $E\_f$ are of the form $(v\_i, v\_j)$ such that $i \< j$. It is easy to see that this subset of edges forms an *acyclic subgraph*.
2. Similarly, $E\_b$ be the set of edges that goes backward, i.e., all edges in $E\_b$ are of the form $(v\_i, v\_j)$ such that $i \> j$. This subset of edges forms an *acyclic subgraph* as well.

It is easy to see that either $|E\_f| \geq |E|/2$ or $|E\_b| \geq |E|/2$.

Since $\mathsf{OPT} \leq |E|$, we get $|E\_f| \geq \mathsf{OPT}/2$ or $|E\_b| \geq \mathsf{OPT}/2$.

In other words, either $E\_f$ or $E\_b$ is a $2$-approximation. The algorithm simply chooses the one with the maximum cardinality.

---
Tags: approximation
---


# Question
Title: Should I remove equivalent variables in a CNF file to be used by a SAT solver?
My CNF file ends with many pairs of clauses that represent that two variables are equivalent (eg: -3 7, 3 -7, 5 -11, -5 11, etc.). Do most SAT solvers automatically pre-process these and replace every occurrence of one variable by the other (eg: replace every 7 by 3, and every 11 by 5), or should I first do the replacement processing to produce a simplified CNF file?

# Answer
> 1 votes
It won't hurt to do that, but you probably don't need to. If you happen to know that two variables are equivalent, a much easier way to let the solver use this information is simply to assert that they are equivalent:

$$\neg x\_3 \leftrightarrow x\_7$$

Which becomes, in CNF:

$$\left(x\_3 \vee x\_7\right) \wedge \left(\neg x\_3 \vee \neg x\_7\right)$$

Any solver based on DPLL knows how to use this information extremely efficiently.

If the variables appear enough, a CDCL solver will probably find these two clauses by itself eventually, but this would save it a bit of work.

---
Tags: satisfiability
---


# Question
Title: Why exactly can Turing Machines implement all computations but computers can't?
Is the only reason for why a modern computer can't implement all computations is that the detailed specification of some algorithmic action (as a natural number) can be larger than what the storage space of the computer allows to process?

I am trying to understand the difference in input implementation between Turing Machines (TMs) and computers. As far as I understand, TMs could take any input because they have an infinite tape. But computers do not have an "infinite tape", and so some computations may be "larger" (in terms of their specification as a natural number) than the computers' own storage space, and so the computers will not even begin processing the input.

Is the above accurate? And if yes, isn't it the case that a computer could read and implement any computation if we are allowed to arbitrary increase the storage space of that computer until it exceeds the specification of the computation-input? Or is there another factor than storage space that also makes a difference between TMs and computers in terms of implementation that we should consider?

Thanks for feedback!

# Answer
You can easily write a Turing machine simulator in your favourite programming language. A universal Turing machine does not need many states, so you can then run the simulator on a universal TM, and indeed the only issue is the tape.

If you implement the tape eg as a doubly-linked list, the simulator could could run into a problem because the pointer to the next cell would eventually exceed whatever bounds for a pointer sizes you have. Alternatively, the entire data structure could exceed the storage space of your harddrive.

Here is another idea how you could implement the tape: The programme could store a tape segment of a few gigabyte in size on a USB stick. If the TM tries to move to the left or right of that segment, the simulator just prompts you to exchange USB sticks, and then continues on the segment which is on the USB stick next. With this model, there is really nothing specific about computers that would limit the ability to simulate TMs. Instead, the limitation is just inherent in your ability to provide more and more USB sticks.
> 1 votes

# Answer
TM's have no physical limitations (they are never built). Computers do.

TM's don't have a specific running time (they are never truly run). Computers die after some years.

---

If you are thinking of a "theoretical computer" of any kind, if it is Turing-complete then it can perform the same computations.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: How to Convert from Decimal to Qm.n format
How would you convert decimal 0.0650 to 1.15 Q format 16-bit of course? I'm kinda stuck in this for 3 days, can someone kindly help me out in this

# Answer
> 0 votes
Convert $0.065$ in binary with 15 digits of precision in the fractional part (rounding to the nearest such number):

$$ (0.065)\_{10} \approx ( 0.000100001010010)\_2$$

Multiply $(0.000100001010010)\_2$ by $(2^{15})\_{10}$ (i.e., remove the fractional-part separator) to obtain $(0000100001010010)\_2$.

If you want it in hexadecimal, as you have asked in another question, you can convert it:

$$ (0000100001010010)\_2 = (0852)\_{16} $$.

# Answer
> 0 votes
If you multiply the Q1.15 format by $2^{15}$ you get a Q16.0, i.e. an integer.

Evaluate $$0.0650\times 2^{15}=2129.92$$ which you round to $2130=100001010010\_b$.

Now you revert to Q1.15 by padding to get $15$ bits after the point:

$$0.000100001010010\_b$$

(this is exactly $0.06500244140625$.)

---
Tags: number-formats
---


# Question
Title: Space efficient data structure to store precomputed All Nearest Neighbors in high dimensions
**Seeking an indexing data structure that is smaller than quadratic in space.**

As part of an NLP algorithm using word embeddings of 300-dimensions, I am trying to improve the speed of Word Mover's Distance (WMD). (Isn't everybody?) Computing the cost matrix is expensive, as it is size MxN (where M and N are the number of distinct non-stop words in documents one and two, respectively). I figured that if I only compute the distances to the k-nearest neighbors of each word and set all others to the mean distance between word pairs, I can perform a high quality approximate value for WMD. (I am not the first to consider this flavor of speedup. See "Speeding up Word Mover’s Distance and its variants via properties of distances between embeddings" by Matheus Werner and Eduardo Laber, 2020 on arXiv.) The trick is knowing what those nearest neighbors are *a priori*.

*The corpus size is S = 250,000 words.*

*The dimensionality is 300 features per word embedding.*

What if you preprocess the corpus of words, performing all nearest neighbors search for every word and store it in a file? That would allow you filter the k-nearest words for each word present in a given document comparison from the index, saving the computation of the distance function for most word pairs and the sorting time of (M + N) * k log k.

It is trivial to store a matrix of size S * S with the neighbors of each word sorted from nearest to farthest.

**Is there a more space efficient structure than quadratic storage**, like a variant on a Trie? I do not need it to store the actual distances, just the ordering. I can recalculate the distances for the pairs I care about. The time complexity of the preprocessing is immaterial.

**Clarification of K:**

Say that you want the k-nearest neighbors of the word "happiness". You might think the index storage requirement is k\*S. However, what I want is NOT the K-nearest neighbors of *happiness* in the whole corpus of S words. I want the k-nearest neighbors drawn from the set of words in the opposite document. The 10th nearest word to *happiness* in the document could be the 10,000th nearest word in the whole corpus! That is the problem. To guarantee that I have all k-nearest words for ANY document that is produced for comparison, I need to store ALL neighbors for *happiness* from nearest to most distant.

As an exception, I will allow that once the distance to a word reaches the average distance between word pairs in S, it can be dropped from the index and the distance assumed to equal that mean distance. This automatically reduces the index size by half.

**Research:**

I have just learned about LSH, HNSW and IVF indices. You have control over accuracy versus speed, but the memory usage is substantial.

I have toyed with using Hilbert indices with lists of line segments sorted to give a loose ordering of neighbors that will need to be sorted later. That reduces number of computations of distances but does not do away with the K log K sort at the end.

# Answer
> 0 votes
After pondering this for days, I have arrived at a possible data structure. It may be some time before I get to testing whether it performs as well as hoped.

The index will be derived from the Hilbert Curve ordering of the points. The index construction time will be O(N-cubed).

1. Normalize and Quantize coordinates of the word embedding vectors to form integer valued points. 16-bits per coordinate should suffice, and likely fewer bits.
2. Obtain Hilbert index of each point.
3. Sort points by Hilbert index.
4. Once sorted, each point will be associate with its position in Hilbert order. Instead of being a huge Hilbert index of 300x16 bits, it will be an integer in \[0,S) where S is the number of words in the corpus.
5. For each point, find all nearest neighbors exhaustively, comparing distance from every point to every other point and sorting.
6. For each point, create an index of neighbors that is a list of Hilbert Curve line segments.
7. Store the index to a file.

The sixth step is the tricky part. A line segment will specify:

* start Hilbert position
* length of segment in word vectors
* Highest position P such that there are no gaps of missing near neighbors with a Hilbert position less than or equal to P in the set of all points included in the union of this segment with all prior segments.

Each constructed line segment will be longer than the previous line segment. The exponential growth factor will be the square root of two. (I will experiment with different growth factors.) By using exponentially growing line segments, we can guarantee that the storage requirement for the index is S log S. The first segment will be length ten. Thus the segment lengths will be 10, 14, 20, 28, 40, 56, 80, etc.

Segments for each point will be defined as follows:

1. The first segment for a point will begin at the position of that point’s nearest neighbor.
2. The segment will extend for ten positions in increasing Hilbert position.
3. A Boolean array called FOUND of length S will record whether the point at that Neighbor index has been included in the current or any prior segment. Found will refer to points in nearest neighbor order for that point, not Hilbert order.
4. Iterate through all points in the segment and mark off in FOUND that they have been captured by a segment.
5. Iterate over FOUND to find the position M of the lowest point in neighbor order that is missing. Record in the segment record the value M-1 as the highest neighbor index without gaps in the segment and all prior segments.
6. Since the segment lengths will be growing and ordered haphazardly, new segments may overlap prior segments. Truncate as much overlap from the end of the segment as possible if it overlaps one or more other segments. Take care not to truncate gaps between the overlapping segments. For example, if a new segment C ranges from 1000-2000 and overlaps segments A from 500-600 and B from 1700-2200, only truncate the new segment C to 1000-1699, otherwise the gap of 601-1699 between A and B will be lost.
7. Each subsequent segment will begin with the nearest neighbor of the target point that has not yet been captured by the index.

**Quality of Approximation**. Because of the locality preserving nature of the Hilbert curve, each of the early segments will contain mostly near neighbors of the target point, but will miss some and include more distant neighbors, thus the approximate nature of the index. Research using the Hilbert curve for clustering shows that the Hilbert curve tends to divide data into 1.5 to 3 times as many clusters as are really present in the data. A Python experiment to explore the viability of this exponential segmentation idea shows that when the cumulative group of segments reaches a place where it guarantees that it has captured the K nearest neighbors, it will have done so by capturing a set of 1.5 to 2K neighbors, and on rare instances up to 2.5K. This is more than acceptable.

Thus my expectation (that must be proven with more experiments upon a fully constructed index) is that when you ask for the K-nearest neighbors of a point, you will typically be given 2K neighbors, but will not miss any of the desired near neighbors.

In the WMD algorithm, we need K neighbors and optimally desire to compute ½ K-squared distances for our cost matrix. Since we get 2K neighbors instead, we instead need to compute 2K-squared distances. This is vastly superior to S-squared!

**Cost Matrix.** In the end, to compose the WMD cost matrix:

1. Load from the index only the lists of segments for the M+N words in your documents.
2. Walk the segments for each word.
3. Toss all words not in the documents.
4. Continue until the set has gathered at least K words from your documents.
5. Perform distance calculations between all retained words.
6. Sort by distance.
7. Keep the K-nearest.

Note:

The index written to the file Contains:

* List of Word Vector ids sorted in Hilbert index order
* A list for each Word Vector of Hilbert segments as defined above

---
Tags: algorithms, space-complexity, nearest-neighbour
---


# Question
Title: Data structure for fast look up of ranges, but that allows insertion
At work I'm looking for a data structure that supports the following operations:

$$insert(X, A, B)$$ $$delete(X)$$ $$glb(C)$$

$insert$ adds the range $\[A, B)$ into the data structure with value $X$ associated with it AND shifts all ranges after (exclusive) $A$ by $B - A$.

$delete$ removes the range associated with $X$. Call that range $\[A, B)$ then every range after (inclusive) $B$ is shifted back by $B - A$

The combination of $insert$ and $delete$ are meant to maintain the invariant that ranges never overlap. In order to actually maintain this however the user must never insert a range that has a lower bound contained in an existing range. So for instance if $\[3, 7)$ had already been inserted then it would be invalid to insert $\[4, 9)$ but it would be perfectly valid to insert $\[1, 5)$ or $\[1, 10)$

$glb(C)$ looks up the pair $(X, \[A, B))$ such that $A$ is the greatest start of an interval less than or equal to $C$. Note that this does not mean that $C \in \[A, B)$ as it could be that $C \gt B$

I'm hoping that I can do this in $\mathcal{O}(lg(n))$ or at least $\mathcal{O}(lg^2(n))$

Also it's highly advantageous if the data structure is a relatively simple data structure. Other practical things that might be of note $A$, $B$, and $C$ range over integers and $X$ can be hashed, ordered, and compared for equality. It's acceptable to have two data structures that we maintain a relationship between (for instancing maintaining a hash table that maps each $X$ to the node in the more complicated data structure that keeps track of the ranges).

So far the best thing I've been able to find is to maintain a finger tree and a hash table. The finger tree's keys are then the length of the interval. To insert like you would normally in a finger tree but you also store a mapping of $X$ to the node in the finger tree in a hash table. To delete you find the node of the value in the hash table then walk up the spine (so this finger tree needs back pointers) to perform the required delete on that child of the tree as normal. To find the $glb$ you perform the standard finger tree lookup. That should be logarithmic for all operations but I would rather have something simpler badly enough that I'd accept a polylogrithmic running time as a trade off.

Is there something simpler than this?

# Answer
You can achieve $O(\log n)$ time for all operations using a self-balancing binary tree. Augment the tree so that you can store a value $\delta$ in each internal node; the meaning is that we add $\delta$ to the key of all descendants of that node. So the actual key value at a particular node is the key stored at that node, plus the sum of all $\delta$'s along the path to the root.

This makes it easy to shift over all intervals after $A$, by adding $\delta$ to $O(\log n)$ nodes chosen so that their descendants cover all the keys after $A$. It's also easy to adjust the lookup procedure to look up a value (the glb operation) and to find where to insert/delete a range.
> 2 votes

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


# Question
Title: Is there a non bruteforce apporach to solving a "synergistic knapsack"?
Sorry for making up a name for the thing, the main reason for posting this question is that I can't find out the name of the problem that i'm thinking about.

I was messing around with min/max DP stuff, and when looking at a knapsack problem I wondered if you could apply DP if each item affected the total value of the other items. For example:

given the input:

```
bag_size = 10,
item_list = [(4,2),(1,2),(10,9),(7,6)], // (value, weight)
synergy_list = [[0, 2, 0, 0],[1,0,1,1],[0,0,0,5],[1,1,0,0]] // increment to [1st, 2nd, 3rd, 4th]

(if you had items 1 and 2 in the bag the total value would be 8
 4 and 1 being the value of the first and second items
 2 and 1 the value of their synergy with each other)

```

I assume you cannot use DP productively due to each item possibly changing the result that would be cached in the standard knapsack, forcing the recomputation. Given that, is there any approach apart from brute force? And also is there a proper name for this type of problem?

Thanks!

# Answer
> 0 votes
TLDR: Transform the problem to a standard knapsack problem, then use a standard algorithm.

Assume that if an item A is paired with an item B to earn a discount based on synergy it may not also be paired with an item C or another B to earn an additional synergy.

1. Construct N(N+1)/2 synthetic items formed by all pairs A+B which have value as the sum of values and weight as the sum of weights adjusted by synergy discount.
2. Discard any synthetic items that have a synergy discount of zero, as they offer no benefit over the component items.
3. Adding this set to the original N types of item gives N(N+3)/2 total types of item, or roughy N-squared.
4. Search for dominance relations and remove superfluous items. For example, if an item X (original or synthetic) has higher value and equal or lower weight to an original item or any other synthetic item Y, Y is superfluous; it cannot appear in an optimal solution so may be discarded, simplifying the problem.
5. Use any knapsack algorithm, approximate or exact. The Big-O running time will be the same, just against a larger set of items N^2.
6. Some of the tested permutations may include unpaired original items A + B that could benefit from a synergy, but the synthetic combination AB will also be tried and yield the proper total weight.

Using the above transformation of the problem , you can use dynamic programming (DP) and benefit from its speed-optimality tradeoff.

NOTE: If the up-front assumption does not hold, you need to augment the list of synthetic items with more combinations, like triples, quadruples, etc, possibly making the problem incapable of being solved in a reasonable time. In that case, this transformation will not be useful.

---
Tags: algorithms, algorithm-analysis, knapsack-problems
---


# Question
Title: Does the Turing test have anything to do with Turing completeness or Turing machines?
I am studying Turing machines and Turing completeness and just remembered I saw something called the Turing test. It seems that the Turing test (from Wikipedia)

> is a test of a machine's ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human.

while Turing completeness and Turing machine are discussed in the context of the theory of computation. Is there a relationship between Turing complete and the Turing test?

I think they are completely separate topics, but I just want to be sure.

# Answer
> 38 votes
No, there is no relationship. The connection is that they are both based on concepts/work by Alan Turing, who was an early pioneer who made many advances.

# Answer
> 8 votes
The relationship exists. All of these were invented by Alan Turing. Alan Turing is the godfather of computer science who laid the solid foundations long before the first electronic computer has even been built. Naming these after him is giving the deserved respect for him, especially since all of these were actually invented by him. His name, again, was Alan Turing.

# Answer
> -3 votes
Negative. They have nothing to do with each other. The Turing test is a tool to assess a machine's ability to display intelligent behavior indistinguishable from that of a human.

There is nothing in the definition saying that the mentioned machine has to be a Turing machine, or that it has to be Turing complete. Nothing, even though any machine implementing an AI algorithm advanced enough to be reasonably expected to pass the Turing test would certainly have to be Turing complete.

All Turing machines are, by definition, Turing complete. All Turing completeness means is the ability to simulate a Turing machine. So, as you see, there isn't any relationship between them at all. Absolutely none whatsoever.

---
Tags: turing-machines, turing-completeness, turing-test
---


# Question
Title: How can a Machine Learning model predict this classification problem?
I am pretty new to ML and have a basic but fundamental question.

Let’s imagine we want to create a simple Sentiment Analysis model using Machine Learning not Deep Learning algorithms, so we need to have a set of handcrafted features for this classification problem.

Let's say we have 2 features (F1, F2) for each sentence and a target class consisting of 0 and 1 as positive and negative. So we have a bunch of sentences in a dataset like this:

Well, classification algorithms like SVM, LR, DT, and …. can be trained from the training set and learn the sentiment of each sentence from their features. They can also test themselves using the test set. Now the model is ready to predict the sentiment of any sentence out of the dataset. Till now, there is no problem and everything is clear to me.

My problem is when we want to give a new sentence to the model form outside the dataset. Obviously, when we give a sentence to the model, we don’t give any feature to the model. **So here is my question, how the model can predict the sentiment of the new sentence when it doesn’t know how to calculate each of the features?**

Should we define what is F1, and F2 in the model first? Should we define a function and for any new input sentence, call the function to calculate the proper value for each feature and then teach the model that the function outputs are equal to F1 and F2 in the dataset?

To make a long question short, let me give a clear instance. My new sentence is "She was overjoyed when saw my cat". I want to give this sentence to the model and obviously expect to see a predicted positive sentiment. This sentence is not in my dataset so there is no feature for it and the model has no idea about F1 and F2. On the other hand, my model learned to determine the sentiment of each sentence using F1 and F2. So back to my question, when I don't give new sentence features (F1, F2) to my model and don't specify any procedure to calculate the features for new inputs, how the model can predict the sentiment of my new sentences?

I would really appreciate your time.

# Answer
> 1 votes
Your premise is wrong. You are assuming we don't know how to compute the features on new sentences. But we do know.

We construct features so that we can compute the features on any sentence whatsoever (not just the ones in the training set). For instance, one feature might be "does the sentence contain the word 'not'?". That is clearly a feature that can be computed on any new sentence.

You might be reading an example in a textbook that omits mentioning how the features are computed, to keep the example simple and avoid mentioning details that are not important for the author's purposes. But if you use this in practice, the features will be known and can be computed on any sentence.

---
Tags: machine-learning, artificial-intelligence, natural-language-processing, classification, features
---


# Question
Title: Why is conjunctive normal form (CNF) "better" for SAT than disjunctive normal form (DNF)?
When hand-manipulating algebra DNF (sum of products) is easier than CNF (product of sums). Possibly because factoring is more difficult than expanding. So why is it the opposite for computational boolean algebra?

Perhaps one argument is that in CNF one can show that an expression is false by showing that one clause is false. But that is no different from showing that an expression is true by showing that one conjunction is true.

# Answer
One (serious) issue is that converting to DNF is *harder* than solving the SAT problem itself! E.g. you can see that:

$$ x\wedge y\ \vee\ x\wedge \neg z$$

has 2 solutions, $x=\top,\ y=\top$ and $x=\top,\ z=\bot$, without doing any fancy work.

This means that converting into DNF is going to be tough, as opposed to CNF for which there are efficient algorithms. Note that in the CNF conversion, the result is not strictly *equivalent* but merely *equisatisfiable*, which is all that SAT solvers care about.
> 2 votes

---
Tags: satisfiability, boolean-algebra
---


# Question
Title: Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem
The following problem statement is given: Let $S = \\{s\_1, s\_2, \cdots, s\_n\\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s\_i$ for every $i$ between $1$ and $n$. The goal is to find a subset of $S$ whose sum is maximum, subject to the constraint that the sum must be $\le K$. Write an approximation algorithm which computes a sum which is at least half of the optimal solution on any given input. This algorithm must run in $O(n)$ time-complexity and $O(1)$ space-complexity.

I've been searching for some simple algorithm to satisfy these conditions and the closest I've come to is this, but since it makes use of sorting, the time-complexity is brought to $O(n\log n)$.

This is taken from a set of exercises given by my uni professor as preparation for the final exam. To be honest, I am not sure whether it is his original work or not, so I don't have any relevant reference to provide.

# Answer
> 3 votes
The idea is to set $K/2$ as the target.

* If there is any given number that is at least $K/2$, just return it.
* Otherwise, all given numbers are $\<K/2$.
    + If the sum of all given numbers is $\le K$, return the sum, which is the optimal solution.
    + Otherwise the sum of all given numbers is $\>K$.
    Let $prefix\\\_sum$ be $0$ initially. We will try adding all given numbers one by one to $prefix\\\_sum$ until it is $\ge K/2$, at which moment it cannot be $\>K$ -- otherwise the last number added must be $\>K/2$. Return it.

---

Here is an algorithm that implements the idea concisely. It runs in $O(n)$ time and $O(1)$ space.

1. Let $prefix\\\_sum = 0$.
2. For $i$ from $1$ to $n$:
    1. If $s\_i\ge K/2$, return $s\_i$. Else add $s\_i$ to $prefix\\\_sum$.
    2. If $prefix\\\_sum\ge K/2$, return $prefix\\\_sum$.
3. Return $prefix\\\_sum$.

---
Tags: algorithms, approximation, greedy-algorithms, subset-sum
---


# Question
Title: Algorithm design: Model redundancy in tests
I've run across an interesting problem at work that I'm not quite sure how to grapple.

Broadly, there is a suite of of $n$ tests to ensure the quality of a product. However, the tests are both time-intensive and frequently run so it's necessary to tradeoff confidence for performance.

### Approach 1: knapsack

For any test $x\_i$, let $t\_i$ represent the time it takes to execute. If we can define some measure of the "quality" of a test, $q\_i$, we can find the subset of tests that maximize $\sum q\_i$ while $\sum t\_i \leq T$ where $T$ is some time limit. Though, unlike $t\_i$, $q\_i$ is difficult to measure or even define. Perhaps $q\_i$ is a correlation between $x\_i$ passing and the whole suite passing? Or manually set to reflect the "importance" of a test? This doesn't feel right since the magnitudes of $q\_i$ sharply affect the outcomes. The better estimate of $q\_i$ would be rank-based.

### Approach 2: probability

If a single test fails, the whole test run fails and can abort preemptively. Forgive an abuse of notation and let $\bar{x\_i}$ represent the event test i fails. We can consider finding the permutation $j\_1, j\_2, \dots, j\_n$ such that $j\_1 = \max\_i P(\bar{x\_i})$ and $j\_2 = max\_i P(\bar{x\_i}|x\_{j\_1})$ and so on. Then, I could truncate the test suite to run the first $m$ tests $x\_{j\_1}, x\_{j\_2}, \dots, x\_{j\_m}$. Factoring in the time of the tests and improving on the greedy method could be later adjustments.

### Approach 3: boolean witchcraft

Suppose there was a latent set of boolean variables $I\_1, I\_2, \dots, I\_m$ that fully described the system and its test performance. (I imagine this to correspond roughly whether or not certain subcomponents of the system are correct). Then each test $x\_i$ could be understood as a boolean formula over those latent variables. Using historical data, we could try to reconstruct the most likely formulas and remove the tests that are "covered" by other tests e.g. if $x\_3$ passes when $x\_1$ passes AND $x\_4$ passes, it can simply be removed. There are a couple worries I have with this approach. One, that beginning assumption was a strong one -- how do I pick $m$? Too large and the system is barely constrained; too small and the formulas barely predict the data. It feels like it requires the same divine revelation involved in picking the number of clusters in clustering. Two, **how does one find the most likely boolean formulas**, anyhow? Probably not by iterating over all ${2^{2^m}}$ possibilities, right?

### Approach 4: clustering

Speaking of clustering, maybe something could work with the same subcomponents mental model as above. If we have $k$ historical test suite runs, we have a $k$-length vector $d\_i$ which describes the test's historical results. One approach could be to cluster these vectors and only test tests closest to the $m$ centers. Again, there's a lot of faith with the $m$ parameter plus there's very little nuance to tune here.

### Approach 5: principal analysis

Hey, if we have the vectors, why stop there? Together, they form a $k \times n$ data matrix $D$ and that reduces this to the trivial problem of feature selection. This post mentions some nice ways to extract high variance-explaining tests using some variants of PCA. The downside here is I'm abandoning the discrete structure of the problem and getting pretty deep in the weeds.

---

If anyone has wisdom into choosing between these approaches, fleshing them out, or suggesting a different one altogether, I'm all ears. This has been a fun jaunt in algorithm design, but I would like to implement something useful at the end of the day as well (:

# Answer
> 0 votes
# Theoretical perspective

One reasonable approach is to sort tests by $t/p$, where $t$ is the time to execute the test and $p$ is the probability the test fails. One can prove that if tests fail independently, then there is a sense in which this algorithm is optimal; see What is the optimal strategy for filtering a large collection of items with multiple filter functions?, Determine what is the best order for running filters on a dataset.

# Caveats

In practice, it might be difficult to estimate $p$, the probability of a test failing, for the reasons articulated by Yves Daoust. So it might be hard to do much better than setting $p$ to be the same for all tests; or, the effort to track the number of times that the test has failed in the past might not be worth the extra effort.

In practice, tests may not be independent, so this model may not be accurate and this schedule may not be optimal. However, characterizing the correlations between tests sounds complex to me, so the simple solution above might be a reasonable pragmatic choice.

# Pragmatic perspective

Overall, in practice, it is not clear whether any sophisticated strategy is going to do sufficiently better than just running the tests in a random order that it is worth the extra implementation complexity to implement the sophisticated strategy.

---
Tags: algorithms, algorithm-design, software-testing, features, boolean-complexity
---


# Question
Title: Finding a minimum cut with an upper bound on the set sizes
In the (unweighted) minimum k-cut problem, the goal is to partition the nodes in a given graph to at least $k$ subsets, such that the number of edges between different subsets is as small as possible.

I am interested in a variant in which the number of subsets is not fixed in advance, but there can be at most $t$ vertices in each subset. So the goal is to partition the nodes into subsets of cardinality at most $t$, such that the number of edges between different subsets is as small as possible.

Is there a polynomial-time algorithm for this problem, assuming $t$ is fixed? And assuming $t$ is part of the input?

# Answer
> 4 votes
The problem is called Component Order edge-Connectivity. The *edge* here refers to deletion of edges. See e.g. Gross et al..

The problem is defined as follows. Given an undirected graph $G = (V, E)$ and two integers $k$ and $\ell$, is it possible to delete at most $k$ edges from $G$ such that in the resulting graph, each connected component has at most $\ell$ vertices.

The problem is related to the vulnerability measure *Edge Integrity*, where you minimize the sum of the largest connected component and the size of the cuts. See e.g. the survey by Bagga et al..

---
Tags: graphs, reference-request, minimum-cuts
---


# Question
Title: can you read and push different symbols in a DPDA?
I have an easy question about the DPDA. Could you read an input and push a different symbol to the stack.

An example would be A transition from q1 to q2 where read input is v pop is epsilon(empty string) and push is x Both v and x are symbols

# Answer
> 1 votes
If you mean, you can push a symbol different from what your machine has read from the input, then yes you can. The input and stack symbols are not related and there is no rule that requires them to be the same (see the formal definition here). Most of the time you would see examples where the same symbol is read and pushed just for convenience. You can even have the set of input and stack symbols to be disjoint.

---
Tags: pushdown-automata
---


# Question
Title: what is the background theory that Z3 uses to prove constraints unsat
The method to get the sat result is kind of straightforward, you can use some search algorithms like heuristic search to get a solution. But how does z3 get the unsat result like x \< 2 && x \> 2

I searched for some articles related to z3 but didn't don't know how. I would be very grateful if someone could give me the answer or recommend me relevant information

# Answer
There are basically two components: the underlying SAT solver procedure (DPLL), and the additional theory-specific procedures.

* For the underlying SAT solver: considering your example of `x < 2 && x > 2`, when viewed as a SAT formula this is just $p \land q$. The SAT solver will determine from this that both $p$ and $q$ have to be true.
* For the additional piece: once the SAT solver has done its job, the SMT solver has a set of constraints $p = $`x < 2` and $q = $`x > 2` that have been accumulated by the SAT solver, that it needs to satisfy. It runs a procedure to collect all these constraints and determine whether they are (i) unsatisfiable or (ii) satisfiable. (This step is specific to the theory that is recognized: so we would apply a different procedure to deal with `<` constraints, or something like a polynomial with `+` and `*`, or something like lists or strings; each gets its own procedure.)

In your example, of course we could directly see that the set of constraints `x < 2` and `x > 2` contains a contradictory pair of bounds on the same variable; we could even check for this directly in a preprocessing step. But the more general case would apply a solver for a theory known as linear real arithmetic or use the simplex algorithm. The basic idea is to translate all the constraints into a matrix form, such as for your example: $$ \begin{bmatrix}-1 \\1\end{bmatrix} \[x\] \> \begin{bmatrix}-2 \\2\end{bmatrix} $$ we can even simplify this further, by adding additional variables like $y$ for the difference between $x$ and $2$, to replace our inequality \> with an equality =, and end up with a matrix equation of the form $$ A\vec{v} = b \text{ subject to } \vec{v} \ge 0 $$

The simplex algorithm continues from here, using techniques from linear algebra to determine whether there exists a solution vector $\vec{v}$ or not. If so, the original formula is satisfiable, and we plug in the resulting satisfying assignment to see if it's a solution. If not, it's unsatisfiable and we return back to the SAT solver to continue trying any other possible assignments.
> 4 votes

# Answer
You are asking about satisfiability modulo theories (SMT). There are similar algorithmic approaches there, and you can refer to Wikipedia for more.

In particular, you can have a look at DPLL(T) which is what z3 uses.
> 2 votes

---
Tags: constraint-satisfaction
---


# Question
Title: Try to proof halting problem on a special TM
Hey guys,

Got a tricky question here. I need to determine if this TM will ever halt on a empty word "". Seems like it will halt but I can't proof it. Can anyone help?

# Answer
The usual way how you would prove that a TM halts on a given input is to write out its computation (ie what is the relevant content of the tape, and what is the current state, for each time step) culminating in it halting. It is possible to design a TM that will halt, and where there is a short proof that it will halt, but the computation is so long that writing it out would be infeasible, but that is going to be a rare situation.

I've not actually worked it out carefully, but it seems that this particular TM will actually never halt. My impression is that the TM will generate an increasing area of $1$s around the initial position, cycling back and forth between growing left and growing right. The transition from $q\_3$ to $q\_5$ should never be taken (and neither should the transition from $q\_1$ to $q\_3$).
> 0 votes

# Answer
The usual way to prove that a particular machine will never halt is to follow the first steps, long enough until you can find a pattern, and then prove by induction that the pattern will repeat. Maybe you can find something like "after 119 steps, and after 250 steps, the TM is in a state with a property X, and this seems to repeat, and I can prove that when the TM is in a state with property X then it will move to a state with property X again, without halting in between". Arno gave a suggestion what the property X would be for this particular TM.

There will be TMs behaving in a way that is "chaotic" enough so you cannot find such a pattern, or there might be a pattern that is too complicated for you to find.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Why is computing $e^x$ faster than computing $2^x$?
Here is a very closely related, but NOT a duplicate question.

One time, I decided to test how long it takes to compute $2^x$ compared to $e^x$ in Python. I expected $2^x$ to be faster as in binary, the base computers use, you can just append 0 to the number 1 $x$ times. I entered into Python IDLE (Python's Integrated Development and Learning Environment):

```
>>> import timeit
>>> timeit.timeit('2**100')
>>> 0.24405850004404783
>>> timeit.timeit('e**100','e=2.718281828459045')
>>> 0.10122330003650859

```

and found that $e^x$ was about twice as fast to compute, despite not being an integer. Why does this happen? (Note that this only happens for large numbers.) The only reason I can think of is that $e^x$ can be easily calculated using a MacLaurin series as $\frac d{dx} e^x$ is equal to $e^x$.

# Answer
You are not comparing the same operations. You are comparing two operations that look very similar in source code, but they are very much different.

`2**100` takes an integer 2, and calculates that integer raised to the 100th power using unlimited precision integer arithmetic. If you tried 2\*1000000 you would get a number with about 300,000 digits containing the *exact* value of `2**100`.

`e**100` with e = 2.718281828459045 takes a floating-point number and raises it to the 100th power using limited floating-point precision. This will not give you more than about 15 digits precision and will fail with overflow when the exponent is about 800 or so. It is a total different operation. So obviously takes a very different amount of time.
> 3 votes

# Answer
The reason is simple: `2**100` returns a bignum, with full accuracy. There is more work to handle the bignum representation than mere binary shifts. On the opposite, `e**100` returns a float and uses the built-in power function of the processor.

```
>>> from timeit import timeit
>>> timeit('2**100')
0.20831729998462833
>>> timeit('2.0**100')
0.008533199987141415
>>> timeit('2.718281828459045**100')
0.008684300002641976
>>> timeit('e**100', 'e=2.718281828459045')
0.10991410000133328
>>> timeit('e**100', 'from math import e')
0.10929809999652207

```
> 5 votes

---
Tags: time-complexity
---


# Question
Title: Greedy algorithm for postive interval covering
Consider the following problem from Jeff Erickson: *Algorithms* that also appears in this post, which wants us to prove a lower bound for the problem.

> Suppose you are given an array $A\[1 .. n\]$ of integers, each of which may be positive, negative, or zero. A contiguous subarray $A\[i .. j\]$ is called a *positive interval* if the sum of its entries is greater than zero. Describe and analyze an algorithm to compute the minimum number of positive intervals that cover every positive entry in $A$. For example, given the following array as input, your algorithm should output $3$. If every entry in the input array is negative, your algorithm should output $0$.
> $${+}3\ {-}5\ {+}7\ {-}4\ {+}1\ {-}8\ {+}3\ {-}7\ {+}5\ {-}9\ {+}5\ {-}2\ {+}4$$

My question is, is there a greedy approach for this problem?

I have an idea, find the largest positive number, then according to whether there is some positive numbers in each side, go left or right to cover more positive number. But I think this idea doesn't work.

# Answer
> 1 votes
There is a simple greedy algorithm.

### A greedy approach

The greedy idea is obvious: starting from the very left, **extend the coverage to the right as far as possible each time**.

However, it may not be obvious to get it right. We should search each next positive interval by the following two criteria:

1. It should cover **the next uncovered positive entry**.
2. It should cover **as many entries as possible after that entry** among all positive intervals that covers that entry.

To boost performance, after the next $u$ncovered positive entry $A\[u\]$ is found, we will **find the optimal start** of the positive interval to cover $A\[u\]$ and the most entries after $A\[u\]$. That optimal start is an entry such that the sum of entries between it and $A\[u\]$ is the largest. In fact, that optimal start can be ignored; knowing that largest sum is enough.

Let $\text{sum}(A\[i..j\])=A\[i\]+A\[i+1\]+\cdots+A\[j\]$, the sum of entries in $A\[i..j\]$.

Here is the greedy algorithm.

$u\leftarrow0.$ $\ rightmost\leftarrow0.$ $\ answer\leftarrow 0.$ Repeat the following $3$ steps.

1. $u\leftarrow$ the least index greater than $rightmost$ at which the entry of $A$ is positive.
If there is no such index, return $answer$.
Otherwise, $answer\leftarrow answer+1$. We will cover $A\[u\]\>0$ and as many entries as possible after it with one positive interval.
2. $surplus\leftarrow$ the largest sum among $\text{sum}(A\[u..u\])$, $\text{sum}(A\[u-1..u\])$, $\cdots$, $\text{sum}(A\[1..u\])$.
For the sake of correctness proof, let $start$ be the corresponding starting index of $surplus$, which is the optimal start of the desired positive interval.
3. $rightmost\leftarrow$ the largest index $k$ such that $ surplus+\text{sum}(A\[u+1..k\])\>0$, where $u+1\le k\le n$. If there is no such index, $rightmost\leftarrow u$.
Conceptually, we select the positive interval $A\[start, rightmost\]$.

#### Complexity Analysis

Each one of step 1, 2 and 3 takes $O(n)$ time.

$u$ starts at $0$ and ends at most $n$. Since $u\le n$ always increases at step 1 unless the algorithm returns, step 1 and hence the whole loop body of step 1, 2, 3 can repeat at most $n$ times. Hence the whole algorithm takes $O(n^2)$ time.

The post here optimizes the approach above to run in $O(n)$ time.

#### Correctness proof

Let $A\[s\_1..r\_1\], A\[s\_2..r\_2\], \cdots$ be the positive intervals selected successively by the greedy algorithm. So $r\_1\<r\_2\<\cdots$.
Let $A\[s\_1'..r\_1'\], A\[s\_2'..r\_2'\], \cdots$ be some positive intervals that covers all positive entries in $A$. WLOG, assume $r\_1'\<r\_2'\<\cdots$.

Let $s\_0=r\_0=s\_0'=r\_0'=0$.

It is enough to prove the greedy algorithm "stays ahead", i.e., $r\_i\ge r\_i'$ for all $i$.

The case $i=0$ is trivial. Suppose $r\_i\ge r\_i'$ for some $i$.

Let $u$ and $start=s\_{i+1}$ be the values found in the step 1 and 2 of the algorithm that leads to the selected interval $A\[s\_{i+1}..r\_{i+1}\]$, i.e., $A\[u\]$ is the positive entry after $A\[r\_i\]$ and $\text{sum}(A\[start..u\])$ is the largest among $\text{sum}(A\[\*..u\])$.

Since $r\_i'\le r\_i\<u$, $A\[u\]$ is not covered by any interval $A\[s\_j'.. r\_j'\]$, $1\le j\le i$. Hence $A\[u\]$ is in some $A\[s\_k'..r\_k'\]$, where $k\ge i+1$. $$ \text{sum}(A\[u+1..r\_k'\])=\text{sum}(A\[s\_k'..r\_k'\])-\text{sum}(A\[s\_k'..u\])\>0-\text{sum}(A\[start..u\])$$ By the step $3$ of the algorithm, the inequality above implies $r\_{i+1}\ge r\_k'$. Hence $r\_{i+1}\ge r\_k'\ge r\_{i+1}'$.

#### A Python implementation

While the indices above start with $1$, they start with $0$ in the implementation.

```
from itertools import accumulate

def minimum_cover(a):
    n = len(a)
    answer = 0
    rightmost = -1
    while True:
        uncovered = rightmost + 1
        while uncovered < n and a[uncovered] <= 0:
            uncovered += 1
        if uncovered == n:
            break
        surplus = max(accumulate(a[uncovered::-1]))
        new_rightmost = uncovered + 1 + max(
            (idx for idx, sm in enumerate(accumulate(a[uncovered + 1:n]))
             if surplus + sm > 0), default=-1)
        if new_rightmost > rightmost:
            rightmost = new_rightmost
            answer += 1
    return answer

print(minimum_cover([1, 7, -9, 2, -10, -5, 5, -10, 4, -2, 3, -1, 2]))  # 2
print(minimum_cover([1, -3, 3, -2, 1, -2, 1]))  # 2

```

# Answer
> 1 votes
The accepted greedy solution doesn't work.

I don't think there is a greedy algorithm. There is a counterexample to the other solution, where they use the heuristic of adding the largest positive interval starting at the current positive integer.

Consider the counterexample:

```
[1, -10, 10, -8, 3, -6, 4, -10, 8]

```

The proposed greedy algorithm will cover the array with 3 intervals:

```
(1, -10, 10) (3, -6, 4) (8)

```

But the array can be optimally covered with just 2 intervals:

```
(1) (10, -8, 3, -6, 4, -10, 8)

```

# Answer
> 0 votes
When we have an array like this: \[1, -6, 5, -100, 101, -8, 3, -6, 4, -90, 8\],

and apply the above greedy algorithm to it, the outcome is 2

However, I think that the correct answer should be 3.

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


# Question
Title: Why does Python behave so absurdly when dealing with numbers with decimal points?
r1 and r2 both are assigned 0.05 initially. If r1 is incremented by 0.01 in this way "r1 = r1 +0.01" we have 0.060000000000000005 as answer not 0.06.

# Answer
This is the foundation of computer arithmetic, when dealing with fractional values. (https://en.wikipedia.org/wiki/Floating-point\_arithmetic.)

The key reason is that numbers are represented in the binary base rather than decimal. Though $0.06$ is a short number in your world, it cannot be represented exactly by a computer.

But there is nothing shocking: try and expand $1/3$ in the decimal notation, and tell us when you are done... :-)

---

The next topic to know about is "rounding": https://en.wikipedia.org/wiki/Rounding.
> 4 votes

# Answer
As @gnashed729 remarks, this is how floating-point arithmetic works, and it is not specific to Python.

It is all clearly explained in the Python manual:

* Python (like most programming languages) interprets a number such as `0.3` as a floating-point number, using the computer's built-in support for floating-point arithmetic, if present;
* computers represent floating-point number as binary fractions, not decimal fractions;
* decimal fractions cannot be represented exactly as binary fractions; for instance, `0.1` (decimal) is `0.0001100110011001100110011001100110011001100110011...` (binary) (this example is from the Python manual);
* as a consequence, you already have a rounding error once you write the number `0.3` down; more rounding errors will occur once you start to do arithmetic with these numbers.

To calculate with exact decimal fractions, you may want to use the `decimal` module.
> 3 votes

---
Tags: memory-management, python, data-types
---


# Question
Title: If NP problems are decidable, and decidable is subset of turning recognizable which recognizer can understand them?
I think the best way to explain my question would be to have sextuple (regular, context-free, Turing-recognisable, decidable, P, NP).were you fill out 1 for promblem which lies into that section, would an np problem such as chess be only 1 for NP or would also fall in decidable?

Some other examples: The regular problem would be (1,1,1,1,1,1) as regular is a subset of CF,TR, Decidable which runs in P time and NP is a subset of NP.

Another example, a context-free language would be (0,1,1,1,1,1).

and I assume chess would be (0,0,1,1,0,1)

So my question is would my assumption on NP problems be correct as some decider has to recognize them?

# Answer
Yes, this is correct, due to the computational equivalence of nondeterministic turing machines to deterministic ones. You can try all possible certificates in exponential time.
> 0 votes

---
Tags: complexity-theory, time-complexity, turing-machines
---


# Question
Title: Why is the heap data structure called 'heap'?
The term "heap" has majorly two meanings in computer science -

1. The "heap" memory in the context of memory management.
2. The "heap" data structure as the representation of a priority tree as an array.

I can understand the use of the word "heap" in the context of memory as it correlates to the literal meaning of the word.

However, the use of the word "heap" for an array representation of a tree is not obvious to me.

Although I have never come across any explanation for using this word in any textbooks or lectures, it would be interesting if someone here could present an explanation for the usage, ideally with citations to resources.

# Answer
It seems that the use of *heap* to denote a priority queue implemented as an implicit binary tree was first introduced in the original Heapsort article: Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348.

A well-known chatbot gives the following explanation: "Williams chose to call this data structure a "heap" because of its resemblance to a heap of pebbles or stones, with the largest or smallest stone at the top, depending on the type of heap." Unfortunately, no reference substantiates that.
> 3 votes

# Answer
In the book *The Algorithm Design Manual$^{\[1\]}$*, the author writes:

> Power in any hierarchically structured organization is reflected by a tree, where each node in the tree represents a person, and edge $(x, y)$ implies that $x$ directly supervises (or dominates) $y$. *The person at the root sits at the “top of the heap.”*

Then in the next paragraph, he continues:

> In this spirit, a *heap-labeled tree* is defined to be a binary tree such that the key of each node dominates the keys of its children. In a *min-heap*, a node dominates its children by having a smaller key than they do, while in a *max-heap* parent nodes dominate by being bigger.

Therefore, I think we can draw the conclusion that, in the *heap* data structure, the notion of heap is used to represent some number of items that we don't necessarily care about as our primary goals are to *insert* and *extract-min/max*.

---

$\[1\]$ Skiena, S.S. (2020). Sorting. In: The Algorithm Design Manual. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-030-54256-6\_4
> 1 votes

# Answer
There's nothing to explain. It's just a name. Instead of "heap", the name could have been "giraffe" or "hxfq" or anything else. A rose by any other name is still a rose.

The definition of a heap data structure is found in standard references, e.g., https://en.wikipedia.org/wiki/Heap\_(data\_structure).
> -1 votes

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


# Question
Title: Can all NP-complete problems be reduced to NP?
I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around?

Can all NP-Complete be reduced to NP problems?

My understanding is that it cannot be done, since that would mean that both are equally complex, therefore NP=NP-Complete.

But the answer to this post seems to point into this direction: Can an NP-Complete problem be reduced to an NP problem?

# Answer
Your answer is basically correct. As Arno says, your confusion arises from not being careful with quantifiers. There are two possible versions of the question, and neither you nor the user in the linked thread made it very clear which one is the intended one.

Version 1: "Given an NP-complete problem A, *does there exist* an NP problem B such that A can be reduced to B?" This is trivially true because you can simply choose B = A.

Version 2: "Given an NP-complete problem A, can A be reduced to *every* NP problem B? If this were true, it would - as you already noticed - imply that NP = NP-C
> 1 votes

# Answer
> I know that by definition, all NP problems can be reduced to NP-Complete problems.

This is wrong.

The definition of NP-complete is as follows:

> If a problem is NP *and* all other NP problems are polynomial-time reducible to it, the problem is NP-complete.

By this definition, each NP-complete problem is also an NP problem. But whether NP = NP-complete is unknown. That is, we do not know whether each NP problem is also an NP-complete problem.
> 0 votes

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


# Question
Title: How to find the maximum size of a B+ tree?
I came across this paper (page 16) which explains how to calculate the size of B+ trees.

According to it the maximum number of nodes at level $i$ is $2(n/2)^{i-1}$ for a B+ tree of order $n$. Thus a B+ tree of $l$ levels will contain at most $\sum\_{i=0}^{l} 2(n/2)^{i-1}$ nodes (\*).

But we also know that for example for a B+ tree which stores $N$ records there're at most $\frac{N}{\lceil n/2 \rceil-1}$ leaves (\**).

The height of a B+ tree can be calculated by this formula: $\lceil \log\_{\lceil n/2 \rceil}N \rceil$.

But then the formulas * and \** contradict each other. For example a B+ tree has $1024$ records and is of order $16$. The depth of the tree will be $4$.

According to \** there're at most $146$ leaves in the tree.

But according to * there're at most $2\cdot 8^3=1024$ nodes at level $4$ which is where the leaves are.

Please help me understand where this contradiction is coming from and what is the correct way to calculate the max size of B+ tree.

# Answer
1. Compute the size of nodes A, B of the following tree
> -1 votes

---
Tags: data-structures, trees
---


# Question
Title: Languages: Prove or Disprove that $A^* = B^* \rightarrow A=B$
A colleague and I with pretty low-grade practical backgrounds decided it's time to try learning theory. This question is asked in a slide-deck he tracked down somewhere or another online without an answer to go with it. We're both leaning towards a simple disproof by Counter-Example:
$A = \\{a,b\\}$
$B = \\{ab,a,b\\}$
But we aren't sure if alphabets are "allowed" to contain redundancies like the one in B. Any quick guidance from the community?

# Answer
> 1 votes
If $A$ and $B$ are indeed meant to be alphabets here, they would contain only symbols, and your counterexample isn't valid. In fact, if $A$ and $B$ are alphabets, the claim is true.

However, I would rather expect $A$ and $B$ to be formal languages here, in which case you have found a perfectly reasonable counterexample.

---
Tags: formal-languages, kleene-star
---


# Question
Title: Why is backpatching needed during intermediate code generation? For what purposes?
I understand *how* backpatching works during intermediate code generation, but I do not understand *why* it is needed.

A common argument for using backpatching during intermediate code generation is as follows:

Suppose the intermediate code generated is:

```
goto L1

...

L1:

```

When `goto L1` is generated, the *actual address* of the target of `goto` is unknown. So we use a label `L1` as a placeholder. When the code `L1:` is generated, we can backpatch the address where `L1:` is to `goto L1`.

However, why should we use the actual address for `L1` during intermediate code generation? For example, LLVM IR uses symbolic labels in `branch` instructions instead of their actual addresses.

Even the RISC-V assembly language, which is often used as a targe language during targe code generation, uses symbolic labels in `jump` instructions. Isn't it the job of an assembler to replace labels with actual addresses?

---

The related post does not address my concerns above.

# Answer
> 12 votes
In the case of LLVM IR, I think the point here is not backpatching an *address*, but backpatching a *label*. If the label is "created" at the point where it is in the code, any forward jumps to it will have to be backpatched.

There are other ways to define an API for building IRs, but this works.

Backpatching *addresses* is the job of an assembler, however some compilers compile directly to machine language, not going through an assembler. This is true of LLVM, which can be used as a JIT compiler where calling out to an assembler would hinder performance.

Contrary to what the other answer says, the CPU typically doesn't want an *address*. Most CPUs do provide a way to jump to an address, but more commonly, it is more efficient to jump to a *relative offset*, i.e. the difference between the address of the jump instruction and the address of the target. Not only is the code sequence shorter, it is more position-independent.

Some CPUs have "long" and "short" jump instructions, where the "short" version will only let you jump less than 128 bytes away in either direction (give or take), but the short instruction is one byte shorter. Because the short instruction is shorter, this means that whether or not you can use a "short" jump may depend on whether or not any jump instructions between the jump and its target are "short" or not.

If the the goal is to minimise the final binary size, the general case of this problem is known to be NP-complete.

For some classic algorithms to solve this, see:

# Answer
> 2 votes
When emitting textual assembly code, backpatching is not strictly necessary, as long as you can predict what the label of a destination is going to be even if that destination is in the future.

There are different ways to make that happen, such as numbering your basic blocks, or doing code generation from your AST or directly in the parser (as done in Compiler design in C by Allen Holub).

# Answer
> 1 votes
I realize that Java bytecode uses (absolute/relative) address offset instead of (symbolic) labels in its jumping instructions such as `goto`. Then I know that backpatching is indeed useful during intermediate code generation. (`javac` uses backpatching.)

# Answer
> 0 votes
One thing I do during compilers I've written is backpatching for recursive closures (in ML syntax):

```
let c = 333 in
let rec f1 x = f2 (x - c)
    and f2 x = f1 (x - c)
in
  f1 3

```

This compiles down into something like:

```
f1 = make_closure(c, f2 <-- f2 doesn't exist yet, so this is a placeholder)
f2 = make_closure(c, f1)
backpatch(f1, f2)

```

Since the functions call each other, you have to delay when you fill in the closure struct, so you emit placeholders and backpatch later.

# Answer
> 0 votes
I don't think you'd ever have to backpatch a control flow address in intermediate code, where you'd at best have abstract labels. One of the reasons we have intermediate code is not to have to do irrelevant low-level things like that in the compiler.

However, we can generalize. Intermediate code may be processed such that various calculated attributes can flow in any direction among the nodes of the program. When they flow in a backwards direction, then that is backpatching.

In a tree/DAG representation of a program, there can be attributes that flow right to left.

For instance, classic example: Pascal-style declarations: `VAR a, b, c : INTEGER`. We might parse this roughly from left to right, seeing the declared `a`, `b` and `c` identifiers first. Then, the type attribute has to flow backwards from the `INTEGER` type to those nodes. That's a sort of backpatching.

Or C structures:

```
struct node {
  struct node *left, *right;
};

```

When `struct node` appears, it has to be introduced as an incomplete type node. Then when the definition is parsed, the type node is backpatched with information about the member types, and flipped to completed state.

When we divide intermediate code into basic blocks, something like batchpatching can take place. Say that we want the basic blocks to be objects which have direct references to other basic blocks (like the ones they jump to). For that, we must resolve the labels. We can do two passes whereby we build up, say, a hash which maps labels to basic blocks, and associates basic blocks with lists of adjacent labels. Then we replace those adjacent labels with blocks references from the hash.

# Answer
> -1 votes
The CPU wants an actual address.

---
Tags: compilers, code-generation, risc-v
---


# Question
Title: Red-blue orthogonal line intersection algorithm
I need to efficiently find the intersections between a set of vertical line segments and a set of horizontal ones. The segments in both families can overlap (but there are no duplicates). Presumably this is done in time $O(n\log n+k)$ for $n$ segments and $k$ intersections.

Can someone describe an ad-hoc solution or provide a reference ?

# Answer
The ad-hoc algorithm for the problem with $m$ horizontal and $n$ vertical line segments might be the following one:

**Step 1**. Project beginning and ending points of all segments on the $OX$ axis and create an array of ***events***, corresponding to $x$-coordinates of these points. Each event consists of three components - the point $x$-coordinate, a pointer to the segment it belongs to, and the event ***type*** from the set {"*beginning of horizontal segment*", "*ending of horizontal segment*", "*vertical segment*"}. The size of this array is $2m+n$. Sort this array by the $x$-coordinate of events (for simplicity we'll assume that all the $x$-coordinates are unique).

**Step 2**. Sweep the set of segments from left to right using the array of events, created earlier. Each step of the sweeping loop will update or use the ***status*** $S$. This status is simply a set of horizontal segments, ordered by their $y$-coordinate, and it can be represented by any type of balanced binary tree. The status is initially empty, and its size never exceeds $m$. Actions, taken on each step of the sweeping loop, depend on the current event type:

* "*beginning of horizontal segment*" - add this segment to the status $S$.
* "*ending of horizontal segment*" - remove this segment from the status $S$.
* "*vertical segment*" - make two binary searches in the status $S$, using two $y$-coordinates ($y\_{min}$ and $y\_{max}$) of this segment, and find the range of horizontal segments, intersecting this vertical segment. Calculate intersection points for all segments in this range.

As you can see, this algorithm doesn't need any complex geometric data structures (segment tree etc.).
> 0 votes

---
Tags: computational-geometry
---