# Question
Title: Efficient way to find the i-th size in a BST
Given the following definition of binary search tree:

$$\text{size}(t)=\cases{0\qquad\qquad\qquad\qquad\qquad\qquad t=\text{ null}\\ 1+\text{size(t.left)+size(t.right)}\qquad\text{otherwise}}$$

for each vertex in the tree t.size contain the size of it's subtree

> Write an algorithm selection(T,i) that gets a Tree with size at each vertex and return the $i-$th smallest/largest size in the tree

---

*Attempt:*

I discovered that the size of a vertex is the number of vertices that there are in the specific root:

e.g:

```
                              V_1
                             /   \
                           V_2    V_3
                           /      / \
                         V_4     V_5 V_6

```

The size of $V\_4,V\_5,V\_6$ is: $1+0=1$

The size of $V\_2$ is: $1+1=2$

The size of $V\_3$ is: $1+1+1=3$

The size of $V\_1$ is: $1+3+2=6$

Now to scan all vertices in the tree using preorder or postorder and to find the $i-th$ size, running time $O(|V|)$,

I am looking for something more efficient.

# Answer
> 0 votes
(Please check the problem statement: having sub-tree sizes at each vertex available in constant time is very useful to find the $i$−th smallest/largest *element/key* (with $2$ being the 3rd smallest element in $1, 2, 2, 2, 3, 4$).)

For finding the $i$−th largest size, notice the tree to be a max-heap with respect to sub-tree sizes.
In search of the $i$−th smallest size, assume that the tree is perfectly balanced but for the path to *one* leaf, which is longer by *i* ($∄j: i = 2^j-1$). Before encountering that path/vertex, all sizes no larger than *i* will have been of the form ($2^j-1$). As you don't know if and where such a path/vertex exists, you will have to visit on the order of all *n* vertices.
*Unless* you find a way to know the $i$−th size among $Ο(n)$ candidates faster, this will be $Ω(n \log(i))$ in $Ο(i)$ space. (This depends on how much additional memory can be used, e.g., with $Ο(n)$ memory, you can do a counting sort of sizes encountered in $Ο(n)$ time.)

Run-time can be reduced by properly bounding the search:
Every non-empty tree will contain at least one leaf, so if *i* is $1$, return $1$.
For $1 \< i$, keep track of the highest size `s` such that every size up to `s` is known to have been encountered. When `s` reaches $i$, return that. Never descend from vertices with *size* no greater than `s`.

---
Tags: algorithms, data-structures, runtime-analysis
---


# Question
Title: Finding strings that are matched by a given regular expression
I'm trying to be ahead of the game by studying some Theory of Computation concepts before class starts at the end of this month. There's this question I came across that I don't understand below.

```
Let L be the language defined by the regular expression:
(c U ab U b)*bb(c U ab)

(U = union)

A.  Write 10 distinct strings that belong to L.
    If such strings don't exist, explain why.

B.  Write 10 distinct strings over alphabet {a,b,c} that don't belong to L.
    If such strings don't exist, explain why.

```

---

I'm totally lost, I have the answer but I just don't get how to go about it.

The only answers that I've came up with, that belong to L, was:

```
bbc, bbab

```

Which's only 2 correct out of the 10 listed in the answer key. I just can't see how to come about the rest of them.

Thanks for taking the time to read.

# Answer
Let's break down the regular expression $(c \cup ab \cup b)^\*bb(c \cup ab)$. It has three parts $(c \cup ab \cup b)^\*$, $bb$, and $(c \cup ab)$. The first part means "zero or more repetitions of $(c \cup ab \cup b)$", the second part matches two $b$, and the third part matches $c$ or $ab$.

As you already mentioned in your question bbc and bbab are strings that are matched. In both we choose zero repetition of the first part then the obligatory bb and then c, respectively ab, to match the third part. To make this easier to see I'll separate the parts of the string that are matched by the different parts of the expression with a - like so: -bb-c and -bb-ab.

We can generate more strings by choosing more than zero repetitions of the first part. For example we can choose one repetition of c to get c-bb-c. c-bb-ab would also be ok. We could also choose more repetitions of c or a c followed by ab for the first part. So cc-bb-c and cab-bb-c would also be acceptable strings.
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: Bit operations; Treating a number like an array
Are there features in programming languages that allow you to directly access the $k^{th}$ bit of a number. Treating it like an integer.

I'm not talking of using bit shifting to retrieve a number. But directly access the bit at index $i$ of a number as if it were an array.

I'm looking at this feature to replace shifting to write an algorithm I was working on. If it isn't faster than shifting, then such a feature would be pointless.

I didn't ask this on stack overflow as this isn't about a specific programming language, but about whether programming languages in general have this feature.

Also are there language features for inverting the bits(a specific bit or as many as needed) of a number?

# Answer
> 2 votes
The answer depends on the programming language and, to some extent, on the CPU. For any practical purpose, though, extracting the $k$th bit is an $O(1)$ operation even on a "big integer" stored on several machine words, since in order to extract the $k$th bit, you can use the following algorithm:

1. Determine which word the $k$th bit is in, and which bit in the word.
2. Extract the appropriate bit from the appropriate word.

In practice it is a reasonable assumption to make that *indices* of bits fit into a machine word, and so all of these operations are $O(1)$.

# Answer
> 1 votes
Felix has a *very* much more general capability.

```
var x : 3 * 2 * 5 = (case 2 of 3, case 1 of 2, case 4 of 5);
println$ x;
var y = x :>> int;
println$ y;
var z : 2 ^ 5 = true, true, true, false, false;
println$ z, z.1;
var a = z :>> int;
println$ a;

```

Basically there is a concept called a compact linear type. Unit (1) is compact linear, any finite sum, product, or exponential of a compact linear type is compact linear. For example

```
typedef bool = 2;

```

is compact linear.

Values of compact linear types have a natural bijection to integers, represented above by using the type coercion operator `:>>`. Felix represents small compact linear types which are defined as 64 bit unsigned integers, or non-compact arrays with compact linear indices.

Felix supports projections and assignments to any component of a compact linear type individually. The primary intent is for array indices because this then gives you polyadic (rank independent) array access.

For example you can coerce between `double^10^20` which is a linear array dimension 20 of linear arrays dimenion 10 to a matrix `double^(10*20)` which has takes a tuple index to `double^200` which is a single linear array of 200 values. The arrays here are not compact linear but the exponents are.

The compiler optimises these operations to ones using addition, multiplication, division and modulo of constants, and expects the underlying C compiler to convert these to bitshifts for powers of two.

The operations are generalisations of C bitfields, which only work for powers of 2. Compact linear types are fully general, up to the 64 bit restriction. However Felix does not provide pointers to components of compact linear types although you can assign to them.

---
Tags: programming-languages
---


# Question
Title: Why are recursive types needed as primitives for proofs in dependent type systems?
I'm relatively new to type theory and dependent programming. I've been studying the calculus of constructions (CoC) and other pure type systems. I'm particularly interested in using it as a proof-preserving intermediate representation for a compiler system.

I understand that (co-)recursive types are representable, *computationally*, using $\Pi$ as the only type constructor. I've read, though, that they cannot be used to build proofs by induction (forgive me, I can't find where now!), e.g., that I couldn't prove that $0\neq 1$ in plain CoC (even though $\texttt{Nat}$ is typeable as $\Pi(\mathbb{N}:\*).\Pi(S:\mathbb{N}\rightarrow\mathbb{N}).\Pi(Z:\mathbb{N}).\mathbb{N}$).

I assume this is why they built the calculus of inductive constructions (CIC). Is this correct? But why? I couldn't find any material explaining why such proofs cannot be represented without using (co-)inductive types as primitives. If this is not true, then why add them as primitives in CIC?

# Answer
I'm not an expert, but I'll share what I understood so far with an example.

Let's consider the boolean type in CoC, using its standard encoding: $$ \begin{array}{l} \mathbb{B} = \Pi\_{\tau:\*} \tau \to \tau \to \tau \\ \mathsf{tt} = \lambda \tau:\*,x:\tau,y:\tau.\ x \\ \mathsf{ff} = \lambda \tau:\*,x:\tau,y:\tau.\ y \end{array} $$ We might expect to be able to prove $$ \Pi\_{b : \mathbb{B}} b={\sf tt} \lor b = {\sf ff} \qquad(\*) $$ Indeed, this quickly follows from the dependent elimination/induction principle we have e.g. in CiC $$ \mathbb{B}\_{ind} : \Pi\_{P:\mathbb{B}\to\*} P({\sf tt}) \rightarrow P({\sf ff}) \rightarrow \Pi\_{b:\mathbb{B}} P(b) $$

However, we can not really expect (\*) to hold in all models of CoC! Intuitively, a value in $\mathbb{B}$ should roughly be a family of functions $\\{f\_\tau\\}\_{\tau}$ assigning to each type $\tau$ a value in the interpretation of $\tau\to\tau\to\tau$. But this does not force $f\_\tau$ to be one between the values of $\sf tt,ff$. We could have e.g. (informally) $$ f\_{\mathbb{N}}(n)(m) = n+m $$

To be sure that the values of $\sf tt,ff$ are the only possible values, we need to restrict ourselves to *parametric* models. Indeed (I think) the property $(\*)$ can be proven from the *free theorem* associated to the polytype $\mathbb{B}$.

However, as far as I understand, CoC does not rule out ad-hoc models, where parametricity does not hold. In some of those, $(\*)$ is simply false. By soundness, in the presence of a countermodel, we conclude that $(\*)$ is not inhabited in CoC. Consequently, there's no $\mathbb{B}\_{ind}$ term in CoC, either.
> 7 votes

---
Tags: type-theory, dependent-types, coq
---


# Question
Title: Algorithms with O(sqrt(N)) SPACE complexity?
Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.

# Answer
> 15 votes
$\sqrt{n}$ space is somewhat unusual; the most likely reason for such a complexity to emerge is as a result of a so-called *meet in the middle* scheme.

Two notable examples off the top of my head are the classical *sieve of Eratosthenes* and the *baby-step giant-step* algorithm for the discrete logarithm over a finite group.

---
Tags: complexity-theory, asymptotics, space-complexity
---


# Question
Title: Query all bounding boxes which contain a point
I'm looking for the most efficient spatial-indexing data-structure for storing and querying bounding boxes which contain individual points. The points represent 2D coordinates on a grid, while the bounding boxes represent regions of the grid. The bounding boxes may vary greatly in size, and multiple bounding boxes may overlap a single point. Both points and bounding boxes are stored as signed integers.

