# Question
Title: Undecidability of TMs recognizing a decidable language
The language $L = \\{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \\}$ is given.

I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it should be similar to prove to the Rice Theorem, using a reduction. However, this hint isn't very helpful to me.

# Answer
1. You want to prove that the language of deciders—the language of Turing machines whose language is decidable—is not recognizable.
2. To prove this by reduction, we need to show that if we assume we have a recognizer $f(M)$ for the language—that is, it correctly outputs YES for every decider $M$ and either runs forever or returns NO for non-deciders—then we can use $f(M)$ as a subroutine to build a recognizer for some unrecognizable language. Because this is impossible, it will establish that no such recognizer $f$ exists, QED.
3. Here is one common example of an unrecognizable language: The language $\overline{A}\_{TM}$ of all pairs (M,w) where M is a Turing machine that runs forever on input w. (This is the complement of the halting problem.)
4. If we have a subroutine $f(M)$ that recognizes whether M is a decider, I claim we can build a TM that recognizes $\overline{A}\_{TM}$. Because that's impossible, this construction will prove by contradiction that $f$ doesn't exist, which shows that the language of decidable Turing machines is *not* actually recognizable.
5. In the proof, it will be useful to have an example of a decidable and undecidable language.

* Let $H(M,w)$ be the Turing machine that simply simulates $M$ on $w$ and returns YES if the simulation halts (or runs forever if the simulation does). Note that the language of $H$ is the language of (M,w) such that M halts on input w—the halting problem—so it's an **undecidable language**. $H$ is *not a decider*.
    * Let $E(x)$ be the Turing machine that ignores its input and loops forever. The language of $E$ is empty $\varnothing$, which is a **decidable language**. $E$ *is a decider*.
6. We're aiming to solve the $\overline{A}\_{TM}$ problem ("Does M loop forever on input w?") using a subroutine for solving the decider problem ("Is M a Turing machine with a decidable language?").

To relate these two problems together, it would be useful if we could take in (M,w) for the $\overline{A}\_{TM}$ problem and convert it into a machine $\tilde M$ whose language is decidable if and only if $M$ loops forever on input $w$. That way, we can recognize whether (M,w) is in $\overline{A}\_{TM}$ by recognizing (using $f$) whether $\tilde M$ is a decider.

We can do exactly that! Given an input (M,w), we will cleverly design a new machine $\tilde M$ which behaves like $E$ if M loops forever on w, or behaves like $H$ if M halts on w. In other words, $\tilde M$ has a decidable language if M loops forever on w, and has an undecidable language if M halts on w.

Here's how to do it:

> Given an input (M,w), define $\tilde M$ as the machine which first ignores its input and just simulates $M$ on $w$. If that simulation halts, then the machine passes its input to $H$ and returns whatever $H$ returns.

Note that if M loops forever on w, then $\tilde M$ loops forever on all inputs and hence has an empty language. If M accepts w, then $\tilde M$ just does whatever $H$ does. Because $H$ has an undecidable language, $\tilde M$ has an undecidable language in this case.

7. Finally, here's a recognizer for $\overline{A}\_{TM}$: \> Given an input (M,w), construct the machine $\tilde M$ which first ignores its input and just simulates $M$ on $w$. If that simulation halts, then the machine passes its input to $H$ and returns whatever $H$ returns. \> \> Feed this new TM $\tilde M$ into $f$ and return its answer.
8. As with many reduction proofs, this proof relies on a convoluted construction. It requires some explanation.

Note that this definition cleverly makes the language of $M^\prime$ depend on whether M loops forever on w or not:

If M loops forever on input w, then $M^\prime$ will loop forever trying to simulate it. So in this case $M^\prime$ never accepts anything — its language is empty. Hence $M^\prime$ will have a decidable language.

If M halts on input w, then $M^\prime$ will always pass its input to $H$ and return whatever it does. In this case, the language of $M^\prime$ will just be the language of $H$, which is undecidable. Hence $M^\prime$ will have an undecidable language.

