# Question
Title: Changing probabilities to 0/1 in definition of class IP
A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$, $$w\in L\Rightarrow Pr\[V\leftrightarrow P\text{ accepts }w\]\geq2/3$$ $$w\notin L\Rightarrow Pr\[V\leftrightarrow Q\text{ accepts }w\]\leq1/3$$

I am trying to understand the claim that changing the $1/3$ to $0$ for the $w \notin L$ case is equivalent to having a deterministic verifier, thus reducing the class to $\mathbf{NP}$. Is this because, in this case, we could rig all of the $V$'s interactions with $P$ so that whenever $Pr\[V\leftrightarrow P\text{ accepts }w\]\>0$, it now determinstically accepts?

If this is correct, then why can't we do a similar thing for the hypothetical situation where the $2/3$ is replaced by a $1$ (apparently doing this does not change $\mathbf{IP}$)? My intuition is that we can't make a similar modification because it would require modifying $V$'s behaviour *for all $Q$.* But my thoughts are bit fuzzy here...

Can someone please help clarify?

# Answer
> 1 votes
Suppose you have a (randomized) verifier $V$ such that, for all $Q,w$,

$$\begin{align\*} w\in L &\implies \Pr\[V\leftrightarrow P\text{ accepts }w\]\geq2/3\\ w\notin L &\implies \Pr\[V\leftrightarrow Q\text{ accepts }w\]= 0. \end{align\*}$$

Since $P$ is one possible value of $Q$, it follows that

$$w\notin L \implies \Pr\[V\leftrightarrow P\text{ accepts }w\]= 0.$$

This means that for all $w \notin L$, there is no choice of random bits such that $V\leftrightarrow P$ accepts $w$, while for all $w \in L$, there *is* a choice of random bits such that $V\leftrightarrow P$ accepts $w$.

This gives you a certificate for the claim that $w \in L$: namely, the random bits used during some accepting execution of $V \leftrightarrow P$ on $w$. By the above arguments, if $w \in L$, such a certificate is guaranteed to exist, whereas if $w \notin L$, no such certificate exists. $V \leftrightarrow P$ can be used as a verifier to check the certificate. Since $V \leftrightarrow P$ runs in polynomial time, we have a polynomial-sized certificate and a polynomial-time verifier for $L$, so it follows that $L$ is in NP.

This also helps answer your second question. If you change the $2/3$ to $1$ but don't change the $1/3$ to $0$, the above argument doesn't go through: you can't conclude that there is no certificate for $w \notin L$, so you no longer have a certificate and verifier for $L$.

---
Tags: complexity-theory, complexity-classes, interactive-proof-systems
---


# Question
Title: Playing the game of life on an infinite grid
I would like to implement Conway's game of life on a grid that is infinite in all directions. It should be initialized with an initial pattern and then run, e.g, like this:

```
set(-500,200)
set(-501,201)
set(-502,202)
start()

```

What data structure should I use?

Matrices usually start with (0,0). One solution is to keep track of the smallest and largest index of a living cell, and move the matrix accordingly (so in the above example, we will need a 3-by-3 matrix). However, this might require to copy the entire matrix whenever a new cell is born.

Another solution is to use a hashtable indexed by pairs of indices. However, in this case the calculation of the next step will be more expensive since cells will not be next to their neighbors.

Is there a better data structure for such infinite grid?

# Answer
> 2 votes
If you want to do better than iterating over each cell, or at least the range of live cells, use Hashlife.

http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478?pgno=1

https://www.youtube.com/watch?v=l228ARRYkNE

---
Tags: data-structures
---


# Question
Title: Given all pairs shortest paths matrix, find graph with minimum total sum of edges
I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some pairs of nodes in the graph $(i,j)$.

We don't have the original graph, we instead only have the all pairs shortest paths matrix given. We need to find minimal number $x$ such that there is a way to build graph whose all pairs shortest path matrix will be the same as the given one and the sum of the edges in the graph will be exactly $x$.

Note that for some all pairs shortest paths there wont be way to build such graph, so we should also check if there can be any valid solution.

For example: for the matrix below we should output 6, if we link edges (2, 3) with cost 2 and edges (1, 3) with 4

```
0 6 4
6 0 2
4 2 0

```

I noticed that the cheapest edges will always exist, so I sorted all the numbers, then I tried using some data structure for checking if from the cheaper edges we have already covered the path from node i to node j, or we should also include new edge in the path.

However my approach doesn't give good results. Please share some advice in which direction the right solution should be.

# Answer
> 1 votes
Let $G=(V,E,w)$ be a weighted graph with $w$, a positive length (weight) function on $E$, i.e, the length of edge $(u,v)$ is $w(u, v)$. Let $d\_{w,G}(u, v)$ denote the distance between vertex $u$ and $v$. $d\_{w,G}$ will be written as $d\_w$ or $d\_G$ or $d$ if there is no ambiguity.

**An edge $(x,y)\in E$ is essential** if $w(x,y)=d\_w(x,y)$ and each path from $x$ to $y$ other than the edge $(x,y)$ is longer than $w(x,y)$. Let $E'$ be the set of all essential edges of $G$. The **essential subgraph of $G$** is $E(G)=(V, E', w)$, where we abuse $w$ to mean its restriction on $E'$ as well. **A weighted graph is essential** if it is an essential subgraph of itself, i.e., if all of its edges are essential.

### Claim: $d\_{E(G)}=d\_{G}$.

Proof. Since $d\_{E(G)}\ge d\_G$, it is enough to show $d\_{E(G)}\le d\_G$. Let $(u,v)$ be a pair of vertices and $p = (u\_0=u, u\_1, u\_2,\cdots, u\_n=v)$ be one of the shortest paths from $u$ to $v$ in $G$.

Consider edge $(u\_i, u\_{i+1})$, which is an edge in that shortest path and, hence, $w(u\_i,u\_{i+1})= d\_G(u\_i,u\_{i+1})$. If $(u\_i, u\_{i+1})$ is not essential, then we can find another shortest path from $u\_i$ to $u\_{i+1}$, which can replace the edge $(u\_i, u\_{i+1})$ in $p$.

Repeat the replacement above. Since each replacement increases the number of vertices in $p$ by at least 1, the replacements must end since $p$ can have at most all vertices and no two vertices in $p$ can be the same. In the end $p$ is the shortest path from $u$ to $v$ in $G$ that only has essential edges. Q.E.D.

### Claim. $E(E(G))=E(G)$, i.e., $E(G)$ is essential.

Proof. It is immediate by definition.

### Claim. Let $G\_1=(V, E\_1, w\_1)$ and $G\_2=(V, E\_2, w\_2) $ be two weighted essential graphs. If $d\_{G\_1}=d\_{G\_2}$, then $G\_1=G\_2$.

Proof. Suppose $e=(x,y)$ is in both $E\_1$ and $E\_2$. Then $w\_1(e)=d\_{w\_1}(x,y)=d\_{w\_2}(x,y)=w\_2(e)$.

Hence, there remains to prove that $E\_1=E\_2$.

For the sake of contradiction, let $c$ be the smallest length such that there is an edge $e$ such that

* either $e\in E\_1$ with $w\_1(e)=c$ but $e\not\in E\_2$,
* or $e\in E\_2$ with $w\_2(e)=c$ but $e\not\in E\_1$.

WLOG, let $e$ be an edge of the former case. Since $d\_{w\_2}(x,y)=d\_{w\_1}(x,y)=w\_1(e)=c$, there is a path $p=(x\_0=x, x\_1, \cdots, x\_n=y)$ in $G\_2$ such that $w\_2(p)=c$ and $n\gt1$. Since $w\_1(p)\gt c$ as $e$ is an essential edge of $G\_1$, there exists edge $e\_i=(x\_i, x\_{i+1})$ for some $i$ such that $w\_1(e\_i)\>w\_2(e\_i)$. So $e\_i\in E\_2$, $e\_i\not\in E\_1$ and $w\_2(e\_i)\lt w\_2(p)=c$. This contradicts the assumption that $c$ is the smallest length of that property. Q.E.D.

### Claim. Let $G\_1=(V, E\_1, w\_1)$ and $G\_2=(V, E\_2, w\_2) $ be two weighted graphs. If $d\_{G\_1}=d\_{G\_2}$, then $E(G\_1)=E(G\_2)$.

Proof. Note that $E(G\_1)$ and $E(G\_2)$ are essential graphs. Since $d\_{E(G\_1)}=d\_{G\_1}=d\_{G\_2}=d\_{E(G\_2)}$, this claim is implied by the previous claim. Q.E.D.

### Claim. Let $G=(E,V)$ be a graph with known all-pairs distance given by $d\_G$. Suppose that $d\_G$ is induced by a positive weight function on $V$. Then $E(G)$ is independent of that weight function. Furthermore, $d\_{E(G)}=d\_G$.

Proof. This is just a restatement of previous claim.

The claim above shows that the question in the title is none other than finding $E(G)$ given its all-pairs distances.

### Algorithm to find $E(G)$ given $G$ and the distance function $d\_G$.

<sub> This algorithm is stated roughly in the question and clearly in Vince's answer. For completeness it is included here. </sub>

Given $V=\\{1,2,\cdots,n\\}$ and $d(i,j)$ the distance between $i$ and $j$ for all $i$ and $j$, here is the algorithm to find $E(G)$ if $d$ is indeed induced by a length function on $V$ or return false if not.

1. Initialize a graph $H$ with nodes $V$ and no edges.
2. Iterate through $d(i,j)$ in increasing order.
    1. Compute $h(i,j)$, the distance between $i$ and $j$ in $H$ ($\infty$ if $i$ and $j$ are not connected by a path).
    2. Compare $h(i,j)$ and $d(i,j)$.
        * if $h(i,j) \< d(i,j)$, return false and stop the algorithm.
        * if $h(i,j) \> d(i,j)$, add edge $(i,j)$ with weight $d(i,j)$ to $H$.
3. return $H$.

### Exercises

**Exercise 1.** (One minute or less) Verify that $E(G)$ is essential if $G$ is a weight graph.

**Exercise 2.** Show that if $d(i,j)$ is induced by a weight function on $V$, the algorithm above returns $E(G)$.

# Answer
> 1 votes
I think your approach works even if you did not give much details.

Let's call $A$ the matrix. First you sort all pairs ($i$, $j$) with $i \< j$ and $A\_{ij}$ increasing. You also have initially a graph $G$ with all nodes and no edges.

Then you process the pairs ($i$, $j$) one by one deciding whether to add an edge between nodes $i$ and $j$:

* compute $D$, the total weight of the shortest path existing in $G$ from $i$ to $j$ ($+\infty$ if no path).
    1. if $D \< A\_{ij}$, the problem has no solution,
    2. if $D = A\_{ij}$, do nothing,
    3. if $D \> A\_{ij}$, add the edge between $i$ and $j$ of weight $A\_{ij}$ to $G$.

If the shortest path from $i$ to $j$ is undirect, it necessarly has already been placed as you sorted your pairs increasing.

---
Tags: graphs, shortest-path, weighted-graphs
---


# Question
Title: Are regular expressions a*a and aa* equivalent?
Let $\Sigma = \\{a, b\\}$ an alphabet. Are the regular expressions $a^\*a$ and $aa^\*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.

# Answer
> 6 votes
Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w\_1\dots w\_\ell$ (where the $w\_i$ are the individual characters) such that, for some $d$, $w\_1\dots w\_d$ matches $R$ and $w\_{d+1}\dots w\_\ell$ matches $S$. Here, $d=0$ and $d=\ell$ mean that we've split $w$ into $\varepsilon$ and $w$ and vice-versa.

So, consider $R=a^\*$ and $S=a$. Then $RS$ matches any string $w=w\_1\dots w\_\ell$ such that, for some $d$, $w\_1\dots w\_d$ matches $a^\*$ and $w\_{d+1}\dots w\_\ell$ matches $a$. We must have $d=\ell-1$ and $w\_\ell=a$ because only the string $a$ matches $a$, and it has length $1$. And we must have $w\_1=\dots=w\_{\ell-1}=a$ because that is the only length-$(\ell-1)$ string that matches $a^\*$. So $w=a^{\ell}$ for some $\ell\geq 1$.

Considering $R=a$ and $S=a^\*$, an almost identical argument shows that any string that matches $aa^\*$ must also be $a^{\ell}$ for some $\ell\geq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^\*$ matches any string $a^\ell$ for $\ell\geq 0$, and $a$ matches the single string $a=a^1$. So $a^\*a$ matches any string $a^\ell a$ for $\ell\geq 0$, i.e., any string $a^{\ell+1}$ for $\ell\geq 0$, i.e., any string $a^\ell$ for $\ell\>0$. Similarly, $aa^\*$ matches any string $aa^\ell=a^{1+\ell}$ for $\ell\geq 0$, i.e., $a^\ell$ for $\ell\>0$.

---
Tags: regular-expressions
---


# Question
Title: Do I need to consider instance restrictions when showing a language is in P?
I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. In my proposition of an algorithm in P, I wasn't sure if my algorithm needs to verify that $G$ indeed contains no cycle or if I assume all inputs are instances of this language (assume all inputs are acyclic graphs). In general, I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time. I'm still learning so I am confused about this part and this has been bugging me for a while.

If this question is too confusing, consider 3SAT. Must I show that verifying the input is indeed a 3CNF is in P to conclude, or can I assume we are only considering inputs within an instance?

# Answer
> I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time.

Very nice question!

What you are talking about is best characterized as promise problem, "a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs". The conventional way to handle promise problem is there are no requirements on the output if the input does not belong to the promise. In particular, if you want to show a promise problem is in **P** of promise problems, your algorithm do not need to check whether the input is valid or not and your algorithm can behave arbitrarily if the input is invalid.

For an in-depth educational survey on promise problems, you are encouraged to read Oded Goldreich's exposition *On Promise Problems*, July 11, 2005.

However, if you want to show a promise problem is in **P**, your algorithm must check whether the input is valid or not and, if the input is invalid, a.k.a as a noninstance, output 0. Here **P** stands for the complexity class as in the famous **P** versus **NP** problem, a.k.a. **P** of decision problems, i.e. **PTIME** or **DTIME**$(n^{O(1)})$ as defined at Wikipedia, or the complexity class **P** as defined in section 34.1 *Polynomial time* of the popular textbook *introduction to algorithm* by CLRS, version 3.

Take 3SAT for an example. An algorithm that show 3SAT is in **P** (of decision problems) should check whether the input is a formula in conjunctive normal form each of whose clauses contains at most three literals among other restrictions. The algorithm should output 0 if it finds the input is not a valid instance of 3SAT.

It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.

I would recommend beginners to write clearly this verification step for the first few occasions before joining the common practice.
> 7 votes

# Answer
The answer depends on exactly what problem you're solving.

* If your goal is to produce an algorithm that correctly solves the problem on the restricted instances, then it's kind of up to you whether or not you check. It feels more robust to check the input but it's perfectly reasonable not to, and that puts you in the realm of promise problems. Here, the "user" promises that the input is valid, and you just have to determine whether the answer is yes or no.
* If your goal is to produce an algorithm that decides whether the input is, e.g., a satisfiable 3CNF then, yes, you do need to check that the input has the properties it's supposed to have.

Your example of 3-colourability for acyclic graphs shows that there can be a big difference between the two approaches. Every acyclic graph is 3-colourable (even 2-colourable) so the algorithm for the promise problem is just `output "yes"`. For the non-promise version, you need to check that your input is a valid graph representation, then check that the graph is acyclic, and only say "yes" if the input passes both tests.

In practical terms, most descriptions of graph algorithms tend to assume that the input is a valid encoding of a graph – it gets a bit tedious writing "Check the input is a valid encoding of a graph" as the first line of every algorithm!
> 4 votes

---
Tags: turing-machines, time-complexity, terminology
---


# Question
Title: What are the k-collections described in ch. 8 of "An Introduction to the Analysis of Algorithms" by Sedgewick
In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425.

My confusion is how to identify the k-collections. A k-collection is defined as: "*to be a word that consists of k different letters with the last letter in the word being the only time that letter occurs*"

Exercise 8.6 of the book asks to find all the 2-collections and 3-collections in Table 8.1, where that table shows the configurations of 4 balls in 3 urns

If I give it a try, I'd say a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end, but I'm pretty sure I"m wrong.

Can anybody help providing an example of a k-collection (2 or 3-collection) from Table 8.1? Thanks

# Answer
> 1 votes
I cannot figure out why you were "pretty sure" you were wrong, because you have given a correct example, "a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end".

Here are 2-collections.
1112, 1113, 2221, 2223, 3331, 3332.

Here are 3-collections.
1123, 1132, 1213, 1223, 1312, 1332,
2113, 2123, 2213, 2231, 2321, 2331,
3112, 3132, 3221, 3231, 3312, 3321.

There is a natural way for you to check whether your understanding is correct without any extra effort, assuming you are required or scheduled to read that section "coupon collector problem" in the book. What you could have done is to try to understand that section as much as possible, assuming whatever interpretation your could have. If you find some inconsistency, then your interpretation is probably wrong. Otherwise, your interpretation is probably correct.

For example, I also doubted my understanding of that definition of $k$-collection.

However, when I have read "if each box of a product contains one of a set of $M$ coupons, how many boxes must one buy, on the average, before getting all the coupons? This value is equivalent to the expected number of balls thrown until all urns have at least one ball or the expected number of keys added until all the chains in a hash table built by Program 9.1 have at least one key", I am confident that I got it correctly. I can imagine each letter in an $M$-collection is a box containing a coupon, where different letters mean different coupons. A ordered collection of letters is an ordered buying sequence of boxes containing coupons. So an $M$-collection means a buying sequence that gets all $M$ coupons right at its last buy. Ditto for chains in a hash table. The more I read, the more confident I become.

---
Tags: algorithm-analysis, hashing
---


title: what is meant by support of a filter?

text:
# Question
Title: what is meant by support of a filter?
what is meant by support of a filter in context of image processing? In the attached link of a short tutorial for detecting bar in an image by gabor filter,it is said that γ=1 helps in finding the support of the filter. link

# Answer
> 3 votes
Many filters, particularly linear time-invariant ones, are represented by a kernel function. The output of a filter at a point is calculated by a weighted average of all the points of the input where the weights are specified by the kernel function. The kernel function takes displacements from the current output point we're calculating to other points, so it is always relative to the output point.

The support of a filter is then, intuitively, the "size" of the kernel. Any displacement for which the kernel function is $0$ means that we don't have to consider the corresponding point at all when calculating the value of an output point. Therefore, the most strict definition of support is that it is the set of displacements where the kernel function is non-zero. This could be a quite complicated set in general, and so isn't particularly helpful for understanding or calculation. A looser definition would be the support is any set (of displacements) which *contains* all the displacements where the kernel function is non-zero. This allows us to conservatively approximate the support with some simple-to-describe shape. This will usually be something like an ellipse or rectangle or square (or their lower-/higher-dimensional analogues). Given such a class of approximate shapes, the support will usually be taken to be the smallest approximate shape which contains all the displacements for which the kernel function is non-zero.

For that page, the support is the smallest ellipse which contains all the non-zero inputs of the kernel function. For discrete kernels that are typically used to implement these filters on a computer, usually a rectangular support is used. This allows calculating the weighted average by iterating only over the points in a (typically much smaller) sub-rectangle of the input, rather than iterating over the entire input while multiplying most values with zero. It also means the kernel function can be described by only specifying its values for that rectangle, and this is usually represented by a matrix called the mask in the 2D case.

---
Tags: image-processing, filtering-problem
---


# Question
Title: Constructing a minimum spanning tree from an all-shortest path graph?
Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D\_{ij}$. Furthermore, the distance matrix $D$ is computed for a connected network $T$ of $n$ nodes and $n-1$ edges - i.e. the shortest path distance between two nodes in $T$.

About the network $T$:

* There are exactly $n$ nodes and $n-1$ edges.
* The network is *one* connected component, thus it is a tree.
* All edges have positive length.

My problem is that if I compute a *minimum spanning tree* $T'$ of $G(D)$ using, for instance, *Kruskal's algorithm* will the resulting tree $T'= T$?

* I tried to argue that they are indeed equal, because if we consider an edge $e$ has been added in a step of *Kruskal's algorithm* then this edge must have been a **light edge** thus it is also the shortest path distance.

I am not sure if this argument holds. How can I argue that $T' = T$?

# Answer
> 2 votes
> If we consider an edge $e$ has been added in a step of Kruskal's algorithm then this edge must have been a **light** edge thus it is also the shortest path distance.

You are almost there. Let me continue your approach.

Suppose edge $(u,v)\not\in T$. Let $P=(u\_0=u, u\_1, \cdots, u\_k=v)$ be the unique path from $u$ to $v$ in $T$ where $k\gt1$. For each edge $(u\_i, u\_{i+1})$, $d\_{u\_iu\_{i+1}}=w((u\_i, u\_{i+1}))\lt \sum\_{0\le j\le k-1} w((u\_j, u\_{j+1}))= d\_{uv}$, where $w$ is the weight/length function on edges of $T$.