For example, in the diagram below, if I were to query points $B$ and $C$, I'd expect a single bounding box in return. However, if I query point $A$, I'd expect an array containing both bounding boxes in return.

```
--------
| B  ============
|    |A|        |
-----|--     C  |
     ============

```

I'm not concerned with insert/remove efficient for adding bounding-boxes to the structure as all bounding-boxes are added to the structure during a one-time initialization. My main concern is efficient look-ups for finding which bounding boxes contain a point, as such queries will be made frequently.

My initial thought is to use a quadtree, and to test all objects contained in a particular node to see if they contain the point being queried. However, I'm wondering: is there a better data-structure I could use to implement this behavior with?

# Answer
Use a 2-d segment tree. Assuming we have $n$ items, construction takes time $O(n \cdot \log^2(n))$ and each query takes $O(\log^2(n))$ time. These times become $O(n \cdot \log(n))$ and $O(\log(n))$ time, respectively, if we use fractional cascading and lowest-level interval tree. These are good times unless there is more problem structure.

---

The query is called "multi-dimensional stabbing query" or "point enclosure query".

Range tree involves finding points in a query range. Segment tree involves finding rectangles that contain a query point.

On an unrelated note, one might wish to use an R-tree with sort-tile-recursive (STR) bulk-loading. This leads to almost no overlap between bounding boxes for a node's children and the structure is balanced. If we are lucky (i.e. R-tree involves heuristics and we wish to avoid ties for each component), the structure is good for moderate number of dimensions because factor of $d \cdot \log(n)$ for time is lower than $\log^{\textrm{max}(d - 1, 1)}(n)$ (noting that $d \geq 1$). We take advantage of fact that use of R-tree does not involve cloning primitives. Also, nearest neighbor via heuristic can perform quite well with R-tree, which seems to be something that that excels at w.r.t. segment tree and range tree. Additionally, one might wish to for dynamic structure use an R\*-tree or one might wish to for slightly more dimensions use an X-tree. The more dimensions one has, the more likely linear scan is more affordable via a kind of "curse of dimensionality".

Further, if one has only distances and no absolute locations, a metric tree will prove useful. Structures that assume rectangle primitives will be aided by fact that a point is a degenerate rectangle. A pair of points that act as opposite corners of a rectangle can be turned into one point via a "corner transformation" from Pagel 1993.

One strategy that may be used with R-tree is augmenting it with "look-ahead" and edge checks to get guaranteed theoretically acceptable time for a query such as point enclosure query. This is even when it seems an R-tree is designed specifically for this kind of query.

**References**

* Pagel et al. - The transformation technique for spatial objects revisited (1993)
> 6 votes

---
Tags: algorithms, data-structures, space-partitioning
---


title: Using tree search

text:
# Question
Title: Using tree search
I have some questions regarding tree search and graph search (Uninformed search) as explained in chapter 3 of the book : http://aima.cs.berkeley.edu/

As I see, the only difference between the two is that the graph search handles loops (avoids them).

First question: Do both graph search and tree search build dynamic trees of the problem at hand?

Second question: I assume graph search was used to solve the map of Romania problem (getting from Arad to Bucharest) with DFS, BFS, UCS as strategies that only sort the frontier queue. Now is there a standard way to change the graph of map of Romania to a tree, and then use tree search?

Third question: What are some of the Criteria that help us choose between graph and tree search for different problems?

Thanks you in advance

# Answer
Both BFS and DFS take a graph and induce a subgraph of it. This subgraph has all the nodes reachable from the start node, and is a tree.

You could probably convert a graph to a tree and then use tree search, but it seems to me that the easiest way to convert a graph to a tree is, in fact, some kind of search, and it would be redundant to use search to convert the graph, then do another search on the tree, when you could have just used the initial search.

You want to use graph search on graphs, and tree search on trees. In particular, this is because graphs which are cyclic can get caught in infinite loops if you use a tree-search on them.

(Note, if we're talking directed graphs, there is probably a special kind of tree search for an acyclic graph. For undirected graphs, and acyclic connected undirected graph is just a tree)
> 1 votes

# Answer
To use which search method(tree search or graph search) depending on the question that you'r handling. Usually the view to think the question affect the solving method. The two search method differ from handling different structures, tree search handle with tree and graph search handle with graph. As we know, the tree is a special kind of graph, which has no cycles. So, if you can modeling the question as a tree, then you can use tree search easily. For example, in the Eight Puzzle, the number which is not in the edge can has 4 decisions, let's consider a case, we move a number up, and the number still has 4 decisions in the new location, but when we deal this question, we only prepare 3 decisions in the new location to avoid the new state is same with the previous. This restriction is helpful to solve the problem. Then the Eight Puzzle solving process can construct a state transfer tree.
> 2 votes

---
Tags: artificial-intelligence, search-algorithms
---


# Question
Title: Is there any graph problem that, when restricted to trees, has $\Omega(n^2)$ time complexity?
Trees are pretty linear in nature, since the number of edges is always one less than the number of vertices. Furthermore, the absence of cycles can sometimes drastically reduce the computational complexity of otherwise pretty hard problems. For example, the longest path problem is NP-hard for general graphs, but is easily solved in linear time for trees. Many other examples exists, where a graph problem magically becomes doable in constant- or linear-time, just because of the restriction to trees (an example for the constant case being the minimum spanning tree problem). I guess sometimes you could be forced to a linearithmic lower bound, although I'm not completely sure at the time of writing this (but my main question for now lies in the next paragraph).

However, I have struggled for a few weeks to come up with an example of a problem that has to have an $\Omega(n^2)$ bound even when restricting to trees. I suspect these problems may exist, but can't come up with any. Can anyone give me an example, or alternatively give me a proof that all decision problems on trees are decidable in less than quadratic time?

Of course, I assume we are not representing the tree using the adjacency matrix, but rather an adjacency-list or other timesaving data structure.

I also suspect that I might need to explicitly state to consider only tractable problems, since I guess you could come up with halting-type problems for trees otherwise.

# Answer
Yes. By the time hierarchy theorem, there is a (tractable, solvable in $O(n^2 \log n)$ time) problem $X$ that (on an $n$-bit instance) can not be solved in less than $\Omega(N^2)$ time.

Given an $n$-bit string, I can encode it as a tree, for instance by taking a path $p\_1,\ldots, p\_n$ of length $n$ and adding an additional leaf vertex to vertex $p\_i$ if the corresponding bit $i$ in the string is $1$ (and perhaps adding some constant-size gadget to mark the beginning of the string).

Now I will define problem $Y$ to be to recognize the trees that encode a bitstring that is a (valid) instance of $X$. Clearly this problem requires at least quadratic time (or otherwise we would have a faster algorithm for $X$).

This is of course a rather contrived and artificial example, but there are some natural problems that are hard for trees as well. See e.g. NP-hard problems on trees.
> 4 votes

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


# Question
Title: Supervised learning with no prior information
I am now reading two modern books on machine learning theory. Both of them emphasize that, in order to succeed in supervised learning, one must choose a good hypothesis class. "Good" means that it is sufficiently simple (formally, has a low VC dimension) and that it contains the true hypothesis or sufficiently close hypotheses. One also mentions the "no free lunch theorem", which says that, without such prior knowledge, you cannot have meaningful learning.

But what do I do if I have no prior knowledge? I have no idea how the correct hypothesis looks like, I do not know if it will be simple or complex. All I have is the training data. Isn't there anything useful I can do with them?

I am thinking of a newly born child. He has no prior knowledge, all he has are "training samples" given by his parents/teachers, and it is still sufficient for meaningful learning. You could say that each child is born with some prior knowledge wired into his brain, but then the question is: where such prior knowledge comes from? And again, what should a person do in a new situation on which his wired prior-knowledge is useless?

To sum, my question is: what is a supervised learning paradigm that can be applied without any prior knowledge on the set of possible hypotheses?

# Answer
I think that the success of a newborn child follows from the fact that the phenomena he's trying to learn is describable (or can be sufficiently approximated) by the hypothesis class generated by the learning algorithm which is going on in his brain.

This is of course, not formal in any way, but say a baby is equipped with some neural network (of fixed depth), and upon receiving new data, the weights are updated accordingly using some algorithm.

The choice of neural network doesn't really matter, simply imagine that you have carefully studied the processes going on inside the human brain, and found out that the human learning process is similar to using a neural net.

In that case, the image of the learning algorithm is some class $\mathcal{F}$, say functions expressible by some fixed depth nets, and the success of the baby in learning new things simply means that the phenomena he's trying to learn is captured by $\mathcal{F}$ (so nothing magical/contradicting what you quoted is going on).

To make sure this answer does more than just contain some of my random thoughts, I will add that **if you truly know nothing, there is nothing you can hope to learn**. The data you're receiving could always be generated from the uniform distribution, i.e. someone is tossing a coin and giving you the outcome. Obviously, in that case, you can not hope for a small generalization error.
> 0 votes

---
Tags: machine-learning, learning-theory
---


# Question
Title: Prove the following language is regular using closures
How can I prove this language is regular using just closures and homomorphism? $$ L = \\{a\_1b\_1a\_2b\_2\dotsm a\_nb\_n \mid a\_i \in L\_1 , b\_i \in L\_2\\} $$ and we know $L\_1$ and $L\_2$ are regular.

# Answer
> 3 votes
To get you started, consider a restricted version of your languge: $$ L'=\\{ab\mid a\in L\_1, b\in L\_2\\} $$ Notice that $L$ is the concatenation $L'=L\_1\circ L\_2$. Can you carry on from there?

---
Tags: regular-languages, closure-properties
---


title: NFA automata with $\epsilon$ moves

text:
# Question
Title: NFA automata with $\epsilon$ moves
I'm trying to understand the NFA and $\epsilon$ moves logic. Let's say there is an NFA $A$ with $\epsilon$ moves, if $\epsilon ∈ L(A)$ then $q\_0 \in F$? and vice versa? If $\epsilon \in L(A)$ then $q\_0 \in F$? How can I prove it?

# Answer
> 1 votes
It is true that if $q\_0 \in F$ then $\epsilon \in L(A)$. The converse holds for DFAs and for NFAs without $\epsilon$ moves, but doesn't hold for NFAs which are allowed to have $\epsilon$ moves. That is, there is an automaton $A$ whose initial state is not accepting, yet $\epsilon \in L(A)$. I'll let you find an example.

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


# Question
Title: Suitable choice for moderate-size square matrix multiplication?
The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, let's say we use floating-point numbers. Ideally, the approach would be fast enough for small $n$ and, of course, should not require size ($n$ value) of ~$10 ^ 6$ to break even relative to brute-force cubic time approach. The lower the running time, the better. Given ties, the lower the coefficient for running time, the better. Given ties again, lower space requirement is desired. Algebraic or combinatorial approaches are acceptable.

Then, what is a suitable algorithm choice for this moderate-size-input square matrix product problem?

# Answer
> 7 votes
Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and list all relevant algorithms.

---
Tags: algorithms, time-complexity, combinatorics, matrices, linear-algebra
---


title: Connected components and graph edition

text:
# Question
Title: Connected components and graph edition
There are known algorithms to find the connected components of a given graph. Those I know are easily extensible to support addition of nodes and edges to the graph and then find the resulting components more quickly than by recomputing from scratch.

What I'm looking for is an algorithm with an associated data structure which allow the efficient determination of connected components after removal of nodes and edges.

# Answer
In general, what you are looking for is known as dynamic connectivity: it comes with different flavors depending on whether vertices/edges can be added, deleted, or if both operations are allowed.

Many relevant papers are summarized in this answer on TCS.SE. If you are looking for a practical implementation, a possible starting point is \[1\]. Here, the authors perform experiments and provide some C++ code (these are for fully dynamic algorithms).

---

\[1\] Iyer, R., Karger, D., Rahul, H., & Thorup, M. "An experimental study of polylogarithmic, fully dynamic, connectivity algorithms." Journal of Experimental Algorithmics (JEA) 6 (2001): 4.
> 5 votes

---
Tags: graphs
---


# Question
Title: How to define a context free grammar from a regular language?
I wonder how do you clasify S-\>a (where a is a Terminal Symbol)

It can be right linear,left linear and context free at the same time?

So the only way to distinguish them is to see what productions there are with Non-terminal symbols (like S in this example)

0) If I see S-\>a it can be (left/right/context-free) impossible to know