Therefore, to recognize whether M loops forever on input w, just compute $f(M^\prime)$. If this subroutine returns YES (M' is a decider), you return YES (M loops forever on input w).

This is a recognizer for $\overline{A}\_{TM}$, which we know is impossible, therefore $f$ (a recognizer for whether a TM is a decider) can't actually exist, QED.
> 1 votes

# Answer
Given a machine $A$, construct a machine $M$ which on input $x$, acts as follows: run $A$ on the empty input, and if it ever halts, run the Turing machine encoded by $x$ on the empty input.

If $A$ halts on the empty input then the language $M$ recognizes is the halting language, while if $A$ doesn't halt on the empty input then the language $M$ recognizes is the empty language.
> 0 votes

---
Tags: turing-machines, undecidability
---


title: Lower bound on computing $x^n$

text:
# Question
Title: Lower bound on computing $x^n$
I know that we can compute $x^n$ in $\log n$. Are there any lower bound for computing $x^n$?

# Answer
> 1 votes
If $n$ is given as a number in some positional number system, say base 2 or base 10, then $\Omega(\log n)$ is a lower bound, since figuring out the value of n alone takes $\Omega(\log n)$ steps.

---
Tags: algorithms, lower-bounds
---


# Question
Title: How to reduce clique to Hamiltonian cycle in an undirected graph?
Recently, I studied how to prove a problem is NP-complete. From the book Introduction to Algorithms (CLRS, 3rd edition), there is an example of reducing vertex cover to Hamiltonian cycle. I believe that it is possible to directly reduce clique to Hamiltonian cycle in an undirected graph, but how to convert it in polynomial time?

\[Deleted question\]

# Answer
You can reduce clique to SAT (Cook's theorem). You can reduce SAT to Hamiltonian cycle (see e.g. Easy reduction from 3SAT to Hamiltonian path problem for the main ideas). Compose these two, and you get a reduction from clique to Hamiltonian cycle.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Data structure for fast insertion and fast random element removal
I'm looking for a data structure that supports the following operations:

*add(elem)* \- Add an element to the data structure.
*remove\_random()* \- Remove and return a random element.

The best I got so far is just shuffling a list on every insertion (or on every lookup), and popping from the top. However, this can be quite slow, so I'm looking for a more specialized data structure. Assume we can generate random numbers for free.

# Answer
> 29 votes
You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement `remove_random()` generate a random index $k$ between $1$ and $n$, swap $A\[k\]$ with $A\[n\]$ and delete (and return) $A\[n\]$.

If you want a non-amortized worst-case bound on the time complexity, then an AVL in which each node $v$ has been augmented to also store the size of the subtree rooted in $v$ supports both those operation in $O(\log n)$ worst-case time per operation.

To implement `remove_random()` simply generate a random number $k$ between $1$ and $n$ and find the element $e$ of rank $k$ in the tree. Then delete $e$ from the tree and return it.

# Answer
> 15 votes
Since you clearly don't care about the order of elements changing, I think the simplest approach is to use a resizable array (like C++'s `std::vector` or Java's `java.util.ArrayList`). When you remove an element, if it's not the last element, you just move the last element to take its place.

That gives amortized-constant-time *add* and constant-time *remove\_random*.

For example, in Java:

```
public final class Example<E> {
    private final Random random = new Random();
    private final ArrayList<E> elements = new ArrayList<>();

    public void add(final E elem) {
        this.elements.add(elem);
    }

    public E removeRandom() {
        if (this.elements.isEmpty()) {
            throw new NoSuchElementException();
        }
        final int n = this.elements.size();
        Collections.swap(
            this.elements,
            this.random.nextInt(n),
            n - 1);
        return this.elements.remove(n - 1);
    }
}

```

# Answer
> 9 votes
Another solution that provides amortized constant time operations is to use a dynamic array with insertion and removal at the end, just as in Steven's answer, but swap the last element with a random one *after insert*, instead of *before removal* as in Steven's method.

That is, instead of doing what Steven suggests (in pseudocode):

```
public method insert(element):
   array.push_to_end(element)

public method remove_random():
   swap_last_with_random()
   return array.pop_from_end()

private method swap_last_with_random():
   i = array.length - 1
   j = random(min: 0, max: i)
   array.swap_elements_at(i, j)

```

you can equivalently do:

```
public method insert(element):
   array.push_to_end(element)
   swap_last_with_random()

public method remove_random():
   return array.pop_from_end()

```

with `swap_last_with_random()` defined as above.

Both of these implementations can be easily shown to work correctly by induction, and they have the same asymptotic time complexity, but their performance in practice may differ.

In particular, with my implementation, multiple consecutive removals require only reading elements sequentially from the end of the array and no writes to the array at all, which might yield a more cache-friendly access pattern. Also, the fact that my method doesn't need to modify the contents of the array during element removal could potentially make implementing efficient concurrent access easier (although it's still not trivial, since removal still changes the *length* of the array).

All that said, I make no claim that this method is actually any faster in practice than Steven's approach. Depending on your access patterns, it could even be slower. But if performance matters, it's at least worth comparing both of them.

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


# Question
Title: Confusion about whats being processed in a quantum computer
Please correct me if im wrong but this is how I think quantum computers work.

Say we have a q-bit. The q-bit is put through a quantum gate to put it into a superposition and manipulate its probabilities.

We can represent this q-bit just like a normal bit on a vector where a normal bit would, when represented on a circle, be either on the x-axis or on the y-axis.

The q-bit however, being in a superposition between 0 and 1,is between 0 and one on the circle.

Since the quantum state vector has length one and the probabilities determine where the quantum state vector will be, the square-route of the probabilities are how the probabilities are represented on the circle(pythagorean theorem).

The quantum gates act like the matrix of the vector in this case.

But I dont actually understand whats actually being calculated in those steps, what is the actual goal of finding out where the q-bit is on the circle.

Say you wanted to calculate 6 + 2 how would this be implemented in this example?

My assumption is that you'd have to configurate the quantum gate in a way that in the end the probabilities turn out in favor of 8.

But then again when going over this assumption it sounds kind of stupid.

Also note that I didnt actually have vectors in school yet since im only in eight grade and im researching this topic out of pure interest.

I only watched one explaining in detail how quantum computers work since it was the only good I found that didnt assume you already learned this in some way and know about what way this is going.

So dont immediately get angry at me for not using the best terms or phrases and not even using the correct format.

Thanks to everyone who takes the time to explain it to me :D

# Answer
> 1 votes
You are not far off the mark - quantum computations are all about probabilities.

You may say that a quantum program (i.e, a series of quantum gates) computes $n+m$ (when $n,m$ are inputs), if with "high probability", the end result will be exactly $n+m$.

The role of the quantum mechanics here are represented in the intermediate states - **before** the end result is "measured". This so-called operation of "measuring", creates a random bit according to probability distribution that the qbit specified.

So even though the input and the output are **particular** bits - everything in the middle are just probability distributions with the fancy name of "qbits". Therefore, it is natural to define the computation of quantum computers in probabilistic terms.

---

If you are interested, the theoretical definition of "with high probability" is having probability of *at least* $\frac{2}{3}$. This can be seen in the definition of the BQP complexity class for example.

---
Tags: quantum-computing
---


# Question
Title: Efficient Way To Compute Points Where Convolution Equals Zero
I want to model the following procedure. Given a shape $L\subseteq\mathbf{R}^2$ (imagine e.g. a letter) and another (could be convex if it makes life easier) shape $K\subseteq\mathbf{R}^2$, I want to compute $\\{p\in\mathbf{R}^2: ((1-1\_L)\*1\_K)(p)=0\\}$ (in terms of convolution) or $\\{p\in\mathbf{R}^2:\forall k\in K:p+k\in L\\}$ in an alternative formulation, e.g. all points $p$ such that $K$ centered at $p$ fits into $L$. What strategies do I have to perform this at high resolution?

One idea I had was that for every shape $K$ there should exist a set of points $\\{d\_i\\}\_i$ such that if I already know that $p+d\_i$ is in my set for all $i$ then $p$ must be in the set as well. E.g. if $K$ is the ball with radius $1$ then $\\{(0,1),(1,0),(0,-1),(-1,0)\\}$ would be such a set. Using this I could create some grid where I compute the function first and from there deduce some values, then maybe proceed with a finer grained grid?

# Answer
I'll describe one way to solve this, with a sweepline algorithm, which I think works. The approach is a bit complex, though it is fully general, should be efficient, and gives the exact answer.

My approach is inspired by the Bentley-Ottmann algorithm, so if this answer is hard to follow, it might be worth reading and understanding that first.

I will assume that the shapes $L,K$ are the interior of polygons, and $K$ is convex. I assume we know the vertices of these polygons. An edge of a polygon is a line segment between two adjacent vertices (i.e., a line segment on the perimeter). Let $p=(p\_x,p\_y)$, i.e., $p\_x$ is the $x$-coordinate of $p$ and $p\_y$ is the $y$-coordinate of $p$.

We'll use the following fact about containment:

Fact: If there are no intersections between the edges of $K,L$, and one vertex of $K$ is inside $L$, then $K \subseteq L$, i.e., $K$ is contained in $L$.

(See e.g. https://stackoverflow.com/a/4833823/781723 and https://stackoverflow.com/a/52827803/781723.)

Let $v$ be a vertex of $K$ (any vertex; say the leftmost one). Then the goal is equivalent to finding all $p$ such that there is no intersection between the edges of $K+p$ and $L$, and such that $v+p$ is inside $L$. To find this set of $p$, we'll use a sweepline algorithm.

At any time step in the execution of the sweepline algorithm, we'll have a vertical sweepline at some particular $x$-coordinate, namely at $p\_x$. The goal will be to find all values of $p\_y$ such that $K+(p\_x,p\_y)$ is contained in $L$, i.e., such that there is no intersection between the edges of $K+(p\_x,p\_y)$ and $L$, and such that $v+(p\_x,p\_y)$ is inside $L$. So let's take a moment to figure out how to achieve that goal. Then, we'll need to sweep the value of $p\_x$ in an increasing way, so I'll need to discuss how to achieve that.

Given a fixed value of $p\_x$, here is how we can find all satisfactory $p\_y$. Consider any edge $e$ of $K$ and any edge $f$ of $L$. Then the set of $p\_y$ such that $e+(p\_x,p\_y)$ does not intersect $f$ is a union of two intervals and is easy to compute. Thus, the set of $p\_y$ such that $e+(p\_x,p\_y)$ does not intersect any edge of $L$ is a union of intervals and is also easy to compute. Similarly, the set of $p\_y$ such that $v+(p\_x,p\_y)$ is inside $L$ is another union of intervals that is also to compute. We can intersect those two sets, to get the set of satisfactory values of $p\_y$, represented as a union of disjoint intervals.

Notice that in this set of values of $p\_y$, the endpoint of each interval corresponds to a critical value of $p\_y$ that causes an intersection between $e+(p\_x,p\_y)$ and $f$, for some edges $e,f$ of $K,L$ respectively.

What if we increase $p\_x$ a tiny bit? What will that do to the endpoint of one of those sets? It'll change the critical value of $p\_y$ a tiny bit, and it is easy to compute this change if you know the corresponding $e,f$. In particular, in some neighborhood of this $p\_x$, there is a linear relationship between $p\_x$ and this interval endpoint (this critical value of $p\_y$). You can also compute the region of validity of this linear relationship (its end corresponds to the $x$-coordinate of the endpoints of $e,f$, which is the first to the right and the first to the left). Each end of the region of validity is an "event" (i.e., value of $p\_x$ where things change).

This lets you build a sweepline algorithm. For a fixed $p\_x$, you can compute the set of valid values of $p\_y$, and a similar relationship that holds in the neighborhood (region of validity). Between each pair of adjacent events (i.e., values of $p\_x$), you can express the set of valid values of $p\_y$ as a disjoint union of intervals whose endpoints are linear functions of $p\_x$.

In this way, we can build up a data structure that represents the valid pairs $(p\_x,p\_y)$. Essentially, it is a union of a bunch of trapezoids, where each trapezoid has a left and right edge that is vertical and aligns with an "event", and where the top and bottom are sloping based on the linear relationship between $p\_x$ and $p\_y$ that holds in that region of validity.

That's a lot of words, and it sounds pretty complex. I apologize that I didn't have time to draw pictures to try to make this clearer. I hope this is helpful nonetheless. I imagine there be corner cases to work out that I have glossed over, based on special cases (e.g., where $e,f$ intersect not at a single point but are parallel, and so on).
> 1 votes

---
Tags: computational-geometry, parallel-computing
---


# Question
Title: Resolving a dependency graph with insufficient resources to store all states
A common way to resolve a dependency graph is to compute an execution order, and then execute each stage in turn - storing and fetching the resources as necessary. In this example, when executing stage `E` we know that stage `B` is present in the cache due to the execution order. At the end of execution, the output of every operation is present in the cache.

This works fine if your cache is big enough to store the output of every result in the graph, but this is not always true. In my case the number of operations may approach 10,000 or so (brush strokes in a painting for the curious), and the number of items that can be stored in the cache is perhaps 100 or so (textures in the GPU). Fortunately the graph has lots of chains, so should be solvable.

There are at (so far) three questions that come out of this situation:

## 1) How to compute an execution order?

Given that the cache is of finite size, not all execution orders are valid. Imagine that we only have two available resources and consider:

If we try execute `B` and `C` (both of which can be computed immediately), then we get stuck because we cannot compute `A` due to lack of resources, and we cannot compute `D` or `E` due to unfulfilled dependencies.

```
Operation:  B | C | A | ?
------------------------------>
In Cache:     | B |B,C| ??

```

Of course, if we execute `A -> B -> D -> C -> E` then we can complete execution of the graph. (The outputs of `A` and `B` can be removed after `D` is computed etc.).

```
Operation:  A | B | D | C | E
--------------------------------->
In Cache:     | A |A.B| D |C,D| E
                        ^
                        |
                 Removed A and B to make room for D

```

This implies that an ad-hoc iterative implementation (for each node check if all it's dependencies are ready, and if so, run it) will not function in cases where resources are low.

So, how can I derive an execution order that is optimized for the lowest number of resources to be allocated at any given time?

## 2) How to count how many resources are required for graph execution?

Evidently there is some limit to if a graph is computable with a provided amount of resource. For example the first graph requires three resources, and the second one requires at least two. In those cases that is because one of the nodes has that many inputs. But this isn't always the case. Consider:

In this case every node has only two inputs, but execution of the graph requires three resources.

I guess this is highly related to actually solving the graph, but it may be separable. Either way it is nice to say "this long an expensive system graph that will take 6 hours to run will successfully complete and not run out of resources half way through"

## 3) How to tell when a resource can be removed from the cache

I guess one approach is to have each item in the cache count how many times it has been used, and when that number is equal to the number of dependants, it can be removed. But it would be nice to compute two associated arrays: one that describes the order of operations to execute, and another that describes, for each operation, which items in the cache are no longer required.

## 4) Are there any existing resources/studies on solving this problem?

I've had a look through some books on graph theory and done some browsing of the web, but haven't found any resources that describe this problem. It is likely that I don't know the terminology involved, so suggesting some reading is welcome. In fact, I would love it if someone says "It's known as problem `x` and there are dozens of papers on the topic"

# Answer
> 0 votes
I chatted to some people at work, one who suggested that you could lay out the graph in "lanes"

This gave a model for how to do analyse how I was mentally assigning execution orders.

@greybeard mentioned the similarities to scheduling and register allocation, so I did a bunch of reading on those. After a while I realized that was exactly what I was doing - I was creating and ordering *instructions* for a computing architecture.

Another realisation came in distinguishing between `load` `execute` and `delete` operations. A resource must be `loaded` before any operation requires it. A resource can (must?) be `deleted` when no other operations require it. Sounds obvious, but it made me realise that each "operation" of the computer architecture consisted of those three parts: load any resource required for the operation, execute the operation then delete any resources no longer needed.

---

After scribbling on paper for an hour or two, here's the algorithm I came up with (Functioning code is available here):

Because this is a dependency graph, we're going to start at the output node and walk backwards until there is nothing left to do.

You will need to track:

* The state of the systems memory
* An array of "ProcessStages" that consist of an operation to execute, resources to load (`allocate_before`) and resource to delete (`delete_after`).
* An array of operations that haven't yet been stored as operations in a ProcessStage.

Then there is some setup:

0. Find all nodes that nothing depends on, Mark it as the current operation and mark as "delete\_after".

Followed by an iterative process:

1. Copy the memory state, ignoring are in `allocate_before` (we are working backwards, so we are saying that "the operation before the current one doesn't have the output from these in memory)
2. Pick an operation from the current memory state, Making sure that it is in the list of operations that haven't yet been assigned to a ProcessStage.
3. Ensure all of the operations dependencies are in memory, marking them as `delete after` if they were not copied from the previous memory state. (We are working backwards, so we are saying that "after being used for this operation it can be deleted")
4. Mark the current operation as "allocate before"

And Then

5. Reverse the order of operations you just derived.

Does it work? Yup. I implemented an "executor" to try execute these instructions (with heaps of asserts to ensure validity) and a "compute\_execution\_order" function.

It took the graph:

And converted it into the execution instructions:

```
ProcessStage(operation=Operation(name='E', depends_on=[]), allocate_before=[('E', 0)], delete_after=[])
ProcessStage(operation=Operation(name='D', depends_on=['E']), allocate_before=[('D', 1)], delete_after=['E'])
ProcessStage(operation=Operation(name='L', depends_on=[]), allocate_before=[('L', 2)], delete_after=[])
ProcessStage(operation=Operation(name='K', depends_on=['L']), allocate_before=[('K', 0)], delete_after=['L'])
ProcessStage(operation=Operation(name='J', depends_on=['K', 'D']), allocate_before=[('J', 3)], delete_after=['K'])
ProcessStage(operation=Operation(name='Q', depends_on=[]), allocate_before=[('Q', 0)], delete_after=[])
ProcessStage(operation=Operation(name='P', depends_on=['Q']), allocate_before=[('P', 4)], delete_after=['Q'])
ProcessStage(operation=Operation(name='O', depends_on=['P']), allocate_before=[('O', 0)], delete_after=[])
ProcessStage(operation=Operation(name='N', depends_on=['O']), allocate_before=[('N', 2)], delete_after=['O'])
ProcessStage(operation=Operation(name='M', depends_on=['N', 'P']), allocate_before=[('M', 0)], delete_after=['N', 'P'])
ProcessStage(operation=Operation(name='F', depends_on=[]), allocate_before=[('F', 4)], delete_after=[])
ProcessStage(operation=Operation(name='G', depends_on=['F', 'M']), allocate_before=[('G', 2)], delete_after=['M'])
ProcessStage(operation=Operation(name='C', depends_on=['D', 'F']), allocate_before=[('C', 0)], delete_after=['D', 'F'])
ProcessStage(operation=Operation(name='I', depends_on=['J']), allocate_before=[('I', 1)], delete_after=['J'])
ProcessStage(operation=Operation(name='H', depends_on=['I']), allocate_before=[('H', 3)], delete_after=['I'])
ProcessStage(operation=Operation(name='B', depends_on=['C', 'H']), allocate_before=[('B', 1)], delete_after=['C', 'H'])
ProcessStage(operation=Operation(name='A', depends_on=['B', 'G']), allocate_before=[('A', 0)], delete_after=['B', 'G'])

```

Which create a memory graph looking like:

```
      |  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9
      | E ☐ |     |     |     |     |     |     |     |     |
  (E) | E ☑ |     |     |     |     |     |     |     |     |
      | E ☑ |     |     |     |     |     |     |     |     |
      | E ☑ | D ☐ |     |     |     |     |     |     |     |
  (D) | E ☑ | D ☑ |     |     |     |     |     |     |     |
      |     | D ☑ |     |     |     |     |     |     |     |
      |     | D ☑ | L ☐ |     |     |     |     |     |     |
  (L) |     | D ☑ | L ☑ |     |     |     |     |     |     |
      |     | D ☑ | L ☑ |     |     |     |     |     |     |
      | K ☐ | D ☑ | L ☑ |     |     |     |     |     |     |
  (K) | K ☑ | D ☑ | L ☑ |     |     |     |     |     |     |
      | K ☑ | D ☑ |     |     |     |     |     |     |     |
      | K ☑ | D ☑ |     | J ☐ |     |     |     |     |     |
  (J) | K ☑ | D ☑ |     | J ☑ |     |     |     |     |     |
      |     | D ☑ |     | J ☑ |     |     |     |     |     |
      | Q ☐ | D ☑ |     | J ☑ |     |     |     |     |     |
  (Q) | Q ☑ | D ☑ |     | J ☑ |     |     |     |     |     |
      | Q ☑ | D ☑ |     | J ☑ |     |     |     |     |     |
      | Q ☑ | D ☑ |     | J ☑ | P ☐ |     |     |     |     |
  (P) | Q ☑ | D ☑ |     | J ☑ | P ☑ |     |     |     |     |
      |     | D ☑ |     | J ☑ | P ☑ |     |     |     |     |
      | O ☐ | D ☑ |     | J ☑ | P ☑ |     |     |     |     |
  (O) | O ☑ | D ☑ |     | J ☑ | P ☑ |     |     |     |     |
      | O ☑ | D ☑ |     | J ☑ | P ☑ |     |     |     |     |
      | O ☑ | D ☑ | N ☐ | J ☑ | P ☑ |     |     |     |     |
  (N) | O ☑ | D ☑ | N ☑ | J ☑ | P ☑ |     |     |     |     |
      |     | D ☑ | N ☑ | J ☑ | P ☑ |     |     |     |     |
      | M ☐ | D ☑ | N ☑ | J ☑ | P ☑ |     |     |     |     |
  (M) | M ☑ | D ☑ | N ☑ | J ☑ | P ☑ |     |     |     |     |
      | M ☑ | D ☑ |     | J ☑ |     |     |     |     |     |
      | M ☑ | D ☑ |     | J ☑ | F ☐ |     |     |     |     |
  (F) | M ☑ | D ☑ |     | J ☑ | F ☑ |     |     |     |     |
      | M ☑ | D ☑ |     | J ☑ | F ☑ |     |     |     |     |
      | M ☑ | D ☑ | G ☐ | J ☑ | F ☑ |     |     |     |     |
  (G) | M ☑ | D ☑ | G ☑ | J ☑ | F ☑ |     |     |     |     |
      |     | D ☑ | G ☑ | J ☑ | F ☑ |     |     |     |     |
      | C ☐ | D ☑ | G ☑ | J ☑ | F ☑ |     |     |     |     |
  (C) | C ☑ | D ☑ | G ☑ | J ☑ | F ☑ |     |     |     |     |
      | C ☑ |     | G ☑ | J ☑ |     |     |     |     |     |
      | C ☑ | I ☐ | G ☑ | J ☑ |     |     |     |     |     |
  (I) | C ☑ | I ☑ | G ☑ | J ☑ |     |     |     |     |     |
      | C ☑ | I ☑ | G ☑ |     |     |     |     |     |     |
      | C ☑ | I ☑ | G ☑ | H ☐ |     |     |     |     |     |
  (H) | C ☑ | I ☑ | G ☑ | H ☑ |     |     |     |     |     |
      | C ☑ |     | G ☑ | H ☑ |     |     |     |     |     |
      | C ☑ | B ☐ | G ☑ | H ☑ |     |     |     |     |     |
  (B) | C ☑ | B ☑ | G ☑ | H ☑ |     |     |     |     |     |
      |     | B ☑ | G ☑ |     |     |     |     |     |     |
      | A ☐ | B ☑ | G ☑ |     |     |     |     |     |     |
  (A) | A ☑ | B ☑ | G ☑ |     |     |     |     |     |     |
      | A ☑ |     |     |     |     |     |     |     |     |

```

---

## Caveats

This is not an optimal solution. In some cases I've been able to derive better orders of operation that use fewer resources. This could be a case of tweaking step #2 to pick a better instruction. I've had good success by picking the operation with the *most* dependencies (because we're working backwards through time, this is equivalent to saying "lets free from memory the one that has the most resources currently in memory"), but as this is a greedy approach, it isn't always globally the best.

# Answer
> 0 votes
If you consider the following decision problem:

* Input: a dependancy graph $G$ and an integer $k$.
* Question: can $G$ be computed using less than $k$ ressources?

Then if every node cannot be computed more than once, the problem is $\textsf{NP}$-complete (Sethi 1973). If a node can be computed several times, the problem is also shown to be $\textsf{NP}$-hard by Sethi, and even $\textsf{PSPACE}$-complete by Gilbert and Tarjan in 1978.

So there is no known efficient solution to this problem.

---
Tags: graphs, cache
---


# Question
Title: Algorithm to compute a div d and a mod d
I wanted to ask here a question about a simple algoirhtm to compute `a div d` and `a mod d`. My doubt specifically depend on negative numbers:

Doesn't the algorithm get wrong results for $-4$ and $2$ for instance, since the reminder of that division is 0? In this case the algorithm should give a quotient of $2$, But i image it should be $-2$, am i right?

# Answer
> 2 votes
You're right. If this algorithm divides -k * d by d, it will return k as the result of the division instead of -k.

On top of that, if you divide one billion billions by one, it will take an eternity to finish. Execution time is O (|a| / d), which is just horribly bad.

---
Tags: algorithms
---


# Question
Title: Finding time complexity $T(n) = 2^n T(n/2) + n^n$
I am applying substitution method to find the time complexity of the following recurrence relation. But I am having difficulty solving it past a certain point.

$$T(n) = 2^n T(n/2) + n^n$$

After substituting $T(n/2)$: $$T(n/2) = 2^\frac{n}{2} T(n/4) + (n/2)^\frac{n}{2}$$

I get, $$T(n) = 2^\frac{3n}{2}T(n/4) + n^n + 2^\frac{n}{2}n^\frac{n}{2}$$

I further substitute $T(n/4)$ and get:

$$T(n) = 2^\frac{7n}{4}T(n/8) +n^n + 2^\frac{n}{2}n^\frac{n}{2} + 2^\frac{2n}{4}n^\frac{n}{4}$$

Thus after generalizing:

$$T(n) = 2^\frac{2k-1}{2^{k-1}}T(n/2^k) + \sum\_{i=0}^{\infty}2^\frac{in}{2}n^\frac{n}{2^i}$$

Can someone help me with the summation: $$\sum\_{i=0}^{\infty}2^\frac{in}{2}n^\frac{n}{2^i}$$

Or suggest some easier way to solve this recurrence relation.

# Answer
We prove by induction that $T(n) \leq Cn^n$, where $C = \max(T(2),4/3)$. The base cases are clear. For the inductive case, $$ T(n) = 2^nT(n/2) + n^n \leq C2^n (n/2)^{n/2} + n^n = C\left(\frac{2}{n}\right)^{n/2} n^n + n^n \leq (C/4 + 1)n^n \leq Cn^n. $$ On the other hand, clearly $T(n) \geq n^n$. Hence $T(n) = \Theta(n^n)$.

In fact, if we work a bit harder, we find out that $T(n) = (1 + o(1)) n^n$. Working even harder, we can obtain the even more accurate estimate $T(n) = n^n + (1+o(1)) (2n)^{n/2}$; and so on.
> 2 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: What is the big-$O$ notation of a summation of logs where the arguments add to $n$?
For: $$\sum^{k}\_{i=1} \log(x\_i)$$ where: $$\sum^{k}\_{i=1} x\_i = n$$ Is there any big-$O$ result in terms of $n$ ?

I found this, but is not what I'm looking for.

# Answer
It is easy to show that $\prod\_{i = 1}^{n}x\_i$ is maximized when all $x\_i$'s are equal, i.e., $x\_i = n/k$ for every $i \in \\{1,\dotsc,k\\}$.

Therefore, $$\sum\_{i = 1}^{k} \log x\_i = \log \left( \prod\_{i = 1}^{k} x\_i \right) \leq \log \left( \prod\_{i = 1}^{k} \frac{n}{k} \right) = k \log (n/k) \leq n = O(n)$$

Thanks to @JohnL. for pointing out that $k\log\_{e}(n/k) \leq n$.
> 2 votes

---
Tags: time-complexity, big-o-notation
---


# Question
Title: Creating an algorithm which utilizes an already known optimal solution to max matching
Assume that there is a maximal matching of size k in an bipartite graph, G=(U,V,E). I now want to utilize this maximal matching in order to find a maximal matching in the bipartite graph where we add some node u to U and some edges (u,v\_1),...,(u,v\_n), where v\_1,...,v\_n are vertices in V.

I have figured out that such an extension may yield a maximal matching of maximum size k+1. Thus I want to formulate an algorithm which finds a maximal matching of size k+1, if one exist. It is clear that if such a matching exist, then it must include the added vertex u. If there exist some v, adjacent to u that is not included in the optimal solution of size k, then we are done as we found a maximal matching of size k+1. In the case where there are no "available" adjacent vertices. Firstly we have to remove some pair which includes one of the occupied adjacent node and connect it with u instead. We now have to rearrange the matching in some clever way, but I'm not sure how to proceed from here, any suggestions?

# Answer
Let $M$ be a maximum matching of graph $G = (V,E)$. Let $G'$ be a new graph after adding a new vertex $u$ and the corresponding edges to $G$. Let $M'$ be a maximum matching of $G'$.

Create a flow network on graph $G'$ by creating new source and sink vertices. Send flow of value $|M|$ through the matching edges in $M$. Create a residual graph corresponding to this flow. If there is an augmenting path in the residual graph, then $G'$ has a matching of size $|M|+1$, otherwise not. The overall running time is $O(|V|+|E|)$.
> 0 votes

---
Tags: bipartite-matching
---


# Question
Title: Prove my algorithm that solves ABC String problem in Codeforces is correct
Here's the statements of problem A, "ABC String" in Educational Codeforces Round 105 (Rated for Div. 2)

> You are given a string a, consisting of n characters, n is even. For each i from 1 to n $a\_i$ is one of 'A', 'B' or 'C'.
>
> A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"), and ")(", "(" and ")" are not.
>
> You want to find a string b that consists of n characters such that:
>
> b is a regular bracket sequence; if for some i and j $(1≤i,j≤n1≤i,j≤n) a\_i=a\_j$, then $b\_i=b\_j$. In other words, you want to replace all occurrences of 'A' with the same type of bracket, then all occurrences of 'B' with the same type of bracket and all occurrences of 'C' with the same type of bracket.
>
> Your task is to determine if such a string b exists.

I submitted my code and it's accepted.

The idea is brute-force. There're only $2^3 - 2$ cases for $A, B, C$ to consider, since $A, B, C$ cannot be all "(" nor all ")", because a RBS(regular bracket sequence) must contain at least one "(" and one ")".

So the problem is to check for validity of each case. What's the algorithm for that?

The idea is to keep track of the number of close brackets and open brackets so that these two conditions hold throughout the search from left to right:

1. $cnt\_{close} \leq cnt\_{open}$
2. At the end of the search, $cnt\_{close} = cnt\_{open}$

cnt stands for **counter**.

But does this algorithm actually work? We have to prove that a BS is considered RBS if and only if the two above conditions hold throughout the search from left to right.

The first side is easy to prove. If a BS is a RBS, we clearly must have $cnt\_{close} = cnt\_{open}$ at the end of the loop.

And we can't have $cnt\_{close} \> cnt\_{open}$ at any point of the search since if we've found a redundant close bracket, it cannot match with any open bracket before it. However, for every close and open brackets in a RBS, it always has a partner. So the two theories are contrary.

Therefore, the two conditions must hold when a BS is a RBS.

The reverse side is more tricky. I'm wrapping my head around it. I tried induction on the second condition and the reductio method but nothing works out.

My reductio approach: So let's assume that when the two conditions hold, we do not have a RBS which means only two cases happen: Either we have $cnt\_{close} \neq cnt\_{open}$ at the end of the loop or a pair of "(" and ")" follow the wrong order, namely "...(1)... ) ...(2)...( ...(3)...".

The former can't happen due to the second condition.

While searching throughout "area (1)", we cannot have $cnt\_{close} \geq cnt\_{open}$ since that would fail the first condition.
That's how far I've gone. Nothing more. I'd like to hear from you your approach to this problem. Thank you in advance!

25/11/2021: What if we define a "RBS" to be a BS such that:

1. For every close bracket, it has a **unique** partner from the left.
2. The number of open brackets equal to the number of close brackets.

# Answer
Yes, your algorithm is correct.

As you have experienced, the fundamental difficulty in proving your algorithm is correct is the definition of "regular bracket sequence". Even a student in early primary schools may understand the definition given in the Codeforces problem, "a regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence." However, that definition does not mention explicitly what is required of brackets in a correct arithmetic expression. While it is clear what is a "correct arithmetic expression" intuitively, the intuition becomes illusive when you need to prove the correctness rigorously.

---

Here is a formal definition of "a regular bracket sequence" or "a string of balanced brackets".

> Given word $u$ that consists of "$($" and "$)$", let $D(u)$ be the number of occurrences of the left parentheses in $u$ minus the number of occurrences of the right parentheses in $u$. Such a word is said to be word of well-balanced parentheses (or "a regular bracket sequence") if
>
> 1. $D(u) = 0$ , and
> 2. $D(v) \ge 0$ for any prefix $v$ of $u$.

If the definition above is used, then, of course, your algorithm is correct!

---

Here is another formal definition of "a regular bracket sequence" or "a string of balanced brackets".

> A word $u$ that consists of "$($" and "$)$" is a word of well-balanced brackets (or "a regular bracket sequence") if
>
> 1. $u$ is empty, or
> 2. $u=(u\_1)$ for some well-balanced brackets $u\_1$, or
> 3. $u=u\_1u\_2$ for some well-balanced brackets $u\_1$ and some well-balanced brackets $u\_2$.

Welcome to the world of Dyck language!

---

**Exercise**. Prove the two definitions above are equivalent to each other.
> 2 votes

# Answer
I'll write the proof for: If a regular bracket sequence follows the second definition, it is true that it has the property stated in the first definition.

> A word $u$ that consists of "$($" and "$)$" is a word of well-balanced brackets (or "a regular bracket sequence") if
>
> 1. $u$ is empty, or
> 2. $u=(u\_1)$ for some well-balanced brackets $u\_1$, or
> 3. $u=u\_1u\_2$ for some well-balanced brackets $u\_1$ and some well-balanced brackets $u\_2$.

Let us view these 3 conditions as functions that return a string.

$\forall u$ as a RBS, $1(u)$ returns an empty string(let's denote it $\emptyset$)
$\forall u$ as a RBS, $2(u)$ returns ($u$)
$\forall u$ and $v$ as two RBS(s), $3(u,v) = uv$

So, all RBS will just be a result of a composite function which is made from these three functions.

For example:
"()()()" = $3(3(2(\emptyset), 2(\emptyset) ), 2(\emptyset))$

Let's denote $len(u)$ to be the length of a string $u$

Lemma 1: The number of brackets in a RBS is even.

Proof: Consider a RBS $u$.
We'll use induction. It is true that "(" or ")" cannot be formed.

Assume the theory is true for every odd number less than $n$($n$ is odd and $n\geq 1$). We'll disprove a RBS $u$ of length $n+2$.

Case 1: $u = 2(v)$. RBS $v$ has length of $n$, which is absurd.

Case 2: $u = 3(a, b)$ with $a$ and $b$ both not an empty string and both RBS(s). $len(u) = len(a) + len(b)$. Since (n+2) is odd, we must have $len(a)$ or $len(b)$ is odd. Again, this is absurd.

Lemma 2: Every RBS $u$, which is not an empty string, starts with "(".

Proof: Let us use induction on length $n$ of $u$. We start with $n = 2$. The only possibility is "()". This one starts with "("

Assume the theory is true for every even $n \geq 2$. We prove it is also true for $n+2$

Since $u$ is not an empty string, we have:
$u = 2(v)$, which proves the lemma.
Or: $u = 3(a,b)$ with $a$ and $b$ not both empty strings. $len(a) \< n$. So, $a$ starts with "(". We're done.

Lemma 3: The number of open brackets equal to the number of close brackets.
Proof:

Induction again. Empty string is the base case. Let us assume correctness for every $n \geq 0$.

Case 1: $u = 2(v)$. $D(v) = 0$. So, adding one close bracket and one open bracket affects nothing.
Case 2: $u = 3(a,b)$. $D(u) = D(a) + D(b) = 0$. We're done.

Lemma 4: For every prefix $v$ of $u$, we have $D(u) \geq 0$.
Proof:
Assume the reverse. We have $D(u) \< 0$ for some prefix $v$.

For example: $u = (( )))))...$

We'll prove this is ridiculous. Let's denote the number of open brackets as $cnt\_{open}$ and the number of close brackets as $cnt\_{close}$. So, $cnt\_{open} \< cnt\_{close}$.

Case 1: $u = 3(a, b)$. The only possibility for $a$ is (()). Since if we pick further than that, $a$ won't be a RBS due to Lemma 3. But then $b$ will starts with ")", which is absurd.

So $u = 2(v\_1)$. $v\_1$ is just $u$ with $cnt\_{close} - 1$ and $cnt\_{open} - 1$. Again, $D(v) \< 0$.

The process repeats. We must have $v = 2(v\_2)$ for some $v\_2$. Consider $v\_{cnt\_{open}}$. This one starts with ")", which is absurd. We're done!

Lemma 3 and Lemma 4 proves the initial problem.
> 1 votes

---
Tags: algorithms, strings
---


# Question
Title: How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)
Let's say I have a point $(x\_0, y\_0)$, and some other points $(x\_1, y\_1), (x\_2, y\_2) ... (x\_n, y\_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that all points are distinct.

Is there any way to sort points $1...n$ by order of the angle they make with $(x\_0, y\_0)$ and the $x$-axis, without ever having to resort to using floating-point numbers?

(This has applications within the Convex Hull Problem; specifically, the Graham Scan, an $O(NlogN)$ algorithm whose first step is to choose the lowest point and to sort all other points in increasing order of the angle they make with the $x$-axis).

My idea: $cos(\theta)$ is strictly decreasing from $0^{\circ}$ to $180^{\circ}$, and it is well-known that given two vectors $v\_1$ and $v\_2$, $cos(\theta) = \frac{a \cdot b}{|a||b|}$. Therefore, treat every point as a vector from $(x\_0, y\_0)$ to that point (i.e. $\langle x\_i - x\_0, y\_i - y\_0 \rangle$); then, comparisons between angles can be done by comparisons between $\frac{a \cdot b}{|a||b|}$. And to take care of the fact that $|a|$ and $|b|$ may not be integers since they are the square root of an integer, we can square the fractions and compare those. The last thing to do is to realize that the squared fractions will always be positive, while the $\frac{a \cdot b}{|a||b|}$ values may initially be negative. To fix this, just keep an extra boolean telling whether or not the value is positive or negative, and proceed...

But this seems pretty complicated, and I'm not even completely sure if the logic is correct. Does anyone have a better idea/a confirmation that this idea will work?

# Answer
In computational geometry, we often sort the points clockwise or anti-clockwise. For example, in Graham's scan, the algorithm sorts the points with respect to $(x\_0,y\_0)$ in clockwise or anti-clockwise order. For that, you can use the concept of left rotation or right rotation. That can be done using cross-product. It does not require any division or square roots. It is given in CLRS in more detail.

Your solution is also correct. Just adding something more. When you compare two fractions $a/b$ and $c/d$. Simply check if $ad \< bc$ assuming without the loss of generality that $d$ and $b$ are positive real values. In this way, you can avoid using division operations.
> 2 votes

---
Tags: algorithms, sorting, computational-geometry, floating-point, convex-hull
---


# Question
Title: Which part of the CPU is responsible for executing instructions
I was reading about the machine cycle. Everything was clear until I started with the execution of instructions. I know how an ALU and a CU work. I'm also aware of the process of fetching and decoding. But, I'm a little bit confused about the part that is responsible for executing instructions in a CPU.

Note: I've searched for an answer before asking. However, nothing was helpful enough.

# Answer
> 1 votes
* All the parts of the CPU are executing instructions at some point of time or the other.
* The part(s) that is/are executing an instruction at a given time depends on the instruction being executed.
* For example, in an add instruction, the ALU performs addition in the execute stage of the instruction cycle.
* Through a process called pipelining, more than one instruction can be executed on a CPU. For example, data can be fetched in the Load stage while addition is being performed in the execute stage in the same cycle.
* Optimizing compilers try to keep the whole CPU busy by reordering instructions such that all the parts of the CPU are busy *most* of the time.

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


title: Turing machine accepting square

text:
# Question
Title: Turing machine accepting square
I'm trying to figure out following assignment and I could use your help, because I'm stuck.

Task:

Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. Basically it accepts those words, where you can arrange ones into square. For example first three acceptable words will be:

```
1Δ; 1111Δ; 111111111Δ;

```

My thoughts:

If I get "1" only once, it should be accepted.

Tape: 1Δ; k=1, n=1 and k=n^2

So I m assuming after one "1" I'm in the "STOP" state (lets call it state A) if there is no other char on the tape.

The next acceptable word is the next square, which we I can write in the formula like this:

(n+1)^2 That equals: n^2 + 2*n + 1 Difference between two consecutive squares is (2*n + 1)

So If my assumption is correct, If I'm in state A I need to somehow check if I get (2\*n + 1) times "1" on tape and if that takes me back to state A, it will be correctly accepted. Anything else should be declined.

The problem I'm facing is, that I don't know, how to count (2\*n + 1) times "1" on tape.

Also I should find solution using only one tape. The hint is that it should end in the form 111#111111111Δ, where the left side sum of ones equals "k" and right side equals "n". Sadly, this hint didn't help me at all. I'd say it made things worse for me.

# Answer
It is indeed a good idea to see that $(n+1)^2 = n^2 + (2n + 1)$.

A program in pseudocode for testing square could be:

```
d = 1
dsqr = 1
while dsqr ≤ n:
   if dsqr = n:
      return true
   dsqr = dsqr + 2d + 1
   d = d + 1
return false

```

However, the previous code raise the following questions:

* How to keep track of the value `d`?
* How to keep track of the value `dsqr`?

Here's an idea (`#` denote blank symbol):

| Tape | Description |
| --- | --- |
| `#11111111111#` | Initial input |
| `#21111111111#` | $d = 1$, $d^2=1$ |
| `#22331111111#` | $d=2$, $d^2 = 4$ |
| `#22233333311#` | $d=3$, $d^2 = 9$ |
| `#22223333333#` | $d=4$, $d^2 \>n$, reject |

In the table, the number of `2` represents the value of $d$, and the total number of `2` and `3` represents the value of $d^2$. When incrementing $d$, one must do the following steps:

* for each `2`, add two `3` at the end of the sequence of `2…23…3`. During this step, it could be usefull to use another symbol, say `2'` to keep track;
* replace the first `3` with a `2`;
* add one last `3` at the end.

If the last step reach a blank symbol before finishing, then the input is not a square. If the last step finishes by replacing the last 1, then the input is a square.

I will let the details of the Turing Machine to you.
> 1 votes

---
Tags: turing-machines, data-structures
---


# Question
Title: Why does the CwF definition require a set of types under a context rather than a class of types?
In "Syntax and Semantics of Dependent Types" at the top of page 24, Martin Hoffman describes $\mathit{Ty}\_{\mathcal C}(\Gamma)$ as the *collection* of semantic types under context $\Gamma$.

It makes sense that he used the word collection rather than set, because in the set-theoretic CwF he describes, the types under a context $\Gamma$ are $\Gamma$-indexed families of sets. It is well known that this is a proper class.

However, on page 26 he provides a more abstract definition where a CwF is a Fam-valued presheaf. Such a presheaf maps an object $\Gamma$ of the context category onto a pair (Ty($\Gamma$), $\mathit{Tm}(\Gamma,\sigma)\_{\sigma \in \mathit{Ty}(X)}$). The left component of an object of Fam is an index *set*, so this contradicts the earlier definition and seems incorrect. Most literature on CwF's takes the same approach. Would it be more appropriate to use the category of class-indexed families of sets as the codomain category for these presheaves?

# Answer
> 3 votes
There is nothing special about types with respect to sizing, compared to what we already have in ordinary categories. A *small category* has a set of objects, and for each pair of objects, a set of morphisms between them; so morphisms are an indexed family of sets. We can immediately extend this definition to small CwFs, where for each context we have a set of types.

All that happens, compared to categories, is that we have four underlying set families (objects, morphisms, types, terms) instead of just objects and morphisms, so we have more degree of freedom when choosing the sizes involved. E.g. we have locally small categories where the set of objects is large (in some sense) and the sets of morphisms are small, and we're likewise free to pick relative sizes of all involved sets in CwFs.

---
Tags: type-theory, category-theory, dependent-types, denotational-semantics
---


# Question
Title: There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple
There are `n` cities and `m` possible roads and `k` temples. The cost of each road is given. Build roads with minimum cost such that each city has access to at least 1 temple.

**Note** that there can be multiple roads(edges) between two cities and each temple is inside a city.

**My attempt** : I tried running Kruskal's Algorithm of the graph and then sort edges in descending order and then remove them one by one if the graph still satisfies the condition. I don't know this algorithm is correct or not.

I found this question in an algorithm book.

# Answer
> 1 votes
Add a new vertex $v$ to the graph. For every *city node* $u$ that contains a temple, add a $0$ weighted edge $(v,u)$ to the graph. Let the new graph be $G'$. Find the minimum spanning tree of $G'$. It would give the minimum cost of constructing roads such that every city has access to at least one temple.

Please try to prove correctness by yourself. Let me know if it works.

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Proving correctness of Polynomial reduction
Given a problem A is NP-Hard and A ≤ B, is there a way to prove that B is also NP-Hard?

# Answer
> 0 votes
The definition of NP-Hard states: "A problem $L$ is NP-Hard, if for every problem $L'\in NP$, there exists a polynomial reduction from $L'$ to $L$, namely - $L'\le\_p L$".

Now, since $A$ is NP-Hard, that would mean that for any $L'\in NP$, we have $L'\le\_p A$. Since the relation $\le\_p$ is transitive (prove it!), we also have $L'\le\_p B$. Hence, by definition $B$ is also NP-Hard.

---
Tags: complexity-theory, np-hard, polynomial-time-reductions
---


# Question
Title: How to solve $T(n) = 27T(n/9) + n^3$ with substitution method
I'm trying to bound this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?

# Answer
I am assuming that the recurrence relation you are trying to solve is: $$T(n) = 27T(n /9) + n^3$$

Using the substitution method, you can prove that for any $k \leqslant \log\_3 n$: $$T(n) = 3^{3k}T\left(\frac{n}{3^{2k}}\right) + n^3\sum\limits\_{i=0}^{k-1} \frac{1}{27^i}$$

For $k = \log\_3n$, we get $T(n) \leqslant n^3T(1) + n^3\sum\limits\_{i=0}^{+\infty}\frac{1}{27^i}=n^3(T(1) + \frac{27}{26})$.

Since clearly $T(n) \geqslant n^3$, we conclude that $T(n) = \Theta(n^3)$.
> 2 votes

# Answer
We have T(3n) = T(n) - n^3.

If T(1) = c, then T(3) = c-1, T(9) = c - 28, T(27)=c-757 etc.
> 0 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Are there complexity classes so that RE ⊂ C ⊂ ALL?
If so what are they? These are Computational Complexity Classes that are not in RE but are in ALL. What would a problem in one of these classes look like? Would any of these problems be decidable?

# Answer
As has been commented above, decidability **implies** recursive enumerability - indeed, one of the standard exercises in any computability theory book is proving that a set is decidable iff it is both r.e. and co-r.e. (note that "decidable," "recursive," and "computable" are all synonyms). So no, a fortiori there are no decidable problems outside of $\mathsf{RE}$.

But that doesn't mean that there aren't interesting non-r.e. problems or classes of problems. For example, the set $\mathsf{Tot}$ of (indices for) Turing machines which halt on *all* inputs is strictly more complicated than any r.e. set; in a precise sense it is the halting problem's halting problem.

A good starting point here is the arithmetical hierarchy. This may seem abstract at first, but results like Post's theorem and Shoenfield's lemma will help demystify it. And even that is only the start of the very intricate picture; further keywords include "**hyper**arithmetic" and "projective."

I strongly recommend the treatment in the first part of Soare's original recursion theory textbook.
> 1 votes

---
Tags: computability
---


title: How was swapping program born?

text:
# Question
Title: How was swapping program born?
Code:

```
a=10
b=5
temp=a
a=b
b=temp

```

I am studying Python and I stumbled upon the classic program: The Swapping Program.

It is simple:

`temp` binds to `a`.

`a` binds to `b`.

`b` binds to `temp`.

I can decode what is happening in memory as well. I will show it here:

But sadly, I can't wrap my head around how we got to this program? What was the problem solving part of this problem. How did we decide that this would be our program? What logic was used to build this program? The reason is simple while I might not come across swapping 3 variables, but if I learn the basics programs properly, I make sure that I learn the complex topics as well.

# Answer
**Problem:** Implement selection sort.

**Solution:**

```
def sort(a):
    """Sort the table a using the selection sort algorithm."""
    for i in range(0, len(a)-1):
        k = i
        for j in range(i+1, len(a)):
            if a[j] < a[k]:
                k = j
        # swap a[i] and [k]
        temp = a[i]
        a[i] = a[k]
        a[k] = temp

```

Note that the last three lines could be implemented without `temp` as `a[i], a[k] = a[k], a[i]`.
> 1 votes

# Answer
TLDR; see **Answer** below.

---

## Explanation

Before anything, there are something need to be clarified:

> I can decode what is happening in memory as well. I will show it here: ...

While the process on your draft indeed show the essence of swapping (i.e., just an process of exchange), it is **NOT** what actually happened in memory. There are a plenty of materials that provide rather adequate resources for the internals of a computer program, such as CS Books, Wikipedia, Online Courses, etc. For the sake of convenience, it suffices to quote some statements from Wikipedia:

> While this is conceptually simple and in many cases the only convenient way to swap two variables, it uses **extra memory**.

If I understand it correctly, the swapping process as you described is as follows:

```
Phase1:
a -> 10
b -> 5

Phase2:
a -> 10 <- temp
b -> 5

...

```

The problem here is that, when a new variable comes up and being assigned for a value, it does not obey the rules that mentioned above, that is, **consuming extra memory**.

In fact, when this program is running on your computer, your program in *Phase 2*, shall behave like this:

```
Phase1:
a -> 10
b -> 5

Phase2:
a -> 10
b -> 5
temp -> 10

...

```

You might be surprised by this somewhat inefficient behavior. But *Sadly* (taking your words), it is true for any one of computer programs, no matter generated by Python, Java, C, C++, etc. The reason why the program does this kind of things is relating to its underlying working mechanism, which is designed for interacting with *Operating System*. More concretely, they are essentially a bunch of operations of manipulating the operating system's Memory and CPU Registers. Hence the things that you are interested in might more likely be interpreted as following phases:

1. Phase 1: `a` got a value `10` in memory address `addr_for_var_a`, `b` got a value `5` in memory address `addr_for_var_b`;
2. Phase 2: `temp` take the value from `addr_for_var_a` into its memory address `addr_for_var_temp`.
3. ...

You see, when `temp` got a value `10`, it is essentially an effect of the operation of copying the value from `a`. This is exactly what happened when your *Swapping Program* running. And there is **no such thing like**: making up a new variable then letting it point to others' *value* so that it need not to have its own *value*. Each variable has its own *value*, note that the term "*value*" here might refer to an actual value, or a memory address.

If you want to check whether what I'm saying here is correct or not, you just need some simple works: Compile Your *Swapping Program* Into Assembly Form. Assembly form is very close to the form that can be understood by your computer hardware directly. In your assembly output, you must see something like this:

```
...
MOVE   Value@X   Value@Y     # copy the X's value to Y
...

```

---

## Answer

If you can understand the things mentioned above, you might not have the doubts about

1. How we got to this program?
2. What was the problem solving part of this problem?
3. What logic was used to build this program?
4. **How was swapping program born?**

Because the answer to those questions might be too simple to understand: Nowadays if you want to exchange the values between two variables, the normal computers **just work in this way**, that is, with the help of the third new variable. If you still cannot understand it properly, check this or this for more details.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: Counting number of times we visit vertices of given tree
Suppose we are given a tree $T=(V,E)$ where $|V|=10$. Now, one of the vertices is goal and we want to find it. The structure of the tree is given as input, but which vertex is the goal is unknown. In each time step, we can visit a arbitrary vertex $v$ and find out which edge of $v$ is nearest to goal.

What is the number of times we visit nodes to identify which node is the goal? If we visit $v$ and find out its neighbor $u$ is goal, we don't need to visit $u$.

I read this link, but the answer is $3$, how we get the answer $3$? This question come from an interace exam of university and it's not homework.

# Answer
> 1 votes
Give a tree and a node $u$ in it. Consider $u$ as the root of the tree. If there is no more than $n/2$ nodes in every subtree (except the whole tree), we will call $u$ a center of that tree. A tree can have multiple centers.

**Fact**: A tree has at least one center.
**Proof**: Select an arbitrary node $u\_1$. If $u\_1$ is a center, we are done. Otherwise, suppose the subtree at $u\_2$ of the tree rooted at $u\_1$ has more than $n/2$ nodes. Now we consider $u\_2$. If $u\_2$ is a center, we done. Otherwise, repeat the process. Since the number of nodes in the most popular subtree is strictly decreasing, in the end, we will find a center.

---

As in the question, suppose we are given a tree $T=(V,E)$ that $|V|=10$.

* Pick $v\_1$, an arbitrary center of $T$. If $v\_1$ or one of its neighbors is the goal, we have found the goal with $1$ visit.
* Otherwise, let $u\_1$ be the root of $T$. We know which edge that is incident to $v\_1$ is nearest to goal. In other words, we know which subtree contains the goal. Let that subtree be $T\_1$, which has no more than $10/2=5$ nodes.
    + Pick $v\_2$, an arbitrary center of $T\_1$. If $v\_2$ or one of its neighbors is the goal, we have found the goal with $2$ visits.
    + Otherwise, let $u\_2$ be the root of $T\_1$. We know which edge in $T\_1$ that is incident to $v\_2$ is nearest to goal. In other words, we know which subtree of $T\_1$ contains the goal. Let that subtree be $T\_2$, which has no more than $5/2=2.5$ nodes, i.e., which has at most $2$ nodes.
        - Pick $v\_3$, an arbitrary node in $T\_2$. The goal is either $v\_3$ or the other node in $T\_2$ that is connected to $v\_3$ if it exists. So we have found the goal with $3$ visits.

In summary, $10\ \rightarrow\ 10//2=5\ \rightarrow\ 5//2 = 2$.

---

**Exercise.** Explain that it is enough for $3$ visits to find the goal if $|V|=12$.

---
Tags: algorithms
---


title: Vertex Cover with minimum degree 1

text:
# Question
Title: Vertex Cover with minimum degree 1
> In Special Vertex Cover, we are given an undirected graph $G$, and an integer $k\in \mathbb{N\_0}$. The objective is to decide whether there exists a vertex cover $S$ of $G$ of size at most $k$ such that $G\[S\]$ (the subgraph of G induced by S) has minimum degree 1 i.e the at the subgraph that induced only by the vertices of $S$ there are no isolated vertices.

I want to design an $O(4^k)$-sized kernel for Special Vertex Cover. but I'm stuck because any reduction rule that I'm trying to apply doesn't save the equivalent of one of the requirements. if I try to remove only 1 vertex at a time the requirement that the minimum degree 1 doesn't save. and if I try to remove 2 vertices the requirement that the set will be at size k doesn't save.

so far I've figured that:

1. if there is an isolated vertex then I need to remove it.
2. if there 2 isolated neighbors then I need to remove them and decrease k by 2.

what else can do?

# Answer
**Reduction Rule:** Let $T$ be the set of vertices such that each vertex has a degree of at least $k+1$ and for every vertex $u \in T$ there exist a vertex $v \in T$ such that there is an edge $(u,v) \in E$. All the vertices in $T$ belong to the vertex cover and already satisfy the "degree $1$" condition. Merge all the vertices in $T$. Let the merged vertex be $t$. Add a new vertex $w$ with $k$ pendant vertices and add an edge $(t,w)$ to the graph. Decrease $k$ by $|T|-2$.

Let $A \subseteq V \setminus T$ be the set of vertices each with a degree of at least $k+1$. Then, $A$ forms an independent set and $|A| \leq k$.

Let $B = V \setminus (A \cup T)$. Then, every vertex in $B$ has a degree at most $k$. Therefore, the graph spanned by $B$ contains at most $k^2$ edges; otherwise, the graph is a "no" instance. Let $B' \subseteq B$ be the set of vertices spanned by these edges. The remaining vertex set $R = B \setminus B'$ forms an independent set. Therefore, $A$ and $R$ form a bipartite graph. Let $x$ and $y$ be two vertices in $R$ that share the same set of neighbors in $A$. Then, one of these vertices can be removed. Using this reduction, the size of $R$ can be reduced to $2^k$. Overall, the number of vertices in the reduced graph is at most $2^k + O(k^2) = O(2^k)$. And, the number of edges is at most $O(k \cdot 2^k)$. I think the number of edges can be further reduced to $O(2^k)$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Need the time complexity of this conditional statement method
My idea of the program is :

Input = n sets

objective function ObjFn equals to O(n^3)

Output = the order of n sets

Steps:

1. Applying ObjFn to all n sets
2. Choose the n of the Minimum ObjFn to be ordered first
3. Eliminate the chosen n
4. Repeat steps 1:3 for the rest n-1 sets Note: If there are more than same minimum ObjFn for more than one of the n-1 , clustering all available solutions

I need to check the time complexity of this type of clustering and the overall time complexity of the method.

In addition if there any reference for a similar optimization method to study it.

Thanks in advance.

Example: If n= 4 and the ObjFns are n1= 30 , n2=50, n3=50, n4=60 then the outputs are n1 n2 n3 n4 and n1 n3 n2 n4 .

# Answer
> 0 votes
Seems $O(n^5)$ since the obj function needs to be evaluated $O(n)$ times for each of the remaining sets (of which there are $n$ at the start). I'm assuming your objective function changes as you add selected sets (i.e. you can't calculate the obj function once per set and store it).

---
Tags: algorithms, complexity-theory, time-complexity, algorithm-analysis, polynomial-time
---


# Question
Title: Expected value of the remainder when a random variable is divided by a number
Let $a,b,c,d,e,f$ be integers selected from the set $\\{1,2,\cdots, 100\\}$ uniformly and at random with replacement. Let $M=a+2b+4c+8d+16e+32f$. What is the expected value of the remainder when $M$ is divided by $64$?

I was trying to write a python code to calculate the answer. Let $f(x)$ be the remainder when $x$ is divided by $64$, then the desired number is $$E(f(M))=\sum\_{k=1}^{100}f(M)\cdot \frac{1}{100}.$$

Here is my code:

```
S=0
for k in list(range(1,101)):
  S += ((k+2*k+4*k+8*k+16*k+32*k)%64)/100
print('E(M mod 64)= ', S)

```

The output is `E(M mod 64)= 36.540000000000006`. But the answer should be $31.5$. What is wrong? Thanks in advance.

# Answer
It gives the wrong answer because you got 6 random variables instead of one, but you are computing esxected value as if you have only one random variable. Let me put this on maths:
Let $f$ be the remainder by 64 for $M$, then $f$ is a function of the random variables $a,b,c,d,e,f$, therefore $$Ef(M)=\displaystyle \sum\_a\sum\_b\ldots\sum\_e\sum\_ff(M)P(a,b,c,d,e,f)$$ Since your selection is uniform with replacement, $P(a,b,c,d,e,f)=1/100^6$. Now you need to rewrite your code.
> 0 votes

---
Tags: python
---


# Question
Title: Understanding P, NP with an example decision problem
I was reading the definitions of p vs np in \[this post\] (What is the definition of P, NP, NP-complete and NP-hard?) and I was wondering about how to classify the example decision problem where you return 1 if a natural number is even and 0 otherwise. I think this would be P complexity, but my TA said that there are infinite even numbers so it should not be P. I think there would be a way using modulo or something to solve this problem more efficiently, but I am honestly confused about P and NP in general. Note that this is not a homework question, I am just trying to wrap my head around complexity before finals.

# Answer
> 0 votes
The problem of deciding if a number is even is in $\mathsf{P}$, since you can design a deterministic polynomial-time algorithm for it. The exact algorithm depends on how you encode the number. If it is in unary you can just count the number of bits modulo 2, if it is in binary you can just check that the last bit is a 0.

Since this problem is in $\mathsf{P}$, it is also in $\mathsf{NP}$ (recall that $P \subseteq \mathsf{NP}$). We don't know whether the problem is $\mathsf{NP}$-complete. If that's the case, then this would imply $\mathsf{P}=\mathsf{NP}$, which is a major open problem.

The claim "there are infinite even numbers so it should not be in $\mathsf{P}$" does not make any sense. All finite languages are decidable in polynomial time **but the converse is not necessarily true**. The fact that there are infinitely many even numbers does not tell you anything about whether your problem belongs to $\mathsf{P}$ or not.

---
Tags: complexity-theory, terminology, complexity-classes, p-vs-np
---


# Question
Title: Detecting cycles with weight zero in a directed graph
I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles.

I need to find an algorithm that returns `true` if and only if there is a cycle with weight zero in the graph.

The time complexity needs to be $O(|V||E|)$, so I thought about using Bellman-Ford algorithm, but I have two problems with that:

First, the graph doesn't necessarily connected, so I can't pick an arbitrary source vertex for the algorithm.

Second, I can't figure out how the algorithm can help me, and what I can do with its output.

I know that a similar question have been asked, but the answer just suggests to run Bellman-Ford algorithm, but as I mentioned, I can't choose a source vertex. In addition, I don't understand why the suggested answer will work at all.

# Answer
> 1 votes
Add a new vertex $s\_0$. Add edges of weight 0 from $s\_0$ to each other vertex. Now you have a graph with a source vertex $s\_0$. Run the previously mentioned algorithm on this new graph, using $s\_0$ as the source vertex.

---
Tags: graphs, weighted-graphs
---


# Question
Title: Proof that for 2n nodes of +1 and -1 position doesn't count
I'm having a hard time understanding how to solve this problem for my Computer Science 101 class.

On a circle there are $2n$ nodes. $n$ out of these hold -1 power and $n$ hold +1 power. Say we play a game where we randomly start from a node and move clockwise. As we move and land on different nodes, the number on each node we land on is added to our score. So, if we jump from a +1 node to a -1 and then a +1 our score is 1. The rules are:

1. We win after we've gone through all the nodes, and
2. If our score drops to -1 at any point we lose.

The question is to prove that for any random sequence, it doesn't matter which, there's always at least one node we can start from that lets us win the game.

I started first by stating the information a bit differently:

a) I can only start from a +1 node, which would leave any player with $2n+1$ nodes where $n$ nodes are -1.

