# Question
Title: Why can $2$-SAT be solvable efficiently, but $3$-SAT not?
I am aware that 2SAT is polynomial while 3SAT is not, but I am looking for an intuition why its so. After all, even in 2SAT we can attempt all possible truth functions and its $2^n$. So I am hoping not for a formal proof, but for intuition or explanations that distinguishes the language from 3SAT?

# Answer
> 5 votes
As was mentioned in a comment we can only say that 3SAT is NP-hard. In 2SAT you can take a variable $x$ and set it to true (or false). Then you can throw out any clauses where $x$ appears, or if a clause becomes unsatisfiable from previous assignments you know that $x$ cannot be true (or false). By proceeding in this manner we can efficiently obtain a satisfying formula or verify that the clauses are not all simultaneously satisfiable.

If you try to extend this intuition to 3SAT and set the truth value of $x$ then you will end up still having to check an exponential number of clauses before shrinking the problem size. This doesn't show that 3SAT is not polynomial-time solvable but it does show that the obvious approach for solving 2SAT fails when extended to 3SAT.

# Answer
> 2 votes
An algorithm running in time $2^n$ is extremely slow. Fortunately, there are better algorithms for solving 2SAT. Here is one such algorithm.

Suppose that $C\_1$ and $C\_2$ are two clauses (disjunctions of variables) such that $C\_1$ contains some variable $x$ and $C\_2$ contains its negation $\bar{x}$. Let $C$ be the clause formed by taking the disjunction of all other literals appearing in $C\_1$ and $C\_2$. For example, if $C\_1 = x \lor y$ and $C\_2 = \lnot x \lor z$, then $C = y \lor z$. The clause $C$ is known as the *resolvent* of $C\_1$ and $C\_2$; we say that it is obtained by applying the *Resolution rule* to $C\_1$ and $C\_2$. The resolvent satisfies the following property:

> If $C\_1$ and $C\_2$ hold, then so does $C$.

Indeed, write $C\_1 = x \lor \alpha$ and $C\_2 = \bar{x} \lor \beta$, where $\alpha,\beta$ are clauses. In these terms, $C = \alpha \lor \beta$. Suppose that $C\_1$ and $C\_2$ hold. If $x$ is true then $\beta$ holds, and if $x$ is false then $\alpha$ holds. In both cases, $C$ holds.

Consequently:

> If a set $\mathcal{C}$ of clauses is satisfiable and $C$ is the resolvent of $C\_1,C\_2 \in \mathcal{C}$, then the set $\mathcal{C} \cup \\{C\\}$ is also satisfiable.

For example, the CNF $(x \lor y) \land (\lnot x \lor z)$ is satisfiable, hence so is the CNF $(x \lor y) \land (\lnot x \lor z) \land (y \lor z)$.

The clauses $\alpha,\beta$ in the definition of the Resolution rule could be empty. If both are empty, then the resolvent is the empty clause, which is unsatisfiable. If we reach the empty clause after several applications of the Resolution rule, then we know that the original CNF was unsatisfiable. Conversely, it turns out that if the empty clause *cannot* be generated from a given CNF, then the CNF is satisfiable. This suggests the following algorithm, which gets as input a CNF in the form of a set of clauses $\mathcal{C}$:

> While there exist two clauses $C\_1,C\_2 \in \mathcal{C}$ which can be resolved and their resolvent doesn't already belong to $\mathcal{C}$, add their resolvent to $\mathcal{C}$. If the empty clause is eventually reached, output *unsatisfiable*. Else, output *satisfiable*.

For example, the CNF $(x \lor y) \land (\lnot x \lor z)$ is satisfiable, since after adding the resolvent $(y \lor z)$ there are no new clauses which can be generated. Conversely, if we start with the CNF $(x \lor y) \land (\lnot x \lor y) \land (z \lor \lnot y) \land (\lnot z \lor \lnot y)$, then we can resolve the first two clauses to get $y$, the other two clauses to get $\lnot y$, and then the two new clauses to get the empty clause; hence the CNF is unsatisfiable.

When applying this algorithm to a 2CNF, the clauses generated always have width at most 2 (that is, they are disjunctions of at most two literals). Since there are $O(n^2)$ many such clauses, where $n$ is the number of variables, the algorithm above stops within $O(n^2)$ iterations, and consequently, it runs in polynomial time.

This is no longer the case for 3CNFs — the width can increase. For example, the resolvent of $x \lor y \lor z$ and $\lnot x \lor u \lor v$ is $y \lor z \lor u \lor v$, whose width is 4. Intuitively, this is why the Resolution algorithm is not efficient for 3CNFs. Indeed, we can exhibit examples of unsatisfiable 3CNFs in which not matter how the algorithm is applied — no matter which two clauses are resolved in each step — it takes exponentially many steps to reach the empty clause. This result is part of an area known as *proof complexity*.

# Answer
> -3 votes
2SAT is NL-complete, so 2SAT is in P. 3SAT is NP-complete, so 3SAT is not in P assuming that P unequals NP.

---
Tags: satisfiability, 3-sat, 2-sat
---


# Question
Title: Can a software program be stored in just one memory cell?
I would define a software program as at least one line of code stored in at least one computer system's memory cell.

Can a software program be stored in just one memory cell or rather (due to binary computation) must it always be stored in two or more memory cells?

# Answer
It depends on the particular instruction set and model of computation, but in some architectures, here is a valid program:

EXIT

In other words, it is just one instruction, which immediately causes the program to halt. If that fits into a single memory cell (and it could; there's no reason in principle why it can't), then you've got a program that fits in one memory cell.
> 2 votes

# Answer
You can even store a software program in 0 memory cells!

All you need to do is to define a programming language in which the *empty program* has a defined meaning. For example, you can define a programming language that is just like Python, except the empty program prints the string `"Hello, World!"` to the console; let's call this programming language Python++.

Now you can store a Python++ "Hello, World" program in 0 memory cells.
> 1 votes

---
Tags: memory-management, memory-access
---


# Question
Title: How can I write 2^65 on my 64-bit computer?
This is possibly a very trivial question for this site.

If I have a 64-bit laptop that means 2^64 combinations in total are possible.

But I can even get $2^{(x\>\>\>64)}$ on my laptop.

Now, it is got to do something with the integer representation but I do not have enough background to understand it.

If let's say I had a 2-bit computer, 00 could represent 1, 01 could represent 1, 10 would represent 2, and 11 would represent 3. So that in total I had 2^2=4 numbers represented.

If somebody could show me how by using a kind of representation it is possible to represent a lot more numbers than 0,1,2,3 in this 2-bit computer I think would understand how it works for a 64-bit computer.

# Answer
> 2 votes
Dynamic arrays is a solution to this problem. Lets say you have `11` in binary or `3` in decimal and you want to add `1`. Your result would be `100` in binary and `4` in decimal. You can think of 3 and 1 like two "arrays" of bits and their result also like an "array" of bits. So take a look at the following image. You calculate the result till you fill the length of your "array" of bits. Once you fill it if the next digits is bigger than zero (assuming you keep them in a temporary array) you know that you have to allocate more memory, so you need to reserve more cells for the result "array" of bits.

Of course this is a super simple example.

There is a great library for C programming language that handles this kind of numbers. You can find out some examples here: https://home.cs.colorado.edu/~srirams/courses/csci2824-spr14/gmpTutorial.html

# Answer
> 0 votes
> If let's say I had a 2-bit computer, 00 could represent 1, 01 could represent 1, 10 would represent 2, and 11 would represent 3. So that in total I had 2^2=4 numbers represented.