1) If I see only production in the form of S-\>a and S-\> aS then it is right lineair

2) If I see only production in the form of S-\>a and S-\> Sa then it is left lineair

3) If I see a mix (left and right) of the form of S-\> aS and S-\> Sa then I know that it is context free

4) If I see a production with a terminal symbol on the left AND on the right then I also know it is context free : like this S-\>aSa

Are these 5 statements correct? Am I missing scenario's to define the difference between regular and context free?

# Answer
Your statement is correct. However your cases do not cover the full width of context-free grammars. All your examples are linear grammars.

In general one also allows right-hand sides that contain more than one non-terminal, like A-\>BC.
> 1 votes

---
Tags: context-free, regular-languages
---


# Question
Title: How do Functional Reactive Programming and the Actor model relate to each other?
FRP is about streaming events and behaviours through pure functions. The Actor model - at least, as implemented in Akka - is about streaming immutable messages (which can be considered to be discrete events) through potentially impure objects, called actors.

So on the surface they seem related.

What else can we say about how they related? Also, what can say about which of them might be more appropriate for different application domains?

# Answer
> 30 votes
Neither actors nor FRP are about streaming. Actors don't even support external configuration of an output stream.

FRP is strongly characterized by its modeling signals and events on a linear timeline, which enables FRP behaviors to compose in a deterministic manner. Actors are strongly characterized by processing messages in non-deterministic order, and have scarcely any compositional properties (i.e. you can't treat an arrangement of two actors as a larger actor).

If you're seeking similarities, both actors and FRP have a close relationship to lambda calculus. Both can model systems responsive to human input. Both support modeling of internal (local) state.

FRP supports local state through integrals or accumulators (fold over time), while actors model supports state by allowing each actor to specify its behavior for the next message in response to the current one. This pervasive support for local state makes both FRP and Actors inadequate for live programming (or runtime upgrade of program code); it becomes too easy to lose important state.

Regarding application domains:

Actors model is well suited for open systems, where we might wish to install or maintain actors at runtime. Actors model is also weakly suited to distributed systems, as the non-deterministic ordering of messages can make a conforming implementation easier. (The reason actors are not more strongly suited to distributed systems is that ensuring a message arrives 'once and only once' is quite difficult in the face of disruption, and actors also tend to require distributed GC, which is a pain.)

FRP is well suited to closed systems that operate over time - e.g. robotic controllers, music programming, computational toys. The determinism and compositional features make FRP more convenient to work with than actors, at least in those cases where FRP can directly model a solution. Integrating FRP with effects (elegantly, without hacking the model with impurity) has proven difficult. There has been recent work on effectful FRP via 'wormholes' - effectively, unique or linear typed access to resources.

There are other models that lie somewhere between FRP and Actors.

Flow Based Programming (FBP), developed by John Paul Morrison, really does support streaming of messages.

Time Warp protocols (or the more recent work on Lightweight Time Warp (LTW)) places actors-like messages on a logical timeline to provide a more controlled and compositional notion of message passing. Time warp is often used for large parallel and distributed systems, e.g. scientific computing. The original time warp was unsuited for interactive simulatons (responsiveness to human input), and LTW is only marginally suited.

I am developing Reactive Demand Programming (RDP) which enables responsive, compositional, FRP-like manipulation and processing of signals in open and distributed systems, and eliminates local state. RDP is achieved by constraining side-effects to commutative, idempotent influence on resource state by signals over time. RDP requires rethinking of resource and state models.

# Answer
> 9 votes
I wanna point out how they are different from a practical point of view:

1) actors send messages to other actors, this message passing is described explicitly and **imperatively**.

For example:

`send msg to Actor137`.

2) in FRP the data flow is described **declaratively**:

For example:

`Cell134=Cell185+Cell42`.

The message passing is handled by the FRP framework and you don't have to describe "manually" how to pass messages from one cell (akin to Actor, encapsulates state, aka Behaviour) to another.

In other words:

The essence of functional reactive programming is to specify the dynamic behavior of a value **completely** at the time of declaration. So all dependencies of `Cell134` are defined at declaration point.

This is **not true** for the actor model. Actors influencing the behaviour of an actor `A` are not defined at the same place in the source code where the actor `A` is defined.

Recently I noticed that there is an interesting hybrid between the two: Akka streams, where the dataflow is described declaratively but is implemented using actors.

Another difference is : Actors tend to be async while FRP tends to be synchronous (often glitch free).

---
Tags: distributed-systems, functional-programming, programming-paradigms
---


# Question
Title: Sort an array of $n$ elements when only $\log n$ are not in place
I'm trying to understand how can I sort an array of $n$ elements when only $\log n$ are not in place.

I heard that sorting an array with at most $I$ inversions has complexity $O(n\log(I/n))$. Because there are $\log n$ elements that are unsorted, in my case there are at most $n\log n$ inversion.

The answer to the question is $O(n\log\log n)$ which is consistent with the formula, but I can't understand the"idea behind it, or which sorting algorithm achieves it.

# Answer
Assuming that "$k$ elements out of place" means that there exist $k$ elements whose deletion leaves the rest of the array sorted, there's an $O(n+k\log k)$-time algorithm to sort the whole array.

In a nutshell, compute an increasing subsequence of length at least $n-2k$, sort the others, and merge. The former can be accomplished in time $O(n)$ by a simple stack algorithm that pushes elements one at a time and pops the top two whenever they're out of order. The optimal deletion strategy must delete at least one of these elements, so the total damage is upperbounded by $2k$ deletions.
> 9 votes

# Answer
Let's say there are $k$ non-in place elements.

Split the array into non-decreasing subarrays. This can be done in $\Theta(n)$ time and will result in at most $2k$ subarrays. Now we just pairwise-merge them in $\Theta(n \log k) $ time, yielding a sorted array.
> 7 votes

---
Tags: sorting
---


# Question
Title: How does the double rotation in AVL tree work?
I am trying to find out from this visualization how does the AVL trees work. But I am not able to find out how is the algorithm choosing which vertex is the right one to use as "partial root".

The simple rotation is actually very simple, but when it comes to the double rotation it is much worse.

There are some tricks with signs of vertices when inserting a new vertex, but I don't completely understand that either (and also I am not sure if it is important for the rotation).

EDIT: I add a drawing of my Insertion. I would expect that the double rotation will choose the purple (left) variant (it seems simplier), but the visualization choose the brown one. Why is that?

# Answer
At the drawing is correct the brown variant. The purple isn't binary search tree (thanks, Hendrik Jan for this clarification) at all.
Why? Because it is not in the right order (for all nodes in a BST must be true, that all nodes in its right subtree have bigger value and all nodes in the left subtree have a smaller value than the node).

About the double rotation itself:
The problem was that I didn't know how to choose the correct vertex, the right answer is that you have to take the middle one as the root of the new subtree (11 from the set 10, 11, 14 on my drawing) and the rest must fit the rules for the binary search AVL trees.
> 1 votes

---
Tags: graphs, search-algorithms, binary-trees, balanced-search-trees
---


# Question
Title: Complexity of Context Sensitive Languages
I was reading above complexity classes from Formal Languages and Automata book by Peter Linz.

It gives following facts (in Theorem 5.2):

> Consider we have a CFG without null or unit productions. For parsing a string w, if restrict ourselves to leftmost derivation, we can have no more than $|P|$ sentential forms after one round, no more than $|P|^2$ sentential forms after the second round, and so on. Parsing $w$ in CFG without null or unit productions cannot involve more than $2|w|$ rounds. Therefore, the total number of sentential forms cannot exceed $M=|P|+|P|^2+⋯+|P|^{2|w|} =O(P^{(2|w|+1)})$

Then (in Example 14.5, citing back above theorem) it says

> However we cannot claim that $CSL \subseteq DTIME(|P|^{cn+1})$ because we cannot put an upper bound on $|P|$ and $c$

I dont understand why it is trying to use the fact about CFLs to find time complexity of CSLs. Is it because if CFLs does not follow that DTIME complexity, CSLs will also not follow it as $CFL\subset CSL$? But then, given any grammar, $|P|$ is fixed, its not infinite and I feel $c$ is always 2 as given in the proof of the theorem 5.2.

# Answer
When the book says

> Following the analysis leading to Equation (5.2),

it implies that if you apply the same kind of reasoning that resulted in Equation (5.2) to context-sensitive languages, then you will get the similar equation