b) There are $2^{n}$ possible sets of positions, but because for any one of these I can start anywhere the $n$ permuatations, we have $\frac{2^{n}}{n}$ possible games.

I first thought that I could show that the question's assertion holds by creating a DFA that would read the language $L=\\{w \in \\{-1,+1\\} \text{ : sum never becomes -1}\\}$. I made it with $q\_0$ as my starting state with $n$ states on its right and one on the left with appropriate transitions for -1 and +1. But all that shows is that some $w$s fail and some do not. It doesn't prove that in a set of our nodes there's at least one possible node to pick so we can win.

Any ideas on how I can prove that?

# Answer
You can prove the claim by induction on $n$. If $n=1$ the claim is clearly true since it suffices to start from the unique "+1" node.

When $n \> 1$, let $u$ and $v$ be two consecutive nodes (moving clockwise) such that $u$ is a "+1" node and $v$ is a "-1" node. This pair always exists. By induction hypothesis there is some vertex $w$ that allows you to win the game in the instance with $2n-2$ nodes obtained by deleting $u$ and $v$. Then, starting from $w$ also wins the original instance with $n$ nodes.
> 12 votes

# Answer
Not a complete proof, but a picture that hints to a solution.

If you start at a random point and add the numbers, then after a complete circle you end again at the initial zero. Track all the intermediate scores. If we start at the node with minimal score you will never get a negative score.
> 19 votes

