# Question
Title: Does immutability in functional programming really exist?
Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property of functionally languages is that **data structures are immutable**. For me this alone raises a lot of questions. But first I will write a bit of what I understand of immutability and if I'm wrong, feel free to correct me.

**My understanding of immutability:**

* When a program starts it has fixed data structures with fixed data
* One can't add new data to these structures
* There are no variables in the code
* You can merely "copy" from the already data or currently calculated data
* Because of all above, immutability adds huge space complexity to a program

**My questions:**

1. If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?
2. What is the point in having a program that can't get new data? Say you have a sensor attached to your computer that wants to feed data to the program. Would that mean that we can't store the incoming data anywhere?
3. How is functional programming good for machine learning in that case? Since machine learning builds from the assumption of updating the program's "perception" of things - thus storing new data.

# Answer
> When a program starts it has fixed data structures with fixed data

This is a bit of a misconception. It has a fixed form and a fixed set of rewrite rules but these rewrite rules can explode into something much larger. For instance the expression \[1..100000000\] in Haskell is represented by a very small amount of code but its normal form is massive.

> One can't add new data to these structures

Yes and no. The purely functional subset of a language like Haskell or ML can't get data from the outside world but any language for practical programming has a mechanism for inserting data from the outside world into the purely functional subset. In Haskell this is done very carefully but in ML you can do this whenever you want.

> There are no variables in the code

This is pretty much true but don't confuse this with the idea that nothing can be named. You name useful expressions all the time and constantly reuse them. Also both ML and Haskell, every Lisp I have tried, and hybrids like Scala, all have a means of creating variables. They just are not commonly used. And again the purely functional subsets of such languages don't have them.

> You can merely "copy" from the already data or currently calculated data

You can perform calculation by reduction to normal form. The best thing to do is probably to go write programs in a functional language to see how they do in fact perform calculations.

For instance "sum \[1..1000\]" is not a calculation I want to perform but it is quite handily done by Haskell. We gave it a small expression that had meaning to us and Haskell gave us out the corresponding number. So it definitely performs calculation.

> If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?

You don't add a new item to a list, you create a new list out of the old one. Because the old one can't be mutated it is perfectly safe to use it in the new list, or whereever else you want. Much more data can be safely shared in this schema.

> What is the point in having a program that can't get new data? Say you have a sensor attached to your computer that wants to feed data to the program. Would that mean that we can't store the incoming data anywhere?

As far as user input goes, any practical programming language has a way of getting user input. This happens. However there is a fully functional subset of these languages that you write most of your code in and you reap the advantages in this way.

> How is functional programming good for machine learning in that case? Since machine learning builds from the assumption of updating the program's "perception" of things - thus storing new data.

This would be the case for active learning but most machine learning I have worked with (I work as a code monkey in a machine learning group and have done so for a few years) has a one time learning process where all the training data is loaded in at once. But for active learning you can't do things 100% purely functionally. You are going to have to read in some data from the outside world.
> 11 votes

# Answer
Immutability or mutability are not a concepts that make sense in functional programming.

## The computational context

This is a very good question that is an interesting follow up (not a duplicate) to another recent one: What is the difference between assignment, valuation and name binding?

Rather that replying to your statements one by one, I am trying here to give you a structured overview of what is at stakes.

There are several issues to be considered to answer you, including:

* What is a model of computation, and what concepts make sense for a given model
* What is the meaning of the words you are using, and how does it depend on the context

Functional programming style seems silly because you see it with an imperative programmer eye. But it is a different paradigm, and your imperative concepts and perception are alien, out of place. The compilers have no such prejudices.

But the end conclusion is that it is possible to write programs in a purely functional way, including for machine learning, thought functional programming does not have the concept of storing data. I seem to disagree on this point with other answers.

In the hope a few will be interested despite the length of this answer.

## Computational paradigms

The question is about functional programming (aka applicative programming), a specific model of computation, whose theoretical and simplest representative is the lambda calculus.

If you stay at a theoretical level, there are many models of computation: the Turing machine (TM), the RAM machine and others, the lambda calculus, combinatory logic, recursive function theory, semi-Thue systems, etc. The more powerful computational models have been proved equivalent in terms of what they can address, and that is the gist of the Church-Turing thesis.

An important concept is reducing models to each other, which is the basis for establishing the equivalences that lead to the Church-Turing thesis. Seen from a programmers perspective, reducing one model to another is pretty much what is usually called a compiler. If you take logic programming as your model of computation, it is quite different from the model provided by the PC you bought in a store, and the compiler does translate programs written in logic programming language to the computational model represented by your PC (pretty much the RAM computer).

However, it does not mean that the two models do things the same ways, or that a concept meaningful for one can be transferred as such to another. Typically, a computation step in a TM has little relation to a ($\beta$-)reduction step in Lambda Calculus, though they are inter-translatable. The concept of optimal evaluation of lambda expression is quite remote from complexity issues in TM models.

In practice, the programming languages that we use tend to mix concepts from different theoretical origins, trying to do it so that selected parts of a programs can benefit from the properties of some model where appropriate. Similarly, people building systems may choose different languages for different components, to best suit the language to the task at hand.

Hence, you seldom see a programming paradigm in a pure state in a programming language. Programming languages are still classified according to the dominant paradigm, but properties of the language may be affected when concepts from other paradigms are involved, often blurring distinctions and conceptual issues.

Typically, languages like Haskell and ML or CAML are considered functional, but they can allow for imperative behavior ... Else why would one talk of the "*purely functional subset*"?

Then one can claim that, you can do this or that in my functional programming language, but it is not really answering a question on functional programming when it is relying on what can be considered extra-functional.

The answers should be more precisely related to a specific paradigm, without the extras.

## What is a variable?

Another problem is the use of terminology. In mathematics a variable is an entity that stand for an undetermined value in some domain. It is used for various purposes. Used in an equation, it may stand for whatever value such that the equation is verified. This vision is used in logic programming under the name of "*logical variable*", probably because the name *variable* already had another meaning when logic programming was developed.

In traditional imperative programming, a variable is understood as some kind of container (or memory location) that can memorise the representation of a value, and possibly get its current value replaced by another one).

In functionnal programming, a variable has the same purpose it does in mathematics as a place-holder for some value, yet to be provided. In traditional imperative programming this role is actually played by constant (not to be confused with *literals* which are determined value expressed with a notation specific to that domain of values, such as 123, true, \["abdcz",3.14\]).

Variables of whatever kind, as well as constant, may be represented by identifiers.

The imperative variable can have its value changed and that is the basis for mutability. The functional variable cannot.

Programming languages usually allow for larger entities to be build from the smaller ones in the language.

Imperative languages allow for such constructs to include variables and that is what gives you mutable data.

## How to read a program

A program is fundamentally an abstract description of your algorithm is some language, whether a pragmatic design, or a paradigmatically pure language.

In principle, you can take every statement for what it is supposed to mean abstractedly. Then the compiler will translate that to some appropriate form for the computer to execute, but that is not your problem in first approximation.

Of course, reality is a bit harsher, and it is often good to have some idea of what happens so as to avoid structures that the compiler will not know how to deal with for efficient execution. But that is already optimization ... which compilers can be very good for, often better than programmers.

## Functional programming and mutability

Mutability is based on the existence of imperative variables that can contains values, to be changed by assignment. Since these do not exist in functional programming, everything can be seen as immutable.

Fuctional programming deals exclusively with values.

Your first four statements on immutability are mostly correct, but describe with imperative view something that is not imperative. It is a bit like describing with colors in a world where every one is blind. You are using concepts that are alien to functional programming.

You have only pure values, and an array of integers is a pure value. To get another array that differs only in one element, you have to use a different array value. Changing an element is just a concept that does not exists in this context. You may have a function that has an array and some indices as argument, and returns a result that is an almost identical array which differs only where indicated by the indices. But it is still an independent array value. How are these value represented is not your problem. Maybe they "share" a lot in the imperative translation for the computer ... but that is the compiler's job ... and you do not even want to know for what kind of machine architecture it is compiling.

You do not *copy* values (it make no sense, it is an alien concept). You just use values that exist in the domains you have defined in your program. Either you describe them (as literals) or they are the result of applying a function to some other values. You can give them a name (thus defining a constant) to make sure the same value is used in different places in the program. Note that function application should not be perceived as a computation but as the result of the application to the given arguments. Writing `5+2` or writing `7` amounts to the same. Which is consistent with the previous paragraph.

There are no imperative variables. No assignment is possible. You can bind names to values only (to form constants), unlike imperative languages where you can bind names to assignable variables.

Whether that has a cost in complexity is totally unclear. For one thing, you reference to complexity concerns imperative paradigms. It is not defined as such for functional programming, unless you choose to read your functional program as an imperative one, which is not the intent of the designer. Indeed the functional view is intended to let you not worry about such issues and concentrate on what is being computed. It is a bit like specification versus implementation.

The compiler has to take care of implementation, and to be smart enough to best adapt what is to be done to the hardware that will do it, whatever it is.

I am not saying programmers never worry about that. I am also not saying that programming languages and compiler technology are as mature as we might wish them to be.

## Answering the questions

1. You do not modify existing value (alien concept), but compute new values that differ where desired, possibly by having one extra element it it is a list.
2. The program can get new data. The whole point is how you express that in the language. You can for example consider that the program works with one specific value, possibly unbounded in size, which is called the input stream. It is a value that is supposed to be sitting there (whether it is already known fully or not is not your problem). Then you have a function that returns a pair composed of the first element of the stream, and the rest of the stream.

You can use that to build networks of communicating components in a purely applicative way (coroutines)
3. Machine learning is just another problem when you have to accrete data and modify values. In functional programming you do not do that: you just compute new values that differ appropriately according to the training data. The resulting machine will work as well. What you worry about is computing time and space efficiency. But, again, that is a different issue, that ideally should be dealt with by the compiler.

