title: undecidability of virus detection

text:
# Question
Title: undecidability of virus detection
I have been reading the following document about the undecidability of virus detection, available at:

https://enterprise.comodo.com/whitepaper/Impossibility\_of\_Virus\_Detection\_WP.pdf

the problem that I have is in the following part:

The part that I do not understand is the one that says:

Halts(P)=not(DetectVirus(MakeVirus(P)))

Because for what I read if P behaves like a virus, which is made by the function MakeVirus(P), then I suppose that DetecVirus() will detect it and because of that this program will halt. So I will end up with:

Halts(P)=(DetectVirus(MakeVirus(P)))=true

but why do they negate that term? is it because P is a virus, but DetectVirus failed to detect it, so their answer instead of being true is false because of:

Halts(P)=not(DetectVirus(MakeVirus(P)))= not(DetectVirus(MakeVirus(P)=returns virus)=false)=true

I am assuming that P is a virus, but DetectVirus() returns false because it failed to detect it; then the negation of this would be a true value, so in this case Halts(p) will also halt the program.

Could somebody explain me what am I doing wrong?

Thanks

# Answer
Abstracting away the details of their argument, what they're saying is basically:

> Suppose we have a Turing machine `DoesItZork(P)` that takes a program `P` and decides whether it zorks or not. Now we can build a Turing machine `RunThenZork(P) = P() then Zork()` which first runs its input, then zorks. Now, if `DoesItZork(RunThenZork(P))` returns True (and `P` itself does not zork), then `P` must halt on the empty input. On the other hand, if it returns False, then `P` must not halt on the empty input. So we just invert the output: `DoesItHalt(P) = not DoesItZork(RunThenZork(P))`. So if we have a way to ensure that `P` never zorks on its own (which we do), then having `DoesItZork` gives us a solution to the Halting Problem. We know that there is no solution to the Halting Problem, therefore, there can be no `DoesItZork`.

As a matter of fact, this proof skips over some important details. For one, Turing machines have no concept of files, so there needs to be some mapping between Turing machines and actual computer programs. (Fortunately, such a thing does exist.)

In addition, there's an easier way to prove this, once you allow for the idea that a Turing machine can be a virus. Rice's Theorem effectively says that all non-trivial semantic properties of a program are undecidable, where a property is trivial if all Turing machines have it or no Turing machines have it, and a property is semantic if it has to do with the program's behavior rather than its encoding. Since there exist programs that are viruses, and programs that are not viruses, and viruses are defined by their behavior, it's undecidable which are which.
> 1 votes

---
Tags: undecidability
---


# Question
Title: An online algorithm to maintain the Pareto frontier elements
I'm looking for an online algorithm/datastructure that is able to maintain a pareto frontier for two dimensional elements in an online scenario where elements can be added and deleted.

For example:

* `insert((3,7))`

+ since the pareto front is empty it has to be added to it
    + set of elements `E={(3,7)}`
    + pareto frontier `P={(3,7)}`
* `insert((7,3))` and `insert((10,2))`

+ both have to be added to pareto frontier (since they arent dominated)
    + set of elements `E={(3,7), (7,3), (10,2)}`
    + pareto frontier `P={(3,7), (7,3), (10,2)}`
* `insert((8,4))`

+ is dominated by `(7,3)` so do not add it to the pareto frontier (but keep it in the set of elements `E` because its maybe going to be part of the pareto frontier later)
    + set of elements `E={(3,7), (7,3), (10,2), (8,4)}`
    + pareto frontier `P={(3,7), (7,3), (10,2)}`
* `remove((7,3))`

+ remove `(7,3)` from the set of elements and from the pareto frontier. The pareto frontier has to adjust accordingly and therefore `(8,4)` is added to the pareto frontier now.
    + set of elements `E={(3,7), (10,2), (8,4)}`
    + pareto frontier `P={(3,7), (10,2), (8,4)}`

This question is similiar to An online algorithm to find the Pareto frontier elements, but in the scenario described above points can also be removed. A brute force algorithm would have quadratic time complexity and I am looking for something better.

# Answer
> 3 votes
You can find an answer to this in "Dynamic Planar Range Maxima Queries", by Brodal and Tsakalidis. They support `insert` and `remove` in $O(\log n)$ time. That paper points to several previous papers that addressed the question as well.

In particular, I expect the simplest solution can be found in sections 8 and 9 of "Maintenance of Configurations in the Plane", Technical Report RUU-CS-79-9, by Overmars and van Leeuwen, (mirror). Their solution takes $O(\log^2 n)$ for each `insert` or `remove`.

---
Tags: algorithms, data-structures, pareto
---


title: Systematically altering functions

text:
# Question
Title: Systematically altering functions
Let A and B be two integers, where their size is constrained to 2 bits in binary. There exists a function F, which outputs integers of the same size, where F(A) = F(B) = Y. For example, A = 01, B = 10, and Y = 11.

There exist some possible functions, such as G(X) = X xor 10. Another could be H(X) = X + 01 (ignoring overflow). However, in terms of their results, many of these would essentially be the same function, mapping the same inputs to the same outputs.

What is the "common denominator", so to speak, that would allow seeing all functions as the same?

The purpose of this is to be able to "increment" a function. In the first example, suppose I do not know what F is, and I want to write a program to find it. I know that F(A)=F(B), so I could write a loop to try all the possible functions by "incrementing" the function after each iteration, until the function that has F(A)=F(B) is found. Ultimately this will be used on larger sized, and possibly differently sized, inputs and outputs

# Answer
You can represent a function by its truth table. Then, any two functions with the same truth table will be the same function, in the sense that they map the same inputs to the same outputs, so this gives you a way to recognize those.

The truth table has 4 entries, each of which are 2 bits, so the truth table is 8 bits long. Thus, each function can be associated with an 8-bit binary string, or equivalently, an integer between 0 and 255. You can "increment" the function by incrementing the corresponding integer and converting it back to a truth table.
> 0 votes

---
Tags: number-theory
---


# Question
Title: CSMA/CD with binary exponential backoff: Do both back off or just the loser?
I've been given two PC's that are connected via Ethernet, and as such are using CSMA-CD with binary exponential backoff.

Now, both PC's, let's call them $A$ and $B$, are trying to send data simultaneously. So, the first time both randomly choose a number from $\\{0,1\\}$. Let's say $A$ wins (i.e. $A$ picks 0 and $B$ picks 1) and sends the first frame of its data.

Instantly after sending the frame, the next collision between $A$ and $B$ occurs.
Now, in my given scenario, for some reason $A$ only picks from $\\{0,1\\}$, while $B$ picks from $\\{0,1,2,3\\}$.

Why is that the case? I don't see how this algorithm is any better than if $B$ gave up right away after losing once.
First: Just using a wider range doesn't stop the two PC's from colliding at all. If only $A$ has enough frames to send, the next collision will occur eventually anyway.
And for every collision afterwards, the chance of $B$ losing just ever increases. So, $B$ will starve and give up eventually anyway as well.

Why not just let $B$ give up instantly, and let $B$ wait till $A$ certainly has finished? Is my given scenario somehow wrong, or am I missing the point?

# Answer
You are right. This does seem like an undesirable consequence of the CSMA-CD protocol.

I suspect this behavior was selected because it is implementable, and because it is not so easy to come up with an alternative that is simple and avoids this problem.