---
Tags: finite-automata
---


title: What's the point of 48 bit colour?

text:
# Question
Title: What's the point of 48 bit colour?
I've read that the human eye can only really decipher around 10 million different colours, so what's the point in technology that uses 48-bit colour, which allows for $2.81\times 10^{14}$ colours. Is this not like giant, super inefficient overkill?

# Answer
Some reasons for using more bits per color channel:

1. **Tetrachromats.** There are rare humans with four types of cone receptors in their retinas instead of the usual three. These people can distinguish an order of magnitude more color shades than the rest of us.
2. **Color gamut**. Your question assumes that the 16 million colors available in 8-bit per channel RGB exactly covers the colors that normal humans can see. But if that were so then we would only need one RGB color space. We have more. More bits per channel allows a wider gamut of colors to be represented without visible posterization, because the increased bit depth means smaller gaps between the individual shades.
3. **Image manipulation.** Every image manipulation, from switching color models for printing, to sharpening, to resizing, to tone curve adjustment, loses information. The more information you start with the more you have at the end of post-processing. The more information you start with the easier it is to avoid the introduction of visible artifacts such as posterization.
> 9 votes

# Answer
The 10 million you gave - something about that, but we do not know which one exactly because it differs per person.

So there is the case that some range of blue is not fully seen by some person, but the orange range is, and another one with different color spectrum looks at the same e.g. screen and also has plausible view without discontinuities.
Another point is using graphic effects, manipulating the image - with more discrete values the roundoffs are smaller.