> $$ N = |P| + |P|^2 + \ldots |P|^{cn} = O(|P|^{cn+1}). $$

This equation is the analog of Equation (5.2) for context-sensitive languages. To prove this equation, you use reasoning similar to that used to prove Equation (5.2).
> 1 votes

---
Tags: complexity-theory, formal-languages, context-free, complexity-classes, context-sensitive
---


# Question
Title: How to Find the minimum permanent which is pumping lemma for language context-free?
Suppose we have context-free language and we know the Context-Free-Grammar, how do i found the minimum permanent which is pumping lemma for language ?

for example let sat i have this Grammar: $$\begin{align} S&\rightarrow AA\mid B\\ A&\rightarrow 0A\mid A0∣1\\ B&\rightarrow 00B0\mid 1\\ \end{align}$$ whats is the best way to find this Minimum permanent?

# Answer
> 2 votes
I presume by "permanent" you mean the integer of the Pumping Lemma, that is the integer $p\>0$ such that for any string $s$ in the language with length $p$ or greater we can express $s=uvxyz$ with . . . \[*blah blah blah*, I'm not going to write the statement here\].

If you've read the proof of the PL, you know that it relies on guaranteeing that in a parse tree for a string of sufficient length, there will always be some path from the root to a leaf which contains a repeated variable. When that happens, we can replace the subtree rooted at the "lower" repeated variable with a copy of the subtree rooted at the "upper" repeated variable and have a parse tree for a new string also in the language: i.e., you've pumped the string.

For the grammar you've given, it is particularly easy to find the shortest strings in the language with a repeated variable in a path from the root to a leaf. Here are the trees for the shortest such strings:

There are two other of the right-hand form, but because of the way your grammar is formed, any string of length greater than or equal to 3 generated by the grammar must be formed by extending one of these two. In other words, the integer of the pumping lemma can be 3 or greater. It can't be 1 or 2, since while the strings $1$ and $11$ are in the language, there are no repeated variables in their parse trees (meaning they can't be pumped). Finally, then, the integer you want is 3.

---
Tags: context-free, pumping-lemma
---


title: Measuring availability from CAP theorem

text:
# Question
Title: Measuring availability from CAP theorem
I wonder how to check availability property from CAP theorem. Consistency check is conceptually easy: if at least once somehow same query at the same time returns different results, then the system may be considered inconsistent (or under some circumstances eventually consistent).

But what about availability? If it takes 1 millisecond for the system to respond, it probably should be considered available. If 1 second for a huge query - probably also available. But what about 50 seconds for a simple query?.. Where is the threshold - how much time should the system take to respond in order to consider it unavailable?

Well, one possible threshold is to consider system unavailable only if it throws some error immediately or doesn't respond at all. But with such definition we may consider available any system that lets the user wait for a long time until all inconsistencies and partitions are resolved.

So my questions are:

1) How do we check if system satisfies availability property as defined in CAP theorem?

2) How do we distinguish the following cases:

* System is available, but it may take 10 minutes to process some huge query.
* Actually system is not available, but there is some wrapper (user calls it instead of the original system) that each time when original system is not available simply waits until it becomes, so to the outside user it looks like the system is available and is simply processing the query.

# Answer
> 4 votes
This is indeed a concern for those building real-world applications - how does one measure "availability" - not the binary property discussed in the CAP theorem, but the experience for users of the system.

There is industry agreement around this concern, and a standardized method of measuring it applicable to all systems. (Note: as stated in the comments, this is a separate concept from the *theoretical* concept of availability, which is analyzed from an algorithm, or perhaps from a simulation of a system.)

The Apdex method assumes you have a definition of "satisfied service" at some response time. Let's say you consider a sub-1-second response time to satisfactory to define "available." Then, by convention, "tolerable" service is 4 times the target time: in our case, a response time from 1 to 4 seconds. Response times longer than 4 seconds are considered "frustrated."

Then, the Apdex score is the number of satisfied requests, plus *half* the number of tolerable requests, plus *none* of the frustrated requests (i.e. 0), all divided by the total number of requests.

For example, if you had 100 total requests, and 30 of them were satisfied (\< 1s), 50 were tolerable (\>1s but \<4s) and 20 were frustrated (\>4s), the apdex score for your service for the period of time those requests were serviced would be (30+25+0)/100, or 0.55. (An apdex score, by virtue of being a ratio, is always between 0 and 1)

Fun fact: a bunch of businesses then teamed up to turn this quite simple idea into a fully-fledged business. If you are a business, you can pay the Apdex Alliance money so they can produce education, webinars, and blogs, as well as certify compliant business so they may use the Apdex name and logo(!)

(I am not affiliated with the Alliance. I just like standards.)

# Answer
> 2 votes
https://en.wikipedia.org/wiki/CAP\_theorem

"CAP is frequently misunderstood as if one had to choose to abandon one of the three guarantees at all times. In fact, the choice is really between consistency and availability for when a partition happens only; at all other times, no trade-off has to be made."

In other words, you are not measuring availability as a matter of "time" as you describe in your question -- it is a computer science property of how the system behaves when something gone wrong -- it is either available or not available -- that is a binary choice and nothing to do with timing or user access.

Once you have determined whether a system should be available or not (binary choice), then the question remains (your question 2) on how the implementation behaves -- and does it works slow vs not at all, but that is the difference between an erroneous implementation and a flawless one, and it is strictly not a computer science question any more than the question of "how do I produce bug-free code"

The CAP theorem is about the algo design of the database and not about writing code or the system that uses the database.

---
Tags: database-theory, databases
---