Consider $t\_0$, the point of time when edge $(u,v)$ had been determined to be part of $T'$ but had not been added to $T'$ yet by Kruskal's algorithm. At time $t\_0$, for all $0\le i\le k-1$, $(u\_i, u\_{i+1})$, an edge that is shorter than $(u,v)$ must have been tried, which meant node $u\_i$ and $u\_{i+1}$ must have been connected by a path in $K(t\_0)$, the edges of $G(D)$ that had been determined to be part of $T'$ at time $t\_0$. That means before $t\_0$, node $u$ and $v$ had been connected by a path in $K(t\_0)$, which implies that edge $(u,v)$ would not be added by Kruskal's algorithm.

The paragraph above shows that all edges of $T'$ must be in $T$. Since the number of edges in each one of them is $n-1$, $T=T'$.

---

Here is a direct generalization as an exercise.

**Exercise.** Suppose the connected network $T$ is a connected network (the number of whose edges should be no less than $n-1)$ with a positive distance between each adjacent nodes. The rest of the setup is the same as in the question. Show that a minimum spanning tree $T'$ of $G(D)$ is also a minimum spanning tree of $T$.

---
Tags: graphs, shortest-path, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Does increasing k in a k-way set-associative cache always lead to a better miss rate?
As far as I know a 2-way set-associative cache works better than a one-way one considerably but going to 4 and 8-way caches leads to a marginal improvement. My question is: does increasing K (going more than 8) lead to better miss rate although marginal?

# Answer
My original answer was incorrect; see https://cs.stackexchange.com/a/105695/755 or https://cs.stackexchange.com/a/105719/755 for correct answers.
> 0 votes

# Answer
It's not guaranteed; it may depend on the data. Let's say an 8-way associative cache can hold 8 items at position 512k + j for each fixed j, and a 4-way associative cache can hold 4 items at position 1024k + j. My algorithm accesses locations 1024k + 512 + j for just four values k all over again. And locations 1024k + j for lots of values k, so there is basically no cache reuse.

In this case, 4-way associative caches has lots of hits and 8-way almost none. (There may be some mistake made somewhere, but you should figure out a pattern where 4-way ends up better).

For random access patterns, and for not carefully constructed patterns, higher associativity will be better. There is of course the problem that picking one out of 8 sets will take more time than picking one out of 2 or out of 4 sets.
> 3 votes

# Answer
I failed to understand @gnasher729 explanation, so this is my one demonstrating the same situation.

Let's consider just one line of 8-way cache, and compare it to two corresponding lines (A and B) of 4-way cache. Imagine the situation when we access 4 different addresses of line A, then 5 addresses of line B, repeating that in loop. So, hit:miss ratio for 4-way LRU cache will be 4:5. But in 8-way cache these 9 addresses will go to the same line, leading to 0% hit ratio.
> 2 votes

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


# Question
Title: An algorithm to maximize the number of parallel tasks
I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed.

The problem can be represented as a directed acyclic graph:

The current scheduler ensures correctness, and capable of culling unneeded tasks such as **k** in the previous graph (assuming the end goal is **i**).

I am struggling to find another equivalent algorithm to maximize number of tasks running in parallel (tasks on the same line may be executed in any order):

```
a, b, j
c
d
e, f, h, g
i

```

Flatten form, what is between `()` may be in any order and represent parallel tasks:

```
  (a, b, j), (c), (d), (e, f, h, g), (i)

```

The idea here I want to fill the compute engine with as much work as possible.

# Answer
From your initial DAG $G(E, V)$ You start reversing all edges to build a new DAG $G'(E, V')$. Then do a BFS from $i$ in $G'$ to remove any unneeded tasks (unreached nodes in the BFS). This step is $O(N)$ with $N = |V'|$, the number of edges.

From $G$, build the number of requirements of each task ($R(V)$) and at the same time the list $L$ of the tasks with no requirements. this takes $O(N)$.

Then you iterate on this pseudo-algorithm:

```
while(root is not executed)
    L' = empty list
    for v in L
        for each node v' with an edge in G' from v to v'
             R(v') -= 1
             if R(v') == O then add v' to L'
    execute all L in a parrallel step
    L = L'

```

this is $O(N)$.
> 1 votes

---
Tags: graphs
---


title: Virtual address translation

text:
# Question
Title: Virtual address translation
I'm in an OS class now. I've been wrestling this problem for a while and can't convince myself of a solution. My professor is very busy and hasn't made time to help. Also, **this question is from an example exam, not something I would be graded on.**

In this question, we're given a virtual address to translate: **0xFEC**. We're also told to use segmentation in accordance with the table and a 14-bit address. Looking at our address in binary, we have **0000 1111 1110 1100**. We'll disregard the two most significant bits, as instructed giving **00 1111 1110 1100**.

Taking the two leading bits as our segment tells us to use the base for the Code section, which is given to be 12. Then, we go to decimal and add.

**dec(00 1111 1110 1100) + dec(12K) = ...**

**7018 + 12,288 = 19306**

The thing that tells me this is incorrect, is that the number 7018 which is approximately 7K is much greater than 3.6K (the given size of the code section). :/

I'm really lost here, and I haven't found any examples of people moving addresses with segmentation or with decimal end numbers.

I think I'm wrong when interpreting the addition, but I'm not sure how.

# Answer
> 1 votes
I suspect that the problem may lie in your title.

There's a whole lot of real-world variety imaginable in memory architectures, and your book will describe them in the abstract. Importantly, in the real world the particular combination of segmentation and virtual addresses is not used. Intel's x86 architecture supports it, but most Operating Systems don't bother and just set all segments to be identical.

This question therefore does assume something non-standard, which means there needs to be some specification of how the hypothetical mechanism works. Importantly, does segmentation happen before or after virtual address translation?

In the model where segmentation checks happen first, 0x0FEC is *not* in the code segment. The top bits suggest it is, but the code segment is only 3686 bytes, not 4077 bytes.

Since the virtual address does not lie in *any* segment, using it would fail even before a virtual-to-physical translation happens.

Now in the model where segment bounds are checked later, you'd first create a physical address, which would use the 12K base address and the 4076 offset. This produces an physical address of almost 16K, past the 15.6K end of the code segment.

---
Tags: virtual-memory
---


# Question
Title: How do I prove that SPACE($n^{555}$) $\neq$ NP?
I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.

# Answer
According to the space hierarchy theorem, there is a language in $\mathrm{SPACE}(n^{556})$ which is not in $\mathsf{SPACE}(n^{555})$. A padded version of this language will be in $\mathsf{SPACE}(n^{555})$. If the latter is equal to $\mathsf{NP}$, then the original language would also be in $\mathsf{NP} = \mathsf{SPACE}(n^{555})$, since we can implement padding while remaining inside $\mathsf{NP}$.

I'll let you flesh out this argument.
> 4 votes

---
Tags: complexity-theory, space-complexity
---


title: Maximum subarray of bounded length

text:
# Question
Title: Maximum subarray of bounded length
I'm giving an array $A\[0..n-1\]$ and an integer $w$. The goal is to find indices $i,j$ that maximize

$$\Phi(i,j) = A\[i\] + A\[i+1\] + \dots + A\[j-1\],$$

subject to the requirements that $0 \le i \le j \le n$ and $j \le i+w$. Or, in other words, I want to find the sequential window of width at most $w$ such that the sum of the numbers in the window is maximized.

Is there an $O(n)$ time algorithm for this task? Or, what is the most efficient algorithm for this task?

There is a trivial $O(nw)$ time algorithm, but I can't see how to do better than that. If $w=\infty$, Kadane's algorithm solves this in $O(n)$ time, but I can't see how to generalize it to my problem. So, can we do better than $O(nw)$ time?

I encountered this problem in the context of an image processing task I'm facing.

# Answer
> 5 votes
The problem you are describing can be solved in $O(n)$.

Let's define the prefix sum as: $$\text{psum}\[i\] = \sum\_{0 \le j \le i} A\[j\]$$ Then your function can be expressed as: $$\Phi(i, j) = \text{psum}\[j-1\] - \text{psum}\[i-1\]$$

Assuming we fix the right boundary $j-1$ (we want to find the window of size at most $w$ ending at $j-1$ with the maximal sum). It should be easy to see, that this window has the sum: $$\text{psum}\[j-1\] - \min\_{i \ge j - w}\left\\{\text{psum}\[i-1\]\right\\}$$

For the actuall implementation we use a data structure called **Minimum Queue**. It is a queue (FIFO) that does the normal push/pop operations in **amortized constant time** and it additionally supports extracting the minimum of its current stored elements in **constant time**.

With it we can find the maximal window in linear time:

```
best = 0
initialize min_queue
min_queue.push(psum[-1])  # psum[-1] can be defined as 0
for j = 1 to n:
    if len(min_queue) > w:
        min_queue.pop()
    cur = psum[j-1] - min_queue.min()
    best = max(best, cur)
    min_queue.push(psum[j-1])

```

One way of implementing a Minimum Queue is to store the elements in a dequeue using value-index pairs. And you keep this queue in non-decreasing order, i.e. you only store the subset of pairs that are or can become the minimum at some point and ignore the remaining elements. This means whenever you push a new element, you remove all previous elements that are bigger from the back of the queue, since the currently added element will dominate them at all times. Therefore the minimum will always be the first element.

This approach, and also two (similar) alternatives are described on cp-algorithms.com.

---
Tags: algorithms, arrays, maximum-subarray
---


# Question
Title: Efficient data structure for storing integers in a range?
Say I'm constantly given integers from the range $\[1,2^{32}\]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ values will have been treated.

What's the best way to store which integers have been treated so far so that we can search if the current integer is a duplicate?

# Answer
> 6 votes
Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's no possible way to store all the information you need with fewer bits than this.

So I recommend **a straightforward bitmap**. In other words, a simple array of bits. When a new value comes in, see if the corresponding bit is on or not; if it's off, flip it on. This takes the minimum possible amount of space, and is extremely fast (since all you have to do is index into an array).

P.S. You need $2^{32}$ bits specifically because the numbers could appear in any order. This means that there are $2^{2^{32}}$ possible states the program could be in, one for every possible combination of seen and not-seen values. Representing this many states will always take at least $2^{32}$ bits. If you knew the numbers would always come in increasing order, on the other hand, there'd only be $2^{32}$ states to distinguish between (since all you care about is the highest value seen so far), so you'd need a minimum of $32$ bits.

# Answer
> 1 votes
If the integers truly arrive in random order, then a bit array is a good (likely ideal) solution, and would require 512MB.