The gamut, which represents what we see and how screens are displaying it we are far behind really showing all colors. Also please remember that every person has dense and sparse regions in different places, depending fully on individual rods and cones distribution in eye.

Let me introduce also some analogy to this "overkill":
Please think of frames per second in movies / games. For the most people 24fps is motion enough, 30fps for the majority, 60 fps - beyond human perception, but still we increase the counter and the feeling of motion being natural increases, which is also hard to explain because we cannot really "see" events lasting below 40ms, but we can tell the difference in reception, which with higher fps feels more natural.

Think about what we hear - 22kHz is the upper bound, but we preserve 44kHz and it makes sound less mechanical and the illusion of being at concert hall increases with higher sampling rate.
The same happens with screens (printers etc.).
There are hues that the most of the people can arrange colors in increasing order - for example people are very sensitive to green hue and see far more then screen can show.
> 4 votes

# Answer
Regarding color gamut... it is almost impossible for ordinary 24 bit RGB to represent the color of many metals with any degree of accuracy. Increasing the bit depth should help improve that situation.
> -1 votes

---
Tags: graphics, hci
---


# Question
Title: Maximal edge weight clique of given size
Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M\<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. we wish to find a set of vertices $S$, $$\max\_S\sum\_{i\in S} \sum\_{j \in S, j\neq i} w\_{ij}\quad \text{s.t.}\quad |S|=M$$