## Final remarks

It is quite clear, from the comments or the other answers, that practical functionnal programming languages are not purely functional. That is a reflection on the fact that our technology is still to be improved, especially where compiling is concerned.

Is it possible to write in a purely applicative style? The answer has been known for about 40 years and it is "yes". The very purpose of denotational semantics as it appeared in the 1970's was precisely to translate (compile) languages into purely functional style, deemed better understood mathematically and thus considered a better fundation to define the semantics of programs.

The interesting aspect ot it is that imperative programming structure, including variables, can be translated into a functional style by introducing appropriate domains of values, such as a data store. And despite the functional style, it remains surprisingly similar to the code of actual compilers written in imperative style.
> 6 votes

# Answer
Let me answer one of your not fully addressed points:

> Because of all above, immutability adds huge space complexity to a program

You're kinda right on the concern over immutability adding huge space complexity. Let me tackle that point.

It's true that constantly creating new data structures instead of mutating existing ones has the potential to consume more memory overall. However, FP languages and libraries are designed with this in mind and use some clever solutions like ***persistent data structures*** to efficiently reuse memory and limit copying. Only the modified parts of the structures get copied, the rest is shared - similar to a ***Git branching model***. This keeps the memory overhead low.

The functional approach also lends itself well to aggressive caching of interim results, reducing re-computation needs that could increase memory usage. There are also functional data types like `lenses` and `zippers` that provide memory efficient ways to derive new updated structures. So while naively creating all new data on each change would be wasteful, persistent data structures and caching in functional programming are optimized to maintain space efficiency. So:

> **The benefits of immutable data in correctness, concurrency and state** **management are viewed as worth the extra effort to keep space** **complexity tight.**
> 2 votes

# Answer
It is a misconception that functional programs can't store data, and I don't think Jakes answer really explained this very good.

Functional programs are, like any programs, really functions mapping integers to integers. Any imperative program operating on mutable data structures have a functional counterpart. This is just another means of achieving the same end.

The functional way of storing experiment data from some source would be calling the storing function with the data structure as argument and outputting a concatenation of the existing data structure and the new data and thus data is stored without the notion of mutable data structures.

**From my own experience**, I think the concept of immutable data structures are leading conventional developers to think that there are certain things that are impractical or even impossible to do in a functional setting. This is not the case.
> 0 votes

---
Tags: data-structures, functional-programming
---


title: Subset ${\tt XOR}$ problem

text:
# Question
Title: Subset ${\tt XOR}$ problem
**Motivation.** This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation.

**Problem.** Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset $S\subseteq X$ such that the the bitwise ${\tt XOR}$ of the members of $S$ is $0$ everywhere.

For example, et $n = 4$ and consider

* $x\_0 = {\tt 1 0 0 1}$
* $x\_1 = {\tt 0 1 0 1}$
* $x\_2 = {\tt 0 0 0 1}$
* $x\_3 = {\tt 1 1 0 0}$.

Then the bitwise ${\tt XOR}$ of $S = \\{x\_0, x\_1, x\_3\\}$ is ${\tt 0000}$.

**Question.** This problem is clearly in ${\bf NP}$ as it is easy to check a proposed solution. Is it ${\bf NP}$-complete?

# Answer
The problem is in $P$. It can be solved in polynomial time with Gaussian elimination.

Build a $n\times n$ boolean matrix $M$, whose $i$th row is the $i$th bit-string in $X$. All arithmetic will be modulo 2 (i.e., in $GF(2)$). Solve for a bit-string $v$ such that $Mv=0$ (and $v \ne 0$). Such a bit-string, if it exists, can be found using Gaussian elimination, as this is a system of $n$ linear equations in $n$ unknowns. Finally, any such bit-string $v$ yields a solution to your problem; the set $S$ includes the $i$th bit-string of $X$ iff $v\_i=1$.
> 3 votes

---
Tags: np-complete, np, subset-sum, xor
---


title: Why is TCP known as reliable protocol?

text:
# Question
Title: Why is TCP known as reliable protocol?
Is it because it uses 3 way handshaking, it is reliable? Or is it due to other reasons? Like due to congestion control, flow control and error control in TCP? Why do we call TCP as reliable?

# Answer
> 8 votes
TCP is said to be reliable because when an application receives data, it knows that this is exactly the data that the sender sent. No part of the data was lost, reordered, etc.

Error control is the part of TCP that deals with ensuring the reliability of connections. For example, if the sender sends two packets A and B and the receiver received only B, the TCP implementation on the receiver side will wait a little in case A took longer than B to arrive. If A finally arrives, the receiver will release A to the application before B. If A doesn't arrive after a while, the receiver will transmit a request to the sender to retransmit A. (I am simplifying somewhat, see the specification for details.)

This is not related to congestion and flow control. They help the performance of the network, but they aren't needed or helpful to make a connection reliable.

# Answer
> 5 votes
Welcome to CS Stack Exchange!
Unlike UDP, TCP provides reliable message delivery.
To summarize in some points, we can say that:

* TCP ensures that data is *not damaged*, lost, duplicated, or delivered out of order to a receiving process, otherwise, it has to recover it.
* TCP is *connection-oriented* and enables two-way communication between two endpoints after the three-way handshake.
* TCP is reliable because the protocol ensures that all *data is fully transmitted* and can be assembled by the receiver **in the correct order**.
* TCP achieves this reliability by assigning a *sequence number* to each octet it transmits and requiring a positive acknowledgment (ACK) from the receiving TCP. If the ACK is not received within the time-out interval, the data is retransmitted. The TCP retransmission time-out value is dynamically determined for each connection, based on round-trip time. **At the receiver**, the sequence numbers are used to correctly order segments that may be received out of order and to eliminate duplicates. Damage is handled by adding a *checksum* to each segment transmitted, checking it at the receiver, and discarding damaged segments.

For more detailed informations, I suggest you have a look at the specific chapter in the book "Computer Networks" by A. Tanenbaum

# Answer
> 2 votes
Most people call TCP lossless and reliable because of error handling in the protocol.

Every packet exchanged in TCP are sent with a CRC32 hash of the data within. It is trivial to compute a CRC32. It is even more trivial to determine if the CRC32 is the right one after the packet has been sent.

For example here's a document I use as a remainder of how CRC32 are calculated for network. At first I calculate a CRC-8 then I do the CRC32 of the letter I.

```
CRC: x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

0001 0000 0100 1100 0001 0001 1101 1011 0111  : Polynomial in binary form
 1     0   4    c    1     1    d    b    7

CRC-8: x8 + x7 + x6 + x4 + x2 + 1

1 0000 0111 : CRC-8 polynomial
I: 0100 1001

0100 1001 0000 0000
1000 0011 1
___________________
1100 1010 1000 0000
1000 0011 1
___________________
0100 1001 0000 0000
 100 0001 11
 __________________
 000 1000 1100 0000
     1000 0011 1
     ______________
     0000 1111 1000
            F    8

E: 0100 0101, result : 0xDC

0100 0101 0000 0000
1000 0011 1
___________________
1100 0110 1000 0000
1000 0011 1
___________________
0100 0101 0000 0000
 100 0001 11
 __________________
 000 0100 1100 0000
      100 0001 11
      _____________
      000 1101 1100
            D    C

I: 0100 1001  CRC-32 of letter I

1001 0010 0000 0000 0000 0000 0000 0000 0000 0000  1)Reverse input bits and 2)append 32 zeros
1111 1111 1111 1111 1111 1111 1111 1111            3)XOR with 32 ones
_________________________________________________
0110 1101 1111 1111 1111 1111 1111 1111 0000 0000  4)Do CRC32 calcs
 100 0001 0011 0000 0100 0111 0110 1101 11         CRC-32 polynomial
 ________________________________________________
 010 1100 1100 1111 1011 1000 1001 0010 1100 0000
  10 0000 1001 1000 0010 0011 1011 0110 111
  _______________________________________________
  00 1100 0101 0111 1001 1011 0010 0100 0010 0000
     1000 0010 0110 0000 1000 1110 1101 1011 1
     ____________________________________________
     0100 0111 0001 1001 0011 1100 1001 1001 1000
      100 0001 0011 0000 0100 0111 0110 1101 11
      ___________________________________________
      000 0110 0010 1001 0111 1011 1111 0100 0100  Remainder
          1111 1111 1111 1111 1111 1111 1111 1111  5)XOR remainder with ones
          _______________________________________
          1001 1101 0110 1000 0100 0000 1011 1011  Result
          1101 1101 0000 0010 0001 0110 1011 1001  6)Reverse result
           D     D    0    2   1     6    B   9   -> What is actually sent with the packet

```

For TCP there exists several packet types like ACK packets which are used to acknowledge packets have been received. There also exists error packets which should either end a transmission or reset the transmission (make a new handshake etc). TCP is known as a connected protocol as opposed to UDP which is connection-less and can be lossy.

# Answer
> 1 votes
The primary purpose of flow control is to prevent overwhelming the receiver with packets. So imagine the sender is fast and the receiver for whatever reason is slow to process the received data, then using flow control, the receives can slow down the sender. If the receiver would not slow down the sender, eventually the receiver needs to drop packets.

The primary purpose of congestion control is similar to that of flow control. The difference is that the network is the one being protected from overload. Imagine there is a super-fast sender and a super-fast receiver, but with a slow network switch between them, then congestion control will prevent the switch from being overloaded. Overload leads to packet loss.

Packet loss is a problem due to head of line blocking. So you can't process packets that follow after a dropped packet. This leads to a performance degradation in the connection.

Both flow control and congestion control, control the size of the window if inflight data. Effectively the size of the window is the minimum of the congestion window and the receive window.