In the real world, information may be unpredictable, but not random, so a number of data structures optimized for sparse information (including sparse missing information) could be more appropriate if memory usage is a concern. For example, a binary tree of run-length encodings.

Assuming that the integers do not arrive in a truly random order, then the more you know about the pattern, the more potential optimizations will be available to you.

---
Tags: data-structures, search-algorithms, integers
---


title: Generating intermediate code

text:
# Question
Title: Generating intermediate code
I have a problem in backpatching "if-else" statements, for generating 3 address codes.

The grammar rule is :

```
  S -》 if E then M1 S1 N else M2 S2

```

The semantic rules are : {

```
 backpatch(E.truelist, M1.quad)
 backpatch(E.falselist, M2.quad)
 S.nextlist = merge(S1.nextlist, N.nextlist,
 S2.nextlist)

```

}

Explanation :

```
  Merge(p1, p2) : concatinates lists pointed by p1 and p2)

  Backpatch(p, i) : inserts i as the target label for each of the statements in the list pointed to by p)

  S.nextlist : "goto" statements to the next instruction after this statement (s)

```

I don't understand why we need "N" in the semantic rules above. Why should we merge N.nextlist along with S1 and S2 nextlists for getting S.nextlist?? I mean why there is "N.nextlist" among other inputs? Tnx for answering, in advance :D

# Answer
> 1 votes
Normal assembly for if/then/else looks like:

```
JMP_FALSE <condexpr> elselabel
<thenstmt>
JMP endlabel
elselabel:
<elsestmt>
endlabel:

```

(You can substitute mnemonics as appropriate for your instruction set.)

This "backpatch" term is probably something specific to some specific code that your professor wrote, or the author of the textbook that you're using. In either case, it's not a promising term.

The "truelist" and "falselist" likely refer to definite assignment (and definite unassignment) tracking; most modern languages keep track of what variables (aka registers) have been definitely assigned (for at-least-once purposes) and some, like Java, keep track of what variables are definitely unassigned (for at-most-once purposes, like Java "final"). Having implemented this a few times, I've used both a non-sparse (custom bit array/set) and a sparse data structure for tracking assignment impact within a scope; in Java, the language is simple enough that register assignment can occur before definite assignment analysis, so the bit array works beautifully (since you can know the zero-based register numbers and use them as the bit indexes).

The "N" probably refers to the unconditional jump to end of if/then/else statement. Again, it's not a promising term, since it implies a number, and IR/assembly should never be dealing with a number when a label will do.

The "quad" term is another made-up term specific to whomever wrote the material that you are working from.

Also: s/them/then

---
Tags: compilers
---


title: What is von Neumann bottleneck?

text:
# Question
Title: What is von Neumann bottleneck?
According to this Quora post,

> It refers to two things: A systems bottleneck, in that the bandwidth between Central Processing Units and Random-Access Memory is much lower than the speed at which a typical CPU can process data internally. The 'intellectual bottleneck' in that programmers at the time spent a lot of time thinking about code optimisation to stop 'lots of words' being pushed back and forth between CPU and RAM.

But according to my class lecture, it is the problem that "Generic implementation of single, common instruction and data hierarchy makes it impossible to access data and instructions at the same time. This is traditionally called von Neumann bottleneck."

Which one is correct?

# Answer
Both are correct, though I'd say the first one more so.

A *von Neumann architecture* means the program is stored in memory along with everything else, rather than being a separate unit attached to the processor. This means that anything the computer tries to do, no matter what it might be, is bottlenecked by the connection between the processor and memory.

So "getting data from memory is slower than processing it" is a valid description, as is "you need to fetch instructions and you need to fetch data and both of those are slow". But the most important part is that fetching from memory is extremely slow compared to anything else the processor might be doing.
> 1 votes

# Answer
As languages were evolving, more and more of the produced code was having to follow indirections (pointer de-referencing), which meant that each pointer itself had to first be fetched, and then the value at in that pointer (an address) referenced another piece of data that had to be fetched. Quite often, that value, too, would end up being a pointer.

Changes to these data structures required maintaining those pointers, which itself was a tremendous load both on the programmer (using an imperative language) and on the machine.

At the time that John Backus gave his Turing Award acceptance speech on this topic, the languages of the day largely forced the developer to manage all of this entropy by hand. John Backus envisioned functional programming languages that would avoid this complexity.

In general, dealing with global, mutable state is a high-entropy experience. That is the von Neumann model. That is the assembly model. That is the C model. That is even still the Java and C# model.

I'm not sure that John Backus was terribly concerned about the machine itself having to do so much work; I think that he was more worried about the cognitive load.

See: https://www.scribd.com/document/357197929/John-Backus-Turing-Award-Lecture
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Can this system of polynomial equations be solved in polynomial time?
I have these **$n$ equations**, with **$n$ variables**. Variables are **first $n$ positive integers**, constants can be any rational number including zero. **Given that there is always a solution**, how do we find a solution to the system:

\begin{align} ax^{1}+by^{1}+cz^{1}+\cdots&=k\_{1}\\ ax^{2}+by^{2}+cz^{2}+\cdots&=k\_{2}\\ ax^{3}+by^{3}+cz^{3}+\cdots&=k\_{3} \end{align}
so on ... till $$ax^{n}+by^{n}+cz^{n}+\cdots=k\_{n}$$

for variables $x,y,z\in \\{1,2\ldots, n\\}$.

The value of constants $a$,$b$,$c$... remain same in all these equations.

And these constants can also be equal to each other. For e.g: $a = b$ so that values of $x$ and $y$ can become interchangeable. In such cases one working solution is suffice.

Can we find a solution or determine none exist in polynomial time?

---

**Edit: For the sake of clarity here is a simple example.**

If $n=3$, I know $x,y,z$ can only take 1, 2 or 3 as their values. So if I have $x + y + z = 9$, I clearly know that $x, y$ and $z$ are all 3. But if I have $x + y + z = 6$, I don't know whether they are $2,2,2$ or $1,2,3$. Then I can make use of $x^2 + y^2 + z^2 = 14$. Then I will know they are $1,2,3$.

# Answer
Let us denote the unknowns by $x\_1,\ldots,x\_n$, and the coefficients by $c\_1,\ldots,c\_n$. For a polynomial $P(x)$, we denote $$ \[P(x)\] = \sum\_{i=1}^n c\_i P(x\_i). $$ We are given the values of $\[1\],\[x\],\ldots,\[x^n\]$, from which we can calculate $\[P(x)\]$ for every polynomial of degree at most $n$. In particular, we can compute, for each $j \in \\{1,\ldots,n\\}$, the value $$ \left\[ \prod\_{k \neq j} \frac{x-k}{j-k} \right\] = \sum\_{i\colon x\_i=j} c\_i. $$ To complete the solution, we need to solve several SUBSET-SUM instances, which possibly interact.

Conversely, we can *encode* SUBSET-SUM using your equations. Given a set of positive coefficients $c\_1,\ldots,c\_n$ summing to $C$ and a target $S$, we encode a solution using $\\{1,2\\}$-valued variables (where $1$ represents a value in the subset summing to $S$), and can compute $\[x^k\] = S + (C-S)2^k$. These numbers satisfy $$ \[x^k(x-1)(x-2)\] = \[x^{k+2}-3x^{k+1}+2x^k\] = \\ (S + (C-S)2^{k+2}) - 3(S+(C-S)2^{k+1}) + 2(S+(C-S)2^k) = \\ (1-3+2)S + (4-6+2)(C-S)2^k = 0. $$ Therefore the argument above shows that every $\\{1,\ldots,n\\}$-valued solution is actually $\\{1,2\\}$-valued. Therefore a solution to your problem exists if and only if the SUBSET-SUM instance is a Yes instance.

When all coefficients $c\_i$ are equal, the argument above allows us to calculate directly the number of $x\_i$'s equal to $j$. Let us take your example: $\[1\] = 3$, $\[x\] = 6$ and $\[x^2\] = 14$. Denoting by $y\_j$ the number of $x\_i$'s equal to $j$, we compute $$ \begin{align\*} y\_1 &= \left\[ \frac{(x-2)(x-3)}{(1-2)(1-3)} \right\] = \frac{\[x^2-5x+6\]}{2} = \frac{14-5\cdot6+6\cdot3}{2} = 1, \\ y\_2 &= \left\[ \frac{(x-1)(x-3)}{(2-1)(2-3)} \right\] = \[-x^2+4x-3\] = -14+4\cdot6-3\cdot3 = 1, \\ y\_3 &= \left\[ \frac{(x-1)(x-2)}{(3-1)(3-2)} \right\] = \frac{\[x^2-3x+2\]}{2} = \frac{14-3\cdot6+2\cdot3}{2} = 1. \end{align\*} $$
> 3 votes

# Answer
My algorithm is not an exact one but actually an approximation algorithm.

**Algorithm**

1. Define three matrices

$$ X = \left\[ \begin{matrix} x & y & z & \cdots \\ x^2 & y^2 & z^2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ x^n & y^n & z^n & \cdots \end{matrix} \right\]\_{n \times n} $$

$$ C = \left\[ \begin{matrix} a \\ b \\ c \\ \vdots \end{matrix} \right\]\_{ n \times 1} $$

$$ K = \left\[ \begin{matrix} k\_1 \\ k\_2 \\ k\_3 \\ \vdots \end{matrix} \right\]\_{ n \times 1} $$

We can see that $X \cdot C = K$

2. Find the Inverse Matrix for C. (Yes, inverse of a column matrix) $$ C^{-1} = \frac{C^T}{C\_{sq}} \\ C\_{sq} = \sum\_{i=1}^n c\_i^2 = a^2 + b^2 + c^2 + \cdots $$

$C^{-1}$ satisfies all properties that a normal matrix inverse does $$ C^{-1} \cdot C = I\_{1 \times 1} \\ C \cdot C^{-1} \cdot C = C $$

3. Now comes the tricky part. Calculate $C^\* = C \cdot C^{-1}$. We can now use this to obtain

$$ X \cdot C \cdot C^{-1} = K \cdot C^{-1} \\ X \cdot C^\* = K \cdot C^{-1} \\ X = K \cdot C^{-1} \cdot C^{\*{-1}} $$

The tricky part is that $C^\*$ is always singular i.e. $|C^\*| = 0$. So it does not have a unique inverse, but has many pseudo-inverses. (Refer: Moore-Penrose Inverse ).

So we have to keep searching for all pseudo-inverses of $C^\*$ i.e. $C^{\*{-1}}$ such that the result $K \cdot C^{-1} \cdot C^{\*{-1}}$ we obtain, matches the pattern observed in $X$.
> -1 votes