---

Some questions regarding this problem assuming $M\ll N$:

1. The brute force algorithm for finding $S$ is simply to examine all $N \choose M$ possibilities, $O(2^N)$. Are they faster deterministic methods? I suspect not, but can we prove this?
2. A simple greedy approach would be to sort the edges by weight, and choosing the top $M$ vertices appearing in these pairs, $O(N^2 \log N)$. Are there known expected performance bounds for this approach? Are there more optimal non-deterministic approaches?

# Answer
Unless the strong exponential time hypothesis fail, there is no deterministic algorithm that can solve your problem in time $N^{o(M)}$, since such an algorithm would immediately solve the $M$-clique problem in the same amount of time. See this paper.

Regarding your greedy algorithm: first of all its time complexity is $\Omega(N^2)$ (although a variant that uses a max-heap only requires time $O(M^2 + M \log N)$). Moreover it cannot provide any constant approximation ratio. Think of a graph consisting collection of $\lfloor M/2 \rfloor$ disjoint edges with weights $1 + \epsilon$ together with a $M$-clique in which each edge weights $1$. Complete the graph with edges of weight $0$.

Your algorithm would return a clique with a total weight of at most $\frac{M+ M\epsilon}{2}$, while the optimal solution has a weight of at least $\frac{M^2}{2}$. The ratio of these two quantities is $\frac{1+\epsilon}{M}$ which approaches $0$ when $M$ approaches $\infty$.

