title: Addition or Subtraction of Polynomials

text:
# Question
Title: Addition or Subtraction of Polynomials
Can addition (or subtraction) of polynomials of degree $\< n$ be done in constant time ?

I am quite new to algorithms. I thought about using sorted arrays for storing the coefficients. But the addition of two sorted arrays appears to be $\in O(n)$. However, I am not convinced that this is the best solution. Could someone please help clarify?

# Answer
> 1 votes
Because the set $\\{1,x,\ldots,x^{n-1}\\}$ is a base for polynomials with degree $\<n$, by definition of base, no element in this set can can be expressed as a combination of others, i.e. no element can be “ignored”.

Therefore, we know that our algorithm needs to at least read all the coefficients corresponding to $n$ elements of the base, thus making at least $n$ steps.

On the other hand, you found that adding/subtracting polynomials can be simulated by element-wise adding/subtracting lists of their coefficients, which is $O(n)$, meaning it requires less than $c \cdot n$ steps for some constant $c$.

Now we know that your algorithm needs to make some number of steps that is between $n$ and $c\cdot n$, and as @Yuval pointed, this is $\Theta(n)$ time complexity.

*(this is all for general case and I don’t know if there exists some special space of polynomials that can be represented more compactly, thus making it possible to add/subtract them faster, but also I think that you are in fact interested in a general case)*

# Answer
> 0 votes
Storing the coefficients of the polynomial terms as arrays is the right way to go, but you will need to traverse both arrays (in one pass) to add the coefficients, and hence your running time will be $O(n)$.

The only way I can see this being faster is in one very limited case.

If you're working with polynomials of max degree 63 with coefficients from $\mathbb{F}\_2$, i.e. either 0 or 1. Then you can store each polynomial as an `unsigned long` where $a\_0 a\_1 a\_2 \ldots a\_{62}a\_{63}$ represents the polynomial:

$$a\_0 + a\_1x + a\_2x^2 + \ldots + a\_{62}x^{62} + a\_{63}x^{63}$$

and you have two such polynomials, say `unsigned long p1` and `unsigned long p2`, then their sum is simply `p1 XOR p2`.

In that case, addition (which is the same as subtraction) can be done in constant time. Furthermore, multiplication can be done in $O(n)$ instead of $O(n^2)$ by iterating over one polynomial and shifting the other.

This may be generalizable to any polynomials over the integers mod $n$ but I don't immediately see how.

---
Tags: time-complexity
---


title: Question related to vertex cover

text:
# Question
Title: Question related to vertex cover
The definition of vertex cover is as is: Set of vertices such that each each has atleast one endpoint in that set.

In the above example, why can't we consider all vertices as vertex cover since all vertices are endpoints to all the edges.

# Answer
> 1 votes
Your misunderstanding might be a false assumption that there is a *unique* vertex cover. This is hardly the case – there could be many different ones.

The set of all vertices always forms a vertex cover. However, there are always smaller vertex covers (even in the complete graph!), and we are usually interested in finding a vertex cover which is as small in size as possible.

# Answer
> 1 votes
As Yuval said, there is a trivial vertex cover for any graph, namely all the vertices.

The NP-complete problem is actually, "Is there a vertex cover of size $\le n$?"

The idea is to find the smallest set of vertices that form a vertex cover.

---
Tags: algorithms
---


title: Algorithm for Even Fitting

text:
# Question
Title: Algorithm for Even Fitting
I'm trying to design an algorithm for evenly fitting decimal numbers into a decimal number.

Say I have a set $N$ of decimal numbers ($N\_1$, $N\_2$, ..., $N\_n$) and a target value $Y$. I'd like to see what combination of values of $N$ (values may be used zero to many times) add up *evenly* to $Y$.

I've accomplished it by selecting random values of $N$ until I either add up to $Y$ or pass it - at which point I start over. This algorithm does not seem efficient, however. Sometimes it takes 50k passes before it lands on an answer.

The set I'm actually working with is 21 dollar values between \\$0.89 and \\$8.04 and the target is \\$43.94.

Is there a simpler algorithm?

# Answer
> 1 votes
Provided the $N\_i$ are all positive, this is pretty much exactly the problem of "how many ways can I make value $Y$ out of coins with values $N\_i$ (assuming no restriction on the number of coins)?"

That problem has a very easy recursive solution that breaks into two cases at each step:

1. Include a "coin" of value $N\_i$ and recurse.
2. Assume you have used $N\_i$ as many times as you are willing and recurse using only values $N\_j$ for $j \> i$.

---
Tags: algorithms
---


# Question
Title: Deleting edges such that largest connected component has at most $n/4$ nodes
Let $G = (V, E)$ be a connected undirected graph with $n \> 4$ nodes $V = \\{v\_1, v\_2, \dots, v\_n\\}$ and $m$ edges. Let $\\{e\_1, e\_2, \dots , e\_m\\}$ be all the edges of $G$ listed in some specific order. Suppose that we remove the edges from $G$ one at a time, in this order. Initially, the graph is connected, and at the end of this process the graph is disconnected. Therefore, there is an edge $e\_i$ such that just before removing $e\_i$ the graph has at least one connected component with more than $n/4$ nodes, but after removing $e\_i$ every connected component of the graph has at most $n/4$ nodes.

Give an efficient algorithm that determines this edge $e\_i$. Assume that $G$ is given to the algorithm as a plain linked list of the edges appearing in the order $e\_1, e\_2, \dots, e\_m$. The worst-case running time of this algorithm must be asymptotically better than $O(mn)$.

# Answer
One naive thought would be that we can maintain the list of the size of current connected component. After removing an edge the content of the list will be changed and when the max member of this list decreased to no more than $n/4$ we can terminate and output the edge. However, simulating such process seems inefficient.

Though removing edge is somehow hard for us to maintain the size of connected component, **adding edge is not**.

We can consider the problem reversely:

Initially, there is no edge in graph $G$, then we add edge in the order of $e\_n,e\_{n-1},\cdots,e\_1$ and at the end of this process $G$ is connected. Therefore there an edge $e\_i$ such that just before adding $e\_i$, every connected component of the graph has at most $n/4$ nodes, but after adding $e\_i$, the graph has at least one connected component with more than $n/4$ nodes.

Obviously, such $e\_i$ is just the edge we want for the origin problem.

We can use Union-Find Algorithm to maintain the size of each connected component. When adding an edge$(u,v)$, first check whether $u,v$ are in different connected components. If yes, then we get a bigger connected component and the size of it will be the sum of size of those two components, otherwise we do not need to do anything.

Once we find adding $e\_i$ results in a connected component bigger than $n/4$, we can terminate and output it.

The overall time complexity is $ O(m\alpha (n)) $
> 5 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: proving correctness of algorithm about graphs with DFS
I need to prove/disprove the correctness of the following algorithm: Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that way. First, you run the DFS algorithm on the graph, since it is connected it will result in a single tree. The for each node $u$, you declare the field $L\[u\]$. $L\[u\]$=0 if $u$ is the root of the tree, otherwise $L\[u\]=L\[\pi(u)\] + 1$, when $\pi(u)$ is the parent of $u$ in the tree.