---
Tags: algorithms, time-complexity, linear-algebra, mathematical-programming
---


# Question
Title: Reduction to a vertex cover problem-like with weighted vertices and edges
### Description

Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas:

* $G$ is an undirected graph
* $K \le |V|$
* $L \> 0$ is the maximum limit
* Each vertex $v \in V$ has a weight $W(v)$
* Each edge $e \in E$ has a length $W(e)$

Let $P(v)$ be a function that returns the minimum length of a path (basically shortest path) from vertex $v$ to a vertex in $V'$.

The decision question is whether there exists a vertex set $V' \subseteq V, |V'| \le K$, such that:

$$ \sum\_{v \in V} W(v) \cdot P(v) \le L $$

### Example

Consider the following graph $G$, with $K = 1$ and $L = 9$:

Taking the set $\\{v\_3\\}$ as $V'$ would be the solution to the question, because the total cost is:

$$ 3 \cdot 0 + 2 \cdot 2 + 1 \cdot 5 = 9 $$

Therefore, this is a yes-instance.

### Question

How do I prove that this problem is in $\mathsf{NPC}$? I tried reducing a $\text{VC}$-instance to this, but that does not seem to work.

What I have tried as well is by converting the above undirected graph to a directed graph with the weighted paths already computed (this is polynomial computable):

$$ \begin{array}{l|l|l} & v\_1 & v\_2 & v\_3 \\ \hline v\_1 & 0 & 3 & 5 \\ \hline v\_2 & 6 & 0 & 4 \\ \hline v\_3 & 15 & 6 & 0 \end{array} $$

However, I'm not entirely sure what $\mathsf{NPC}$ problem to reduce from. I got the tip to use the $\text{CLIQUE}$ problem from this answer, but I do not see how to perform the reduction, so that seems unlikely. To me, this looks more like something that can be reduced from the $\text{KNAPSACK}$-problem or the $\text{SET COVER}$-problem, using the weights from the transformed directed graph, but I fail to see how exactly to this. I am starting to think that the transformed directed graph is of no use here.

What $\mathsf{NPC}$-problem can I use for the reduction?

# Answer
> 1 votes
This problem is a generalization of Dominating Set, and if you let weights of vertices and edges be 1, then you have exactly Dominating Set.

The problem definition of Dominating Set is:

> Given a graph $G = (V, E)$ and an integer $k$, is there a set $V' \subseteq V$ of size at most $k$ such that the distance of any vertex $v \in V \setminus V'$ to $V'$ is 1.

(This is assuming that the distance from $v' \in V'$ to $V'$ is defined as 0.)

It follows that WVE is NP-hard. This is occasionally called *proof by generalization.*

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


# Question
Title: Implementation-level of a Turing machine that accepts a specific language
I'm trying to figure out a way to implement this kind of a Turing machine that accept the following language:

$$\Sigma = \\{ 0,1,2 \\}, \quad\quad L(A) = \\{ abc \mid a=b \land c = a^R \\}$$

I was thinking of a 3-tape Turing machine or using $\\#$ symbol that separates the $a$, $b$ and $c$, but I'm struggling for the $c$ part.

I only need Implementation-level or the way it works.

# Answer
I will use two tapes with deterministic Turing Machine.

Say you have $123321233223321B$ on first tape as input, where B is blank symbol.

At first use three states counter and add some symbol to the second tape, say # every third symbol. Check whether input is divisible by 3 (otherwise reject).

After first iteration you have:
$123321233223321B$
$#####$

Here you do not reject, as it is divisible by 3.
Now move elements from first tape to second one. After this step you have:
$1233223321$
$12332$

Compare elements from second tape with first one (deleting from first one). After that step you have:
$23321$
$12332$

Place head on first tape at the beggining and head of second tape at the end. Compare char by char moving in oposite directions (erasing symbols). If anywhere during comparison there was a mismatch then reject, otherwise accept (if this is required leave something in the first tape at that point).
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval
Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a \[min, max\] pair?

The naive approach is very straightforward, but has O(intervals) test performance:

```
list intervals (min, max)

func testVal(val){
  foreach (interval(min, max) in intervals)
    if (val > max) || (val < min) return false
  return true
}

```

In the problem I'm facing the list is not updated frequently, but it is tested against with very high frequency.

Thus, it's acceptable for updating the list to be expensive, but tests need to be sublinear, ideally constant time.

One option is to insert every value in the intervals into a hashtable, but this is memory-intensive and not practical when the intervals get large. Memory usage needs to be proportional to the number of intervals, not the sum of the sizes of the intervals (probably ok to have a log(n) memory usage term thrown in if it greatly aids performance).

I've started poking around with various tree-based options to make this better, but it feels like a general enough problem that I suspect there is preexisting work I should be referencing. Are there any existing solutions to get sublinear tests (ideally constant time) on a list of intervals by preprocessing them into some other datastructure(s)?

# Answer
Here's my thought process on this problem:

* If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order.
    + Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes.
* For a given point and a given interval, you can determine whether the point is "outside to the left", "inside", or "outside to the right" in $O(1)$.
    + This assumption only works as long as you have a fixed word length, but that's generally true for all practical purposes.
    + Let's change the terms: "outside to the left" is "less than", "inside" is "equal to", and "outside to the right" is "greater than".
* Now you can use standard binary search!
    + Since each comparison is $O(1)$, the total time is $O(\log n)$.

And voilà, each check takes only logarithmic time! Setting up the list in the first place takes $O(n \log n)$, and adding a new interval to the list later takes $O(n)$ in the worst case.
> 1 votes

# Answer
You need an interval tree, which queries in O (logn + m) time, where $m$ is the number of intervals the point hits (as opposed to O (n) for n intervals in the data structure).

This should produce enough savings that you'll hardly notice the cost of $m$.

This output sensitive algorithm is likely the best you can do. The other answer suggests this structure without name, with the additional step of making all intervals disjoint to get log$n$ ($m$ guaranteed to be 1) That's fine, but I'd still use an established data structure.
> 1 votes

---
Tags: algorithms, data-structures, intervals, lists
---


title: What is a search problem?

text:
# Question
Title: What is a search problem?
I'm looking for a formal and broad definition.

Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a problem requires multiple checks?

Alternatively, I also think intuitively of problems with multiple paths as a search problem. In this case, only a single check might be necessary but multiple comparisons are needed in order to know which path is the best to follow.

# Answer
> 4 votes
A problem is a *search problem* if there's an algorithmic way to verify the answer. In particular, let $V$ be any algorithm that takes two inputs and always terminates. Then the following is a search problem:

*Input:* $x$
*Goal:* find and output any $y$ such that $V(x,y)=1$, or report that no such $y$ exists

Every search problem can be written in this form. In particular, you can take the above as the definition of a search problem: a problem is a search problem if there exists an always-terminating algorithm $V$ that has the above form.

---
Tags: search-algorithms, search
---


# Question
Title: Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?
We see that there is a sign, exponent, and mantissa part for the notation. But, there is no location for the significant bit.

Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?

# Answer
> 1 votes
There are two tricks used here.

The first trick is to realise that any number can be expressed with a single whole digit and a fractional part by modifying the exponent.

eg:

```
  = 435.32 * 10^3
  = 43.532 * 10^4
  = 4.3532 * 10^5

  = 0.00453 * 10^1
  =  0.0453 * 10^0
  =   0.453 * 10^-1
  =    4.53 * 10^-2

```

The second trick is to notice that this single whole digit is never zero. So when the number is expressed in binary `(0, 1)` that digit must always be `1`.

Therefore if we mandate that the number is stored in binary, and the exponent is always adjusted to express the number as a single whole digit and a fractional part, the whole digit can be optimised away as it never varies. This leaves just the sign, exponent, and fractional parts of the number to encode.

That being said (as pointed out in the comments), the IEEE754 standard does include "denormalised" numbers which as you might guess do not have a leading implied 1, but are instead lead by an implied 0.

These numbers have the smallest possible exponent making these values truly tiny. The point of presuming a zero here is to allow the storage of even smaller values than could have otherwise been expressed.

Essentially it is a compromise, by altering the rule for the smallest possible exponent a series of even smaller numbers with reducing precision can be stored. The cost for this is that numbers at the 2^smallest-exponent cannot be accurately stored.

---
Tags: floating-point, number-formats, binary
---


title: What makes PROLOG Turing-complete?

text:
# Question
Title: What makes PROLOG Turing-complete?
I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this:

```
turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

```

Source

However, I’m wondering which parts of the PROLOG language one could strip away (esp. function symbols, clause overloading, recursion, unification) without losing Turing completeness. Are function symbols themselves Turing complete?

# Answer
It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you *certainly* have Turing-completeness!)

Let's assume for the moment that you've already stripped arithmetic. We'll also assume that you don't have any non-logical features like `atom_chars`, `assert`, and so on, which enable general shenanigans.

If you stripped out function symbols, you can't construct answers or intermediates of unrestricted size; you can only use atoms which appear in the program and the query. As a result, the set of all possible solutions to any query is *finite*, so taking the least fixed point of the program/query will always terminate. Datalog (a relational database query language based on Prolog) works on this principle.

Similarly, if you restricted Prolog to primitive recursion only (that includes no recursion as a degenerate case), then the amount of recursion that you can do is bounded by the size of the query, so all computation terminates. So you need general recursion for Turing-completeness.

And, of course, if you have general recursion, you can cut a whole bunch of features and retain Turing-completeness, including general unification (construction and top-level pattern matching is sufficient), negation, and the cut.
> 24 votes

# Answer
Completing the excellent answer by @Pseudonym and referring to your last question "Are function symbols themselves Turing complete?".

You probably mean: Can a language made only of function symbols be Turing-Complete?

The answer is yes - think of Functional Programming languages like ML and Haskell.
> 1 votes

---
Tags: programming-languages, turing-completeness, logic-programming, prolog
---


title: Polynomial Time reducible explanation

text:
# Question
Title: Polynomial Time reducible explanation
Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct?

> If set $Y$ can be solved in $O(2^n)$ and $Y \leq\_p X$ then $X \not\in P$ is false

I think this means that since $Y$ is *not* polynomial time solvable, and it is reducible to $X$, then X is not polynomial time reducible. This makes sense to me, but the statement ends with a false, how is that?

> If $Y \leq\_p X$ and $X$ is solvable in constant time, then $Y$ is solvable in constant time as well

Seems pretty intuitive, if you can reduce to $Y$ using a polynomial reducer, then it should also be solvable in constant time. But I have the nagging feeling that it wouldn't be constant time since polynomial time \> constant time.

> Say you have $SORT$ which checks if the list of ints is sorted, then for all $X$ we have $SORT \leq\_p X$