I don't know what you mean by "more optimal non-deterministic approaches". It is very easy to come up with a linear-time non-deterministic algorithm for the decision version of your problem. Then polynomially-many invocations of such an algorithm suffice to find the optimal solution to the optimization version.
> 2 votes

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


# Question
Title: How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time
This is a problem I've come across while studying on my own; it's from *Algorithms* by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is:

> Give a linear-time algorithm that takes as input a tree and determines whether it has a *perfect matching*: a set of edges that touches each node exactly once.

In the context of this book:

* A *tree* is an undirected, connected and acyclic graph.
* A linear-time algorithm on a graph $G = (V,E)$ is something that runs on $O(|V| + |E|)$ time.

Thinking on the problem, the following seemed promising:

> Of course, the tree must have an even number of nodes, otherwise we can exit early and report that there is no perfect matching. Additionally, if at any point we find an isolated vertex, we can can do the same.
>
> Since we're dealing with a tree, we can search for a leaf $v$, a node with a single incident edge $(u,v)$. This edge *must* be in the perfect matching, for it's the only one that matches $v$.
> We then remove the vertices $u$ and $v$ from $T$, along with all edges that involve them, and repeat the process.
>
> If we remove all vertices in this manner, we have found a perfect matching.
>
> Notice that, while the removal may disconnect the graph, it will remain acyclic and this is what matters. Disconnecting the graph essentially splits the tree into multiple trees, so the iteration continues to make sense even in this case.

Now, this problem shows up in the chapter about greedy algorithms, so this approach seems like a natural fit.

Moreover, searching on the topic I've found that a tree has at most one perfect matching (see, for instance, this). In other words, if it has one, it is unique, so the algorithm must produce the one if it exists.

However, when actually thinking about implementation, I don't really see how this runs in $O(|V| + |E|)$. The naive approach appearcs to be quadratic, because at each step we need to scan for a leaf and update the graph, and neither of these take constant time. I'm mostly thinking of adjacency list representation, but this seems to hold true for adjacency matrix as well.

I've also toyed with precomputing and updating degree values for vertices, but haven't nailed it.

Searching more on the topic, I've come across this link, which suggests what's essentially the same algorithm to solve the same problem (number 2 on the exam). However, in the statement and solution, they only claim it to run in polynomial time.

> How would one implement this algorithm in linear time, or else design another algorithm to solve the problem in linear time? What do we assume about data structures or operation complexities involved?

---

EDIT: Following on sdcvvc's suggestion, here's some C++-esque pseudocode implementing his idea. I think this works.

```
enum class MatchStatus
{
    HAS_MATCH,
    ROOT_NEEDS_MATCHING,
    CANNOT_MATCH
}

bool hasMatching(tree t)
{ return hasMatching(t.root) == MatchStatus::HAS_MATCH; }

MatchStatus hasMatching(node treeRoot)
{
    // Keep track of whether the current node (root of the current (sub)tree)
    // is matched to some child node
    bool isMatched = false;

    for(node subTreeRoot : treeRoot.children)
    {
        MatchStatus subTreeStatus = hasMatching(subTreeRoot);

        if(subTreeStatus == MatchStatus::CANNOT_MATCH)
            return MatchStatus::CANNOT_MATCH;

        // The subtree has a perfect matching *except* its root needs to be matched
        else if(subTreeStatus == MatchStatus::ROOT_NEEDS_MATCHING)
        {
            if(isMatched)
                // Current node is already matched
                // The subtree root needs a match but cannot be matched
                return MatchStatus::CANNOT_MATCH;

            else
                // Match the current node to subTreeRoot
                isMatched = true;
        }

//      else if(childStatus == MatchStatus::HAS_MATCH)
//          continue;
    }

    return isMatched ? MatchStatus::HAS_MATCH : MatchStatus::ROOT_NEEDS_MATCHING;
}

```

# Answer
Suppose you remove vertices of degree 1 as long as possible, but with an additional constraint: you never disconnect the graph. If you think about it, either you will succeed in removing all vertices (the tree has a matching), or you will end up with a single vertex (which cannot be covered), or you'll be stuck with this situation:

```
 ...
  |
  *
 / \
 * *

```

i.e. a vertex with two (or more) leaves, which does not have a matching no matter what is the rest of the graph.

You can classify trees into (A) coverable, (B) coverable except the root and (C) inherently uncoverable.

Suppose you've computed the status of trees $T\_1,\dots,T\_n$ and would like to compute the status of the tree consisting of a vertex connected to $T\_1,\dots,T\_n$. If any of $T\_i$ is (C), then the result is (C). If all $T\_i$ are (A), then the result is coverable except for the root (B). If there is one (B) and everything else is (A), then you can match that vertex with the root and the result is (A). Finally, if the tree is connected to more than one (B), it can't be covered (C). This is a recursive traversal of the tree, which can be done in linear time.
> 3 votes

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