Flow control and congestion control do not make a TCP connection reliable. The primary purpose is to obtain maximum performance without running into congestion which could eventually lead to congestion collapse if not dealt with correctly.

# Answer
> 1 votes
It's interesting to note that while the protocol is called "reliable" you can't build a system with guaranteed data delivery with it. It looks like it can be said it's *receiver reliable*, since receiver always receives the exact data the sender sent (checked through checksumming) in correct order (achieved through sequence numbers) but it doesn't have a way to know that *all* data is received, that is left to higher level protocol (usually called application layer). So for sender to achieve actual *reliability* it must wait for some kind of confirmation from receiver (e.g. HTTP/SMTP responses) meaning as it is it can't be called *sender reliable*.

Interesting read on the topic: why you can’t build a reliable TCP protocol without app-level acks…

---
Tags: computer-networks
---


title: Time complexity of tree algorithm

text:
# Question
Title: Time complexity of tree algorithm
I'm new to recurrence relations and master theorem so trying to learn. Say there's an algorithm $A$ whose input is the root of a binary tree $T$. $A$ recurses so that it's called on each and every node in $T$ exactly once. The time complexity of $A$ called on a node $X$ is $O(number\\:of\\:nodes\\:in\\:subtree\\: rooted\\:at\\:X)$.

What's the overall big O time complexity of $A$ (probably in terms of $N$, the total number of nodes in $T$)?

My (informal) approach is to imagine $T$ as a maximally imbalanced tree (single line of nodes straight down). Then the time complexities of the nodes starting from root is $N$, $N-1$, .... $1$, of which there are $N$. That becomes $(N+1)\*(N/2) == N^2/2+N/2 == O(N^2)$.

However I'm not sure this holds for other types of binary trees (such as perfect). I'm struggling to come up with a formal approach.

I'm trying to use master theorem and believe the recurrence relation is $T(n) = 2T(n/2) + f(n)$.

$c\_{crit} = log\_2 2 = 1$.

Worst case of $f(n)$ is at root of $T$ which is $O(n)$, so $f(n) = O(n^c)$ gives $c = 1$, and thus it cannot be Case 1 or 3 because $c == c\_{crit}$. So it must be Case 2. But how do I determine the value of $k$ in $f(n) = \theta(n^{c\_{crit}}log^{k}n)$?

# Answer
> 3 votes
Note that the complexity of the algorithm depends on the tree $T$. For the maximally imbalanced tree, as you computed the complexity is $O(n^2)$. Another important observation is that the complexity on this particular type of tree is $\Omega(n^2)$.

If you take a perfectly balanced complete tree, then then the root node has cost $n$; nodes at level $1$ have costs at most $n/2$; and so on... If you sum up the costs, you get $n + 2 \cdot n/2 + 4 \cdot n/4 + \dots + n \cdot 1 = O(n \log n)$. Moreover, the complexity over this particular type of tree is $\Omega(n \log n)$.

Now, let us talk about any general tree. Any node of the tree has cost at most $n$. Suppose we assume this worst cost for every node in the tree, then the complexity is at most $n^2 = O(n^2)$. Simple! This complexity is tight for general tree, since you already showed a worst case example of a maximally unbalanced tree to be $\Omega(n^2)$.

---
Tags: complexity-theory, time-complexity, trees, recurrence-relation, master-theorem
---


# Question
Title: Binary logarithm of binary number using logic gates
I need to use logic gates to calculate the floor of binary logarithm of a binary number $x\_{n-1}, ..., x\_0$.

I know that this can be computed when I find the position of the most significant bit set to 1.

So how do I find this bit and return it's position using only binary logic gates (AND, OR, XOR, NOR, NAND, NOT)?

# Answer
You start by building a circuit for two input bits. It has two outputs: the position of the highest bit, either 0 or 1, and a bit indicating that the input is not zero. This is easy: The position is equal to bit 1 of the input, “non-zero” is bit 1 or bit 0.

Now you build a circuit with four input bits. You feed bits 3 and 2 into one two-bit circuit, and bits 1 and 0 into a second one. There are two bits for the bit position with a value from 0 to 3. The higher bit is set if the higher two bits are non-zero. The lower bit is equal to the position from the higher two bit circuit if it is non-zero, and taken from the lower two bit circuit otherwise. The inputs are non-zero if one of the two bit pairs is non-zero.

So if we have two 2-bit circuits C1 and C2, then pos1 = C1.nonzero, non-zero = C1.non-zero or C0.non-zero, and pos0 = (C1.nonzero and C1.pos) or (not C1.nonzero or C0.pos).

Now you build a circuit with eight input bits. Output is three bits position with a value 0 to 7 and a “nonzero” bit. Bits 7 to 4 go into one four-bit circuit, bits 3 to 0 into a second one. Again bit 2 of the position is taken from the non-zero bit of the first circuit, you OR the two non-zero bits together, and select the lower two bits from one of the two four bit circuits.

And then you create a 16, 32 and 64 bit circuit in the same way. So if you have 64 input bits, you need two 32-bit, four 16-bit, eight 8-bit, sixteen 4-bit, and thirty-two 2-bit circuits.
> 1 votes

# Answer
As pointed out in the comments, your question was already answered in Arithmetic network to compute floor of binary logarithm. If you turn that answer into a circuit diagram, it looks like this:

The 32 bit logarithm block shown here is build from two 16 bit logarithm blocks and a few extra gates. The AND-OR bank is simply a multiplexer. The output of the 0..15 sub-block is normally ignored (by the AND gates) unless the 16..31 sub-block produces an invalid result (input = output = all zeros, indicated by the zero flag). In this case, the output of the 0..15 sub-block becomes the overall output. The high bit (bit 4) of the overall output is set when any of bit 16..31 of the input is non-zero.
> 1 votes

---
Tags: circuits, arithmetic
---


# Question
Title: Usefulness of binary extension field GF(2^n)
The binary extension field, usually denoted as $\textsf{GF}(2^n)$ or $\mathbb{F}\_{2^n}$, is a finite field of characteristic 2.

> **Are there any applications of $\textsf{GF}(2^n)$ (or more broadly, $\textsf{GF}(p^n)$), for $n\>1$, in computer science?**

My impression is that most applications only require a sufficiently large domain. Therefore $\textsf{GF}(p)$ suffices. One exception is in cryptography: the design of some popular block ciphers uses binary extension fields. But more recent cryptographic designs seem to avoid $\textsf{GF}(2^n)$ operations.

# Answer
> 14 votes
$GF(2^n)$ is used in error correcting codes, in some elements of cryptography (e.g., message authentication with 2-universal hashing), and in the AES block cipher, which is very widely used.

# Answer
> 4 votes
There indeed aren't a lot of situations where *any* binary extension field would work but *no other* finite field would. In fact, I can't think of any off the top of my head. Usually, you either need a *specific* field (and often a specific representation of that field, as with AES) or you just need a finite field and any one of sufficient size can (at least theoretically) be used.

That said, in cases where any (sufficiently large) finite field would do, binary extension fields are often a convenient choice due to the fact that their elements map 1:1 to fixed-length bitstrings.

This makes converting binary data (which is what our computers store everything as) into field elements and back *very* easy and convenient, since you don't really have to *do* anything — you can just take any string of $n$ bits and say that it represents an element of $GF(2^n)$!

---

For example, Shamir's threshold secret sharing scheme was originally formulated over prime fields, but it works over any finite field. For computer implementation binary extension fields are usually preferred, with the most convenient choice often being $GF(2^8)$, since it allows you to share arbitrary byte sequences and keep the byte length of the shares equal to that of the secret string.