# Question
Title: Operator-precedence grammar`s symmetrical rule
I have a basic question, but I cannot find an answer anywhere on the Web. I have the following grammar rules:

1. `S -> if C ;`
2. `C -> O < O`
3. `O -> O + i`
4. `O -> i`

The part than I\`m interested in is at rules 1,2 and 4.

I have calculated First(O) = {i, +} and Last(O) = {i}.

So, First(C) = {i,+,\<} and Last(C) = {\<, i}.

Also, if \<\* First(C) and Last(C) \>\* ;

I have build the precedence table and now I want to parse the input: `if < ;`

So when i parse it, I first have `if` on top of my stack. Then I look at `<`, `if <* <`, so I push `<` on top of the stack. So now I compare `<` to `;`, `;` has higher precedence according to the rules, so I must pop. The last part is trivial, and leads me to `S`, thus accepting the sentence.

**BUT**, as we can clearly see from the rules, this sentence should not be accepted (we only have 1 `<`, not enough to form `C` in order to reduce it).

I have noticed that this happens because there is a symmetrical rule (rule 2 in our case), which means that `if <* {i, <} >* ;`, so we cannot verify that there was indeed an `<` or only an `i`.

What is the solution to this problem? How do we handle these special cases where symmetrical rules\`s precedence relations overlap? I\`m sure there must be one, because this grammar is conceptually close to a programming language parsing problem itself.

Thank you for your time!

# Answer
> 5 votes
It's not the symmetry of rule 2 which is the problem (whatever you mean by symmetry). The problem is (more or less) inherent to the operator precedence algorithm.

O-P parsing was dropped from the Dragon book between the first and second editions, presumably because the authors no longer believed to be a useful parsing technique \[Note 1\]. So I'm quoting from the first edition, which I still have on my bookshelf for odd sentimental reasons \[Note 2\]. And what it says is: (p. 203)

> As a general parsing technique, operator-precedence has a number of disadvantages… since the relationship between a grammar for the language being parsed and the operator-precedence parser itself is tenuous, one cannot always be sure the parser accepts exactly the desired language.

And that's the case. Operator-precedence grammars tend to accept a superset of the desired language, and you need to augment them with a number of checks to ensure that invalid sentences like the one you threw at your parser don't actually get recognized.

The classic O-P construction -- the one I think you are referring to with your use of $First$ and $Last$ -- has two problems, one inherent to O-P parsing and the other which can be (mostly) avoided. The first problem is that all non-terminals look the same to an operator-precedence grammar. That's the essence of the O-P parsing technique, so there's not much that can be done about it. The other problem is that $First$ (and $Last$) don't even distinguish between the presence and absence of a non-terminal. For this reason, $First(O)$ (not to be confused the the $LL$ algorithm's $FIRST\_k$ function) includes $\fbox{+}$, and $First(C)$ includes $\fbox{\<}$. In both cases, the terminal would not be in the $LL$ $FIRST$ set, because it does not appear exactly at the beginning of the right-hand side, but rather immediately following the non-terminal at the beginning.

Given that the $First$ function can't distinguish between terminals which follow non-terminals and terminals which just start a production, it is hardly surprising that the parser doesn't really care whether or not $\fbox{\<}$ has an argument. Regardless of whether there is an expression before the $\fbox{\<}$ or not, the grammar simply sees that $\fbox{if} \lessdot \fbox{\<}$. And consequently, it doesn't complain when the two tokens are consecutive.

Now, *in theory*, the O-P parser uses precedence relations only to find a *possible* handle. Once it does so, the parser should find the grammar rule for which the handle is the right-hand side, if any, or throw an error. But I've rarely seen a description of O-P parsing which actually does that. Instead, the simplifying assumption is made that you can figure out which rule to reduce with by just looking at the last terminal on the stack, and that the input is correct \[Note 3\].

It's actually pretty easy to extend O-P to get around this problem. The basic idea is to divide the relations into two classes: those which apply to adjacent terminals, and those which apply to terminals separated by a single-non-terminal. (Since the grammar is an operator grammar, those are the only two possibilities.) I refer to these as 0- and 1-superscripted relations, where the number refers to the number of intervening non-terminals.

To compute these relations, we start by compute two groups of $First$ and $Last$ sets, using the same subscript notation. So $First^0(N)$ is the set of terminals which *immediately* start a right-hand side of $N$, and $First^1(N)$ is the set of terminals which immediately follow a non-terminal which immediately starts a right-hand side.These two sets are not necessarily disjoint, for example in the case of an operator like $\fbox{-}$ which can be either prefix or infix, but their union is the classic $First(N)$ set.

More precisely, using the standard convention that lower-case letters $a$, $b$, $c$… represent terminals, upper-case letters $A$, $B$, $C$… represent non-terminals while $P$, $Q$… represent productions, and greek letters $\alpha$, $\beta$, $\gamma$… represent *possibly-empty* sequences of grammar symbols, either terminals or non-terminals, we define:

$$First^0(N) = \\{ a : N \Rightarrow^\* a\beta \\}$$ $$First^1(N) = \\{ a : N \Rightarrow^\* B a\beta \\}$$ $$Last^0(N) = \\{ a : N \Rightarrow^\* \beta a\\}$$ $$Last^1(N) = \\{ a : N \Rightarrow^\* a\beta aB\\}$$ Correspondingly, we define two of each precedence relationship.

$$a \lessdot^0 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^0(B)$$ $$a \lessdot^1 b \iff \exists N,B : N \to \alpha a B \beta, b \in First^1(B)$$ $$a \gtrdot^0 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^0(A)$$ $$a \gtrdot^1 b \iff \exists N,A : N \to \alpha A b \beta, a \in Last^1(A)$$ $$a \doteq^0 b \iff \exists N : N \to \alpha a b \beta$$ $$a \doteq^1 b \iff \exists N,X : N \to \alpha a X b \beta$$ For each production $N \to \alpha A x \beta$, add $Last\_0(A) \gtrdot\_0 x$ and $Last\_1(A) \gtrdot\_1 x$

To parse, we use essentially the standard algorithm taking account of the presence or absence of non-terminals. Conceptually, we store both terminals and non-terminals on the stack. (In practice, I would keep separate stacks and use a flag on the terminal to indicate whether it has a non-terminal on top of it or not -- there can only be one, because it is an operator grammar.) At each step, we compare the incoming terminal with the topmost terminal on the stack. If the actual top of the stack is a non-terminal, we use the 1-superscripted relations; otherwise, we use the 0-superscripted relations. As before, if no relation exists between the two terminals an error is signalled (and that will catch your error).

Now, to assist with the identification of the production corresponding to the handle, we can store a little bit more information on the stack. When we push a terminal onto the stack, it is either because there was a $\lessdot$ relation with the previous stacked terminal, in which case we are starting a right-hand side, or there was a $\doteq$ relation with the previous terminal, which must be part of the same right-hand side. In either case, we can record the prefix of the appropriate RHS (up to the curren point) instead of the terminal. That has two advantages.

* it lets us distinguish between prefix and infix operators in a natural way; and
* it really lets us assign them different precedences, because we can actually define the precedence relations as relations between RHS location and incoming terminal, instead of terminal and incoming terminal, thereby allowing a bit more discrimination. (That's needed to give unary minus tighter binding.)

Now before you rush out and start coding a parser generator based on this idea, please re-read \[Note 1\], because at this point we are 90% of the way to rediscovering $LR$ parsing. I really believe that if you follow this algorithm closely, you will gain some useful intuitions for understanding $LR$ parsing. And it should be obvious that it is only a small step between "extended" O-P parsing and a table-driven $LALR(1)$ parser, at which point you might as well haul out bison or some other yacc-derivative and let it build your parser for you. \[Note 4\]

### Notes

1. Personally, I would have dropped LL-parsing, but who am I to judge :) It's not that O-P parsing is at all useful once the LALR(1) construction algorithm is known. It isn't, and the problem you're having is a case in point. Any language parseable by O-P can be parsed correctly and unambiguously with LALR(1), and with the same computational complexity. (Indeed, with essentially the same amount of time and space.) The only reason to keep O-P hanging around at all is that (again, in my opinion), thinking about O-P parsing will (if you think about it the right way) lead you to the key insights which lead to LR parsing.
2. I like the cover.
3. In practice, there is another classic problem with O-P parsing, which was mentioned in the text I replaced with an … in the Dragon book quote: the algorithm as described can't distinguish between prefix and infix uses of $\fbox{-}$. The usual hack used to fix that problem is to use a small state machine (two states, typically) which is sufficient to reveal whether or not an operator was preceded by an operand. That's also sufficient to throw an error if an operator cannot be used as a prefix operator, so practical O-P parsers don't really have a problem. A while back, I described such an algorithm in a StackOverflow answer
4. I'm sure I'm not the first person to have thought up this idea, in several decades of very clever people thinking about parsing algorithms, but I haven't ever seen it described anywhere. As I said, I worked it out while I was trying to grasp the mechanics of bottom-up parsing, and afterwards it seemed a bit redundant. But if anyone passing by happens to know a literature reference, I'd appreciate a pointer.

---
Tags: formal-grammars
---


# Question
Title: Is there a generalization of Huffman Coding to Arithmetic coding?
In trying to understand the relationships between Huffman Coding, Arithmetic Coding, and Range Coding, I began to think of the shortcomings of Huffman coding to be related to the problem of fractional bit-packing.

That is, suppose you have 240 possible values for a symbol, and needed to encode this into bits, you would be stuck with 8 bits per symbol, even though you do not need a "full" 8, as 8 can express 256 possible values per symbol. A solution to this problem is something I've seen referred to as "fractional bit packing", where you are able "bitshift" by a non-power of two using multiplication. Just like multiplication of powers-of-two are shifting `x * 2 == x << 1` and `x * 4 == x << 2` and so on for all powers of two, so too you can "shift" with a non-power-of-2 by multiplying instead, and pack in fractional-bit-sized symbols.

The problem is similar with Huffman coding: you end up with codes that must be non-fractionally-bit-sized in length, and therefore it has this packing inefficiency. However, you can't just use the solution of fracitonal-bit-packing, because this solution assumes fixed sized symbols.

The question is, **are there any papers or solutions to improve on huffman coding with a similar idea to fractional-bit-packing to achieve something similar to arithmetic coding?** (or any results to the contrary).

# Answer
Let's look at a slightly different way of thinking about Huffman coding.

Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for this example.

Suppose our state is a large integer, which we will call $s$. You can think of encoding as a function which takes the current state, and a symbol to encode, and returns the new state:

$$\begin{align\*} \hbox{encode}(s, A) &= 2s\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3\\ \end{align\*}$$

So let's start with the state 11 (which is 1011 in binary), encode the symbol B. The new state is 46, which is 101110 in binary. As you can see, this is the "old" state with the sequence 10 added to the end. We have essentially "output" the bit sequence 10.

So far, so good.

Now think for a moment about how arithmetic coding works. If you put the probabilities over a common denominator, the symbol A actually represents the range $\[\frac{0}{4},\frac{2}{4})$, the symbol B represents the range $\[\frac{2}{4},\frac{3}{4})$ and the symbol C represents the range $\[\frac{3}{4},\frac{4}{4})$.

Basically what we're doing here is multiplying everything by the common denominator. Imagine that the state was actually in base 4. Encoding a symbol B is really outputting the digit 2 in that base, and encoding a symbol C is outputting the digit 3 in that base.

However, symbol A is a little different, because it isn't a whole digit in base 4.

Instead, we can think of the alphabet as the set of symbols A\_0, A\_1, B, C, with equal probability. This, again, has an optimal Huffman code 00, 01, 10, 11. Or, again, we can think of this in base 4. To encode a symbol, we just do:

$$\begin{align\*} \hbox{encode}(s, A\_0) &= 4s + 0\\ \hbox{encode}(s, A\_1) &= 4s + 1\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3 \end{align\*}$$

So now it's clear how to encode symbols B and C, but to encode a symbol A, we have a choice. Which of $A\_0$ and $A\_1$ should we use?

Now here's the clever idea: we steal one bit of information from the state $s$:

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$ $$i = s \bmod 2$$

and then $\hbox{encode}(s', A\_i)$.

Using our previous example, $s=11$, we find that $s'=5$ and $i=1$, and then $\hbox{encode}(5, A\_1) = 4\times 5+1 = 21$. The new state is 10101 in binary.

Now this doesn't produce exactly the same bit output as Huffman coding, but it does generate an output which has the same length. And what I hope you can see is that this is also uniquely decodable. To decode a symbol, we take the remainder when divided by 4. If the value is 2 or 3, then the symbol is B or C respectively. If it's 0 or 1, then the symbol is A, and then we can put the bit of information back by multiplying the state by 2 and adding either 0 or 1.

The nice thing about this approach is that it extends naturally to fractional-bit encoding, when the numerator and/or denominator of the probabilities are not powers of two. Suppose we have two symbols, A and B, where the probability of A is $\frac{3}{5}$ and the probability of B is $\frac{2}{5}$. Then we can encode a symbol with:

$$\begin{align\*} \hbox{encode}(s, A\_0) &= 5s + 0\\ \hbox{encode}(s, A\_1) &= 5s + 1\\ \hbox{encode}(s, A\_2) &= 5s + 2\\ \hbox{encode}(s, B\_0) &= 5s + 3\\ \hbox{encode}(s, B\_1) &= 5s + 4 \end{align\*}$$

To encode the symbol A, we take $s' = \left\lfloor \frac{s}{3} \right\rfloor$ and $i = s \bmod 3$, and then $\hbox{encode}(s', A\_i)$.

This is equivalent to arithmetic coding. It's actually a family of methods known as Asymmetric Numeral Systems, and was developed over the last few years by Jarek Duda. The meaning of the name should be obvious: to encode a symbol with probability $\frac{p}{q}$, you conceptually steal a base-p digit from the state, and then add a base-q digit. The asymmetry comes from interpreting the state as a numeral in two different bases.

The reason why it's a family of coding methods is that what we've seen here is impractical by itself; it needs some modifications to deal with the fact that you probably don't have infinite-precision integers to manipulate the state variable efficiently, and there are various ways that you can achieve this. Arithmetic coding, of course, has a similar issue with precision for its state.

Practical variants include rANS (the "r" means "ratio") and tANS ("table-driven").

ANS has a few interesting advantages over arithmetic coding, both practical and theoretical:

* Unlike arithmetic coding, the "state" is a single word, rather than a pair of words.
* Not only that, but an ANS encoder and its corresponding decoder have *identical* states and their operations are completely symmetric. This raises some interesting possibilities, such as that you can interleave different streams of encoded symbols and everything synchronises perfectly.
* Practical implementations need, of course, to "output" information as you go, and not just collect it in a big integer to be written at the end. However, the size of the "output" can be configured in return for (usually modest) compression loss. So where arithmetic coders must output a bit at a time, ANS can output a byte or a nybble at a time. This gives you a direct tradeoff between speed and compression.
* It appears to be about as fast on current-generation hardware as binary arithmetic coding, and hence competitive with Huffman coding. This makes it much faster than large-alphabet arithmetic coding and its variants (e.g. range coding).
* It appears to be patent-free.

I don't think I'm ever going to do arithmetic coding again.
> 14 votes

# Answer
As a simple example, if you had three symbols with probability 1/3rd each, your optimal Huffman encoding would use the three symbols 0, 10 and 11 with an average of 5/3rd bits.

There are 243 symbols created by concatenating 5 of the original symbols, each with probability 1/243. Which is much closer to 1/256. The optimal Huffman encoding will encode 13 of these groups in 7 bits and 230 groups in 8 bits, for an average of 7.9465 bits per group or 1.5893 bits per original symbol, down from 1.6667 bits for the original Huffman coding, with arithmetic coding taking 1.5850 bits.

So in theory you could just combine two symbols each into one larger symbol, or three symbols each into one larger symbol, and use Hufman coding for the combinations.
> 2 votes

---
Tags: information-theory, data-compression, coding-theory, entropy, huffman-coding
---


# Question
Title: How to efficiently code Dynamic Time Warping algorithm with a locality constrain?
For given two lists $\[s\_1, s\_2, ... s\_n\]$ and $\[t\_1, t\_2, ..., t\_m\]$

I need to implement DTW algorithm with one extra constraint:

If $s\_i$ is matched with $t\_j$ then the next element $s\_{i+1}$ has to be matched with some $t\_{j+k}$ **close enough** to $t\_j$ (i.e. $0 \le k \le W$ for some fixed window size $W$).

This constraint has to hold for each $s\_i$.

1) Does there exist $O(nm)$ solution to such problem?

2) If an efficient algorithm does not exist, what would be a good practical solution?

(Note that locality constraint mentioned in the DTW link above is different from the constraint I need).

# Answer
There is a $O(nmW)$-time algorithm using dynamic programming. Let $A\[i,j\] = $ the cost of the best matching of $\[s\_1,\dots,s\_i\]$ to $\[t\_1,\dots,t\_j\]$ such that $s\_i$ is matched to $t\_j$. Then

$$A\[i,j\] = \min\\{c(s\_i,t\_j) + A\[i-1,j-k\] : k=0,1,\dots,W\\}.$$

If you consider $W$ a constant, then you obtain a $O(nm)$-time algorithm.

I don't know if the factor of $W$ can be eliminated.

---

If $W$ is large, this can be improved to $O(nm \lg W)$ time. The basic primitive we need is:

Given an array $B\[1..m\]$ and $W$, preprocess $B$ so that we can efficiently answer queries "compute $\min\\{B\[i\],B\[i+2\],\dots,B\[i+W-1\]\\}$".

Here's how to do that. Assume first for simplicity that $W$ is a power of two. You construct secondary arrays $M\_2,M\_4,M\_8,\dots,M\_W$ such that $M\_w\[i\] = \min\\{B\[i\],B\[i+1\],\dots,B\[i+w-1\]\\}$. You can build them up in $O(m \lg W)$ time, as each $M\_{2w}$ can be constructed from $M\_w$ in $O(m)$ time. Thus if $W$ is a power of two you can answer subsequent queries in $O(1)$ time per query.

If $W$ isn't a power of two, you can still express the interval $i,i+1,i+2,\dots,i+W-1$ as the union of at most $\lg W$ intervals each of whose width is a power of two. Thus, if $W$ isn't a power of 2, you can answer subsequent queries in $O(\lg W)$ time per query.

Finally, apply this to the original problem. You apply this to each row of $A$, i.e., to $A\[i,\cdot\]$ for each $i$. Then the recurrence can be computed using a single query, and it takes $O(\lg W)$ time instead of $O(W)$ time to compute the min. You'll need to update the secondary arrays each time you update $A\[i,j\]$, but this takes only $O(\lg W)$ time per update to $A\[i,j\]$ (as there are only $\lg W$ secondary arrays to update).

In all, you obtain an algorithm whose running time is $O(nm \lg W)$ and with $O(nm \lg W)$ space usage. (I suspect it's also possible to achieve $O(nm \lg W)$ time and $O(nm)$ space, if necessary, by only storing $M\_w\[i\]$ for values of $i$ that are a multiple of $w$, at the cost of about a 2x increase in running time.)
> 2 votes

# Answer
Although the accepted answer is correct, an alternative solution also works well in practise, when one is not very strict about the $0 \leq k \leq W$ constraint, but still wants to have the "locality" property:

1) Let $cost\[i\]\[j\]$ be the minimum cost to align $\[s\_1, s\_2, ... s\_i\]$ and $\[t\_1, t\_2, ..., t\_j\]$. We first build $cost$ matrix in $O(nm)$ time using dynamic programming.

2) We find the **minimum** index $last$ such that $s\_n$ could have been aligned with $t\_{last}$:

```
last = m;
// While ignoring extra element in the sequence (t_n) won't make cost worse
while (cost[n][last] >= cost[n][last - 1])
    // We ignore it
    last--;
}
return last;