Let's say you have a number system that uses 10 different symbols to represent numbers. Let's call these symbols `0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, and `9`.

This means that in total, you can represent 10 numbers.

> If somebody could show me how by using a kind of representation it is possible to represent a lot more numbers than 0,1,2,3 in this 2-bit computer I think would understand how it works for a 64-bit computer.

Do you understand how you can use only 10 symbols to represent an arbitrary amount of numbers of arbitrary size?

Well, you can use only 4 symbols, or only 2 symbols, or only 2^64 symbols, to represent an arbitrary amount of numbers of arbitrary size *in exactly the same way*.

Big number representation and arithmetic in computers works exactly the same as on paper. The only difference is that there are 2^64 "digits" instead of 10.

---
Tags: memory-management, memory-allocation, storage
---


title: Can't figure out decision variable

text:
# Question
Title: Can't figure out decision variable
Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to according LP.

So I have n goods which I have to ship using three cargo companies. the Paths P i,j is composed of segments of road 'e' and some of these segments can be blocked as you can read from the exercise.

What I am getting confused here is how to determine the decision variables and its constraints? should I select e.g. x for a single path or x for a single good? and y for segment? I have to minimize the overall number of segments as low as possible for a single path.

Any guidance and clearance regarding this formulation would be a great help!

# Answer
For each good $g\_i$ you have three binary variables $d\_{i,j}$: whether good $i$ it was delivered by truck 1, 2 or 3.

You make sure that exactly one truck takes the good: $b\_{i,1} + b\_{i,2} + b\_{i,3} = 1$

Now you want to minimize the sum of all segments multiplied by the obstructions. So you minimize $\sum\_{i, j} b\_{i,j} \cdot x $ where $x$ is constant one for obstructed road or constant zero for a good one.
> 1 votes

---
Tags: algorithms, linear-programming, integer-programming
---


# Question
Title: If Interpreters are used to run code and are written in another language, won't interpreters need interpreters?
As I was going through my online lectures, it is stated that python is interpreted with Cpython, a software written in C. Similarly, they have Jython (written in Java) and PyPy (written in Python). My question is is these interpreters break down the language into low level code like Assembly and machine code, then who helps interpret the software of these interpreters so that they run in the computer?

# Answer
> If Interpreters are used to run code and are written in another language, won't interpreters need interpreters?

Yes. Maybe. But mostly yes. Depending on how you look at it.

You need an interpreter to execute something. Period. There is no way around that. Even if you just read the source code and figure out the result by hand, you are interpreting the code in your head: *you* are the interpreter. For native machine code, the CPU is the interpreter.

You *cannot* execute code without interpreting it.

If you have a program written in some language **X**, and you want to know what the result of that program is, there are only two things you can do:

* Interpret the program with an interpreter for language **X**, or
* Compile the program with a compiler from **X** to **Y** to some other language **Y**, for which you have an interpreter.

Note that you can construct a longer chain if necessary: If you have a program written in **X**, and you have a compiler from **X** to **Y**, but no interpreter for **Y**, but instead you have an interpreter for **Z** and a compiler from **Y** to **Z**, you can

1. Compile the program from **X** to **Y**, then
2. Compile the program from **Y** to **Z**, then
3. Interpret the program using your **Z** interpreter.

Likewise, if you have a program written in **X**, and you have an interpreter for **X** written in **Y**, but no interpreter for **Y**, but instead you have an interpreter for **Y** written in **Z**, you can

1. Interpret the program using your interpreter for **X** running on …
2. your interpreter for **Y** running on …
3. your interpreter for **Z**.

# Two ways of implementing programming languages

Fundamentally, there are two ways of implementing a programming language: *compilation* and *interpretation*.

**tl;dr**: An interpreter *runs* the program, a compiler *translates* the program to another language.

> My question is is these interpreters break down the language into low level code like Assembly and machine code,

Interpreters don't "break down the language into low level code like Assembly and machine code". Interpreters *interpret* programs written in the programming language they are interpreting, i.e. they *run* the programs. They do not, in some way, produce another output program in something like assembly or machine code. That would be a *compiler*.

The fundamental difference between an interpreter and a compiler is that the interpreter *runs* the code (but never translates it), and a compiler *translates* the code (but never runs it).

Importantly, the fact that a compiler only translates the code but never runs it means that you *need* an interpreter to run the code. You *cannot* run code without an interpreter. It doesn't have to be an interpreter for the specific language your program is running in (you could compile it to some other language and then interpret *that*), but somewhere, sometime, at some point, ultimately, you need an interpreter.

> then who helps interpret the software of these interpreters so that they run in the computer?

Another interpreter.

If we take the example of Jython, it is an interpreter for Python written in Java. (It's actually more complicated than that, but this will suffice for the moment.)

The typical way how a Python program is executed using Jython is something like the following:

1. You feed the Python program to Jython. Jython then runs the Python program.
2. Oh, but Jython is written in Java! So, you need either an interpreter for Java, or you need to compile Jython to another language that you already have an interpreter for.
3. Typically, Jython is compiled to JVM bytecode using a Java compiler.
4. Oh, but now we need a Java compiler! Well, that's okay, we have one: `javac` ships as part of the JDK.
5. Well, now we have Jython in the form of JVM bytecode. But how do we run that? We need an interpreter for JVM bytecode!
6. Luckily, we have such an interpreter, it is called a Java Virtual Machine.
7. Oh, but wait! Our JVM is written in C++! We don't know how to run C++. So, we need either an interpreter or a compiler for C++.
8. Luckily, we have such a compiler as well, it is called Clang (or GCC or Microsoft Visual C++ or …)
9. Great! Now we have a JVM in the form of AMD64 machine code.
10. But wait! How do we run that AMD64 machine code? Well, we need an interpreter …
11. Puh, we actually have one: it is called a CPU.

So, the way Jython executes Python is as follows:

1. Python is interpreted by …
2. Jython (originally written in Java and then compiled to JVM bytecode) which is interpreted by …
3. the JVM (originally written in C++ and then compiled to AMD64 native machine code) which is interpreted by …
4. the CPU.

This is actually a significant simplification.

For example: the `javac` Java compiler that ships with the JDK is actually itself written in Java, so we need a Java compiler to compile the Java compiler to JVM bytecode which then gets interpreted by the JVM. And the C++ compiler is itself written in C++, so we need a C++ compiler to compile the C++ compiler. And actually, the JVM does not only interpret the JVM bytecode, it also compiles it to native machine code after a while. And modern CPUs often compile their "external" instruction set into a simplified "internal" instruction set. Also, I believe that Jython actually compiles Python to an internal representation and then interprets *that* representation instead of interpreting Python directly.

Also, consider this: what if, instead of compiling our JVM to AMD64 machine code, we instead compile it to MIPS machine code and then run it in an emulator …

# Compilers and interpreters

An *interpreter* for language **X** is a program (or a machine, or just some kind of mechanism in general) that executes any program **p** written in language **X** such that it performs the effects and evaluates the results as prescribed by the specification of **X**. CPUs are usually interpreters for their respective instructions sets, although modern high-performance workstation and server CPUs are actually more complex than that; they may actually have an underlying proprietary private instruction set and either translate (compile) or interpret the externally visible public instruction set.

A *compiler* from **X** to **Y** is a program (or a machine, or just some kind of mechanism in general) that translates any program **p** from some language **X** into a semantically equivalent program **p′** in some language **Y** in such a way that the semantics of the program are preserved, i.e. that interpreting **p′** with an interpreter for **Y** will yield the same results and have the same effects as interpreting **p** with an interpreter for **X**. (Note that **X** and **Y** may be the same language.)

In some cases, we have more specialized names for certain kinds of compilers, depending on what **X** and **Y** are, and what the compiler does:

* if **X** is perceived to be assembly language and **Y** is perceived to be machine language, then we call it an *assembler*,
* if **X** is perceived to be machine language and **Y** is perceived to be assembly language, then we call it a *disassembler*,
* if **X** is perceived to be lower-level than **Y**, then we call it a *decompiler*,
* if **X** and **Y** are the same language, and the resulting program is in some way faster or lighter, then we call it an *optimizer*,
* if **X** and **Y** are the same languages, and the resulting program is smaller, then we call it a *minifier*,
* if **X** and **Y** are the same languages, and the resulting program is less readable, then we call it an *obfuscator*,
* if **X** and **Y** are perceived to be at roughly the same level of abstraction, then we call it a *transpiler*, and
* if **X** and **Y** are perceived to be at roughly the same level of abstraction and the resulting program preserves formatting, comments, and programmer intent such that it is possible to maintain the resulting the program in the same fashion as the original program, then we call it a *re-engineering tool*.

Also, note that older sources may use the terms "translation" and "translator" instead of "compilation" and "compiler". For example, C talks about "translation units".

You may also stumble across the term "language processor". This can mean either a compiler, an interpreter, or both compilers and interpreters depending on the definition.

The terms *Ahead-of-Time (AOT)* and *Just-in-Time (JIT)* refer to *when* compilation takes place: the "time" referred to in those terms is "runtime", i.e. a JIT compiler compiles the program *as it is running*, an AOT compiler compiles the program *before it is running*. Note that this requires that a JIT compiler from language **X** to language **Y** must somehow work together with an interpreter for language **Y**, otherwise there wouldn't be any way to run the program. (So, for example, a JIT compiler which compiles JavaScript to x86 machine code doesn't make sense without an x86 CPU; it compiles the program while it is running, but without the x86 CPU the program wouldn't be running.)

So, we have:

* AOT compiler: compiles before running
* JIT compiler: compiles while running
* interpreter: runs

# JIT Compilers

Within the family of JIT compilers, there are still many differences as to when *exactly* they compile, *how often*, and at what granularity.

Some JIT compilers for example only compils code *once* (when it is loaded) and compile a whole module at a time. Other compilers may gather information while the program is running and recompile code several times as new information becomes available that allows them to better optimize it. Some JIT compilers are even capable of *de-optimizing* code. Now, you might ask yourself why one would ever want to do that? De-optimizing allows you to perform very aggressive optimizations that might actually be unsafe: if it turns out you were *too* aggressive you can just back out again, whereas, with a JIT compiler that cannot de-optimize, the program would crash or return a wrong result; in other words, you simply can't allow yourself to perform the aggressive optimizations in the first place.

JIT compilers may either compile some static unit of code in one go (one module, one class, one function, one method, …; these are typically called *method-at-a-time* JIT, for example) or they may *trace* the dynamic execution of code to find dynamic *traces* (typically loops) that they will then compile (these are called *tracing* JITs).

# Combining Interpreters and Compilers

Interpreters and compilers may be combined into a single language execution engine. There are two typical scenarios where this is done.

Combining an AOT compiler from **X** to **Y** with an interpreter for **Y**. Here, typically **X** is some higher-level language optimized for readability by humans, whereas **Y** is a compact language (often some kind of bytecode) optimized for interpretability by machines. For example, the CPython Python execution engine has an AOT compiler that compiles Python sourcecode to CPython bytecode and an interpreter that interprets CPython bytecode. Likewise, the YARV Ruby execution engine has an AOT compiler that compiles Ruby sourcecode to YARV bytecode and an interpreter that interprets YARV bytecode. Why would you want to do that? Ruby and Python are both very high-level and somewhat complex languages, so we first compile them into a language that is easier to parse and easier to interpret, and then interpret *that* language.

The other way to combine an interpreter and a compiler is a *mixed-mode* execution engine. Here, we "mix" two "modes" of implementing the *same* language together, i.e. an interpreter for **X** and a JIT compiler from **X** to **Y**. (So, the difference here is that in the above case, we had multiple "stages" with the compiler compiling the program and then feeding the result into the interpreter, here we have the two working *side-by-side* on the same language.) Code that has been compiled by a compiler tends to run faster than code that is executed by an interpreter, but actually compiling the code first takes time (and particularly, if you want to heavily optimize the code to run *really* fast, it takes a *lot* of time). So, to bridge this time where the JIT compiler is busy compiling the code, the interpreter can already start running the code, and once the JIT is finished compiling, we can switch execution over to the compiled code. This means that we get both the best possible performance of the compiled code, but we don't have to wait for the compilation to finish, and our application starts running straight away (although not as fast as could be).

This is actually just the simplest possible application of a mixed-mode execution engine. More interesting possibilities are, for example, to not start compiling right away, but let the interpreter run for a bit, and collect statistics, profiling information, type information, information about the likelihood of which specific conditional branches are taken, which methods are called most often etc. and then feed this dynamic information to the compiler so that it can generate more optimized code. This is also a way to implement the de-optimization I talked about above: if it turns out that you were too aggressive in optimizing, you can throw away (a part of) the code and revert back to interpreting. The HotSpot JVM does this, for example. It contains both an interpreter for JVM bytecode as well as a compiler for JVM bytecode. (In fact, it actually contains *two* compilers!)

It is also possible and in fact common to combine those two approaches: two phases with the first being an AOT compiler that compiles **X** to **Y** and the second phase being a mixed-mode engine that both interprets **Y** and compiles **Y** to **Z**. The YARV Ruby execution engine works this way, for example: it has an AOT compiler that compiles Ruby sourcecode to YARV bytecode and a mixed-mode engine that first interprets YARV bytecode and once it has gathered some information compiles the most often called methods into native machine code. Most ECMAScript execution engines work this way, too, as do most Smalltalk environments and many Lisps.

Note that the role that the interpreter plays in the case of a mixed-mode execution engine, namely providing fast startup, and also potentially collecting information and providing fallback capability may alternatively also be played by a second JIT compiler.

This is how the second generation of Google's V8 ECMAScript engine worked, for example. This generation of V8 never interprets, it always compiles. The first compiler is a very fast, very slim compiler that starts up very quick. The code it produces isn't very fast, though. This compiler also injects profiling code into the code it generates. The other compiler is slower and uses more memory, but produces much faster code, and it can use the profiling information collected by running the code compiled by the first compiler. The current generation of V8 is different from that again. It includes an interpreter as well. In contrast, the first generation of V8 only contained a single compiler which compiled ECMAScript straight to native machine code.

# Python

Every programming language can be implemented by an interpreter and every programming language can be implemented by a compiler.

Case in point: there are interpreters for C and there are native code compilers for Java and for JVM byte code.

However, it is important to understand that *all a compiler does* is translate a program from one language to another language. That's it. That's all it does.

*Only* an interpreter can actually execute code.

Interestingly, here is *no* pure Python interpreter in existence at the moment. All widely-used mainstream Python implementations have compilers:

* CPython compiles Python to CPython byte code (which it then interprets),
* Jython (sometimes) compiles Python to JVM byte code,
* IronPython compiles Python to DLR Trees,
* GraalPython is a strange one, it parses Python into Truffle ASTs, and then interprets the Truffle ASTs with a *specializing interpreter*, which is essentially equivalent to compiling the Truffle ASTs (it's related to Partial Evaluation and Abstract Interpretation (aka Supercompilation)),
* PyPy is another strange one, it compiles Python to PyPy byte code, interprets that PyPy byte code, and uses a tracing compiler to compile a specialized version of the interpreter which can only interpret that one program, which is essentially equivalent to compiling the PyPy byte code (it's related to Partial Evaluation and Abstract Interpretation (aka Supercompilation)).
> 5 votes

---
Tags: compilers, interpreters, theory
---


# Question
Title: Stalmarck's method: x ≡ x → z, does z have to be true?
I have been researching Ståmarck's method . In the paper cited here, some rules are given. Rules are made of triplets (x, y, z) such that:

y $\to$ z $\equiv$ x

where x, y and z are booleans which values are either 0 (false) or 1 (true). And rules then infer a consequence (bottom part of the rule).

For example:

$$ \frac{(x, y, 1)}{x/1} $$

means that given a triplet (x, y, 1), x has to be 1 (true). This makes sense because if the expression is $ y \to 1 $, then regardless of the value of y, the expression will be true (1). Now my question is, given the following rule:

$$ \frac{(x, x, z)}{x/1} $$

**Why is it not possible to infer that z = 1 as well?** If the truth table of this expression is drawn, this is the result (bear in mind that the result has to be the same value as x for it to make sense):

x | z | x -\> z ($ \equiv x $)
0 | 0 | 1
0 | 1 | 1
1 | 0 | 0
1 | 1 | 1

Clearly, the only line that does not immediately lead to a contradiction is the last one, and in this case z = 1 as well.

Sheeran, Mary, and Gunnar Stålmarck. "A tutorial on Stålmarck’s proof procedure for propositional logic." International Conference on Formal Methods in Computer-Aided Design. Springer, Berlin, Heidelberg, 1998.

# Answer
Yes, you are right. Having $x \leftrightarrow (x \rightarrow z)$ one can deduce that $x\equiv 1$ **and** $z \equiv 1$.

In the paper you cite (the link is to another one btw.), rule 6 allows only to deduce that $x\equiv 1$ holds.

But then you have the triplet $(1,1,z)$ and you can apply rule 4 $\frac{(x,1,z)}{x/z}$ to deduce $z\equiv x$, i.e., $z \equiv 1$ holds, too.

I have also seen other publications that include the conclusion $z \equiv 1$ directly in rule 6.
> 3 votes

---
Tags: logic, satisfiability, boolean-algebra, propositional-logic, sat-solvers
---


# Question
Title: Efficient intersection of equivalence classes
Having two equivalence relations, both as a union find data structure with the same number of elements, what is the most efficient way to find the equivalence relation that is the intersection of both relations?

For example, lets have $R\_1=\\{\\{1,2,3\\},\\{4\\}\\}$ and $R\_2=\\{\\{1\\},\\{2,3,4\\}\\}$. Then the intersection would be $R'=\\{\\{1\\},\\{2,3\\},\\{4\\}\\}$ as $2$ and $3$ are considered equivalent in both $R\_1$ and $R\_2$.

The "obvious" way would be $O(n^2)$ and test equivalence for each pair in each of the given relations. But maybe some property of the given union-find data structure would allow for better complexity?

As far as I know, even the canonical representative of a class is not necessary the same but depends on the sequence of class merges. (that was one approach I had in mind but did not really work out)

# Answer
> 3 votes
For each equivalence class $X$ of $R\_1$, find the representatives of all elements of $X$ in $R\_2$. This tells you how the elements of $X$ split in $R\_1 \cap R\_2$. (You might need to use some efficient data structures or algorithms beyond union-find.) Repeat for all other equivalence classes. Total running time is $\tilde{O}(n)$.

---
Tags: algorithms, union-find
---


# Question
Title: Find most vertices in a directed tree where no path of length less than 3 connects any pair
Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of length at least 3. Furthermore, $A$ should contain the maximum number of vertices.

The above is an exercise in my homework. "A directed tree" means a rooted tree where all edges are directed away from the root. Note that a vertex in $T$ might have more than 2 children.

---

We can use dynamic programming to compute such a set for the subtree rooted at each vertex of $T$. However, I found a simple greedy algorithm.

1. Create an empty set $A$.
2. As long as $V\neq \emptyset$, repeat the following action.
    1. Add all leaves to $A$.
    2. Remove their parents and their grandparents from $V$ (and the edges that are connected to them from $E$).
3. Return $A$.

It's easy to verify that all vertices added satisfy the path separating condition.

I believe that the number of all vertices added is optimal. It is indeed true in all cases that I have tried. Is it true? Does the greedy algorithm always work? I would like to see a proof for it.

# Answer
Yes, the greedy algorithm (you described) works.

Given a directed graph, call a subset of its vertices "a 3-separated set" if there isn't a path of length less than 3 between any pair of vertices among them. Call a 3-separated set a 3-separated-max set if it contains the maximum number of vertices. The problem is to find a 3-separated-max set in a directed tree.

Here is a proof of the greedy algorithm works.

**Proof.** It is enough to prove that there is a 3-separated-max set that contains all leaves.

Consider $S$, a 3-separated-max sets that contains the most number of leaves. It is enough to prove $S$ contains all leaves.

Suppose $S$ does not contain all leaves. Let leaf $l\not\in S$. Consider all ancestors of $l$. There are two cases.

* $S$ contains no ancestor of $l$. Then $S\sqcup\\{l\\}$ is a 3-separated set that has one more vertex than $S$, which is impossible.
* $S$ contains at least one ancestors of $l$. Let $\alpha$ be the ancestor in $S$ that is nearest to $l$. We can check easily that $(S\setminus\\{\alpha\\})\sqcup\\{l\\}$ is a 3-separated-max set that has one more leaf than $S$, which is impossible.

Since all cases are impossible, it cannot happen that $S$ does not contain all leaves, i.e., $S$ does contain all leaves. $\checkmark$

---

**Exercise** (easy). Generalize $3$ to any positive integer.
> 1 votes

---
Tags: trees, greedy-algorithms, directed-graphs, path
---


# Question
Title: Can a program span on 0 memory cells? If so, where is it hosted? (where it "sits down")?
In this question post, one of the answers is:

> ```
> You can even store a software program in 0 memory cells!
>
> All you need to do is to define a programming language in which the
> empty program has a defined meaning. For example, you can define a
> programming language that is just like Python, except the empty
> program prints the string "Hello, World!" to the console; let's call
> this programming language Python++.
>
> Now you can store a Python++ "Hello, World" program in 0 memory cells.
>
> ```

I read this answer several times but I cannot understand what the author intended. I tried to ask for clarification which the author read for sure (before declining my edit) but sadly didn't relate to.

Can a program span on 0 memory cells? If so, where is it hosted? (where it "sits down" if not in the memory --- any software memory type \[Central-Processing-Unit-memory/Hard-Drive-Disk-memory/etc.)?

# Answer
> 1 votes
In the scheme the author is using, the *program* can occupy zero memory cells. The thing you are using to *hold* the program might take some memory though.

Consider for instance a file on your hard disc. That file will still have a file name, size information, and other metadata in your file system, and that metadata takes up space. But the "payload" of the file - the section containing the file's data contents - is allowed to have zero length, and take up no space at all on disc. See zero-byte file.

Or, when you load the program into an interpreter, you might store its text/symbols in an array variable inside that interpreter's program. For the example of a zero memory cell program, that array would have zero length. The variable would still occupy some memory in your interpreter's address space - for instance, in a managed language it would likely store some type information and a start/end pointer or length - but the part of that space used by the "zero memory cell program" could indeed be nothing at all.

```
Array
  type: program_symbol
  start: null_pointer
  length: 0