Finally the algorithm says that: if there exists and edge $e=${$u,v$} in the original graph $G$ so that $L\[u\] + L\[v\]$ is even than the graph contains and odd cycle. Otherwise (if such edge doesn't exist) the graph doesn't contain an odd cycle.

I am inclined to says that the algorithm is correct. I even have an idea of a proof that uses the idea that if such edge $e$ exists, then it must be a back edge in the DFS tree. That would mean there is a cycle and since $L\[v\] = L\[u\] + t$, where $t$ is the number of tree edges in the DFS tree between $u$ and $v$, I'll get $2L\[u\] + t = $ even number, which means that $t$ is even and then with the edge $e$ there is an odd cycle.

However, I want to make sure that I am not missing anything, So if some one approve my way or even give an example to disprove the algorithm I would be glad.

# Answer
Your algorithm is correct, but I think there's an issue with your proof. The issue is that if $u$ and $v$ are in different branches of the tree, then their distance would be $L\[u\]+L\[v\]$, not $t$. This quantity is already defined to be even, so your proof only needs to be slightly modified to handle this case.

Edit: It is also the case that for any DFS tree, any edge not in the tree will be a back edge between nodes in the same branch. Therefore, the question asker's proof is correct.
> 1 votes

---
Tags: algorithms, graphs, correctness-proof
---


# Question
Title: Placing a point between two nearest ones
I have a closed 2D shape expressed as a list of points, like that:

```
[
  {0,  5}, <-- {x, y}
  {10, 5},
  {15, 6},
  ...
]

```

The user has a canvas: each time he clicks on that canvas, a point will be appended to the list, and he will see the updated shape on screen.

How can insert the point between two nearest points instead of appending it to the list?

Let's say I have this shape:

All points got inserted counter-clockwise, starting from the first point to the left of the red one (meaning that the red one will be the last one):

Suppose that the user wants to place a point on the yellow area:

Right now the algorithm simply appends the new point to the list of existing points, so the new point will be inserted after point number 5, resulting in this shape:

Clearly I don't want this behaviour. I'd like the point to be inserted between points 3 and 4 instead, so that the result will be like that:

I came up with a possible solution.

Find distances between tuples and subtract them. The point's nearest tuple is the one with the minimum distances subtraction

Example:

```
d1 = abs(pink - blue)
d2 = abs(blue - green)
d3 = abs(green - red)
d4 = abs(red - yellow)
d5 = abs(yellow - pink)

```

Here, `d2` will be the minimum, hence the point will be inserted between 3 and 4.

This approach however is buggy: if point 5 is a bit closer to the line between point 3 and 4, `d3` will be the minimum, so the point would be inserted between points 4 and 5, which would be wrong.

Calculating areas of triangles instead of distances has the same issue.

I'm thinking there should be a way to take the segment distance into account. I mean, I would need to not only calculate distances between points, but also the new point's distance from the given segment. That way, I could tell that segment `3-4` is the nearest one, so I'll insert the point between 3 and 4.

So, what is an effective way to to handle this?

# Answer
Don't add the point between the closest pair of points; add it between the endpoints of the closest edge.
> 1 votes

---
Tags: algorithms, nearest-neighbour
---


title: Why do compilers produce assembly code?

text:
# Question
Title: Why do compilers produce assembly code?
Assembly language is converted in to machine language by assembler. Why would a compiler convert high-level language to assembly? Can't it directly convert from the high-level language to machine code?

# Answer
Other reason for compilers to produce assembly rather than proper machine code are:

* The symbolic addresses used by assemblers instead of hard-coding machine addresses make code relocation much easier.
* Linking code may involve safety checks such as type-checking, and that's easier to do with symbolic names.
* Small changes in machine code are easier to accomodate by changing the assembler rather than the code generator.
> 20 votes

# Answer
A compiler does usually convert high-level code directly to machine language, but it can be built in a modular way so that one back-end emits machine code and the other assembly code (like GCC). The code generation phase produces "code" which is some internal representation of machine code, which then has to be converted to a usable format like machine language or assembly code.
> 16 votes

# Answer
Historically a number of notable compilers did output machine code directly. There are some difficulties with doing so, however. Generally someone who's trying to confirm that a compiler is working correctly will find it easier to examine assembly-code output than machine code. Further, it's possible (and was historically common) to use a one-pass C or Pascal compiler to produce an assembly-language file which can then be processed using a two-pass assembler. Generating code directly would require either using a two-pass C or Pascal compiler or else using a single-pass compiler followed by some means of back-patching forward-jump addresses \[if a runtime environment makes the size of a launched program available in a fixed spot, a compiler could write a list of patches at the end of the code and have startup code apply those patches at runtime; such an approach would increase the executable size by about four bytes per patch-point, but would improve program-generation speed\].

If the goal is to have a compiler that runs quickly, direct code generation can work well. For most projects, however, the cost of generating the assembly-language code and assembling it really isn't a major problem nowadays. Having compilers produce code in a form that can interact nicely with code produced by other compilers is generally a big enough benefit to justify the increase in compilation times.
> 11 votes

# Answer
Even platforms that use the same instruction set may have different relocatable object file formats. I can think of "a.out" (early UNIX), OMF, MZ (MS-DOS EXE), NE (16-bit Windows), COFF (UNIX System V), Mach-O (OS X and iOS), and ELF (Linux and others), as well as variants of those, such as XCOFF (AIX), ECOFF (SGI), and COFF-based Portable Executable (PE) on 32-bit Windows. A compiler that produces assembly language need not know much about object file formats, allowing the assembler and linker to encapsulate that knowledge in a separate process.

See also Difference between OMF and COFF on Stack Overflow.
> 3 votes

# Answer
Usually compilers work internally with sequences of instructions. Each instruction will be represented by a data structure representing it's operation name, operands and so-on. When the operands are addresses those addresses will usually be symbolic references, not concrete values.

Outputting assembler is relatively simple. It's pretty much a matter of taking the compilers internal data structure and dumping it to a text file in a specific format. Assembler output is also relatively easy to read which is useful when you need to check what the compiler is doing.

Outputting binary object files is significantly more work. The compiler writer needs to know how all the instructions are encoded (which can be far from trivial on some CPUS), they need to convert some symbolic references to program counter relative addresses and others in to some form of meta data in the binary object file. They need to write everything out in a format that is highly system specific.

Yes you absolutely can make a compiler that can outputs binary objects directly without writing out assembler as an intermediate step. The question like so many things in software development is whether the reduction in compilation time is worth the extra development and maintenance work.

The compiler i'm most familiar with (freepascal) can output assembler on all platforms but can only output binary objects directly on a subset of platforms.
> 3 votes

# Answer
A compiler should be able to produce an assembler output in addition to the normal relocatable code is for the benefit of the programmer.

One time I just not find the bug in a C program running on Unix System V on an LSI-11 machine. Nothing seemed to work. Finally in desperation I had the protable C compiler excrete an assembler version of its translation. I had finally found the bug! The compiler was allocating more registers than existed in the machine! (The compiler allocated registers R0 through R8 on a machine with only registers R0 through R7.) I managed to work around the bug in the compiler and my program worked.

Another benefit of having assembler output is trying to use "standard" libraries that use a different parameter passing protocols. Later C compilers allow me to set the protocol with a parameter ("pascal" would make the compiler add the parameters in the order given as opposed to the C standard of reversing the order).

Yet another benefit is allowing the programmer to see what an appalling job his compiler is doing. A simple C statement takes about 44 machine instruction. Values are loaded from memory and then quickly discarded. etc, etc, etc ...

I personally believe that having a compiler instead of a relocatable object module is really stupid. While compiling your program, the compiler gathers a great deal of information about your program. It usually stores all this information in something called a Symbol Table. After excreting the assembler code it throws all this information table. The assembler then examines the excreted code and re-collects some of the information the the compiler already had. However assembler know nothing about If statements of For statements or While statements. So all this information is missing. Then the assembler produces the relocatable object module that the compiler did not.

Why???
> 1 votes

---
Tags: compilers, code-generation, assembly
---


# Question
Title: Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?
I can compute this easily in the case that $xy \< 2^{64}$. But I'm not sure how to do this if $xy \geq 2^{64}$.

I know that $\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$, but I'm not sure where to go from there.

# Answer
Use two integers to represent one integer. Assume you are using c/c++. You can use a struct that has two long long unsigned integers to represent $x$, $y$ and $z$. So you can express $x = 2^{32}x\_1+x\_2$ with $x\_1$ being a nonnegative integer smaller than $2^{32}$ and $x\_2$ being a nonnegative integer not greater than $2^{32}$. I would assume you will know the rest.

Or you can choose to use some libraries or built-in classes. For example, you can use BigInteger class in Java.

(It goes without saying that you will not have these problems if you were using Python, Ruby, etc.)
> 1 votes

# Answer
Split $x = 2^{32} \cdot x\_{hi} + x\_{lo}$, $y = 2^{32} \cdot y\_{hi} + y\_{lo}$. Then

$x \cdot y = 2^{64} \cdot x\_{hi}\cdot y\_{hi} + 2^{32} \cdot x\_{hi}\cdot y\_{lo} + 2^{32} \cdot x\_{lo}\cdot y\_{hi} + x\_{lo}\cdot y\_{lo}$. You can easily calculate each of these products except for the factor $2^{32}$ or $2^{64}$.

You split the products $x\_{hi}\cdot y\_{lo}$ and $x\_{lo}\cdot y\_{hi}$ into higher and lower 32 bits and add up the components.
> 1 votes

---
Tags: arithmetic, modular-arithmetic
---


# Question
Title: Regarding time complexity of multi-tape Turing machines
So let's say I've implemented an algorithm running in $O(n^2)$ on my 3-tape TM. What kind of time complexity would I expect for a single-tape TM?

I just don't know where to get started...

# Answer
Multi-tape Turing Machine running in $O(f(n))$ can be simulated by a single-tape Turing machine running in $O(f^2(n))$.

Try writing a single-tape Turing machine that stores symbols from your $3$ tapes on its one tape, separated by some unique symbol not in $\Sigma$.

---

**hint:** For every step of your $k$-tape machine, a one-tape machine must first do at most $k\cdot n$ steps to find the position.
> 1 votes

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


# Question
Title: Why does Radix sort require stable digit sorts?
I'm reading the CLRS book and have a question about the following quote from the book.

> In order for radix sort to work correctly, the digit sorts must be stable.

Why is stability required? Wouldn't Radix sort still produce correctly sorted output even if there was no consistency in ordering of identical values, since Radix sort sorts on every digit position?

# Answer
Integers that are equal in *some digit* aren't always equal (e.g., 12 and 13).

Let's sort `[13, 12]` using a LSD-first radix sort (base 10). But we'll use an unstable sort for each digit.

First we sort by the 1's place, so the array becomes `[12, 13]`.

Now we sort by the 10's places, but 12 and 13 have the same digit. Since the sort is unstable, the resulting array could be `[12, 13]` or `[13, 12]`. We don't know.

If the sort were stable we would be guaranteed to get a correctly sorted array.
> 8 votes

---
Tags: algorithms, sorting, radix-sort
---


# Question
Title: How to compare an element with other elements within an array efficiently for a condition
I need to compare each index with one another and associated array value as well.

For example,

```
for(int i = 0; i < n - 1; i++) {

    for(int j = i + 1; j < n; j++) {

        if(a[i] > a[j]) { // Condition will be any

            swap(a[i], a[j]); // Any action
        }
    }
}

```

Inside loops, there is a condition to check. Similarly I need to use any condition

eg: `if(i + j == a[i] + a[j])`

Could anyone help to optimize this index comparison? How to compare each index with other and element value with others efficiently i.e. less than O(n²)

# Answer
> 2 votes
In the general form you present, you have $\Theta(n^2)$ things to compare so you need $\Omega(n^2)$ time. If you know more about the arrays or the comparison operator (e.g., the arrays are sorted and the comparison is $\<$ or $\>$) then you can probably do something better but, without more restrictions, there's no hope.

---
Tags: time-complexity, sorting, arrays, comparison
---


# Question
Title: Justification for the pumping lemma of context free languages
I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those repeated states as many times as you wish.

However for the context free language version I can't seem to come up with the same intuitive understanding for why the lemma holds. My textbook mentions abusing the fact every CFG can be put into Chomsky normal form and then using some properties of binary trees to show productions can be pumped but Im having a hard time following why this would lead to repeated states, let alone two repeated states.

# Answer
> 1 votes
Im not sure what the rule is in linking to off site resources but I found this video particularity helpful in getting an intuitive understanding for the pumping lemma for CFGs

The idea is that a sufficiently long string will have some repeated path along it from root to leaf. This path can be repeated as many times as we wish. The left side and the right side of the tree will be "pumped" and the the characters in the center of the subtree will remain. This is where we get `x^n y z^n` substring from the pumping lemma. I highly recommend watching the video however, it is explained much better and the visualization helps.

# Answer
> 2 votes
A context-free grammar has a finite number of nonterminals. This means the number of different derivation trees you can generate such that each nonterminal on each path of each tree is different is also finite: if you have $n$ nonterminals, then each path longer than $n$ will contain at least one nonterminal twice. That means all *other* derivations have a repeating nonterminal $A$ on some path. We can then pump by repeating the path segment from $A$ to $A$ arbitrarily often. This remains true after we make the grammar proper by removing all unproductive and unreachable nonterminals and cyclic rules.

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


# Question
Title: fully homomorphic encryption with information-theoretic security?
An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can reduce your uncertainty about the plaintext.

Fully homomorphic encryption is, roughly, an encryption scheme where $\text{Encr}(T(x)) = T(\text{Encr}(x))$ for arbitrary transformations of the ciphertext and plaintext (this is not entirely accurate but that's not important for this question).

**Is it *theoretically* possible to have an information-theoretically secure FHE scheme?** That is, is it possible to encrypt a plaintext $x$, have an external party do computations on them in a fully homomorphic way, without them being able to gain ANY information about the plaintext even with **infinite**? computing power?

# Answer
> 1 votes
You said you don't need to conceal the set of transformations that have been applied. In that case a simple scheme is

$$T(\text{Enc}(x)) = \langle T, \text{Enc}(x)\rangle,$$

where $\text{Enc}$ is information-theoretically secure encryption (e.g., the one-time pad). In other words, you simply list in the cipher text which transformations should be applied to $x$ after it is decrypted.

---
Tags: information-theory, cryptography, encryption
---


# Question
Title: Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices
I'm trying to minimize the area of a simple (non-intersecting, without holes) polygon by adding points to it, or modifying points of its subset. Let me describe this more formally:

Let:

* $P$ be a polygon consisting of points $\\{x\_1,x\_2,...x\_n,x\_1\\}$
* $S$ be a subset of $P$, bounded by points $x\_j$ and $x\_k$:
* $m$ be a number of extra points we can allocate

Then, we want to minimize the area of $P$, using the following means:

* modifying the position of points $\\{x\_{j+1},...,x\_{k-1}\\}$
* adding new points to the interval $(x\_j,x\_k)$

Here is a very example for $m =1$ (notice that the boundary points $x\_j$ and $x\_k$ aren't subject to being modified)

So far, the best I can do is a bruteforce solution. Basically try moving the point around in some discrete increments into various directions, then check if it makes sense (see that it does not create intersections within the polygon), and calculate the area. After that, I check which direction gave the best area, and I continue the process again until the area converges.

Obviously this is a flawed solution in that:

* It does not guarantee anything, it is just trial and error
* It is extremely computationally expensive
* It gives rise to certain anomalies

My question is, could there possibly be a better approach, maybe even one that would guarantee an exact solution in polynomial time?

# Answer
Try all possibilities for vertices $P,Q,R,S$ where $P,Q$ are adjacent and $R,S$ are adjacent (there are $O(n^2)$ possibilities). For each such possibility, find the best way to add a point $T$ after $P$ and before $Q$, such that $T$ falls on the line segment $RS$. This involves finding a point $T$ on the line segment $RS$ that maximizes the area of the triangle $PTQ$. You should be able to do that in $O(1)$ time. Repeat for each possible $P,Q,R,S$ and take the best one found. This should yield an $O(n^2)$ time algorithm.

I don't know if it is possible to do better than $O(n^2)$ time.
> 0 votes

---
Tags: optimization, computational-geometry
---


# Question
Title: What is the best way to compress a string with only numbers and commas in it?
I have a string like this:

```
11,512,64,23,46,12,67,85,84

```

And I'm sure it's following these rules below:

1. Only `,` and `0123456789` in it.
2. No number will be bigger than 999, that means they are all 1,2 or 3 digits number.

Are there any simple algorithms that I can have to compress/decompress the data?

For instance, a very stupid way I can think is to convert each number into base-16 or even base base-36 numbers.

# Answer
Treat this as a base-11 number (the comma is treated like the digit "10"). Convert the base-11 number to binary, and use the resulting binary string as the compressed version of your data.

This will be close to optimal. It falls short of optimal only in that it does not take into account the guarantee that every number in the list will have at most 3 digits -- but even taking that into account would not improve the compression ratio much.

The absolute best method will depend on the distribution of data that you will be compressing; but I expect this will be close to optimal for most real-world distributions.
> 3 votes

---
Tags: algorithms, data-compression
---


# Question
Title: How many prefix code we can find for a given distribution of probability?
A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the same performance (efficiency)?

# Answer
> 0 votes
There are infinitely many prefix codes over $\\{a,b,c\\}$ containing 5 elements, for example $a,ba,b^2,b^3a,b^{4+n}a$ for all $n \geq 0$. I'm assuming the question is concerned with "saturated" or "minimal" prefix codes, which are prefix codes which satisfy one of the following equivalent conditions:

* Each string in $\\{a,b,c\\}^\omega$ contains some codeword as a prefix.
* Kraft's inequality is tight.
* The ternary tree corresponding to the code is full, that is, each internal vertex has exactly three children.

It's not hard to check that all such codes containing 5 codewords must look as follows: $$ \alpha, \beta, \gamma\alpha, \gamma\beta, \gamma\gamma. $$ For such a code to be optimal for your particular distribution, a necessary and sufficient condition is that $\alpha,\beta$ are assigned to the heavy elements and $\gamma\alpha,\gamma\beta,\gamma\gamma$ to the light elements. You can check it by direct calculation (there are only 3 options, up to symmetry), or by noticing that if a code uses a length-1 codeword for a light element and a length-2 codeword for a heavy element, then switching them reduces the average codeword length.

Indeed, if we *fix* the codewords, then it is easy to assign them to symbols. The more difficult task is to find the optimal set of codewords. In this case, there is only one set of codewords, so there is no need to run any fancy algorithm such as Huffman's.

---
Tags: probability-theory, information-theory, coding-theory, mathematical-foundations
---


# Question
Title: NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT
It is often stated that the MAX-XOR-SAT problem is NP-hard, and that likewise is the MAX-2-XOR-SAT problem. However, I cannot find a reduction from SAT to either of these problems, nor a proof of NP-hardness. Is one published anywhere?

# Answer
MAX-2-XOR-SAT is a generalization of the more familiar problem MAX-CUT.

To see this, consider a graph $G=(V,E)$. We will have a variable $x\_v$ for each $v \in V$, and a constraint $x\_u \oplus x\_v$ for each edge $(u,v) \in E$. We can identify a cut $S \subseteq V$ with a truth assignment by $S = \\{ v \in V : x\_v = 1 \\}$. You can then check that the number of clauses satisfied is exactly the same as the number of edges cut by $S$.
> 5 votes

---
Tags: np-complete, satisfiability
---


# Question
Title: Compound interest with varying compounding frequency
Here is the problem I have attempted to solve.

> Given original principal $n$ and aggregate rate $r$, find the maximum final principal that can be yielded.

Though I know that the higher the compounding frequency is, the higher the final principal will be, a special condition applies:

> Intermediate principals are rounded down to the the nearest integer each time.

So for example $n = 10000$ and $r = 3$, I can choose to have

* 1% growth 3 times
* a 2% growth then a 1% growth
* or a 3% growth.

For case 1 n would grow as 10000 -\> 10100 -\> 10201 -\> 10303.

For case 2 n would grow as 10000 -\> 10200 -\> 10302.

For case 3 n would grow as 10000 -\> 10300.

So in this case the highest value would be 10303.

As another example, take $n = 10$ and $r = 10$. As it will not yield any changes to $n$ unless the growth rate is higher than 10%, the answer is 11.

So in mathematical terms it is to find $\max n\prod(1+r\_i\\%)$ where $\sum r\_i = r$ with the rounding condition.

What I was trying to do is to find the minimum growth rate that would result in a change in $n$ and apply it immediately, then repeat the process until $r$ is used up, but it doesn't seem that it is getting the desired answer. Any hints would be appreciated. If you need any clarification please tell me.

```
    while(r > 0 && rate < r){
        rate++;
        if (n * (100 + rate) / 100 != n){
            n = n * (100 + rate) / 100;
            r -= rate;
            rate = 0;
        }
    }

```

$r\_i$ must be positive integers. This problem is adapted from A028:武器の強化 problem, which can be found here (on paiza, which is a Japanese-language coding contest site).

# Answer
> 1 votes
This problem is a good example of problems that can be solved by dynamic programming.

Given original principal $n$, the subproblems are, what is $p(t)$ for $0\le t\le r$, the maximum final principal that can be yielded if aggregate rate is $t$ . We have the following recurrence relation, where $//$ means the integer division, for example, $13 \operatorname{//} 5 = 2$.

$$p(t) = \max( p(0) + p(0)\* t \operatorname{//} 100,\ p(1)+p(1) * (t-1) \operatorname{//} 100,\ p(2)+ p(2) * (t-2) \operatorname{//}100,\ \cdots,\ p(t-1)+ p(t-1) * 1 \operatorname{//} 100) $$

From $p(0)=p$ you can compute $p(1)$. From $p(0)$ and $p(1)$, you can compute $p(2)$. And so on. Finally you can will get $p(r)$, which is what you want.

I will left you figure out the actual implementation. By the way, the code in question, fails when the original principal is 23 and the aggregate rate r is 9.

---
Tags: algorithms
---


# Question
Title: The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm
I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why.

Here the Wikipedia version:

Inputs: $n$: a composite number

Output: a nontrivial factor of $n$ or failure

1. select a smoothness bound $B$
2. define ${\displaystyle M=\prod \_{{\text{primes}}~q\leq B}q^{\lfloor \log \_{q}{B}\rfloor }} $ (note: explicitly evaluating $M$ may not be necessary)
3. randomly pick $a$ coprime to $n$ (note: we can actually fix $a$, e.g. if $n$ is odd, then we can always select $a = 2$, random selection here is not imperative)
4. compute $g = \operatorname{gcd}(a^M − 1, n)$ (note: exponentiation can be done modulo n)
5. if $1 \< g \< n$ then return $g$
6. if $g = 1$ then select a larger $B$ and go to step 2 or return failure
7. if $g = n$ then select a smaller $B$ and go to step 2 or return failure

I would say that:

The first step takes constant time (clear).

The second step takes $\mathcal{O}(B \log B)$ time due to the distribution of prime numbers.

The third step takes constant time.

Concerning the 4th step: Fast-Exponentiation takes (in the version that I know) $\mathcal{O}(\log M)$ time. The gcd takes $\mathcal{O}(\log n)$ time. (I supposed that $ n \< a^M-1$, but I am not sure if this is safe to assume.)

The remaining steps take constant time.

So because of step 2 and 4 I would say that the algorithm takes $\mathcal{O}(B \log B) + \mathcal{O}(\log n) + \mathcal{O}(\log M)$ time. What am I doing wrong?

# Answer
As you mention, the costliest step is computing $a^M \bmod{n}$. This is done using the repeated squaring algorithm. Each squaring or multiplication modulo $n$ takes time $M(n)$, where $M(n)$ is the time complexity of multiplication.

We can estimate the number of multiplications by $$ \sum\_{\text{prime } q \leq B} \frac{\log B}{\log q} \cdot \log q \< \pi(B) \log B = O(B). $$ This improves slightly on the Wikipedia estimate of $O(B\log B)$.

The school multiplication algorithm takes time $O(\log^2 n)$, which is how Wikipedia got that factor. But nowadays faster algorithms are known, which run in time $\tilde{O}(\log n)$. So a better estimate on the complexity is $\tilde{O}(B\log n)$.
> 2 votes

---
Tags: algorithms, runtime-analysis, primes
---


# Question
Title: Multiple Constraint Knapsack Problem Dynamic Programming
Is there any way for solving the Knapsack problem when we are limited by several constraints?

Let's assume that we have a set of items in which we have value `v` that we want to maximize and we also have two constraints `weight` and `volume` that must be lower or equal than the values `W` and `V` respectively.

My question is, can this problem be solved using dynamic programming?

# Answer
> 2 votes
Yes. More precisely, for any fixed number of constraints (for example, weight and volume) the problem has a pseudo-polynomial time algorithm based on dynamic programming.

The idea in your comment (add one more dimension to the dynamic programming table) is essentially correct. In the classic knapsack, for any $i=0,\ldots,n$ and $w=0,\ldots,W$, you compute the highest profit that you can get with items of type $\le i$ and total weight $\le w$ (so you can get an $O(nW)$ time algorithm). In the generalization, you also need to iterate on the total volume $v=0,\ldots,V$, which means an $O(n W V)$ time algorithm.

# Answer
> 0 votes
In knapsack algorithm, if any object fits the knapsack, you compare the value of the objects. You still have to compare the objects but you got two parameters to compare for each object. Tricky part will also be backtracking, if required. Refer this: http://user.engineering.uiowa.edu/~dbricker/Stacks\_pdf1/MultiDim\_Knapsack.pdf

---
Tags: dynamic-programming, knapsack-problems
---


title: Cost of the MST of the graph

text:
# Question
Title: Cost of the MST of the graph
Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated!

Although the picture shows a directed graph, please treat it as an undirected graph, ignoring all the edge orientations.

# Answer
> 0 votes
A Yuval said, you can just go ahead with any algorithm. In fact, you should probably be able to find a solution by trial and error.

In case you are stuck for some time, move your mouse over to see a solution below.

> We can use Prim's algorithm, which iteratively selects an edge of the least weight from the available edges as long as it does not introduce a cycle. We will select the edge of weight 1, two edges of weight 2, all edges of weight 3,4,5,6,7 respectively. We will skip the vertical edge of weight 8 since it introduces a cycle. We will select the horizontal edge of weight 8. Now all vertices have been included except the bottom left one. So we will select the edge of weight 12 to connect vertex. The total weight is 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 12 = 50. So the answer should be "none of the listed".

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


# Question
Title: Find a strategy to evade hungry lions on the real line for the longest time
This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up.

You are placed on the real line, and there also are $K$ lions on the real line, which are currently sleeping. You are given the wake up time of each lion. You can walk past a lion as long as it is sleeping. As soon as any lion wakes up, it starts walking towards you to eat you. Both you and the lions can walk at a maximum speed of 1m/s.

Given your starting position and the starting positions and wake up times of the lions, find the maximum time you can stay alive (can be infinite), and the strategy you should follow.

# Answer
Assume you start at zero. Lion #i is at $d\_i$ and wakes up at $w\_i$. If there is no lion with $d\_i \> 0$ and $w\_i \< d\_i$ then you walk to the right and are safe. If there is no lion with $d\_i \< 0$ and $w\_i \< |d\_i|$ then you walk to the left and are safe.

Otherwise, you die. There is always an optimal strategy of the form "move to some point X and stop, then wait until lions force you to move, and die when two lions from either side meet" - the point X is obviously not known. The point X is limited; if for example $d\_i \> 0$ and $w\_i \< d\_i$ then you can walk only $(d\_i + w\_i)/2$ before you are forced back.

Just check the points X that are just before a sleeping lion, or just before one of the two points where you are forced back. For each of these points X, calculate at which time you will die, and pick the best one.

(To make this easier to visualise: If all lions wake up at the same time, and you can't escape, then you want to be within the largest gap between two lions that you can reach, at the moment they wake up. So the point to move to could be anywhere, depending on where the lions are).
> 2 votes

---
Tags: algorithms, optimization
---


# Question
Title: Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it
Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the shortest path from node $u$ to node $v$ there are odd numbers of ones ( or in other words the sum of all integers on this path is odd number ).

I know that this can be solved easily by running a single DFS from each node, but this works in $O(N^2)$. I'm trying to find way to narrow it down to $O(N\log N)$ or $O(N)$. I was thinking about applying some dynamic programming, but I couldn't find the relations between the nodes.

# Answer
You can solve in linear time this using dynamic programming on trees.

Scan the tree from the leaves up toward the root, for each vertex $v$ calculating, for $b \in \\{0,1\\}$, the number of vertices $u$ below $v$ such that the $(v,u)$ path has the same parity as $b$.
> 2 votes

---
Tags: trees, counting
---


# Question
Title: Transformation of a Product Buchi Game to a Parity Game
Is there anyway to express a Product Buchi game as a parity game? There is no stochasticity in my original turn-based game and a Deterministic Buchi Automaton is constructed for LTL specifications.

# Answer
> 1 votes
I will assume that by "Product Buchi game", you mean the (synchronous) product of a deterministic Buchi automaton and some kind of plant or deterministic finite automaton that represents the rules of the game (so to speak) apart from the specification.

You then translated this product between the Buchi automaton and a deterministic automaton to a game by assigning atomic propositions (of which the actions of the two players are composed) or characters to the two players. You have a Buchi game then. Because in your question you state that you want to represent a Product Buchi game as a parity game, I will assume that you have this product Buchi game already.

Translating a Buchi game to a parity game is now easy: Let $\mathcal{F}$ be the set of accepting states/vertices/positions in the Buchi game. Then, you can replace $\mathcal{F}$ by the following coloring function (for every vertex $v$):

$$ c(v) = \begin{cases} 1 & \text{ if } v \in \mathcal{F} \\ 0 & \text{ otherwise} \end{cases} $$

This will give you a parity game in which the player who was formerly the Buchi player can ensure that the highest color visited infinitely often is odd if and only if it is able to win the Buchi game from which the parity game was translated.

If your definition of parity game reasons about the *lowest* color visited infinitely often, swap the 0 and 1 in the formula above. Likewise, add 1 to every number if the player should make sure that the highest/lowest color should be even. There are multiple definitions of parity game winning in the literature, which are however all equivalent.

---
Tags: game-theory, buchi-automata
---


# Question
Title: When to add and when to multiply to find time complexity
I am trying to learn how to determine time complexity. Sometimes, I see complexity as $\log n + \log n = 2\log n$ but sometimes I see complexity as $\log n\cdot\log n$ which is $(\log n)^2$.

Suppose I need to do two binary searches to find two different elements, in one algorithm. Is this $\log n + \log n$ time, or would it be $(\log n)^2$ time?

# Answer
> 7 votes
You add time complexities when you have something of the form: do operation $A$, then do operation $B$. This would be (time complexity of $A$) + (time complexity of $B$).

You multiply time complexities when you have something of the form: do operation $A$, $X$ times (eg. in a for loop). This would be $X \cdot $(time complexity of $A$).

If you perform two binary searches, each of which has time complexity $\log n$, the total runtime is $\log n + \log n$. You might see a runtime of $(\log n)^2$ if you had to perform $\log n$ binary searches.

# Answer
> 6 votes
Don't look for rules that you can follow. Try to understand what is actually going on and then write down the mathematics that expresses that.

You would, I hope, have no difficulty answering the following questions:

* If I have a line of $m$ bricks and a line of $n$ bricks, how many bricks do I have?
* If I want to build a wall that is $m$ bricks tall and $n$ bricks wide, how many bricks do I need?

Use the same sort of reasoning to figure out what is going on in complexity analyses.

---
Tags: algorithm-analysis
---


# Question
Title: How to calculate the number of tag, index and offset bits of different caches?
Specifically:

1) A **direct-mapped cache** with 4096 blocks/lines in which each block has 8 32-bit words. How many bits are needed for the tag and index fields, assuming a 32-bit address?

2) Same question as 1) but for **fully associative cache**?

Correct me if I'm wrong, is it:

> tag bits = address bit length - exponent of index - exponent of offset?
>
> \[Is the offset = 3 due to 2^3 = 8 or is it 5 from 2^5 = 32?\]

# Answer
> 25 votes
The question as stated is not quite answerable. A *word* has been defined to be 32-bits. We need to know whether the system is "byte-addressable" (you can access an 8-bit chunk of data) or "word-addressable" (smallest accessible chunk is 32-bits) or even "half-word addressable" (the smallest chunk of data you can access is 16-bits.) You need to know this to know what the lowest-order bit of an address is telling you.

Then you work from the bottom up. Let's assume the system is *byte* addressable.

Then each cache *block* contains 8 words\*(4 bytes/word)=32=25 bytes, so the *offset* is 5 bits.

The *index* for a direct mapped cache is the number of blocks in the cache (12 bits in this case, because 212=4096.)

Then the *tag* is all the bits that are left, as you have indicated.

As the cache gets more associative but stays the same size there are fewer index bits and more tag bits.

# Answer
> 3 votes
Your formula for tag bits is correct.

Whether the offset is three bits or five bits depends on whether the processor uses byte (octet) addressing or word addressing. Outside of DSPs, almost all recent processors use byte addressing, so it would be safe to assume byte addressing (and five offset bits).

# Answer
> 2 votes
There are no index bits in a fully associative cache. The index bits are used to uniquely identify which set the block belongs. In a fully associative cache, all blocks are essentially part of the same set.

# Answer
> 1 votes
I'm learning for the final exam of subject Computer System, I googled for a while and found this question. And this part of the question is confuse : "in which each block has 8 32-bit words". A word is 4 bytes (or 32 bits) so the question just need to be "...in which each block has 8 words"

The answer is \- Each block is 32 bytes (8 words), so we need 5 offset bits to determine which byte in each block \- Direct-mapped =\> number of sets = number of blocks = 4096 =\> we need 12 index bits to determine which set

=\> tag bit = 32 - 12 - 5 = 15

For fully associative, the number of set is 1 =\> no index bit =\> tag bit = 32 - 0 - 5 = 27

# Answer
> -1 votes
in full associate mapping index is 0 b/s like you say set = 1 so index=log of 1 in base 2 =0 set offset =log of block size of byte base 2 so use 8=2^3 or 32=2^5 tag=32-0-5=27 for direct index=2^12=12 offset=0 bit tag= 32-12-0=20

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


title: Randomly Choosing a N-Bit Prime

text:
# Question
Title: Randomly Choosing a N-Bit Prime
I've been studying some number theory, and I came across this problem:

> Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.
>
> Consider the following algorithm to choose a random n-bit prime:
>
> 1) Pick a random n-bit number $k$.
>
> 2) Run a primality test on $k.$
>
> 3) If it passes the test, output $k$; else repeat the process.
>
> Show that this algorithm will sample on average $O(n)$ random numbers before hitting a prime.