```

3) After we know $last$, we find the **maximum** index $first$ such that $s\_1$ could have been aligned with $t\_{first}$:

```
int first = last;
    int i = n - 1;
    while (i > 0) {
        // if to align i-th element with first is not worse that other options
        if (cost[i - 1][first] + distance(i, first) <= cost[i][first - 1]) {
            // we align it
            i--;
        } else {
            // otherwise we have to use one more point from sequence (t_n)
            first--;
        }
    }
return first;

```

4) At the end we have found a minimal interval $\[t\_{first}, ... t\_{last}\]$ with which the whole sequence $(s\_n)$ was aligned. If the length of this interval is not too big (e.g. less than $\frac{3}{2}n)$ we can assume that an alignment satisfying "locality" property has been found.

The nice thing about this approach is that it can be coded in $O(nm)$ time and the code is relatively short.
> 0 votes

---
Tags: algorithms, dynamic-programming, subsequences, time-series-analysis
---


# Question
Title: No subset of RE captures the set of TMs halting on themselves as input
For a property $P$ of languages, which we identify with the set of languages satisfying it, let $L\_P = \\{ \langle M \rangle \mid L(M) \in P \\}$ be the set of descriptions of Turing machines whose languages satisfy $P$.

> How can we prove that there's no property $\displaystyle P\subseteq RE $ for which $ L\_{P}=K $, where $K=\\{\langle M \rangle \mid M(\langle M \rangle)\\!\downarrow\\} $?

# Answer
According to the recursion theorem, there is a Turing machine $M$ such that $L(M) = \\{\langle M \rangle\\}$. If $P$ is a property such that $L\_P = K$ then $\langle M \rangle \in K$ implies that $L(M) = \\{ \langle M \rangle \\} \in P$. Now it is easy to construct a different machine $M' \neq M$ such that $L(M') = \\{ \langle M \rangle \\}$. Since $L(M') \in P$ and $L\_P = K$, we must have $\langle M' \rangle \in K$, yet $M'$ doesn't halt on $\langle M' \rangle$.

Note that this solution doesn't use the condition $P \subseteq RE$.
> 2 votes

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


# Question
Title: Conflicting definitions of quasipolynomial time
The textbook The Nature of Computation uses the following definition of quasipolynomial time:

> A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k \> 0$, where $\log^k n$ denotes $(\log n)^k$. Let us define **QuasiP** as the class of problems that can be solved in quasipolynomial time.

So presumably the definition for **QuasiP** could be written $TIME(\bigcup\_k 2^{\Theta(\log^k n)})$. However every other definition I've found on the web, in particular the one from Wikipedia, suggests the alternative definition $TIME(\bigcup\_k 2^{O(\log^k n)})$.
Now I can't see how these definitions are supposed to be equivalent. In fact I can imagine that there's a function $f$ that requires $2^{\log n}$ steps for even values of $n$ and $1$ step for odd values of $n.$ $f$ would fail to be in $2^{\Theta(\log^0 n)}$ because of the even values of $n$ and it would fail to be in $2^{\Theta(\log^k n)}$ for any $k \> 0$ because of the odd values of $n$. However $f$ is still in $2^{O(\log^1 n)}$.
So apparently such an $f$ is in **QuasiP** according to the second definition but not according to the first. Did I make a mistake in the reasoning here? And if not am I correct in assuming that the definition in The Nature of Computation is erroneous?

# Answer
> 6 votes
The equality

$Time\left(\bigcup\limits\_k 2^{O\left(\log^k n\right)}\right)= Time\left(\bigcup\limits\_k 2^{\theta\left(\log^k n\right)}\right)$

is an equality betweeen two sets of languages decidable by certain Turing machines, and not an equality between sets of functions $f:\mathbb{N}\rightarrow\mathbb{N}$.

The function you constructed is an example of a function in $\bigcup\limits\_k 2^{O\left(\log^k n\right)}\setminus \bigcup\limits\_k 2^{\theta\left(\log^k n\right)}$, but this does not contradict the above equality.

Let $L\in Time\left(2^{O\left(\log^k n\right)}\right)$ for some $k\in\mathbb{N}$, be a language decidable by a Turing machine which runs in time $2^{O\left(\log^k n\right)}$. You can simply construct an equivalent Turing machine which runs in time $2^{\theta\left(\log^k n\right)}$ by adding redundant steps in case the computation ended too quickly, and this shows $L\in Time\left(2^{\theta\left(\log^k n\right)}\right)$.

# Answer
> 7 votes
Both definitions are equivalent, since when we say that a problem can be solved in time $t$, we usually mean that it can be solved in time *at most* $t$. For example, a problem can be solved in time $n$ if there is an algorithm solving it whose running time $T(n)$ satisfies $T(n) \leq n$.

---
Tags: terminology, time-complexity, asymptotics, landau-notation
---


# Question
Title: For a given certain situation how to prove that the system will never get into the state of Deadlock
The situation is as follows

> 'm' process shares 'n' resources of same type. The maximum need of each process does not exceed 'n' and the sum all their maximum needs is always less than m+n. In this set up will deadlock ever occur

This is a question from **Operating System Concepts** by **Silberschatz, Gagne and Galvin**.

I tried to prove this using using *Banker's Algorithm*. Initially, I assumed that the *Allocated Matrix* for 'm' processes is a zero matrix. And *Maximum Matrix* of 'm' process is 'n'. Since *Need matrix* is difference of *Allocated Matrix* and *Max Matrix* therefore, *Need Martix* is equilavent of *Maximum Matrix*. And at last *Available Matrix* is equal to 'n'.

At this point I feel stuck and not able to find a way to proceed. Looking forward for help from you guys. Thanks in advance.

# Answer
The solution of a related problem helped me in the proof. Here I am first sharing that question along with one of the possible answer, and later propose my proof in a similar manner.

> Consider a system which has $3$ processes and each process requires $2$ identical resources to complete their execution then what is the minimum number of resources required to ensure deadlock free execution.

The easy way to do this is, *allocate exactly one less than the required number of instances of the resource to all the processes. Except for one of the processes, whose need is completely fulfilled*.

If there are $3$ processes say $P\_1,P\_2,P\_3$. We give exactly one instance of the resource to $P\_2, P\_3$ and two instances of resource to $P\_1$. In total $4$ instances of the resource are required to ensure a deadlock free execution.

Let us now generalize this concept and see what we get.

---

There are $m$ processes say $P\_1,P\_2,P\_3,..,P\_m$ sharing $n$ resources. And let $S\_i$ be the maximum requirement of a process $P\_i$ to execute completely.

Now to ensure that system is deadlock-free, we ***allocate all the processes exactly one less than the required number of instances of the resource except for one of the processes whose requirement is completely fulfilled***.

Mathematically,

$$\sum\_{i=1}^{m}S\_i-m+1 \leq n$$

or we can say

$$\sum\_{i=1}^{m}S\_i \< m+n$$

This expression tells us that as long as the sum of maximum need of all the processes is less than $m+n$, the system will remain deadlock free.

HTH
> 0 votes

# Answer
The question in the given situation is equivalent to the question: is it possible to create or to design a system such that m processes sharing n resources of the same type may enter a deadlock state subject to the following: each process needs less than or equal to n resources, and the total number of needed resources is less than or equal to m+n (“For a given certain situation”, 2015)?

Assumptions. Processes run on a single processor. The processor can execute a statement from one and only one process at a time. In other words every statement in a process is an atomic operation. After ending a statement and before executing the next statement of a process, the processor can switch to another process and execute the other process’ next statement.

Consider using a Petri Net for the system design. In terms of Petri Nets a deadlock is a situation when no transition is enabled. Figure 1 is an example of a system that may enter a deadlock state. In this example, m=2 and n=2. For the same number of processes and resource needs per process (m=2 and n=2), it is also possible to create a system that does not enter a deadlock state. Each of Figure 2 and Figure 3 is an example of two systems that will never reach a deadlock state.

Figure 1: A System with Deadlock

Figure 2: A System without Deadlock

Figure 3: Another System without Deadlock

## Notes

For Figure 1, the transitions related to Process 1 (Process 2) are:

* T0 (T4) – get 1 resource unit.
* T1 (T5) – get 1 resource unit.
* T2 (T6) – process critical section.
* T3 (T7) – return 2 resource units.

For Figure 2, the transitions related to Process 1 (Process 2) are:

* T0 (T4) – get 1 resource unit.
* T1 (T5) – get 1 resource unit.
* T2 (T6) – process critical section.
* T3 (T7) – return 2 resource units.
* T8 (T9) – return 1 resource unit.

For Figure 3, the transitions related to Process 1 (Process 2) are:

* T0 (T3) – get 2 resource units.
* T1 (T4) – process critical section.
* T2 (T5) – return 2 resource units.

For the PDF version of this reply, Figure 1, Figure 2 and Figure 3 are interactive, dynamic diagrams.

## References

Chionglo, J. F (2015). "A Reply to "For a given certain situation how to prove that the system will never get into the state of deadlock" at Computer Science Stack Exchange". Available at http://www.aespen.ca/AEnswers/OnMWQ1449933168.pdf

“For a given certain situation how to prove that the system will never get into the state of Deadlock” (2015). Mathematics Stack Exchange. Retrieved on Dec. 2, 2015 at For a given certain situation how to prove that the system will never get into the state of Deadlock.
> 3 votes

---
Tags: operating-systems, concurrency, deadlocks
---


title: Visit all vertices on directed graph

text:
# Question
Title: Visit all vertices on directed graph
We are given a directed graph, the number of vertices and edges. We need to decide, whether there is a \[starting\] vertex where we can get started and visit all the vertices. You can revisit vertices, but can't "use" edges twice or more time. All this in linear time.

I was thinking about DFS - if the number of vertices in the result matches the total number of vertices, obviously there is a way to visit all the vertices. The only problem about this - I guess - is that how do I choose the vertex where I'm starting off. Or can I do DFS with all the vertices and still remain in linear time?

(I tried to look into Eulerian path and Hamilton path problems, but I think they have nothing to do with my problem)

Any feedback is appreciated.

# Answer
Actually, you can use DFS to solve this problem.

Let's denote the set of all roots in graph $G$ as $R\_G$

**Lemma:** for every run of DFS, the last DFS tree contains $R\_G$. Let $ T\_1, T\_2, ..., T\_t $ be the DFS trees found in a DFS run, such that $T\_i$ is the ith tree that was discovered. Assume that there is a root $r$ such that $r \in T\_i$ for $i\<t$. Denote $r\_k$ the root of the kth tree.

Since $r$ is a root, there is a route from $r$ to $r\_t$ in $G$. let $u$ be the first vertex on that route such that $u \in T\_t$, and let $w$ be the vertex before $u$ on that route.

When DFS discovers $w$, the vertex $u$ hasn't been discovered yet (since $u \in T\_t$ and $w \in T\_i$). So $w$ is a predecessor of $u$ in the DFS "forest" - and that contradicts that $u$ and $w$ are in different DFS trees.

We now conclude that $R\_G \subseteq T\_t$

So an algorithm to decide whether there is a root for $G$: we run a DFS, and then start a second DFS from the root of the last tree. if in that DFS run we've found all the vertices, and we have a root. otherwise, by the lemma, there is no root for $G$

The time complexity is ofcourse $O(|V| + |E|)$ since we did 2 runs of DFS.
> 0 votes

# Answer
The first question you need to ask yourself, is when does it happen that there is *no* such vertex. For undirected graphs the answer is easy: such a vertex exists if and only if the graph is *connected*. DFS/BFS allow us to decompose the graph into connected components, and in particular we can find out whether there is more than one.

For directed graphs, it could happen that the underlying undirected graph is connected, yet the directed graph itself has no vertex from which you can reach all others. An example is a path with two edges directed toward the center. The corresponding refinement of the concept of *connected components* is *strongly connected components*, in which each vertex is reachable from any other. We can contract each strongly connected component to a single vertex, and then what we are left with is a DAG (directed acyclic graph; can you see why?). The question you should be asking yourself now is:

> Given a DAG, when is there a vertex from which all other vertices are reachable?

Once you answer this question, all you need is an algorithm for finding strongly connected components. There are several DFS-based algorithms for that available on the web.

(Note: while this may not be the simplest solution, that is, there might be "shortcuts", the concept of strongly connected components is inherently useful and good to be aware of.)
> 2 votes

# Answer
Actually, your question is related to Eulerian graph. I think all you need to do is calculate the in-degrees and out-degrees of each vertex. If there is any vertex whose number of in-degrees is not equal to number of out-degrees, then the answer to your question is NO. if all vertices satisfy this property(inDegree\[u\] = outDegree\[u\]), then the answer is YES.

This is much easier than using DFS when you don't actually need to compute the cycle and only find if it exists.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Maximal majoritarian program under incomplete voting
I have conducted two surveys on French political preferences. As half of each sample (of ~1000 persons) gave a satisfactory margin error, I have randomly displayed (or not) several questions. Now, I have an incomplete dataset of the preferences of the sample over many political propositions (I can provide it if needed). For the sake of simplicity, let us assume that for each proposition of reform, either the respondent agrees for a change (True), or not (False), either the question was not asked to him-her (NA).

I am looking for a political program (i.e. a set of propositions) which gathers a majority of adhesion: I call this a *majoritarian program*. For a program to be majoritarian, we need that a majority of the respondents agree jointly with **all** the propositions of the set. As the dataset is incomplete, we need to **check** that any subset of propositions in the program gathers a majority (i.e. gathers more True than False). Indeed, it could be that only 5 respondents have voted to all the propositions in the program, by chance all favorably; then, we could still not deduce that this program is majoritarian because one of its proposition could have failed to obtain a majority itself. Finally, I am looking for the *maximal* majoritarian program, i.e. the largest one (in terms of number of propositions).

Does anyone have an idea on how to solve exactly this computational problem? Any insight on the question is welcome, including broader reflection on optimizing over the subsets of a big set.

So far, three methods have come to my mind to solve this problem:

1. **Brute force** I have optimized an exact algorithm (which I can provide). With my (rather small) dataset (a hundred propositions), it works if I restrict the number of propositions I analyze to 47, but it is way too computationally demanding if I try to analyze all propositions. Indeed, the number of potential programs of size k grows exponentially: it is $2^k$.
2. **Completion of data** I haven't try this because I don't know the theory of imputing missing data. If such an imputation proves always reliable, then the problem may be solved. Indeed, a friend have shown me a way to reduce my problem to linear optimization as long as the dataset is complete.
3. **Machine learning** By defining appropriate an weight on each answer, that depends on the examined program, we can train a neural network to find the best ordering of propositions so as to form our program with the adequate number of highest-ranked propositions. (The gain function values individual adhesion to the program as well as its size.) However, this method is just an heuristic for the problem, and its solution is simply a proxy for the real answer. Indeed, the necessary check of the *potentially maximal* program may take too long a time (as we need to examine each subset of propositions in the program). Nonetheless, I will implement this method soon.

# Answer
We can formalize this problem as follows. Let the propositions be numbered $1,2,\dots,n$. We have a function $f$ that, given a subset $S \subseteq \\{1,2,\dots,n\\}$ of propositions, returns true or false according to whether every proposition in $S$ has majority support among the survey respondents who saw every proposition in $S$. Define $S \subseteq \\{1,2,\dots,n\\}$ to be a majoritarian program if $f(T)$ is true for all $T \subseteq S$. Now we want an algorithm that, given ability to invoke $f$, finds the largest majoritarian program $S \subseteq \\{1,2,\dots,n\\}$.

We will of course interpret $S$ as follows: for each $i \in S$, we take whichever side of proposition $i$ has majority support (when considered in isolation; among all survey respondents who saw $i$), and take the conjunction of all of those. Given $S$ you can easily compute $f(S)$ from the survey responses.

Here is one natural but not necessarily optimal algorithm for this. Basically, you grow subsets from the "bottom up". In particular, the algorithm looks like this:

```
Try(S):
1. If S is not a majoritarian program, return
2. If S is larger than the largest so far, remember S as the largest so far.
3. For each i in 1+max(S) .. n:
4.     Try(S ∪ {i})