```

Your interpreter would then have a check something like:

```
if (programContents.length == 0) {
   // Do the defined operation for a zero-length program.
   Print("Hello World");
} else {
   // Iterate over the program's contents and interpret each symbol...
}

```

This is how we could implement a programming language like the author of the original answer describes, where a zero-length program still does something. Any one thing that we choose, in fact!

I hope it's clear, this is not a useful way to write new software. It's just an edge case in how we define a program. If a program is a sequence of symbols that is valid and interpretable according to a chosen programming language definition, then we can choose to define our programming language so that the empty sequence is a valid program with a given interpretation.

---
Tags: memory-management
---


# Question
Title: Can we DISPROVE that a problem is NP-complete
So I basically had an exam question in which we were given a problem and we had to prove or disprove that it was in NP-complete. I tried to prove it but could not because apparently it could not be proved.

In the solution that the instructor sent us, they proved that we cannot prove that this problem is in NP; therefore, we cannot prove that it is in NP-complete. What he did was basically create a certificate which could not be checked in polynomial time. Is this a valid way to prove that a problem cannot be proved to be NP-complete (aside from the fact that it is not even disproving the claim.)? Because there might exist another certificate which could have been checked in polynomial time.

The problem was: Do there exist at least $n/4$ paths of $length ≥ K$ in a graph $G$ from source $s$ to destination $t$?

# Answer
> 1 votes
The provided answer is not valid to the question, as far as I know. Your rebuttal that there could be some other clever certificate is totally reasonable.

However, is it possible that you misunderstood the question? The question may be asking why this problem is not straightforwardly in NP-complete, in which case the "obvious" certificate would indeed not work, as the provided answer states.

To show that a problem is not NP-complete, there are two possibilities: it is either too easy\* or too hard. For the too easy case, you can show that it can be solved in polynomial time by giving an algorithm. This shows that it is in $P$, but see the caveat below. For the too hard case, you need to show that it is at least EXPSPACE-complete, by e.g. a reduction from another EXPSPACE-complete problem such as $EQ\_{REX\uparrow}$ (equivalence of regular expression with exponentiation). By space hierarchy theorem, an EXPSPACE-complete problem cannot be solved in PSPACE, which is equal to NPSPACE (by Savitch's theorem), which contains NP. You can also show that it is an NEXPTIME-complete, which properly contains NP by the time-hierarchy theorem. Note that PSPACE-complete or even EXPTIME-complete would not do, since it is unknown whether NP is strictly contained in PSPACE or EXPTIME.

* In fact, the "too easy" case is dependent on $P \neq NP$, which is open. So the most correct thing we can say is that it is unknown whether the problem is NP-complete or not.

# Answer
> 1 votes
What is $K$?

If $K$ is constant then this problem is in $P$. The number of paths with source s is less than $\binom{n-1}{K} \in O(n^K)$. So one can enumerate these paths in polynomial time.

At first, we will construct an algorithm, that finds one path from s to t with length $\ge K$

```
function has_paths(G,s,t,K):
 { for all paths (s=v_1,v_2,...v_{K_1}) in G\{t} do
     { find path from V_{k-1} to t in G\{v_1,v-2,...v_{k-2}}
  }

```

This algorithm can be modified, that it would search n/4 path and stop after finding it. This Version will be still in P. (Hint: use shortest path algorithm and weighted graphs)

If $K=n-1$ then to find one path is a Hamilton-path problem and NP-complete and to find $n/4$ path is NP-hard.

If $K$ is a function with $\lim\_{n\to\infty} K(n) =\infty$ and $K(n)=o(n)$ then findding one path is a good candidate for the class NPI

---
Tags: np-complete, np-hard, np, decision-problem, p-vs-np
---


title: Beginning Algorithm Design and Proving

text:
# Question
Title: Beginning Algorithm Design and Proving
I know this is a general question, so you can address this by giving some examples that are specific to your field.

I want to start learning algorithm design and consequently prove its convergence. Most of the algorithms I am interested in will be for use in machine learning and its applications. Where do I begin? I am reasonably proficient in mathematics and machine learning, but have been the enduser of such algorithms. Where/what books do I start learning for 'design' if I want to make an algorithm and analyse it myself?

thanks

# Answer
> 1 votes
If you really want to study algorithms, start by looking at a few courses on algorithms at reputable universities, check what textbooks they offer, and start reading one of those textbooks. Or, pick an online algorithms course (perhaps a MOOC, through companies such as EdX, Coursera, Udacity, etc.) and take it.

I personally am fond of *Algorithms* by Dasgupta, Papadimitriou, and Vazirani, but others have other preferences.

If you search this site, I think you can find many other recommendations for other algorithms textbooks.

It's possible you might actually be more interested in learning about optimization and numerical methods / numerical analysis, rather than classical algorithms. You can use the same procedure to find a textbook or course on one of those subjects.

Be warned that it's unlikely you will be able to prove convergence guarantees for most modern machine learning algorithms (e.g., those that use neural networks). Modern machine learning is primarily an empirical science, rather than one that comes with provable guarantees.

---
Tags: algorithms, mathematical-programming, algorithm-design
---


# Question
Title: Why can't hash tables provide O(n) sorting?
Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then retrieving them in order?

You just insert each number into the hash table, and remember the lowest and highest number inserted. Then for each number in that range, in order, test if it is present in the hash table.

If the array being sorted contains no gaps between values (i.e. it can be \[1,3,2\] but NOT \[1,3,4\]), this should give you O(N) time complexity.

Is this correct? I don't think I've ever heard of hash tables being used this way - am I missing something? Or are the restrictions (numeric array with no gaps) too much for it to be practically useful?

# Answer
The algorithm you give is exponential time, not linear. If you're given $n$ $b$-bit entries, the size of your input is $nb$ bits but the algorithm takes time $\Theta(2^b)$, which is exponential in the input length. In particular, your algorithm takes $2^k$ steps to sort the roughly $2k$-bit input $\\{0, 2^k\\}$.
> 5 votes

# Answer
The reason you've never heard of hash tables being used like this is that hash tables are either "too much" or "not enough" in this situation.

* If the range of elements being sorted is small, then you can use counting sort, or something similar. But for counting sort, you would almost certainly want to use a simple array rather than a hash table. If you know the max and min values of the numbers, then the array can be of size max-min+1, and value x would be associated with index x-min. By using an array, you avoid the extra complications of hash tables. Those extra complications are buying you nothing in this application, so hash tables are "too much".

Notice that your "no gaps" restriction ensures that the range of numbers is small (no larger than the number of elements in your original input).
* However, if gaps can be present then the range of elements is potentially MUCH larger than the number of elements in your original input. Then your running time is dominated by the size of that range, NOT by the size of your original input. Hash tables do not help you deal with those gaps efficiently, so in this case hash tables are "not enough".
> 7 votes

# Answer
kudos, The title of question if alone is to be considered- does have an ambitious idea, as there does exist a related research paper which sorts in linear time provided the constraints of no duplicates and knowing the range of input (gaps are allowed): Hash sort: A linear time complexity multiple-dimensional sort algorithm

However the steps mentioned in the paper are not as trivial as the question.

Coming to your last sub-question : *Or are the restrictions (numeric array with no gaps) too much for it to be practically useful?*

Given that we have the range (lowest and highest) and there are no gaps in numbers, why would we take the toll to sort it, the same practically can be represented by an interval \[low, high\], numbers if needed in order of this interval can practically be generated simply by incrementing which is not greater than linear time.

The sole purpose of sorting is to find an ordered collection, if the resulting ordered collection is known given the constraints (range and no gaps), its practically of no use.
> 0 votes

---
Tags: data-structures, runtime-analysis, sorting, hash-tables
---


# Question
Title: How can i do this type of swap(4-opt) between 4 edges of a graph?
The double bridge move is a specific type of swap between 4 edges of a graph, also called 4-opt. It consists of removing 2 pairs of edges. Let\`s call them (I, I+1), (J, J+1) and (P, P+1), (Q, Q+1). The edges are removed and reconnected in this way (I, J+1), (J, I+1), (P, Q+1) and (Q, P+1), like in the first image below. In this way, the graph that could be seem like circular now has 2 "bridges"(pair of edges) crossing each other.

I need this for the Travelling Salesman Problem. **I want to know the best way to do the Double bridging, in pseudocode.** I have coded the 2-opt already, but this type of 4-opt cannot be reproduced by any sequence of 2-opts. Not unless some sort of reversal is also made in some edges of the graph, and i don't know how to do this.

I searched the entire internet including several papers for any explanation regarding double bridge but none have helped me.

# Answer
> 0 votes
If the path is stored as a doubly-linked list, you can do it in $O(1)$ time in a straightforward way: you have to change around 4 edges, and each change can be done in $O(1)$ time. With an array it takes $O(n)$ time but is also straightforward to implement.

---
Tags: optimization, np-hard, shortest-path, traveling-salesman
---


# Question
Title: Can a context-free Language have an infinite pumping length?
I have a language that would require an infinite pumping length, I know the language is not context-free, but is this sufficient prove ?

# Answer
> 1 votes
The pumping lemma for context-free languages states that if $L$ is context-free then there exists a constant $p$ such that each word $w \in L$ of length at least $p$ can be partitioned into $w = uxyzv$ such that the following properties hold:

* $|xz| \> 0$.
* $|xyz| \le p$.
* For each $i \geq 0$, $w = ux^iyz^iv$.

In order to show that a language $L$ isn't context-free, we show that the property above doesn't hold for *any* $p$. That is, we show that for every *constant* $p$ there exists a word in $L$ of length at least $p$ which cannot be partitioned as above.

While the concept of *pumping length* is natural, it is not a standard one. One way to define it is as the minimal $p$ for which the consequence of the pumping lemma holds, if such a $p$ exists, or infinity otherwise. In these terms, the pumping lemma can be expressed succinctly as stating that context-free languages have finite pumping length. Equivalently, a language with infinite pumping length is not context-free.

The converse doesn't hold: some non-context-free languages have finite pumping length. In the case of regular languages, the pumping lemma can be strengthened to give an if-and-only-if condition, as was done by Jaffe and by Stanat (and possibly by others). To the best of my knowledge, no such strengthening exists for context-free languages, though stronger versions of the pumping lemma are known, for example Ogden's lemma (which can be "backported" to regular languages).

---
Tags: pumping-lemma
---


# Question
Title: Proof no DPDA can accept Palindrome (need explanation for the attached proof)
The given proof for proving that no DPDA can be constructed to accept palindromes is unclear. There exists another similar question but it only explains the proof partially.

I understood how it aims to find two strings r and s (r!=s) for which rz,and sz with a common suffix z will be processed in the exact same way by a hypothetical DPDA.

However, how is it possible to find such strings if the DPDA doesn't exist at all?

# Answer
This is a proof by contradiction. If you're not familiar with proof by contradiction, I suggest learning about that proof method (and more generally, refreshing your knowledge of discrete mathematics and proof techniques) before trying to understand this specific proof.

You can think of it this way: either $M$ exists, or it doesn't. If $M$ does exist, you can find strings $r,s$ with a property that leads to a contradiction -- so we can conclude that it's not actually possible for $M$ to exist. The only remaining possibility is that $M$ does not exist.
> 1 votes

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


# Question
Title: What would be the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?
What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?

I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $3n^2 + 2n \ge 3n^2 + n$ is the tightest lower bound I can come up with.

However, would this be the correct answer instead? $\omega(n) = cn^2$ for the constant $c = 3$ and integer $n \ge 1$? Are we allowed to drop variables of a lower order when producing an asymptotic lower bound?

# Answer
A function $g(n)$ is an asymptotic lower bound for a function $f(n)$, in symbols $f(n) = \Omega(g(n))$, if the following holds:

> There exist $N,c \> 0$ such that for all $n \geq N$: $f(n) \geq cg(n)$.

In your case, $f(n) = 3n^2 + 2n$. You can check that $f(n) = \Omega(f(n))$, that is, the function is its own asymptotic lower bound. Similarly, you can check that $f(n) = \Omega(3n + 2)$, that is, $3n+2$ is an asymptotic lower bound on your function, though it is not tight.

Usually we are interested in a *simple* function which is an asymptotic lower bound. Moreover, when possible, we want our lower bound to be *tight*.

A function $g(n)$ is a tight asymptotic lower bound for a function $f(n)$, in symbols $f(n) = \Theta(g(n))$, if the following holds:

> There exist $N,C,c\>0$ such that for all $n \geq N$: $Cg(n) \geq f(n) \geq cg(n)$.

(For the experts: a more permissive definition would ask that $f(n) = \Omega(g(n))$ but $f(n) \neq \Omega(h(n))$ whenever $h(n) = \omega(g(n))$. As an example, $1$ is a tight asymptotic lower bound on $n(\sin n + 1) + 1$.)

Every function is its own tight asymptotic lower bound. In your case, the simpler function $n^2$ is also a tight asymptotic lower bound on $f(n)$. Indeed, we can take $N = 1$, $C = 5$, $c = 3$. For all $n \geq 1$: $$ 5n^2 \geq 3n^2 + 2n \geq 3n^2. $$ Hence $3n^2 + 2n = \Theta(n^2)$, which is probably the answer that was expected.
> 1 votes

---
Tags: asymptotics, big-o-notation
---


title: Asymptotic height of d-ary heap

text:
# Question
Title: Asymptotic height of d-ary heap
I know that the height of a $d$-ary heap on $n$ nodes is $\lceil (\log\_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's $\Theta(\log\_d n)$? I know the definition of $\Theta, O, \Omega$ if only one variable is involved. In particular, what is the formal definition of a function $h(n,d)$ being in $\Theta(\log\_d n)$?

One can clearly upper bound the height by $\log\_d (n)+1$, but why does that imply the height is in $O(\log\_d n)$? The problem is that $d$ can exceed $n$, and if $d$ keeps increasing while $n$ is fixed, then $\log\_d n$ will approach $0$.

Also, one can show that the height is at least $\log\_d (n(d-1) + 1) - 1\ge \log\_d n - 1$ for $d$ sufficiently large. Why is this in $\Omega(\log\_d n)$?

# Answer
> 0 votes
Suppose that $n \geq 1$ and $d \geq 2$. On the one hand, $$ \lceil \log\_d(n(d-1)+1)-1 \rceil \leq \log\_d(2dn) \leq \log\_d n + 2. $$ On the other hand, $$ \lceil \log\_d(n(d-1)+1)-1 \rceil \geq \log\_d(nd/2)-1 = \log\_d n - 1. $$

In other words, your expression is equal to $\log\_d n$ up to a constant additive term.

In particular, if we *fix* $d$ then your expression is $\Theta(\log n)$. You can say more: we can find constants $c,C\>0$ such that your expression is bounded between $c \log\_d n$ and $C\log\_d n$.

Asymptotic notation in several variables is ambiguous. Often we use it when the expression in question is monotone increasing in all variables, which is not the case here, and so whenever using it, you should clarify what it means.

I wouldn't spend too much time agonizing on the relation between your expression and the quantity $\log\_d n$. Informally, your expression is very close to $\log\_d n$. This can be formalized in several ways, as I indicated above. Informally, one could write that your expression is $\Theta(\log\_d n)$, but this is somewhat ambiguous, and as you point out, is false when $n$ is small compared to $d$. Nevertheless, it can be made precise in various ways.

For more on formalizations of asymptotic notation on several variables, see the answers to this question.

---
Tags: data-structures, asymptotics, discrete-mathematics, heaps
---


title: How much CMIX compresses text data?

text:
# Question
Title: How much CMIX compresses text data?
I have atleast a terabyte of text data which I need to compress as efficiently as possible. It is file of english words and numbers (Not randomly arranged but forming meaningful syntax just as regular grammatical sentences). I got to know about CMIX compressor and its benchmarks (not too much understandable to me) and there was no short answer on google such as : cmix compressed a file of n GB to n GB OR n MB etc. So I want to know how much (how closely will it be able to) compression I will get if I use it on my 1 TB text data. And is there any other compressor better than cmix.

# Answer
> 1 votes
There *is* no answer. It depends on the specific text file. If you want to know how much it will compress a specific file, the way to find out is to try compressing that file and see what you get. The compression ratio may vary from file to file, even for text data.

---
Tags: data-compression
---


# Question
Title: Why does the formula 2n + 1 find the child node in a binary heap?
I learned that when you have a binary heap represented as a vector / list / array with indicies \[0, 1, 2, 3, 4, 5, 6, 7, 8, ...\] the indicies of the children of element at index n can be found with

$leftchild = 2n + 1$

$rightchild = 2n + 2$

I can see that this formula works and have played around with it for a little bit looking at examples, but I still don't understand **why** it works. Can anyone help me understand the intuition behind why this is correct?

# Answer
> 8 votes
Let us consider first the case in which node indices are 1-based (start at 1). The nodes in a heap are arranged so that node $1x\_1x\_2\ldots x\_\ell$ (given in binary) is reached by starting at the root and then:

* If $x\_1 = 0$, choose the left child; if $x\_1 = 1$, choose the right child.
* If $x\_2 = 0$, choose the left child; if $x\_2 = 1$, choose the right child.
* ...
* If $x\_\ell = 0$, choose the left child; if $x\_\ell = 1$, choose the right child.

This gives a rule for "decoding" any positive integer. This kind of encoding makes it clear that the left child of node number $x$ is $2x$, and the right child of node number $x$ is $2x+1$.

When nodes are 0-based, the formula becomes a bit different. If $y$ is the 0-based address of a node, then $y+1$ is its 1-based address. The 1-based addresses of the children are $2(y+1)$ and $2(y+1)+1$, hence their 0-based addresses are $2(y+1)-1$ and $2(y+1)$, which work out to $2y+1$ and $2y+2$.

# Answer
> 8 votes
I would like to propose my revisited version of Hiroki's answer. Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being of use to anyone. Credits to Hiroki for the original answer and structure.

I've simply clarified the math and made every step explicit and chosen a slightly different terminology.

---

Let's assume that each tier of the heap is an array.

```
T1 [                n0                 ]

T2 [      n1,                n2        ]

T3 [  n3,     n4,       n5,       n6   ]

T4 [n7, n8, n9, n10, n11, n12, n13, n14]

```

It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.

Likewise, $n1$ is the parent of $n3$ and $n4$.

For example, $T2$, the second tier, contains nodes $\[n1, n2\]$ and has length $2$.

Let's say $i$ is the global index of the node in question (i.e. the node's index if the entire tree were to be collapsed within a single array), and $j$ is the local index of the node, i.e. the index of the node within its tier.

For example, in the diagram above, if the node in question is $n3$, $i = 3$ and $j = 0$, because $n3$ is the first element in the 3rd tier.

```
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier

```

The maximum number of nodes in a tree up to a certain tier can be expressed by:

$total\\\_nodes\\\_up\\\_to(T) = 2^T - 1$

e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$

This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} - 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2

Since indexes start from 0, the index of the last node in an array of nodes will be $numNodes - 1$. This means that the global index of the last node in some tier $T$ is:

$i\_{last} = total\\\_nodes\\\_up\\\_to(T) - 1 = 2^T-1-1$

While the local index of the last node in the tier is:

$j\_{last} = 2^{T-1} - 1$ // since there are $2^{T-1}$ elements in tier $T$

We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index. You can visualize it mentally as "walking backwards" starting from the the last node - if you take local-index-many steps back you land onto the first node in the tier:

$i\_{first} = i\_{last} - j\_{last}$

$i\_{first} = 2^T - 1 - 1 - j\_{last}$

$i\_{first} = 2^T - 1 - 1 - (2^{T-1} - 1)$

$i\_{first} = 2^T - 2^{T-1} - 1$

$i\_{first} = 2\*2^{T-1} -2^{T-1} - 1$

$i\_{first} = (2 - 1)\*2^{T-1} - 1$

$i\_{first} = 2^{T-1} - 1$

We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:

$i = i\_{first} + j$

$i = 2^{T-1} - 1 + j$

Let's now think about the first (left) child of the node in question.

```
The left child, n', will be in the next tier, T+1.
The indices in T+1 will be referred to as i', j', i'_first ...

```

Based on what we've shown so far, we can say that the global index of the first node in the next tier is:

$i\_{first}' = 2^{T+1-1} - 1 = 2^T - 1$

Now, for each predecessor of the parent node $n$ in tier $T$ there will be 2 predecessors of left-child node $n'$ in $T+1$. Also, given index $j$ in $T$, we know there are $j$ predecessors of $n$ in $T$ \- i.e. the index of a node is equal to the number of its predecessors. So we can conclude that:

$j' = 2j$

Putting it all together, we can conclude that

$i' = i\_f' + j'$

$i' = 2^T - 1 + 2j$

Now let's rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:

$i + 1 = 2^{T-1} + j$

Finally, let's compare that to the equation of the global index of the left-child node:

$\begin{align} i' &= 2^T - 1 + 2j\\ &= 2\*2^{T-1} + 2\*j - 1\\ &= 2\*(2^{T-1} + j) - 1\\ &= 2\*(i + 1) - 1 \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\ &= 2i + 2 - 1\\ &= 2i + 1\\ \end{align}$

Although the question was why the $2n + 1$ formula works, note that I used $i$ instead of $n$! Let me know if there is anything unclear.

# Answer
> 5 votes
Just see it as a perfect binary tree, where you have numbered its nodes from root downwards, level by level. What is the relationship between the number you gave an element x and the number that you gave to its children?

Other useful questions: How many nodes are between an element and its children? Why is that? Does it have anything to do with powers of 2, and the tree being a perfect binary tree?

# Answer
> 4 votes
Let's assume that each tier of the heap is an array.

```
T1 [            0              ]

T2 [     1,            2       ]

T3 [  3,   4,      5,      6   ]

T4 [7, 8, 9, 10, 11, 12, 13, 14]

```

It may not be clear, but I want you to imagine that $0$ is the parent of $1$ and $2$.

Likewise, $1$ is the parent of $3$ and $4$.

For example, the second tier's length is $2$.

i.e. $\[1,2\]$

Let's say $i$ is the index of the node in question, and $j$ is the index of the tier.

e.g. In the diagram above, if the node in question $(i)$ is $3$, $j$ is $0$, because $3$ is the first element in the 3rd tier.

```
i = the index of the heap, indicating the node in question
j = the index of the tier where the node in question exists
T = tier

```

The maximum number of nodes in a certain tier can be expressed by...

$2^T - 1$ E.g. when you have 3 tiers, you can put 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$

This means that the index of the node in question looks like...

$i = 2^T-1 - 1 + j$ //This will shortly become "$i + 1 = 2^T-1 + j$"

The first child (left child) of $i$ can be derived by...

$i' = 2^T -1 + 2j$

If you don't see why I multiplied $j$ by 2, I would suggest you draw a map on a paper and see the indexes of $i - 1$'s left and right child.

$\begin{align} i' &= 2^T -1 + 2j\\ &= 2(2^T-1 + j) - 1\\ &= 2(i + 1) - 1 \text{//NOTE: Here we use $i + 1 = 2^T-1 + j$ mentioned above}\\ &= 2i + 2 - 1\\ &= 2i + 1\\ \end{align}$

Although the question was why the $2n + 1$ formula works, note that I used $i$ instead of $n$! Let me know if there is anything unclear.

# Answer
> 2 votes
Frankly the same question popped up in my head, i tried to do the proof my self at first, but i did not succeed. So i searched for it, and came by this question, but noticed that the top voted solutions had the same ideas as me, so i came back to my ideas and came up with the following solution:

Lets look at an example of a small complete binary tree

```
Nodes                                   Level   Number of nodes in this level
1                                       1     | 2^0
2 3                                     2     | 2^1
4 5 6 7                                 3     | 2^2
8 9 10 11 12 13 14 15                   4     | 2^4

```

I'm going to use 3 variables to make things shorter: L the level in which a node exists, g the global index of a node, s the subindex of a node in a level (the index of that node in that level). More explanation of these variables will come ahead

**Notice that for this whole proof, i'm not starting my indexes at zero but at one to make things easier.**

Notice that at each level the number of nodes in that level is 2^(L-1). Also since each level has 2^(L-1) nodes then the index at that level starts at 2^(L-1). Based on the previous info we get that

```
g = 2^(L-1) + s - 1

```

so for example the global index of the second node in the third level is

```
g = 2^(3-1) + 2 - 1 = 4 + 2 + 1 = 5

```

now lets say we want to get the left child of the node (6), here is what we need to do, we need to walk 1 more step to the end of the current level and then for each node that came before node (6) we need to walk two steps (since each node has 2 children) and then one more step to get to the first (left child).

transforming this into an equation we get

```
leftChildIndex = parentIndex + (2^(L-1)-s) + 2(s-1) + 1

```

where (2^(L-1)-s) is the steps that is left to reach the end of current level, and 2(s-1) is 2 steps we need to take for each node that came before the current node.

As an example say we want to get the left child of node (6), this means first we need to move 1 step to reach end of Level 3, then we need to take 4 steps (because of nodes 4,5 having two children's each) and one step.

so for first child of node (6) we get

```
leftChildIndex = 6 + (2^(3-1) - 3) + 2(3-1) + 1 = 6 + 1 + 4 + 1= 12

```

so now that we saw the equation works lets get back to it

```
leftChildIndex = parentIndex + (2^(L-1)-s) + 2(s-1) + 1 = parentIndex + 2^(L-1) - s + 2s  -2 + 1 = parentIndex + 2^(L-1) + s - 1 = parentIndex + g = g + g = 2g

```

we can replace parentIndex with g so we get leftChildIndex = 2g as expected

I got 2g instead of 2g + 1 because i started my indexes at 1 instead of 0, starting them at zero will get you 2g + 1.

# Answer
> 1 votes
I really liked Yuval Filmus' answer, but wanted to try explaining it a bit differently after it had clicked for me.

The idea of implementing a full binary tree with an array is essentially just assigning indexes to each node. We'll use 1-indexing, as you'll soon see why, to show that the indexes sneakily encode the normal tree traversal you would use to reach any node.

Normally we start from the root and then go downwards, traveling either left or right. Take the 26th node for example. To reach the 26th node, we take the following path:

`root -> right -> left -> right -> left`

Now note the binary representation of 26:

`26 = 0b1_1010`

The initial `1` denotes the root. Afterwards, **`0` represents going left** while **`1` represents going right**.

This means that in order to go left we want to append a `0` bit, and to go right we want to append a `1` bit.

In order to achieve this, we left shift one bit (which is multiplying by 2) and then add either 0 or 1.

* `tree[i].left = tree[2*i]` to add a `0` bit.
* `tree[i].right = tree[2*i+1]` to add a `1` bit.

To use 0-indexing, all we have to do is add `1` everywhere to simulate 1-indexing.

# Answer
> 0 votes
Consider below tree and its array representation.

```
            0
        1       2
      3   4   5   n

```

`[0, 1, 2, 3, 4, 5, ..., n]`

Now element at 0 index has children at indices 1 & 2. Similarly it is true for rest elements as below.

```
0, 0+1, 0+2
1, 1+2, 1+3
2, 2+3, 2+4
3, 3+4, 3+5
4, 4+5, 4+6
5, 5+6, 5+7
n, n+(n+1), n+(n+2)

```

Which in tern

n + (n+1) = 2n+1

n + (n+2) = 2n+2

# Answer
> 0 votes
Well, first of all, i\_right = i\_left + 1. Always. It's obvious, so bellow I'm gonna show only proof of expression i\_left\_child = i\_parent * 2 + 1.

In the explanation bellow there might be quite many definitions like: parent, child, index, position in current level, etc. So instead of greek/latin letters I decided to use the exact numbers from picture, but **avoid** any math operation on it, like it was a symbol. So it should work with all the numbers.

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


title: Why is SET PACKING in NP?

text:
# Question
Title: Why is SET PACKING in NP?
I have seen an lot of proves why SET PACKING is NP complete. However, in every prove it states that SET PACKING is clearly in NP. It might be a stupid question, but is not so clear to me. I see that the procedure contains of 2 parts:

1. Choosing a subset of size k from a collection of sets
2. Check whether the chosen subset of size k is mutually disjoint

But why does this take polynomial time? I can see that step 1 takes n steps in the worst case scenario, but I don't know what to do for the second step. How does the Turing machine verify this? And how many steps does this take?

Thanks a lot in advance!

# Answer
To solve such a problem, you should have more of a "programming" point of view rather than a "Turing machine" point of view.

Sure, $\mathsf{NP}$ is defined considering the executing time of a Turing machine, however we, human beings, are not made to think in TM. You could think of it as the same difference between programming in a very low level programming language (like assembler) and a high level language (like python).

To have an idea as to how verify the solution of a Set Packing problem, you could also think of a usefull data structure to ease the verification. Here, I think that using boolean arrays is the easiest:

* since all subsets are subsets of the same set $S$, consider a bijection between $S$ and $\\{1, …, n=|S|\\}$ (I will now identify elements of $S$ with integers);
* a subset $T\subseteq S$ can be represented with an array $\[t\_1, t\_2, …, t\_n\]$ such that $t\_i = true$ if $i\in T$ and $t\_i = false$ otherwise;
* considering a family $T\_1, T\_2, …, T\_k$ of subsets of $S$, you can consider the following algorithm to verify that they are disjoint:

```
Input: boolean arrays T1, T2, …, Tk of length n
Create T a boolean array containing n false
for i = 1 to k do
    for j = 1 to n do
        if T[j] and Ti[j] then
           return False
        T[j] ← T[j] or Ti[j]
return True

```

The idea is that the array $T$ will keep track of all elements of $\bigcup\limits\_{i = 1}^k T\_i$. If I find an element $j$ is in $T\_i$ but I have already found $j$, then there are two subsets that are not disjoint.

The time complexity of the algorithm is $\mathcal{O}(n)$ (creation of $T$) + $\mathcal{O}(nk)$ (loops). It is indeed polynomial in the size of the problem.

Note that you could consider representing $T$ with a boolean array, and $T\_1$, …, $T\_k$ using a list of contained elements. That would result in a better complexity.

```
Input: integer n, lists T1, T2, …, Tk containing elements between 1 and n
Create T a boolean array containing n false
for i = 1 to k do
    for x in Ti do
        if T[x] then
           return False
        T[x] ← True
return True

```
> 0 votes

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


# Question
Title: Does a set definition have computational complexity?
I'm wondering if a mathematical set definition has a computational complexity.

For example, assume I have some kind of problem where the solution is given by the positive integers smaller than a given integer $n$:

$M = \\{ x | x \< n, x \in \mathbb{N} \\}$

Could I say this problem can be solved in $\mathcal{O}(n)$ because I could realistically construct an algorithm that yields this result in linear time?

I actually have such an approach in a paper where it makes more sense to define a set than give an (trivial) algorithm that returns this set.

# Answer
Usually, mathematical definitions are not computational. Informally, mathematics describes the "what", not "how" you compute it.

However, for some problems there is an obvious algorithm deciding them. I would not see an issue with a sentence like this:

> The problem $\\{x \in \mathbb N\\,|\\, x \< c\\}$ can be decided in $O(n)$ for all constants $c$.

Yet, the set definition still does not carry any computational behavior. It's just that it is decidable, and you consider finding a decision procedure with the stated complexity trivial enough for your target audience. The decidability does not depend on how you define it.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: How Universal Turing Machines can do something if a machine doesn't accept?
In our Computability & Complexity course, we wanted to show that $ALL\_{TM}\notin RE$. To do that, we have seen the following claim (I'm summarizing it):

Denote the languages: $ALL\_{TM}=\\{(M)|L(M)=\Sigma^\*\\}$ and $A\_{TM}=\\{(M,\\,w)|w\in L(M)\\}$.

> The problem is that we want to simulate $M$ on $w$, but we can actually want to do something if $M$ does not accept $w$. Now, if $M$ rejects $w$ that's fine. We'll wait until it rejects, and go about our business. However, what happens if $M$ does not halt on $w$? Well, then we need some tricks.

> **Claim:** $\overline{A\_{TM}} \le\_M ALL\_{TM}$ (and thus $ALL\_{TM} \notin RE$). **Construction:** On input $(M,\\,w)$, the reduction constructs the machine $K$ that on input $x$, simulates $M$ on $w$ for $|x|$ steps. If, during this, $M$ accepts, then $K$ rejects. otherwise, $K$ accepts.

Then, when proving the correctness, they claimed the following:

> If $(M,\\,w)\in \overline{A\_{TM}}$ then $M$ does not accept $w$ and in particular $M$ does not accept it within $|x|$ steps, for all $x$. Thus, $K$ accepts every input so $L(K)=\Sigma^\*$ and $(K)\in ALL\_{TM}$.

Now, I understand that, take some input, $(M,\\,w)$ from $\overline{A\_{TM}}$, then if $M$ rejects/not halt on $w$ it means that $(M,\\,w)\in \overline{A\_{TM}}$ and otherwise it's not. My problem is with the justification "\[...\] in particular $M$ does not accept it within $|x|$ steps, for all $x$. Thus, $K$ accepts every input \[...\]": Lets say that $M$ won't halt on $w$. In this case, when $K$ simulate $M$ \- $M$ will not halt - and as a result, $K$ won't halt either, so how come we can say that it'll accept? I understand that in the construction we said that if during the simulation $M$ accepts, then $K$ rejects - but what if in the simulation $M$ doesn't stop at all, how will $K$ have the opportunity to accept? How will it know when to say "enough is enough, I'm going to accept this?"? I can't see what the "trick" is that they applied here.

# Answer
> 1 votes
The input of $K$ is $x$, and $K$ will only simulate $M$ during at most $|x|$ steps. Therefore, there is no situation where the simulation of $K$ does not stop.

If $M$ does not accept $w$, then for any word $x$ of length $n$, executing $M$ during $n$ steps will never reach an accepting state. And so, after $n$ steps of simulation, the TM $K$ will accept the word $x$.

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


# Question
Title: Given a vector of points, what is the fastest algorithm to find all pairs of points at a distance of 1?
Given a vector of points (on the 2D plane), what is the fastest algorithm to find all pairs of points at a distance of 1?

Of course, I could use the $O(N^2)$ algorithm to check all pairs of points. However, I recently found out that there are at most $O(N^{4/3})$ points which satisfy the property, so I am wondering if a quicker algorithm exists.

Thanks!

# Answer
> 1 votes
You may use a Well-Separated Pairs Decomposition (WSPD). This is a hierarchical decomposition, where at each level, you split the points into two parts, each of them a certain distance from the sphere enclosing the other set, and a certain radius of the sphere containing them.

It runs in $O(n\log n + X)$, where $X$ is an output sensitive parameter, that measures the number of the partitions required to make the full decomposition. (Of course, you can stop the decomposition algorithm after you are working with distances less than 1)

# Answer
> 1 votes
The problem can be regarded as a special case of incidence reporting problem with $N$ unit circles and $N$ points in the plane.

If the number of unit circles is $m$, then this problem can be solved in $\tilde{O}(m^2 + N)$ time ($\tilde{O}(\cdot)$ ignores polylogarithmic factors). First, explicitly computing the arrangement (the division of the plane, its edges, and vertices) of circles, then constructing a point location data structure, and query the data structure for each point.

The set of $N$ circles can be partitioned into $\sqrt N$ subsets of each $\sqrt N$ size, and each sub-problem can be solved separately. The total runtime is $\tilde{O}(N^{3/2})$. A more involved approach yields a $\tilde{O}(N^{4/3})$-time randomized algorithm \[1\].

---
Tags: algorithms, computational-geometry, euclidean-distance
---


# Question
Title: Efficient comparison, using only sum, product, difference, and conditional jump if zero
I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you can individually (hopefully) address bits.

So was wondering, in addition to $+, -, \cdot$ (no $\\%$) what else is needed to implement $\gt$ efficiently? Let's say we have a single kind of conditional branch statement:

$$ \text{goto\_line } l \text { if } a = 0 $$

Then can we implement $\gt$ efficiently? By efficiently I mean that an algorithm runs in worst case, polynomial-time, if and only if there exists a program implementing the algorithm on the above machine that runs in polynomial-time (roughly speaking).

# Answer
Any such algorithm requires exponential time. Here is a proof sketch (omitting technicalities).

Let $n$ be the input length. The input is $-2^n \lt x \lt 2^n$ and the algorithm determines $x \gt 0$. An algorithm for the problem can be represented as an infinite decision tree, where each node is either a leaf (termination) or a branch with "zero" and "nonzero" child nodes.

The operand of each branch node can be represented as a polynomial of $x$. Without loss of generality, I assume every such polynomial is non-constant.

Consider the path from the root where "nonzero" branch is taken at every branch. Let $p\_i$ be the $i$'th polynomial. Then, because a non-constant polynomial of degree $d$ can have at most $d$ roots, at least $2^{n+1} - \sum\_{i=1}^{t-1} \mathrm{deg}(p\_i) - O(1)$ inputs from $(-2^n,2^n)$ will take this nonzero-only path. The degree of the polynomial isn't be too large because it could have taken at least $\deg(p\_i)$ time to compute this value. Thus, the algorithm takes an exponential time to terminate.
> 2 votes

---
Tags: computation-models, polynomial-time, arithmetic, integers, comparison
---


# Question
Title: Why do we not use continuous real quantities to represent continuous numbers
I've just been doing some pondering, and given the fact that computers already operate on fundamentally continuous physical quantities, and then we have to use transistors to turn those real quantities into effectively discrete numbers, why don't any computer architectures just skip the intermediary and do away with floating point numbers to represent reals. I understand for general purpose computing this is probably more effort than it's worth, but high precision scientific computing is such such a large field, it surprises me that there aren't any general purpose chips that actually leverage the continuous nature behind the representation of numbers on computers. What are the challenges in making an analogue computing machine general purpose enough to be widely used, and are there any potential solutions to those problems? It's a bit of a vague question, I know, but at the same time my knowledge is quite vague so it's difficult for me to ask more precise questions. Any related links or avenues for further research would also be greatly appreciated.

# Answer
There are many challenges:

* Digital logic can be made reliable, so that small variations in voltage etc. are corrected. It's less clear how to do that with continuous/analog logic, so small noise and/or errors could compound.
* This would at best let you represent fixed-point numbers, not floating-point numbers. For instance, if a wire carrying $x$ volts represents the number $x$, then you won't be able to accurately represent either $10^{-9}$ and $10^9$ with such a representation, yet standard floating-point arithmetic can easily represent very small and very large numbers with no difficulty. A lot of scientific computing relies heavily on floating-point numbers, so limiting to fixed-point numbers is a significant limitation. The up-front cost of designing hardware is very high, so if you're going to design hardware, it needs to be widely applicable.
* The precision would likely be poor, due to noise in analog circuits. You might get two or three digits of precision (only). That's not enough for most scientific computing.
* How would you multiply two numbers? It seems very difficult to design a circuit that multiplies two numbers: given one wire powered at $x$ volts and another wire powered at $y$ volts, you'd need a circuit that produces an output wire wired at $xy$ volts.

This makes analog circuits likely not very attractive for general-purpose computation or for scientific computing in general. Still, there have been proposals to use analog circuits for some very specific tasks, such as computing neural networks.
> 3 votes

# Answer
The problem you identify is much deeper than computing.

The main use of computing, for various kinds of business administration, is not a continuous problem at all, but one that deals with the processing of discrete symbols.

The predecessor to the electronic computer in this field, pen and paper, also used discrete symbols, so you can see that the reduction of the continuous to the discrete did not start in the computer era.

The problem with continuous phenomena is that they cannot be represented. Therefore one of the most basic activities that humans perform on an ongoing basis is the reduction of the continuous to the discrete. Speech is reduced to words and alphabet letters. The visual field of the eye is reduced to objects and the occurrence of processes (which can be spoken about in words). All sorts of things are reduced to discrete symbolic measurements.

Even the "analog clock" is reduced, in the human reading of it, to cardinal hours or smaller discrete divisions, and it incorporates discreteness internally in terms of its gear teeth and the periodicity of its oscillating element (typically a pendulum). Even a sundial has a discrete scale - otherwise, you would just read any old shadow.

The main problem with analog devices is precisely their residual continuity, which is a source of mental effort (and variability) for reducing their final output to the fully-discrete, and a source of error in their internal processing.

The digital computer essentially works by seeking to reduce *all* its internal and external workings to the discrete, to mirror *exactly* what a human would do with pen and paper. It is a final perfection of implementing pen-and-paper working as a mechanical machine. The digital computer *is* a general purpose analog computer.

The only residual area for the use of analog machines is for *special purposes*. This includes cases where no known discrete (pen-and-paper) method exists for the processing being performed, or where it is too complicated for a digital machine to perform discretely.

This also includes cases where the sheer simplicity of the processing allows it to be implemented very simply in terms of basic mechanical or electronic components (without the overheads of creating a general-purpose assembly of such components operating on digital principles).

Incidentally, what we think of as analog clocks remain in use firstly because the representation of time as angles of clock hands remains preferred - most of us are so familiar with them that the cardinal angular patterns have been learned as discrete symbols, like an alphabet, so it is very easy to read the approximate time even at a glance through peripheral vision (whereas a digital display requires four symbols to be parsed, whose indistinctness requires the use of central vision). Also, the complexity of incorporating a digital computer and a stepper motor to generate the angle for each hand, is far more than just implementing the whole thing as a gear train.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?
Given a multiset $S$ of numbers, partition it into two subsets $S\_1 $ and $S\_2$. How to maximize the sum of their medians? For example, the median of `{1,2}` is `1.5`.

I've found a greedy algorithm that $S\_1$ contains the maximum of $S$ (if multiple, select one), $S\_2$ contains the rest of $S$. It's intuitively correct but I can't prove it.

# Answer
> 4 votes
Your algorithm is correct. The following is its proof of correctness.

Let $S\_1$ and $S\_2$ be the optimal partitions of $S$. Let their medians be $m\_1$ and $m\_2$. Let the maximum element is $M$ that belongs to $S\_1$ (without loss of generality). Let $m$ is the median of $S\_1 \cup S\_2 \setminus \\{M\\}$. Then, we can show that the value $M + m$ is at least $m\_1+m\_2$.

**Proof:** When we merge the sets: $S\_1 \setminus \\{M\\}$ and $S\_2$. Then, in $S\_1 \cup S\_2 \setminus \\{M\\}$, there are at least $\lfloor |S\_1|/2 \rfloor + \lfloor |S\_2|/2 \rfloor-1$ elements that are larger than $\min\\{m\_1,m\_2\\}$. Suppose there are at least $\lfloor |S\_1|/2 \rfloor + \lfloor |S\_2|/2 \rfloor$ elements larger than $\min\\{m\_1,m\_2\\}$; then, we are done. That is, $\lfloor |S\_1|/2 \rfloor + \lfloor |S\_2|/2 \rfloor \geq \lfloor (|S\_1|+|S\_2|-1)/2 \rfloor$, the median $m$ of $S\_1 \cup S\_2 \setminus \\{M \\}$ has value at least $\min\\{m\_1,m\_2\\}$. Since $M \geq \max\\{m\_1,m\_2\\}$. We get $m+M \geq m\_1 + m\_2$. Hence proved.

Therefore, let us assume that there are exactly $\lfloor |S\_2|/2 \rfloor + \lfloor |S\_2|/2 \rfloor-1$ elements that are larger than $\min\\{m\_1,m\_2\\}$. Let us make some cases:

Case 1: $|S\_1|$ and $|S\_2|$ are odd. In this case, there are always $\lfloor |S\_2|/2 \rfloor + \lfloor |S\_2|/2 \rfloor$ elements with value larger than $\min\\{m\_1,m\_2\\}$. So we are done.

Case 2: $|S\_1|$ and $|S\_2|$ are even. Let $m\_1 = \frac{(l\_1+r\_1)}{2}$ and $m\_2 = \frac{(l\_2+r\_2)}{2}$ such that $l\_1,r\_1$ are middle elements of $S\_1$, and $l\_2,r\_2$ are middle elements of $S\_2$. Note that in $S\_1 \cup S\_2 \setminus \\{M\\}$, there are at least $\lfloor |S\_1|/2 \rfloor + \lfloor |S\_2|/2 \rfloor$ elements larger than $\min\\{l\_1,l\_2\\}$. Therefore, observe that the median $m$ is at least $\max\\{l\_1,l\_2\\}$ or $\min\\{r\_1,r\_2\\}$. Since $M \geq \max\\{r\_1,r\_2\\}$, it is easy to see that $m+M$ is at least $\frac{(l\_1+r\_1)}{2} + \frac{(l\_2+r\_2)}{2} = m\_1 + m\_2$. Hence proved.

Case 3: $|S\_1|$ is odd and $|S\_2|$ is even. Let $m\_2 = \frac{(l\_2+r\_2)}{2}$ such that $l\_2,r\_2$ are middle elements of $S\_2$. Note that the median of $S\_1 \cup S\_2 \setminus \\{M\\}$ is either at least $m\_1$ or $\frac{(l\_2+r\_2)}{2}$ or $\frac{(l\_2+m\_1)}{2}$. Since $M \geq \max\\{m\_1,l\_2,r\_2\\}$, it is easy to see that $m+M$ is at least $m\_1+m\_2$ for each of the possible values of $m$. Hence proved.

Case 4: $|S\_1|$ is even and $|S\_2|$ is odd. It is similar to Case 3.

---
Tags: algorithms, greedy-algorithms, partitions
---


# Question
Title: Tower of Hanoi variation - Split into two towers of odd and even disks
Suppose we have three rods `A`, `B` and `C`, and rod `A` contains `n` disks (Exactly like the original Tower of Hanoi problem). The disks are numbered `1` to `n`, when the bottom disk is number `1` and the top disk is number `n`.

I want to build two towers: One on rod `B` which contains only the odd numbered disks and one on rod `C` which contains only the even numbered disks. The laws of disk moving is exactly like in the original problem.

I am trying to think if it is possible to solve it with only three rods, and if it is how can it be solved recursively.

I thought about moving the top two disks by hand (maybe depends on the parity of `n`) and then perform a recursive call, but I am not sure at all how to do it.

# Answer
> 1 votes
Let $T\_i$ be the tower defined by disks: $i,\dotsc,n$.

Here is a simple recursive algorithm:

```
Initialize i := 1
while(i != n+1)
    If i is even:
           move the tower T(i+1) on any rod other than C using the standard Tower of Hanoi algorithm.
           move disk i to rod C
    else:
           move the tower T(i+1) on any rod other than B using the standard Tower of Hanoi algorithm.
           move disk i to rod B
    i <- i+1
end

```

---
Tags: recursion, towers-of-hanoi
---


title: Is Desmos Turing-Complete?

text:
# Question
Title: Is Desmos Turing-Complete?
The graphing calculator Desmos has a ton of functions, and can express any arithmetric formula. What I want to know is, is it Turing-Complete?

Desmos supports, among other things:

* Most mathematical operations / functions
    + Multiplication, addition, subtraction, division, modulo, etc
    + Sum and product
    + Integration and differentiation
* Variables
* Non-recursive functions
* Actions, basically functions that modify the global state
* Conditionals

However, the global state is *static* \- Actions and user interaction are the only thing that can modify this.

The only way of looping is through the ticker, a recent feature that executes an action at set intervals. For example, this calculates the factorial through looping, by multiplying a by b and decrementing b until b is 0. Multiple actions can be put in the ticker, separated by commas.

# Answer
> 14 votes
I tried various things with Desmos and came to the following conclusions:

### Desmos *without Actions* is not Turing-complete.

* All built-in functions are halting (basically since they are mathematical in nature).
* Variable assignment is halting. (A variable can hold either a number or a list of numbers, nothing else.)
* All function definitions are halting. Recursive definition is not allowed, so I tried to simulate something like a fixed-point combinator, but a function parameter can only be a number or a list (function is not allowed) so this is impossible.
* A conditional in Desmos is officially called a *piecewise function* which is in the form of `{cond1:value1, cond2:value2, [default]}`. All branches should evaluate to a number or a list, and they are evaluated eagerly. No means to introduce a loop here.
* You can introduce a bounded loop on a variable in the form of (min, max, step). But both min and max should be a finite number, and setting step to 0 does not actually set the step size to zero. Therefore, you cannot introduce an infinite loop using this feature.

Therefore, any "program" in Desmos without Actions always halts, which means it is not TC.

**Edit:** @pVC noted that a slider can be infinitely increasing. I haven't been able to reproduce it, but its addition does not change the conclusion since it does not allow any kind of global state to be shared between each iteration (without Actions, we don't have any global variables we can modify within each iteration). It is trivially impossible to make the loop halt, and again the Halting problem is solved.

### Desmos *with Actions* is Turing-complete.

(Side note: ~~Using Actions requires a registered account.~~ The doc says so, but apparently it's not.)

The most important feature that matters here is **Tickers**, which adds the ability to introduce an infinite loop. It is *almost* thoroughly documented, but a crucial piece that is missing is that, if you use a piecewise function with actions as branches and omit the default branch, the entire simulation halts when it hits the default branch.

This, combined with the support for numbers and lists, is enough to easily simulate some of the minimalist TC languages such as

* Tag system, especially a version with an explicit halt symbol
    + Example: Set the ticker action to `{s[1]=1: s->join(s[3...],[2,2,1,0]), s[1]=2: s->join(s[3...],[2])}` with the initial condition of `s` being a list of 1 and 2's
* FRACTRAN
    + Example: Set the ticker action to `{mod(f,2)=0: f->3f/2, mod(f,3)=0: f->2f/3}` with the initial condition of `f` being a positive integer
    + Works only theoretically, because Desmos uses JS numbers under the hood which has limited precision (which is why I included tag systems as a more concrete proof)

Therefore Desmos with Actions is TC.

# Answer
> 3 votes
This may be an old topic but using regressions you can repeatedly redefine variables (I think it's 60FPS).

Basic tutorial:

Step 1:

copy and paste this into a new desmos session:

```
v_{ariable}=0
V_{ariable}~v_{ariable}+1

```

Step 2:

copy and paste this into both slider bounds of `v_{ariable}=0`:

```
V_{ariable}

```

Step 3:

Press play on what is now `v_{ariable}=1`

Example of usage: https://www.desmos.com/calculator/vtogi0kp5t

More information: https://www.reddit.com/r/desmos/wiki/regression\_bug

---
Tags: turing-completeness
---


# Question
Title: Are there any operating systems that utilize only user threads?
We're going over threading models in my freshman CS class. Are there any examples of operating systems that use exclusively user threads (N:1)? It looks like 1:1 is far and away the most common model but I wanted to see live examples of this other model. Google had been inconsistent and it seems a lot disagree on which actually is user thread based or not. As best as I can tell it hasn't been used in years.

Any programs or languages that utilize user threads count too.

All help appreciated! Thank you!

# Answer
There might be some research OS's for embedded systems that use only user threads, but I'm not aware of any production systems right now. The challenge is that you can't get security/isolation for multiple users with user threads (at least, not without a lot of extra work, like using software fault isolation and more).
> 1 votes

---
Tags: operating-systems, process-scheduling, threads, os-kernel, multi-tasking
---


title: External consistency vs linearizability

text:
# Question
Title: External consistency vs linearizability
In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes:

> One subtle thing about Spanner is that it gets serializability from locks, but it gets **external consistency** (similar to **linearizability**) from TrueTime \[*emphasis added*\].

What is the definition of *external consistency*, and how does it differ from *linearizability*?

# Answer
When mentioning "external consistency", Brewer references B. Liskov. Practical Uses of Synchronized Clocks in Distributed Systems. ACM Principles of Distributed Computing (PODC). Montreal, Canada, August 1991.

Liskov, in term, references Gifford D.K. Information Storage in a Decentralized Computer System. Technical Report CSL-81-8, Xerox Corporation, March, 1983

Here's how Gifford defines external consistency:

> External consistency guarantees that a transaction will always receive current information. Using the concepts we have just introduced, we can provide a formal definition of external consistency. The actual time order in which transactions complete defines a unique serial schedule. This serial schedule is called the *external schedule*. A system is said to provide external consistency if it guarantees that the schedule it will use to process a set of transactions is equivalent to its external schedule.

As @Oleg mentions, this sounds like strict serializability.
> 1 votes

# Answer
External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document:

> For any two transactions, $T\_1$ and $T\_2$ (even if on opposite sides of the globe): if $T\_2$ starts to commit after $T\_1$ finishes committing, then the timestamp for $T\_2$ is greater than the timestamp for $T\_1$.
> 13 votes

# Answer
There is a distinction between external consistency and strict serializability. I wrote a comment on it here https://stackoverflow.com/questions/60365103/differences-between-strict-serializable-and-external-consistency/65853495#65853495.

The difference is that strict serializability imposes no order on concurrent transactions, whereas external consistency does (the order in which they commit).
> 3 votes

# Answer
You can think about external consistency from transactions (Tx) isolation and order point of view. In Tx isolation speak the external consistency is equivalent to the strict serializable isolation, where 'strict' is the real-time constraint part (as in linearizability).

That again all means that to a system client observable Tx side effects are equivalent to a system, where all Tx take place in isolation without any concurrency and where their real-time ordering, as seen by the client, is preserved. More importantly this same ordering is seen by any other unrelated client.

Read more about the distinction at this blog.
> 2 votes

# Answer
To my limited understanding there is not much differency bw external consistency and linearizability:

Definition of linearizability \[1\] is

> 1. The extended list can be re-expressed as a sequential history (is serializable).
> 2. That sequential history is a subset of the original unextended list.

And 2. means:

> If an operation op1 completes (gets a response) before op2 begins (invokes), then op1 precedes op2 in history.

And that is what exactly Google calls external consistency \[2\]:

> For any two transactions, T1 and T2 (even if on opposite sides of the globe): if T2 starts to commit after T1 finishes committing, then the timestamp for T2 is greater than the timestamp for T1.

Replace op with tx, response with commit and here we are. They seem to be essentially the same.

\[1\] https://en.wikipedia.org/wiki/Linearizability
\[2\] https://storage.googleapis.com/pub-tools-public-publication-data/pdf/45855.pdf
> 0 votes

---
Tags: distributed-systems
---


# Question
Title: Can I use the CYK-Algorithm for a Grammar where all results still have a Variable in them?
Let the Grammar be G = ({S}, Σ, P, S), where Σ = {⟨,⟩,\[,\]} and

```
P: S → ⟨S⟩, [S], SS, ε
[⟨ → ⟨[

```

Can I still use the CYK-Algorithm and if yes then how would I do it for a word like ⟨\[\]⟩ ?

# Answer
> 1 votes
the Grammar is not context-free and thus the CYK -Algorithm wont work

---
Tags: context-free
---


title: bellman ford and one surprizing fact

text:
# Question
Title: bellman ford and one surprizing fact
I ran into a very surprising local contest problem.

> after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex **v** being updated, then **v** is on negative cycle.

there is very easily counterexample that the above sentence is false, but two times asking from my instructor, he told me this is true. what is the trick here?

# Answer
> 1 votes
You are right that this statement is not correct. Since, especially, $t$ will potentially be updated after $n$ iterations.

A correct statement is that if a vertex $v$ gets updated after the $n$ first rounds, then there is a path from $s$ to a negative cycle $C$ that ends in $v$.

To *find* a negative cycle, you start from $v$ (the vertex that gets updated in the $n+1$st round) and go backwards (in the dp table) until you reach a vertex $u$ twice. The path between the two occurrences of $u$ is a constitutes a negative cycle.

---

In your example, if $t$ gets updated, then you follow backwards $t \leftarrow v \leftarrow u \leftarrow v$, and the negative cycle is $C = \langle v, u, v\rangle$.

---
Tags: algorithms, data-structures, trees, shortest-path, discrete-mathematics
---