# Question
Title: Minimum number of tree operations to normalize a labeled tree
Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many applications of commutativity (swapping the two children of a node) and associativity (tree rotations) are needed to bring this tree to a sorted normal form like $a(b(cd))$ or $a(b(c(d(ef))))$? Examples:

$$(bc)(ad)\mapsto((bc)a)d\mapsto(a(bc))d\mapsto a((bc)d)\mapsto a(b(cd))$$

\begin{align} &\phantom{{}\mapsto{}}((af)e)(c(db))\\ &\mapsto (a(fe))(c(db))\\ &\mapsto (a(fe))((cd)b)\\ &\mapsto (a(fe))(b(cd))\\ &\mapsto (a(ef))(b(cd))\\ &\mapsto a((ef)(b(cd)))\\ &\mapsto a((b(cd))(ef))\\ &\mapsto a(b((cd)(ef)))\\ &\mapsto a(b(c(d(ef)))) \end{align}

There are $C\_{n-1}\cdot n!$ possible trees on $n$ elements, and about $2n$ possible operations to apply at each stage, so the information theoretic bound gives $\Omega(\log\_{2n}(C\_{n-1}\cdot n!))=\Omega(n)$. On the other hand, if we first fully right associate, then we can perform adjacent swaps with $O(1)$ operations, leading to an upper bound of $O(n^2)$ operations.

I suspect that $O(n\log n)$ operations suffice, perhaps even $O(n)$, but I have not been able to improve on the above bounds. I know that $O(n)$ operations work if it is possible to perform exchanges in $O(1)$, but every element has its depth change by at most 1 per operation, so exchanges are rather expensive ($O(n)$) in this model. Probably we want to keep the tree balanced during the sorting, but assuming a balanced tree it's not clear how to sort effectively by block swaps.

# Answer
> 2 votes
$O(n \log n)$ operations suffice, as you conjectured. One can implement something akin to quicksort (using the median as the pivot in each stage). I'll describe the details below. For simplicity of exposition, let's assume $n$ is a power of two (though it all works for arbitrary powers of two). We'll bring the tree into a normal form, which is a complete binary tree (i.e., all leaves are at the same depth, $\lg n$).

Let $\alpha$ be the $n/2$th label (in sorted order of the labels). We'll first manipulate the tree so it has the form $xy$, where $x$ is a subtree of size $n/2$ containing all items $\le \alpha$ and $y$ is a subtree of size $n/2$ containing all items $\>\alpha$. Call this the partition operation. Then, we'll recursively apply the algorithm to the left subtree and to the right subtree.

I'll argue below that the partition operation can be done with $O(n)$ operations. Then it follows that the total number of operations performed by this algorithm obeys the recurrence relation

$$T(n) = 2 T(n/2) + O(n),$$

which has the solution $T(n) = O(n \log n)$. It follows that this algorithm takes $O(n \log n)$ operations.

So how do we do the partition operation? Well, suppose the tree is originally of the form $uv$. We'll recursively apply the partition algorithm to $u$, to get a tree of the form $u\_0u\_1$ where the leaves of $u\_0u\_1$ are the same as the leaves of $u$, but now $u\_0$ has all items of $u$ that are $\le \alpha$ and $u\_1$ has the items that are $\>\alpha$. Similarly, we'll recursively apply the partition algorithm to $v$, to get $v\_0v\_1$. So after the recursive calls to the partition algorithm, the tree has the form $(u\_0u\_1)(v\_0v\_1)$. Now by a constant number of applications of commutatively and associativity, this can be transformed to $(u\_0v\_0)(u\_1v\_1)$. At this point, the tree has the desired form, as $u\_0v\_0$ is composed of all of the items of $uv$ that are $\le \alpha$ and $u\_1v\_1$ is composed of all of the items of $uv$ that are $\>\alpha$.

The running time of the partition algorithm is given by the recurrence

$$U(n) = 2U(n/2) + O(1),$$

which has the solution $U(n) = O(n)$. Thus, the partition algorithm can be done in $O(n)$ operations.

# Answer
> 2 votes
$\Omega(n \log n)$ operations are needed. More precisely, starting from any given tree $T$ you can only reach $\exp(O(n+m))$ other trees in $m$ operations. The idea is to augment your information-theoretic argument with the observation that most operations commute. Note that we cannot hope to replace $O(n+m)$ with $O(m)$, since for $m = 1$ there can be $O(n) \gg 1$ reachable trees.

Let's represent sequences of operations using strings in the six-letter alphabet $\\{a, b, c, (, |, )\\}$, where the letters $a$, $b$, $c$ represent the basic operations "swap the children of the root", "apply a rotation at the root" and "apply a rotation at the root, but the other direction". The empty string represents the empty sequence. For well-formed strings $L$, $R$, their juxtaposition $LR$ represents "do $L$, then $R$", and $(L|R)$ represents "do $L$ in the left child of the root, and $R$ in the right child". It can be checked that any sequence of operations can be represented by some string and that every string represents at most one sequence of operations. I claim that in fact for any sequence of $m$ operations there is a string of length $O(n+m)$ which represents an equivalent sequence of operations. (Equivalent in the sense that, starting from $T$, one ends up at the same tree after applying either sequence.) Then we'll be done, since the number of such strings is only $\exp(O(n+m))$.

To begin, note that we can find a representing string where the letters $a$, $b$, $c$ together occur exactly $m$ times. So it suffices to bound the number of occurrences of the $(L|R)$ pattern. Let's not count the occurrences which directly precede or succeed one of the letters $a$, $b$, $c$, since there are at most $O(2m)$ of those. We can also assume that $(L|R)(K|S)$ doesn't occur anywhere since it can be replaced by $(LK|RS)$. It remains to consider patterns like $((L|R)|K)$. In this case, the idea is to try to write $(L|R)$ earlier in the string.

To be more precise, after parsing a prefix of our string, we have a state of the following form: a tree $T'$ (the current transformation of $T$), a node $v \in T'$ (the node at which our operations are currently based), and a subset $V \subseteq T'$ of "visited nodes", such that $v \in V$. Initially $T' = T$, $v$ is the root, and $V = \\{v\\}$. Let's say that after a rotation operation, the newly created node is unvisited, so that the number $|V|$ of visited nodes may decrease by one. But it never decreases otherwise, so it will increase at most $n+m$ times. Returning to the pattern $((L|R)|K)$, consider the state $(T', v, V)$ right before parsing $(L|R)$. If $v$ was already in $V$ earlier, then we can move $(L|R)$ to the corresponding position of our string; otherwise we are in one of only $n+m$ positions where $|V|$ increases.

---
Tags: complexity-theory, asymptotics, combinatorics
---


# Question
Title: I have found an example where regular expression is not closed under concatenation. Where am I wrong?
$a^n$ is a regular expression. $b^n$ is a regular expression. their concatenation is $a^nb^n$ which is not a regular expression.

# Answer
> 12 votes
If $n$ is fixed then $a^n$ is just a **single** word and so is $a^nb^n$.

If by $a^n$ you mean the language $\\{a^n \mid n \ge 0\\}$ (whose corresponding regular expression is $a^\*$) then the problem is that the variable $n$ in $a^n$ is independent of the variable with the same name in $b^n$.