I don't get this at all, how can the $SORT$ algorithm be reducible to **all** $X$, isn't that a bit too farfetched?

> Assume $Y \leq\_p X$, if $Y$ doesn't have a polynomial time algorithm to solve it, then there isn't one for $X$ either

I think this implies that since $Y$ is not solvable in polynomial time then neither is $X$, but isn't that false? Isn't the whole purpose of us using reductions is to show that we can reduce one to another that already has a solution, thus translating the solution?

# Answer
> 1 votes
### What is polynomial-time reduction?

Let us recall the definition of polynomial-time reduction (function) as presented in section 34.3, *NP-completeness and reducibility* CLRS, third edition.

> Let $\Sigma=\\{0,1\\}$. A language $L\_1$ over $\Sigma$ is polynomial-time reducible to a language $L\_2$ over $\Sigma$, written $L\_1 \le\_p L\_2$, if there exists a polynomial-time computable function $$f: \\{0, 1\\}^\*\to\\{0,1\\}^\*$$ such that for all $x\in \\{0,1\\}^\*$, $$x\in L\_1\Longleftrightarrow f(x)\in L\_2.$$ We call the function $f$ the reduction (function), and a polynomial-time algorithm $F$ that computes $f$ is a reduction (algorithm).

### Examples

> \[FALSE\]$\ \ $ If set $Y$ can be solved in $O(2^n)$ and $Y \leq\_p X$ then $X \not\in \bf{P}$.

What is $O(2^n)$? It is not $\Omega(2^n)$! For example, a constant function is in $O(2^n)$. If set $Y$ can be solved in constant time and $Y \leq\_p X$ then $X$ can be in $\bf{P}$. For example, we can let $X=Y$.

> \[FALSE\]$\ \ $ If $Y\le\_p X$ and $X$ is solvable in constant time, then $Y$ is solvable in constant time as well.

You cannot ignore the time spent in the reduction step. $Y\le\_p X$ tells us that it takes no more than polynomial time to map (a.k.a. reduce) an instance (a.k.a a word) of $Y$ to an instance of $X$. That polynomial time, as you suspected, is significant.

In fact, the complexity class $\mathbf P$ can be defined as all $Y$s such that $Y\le\_p X$ for some $X$ that is solvable by constant time.

> \[ALMOST TRUE\]$\ \ $ Say you have $SORT$ which checks if the list of ints is sorted, then for all $X$ we have $SORT \leq\_p X.$

There is a polynomial-time computable function $f$ that maps a word in $\\{0,1\\}^\*$ that encodes a sorted list of ints to 1. Basically, we can use an algorithm that checks each int in the list is not greater than than the next int in the list. This algorithm is, in fact, linear-time.

Suppose word $x\_0\not\in X$ and $x\_1\in X$. Let $g$ be a function that maps 0 to $x\_0$ and 1 to $x\_1$. $g$ can be computed by a constant-time algorithm, since both $x\_0$ and $x\_1$ are fixed sequences of 0s and 1s. $g\odot f$ is a polynomial reduction from $SORT$ to $X$.

As long as $X$ is not the empty set nor the set of all words over $\Sigma$, $SORT \leq\_p X.$

If $X$ is empty set, there is no reduction of any kind. If $X$ is the set of all words, then any map to $X$ will map any instance, including a "no" instance to a "yes" instance of $X$. Because of these two exceptions, we can say the proposition is false.

> \[TRUE\]$\ \ $ Assume $Y \leq\_p X$, if $Y$ doesn't have a polynomial time algorithm to solve it, then there isn't one for $X$ either

$Y \leq\_p X$ implies
$\quad X$ is solvable in polynomial time $\Longrightarrow$ $Y$ is solvable in polynomial time.
Note that contrapositive of that implication is exactly
$\quad Y$ is not solvable in polynomial time $\Longrightarrow$ $X$ is not solvable in polynomial time.

### Exercises

Check whether the following propositions are true.

**Proposition 1.** If set $Y$ can be solved in $\Omega(2^n)$ and $Y \leq\_p X$ then $X \not\in \bf{P}$.

**Proposition 2.** If set $X$ can be solved in $O(2^n)$ and $Y \leq\_p X$ then $Y \not\in \bf{P}$.

**Proposition 3.** If set $X$ is solvable by polynomial time, then $\mathbf P$ can be defined as all $Y$s such that $Y\le\_p X$.

---
Tags: formal-languages, reductions, polynomial-time
---


# Question
Title: When is a root node an articulation point in a graph?
I am trying to find the articulation points in a connected undirected graph and I'm finding it difficult to figure out if the root node of the DFS is an articulation point.
Based on the literature I've read the root node is considered an articulation point if it has more than one child link1

My question is around the graph (0 - 1) (0 - 2) (1 - 2) (1 - 3) (2 - 4) (2 - 5)