```

You start by invoking `Try({})`, and when it returns, the best subset so far is the largest majoritarian program possible. This effectively takes small subsets and tries to grow them to become bigger, but if they don't get majority support, the search is pruned and it stops trying to grow that set.

The running time could be exponential. If you get lucky, you could hope that it runs more efficiently than that, though I don't know if you'll be lucky.

As a heuristic, you could sort the propositions by order of polarization, from most unanimous to most controversial. That might speed up the search, or allow you to cut off the search after a certain time limit and take the best you've seen so far (with no guarantee that it is optimal, but the hope that it might be close).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Does every data type just boil down to nodes with pointers?
An array or vector is just a sequence of values. They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node.

Stacks and queues are two abstract data types commonly taught in Intro CS courses. Somewhere in the class, students often have to implement stacks and queues using a linked list as the underlying data structure, which means we are back to the same "collection of nodes" idea.

Priority queues can be created using a Heap. A heap can be thought of as a tree with the min value at the root. Trees of all sorts, including BSTs, AVL, heaps can be thought of as a collection of nodes connected by edges. These nodes are linked together where one node points to another.

It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node. Is that right? If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers? How do we go from nodes to binary code?

# Answer
Well, that is basically what all data structures boil down to. Data with connections. The nodes are all artificial - they don't actually exist physically. This is where the binary part comes in. You should create a few data structures in C++ and check out where your objects land in memory. It can be very interesting to learn about how the data is laid out in memory.

The main reason for so many different structures is that they all specialize in one thing or another. For example, it is typically faster to iterate through a vector instead of a linked list, due to how pages are pulled from memory. A linked list is better to store larger sized types because vectors must allocate extra space for unused slots (this is required in the design of a vector).

As a side note, an interesting data structure you may want to look at is a Hash Table. It does not quite follow the Nodes and Pointers system you are describing.

TL;DR: Containers basically all Nodes and Pointers but have very specific uses and are better for something and worse for others.
> 16 votes

# Answer
> It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node.

Oh, dear no. You are hurting me.

Like I tried to explain elsewhere ("What's the difference between a binary search tree and a binary heap?") even for a fixed data structure there are several levels to understand it.

Like the priority queue you mention, if you only want to use it, it is an abstract data type. You use it knowing what kind of objects it stores, and what questions you can ask it to do. That's more data structures as a bag of items. On the next level its famous implementation, the binary heap, can be *understood* as a binary tree, but the last level is for efficiency reasons implemented as an array. No nodes and pointers there.

And also for graphs for instance, which certainly look like nodes and pointers(edges), you have two basic representations, adjacency array and adjacency lists. Not all pointers I imagine.

When really trying to understand data structures you have to study their good points and teire weaknesses. Sometimes a representation uses an array for efficiency (either space or time) sometimes there are pointers (for flexibility). This holds **even** when you have good "canned" implementations like the C++ STL, because also there you can choose sometimes the underlying representations. There is always a trade-off there.
> 15 votes

# Answer
Let's make an analogy with mathematics. Consider the following sentence: "$f:\mathbb{R} \rightarrow \mathbb{R}$ is a continuous function". Functions are really defined in terms of relations, which are defined in terms of sets. The set of real numbers is the unique complete totally ordered field: all of these concepts have definitions in simpler terms. In order to talk about continuity you need the concept of neighborhood, which is defined in relation to a topology... and so on all the way down to the axioms of ZFC.

Nobody expects you to say all of that just to define a continuous function, otherwise nobody would be able to get any work done at all. We just "trust" that someone made the boring work for us.

Every data structure you can possibly think of boils down to the basic objects that your underlying computational model deals with, integers in some register if you use a random-access machine, or symbols on some tape if you use a Turing machine.

We use abstractions because they free our mind from trivial matters, allowing us to talk about more complex problems. It is perfectly reasonable to just "trust" that those structures work: spiraling down into every single detail is - unless you have a specific reason to do so - a futile exercise that doesn't add anything to your argument.
> 12 votes

# Answer
Here's a counter-example: in λ-calculus, every data type boils down to functions. λ-calculus doesn't have nodes or pointers, the only thing it has are functions, therefore everything must be implemented using functions.

This is an example of encoding booleans as functions, written in ECMAScript:

```
const T   = (thn, _  ) => thn,
      F   = (_  , els) => els,
      or  = (a  , b  ) => a(a, b),
      and = (a  , b  ) => a(b, a),
      not = a          => a(F, T),
      xor = (a  , b  ) => a(not(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

```

And this is a cons list:

```
const cons = (hd, tl) => which => which(hd, tl),
      first  = list => list(T),
      rest   = list => list(F);

```

Natural numbers can be implemented as iterator functions.

A set is the same thing as its characteristic function (i.e. the `contains` method).

Note that the above Church Encoding of Booleans is actually how conditionals are implemented in OO languages like Smalltalk, which don't have booleans, conditionals, or loops as language constructs and implement them purely as a library feature. An example in Scala:

```
sealed abstract trait Boolean {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def ∧(other: => Boolean): Boolean
  def ∨(other: => Boolean): Boolean
  val ¬ : Boolean

  final val unary_! = ¬
  final def &(other: => Boolean) = ∧(other)
  final def |(other: => Boolean) = ∨(other)
}

case object True extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def ∧(other: => Boolean) = other
  override def ∨(other: => Boolean): this.type = this
  override final val ¬ = False
}

case object False extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def ∧(other: => Boolean): this.type = this
  override def ∨(other: => Boolean) = other
  override final val ¬ = True
}