I'm guessing I need to approach this probabilistically. Let $p$ be the probability that we randomly choose a prime. Let $E$ be the expected number of random numbers to choose before hitting a prime. Then, I need to express $E$ in terms of $p$, and show that it is less than or equal to $n$, right? Since, if we sample on average $O(n)$ numbers, then the expectation $E$ should be $\le n$.

But I'm a bit stuck on how to go about doing this. Is each event of choosing a random number binomial? Either we choose a prime or we don't, and each event is independent. But the expectation of a binomial RV is $np$, which is clearly not $\le n$.

I feel like I'm going about this all wrong. What am I missing here? Am I even on the right track? Thanks for your help.

# Answer
> 2 votes
Actually you should be thinking about a geometric random variable, not a binomial RV, since you're interested in the number of times that you have to sample before you hit a prime. And each sampling event is actually a Bernoulli trial (with probability of choosing a prime $p = \Theta(1/\log {2^n}$), where $n$ is the number of bits).

And for showing that the expected value is $O(n)$, you don't need to show that it's less than $n$. You actually need to show that there are some constants $k$ and $N$ such that the expected value is less than $kn$ for all $n \ge N$.

But besides that, you're on the right track.

# Answer
> 1 votes
It doesn't follow from the Lagrange’s prime number theorem alone.