When we the DFS rooted at 0 should 0 be considered an articulation point? it does have more than one child, however, the children are connected so removing 0 does not increase the number of connected component (doesn't cut the graph)

I would appreciate if someone can shed some light on this for me.

# Answer
> 2 votes
In the example above running DFS rooted at 0 the vector 0 will only have one tree link as the algorithm will follow the route: 0 -\> 1 -\> 2 -\> 0 Since the edge 0-2 is considered a back link and not a tree link 0 is not considered an articulation point.

# Answer
> 0 votes
By definition, a vertex is an articulation point if its removal increases the number of connected components. Thus, in general, the root node of a DFS is not necessarily an articulation point.

---
Tags: algorithms, graphs
---


# Question
Title: A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher
Referring to these notes regarding DFS - Click Here

They refer to the following claim that follows Definition 0.2. as observation:

> A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher.

However, I don't really understand why is that obvious or how can it be proved.

I'd appreciate a proof of this claim.

# Answer
We must prove two directions: (i) if $uv$ is a cut edge, then there is no edge from $v$'s subtree to $u$ or higher and (ii) if there is no edge from $v$'s subtree to $u$ or higher, then $uv$ is a cut edge.

For (i), if there was an edge from $v$'s subtree to $u$ or higher, then the removal of $uv$ would not increase the number of connected components contradicting the fact that $uv$ is a cut edge. To prove (ii), since every path from any vertex in a subtree of $v$ to a vertex that is $u$ (or higher than $u$) must use the edge $uv$, we see that $uv$ is indeed a cut edge.
> 1 votes

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


title: Problem with definition of bisimilarity

text:
# Question
Title: Problem with definition of bisimilarity
In my model checking class we have defined a bisimulation like this:

Let $K=(S,S\_0,Act,R,L)$ and $K'=(S',S'\_0,Act,R',L')$ be two kripke structures. A relation $B \subseteq S \times S'$ is called bisimulation if $\\,\forall (s, s') \in B$ following points are true:

1. $L(s) = L(s')$
2. $\forall \\,t \in S, a \in Act: (s,a,t) \in R =\> \exists \\, t' \in S': (s',a,t') \in R' \\, \land (t,t') \in B$
3. $\forall \\,t' \in S', a \in Act: (s',a,t') \in R' =\> \exists \\, t \in S: (s,a,t) \in R \\, \land (t,t') \in B$

Two states $s \in S, s' \in S'$ are called bisimilar iff. there is a bisimulation $B$ with $(s,s') \in B$.

$K$ and $K'$ are called bisimilar if:

1. $\forall \\, s \in S\_0 \\, \exists \\, s' \in S': s \sim s'$
2. $\forall \\, s' \in S\_0' \\, \exists \\, s \in S: s \sim s'$

My problem is that this definition is defined recursively. Take for example this two structures:

$\hskip2in$

Of course these structures are bisimilar since they are the same but to show that $(s\_0, s'\_0) \in B$ I have to show that $(t, t') \in B$ and now I'm in an endless recursion.

Have I misunderstood something about the definition?

# Answer
> 5 votes
You seem to be confusing the *definition* of bisimilarity with an *algorithm for finding* a bisimulation.

In your examples, the states are indeed bisimilar, and the relation is the set $$\\{(A,A)\\}$$ It is easy to verify that it satisfies the desired properties.

This means that the structures are indeed bisimilar.

What you were trying to do is to find an algorithm for constructing a bisimulation, given the two different structures. If you try to proceed by taking the initial states, and moving through paths, then you indeed encounter a problem with cycles. (By the way, if the structures were trees, or DAGs, then your approach would work).

This is why algorithms for finding bisimulations typically take a different approach -- namely *refinement*: you start with a naive relation (e.g., everybody is bisimilar to everybody), and whenever you find a mismatch, you refine your relation.

Take a look at the "fixpoint" definition of bisimilarity here, and try to extract an algorithm from it.

---
Tags: formal-methods, process-algebras
---


title: Find an optimal ordering

text:
# Question
Title: Find an optimal ordering
I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!

> Suppose we are given a matrix $\\{-1, 0, 1\\}^{n\ \times\ k} $, for example,
>
> $$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & -1 \\ -1 & -1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & -1 \end{bmatrix}$$
>
> Without trying every single permutation, find an ordering of columns $c\_i$ that maximises the number of rows for which the first non-zero element is $1$.

For the example above, one such ordering (it's not unique!) is $(c\_3, c\_4, c\_1, c\_2, c\_5)$, i.e.,

$$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ 0 & 0 & -1 & 0 & 1 \\ 1 & 0 & 0 & 1 & -1 \\ 0 & 1 & 1 & -1 & 1 \\ 0 & 0 & 1 & 0 & -1 \end{bmatrix}$$

Here, for $4$ out of $5$ rows the first non-zero element is $1$.

# Answer
> 4 votes
This problem, which I'll call CO for Column Ordering, is NP-hard. Here's a reduction from the NP-hard problem Vertex Cover (VC) to it:

## Decision problem forms of VC and CO

Let the input VC instance be $(V, E, k)$. It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $E$ is incident on at least one chosen vertex?" We will construct an instance $(A, k')$ of CO that represents the question: "Given the matrix $A$ with elements in $\\{-1, 0, 1\\}$, is it possible to permute the columns of $A$ such that a 1 appears before a -1 on at least $k'$ rows?" These two problems are stated in *decision problem* form, whereby the answer to each is either YES or NO: formally speaking, it is this form of a problem that is NP-complete (or not). It is not too difficult to see that the more natural *optimisation problem* form stated in the OP's question is roughly equivalent in terms of complexity: binary search on the threshold parameter can be used to solve the optimisation problem using a decision problem solver, while a single invocation of an optimisation problem solver, followed by a single comparison, is enough to solve the decision problem.

## Constructing an instance of CO from an instance of VC

Let $n=|V|$ and $m=|E|$. We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns. The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing *an edge that needs to be covered*. The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

For each vertex $v\_i$, create a column in which:

* among the top $(n+1)m$ rows, the $j$-th block of $n+1$ rows all contain a +1 when edge $e\_j$ is incident on $v\_i$, and 0 otherwise, and
* the bottom $n$ rows are all 0 except for the $i$-th, which is -1.

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Finally, set the threshold $k'$ for the constructed CO instance: $(n+1)m + n - k$. In other words, we allow at most $k$ rows in which a -1 appears before a +1. Let's call this number of violating rows the "cost" of a CO solution.

## Proof

The correspondence between a solution to the CO instance and a set of vertices in the original VC instance is: Every column to the left of the fence corresponds to a vertex that is in the set, and every column to the right of the fence corresponds to a vertex that is not.

**Intuitively, the -1s in the top of the "fence" column force the selection of a subset of columns to be placed to its left that together contain +1s in all these positions -- corresponding to a subset of vertices that are incident on every edge.** Each of these columns that appears to the left of the "fence" has a -1 on a distinct row somewhere in the bottom $n$ rows, incurring a cost of 1; the +1s in the bottom of the "fence" ensure that all columns placed to its right incur no such cost.

Clearly a VC solution using at most $k$ vertices yields a solution to the constructed CO instance with cost at most $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to the CO instance with cost at most $k$ corresponds to a vertex cover with at most $k$ vertices.

Suppose to the contrary that there exists a solution to the CO instance with cost at most $k$ that leaves some row in the top $(n+1)m$ rows with a -1 before a +1. This row belongs to a block of $(n+1)$ rows corresponding to a particular edge $uv$. Every row in this block in the original instance $A$ is identical by construction; permuting columns may change these rows, but does not affect the fact that they are identical. Thus each of these $n+1$ identical rows has a -1 before a +1 in the solution, implying a cost of at least $n+1$. But $k \le n \< n+1$: contradiction.

Since each of the $m$ blocks of rows in the top $(n+1)m$ rows have a +1 before a -1, each of the corresponding edges is covered by a vertex corresponding to a column to the left of the fence: that is, this subset of vertices constitutes a vertex cover. Since none of the top $(n+1)m$ rows have a -1 before a +1, the only place where cost can accrue in the solution is in the bottom $n$ rows, from columns placed to the left of the fence. Each such column has cost exactly 1, so given that the cost is at most $k$, there must be at most $k$ such columns, and hence at most $k$ vertices in the cover.

Finally, it's clear that the CO instance can be constructed in polynomial time from the VC instance, meaning that if a polynomial-time algorithm existed for solving CO, any VC instance could also be solved in polynomial time by first constructing a CO instance as described above and then solving it. Since VC is NP-hard, CO is too.

# Answer
> 2 votes
I don't know if there is actually a polynomial solution. Nevertheless based on Pål GD's comment, you can build a simplification function. The initial matrix is simplificated as you build the output sequence $S$.

```
function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then,
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

```

Then you have to do a complete exploration of the combinatorics using iteratively the function pick:

```
function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

```

After every pick you can do a simplification to possibly reduce the number of possibilities to explore. I suggest to explore greedily starting with the column having the less -1, thus you may reach a lower bound making a stop criterion.

On the given example, the first simplification gives (as Pål GD explained in comment)

* $S\[0\] = c3$, remove r1, r3
* $S\[1\] = c4$, remove r4
* $S\[2\] = c2$ this let you with a simple matrix to explore. $$\begin{bmatrix} -1 & 1 \\ 1 & -1 \\ \end{bmatrix}$$

I think a matrix making this method quite unefficient would have exactly one 1, and one -1 per row/column, something like $$\begin{bmatrix} -1 & 1 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 0 & 1 & -1 \\ \end{bmatrix}$$

Nevertheless, the simplification still spare about half the exploration steps. And this type of matrix can be split in several independant sub-matrix.

---
Tags: algorithms, optimization, combinatorics, matrices, permutations
---


title: Problems in $\textbf{DSPACE}(\log^2 n)$

text:
# Question
Title: Problems in $\textbf{DSPACE}(\log^2 n)$
Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$ and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations for problem $Q$ is polynomial many.

**Question :** Can I say that $\textbf{DSPACE}(\log^2 n)$ is in polynomial time complexity class?

# Answer
> 1 votes
There are about $2^{\log^2n}$ possible configurations, and $2^{\log^2n} = n^{\log n}$, which is not polynomial (it's "quasipolynomial"). So, no, you can't claim that $\mathrm{DSPACE}\[\log^2 n\]\subseteq \mathrm{P}$.

---
Tags: complexity-theory
---


# Question
Title: What is the difference between Consensus and Leader Election problems?
According to this paper written by Lamport, \`***selecting a unique leader is equivalent to solving the consensus problem'.***

Based on the above quote, **my question is**: What is the difference between consensus and leader election problems?

My answer: I think that there is no *theoretical* difference between them. They are two terms with the same meaning, but they are used in different context. When the context is related to data stores, replication, or related subjects, 'consensus' is used, otherwise, 'leader election' is used.

---

Note: In the above paragraph, '*theoretical*' means the way of defining a true consensus and leader election algorithm. A true consensus and leader election algorithm should satisfy three properties-- termination, agreement, and integrity.

# Answer
> 7 votes
This is not a matter of terminology: they're related, but different concepts.

A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in such a way that all the participants choose the same value. A solution to the consensus problem is a distributed algorithm that has the following properties:

* At the beginning, each participant $i$ has an initial value $v^0\_i$.
* At the end, all the participants must have the same value: $\forall i, \forall j, v\_i = v\_j$.
* The common final value must be the initial value of at least one of the participants: $\exists i, v\_i = v^0\_i$.

A leader election algorithm is a special case of consensus algorithm where the set is the set of participants. The leader election problem consists of requiring a leader election whenever there is no leader. If there are failures, this may require running more than one election, because a new election becomes necessary when the current leader fails.

In the absence of failures, if you can solve consensus then you can solve the leader election problem: apply consensus with every participant initially choosing themselves. Conversely, if you can elect a leader, then you can solve consensus by having everybody choose the leader's value. This is often how consensus is solved in practice: choose a leader (using a specialized consensus algorithm), then the leader broadcasts its choice of value each time a consensus is needed.

However, if there are failures, this equivalence no longer holds. There are failure models where it's possible to solve consensus, but not to elect a leader. See Laura S. Sabely and Keith Marzullo, *Election Vs. Consensus in Asynchronous Systems*, Cornell University technical report, 1995. The gap is that certain failure detectors are sufficient to run a consensus algorithm, so they are sufficient to run a leader election, but they are not sufficient to solve the leader election problem, because they aren't sufficient to detect when a new leader election is needed.

# Answer
> 2 votes
Consensus is broader. Leader election is about coming to agreement on the leader. Consensus is about coming to agreement on something -- might be on the leader, but might be something else that the participants want to agree on.

---
Tags: distributed-systems, parallel-computing
---


title: proving big theta

text:
# Question
Title: proving big theta
How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$

I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as

$$10n^3+3n \leq c\_1n^3$$

$$0 \leq c\_1n^3 \leq 10n^3+3n \leq c\_2n^3$$

# Answer
You may find the limit definitions much more simpler. So let $f(n) = 10n^3 + 3n$. You want to prove that

(i) $f(n) = \lim\_{n \to \infty} f(n) / n^3 \< \infty$, and that

(ii) $f(n) = \lim\_{n \to \infty} f(n) / n^3 \> 0$.

Now you only need to apply elementary algebra.
> 2 votes

# Answer
The definition of $f(n) = O(g(n))$ (for $n \to \infty$) is that there are $N\_0, c$ such that for $N \geq N\_0$ it is $f(n) \leq c g(n)$.

In your case, pick e.g. $N\_0 = 2$, then you have $10 n^3 + 3 n \< 10 n^3 + 3 n^3 = 13 n^3$, and $c = 13$ works.

The definition of $f(n) = \Omega(g(n))$ (for $n \to \infty$) is that there are $N\_0, c$ such that for $N \geq N\_0$ it is $f(n) \geq c g(n)$.

Pick e.g. $N\_0 = 5$, so $10 n^3 + 3 n \> 10 n^3$, and $c = 10$ works.

Now, $f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, and you are done.

Note the $N\_0$, $c$ don't have to be the same (usually at least $c$ is different).
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Find maximal subgraph containing only nodes of degree 2 and 3
I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to compute a maximal 2-3 subgraph of the input graph.

To be precise, a 2-3 graph is one that has only vertices of degree either 2 or 3. By maximal we mean that there is no other 2-3 subgraph which contains the maximal subgraph as a proper subgraph. It does not have to be a *maximum* subgraph.

The authors of the paper claim that the computation can be carried out by a simple Depth First Search (DFS) on the graph. However, this algorithm seems to elude me. How can the maximal subgraph be computed?

# Answer
Basically, in 2-3 graph, the lower bound 2 means that any node has to be in a cycle.

In DFS, when you reach an already visited node, you found a cycle. Just check if adding this cycle to your subgraph also respect the upper bound 3.

As you suggested, the maximal 2-3 subgraph is not unique. But if you built it following this method, you ensure that any node/vertex of $G$ you did not select in your subgraph:

* either is not part of any cycle and would lead to a vertex of degree 1 if selected
* either is part of cycles that would all lead to a vertex of degree 4 if selected

Thus, your 2-3 subgraph is maximal.
> 0 votes

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


# Question
Title: Finding the largest possible area covered by M rectangle under a given histogram
Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles instead of one rectangle in the previous problem.

So, my problem is to find the largest area under a histogram by $M$ rectangles which don't have overlap with each other. It should be noted that the bottom edge of all rectangles should be on the vertical axis of the histogram.

Is there any tractable solution for large $N$ (where $N$ is the number of bars in the histogram).

**Edit**:
@Apass.Jack suggested an approach with the complexity of $\Theta(MN^2)$, but after implementation, it needs some days for running! Is there any faster solution? For clarification, the value of $N$ is around $10^7$ and the value of $M$ is around $10^3$.

# Answer
What are the subproblems of this problem when we try dynamic programming? Or what is the table?

The subproblems are finding $dp\[m\]\[n\]$, the largest area possible by $m$ non-overlapping rectangle

* which are under the first $n$ leftmost bars and,
* the rightmost of which contains the $n$-th bar.

Let $dp2\[m\]\[n\]$ be the the largest area possible by $m$ non-overlapping rectangle

* which are under the first $n$ leftmost bars and,
* the rightmost of which is not to the right of the $n$-th bar.

The answer is the maximum of $dp2\[M\]\[n\]$, where $M\le n\le N$.

$dp\[m\]\[n\]$ is the maximum of $dp2\[m-1\]\[n-1\] + R\_{n,1}$, $dp2\[m-1\]\[n-2\] + R\_{n,2}$, $\cdots$, $dp2\[m-1\]\[n-i\] + R\_{n,i}$, $\cdots$, where

* $R\_{n,1}$ is the area of $n$-th bar
* $R\_{n,2}$ is the area of the rectangle which expands the $n$-th bar and $(n-1)$-th bar horizontally and which contains $n$-th bar
* $\cdots$, where $R\_{n,i}$ is the area of the rectangle which expands the $n$-th bar and $(n-i+1)$-th bar horizontally and which contains $n$-th bar.

$dp2\[m\]\[n\]$ is the larger of $dp2\[m\]\[n-1\]$ and $dp\[m\]\[n\]$.

The initial values of the two tables and boundary relations should be easy to determine.

There might be optimization tricks to speed up computation besides the standard memorization. You can check whether this naive dynamic programming is fast enough, whose worst behavior is about $\Theta(MN^2)$, which happens when all bars are becoming shorter and shorter from left to right.
> 2 votes

---
Tags: algorithms, time-complexity, optimization, dynamic-programming
---


# Question
Title: Show $\{1^n0^m |\space n \neq 2^m\}$ not regular using pumping lemma
Showing that the language $L$ with $\\{1^n0^m |\space n \neq 2^m\\}$ is not regular using Myhill-Nerode is easy: Let $i, j\in \mathbb{N}.i\neq j.$ It follows $1^{2^i}\nsim 1^{2^j}$ because $1^{2^i}0^{i}\notin L$ but $1^{2^j}0^{i}\in L$. Therefore $L$ has an infinite amount of Myhill-Nerode equivalence classes and is not regular. But how do I show this using the general version of the pumping lemma for regular languages? https://en.wikipedia.org/wiki/Pumping\_lemma\_for\_regular\_languages#General\_version\_of\_pumping\_lemma\_for\_regular\_languages

# Answer
> 1 votes
Let $p$ be the pumping length, and consider the string $u=1^{2^{p!+p}}$, $w = 0^p$, $v = \epsilon$. Notice $uwv \in L$. According to the pumping lemma, there is a value $q \in \\{1,\ldots,p\\}$ such that $1^{2^{p!+p}} 0^{p-q+iq} \in L$ for every $i \geq 0$. Choosing $i = 1 + p!/q$, we obtain a contradiction.

# Answer
> 0 votes
This answer uses the standard pumping lemma. Depending on your perspective, this answer may or may not have used the general pumping lemma.

Consider $L' = (1^\*0^\*) \setminus\\{1^n0^m \mid n \neq 2^m\\}=\\{1^n0^m\mid n=2^m \\}$.

Suppose the pumping length of $L'$ is $p$. Consider $w=1^p0^{2^p}\in L$. Then $w=xyz$, where $|xy|\le p$, $|y|\ge 1$ and $xy^0z=xz\in L'$. Since $y$ contains 1 only, $xz$ has less numbers of 1s and the same numbers of 0s as $w$. So $xz\not\in L'$. That contradiction shows $L'$ and, hence, $L$ is not regular.

---
Tags: regular-languages
---


# Question
Title: Enumerate over all halting Turing Machines?
I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the natural numbers and checking whether each number describes a syntactically well-defined TM.

I am wondering how it is possible to enumerate over all halting TMs. My intuition tells me that since the halting problem is undecidable, it should not be possible to filter an enumeration of all TM descriptions to only those TM descriptions which describe halting TMs.

Nevertheless, I recently came across a well-reputed Oded Goldreich and Bernd Meyer, *Computational Indistinguishability: Algorithms vs Circuits*, *Theoretical Computer Science* 191(1–2):215–218, 2998) that uses an enumeration of all halting Turing Machines (see Proposition 1, pg. 2). I'd appreciate any help in understanding this.

# Answer
> 4 votes
The paper you're referring to is using "enumeration" just to mean "ordered list". Your feeling that such a list can't be computed by a Turing machine is correct. However, the list *exists*, even though there's no algorithm that will tell us what its members are.

Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of *the* halting Turing machines". So it's just any ordered list of halting Turing machines, not necessarily all of them. It specifically mentions enumerations of polynomial time Turing machines. You might be surprised that these *are* enumerable, up to equivalence*. This is because you can turn any Turing machine into a polynomial time Turing machine by picking your favourite polynomial and modifying the machine so it rejects if it hasn't in that many steps. Since you can enumerate all polynomials (say, with nonnegative integer coefficients), and you can enumerate all Turing machines, you can combine the two to enumerate all polynomial time Turing machines.

* Two Turing machines are equivalent if they give the same output for every input.

# Answer
> 3 votes
If you mean halting TMs by TMs that are halt on **all** strings, then yes, it is impossible to enumerate over all halting TMs. However, this is not because the set of halting TMs is undecidable, but because it is even not recognizable. Note there exists a TM enumerating all valid strings of a language if and only if the language is recognizable.

The word "enumeration" in the paper you linked to is different from our common understanding of an enumerator. Or rather, it means an infinite sequence of halting TMs, and is not required to contain **all** halting TMs.

---
Tags: turing-machines, halting-problem, enumeration
---


# Question
Title: Constructing a reduction between two languages about pairs of Turing machines
I'm curious about a potential relation between the following two languages.

$L\_1 := \\{\langle M\_1, M\_2 \rangle : L(M\_1) \cap L(M\_2) \ne \emptyset \\}$.

$L\_2 := \\{\langle M\_1, M\_2 \rangle : L(M\_1) \ne L(M\_2) \\}$.

> Is it true that $L\_2$ mapping reduces to $L\_1$?

I've had many failed attempts to construct a reduction and would appreciate any help.

# Answer
> 0 votes
Here are three hints.

* Show that $L\_2$ is not computably enumerable.
* Show that $L\_1$ is computably enumerable.
* If $L\_2$ mapping reduces to $L\_1$, what does it imply?

---
Tags: turing-machines, computability, reductions
---


# Question
Title: Index matching algorithm without hash-based data structures?
I am programming in C, so I do not want to implement a hash-based datastructure such as a hashset or hashmap/dictionary. However, I need to solve the following task in linear time.

Given two arrays $a$ and $b$ which contain the same set of distinct integers, determine for every element of $a$ the index of the same element in $b$.

For example, if $a=\[9,4,3,7\]$ and $b=\[3,4,7,9\]$, then the output should be $\[3,1,0,2\]$.

Note that this becomes a very easy task when you have a hashset, because you can simply store for every element in $b$ the index, and then query the hashmap for every element of $a$.

So my question is whether there is a linear algorithm for this task that does not use any hashsets.

# Answer
If the only operation allowed between any two (possibly the same) elements in the two arrays is to determine which one is the smaller one, then it will take $\Theta(n\log n)$ time in worst case for any algorithm.

This can be seen from the situation when array $a$ is sorted while array $b$ is arbitrary before we apply the algorithm. Knowing the index $I(k)$ of the element in $b$ which is the same as the $k$-th element of $a$ for all $k$, we can sort $b$ in $O(n)$ time by simply putting $b\_{I(k)}$ in $k$-th position (using one temporary working space or a new result array of length $n$). However, it is well-known that it takes at least $\Theta(n\log n)$ time (comparisons) to sort $b$ in worst cases for any algorithm. So obtaining that knowledge, the index $I(k)$ for all $k$ must take at least $$\Theta(n\log n)- O(n)=\Theta(n\log n)$$ time as well in worst cases.

The following is a formal formulation of the conclusion above in the comparison computation model.

Let $\mathcal O$ be an oracle that can tell a fixed strict linear ordering on $E$, a set of $n$ elements. That is, on input $e,f\in E$, $\mathcal O$ outputs -1 if $e\prec f$, 0 if $e$ is $f$ and 1 otherwise. Let $a$ and $b$ are two bijections from $\\{0, 1,\cdots, n-1\\}$ to $E$. To output $I(0), I(1), \cdots, I(n-1)$ in that order such that $a(k)=b(I(k))$ for all $0\le k\le n-1$, it will take $\Theta(n\log n)$ queries against $\mathcal O$ in the worst case.

> whether there is a linear algorithm for this task that does not use any hashsets.

A computation model that is defined by no usage of hashset is not a well-defined computation mode. How can you check there is no usage of hashset? There are literally hundreds of ways to implement a data structure that is a hashset or looks like a hashset or looks like a hashset partially. In general, a well-defined computation model must be defined by what can be done formally.
> 3 votes

---
Tags: search-algorithms, hash-tables, permutations
---


# Question
Title: How does a Turing machine compute when its head is at the right-hand end of its configuration?
I'm reading Sipser's *Introduction to the Theory of Computation* (2nd ed.), and I am having trouble understanding one of the cases of Turing machine computation. Sipser describes the cases in terms of how one configuration yields another after a step of computation. For example, if the head is not at either end of the configuration and is moving leftward:

> Suppose that we have $a$, $b$, and $c$ in $\Gamma$, as well as $u$ and $v$ in $\Gamma^\*$ and states $q\_i$ and $q\_j$. In that case $uaq\_ibv$ and $uq\_jacv$ are two configurations. ... $uaq\_ibv$ yields $uq\_jacv$ if the transition function $\delta(q\_i,b)=(q\_j,c,L)$.

where $\Gamma$ is the tape alphabet and $L$ means the head is moving leftward.

I understand this case, as well as the case where the head moves rightward without being at either end and the cases where the head is at the left-hand end. However, I don't understand the cases where the head is at the right-hand end. Here's how Sipser explains the end cases:

> Special cases occur when the head is at one of the ends of the configuration. For the left-hand end, the configuration $q\_ibv$ yields $q\_jcv$ if the transition is left-moving (because we prevent the machine from going off the left-hand end of the tape), and it yields $cq\_jv$ for the right-moving transition. For the right-hand end, the configuration $uaq\_i$ is equivalent to $uaq\_i⌴$ because we assume that blanks follow the part of the tape represented in the configuration. Thus we can handle this case as before, with the head no longer at the right-hand end.

where ⌴ is the blank symbol.

I'm not sure how to handle this case as I don't know where "as before" refers to. I conceptualize the head like a text cursor stuck in overtype mode, and so my initial guess would be that $uaq\_i⌴$ yields something like $uacq\_j⌴$ when moving rightward and $uq\_iac⌴$ when moving leftward, but I worry that I've missed something. Am I on the right track or am I way off base?

# Answer
Yes, your understanding is correct.
> 2 votes

---
Tags: turing-machines
---