# Question
Title: Efficiently generating a uniformly random list of unique integers in a range
The problem:

* To generate a list of size $n$,
* Containing *unique* integers,
* Sampled uniformly in the range $\left\[0,m\right)$,
* In $O(n)$ time, except that:
    + Assuming $m$ is bounded by some word-size, $\left|m\right|$, the specific time should be $O(n\cdot\left|m\right|)$, as one cannot do better than this.

Apologies if this is a duplicate, if you find one, feel free to point it out.

---

**EDIT**: to clarify, the question implies that we are concerned the complixity in terms of *bit-operations*. (See logarithmic cost model).

# Answer
Here is a solution in $O(n\log n)$ (with high probability). We consider two cases: $n\log n \geq m$ and $n\log n \leq m$. In the first case, we choose a random permutation of $\[0,m)$ and take only the first $n$ elements. This takes time $O(m) = O(n\log n)$. In the second case, we maintain a balanced binary search tree (or equivalent), adding to it random elements from $\[0,m)$ one by one, checking for duplicates each time. In expectation we need to try at most $1/\log n = o(1)$ extra times for each element, so the expected running time of this algorithm is $O(n\log n)$. In fact, the running time is $O(n\log n)$ also with high probability.

We can obtain an expected $O(n)$ solution by replacing the balanced binary search tree with a hash table, and changing the cutoff to $n \geq m/2$ versus $n \leq m/2$.
> 4 votes

# Answer
Another approach is to use format-preserving encryption (e.g., a Feistel cipher) to build a pseudorandom permutation on the domain $\\{0,1,\dots,m-1\\}$, then encrypt the sequence $0,1,\dots,n-1$ and output the encrypted sequence. The randomness of this will be dependent upon cryptographic assumptions, and it might or might not perform as well as the other alternatives in practice.

If we use the Feistel cipher construction, then I would expect the running time of each encryption to be $O(|m|)$, so the running time to generate the full sequence to be $O(n \cdot |m|)$. However, expressing asymptotic runtime in this way might be a bit misleading, as it assumes one can build a PRF on $\\{0,1,\dots,m-1\\}$ whose running time is $O(|m|)$. That is indeed possible under suitable cryptographic assumptions (e.g., that AES is secure), but it does require those unproven assumptions. So while this is an approach you could try if you want this for a practical purpose, it might not be very useful if your goal is to prove a theorem about computational complexity.
> 4 votes

# Answer
1. Make a binary tree/trie, starting with nothing in the trie
2. Pick a uniform random number over $\left\[0,m\right)$
3. Pad the number to $|m|$ bits, adding leading zeros if necessary
4. Insert the number into the binary tree/trie, one bit at a time where a 0 bit means "left" and a 1 bit means "right", inserting nodes as necessary:
5. Every node in the binary tree/trie will keep track of the number of nodes underneath it in the binary tree/trie; it should be easy to maintain these tracking/values with no added complexity:
6. Based on the previous step, it is possible to compute how many unused-numbers are possible under each branch in the tree: Given the depth of the node and the height of the tree, and the "number of nodes underneath it" from the previous step, it is possible to calculate the number of "unused numbers" on each branch:
7. Using those numbers as weights, the next number should be computed by a weighted random selection of the branches. If a branch has a "unused numbers" weight of 0, then it will have zero chance of being selected, ensuring uniqueness.
8. Go to step 3 and repeat until $n$ numbers are selected.

### Complexity (feel free to correct):

* Each insertion is $O(|m|)$, the depth of the binary tree/trie
* Maintaining the weights adds no complexity
* Choosing the random branches/bits would itself require a weighted random selection, for each branch/bit
* A simple weighted random selection could take $O(|m|)$ time, given a $O(1)$ fair coin tossing method
* Computing each number would therefore take `|m| bit selections * O(|m|) time per selection * n integers` = $O(n\cdot \left|m\right|^2)$
> 4 votes

# Answer
I stumbled upon this question looking for a more practical answer, so here is a more hands-on solution using Java code and 32-bit integers as example. The basic idea is to take an array $\left\[0, 1, ... m-1\right\]$, shuffle it, and return the first $n$ entries. The go-to shuffling algorithm is Fisher-Yates which can be stopped early, making our solution even more efficient. This leads to the following code:

```
int[] randIntsUniqDense( RandomGenerator rng, int m, int n )
{
  assert m >= n;
  var samples = IntStream.range(0,m).toArray();
  // Partial Fisher-Yates shuffle
  for( int i=0; i < n; i++ ) {
    int j = rng.nextInt(i,m);
    // swap i <-> j
    int sample = samples[j];
    samples[j] = samples[i];
    samples[i] = sample;
  }
  // Return requested number of samples
  return Arrays.copyOf(samples,n);
}

```

The implementation above requires $\mathcal{O}(m)$ operations due to the large `samples` array that we have to build. But it turns out we can do better. Instead of keeping track of the entire `samples` array, we can only keep track of the changes using a Hash Table. The following `randIntsUniqSparse()` method behaves identical to `randIntsUniqDense()` while only requiring $\mathcal{O}(n)$ operations:

```
int[] randIntsUniqSparse( RandomGenerator rng, int m, int n )
{
  assert m >= n;
  var results = new int[n];
  var changes = new HashMap<Integer,Integer>();

  // Partial Fisher-Yates shuffle
  for( int i=0; i < n; i++ ) {
    int j = rng.nextInt(i,m);
    // swap i <-> j
    var sample = changes.remove(j);
    if( sample == null )
        sample = j;

    if( i < j ) {
      var displaced = changes.remove(i);
      if( displaced == null )
          displaced = i;
      changes.put(j,displaced);
    }

    results[i] = sample;
  }

  return results;
}

```

To accurately answer the question, we now have to check that `randIntsUniqSparse` can be generalized to arbitrary-length integers, using at most $\mathcal{O}(n\*log(m))$ operations. The answer is yes, assuming that `rng.nextInt(i,m)` is an $\mathcal{O}(log(m))$ operation. That assumption may not be valid for pseudo-RNGs if the desired bits of randomness increase with $m$. Instead, You could use a Hardware RNG.
> 1 votes

---
Tags: algorithms, randomness, sampling
---


# Question
Title: how Is Convergence of machine learning bounded O(n)?
All charts of machine learning performance (y-axis:accuracy 0.0-1.0) across epochs have the below shape. Is there any research that explain how this convergence is bounded O(n) where n is the number epochs (and ultimately the number of examples the algorithm visits).

# Answer
> 0 votes
From what I understand for Neural networks depending on the optimization method used Stochastic gradient Descent or Nesterov Acelerated Descent the convergence is bounded by $O (1/k)$ and $O(1/k^2)$ respectively. This is expressed in terms of loss reduction e.g. how quickly can the algorithm reduce error, where k is the number of iterations it takes for the algorithm to achieve it.

To describe the above chart that is performance overtime rather than loss reduction. We could say $1 - O(1/k)$ since 1.0 is considered the upper perfect learning scenario.

See https://angms.science/doc/CVX/CVX\_FoM\_tight\_rate.pdf

---
Tags: time-complexity, machine-learning
---


# Question
Title: Finding sequences of 0's in a 2D binary grid
*Requirements:*

> Given a 2D array of 1's and 0's (black and white cells) find blocks of white cells of size 1xT or Tx1 where T \>= 1. Any block should not be a subset of a larger block. **Return the number of these blocks.**

This is an example solution of a 5x3 grid. There should be 8 blocks. Block `y:1, x:0` is not a block because it would be a subset of a bigger block `y:1->3, x:0`.

**What I've tried so far**

I've developed a pretty inefficient solution where I iterate through all white cells and for each one get a vertical and horizontal block. Then only accept either block if it isn't a subset of an already accepted block.

The most time complex operation in my code is checking whether a block is a subset of another accepted block.

**My questions**

What would be a more efficient solution to this problem?

Is there a data structure that would help me with this?

# Answer
> 0 votes
you can solve it easily in O(mn). where `m*n` is matrix dimension. first consider only `1*T` type blocks.

iterate each row and in any row whenever you see a 0-\>1 consecutive element increase your block count by 1. (if first element of row is 1 then also increase count) similarly, do this on columns.