That theorem alone would still allow for example no primes between $2^n$ and $2^{n+1}$ if n is even, and accordingly more if n is odd. So if you pick an even n, the algorithm could run forever. (It won't, but it doesn't follow from this theorem).

There is a stronger theorem that with π(N) := "Number of primes ≤ N", the limit of (N / ln N / pi(N)) = 1. From this theorem it follows that for large n, there are more than $2^n / n$ primes between $2^n$ and $2^{n+1}$ (note ln = base - e), so picking a random number in this range has probability \> 1/n for picking a prime.

Let E be the expected number of attempts. You either find a prime in the first attempt, or within 1+E attempts. E = (1/n) + (1 - 1/n)(1+E), or E = (1/n) + 1+E - 1/n - E/n, or E/n = (1/n) + 1 - 1/n or E = n.

---
Tags: number-theory, probabilistic-algorithms, primes
---


# Question
Title: How to solve $T(n) = 3 T(n-1) + 10 T(n-2) + 7 \cdot 5 ^ n$?
Consider the recurrence $$ T(n) = 3 T(n-1) + 10 T(n-2) + 7 \cdot 5 ^ n, $$ with base cases $T(0) = 4$ and $T(1) = 3$.

How do I solve such a recurrence?

# Answer
> 0 votes
Let $S(n) = T(n)/5^n$. Then $S(0) = 4$, $S(1) = 3/5$, and $$ S(n) = \frac{3}{5}S(n-1) + \frac{2}{5}S(n-2) + 7. $$ Let $R(n) = S(n) - 5n$. Then $R(0) = 4$, $R(1) = -22/5$, and $$ R(n) = S(n) - 5n = \frac{3}{5}R(n-1) + 3(n-1) + \frac{2}{5}R(n-2) + 2(n-2) + 7 - 5n = \\\frac{3}{5} R(n-1) + \frac{2}{5} R(n-2). $$ We've reached a recurrence that we know how to solve. First, we need to find the roots of $x^2-(3/5)x-(2/5) = (x-1)(x+2/5)$. This shows that $$ R(n) = A + \left(-\frac{2}{5}\right)^n B. $$ Substituting the values of $R(0)$ and $R(1)$, we get $A+B = 4$ and $A-(2/5)B = -22/5$, and so $A = -2$ and $B = 6$. We conclude that $$ T(n) = \left(6\left(-\frac{2}{5}\right)^n+5n-2\right)5^n = 5^{n+1}n - 2\cdot 5^n + 6(-2)^n. $$