Recall, the only thing that is observable to B when it tries to send is whether that send was successful or a collision occurred. B can't see anything about whether it "wins" or "loses"; it has no visibility of the other parties. It doesn't know that A is also trying to send at the same time. If B tries to send and succeeds, then B doesn't know whether that's because no one else wanted to send; or A wanted to send and previously "won" (already finished sending); or A wants to send but has "lost" (hasn't sent yet and has a backoff time that is still in the future) -- B has no way to distinguish between those cases.

It sounds like one of your alternative proposals is that B should give up permanently as soon as it is involved in a two consecutive collisions. That doesn't seem to make sense to me. When B gives up permanently, that means that it just powers down and never sends on the network again? You can't have permanent disconnection -- that wouldn't be useful. There has to be *some* point at B is going to try to send something again, so it's just a question of what that condition is.

It sounds like another of your proposals is that if B collides with A, and A gets to send first, then B should wait until A is finished. That's harder to implement, and I'm not sure it has much benefit for B (B is still stuck waiting). Why is it hard to implement? It's hard to implement, because it's not clear how B would know when A is "done" transmitting. It's not even clear what "done" means. Even A won't know when it is done; A doesn't necessarily know what other packets it might want to send in the near future. So now we get into some design space where we try to figure out what we mean by "done", and how B would know when A is done (maybe it's that A hasn't sent anything in the last 20ms?). It's not enough to have A declare how much more it currently has to send as soon as it succeeds on a retransmission attempt and then require B to wait until that much has been sent, because what if after A finishes sending that much, A discovers it has more that it wants to send? (Presumably, there's some application running on A that periodically wants to send stuff. A's ethernet card can't predict what future sends the application will want to do. Maybe the application will end up continuously trying to send packets, one after another, rapid-fire.) If A tries to send some new message as soon as it finishes the previous one, you'll be back to the same scenario where A is more likely to win, so this doesn't eliminate the problem.

Or, if you were proposing that each PC remembers who won the last time and you alternate, that is also problematic, for a different reason. It doesn't scale well to more than two PCs on the same network.

The standard protocol is memoryless; it doesn't require keeping track of past history. This makes it simple, scalable, and reasonably efficient in many scenarios.
> 2 votes

---
Tags: computer-networks
---


title: Algorithm analysis

text:
# Question
Title: Algorithm analysis
why option c is the answer ? And why not option B ?

# Answer
`f` will be called many times in this algorithm, as `f(c0),f(c1),...`.

Since `counter` is reset to `0` after each call to `f`, we get that `c0+c1+... <= n`. Since `f` has a linear cost, the cumulative cost of all the calls to `f` is `<= k c0 + k c1 + ... = k n` for some constant `k`. Hence this cost is $O(n)$.

The rest of the program only adds $O(n)$ more operations, so we get $O(n)$ overall cost. Since the loop takes $\Omega(n)$ iterations, we also get $\Theta(n)$ overall cost.
> 0 votes

---
Tags: algorithm-analysis
---


# Question
Title: What is the equation for a spiral path in 3D?
I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.

Would anyone please show me the equation for 3D spiral patterns, which should involve X, Y, and Z coordinate ?

Thanks.

# Answer
I have just found this correct answer on the web (by someone else):

A helix is a circle that moves up with time. Hence, the equations for one helix are:

x(t) = sin t

y(t) = cos t

z(t) = t

A double helix include two helices that are offset by half a turn. So, the equations for the second helix would then be :

x(t) = sin t

y(t) = cos t

z(t) = t + \pi
> 1 votes

---
Tags: pattern-recognition, mathematical-programming, mathematical-software
---


# Question
Title: Compute unknown matrices that minimize a sum
This problem is about working with smart-phone accelerometers.

To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum: $$\sum\_{i=0}^N(|g|^2 - |TK(a\_i + B)|^2)^2,$$ where $a\_i$ is a known 3x1 vector and |$g$| is a known constant and unknown matrices are: $$T = \begin{bmatrix} 1 & t\_1 & t\_2 \\ 0 & 1 & t\_3 \\ 0 & 0 & 1\end{bmatrix},\ K=\begin{bmatrix} k\_1 & 0 & 0 \\ 0 & k\_2 & 0 \\ 0 & 0 & k\_3\end{bmatrix},\ B=\begin{bmatrix} b\_1 \\ b\_2 \\ b\_3\end{bmatrix}.$$

I have read in an article one can solve such problems by Levenberg-Marquardt (LM) algorithm. Unfortunately I cannot figure out how. Can anyone suggest a solution to this minimization problem? And I need to implement the algorithm in python so if you know any good python library please name it.

# Answer
> 1 votes
I've found the answer. You can solve such problems using scipy.optimize.root which includes Levenberg-Marquardt (LM) algorithm.

---
Tags: optimization, matrices, linear-algebra, signal-processing
---


# Question
Title: General version of pumping lemma for regular languages, how many partitions to consider
The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$.

The article on wikipedia says, that this version is a special case of a more general version, in which one should consider strings $uwv = uxyzv$.

When using that general version of the lemma, does it require considering every possible partition of the string into $uxyzv$? I.e. does it require considering every possible $u$ and $v$?

# Answer
> 3 votes
The general version of the Pumping Lemma specifically applies to all strings $uwv \in L$ such that the length of $w$ is greater than or equal to a certain constant (the pumping length). No matter what $u$ and $v$ you pick, so long as whatever's between them is long enough, the general version will work.

So you don't need to consider all $u$ and $v$, only the ones that are useful to solving your problem. For instance, if you have the language $0^a 1^b 2^b 3^c$ where $a$, $b$, $c$ are positive integers, you can let $u$ be the string of zeroes at the beginning, let $v$ be the string of threes at the end, and then apply the simpler version of the lemma to the remaining part.

Conversely, the choice of $x$, $y$, and $z$ is harder, because the lemma doesn't guarantee that it works for *all* choices of these substrings, only for *at least one* choice of them.

---
Tags: formal-languages, pumping-lemma
---


title: Proving GCD algorithm terminates

text:
# Question
Title: Proving GCD algorithm terminates
I'm reading this article on a GCD algorithm described by Dijkstra: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.4.html

I'm looking at program 1. In particular I'm trying to understand the proof that the loop terminates. Here is program 1 (my notation is slightly different than the one in the article):

```
function GCD(a,b)

while a != b
    if a > b
        a = a - b
    else
        b = b - a

return a

```

I get that max(a,b) at loop n is strictly greater than max(a,b) at loop n+1. Since a and b are integers greater than 0 it follows that max(a,b) is always greater than 0. This implies a lower bound. Therefore the while loop must terminate.

Is my understanding correct?

# Answer
> 1 votes
If you just care about termination of the algorithm not the tight analysis then you can say that it will terminates within $a+b$ steps as inside the while loop you are decreasing either $a$ or $b$ depending on some condition, so your while loop have to terminate within $a+b$ iterations.

# Answer
> 1 votes
**Assuming that you start with positive integers**, your reasoning is correct. `max(a,b)` strictly decreases and the loop will terminate before this value reaches zero (since the only way for it to become zero is if `a == b`). Therefore it can run for at most `max(a,b)-1` steps

If you don't start with positive integers, then you'll loop forever. So make sure to avoid that.

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


# Question
Title: Is writing a number as two squares and writing the factors of a number equally hard?
Let $L\_1$ and $L\_2$ be the following:

$L\_1=\\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\\}$

$L\_2=\\{(N,M): M\<N, \exists 1\<d\leq M \text{ such that d|N} \\}$

Claim $L\_1 \leq\_P L\_2$

Sketch Proof

If I want to know whether $r\in L\_1$.

The number of integer solutions to $x^2+y^2=r$ is given by

$g(r)=\sum\_{d|r}{\chi{(d)}}$ where $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Then $L\_1=\\{r: g(r)\neq 0\\}$. So then to answer is "$r\in L\_1$?" is at most as hard to answer as "what are the divisors of $r$?"

$\square$

What I would like to know is if this is true the other way around. Is it true that if I had a machine which could tell me in constant time whether $r\in L\_1$ could I create a machine which could answer "is $(M,N)\in L\_2$?" in polynomial time?

**Motivations**

This question came out of a discussion on this question.

**Apologies** I am really just a math.se member who has gotten lost and wandered on to cs.se. Let me know if my question is clear and up to the standards of this site. I am happy to make corrections.

# Answer
> 5 votes
Here's the situation as far as I can tell:

The most efficient way known to test membership in $L\_1$ is to factor $r$. No more efficient algorithm seems to be known.

However, there is no obvious reduction to prove $L\_2 \le\_P L\_1$. In other words, if we had a machine to decide $L\_1$, there's no easy way to use that to factorize. If we want to factor a number $N$, we can check whether $N \in L\_1$, but this only gives us one bit of information about the factors of $N$. Testing multiples of $N$ (i.e., whether $cN \in L\_1$ for some integer $c$) doesn't give us any additional information, as knowing whether $N \in L\_1$ suffices to predict whether $cN \in L\_1$ for all $c\>0$. Testing other numbers doesn't seem to help in any obvious way, either. (Testing whether $N' \in L\_1$ for some other number $N'$ doesn't seem to give any useful information, if $\gcd(N,N') =1$; and if we had a way to find another number $N'$ such that $\gcd(N,N')\ne 1$, we'd already know how to factor, but of course we don't know how to do that -- so any number we know how to generate is unlikely to give us any useful information on the factors of $N$.) This is not a proof; it is just handwavy intuition.

So it seems plausible that $L\_1$ might be easier than $L\_2$, and it also seems plausible that they might be of the same difficulty. I'm not aware of any further results on this subject.

---
Tags: complexity-theory, time-complexity, np, decision-problem
---


# Question
Title: DFS and BFS Time and Space complexities of 'Number of islands' on Leetcode
Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS. Apparently, the grid can be viewed as a graph.

I have included the problem statement here for easier reading.

```
Given a 2d grid map of '1's (land) and '0's (water), count the number of
islands. An island is surrounded by water and is formed by connecting adjacent
lands horizontally or vertically. You may assume all four edges of the grid are
all surrounded by water.

    Example 1:

    Input:
    11110
    11010
    11000
    00000

    Output: 1

    Example 2:

    Input:
    11000
    11000
    00100
    00011

    Output: 3

```

I am unclear as to why the time complexity for both DFS and BFS is `O(rows * columns)` for both. I see how this is the case where the grid is just full of 0's - we simply have to check each cell. However, doesn't the DFS approach add more time to the search? Even if we mark the cells we visited by changing them to `0` in the dfs methods, we still would revisit all the cells because of the two outer loops. If dfs could be have time complexity of O(n) in the case of a big grid with large row and column numbers, wouldn't the time complexity be O(rows * columns * max\[rows, cols\])? Moreover, isn't the same case with the BFS approach where it is `O(rows * cols * possibleMaxSizeOfQueue)` where `possibleMaxSizeOfQueue` could again be `max[rows, cols]`?

```
for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

```

How is DFS's space complexity `O(rows*cols)`? Is it not possible/common to consider the call stack space as freed when a recursion branch returns? How is the space complexity for BFS `O(min(rows, cols))`? The way I see it, the queue could be full of all elements in the case of a grid with just 1's thereby giving `O(rows*cols)` for BFS space complexity.

**DFS Solution**

```
class Solution {
  void dfs(char[][] grid, int r, int c) {
    int nr = grid.length;
    int nc = grid[0].length;

    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
      return;
    }

    grid[r][c] = '0';
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
  }

  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
}

```

> Time complexity : O(M×N) where M is the number of rows and N is the number of columns.
>
> Space complexity : worst case O(M×N) in case that the grid map is filled with lands where DFS goes by M×N deep.

**BFS Solution**

```
class Solution {
  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;

    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          grid[r][c] = '0'; // mark as visited
          Queue<Integer> neighbors = new LinkedList<>();
          neighbors.add(r * nc + c);
          while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
              neighbors.add((row-1) * nc + col);
              grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
              neighbors.add((row+1) * nc + col);
              grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
              neighbors.add(row * nc + col-1);
              grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
              neighbors.add(row * nc + col+1);
              grid[row][col+1] = '0';
            }
          }
        }
      }
    }

    return num_islands;
  }
}

```

> Time complexity : O(M×N) where M is the number of rows and N is the number of columns.
>
> Space complexity : O(min(M,N)) because in worst case where the grid is filled with lands, the size of queue can grow up to min(M,N).

# Answer
> 1 votes
DFS takes linear time. It only visits each vertex once; it has an explicit check, before visiting a vertex, to see whether it has been visited before, and if so, avoid visiting it again. This should be covered in standard algorithms textbooks, so there is little point in repeating the standard analysis of DFS here -- I suggest finding a good textbook and reading their chapter on depth-first search. I like the discussion in Dasgupta, Papadimitriou, and Vazirani's textbook, but there are many others.

See also Counting islands in Boolean matrices for an even better algorithm that has the same asymptotic running time, but lower space complexity.

---
Tags: algorithms, graphs, asymptotics
---


title: Count all paths between two vertices

text:
# Question
Title: Count all paths between two vertices
The problem is we have to count number of paths between a source and a destination in a graph. The brute force approach is using backtracking which is $O(n!)$.

Is there any better solution to this problem?

Note that we have to count paths so we can't visit the same node again in a path.

I think this problem is np-hard and is similar to finding hamiltonian path in a graph. So, I can use Held-Karp algorithm to solve it in $O(n^2\*2^n)$ using dynamic programming. Am I right?

# Answer
Let $A$ denote the adjacency matrix, $A^k$ its $k$th power, and $(A^k)\_{ij}$ the entry of $A^k$ at row $i$, column $j$. Then $(A^k)\_{ij}$ is a count of the number of paths of length $k$ from node $i$ to node $j$.

Let $M = \text{Id} + A + A^2 + A^3 + \cdots$. Then $M\_{st}$ is a count of the number of paths (of any length) from source $s$ to destination $t$. So, we just need to compute the matrix $M$. The matrix $M$ can be computed using the matrix identity

$$M = (\text{Id} - A)^{-1}.$$

Thus, with a matrix subtraction and inversion, then looking at the $u,j$ entry of the resulting inverse, you can obtain a count of the number of such paths.

This includes paths where a node can be repeated. If you want to count the number of simple paths, then the problem is #P-complete for general graphs (and thus likely has no efficient algorithm), or can be done in linear time for directed acyclic graphs by topological sorting and then using dynamic programming.
> 5 votes

---
Tags: algorithms, graphs
---


# Question
Title: When to terminate search for path in an infinite grid
I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in a certain scope/range. However when expanding this to an infinite 2D grid, I don't understand when (say using BFS as an example) to conclude that a path simple doesn't exist without having the algorithm run infinitely since I can't use grid size as a boundary condition. Is there some kind of formula that can be used in these cases? Also, take into account that there could be obstacles along the path too so the path distance can vary from different origins to destinations.

I've considered trying to take the absolute value of the difference between the coordinate points and raising it to some power as a way of setting an upper limit of steps taken before considering that a path must not exist, but this approach is obviously lacking and incorrect to say it bluntly since it doesn't work for many cases.

I apologize if my question is confusing. I'll restate it here: basically, how do I know when to assume a path from an origin to a destination doesn't exist in an infinite 2D grid?

# Answer
> 2 votes
Unfortunately, the simple answer is, you can't.

All the standard search algorithms have a runtime that's polynomial in the size of the graph. If your graph is infinitely large, there's no guarantee that they'll ever terminate for arbitrary inputs: how can they ever know whether they should give up now, or whether they'd find the answer if they just expanded one more node?

Any approach that involves putting an upper limit on the number of steps, is doomed to failure. Even if the start and end points are right next to each other in the coordinate system, I could delete the edge between them, then make it so that the shortest path from one to the other takes one more step than you're allowing. And then your algorithm will say, incorrectly, that there's no solution.

However, if you have additional information about your graph (perhaps there's only a finite number of edges missing from the grid?), then you can potentially exploit this to find an answer. It's only impossible for *arbitrary* infinite graphs; there are many classes of infinite graphs for which it can be solved.

---
Tags: algorithms, graphs, approximation, graph-traversal
---


# Question
Title: CNN/Neural Network: Can I still estimate 3 parameters if my input data has insufficient parameter labels?
I am trying to simplify a CNN model. Currently, I need to train 3 different models (with the same architecture) to estimate each parameter. I am just wondering if there is a way to just train one model that outputs 3 parameters, with input images containing only single parameter label. Say the three parameters are some kind of measure of symmetry (sym), repetitiveness (rep), roundness (rd). Each of my input images will only give a label for one of the parameters. For each parameter, there is the same number of images. I am thinking if there is a way to accomplish this using some kind of dummy variable to block out the unavailable parameters from backpropagation?

If anyone who has experience with this scenario could give me some advice, it would be super appreciated.

# Answer
> 1 votes
Yes, this can be done. Basically, you define a custom loss function, and then train the neural network to minimize this loss function. In particular, you construct a single neural network that has 3 outputs; the first output is a measure of symmetry, the second of repetitiveness, and the third roundness. The custom loss function should look at the output for which you have a known label and penalize the model according to how much that output is in error (it ignores the other 2 outputs). For instance, if you are currently using mean-squared error, your custom loss function would be equal to the square of the difference between the known label and the corresponding output of the network. This custom loss function is differentiable, so all the standard training methods (backpropagation, gradient descent, Adam solver, etc. etc.) work directly, with no modifications needed.

Many libraries for training neural networks will let you specify a custom loss function.

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


# Question
Title: Symmetric difference of a set with an empty set
The definition of symmetric difference of two sets $\alpha $ and $\beta$, $\alpha \oplus \beta$ is defined as the set of all $x$ such that, $x \in (\alpha \cup \beta) - (\alpha \cap \beta)$.

If, $\alpha$ is some set with some members and $\beta = \phi$,

Will $\alpha \oplus \beta$ not contain "nothing"? I mean, If we take away all the elements of $\alpha \oplus \beta$, will we not get $\phi$ in end?

# Answer
> 2 votes
Consider $\alpha = \\{1,2\\}$ and $\beta=\emptyset$.

Then,

$$ \alpha\oplus\beta = (\alpha\cup\beta)\setminus(\alpha\cap\beta) = (\\{1,2\\}\cup\emptyset)\setminus(\\{1,2\\}\cap\emptyset) = (\\{1,2\\})\setminus(\emptyset) = \\{1,2\\} $$

So, no, $\alpha\oplus\beta$ is not "nothing", in general.

---
Tags: discrete-mathematics, number-theory
---


title: Need pointers for problem formulation

text:
# Question
Title: Need pointers for problem formulation
*I have very little experience with graph DBs but i imagine this problem suits one*

Assume a dataset with two entities , **Users** and **Foods**. A user can have a relationship with a **Food**, specifically they can score it from 0 to 100.

What i'd like to achieve is, for every user, find all the other users that are similar to them. By similar i mean *find the **Users** that have also liked similar **Foods** and get a match* so essentially im trying to build a a matchmaking system.

Algorithms such as finding friend's of friends are relatively easy to wrap my head around however im unsure as to how to approach this one and wether describing my data as a graph is even the right way to go about it.

I originally made a thought experiment to see how this would look on a relational database and its clearly quite hard to achieve as for every insert of a new **Food** or **User**, recalibration would need to happen for the entire database ( which sounds unavoidable in the first place )

I dont know what i dont know so if you could give me some pointers from here i'd be happy to follow your leads. Thanks so much.

# Answer
> 1 votes
Yuval Filmus already pointed you towards recommender systems, which in your case is the right way to go.

However, since you asked for a graph formulation and tagged it with graph-theory, we will go out of our way to put this into such a setting.

## Definitions

A graph is called *bipartite* if its vertices can be partitioned into two sets, say $U$ and $V$ in such a way that all edges are between $U$ and $V$. (Coincidentally a graph is bipartite if and only if it is two-colorable.)

A bipartite graph is called *complete* if every edge between $U$ and $V$ are present, i.e., it is isomorphic to $K\_{n,m}$ for some $n,m \in \mathbb{N}$.

A bipartite graph is called a *bicluster* if its connected components induce complete bipartite graphs.

## The problem

An *editing* problem is a graph problem where we want to add or delete (as few as possible) edges to make a graph have a certain property. So let us define **Bicluster Editing** as the following problem:

Given a bipartite graph $G = (V, U, E)$ and a natural number $k \in \mathbb N$, does there exists a set of edges $E'$ such that $G' = (U, V, E')$ is a bicluster and $|E \triangle E'| \leq k$ (where $\triangle$ is the symmetric difference)?

Now, what does this mean? If such a set exists for a small $k$, you have partitioned your users and foods into equivalence classes such that in every equivalence class, all the users like the same foods and all the foods are liked by the same users, changing the graph very little.

Is it **practical**? No. But at least it's NP-complete.

---
Tags: graphs
---


# Question
Title: Understanding the algorithm behind day of week calculation
I came across this algorithm recently to calculate day of the week for any year.

```
int y0 = year - (14 - month) / 12;
int x = y0 + y0/4 - y0/100 + y0/400;
int m0 = month + 12*((14 - month)/12) - 2;
int d0 = (date + x + (31*m0)/12)%7;
switch (d0) {
    case 1: return "Monday";
    case 2: return "Tuesday";
    case 3: return "Wednesday";
    case 4: return "Thursday";
    case 5: return "Friday";
    case 6: return "Saturday";
    case 0: return "Sunday";
}

```

How does this algorithm work? I see a lot of magic numbers in calculations above, but its difficult to understand the intuition behind this algorithm

# Answer
As mentioned in a comment, this program is a variant on Zeller's congruence.

Here are the steps:

0. It's good to know that the Gregorian calendar (which is what we are using) repeats every 400 years. In the 400 year cycle, every fourth year is a leap year except for the centuries other than the one at the start of the cycle. In other words, in the 400-year cycle starting 2000 and ending 2399, there are 97 leap years: all the years divisible by 4 except 2100, 2200 and 2300.

There are 365 days in a normal year, which is 52 weeks and one day. A leap year has an extra day. So the 400-year cycle, which has 303 normal years and 97 leap years, is 52*400 weeks plus (303 + 97*2 = 497) days. 497 days is exactly 71 weeks, so the cycle is an exact number of weeks, which means the weekday for a given date is the same for the "same date" in every cycle. (The same date meaning the same day, month and year mod 400.)

Since we're only interested in which weekday a date is, and not the total number of days since some determined starting point, we can do all computations mod 7. So if we know the weekday for some particular date, we can find the weekday for the same day/month in another year by adding the number of years and then the number of intervening leap days.

```
 int x = y0 + y0/4 - y0/100 + y0/400;

```

`y0` is explained below; if you think of it as the number of years from the beginning of (some) 400 year-cycle, then `x` is just the number of years plus the number of leap years: `y0/4` (every fourth year) `- y0/100` (except for centuries) + `y0/400` (other than the centuries which start a cycle). If we had computed `y0` as years into the current cycle, we could have avoided the `y0/400` term.
1. The fact that a leap day falls into the middle of a year complicates that computation. To make it simpler, we start the cycle at March 1 instead of January 1, effectively moving January and February to the previous year. That puts the leap day at the end of the year, so we can evaluate the number of leap days by counting the number of leap years, as above. As we'll see below, this also has the advantage of making the alternation of month lengths more regular; aside from February, months more or less alternate between 31 and 30 days.

```
 int y0 = year - (14 - month) / 12;
 int m0 = month + 12*((14 - month)/12) - 2;

```

Those lines are trying to way too hard to be clever, and end up being terrible because of the slowness of division (even though division by 12 can be performed with multiplies, and even though the compiler can figure out that it's only necessary to do it once. The code would be clearer and faster if it were written in the obvious way:

```
 int y0 = year, m0 = month - 2;
 if (m0 < 1) { --y0; m0 += 12; }

```
2. Essentially, we now have a weekday offset of March 1 in the specified year from the March 1 which starts the cycle. Now we just need to figure out the adjustment for the months between March and the specified month. Each of these months will move the weekday by either two (30 mod 7) or three (31 mod 7) days. Months mostly alternate between 31 and 30 days, except although sometimes there are two 31-day months in a row. (As mentioned above, we can ignore February here because we're only counting months which come before the specified date, and with February shifted to the end of the year, it is never before any date in the year.)

```
 int d0 = (date + x + (31*m0)/12)%7;

```

`(31 * m0) / 12` for `m0` in the range `[1, 12]` produces the sequence `{2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31}`. The adjacent differences in that sequence are `{3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3}` which happen to correspond to the lengths of the months (mod 7) starting at March. (The pairs of consecutive 3s correspond to July/August and December/January.) So adding this to the year adjustment `x` and the date in the month `date` and then reducing the sum mod 7 gives us the day in the week with the week starting three days before March 1 of (every) cycle. (Three days before because (1) the magic formula `(31 * m0) / 12` starts with 2, not 0, and (2) the day of the month starts with 1, not 0. So the formula is off by 3.)

This is not the only way of performing this calculation. As it happens, exactly the same sequence is produced with `(13 * m0 - 1) / 5`. Either way, the cleverness is not justified by efficiency; division is a lot slower than a simple table lookup:

```
 /* Not optimal but it corresponds to the above computation */
 static const char month_adjust[] = {
     2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31
 };
 int d0 = (date + x + month_adjust[m0]) % 7;

```

The above table could be reduced to three bits per month, since only the value mod 7 is important. That means that the lookup table could be replaced with a magic integer constant and a bit-shift, but the potential gain is probably insignificant. I'll leave the details as an exercise for would-be code golfers.
3. March 1 of every cycle is a Wednesday, and that needs to correspond to the value 3 of that computation. The mapping between modulo and day of the week is provided by the switch statement:

```
 switch (d0) {
     case 1: return "Monday";
     case 2: return "Tuesday";
     case 3: return "Wednesday";
     case 4: return "Thursday";
     case 5: return "Friday";
     case 6: return "Saturday";
     case 0: return "Sunday";
 }

```

I would have used a lookup table instead of a switch, which leads to more direct code:

```
 static const char* weekdays = {
     "Sunday", "Monday", "Tuesday",
     "Wednesday", "Thursday",
     "Friday", "Saturday"
 };
 return weekdays[d0];

```
> 7 votes

---
Tags: algorithms
---


# Question
Title: Prove np-hardness of dividing items from the lists
I have the following problem.

Given a finite number of lists of items. The same item can appear in many lists. I would like to color items with **3** colors, such at least two colors appear in each list.

I would like to show that this problem is NP-hard. I would like to provide reduction from the 3-coloring problem which seems to be similar.

I think I could make items as nodes and link every item with every other from the shared lists, but then the condition of 3-coloring would be too demanding in comparison to my problem. What should I do differently in order to create the reduction?

# Answer
To prove that a problem is NP-hard, we need to reduce an NP-hard problem to it (which in this case as you mentioned would be 3-coloring).

So what we are trying to do, is to map every graph $G(V,E)$ to an instance of your problem, where every node $v\_i$ will be mapped with an element $el(v\_i)$ and every edge $\epsilon\\{v\_1, v\_2\\}$ would be represented with a two-element list $\\{el(v\_1), el(v\_2)\\}$.

So now a coloring $f:V\rightarrow C$ would be reduced to a coloring on the set of elements in your problem which means, if we found a coloring on the elements of the proposed problem, we can use the same coloring on our graph and it would be a proper coloring.

Proof. If $f:V\rightarrow C$ isn't a proper coloring, that means there is an edge with both nodes having the same color, which means there is a set with two elements and both of them have the same color which contradicts the statement of your problem.
> 3 votes

---
Tags: graphs, np-complete, reductions, np-hard, colorings
---


# Question
Title: Shortest path from source to destination in directed acyclic graph
There is an approach given in this article Shortest Path in Directed Acyclic Graph to find the shortest path in O(V+E) using topological sort.

I have another approach which I think is more efficient. If use dynamic programming to store the minimum distance from a vertex to a destination than I don't need to explore that node again. Now, time complexity of this solution would be O(V+E) if I am using top to bottom approach (bottom to top approach would be O(V^2).

The advantage of this method is I don't have to find topological order first to find the minimum distance, I can find it directly.

The only disadvantage I can see of this method is, If the depth of my recursion tree is large, then I can run out of stack space and I have to use bottom to top approach. Now, if I have a sparse graph (E=O(V)), time complexity using this method would be O(V^2) but using topological sort method would be O(V) and I can use kahn's algorithm to find topological sort which is done iteratively so running out of stack space wouldn't be an issue.

Is there anything wrong in whatever I have written above?

# Answer
> 1 votes
If your algorithm runs in $O(V+E)$ time, and their algorithm runs in $O(V+E)$ time, I don't see any basis for calling your approach more efficient. At least, asymptotic running time does not seem precise enough to determine which will be more efficient in practice.

# Answer
> 0 votes
No, the time complexity using top to bottom approach would also be $O(V^2)$. So the topological sort method is more efficient as it can find the shortest path in $O(V+E)$.

---
Tags: algorithms, graphs
---


title: Clone an Undirected Graph

text:
# Question
Title: Clone an Undirected Graph
I was reading an article on Clone an Undirected Graph, It says I have do do bfs and have to keep track of visited/cloned nodes.

I have another approach- I will initialize an empty adjacency list and then traverse the original adjacency list and copy it. Its time complexity is O(V+E) and I don't have to keep track of anything.

Is there anything wrong with this approach?

# Answer
> 0 votes
Assume that you are only given a source vertex and not given the whole adjacency list, then this method won't work.

---
Tags: algorithms, graphs
---


# Question
Title: How to Efficiently Define the Natural Numbers in Type Theory
A while ago I wondered about how Proof Assistants like Coq prove $m \leq n$ and the like. It looks like they actually need to traverse the natural numbers based on the successor/predecessor formulation:

> `Coq < Eval compute in le_lt_dec 100000 1000000.` Warning: Stack overflow or segmentation fault happens when working with large numbers in nat (observed threshold may vary from 5000 to 70000 depending on your system limits and on the command executed). Stack overflow.

One of the answers suggested using the BinInt (Binary Integers representation) to perform this operation.

> When a mathematician looks at a claim like $1000 ≤ 1000000$ and says "obviously", they are taking advantage of the fact that we wrote the claim in **decimal notation**. If you want to do something similar in CoQ, you could try to prove, e.g., $10∗10∗10≤10∗10∗10∗10∗10$.

So I'm wondering if there is a standard way of representing numbers as types without defining them like Peano's axioms style, using successor/predecessor and the like. Something that allows you to prove two numbers have a relation such as $m \leq n$ or $m \neq n$ or do other common things with numbers like adding/subtracting, in such a way where the "formal definition" (i.e. succ/pred) of the numbers is combined with some more computationally optimal version so you can use it in practice. Not sure what best-practice is to do here, but I would like to define a numbers type and have it gain all the advantages of proof theory / proof assistants, while also being the actual type definition used to construct i.e. integers.

# Answer
> 7 votes
There's nothing stopping you from defining binary numbers in type theory, and this should give greater efficiency in practice.

For example:

https://coq.inria.fr/library/Coq.Numbers.BinNums.html

EDIT: Why not base 10?

Comparison on binary numbers can be done in $O(\log\_2 n))$ time. If you have base 10, you can do it in $O(\log\_{10} n)$ time. But if we apply the change of base formula, $O(\log\_{10} n) = O(\log\_{2} n / \log\_{2} 10) = O(\log\_2 n)$, since $O(\log\_2 10)$ is constant.

There's a speed tradeoff. You get constant speedup for some operations, but you get constant slowdown for others. For example, each pattern match now has 11 options instead of 3. So, given that they have the same asymptotic behavior, we usually go with the simplest one.

Finally, the advantage with base 2 is that, if you limit yourself to 32 or 64 bits, you can represent them using machine integers, for example, if you extract your Coq code to OCaml, which means you can get very fast extracted code.

---
Tags: type-theory, proof-assistants
---


title: Rectangular Automata

text:
# Question
Title: Rectangular Automata
have a question regarding rectangular automata and their derivatives.

In each location the derivates are defined by a interval, how are the derivates applied on the variables? Is one value chosen out of the interval and added to the value or do we reset the value to one value in the interval ?

Regards

# Answer
The derivatives are applied over time in a continuous fashion.

Here is an example:

Assume that we want to find out whom of two runners wins a running tournament. They run for 100 meters each, and the one reaching a goal first wins.

We can model the position of the two runners using two variables $x$ and $y$. We do not quite know the exact speed of the runners, as it depends on how well they feel at the tournament day. But we know some boundaries on their speed, i.e., how $x$ evolves over time. Let's assume we know that $\dot x \in \[9.8,9.9\] \ \frac{m}{s}$ and that $\dot y \in \[9.7,9.78\] \ \frac{m}{s}$

So a rectangular hybrid automaton would have one "running" state in which the variables evolve like this, and then there are two states for the cases that runner $x$ has reached the goal and that runner $y$ has reached the goal. You can see from the numbers above that player $x$ will win, but let's assume that this is not obvious, and we want to use a rectangular hybrid automaton for this:

```
   | x:=0, y:=0
   V
+- -------------------+    x >= 100       +---------------------+
| 0.98 <= x' <= 0.99  |------------------>| x' = 0              |
| 0.97 <= y' <= 0.978 |                   | 0.97 <= y' <= 0.978 |
| x < 10, y<10        |                   +---------------------+
+---------------------+
   |                       y >= 100       +---------------------+
   +------------------------------------->| 0.98 <= x' <= 0.99  |
                                          | y' = 0              |
                                          +---------------------+

```

If we always "reset the value to one value in the interval", then the two runners would never reach the 100 meter mark and hence one of the two goal states on the right is never right.

But it is also not the case that "one value chosen out of the interval and added to the value". Because adding is a discrete actions. You could, for example, add x' to x until one of the two conditions have been reached. But then, it takes exactly 11 steps for both runners to reach the goal, and hence, they both win at the same time. But that makes no sense, because time is continuous. Rather, if you plot the evolution of x over time, you would use x' as the steepness of the line, and the positions of the runners are really continously updated as time progresses, as in real life.

In rectangular hybrid automata, it doesn't really matter whether $\dot x$ can change at every moment of time to a different value in the interval or not. The reason is that we use these automata for checking the properties of model. In the example above, this would be whether the bottom-right location is ever reached (which is not the case). And for this analysis, whether the first derivatives has to stay constant (within their defined interval) or not does not matter.
> 2 votes

---
Tags: automata
---


title: Bubble in a pipeline

text:
# Question
Title: Bubble in a pipeline
When NOPs are introduced in the pipeline by the control unit, how does they really cause the pipeline to stall? I mean, at every clock cycle, the pipeline register will eventually forward its contents to the very next stage, so how does NOPs prevent that from happening?

Also when NOPs are introduced the PC doesn't increment and no fetch occurs? How does that happen?

# Answer
> 2 votes
Inserting NOPs *is* the stall. It delays execution until the result is ready.

A simple pipelined CPU will have a instruction decoder that controls the entire CPU at a low level setting control lines to each functional unit to control how it behaves. Including whether to pull in a new instruction.

The decoder checks dependencies between instructions and when it sees it needs to delay it will stop pulling in new instructions until it can start the new one.

More advanced CPUs with out-of-order execution (every non-mobile/non-embedded CPU nowadays) will pull in a few more instructions and only start those that don't need to wait on data. The details of out of order execution is too complex to fully explore in this answer.

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


title: Interrupt driven I/0 handling

text:
# Question
Title: Interrupt driven I/0 handling
Suppose in an architecture, interrupt driven IO is used. And suppose a program is to be loaded from an IO device into the RAM. I have been studying IO mechanisms and I came to know that upon receiving a request to load a program, the processor generates control signals to the IO module and then the data is loaded into the IO module interface buffer. When its done loading, it will generate an interrupt to CPU.

But how does a complete file or program gets transferred to RAM? I mean does the processor issues requests only for a byte/word transfer at a time and the interrupt is raised each time a word gets transferred from io device to module? Or is it something else? Please help me understand.

# Answer
I modern architectures the peripheral has direct access to the system RAM independent of the CPU and what it is executing. This is called a DMA (direct memory access) transfer.

In other words when the interrupt is raised the entire transfer is already completed and you can read the data transferred.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Construct binary palindrome by repeated appending and trimming
I was reading an article on Construct binary palindrome by repeated appending and trimming. The problem is Given n and k, Construct a palindrome of size n using a binary number of size k repeating itself to wrap into the palindrome. The palindrome must always begin with 1 and contains maximum number of zeros.

I solved the problem using this algorithm-

1. I will declare a string of size n with all the entries 0.
2. Leftmost character has to be 1, so to be a palindrome rightmost should also be a 1 .
3. Now after every k-1 places starting from start, I will put a 1.
4. And before every k-1 places starting from end, I will put a 1.

This algorithm has O(n) runtime. Is there anything wrong with this algorithm?

In the article, They have declared an array of size n, and then laid the index of the k sized binary to hold into an array, for example if n = 7, k = 3 arr becomes \[0, 1, 2, 0, 1, 2, 0\]. And then connected the indices of the k sized binary which should be same by going through the property of palindrome which is kth and (n – k – 1)th variable should be same. And then they apply dfs on 0. For more clearance, please see the article above.

We already know which nodes would be connected to index 0 (that I have done in my algorithm), then why are we connecting all the indices ?

Is there something, I am missing?

# Answer
I suspect that when n is not a mutiple of k then you may not get the desired wrapping effect.

In particular, let me interpret "after every k places from the start" as "the (k+1)th position in the array" - assuming 1-based indexing. Then in the given example on that page, with k = 4 and n = 10, your algorithm produces `1 0 0 0 1 1 0 0 0 1` \- which is not a 4-length binary string being repeated and wrapped off at the end (the right answer would be `1 1 0 0 1 1 0 0 1 1`.

If I am off-by-one on interpreting "k places from the start" (so say you were refering to the kth position), then even with n = 5 and k = 3 we get `1 0 1 0 1`, whereas the right answer would be `1 1 0 1 1`.
> 1 votes

---
Tags: algorithms, graphs, strings
---


title: Fair division of two-dimensional cake

text:
# Question
Title: Fair division of two-dimensional cake
I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division).

In contrast to the well-studied cake-division problem, land-division is two-dimensional, i.e., the preferences of the users may vary both horizontally and vertically. Therefore, it is not practical to limit the algorithm to parallel cuts.

The only reference I found so far is Karthik Iyer and Michael Huhns, 2007. They say that "We have not come across any constructive (algorithmic) solutions so far to the generic land division problem. All the papers have offered existential solutions to qualified versions of the problem."

They themselves prove an O(n^2) algorithm for proportional land division, with certain limitations (e.g. each of the n agents must mark n rectangular regions with utility 1/n, and if the rectangles don't overlap too much, the algorithm guarantees that each agent gets one of its rectangles).

Do you know of any newer references on this problem? I am interested specifically in practical algorithms, and they may be approximate.

# Answer
> 3 votes
The authors you cite have another paper on the topic.

Would you be satisfied with a model which assumes that the properties of the surfaces to be allocated can be summarized by an arbitrarily large but finite set of one-dimensional parameters (say length, depth, northmost point, eastmost point,... really as many as you want but finite) ?

If this is satisfying to you, and you are ok with assuming that people have preferences over surfaces as described by the values of these parameters, you might find useful insights in the theory of fair allocation of bundles of multiple goods. A great (and free) introduction is "Fair Allocation Rules" by William Thomson.

Of course when the dimensions represent parameters describing the shapes to be allocated, you are likely to have unusual preferences which are hard to work with and do not fit nicely with the existing results. Might be worth giving it a try though...

# Answer
> 2 votes
I suppose you could address the issue by reducing the dimensionality of the problem. For example, you could divide the land into discrete areas (either manually or using a suitable algorithm). Then you could use any discrete one dimensional algorithm like the Sealed bid method described in http://www.colorado.edu/education/DMP/fair\_division.html .

# Answer
> 2 votes
I did not find a suitable answer, so I had to write one myself. It was the first part of my Ph.D. thesis. There are still a lot of open questions in this field.

---
Tags: reference-request, game-theory
---


# Question
Title: How curves are represented in a computer
I am confused now (in thinking about limits and continuity) how curves are represented in a typical modern computer. Curves are "continuous" in that there is no discrete change from one angle to the next. Wondering how the computer approximates this and/or what equations it uses/approximates.

# Answer
A curve can be quantized (also known as rasterized) to a certain precision after which it is discrete, and the issue is gone. If you see a picture that contains a curve on a modern computer, there's a good chance it already has been rasterized (e.g. PNG or jpeg).

However, it is possible to represent curves (and other primitives) directly. Then you're looking at vector graphics. In most implementations of vector graphics only a couple specific subsets of curves are supported, most often circles, ellipses and **Bézier curves**. Especially the latter is the most common powerful generic way of storing curves.

It is possible to describe an arbitrary curve through some mathematical framework and storing the mathematical description of the curve. But such a generalized approach is rarely done for computer graphics.
> 4 votes

---
Tags: graphics
---


# Question
Title: List points with integer coordinates on a scaled standard simplex
Given two positive integers:

* $d \in \mathbb{N}^+$ space dimension
* $s \in \mathbb{N}^+$ expected sum

list all the points $(x\_1, .. x\_d) \in \mathbb{N}^d$ such that $$\sum\_{i=1}^d x\_i = s$$

Expected output:

* For $d = 2$ and $s = 3$ the algorithm should output (3, 0), (2, 1), (1, 2), (0, 3).
* For $d = 3$ and $s = 1$ the algorithm should output (1, 0, 0), (0, 1, 0), (0, 0, 1).

What is the most efficient algorithm to achieve this?

# Answer
> 3 votes
Hint: let's say $f(d, s) = \mathbb{N} \times \mathbb{N} \to \mathbb{N}^{d}$ is the solution to your problem. Then you have recursive solution:

$$f(d, s) = \bigcup\_{k=0}^s \left \[ (k) \times f(d-1, s-k)\right\]$$ $$f(1, s) = (s)$$

Where $(k)$ is the unary tuple containing $k$ and $\times$ is the Cartesian product.

---
Tags: algorithms
---


# Question
Title: Optimal strategy in repeated cake-cutting
Alice and Bob play the famous game of divide and choose $n$ times with $n$ identical cakes. Each time, Alice cuts the cake to two pieces, and Bob chooses the piece he prefers. Alice does not know Bob's preferences, but she assumes that they come from a uniform distribution.

**What is the strategy that maximizes Alice's expected total value?**

Here is my solution so far.

Let's assume that the cake is the interval $\[0,1\]$. Alice cuts the cake by choosing some $x\in \[0,1\]$. Let $h\in\[0,1\]$ be a point such that Bob is indifferent between the cake to the left of $h$ and the cake to the right of $h$. Let $V(x)$ be Alice's valuation of the interval $\[0,x\]$; it is a continuous and increasing function of $x$. Then:

* If $h\> x$, then Bob picks $\[x,1\]$ and Alice gets $\[0,x\]$ and gains $V(x)$.
* If $h\< x$, then Bob picks $\[0,x\]$ and Alice gets $\[x,1\]$ and gains $V(1)-V(x)$.
* If $h=x$ then, let's say Bob picks a piece at random so Alice gains on average $V(1)/2$.

If Alice knows $h$, then she has a simple optimal strategy:

* If $V(h) \> V(1)-V(h)$, then select $x^\* = h-\epsilon$, for some $\epsilon\>0$, and gain $\approx V(h)$.
* Otherwise, select $x^\* = h+\epsilon$, for some $\epsilon\>0$, and gain $\approx V(1)-V(h)$.

Initially, Alice does not know $h$, so she assumes it is distributed uniformly in $\[0,1\]$. If Alice cuts at $x$ and Bob chooses left, this tells Alice that $h\in\[0,x\]$; if Bob chooses right, this tells Alice that $h\in\[x,1\]$. So, using binary search, Alice can estimate $h$ to an arbitrary precision. This seems to be an optimal strategy when $n\to\infty$: spend a lot of rounds initially for getting an accurate estimate of $h$, and use this estimate from then on to get the optimal possible value.

I am stuck at the case where $n$ is finite and small. The question bogs me even for $n=2$: what is the optimal first cut?

# Answer
> 4 votes
Let $v(x) = \frac{V(x) - V(0)}{V(1) - V(0)}$ so $v(x)$ nicely goes from $0$ to $1$. Maximizing $v$ also maximizes $V$. To cover my ass for future mistakes regarding $\<$ vs $\leq$, I will assume that you will never exactly guess $x = h$.

Now, if $n = 1$, we can find the expected value from cutting at $x$ by integrating over all possible $h$:

$$e\_1(x) = E\[v(x)\] = \int\_0^x (1 - v(x))dh + \int\_x^1 v(x)dh = (1 - 2x)v(x) + x$$

Which allows you to maximize $e\_1$ with differentiation to find the optimal $x$. Note that in the above example "all possible $h$" meant $\[0, 1\]$. But what if we know that $h \in \[a, b\]$ due to previous information?

Then we get the following sum of integrals for when also $x \in \[a, b\]$:

$$\int\_a^x (1 - v(x))dh + \int\_x^b v(x)dh = (a + b - 2x)v(x) - a + x$$

Which makes the total expected valuation:

$$e\_{1,a,b}(x) = E\[v(x) | a \leq h \leq b\] = \begin{cases} v(x) & \text{if $x \< a$}\\ (a + b - 2x)v(x) - a + x & \text{if $a \leq x \leq b$}\\ 1 - v(x) &\text{if $x \> b$} \end{cases}$$

Now let's analyze $n = 2$. Suppose our first cut is at $x$, then there is a $x$ chance $h \leq x$ and $1 - x$ chance $h \geq x$. In both those scenarios we will then choose our best possible $y$. This gives equation:

$$e\_2(x) = e\_1(x) + x\left( \max\_{0 \leq y \leq 1} e\_{1,0,x}(y)\right) + (1-x)\left( \max\_{0 \leq y \leq 1} e\_{1,x,1}(y)\right)$$

$$\max\_{0 \leq y \leq 1} e\_{1,0,x}(y) = \max\left(\max\_{0 \leq y \leq x} ((x - 2y)v(y) + y), \max\_{x \leq y \leq 1} (1 - v(y))\right)$$

$$\max\_{0 \leq y \leq 1} e\_{1,x,1}(y) = \max\left(\max\_{0 \leq y \leq x} v(y), \max\_{x \leq y \leq 1} ((x + 1 - 2y)v(y) - x + y)\right)$$

Now let's say $v(x) = x$, a simple linear increase in desire for more cake. Now we can actually solve:

$$\max\_{0 \leq y \leq 1} e\_{1,0,x}(y) = \max\left(\begin{cases}x(1-x)&0\leq x \leq \frac{1}{3}\\\frac{1}{8}(x+1)^2&\frac{1}{3} \leq x \leq 1\end{cases}, 1 - x\right)$$

$$\max\_{0 \leq y \leq 1} e\_{1,x,1}(y) = \max\left(x, \begin{cases}\frac{1}{8}(x-2)^2&0\leq x \leq \frac{2}{3}\\x(1-x)&\frac{2}{3} \leq x \leq 1\end{cases}\right)$$

Now $e\_2$ is complicated, but is essentially a piecewise function which can be solved.

---
Tags: game-theory
---


# Question
Title: Cover k edges to minimize the length of the longest uncovered path in a tree
> You are given a **tree** $G\langle V, E\rangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path's length)
>
> Constrains: $O(n\log n)$ time and $O(n)$ space.

Now, the scheme of the algorithm is kinda obvious (from the given constrains). We need to priorities the edges and pick the highest $k$-edges (technically, we throw all edges to a priority queue and pick the first $k$)

So, I think, the keys should tell us how centric the edge is.

My first attempt was BFSing the graph from some node and BFSing again from the most distant node of the first scan.

Each node will get two values: distance from the first starting node and distance from the second starting node.

Though, I'm not sure how well this method grasp the notion of *centric*.

I'd be glad to hear your thoughts about the current idea or your own ideas.

# Answer
> 6 votes
*(This answer expands on Albert Hendriks' approach from the comments.)*

**First idea:** let us turn the problem around. As stated, we fix the number of covered edges, $k$, and minimize the maximum length of an uncovered path $d(k)$. Instead, let us fix the maximum length of an uncovered path, $d$, and minimize the number of covered edges $k(d)$.

Suppose now we can calculate $k(d)$ in $O(n)$. Then the original problem can be solved in $O(n \log n)$. Indeed, note that both $d(k)$ and $k(d)$ are non-increasing functions. To answer the question "what is $d(k\_0)$?", we can find the minimum $d\_0$ such that $k(d\_0) \le k\_0$. And that can be done in $log (n)$ calculations of $k(d)$ by doing a binary search for the right $d$ with the obvious bounds of $\[0, n-1\]$.

---

What's left is to, given a fixed value $d$, calculate $k(d)$ in $O(n)$.

**Second idea:** we can select an arbitrary vertex as the root, run a depth-first search from the root, and make decisions about covering edges in depth-first search order.

Let us visit a vertex $v$ in our depth-first search. We recursively visit all its children in any order. After visiting child $u$, we assume that we have dealt with all uncovered paths longer than $d$ in $u$'s subtree. We also know the length $\mathrm{dfs}(u) \le d$ of the longest uncovered path from $u$ to the vertices of its subtree. The longest uncovered path from $v$ to the vertices of $u$'s subtree has an extra edge $v - u$, so its length is $r = \mathrm{dfs}(u) + 1$.

**(I)** Obviously, if $r \> d$ (it can only be $d + 1$), we have to cover some edge on the long path we found. Since the whole subtree of $u$ is already dealt with, it makes sense to cover an edge which is the closest to the complement of the subtree of $u$ in the whole tree, which is the edge $v - u$.

**(II)** But there's more to consider. A path can go from the subtree of one of our children, via our vertex $v$, to the subtree of another child. And if such path has length greater than $d$, we have to cover an edge on it.

To find such paths, for our vertex $v$, we store the maximum length of an uncovered path into a child's subtree we have so far. Let this stored length be $s$, initially zero. After each child $u$ we visit, check whether $r + s \> d$. If so, let us cover the edge to the longest of $r$ and $s$, so the new maximum length of an uncovered path becomes $s\_{\textit{new}} = \min (s\_{\textit{old}}, r)$. If $r + s \le d$, we don't yet have to cover anything, and the new maximum length is $s\_{\textit{new}} = \max (s\_{\textit{old}}, r)$.

Note now that, with such implementation, case (I) is covered by case (II). In particular, if we don't yet store a path in a child's subtree, the stored value just adds a length of $0$.

When we finish visiting all children of $v$, the stored value $s$ is the length of the longest remaining uncovered path from $v$ to the vertices of its subtree. In particular, if $v$ is a leaf, the value $s$ remained zero. We can now return this value as $\mathrm{dfs}(v)$.

The remaining question is, if we don't cover an edge using the algorithm above, could it have helped us later if we had in fact covered it? The answer is no: such a cover could safely be moved at least one step closer to the root of the tree, without altering other covers.

---

In pseudocode, with a bit more low-level details than the explanation above. Assume the vertices are numbered `0`, `1`, ..., `n-1`. We select vertex `0` as the root (recall that the root can be arbitrary), and just call `dfs (0, -1)`.

```
dfs (v, p):                            // v is current vertex, p is its parent
    {s, w} := {0, -1}                  // maximum path of length s into child w's subtree
    for u in adjacent[v]:              // all neighbors of v...
        if u != p:                     // ...except its parent, if it has one
            r := dfs (u, v) + 1
            if r + s > d:              // we have to cover the longest...
                if r > s:
                    cover (v, u)
                else:
                    cover (v, w)
                    {s, w} := {r, u}   // ...and possibly update to shortest
            else:
                if r > s:
                    {s, w} := {r, u}   // here, update to longest
    return s                           // length of the longest remaining path

```

As we can see, `dfs (v, p)` returns the length of the longest uncovered path from $v$ to the vertices of its subtree.

So, we set the value `d` (to the pseudocode, it acts as a global variable), run `dfs`, and track the number of covered edges as the total number of calls to the `cover` function. The `cover` function may actually record the covered edges if need be, but at the very least, it increases the counter `k` by `1`. If the edges themselves are not needed, we can drop the variable `w` too, and leave only `s` from the tuple `{s, w}`.

For the original problem, do the above in a binary search over the possible values of `d` to get the full solution.

---
Tags: algorithms, graphs, trees
---


# Question
Title: How to specify a robot go always right relative to itself from absolute perspective (north west east south)
I have a robot that has a start and goal position within a maze. Each point in the maze-grid is simply a Position object containing x and y. I need an algorithm that specifies the robot only moving to its relative right only using goEast, west, east and south from the perspective of the maze. There is an implementation already (with uml and mathod names) that does not support degrees or heading. Just current position, next position and then directions in absolute terms. And the logic that goes for the robor for going only to it's relative right.

# Answer
> 0 votes
I'm not sure what the difficulty is, here. If the robot is facing north, its right is east; if the robot is facing east, its right is south; etc.

# Answer
> 0 votes
As suggested in another comment, a viable solution would be to keep track of the heading of your object.

Your goEast function would look something like this:

```
while(heading != south)
    turn right 90 degrees

```

Same thing for the rest of the directions

---
Tags: algorithms, logic, object-oriented, adjacency-matrix
---


title: Independence Implies P $\ne$ NP

text:
# Question
Title: Independence Implies P $\ne$ NP
Suppose P vs. NP is independent of ZFC. Then there cannot be an efficient SAT solver, otherwise it would constitute a proof for P = NP. Therefore P $\ne$ NP.

What we see here is that independence implies unequality. So why is independence a big deal? It is just one way to show P $\ne$ NP. See Scott Aaronson's paper *Is P Versus NP Formally Independent?*.

# Answer
> 1 votes
As Yuval Filmus comments, your argument is flawed: just because a given algorithm *is* a SAT-solver doesn't mean that we can *prove* that it is a SAT-solver.

*Technically, the same issue applies to the time bound - we can cook up a Turing machine which always runs in polynomial time iff ZFC is consistent - but this is easily avoidable: given a Turing machine $T$ and a polynomial $p$, we can form a machine $T\[p\]$ which behaves like $T$ except with the time bound $p$ artificially imposed: on input of length $n$, $T\[p\]$ simulates $T$ for $p(n)$-many steps and diverges if it hasn't halted within that time. We **can** decide whether a machine $S$ has the form $T\[p\]$ for some $T, p$, so if $T$ happens to be a SAT solver which operates in polynomial time $p$, then $T\[p\]$ is a polytime SAT solver which we can prove operates in polynomial time. The culprit is "is a SAT solver," for which there doesn't appear to be a similar trick.*

The issue here is **logical complexity**. "Undecidability implies truth" holds for statements with *verifiable counterexamples*; these are the $\Pi^0\_1$ statements.$^\*$ The Goldbach conjecture is a good example: in order to be false, there would need to be a counterexample, and being a counterexample to Goldbach is an easily checkable property since it only relies on "bounded quantifiers." By contrast, the Twin Primes Conjecture is a priori merely $\Pi^0\_2$, and so at the moment we don't have any reason to believe that its undecidability from (say) PA would imply its truth.

Even in the $\Pi^0\_1$ context, however, undecidability is more than just a method for proving a statement. It establishes that the principle is true "for deep reasons" in some sense. If a statement $P$ about the natural numbers$^{\**}$ is true but not PA-provable, this means that the *reason* $P$ is true is more complicated than just our simple intuitions about induction, since PA already incorporates the full arithmetical induction scheme. Now whether one consider this a worthwhile observation depends on one's particular interests, but it (and even weaker independence phenomena) is certainly noteworthy to me.

---

$^\*$This is in fact an exact characterization, in the following sense. If $S$ is a reasonable theory of arithmetic, and the independence of $P$ from $S$ implies the truth of $P$, then $P$ is equivalent to the statement "$P$ is not provable from $S$" (part of "reasonable" here is *soundness*). But this latter statement is $\Pi^0\_1$. Now this is actually silly - every sentence is either equivalent to $0=0$ if true or $0=1$ if false - but it can be "de-sillified" by phrasing it as: if $T,S$ are reasonable theories and $T$ proves that $S$ is consistent and that if $P$ is $S$-undecidable then $P$ is true, then $T$ proves that $P$ is equivalent to the $\Pi^0\_1$ sentence "$P$ is not $S$-disprovable."

$^{\**}$Or a statement *interpretable as a statement* about the natural numbers; e.g. "P=NP" is a statement about Turing machines, but by the usual techniques is "faithfully translateable" into the language of arithmetic.

---
Tags: p-vs-np
---


title: Byte/word addressing

text:
# Question
Title: Byte/word addressing
I am confused on byte addressable/word addressable architecture.

I have studied MIPS implementation and I came to know that when the data is retrieved from main memory, it is shifted accordingly to convert it into a byte. But if this is the case, why do we need byte addressable? We can simply fetch a word shift it and operate on its 8 bits.

Or is it that the byte addressable architecture requires multiplexers to select a byte from a 32/64 word fetched from memory?

Please help me out.

# Answer
In simple implementations, byte addressable is more important for writes than for read. Because, with RAM, you read all 32 or 64 bits then steer data with a multiplexer. For writes, you need to be able to selectively update each part. (An alternative, in early DEC Alpha processors, was not to provide any byte wide access instructions, they eventually added these 8/16 bits accesses in later models)

In a less ideal world, several issues may need to be considered:

* Some I/O ports may have side effects on reads, so that it is important to know whether each individual byte is read.
* With EDC memory (error detection and correction), you cannot read or write only a byte, as error detection and correction is only efficient when handling at least 32 or 64 bits at once.
> 1 votes

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


# Question
Title: Is k -rainbow coloring of a hypergraph NP-complete or not?
\**A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Is k-rainbow coloring of a hypergraph is NP-complete or not? The problem is also called "polychromatic coloring" \**

I looked at some reference papers such as "Hardness of Rainbow Coloring Hypergraphs by Venkatesan Guruswami and Rishi Sakety" and "Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs by Venkatesan Guruswami and Euiwoong Lee". But these are the only reference I found discuss the problem but the authors foucs on generating balance rainbow coloring for K-uniform hypergraph where each color has to appear the same number of times in the hypergraph. It has been proved that K-rainbow coloring for planer graph is P for K= 2 and NP complete for K=3,4 according to this reference "Polychromatic Colorings of Plane Graphs".

My question " Is k-rainbow coloring of a hypergraph NP-complete or not?" in general for any hypergraph. I think this problem is related to vertex cover problem.

# Answer
> 4 votes
Deciding if a hypergraph can be rainbow colored in $k$ colors is NP-complete for every $k \geq 2$. A proof is given in \[1, Theorem 12\].

For $k=2$, the result follows immediately by observing the problem is equivalent to set splitting (also known as hypergraph 2-coloring). For $k \geq 3$, the authors of \[1\] give a reduction from chromatic index on $k$-regular graphs.

---

\[1\] M. Koivisto, P. Laakkonen, and J. Lauri. "NP-completeness results for partitioning a graph into total dominating sets". In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON), volume 10392 of Lecture Notes in Computer Science, pages 333-345. Springer, 2017.

---
Tags: complexity-theory, discrete-mathematics
---


# Question
Title: Is the union of NP Complete language and a finite language (in P) NP Complete?
Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?

# Answer
> 2 votes
The answer is yes, and this is a special case of the following statement:

Let $X$, $Y$ be non-trivial languages (ie either empty nor everything) such that the symmetric difference $(X \setminus Y) \cup (Y \setminus X)$ is finite. Then $X \leq Y$ (linear time, constant space manyone reduction).

The reduction just tests whether the input is any of the finitely many values in $(X \setminus Y) \cup (Y \setminus X)$ and proceeds in a hard-coded way there. This takes constant time+space. Otherwise, it copies the input, since $X$ and $Y$ will agree there.

How to use this: For NP-hardness of $A \cup B$, set $X := A$ and $Y := A \cup B$. For NP-membership of $A \cup B$, set $X := A \cup B$ and $Y := A$. Note that the symmetric difference of $A$ and $A \cup B$ is included in $B$, hence if $B$ is finite, so is the symmetric difference.

---
Tags: complexity-theory, np-complete, closure-properties
---


# Question
Title: Can the subset sum problem work with an undefined set?
To give a brief outline of my actual problem, I'm attempting to identify possible impurities in proteins. I have a theoretical mass and an experimental mass, and the difference between the two would in theory be caused by any impurities present in the proteins. Impurities could take the form of an amino acid insertion, an amino acid deletion, an amino acid substitution, or an amino acid modification (modifications can both add and subtract mass).

Every impurity can be associated to a known change in mass, so I want to use the subset sum problem to get all subsets of impurities that add up to the delta mass. My issue is that I'm working with an undefined set. I know what impurities I can have, but I don't know how many of each I can have.

Is it possible to get the subset sum problem to work with an undefined set such as this? Is there a better algorithm I could implement to solve the issue?

# Answer
> 1 votes
If you only have *extra* impurities, then the DECOMP program described in the following paper will efficiently solve the problem -- even if you only have an approximate mass difference $d$ to work with:

DECOMP--from interpreting Mass Spectrometry peaks to solving the Money Changing Problem (Böcker S., Lipták Z., Martin M., Pervukhin A., Sudek H. 2008)

The paper cites earlier papers by the same authors that describe the underlying Round Robin algorithm -- a very nice and fast algorithm based on Frobenius numbers for solving a problem that people previously resorted to tables computed using brute-force to solve.

To deal with "negative impurities" (components that should be present but are absent from the experimental sample), I think your best option is to try all possible "missing mass" values $a$ in a small range that includes zero, and for each such value $a$, use DECOMP to solve two problems: One that finds all possible combinations of "missing" components that solves for $a$, and one that finds all possible combinations of "extra" components that solves for $d+a$. Every pair of (missing, extra) component multisets is then a solution for the chosen $a$.

Bear in mind that, if there is a subset of components that sums to zero, then there will be an infinite number of solutions, since it is always possible to add another copy of this component subset to a solution to get another valid solution.

---
Tags: subset-sum
---


# Question
Title: What does floating point biased notation have to do with 2's complement?
During lecture the professor talked about Integer Compare for floats and kept mentioning two's complement.

What's the relation between them?

All I understand is that two's complement can take us from a number to its negative.

# Answer
IEEE 754 Floating point is a standard way of representing fractions in binary which does *not* use two's complement. There's a discussion here about why that is.
> 2 votes

---
Tags: computer-architecture, floating-point
---


# Question
Title: What does "cavallier extension claim" in The Algorithm Design Manual mean
I have been reading the Algorithm Design Manual by Steven S. Skienna and on page 15 it mentions a term called "cavallier extension claim" and I have been desperately trying to find a definition for this. A search in Google just returns quotes of the same book.

Possibly my confusion lies in the misspelling of the word "cavallier", which seems like it should be spelled "cavalier", unless it was the name of some French mathematician or some other concept that I am missing.

**Update**

As requested here is the context. First he talks about *boundary errors* in inductive proofs and then this:

> The second and more common class of inductive proof errors concerns cavallier extension claims. Adding an extra item to a given problem instance might cause the entire optimal solution to change.

# Answer
> 4 votes
The phrase means "cavalier" in the ordinary English sense of the word, i.e., it is talking about a claim in a proof that is made carelessly. Without more context or examples I'm not sure exactly what pattern of flawed proof it is referring to, but it has something to do with making an assumption/claim (without justifying it) that the solution for $n+1$ is related to the solution for $n$ in a particular way.

"Cavallier extension claim" is not a technical phrase. It's just some English that the author is using.

---
Tags: algorithms
---


# Question
Title: Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?
Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case?

Even in the case of a reversely sorted list, it's not like it'll have to compare each element with all the other elements. For example in `[4, 3, 2, 1]`, 4 won't be compared with anything. 3 will only be compared with 4. 2 will be compared with 4 and 3 but not 1. And only 1 will be compared with all the other 3 items.

How is this O(n^2) and not O(nlogn)? What am I missing here?

My implementation of Insertion Sort:

```
const insertionSort = (arr) => {
  for (let i of arr) {
    for (let x = arr.indexOf(i) - 1; x >= 0 && arr[x] > i; x--) {
      arr[x + 1] = arr[x];
      arr[x] = i;
    }
  }

```

# Answer
On an array of length $n$ which is reversely sorted, the first element would be compared to 0 elements, the second element to 1, the third element to 2, and so on. In total, the number of comparisons will be $$ 0 + 1 + 2 + \cdots + (n-1) = \\ \frac{1}{2} \bigl((0 + 1 + 2 + \cdots + (n-1)) + ((n-1) + \cdots + 2 + 1 + 0)\bigr) = \\ \frac{1}{2} \bigl((0 + (n-1)) + (1+(n-2)) + (2+(n-3)) + \cdots + ((n-1)+0)\bigr) = \\\ \frac{1}{2} \bigl(\underbrace{(n-1)+(n-1)+(n-1)+\cdots + (n-1)}\_{\text{$n$ times}}\bigr) = \\ \frac{n(n-1)}{2}. $$ This number scales like $n^2$.
> 1 votes

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


# Question
Title: Efficiently find elements which are out of place in an otherwise sorted list
I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the value in `Col B` breaks chronology in the column.

**Structure**

```
    *    Col A    *    Col B    *
    *    Opened   *    Moved    *
Row * --------------------------*
 1  * 06/20 10:00 * 06/22 08:10 *
 2  * 06/20 10:30 * 06/22 08:40 *
 3  * 06/21 10:00 * 06/22 08:30 *
 4  * 06/21 11:00 * 06/22 08:50 *

```

The table is sorted on `Col A`, from smallest to largest.

The rule is that the oldest open item should be moved first.
Thus, moving some arbitrary item that **isn't** the oldest open item is illegal.

**Example**

The item in row 3 was moved at 08:30, but at that time there was an older item (row 2) that should have been moved first. That means that row 3 represents an illegal operation and should be marked or returned.

**My case**

My data set is in the range of millions of rows. I need an accurate method for finding these illegal operations, but I am a little stuck on how to approach the problem.

The most workable idea I've had so far, I think, is to build a helper column where the data from `Col B` is sorted lowest to highest, compare this step by step with the original column, and shift the data downwards every time the data doesn't match. This will leave the helper column with blanks indicating illegal operations in the corresponding row in the original dataset.

Another idea was to compare the current, preceeding and following dates - but this has seemingly expensive weaknesses. Although rare it's conceptually possible that several illegal operations can immediately follow each other, meaning that I have to compare some arbitrary higher number of dates (let's say 15 instead of 2 (the preceeding + following)) for each step in a loop.

While one of these sub-optimal ideas probably will do the work, in the sense that the job gets done eventually, I struggle with the thought that there isn't a better way to solve this.

# Answer
If I'm understanding the problem correctly, you have a list that's supposed to be monotonically increasing (aka sorted), and need to discard any items that break this rule. The trick being, an item that's greater than its predecessor might still be invalid, if its predecessor was invalid.

I'm going to make one additional assumption: the first row is always correct. (Because I don't see any way it could be wrong, and if there is, you can check that by hand in $O(1)$ before running.)

If this is correct, then here's how I would solve it.

```
define FlagBadItems(timestamps[0..n]):
    last_good = timestamps[0]
    for item in timestamps[1..n]:
        if item < last_good:
            flag item as bad
        else:
            last_good = item

```

In other words, we keep a variable called `last_good` which is the last timestamp we know to be correct. Each row is considered bad if it's lower than `last_good`. If it's bad, `last_good` remains the same, otherwise, `last_good` is updated.

This runs in $O(n)$, since there's a single run through the data set, with constant work per iteration. The space complexity is $O(1)$ for overhead plus $O(n)$ for your input list.
> 3 votes

# Answer
Each date represents an event: either something was opened, or something was moved. Thus, if you have $n$ rows in your table, there are $2n$ events.

Sort the events, and scan through them in linear order. Keep track of the set of open items as you go. Each time you hit a "moved" event, you can calculate which was the oldest open item (using that set), and check whether that was the one that was moved or not. In this way, you can find invalid "moved" events.
> 0 votes

---
Tags: algorithms, sorting, efficiency
---


title: Question on time hierarchy

text:
# Question
Title: Question on time hierarchy
How can I prove that $\mathsf{DTIME}^{\mathrm{Htm}}(n^2)$ is contained in $\mathsf{DTIME}^{\mathrm{Htm}}(n^3)$?

(sorry about how it is written. I mean the set of languages decided by a deterministic TM with an oracle to $\mathrm{Htm}$ in $n^2$ time and $n^3$ time).

If someone can please write the proof, it will be great.

# Answer
> 1 votes
A language is in $\mathsf{DTIME}(f(n))$ if there is a Turing machine accepting the language and running in time *at most* $f(n)$ (or, in some definitions, $O(f(n))$). Therefore $f(n) \leq g(n)$ implies that $\mathsf{DTIME}(f(n)) \subseteq \mathsf{DTIME}(g(n))$. The same holds for relativized classes.

---
Tags: complexity-theory, time-complexity, complexity-classes, oracle-machines
---


title: Restrictions needed on ADT for totality

text:
# Question
Title: Restrictions needed on ADT for totality
In the paper Total Functional Programming by D.A. Turner three rules are given for a programming language to remain total:

1. complete case analysis
2. covariant type recursion (type constructor should not appear in negative position in a constructor argument)
3. structural recursion

But with these rules I can still have an infinite loop:

```
data Fix f = Fix (f (Fix f))
data Bad r = Bad (r -> r)

bad :: Fix Bad -> Fix Bad
bad b =
  case b of
    Fix t ->
      case t of
        Bad f -> f b

nonTotal = bad (Fix (Bad bad))

```

Where is my mistake? Should all type variables also only appear covariantly? Or is the "covariant type recursion" condition more strict?

# Answer
> 2 votes
The constraint

> 2. covariant type recursion (type constructor should not appear in negative position in a constructor argument)

excludes this

```
data Bad r = Bad (r -> r)
                  ^    ^--- positive position
                  ^-------- negative position

```

Indeed, *all* the occurrences of `r` must appear in positive position.

> Should all type variables also only appear covariantly?

Yes, precisely.

Essentially, your `Fix Bad` tries to generate a type $T$ isomorphic to $T \to T$. If we had that, we would have a model of the untyped $\lambda$ calculus, where terms are not normalizing ("terminating") in general.

Indeed, to apply any two terms $x, y : T$ we can exploit the isomorphism to treat $x$ as if $x : T\to T$, at which point the application $x y$ becomes feasible. As a special case, we also obtain $xx$, hence $\Omega = (\lambda x.xx)(\lambda x.xx)$ which is the archetypal non normalizing term.

To conclude let me point out that, in some advanced calculi with dependent types, covariant recursion is not enough, and you need an even stricter constraint called "strict positivity". Without that, contradictions arise. In Haskell-like languages, covariance (and the other constraints you mention) should suffice.

---
Tags: type-theory, inductive-datatypes, abstract-data-types
---


# Question
Title: Given a Turing machine M, is there a TM that computes the number of states M has?
I've seen it used but I can't think of a way to construct such TM. Would appreciate any help!

# Answer
I think you are a bit confused about TMs. A Turing machine, by canonical definition (as found in textbooks like \[Sipser 1996\], \[Papadimitriou 1982\] and \[Hopcroft and Ullman 1979\], as well as on Wikipedia), is a 7-tuple, one of which is $Q$, the set of states. So, the set of states of a Turing machine is *not* computed; it is part of the definition of a TM.

In case of a universal TM, the input to the TM is the encoding of another TM (as well as its input). If you are familiar with functional programming, this is similar to a meta-circular evaluator (it is also similar to the `eval` function in some programming languages).

So, an encoding of a TM should encode all 7 elements that comprise the TM. Which means that a correct encoding of a TM must encode an enumeration of the set $Q$. Now, you can construct another TM that operates on the encoding of TMs (again, if you have done FP, it is similar to higher-order functions in FP).

If you know the encoding used, it should be trivial to retrieve the set of states of the input TM. You do need to count the number of elements in that set, but that should be Turing computable (because the set of states has to be finite). Now you have a TM that computes the number of state that another TM has.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Prove or disprove those languages are regular
in my practice for a test I came across this question: prove or disprove that those languages are regular:

I succeeded proving that the second language is nonregular with homomorphism but i'm having trouble with the other 2 -

1. my intuition tellin me that first 1 is Σ∗ but i'm really stuck on how to prove it
2. (not sure why it writes 2 when i'm writin 3 haha) in this one i'm really stuck - my intuition is tellin me again that it will be finite automaton (automata? sorry if my english is not so good) and therefore regular language but how can I prove it? how can I use the fact that |w| is bounded? - i guess I need to build an automaton , maybe with some "flags" but I suck at it (for now) :\[.

does ww^R is regular language when |w| is bounded? I've looked a lot (through google in this site) for an answer for this question but I havent find something - only that this language is not regular when |w| is not bounded.

Can I get some hints on both of those languages please?

# Answer
> 2 votes
For number 1, you're entirely correct. Every string in $\Sigma \*$ is in this language. Take an arbitrary string of zeroes, ones, and twos, then let $y$ be that string, and $w$ be empty.

For number 2, the standard way I learned to prove it's not regular is with "fooling sets". The Pumping Lemma also works here.

For number 3, consider that there are only finitely many possibilities for $w$. This means you could, in theory, write a regular expression that just listed all of them. So this one is actually regular, through "brute force".

---
Tags: regular-languages
---


# Question
Title: Linked List in Maximal Scoring Subsequences Algorithm
For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, when doing the search for the rightmost value of $j$ that satisfies $L\_j \< L\_k$, we can search a linked list with monotonically decreasing $L\_j$ values.

I'm slightly confused on how this works. If we store a pointer to the element $j$ we found during Step 3, then we must start iterating with *some* element in Step 1. What element would operate as the head of the linked list in this case? In other words, in Step 1, instead of searching through the whole list, what element do we start searching with?

I found these lectures notes easier to read than the actual paper. I also implemented a $O(n^2)$ version of the algorithm in Go here, which anyone may use to reference. However, I would like some help cutting the complexity down to $O(n)$. Any help would be appreciated!

# Answer
> What element would operate as the head of the linked list in this case?

That's of course $L\_{k-1}$.

If you are surprised why this works in $O(n)$, that paper has already explained:

> Once a list element has been by-passed by this chain, it will be examined again only if it is being deleted from the list, either in Step 2 or Step 4. The work done in the “reconsider” loop of Step 4 can be amortized over the list item(s) being deleted. Hence, in effect, each list item is examined a bounded number of times, and the total running time is linear.

---

Let's consider the example given in the paper. The sequence is $(4, -5, 3, -3, 1, 2, -2, 2, -2, 1, 5)$. The list is initially empty. The first subsequence $(4)$ comes, we keep a pointer to the head of the list, like

```
H <- (4)

```

Next, we sWe add it to the end of the list. We search $I\_1$ and find $L\_1\>L\_2$, so we keep a pointer to the head, like

```
H <- (4)  (3)
^         /
 \       /
  -------

```

Next, we skip $-3$ and the subsequence $(1)$ comes. We search $I\_2$ and find $L\_2=L\_3$. Since $I\_2$ points to the head, we assert there is no such $j$ such that $L\_j\<L\_3$ and keep a pointer to the head, like

```
H <- (4)  (3)  (1)
^         /    /
 \       /    /
  ------------

```

Next, the subsequence $(2)$ comes. We search $I\_3$ and find $L\_3\<L\_4, R\_3\<R\_4$, so we apply step 4 and get (note $I\_3$ need to be reconsidered after merging while no change is needed here since it points to the head)

```
H <- (4)  (3)  (1,2)
^         /    /
 \       /    /
  ------------

```

Next, we skip $-2$ and the subsequence $(2)$ comes. We search $I\_3$ and find $L\_3\<L\_4, R\_3=R\_4$, so we keep a pointer to $I\_3$, like

```
H <- (4)  (3)  (1,2) <- (2)
^         /    /
 \       /    /
  ------------

```

Next, we skip $-2$ and the subsequence $(1)$ comes. We search $I\_4$ and find $L\_4=L\_5$, then search $I\_3$ and find $L\_3\<L\_5, R\_3\>R\_5$. We keep a pointer to $I\_3$, like

```
H <- (4)  (3)  (1,2) <- (2)  (1)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

```

Next, the last subsequence $(5)$ comes. We search $I\_5$ and find $L\_5\<L\_6, R\_5\<R\_6$, then we merge $I\_5$ and $I\_6$ and get

```
H <- (4)  (3)  (1,2) <- (2)  (1,5)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

```

Note $I\_5$ needs to be reconsidered. Since $I\_5$ points to $I\_3$, we search $I\_3$ first and find $L\_3\<L\_5, R\_3\<R\_5$, so we merge $I\_3,I\_4,I\_5$ and get

```
H <- (4)  (3)  (1,2,−2,2,−2,1,5)
^         /    /
 \       /    /
  ------------

```

We then reconsider $I\_3$ and no change is needed since it points to the head.
> 1 votes

---
Tags: algorithms, algorithm-analysis, efficiency, linked-lists
---