The language obtained by concatenating $A=\\{a^n \mid n \ge 0\\}$ with $B=\\{b^n \mid n \ge 0\\}$ is $\\{xy \mid x \in A, y \in B\\} = \\{a^nb^m \mid n,m \ge 0\\}$ and the corresponding regular expression is $a^\*b^\*$. As you can see this is exactly the concatenation of $a^\*$ and $b^\*$.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: How to write a regex for repeated patterns
I have an alphabet $\Sigma = \\{a,b,\\#\\}$. I'm trying to write a regex that only accepts strings that have the same pattern before and after the $\\#$ without using back references. For example, $aab\\#aab$ is accepted, but not $aba\\#aab$. How in the world do you handle this? I thought you could maybe do something like $(a|b)^\*\\#(a|b)\*$, but this doesn't work at all.

# Answer
As pointed out by Pseudonym (in the comments) it's not a known pattern nor regular to be matched by a simple regex. If you knew the possibilities then sure you could use a regex `(aab#aab|bba#bba)`.

Another option is to write some code to use the regex to find a looser pattern but then validate the pattern that you wish to have:

const input = "aab#bba aab#aab"

/**
 *
 * @param {string} val input of plain text
 * @returns Array<string> Strings that have a matched pattern
 */
function findMirroredString(val = "") {

  const matches = val.match(/([a-z]+#[a-z]+)/g);

  // Return early if no matches were found by the regex.
  if (!matches) return [];

  // Filter to find the correct patter of "x#y" where x equals y
  return matches.filter(match => {
      // Split the parts by the # symbol and check if the two parts are equal,
      // If they are equal then the pattern is valid.
      const parts = match.split("#");
      return parts[0] === parts[1];
    });
}

console.log(
    findMirroredString(input)
);
```

> 1 votes

---
Tags: regular-expressions
---


title: UTC Time Offset

text:
# Question
Title: UTC Time Offset
Really confused about the meaning of offset in email headers.

Header date reads as:

```
Sat, 8 Jun 2019 11:45:15 −0500

```

Does the time shown 11:45:15 is the actual time at timezone -0500

OR

Actual time at time zone -0500 is calculated by subtracting offset??

Thanks.

# Answer
The timestamp you are seeing is the time in the given timezone using the given offset from UTC. The specific format of the timestamp you are looking at is an RFC2822 formatted timestamp which means that it follows a standard

Time: `11:45:15`

Offset from UTC: `−0500`

---

From RFC2822 spec:

```
   The zone specifies the offset from Coordinated Universal Time (UTC,
   formerly referred to as "Greenwich Mean Time") that the date and
   time-of-day represent.  The "+" or "-" indicates whether the
   time-of-day is ahead of (i.e., east of) or behind (i.e., west of)
   Universal Time.  The first two digits indicate the number of hours
   difference from Universal Time, and the last two digits indicate the
   number of minutes difference from Universal Time.  (Hence, +hhmm
   means +(hh * 60 + mm) minutes, and -hhmm means -(hh * 60 + mm)
   minutes).  The form "+0000" SHOULD be used to indicate a time zone at
   Universal Time.  Though "-0000" also indicates Universal Time, it is
   used to indicate that the time was generated on a system that may be
   in a local time zone other than Universal Time and therefore
   indicates that the date-time contains no information about the local
   time zone.

   A date-time specification MUST be semantically valid.  That is, the
   day-of-the-week (if included) MUST be the day implied by the date,
   the numeric day-of-month MUST be between 1 and the number of days
   allowed for the specified month (in the specified year), the
   time-of-day MUST be in the range 00:00:00 through 23:59:60 (the
   number of seconds allowing for a leap second; see [STD12]), and the
   zone MUST be within the range -9959 through +9959.

```
> 2 votes

# Answer
It simply means what is the difference between that time zone and the Greenwich mean time. Ex- UTC of India is +5.5
> 0 votes

---
Tags: real-time
---


# Question
Title: Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?
It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the problem has a polynomial time algorithm that is known about. Many applications of graphs don't require more than say 50 incident edges per node. For example in visualizations involving commutative diagrams of mathematics, rarely is there a need for anywhere close to that number of connections. This is because as the graph complexity grows, the diagram becomes more useless as a mnemonic for studying math.

So, my question is: if we constrain our nodes to have maximally a constant number of incident edges, then does the subgraph isomorphism problem become polynomial-time solvable?

That is, both the query graph $G$ and the large graph $H$ have bounded incident edges, such that you're trying to find an isomorphism of $G \xrightarrow{\sim} H' \subset H$.

# Answer
The problem is still NP-hard. You can show a polynomial-time reduction from the Hamiltonian path problem on graphs of degree at most $3$.
> 2 votes

---
Tags: graphs, time-complexity, polynomial-time, graph-isomorphism, subgraphs
---


# Question
Title: Counter automata with a bound on the counters?
It is widely known that the emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example).

However, what happens if we put a bound $k$ on the values stored by the counters? In this restricted model, the counters cannot be incremented more than $k$.

I think this makes the problem decidable, is this correct? And in this case, what is the complexity? Is there any reference about this problem?

# Answer
> 2 votes
If the counters are bounded by $k$, then the number of possible states is finite, so this is a finite-state machine, and emptiness for finite-state machines is decidable. In particular, if there are $c$ counters, each bounded by $k$, then there are $O(k^c)$ states, so emptiness can be tested in $O(k^c)$ time.

Assuming the automaton allows nondeterminism, it is easy to prove that the problem is NP-hard, by a reduction from 3SAT. (Store the value of $x\_i$ in the $i$th counter, selecting its value nondeterministically, then scan over the formula, checking each clause to see if it holds.)

---
Tags: automata, reference-request
---


# Question
Title: Why is the space complexity of finding anagrams in a string O(1) instead of O(n)?
In the problem find-all-anagrams-in-a-string, one tries to find all anagrams of a string $p$ (of length $k$) in a string $s$ (of length $n$) and return a list of the anagrams' starting indices.

The solution is to use a *sliding window* of length $k$ and move that window from the first index all the way up index $n - k + 1$. However, the solution states that the space complexity is $O(1)$ instead of $O(n)$. This is confusing to me, as shouldn't it be $O(n)$ as the worst case scenario is that $p$ is 1 character and $s$ (with length $n$) is comprised solely of $p$'s character? Then the start indices list we would return would be of length $n$.

# Answer
No, because you can write an algorithm with space complexity $O(1)$ that prints an unlimited amount of output. For instance, here is one

```
while true:
    print('yo!')

```

This means that the length of the output can be much larger than the space complexity, and the length of the output is not a lower bound on the space complexity.
> 1 votes

---
Tags: algorithms, time-complexity, data-structures
---


# Question
Title: What is the difference between Euler and Eulerian graph?
A Graph is Eulerian iff $\exists$ an Eulerian Cycle or all the vertices of Graph have even degree.
What is an Euler graph?
Wiki has a definition for the Eulerian graph but not for the Euler graph.

# Answer
The distinction is given at Wolfram.

The Euler graph is a graph in which all vertices have an even degree. This graph can be disconnected also.

The Eulerian graph is a graph in which there exists an Eulerian cycle. Equivalently, the graph must be connected and every vertex has an even degree.

In other words, all Eulerian graphs are Euler graphs but not vice-versa.
> 4 votes

---
Tags: graphs, discrete-mathematics
---


# Question
Title: How does primitive recursion handle mutual recursion?
My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this.

Is this true?

Thanks, friends :)

# Answer
Suppose you have two mutually recursive maps $f, g : \mathbb{N} \to \mathbb{N}$ defined by \begin{align\*} f(n) &= \Phi(f, g, n), \\ g(n) &= \Psi(f, g, n) \end{align\*} We may replace this with a *single* recursive map $h : \mathbb{N} \to \mathbb{N} \times \mathbb{N}$, where $h(n) = (f(n), g(n))$, so that $f(n) = \pi\_1(h(n))$, $g(n) = \pi\_2(h(n))$. Then the above recursive definition may be rewriten as $$ h(n) = (\Phi(\pi\_1 \circ h, \pi\_2 \circ h, n), \Psi(\pi\_1 \circ h, \pi\_2 \circ h, n)) $$ The above trick is very general and works in many situations. Regarding primitive recursion, we just have to verify that the passage between $f, g$ and $h$ preserves the primitive recursive nature of functions, which it does because pairing, projections and compositions are primitive recursive.
> 5 votes

---
Tags: computability, recursion, primitive-recursion
---


# Question
Title: Optimal set of shortest paths from one node to all others in a network graph
Let's say I have a country with a set of cities, which I represent on the network graph below as a set of nodes. Furthermore, the weighed edge between pairs of nodes, represent the distance by road between them. I'll define the capital city as node A. There is no direct route between A and C so there is no edge between them.

I want to keep all the roads in my country that represent the shortest path from the capital A to all other cities. I then want to remove all other roads. However, I want to find the solution which allows me to remove the largest distance of road possible.

If we look at my network below, the solution in this case is to remove the edge between C and D. By doing so, I can still visit B, C, or D from A at the shortest possible distance and I have removed road of length 3. If I instead removed the road between B and C, I would have only removed road of length 2, so this is not the solution I am looking for.

How might I go about solving this problem? I'm using networkx and Python and I can use the the function nx.all\_shortest\_paths() to return the shortest paths between two cities. However I can't figure out which path to choose when I have several options like this. Obviously there can be much more complex examples than that provided here. So to clarify, I want to remove the largest sum of road not needed. That is, the sum of the edge weights removed should be a maximum.

I've also post my question on stack overflow: https://stackoverflow.com/questions/69306867/optimal-set-of-shortest-paths-from-one-node-to-all-others-in-a-network-graph

# Answer
Your problem can be solved in the same time needed to compute a shortest-path tree of your graph. See Theorem 3 in the paper "Balancing Minimum Spanning Trees and Shortest-Path Trees" by Khuller et al. which also deals with directed graphs.

Essentially you want to find a minimum-weight branching (directed spanning tree) of the subgraph $H$ containing all edges that belong to some shortest path from the source vertex.

Once the distances $d(v)$ from the source to every vertex $v$ are known, $H$ can be found in linear time (simply check, for each edge $(u,v)$, whether $d(u)+w(u,v)=d(v)$, where $w(u,v)$ is the weight of edge $(u,v)$). Then, the paper gives an easy linear-time algorithm to find a minimum-weight branching from $H$. If there are no edges of weight 0 in your original graph (and hence in $H$) the algorithm boils down to selecting, for each vertex $v$, the minimum-weight edge among those entering $v$ in $H$.

If there are edges of weight 0, you can first contract all those edges and then apply the above strategy. The selected edges plus the contracted edges form a graph of minimum weight containing at least one shortest path from the source towards every other vertex.
> 1 votes

---
Tags: graphs
---


# Question
Title: Similarity measures for (geometric) triangulations
In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a **fixed** pointset $S$. I would like to cluster similar triangulations.

My first Idea was something like the edge flip distance, i.e. the minimal number of edge-flips in a quadrilateral needed to get from one triangulation to the other. Calculating this number is Np-Hard and since my datasets are not small, there are no algorithms that can calculate the flip distance in reasonable time.

Next I had a look at similarity measures for geometric graphs, but they emphasize the translation and insertion/deletion of points to get from one graph to the other one. These kinds of modifications are not interesting in my case, since the positions of the vertices are fixed for both triangulations.

In the figure two different triangulations on the same pointset are given. Note that we already have a one to one correspondence between the vertices of the two Triangulations, since they are generated with respect to the same set of points.

All in all I would like to know if there are any known similarity measures in the context of graphs/geometric graphs/triangulations, that may be interesting and could possibly be adapted to triangulations.

# Answer
> 1 votes
## Near Delaunay

There has been some recent research on this topic. Specifically, the paper *Near-Delaunay Metrics* by Beusekom et al. investigates the similarity of arbitrary triangulations to a Delaunay triangulation. Some of this has been inspired by the notion that a Delaunay triangulation of a point-set is one of the "nicest" triangulations there are, and so it might be worth our while whether we can measure the distance of a triangulation to a Delaunay triangulation.

## Application to general similarity

Of course, you're not so much interested in the similarity of a triangulation $T$ to the Delaunay triangulation $\mathcal{D}$, but rather between $T$ and $T'$. Fortunately, there are many ways in which you could use their results.

You could directly apply one of their metrics and cluster purely based on the "nearness to Delaunay". Another option is clustering on in which of their metrics the triangulation is closest to the Delaunay triangulation.

It's probably better to also try to use their ideas and create a method on your own. This will depend on your application, requires prototyping, experimenting, and testing. So, that part will be up to you. Good luck!

---
Tags: graphs, computational-geometry, planar-graphs
---


# Question
Title: How many functions require precisely $n^2$ gates?
I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $n$-bit inputs, $\\{0,1\\}$ output, and requires precisely $n^2$ NAND gates. I'm trying to show that this is $2^{o(n^3)}$.

I've thought about just counting all functions but that's too big, $2^{2^n}$. I've thought about all ways to wire up $n^2$ gates and the best bound that I can think of is to reason that each NAND has two wires in and one out. So each gate entails $\binom{n^2+n}{3}$ choices of wires in and out, by a rough over-count. Then you make a choice for each gate so that's $\binom{n^2+n}{3}^{n^2+n}$ by another rough over-count. But I believe this grows faster than $n!$ which is worse than $2^n$.

But any time I try to determine a more precise count of this set I just can't see the things I should count. When I think about writing a recurrence relation, that seems hopeless to write, let alone solve.

# Answer
Note that $$ \binom{n^2+n}{3}^{n^2+n} = O(n^2)^{O(n^2)} = 2^{O(n^2\log n)} = 2^{o(n^3)}. $$ In fact, using this kind of calculation you can show that most $n$-bit functions require circuits of length $\Omega(2^n/n)$.
> 1 votes

---
Tags: asymptotics, counting, digital-circuits
---


# Question
Title: What important/crucial real-world applications use blockchain?
As part of some blockchain-related research I am currently undertaking, the notion of using blockchains for a variety of real-world applications are thrown about loosely.

Therefore, I propose the following questions:

1. What important/crucial real-world applications use blockchain?
2. To add on to the first question, more specifically, what real-world applications actually need blockchain - who may or may not currently use it?

From a comment, I further note that this disregards the notion of cryptocurrencies. However, the use of smart contracts can have other potential applications aside from benefits they can pose to the area of cryptocurrencies

# Answer
Apart from Bitcoin and Ethereum (if we are generous) there are no major and important uses today.

It is important to notice that blockchains have some severe limitations. A couple of them being:

* It only really works for purely digital assets
* The digital asset under control needs to keep its value even if it's public
* All transactions need to be public
* A rather bad confirmation time
* Smart contracts are *scary*

**Purely digital assets**

If an asset is actually a physical asset with just a digital "twin" that is being traded, we will risk that local jurisdiction (i.e. your law enforcement) can have a different opinion of ownership than what is on the blockchain.

To take an example; suppose that we are trading (real and physical) bikes on the blockchain, and that on the blockchain, we put its serial number. Suppose further that I hack your computer and put the ownership of your bike to be me. Now, if you go to the police, you might be able to convince them that the real owner of the bike is you, and thus I have to give it back. However, there is no way of making me give you the digital twin back, thus there is a dissonance: the bike is owned by you, but the blockchain claims it's owned by me.

There are many such proposed use cases (trading physical goods on a blockchain) out in the open of trading bikes, diamonds, and even oil.

**The digital assets keep value even if public**

There are many examples where people want to put assets on the blockchain, but are somehow under the impression that that gives some kind of control. For instance, musician Imogen Heap is creating a product in which all musicians should put their music on the blockchain and automatically be paid when a radio plays your hit song. They are under the impression that this creates an automatic link between playing the song and paying for the song.

The only thing it really does is to create a very large database for music which is probably quite easy to download.

There is currently no way around having to put the full asset visible on the chain. Some people are talking about "encryptions", "storing only the hash", etc., but in the end, it all comes down to: *publish the asset, or don't participate.*

**Public transactions**

In business it is often important to keep your cards close to your chest. You don't want real time exposure of your daily operations.

Some people try to make solutions where we put all the dairy farmers' production on the blockchain together with all the dairy stores' inventory. In this way we can easily send trucks to the correct places! However, this makes both farmers and traders liable for inflated prices if they are overproducing/under-stocked.

Other people want to put energy production (solar panels, wind farms) on the blockchain. However, no serious energy producer will have real time production data out for the public. This has major impact on the stock value and that kind of information is the type you want to keep close to your chest.

This also holds for so-called *green certificates*, where you ensure you only use "green energy".

*Note*: There are theoretical solutions that build on zero-knowledge proofs that would allow transactions to be secret. However, these are nowhere near practical yet, and time will show if this item can be fixed.

**Confirmation time**

You can, like Ethereum, make the block time as small as you would like. In Bitcoin, the block time is 10 minutes, and in Ethereum it is less than a minute (I don't remember the specific figure).

However, the smaller block time, the higher the chance of long-lived forks. To ensure your transaction is confirmed you still have to wait quite long.

There are currently no good solutions here either.

**Smart contracts are scary**

Smart contract are difficult to write. They are computer programs that move assets from one account to another (or more complicated). However, we want traders and "normal" people to be able to write these contracts, and not rely on computer science programming experts. You can't undo a transaction. This is a tough nut to crack!

If you are doing high value trading, and end up writing a zero too much in the transaction (say \\$10M instead of \\$1M), you call your bank immediately! That fixes it. If not, let's hope you have insurance. In a blockchain setting, you have neither a bank, nor insurance. Those \\$9M are gone and it was due to a typo in a smart contract or in a transaction.

Smart contracts is really playing with fire. It's too easy to empty all your assets in a single click. And it has happened, several times. People have lost hundreds of millions of dollars due to smart contract errors.

*Source: I am working for an energy company doing wind and solar energy production as well as trading oil and gas. Have been working on blockchain solution projects.*
> 99 votes

# Answer
There are varying definitions of blockchain, and the answer to this question depends a lot on whether you consider the broad or the narrow interpretation. Typical cryptocurrency implementations such as Bitcoin have two parts:

1. A chain of blocks, linked by cryptographic hashes (SHA256 in Bitcoin) so that the identity of the newest block prevents modifying any earlier record. Most common structure is the Merkle tree, which was first patented in 1979.
2. A peer-to-peer network of computers that decides what is the newest block (also called "consensus protocol"). In Bitcoin this is done by proof-of-work mechanism (so called mining), which distributes the trust and authority in the network.

A wide interpretation of blockchain would be anything that has the first part, a chain of blocks. These have many widely used applications that predate the cryptocurrencies. Some examples:

* Git version control system, where Merkle tree is used to protect the version history of software against modification.
* Certificate Transparency logs, which allow public monitoring of issued HTTPS certificates.
* Many distributed database systems such as Apache Cassandra, where it is used to check for data consistency between nodes.

However, even though the Merkle tree is a "chain of blocks", many consider that it alone doesn't make a system blockchain based. After all, blockchain is considered a new invention, and Merkle tree definitely isn't new. There is merit to both sides of the argument.

As Pål GD's answer details, apart from cryptocurrencies, there haven't been any widely spread real applications of the full Merkle tree + peer-to-peer network combination.
> 26 votes

# Answer
The given answers focus on the open p2p blockchains of Bitcoin and its likes.

There is however also such initiatives as Hyperledger, R3 Corda, and Enterprise Ethereum Alliance, etc. (Even cloud providers (eg aws) have offerings). These kinds of platforms tend to avoid the time-consuming proof-of-work part and do consensus between selected parties, not being open for anyone with an internet connection necessarily. They also do not always display information in the blocks to the entire world; and instead tend to have protections regarding who can read what on the chain.

These platforms tend to promote their usefulness in cases where parties not wanting to trust each-other, or a third party, with some information, still need a shared source of said data, with agreed-upon rules of how the data will be changed that can be verified.

Goals in using such distributed ledgers include different things, such as added security, transparency and auditability, anonymity, scalability, increased industry collaboration, and allowing for new business models. Which, and how, would depend on which industry and application, but maybe some ideas can be found in this survey or similar places. These kinds of platform are likely what existing companies would look at using if they got into the blockchain space.

Looking at pieces that the platforms advertise actually being used in, we find such initiatives as:

Commodity tracking \- for example major food producers and retailers joining a network aimed at "...connecting growers, processors, distributors, and retailers through a permissioned, permanent and shared record of food system data.".

Data sharing \- for example insurers sharing data for compliance reasons to a network where regulators with permission can look at it. There can also be improved handling of documents on a network instead of current siloes.

Personal information control \- for example hu-manity.co controlling how personal data is shared with companies.

Since blockchain is new and untested, there would at the moment be more experiments and proof-of-concept applications rather than real-world ones. Many of them will turn out to be poor matches for a hyped technology looking for a problem to solve. However, permissioned or consortium distributed ledgers is one place too look where smaller projects have started to be launched for real applications.
> 11 votes

# Answer
An application that is not big *yet*, but that may become big soon is authentication of digital documents. I don't know anybody who does this yet, but it is being discussed.

The problem is this: An administrative authority of some sort has thousands, if not millions of digital documents in their care. How do we make sure that the documents that are in the database *today* are identical to the ones that were there yesterday?

This can have large legal consequences.

One could make several full backups on DVDs or something and store them is several different safe places, but this is costly and still not really safe.

Another problem is that these documents can be confidential and you really don't want to spread copies of them around.

Instead one can make lists of hash signatures and spread *those* around. They are much smaller and also not confidential. (If done right)

Now, I not sure we really need the *chain* aspect of block chains, two or three levels of Merkle trees are probably sufficient. However, as long as we are hashing things anyway, it costs very little to add the signature list as a document for the next batch. Maybe not necessary, but doesn't hurt.

One weakness in this system is that documents can be *deleted*. With only the hash value to go by we can't reconstruct them, but it would add a very visible hole in the data that should at least look ugly to those concerned.
> 0 votes

# Answer
As another commenter noted, the answer depends in part on which blockchain model you're talking about.

Proof of Work blockchains (Bitcoin-alikes) are utterly worthless. Given their energy requirements they are less than worthless and actively harmful.

Delegated Proof of Stake (DPOS, such as Hive, previously Steemit) works differently, with some elected number of nodes sharing signing duty in a round robin, rather than every note competing to waste more electricity faster. That makes the signing time very small (a few seconds), and allows for a semi-democratic governance model rather than totally antagonistic anarchy. The largest DPOS network is Hive, which is mostly a community blogging platform but is also used as the underlying database for a few online games et al.

On the flipside, DPOS's version of democracy is essentially "one dollar, one vote", so it inherently favors the "wealthy."

I think the best use of DPOS is as a micropayments system, where it's not a store of wealth but a way to micro-pay for entertainment services (games, blogging, etc.) that can then be converted back to fiat money later. The cryptocurrency part is semi-incidental and only really relevant to the highest-value holders, who tend to become (or control) the signing nodes.

At its core, blockchains are better than a central DB if and only if your primary feature requirement is censorship avoidance. A properly designed blockchain is really really hard (but not impossible) to censor, or delete data from, or rollback. That is its only real advantage, IF that is an advantage you want. It isn't always.

That is the advantage the original Bitcoin fanatics wanted, because they saw the "quantitative easing" of central banks circa 2008-2010 as a form of censorship (because it by design devalued the money held by the wealthy). However, it also has no Undo command, which as other commenters noted is rather important for financial transactions.

It's also difficult if not impossible to separate blockchains from some form of score-keeping (cryptocurrency), because that is the only incentive for people to play nice and actively maintain the network. Absent that, there's no reason for anyone to go to the expense of running a signing node.
> 0 votes

---
Tags: blockchain
---


# Question
Title: Why is this greedy strategy always correct for this problem?
I'm trying to solve the following problem: https://cses.fi/problemset/task/1084/

My first idea to solve this was to sort the applicants and apartments in increasing order. Then, I iterate through all the applicants and for each one, pair it up with the smallest apartment that would satisfy them (if it exists). This greedy strategy managed to correctly answer every test case, but I'm not sure why (because it seems to me that sometimes, it may be better to let another applicant take the apartment we are considering in order to open up more apartments for the rest of the applicants).

Can somebody help prove why this greedy strategy is correct for this problem?

# Answer
> 1 votes
Let the applicants demands in the increasing order is: $d\_1, \dotsc,d\_{n}$.

Let the apartments sizes in the increasing order is: $s\_1, \dotsc,s\_{m}$.

Try to prove the following claim:

**Claim:** Let $d\_i \leq d\_j$ and $s\_x \leq s\_y$. If $d\_i$ can be assigned to $s\_y$, and $d\_j$ can be assigned to $s\_x$. Then, it is possible to assign $d\_i$ to $s\_x$, and $d\_j$ to $s\_y$.

For proof, try to take cases like $d\_i \leq s\_x$ or $d\_i\>s\_x$. Using it you can show that $d\_i$ can be assigned to $s\_x$. Using similar cases, you can further show that $d\_j$ can be assigned to $s\_y$.

I leave the rest of the details to you.

---
Tags: algorithms, sorting, greedy-algorithms
---


# Question
Title: What are the advantages of x86 CPUs over ARM?
Now that Apple is switching the MacOS platform to ARM chips, much has been said about the benefits of ARM processors (they save energy, are passively cooled, and the Apple M1 seems to be faster than even an Intel Core i9 processor).

I'd like to know what advantages of the x86 platform are left. Are there any specific circumstances where the x86 CPUs still have the edge? AFAIK they have an much bigger instruction set than the ARM chips. Under what circumstances is the bigger instruction set an advantage, and why?

Note that I'm not asking about a specific software ecosystem like Windows. I know that Windows has many software titles (e.g. games) that don't run (yet) on any ARM platform. That's not the answer I want to hear. An ecosystem advantage like that of Windows is more or less baggage from previous years. It does not necessarily mean that the CPU platform is in any way better, today.

# Answer
I'll start with the commonly known stuff, that are currently talked about the most.

**x86**

All x86 processors are developed from the CISC (Complex Instruction Set Computers) architecture. The x86 processors allow you to perform several activities at the same time from a single instruction. Also, they can perform numerous simultaneous tasks without any of them being affected.

This makes them very sophisticated and advanced processors, allowing many complex calculations in a short time. The disadvantage of this design is that they need a lot of power to function and more power means more heat.

Summary: x86 chips are designed to be power hungry and high clocked, multi-thread, high instructions per cycle. In the general use-case they will be a lot faster than your common ARM chip.

**ARM**

As for ARM processors, they are based on the RISC (Reduced Instruction Set Computer) architecture, which is much simpler than CISC. These processors can do a much smaller number of calculations since they require several commands to act.

RISC instructions are smaller and faster to process, so in part, the disadvantage of having to process several commands for a single action is minimized. Still, ARM processors are much less powerful than the x86.

Summary: ARM chips are designed for low power draw, flexibility, low cost and low heat with good performance.

source of the info above

**SoC M1**

M1 is not a CPU. It is a whole system of multiple chips put into one large silicon package. The CPU is just one of these chips. And that's the main reason why it's so different and fast compared to the typical ARM chip.

Basically, the M1 is one whole computer onto a chip. The M1 contains a CPU, graphical processing unit (GPU), memory, input and output controllers, and many more things making up a whole computer. This is what is call a system on a chip (SoC).

In the past computers would have multiple physically separate chips on the motherboard of the computer. However because we are able to put so many transistors on a silicon die today, companies such as Intel and AMD began putting multiple microprocessors onto one chip (CPU cores). One core is basically a full independent chip that can read instructions from memory and perform calculations. This has for a long time been the name of the game in terms of increasing performance - just add more general-purpose CPU cores.

Instead of adding ever more general-purpose CPU cores, Apple has followed another strategy - they have started adding ever more specialized chips doing a few specialized tasks. The benefit of this is that specialized chips tend to be able to perform their tasks significantly faster using much less electric current than a general-purpose CPU core.

Hope that answers your question.

You can find more details on the M1 where I got the info for the second part of the answer. There is a lot of additional and interesting info on the CPU market and the software differences inside the M1 and Intel/AMD chips: link
> 8 votes

# Answer
There are far less advantages in both directions than you might think.

The reason is, that currently there are actually no modern x86 CPUs on the market. Both Intel and AMD don't actually use x86 cores, but instead proprietary RISC cores, with microcode that translates the x86 code to RISC code on the fly at execution time.

ARM chips on the other hand don't use microcode, bun instead directly run their code on an ARM RISC core.

So the cores that do the actual execution are pretty similar. The usage of microcode, though, is the biggest difference. For ARM this is a small advantage for calculation power per watt. But for x86 CPUs that means that the microcode can be updated after production (so with a regular OS update) to fix bugs or improve performance.

The actual performance or power consumption differenced come down to the manufacturers, their priorities and their research. Intel actually made quite decent x86 phone CPUs, but marges were too low for them and the competition had too much of a headstart.

Also, high performance ARM CPUs for desktop and servers are totally possible, but x86 has almost 100% market share there and had that for almost 20 years. That's a very tough market to break into. But it's totally possible, as seen with Apple.

So it has much more to do with money, markets and customers, than with actual advantages of the architectures.

**What is the difference between ISAs and implementations?**

When talking about ISAs, people often confuse the advantages of specific ISAs with the advantages of specific implementations.

So for example, you will often hear things like "x86 has more performance" or "ARM is more power efficient". These things don't actually have anything to do with the ISA, but are implementation specific.

The ISA is nothing more than the language the CPU speaks. It does not say anything at all about the implementation.

So saying "ARM is more power efficient", because you have seen a few power-efficient ARM CPUs is like saying "People who speak German are blond".

The real difference is that there are two strong mobile ecosystems that mainly use ARM (Android and iOS). You can run Androidx86, but many apps won't work on x86 (Source: me, I had an x86 tablet). So because ARM is used a lot in mobile devices, there will be more funding for mobile ARM CPUs.

And there are very strong x86 ecosystems for desktop and server, so there is more research into high performance x86 chips.

**Counterexamples**

The Intel Atom x6200FE has a TDP of 4.5W. That's less than half of the Snapdragon 888, which has a TDP of 10W.

The Ampere Altra Max is a 128 Core Server ARM CPU, with a TDP of 250W. This thing strips the socks off most x86 CPUs on the market, in terms of performance.
> 6 votes

---
Tags: cpu
---


# Question
Title: Complexity of a variant of Subset Sum problem
This is the variant of SSP: Given $n$ positive integer points $a\_1, \ldots, a\_n$ which are all at most $n$, does there exist a subset $\\{a\_i\\}\_{i \in P}$, such that its summation is exactly $n+1$?

My question is, for general $n$, is this problem NP-hard?

# Answer
The problem is polynomial-time solvable using a reduction to 0-1 knapsack problem. Take a knapsack of size $W = n+1$. Take $n$ items of size $a\_i$ and value $a\_i$. The maximum value obtained is $n+1$ if and only if there exists a subset of items that sum to $n+1$.

The 0-1 knapsack problem can be solved in time $O(n \cdot W)$ using dynamic programming. Therefore, the running time of the algorithm here is $O(n^2)$.
> 3 votes

# Answer
No (unless $\mathsf{P}=\mathsf{NP}$), the problem is in $\mathsf{P}$. The following is polynomial-time dynamic programming algorithm.

For $i=0,\dots,n$ and $j=0, \dots, n+1$ let $S\[i,j\]$ be true iff there exists a subset of $\\{a\_1, \dots, a\_i\\}$ whose elements sum up to $j$. We trivially have that $S\[i,0\]$ is true for all $i$, while $S\[0,j\]$ if false for all $j\>0$. Moreover, for $i,j\>0$ we have: $$ S\[i,j\]= \begin{cases} S\[i-1,j\] & \mbox{if } a\_i \> j \\ S\[i-1,j\] \vee S\[i-1, j-a\_i\] & \mbox{otherwise} \end{cases}. $$

The instance admits a solution if and only if $S\[n, n+1\]$ is true.
> 2 votes

---
Tags: complexity-theory, subset-sum
---


# Question
Title: hash-tables - Expected-time for an unsuccessful search
> The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c.

Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by the following formula: $$ \alpha = 1 − \frac{1}{\log n} $$ If you resolve collisions by chaining, what is the expected time for an unsuccessful search in terms of n? (assume simple uniform hashing)

**My reasoning**: the expected-time for an unsuccessful search would be $\Theta(1 + E\[X\])$, where $E\[X\]$ is the expected number of elements in any slot after the insertion of n-elements.

Now, by definition, we have $\alpha = \frac{n}{m}$, which combined with the above formula we get $\frac{1}{m} = \frac{1}{n}\Bigl(1 - \frac{1}{\log n}\Bigr)$. And based on simple-uniform hashing, this is the probability with which the $(n+1)^{th}$ element will hash to any particular slot.

Let $X\_{i}$ be an indicator random-variable, where $i = 1, 2, ..., n$, which indicates that the $i^{th}$ element added to the hash-table (which at this piont contains $(i-1)$ elements) hashes to a particular slot, i.e. $$ X\_{i} = \begin{cases} 1, & \frac{1}{m} = \frac{1}{(i-1)}\Bigl(1 - \frac{1}{\log (i - 1)}\Bigr) \\ 0, & 1 - \frac{1}{m} \end{cases} $$ Then, the total number of elements $X$ in any particular slot , is given by $$ X = \sum\_{i=1}^{n}X\_{i} $$ And the expected number of elements in any particular slot becomes: $$ \begin{align} E\[X\] & = \sum\_{i=1}^{n} E\[X\_{i}\] \\ & = \sum\_{i=1}^{n} \biggl\\{\frac{1}{(i-1)}\Bigl(1 - \frac{1}{\log (i - 1)}\Bigr)\biggr\\} \end{align} $$

But the $|E\[X\_i\]| = \infty$, when $i = 1, 2$. *This is where I got stuck!*

So, **is my reasoning correct?** And if not, **how to solve this problem?**

# Answer
Didn’t read your solution.

You have n slots, alpha x n are occupied, (1-alpha) n are empty. Every hash code defines a sequence of indices that will be checked until either the item or an empty slot is found. Let E(Alpha) be the expected number of slots visited, then E(alpha) = 1 x (1-alpha) + alpha (1 + E(alpha)) or E(alpha) = 1 / (1-alpha). With your alpha = 1 - 1/log n, E = log n.

PS. I have never seen an implementation that doesn’t store all items in the table. In general it’s better to generate locations based on the hash code, and not each location based on the previous location, so items with different hash codes can hit the same first slot but then follow different paths.

There is a complication when items can be deleted. Deleted slots cannot be changed to “empty” but must be changed to “deleted” to stop chains from being broken. So load factor would take used and deleted slots into account.
> 0 votes

---
Tags: algorithm-analysis, hash, hash-tables
---


# Question
Title: How is it possible that for infinite L in R exists subset L' which is not in Re?
Proove that for every infinite $L \in R$ there is a $L' \subseteq L$ s.t $L' \notin RE$.

How can I proove it? if sketched on venn diagram it doesn't make sense...

From my point of view everything that is in R suppose to be in Re. $x \in A $ and $A \subseteq B$ then $x \in B$. Why does it fail? and how am I suppose to proove it?

# Answer
> 2 votes
Subsets of recursive languages aren't always recursive or recursively enumerable. The simplest example is the language of all strings: it is clearly recursive (even regular), and all languages are its subsets including those not in $RE$.

To solve this question, consider this: how many subsets does an infinite language $L$ have? What does that imply regarding their membership in $RE$?

---
Tags: turing-machines, computability, decision-problem, computation-models, semi-decidability
---


# Question
Title: What is the difference between FLOPS and OPS?
I have typically heard computer performance discussed in terms of FLOPS.

However, I have recently seen multiple references instead using OPS i.e. operations per second, typically in the context of Big Data.

**What is the difference between FLOPS and OPS?** Why use one over the other?

I appreciate that they are both metrics for measuring performance - are there cases where the non-floating point operations have large overheads or are non negligible compared to the float operations? What is an example of a non-floating point operation?

Thanks

# Answer
> What is the difference between FLOPS and OPS?

* *FLOPS* is *floating-point operations per second*
* *OPS* is *operations per second*

The difference should be obvious from the name: one is the number of operations per second, the other is the number of floating-point operations per second.

> Why use one over the other?

If you want to know the floating-point performance, you would measure FLOPS, if you want to know the performance over all kinds of operations, you would measure OPS.

Floating-point operations are just not terribly interesting for most use cases. In fact, in the past, floating-point operations used to be implemented on a separate chip sitting in a separate socket on the motherboard. This was done for two reasons: floating-point operations are pretty complex, slow, and power-hungry, so it was simply not physically possible to have the complex Floating-Point Unit (FPU) on the same die as the CPU. And second, only few people need high floating-point performance, so this made it possible for people to only buy an FPU if they actually needed it, and everybody else avoided wasting money, complexity, and power on an FPU they rarely used.

FLOPS are just not a terribly interesting metric for most use cases. Both parts of the metric, actually: the *FLO* part (floating-point) and the *PS* part (time).

If you are building a supercomputer for military applications, then yes, FLOPS is interesting to you. However, if you are *not* building a supercomputer, then it is highly likely that you don't actually care about floating-point operations *at all*. And even if you are building a supercomputer for a company, then you *do* care about floating-point operations, but you actually care more about floating-point operations *per dollar* (cost), *per watt* (not just energy cost, but also thermal management, cooling, waste heat, etc.), and *per cubic meter* (rack space, real estate, property taxes, etc.)

Really, only the military cares about brute-force performance with no regard to cost, energy, or size.

For my mobile phone, I care about the performance-per-cost, performance-per-Watt (both battery life and heat), and of course size. For my desktop, size is a little less important, but cost and energy still are. (And who has desktops anymore?) Even extreme gamers care about waste heat and thermal management!

Crypto miners are *all about* performance per Watt, since energy *dominates* the cost for mining. That's why regions with lots of wind, solar, hydro, and geothermal energy are popular with miners. (Or, regions with less than strict environmental laws – apparently, miners have bought or leased and reactivated coal and gas plants that were in the process of being shut down in favor of alternative energy sources.)

> What is an example of a non-floating point operation?

* Integer operations
* Fixed-point operations
* Rational operations
* Complex operations
* Decimal operations
* Money operations (nobody in their right mind would use floating-point for money)
* \[literally *every single kind of number that is not a floating-point number*\] operations
* text operations
* boolean operations
* binary operations
* cryptographic operations

Basically, most of the operations we use in our everyday usage of computers.
> 5 votes

---
Tags: performance, big-data, high-performance-computing
---


# Question
Title: Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
For the following recurrence relation:

$$T (n) = T (n/2) + n(2 - \cos n)$$

I see it based on values of $\cos$ function given that it output values in range, but this does not seem to have anything to do with solving the problem. I found a solution which says that comparing this to master method yields that this does not apply to master method, so please based on master method why the previous recurrence relation does not apply based on 3 cases we have?

**Solution Found**: Does not apply. We are in **Case 3**, but the regularity condition is violated. (Consider $n = 2πk$, where k is odd and arbitrarily large. For any such choice of n, you can show that $c \ge 3/2$, thereby violating the regularity condition.)

# Answer
Since $|\cos n| \leq 1$, we have $1 \leq 2-\cos n \leq 3$, and so $$ T(n) = T(n/2) + \Theta(n). $$ This is something that the master theorem can handle.
> 5 votes

# Answer
$n(2-\cos n)$ always lies between $n$ and $3n$.

On expansion, we get:

$T(n) \leq 3 (n+n/2+n/4+\dotsc+1) \leq 6n$

and

$T(n) \geq (n+n/2+n/4+\dotsc+1) \geq n$

Hence, $T(n) = \Theta(n)$.
> 4 votes

# Answer
Define $T^-(n) = T^-(n/2) + n$ and $T^+(n) = T^+(n/2) + 3n$. You can see that $T^-(n) \le T(n) \le T^+(n)$.

Since the master theorem applies to both $T^-(n)$ and $T^+(n)$ which have solution $\Theta(n)$, you can also conclude that $T(n)=\Theta(n)$.
> 3 votes

---
Tags: recurrence-relation, discrete-mathematics
---


# Question
Title: Do number of registers and width of register have to be the same?
I am studying Computer Architecture with MIPS-32. The example system has 32 registers with each register having a width of 32 bit.

If I would want 128 registers instead of 32 registers, would I have to increase the width of each register to 128 bit as well?

Or do I just need 64 bits, which is enough to address the new registers?

# Answer
> 5 votes
The number of registers and their width is not really related, they just happen to be the same in MIPS-32. You can look at other ISAs for different combinations of register width/number:

* IA64: 128 64-bit registers
* SPARC: 32 32-bit or 64-bit registers
* 6502: 3(?) 8-bit registers
* x64: 16 64-bit registers

> If I would want 128 registers instead of 32 registers, would I have to increase the width of each register to 128 bit as well?

You would need to widen instructions (or change the instruction format without widening the whole instruction) to widen the operand fields, or add some other feature that enables using 128 registers (hypothetically you could have an ISA that "has" 128 registers but can only ever access 32 of them, but doesn't that just mean that it really has 32 registers?). The obvious way is having 7 bits per operand, but there are different ways to do it, such as using "register windows".

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


# Question
Title: What is the the greatest thing a computer has trouble doing?
If we have all these optimized programs for very specific tasks, what would be the antithesis of them?

I've asked a programmer friend of mine, and they thought a good answer had to do with multi-dimensional arrays and nested for-loops in graphics programming. I just want to see what other answers there are.

Essentially, as the title says, what is the hardest/slowest thing for a computer to do?

# Answer
I would say the halting problem, is the hardest - single most important problem in computer science.

The halting problem is an undecidable problem \- meaning that no computer program can always successfully solve it **and** never get stuck in an infinite loop.

An important implication of the halting problem, is Rice's theorem, which can prove that some practically useful programs do not exist. For example, one cannot write a perfect anti-virus program that always managed to decide whether another given executable is malicious or not.

There are a lot of other interesting and potentially useful problems that we can't solve because of this, so I would say this is one of the most important results in the computer science computability field of study.
> 0 votes

# Answer
A computer doesn't have trouble doing anything; it does precisely what it's programmed to do. It is efficient in doing a task if and only if we come up with an efficient algorithm for it.

In that regards, we have a whole hierarchy of less and more efficient such tasks. On the bottom of the hierarchy is the problems where the machine just finishes after a couple of steps. Then there are an infinite hierarchy of problems solvable in logarithmic and polynomial time, followed by an infinite hierarchy of problems only solvable in exponential time followed by an infinite hierarchy of problems only solvable in super-exponential time (and so it goes) until you reach the limit of algorithms.

Then you get to the tasks for which there provably cannot exist any algorithm whatsoever for solving them, which is an infinite hierarchy of more and more *undecidable* problems. And we *still* have only seen a tiny tiny tiny part of all problems that exists. The majority of the problems lie above all these hierarchies.

---

Summing up, computers run algorithms. Some tasks have efficient algorithms, and some don't (and for some, we don't know).
> 0 votes

---
Tags: time-complexity, computability
---


# Question
Title: Is it possible to write a program that is able to recognize some source-code as being its own source code?
Is it possible to write a program that is able to recognize some source code as being its own source-code?

Biological organisms evolved the ability of kin-recognition, and later, self-recognition, early on. This led to the evolution of the immune system.

Of course the immune system does not go through the DNA of a potentially foreign cell one base pair at a time. Rather it recognizes certain "cues" that are highly unlikely to be the same unless the target is of self. (This acts similar to using a hash value to determine identity.)

However it has made me wonder if it is theoretically possible for a machine running a computer program to be able to determine with full accuracy and no ambiguity whether or not a given body of source code, if compiled, would result in the same program as the one that is currently running.

It seems to me this must be impossible, because for a given program to be able to recognize itself, it seems like it would have to contain a full representation itself. This seems impossible because there would have to be some additional code, besides the self-representation, to handle the recognition aspect.

However, perhaps there might be an algorithm capable of creating a guaranteed-unique cryptographic signature of some code, up to a particular size, which could then be saved into the program whose signature it is. That way if it's looking at some source code, as long as it has access to a way to compile the code, it can verify whether its own signature matches the signature of that code, and if so, it would know that code represents itself.

Indeed, we already use code-signing extensively to allow an OS to verify that a program hasn't been tampered with after it was compiled and saved to disk. However I don't know if such signatures are fully unique or whether they have collisions. I don't know if it's even possible to have a signature without any collisions up to a given size.

I don't have a use case behind this question, but I'm more just curious if anyone has thoughts on this or if you could point me in the direction of some recent scholarship on this matter.

# Answer
Read Hofstadter’s “Gödel, Escher, Bach: An Eternal Golden Braid”.

It is quite easy to write say a C program printing its own source code. Now reading any code can be a bit difficult, say if you are talking about operating a camera and OCR, but once you’ve done that, writing a program that reads code and detects that it is its own source code is not difficult.

PS. Oh well. Some people seem to have a very very deep connection between "own source code" and "halting problem". The question has nothing whatsoever to with the halting problem.

Assume you want to write a C program that can recognise its own source code. First you write a function that *reads* the source code. For example reading it from a file, scanning the text of a book etc. Let's say this function has a prototype char\* readsource().

Then you write your C program. It starts with some code. Then it contains a line

```
char* source = "......@.....";

```

and then it ends with more code. Let "prefix" be everything up to the first quote in the char\* source line, let "suffix" be everything from the second quote to the end of the program. Then we replace the first set dots with "prefix", and the second set of dots with "suffix".

The whole program now consists of prefix, prefix, a "@" character, suffix, suffix.

What the program does is call readsource() to read its source code, and then it checks whether the source code that it read consists of prefix, prefix, "@" character, suffix, suffix. Very simple.
> 1 votes

---
Tags: cryptography, hashing, general
---


# Question
Title: How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?
Can somebody help me with this recurrence please?

$T(n)=4T(\sqrt{n}/3)+(\log n)^2$

# Answer
The division by 3 makes the task a little non-trivial, but you can still figure out how to proceed in the manner proposed by the answer suggested by Nathaniel in the comments.

Let $n = 3^{2^k-2}$ and you can modify the recurrence equation as $$T(n) = 4T\left(\frac{\sqrt{n}}{3}\right) + (\log\_3{2})^2.(\log\_3n)^2$$

However, this modification will only bring a change of constant in your final solution. So we can safely assume that the original equation had the base of the logarithm as 3.

You have that $k = \log\_2(\log\_3n+2)$, and you can substitute this at the end to find your answer.
> 3 votes

# Answer
**Master Theorem** is for **Dividing** and **Subtracting** Function.
The Master Theorem at it's core **don't discuss Square Root Function.**

Although, some Manipulations can be done.

But for the sake of simplicity, solving by **Substitution Method**

**Given**,

$T(n)=4T\bigg(\frac{\sqrt n}{3}\bigg) + (\log(n))^2$

$T(n)=4T\bigg(\frac{n^{1/2}}{3}\bigg) + (\log(n))^2$

$T(n)=4\bigg(4T\bigg(\frac{n^{1/4}}{3}\bigg) + (\log(n^{1/2}))^2\bigg)+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + 4(\log(n^{1/2}))^2+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + (2\log(n^{1/2}))^2+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + (\log(n))^2+(\log(n))^2$

$T(n)=4^2T\bigg(\frac{n^{1/2^2}}{3}\bigg) + 2(\log(n))^2$

$T(n)=4^2\bigg(4T\bigg(\frac{n^{1/2^3}}{3}\bigg) + (\log(n^{1/2^2}))^2\bigg)+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + 4^2(\log(n^{1/2^2}))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + {2^2}^2(\log(n^{1/2^2}))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + ({2^2}\log(n^{1/2^2}))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + (\log(n))^2+2(\log(n))^2$

$T(n)=4^3T\bigg(\frac{n^{1/2^3}}{3}\bigg) + 3(\log(n))^2$

Therefore, for **k iterations**

## $$T(n)=4^kT\bigg(\frac{n^{1/2^k}}{3}\bigg) + k(\log(n))^2$$

Now, **Assuming** $T(1)=1$

Therefore, put $$\frac{n^{1/2^k}}{3}=1$$

$$n^{1/2^k} = 3$$

$$\frac{1}{2^k}log\_3n = 1$$

$${2^k} = log\_3n$$ $$k = log\_2(log\_3n)$$

Thus,

## $$T(n)=4^{log\_2(log\_3n)}T(1) + {log\_2(log\_3n)}(\log(n))^2$$

Solving Further,

$T(n)=2^{2log\_2(log\_3n)} + {log\_2(log\_3n)}.(\log(n))^2$

$T(n)=2^{log\_2(log\_3n)^2} + {log\_2(log\_3n)}.(\log(n))^2$

$T(n)=(log\_3n)^2 + {log\_2(log\_3n)}.(\log(n))^2$

Since, we don't know **base of logarithm** given in **Recurrence Relation**, and also since base don't matter on applying **Base Change Formula**

$T(n)=(\log(n))^2 + {log(logn)}.(\log(n))^2$

## **Therefore, $T(n)$ is $O\bigg((log(logn)). (log n)^2\bigg)$**
> 1 votes

# Answer
Define S(n) = T(2^n), write down a recursion formula for S, solve it using the master theorem, and then let T(m) = S(log m).

Or calculate T(n) for n = 3^0, 3^2, 3^6, 3^14, 3^30, 3^62 etc. without the master theorem, guess a formula for T(3^(2^k-2), and prove it.

Let D log 3.

If T(1) = c, then T(9) = 4T(1) + (log 9)^2 = 4c + 4D^2.

T(3^6) = 4T(9) + 36D^2 = 16c + 52D^2.

T(3^14) = 4T(3^6) + 196D^2 = 64c + 404D^2.

T(3^30) = 4T(3^14) + 900D^2 = 256c + 2516D^4

Etc.
> 0 votes

---
Tags: algorithms, time-complexity, algorithm-analysis, recurrence-relation, master-theorem
---


# Question
Title: A question about the paper "Ensembling Ten Math Information Retrieval Systems"
My question is about the paper Ensembling Ten Math Information Retrieval Systems.

I am interested in the task of finding answers.

Which of the ten system are able to answer questions using **only** dot products?

(I think CompuBERT is one of them, look)

# Answer
All ten systems are able to retrieve answers using only the dot product:
> 1 votes

---
Tags: information-retrieval
---


# Question
Title: Why modulo-2 arithmetic over n-bits doesn't produce single bit result?
I was studying CRC and came across modulo 2 arithmetic. When we add two 1 bit numbers like 1 + 1, 0 + 1, then the result is summation modulo 2 which is similar to XORing of the two bits. My doubt is when this is extended to multiple bits why is the solution not summation modulo 2 i.e. one bit result either 0 or 1, instead it is defined as XOR of the two n-bit numbers to be added. Modulo 2 addition should be sum modulo 2 right?

# Answer
> 0 votes
There is a difference between applying the modulus to the entire integer, or applying it to the individual bits. The first would have the effect you describe here: $1010\_b + 0101\_b \equiv 1\_b(\mod 2)$. However, that is not always very useful. Bitwise application of the modulus can give you arithmetic in finite fields. In particular, bitwise addition of $2^k$-ary binary integers can be extended into the finite field $\mathbb{F}\_{2^k}$.

Much of the theory of cryptography and coding theory rely on finite fields, both because arithmetic tends to be more computationally challenging (for crypto, this means we can design encryption methods that are hard to decrypt, for coding theory, this means that there is something complicated to study ;) ), especially compared with infinite fields such as the real numbers, $\mathbb{R}$. If all this went over your head, just remember that there is a difference between bitwise and ordinary modulus, and that the bitwise modulus has a well-known and solid theoretical component as well.

---
Tags: modular-arithmetic
---


# Question
Title: Squaring the weights of an undirected graph and minimum spanning trees
This is from question 3(a) from http://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/exams/exam2-practice-sol.pdf, which is: consider an undirected graph $G$ with unique positive weights. Suppose it has a minimum spanning tree $T$ . If we square all the edge weights and compute the MST again, do we still get the same tree structure? The answer says that it is true so I'm trying to prove it, but I'm quite stuck. I have only written the following. By contradicion, let $T'\neq T$ be MST of the graph $G$ with the squared weights. Then \begin{align\*} \sum\_{i\in T'}w\_i^2 \< \sum\_{i\in T}w\_i^2 \end{align\*} how can arrive at a contradiction (for example, $\sum\_{i\in T'}w\_i \< \sum\_{i\in T}w\_i$)?

# Answer
> 1 votes
Hint: how does Kruskal's algorithm work? What can you say about the execution of Kruskal on the new graph?

---
Tags: graphs, discrete-mathematics, minimum-spanning-tree
---


title: A single heap nim game

text:
# Question
Title: A single heap nim game
Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P = {p1,p2,…,pk} determines the allowed moves. For example, if P = {1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1 , 2 ,…, n if the first player has a winning or losing position.

How to solve this question. Thank You for help.

# Answer
> 2 votes
I'll give you two hints. Firstly, A losing position means there exists a move for your opponent to win in a single move, or to bring you to a losing position in a single move. Observe that if you are currently in a winning position, you can put yourself in a winning position within one move.

Secondly, you should label winning positions starting from the very first stick until the last, e.g. since stick $i$ is a winning / losing position for the starting player, stick $i + p$ must be a winning / losing position for starting/second player.

P.S. The game might deadlock for $p\_1 \> n$, where $n$ is the number of remaining sticks and $p\_1 \< p\_2 \< ...$.

# Answer
> 1 votes
It would be easier to determine which positions are winning positions and loosing positions if you start from the 1.

Using your set {1, 3, 4} as an example, the first player can easily win the game if the number of sticks are either 1, 3 or 4 as he just has to take all.

Counting upwards from 1, we see that 2 is the least number which has not been classified as either a winning position or loosing position so 2 becomes a loosing position for the first player.

Indeed if the heap was of size 2, the first player would be forced to take just 1 and the second player wins by taking the other one.

Since 2 is a loosing position for the first player, 2 + 1, 2+3 and 2+4 are all winning positions for the first player i.e(3, 5, 6). Then the next number which hasn't been classified as we go upwards is 7. So it is a loosing position for the first player. His next winning positions would be 7+1, 7+3 and 7+4.

Continuing with this algorithm, you can determine all the winning positions and the loosing positions for the first player.

---
Tags: algorithms, game-theory
---


# Question
Title: How can we get upper bound in terms of Big Oh notation using Master theorem?
The recursion is:

```
T(n) = 5T(n/2) + O(n)

```

I solved for the time complexity using Master theorem and found Θ(n^2). but, the question has asked to find the upper bound in terms of Big Oh. Is there any principle to convert it into Big Oh form? I read some examples where they substituted some values and deduced but I couldn't understand.

Update: I apologize for writing the recursion equation wrong. The actual recursive equation for this question is:

```
T(n) = 2(n-1) + O(n)

```

# Answer
Your reasoning is wrong. It is in $\Theta(n^{\log\_2(5)})$. Hence, it is also in $O(n^{\log\_2(5)})$.

**Answer to the update**: Also, for the update part, it is wrong. You can find it by a straightforward expansion (no need to master theorem):

$$ T(n) = 2T(n-1) + O(n) = 2(2T(n-2) + O(n-1)) + O(n) \\ = 2^2T(n-2) + O(n-1) + O(n) = \cdots = \\ 2^n * T(0) + O(1) + O(2) + \cdots + O(n) \in O(2^n) $$
> 4 votes

---
Tags: time-complexity, recursion, big-o-notation, master-theorem
---


# Question
Title: Using B+Tree to implement index, when the index-key size and the data-block size are of the same order
I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a pivot in the B+Tree inner nodes, since the branching factor would be too small which results in too many IOS for any read/write operation, as the B+Tree will be significantly high. Moreover, I wish to preserve key's order, what means that compression methods which does not preserve order cannot work for me without adjustments. I am looking for papers which talks about it and related issues. In addition if you have tackled this problem before, I would be glad to accept any suggestions and ideas. Also I wish to use a B+Tree, I am open for any other data-structure which might be more appropriate for this task.

# Answer
> 3 votes
Note: In what follows, I'm going to use the term "B-tree" to refer to the general idea of B-trees regardless of the variant, and "B+-trees" to refer specifically to B+-trees.

You've correctly identified a real-word complication of using B-trees to index strings: B-trees are page-structured files, but strings are of arbitrary length. This is glossed over in most tutorials and textbooks, but it's a real issue.

Most theoretical presentations of B-trees talk in terms of fixed fanouts, but in practice, the fanout of a node is partly determined by the sizes of the keys. If the keys are physically smaller, you can store more pointers in the node.

For this reason, many (probably most) database systems impose an upper limit on the size of a key that can be stored in a node. Say you're using 64kB pages/blocks, then you might require that no key can take up more than 8kB in a node. This gives you a minimum fanout of 8 for a B+-tree inner node (remember that if there are n pointers out of a node, you only need to store n-1 keys).

The simplest (and likely the most common) realisation of this idea means that the index is only "fast" on the first 8kB of a string, and the index lookup devolves to some other algorithm (e.g. linear or binary search) if there are too many records whose keys are distinct, but not distinguished by their first 8kB.

For a general-purpose DBMS, this is probably the right thing to do. The meaning of a query is still correct because the "real" keys are present in the records, and the system doesn't spend a lot of complexity on an uncommon case.

Even relatively inexperienced database designers know what B-tree string indexes are good for, and indexing a whole XML document as a string is not that. If someone ever does it, whether on purpose or by accident, the DBMS will still return the correct answer, but it will just degenerate to a less-efficient algorithm, and probably also signal to the database administrator that there are a significant number of inefficient queries occurring and perhaps they should take a look.

This is why the problem hasn't historically received a lot of attention.

OK, but let's assume you're not doing that. Your database is not general-purpose, and you have an excellent reason to want to index long strings. What to do?

If the key size is really roughly the same as the page size, this suggests a simple solution: make the page size bigger. Page size doesn't matter as much as it once did, since virtual address spaces are so much bigger than file sizes. Plus, you get a read-ahead bonus on modern operating systems if you read part of a file sequentially. So simply using bigger pages may not be as bad as you think if you need a quick and dirty solution.

But even if virtual memory space is essentially free, RAM and cache are not, so it's worth trying to be smart about it.

A few observations:

* You don't need to store "real" keys in a B+-tree internal node. You only need a value which is guaranteed to be "between" all of the keys in two child subtrees.
* If you have long keys, you don't want to be comparing whole keys all the time, and indeed you probably aren't. The further down you go in the tree, the more likely it is that all of the keys in the subtree share a (long?) prefix. You don't want to store, or compare, that prefix in every place where a key needs to be stored.

You see, most of the time, you'll find yourself in one of two situations: either the set of keys in the index that you're considering don't have a long common prefix, in which case you should be able to compare the first portion of the keys only, or they do have a long common prefix, in which case you shouldn't need to compare that prefix. Moreover, that prefix should only need to be stored *once* for all keys in the subtree.

This suggests that what you probably want is something more like a trie. Perhaps unsurprisingly, there are data structures that do this, such as prefix B-trees and B-tries (which are basically burst tries stored on disk).

I recommend you read those papers, but I'll try to give you some ideas about the design space here.

Suppose that all keys under a given node have a common prefix. Then within a node, you only need to store the "distinguishing" parts.

Think about the "internal" representation of a B+-tree node. The way that B+-trees are usually presented is that internal nodes are an array of n-1 keys and an array of n pointers, and you use binary search on the keys to find which pointer to traverse.

Arrays-with-binary-search are only one possibility, and you could in theory pack any search data structure that you want within a node. There's no reason why you couldn't use something more like a trie for the node representation.

If you do find yourself with a highly lopsided node in your B+-tree, say where one key is different in its first character, but all of the others have an 8kB prefix in common, you could use that to inform the balancing policy. Perhaps that one key could be moved into a sibling node? Even if that results in the sibling node splitting, that could be preferable than the alternative.

You also may have to live with using a different balance condition for your tree as a whole, such as the fanout for each node depending on key distribution, or the distance from the root not being the same for all leaves.

Consider the possibility, for example, of a B+-tree node with only one child pointer, with the rest of the node simply serving the purpose of storing "common prefix" for all child keys. You could think of this as inserting an extra "level" in the node where needed, or you could think of that node and its child as being one logical node that just happens to be larger than a page in size so that more key material can be stored. Is this a distinction without a difference?

If you're worried about complexity... well, yes, you would like $O(\log n)$ I/O operations where $n$ is the number of nodes, but if keys are huge, there is no way (compression notwithstanding) to get around doing $O(\frac{s}{p})$ I/O operations where $s$ is the size of the key and $p$ is the page size. We usually don't consider that when analysing B-trees, but that may dominate in your application.

Good luck!

---
Tags: data-structures, reference-request, database-theory, data-compression, storage
---


title: Return indices in the two sum problem

text:
# Question
Title: Return indices in the two sum problem
Given an array unsorted `P` of integers and a number `m`. I am trying to write a code that returns indices `i`, and `j` to satisfy `8P[i] + 7P[j] = M` with time `O(n log n)`.

I iterated over `P[0]` to `P[n-1]` and searched for `P[j] = (M - 8P[i])/7` using binary search. Here, I can get the values of `P[i]` and `P[j]`, but the original index of `j` is changed while sorting before binary search. What could be the better way to get the index?

# Answer
Create a $2$-d array $D\[n\]\[2\]$, where $D\[i\]\[0\]$ stores $P\[i\]$, and $D\[i\]\[1\]$ stores the index $i$.

Sort the array by comparing just the first value. When, swapping the two items of the array, swap their second values also. In this way, you can access the original index value after sorting.

There are other ways to do it. For example, create an array of structure or a pair of two values, etc, and sort the items based on the first value.
> 0 votes

---
Tags: algorithm-analysis, big-o-notation, searching
---


# Question
Title: Are the weights between hidden layers changed in backwards propogation? If so, how
If so, I don't understand how, as a large part of back propogation is knowing what the 'real' answer is in comparison to 'predicted' answer. With 1 neuron in a hidden layer, we do not know the 'real answer' so theoretically it is impossible unless another technique is employed?

# Answer
What the backpropagation is computing, is the derivative (gradient) of that final output with respect to each neuron and each weight in the metwork.

This isn't a problem! You can think of it as computing the derivative of $f(g(x;w\_1);w\_2)$, once with respect to $w\_2$, and once with respect for $w\_1$. Do note that $f$ and $g$ would be very simple functions for which this computation can be done efficiently.

For example, if we set $f(a;w\_2):=a+w\_2$ and $g(x,w;1):= x+2w\_1$, then $f(g(x;w\_1);w\_2)=x+2w\_1+w\_2$, and the derivatives by $w\_1$ and $w\_2$ would be $2$ and $1$ respectively. Do note though, that in a real scenario, the functions are a bit more complicated and you might needore thought about how to compute the gradients (hence the backpropagation algorithm)
> 2 votes

# Answer
Backpropagation computes the gradient of the loss function (with respect to the weights). Then, the weights are updated using this gradient. There are many tutorials on how back propagation works. Note that supervised learning assumes all training set instances are labelled, so we *do* know what the real answer is for each sample in the training set; the loss function is computed based on the extent to which the prediction matches (or does not match) this real answer.
> 1 votes

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


# Question
Title: How can I optimize the systems in the paper "Ensembling Ten Math Information Retrieval Systems"
My question is about the paper Ensembling Ten Math Information Retrieval Systems.

I already know the algorithms in the paper can answer questions only using dot products (look the post).

How can I optimize them?

Could you add here (and in the next paper you will produce) the complexities of time preprocessing, memory and time consumption for question answering for all systems? (this is a solicitation for @Witiko)

# Answer
Here are two major ways in which you can make the ten math information retrieval systems in the MIRMU and MSM at ARQMath 2021 paper (and many other experimental retrieval systems) faster:

1. using appropriate data structures for exact nearest-neighbor search,
2. using approximate nearest-neighbor search.

#### Data structures

All systems except MSM – PZ use either sparse or dense matrices to represent the document corpus and to perform exact NNS. For a corpus of size $n$, this is a representation that is easy to construct ($\mathcal{O(n)}$), but quite costly for nearest-neighbor search (NNS) even if we bound the query length by a constant because we need to check every document in the collection ($\mathcal{O}(n)$) even if we only need the 1,000 nearest neighbors or fewer.

MSM – PZ uses pyserini, which is a Python library on top of the industry-strength Apache Lucene. Lucene uses the inverted index to represent a document corpus. For a corpus of size $n$, the worst-case time complexity of NNS is still $\mathcal{O}(n)$, but since we will only check documents that contain at least one term from the query, the actual speed is much higher. You can see this in the speed results from the paper, where MSM – PZ is much faster at searching (1.1 seconds per a query on average) than the other systems:

All systems except MSM – PZ that use NNS with sparse high-dimensional vectors (i.e. all except MSM – PZ and MIRMU – CompuBERT) can be optimized by using an inverted index instead of matrices as their data structure. For MIRMU – CompuBERT, we could use any data structure for NNS with dense low-dimensional vectors, which there are several.

#### Approximate nearest-neighbor search

Moving away from exact search allows you to achieve $\mathcal{O}(1)$ time complexity of NNS with dense low-dimensional vectors at the cost of accuracy: some nearest neighbors may be missed and some distant neighbors may show up at the family dinner. Embarassing! Popular algorithms implemented in Python include annoy and faiss. The MIRMU – CompuBERT system could be optimized this way.

Since the constant-time complexity depends on a constant number of dimensions, the above does not apply to sparse high-dimensional vectors, where the dimensionality is not constant but equals the vocabulary size ($\sqrt{n}$ according to Heaps' law). The curse of dimensionality rears its ugly head once again! Here are some tentative ideas for a solution:

1. You could use dimensionality reduction techniques to reduce high-dimensional sparse vectors to low-dimensional dense vectors. However, there are reasons to believe that this will impact your retrieval performance.
2. Alternatively, you can achieve $\mathcal{O}(1)$ time complexity in an inverted index by pre-sorting documents by a common criterion that reflects general usefulness (e.g. PageRank) and then stop the retrieval after a certain number of documents has been collected. See the textbook of Manning for a more complete discussion and implementation details. In theory, pyserini should be capable of this, but I am not sufficiently familiar with it.

#### Why is MIRMU – SCM so slow?

It is, isn't it? 3.72 minutes per a query on average. The SCM uses the formula $\vec{x}^T\cdot S\cdot\vec{y}$ to compute the similarity of two documents $\vec{x}, \vec{y}$ according to a term similarity matrix $S$:

*The representation of two documents, “Hi, world” $(\vec{x})$ and “Hello, world” $(\vec{y})$ in the TF-IDF vector space model (VSM, left) and in the TF-IDF soft vector space model (soft VSM, right). In the VSM, different terms correspond to orthogonal axes, making the document representations distant despite their semantic equivalence. In the soft VSM, different terms correspond to non-orthogonal axes, where the angle between the axes is proportional to the similarity $(S)$ of terms in a word embedding space (middle).*

This formula is quadratic in the vocabulary size ($\mathcal{O}(\sqrt{n})^2 = \mathcal{O}(n)$ according to Heaps' law), which makes NNS extremely costly ($n\cdot \mathcal{O}(n) = \mathcal{O}(n^2)$). However, as I show in proof to Theorem 3.4 in my paper, we can reduce the time complexity from $\mathcal{O}(n)$ to $\mathcal{O}(1)$ by making sure that matrix $S$ contains no more than $C$ non-zero elements in any column for a constant $C$ (we used $C = 100$ in MIRMU – SCM). Here is our implementation in the gensim Python library. It is painfully slow. Why?

The paper assumes that we will compute $\vec{x}^T\cdot S\cdot\vec{y}$ as a single operation, which will allow us to eliminate any $i$ and $j$ for which either $x\_i = 0, y\_i = 0,$ or $s\_{ij} = 0$: $$\vec{x}^T\cdot S\cdot\vec{y} = \sum\_i\sum\_j x\_i\cdot s\_{ij}\cdot y\_j$$ Our implementation uses the SciPy library for convenience. SciPy will separate $\vec{x}^T\cdot S\cdot\vec{y}$ into two operations: $\vec{x}^T\cdot S$ and $\\\_\cdot\vec{y}$. This makes our implementation $O(\sqrt{n})$ instead of $O(1)$.

Here are some ideas for an improvement:

1. If you can figure out how to compute $\vec{x}^T\cdot S\cdot\vec{y}$ over sparse high-dimensional $\vec{x}, \vec{y},$ and $S$ efficiently in Python, you could significantly speed up MIRMU – SCM. This may involve low-level Cython or C programming.
2. Alternatively, you could use the transformations discussed in Theorem 4.2 of my paper to first transform the document vectors to a form $\vec{x}', \vec{y}',$ where a simple dot product $\vec{x}'^T\cdot\vec{y}'$ is equivalent to $\vec{x}^T\cdot S\cdot\vec{y}$, and then use some general solution for exact or approximate NNS over sparse high-dimensional vectors as discussed in the first part of my answer.

Neither is a simple undertaking and will require significant programming expertise and effort. Perhaps you can contribute?
> 3 votes

---
Tags: algorithm-analysis
---


# Question
Title: Does CompuBERT suffer from the curse of dimensionality?
This question is about CompuBERT (new implementation).

I have read textual data have high dimensionality so I would like to know the behaviour of CompuBERT which uses a dot product for question answering.

If I increase the embedding dimension will CompuBERT suffer from the curse of dimensionality?

(I googled for the same question for sentence-BERT/siamese-BERT but there is no study yet about that...)

# Answer
The time complexity of matrix multiplication depends on both dimensions $m$ (the number of documents) and $n$ (the number of features). That is to say: Yes, increasing the number of features will adversely effect the speed.

> I googled for the same question for sentence-BERT/siamese-BERT but there is no study yet about that...

I don't assume there ever will be. The above observation is quite pedestrian.
> 0 votes

---
Tags: information-retrieval
---


# Question
Title: prove sub array has a definite form with distinct end point integers
An array has elements from set {0, 1, 2}. A span **SP** of an array is any interval *\[start S, end E\]* such that the sub array must contain all elements from {0,1,2}.

For example: in Array A = (0,1,0,1,1,2,0,1) we can say SP=\[1,6\] and SP=\[5,8\] but \[1,5\] is not a span as elements in array from index 1 to index 5 (0,1,0,1,1) do not contain {0,1,2}.
Here in the example array A minimum SP is \[5,7\] as it has only 3 elements (1,2,0) and maximum SP is \[1,6\] as it has 6 elements (0,1,0,1,1,2).

To find the number of elements in SP we can just (end E - start S + 1) i.e in the above example SP = \[1,6\] = 6 - 1 + 1 = 6 elements in this sub array (0,1,0,1,1,2)

How can i show that sub array of minimum SP is of the form $xy^{E -S - 1}z$ where (x,y,z) is a permutation of (0,1,2).

# Answer
Let $A$ be the array, and $B$ be the minimum span from $A$ (starting in $x$ and ending in $z$). We will prove that $x$ and $z$ only occur **once** in the subarray $B$.

Lets assume towards contradition, that $x$ occurs at least twice in $B$, and denote by $k$ the last index in $B$ at which $x$ appears. By our assumption, we know that $k\>0$. Now we have two parts: either there occurs a $y$ after the index $k$, or there isn't.

* If there is a $y$ after the index $k$, then the subarray of $B$ starting at $k$ would have all three values: $x$ at $B\[k\]$, $y$ somewhere afterwards, and $z$ at the end. Hence, we proved that in this case $B$ isn't minimal (which contradicts our assumption on it).
* If there isn't a $y$ after $k$, then denote $m$ the last index at which $y$ appears. Since it doesn't appear after $k$, and $B\[k\]=x$, then $m\<k$. But also $0\<m$ since $B\[0\]=x$. Hence, the subarray of $B$ starting at $m$ would contain all three values: $x$ at $B\[m\]$, $y$ at $B\[k\]$, and $z$ at the end. But since $m\>0$, then this subarray is smaller than $B$ which once again contradicts our assumptions on it.

You can prove the same way also for $z$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, arrays
---


# Question
Title: Is top-down dynamic programming always recursive?
I think top-down dynamic programming is mostly recursive (at least when we use memoization). For instance, solving the rod-cutting problem by this algorithm:

```
MEMOIZED-CUT-ROD(p, n):
    let r[0..n] be a new array
    for i = 0 to n:
        r[i] = -\infty
    return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r):
    if r[n] >= 0:
        return r[n]
    if n == 0:
        q = 0
    else q = -\infty
        for i = 1 to n:
            q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
    r[n] = q
    return q

```

But is it always recursive? By recursive I mean we call the same function but with smaller parameters (Of course if this is the correct definition for recursive.)

Here's some text about dynamic programming from CLRS:

There are usually two equivalent ways to implement a dynamic-programming approach. We shall illustrate both of them with our rod-cutting example. The first approach is top-down with memoization. In this approach, we write the procedure recursively in a natural manner, but modified to save the result of each subproblem (usually in an array or hash table). The procedure now first checks to see whether it has previously solved this subproblem. If so, it returns the saved value, saving further computation at this level; if not, the procedure computes the value in the usual manner. We say that the recursive procedure has been memoized; it “remembers” what results it has computed previously. The second approach is the bottom-up method. This approach typically depends on some natural notion of the “size” of a subproblem, such that solving any particular subproblem depends only on solving “smaller” subproblems. We sort the subproblems by size and solve them in size order, smallest first. When solving a particular subproblem, we have already solved all of the smaller subproblems its solution depends upon, and we have saved their solutions. We solve each subproblem only once, and when we first see it, we have already solved all of its prerequisite subproblems.

# Answer
I think the short answer here is: There is no such thing as top-down dynamic programming.

The definition of *a recursive function* is a function that calls itself. In dynamic programming, we find solutions for subproblems before building solutions for larger subproblems.
> 2 votes

---
Tags: dynamic-programming, recursion
---


# Question
Title: Time-varying edge cost Minimum Spaning Tree
I am having a hard time wrapping my head around the time-varying edge cost of this question :

> Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a function $f\_e$. Thus, at time t, it has cost $f\_e(t)$. We’ll assume that all these functions are positive over their entire range. Observe that the set of edges constituting the minimum spanning tree of $G$ may change over time. Also, of course, the cost of the minimum spanning tree of $G$ becomes a function of the time $t$; we’ll denote this function $c\_G(t)$. A natural problem then becomes: find a value of $t$ at which $c\_G(t)$ is minimized. Suppose each function $f\_e$ is a polynomial of degree 2: $f\_e(t) = a\_et^2 + b\_et + c\_e$ , where $a\_e$ is positive for each edge $e$. Give an algorithm that takes the graph $G$ and the values $\\{(a\_e , b\_e , c\_e) : e ∈ E\\}$ and returns a value of the time $t$ at which the minimum spanning tree has minimum cost. Your algorithm should run in time polynomial in the number of nodes and edges of the graph $G$. You may assume that arithmetic operations on the numbers $\\{(a\_e , b\_e , c\_e)\\}$ can be done in constant time per operation.

My first idea was, because $a\_e$ is positive, to find out the maximum value of $t$ that minimizes the cost of an edge $e$ (in other words looping through every edge once and find their minima). Intuitively, the maximum of these minima could be an upper-bound for the value that minimizes $c\_G(t)$. Then I could run a MST algorithm for every time step from 0 to t and return the t that answers the question. However, this looks like a very brute-forcey method and thus not time-efficient at all.

Any help would be greatly appreciated!

Note that this question was part of the Greedy Algorithm chapter.

# Answer
Consider the edges sorted by $f\_e(t)$ for some $t$.

Two quadratic polynomials can intersect at most two times. When the cost function of two edges $e\_1$ and $e\_2$ cross at time $t$, it means that

* $f\_{e\_1}(t-\epsilon) \< f\_{e\_2}(t-\epsilon)$ and
* $f\_{e\_1}(t+\epsilon) \> f\_{e\_2}(t+\epsilon)$.

Since there are $m$ edges and each pair of edges crosses at most twice, we have at most $2 \cdot {m \choose 2} \leq m^2$ many crossings, and therefore at most $m^2$ many times two edges can swap order in the sorted list.

Now you try all possible time intervals that don't contain crossings, $(t\_a, t\_b)$ and pick the $n-1$ cheapest edges. What remains is to minimize a sum over $n-1$ quadratic functions which is indeed a quadratic function.
> 1 votes

---
Tags: algorithms, graphs, trees, greedy-algorithms, minimum-spanning-tree
---