---
Tags: recurrence-relation
---


# Question
Title: Shannon Entropy of 0.922, 3 Distinct Values
Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.

Taken from the introduction on this wikipedia page:

https://en.wikipedia.org/wiki/Entropy\_%28information\_theory%29

So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?

Thank you in advance.

# Answer
> 16 votes
The entropy you've calculated isn't really for the specific string but, rather, for a random source of symbols that generates $A$ with probability $\tfrac{8}{10}$, and $B$ and $C$ with probability $\tfrac1{10}$ each, with no correlation between successive symbols. The calculated entropy for this distribution, $0.922$ means that you can't represent strings generated from this distribution using less than $0.922$ bits per character, on average.

It might be quite hard to develop a code that will achieve this rate.* For example, Huffman coding would allocate codes $0$, $10$ and $11$ to $A$, $B$ and $C$, respectively, for an average of $1.2$ bits per character. That's quite far from the entropy, though still a good deal better than the naive encoding of two bits per character. Any attempt at a better coding will probably exploit the fact that even a run of ten consecutive $A$s is more likely (probability $0.107$) than a single $B$.

---

* Turns out that it isn't hard to get as close as you want – see the other answers!

# Answer
> 18 votes
Here is a concrete encoding that can represent each symbol in less than 1 bit on average:

First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111. I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.

This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).

The average number of bits per symbol pair for the above encoding is $$\frac{8}{10} \cdot \frac{8}{10} \cdot 1 + 3 \cdot \frac{8}{10} \cdot \frac{1}{10} \cdot 3 + \frac{1}{10} \cdot \frac{8}{10} \cdot 4 + 4 \cdot \frac{1}{10} \cdot \frac{1}{10} \cdot 6 = 1.92$$ i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.

# Answer
> 13 votes
Let $\mathcal{D}$ be the following distribution over $\\{A,B,C\\}$: if $X \sim \mathcal{D}$ then $\Pr\[X=A\] = 4/5$ and $\Pr\[X=B\]=\Pr\[X=C\]=1/10$.

For each $n$ we can construct prefix codes $C\_n\colon \\{A,B,C\\}^n \to \\{0,1\\}^\*$ such that $$ \lim\_{n\to\infty} \frac{\operatorname\*{\mathbb{E}}\_{X\_1,\ldots,X\_n \sim \mathcal{D}}\[C\_n(X\_1,\ldots,X\_n)\]}{n} = H(\mathcal{D}). $$

In words, if we encode a large number of independent samples from $\mathcal{D}$, then on average we need $H(\mathcal{D}) \approx 0.922$ bits per sample. Intuitively, the reason we can do with less than one bit is that each individual sample is quite likely to be $A$.

This is the real meaning of entropy, and it shows that computing the "entropy" of a string $A^8BC$ is a rather pointless exercise.

---
Tags: information-theory, mathematical-foundations, entropy, binary
---


# Question
Title: Checking Divisibility Using Minimal Bits
> Suppose we're given an infinite stream of integers, $x\_1, x\_2, \dots$.
>
> a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log N)$ bits of memory.
>
> b) Let $N$ be an arbitrary number, and suppose we're given $N$'s prime factorization: $N = p\_1 ^{k\_1} p\_2 ^{k\_2} \dots p\_r ^{k\_r}$. How would you check whether $N$ divides the product of all integers $x\_i$ seen so far, using as few bits of memory as possible? Write down the number of bits used in terms of $k\_1, ..., k\_r$.

For part a), we know that for any prime $p \ne 2, 5$, there is an integer $r$ such that in order to see if $p$ divides a decimal number $n$, we break $n$ into $r$-tuples of decimal digits, add up these $r$-tuples, and check if the sum is divisible by $p$. But $N$ is a fixed integer, and not necessarily a prime. Is there some way to connect the theorem above to any arbitrary integer?