object BooleanExtension {
  import scala.language.implicitConversions
  implicit def boolean2Boolean(b: => scala.Boolean) = if (b) True else False
}

import BooleanExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3

```
> 11 votes

# Answer
Many (most?) data structures are built of nodes and pointers. Arrays are another critical element of some data structures.

Ultimately, every data structure is just a bunch of words in memory, or just a bunch of bits. It's how they are structured and how we interpret and use them that matters.
> 6 votes

# Answer
*Implementation* of data structures always boils down to nodes and pointers, yes.

But why stop there? Implementation of nodes and pointers boils down to *bits.*

Implementation of bits boils down to electrical signals, magnetic storage, perhaps fiberoptic cables, etc. (In a word, physics.)

This is the *reductio ad absurdum* of the statement, "All data structures boil down to nodes and pointers." It's true—but it only relates to *implementation.*

---

Chris Date very able differentiates between *implementation* and *model*, though his essay is aimed at databases in particular.

We can go a little bit further if we realize that there is not a *single* dividing line between model and implementation. This is similar (if not identical) to the concept of "layers of abstraction."

At a given layer of abstraction, the layers "below" you (the layers on which you are building) are mere "implementation details" for the abstraction or *model* which you are addressing.

However, the lower layers of abstraction *themselves* have implementation details.

If you read a manual for a piece of software, you are learning about the abstraction layer "presented" by that piece of software, on which you can build your own abstractions (or just perform actions such as sending messages).

If you learn the *implementation details* of the piece of software, you will learn how the creators underpinned the abstractions which they built. The "implementation details" may include data structures and algorithms, among other things.

However, you would *not* consider voltage measurement to be part of the "implementation details" for any particular piece of software, even though this underlies how "bits" and "bytes" and "storage" actually work on the physical computer.

In summary, **data structures are an abstraction layer for reasoning about and implementing algorithms and software.** The fact that this abstraction layer is built on lower-level implementation details such as nodes and pointers is true but irrelevant *within the abstraction layer.*

---

A big part of really understanding a system is grasping *how* the abstraction layers fit together. So it's important to understand how data structures are *implemented.* But the fact that they *are* implemented, doesn't mean that the abstraction of data structures doesn't *exist.*
> 4 votes

# Answer
> An array or vector is just a sequence of values. They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node.

An array or a vector can be implemented with a linked list, but almost never should be.

That's because accessing the $n$-th element in a linked list requires traversing a chain of $n$ pointers, and thus requires $\Theta(n)$ time. A tree-based implementation (still made out of just nodes and pointers) is a bit more efficient, requiring just $\Theta(\log n)$ time to access an arbitrary leaf, but that's still far short of the $\Theta(1)$ access time provided by using *an actual array* (i.e. a sequential block of random access memory). Also, on the CPU, accessing the actual array is far simpler to implement and faster to execute, and storing it takes less memory due to not having to waste any space on pointers between separate nodes.

Of course, actual physical arrays have their down sides, too: notably, they need $\Theta(n)$ time to insert a new element, something that a linked list can do in $\Theta(1)$ time if you already have a pointer to a neighboring element. Insertions at the *end* of the physical array can be amortized down to $\Theta(1)$ on average, at the cost of at most a constant factor of extra memory, just by rounding the actual allocated size of the array up to e.g. the closest power of 2. But if you need to do a lot of insertions and/or removals of elements in the middle of your list, a physical array may not be the best implementation for your data structure. Pretty often, though, you can replace insertions and removals with swaps, which are cheap.

If you broaden your scope a little, to include physical contiguous arrays in your toolbox, almost all practical data structures can indeed be implemented with those together with nodes and pointers.

In fact, off the top of my head, I can't think of any common data structure that would *need* anything else, although in some cases a bit of space or time efficiency can be squeezed out by stepping outside that paradigm. As an illustrative example of such a case, consider the XOR linked list, which allows a two-way traversable linked list to be implemented using (asymptotically) no more space than a one-way linked list, by replacing the individual next and previous node pointers by their bitwise XOR, and has a few other convenient features too (such as a $\Theta(1)$ reversal operation). In practice, though, those features are rarely useful enough to overcome its drawbacks, which include extra implementation complexity and incompatibility with standard garbage collection schemes.
> 3 votes

# Answer
> If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers?

Because that's not what "data" means. You are conflating abstract ideas with implementations. "Data" is a highly abstract idea: It's just another name for "information." A bunch of linked nodes with pointers (a.k.a., a "linked data structure") is a much more concrete idea: It's a specific way of representing and organizing information.

Some data abstractions lend themselves very well to "linked" implementations. There are not many good ways to implement the branching nature of a fully general tree without using explicit nodes and pointers (or, some isomorphism of nodes and pointers.) But then, there are other abstractions that you would never implement using nodes and pointers. Floating point numbers come to mind.

Stacks and queues fall somewhere in between. There are times when it makes a lot of sense to do a linked implementation of a stack. There are other times when it makes much more sense to use an array and a single "stack pointer".
> 3 votes

---
Tags: algorithms, data-structures, abstract-data-types
---