(here don't consider `1*1` blocks initially in any iteration. finally after iterating over all rows and columns. check for `1*1` blocks separately)

# Answer
> 0 votes
I fail to see any difficulty in this exercise.

Scan every row in turn, in any order. In a row, scan every column from left to right (or conversely), start a block and increment the counter when you meet a white, and end the block when you meet a black or the end of the row.

Scan every column in turn, in any order. In a column, scan every row from top to bottom (or conversely), start a block and increment the counter when you meet a white, and end the block when you meet a black or the end of the column.

# Answer
> 0 votes
I have to agree with both the suggestions by Yves Daoust and Ashish gupta. The following observations should hold:

* A $1 \times S$ block can only be a subset of a $T \times 1$ block if $ S = 1 $.
* An $S \times 1$ block can only be a subset of a $1 \times T$ block if $ S = 1 $.
* Only isolated $ 1 \times 1 $ blocks (without white neighbors) are not subsets of a larger blocks.
* $ 1 \times T $ blocks in different rows can never be subsets of one another.
* $ T \times 1 $ blocks in different columns can never be subsets of one another.

This should allow You to split the block finding as follows:

1. Find $ 1 \times T $ blocks for $ T \> 1 $ in each row separately
2. Find $ T \times 1 $ blocks for $ T \> 1 $ in each column separately
3. Find all isolated $ 1 \times 1 $ blocks

Both `1.` and `2.` can both be reduced to the same 1D problem. The following Python code finds all white segments longer than 1 in a 1D array:

```
import numpy as np

def find_segments( array_1d ):
  array_1d = np.asarray(array_1d, dtype=bool)
  assert array_1d.ndim == 1

  # append black block for simplicity
  # (otherwise last segment needs separate handling)
  array_1d = np.append(array_1d, 1)

  start = None

  for i,ai in enumerate(array_1d):
    if start is None and ai == 0:
      # segment start found
      start = i

    if start is not None and ai == 1:
      # segment end found
      end = i-1
      if start < end: # <- only accept segments greater than 1
        yield (start,end)
      start = None

    i += 1

```

Finding isolated $ 1 \times 1 $ blocks should be as simple as going through each blocks and looking at its neighbors:

```
def find_1x1_blocks( array_2d ):
  array_2d = np.asarray(array_2d, dtype=bool)
  assert array_2d.ndim == 2

  # pad with black for simplicity
  array_2d = np.pad(array_2d, 1, constant_values=1)

  for (i,j),aij in np.ndenumerate(array_2d):
    if(
      aij == 0
      and array_2d[i-1,j  ] == 1 # <- North
      and array_2d[i,  j+1] == 1 # <- East
      and array_2d[i+1,j  ] == 1 # <- South
      and array_2d[i,  j-1] == 1 # <- West
    ):
      # subtract padding
      i -= 1
      j -= 1
      yield (i,j)

```

Using these two subroutines together, we should be able to find all blocks without duplicates:

```
def find_all_blocks( array_2d ):
  array_2d = np.asarray(array_2d, dtype=bool)
  assert array_2d.ndim == 2

  (m,n) = array_2d.shape

  # search rows
  for i in range(m):
    for (j,k) in find_segments(array_2d[i,:]):
      yield { 'y': i, 'x': (j,k) }

  # search columns
  for k in range(n):
    for (i,j) in find_segments(array_2d[:,k]):
      yield { 'y': (i,j), 'x': k }

  # collect 1x1 blocks
  for (i,j) in find_1x1_blocks(array_2d):
    yield { 'y': i, 'x': j }

```

All that's left now is to count the blocks. Let's use Your example:

```
input = np.array(
  [[1,0,0],
   [0,1,0],
   [0,0,1],
   [0,0,0],
   [1,0,0]]
)

blocks = [*find_all_blocks(input)]

for block in blocks:
  print(block)
# Output:
# {'y': 0, 'x': (1, 2)}
# {'y': 2, 'x': (0, 1)}
# {'y': 3, 'x': (0, 2)}
# {'y': 4, 'x': (1, 2)}
# {'y': (1, 3), 'x': 0}
# {'y': (2, 4), 'x': 1}
# {'y': (0, 1), 'x': 2}
# {'y': (3, 4), 'x': 2}

print(len(blocks))
# Output: 8

```

---
Tags: algorithms, arrays
---


# Question
Title: How does the OS track Reference Counters in Copy-on-Write forks?
I'm trying to modify xv6-riscv to perform a copy-on-write mapping when executing `fork()`, but I'm struggling to determine a concise way to manage the copy-on-write pages.

Most sources I can find online suggest to keep reference counter of how many processes currently are able to read from a given copy-on-write page, storing the counter in the PTE. Only pages with a reference count of 1 may be written to, otherwise you must copy the page and decrement the reference count.

However, it's not clear to me how you would actually implement this. The PTE is of a fixed size, and the vast majority of bits, especially in RISCV, are reserved for other purposes, so storing the number of references in the actual PTE feels impractical, especially if the process calls fork() many times.

Furthermore, how would you synchronize this information across page tables? Each process gets their own PTE for a given physical page. Updating the reference count on the current process's PTE for a physical page will not give any information to the other processes.

My idea was to create a sort of page table tree which would dynamically grow as processes `fork()` and shrink as processes call `exec()` or `kill()`, but this doesn't seem to be mentioned anywhere, and it's pretty convoluted, incurring `O( number of procs sharing COW page )` access time on writes to copy-on-write pages, so I wanted to explore simpler options.

# Answer
In a typical modern operating system, there are three data structures which represent the state of memory. Also note I'm going to use Unix-ish terms for these; Windows has much the same concepts but may use different terms.

1. The *page tables* are the CPU's view of *virtual* memory. There is usually no "room" in a page table entry (PTE from now on) to store anything when the page is valid.
2. The *virtual memory map* is the OS's view of *virtual* memory. You can think of this as a list of *segments* which represent a range of virtual memory, what it corresponds to (e.g. anonymous memory, some section of a mapped file), and its semantics (e.g. zero fill, copy on write).
3. The *core map* is the OS's view of *physical* memory. The Unix v6 core map was very simple; it was just a bitmap, with one bit denoting if a page frame was used or free. Today, an array of structures, one per page frame, allocated at boot time is a common implementation.

If a page of virtual memory is not resident in core, then it doesn't really "need" a representation that is distinct from the segment that it belongs to. The virtual memory map can record sharing information.

If page is resident in core, the information about sharing can be stored in the core map, or in a structure available from the core map.

The core map entry structure should be small, since there is one per page frame. For kernels implemented in C, judicious use of `union` is very common. A typical core map entry might information such as:

* A word representing the type of memory (e.g. free, page cache, kernel allocated, memory-mapped I/O area, ROM) and associated flags (e.g. whether or not it is shared, or perhaps some concurrency protection).
* The previous/next pointers of a doubly-linked list. This might, for example, represent the free list if the page frame is free, or an LRU cache (for "page out" purposes) if it is part of the page cache.
* An integer (perhaps an atomic integer) representing the number of address spaces that the page is used by.
* If the page frame is singly-mapped, the address space and offset that this page frame belongs to. Otherwise, if the page frame is shared, this space could be used to point to an auxiliary structure which represents a list of mappings.

xv6 doesn't have support for any of this, since its physical and virtual memory management is very simple for teaching purposes. As well as not supporting shared segments, it also doesn't support memory-mapped files or swap. It doesn't even seem to have a page fault handler, as far as I can tell. Rather, xv6 manages physical memory as a free list.

I can't tell you how you should implement this, but I would start with implementing a core map and reworking the kernel allocation system to use it, then iterate on that.
> 3 votes

---
Tags: operating-systems, virtual-memory
---


# Question
Title: How to generate all the possible nodes inside a polygon, if the polygon is represented by its vertices
If a polygon is represented by its vertices(latitudes, longitudes), is it possible to find all the possible points or nodes(latitudes, longitudes). If so, what kind of algorithm is used. The polygon does not intersect itself and it does not have any holes.

# Answer
> 0 votes
I wrote you a pseudocode of the algorithm, I don't think it's perfect, but you can take the idea. Take the vertices of the polygon as an array of pairs of latitude and longitude lines. GSize determines the number of matches in each dimension of the grid. For each point inside the polygon.

```
// Determine the bounding box
function findPoints(NVertices, GSize):
     minX = min(NVertices.longitude)
     maxX = max(NVertices.longitude)
     minY = min(NVertices.latitude)
     maxY = max(NVertices.latitude)

     //Divide the bounding box into a grid of cells
     cellSizeX = (maxX - minX) / gridSize
     cellSizeY = (maxY - minY) / gridSize

//Iterate over each cell in the grid
for i from 0 to gridSize-1:
    for j from 0 to gridSize-1:
        // Step 4: Calculate the center point of the cell
        cellCenterX = minX + (i + 1) * cellSizeX
        cellCenterY = minY + (j + 1) * cellSizeY

        // Check if the Center point lies within the polygon
        if isPointInPolygon(cellCenterX, cellCenterY, polygonVertices):
            // Center point is within the polygon, consider it as a point within the polygon
            output(cellCenterX, cellCenterY)
return

function isPointInPolygon(x, y, Vertices):
isInside = false
j = Vertices.length - 1
for i from 0 to Vertices.length - 1:
    if ((Vertices[i].latitude <= y) != (Vertices[j].latitude > y)) and
       (x < (Vertices[j].longitude - Vertices[i].longitude) * (y - Vertices[i].latitude) / (Vertices[j].latitude - Vertices[i].latitude) + Vertices[i].longitude):
        isInside = !isInside
    j = i
return isInside

```

There is such an algorithm, I'm writing you a kind of script here, I saw it once, it should work.

---
Tags: algorithms, complexity-theory, graphs, data-structures
---


# Question
Title: Meaning/veracity of "each state has [..] or two outgoing ϵ transitions" in Thompson's construction
The dragon book lists properties of an NFA N(r) created using Thompson's construction, in particular:

> 3. Each state of N(r) other than the accepting state has either one outgoing transition on a symbol in Σ **or two outgoing transitions, both on ϵ**.

However, the same book shows NFAs created using Thompson's construction that seem to contradict that very statement, like this one:

Here, nodes 3 and 5, which are not accepting states, have only one outgoing ϵ transition each. What am I missing?

# Answer
> 1 votes
Thanks @Highheath in the comments, you are right.

At first I found it hard to believe that I should be the first one to have found such an error in the 36+ years since this - apparently very popular - book is out. It is in its second edition since 2008, but I would have expected this part to have been in the first edition as well.

Be that as it may, the error shows up in the errata:

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: ER model cant understand where I am wrong?
I am studying this ERD:

The bank and the customer are obviously strong entities because they are a bank and a person. The bank branch is clearly a weak entity because it depends on the bank associated with it. How are a account and a loan not weak entities? Since a loan and a account depend on the customer and the bank branch. How am I thinking wrongly of this?

# Answer
A weak entity type is an entity type identified by some attribute/s together some related object (https://en.m.wikipedia.org/wiki/Weak\_entity)

For instance, the room of a hotel might be seen as a weak entity type since it is identified by the hotel, and a number. A number itself cannot identify a room because there are several rooms with the same number (in different hotels).

In your exercise, it seems that loans and accounts have their own unique identifier number. That is, there are no two loans (or accounts) with the same loanNo (accountNo), not even in different banks. Hence, in this exercise, loans and accounts can be seen as strong entities.
> 0 votes

---
Tags: database-theory
---


# Question
Title: Complexity of a variant of #Positive-2-SAT
***#Positive-2SAT*** is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable.

The following variant of *#Positive 2-SAT* is defined as follows :

For example ,We are given a set of variables :

**(a,b,c,d,e)**

The set of all possible *positive 2-literal clauses* from the given set of variables are :

* **A = \[ ab ,ac ,ad ,ae \]**
* **B = \[ bc ,bd ,be \]**
* **C = \[ cd ,ce \]**
* **D = \[ de \]**

This version of problem puts restrictions on the inputs such that we can only choose at max only two clause from each set mentioned above to form our set of input clauses.

Ex-

1. A valid input to this variant of *#Positive 2-SAT* would be ***(ab ,ac ,bc ,cd)*** here we have only at max 2 clauses form each set mentioned above.
2. An invalid input to this variant of *#Positive 2-SAT* would be ***(ac ,ad ,ae ,bc ,cd)*** this is invalid as we have chosen more than 2 clauses from *set A*, mentioned above, thus its not a valid input to this version of the problem as we must only choose at max 2 clause form each set.

If its #P-complete for 2-clauses per set at max ,then is the result also true for 1-clause per set at max?

> Motivation behind this is to see how the number of solutions changes with respect to the overlap between clauses ,thus I want to know if its *#p-complete even for 2-clauses per set* ,this will make it easier to see the relation.

We know from this post that this variant is #P-complete where we can select at max only 3-clauses from each set mentioned above ,that's why I wanted to know if this is #P-complete where we allowed to select at max only 2 clauses from each set.

Is this variant of *#Positive-2-SAT* *#P-complete*?

Edit :

To clarify Steven confusion ,The sets are just a special way to classify the set of all possible positive-2-literal clauses with respect to k variables ,and my restriction is that we can make a set of 2-literal clauses as our input to the #Positive-2-SAT but we choose clauses from each set but we may not choose more than 3-clauses from any of these sets.

And any current answer doesn't resolve my question as they seem have to misunderstood the problem statement.

# Answer
The question is ambiguous, as Steven has indicated.

One possible interpretation is that there is one set per variable, or in other words, each variable can occur in only two clauses. This is unlikely to be $\\#\mathsf{P}$-complete, as indicated below.

Another possible intepretation is that there can be any number of sets, from 0 to the number of variables, and the sets are provided as part of the input, and the only restriction is that the formula must be consistent with the provided sets. In this case, the problem is $\\#\mathsf{P}$-complete, as indicated below.

# One set per variable

Assuming you have one set per variable, it can be solved in polynomial time.

Form an undirected graph with one vertex per variable and one edge per clause. Then there are at most two edges incident on each variable, i.e., each vertex has degree at most 2. This graph splits into a disjoint set of components, where each component is a simple cycle, a simple path, or an isolated vertice. For each component, you can count the number of satisfying assignments for that component (i.e., number of ways to assign values to the variables involved in that component) in polynomial time, then multiply them to get the total number of satisfying assignments for the original formula.

I leave it to you as a straightforward exercise describe a polynomial-time algorithm to count the number of satisfying assignments for an isolated vertex (hint: 2), for a simple path, and for a simple cycle. A simple path corresponds to a formula of the form

$$(x\_1 \lor x\_2) \land (x\_2 \lor x\_3) \land \dots \land (x\_{k-1} \lor x\_k),$$

and a simple cycle corresponds to a formula of the form

$$(x\_1 \lor x\_2) \land (x\_2 \lor x\_3) \land \dots \land (x\_{k-1} \lor x\_k) \land (x\_k \lor x\_1).$$

It is believed that $\mathsf{P} \ne \\#\mathsf{P}$. Therefore, it is unlikely that this problem is $\\#\mathsf{P}$-complete.

# Any number of sets

In this case, one special case is where there are zero sets. This means that there are no restrictions on the formula, except that it must be a positive 2CNF formula.

It is known that counting the number of satisfying assignments to a positive 2CNF formula is $\\#\mathsf{P}$-complete. If a special case of the problem is $\\#\mathsf{P}$-hard, then the general problem must be $\\#\mathsf{P}$-hard as well. It follows that your problem is $\\#\mathsf{P}$-hard.

Also, it is easy to see that your problem is in $\\#\mathsf{P}$.

It follows that your problem is $\\#\mathsf{P}$-complete.
> 0 votes

---
Tags: complexity-theory, satisfiability, complexity-classes, counting
---


title: Programs with feedback?

text:
# Question
Title: Programs with feedback?
Suppose we have a program like this:

```
def feedback(number):
    final(number)
def final(number):
    if number=2 or number=4:
       print(number)
    else:
       feedback(number/2)

```

which is self referential in a way how can we predict the output of such programs? Do we have to brute force the result or is there a clever way to think about it?

# Answer
> 0 votes
The program you show has no output. It defined two functions called `feedback` and `final`, and does nothing after that.

You probably meant to ask what happens if we *call* `final` with a given number? This can be analyzed quite easily, I suggest you do it as a useful exercise. Draw a table for values $n = \ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$ and for each $n$ determine what $\mathtt{final}(n)$ does. (Of course, you should actually run your code to see what it does.) Can you spot any patterns?

---
Tags: algorithms, computability, dynamic-programming, recursion
---


# Question
Title: What algorithm constructs the optimal code $f$ of size $a$?
I'm looking at Shannon's source coding theorem for symbol codes. It provides a very nice bound on the expected code length $S=|f(X)|$ of an optimal code $f$ over the sequence variable $X$:

$$ \frac{H(X)}{log\_2(a)} \le \mathbb{E}\[S\] \lt \frac{H(X)}{log\_2(a)} + 1 $$

It does not however prescribe an algorithm that can learn an optimal code $f$ with size $a$ for a data set of sequences $D=\\{D\_0, D\_1, ...\\}$, where $D \stackrel{iid}{\sim} X$

In pseudocode, I think it would look something like:

$$ f = learn(D, a) $$ $$ T\_i = encode(D\_i, f) $$ $$ D\_i = decode(T\_i, f) $$

Is there an algorithm for that?

One trivial example is, if $a \ge |D|$, we could set $f=D$ and say $T\_i = (i)$, which guarantees length 1, however I'm more interested in the $a \ll |D|$ regime.

# Answer
> 2 votes
Arithmetic codes can get arbitrarily close to the Shannon limit, assuming your model of probabilities is correct. It it typically shown in the context of a binary alphabet, but there's nothing fundamental about that. It can work in any radix, as well as mixed-radix systems.

---
Tags: information-theory, data-compression
---


# Question
Title: Tail call optimization via translating to CPS
I am struggling to wrap my head around this compiler technique, so let's say here's my *`factorial`* function

```
def factorial(value: int) -> int:
    if value == 0:
        return 1
    else:
        return factorial(value-1) * value

```

It is recursive, but not TCO friendly yet, so, as the theory goes, the first thing to try here is translate it to CPS:

```
def factorial_cont(value: int, cont: typing.Callable[[int], T]) -> T:
    if value == 0:
        return cont(1)
    else:
        return factorial_cont(value-1, lambda result:  cont(value * result))

```

Now, as the function is tail call recursive, I can do the usual trick with the while loop:

```
def factorial_while(value: int, cont: typing.Callable[[int], T]) -> T:
    current_cont = cont
    current_value = value
    while True:
        if current_value == 0:
            return current_cont(1)
        else:
            current_cont = lambda result: current_cont(current_value * result)
            # note: in actual python that would look like
            # current_cont = lambda result, c=current_cont, v=current_value: c(v * result)
            current_value = current_value - 1

```

This `current_cont` thing effectively becomes a huge composition chain, in `haskell` terms for the `value == 3` that would be `let resulting_cont = ((initial_cont . (3*)) . (2*)) . (1*)`, where `initial_cont` is safe to default to `id`, and surely enough `resulting_cont value == value!`.

But I also know the trick with "`accumulator`" value:

```
def factorial_acc(value: int, acc: int = 1) -> int:
    current_acc = acc
    current_value = value
    while True:
        if current_value == 1:
            return current_acc
        else:
            current_acc = current_acc * current_value
            current_value = current_value - 1

```

which looks pretty much identical to the CPS version after the introduction of while loop.

The question is, how exactly do I massage the continuation `let resulting_cont = ((initial_cont . (3*)) . (2*)) . (1*)` into the form resembling `accumulator` version?

# Answer
> 2 votes
Somehow turn the opaque lambdas

```
next_cont = lambda result: current_cont(current_value * result)

```

into transparent data

```
next_cont = Compose( current_cont, Mult(current_value))

```

then use the fact that

```
 Compose( Compose( a_cont, Mult(val)), Mult(current_value))
==
 Compose( a_cont, Compose( Mult(val), Mult(current_value)))
==
 Compose( a_cont, Mult( val*current_value ))

```

You end up with `Compose( init_cont, Mult( result ))` which you then call with

```
 call( Compose( init_cont, Mult( result )), 1 )
=
 init_cont( call( Mult(result), 1))
=
 init_cont( result*1 )

```

Look up "reifying continuations" and "defunctionalization".

---
Tags: compilers, recursion, loops, continuations, tail-recursion
---


title: Is this function computable?

text:
# Question
Title: Is this function computable?
Given a function like:

f(x) = x=y then 1 else 0

The number y is a natural number, other than that is unknown

I had two approaches in mind:

* The function is computable since an algorithm exists, that can compare two numbers, and tell whether they are equal return 1, otherwise 0.
* The function is not computable, since we would need to know the number y to write an algorithm that compares the numbers.

Can someone give me a hint into the right direction?

# Answer
> 1 votes
A common definition of a computable function $f(x) : \mathcal{X} \to \mathbb{N}$ is as follows:

> There exists a Turing machine that given $x\in \mathcal{X}$ on its initial tape will produce $f(x)$ after a finite amount of steps.

Note that it only requires such a Turing machine to *exist*.

Now for your question, we can produce an infinite set of Turing machines by mapping each natural number $y$ to a Turing machine that tests if its input $x$ equals $y$. Each of these Turing machines obviously exists. Since your function $f$ is equivalent to one of these Turing machines, it must be computable.

---
Tags: computability
---


# Question
Title: How branching factor affects complexity of Monte Carlo Tree Search?
I was reading: https://stackoverflow.com/questions/34724201/whats-the-time-complexity-of-monte-carlo-tree-search

Where it says:

> The runtime of the algorithm can be simply be computed as O(mkI/C) where m and k are the same as before, and I is the number of iterations and C is the number of cores available.

According to this definition let's suppose we had a game with a branching factor of b then made some changes to that game so the new branching factor is 5b. How does this affect the run time complexity of MCTS?

From what I see if we run in same environment this doesn't change the run time (as the equation doesn't include b - branching factor) but that doesn't make sense to me...

# Answer
> 2 votes
Monte-Carlo Tree Search is not an exhaustive search algorithm. It just does a certain amount of iterations, and then it is done. The branching factor has a (dramatic) influence on the size of the search space, but this does not affect the runtime of MCTS.

Note that if the search space is a lot larger, the quality of a result with a fixed number of iterations is likely (much) lower. So if a similar quality of result is required, the number of iterations must also drastically go up. But this is not a *requirement* like it is with exhaustive search algorithms, you can also simply accept a (relatively) poor quality result. If you are facing an opponent that also can not afford to do an exhaustive search, this is not a problem in of itself.

What *does* affect the performance of MCTS is the average *depth* of a game tree, as it means more time has to be spent in random rollouts to get sample outcomes. At least in traditional MCTS, some variants replace the random rollout with estimators such as heuristics or neural networks which may not become more expensive with a higher average depth.

---
Tags: algorithms, time-complexity, algorithm-analysis, runtime-analysis, monte-carlo
---


title: `transp` In Agda

text:
# Question
Title: `transp` In Agda
I'm still a bit confused about the `transp` operator in Agda:

> ```
> transp : ∀ {ℓ} (A : I → Set ℓ) (r : I) (a : A i0) → A i1
>
> ```

Is found this paper and I wonder if there is a relation?

>

As far as I understand, the $\mathsf{comp}^i$ operator lets you transport an $n$-dimensional cube along $i$ and if you already know how some of the faces in the resulting $n+1$-dimensional cube should look like, you can specify them. So for example, $\mathsf{comp}^i A\ \[(j=0)\mapsto q\ i\]\ (p\ j)$ would only respect $q\ i$ but at $j=1$, the resulting face would not necessarily equal $r\ i$, is that correct?

They also define $\mathsf{transport}^i\ A\ u\_0$ as $\mathsf{comp}^i\ A\ \[\]\ u\_0$ which I read as composition with no constraints and which looks a little bit like Agda's `transport`:

> ```
> transport : ∀ {ℓ} {A B : Set ℓ} → A ≡ B → A → B
> transport p a = transp (λ i → p i) i0 a
>
> ```

Could it be that `transp` is something like $\mathsf{comp}^i$ but where all constraints (like $q\ i$ and $r\ i$ in the example above) are constant (in $i$) and $r$ specifies at which faces the constant constraints are introduced?

# Answer
$\newcommand{\comp}{\mathsf{comp}}$ $\newcommand{\hcomp}{\mathsf{hcomp}}$ $\newcommand{\transp}{\mathsf{transp}}$ $\newcommand{\transport}{\mathsf{transport}}$

Compared to the paper you're reading, Agda divides $\comp$ into two distinct operations:

1. $\hcomp$ is like $\comp$, but the $A$ parameter is not allowed to vary in $i$. This is "homogeneous composition."
2. $\transp$ is the part of $\comp$ that allows $A$ to vary. It strictly deals with transporting along a path between types.

If you put these two components together, you can regain $\comp$ (by transporting things and doing the composition part in a homogeneous context), but it has been divided into orthogonal pieces that are easier to manage individually (although I don't have the expertise to explain exactly *what* about it is easier).

There is one important difference between $\transp$ and the $\transport$ defined in the paper you're reading (and in Agda). $\transp$ has the extra second argument $φ$, which specifies when it's allowed to reduce away. The side condition required is that when $φ$ holds, $A$ is constant in $i$. In that case, we have that $\transp\ A\ φ\ x = x$. So, $\transp$ doesn't strictly correspond to an empty $\comp$, but rather to something like:

$$\comp^i A\ \[φ \mapsto u\_0\]\ u\_0$$

which only makes sense when $A$ is the type of $u\_0$ (which cannot depend on $i$) whenever $φ$ holds. Then $\transport$ is defined with $φ = 0$, which reduces to an empty $\comp$.
> 3 votes

---
Tags: type-theory, agda, cubical-type-theory
---


# Question
Title: Can we tell if we can tell if an algorithm halts or not?
We proved that, there exist no algorithm so it can tell us if an algorithm halts or not (a.k.a. the halting problem is undecidable). But it surely can handle some of those; can we tell which of those it can handle, and which not? If we can't, can we tell which of those we can tell if it can handle or not? And even if not that, can we tell which of those that we can't tell which of those we can tell if it can handle or not? (do it recursively till a yes comes; do a yes ever come?)

# Answer
If you set a timeout on the decision algorithm $A$ (let us call this variant $A'$), then by running it on any input you will get either a *yes/no* answer or a *don't know*. And this is precisely the question you are asking, "which of those it can handle, and which not", where "it" is $A'$.
> 1 votes

# Answer
If I understand your question correctly, you are considering an algorithm $A$ that, when run with an input $x$ (which is in turn an algorithm) *attempts* to predict whether $x$ halts or not. Notice that $A(x)$ could accept, reject, or run forever.

Now you consider the language $H\_{A}$ containing all algorithms $x$ such that either i) $x$ halts and $A(x)$ accepts, or $x$ does not halt and $A(x)$ rejects. The question is whether $H\_A$ is decidable.

The answer depends on $A$. For example, if $A$ is an algorithm that runs forever. Then $H\_A = \emptyset$ and hence it is trivially decidable. If $A$ is the trivial algorithm that always accepts, then $H\_A$ is the language of the halting problem and hence it is undecidable.
> 1 votes

---
Tags: decision-problem, halting-problem
---


# Question
Title: Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete
Prove if $A,B$ are NP-complete then $((a, b) \mid a \in A \lor b \in B)$ is also NP complete

I can understand why the union and intersection of 2 NP-complete languages are true but for statement above I can't understand why and how to prove.

# Answer
To prove it is in $\mathsf{NP}$, use both certificates for $A$ and for $B$, and check if one of them is verified.

To prove it is $\mathsf{NP}$-hard, you can find a reduction from $A$ to $L = \\{(a,b)\mid a\in A \lor b\in B\\}$: since $B$ is $\mathsf{NP}$-complete, it is neither the empty set nor the universal set. Let $x\notin B$ (there exists such an element). Then $a\in A$ if and only if $(a, x) \in L$. The construction is done in polynomial time, because $x$ does not depend on $a$.
> 1 votes

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


# Question
Title: Parameterized intractability relation between split and chordal graphs
I am a research scholar currently working in computational complexity. I am working on a decision problem $P$ that is known to be W\[2\]-hard parameterized by the solution size on split graphs. As split graphs are chordal graphs, if a problem is NP-complete on split graphs, it is also NP-complete on chordal graphs. I wonder whether this also holds in terms of parameterized complexity. Can I say that the problem $P$ on chordal graphs is at least W\[2\]-hard? If not, can I also at least rule out the fixed-parameter tractability of the problem for the given parameter? Please let me know.
More information on parameterized complexity and W-hierarchy can be found here.

# Answer
Yes, since the class of split graphs is a subclass of the class of chordal graphs, you can define a `parameterized reduction` from the problem parameterized by output size on split graph to the same problem parameterized by output size on chordal graph with $(G, k)\mapsto (G, k)$ where the output of the reduction is the same graph. Clearly, the resulting graph is a chordal graph, and hence, the problem is W\[2\]-hard on chordal graphs as well.

---

You can check the book `parameterized complexity` by Cygan et al. for more information about parameterized reductions.
> 2 votes

---
Tags: algorithms, complexity-theory, np-complete
---


# Question
Title: Turing Machine, UNLIMITED number of steps left or right on the tape?
In the Church-Turing thesis Wiki page, there are a set of descriptions of the "behavior of a computor—\`a human computing agent who proceeds mechanically'". I am content with all of them, except:

> (L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a **bounded** distance of the immediately previously observed configuration.

I suppose this is related to the fact that in the standard description of a Turing machine, we are only allowed to move **one** step left or **one** step right at any step of the computation (e.g. the transition function is a map t : Symbols x States -\> Symbols x States x {L,R}).

Indeed, this finiteness/locality assumption is present in Turing's original paper: in Section 9, Turing writes:

> Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square.

My issue with this is that I don't think it matches the standard motivating intuition provided for Turing machines (Turing himself provided this motivating picture in his original paper), namely that of some person, working with a finite set of symbols (e.g. all the symbols we can produce on a keyboard say), and finitely many "states of mind", reading/writing/erasing symbols on an unlimited pile of paper. I think it's entirely reasonable for that person, to flip an arbitrarily large number of pages forward or back in the pile/sequence of papers. Of course, if I wanted to flip a million pages back, I could! Or if I wanted to flip a trillion pages forward, I could!

Well, indeed in the standard model of Turing machines, I can have some sort of counter-variable holding the value of a million or trillion, and then take one step left or right, decrementing the counter-variable each time. So in this way, an unlimited number of steps left or right can be interpreted as just one step left or right, but over the course of many "units" of time.

But if truly unlimited numbers of steps left and right can be simulated by a standard Turing machine, why even bother stating this finiteness/locality "axiom"? I am having trouble understanding the subtlety of what sorts of "unlimited steps" left or right the "axiom" forbids, and what sorts of "unlimited steps" left or right the "axiom" allows (e.g. my "one trillion steps" example above).

EDIT: see also Intuition for Church-Turing thesis for Turing machines which says

> The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations.

I guess my above question is basically asking for a more precise understanding of what "locality" means. *Fun bonus trivia:* https://math.stackexchange.com/questions/402934/why-do-we-believe-the-church-turing-thesis mentions spacetime structures consistent with General Relativity which in some sense allow infinite computation in finite time!

# Answer
A move of unlimited amplitude requires an unlimited amount of information for its description. There is no room in the model for such an amount, except on the tape. But it is not the purpose of the tape to encode move lengths explicitly.
> 2 votes

# Answer
While "unlimited" is also correct, "bounded" is much preferred.

---

Here is the expanded answer.

> The new observed configurations must be within a bounded distance of the immediately previously observed configuration.

As you have explained, it is certainly reasonable and correct to replace "a bounded distance" with "a finite distance" (and replace "the immediately" with "a") in the quoted statement above. I prefer "finite" to "unlimited" since the latter might be interpreted as "possibly infinite", which is of course neither your intention nor the intention of any involved party.

However, I would like to stick to "a bounded distance", which means a distance that is bounded above from a fixed distance that only depends on the "computor". That limiting distance is the same for all successive changes of attention ever made by a specific computor.

Why?

Because one of the criteria to understand/define/create Turing machine is simplicity. According to Occam's razor, we should prefer explanations constructed with the **smallest** possible set of elements. Or according to Albert Einstein, "the supreme goal of all theory is to make the irreducible basic elements **as simple and as few as possible**".

It occurs to me that "a bounded distance" is simpler than "a finite distance" or "an unlimited distance". A distance that is "finite" or "unlimited" is somewhat harder to understand and explain because infinity is not easy to understand and explain. Infinity is a tricky beast (or, should I say, infinities are tricky?)

While "A computor" may shift attention to a new symbolic configuration that is "a finite distance" or "an unlimited distance" away from "a previously observed configuration", it might be the result of shifting attention **many times**. What we would like to describe/define/depict here is one atomic action of "a computor" that shifts attention from "the **immediately** previously observed configuration" instead of multiple actions. "Multiple actions" is understood as/defined by a sequence of successive atomic actions. The result of multiple actions is the aggregated consequence of all actions in the multiple actions. For example, I agree that "if I wanted to flip a million pages back, I could!". However, flipping a million pages back should be considered as flipping one page back a million times. Our interest here is about "flipping one page back" instead of "flipping one page back a million times".
> 1 votes

---
Tags: turing-machines, computability, church-turing-thesis
---


# Question
Title: Let 3-COL-$K_4$-FREE be the decision problem that asks if a graph that doesn't contain $K_4$ admits a 3-coloring. Show that the problem is NP-complete
I'm kind of struggling with this excercise. The obvious thing to try is to show that **3-COL** $\leq\_p$ **3-COL-$K\_4$-FREE** ($\leq\_p$ stands for polynomial reduction). It is clear that **3-COL-$K\_4$-FREE** is in $NP$.

The first thing that comes to mind then is to take the trivial reduction that maps a graph $G$ to itself, but this doesn't work because a graph which contains $K\_4$ is not a valid instance of **3-COL-$K\_4$-FREE**. So, i'm looking for a polynomial reduction that maps a graph $G$ to some other $G'$ such that it gets rid of every $K\_4$ in $G$ while preserving the coloring in both ways (i.e, a reduction $r$ such that $G$ is a positive instance of **3-COL** $\iff$ $r(G)$ is a positive instance of **3-COL-$K\_4$-FREE**).

# Answer
Here is a possible reduction $f$ from $3\text{-COL}$. Let $H$ be any fixed graph that does not contain $K\_4$ and is not $3$-colorable (e.g., $H=(\\{1,2,3,4,5\\}, \\{(1,2), (1,3), (1,4), (2,3), (2,4), (3,5), (4,5)\\})$). Given an instance $G$ of $3\text{-COL}$ $f(G)$, define $f$ as follows: $$ f(G) = \begin{cases} H & \text{ if $G$ contains $K\_4$}; \\ G & \text{otherwise}. \end{cases} $$

The function $f(G)$ is computable in polynomial-time since you can simply inspect all sets of $4$ vertices from $G=(V,E)$ in time $O(|V|^4)$.

To see that the reduction is correct, notice that if $G$ contains $K\_4$ then $G \not\in 3\text{-COL}$ and $f(G) = H \not\in 3\text{-COL-}K\_4\text{-FREE}$. Otherwise $G \in 3\text{-COL} \iff f(G) = G \in 3\text{-COL-}K\_4\text{-FREE}$.
> 1 votes

---
Tags: np-complete, colorings, polynomial-time-reductions
---


# Question
Title: Detecting if an object reached target points
I have an object that is moving towards target points and I want to determine when it will reach or pass through them. I receive points in real time, which represent the current position of the object. The position is a 6-D vector. The data can be download from here

**Initial approach**

For each received point:

* Calculate distance between current and target points.
* As the object approaches the target, the distance decreases. If current distance is greater than previous distance, I consider that it has reached the target. It's good enough for me.

**Problem**

The problem is that the point can sometimes fluctuate a bit. It can increase and then decrease again (noise), even if it has not yet reached the target. But because of this fluctuation, my algorithm detects a false positive because the current distance is greater than the previous one.

The image shows false positives and true positives. When a real upward trend begins, I know that the object has reached the target point. My simple idea to start with is to get rid of false positives by using a smoothing filter and fit a curve. After that I can find when positive slope begins which tells me when object reached target.

I wonder if I should try this approach or any other recommendations including smoothing filters, fitting a curve, etc?

# Answer
> 0 votes
No one can tell you what will be best; you'll have to try different approaches and see what works best in your setting.

I think one reasonable approach worth trying is to filter the data using a Kalman filter, then find the filtered point that is closest to the origin (or target) (without trying to look for upward/downward trends).

---
Tags: algorithms, python, robotics
---


# Question
Title: Reduction from a language with unknown decidability to HALT
We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$ L\leq\_mHALT $$ So that I can determine $L \in RE$? More specifically, given the quite common problem of the decidability of $$ L=\\{\langle M\rangle | |L(M)| ≥ 5\\} $$ (Or any other natural number instead of 5)

All proofs I've seen online construct a TM that uses dovetailing so I was wondering if there is a different way to solve this problem, specifically using a reduction.

# Answer
You can get a reduction from the proofs you've seen. Construct a TM $M\_L$ which uses dovetailing to count how many inputs a given TM $M$ accepts and let $M\_L$ halt once that counter reaches a value $\geq 5$. Thus, $M\_L$ halts on input $\langle M \rangle$ if and only if $\langle M \rangle \in L$, yielding the desired reduction.

I don't see an easier reduction for this problem.
> 0 votes

---
Tags: turing-machines, reductions, halting-problem, turing-recognizable
---


title: Max Unique Clique in $\Sigma^2_p$

text:
# Question
Title: Max Unique Clique in $\Sigma^2_p$
I want to prove that the language $\text{Max-Unique-Clique} = \\{\<G\> | \text{The maximal clique of $G$ is unique}\\}$ is in $\Sigma\_2^p$ by using the following $\Sigma\_2^p$ machine:

1. The machine guesses $k$ and verifies that there is a subset of size $k$ that is a clique. If not, it rejects.
2. It verifies that all other subsets of vertices of size $k$ and all subsets of size $k+1$ are not a clique. If both conditions are true, it accepts; otherwise, it rejects.

The correctness of the machine is trivial, but I'm not sure if it qualifies as a legal $\Sigma\_2^p$ machine because I want to verify whether: $$\exists k,y\_1,\ldots ,y\_k\forall z\_1,\ldots ,z\_k,w\_1,\ldots,w\_{k+1}M(x,y,zw)=1$$

However, the length of the variables depends on $k$, which may be problematic.

# Answer
> 0 votes
I'm not sure what you mean by "$\Sigma\_2^p$ machine". If you consider a polytime NTM with a $\mathsf{coNP}$ oracle (i.e. using $\Sigma\_2^p = \mathsf{NP}^{\mathsf{coNP}}$), then we only have restrictions on running time (that is, the length of "guessed" witnesses is merely bounded rather than fixed); essentially the same is true for alternating TMs (i.e. using $\Sigma\_2^p = \Sigma\_2 \mathsf{Time}(\mathrm{poly}(n))$).

From a very technical point of view, you are correct when using the certificate/verifier definition: The class is usually defined such that the length of the witnesses is purely defined in terms of the input length. However, you can easily fix this problem by padding your witnesses. Simply use $n$ bits to encode a subset of the vertices of your graph by setting the $i$-th bit to $1$ iff you wish to specify that the $i$-th vertex (say, in the order they appear in the encoding of the input graph) lies in the set under consideration.

---
Tags: np-hard, decision-problem
---


# Question
Title: Hardness of finding exactly two Hamiltonian cycles in a graph
$\newcommand{\nuSwap}{\nu\textsf{-swap}}$

*Two Hamiltonian cycles are different if and only if there is at least one edge they do not share.*

Let $L$ consist of all graphs with exactly two Hamiltonian cycles. What complexity class does it belong to?

Let us construct an NTM $M$ that decides $L$ in polynomial time.

Take an NTM $M\_1$ that recognizes the existence of a Hamiltonian cycle in polynomial time and run it on $G$. If $M\_1$ rejects $G$, reject, otherwise use $M\_1$ to construct the cycle $P\_1$. Now for each edge $e\_i \in P\_1$ run $M\_1$ on $G\_i = (V, E \setminus \\{ e\_i \\})$. If $M\_1$ never accepts, reject, otherwise find another Hamiltonian cycle $P\_2$ using $M\_1$ on any $i$ such that $M\_1$ accepts $G\_i$. Repeat the same process again but now try every $e\_i \in P\_1$, $e\_j \in P\_2$ on $G\_{ij} = (V, E \setminus \\{ e\_i, e\_j \\})$. If the third Hamiltonian cycle is found, reject, otherwise accept.

Now we can also make $M'$ that decides $\overline{L}$ in polynomial time. We use $M\_1$ to see if there is a Hamiltonian cycle - if not, accept, otherwise construct it and use the same process as before to find a second Hamiltonian cycle. If it is not found, then accept, otherwise try to find a third hamiltonian cycle by deleting each pair like before. If the third Hamiltonian cycle was not found, then reject, otherwise accept.

Both $M$ and $M'$ seem to run in polynomial time as they only use $M\_1$ but there must be a mistake as this would prove that $\mathcal{NP} = co \textsf{ -} \mathcal{NP}$.

Where is my reasoning wrong and how to decide which complexity class does $L$ belong to?

# Answer
> 1 votes
Your $M\_1$ is not a polynomial time NTM unless $\mathsf{NP} = \mathsf{coNP}$, I think. In the last step (checking that $G\_{ij}$ contains no HC), you essentially want to decide the complement of HC, which is $\mathsf{coNP}$-complete. This is a bit of a tricky thing about nondeterministic computation: you cannot simply invert answers like you can with deterministic computation.

As for the complexity of your problem: Note that it is the intersection of a $\mathsf{NP}$-language (are there at least 2 different HCs) and a $\mathsf{coNP}$-language (does any triple of HCs contain the same HC twice?) and hence in $\mathsf{DP} \subseteq \Delta\_2^p$. I don't see an easy way to convincingly argue that it's not contained in some lower class.

---
Tags: complexity-theory, np-complete, co-np
---


# Question
Title: How to determine the largest number of disconnected arcs in a graph?
Given a directed graph $G=(V,E)$, I'm wondering if there's a way to determine the largest size of a set of edges that are disconnected pairwise. There is a similar problem for vertices (Maximum Independent Set). However, I'm unable to think of the corresponding problem for edges.

When I say "two disconnected edges" I mean the following:

* $(u,v)$ to $(u,w)$ are "disconnected" since the tail of one does not equal the tip of the other.
* $(u,v)$ to $(w,v)$ are "disconnected" since the tail of one does not equal the tip of the other.
* $(u,v)$ to $(v,w)$ are "connected" since the tail of one *does* equal the tip of the other.

What is the name of this type of problem?

# Answer
The problem can be reduced to the *maximum independent set problem*. Let $G = (V,E)$ be the input instance of the problem. Then, create a new graph $G'$ such that each vertex in $G'$ corresponds to an edge in $G$. Two vertices in $G'$ have an edge between them if and only if the corresponding edges are connected in $G$. The following claim follows easily.

*Claim*: There exists a set of $k$ pairwise-disconnected edges in $G$ if and only if $G'$ has an independent set of size $k$.
> 2 votes

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


# Question
Title: Partition of two sets for multi-line fitting, NP-hard?
Given two sets of nonnegative numbers $X=\\{x\_1,...,x\_n\\}$ and $Y=\\{y\_1,...,y\_n\\}$, my problems consists in finding the partition $S \subseteq \\{1,...,n\\}$ and $\bar{S}=\\{1,...,n\\}\backslash S$ maximizing the following quantity: $$\frac{\displaystyle\left(\sum\_{i\in S}x\_iy\_i\right)^2}{\displaystyle\sum\_{i\in S}x\_i^2}+\frac{\displaystyle\left(\sum\_{i\in \bar{S}}x\_iy\_i\right)^2}{\displaystyle\sum\_{i\in \bar{S}}x\_i^2}.$$

Question: **is this problem NP-hard ?**

I tried many things, for example the particular case where $y\_i=1-x\_i$ which is easy because this amounts to sort the set X and testing the various possible partitions in that order.

And when I search the web, I only find references to the famous PARTITION problem, but I don't see how this problem could be related to mine.

Thanks for any help!

**EDIT:** (as requested in the comments, here is an explanation of the origin of the problem)

Let $\\{(x\_1,y\_1),...,(x\_n,y\_n)\\}$ be a set of $n$ points in the nonnegative orthant. I want to partition this set of points such that the first part is fitted by the equation $y=\beta\_1x$ and the other part is fitted by the equation $y=\beta\_2x$ using the ordinary least squares.

To paraphrase, I want to find the partition $S \subseteq \\{1,...,n\\}$ and $\bar{S}=\\{1,...,n\\}\backslash S$ (and the corresponding $\beta\_1$ and $\beta\_2$) minimizing $$\min \sum\_{i\in S}(y\_i-\beta\_1x\_i)^2+\sum\_{i\in \bar{S}}(y\_i-\beta\_2x\_i)^2.$$

Given $S$, the closed-form solution for $\beta\_1$ is $\beta\_1=\frac{\sum\_{i\in S}x\_iy\_i}{\sum\_{i\in S}x\_i^2}$ (same for $\beta\_2$ with $\bar{S}$) and by using these values and developping the objective function, we obtain the problem described above.

# Answer
> 1 votes
**This problem can be solved in polynomial time** in the manner alluded to by Yves Daoust in a comment. Specifically, I'll show that there exists an optimal solution in which every input point "above" some line through the origin can be placed in one part, and every other point in the other. This enables a simple algorithm involving $n-1$ steps, in each of which we guess the location of the threshold line to be between the $i$-th and $(i+1)$-th points taken in increasing order of angle from the $x$ axis, form the two parts accordingly, and optimise each part separately using least squares as usual; the solution with the lowest sum of costs is overall optimal. A slight wrinkle is that points on the $y$ axis can be assigned to either part without affecting the outcome, but this only makes it easier to find an optimal solution: We can ignore these points initially, then add them to either part at the end. This also conveniently avoids having to deal with infinite gradients.

What made the optimality of this algorithm challenging to show was actually the amount of "detail" in the objective function of the original problem statement, caused by the (usually desirable) fact that the $\beta\_i$ parameters were "hidden" (replaced with their closed-form optimal solutions). I wasn't able to make progress on that original problem statement. Once I focused on the later expression explicitly involving $\beta\_i$, the proof was much easier. The key is to treat $\beta\_1$ and $\beta\_2$ as being *given*, rather than being implicit quantities inferred from the data. What I in fact show below is that, **for *any* fixed pair of distinct slopes $\beta\_1$, $\beta\_2$, all optimal solutions partition the input points on either side of the line through the origin with gradient $(\beta\_1+\beta\_2)/2$**, with free choice of part for points lying exactly on this line. Any solution for given $\beta\_1$, $\beta\_2$ that violates this can be strictly improved by changing the part assignment of the erroneous points *without* changing $\beta\_1$ or $\beta\_2$, and this suffices to rule out such solutions from optimality (the fact that $\beta\_1$ and $\beta\_2$ can be reoptimised after "fixing" the partition to further improve the total cost is actually irrelevant to the proof). In particular, this rules out all "nonconvex" solutions -- that is, solutions in which the assigned partition changes more than once when considering points in increasing angular order.

## Proof sketch

Assume w.l.o.g. that $\beta\_1 \< \beta\_2$.

In the expression $$\min \sum\_{i\in S}(y\_i-\beta\_1x\_i)^2+\sum\_{i\in \bar{S}}(y\_i-\beta\_2x\_i)^2$$ each $(x\_i, y\_i)$ participates in exactly one of two ways: either as $(y\_i-\beta\_1x\_i)^2$, or as $(y\_i-\beta\_2x\_i)^2$. Choosing the smaller of these independently for each $i\in S$ is sufficient to minimise the entire expression. For simplicity I'll drop the subscripts on $x$ and $y$.

I'll now show that $y/x \< (\beta\_1+\beta\_2)/2$ implies $(y-\beta\_1x)^2 \< (y-\beta\_2x)^2$.

\begin{align} &y/x \< (\beta\_1+\beta\_2)/2\\ \implies& 2y \< (\beta\_1+\beta\_2)x\\ \implies& y-\beta\_1x \< \beta\_2x-y\tag{1} \end{align}

The RHS must be positive:

\begin{align} &y/x \< (\beta\_1+\beta\_2)/2 \< (\beta\_2+\beta\_2)/2 = \beta\_2\\ \implies& \beta\_2x-y \> 0\tag{2} \end{align}

The LHS could be $\< 0$, or $\geq 0$.

**Case 1:** $y-\beta\_1x \< 0\qquad(3)$ \begin{align} \implies& \beta\_2x-y \> \beta\_1x-y \> 0\textrm{, with the first \> because }x \> 0\textrm{ and }\beta\_2 \> \beta\_1\\ \implies& (\beta\_2x-y)^2 \> (\beta\_1x-y)^2\textrm{ since both sides of }\beta\_2x-y \> \beta\_1x-y\textrm{ are positive by }(2), (3)\\ \implies& (y-\beta\_2x)^2 \> (y-\beta\_1x)^2\textrm{ and we are done for this case.} \end{align}

**Case 2:** $y-\beta\_1x \geq 0\qquad(4)$ \begin{align} \implies& y-\beta\_1x \< \beta\_2x-y\textrm{ from }(1)\textrm{ with both sides nonnegative by }(2), (4)\\ \implies& (y-\beta\_1x)^2 \< (\beta\_2x-y)^2\\ \implies& (y-\beta\_1x)^2 \< (y-\beta\_2x)^2\textrm{ and we are done for this case.} \end{align}

In both cases, we establish that $y/x \< (\beta\_1+\beta\_2)/2$ implies $(y-\beta\_1x)^2 \< (y-\beta\_2x)^2$. Similar reasoning shows that this claim also holds with the inequalities reversed. The two results together give a rule to decide which part to assign to each input point.

---
Tags: complexity-theory, np-hard, partitions
---


# Question
Title: Finding shortest path between two points in a polygon whose vertices are given?
A contiguous single polygon is specified by it's vertices $(v\_1, \ldots, v\_n)$, given in order such that the line between $v\_i$ and $v\_{i+1}$ is an edge of the polygon (there's also an edge between $v\_n$ and $v\_1$). For example, a triangle might look like $v\_1=(0, 0), v\_2 = (1, 1), v\_3 = (2, 0)$.

Anyways, given two points $p\_1$ and $p\_2$ that lie within the polygon, I want to find the shortest path between them. If the polygon is convex, this is obviously simple and just the line between the points. But in the worst case, the polygon can literally trace out a maze.

If possible, I'd like an answer that reduces this to a problem of finding the shortest path in a graph.

In particular, one idea I have is that, since the shortest path will have you always going between vertex to vertex (or between the initial/end point and a vertex), one constructs a graph of all vertices, with edges connecting them if there is a direct line (that doesn't exit the polygon) between them (and the edge having corresponding weight of the length of that direct line). This graph would also contain the start/end points, and edges between them and all their directly-accessible vertices. From there, you can just use something like A-star or Djikstra's on the graph to find the shortest path, I imagine.

The problems with my method are

1. given two vertices $v\_i$ and $v\_j$, how does one know whether the line between them doesn't exist the polygon?
2. Is there a significantly more efficient way of constructing the graph other than $O(n^2)$ checking every pair of vertices?
3. Is my method decently good, or is there a much more optimal standard solution for this problem?

I'd imagine that the solution to (1.) will take $O(n)$ time for each edge, making the entire algorithm take $O(n^3)$, which isn't...the best.

# Answer
> 2 votes
The graph that you defined is known as visibility graph. You can find a $O(n^2 \log n)$ algorithm here. There are other better algorithms stated in the first link. Note the algorithms are for the visibility graph over obstacles. However, you can use the same algorithm by creating a convex hull of the vertices of the polygon; and defining the region between the boundary of convex hull and the polygon to be obstacles.

---

There is dedicated chapter named ""Visibility Graphs" for the same problem in Computational Geometry book by Berg et al. You can find more recent results in its chapter notes.

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


# Question
Title: Why GPT model is a higher order hidden markov model
I have read the GPT-1 paper, and my understanding is that it works as follows: $U$ is input tokens, $h\_0=UW\_e+W\_p$, $h\_i=\text{transformer\_block}(h\_{i-1})$ and the output is a probability vector $P(u)=\text{softmax}(h\_nW\_e^T)$, and the hidden states are the final latent layer before softmax, so the hidden states are $h\_n(U)$? I do not really understand, how to formalise this as a hidden Markov chain similar to the definition in Wikipedia?

# Answer
> 1 votes
The statement that GPT is a higher order hidden Markov model should not be taken too seriously. It is intended as a slogan or intuition, not something that is intended to be be rigorously proven.

Let $x\_1,x\_2,\dots,x\_k$ denote the words of the text, in order ($x\_1$ is the first word, etc.).

GPT is a model for predicting the next word, given all prior words. In other words, it estimates $p(x\_i | x\_1,x\_2,\dots,x\_{i-1})$. Hopefully you can see how this resembles the formulation of a Markov model.

It is higher-order, because it uses *all* prior words to predict the next word, not just the previous few words.

---
Tags: machine-learning, artificial-intelligence
---


title: Sorting n-tuples

text:
# Question
Title: Sorting n-tuples
I've just hashed up the following hair-brained idea of how to sort n-tuples of integers, as demonstrated below with a set of 3-tuples:

```
[ 4 , 1 , 3 ]
[ 1 , 2 , 1 ]
[ 2 , 2 , 1 ]
[ 2 , 1 , 1 ]
[ 1 , 1 , 1 ]
[ 2 , 1 , 2 ]
[ 3 , 1 , 3 ]
[ 1 , 2 , 2 ]
[ 1 , 1 , 3 ]
[ 1 , 1 , 2 ]
[ 3 , 1 , 1 ]
[ 3 , 1 , 4 ]

```

First "partition" data by 1st index, thusly (as shown by the dotted lines)

```
[ 1 , 2 , 1 ]
[ 1 , 2 , 2 ]
[ 1 , 1 , 3 ]
[ 1 , 1 , 2 ]
[ 1 , 1 , 1 ]
......................
[ 2 , 1 , 2 ]
[ 2 , 2 , 1 ]
[ 2 , 1 , 1 ]
......................
[ 3 , 1 , 1 ]
[ 3 , 1 , 4 ]
[ 3 , 1 , 3 ]
......................
[ 4 , 1 , 3 ]

```

Further next, I "partition" the previous partitions by the 2nd index

```
[ 1 , 1 , 3 ]
[ 1 , 1 , 2 ]
[ 1 , 1 , 1 ]
.....................
[ 1 , 2 , 1 ]
[ 1 , 2 , 2 ]
......................
[ 2 , 1 , 2 ]
[ 2 , 1 , 1 ]
......................
[ 2 , 2 , 1 ]
......................
[ 3 , 1 , 1 ]
[ 3 , 1 , 4 ]
[ 3 , 1 , 3 ]
......................
[ 4 , 1 , 3 ]

```

Finally I partition by 3rd index

```
[ 1 , 1 , 1 ]
[ 1 , 1 , 2 ]
[ 1 , 1 , 3 ]
.....................
[ 1 , 2 , 1 ]
[ 1 , 2 , 2 ]
......................
[ 2 , 1 , 1 ]
[ 2 , 1 , 2 ]
......................
[ 2 , 2 , 1 ]
......................
[ 3 , 1 , 1 ]
[ 3 , 1 , 3 ]
[ 3 , 1 , 4 ]
......................
[ 4 , 1 , 3 ]

```

This seems to have the potential of being cache-friendly. Is it a sensible algorithm (or totally stupid) or have I reinvented the wheel here?

# Answer
You've rediscovered radix sort.
> 1 votes

# Answer
You don't tell us how you perform the "partitions", and in particular how you perform the sorts on the respective tuple elements. So it is hard to say if your rediscovered a radix-sort-like procedure or just successive sorting passes.

By the way, it is probably more efficient to use a standard sort with a lexicographical comparison function (compare the first components, and in case of equality compare the second, and so on), as the number of moves can be lower and some comparisons are spared.
> 2 votes

---
Tags: sorting
---


title: Solve Recurrence Equation: ()=(−4)+^2

text:
# Question
Title: Solve Recurrence Equation: ()=(−4)+^2
I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method. I was wondering if what I write below was correct and obviously the result:

$T(n) = n^2 + T(n-4) = n^2 + \[n^2 + T(n - 8)\] = n^2 + n^2 +\[n^2 + T(n-12)\] = n^2 + n^2 + n^2 + \[n^2 + T(n-16)\] = ...$

In general we can say that $T(n)$ is done in the following way:

$$T(n) = \sum\_{i=0}^{\frac{n-5}{4}} n^2 + T(n-(4+4i))$$

Note that the summation takes that form because $T(n-(4+4i)) = T(1) = 1$ when $( −(4+4) ) = 1$ which occurs for $i = \frac{n-5}{4}$

So it would be more correct to write T(n) as follows:

$$T(n) = \sum\_{i=0}^{\frac{n-5}{4}} n^2 + 1 $$

At this point we leave out the constant 1 (which asymptotically is irrelevant) and focus on the summation :

$$T(n) = \sum\_{i=0}^{\frac{n-5}{4}} n^2 = n^2\sum\_{i=0}^{\frac{n-5}{4}} 1 = n^2 ( \frac{n-5}{4} +1) = O(n^3)$$

So overall we can say that :

$$T(n) = O(n^3)$$

# Answer
> 1 votes
As the recurrence only involves values four units apart, we rewrite with $n=4m$:

$$T(4m)=T(4m-4)+(4m)^2$$

or

$$U(m)=U(m-1)+16m^2.$$

The solution is

$$U(m)=U(0)+16\sum\_{k=1}^mk^2= U(0)+16\frac{m(m+1)(2m+1)}6$$ by the well-known formula for the sum of squares. From this

$$T(n)=T(0)+\frac{n(n+2)(n+4)}{12}$$ which is obviously $O(n^3)$.

---

Note that this result holds for $n$ multiple of $4$ only. For $n$ of the form $4m+i$, replace $T(0)$ by $T(i)$.

---
Tags: asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: A version of Bareiss algorithm or similar for symmetric matrices
A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use Cholesky decomposition which is more efficient than LU decomposition. If the entries of $A$ are all integers one can use the Bareiss algorithm which is similar to Gaussian elimination but only does divisions that are exact for integers thus avoiding fractions.

My question is: Is there a version of Bareiss algorithm or some other similar algorithm for symmetric integer matrices such that it would utilize the symmetry and use less operations than the basic Bareiss algorithm?

# Answer
Standard Cholesky requires square roots, which will break the integral property. The method you are after is probably LDL decomposition. https://en.wikipedia.org/wiki/Cholesky\_decomposition#LDL\_decomposition
> 0 votes

---
Tags: algorithms, matrices, linear-algebra
---


# Question
Title: Why does Java's HashSet have an underlying HashMap, not the other way around?
Why does Java's `HashSet` have an underlying `HashMap`, not the other way around? `HashMap` could have contained an internal `HashSet` of `Map.Entry`s, and `HashSet` wouldn't have stored a reference to an internal "dummy" `Object` per each element (while implementing the hashtable data structure itself). Is there (could there be) some idea behind this design that I don't understand?

> A `HashSet` of `Map.Entrys` would hash both the key and the value, so it would be impossible to access the value for a given key unless you already knew the value.
>
> *–a user of a sibling site*

Why couldn't `HashSet` hash just the key?

> At that point what you're describing is just a regular hashmap, isn't it?
>
> *–another user on the same site*

Ok. But there's no way it's the most efficient solution to pair each element with a meaningless object reference, is there?

```
// I simplified Java's actual HashSet code to convey the gist of its design

public class HashSet<E> {
    private HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public void add(E e) {
        return map.put(e, PRESENT);
    }
}

```

# Answer
If I am reading this right, you are saying that Java implements HashSet using HashMap, with NULL values, and are asking why you couldn't implement HashMap using (an alternate implementation of) HashSet?

If this is the case, then consider: This alternate implementation of HashSet would most likely NOT store the hashed elements of the set in a record containing both a reference to the set element AND a reference to an associated value, since there would be no associated value. How would one then implement HashMap using this? I.e how would one add the missing value reference slot to the element record?
> 0 votes

---
Tags: data-structures, java
---


# Question
Title: Orthogonal connectors with non-overlapping horizontal or vertical line segments
I have an upper row of $N$ equally spaced 'units' and a lower row of $N$ equally spaced 'units'. I would like to connect any of the upper row of units to the lower units via orthogonal connectors (consisting of horizonal and vertical line segments) such that although a horizontal and a vertical line segment, e.g. connecting $(3, 12)$ and $(4, 10)$, are allowed to intersect as shown below,

a horizontal line segment may not overlap another another horizontal line segment, and vice versa for a vertical line segment, e.g. connecting $(9, 10)$ and $(8, 19)$ as shown below

An acceptable connection between these units would look like this

where the vertical line segments no longer overlap.

The only restriction is that each unit cannot 'support' more than one connection.

---

Here is the preferred solution to the *special case* of connectors between corresponding neighbouring upper and lower units e.g. $(0, 11)$ and $(1, 10)$

# Answer
> 2 votes
Let the upper row units be denoted by $u\_1, \dotsc, u\_N$ and lower row units be denoted by $\ell\_1, \dotsc, \ell\_N$. You can divide the region between the upper and lower rows into a grid $G$ of size $2N \times 2N$. For connecting $u\_i$ to $\ell\_j$ simply choose the path $G\[1,2i\]$ -\> $G\[2i,2i\]$ -\> $G\[2i,2j-1\]$ -\> $G\[2N,2j-1\]$ (assuming $1$ based indexing).

Next, we show that for any two pairs $(u\_i,\ell\_j)$ and $(u\_p,\ell\_q)$ such that $i \neq p$ and $j \neq q$, the connections do not overlap.

*Proof*: Note that the horizontal line segment for connection between $u\_i$ and $\ell\_j$ uses row number $2i$ which is different from the row number $2p$, which is used by connection between $u\_p$ and $\ell\_q$ since $i \neq p$.

The vertical line segments uses the columns $2i$, $2j-1$, $2p$, and $2q-1$. Since an even numbered and odd numbered column can never overlap, we just need to check if $2i$ overlaps with $2p$ or $2j-1$ overlaps with $2q-1$. Since $i \neq p$ and $j \neq q$, overlapping is not possible.

---
Tags: algorithms, computational-geometry
---


# Question
Title: Why do we still need virtual memory in 21st century?
AFAIU, there are only two issues, that VM solves:

1. Scarcity of RAM;
2. Access control to "unknown" memory, where SW tries to read from or write to the memory it does not own or share with other processes.

While p.1) is becoming a non-factor for more use-cases, than it probably was in the past, are there any solutions for guarding against buggy/malicious SW without VM? Something that is not that involved as VM and more predictable (constant access time)? How can an embedded multi-core systems implement protection if there is no VM?

# Answer
A key benefit of virtual memory (besides simulation of more RAM than truly available) is that *every process* sees the *whole address space* available to itself. This greatly simplifies memory mapping for the applications. Together with processor time sharing, every process gets an own, private and huge computer.
> 3 votes

# Answer
> How can an embedded multi-core systems implement protection if there is no VM?

ARM Cortex M0+ with an MPU, as found in RP2040 for example (embedded multi-core controller), uses a limited number (namely 8) of configurable memory regions. Start, size, and protection bits can be set per region, and regions can overlap (which region takes priority is also configurable). Note that Cortex M0+ does not have an unprivileged execution mode, so this memory protection does nothing against malicious software - but that's not much of a concern for a microcontroller. That limitation is not inherent to this type of memory protection though.

In general, this type of memory protection is efficient and predictable, but not scalable: the number of regions must be small, since the MPU has to hold all regions in internal configuration registers at the same time and compare the address of each memory access to all bounds to find the region it's in. In parallel, of course, since it's in hardware - but that still doesn't scale very well.

Another alternative is some form of segmentation, where an advanced segmentation technique (not just a bare offset as in 8086) can support process isolation. But segmented memory is annoying to write software for, and tends to suffer from external fragmentation. Individual memory access when viewed in isolation can be efficient and predictable, without TLB misses, but a similar problem is off-loaded to software (which has a harder time dealing with it): segment registers and their hidden state are comparable to a software-managed TLB, but worse.
> 2 votes

# Answer
There are a lot more use cases for virtual memory. On top of address space separation as Yves pointed out, there are a bunch of others, for example:

* Sharing memory between processes. This is much more common than you think, since it's how running multiple copies of an executable, or shared libraries, are often handled.
* Memory-mapping files, which is a *much* more performant way to handle file I/O than an read/write-style API.

That last one is extremely important in modern computing. A modern operating system maintains a cache of data from disk. A read/write API means copying data between the buffer cache and process memory, but memory-mapped files means you can just map the buffer cache directly with no copying. Programs like database servers benefit enormously from this, because as RAM gets larger, databases also get larger.

Also, if you never modify the file, any part of the file you're not using require "allocating" RAM or swap. Compilers benefit from this, because they can just memory-map source code files.

Virtual memory can also simplify programming by effectively eliminating external fragmentation. On a 64-bit machine, there is more address space than you will ever need. So if you need an array but don't know how big it will be, you can reserve gigabytes of address space but only allocate as much actual RAM as you find that you need within that space.

One final thing to consider is that "scarcity of RAM" became a *financial* consideration when people started moving their services, written in managed languages, onto cloud providers.

Managed languages like Java or Python typically give you less control over how much RAM you use than a systems language like C++ or Rust. Cloud providers often have a limited range of virtual machines that you can deploy onto, and the amount of RAM typically scales with the number of CPUs. If you don't need that many GPUs, but do need working storage, it can be worth it to pay for a smaller machine and use swap storage.
> 1 votes

---
Tags: virtual-memory
---


# Question
Title: Can we further minimize this regular expression: a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*
I am trying to create the regular expression for the automaton named "full closure" in the following diagram using the arden's theorem:

Since, we have 3 accepting states, we would find 3 different regular expression and then just union them up. I was able to find regular expression for q0, q1 but facing issues when trying to find one for q2:

```
q0 = a*
q1 = a*b* + b*
q2 = a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c*

EDIT: I was able to minimize the final expression that is r = q0 + q1 + q2, to

 r = a*b*c* + a*bc* + b*c*

 can we further minimize this expression to "a*b*c*"?

```

My question is can we further minimize this regular expression for q2 and overall when we union? The "full closure" automata recognizes language "a\* b\* c\*"

# Answer
As $a^{\*}bc^{\*}$ and $b^{\*}c^{\*}$ are subsets of $a^{\*}b^{\*}c^{\*}$ we can write the regular expression as $a^{\*}b^{\*}c^{\*}$.
> 0 votes

# Answer
Obviously yes because every single string ends in c\*.

Note that (x)\*y is always a superset of y, so if both are present then y can be removed. We do this and get

$a^\*(ac^\* + b^\*bc^\* + b^\*cc^\* ) + c^\*$

$b^\*cc^\*$ includes $c^\*$ except $\epsilon$, so this is $a^\* (a + b^\*b + b^\*c) c^\* + \epsilon = a^\* (a + b^\*(b + c)) c^\* + \epsilon $
> 0 votes

# Answer
```
a*(ac* + bc* + cc* + b*bc* + b*cc* ) + b*(bc* + cc*) + c* =
(a*a + a*b + a*c + a*b*b + a*b*c + b*b + b*c + ϵ)c* =
(a*a + a*b*b + a*b*c + ϵ)c* =
a*(a + b*b + b*c + ϵ)c*

```
> 0 votes

---
Tags: automata, regular-expressions
---


# Question
Title: maze solving algorithms (pledge algorithm)
I saw this maze, and tried to apply pledge algorithms to it. But I am not able to solve this maze using this algorithm. What am I missing/doing incorrectly?

PLEDGE ALGORITHM: in both cases we don't get to exit.

you can read about these algorithms at:

http://en.wikipedia.org/wiki/Maze\_solving\_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm

# Answer
> 1 votes
If you use wall following with the right hand, you should place your hand on the right wall.

For the pledge algorithm your source says

> It's a guaranteed way to reach an exit on the outer edge of any 2D Maze from any point in the middle, however it's not able to do the reverse, i.e. find a solution within the Maze.

There is no guarantee that the exit reached is the one labeled "Exit" instead of the one labeled "Start".

# Answer
> 0 votes
The Pledge algorithm requires you to be able to recognize the entrance whenever you stumble upon it and treat it as a wall.

In essence, it is as if you initially walked into the maze and closed the entrance door behind you, immediately putting yourself at an interior point in the maze—the scenario that the Pledge algorithm is suited for.

---
Tags: algorithms, robotics
---


title: Minimum dominating set on trees

text:
# Question
Title: Minimum dominating set on trees
I am working on an NP-Complete problem, i.e., the dominating set. Given a graph $G = (V, E)$, a set $S$ is a dominating set if every vertex $v \in V \setminus S$ has at least one neighbor in $S$. I am looking for the complexity of the problem in trees. I have tried the greedy method to solve this problem. But, looks like a greedy algorithm would not work on trees. Is the problem polynomial time solvable? If yes, could someone point me to any references to this result?

# Answer
> 2 votes
The problem is solvable in linear time by dynamic programming.

Root a the input tree $T$ in an arbitrary vertex and let $T\_v$ be the subtree of $T$ rooted in v.

Let $OPT\[v\]$ denote the size of a minimum dominating set of $T\_v$. Let $OPT^-\[v\]$ denote the minimum size of a subset of vertices of $T\_v$ that dominates all vertices in $T\_v$ except, possibly, for $v$. Finally, let $OPT^+\[v\]$, denote the size of a minimum dominating set of $T\_v$ that necessarily includes $v$.

If $v$ is a leaf then $OPT\[v\]= OPT^+\[v\] = 1$ and $OPT^-\[v\] = 0$.

Otherwise let $u\_1, \dots, u\_k$ be the children of $v$ in $T$. $$ OPT^+\[v\] = 1 +\sum\_{i=1}^k OPT^-\[u\_i\] $$

$$ OPT^-\[v\] = \min\\{OPT^+\[v\], \sum\_{i=1}^k OPT\[u\_i\] \\} $$

$$ OPT\[v\] = \min \begin{cases} OPT^+\[v\]; \\ \min\_{j=1,\dots,k} \left( OPT^+\[u\_j\] + \sum\_{\substack{i=1,\dots,k \\ i \neq j} } OPT\[u\_i\] \right). \end{cases} $$

Notice that the above formulas for $v$ can be evaluated in time $O(k)$. The only one for which this might not be obvious is the second argument of the minimum in $OPT\[v\]$. This can be handled by first computing $S = \sum\_{i=1}^k OPT\[u\_i\]$ (in $O(k)$ time) and then noticing that, for a $j=1,\dots, k$, the desired quantity can be found in constant time as $S - OPT\[u\_j\] + OPT^+\[u\_j\]$.

---
Tags: graphs, np-hard, polynomial-time
---


title: Detect contour from point grid

text:
# Question
Title: Detect contour from point grid
Suppose we have a grid of points (which can also be very dense 10000x10000) like the one in the figure in which the points are marked with two different colors.

What is the best algorithm from a performance point of view that allows me to reconstruct the outline of the red dots connecting the points of the grid itself? Here is the result I expect.

In the figure the contour is continuous, but in reality I'm also fine with finding a stepped contour that connects the border points between the red and blue ones. In general the region of red points is always connected but may not be convex. The algorithm will be added inside a simulation routine, so it should be as fast as possible.

# Answer
Marching squares might be the simplest. Imagine that the red points are samples with value -1 and the blue points are samples with value 1, then look for a line with value 0.

This algorithm is optimal, in that you have to visit each cell at least once, and this visits each cell once.

Just for completeness, if you did want a smoother outline, there are some options. One option is to "blur" the image first (either explicitly or implicitly), which would give the marching squares algorithm a little more information to go on.

Another option is to smooth the contour as a post-pass, but to do that, you need an appropriate representation and an appropriate definition of "smooth".

To help you in your search for that step, cartographers refer to producing lower-resolution versions of contours "generalising", which is an overloaded word. In meteorology and spatial data science, contour lines on maps are also known as "isopleths".
> 1 votes

---
Tags: square-grid
---


# Question
Title: What are the necessary requirements for proving NP is closed under complement?
I've had the following question on a test and I answered: 'False', my answer was incorrect and I'm trying to understand why.

$VC = \\{\<G,k\> |\ G =$ undirected graph with a vertex cover of size $k\\}$

$IS = \\{\<G,k\>|\ G =$ undirected graph with an independent set of size $k\\}$

**Ture or False:**

**Assuming there exists a language $A$ such that: $ (VC≤\_P A) \land (\overline{A} ≤\_P IS) $ then NP is closed under complement**

When trying to prove it is true I tried to use the following theorem:

> $L\in NPComplete \land L\in coNP → = → NP$ is closed under complement

My attempt:

We know both VC and IS are NPComplete problems, which implies from the reductions that:

$A \in \text{NP-Hard}$ and $\overline{A}\in NP$

the only thing missing is $A\in NP$ for satisfying the condition: $A\in NPComplete \land A\in coNP$ and reaching the conclusion: $NP=coNP$

What am I missing?

# Answer
ok apparently $\overline{IS}$ is also $NPComplete$ which means $A \in NP$ and we already know from the reduction that $A\in \text{NP-Hard}$ which mean $A\in NPComplete$

we also know that $\overline{A}\in NP$

$→A\in NPComplete \land A\in coNP → NP=coNP →$ NP is closed under complement
> 0 votes

---
Tags: complexity-theory, graphs, np-complete, np-hard, np
---


# Question
Title: Need help with a proof: L is recursively enumerable if and only if L is Turing recognizable
I am unable to understand this proof

> L is recursively enumerable if and only if L is Turing recognizable

If anyone can prove this, that would be great help

# Answer
> 0 votes
If $L$ is recursively enumerable then, given $x \in \Sigma^\*$, you can iterate over all $y \in L$ and check whether $x=y$. If that's the case accept, otherwise continue with the next $y$. After examining the last $y \in L$ (if any) reject. If $x \in L$, this procedure eventually accepts. If $x \not\in L$ this procedure either never halts or it rejects.

If $L$ is Turing recognizable by some TM $T$ then you can execute $T(x)$ for all $x \in \Sigma^\*$ in a dovetail fashion. If $x \in L$, $T(x)$ will eventually halt and accept, and you can output $x$. If $x \not\in L$, $T(x)$ will either never halt or it will reject (and you ignore $x$).

---
Tags: turing-machines, computability, recursively-enumerable
---


# Question
Title: On hardness of finding dominating sets in triangle-free regular graphs
A $k$-regular graph is one in which every vertex has degree *k*. A *triangle-free* graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices such that $\forall v \in (V(G)\setminus D)$, $v$ has a neighbour in $D$.

Is anything known about the hardness of deciding whether there is a dominating set of a given size in $k$-regular *triangle-free* graphs?($k\geq3$). It is already known that this problem is $NP-complete$ for *triangle-free* graphs.

# Answer
We show that the minimum dominating set (MDS) problem is $\mathsf{NP}$-hard on $3$-regular triangle-free graphs. We show this by a reduction from the bipartite graphs of maximum degree $3$.

The MDS problem is $\mathsf{NP}$-hard on the bipartite graphs with maximum degree $3$ as shown in Theorem 6 of this paper. The reduction would imply that the problem is $\mathsf{NP}$-hard on $3$-regular triangle-free as well.

The following is the reduction:

Let $G$ be any bipartite graphs of maximum degree $3$. Note that $G$ is already triangle-free since it is bipartite. Moreover, we can assume that all the vertices in $G$ have degree either $2$ or $3$. Now, we create a $3$-regular triangle-free $G'$ as follows. For every vertex $v \in G$ of degree two, we define a gadget $G\_{cv}$ shown below:

We connect vertex $v$ to gadget $G\_{cv}$ with edge $(v,v\_a)$. Let the new graph be $G'$. Note that $G'$ is $3$-regular triangle-free graph by construction. Now, the following claim easily follows:

*Claim:* $G$ has a dominating set of size $k$ if and only if $G'$ has a dominating set of size $k+2|V\_t|$, where $|V\_t|$ are the number of vertices in $G$ with degree two.

*Proof*: ($\to$) Suppose $G$ has a dominating set of size $k$. For every gadget $G\_{cv}$, we add the vertices $v\_b$ and $v\_c$ to the dominating set. The vertices $v\_b$ and $v\_c$ dominates all the vertices in a gadget. Thus, $G'$ has a dominating set of size $k + 2|V\_t|$.

($\gets$) Suppose $G'$ has a dominating set of size $k + 2|V\_t|$. It is easy to see that to dominate all vertices in a gadget, we require at least two vertices. Moreover, if $v\_a$ is included in the dominating set then we still require two more vertices to dominate all the vertices in a gadget. Therefore, if any gadget has vertex $v\_a$ included in the dominating set, we can replace vertex $v\_a$ with $v$ in the dominating set. Moreover, the other vertices of the gadget chosen in the dominating set, we replace them with $v\_b$ and $v\_c$. Thus, $G'$ has a dominating set of size at most $k + 2|V\_t|$ such that it does not include any vertex $v\_a$ and each gadget contains exactly two vertices. Thus, the vertices in the dominating set that comes from $G$ have size at most $k$ and they dominate all the vertices of $G$. Thus, $G$ has a dominating set of size $k$.
> 1 votes

---
Tags: graphs, np-complete, reference-request, combinatorics, decision-problem
---


# Question
Title: nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive
I have a question I need to give the NFA of the following language: L={w belongs to (a,b)\*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa and ends with aa. I did this:

but if I turn it into the DFA I get this:

but with this DFA if we have the word "baab" it ends in an accepted state which is wrong. can anyone please help me know where my mistake is.

---

Update: I did starts with aa as DFA and end with aa as DFA I did the union I got the DFA. if I wanted the NFA should I do D1 and D2 as NFA instead of DFA?

# Answer
> 0 votes
The incorrect behavior of the DFA comes from the fact that NFA is also wrong. Look at the initial state: it contains a self-transition labelled $b$. You are effectively "discarding" all leading $b$s. Instead, your NFA/DFA needs to check whether a word starts with $aa$ and "remember" it (via new states).

Probably the easiest way to solve this exercise is that of building a DFA $D\_1$ for strings that start with $aa$ and another DFA $D\_2$ for strings that end with $aa$. Designing $D\_1$ and $D\_2$ should be trivial. Finally, combine $D\_1$ and $D\_2$ into a NFA by adding a new initial state and two $\epsilon$-transitions.

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?
# Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?

I am trying to write a program to analyze Java programs and figure out the transitive closure of the callgraph of each main method. Consider the program below:

```
class Foo{
    void runOne();
    void runTwo();
}
class Bar extends Foo{
    void runOne(){ }
    void runTwo(){ }
}
class Qux extends Foo{
    void runOne(){ }
    void runTwo(){ }
}

class MainA {
    public static void main(String[] args) {
        new Bar().runOne();
    }
}
class MainB {
    public static void main(String[] args) {
        new Qux().runTwo();
    }
}
class MainC {
    public static void main(String[] args){
        Foo[] foos = {new Bar(), new Qux()};
        for(Foo foo: foos){
            foo.runOne();
        }
    }
}

```

Here, we would expect :

1. `MainA`'s transitive callgraph would include `Bar#runOne`
2. `MainB`'s transitive callgraph would include `Qux#runTwo`
3. `MainC`s transitive callgraph would include `Bar#runOne` and `Qux#runOne`

To get to that conclusion, we need to traverse the callgraph via two different kinds of edges: each method can both call other methods, or it can instantiate classes, and only if both a class is instantiated and a method is called do we consider that method part of the callgraph.

Method calls and instance instantiations can appear in different places, e.g.

```
class MainD {
    public static void main(String[] args){
        helperA(helperB());
    }
    public static void helperA(Foo foo){
        foo.runTwo();
    }
    public static Foo helperB(){
        return new Bar();
    }
}

```

Here `helperA` calls `Foo#runTwo`, but we don't know what `Foo` is until we get to `main` and we see that `helperB` instantiated a `new Bar()`, meaning the transitive callgraph for`MainD.main` is `Bar#runTwo`. In fact, neither `helperA` nor `helperB` would be enough to draw that conclusion on their own, even though `MainD.main` which calls them is able to.

Effectively, it seems like we need to do a breadth/depth-first graph traversal, with one kind of node representing each method definition, but two kinds of edges: one representing method calls, and one representing class instantiations. And we only add a node to our traversal if it has *both* kinds of edges pointing to it.

For now, I'm ignoring the additional complexities of mutable state, exceptions, reflection, and so on.

Is there a name for this kind of analysis/algorithm, or any prior art or literature written up e.g. about its limitations or implementation strategies? I can probably hack something together myself, but I'd rather build upon any prior work that exists rather than having to re-discover it from first principles.

# Answer
I suspect you might be interested in Class Hierarchy Analysis (CHA), Rapid Type Analysis (RTA), or Variable Type Analysis (VTA). These are three methods for efficient construction of a call graph in object-oriented languages like Java. For instance, some of these algorithms are implemented in SOOT.

There is also other work on virtual method call resolution for Java, which you can search out using Google Scholar. (For instance, you can use points-to analysis for this purpose, e.g., Anderson's algorithm.)
> 1 votes

---
Tags: algorithms, graphs, programming-languages, search-algorithms, compilers
---