For part b), for the product of $x\_i$ (call it $y$) is divisible by $N$, then $y$ must be divisible by each $p\_i ^{k\_i}$ (call it $a\_i$. Since we're given the prime factorization, we can just check if $y$ is divisible by $N$ by dividing $y$ by each $a\_i$ and halting when it fails, right? Would this result in using $k\_1 \times \dots \times k\_r$ bits?

Am I at least on the right track, or am I completely wrong? Any help understanding this problem would be tremendously helpful.

# Answer
For part (a), the idea is that it suffices to store the sum of all integers seen so far modulo $N$. Since this is an integer between $0$ and $N-1$, storing it requires only $\lceil \log\_2 N \rceil$ bits.

For part (b), let $x\_i = p\_1^{a\_1(i)} \cdots p\_r^{a\_r(i)} q$, where $q$ is relatively prime to $p\_1,\ldots,p\_r$. Then $x\_1 \cdots x\_m$ is divisible by $N$ iff $a\_j(1) + \cdots + a\_j(m)\geq k\_j$ for $j=1,\ldots,r$. Hence it suffices to store $\min(a\_j(1)+\cdots+a\_j(m),k\_j)$ for $j=1,\ldots,r$. The $j$th number is between $0$ to $k\_j+1$, and so requires $\lceil \log\_2 (k\_j+1) \rceil$ bits, for a total of $$ \sum\_{j=1}^r \lceil \log\_2(k\_j+1) \rceil \text{ bits}. $$ (In fact, we can be a little bit smarter and use only $\left\lceil \sum\_{j=1}^r \log\_2(k\_j+1)\right\rceil$ bits, but it's not such a big difference.)

In both cases, it is possible to show that the amount of bits stated is also required. For example, in part (a), at any given point in time you need to distinguish between $N$ different states, correspond to the current sum modulo $N$. Indeed, all sequences $0;1;\cdots;N-1$ must lead to different memory states, since if $i$ and $j$ led to the same state, then we would not be able to distinguish between the sequences $i,N-i$ and $j,N-i$, although one of them satisfies the divisibility property and the other doesn't.
> 1 votes

---
Tags: number-theory, modular-arithmetic
---


# Question
Title: Is there a name for this graph search strategy?
The standard implementation of breadth-first search looks like

```
queue = [root]
while queue:
    node = queue.pop()
    visit(node)
    for_each child in node.children:
        queue.push(child)

```

Just by switching the queue to a stack:

```
stack = [root]
while stack:
    node = stack.pop()
    visit(node)
    for_each child in node.children:
        stack.push(child)

```

we get depth-first search.

There is another way to write breadth-first search:

```
visit(root)
queue = [root]
while queue:
    node = queue.pop()
    for_each child in node.children:
        visit(child)
        queue.push(child)

```

But when you switch this one from a queue to a stack:

```
visit(root)
stack = [root]
while stack:
    node = stack.pop()
    for_each child in node.children:
        visit(child)
        stack.push(child)

```

You do not get a traditional depth-first search. Instead, you get a variant where all a node's immediate children are visited first, then its other ancestors in a depth-first way. For example, on this tree:

```
     F
   /   \
  B     G
 / \     \
A   D     I
   / \   /
  C   E H

```

Depth-first search gives the order

> \[F, G, I, H, B, D, E, C, A\]

The last algorithm gives the order

> \[F, B, G, I, H, A, D, C, E\]

which is not exactly depth-first because B and G are both visited before I. Does this algorithm have a name?

# Answer
*Summary: We can name it (a variant of) **preorder children-together depth-first traversal**.* No particular name or usage for this search algorithm has been found in existing literature yet.

---

The words "search" and "traversal" are often used interchangeably. In strict sense, this is a traversal algorithm but not a search algorithm (binary search algorithm is a proper search algorithm) since it is not actually searching for any element. Any traversal algorithm can be used for searching naturally, though, which is why we see depth-first search and breadth-first search often.

## Description of this algorithm

**Firstly, it visits a parent before its children** and, hence, before all its descendants)

This property can be considered as the naturalness of a tree traversal algorithm since a parent comes before its children conceptually and historically. Or we can reuse the more conventional term, "preorder" to describe it.

**Secondly, it visits children together,** but not grandchildren together in general.

Given any node, once it starts traversing its children, it will visit all of its children before any of its further descendants such as grandchildren, great-grandchildren, etc. In other words, all children of any given node will be visited consecutively, in some order which can be specified as, for example, from left child to right child (or some random order).

**Thirdly, it is mostly depth-first.** After visiting any node, it visits all of its descendants together.

Given any node, once this algorithm begins visiting any of its descendants, it will visit all of its descendants before visiting any node that is not its descendant. It goes deeper and deeper down the descendants towards the leaves, until it reaches the leaves, at which time it will backtrack.

**Fourthly, it is not the standard depth-first traversal (SDFS).**

For any two siblings nodes $s\_1$ and $s\_2$, if SDFS visits $s\_1$ before $s\_2$, then it visits all descendants of $s\_1$ before all descendant of $s\_2$ as well as $s\_2$ itself. In others words, for any two disjoint subtrees $t\_1$ and $t\_2$, SDFS will either visit $t\_1$ completely before $t\_2$ or visit $t\_2$ completely before $t\_1$. However, for this traversal algorithm, if it visit $s\_1$ before $s\_2$, then it will visit all descendants of $s\_1$ after it has visited the subtree at $s\_2$.

This fourth point is also implied by the second point.

So this algorithm can be called **a variant of preorder children-together depth-first traversal**.

## Why do we say "a variant of"?

The following algorithm is the algorithm that should be called **the** preorder children-together depth-first traversal, as it is more natural in the sense that all immediate or distant siblings are visited from left to right, in the same order as children of the same node is visited. In other words, all nodes in the same level are visited from left to right, although not consecutively in general.

```
myStack = [root]  // myStack is a stack.
while myStack:
    node = myStack.pop()
    for child in node.children: // assuming left to right
        visit(node)
    for child in node.children.reverse: // pushing children in reverse order
        myStack.push(child)

```

The output of above algorithm on the graph in the question is

> F B G A D C E I H

Note that nodes in each level is always visited left to right as \[F\], \[B,G\], \[A,D,I\] and \[C, E, H\]. This algorithm is also more natural in the sense that can be defined recursively naturally as the following pseudocode in Python style

```
def traversal(tree, node):
   for child in tree.getChildren(node):
     visit(child)
   for child in tree.getChildren(node):
     traversal(tree, child)

```

To traverse a tree T rooted at R, call it as `visit(R); traversal(T, R)`.

---

We can generalize this algorithm so that all $k$-level descendants are visited together. For example, we can have a preorder grandchildren-together depth-first traversal, which may output `F B G A D I C E H` for the given graph. There are several variations to them, which will not be discussion here.

## Tree or general graph

Please note all search strategies mentioned above and in the question can be adapted slightly so as to be applied to general undirected graphs instead of rooted trees. All we need are the following changes. (More adaptation is needed for general directed graphs.)

* Select an arbitrary node as the root.
* Initialize a boolean array to record whether a node has been visited or not.
* Mark a node as visited right after it has been visited.
* Skip pushing any visited node to the stack or queue.

## Two simple exercises

**Exercise 1**. Write the algorithm in the question as a recursive function/method in pseudocode or your favorite language.

**Exercise 2**. Suppose every parent should be visited after all its descendants. Implement that variation in pseudocode or your favorite language. Show its output for the given graph.
> 1 votes

# Answer
I don't think it has any standard name, but you might arguably call it a depth-first search with one level of lookahead.
> 2 votes

---
Tags: graphs, trees, graph-traversal
---


# Question
Title: Finding time complexity when while loop included
There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays.

Example 1:

nums1 = \[1, 3\] nums2 = \[2\]

The median is 2.0

Example 2: nums1 = \[1, 2\] nums2 = \[3, 4\]

The median is (2 + 3)/2 = 2.5

Here is my solution:

```
//Find out the median of two sorted array
public class Median {
public static void main(String args[]){
    int arr1[]={1,2,6};
    int arr2[]={3,5,7};

    int temp[]=new int[(arr1.length)+(arr2.length)];
    int k=0,i=0,j=0,mid=0,k2=0;

    while(i< arr1.length && j<arr2.length) {
        if (arr1[i] < arr2[j]) {
            temp[k] = arr1[i];
            i++;
        } else {
            temp[k] = arr2[j];
            j++;
        }
        k++;
    }
    while (i < arr1.length) {
        temp[k++] = arr1[i++];
    }
    while (j < arr2.length) {
        temp[k++] = arr2[j++];
    }

    int a= temp.length;
    if(a%2==0){
        k2=(temp.length)/2;
        mid = (temp[k2]+temp[k2-1])/2;
    }
    else{
       int k1=(int)(temp.length)/2;
        mid=temp[k1];
    }
    System.out.println("The median of two sorted array is "+mid);
}
}

```

I want to know that what is the time complexity of my code? Is there any better way to solve this?

I know how to find out the time complexity if there is for loop. But if there is while loop then how could I find out the time complexity?

# Answer
> 0 votes
Let’s say two arrays have a million elements each. A \[500,000\] = 3,516 and B \[500,000\] = 12,920. Can you say anything about the median? Is there anything you can do with this information to save a lot of work? What if A\[750,000\] = 11,416?

Your code takes O(n+m) both in time and space. This can be done in O(ln n + ln m).

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Need Help Understanding MST Cutset Formulation
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).

This is the definition:

> An *integer* linear program that solves the minimum spanning tree problem is as follows:
>
> $$ \begin{align\*} \text{Minimize} & \sum\_{\\{u,v\\} \in E} w\_{u,v}x\_{u,v} \\ \text{subject to} & \sum\_{\substack{\\{u,v\\} \in E\colon \\ u \in S, v \notin S}} x\_{u,v} \geq 1 & \text{for all $S \subseteq V$ with $0 \< |S| \< |V|$} \\ & \sum\_{\\{u,v\\} \in E} x\_{u,v} \leq |V|-1 \\ & x\_{u,v} \in \\{0,1\\} & \text{for all $\\{u,v\\} \in E$} \end{align\*} $$

$x\_{ij}$ is defined to be $1$ if the edge $ij$ is in $T$.

What exactly does the optimum value represent here? Is it the number of edges that are used in our MST? If so, how does knowing the number of edges help us in forming the MST?

How does this ILP "work" to solve the MST problem?

# Answer
The first constraint makes sure the induced subgraph remains connected : there must be an edge between every pair of subsets of $V$ ; or in terms of graph theory, *for every cut, at least one edge must cross the cut*. For example, if $S=\\{a\\}$, the constraint is $$ \sum\_{(u,a)|u\neq a} x\_{ua} \ge 1 $$ and this imposes that $a$ does not end up alone.

The second constraint makes sure you end up with $n-1$ edges, which is a characteristic of a tree.
> 3 votes

# Answer
The objective value of the integer program is the total weight of edges in the tree.

Here is how this integer program works:

1. The constraint $x\_{uv} \in \\{0,1\\}$ allows us to consider the set $T = \\{ uv : x\_{uv} = 1 \\}$.
2. The first constraint states that $T$ crosses every cut in the graph.
3. The second constraint guarantees that $T$ contains at most $|V|-1$ vertices.
4. The objective function is the total weight of edges in $T$.
> 1 votes

# Answer
Yuval has explained why and how that program by integer linear programming works.

I would like to point out that **a simpler version of that program** in the following. Please note, as usual and as in the question, we assume the graph is a connected graph.

> $$ \begin{aligned} \text{Minimize} &\sum\_{\\{u,v\\} \in E} w\_{u,v}x\_{u,v} \\ \text{subject to} &\sum\_{\substack{\\{u,v\\} \in E\colon \\ u \in S, v \notin S}} x\_{u,v} = 1 & \text{ for all } S \subseteq V \text{ with } 0 \< |S| \< |V| \\ & x\_{u,v} \in \\{0,1\\} & \text{ for all } \\{u,v\\} \in E \end{aligned} $$

Here is a brief explanation why the above simpler program is correct.

1. The last constraint, $x\_{u,v} \in \\{0,1\\} \text{ for all } \\{u,v\\} \in E$ indicates whether the edge $\\{u,v\\}$ is included or not. 1 means inclusion and 0 means exclusion.
2. The first constraint requires that for any given cut of the graph, the set of included edges must contain an edge that crosses that cut. That is, it must be a connected spanning subgraph. Since it never has more than one edge to cross the same cut, it does not contain a cycle. So it is actually a spanning tree. That is why we can do away with the second to last constraint in the original program.
3. The objective function is the total weight of included edges, which is a spanning tree. Since we want to minimize that objective function, we will find the minimum spanning tree.
> 1 votes

---
Tags: graphs, linear-programming, integer-programming, minimum-spanning-tree
---


# Question
Title: Modification of dynamic programming for a knapsack problem
We have the following recursive function for the dynamic programming problem for a knapsack problem:

\begin{align} V(i,w)=&max\[ V(i-1,w), v\_i +V(i-1,w-w\_i)\], \quad 1\leq i \leq n, 0\leq w \leq W \\ \end{align} and $V(0,w)=0$.

But is it possible to add a constraint on the items to this function? If we for instance only are allowed to put one of the items 1 or 2 in: $x\_1 + x\_2 \leq 1$? And how to do this?

# Answer
Apply the golden rule of DP (that is how I name it), namely, adding another parameter to the subproblems/object function when there is an extra condition or dimension of freedom. This rule is simple and powerful, yet it can be overlooked by DP beginners and sometimes experienced guys.

In this particular question, instead of $V(i,w)$, define $V(i,w,c)$, where $V(i,w,0)$ means no item 1 and no item 2, $V(i,w,1)$ means one item, and $V(i,w,2)$ means one item 2. Rewrite the recurrence relation accordingly. Compute the values either recursively or iteratively with memoization. Select the desired result among possible candidates.

This answer can be seen as a formalization of @fade2black's answer, although I had/have been calling/using the golden rules too many times in my DP adventure.
> 2 votes

# Answer
One possible way is to call the the DP algorithm first without the item 1 and then without the item 2. The maximum one is the optimal solution.
> 0 votes

# Answer
No, if you want to allow an arbitrary number of those constraints. The constraints that you would like to add make the problem strongly NP-hard, because they can encode the independent set problem. In particular, your problem with constraints cannot have a pseudo-polynomial time algorithm (unless P = NP).
> 0 votes

---
Tags: optimization, dynamic-programming, knapsack-problems, integer-programming
---


# Question
Title: Would memoization make any improvement to Strassen's algorithm?
Could the run-time of the Strassen's algorithm be improved by adding Memoization to it?

# Answer
> 5 votes
I don't get why the other answerers don't even make an attempt to reason along the lines the question has been asked. If anything, they should explain why memoization can or cannot work.

In any case, let's think about how we can can approach memoization in the Strassen's algorithm. We know that it involves dividing our matrix into four equal quarters, calculating products of individual submatrices and combining them through addition with the following complexity:

$T(N) = 7T(N/2) + O(N^2)$

The one place where we can apply memoization is in the product of the submatrices stage. Each time we encounter two submatrices that need to be multiplied, we can store the result hoping that we encounter the same submatrices again and don't have to recompute the product. This will take up a lot of memory of the order of $O(N^2)$ for each saved product.

That brings us to the next question - How many products are going to be there? We will be having one $N^2$ matrix in the outermost call, $7(\frac{N}{2})^2$ matrices in the next call, $49(\frac{N}{4})^2$ matrices in the subsequent call and so on until $7^{(log N)}$ individual products. You will notice that we're using more and more memory as the recursion depth increases. (The memory requirement will be greater than $O(N^2)$)

Although the memory size is large, what is really important for us is to locate a given matrix from the set of stored matrices. Naively, this would take $O(number\\\_of\\\_products \cdot N^2)$ time for iterating through all of the products computed so far. We can probably make it faster by passing the input matrices through a hash function and mapping the hash value to the matrix. This can be done in $O(N^2)$ for the right choice of hash function, and $O(1)$ for a map based lookup.

How will this affect our complexity? We now do an additional lookup before computing the product, and save the product right after as well. $T(N) = O(N^2) + 7T(N/2) + O(N^2) + O(N^2)$. This is equivalent to our original complexity.

This shows us that asymptotically, we don't do worse in terms of time complexity although the space complexity shoots up.

Will it actually speed things up? It really depends on how often we will have repeating submatrices that we need to recompute. I do not think that in any practical scenario (especially if we are dealing with floating point operands), we will see the same sets of submatrices too many times. But this is an intuition. If I were you, I'd try it out and empirically find out if it helps.

# Answer
> 3 votes
No. Memoization isn't some magical keyword you can apply to anything to make it faster.

# Answer
> 2 votes
Nope, We generally use memoization for **Dynamic Programming** strategy(where we can speed up our programs by storing the results of expensive recursive calls and returning the cached result when the same inputs occur again). Whereas, **Strassen's** algorithm is a **Divide and Conquer** strategy.

---
Tags: algorithms
---


# Question
Title: Behaviour of Dijkstra in Case of Negative Edge Weight
I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.

For the given below graph

What should be the Cost to reach Node G from Source Vertex A?

I was getting 2, as vertex E is the last processed vertex and when it was being processed

$E.d=9,(E,G)=-7$ so $G.d=2$ changed.

Some implementation of Dijkstra says that once a vertex v has been relaxed, then it's estimated $v.d$ is never changed.

Like here

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Here $v.d$ is changed only when sptSet\[v\] for that vertex is false, means that vertex was not processed before.

But CLRS says that for each vertex U that belongs to queue and results from U=EXTRACT\_MIN(Q), we relax all edges leaving U.

So, If I follow the implementation of Dijsktra of what is given in CLRS, I get cost of 2 to reach node G from source Vertex A.

Please guide what should be correct.I am really confused about it.

# Answer
The article on Dijkstra's algorithm at GeekForGeeks say "Dijkstra’s algorithm doesn’t work for graphs with negative weight edges in general."

*Introduction to Algorithms* by Corman et al. says "Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph for the case in which all edge weights are nonnegative."

As explained in the linked question and answer and as OP has found, the general proof of the correctness of Dijkstra's algorithm will fail if there are negative edges, hence discussing Dijkstra on graphs with negative weight edges doesn't make sense.

I would advise you to stay away from Dijkstra’s algorithm when a graph that has negative weights appears. It might work in some cases, but it may lead you into troubles that will be avoided if you apply Bellman–Ford algorithm or Floyd–Warshall algorithm.

By the way, the shortest distance from $A$ to $G$ is 2.
> 0 votes

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


# Question
Title: Is this a correct grammar for untyped lambda calculus?
I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this:

```
without left-recursion:
TERM         -> APPLICATION | ABSTRACTION
ABSTRACTION  -> LAMBDA LCID DOT TERM
APPLICATION  -> ATOM APPLICATION'
APPLICATION' -> ATOM APPLICATION' | ε
ATOM         -> LPAREN TERM RPAREN | LCID
LCID         -> 'a' | 'b' | ... | 'z'
DOT          -> '.'
LAMBDA       -> 'λ'

```

I assume that for writing the parser I do not necessarily need the productions that only expand into terminals.

Can this grammar be used to write a recursive descent parser that only does 1-token lookups? What would be the resulting AST for `(λx.x)(λy.y)` ?

# Answer
> 0 votes
Your grammar looks fine. You can make a recursive descent parser for it.

The AST for `(\x.x)(\y.y)` is, if I got everything right,

```
term
  application
    atom
      lparen
      term
        abstraction
          lambda
          lcid
            x
          dot
          term
            application
              atom
                lcid
                  x
              application'
                eps
      rparen
    application'
      atom
        lparen
        term
          abstraction
            lambda
            lcid
              x
            dot
            term
              application
                atom
                  lcid
                    y
                application'
                  eps
        rparen
      application'
        eps

```

---
Tags: formal-grammars, lambda-calculus, parsers
---


# Question
Title: Find Hamiltonian cycle in polynomial time
I want to know for what types of graph it is possible to find Hamiltonian cycle in polynomial time. It would be helpful also to show why on some types of graph finding Hamiltonian cycle would be only possible in exponential time.

# Answer
> 1 votes
Perhaps the most comprehensive list is available via ISGCI, along with references. Examples for which the problem is easy include bounded treewidth graphs and many subclasses of chordal graphs.

As to why exponential time seems unavoidable in general, we don't strictly know. As far as we know, P = NP is also possible.

---
Tags: time-complexity, polynomial-time, hamiltonian-circuit
---


# Question
Title: Undecidable problems limit physical theories
Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual circuit based construction. Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt. This seems a triviality, but doesn’t this give us a weak sort of unpredictability without reference to quantum or chaotic considerations? Moreover we can strengthen the above argument by noting that there is nothing special about the circuit based UTM, so we have that the behavior of a physical system is in general undecidable at any level where a UTM can be constructed.

Edit: as pointed out by both Babou and Ben Crowell, my suggested circuit construction is merely an LBA. As I argued in the comments, I find it easy, and intuitive to imagine a machine which is physical but is not linearly bounded. Simply construct a machine (robot) which can mechanically move left/right on an input arbitrarily many times, and assume it has a finite, but non expiring power source. Now we also run into the problem that the universe is finite, but that lets us conclude either that the universe is finite, or the originally hoped for consequence must be true (that would still be a surprising conclusion to arrive at from the above argument).

# Answer
This was initially intended as a comment, as it side-steps a bit the question. But I think it does answer in its own way.

What is known, or attempted so far, shows that connecting computation theory with physics can be a pretty subtle endeavour, and I am afraid that the approach suggested in the question is probably a bit too crude. I am not sure it is much better than the classical argument that, everything being finite, all we need is finite state automata theory, and that studying Turing machines is a waste of time. (Not my view of things)

## Why should such issues be addressed with caution

I should probably motivate the above comparison with the finite automata argument. My perception is that computability is, maybe even more than complexity, an asymptotic theory: what matters is what occurs at infinity. But we do not know whether the universe is finite or infinite. If it is finite, then what would be the point of considering infinite computations. The following concerns physics, and *I am not a physicist. I do my best to be accurate, but you have been warned*.

We often see the Big Bang as a "time" when the whole universe was a very tiny something, with a very small size. But if it had a size at some point, how did it transform into something infinite at a later time. I am not trying to say it is impossible ... I do not have the slightest idea. But it could be that it always was infinite.

Then, let us consider the universe as infinite. Does it help us? Well, we have some problems with the speed of light. If we consider what may be relevant here (where we are), we have to consider that we can be concerned only by a part of the universe that is included in a finite sphere. The radius $r$ of that sphere is such that the relative speed of two points at distance $r$ due to expansion is equal to the speed of light. According to what we currently know, without a future variation in expansion speed, nothing outside that sphere will ever be of concern to us. So the universe is finite for us for all practical purposes. Actually, things are even worse if you consider the contents of this relevant universe: it is shrinking (unless there is some creation process). The reason is that the sphere is expanding beyond its own diameter, carrying with it some of its content that becomes irrelevant too. Remark: that sphere is not what is called the observable universe (which is dependent on the age of the universe), it is much larger.

Thus, not only "our" universe is finite, but its resources might be shrinking. It is possible that in so many billions years, only our galaxy might be still relevant to us (assuming we still exist), with the Andromeda galaxy which will hit the Milky Way before then.