# Question
Title: How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then finding that assignment with at most $2n+1$ times using $M$?

I know that every $SAT$ instance can comverted to $CNF$ clauses so i think we can do it recursively to checking satisfiblity and then finding it, but i get stuck to formulate it that how we can do it.

Also similar question asked at this link.

# Answer
> 1 votes
If you want to decide whether a CNF formula is satisfiable or not you can simply decide it with one invoke of $M$ on your formula. But if you want to calculate its satisfying assignment, your problem is a search problem not a decision problem. To do that you can simply invoke $M$ on $\phi \[True/x\_i\]$ (substituting variable $x\_i$ with value $True$) for each variable $x\_i$ recursively until no more variables left. It is easy to see that if the result is $Accept$, you can assign $True$ to $x\_i$ and $False$ otherwise and recurse on the new formula $\psi= \phi \[v(x\_i)/x\_i\]$. If you want more details about how to formulate it you can check Arrora complexity book for this purpose.

# Answer
> 1 votes
First of all, check whether $\phi$ is satisfiable using $M$. If it is, you can find a satysying assignment as follows:

For each variable $x$ of $\phi$ do the following:

* Set $x$ to true. Simplify $\phi$ to remove $x$ (if a clause contains $x$ then you can delete the clause, if a clause contains $\overline{x}$ then you can delete $\overline{x}$ from the clause) and let $\phi\_x$ be the resulting formula.
* Check whether $\phi\_x$ is satisfiable using $M$.
* If $\phi\_x$ is satisfiable, set $\phi=\phi\_x$ and continue with the next variable.
* Otherwise $x$ must be false. Set $x$ to false and update by $\phi$ by removing all occurrences of $x$ or $\overline{x}$ (if a clause contains $\overline{x}$ then you can delete the clause, if a clause contains $x$ then you can delete $x$ from the clause). Then continue with the next variable.

At the end of this process, the values assigned to the variables are a satisfying assignment of the input formula. This requires at most $n+1$ invocations of $M$.

# Answer
> 1 votes
You can actually do it in at most $n+1$ queries. Just first check that the whole sentence is satisfiable, then play guess-and-check for each variable. Writing $|\phi|$ for the number of variables in the sentence $\phi$,

$$\mathit{cnf\\\_and\\\_sat}(\phi)=\left\\{\begin{align\*} &\mathit{cnf}(\phi,|\phi|)&\mathit{sat}(\phi)\\ &\mathbf{unsat}&\mathrm{otherwise} \end{align\*}\right.$$

$$\mathit{cnf}(\phi,n)=\left\\{\begin{align\*} &\emptyset&n=0\\ &\\{x\_n\\}\cup\mathit{cnf}(\phi\land x\_n,n-1)&n\ne0\enspace\mathrm{and}\enspace\mathit{sat}(\phi\land x\_n)\\ &\\{\overline{x\_n}\\}\cup\mathit{cnf}(\phi\land\overline{x\_n},n-1)&\mathrm{otherwise} \end{align\*}\right.$$

---
Tags: algorithms, complexity-theory, formal-languages, turing-machines, automata
---


# Question
Title: Searching for sorting algorithm taking into account all possible solution of similar numbers
I need a reference for sorting algorithm where all possible orders are considered.

example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ascend

The two solutions are:

n1(3) n2(5) n4(5) n3(10) and

n1(3) n4(5) n2(5) n3(10)

1. what is the name of this technique?
2. what is its time complexity?
3. If I do not know the values by beginning as they may be dependent on each other sequentially, how to predict the number of all possible solutions?

# Answer
> 1 votes
The only way to have multiple solutions is if there are repeated values. So say your numbers are 3 10 5 5 5 3 10 3 10 5 3 10, then you can simply find the set of distinct values (3 10 5) and then sort this (3 5 10) and then since there are four copies of 3, four copies of 5, and three copies of 10, you just write out all 4!\*4!\*3! permutations of your objects.

1. I do not know if there is a name of this sort of thing, aside from 'sorting objects with repeated keys'
2. The time complexity to write them all out will depend heavily on the number of repeats of a number. In the worst case, all values are equal, and so every permutation of your $n$ objects needs to be written out, and this takes $O(n!)$ time
3. If you can scan your list and count how many copies of each type there are, then the formula I gave above (the product of all the factorials of the frequencies) will be the number of sorted orderings

# Answer
> 1 votes
Just ise any regular sorting algorithm.

All other permutations are guaranteed to be formed by taking all inner permutations of elements with the same value (e.g, if there are 3 elements with the same value, we consider all arrays with all $3!=6$ permutations of those elements).

The time complexity will vary by the number of "same value elements".

In general, here are the time complexities (in terms of the number of "same value elements):

* If all elements have the same value, we have to consider all permutations and hence the complexity is $\Theta(n!)$
* If all elements are distinct in their values, then the time complexity is $O(n\log(n))$ since we won't consider any more permutations.
* If there are $k\_1, \dots,k\_l$ elements of values $v\_1,\dots,v\_l$ respectively, then the complexity is $O\left(n\log(n)+\Pi\_{i=1}^l k\_i!\right)$

---
Tags: algorithms, time-complexity, reference-request, sorting, quicksort
---


title: How to think about heuristics

text:
# Question
Title: How to think about heuristics
I have a game about drone delivery company.

The game consists of a rectangular map, which contains tiles that cannot be passed. I can control a certain amount of drones, each one of them starts at a certain tile. In addition, There are clients that move along a certain circular path (each client has his own path). Every client has a few packages that are scattered over the map.

The map, the initial location of the drones and the packages, and the path of each client along with his packages are given as parameters to the game.

The goal is to deliver each client his packages in the minimal number of steps.

In each step I can control all of the drones to move (right, left, up and down according to the map), pickup a package (if the drone carries less than two packages), deliver a package (if its client is in the same tile) and to wait.

I need to think about an heuristics for the game: given a state (the location of each drone, package and client) I need to come up with an heuristic that will return a number. The returning number is used in a search algorithm, and the goal is to minimize the number of actions to the goal.

I am having troubles to think about a good heuristics, even when there is only one drone (and in the game there are a few). I thought about the shortest distance to a package or a tile of a client (which is complicated, since the clients are moving) , but I don't know how to continue from here.

# Answer
You can pick any (not-necessarily-optimal) simple heuristic strategy for delivering packages, figure out how long it would take with that strategy, and use that as your heuristic.

For example, here is one idea, based on hub-and-spoke distribution. Let $H$ be a position in the center of the area, which will represent the hub. The idea is that each package will be assigned more or less arbitrarily to a drone, and that drone will fly from $H$ to pick up the package and then deliver it immediately and fly back to $H$ (so the drone only carries at much one package at a time).

For each package, compute the shortest time for a drone starting at $H$ to fly from $H$ to the package, then deliver from there to the client's future location, then fly from there back to $H$. (You can compute this by looping over all future client locations, and computing the Manhattan distance between each pair of those points, and comparing to the time when the client will be at that future location.)

Now sum up all of these times, plus the time it takes for each drone to fly from its starting point to $H$. Divide by the number of drones. The result is an estimate of the time it will take all packages (likely an over-estimate, as it uses a highly non-optimal strategy for distribution).

Of course, if this is too coarse an estimate, you can pick a slightly better strategy. For instance, maybe you use a greedy heuristic: whenever a drone is free, it picks the package that it can deliver first, and takes responsibility for that package and immediately flies to it and delivers it. You can use your creativity in coming up with simple strategies, and use the time they take as your heuristic.
> 0 votes

---
Tags: artificial-intelligence, heuristics
---


# Question
Title: Can Operating system allocate a page of process to any free frame in memory?
Consider I have a user program of 6 pages and 4 byte page size. Now my memory has 300 frames out of which 10 frames are free for allocation. Can the OS allocate **page 1 of the given process to any of these 10 frames** or is there any specific algorithm to select a frame?

# Answer
> 1 votes
That's entirely up to the OS, and different OS's may have different strategies. In principle, the OS could assign any frame it wants.

---
Tags: operating-systems, paging, memory-allocation
---


# Question
Title: Why proofs of Cook's Theorem assume k is given (n^k for NTM)?
A typical proof of Cook-Levin's Theorem proceeds like this:

> Suppose problem X is in NP. Then there is an NTM M deciding X in time n^k, for some k. Given a word w, NTM M, **and k**, we construct a Boolean formula φ in polytime(|w|) that is satisfiable iff the NTM accepts w, as follows. \[...\]

Question: why can we assume that k is given? I agree that "there exists such k", however knowing that it exists and directly using it in the reduction are different things (to me). I would expect the reduction to be independent of k (so the formula doesn't depend on k), but the proof of its correctness relies on the fact that k in N exists.

# Answer
> 2 votes
Look at the statement of Cook's theorem: it states that for any problem in NP, there exists a reduction from that problem to 3SAT. The key part is the "there exists". The proof only needs to show that there exists such a reduction. For these purposes, it suffices to note that there exists a $k$ such that $M$ runs in time $O(n^k)$. There is no requirement that we be able to find $k$ or find the reduction.

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


title: reduction from ALLTM to ETM

text:
# Question
Title: reduction from ALLTM to ETM
I am trying to understand why this "proof" of ETM undecidability is wrong.

ALLTM={ \< M \>|M is a TM, L(M)=∑\*}

ETM={\< M \>|M is a TM, L(M)=∅}

We know that ALLTM is undecidable, lets assume ETM is decidable (T is a TM that decides ETM) and get a contradiction.

```
 S= "On input < M >, M is a TM:

  1.Construct the following TM M1,

   M1=" On input x:

    1.Run M on x, if M accepts x, reject. otherwise, accept x."

    2.Run T on input < M1 >.

    3.If T accepts, accept, if T rejects, reject.

```

If ETM is decidable, ALLTM is decidable =\> ETM is undecidable.

Why this reduction doesn't prove that ETM is undecidable?

# Answer
The problem is the line "If M accepts $x$, reject. Otherwise, accept $x$." You can't check to see if a machine rejects $x$ and then react accordingly, because some machines reject by *looping forever* (!). The broader consequence of this is you can't take the complement of a Turing machine.

That's a shame because if you could convert a machine $M$ into another machine $M^\prime$ which accepts all of the strings that $M$ rejects and vice-versa, you could show the reduction between $\mathsf{ALL}\_\mathsf{TM}$ and $\mathsf{EMPTY}\_\mathsf{TM}$ rather easily.

Instead, you need a different approach to prove that $\mathsf{EMPTY\_{TM}}$ is undecidable.

---

Here's a different reduction, this time from the halting problem.

1. Given a TM $M$ and a word $w$, construct the machine $M^\prime$ which, on input $x$, simulates $M$ on $w$ for $\mathsf{length}(x)$ steps and accepts if and only if the simulation finishes with accept.
2. Now, if $M$ eventually accepts $w$, then $M^\prime$ accepts some sufficiently long strings. If $M$ rejects $w$, then $M^\prime$ doesn't accept any strings.
3. So if you can decide whether $M^\prime$ is empty, you can decide whether $M$ accepts $w$. But acceptance is undecidable, therefore emptiness is undecidable.
> 1 votes

---
Tags: turing-machines, reductions, undecidability, proof-techniques
---