(The only major drawback of using $GF(2^8)$ is that it only allows at most 255 shares, since each share needs to be associated with a unique non-zero field element. Of course, if that's a problem, you can use $GF(2^{16})$ or $GF(2^{32})$ or even $GF(2^{256})$ instead and pad your secret with some extra bytes as needed.)

---
Tags: arithmetic, applied-theory
---


# Question
Title: When a CPU copies instructions from storage into RAM how does it jump to instructions no longer in RAM?
When a CPU needs to get more instructions from storage and copies them to RAM, how does the CPU jump to previous instructions that are no longer in the RAM? Would it have to copy the old instructions back into RAM?
I feel like that would take a very long time to do.

FOR EXAMPLE: this is storage xsxx xxax.
Pretend the "x" is a random instruction that doesn't matter. The RAM can hold 4 instructions but the program is 8 instructions long. The first four instructions are in RAM the CPU runs all of them and copies the last 4 into RAM from storage (SSD, ROM, or HDD). Now for example "a" is an instruction the makes the CPU jump back to the "s" which is in the old 4 instructions which is not in RAM anymore.
How would it do this?

# Answer
> 3 votes
You have many memory pages - thousands 20 years ago, possibly millions today.

When the next instruction is not in RAM, it is loaded for example from disk. Some other page of memory will be thrown out. However it is very, very unlikely that the page with the previous instruction is thrown out, because the OS will throw out pages that have not been used in a while, and the page with the previous instruction has been used nanoseconds ago. So the whole scenario is very, very unlikely to happen.

*If* that page had been thrown out, it would just be reloaded from disk. The OS has no problems handling multiple page faults in one instruction.

# Answer
> 0 votes
There seems to be a faulty premise in your question. Normally, old instructions remain in memory. They are not removed from memory.

If the virtual memory subsystem pages/swaps them out, it will page/swap them in when needed, just as with any other memory that is accessed.

---
Tags: computer-architecture, cpu, paging, storage, memory-hierarchy
---


title: How to simulate a die given a fair coin

text:
# Question
Title: How to simulate a die given a fair coin
Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate integers $k,m$, such that $2^k = 6m$. So after flipping the coin $k$ times, we map the number encoded by the k-length bitstring to outputs of the die by dividing the range $\[0,2^k-1\]$ into 6 intervals each of length $m$. However, this is not possible, since $2^k$ has two as its only prime factor but the prime factors of $6m$ include three. There should be some other simple way of doing this, right?

# Answer
To have a slightly more efficient method than the one pointed out by @FrankW but using the same idea, you can flip your coin $n$ times to get a number below $2^n$. Then interpret this as a batch of $m$ die flips, where $m$ is the largest number so that $6^m \< 2^n$ (as already said, equality never holds here). If you get a number greater or equal to $6^m$ you must reject the value and repeat all $n$ flips.

You can implement a function which returns a single die flip by making $n$ coin flips and then cache the result for the following $m-1$ die flip requests.

The interesting point is that some values of $n$ are better than others because they have a less rejection rate. Here is a list of good values (i.e. values which have lower rejection rate than the previous ones):

```
n m r
3 1 0.25
8 3 0.15625
13 5 0.05078125
44 17 0.0378308072686
75 29 0.0247036782182
106 41 0.0113974522704
243 94 0.00933096248381
380 147 0.00726015308463
517 200 0.00518501504347
654 253 0.00310553931213
791 306 0.00102171682348

```

obtained with the formulas: $$ m = \lfloor {n\log\_3 2} \rfloor \\ r = 1 - \frac{3^m}{2^n}$$.

The first row corresponds to the answer of @FrankW with a reject rate of 25%. The following numbers are nice: $n=8$ and $n=13$ can both be kept in a single integer static variable. In particular the reject rate of $n=13$ is only 5% which is a sensible improvement with respect to 25% and makes this a good candidate for a possible implementation.
> 12 votes

# Answer
What you can do, is to employ a method called rejection sampling:

* Flip the coin 3 times and interpret each flip as a bit (0 or 1).
* Concatenate the 3 bits, giving a binary number in $\[0,7\]$.
* If the number is in $\[1,6\]$, take it as a die roll.
* Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.

Since $\frac 68$ of the possible outcomes lead to termination in each set, the probability of needing more than $l$ sets of flips to get a die roll is $(1-\frac 68)^l = \dfrac 1{4^l}$. Hence, this method is efficient in practice.

Improvements:

@Angel's answer points out, that the number of coin flips in each set but the first can be reduced from 3 to 2, by using the distinction between a $0$ and a $7$ as the first bit for the next set.

@Emanuele Paolini explains, how you can reduce the number of rerolls, if you need multiple die rolls.
> 29 votes

# Answer
An alternative to rejection sampling (as described in FrankW's answer) is to use a scaling algorithm, that takes into account an answer of \[7,8\] as if it was another coin flipping.

There is a very detailed explanation at mathforum.org, including the algorithm (its `NextBit()` would be flipping your fair coin).

The case for throwing a dice with a fair coin (sampling 2 → 6) is easier than the generic algorithm. You just take a failure (7 or 8) as another coin input and perform two more flips.
> 7 votes

# Answer
## A possibly simpler explanation of improved rejection sampling.

I am giving this explanation as it may hopefully help simplify understanding or analysis of probabilities in some situations.

FrankW suggests using rejection sampling, flipping the coin three times, keeping the result if it is in the right range, or repeating the three flips otherwise, until success.

Ángel suggests to save one flip on each trial, replacing it by a the binary choice remaining from the two unused values of the previous set of three.

This means really that one bit of information was produced with the first three flips, that did not need to be produced. More precisely, you should need to flip the coin only twice to know whether the current set of flips will be successful.

**Knowing whether the current set of flip will be successful is the only probability that matters**, since interpreting a successful set of flip is probability independent. **And this can be known before all the flips are completed** for that set.

This can be achieved in at least two ways, or more precisely in two different interpretations of the flips. There may be others.

**Grouping results in pairs**

The idea is to consider only three values (1,2), (3,4) and (5,6) represented by any three double-flip configurations, say TT, TH, HT. Then, you can apply rejection sampling with double-flips, repeating whenever you get the failure configuration HH.

Once you get one of the three successful configurations, you just flip the coin once more to decide whether you should take the first or the second value of the corresponding pair.

**Early detection of flip-set failure**

The idea is to use a slightly different reading of the three-flip configuration. If Head and Tail are interpreted as 1 and 0, then a configuration should correspond to the binary interpretation plus one. That is TTT (i.e. 000) corresponds 1, HTH (i.e. 101) corresponds 6, HHT (i.e. 110) and HHH (i.e. 111) corresponds to 7 and 8, or anything outside \[1,6\].

Then we know that the flip-set is succeeding or failing with only the first two flips. If they produce HH, the flip set fails independently of the last flip. So it can be skipped.

I think that *early detection* can always be used as an explanation, but depending on the number of faces on your simulated dice, failure detection may happen after a variable number of flips.

For example for a 10 faces dice you need in principle a flip set of 4 flips, with 6 configurations corresponding to failure. The trick is to have all the failure configurations at the high end of the sequence of binary values as follows:

```
TTTT  0000   1
HTTT  1000   9
HTTH  1001  10
HTHT  1001  11
HTHH  1011  12
HHTT  1100  13
HHHH  1111  16

```

Successful configurations correspond to range \[1, 10\] and failures to range \[11,16\].

Then you fail when the first two flips give HH, or when the first three give HTH, without having to even attempt the missing flips of the set.

If you do not fail, you just terminate the set of flips.
> 2 votes

# Answer
Another approach to simulate a roll of a dN using a dM (in the case of the specific question asked a d6 using a d2) is to partition the interval \[0, 1) into N equal intervals of length 1/N, \[0, 1/N), \[1/N, 2/N), ..., \[(N-1)/N, N).

Use the dM to generate a base-M fraction, 0.bbbb..., in \[0, 1). If that falls in \[(i-1)/N, i/N), take i as the roll of the dN. Note that you only have to generate enough base-M digits of the fraction to determine which interval it is in.
> 2 votes

# Answer
I came across this thread looking to validate if the solution I came up with with when my kids wanted to play a game requiring a die but one could not be found.

Take three coins and write numbers like this:

|  | Coin 1 | Coin 2 | Coin 3 |
| --- | --- | --- | --- |
| Head | 2 | 0 | 0 |
| Tail | 1 | 1 | 3 |

Flip the coins and add up the value, but reject if all heads or all tails. This prevents 2 and 5 from having two possible solutions. Should be fair, and doesn't require considering the coin order or doing any binary math. Easy enough for my 5 year old.

| Coin 1 | Coin 2 | Coin 3 | Sum |
| --- | --- | --- | --- |
| H - 2 | H - 0 | H - 0 | n/a |
| H - 2 | H - 0 | T - 3 | 5 |
| H - 2 | T - 1 | H - 0 | 3 |
| H - 2 | T - 1 | T - 3 | 6 |
| T - 1 | H - 0 | H - 0 | 1 |
| T - 1 | H - 0 | T - 3 | 4 |
| T - 1 | T - 1 | H - 0 | 2 |
| T - 1 | T - 1 | T - 3 | n/a |
> 2 votes

# Answer
I would flip the coin three times and interpret the outcome as a binary number, rejecting outcomes out of range.

For example, let heads be a 1 and tails be 0. If you flipped it three times and got heads, tails, heads, you'd have binary 101, which is 5 in decimal. HHT = 110b = 6. TTT = 000b = 0 and HHH = 111b = 7, both of which are out of range and would be rejected, and you would reflip for all the digits.
> 1 votes

# Answer
There are two well-known approaches to this. One is "rejection sampling". For example, use three bit to pick one out of six values, trying again for the two extra samples. Or use 14 bits (8192 values) to select 5 values from 1 to 6 (7776 possibilities), trying again in 13 out of 256 cases.

The other is using the decompression part of a compression / decompression algorithm: With arithmetic coding, a sequence of random values from 1 to 6 can be compressed with almost no redundancy. Generate the compressed sequence at random, and decompress it. This is a lot more complicated, but will practically not require any additional random numbers.
> 1 votes

# Answer
Sorry in advance if the explanation is superfluous. I wasn't sure how much detail to go in to or how easy the concept was to understand.

Say you have three coins (fair coins). If you incrementally assign a value to each side of each coin, you'll have six values.

Like so: On the first coin, heads is 1 and tails is 2. On the second coin, heads is 3 and tails is 4. On the third coin, heads is 5 and tails is 6.

Flipping the coins will leave you with a set of three numbers, your current set. Now, your current set will become your previous set and you will repeat the process to get a new set of three numbers.

Continue doing this until one and only one number matches from your current to previous set. That's your number.

So if you got \[ heads, tails, heads \] for the current set, that'd be \[ 1, 4, 5 \]. Now you flip them again and your current set is \[ 2, 4, 5 \]. Two matches. No good. Try it again. You get \[ 2, 3, 6 \]. Only one match. Your number is two.

There will be an equal chance that any given number will appear, but it's not particularly cost-effective, given that there's only a 3/32 change that any given pair of sets will be successful (only one match). So on average, the algorithm would have to repeat about ten times. Also, it's not easily generalizable to odd-numbered die.

At the very least, maybe it's food for thought. Very interesting question.
> 0 votes

# Answer
Unfortunately one cannot (faithfuly) simulate a (fair) die using (sequences of) fair coin(s).

Simply because the event space of a die has a dimensionality of $6$ and this cannot be exactly matched by a power of $2$ (which is what the event space of a fair coin provides).

But one can do this with a fair "tri-coin" (if such a term can be used). Meaning a coin with 3 outcomes. **And** a simple 2-coin, so the joint space of these 2 coins matches exactly the event space of the die.

Rejection sampling (as mentioned in some answers) may provide an **approximate** simulation indeed. But it will still have an amount of error or mis-match of probabilities (in finite time). So if one wants to actually match the event spaces of these 2 systems, there will be cases it will not work.

In probabilistic simulation (of which rejection sampling is an example), generated typical sequences do indeed exhibit the relative elementary probabilities (in this case the event space of a die). However (as mentioned in comments) **each of these typical sequences can contain arbitrarily long sub-sequences** of exactly the same outcomes. This means that in order to use rejection sampling (in some cases) either it can take arbitrarily long or the generated distribution will be biased (i.e not fair die), due to over-representation or under-representation of some parts of its event space. if this was not the case, then a deterministic algorithm would be possible which would exactly match the event spaces of a die and a coin (which do not match by dimensionality).
> 0 votes

# Answer
Take 6 coins. Each coin gets 1 point for tails, 2 points for heads. Dump out the coins and count up the total based on this idea.
> -1 votes

---
Tags: probability-theory, randomness, sampling
---


# Question
Title: What does the language of DFA of LR itemsets represent?
As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production.

With this $.$ we keep track of characters that compiler has seen yet, and continue to make states of these itemsets, which ultimately make a deterministic finite machine (DFA).

Formation of DFA is natural, as the compiler will visit the \*finite\* states \*deterministically\*.

My question is, \**what does the regular language of this DFA signify?\**

# Answer
For grammar $$ S \rightarrow Sa | b $$ The following represents the $LR(0)$ itemset and its finite automata. *(ignore the $ symbol)*

If every state is final state of the above $FA$, it would recognise $\\{\epsilon, b, S, Sa \\}$ , hence this is set of all **viable prefixes**, which are defined as *the prefixes of right sentential forms that can appear on the stack of a shift-reduce parser.*
> 1 votes

---
Tags: finite-automata, context-free, compilers
---


# Question
Title: Efficient way of computing average ALL function over matrix rows
Assume that a matrix $M\in \[0;1\]^{n\times d}$ is given, i.e., all values in the matrix are in the range 0 to 1. I would like to compute the following function for all rows of $M$:

$$ f(m\_1,m\_2,...,m\_d)=\frac{1}{n}\sum\_{i=1}^{n} \begin{cases}1 \quad \text {if} \quad M\[i,j\] \le m\_j \text{for all} j\\ 0\quad \text{else} \end{cases} $$ The input $m\_1,m\_2,...,m\_d$ is one row of $M$, and I would like to compute $f$ for all rows. Intuitively, $f$ computes the average number of rows for which it holds that all columns are smaller (or equal) than all columns of the input row.

This can be naively done by directly computing $f$ for $i\in 1,...,n$ but this would require a total of $\mathcal{O}(n^2\cdot d)$ computations.

**Question**: Is there a more efficient way of getting the result for all rows? For example, an algorithm that requires $\mathcal{O}(n\log n \cdot d)$ steps.

My gut feeling tells me this should be possible using dynamic programming because we can reuse several intermediate results of each call to $f$, but I don't know how.

# Answer
> 1 votes
Except in some special cases where $d$ is very small, I don't think there is any algorithm whose running time is noticeably better than $\mathcal{O}(n^2)$ (ignoring the dependence on $d$). In particular, I suspect one can prove a reduction showing that you can't do better than $\mathcal{O}(n^{2-\epsilon})$ unless the Strong Exponential Time Hypothesis (SETH) is false. Since SETH is an open conjecture, this would supply evidence that it won't be easy to exhibit an algorithm to substantially improve on the naive algorithm you've already gotten.

If $d$ is very large, I suspect you'll be able to get good results by a random linear project down to $d'=O(\lg n)$ dimensions.

Relevant reading: https://cstheory.stackexchange.com/q/37361/5038, https://algorithm-wiki.csail.mit.edu/wiki/Partial\_Match, https://stuff.mit.edu/afs/sipb/user/bert/debug/root/mit/jfc/tmp/subset%20queries.pdf.

---
Tags: dynamic-programming
---


# Question
Title: Splitting a Larger Unsigned Integer into Summable Parts
I have a very strange (arbitrary) problem that I have been trying to wrap my head around, but have been struggling to figure out how to accomplish this. I'll use Rust but in a pseudo-code fashion, these probably won't compile.

### Background

The library function takes a `&[u64]` (a slice/array/list of unsigned, 64-bit integers) and produces a `String` (byte array of utf-8 data), so the contract looks something like this:

```
pub trait Translator {
    fn translate(numbers: &[u64]) -> String;
}

```

Usage would look something like this:

```
let a: u64 = 1;
let b: u64 = 2;
let translated: String = TranslatorImpl::translate(&[a, b]);

```

The translation is lossless, so the output stored in `translated` can be converted back into a `&[u64]` without any loss of data. The data representation is *compact* so that it uses as little output data as possible to represent the input. I'm of course aware of hash functions, but I need the output to be as compact as possible, and I do not need cryptographic levels of collision resistance.

Lacking sufficient documentation, I assumed originally that the purpose of accepting a `&[u64]` was in order to allow passing arbitrarily-sized integers beyond 64-bits. However, the actual implementation details are that the input forms a nested "tree" (without ever having more than one child, so perhaps a linked-list is a better description), but the library contract is that a collision is impossible such that `&[x]` cannot produce the same value as `&[x, y]`. It can essentially be thought of as a filesystem path, e.g. `x/y/z`.

This being the case, my original understanding was incorrect, but I'd still like to proceed to try to solve this challenge.

### Problem

I'd like to be able to pass a `u128` (unsigned, 128-bit integer) to the library, but to do so in a way where the *sum* of the values of the `u64` array will equal the value of the 128-bit integer. I'd also like to be able to do this for any size of unsigned integer/any array of bytes. I can convert any integer in Rust to native/big/little-endian bytes, but I'll choose big-endian because it's typically used in networking. I'll also be using `u8` and `u16` (unsigned 8-bit/16-bit integers) in my example to prevent binary representations from being too long/difficult to read.

To make explaining this easier, here is a table of what binary values look like between `u8` and `u16`:

| Type | Value (Base-10) | Value (Binary) |
| --- | --- | --- |
| `u8` | `255` | `11111111` |
| `u16` | `255` | `00000000_11111111` |
| `u16` | `256` | `00000001_00000000` |
| `u16` | `257` | `00000010_00000000` |
| `u16` | `258` | `00000011_00000000` |

The max value, of course, that can be represented by a `u8` is `11111111` in binary, `255` in base-10. If I have a `u16` which is `255 + 1`, i.e. *just* beyond what a `u8` can represent, the binary pattern is `00000001_00000000`, `255 + 2` is `00000010_00000000`, etc.

If I were to try to split a `u16` into two `u8`s which *sum* to the same value, the digit rotation clears all previous bits, as can be seen in the difference between `255u16` and `256u16`. Solving *this* part of things is not very difficult, as I can basically do this:

```
let first_chunk: u8 = if value > 255 {
    255
} else {
    value as u8 // downcast because it can be represented as a u8
}

```

However, I have had an extremely difficult time trying to figure out how to get the remainder of this such that the second part remains accurate. I was originally trying to right bit-shift, but as per the table above, this clearly does not work, because the representation of `257 >> 8` (`00000001`) is *not* the same as a `u8` of value `2` (`00000010`). Division/modulo also doesn't work, and I'm kind of struggling to figure out how to proceed. I do assume that achieving this is possible, but I'm at a loss to figure out exactly *how*.

Here are some test cases and a sample function which implements the interface described:

```
fn split_to_sum(value: u16) -> [u8; 2] {
    // TODO
}

#[test]
fn test_split_to_sum() {
    // NOTE the output representation should be such that if the input is
    //      greater than the chunk size, the first chunk should be a full
    //      bit pattern, and so on and so forth
    assert_eq!([255u8, 0u8], split_to_sum(255u16));
    assert_eq!([255u8, 1u8], split_to_sum(256u16));
    assert_eq!([255u8, 2u8], split_to_sum(257u16));
    assert_eq!([255u8, 3u8], split_to_sum(258u16));
}

```

How can I go about solving this, such that a larger unsigned integer is split into chunks of a smaller unsigned integer where the *sum of the parts* is equal to the *original, larger-width integer*?

### TL;DR

Choose a size of unsigned integer, which we will call `x_size`. Next, choose a size of unsigned integer which is smaller than `x_size` and is divisible by `x_size` (this is always the case because of powers of two) which we will call `y_size`.

```
# size of x could be 128 bits, size of y could be 64 bits
assert x_size > y_size
# size of x must be divisible by size of y without a remainder
assert x_size % y_size = 0

```

Next, we will take an unsigned integer of size `x_size` named `x`. ~~Take `x` and split it into parts of size `y_size` where the *sum* of each part equals the value of the original value of `x`.~~

> **EDIT**: I have just realized that what I'm asking for is **fundamentally impossible**. Two unsigned 64-bit integers when summed together *cannot* represent the full space of an unsigned 128-bit integer. This should have been obvious to me, but I got lost in the details and just realized my mistake.
>
> For example, let's assume we are splitting an unsigned 32-bit integer into two unsigned 16-bit integers. The max value that a unsigned 16-bit integer can fit is, of course 216. The max value of two 16-bit unsigned integers when summed together is 2 * 216, which only occupies 18 bits, so we cannot sum the split parts from two 16 bit integers into a 32 bit integer, we cannot represent a larger unsigned integer as the sum of two evenly-split parts.
>
> I'm not sure why this didn't immediately stick out to me, because it seems pretty obvious now. The only way to split a larger integer into two parts is to simply split its actual bits.

# Answer
As requested, I am posting my edit to the question above as an answer:

> I have just realized that what I'm asking for is fundamentally impossible. Two unsigned 64-bit integers when summed together cannot represent the full space of an unsigned 128-bit integer. This should have been obvious to me, but I got lost in the details and just realized my mistake.
>
> For example, let's assume we are splitting an unsigned 32-bit integer into two unsigned 16-bit integers. The max value that a unsigned 16-bit integer can fit is, of course 216. The max value of two 16-bit unsigned integers when summed together is 2 * 216, which only occupies 18 bits, so we cannot sum the split parts from two 16 bit integers into a 32 bit integer, we cannot represent a larger unsigned integer as the sum of two evenly-split parts.
>
> I'm not sure why this didn't immediately stick out to me, because it seems pretty obvious now. The only way to split a larger integer into two parts is to simply split its actual bits.

In essence, the only way to represent the full value of a `u128` in binary is by using the *full* address space of 128 bits. It cannot be losslessly compressed into two `u64`s summed together.

For instance, we will calculate the maximum unsigned 64-bit and 128-bit integer values in Python:

```
# calculate the maximum value that a u128 can hold:
max_u128 = (2 ** 128) - 1
# calculate the maximum value that a u64 can hold:
max_u64 = (2 ** 64) - 1
# calculate the amount of u64s that, when summed, would equate the max
# value of a u128:
u64_count_for_u128 = max_u128 / max_u64
# display the ungodly number
print("{:f}".format(u64_count_for_u128)
# and here it is
assert 18446744073709551616.0 == u64_count_for_u128

```

To represent a u128 as a set of u64s which sum to the same value, you would need a set of **18,446,744,073,709,551,616.0** u64s. Thus, splitting a u128 into two u64s which sum to the same value is impossible.
> 1 votes

---
Tags: binary, bit-manipulation
---


# Question
Title: Influence of debugging on runtime complexity
I'm curious about how much complexity is introduced to an algorithm while it's being debugged. Is there a general theory for optimal debugging algorithms and theoretically optimal debugging performance?

The curiosity is a consequence of the following question: If I mean debugging to be the process of making information available to the programmer during the runtime of the program, then we'd call a total debugging algorithm to be one that made all information available to read during the run time. Would this necessarily double the run time?

I'd also like to pose and open ended question for discussion sake.

What are your thoughts about the relationship between the introduced complexity from debugging algorithms (using the definition for debugging I describe) and uncertainty as it exists in observing the real world as in physics?

In your opinion is there a strong or weak correlation between the concept of observational biases in the respective cases?

# Answer
> 1 votes
Unfortunately I suspect this is not the sort of problem that theoretical running time analysis will be very useful for adding much insight on.

Theoretical analysis is very useful when there are algorithmic techniques that make a major difference in scaling (e.g., $O(n)$ vs $O(n^2)$). Theoretical running time analysis is not very useful when you care about constant factors.

The cost of debugging is a constant factor, which is ignored in asymptotic analysis. I suspect that the costs of debugging are driven primarily by engineering concerns, which are typically abstracted in theoretical running time analysis.

One theoretical result that might be of interest to you: it is possible to keep track of all past states of the program (see, e.g., time-travel debugging) by using persistent data structures. Persistent data structures are known to impose at most a logarithmic overhead in running time. The practical cost of time-travel debugging might typically be less than that in practice, for a number of reasons that are beyond the scope of theoretical algorithms.

---
Tags: complexity-theory
---


# Question
Title: Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M\_0 = \\{1,\dots,n\\}$. Player A chooses a number $m\_1$ from $M\_0 \setminus \\{1\\}$ and B has to choose a divider $m\_2$ of $m\_1$ from $M\_1 = M\_0 \setminus \\{m\_1\\}$. The players continue to choose a number $m\_i$ from $M\_{i-1} = M\_{i-2} \setminus \\{m\_{i-1}\\}$ alternatingly, where every $m\_i$ has to divide $\sum\_{k=1}^{i-1} m\_k$. A player wins, if the other player is unable to do so and $M\_{i-1} \neq \emptyset$, $M\_{i-1} = \emptyset$ is considered a tie.

My questions:

* Is there an $n \> 2$, for which A has no winning strategy?
* Given some $n$ (in unary representation), how hard is it to decide whether there is a winning strategy for A
    + where A wins in at most $k$ steps ?
    + where A chooses no prime numbers ?

# Answer
1. Is there an n\>2, for which A has no winning strategy? To determine if there is an n\>2 for which A has no winning strategy, we can analyze the rules of the game. Player A's goal is to select a number mi such that mi divides the sum of all previous numbers mk (where k \< i). This means that Player A wants to select a number that results in a sum divisible by mi.

If we consider the case where n is a prime number, A will always have a winning strategy. This is because any prime number can only be divided by 1 and itself, and since A cannot choose the number 1, B will have no valid option to choose from in subsequent rounds. Therefore, A will always be able to choose a number mi such that the sum is divisible by mi.

However, if n is a composite number (not prime), there may be cases where A does not have a winning strategy. Let's consider an example: n = 4. A starts by choosing m1 = 4. Then B can choose m2 = 2, as 4 is divisible by 2. The game ends there, as M1 = ∅. B wins. Therefore, for values of n that are composites, it's possible for A to have no winning strategy.

2. Given some n (in unary representation), how hard is it to decide whether there is a winning strategy for A where A wins in at most k steps, and A chooses no prime numbers? This problem can be approached by creating an algorithm that explores all possible game paths up to k steps, checking if there exists a winning strategy for A. This would involve generating all possible combinations of numbers, selecting valid dividers, and recursively checking the next steps until either A or B wins or the maximum number of steps is reached. The complexity of this algorithm would depend on the values of n and k. As n increases, the number of possible combinations grows exponentially, increasing the computation time. Additionally, as k increases, the number of steps to be explored grows, further increasing the time complexity. Therefore, the decision problem of whether there is a winning strategy for A in at most k steps can be considered difficult and may have high computational complexity, especially for large values of n and k.

However, if the given value of n is relatively small, it may be feasible to employ dynamic programming techniques and memoization to optimize the search for winning strategies. By storing intermediate results and avoiding redundant calculations, the overall computation time could be significantly reduced.

In summary, determining whether A has a winning strategy for a given n and maximum number of steps k, where A chooses no prime numbers, can be computationally difficult, especially for larger values of n and k. Employing dynamic programming techniques could potentially optimize the search process for smaller values of n.
> -1 votes

---
Tags: complexity-theory, time-complexity, game-theory, number-theory
---


# Question
Title: Is transitivity required for a sorting algorithm
Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators?

Background:

* *A sorting algorithm generally sorts the elements of a list according to a comparator function C(x,y), with*

\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec y \\ 0 & {\text{if}}\ x\sim y \\ +1 & {\text{if}}\ x\succ y \\ \end{cases} \end{array}

*The requirements for this comparator are, as far as I understand them:*

+ *reflexive:* $\forall x: C(x,x)=0$
    + *antisymmetric:* $\forall x,y: C(x,y) = - C(y,x)$
    + *transitive:* $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
    + *C(x,y) is defined for all x and y, and the results depend only on x and y*

*(These requirements are always listed differently accross different implementations, so I am not sure I got them all right)*

Now I am wondering about a "tolerant" comparator function, that accepts numbers x,y as similar if$ |x - y| \le 1$: \begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\lt y-1 \\ 0 & {\text{if}}\ |x - y| \le 1 \\ +1 & {\text{if}}\ x\gt y+1 \\ \end{cases} \end{array}

Examples: both `[ 1, 2, 3, 4, 5]` and `[1, 4, 3, 2, 5]` are correctly sorted in ascending order according to the tolerant comparator ($C(x,y) \le 0$ if x comes before y in the list)
but `[1, 4, 2, 3, 5]` is not, since C(4,2)=1

This tolerant comparator is reflexive and antisymmetric, but not transitive.

i.e. C(1,2) = 0 , c(2,3) = 0, but C(1,3) = -1, violating transitivity

Yet I cannot think of any sorting algorithm that would fail to produce a "correctly sorted" output when given this comparator and a random list.

Is transitivity therefore not required in this case? And is there a less strict version of transitivity that *is* required for the sorting to work?

Related questions:

# Answer
> 13 votes
You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator?

The answer: Of course. You can run any algorithm with any input.

However, you know the rule: Garbage In, Garbage Out. If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output. In particular, there is no guarantee that the output will be "sorted" according to your comparator. So, running a sorting algorithm with a non-transitive comparator is not likely to be useful in the way you were probably hoping for.

As a counterexample, running insertion sort on the input list $\[3, 2, 1\]$ using your comparator would leave the list unchanged -- yet the resulting output list is not in sorted order (according to your comparator).

# Answer
> 5 votes
Given a set of elements and a binary ordering relation, transitivity is required to totally order the elements. In fact, transitivity is even required to define a partial order on the elements. http://en.m.wikipedia.org/wiki/Total\_order

You would need a much broader definition of what "sorted" means in order to sort elements without transitivity. It is hard to be self-consistent. Another answer says "In particular, there is no guarantee that the output will be 'sorted' according to your comparator." But we can actually say something much stronger. You are *guaranteed* that the output is *not sorted* according to your comparator.

Say that you have a non-transitive comparator that tells you $a\<b$, $b\<c$, and $c\<a$. Which element is the smallest one? No matter which one you choose, your comparator will tell you another element is smaller.

# Answer
> 2 votes
It sounds as though what you want is to arrange items such that all discernible rankings are correct, but items which are close might be considered "indistinguishable". It is possible to design sort algorithms which will work with such comparisons, but unless there are limits to how many comparisons may report that things are indistinguishable, there is no way to avoid having them require N(N-1)/2 comparisons. To understand why, pick some number N and any sorting algorithm that does less than N(N-1)/2 comparisons. Then populate a list L\[0..N-1\], setting each element L\[I\] to I/N and "sort" it using your comparator (the minimum value will be 0 and the maximum (N-1)/N, so the difference will be (N-1)/N, which is less than 1).

Because there are N(N-1)/2 pairs of items that could be compared, and the sort didn't do that many comparisons, there must be some pair of items that was not directly compared against each other. Replace whichever one of these ended up being sorted first by 1, and the other with -1/N, revert all items to their initial position, and repeat the sorting operation. Every single comparison operation will yield zero, just as it did the first time, so the same comparisons will be performed and items will end up in the same sequence. For the list to be correctly sorted, the "1" would have to sort after the "-1/N" (since they differ by more than one) but since the sorting algorithm would never compare those two items directly against each other, it would have no way of knowing that.

# Answer
> 1 votes
Fill an array of n elements with the values n, n-1, n-2, ..., 2, 1. Then try to sort using the "straight insertion" algorithm. You'll find that each element is considered equal to the element just before it, and therefore isn't moved. The result of the "sort" is the same array.

# Answer
> 1 votes
I second the answers given so far (equality and comparison operators but fulfill the mathematical requirements and not doing so can cause nasty bugs that are hard to spot). But I want to mention a method that sometimes solves the problem that people try to solve using an invalid comparator like the one mentioned in the OP. Assume you have a list of float numbers and you consider them "sufficiently equal" when they're closer than 1e-4. Then define the equality operator and the comparator based on their rounded values:

```
rounded(x) = 1e-4 * Round(1e4 * x) // where Round rounds to integers
x1 :== x2 iff rounded(x1) == rounded(x2)
x1 :< x2 iff rounded(x1) < rounded(x2)
..

```

Such and equality operator is valid for grouping methods and the corresponding comparator can be used for sorting. The results are reasonable.

When the numbers have a wide range of magnitudes you can also format each number into a string with the usual formatting options (exponential or smart with 4 significant digits or so), and define equality based on those strings:

```
str(x) := sprintf("%4g", x)
x1 :== x2 iff str(x1) == str(x2)
x1 :< x2 iff str(x1) != str(x2) and x1 < x2
..

```

Please forgive me if these snippets are not valid pseudocode, I hope they're good enough to explain the idea.

# Answer
> 1 votes
Define “correctly sorted”. Here’s an attempt: An array is k-sorted if $a\_i \<= a\_j$ whenever $i \<= j \<= i+k$. If \<= is transitive then any 1-sorted array is (n-1)-sorted.

With the definition of \<= in the question, assume the array contains one element equal to zero, one element equal to 1+epsilon, and all other elements from epsilon to 1. Then there is exactly *one* pair of elements that don’t compare equal. If we don’t compare these two elements then all comparisons result in “equal”, so an algorithm that doesn’t take O(n^2) steps might produce a result that is not even two-sorted.

# Answer
> 1 votes
Well it is very much possible to sort using some non transitive comparer. But it depends on what non transitivity means for you. For situation **A \> B && B \> C** there are 3 possible scenarios:

* A \> C (that's transitivity)
* A \>= C (soft non transitivity)
* A and C in any relation (hard non transitivity)

If you have transitive comparer, you can use fast sorting algorithms in n\*log(n). If you have a soft nontransitive comparer, you can use slower n^2 sorting algorithms. For example bubble sort:

```
private T[] BubbleSort<T>(IEnumerable<T> values, IComparer<T> comparer) {
    T[] result = values.ToArray();
    for(int i = result.Length - 1; i >= 0; i--) {
        for(int j = 0; j < i; j++) {
            int c = comparer.Compare(result[j], result[j + 1]);
            if(c >= 0) {
                T tmp = result[j];
                result[j] = result[j + 1];
                result[j + 1] = tmp;
            }
        }
    }
    return result;
}

```

For hard nontransitivity, you cannot use any sorting algorithm and expect some reasonable outcomes.

The reason why you need an n^2 algorithm is, beacause then the algo actually compares every element with one another. In n\*log(n) it takes advantage of transitivity.

Note in the above algo, we swap the elements even for c == 0, so even when they are equal regarding the soft nontransitive comparer. That way all elements eventually get to the ones they can compare to.

# Answer
> -1 votes
In general, sorting algorithms rely on the transitive property of the comparison function to correctly order elements. Transitivity ensures that if A is less than B and B is less than C, then A must be less than C. This property guarantees that the sorting algorithm can consistently compare and order elements.

However, in your case, the tolerant comparator function violates transitivity. Despite this violation, it is still possible to use a sorting algorithm with this non-transitive comparison function. One way to achieve this is by modifying the sorting algorithm to handle the non-transitive nature of the comparator.

One approach is to perform multiple passes through the array, each time considering a different subset of the elements that are within the tolerance range. The idea is to divide the array into smaller parts and sort them separately. Within each part, the transitivity violation is still present, but we only compare elements within that specific part. By doing so, we can ensure that the sorting algorithm produces a "correctly sorted" output based on the given comparator.

For example, let's consider the array \[1, 4, 2, 3, 5\] with the tolerant comparator. We can perform two passes. In the first pass, we consider elements within a tolerance range of 1. This would result in the following subsets: \[1, 2\], \[4, 3\], \[5\]. Within each subset, the tolerance is satisfied, and we can sort them independently. After sorting each subset, we combine them back together, resulting in \[1, 2, 3, 4, 5\], which is correctly sorted based on the given comparator.

So, to summarize, while the tolerant comparator violates transitivity, it is still possible to use a sorting algorithm by modifying it to handle the non-transitive nature. By dividing the array into subsets and sorting them separately, we can ensure a correctly sorted output based on the given comparator.

---
Tags: algorithms, sorting, quicksort, transitivity
---


# Question
Title: Why is Integer Linear Programming in NP?
The decision version of the problem Integar Linear Programming is the following:

* Input: two matrices $A\in \mathcal{M}\_n(\mathbb{Z})$ and $B\in \mathcal{M}\_{n,1}(\mathbb{Z})$.
* Question: is there a matrix $X\in \mathcal{M}\_{n,1}(\mathbb{Z})$ such that $AX\leqslant B$? (the inequality being component by component).

This is a well-known $\mathsf{NP}$-complete problem, but I struggle to prove that it is in $\mathsf{NP}$.

An obvious certificate for a positive instance $(A, B)$ would be such a $X$, but there is no guarantee that the size of such an $X$ is polynomial in the size of the input (here, we can consider the size of the instance $(A, B)$ to be $n^2\log\_2(\max(|a\_{ij}|, |b\_i|)$ and the size of $X$ to be $n\log\_2(\max |x\_i|))$.

What I expect is that if there is such an $X$, there is one with coefficients not too big, but I don't know how to prove this.

While this is a computer science formulation, I am sure that there is some maths behind this to prove the result, so maybe this question should be asked on maths.SE?

This document states:

> ILP ∈ NP. (Not obvious! Need a little math to prove it. Proof omitted.)

and this one states:

> Unlike with most NP-complete problems, it is not that easy to see that ILP ∈ NP, since a witness need not necessarily have polynomial size. This is the case though, but the reasons are beyond the scope of the course.

But none gives further references.

(Note: I think that this problem is an answer to my previous question)

# Answer
> 19 votes
As you have seen in other sources, the proof that there exists a witness with polynomial size does not exactly fit inside the margin, so to speak. The proof I know of (from the book I mention below) depends heavily on the mathematics of linear inequalities and polyhedra, and I expect this to be the case for most proofs. I don't think you will get a deep understanding of the proof without studying the subject first.

This is why, if you wish to know, I suggest you read a book. The book *Integer Programming* by Conforti, Cornuejols, and Zambelli prove this fact in section 4.8.2 by making use of various results on linear inequalities and polyhedra they covered in earlier chapters. To get the required background for the proof, you should work through chapters 1,3,4. This may take a couple of weeks of your time.

---

As a very rough sketch of their proof: the idea is that the solution space of a linear program, a polyhedron, can be described in terms of its "boundary": as a combination of a set of vectors called vertices and another set of vectors called (extreme) rays. That is, every point in the solution is equal to the sum of coefficient multiplied by one of these vectors. (with a few more constraints on the coefficients)

It can be shown that we do not need too many of these vectors (this follows from Caratheodory's theorem) and that these vectors have size polynomial in the encoding of the input. Some of the coefficients are already bounded, some are not but can be bounded via the same approach as Meyer's theorem. The combination of these bounds gives a polynomial bound on the size of the solution point.

# Answer
> 5 votes
The paper "On the Complexity of Integer Programming" from Papadimitriou has a very compact (2 and a half pages counting from abstract) proof.

It only needs the common knowledge about dual programs and linear algebra, but might be a bit terse.

# Answer
> 1 votes
I think there is a reasonably succinct proof in Schrijver (1986) "Theory of Linear and Integer Programming".

# Answer
> -2 votes
If I gave you a solution, you would be able to check it in polynomial time. That's what NP means: It is a decision problem, and if the answer is YES, then I can give you information that lets you verify that the answer is YES. Finding that information (in this case: Finding a solution) may be hard.

Also, if there is no solution, I wouln't know what information I could give you that you can check in polynomial time to find that the answer is NO. So unless I (and many very clever people) have missed something, the problem is not in co-NP.

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


# Question
Title: Is there an algorithm to implement N-input-gates using smaller gates?
To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I am calling these N-input-gates.

I want to know if there exists a general algorithm which can always describe an optimal way to implement an N-input-gate using only a collection of N-input-gates with smaller N.

Such as: emulate such-and-such specific 7-input-gate (perhaps uniquely identified by a 128-bit string of outputs) using only a lot of 3-input-gates.

This might most commonly be approached in the real world by breaking N-input-gates into small messes of 2-input-gates (such as AND/OR/XNOR), for example.

But it would also be interesting if the algorithm could be general enough that a person could specify the size of the smaller gates to use.. or perhaps even an exact breakdown of *which* gates to use (say, "find optimal solution using only NAND or only NOR gates or only AND+NOT gates or only copies of the 3-input (01011101) gate").

Algorithm would obviously need to be able to express when no solution is possible (eg: cannot emulate AND gate using only NOT gates) and structure of algorithm might be dependent on what types of input mutations are allowed (can one output be duplicated into multiple new gates? Can a constant one or zero be fed into a gate somewhere? etc)

I'm asking because I'm curious in principle whether this angle of research has already been done, and it's hard to search for unless one already knows many clever and unique search terms to cut through the noise of ambiguous and overloaded terms. Trust me, "and", "gate", and "function" mean a zillion different things in various contexts.

Also for my own sake I am creating a small logic simulation game based upon cellular automata and I'm curious about possible ways to automate some of the digital signal processing logic I can do within the system. EG if I know I want a specific (arbitrary) set of 16 output bits (EG: 1011011111101011) to come from a nibble of input bits and only have certain N-input-gate building blocks available to implement that, how can that most efficiently be done? Or can it be?

# Answer
> 0 votes
There is most likely no polynomial-time algorithm, i.e., no approach that will be efficient on all inputs. The problem is $\Sigma\_2^P$-complete, i.e., at least as hard or even harder than NP-hard, even when limiting to a basis of standard two-input gates. However there are heuristic methods.

See also https://en.wikipedia.org/wiki/Logic\_optimization, https://en.wikipedia.org/wiki/Logic\_synthesis.

# Answer
> 1 votes
You can always check whether two circuits have identical behaviour, there are only a finite number of circuits of size k for every k, so you can just systematically try out all circuits ordered by size and produce the first one matching the original, all in finite time. So there is an algorithm.

In practice the number of possible circuits is finite but HUGE. For example, finding an optimal (in some metric) circuit made of NAND gates for five inputs is about at the limit unless you are more clever than I am. Four inputs is no big deal because there are only 65,536 functions with four inputs, but there are over 4 billion with five and 16 billion billion with six inputs.

# Answer
> -2 votes
I can provide a solution to your problem by discussing a general approach to implementing N-input-gates using smaller N-input-gates.

To start, let's consider the case where we want to implement an N-input-gate using only 2-input-gates. One approach is to break down the N-input-gate into smaller sub-gates, such as AND, OR, XOR gates, which are typically implemented using 2-input-gates. This approach is commonly known as gate-level synthesis.

For example, to implement an N-input AND gate using only 2-input-gates, we can break it down as follows:

1. If N == 2, use a single 2-input AND gate.
2. If N \> 2, divide the N inputs into two groups, each having approximately equal number of inputs.
3. Implement an N/2-input AND gate for each group using recursion (step 1 and 2).
4. Finally, implement a 2-input AND gate with the outputs of the two N/2-input AND gates.

Similarly, other N-input-gates like OR or XOR can be implemented using 2-input-gates following similar recursive approaches.

Now, if you want to specify the size of the smaller gates to use, or even the exact breakdown of which gates to use, the problem becomes more complex. In this case, the problem can be formulated as a constraint satisfaction problem (CSP) and can be solved using various algorithms like backtracking or constraint propagation.

In this formulation, you would define constraints based on the available building blocks and the desired gate to be implemented. The algorithm then tries to find a valid combination of building blocks that satisfies the given constraints.

However, for large N or complex constraint sets, finding an optimal solution may not be computationally feasible. In such cases, heuristic search algorithms or approximation techniques can be employed to find good solutions.

It is worth noting that the specific constraints, available building blocks, and desired gate configurations will heavily influence the structure and implementation of the algorithm. Therefore, you may need to tailor the algorithm to your specific requirements and constraints.

To conclude, the research on optimizing the implementation of N-input-gates using smaller N-input-gates has been extensively studied in the field of digital circuit design. Various techniques and algorithms have been developed, but the actual implementation of an optimal solution will heavily depend on the specific constraints and requirements of your problem.

---
Tags: optimization, boolean-algebra, binary, digital-circuits, bit-manipulation
---


# Question
Title: Time Complexity: Determining if a binary tree is balanced
I found an algorithm for determining if a binary tree is height-balanced. It Gets the height of left and right subtrees using dfs traversal. Return true if the difference between heights is not more than 1 and left and right subtrees are balanced, otherwise return false.

algorithm code:

```
/* CPP program to check if
a tree is height-balanced or not */

#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data,
pointer to left child and
a pointer to right child */
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int d)
    {
        int data = d;
        left = right = NULL;
    }
};

// Function to calculate the height of a tree
int height(Node* node)
{
    // base case tree is empty
    if (node == NULL)
        return 0;

    // If tree is not empty then
    // height = 1 + max of left height
    // and right heights
    return 1 + max(height(node->left), height(node->right));
}

// Returns true if binary tree
// with root as root is height-balanced
bool isBalanced(Node* root)
{
    // for height of left subtree
    int lh;

    // for height of right subtree
    int rh;

    // If tree is empty then return true
    if (root == NULL)
        return 1;

    // Get the height of left and right sub trees
    lh = height(root->left);
    rh = height(root->right);

    if (abs(lh - rh) <= 1 && isBalanced(root->left)
        && isBalanced(root->right))
        return 1;

    // If we reach here then tree is not height-balanced
    return 0;
}

// Driver code
int main()
{
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->left->left = new Node(8);

    if (isBalanced(root))
        cout << "Tree is balanced";
    else
        cout << "Tree is not balanced";
    return 0;
}

```

Claimed this code has `O(n^2)` complexity but I can not understand why. I think the worst case is when the Binary Tree is full, and in this case, the height of BST is `log n` that in every level it runs the `height` function with `O(n)` complexity. So I think I must have `O(n log n)` time complexity.

# Answer
> 1 votes
Determining if a binary tree is balanced runs in $O(n)$, since we only need to traverse each node once, and moving from one node to another requires $O(1)$ moves.

However, since your code calculates height from scratch repeatedly, it runs in $O(n^2)$.

---
Tags: runtime-analysis, binary-search-trees, avl-trees
---


# Question
Title: Can the loops be in any order in the Floyd-Warshall algorithm?
I have a question about the Floyd Warshall algorithm. Here is the code from the Wikipedia page:

```
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j]
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

```

Our professor told us that the loop for k MUST be outside the i and j loops. I am unable to understand why this must be the case. He said that if k is inside we will only compute the best 2 edged or 1 edge path from i to j. I just don't see it. Can someone help?

# Answer
The pseudocode came from Wikipedia and the explanation is in Wikipedia as well. The recurrence is $dist(i, j, k) = min(dist(i,j,k-1),\ dist(i,k,k-1) + dist(k,j,k-1))$ with the base case $dist(i, j, 0) = w(i, j)$. There is only one way we can achieve this iteratively, by calculating all cases of $k-1$ before calculating cases of $k$. The other answer has an example when this is broken.
> 2 votes

# Answer
Suppose that you change the order of loops from $k,i,j$ to $i,j,k$. Let's see what happens when $i=1$ and $j=2$:

```
for k from 1 to |V|
  if dist[1][2] > dist[1][k] + dist[k][2]
    dist[1][2] ← dist[1][k] + dist[k][2]
  end if
end for

```

It is not too hard to check that this puts in `dist[1][2]` the value $$ \min\_{1 \leq k \leq |V|} w(1,k) + w(k,2), $$ where $w(1,1) = w(2,2) = 0$. This is the cost of the shortest path of length at most $2$ from $1$ to $2$.

The $(1,2)$'th iteration is the only one which modifies `dist[1][2]`, so at the end of the procedure, `dist[1][2]` will still contain $$ \min\_{1 \leq k \leq |V|} w(1,k) + w(k,2), $$ which could be arbitrarily off from the real shortest path from $1$ to $2$.
> 1 votes

# Answer
The order of the loops in the Floyd-Warshall algorithm is crucial. The algorithm works by progressively improving an estimate of the shortest path between every pair of vertices by considering each vertex as a possible intermediate step on the path.

If you change the order of the loops such that k (the intermediate vertex) is considered last, the algorithm will not work correctly. This is because when you calculate dist\[i\]\[j\], you're assuming that you've already considered all possible intermediate vertices that could provide a shorter path. If k is considered last, then you're not actually considering all possible intermediate vertices before updating dist\[i\]\[j\].

So, altering the order of loops to i, j, k will not yield the correct shortest paths between all pairs of vertices. The correct order is k, i, j as in the original Floyd-Warshall algorithm.
> 0 votes

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


# Question
Title: A data structure for an allocation-free dynamic sample rate buffer
I'm looking for a data structure that would allow storing samples (in O(1)) from a data stream in a fixed-size buffer while the stream length isn't known in advance.

Once the buffer size is exhausted it should start overwriting previous elements in a staggered manner, retroactively reducing the sampling rate of the data in the buffer.

**I've already come up with the algorithm, but want to know if there's a proper name for this so I can look for ready-made implementations.**

Basically, for a 16-element buffer, the insertion order would be:

```
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
   16    18    20    22    24    26    28    30 [a]
      32          36          40          44
         48          52          56          60
            64                      72
               80                      88
                  96                      104
                     112                     120
                        128
                           144
                              160
                                 176
                                    192
                                       208
                                          224
                                             240
<repeat from [a]>

Sorted buffer contents after the first 16 insertions:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sorted buffer contents after the first 32 insertions:
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

After 64 insertions:
0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60

...and so on.

```

Basically, after storing the initial N elements, with each following M * N/2 elements stored, the buffer contains a (shuffled) history with an effective sampling rate of 1/(M+1).

# Answer
The best name I can think of is derandomized or deterministic reservoir sampling. I don't know of any ready-made implementations.
> 4 votes

---
Tags: data-structures, sampling, storage
---