Well, I do not know what is considered established at this time, but it shows at least that assuming infinity is a big assumption.

However, is it the case that physical limitations prevent us from using computability theory. All that can be concluded from the above is that it may be unreasonable to draw physical conclusions from the theoretical work on Turing Machines and the halting problem.

However the concerned techniques may also give useful results when applied to devices or formalisms that are not Turing-complete. I would not try to go into details, if only because algorithmic complexity is not my area, but I would guess that, if the structure of the universe is discrete, complexity could be in some form relevant to the behavior of some phenomena. Of couse, this is only wild speculation on my part. Some of the research I reference below is related to such discreteness issues.

## Some examples of work relating physics and computation theory

There is a significant body of work trying to tie computation and physics, most of which I barely know of. *So, please, do not rely on anything I might say*, but simply take it as pointers to search for potentially relevant work.

A good part of that work is concerned with thermodynamic aspects, such as the possibility of reversible computing with no energy cost. I thinks this ties with functional programming as it is side-effects that cost energy (but do not trust me). You may take wikipedia as an introduction, but Google will yield many references.

There is also work trying to tie Church-Turing thesis and physics, involving information density among other things. See for example:

I vaguely recall seen other interesting takes on this, but it escapes me right-now.

Then you have Lamport's work on clocks synchronization and relativity in distributed systems.

And, of course, you have quantum computing that apparently changes some (achievable) time-complexities, though it does not affect computability.

Another take is Wolfram's work on modelling physical laws with cellular automata, though the real benefits of this work seem disputed.

I think that trying to understand all this work could get you closer to understanding how you can tie some computability knowledge with (as implying) theoretical limitations of the physical world, though the trend so far was more to tie limitations of computability to (as consequences of) properties of the physical universe.

One possible problem in all this is the self-embedding of all our theories (mathematics, computation, physics, ...) within the limits of concepts that are syntactically expressible (i.e. by a language) which might set a limit on the expressive power of our science. But I am not sure whether the preceding sentence has meaning ... sorry about that, it is the best I can do to express one nagging doubt.

As an account of personal disappointment, I would add that physicists (at least on http://physics.stackexchange.com) are not very amicable to discussing what other sciences could have to say about physical issues (though they are quite willing to discuss what physics may have to say about other sciences).
> 7 votes

# Answer
Babou,

It's indeed a very interesting question but as said above a lot of literature has been produced on the subject. The least you can say once you have read all that is that mapping UTM to physical systems is far from straightforward - however seducing the idea is.

Personally I like to start from the concept of reversible computing introduced by Landauer and mentioned in the previous answers. **There seems to be a conceptual connection between entropy and UTM.**

Think about it this way: imagine you want to walk from point A to point B (geographically distinct) using a deterministic plan (i.e. a number of steps which can be written down in advance like a UTM: walk straight for 100m, turn right at the bakery, walk 50m etc.). You can walk the distance once. Twice. Three times. How many times can you do it? Unless you include an infinite stock of food and water in your plan, you'll have to stop after a finite number of journeys. But although a UTM tape is infinite, the number of steps of the TM itself has to be written in a finite number of characters. Therefore your plan cannot include an infinite amount of food and water.

Now energy is a conservative quantity. So you could think a finite amount of provisions should suffice. But clearly this is not your issue here. Even if you travel very slowly between A and B, your body will turn your food into something you cannot consume anymore. Note that if you try to escape that issue and go INFINITELY slowly (quasi-statically between A and B) you cannot write your "plan" with a finite number of characters anymore. **So it's the increase of thermodynamic entropy (degradation of food and water through the processing of your body) which seems to pose a limit to the number of journeys you can make while sticking to a deterministic plan (i.e. a UTM).**

**If this is right, the unpredictability of TM has to be mapped to the increase of thermodynamic entropy.** Note how this seems quite counter-intuitive (as said before that sort of mapping is far from trivial): to infinity the increase of thermodynamic entropy leads to an equilibrium i.e. something stable; but the same infinite limit of the corresponding UTM leads to a random behavior (i.e. we are not sure what sort of output). That's even more striking with a ball rolling down a convex curve with frictions: thermodynamic entropy makes the ball stop at the low ebb of the curve which is something quite easy to predict; but the equivalent UTM will tell you that "something random" happens in the end which cannot be predicted. Is it that we have to map that unpredictability to the random motion of atoms created by the heat dissipation of the movement of the ball against the surface of the curve? That's an open question but at least it shows you the difficulty.

Hope that helps!
> 1 votes

# Answer
The question asks in part about *nonpredictability of physical systems*. Undecidability does show up in a few physics problems. An early survey by this is by Wolfram, Undecidability and Intractability in Theoretical Physics (or here) and this area continues to expand. However, a better way to understand physical inherent unpredictability is more via what is known as "sensitive dependence on initial conditions" aka butterfly effect. This can be studied using the Lorentz attractor as a semi-toy model.
> 0 votes

# Answer
The question is interesting (you may want to check a related question "Is there a connection between the halting problem and thermodynamic entropy?")

The core of the problem is what comes first mathematics or physics? Well **physics is the answer**. A quote by Einstein says: "*the kind of mathematics we do, depends on the world we live*" (if i'm not mistaken this is in "Einstein, Philosopher-Scientist") (and another related, and slightly paraphrased "*Nature does not care about our mathematical difficulties. It integrates empirically*"). So in this sense certain physical features are reflected in the mathematical symbolism and procedure. But one can also take the opposite view that mathematics defines physics (a view that is quite popular in certain circles).

There is a passage in the introduction of the book "Linear Algebra" by J B. Fraleigh, R A. Beauregard (a good book on the subject and a point i wanted to address given the opportunity)

> Numbers exist only in our minds. There is no physical entity that is number 1. If there were, 1 would be in a place of honor in some great museum of science, and past it would file a steady stream of mathematicians gazing at 1 in wonder and awe.

Yet this **is not true**, there **is indeed** something which we experience and is **one (literaly)**, the **sun** (careful not the stars at night nor the moon which is not perceived as one under all circumstances, the sun, the one and only visible thing in the sky in daylight). (and indeed it has been historicaly an object of honor and awe from the humankind). One can go on and discuss other things which we experience as *two* or *three* and *four* (*two* hands, *five* fingers and so on), but the main point has been given (for more information search for "*pre-history and history of number systems*")

Say for a minute that a mathematical result would state something but then a physical theory would provide a procedure to achieve the opposite (effectively a constructive proof of the opposite). Then something would be wrong, these are related especialy when they use the exact same formalism. It is intuitive that these should be related somehow.

For example an mathematical imposibility result would limit the mathematical description of a physical theory that would need such a result and so on. An example that i can use right now is the so-called "theory of everything". It is supposed to describe in mathematical form all the physical interactions that take place, so in effect describe everything. However by Goedel's theorem it is known that such a description would be incomplete in one sense or another. Does this say something about the world we live? Most probably.

But **imposibility results are known in purely physical terms** and most of them are related to thermodynamics. For example "Heat flows from hot to cold". This is an imposibility result. But this also **limits any mathematical result** which would imply (when applied in the proper context) that *heat flows from cold to hot*, this does not happen. So **mathematics can be limited by physical terms**. The real question is what is the exact connection (if any) between these two and this is a very interesting question with interesting anf far-reaching results. For example you can check the work of G. Chaitin which relates information theory, Goedel's theorems and bio-physical systems for a start. Some other connections have been already mentioned like reversible computing, quantum computing and so on.

Last but not least remember that **physics relies on experiment to formulate and verify things and not symbolic proofs**. (A) Mathematical description of a physical theory is important in terms of calculations, so a problematic mathematics *may* limit or otherwise pose problems in the calculation power of the theory, experiment remains nevertheless. And remember that physicists are usualy among the **creators of new mathematics** as needed (e.g Calculus and Differential Equations, Probabilities, Tensor analysis, Renormalisation procedure in quantum mechanics, Analytic regularisation and so on)

As regards your example connecting un-predictability with a TM, the connection can be done and it might require an unbounded tape provided the machine will need to calculate with infinite precision (i.e irrational/transcendental numbers which are in no-way excluded from a physical system). Then an LBA machine will not be powerful enough to calculate a given physical system and one enters the infinite tape UTM which has a halting problem. The question whether unpredictatibility can be attributed to initial conditions (the taught formal definition of chaotic behaviour) or the computation itself is not of the essence since it only shifts the problem to another place instead of addresing it.
> 0 votes

# Answer
I think a good model for this is Conway's game of life.

Since we invented the rules, we know them perfectly. This is analogous to a physical theory.

Yet, despite how simple the rules are, and the fact that we know them, life is undecidable.

Similarly, even if we learned all the laws of physics, it could turn out they are undecidable as well.

There is not really anything you can do about it. One thing to keep in mind though is that you can predict Conway's game of life for any *finite number of steps*. This might turn out to be the same for physics.
> 0 votes

---
Tags: computability, turing-machines, undecidability, physics
---


title: FSA for $(ab)^*(cb^n)^*$

text:
# Question
Title: FSA for $(ab)^*(cb^n)^*$
> How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^\*(cb^n)^\*$, where $n\ge1$?

An automaton can easily be drawn for the part $(ab)^\*$, but the part $(cb^n)^\*$ doesn't seem to be regular because if the Kleene closure is taken $\ge2$ times, then it will be of the form $(cb^n)(cb^n)$, which reduces to string matching and is context-sensitive.

This was actually a question, solution to which said that the above language has the following regular expression: $(ab)^\*(cbb^\*)^\*$.

# Answer
> 0 votes
For the correct/sensible interpretation, $(ab)^\*(cbb^\*)^\*$, I will list the states and its corresponding regular expressions below; you can figure out the transitions between the states.

$q\_{0}$: $(ab)^\*$, start state
$q\_{1}$: $(ab)^\*a$
$q\_{2}$: $(ab)^\*(cbb^\*)^\*c$
$q\_{3}$: $(ab)^\*(cbb^\*)^\*$, accepting state
$q\_{4}$: for all other strings, rejecting state/dead-end state

For the incorrect/unlikely interpretation, where $(cb^n)^\*$ means all words like the empty word, $cb^n$, $cb^ncb^n$ and $cb^ncb^n\cdots cb^n$ for some $n\ge1$, the corresponding language is not regular since its intersection with the language with regular expression $cb^\*cb^\*$, $\\{cb^ncb^n\mid n\ge1\\}$ is not a regular language. So there is no FSA for that language.

---
Tags: regular-languages, finite-automata, context-sensitive
---