# Question
Title: Is there a philosophical counterpart question to P != NP?
Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such statement might be "This Theorem is practically unprovable". The consequences of an existence of such theorem would be: If the sentence is true, than there is no practical way to prove it. If it is not true, then there is a practical way to prove it, hence it must be true, which is a contradiction. Since P!=NP is such a deep question, I wonder if philosophist have a counterpart question in the sense given above.

# Answer
> 3 votes
Shortly: No.

Gödel motivation was to give closure, in a sense the very same as Hilberts to make one connected field. This is meta-science (meta-mathematics) but not based on philosophy but mathematics.
The concept of **truth** was connected with logic (in logic it is just well defined symbol), and the idea was to give axiomatic (absolute **truth**), in order to achieve that the one obvious idea is to give a function (even oracle) that evaluates given object (explicitly loose statement, as it was (and is) underdefined). It was meant to rescue the concept (the truth depends on context, field given, e.g. in Psychology the absolute truth would not be of that much use), which is required to prove anything.

Gödel started as mathematician, the pursuit of closure pushed him to mathematical philosophy (self-studied, not at the professional level), which was used as meta-science, meta-logic, but every time any advancement was made it was back in the field of mathematics. The urge to prove was bigger than to disprove so he picked contraposition to get back to mathematics (CS). After that he succumbed into idealism.

Any proof in given field must be proved in given field, using provided tools, meta-tools and must be verified (and understood) by people from that field otherwise this is just loose statement. In example $P vs NP$ cannot be proved using philosophy, where it is undefined problem. Unfortunatelly it would require to take understanding of the whole field, define the problem using strict notation and use M or CS tools.

The philosophical counterpart does not exist, moreover in that field the $P vs NP$ problem might be defined with assumption of one being true, both or neither. Nothing prevents from defining problem as exclusive alternative or nonexclusive alternative. The concept will be well defined in any cases giving the frame of reference, outcomes and closed entity (world) where we can go further with provided axioms (and this is what we do in CS, there are conditional proofs "if P = NP then ..."). But the task to actually prove it is in the field of Mathematics or Computer Science.

There is no counterpart theory or framework of inference. The sentence you have provided is not proper. Any kind of paradox, tautology or too loose statement to deal with in some other field gives nothing and proves nothing. For the sake of argument if there were counterpart theory it still would be too weak to infer anything. The paradox is something that goes beyond formalism or simply includes mistakes at language level - which are totally irrelevant when analysing in philosophy since it can be resolved at any level giving explicit assumptions.

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


title: Graph adjacency using Hashing

text:
# Question
Title: Graph adjacency using Hashing
Consider a graph $G = (V,E)$ and the following operation

$\text{neighbour}(v\_1,v\_2)$: returns `true` if the vertices $v\_1$ and $v\_2$ are adjacent, and `false` otherwise.

I now consider two standard data structures:

**Adjacency Matrix.** Space complexity is $\mathcal{O}(|V|^2)$ and supports the neighbour-query in $\mathcal{O}(1)$ time.

**Adjacency List.** Space complexity is $\mathcal{O}(|E| + |V|)$ as far as I understand, however the neighbour-query depends on the degree size.

My question is the following:

> How can we improve these data structures using hashing? (space/time complexity in terms of $|V|$ and $|E|$)

Can we e.g. reduce the space complexity of the adjacency matrix and retain an average constant time query?

# Answer
> 3 votes
With hash the space needed is $\mathcal O(|E| + |V|)$ (depending on array size given), and the time is expected $\mathcal O(1)$, but might degrade to $\mathcal O(|V|)$ (depending on collision resolving scheme).
With minimal perfect hash the space is exactly $|E| + |V|$ of entries (of appriopriate entry size).

Minimal perfect hash will map without collisions the given set - array for $n$ elements will have exactly $n$ length, so the $|E|$ edges will occupy exactly $|E|$ array elements. Defined function $h$ will disregarding the number of entries, as opposed to normal hash which might be several times bigger than number of entries and collisions degrade the query time (as linked-list).

This is very efficient scheme for static graph, in case of dynamic one the same issue of rehashing holds. It does not matter how the nodes are encoded (string, int etc.).

How MPH works.

# Answer
> 2 votes
I have done it this way, but this implies you have your nodes represented as integers from $0$ to $|V| - 1$. It is actually quite similar to adjacency lists, but instead of have a list to store the indexes of the neighbors you will have a hash table (or a hash set depending on your specific problem), the space complexity depends on the specific implementation but with a dynamic array tou may reach $O(|d\_{i}|)$ for a given node $i$, to achieve a $O(|E|+|V|)$ space complexity.

In terms of time, as you have a list of hash tables/sets the access for a given node is constant in the list, and depending on your hashing scheme you may achieve $O(1)$ access for each node. As I've mentioned before this assumes you have represented your nodes as integers, so a common hashing method as Knuth's multiplicative method would be fine to retain constant access.

Another option is to represent your graph directly as edges and do a hashing function over the pairs of nodes that represent an edge, this would lead to $O(|E|)$ in theory, depending on your implementation. A common way to implement those hash function is to combine the hash functions of each component of the pair, typically computing the xor of the hash functions. If you already know the size of the graph and it is static is straightforward to came up with a perfect hash function to achieve a tight bound in space and complete $O(1)$ access. It depends on the problem you are solving though.

---
Tags: graphs, hash
---


# Question
Title: Find string patterns preferably in regex for string streams
I am trying to classify the data in a database columns. DB has about 90 million entries.The main goal is to find different patterns in columns to leverage it for create look alike data. The data columns has entries which can easily look like patterns as :

```
 CUST1212,CUST1213,CUST1214...,  number sequential after CUST
 CODE1213,CODE1242,CODE1289...   random numbers after code
 CUST1213,MUST8324,FIFA12313...
 009-123-2123,003-124-2314,006-213-5322,
 INTER122,INTER222,INTER322...,  number increasing in batch of 100
 OM|ON|TO, IO|OI|UH...,  pipe delimited
 some 6 and 7 digits number.

```

The issue is there are so many patterns and looks like creating patterns manually based on data is out of option.

I would really appreciate if one can point to how can I build a collection of patterns preferably by usage frequency.

What I started is 1. Segregate the data as per their length as patterns usually generate same string length, sorted them and stored them in different files. 2. Then classifying them further as per Alphabet prefix or numeric prefix. 3. For alpha-prefix segregate further on common alphabets at start.

Now seems I am lost and sincerely hoping if one can point out to me what are my options and probably best to took.

I believe if end of computation if get something like patterns in data and their frequency e.g. CUST\[0-9\]{4} -\> 10k times, \[a-zA-Z\]{4} -\> 50k times \[0-9\]{3}-\[0-9\]{3}-\[0-9\]{4} 10K times etc....., it would be great.

Thanks

# Answer
> 1 votes
The general approach is likely to be:

1. Identify a set of candidate patterns that *might* appear.
2. For each candidate pattern, check for all instances of that pattern.

I'm not aware of any simple procedure that avoids the need for step 1. The problem is that there are many possible patterns that might appear (e.g., "consists solely of Latin-8 characters"; "length is always at most 100") but most of them won't be meaningful or useful in your domain. Only you know what will be meaningful/useful. So, you'll have to use your domain knowledge to identify which potential patterns are useful -- I don't know of any algorithm that can do that for you.

---
Tags: regular-expressions, data-mining, classification, pattern-recognition
---


# Question
Title: Why are hash map look-ups assumed to be $O(1)$ on average
To look up a key in a hash map you have to

1. calculate its hash
2. find the entry in the resulting hash bucket

Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.

When using an index (like a binary tree) for each bucket, finding an entry within a bucket that contains $k$ entries can be done in $O(\log k)$. With $n$ being the total number of entries in the hash map and $m$ being the number of buckets, $k$ averages to $n/m$. Due to $m=2^l$ we thus get $O(\log k) = O(\log n/m) = O(\log n - \log m) = O(\log n - l)$.

Combining these two runtimes one gets a total look-up time of $O(l + \log n - l) = O(\log n)$, which conforms to the intuition that a lookup in a collection with $n$ entries is not possible below $O(\log n)$ operations.

In short, it is generally assumed that $l$ *and* $k$ are both constant with regard to $n$. But if you fix $l$ then $k$ grows with $n$.

Am I missing something here?

# Answer
Because we generally use the RAM model of computation with uniform cost model when computing the running time of operations on a hash table, and the RAM model with uniform cost states that the time to do a single operation on an entire machine word is $O(1)$. Also, we generally assume that the hash value fits within a single machine word.

Thus, the running time of computing a hash value is not $O(l)$, but rather $O(1)$ \[assuming both the value being hashed and the hash value fit within one word, or a constant number of words\].

Moreover, when you choose the hash function and size of the hashtable appropriately, the expected value of $k$ is $O(1)$. In particular, the number of buckets is not fixed, but increases as the number of items in the hashtable grows. The number of buckets it is usually chosen to be some function of $n$; say $m = 4n$, or something like that. In any case, we usually choose $m$ so that $n/m = O(1)$. Therefore, the (expected) running time to find an item within the bucket is $O(1)$.

Therefore, the total (expected) running time is $O(1)+O(1) = O(1)$.

So why do we use the RAM model with uniform cost model? Because it's often a better match to reality than other alternatives.
> 8 votes

# Answer
The runtime analysis as given for example in the Wikipedia only counts the number of comparisons, which is indeed O(1), if you resize your table. You have to add the time to compute the hash function if you want to be precise.

Note that this isn't too bad though. Computing the hash function for some object with $n$ bits takes $O(n)$ operations (for reasonable hash functions). Comparing two objects with $n$ bits also takes that long. So computing the hash function costs about as much as a comparison, up to constant factors.
> 1 votes

# Answer
If a value has size l, I can easily calculate a hashcode in constant time, by ignoring all the data beyond some limit. I know of one implementation for strings that uses only up to 80 characters in the hash.

Or take an array: A reasonably simple hash for an array takes the number of elements, and the hash code of one array element chosen in a deterministic way from the element count, and hashes these two numbers.
> 0 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, hash-tables
---


# Question
Title: Is there a fast solution for this set reduction problem?
Let there be a set $S$ and denote by $P=2^S$ the power set of $S$. We are given a finite subset $L = \\{p\_0, \ldots, p\_{n-1}\\}$ of $P$ and we are allowed to transform the set as follows: if two sets $p\_i$ and $p\_j$ share some elements, i.e. $p\_i \cap p\_j \neq \emptyset$, remove both $p\_i$ and $p\_j$ from $L$ but add their union $p\_i \cup p\_j$ to $L$.

What is the algorithmically fastest way to reach a state where there is no further (or almost no further) transformation of $L$ possible?

One simple way to achieve that goal is to compare all elements with each other and perform a transformation if possible, repeat until no changes are possible.

Pseudo C++-code using std::vector:

```
vector<Set> L = ...;
int n = L.size();

bool hasChanged = true;
while (hasChanged) {
    hasChanged = false;

    for(int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (!isDisjoint(L[i], L[j])) {
                // remove L[i] and L[j]
                swap(L.back(), L[i]);
                L.pop_back();
                swap(L.back(), L[j]);
                L.pop_back();

                // add their union
                L.push_back(getUnion(L[i], L[j]));

                hasChanged = true;
                i -= 1; // we don't want to skip the swapped element
                break;
            }
        }
    }
}

```

This algorithm takes $\frac{n^2-n}{2}$ comparisions in the best case and $\sum\_{k=1}^n \frac{k^2-k}{2}$ comparions in the worst case. Naturally the number of comparisons needed depends on the ordering of the elements in the vector.

To provide some less abstract context: I have a set of line segments which i want to reduce. So the idea is to connect lines which are "close" to each other. A connected line does not necessarily share start or endpoints with its original lines but it can be connected to other lines in the set. How do I connect all the lines until there is no further improvement possible in the fastest way possible?

# Answer
> 2 votes
This rewriting system is confluent, so if you just repeatedly pick a legal transformation and apply it, over and over again, until you can't any longer ... you will always end at the same state.

In other words, there is a unique end state from which no further transformations are possible, and you can reach it by any sequence of legal transformations. Define a state to be a *final* state if no further transformations are possible from it. Then there is a unique final state, so you can reach it by following any legal sequence of transformations and continuing until you can't continue any further. (This will terminate, since each step reduces the size of $L$. By definition, once you can't continue, you are in a final state. Since the final state is unique, this terminates at the unique final state.)

You can even find the shortest such sequence, relatively efficiently. Build an undirected graph with one vertex for each $p\_i$, and with an edge $(p\_i, p\_j)$ if $p\_i \cap p\_j \ne \emptyset$. Compute the connected components of this graph. Then the final state will have one subset per connected component in the graph; it will be a subset containing the union of all of the vertices of the connected component. You can get to that connected component by repeatedly picking some pair of vertices $p\_i,p\_j$ that are joined by an edge, merging those two vertices into a new vertex $p'$, and then updating the edges ($p'$ gets an edge to each vertex that had an edge to either $p\_i$ or $p\_j$; but remove all self-loops). If there are $n$ vertices originally and $c$ connected components, this will terminate after $n-c+1$ steps.

In fact, looking at it a bit longer, you can discover that *any* legal sequence of valid transformations that ends at a final state is equally good -- all such sequences have the same length. You start with $L$ containing $n$ subsets; you end with $L$ containing $c$ subsets; each transformation reduces the length of $L$ by one; so any such sequence must contain exactly $n-c+1$ steps. All the legal sequences end at the same final state, so all sequences are equally good.

**TL;DR:** At each step, apply *any* valid transformation. Eventually you will terminate. It doesn't matter which pair of subsets you choose to merge at each step; you'll eventually end at the same ending point, and the total number of steps will be the same regardless of the choices you make at each step.

This is the most wonderful kind of algorithm: at each step, do *anything* that's not illegal, and you'll eventually end up a winner. You can't lose!

---
Tags: algorithms, complexity-theory
---


# Question
Title: Topological Sort without modifying the graph or marking edges
I have a DAG which I want to traverse in a topological order. Wikipedia describes two algorithms for topological sorting, which both work in theory but seem impractical to me from a design point of view: Kahn's algorithm modifies the graph (by removing edges) and the DFS-based one marks nodes, which would require me to modify my node classes (by adding a boolean field) and is furthermore not thread safe.

Are there more practical approaches, that preserve the asymptotic runtime but do not interfere with my business logic so much?

# Answer
> 2 votes
Instead of seting a 'mark' flag;

```
 node.Marked = true;

```

You can maintain a set of marked nodes in a hashtable or similar;

```
 hashTable[node] = true;

```

You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked.

# Answer
> 1 votes
You can do a topological sort with a DFS and retrieve the nodes order by pushing the node on a stack just before the recursive call ends. This implies extra memory to mark a node as visited though, anyway to transverse a graph you almost always will need extra memory to keep account of visited nodes.

That visited marks can be implemented with a hash table as mentioned before without modify your business logic.

A quick pseudocode:

```
topSortRec(currentNode, graph):
  for neighbor in graph.neighbors(currentNode):
    if neighbor is not visited:
      topSortRec(neighbor, graph)

  S.push(currentNode)

topsort(graph):
  for each node in graph:
    mark node as not visited

  S = init as empty stack
  for each node in graph:
    if not is not visited:
      topSortRec(node,graph)

  path = init as empty list
  while S is not empty:
    node = S.pop()
    path.append(node)

  return path

```

# Answer
> 1 votes
Kahn's algorithm is practical. When the algorithm says "delete an edge", what you actually do is mark the edge and remember to treat marked edges *as if* they were deleted. It's easy to figure out how to go from there. You can keep a set (hashtable) of marked edges.

Or, you can make a copy of the graph, and then delete edges in the copy. That's even easier to implement, and a quite reasonable implementation strategy.

---
Tags: dag
---


# Question
Title: Basic question about 4-way set associative
When the CPU writes or reads from the memory and stores the value that was read or written into L1 cache. Do the CPU store the whole block( 1 block , leaves the other three ways empty) or the whole set ( 4 blocks)?

# Answer
Four way set associative does not mean 4 sets.

It means each set is of 4 blocks.

Individual block can be read or written.

Go through this document for understanding the concept of set associative cache.
> 2 votes

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


# Question
Title: Proving $(a+b)^* = b^*(ab^*)^*$ equationally
I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.

I need to prove the following property using different Kleene star properties:

$$(a+b)^\* = b^\*(ab^\*)^\*$$

# Answer
A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^\* = (a^\*b)^\*a^\*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free): $$ \begin{align\*} (a+b)^\* &= (b+a)^\* && C2 \\ &= (b^\*a)^\*b^\* && C11 \\ &= (\epsilon+b^\*(ab^\*)^\*a)b^\* && C12 \\ &= b^\* + b^\*(ab^\*)^\*ab^\* && C9 \\ &= b^\*(\epsilon + (ab^\*)^\*ab^\*) && C8 \\ &= b^\*(\epsilon + \epsilon(ab^\*\epsilon)^\*ab^\*) && C6,C7 \\ &= b^\*(\epsilon ab^\*)^\* && C12 \\ &= b^\* (ab^\*)^\* && C7 \end{align\*} $$
> 6 votes

# Answer
Applying kleen star on both side

((a+b)\*) \*= ( b * (ab\*)\*) *

But ((a+b)\* )\* = (a+b)\* as we know (a\*)\* = a\*

( b * (ab\*)\*) * = (b + (ab\*))\* as we know (a+b)\* =(a\* b\*)\*

I can use b\* as empty string as its redundant.

Even if we are using b\* as empty string the expression gives all strings of a's and b's. So using b\* wont add new strings to the set.

So we can say

(b + (ab\*))\*= (b+a) * = (a+b)\*

Proved
> -1 votes

---
Tags: formal-languages, proof-techniques, regular-expressions, kleene-star
---


# Question
Title: Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?
I'm working with a flow network like the following:

The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, also with capacity 1. X and Y both have edges with capacity 4 to the sink t.

Typically this would have many solutions: all of the ways you could split up A, B, C, and D between X and Y. In the modified version, I have to pick either X or Y. If the flow on (X, t) \> 0, the flow on (Y, t) must be 0, and vice versa. So there are only two solutions, sending all 4 units of flow through X or through Y.

I'm wondering if there is a way to reduce this constraint to the standard max-flow so I can just run Ford-Fulkerson on a modified graph. That, or whether this is fundamentally harder and is an isomorphism of a different problem.

In simpler versions like the one I've laid out above you could just reduce the decision to a problem where you have only s, t, and the nodes X and Y and must send 1 unit of flow through the network, but I'm struggling with the general case where we have two edges X and Y, only one of which is allowed to have nonzero flow through it in the solution.

# Answer
You can reduce SAT to this version. Connect the source to nodes $x\_1,\ldots,x\_n$, one per variable, with infinite capacity. Connect each $x\_i$ to two exclusive nodes $x\_i^T,x\_i^F$, with infinite capacity. Create one node per clause, and connect a literal to a clause (with infinite capacity) if the clause contains the literal. Finally, connect each clause to the sink with unit capacity. The maximum flow is the number of clauses iff the formula is satisfiable.
> 4 votes

---
Tags: network-flow, max-flow, ford-fulkerson
---


# Question
Title: Why does P/Poly can also receive bad advice?
(from my class's slides)

*"NP and P/Poly both use an external string for computation. However, for L in NP, any witness is rejected if x $\notin$ L. For L in P/Poly, there can be bad advice!*"

I'm having a hard time understanding why this is true. My intuition is that if there are indeed 'bad advice', i.e advice that make the Turing Machine return bad answers, doesn't it mean that a situation where ALL of the advice are 'bad' is technically possible?

# Answer
Lets review the definition of the class $P/poly$ by Turing machines which take advice.

The class $T(n)/a(n)$ is the set of languages decidable by a Turing machine which runs in time $T(n)$ with advice of length $a(n)$.

More formally, $L\in T(n)/a(n)$ if there exists a Turing machine $M(x,y)$ and a sequence of strings $\left\\{\alpha\_n\right\\}\_{n\in\mathbb{N}}$, with $\alpha\_n\in\left\\{0,1\right\\}^{a(n)}$, such that for all $x\in\left\\{0,1\right\\}^n$ $M$ runs in time $T(n)$ and $x\in L \iff M(x,\alpha\_n)=1$.

$P/Poly=\bigcup\limits\_{c,d}n^c/n^d$.

As you can see in the definition above, we only require the existence of some sequence of advice $\alpha\_n$ that we can trust. Perhaps for some different sequence, $\beta\_n\in\left\\{0,1\right\\}^{a(n)}$, and some $x\notin L$, it holds that $M(x,\beta\_{|x|})=1$, but we don't care, since we only required the existence of a "good" sequence of advice.

This is unlike the case with $NP$, where if $x\notin L$, all witnesses must be rejected.
> 9 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: How is Memory Access Time of Processor calculated?
In the Art of Assembly ebook, I have read that 8088 processor require four clock cycle to access memory (in whatever clock speed & memory speed is). How is it calculated? Is it time for processor to prepare for calculate address and put data on the bus?

# Answer
The 8088 is $16 bit$ microprocessor with $8 bit$ data bus, it requires $2$ cycles to access word. During the second read counter is automatticaly incremented. In 8088 $1$ cycle is needed to apply valid physical memory address (and read or write). The missing $1$ cycle is for preparation. The cycles are not calculated, simply read from specification steps performed.

**Cycle:**

1. acquire valid address to address bus.
2. RD (or WR) signal is issued, DEN is asserted (if WR then data is put onto the data bus). DEN connects data bus buffers to external data.
3. allow memory to access data, if RD the data bus is sampled ot the end of cycle.
4. bus signals are deactivated, data sampling is finished (RD). If WR data is transfered to memory.
> 0 votes

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


# Question
Title: Is hedge union always as fast as divide and conquer?
Adams describes a divide-and-conquer algorithm for finding the union of two sets (represented as weight-balanced binary search trees). He then describes a then-new "hedge union" algorithm which he claims improves on the divide-and-conquer one. However, he does not offer a proof, or even a real explanation, of why it should be $O(m + n)$, let alone why it should be faster than divide-and-conquer.

Blelloch, Ferizovic, and Sun show that Adams's divide-and-conquer algorithm actually attains the theoretically optimal $\Theta (m \log (n/m + 1))$ where $m \le n$. They do not, however, address the hedge union algorithm.

Is hedge union, in fact, as efficient as divide-and-conquer? The least obvious part is the inner trim. It appears, at least superficially, to duplicate work between the left and right subtrees that the full split shares between them. Perhaps this is okay for some reason, but I don't know why.

A further inquiry: Haskell's `Data.Set` and `Data.Map` use hedge variants of intersection and difference, as well as union. I have not found any published discussion of those algorithms at all. Similar questions apply to these as well.

# Answer
> 3 votes
While I have yet to see, or produce, a theoretical analysis of the hedge algorithms, I do have some empirical evidence that they are *worse* than the divide-and-conquer algorithms for binary trees.

Starting with the code in the Haskell `containers` package, I optimized the hedge union algorithm by manually applying call-pattern specialization to reduce intermediate allocation. This improved its performance by about 10%, giving it a fair shot.

Starting with the divide-and-conquer code in Adams, I optimized the union algorithm by adding special cases when either of the inputs is a singleton (the hedge union code optimizes one side thus, and it's not clear if the other side can be optimized similarly).

I tested each implementation using a collection of set operation benchmarks packaged with `containers`. Divide-and-conquer was usually faster than hedge, sometimes twice as fast. When it was slower, it was only slightly so.

Similar benchmarks of other set operations gave similar results.

---

Speculation:

Hedge algorithms may be helpful when using trees with a large branching factors, which may be more expensive to split recursively. They may also be helpful for small subtrees, where they may save enough allocation to be worth the extra work.

---
Tags: data-structures
---


# Question
Title: Is zero allowed as an edge's weight, in a weighted graph?
I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.

actually it makes sense that 0 could be used as an edge's weight, but I've been working with graphs in last few days and I have never seen an example of it.

# Answer
> 165 votes
Allowed *by whom*? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing.

The reason you don't usually see zero-weight edges is that, in most contexts, an edge with weight zero is exactly equivalent to the absence of an edge. For example, if your graph represents countries and the amount of trade done between them, a zero-weight edge would mean no trade, which is the same as having no edge at all. If your graph represents distances, a zero-weight edge would correspond to two places at distance zero from each other, which would mean they'd actually be the same place, so should both be represented by the same vertex. However, in other contexts, zero-weight edges could make sense. For example, if your graph represents a road network and edge weights represent the amount of traffic, there's a big difference between a road that nobody uses (zero-weight edge) and no road at all (no edge).

# Answer
> 13 votes
It depends on the context. In general yes, edges of zero and even negative weight may be allowed. In some specific cases the edge weights might be required to be non-negative or strictly positive (for instance, Dijkstra's algorithm requires weights to be non-negative).

# Answer
> 5 votes
As the other answers note, you're perfectly free to consider (or exclude from consideration) weighted graphs with zero-weight edges.

That said, in my experience, the *usual* convention in most applications of weighted graphs is to make no distinction between a zero-weight edge and the absence of an edge. One reason for this is that, typically, weighted graphs show up as generalizations of multigraphs, which in turn are generalizations of simple graphs.

Specifically, a multigraph is a graph that (unlike a simple graph) allows multiple edges between the same pair of nodes. Whereas, in a simple graph, any pair of nodes is always connected by 0 or 1 edges, a pair of nodes in a multigraph may be connected by 0, 1, 2, 3 or more (but always a non-negative integer number of) edges.

Generalizing a multigraph to allow for *a fractional number of edges* between a pair of nodes then naturally leads one to consider weighted graphs, and many algorithms that work on arbitrary multigraphs can also be made to work on such weighted graphs. But for such algorithms, the "weight" of an edge really denotes its *multiplicity*. Thus, given this interpretation, there can be no meaningful distinction between "no edge" and "0 edges" between a pair of nodes: both mean exactly the same thing.

Of course, a "weighted graph" by definition is really just a graph with a number associated to each edge, and it's perfectly possible to interpret the weight as something *other* than multiplicity, in which case a distinction between no edge and a zero-weight edge may indeed be meaningful. But trying to apply standard multigraph algorithms to such "strangely weighted graphs" is unlikely to produce results that would make sense in terms of the alternative (non-multiplicity) interpretation of edge weights.

# Answer
> 0 votes
Think of a graph of the road system in Cambridge UK, the notes are shared between cyclists and car drivers, so are most of the edges. Doing so greatly decreases the cost of maintaining the data.

Now if we define the edge weight as being travel time in seconds, cleanly each edge will have two weights, one for cars anther for bikes. Some weights will be infinite as cars are not allowed on cycle ways.

Now consider two road junctions that very close to each other so close they are only serrated by a few posts that stop car drivers. (For example a cross road, where car drives can only turn left, but cyclists can go in any direction.) We then get some edges with infinite weight from car drivers and 0 weight for cyclists.

(Clearly the graph could then be pre-processed to create a simpler graph for the routing of cyclists, before working out the best routs.)

# Answer
> 0 votes
It sounds like you are using the weight to try and represent two distinctly different aspects of the graph. The first is whether the graph actually has a representable (drawn) edge, and the second is it's actual weight.

As you have noticed, you drop into a confusing situation if you have used 'non-zero' as an indicator that an edge is present (and would need to be drawn, or listed), while at the same time have now found a situation where zero weight is classed as valid.

Essentially you will need another way of representing the presence of the edge (assuming you actually need that, and can't simply create an N^2 array of weights, but then you fall into the trap of needing to decide what to do about loop back edges...)

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


title: What is a "special sequence" in EBNF?

text:
# Question
Title: What is a "special sequence" in EBNF?
In Extended Backus-Naur Form (EBNF) there is one form called a "special sequence" which is surrounded by questions marks `?...?`

What does this mean?

# Answer
> 1 votes
Quoting from the Wikipedia page:

> According to the ISO 14977 standard EBNF is meant to be extensible, and two facilities are mentioned. The first is part of EBNF grammar, the special sequence, which is arbitrary text enclosed with question marks. The interpretation of the text inside a special sequence is beyond the scope of the EBNF standard.

---
Tags: parsers
---


# Question
Title: Finding integer square root for large integers [find asymptotic time complexity]
So I found this tasks in one book I am practicing from where it says: "Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time complexity". Results can be in integer range. I am not sure which algorithm should I use, but I started with recursive method where I count the medium between two borders and go on until i find the perfect score, or if begin border becomes greater than the end one. What I have problem here is how to measure complexity for this problem and I am not even sure does this method count as divide-and-conquer?

# Answer
> 3 votes
Normally, you don't measure the complexity of a problem before designing an algorithm; instead, you measure the complexity of a particular algorithm. So, before you get to measuring complexity, the first step is to come up with a specific algorithm.

When you have a specific algorithm in mind, one technique that's useful for analyzing the running time of divide-and-conquer algorithms is to write down a recurrence relation characterizing its running time, and then solve the recurrence. You can often use the Master theorem to solve the recurrence.

To learn these techniques, see your favorite algorithms textbook, or read the following resources:

# Answer
> 0 votes
What you are describing is something related to binary search to find the square root but it does not look to me like divide and conquer, why?, you are choosing a half of the interval each time not merging the result of the recursive calls which is the "conquer" part. That said, there is a discussion about if binary search is divide and conquer or not here is a good discussion with links provided : https://stackoverflow.com/questions/8850447/why-is-binary-search-a-divide-and-conquer-algorithm

About the complexity: what you should do is to come up with a recurrence relation from the time your algorithm takes based on the steps In each case of the recursive calls, then you solve that equation usually with Master method (but is not always the case).

If you \**really \** want a divide and conquer with the "merge" part I suggest you to see the square root as an exponent and decompose it in subproblems and solve it, hint: if you multiply two powers with the same base how do you merge the exponents?. Nevertheless, it would be slower than the binary search approach.

---
Tags: complexity-theory, divide-and-conquer
---


# Question
Title: Shortest path algorithm using Dijkstra with Fibonacci heap
Given an undirected connected graph $G=(V,E)$ with positive weights, where $|V|\>2009$, and each vertex is of degree of at most $10$. Give an efficient algorithm to find the $2009$ closest nodes to a given source vertex $s$ (with respect to edge weight).

Is it correct to say that Dijkstra's algorithm with Fibonacci heap will run in $\mathcal O(\log V)$?

Reasoning: Dijkstra's algorithm with Fibonacci heap runs in $\mathcal O(E+V\log V)$. the amount of vertices pulled out of the heap is $2009$, and the amount of key decreased is at most $2009\*10$. Therfore the running time of Dijkstra's algorithm for this case is $\mathcal O(2009\*10+2009 \log V)=\mathcal O(\log V)$

# Answer
I do not think you can take $|V| = 2009$ because you are saying that $|V|\>2009$, which means that in the *best case* $V = 2010$ but it does not say anything about the **worst case** (which is what big oh notation is about). So you cannot say that $|V|$ is constant as is implied in your question.

The correct process would be this: $O(|E| + |V| log |V|) = O(|V|\*10 + |V| log |V|) = O(|V| + |V| log |V|)$
The only assumpution you can make is that $|E| = |V|\*10 = |V|$. Remeber that you should only get rid of a variable in asymptotic notation if it is equal to a constant.

You can safely assume that $|E| = |V|\*10$ because in the worst case every node will have 10 edges as stated in your question.

According to your reasoning dijkstra algorithm will only need overall 2009 extractions from the heap because you are looking for 2009 nodes close to $s$. That is not correct because is not possible in the algorithm to know beforehand which will be the exactly 2009 nodes that are close, say for example that the cheapest node $c$ has a shortest path of length $k$ and $k \> 2009$, where $k$ is the *number of nodes in the shortest path*. Dijkstra algorithm will need to transverse the previous nodes and that will require more than 2009 operations in the heap because you have to process the nodes to reach node $c$ first.

Example:

Suppose you do not want to find 2009 closest nodes but 4 and that our source vertex is $7$, so following your question there should be overall 4 operations to get the 4 closest nodes. Given the following graph:

When you start the algorithm node $7$ is pushed into the heap, then nodes $0,1,2,3$ are pushed, in this case the number of times the nodes are pushed is the same number of times the nodes are popped from the heap (which may not be the case), now, as the algorithm proceeeds it will push nodes $4$ and $5$ until it reaches $6$ which in fact, is the closest node to $s$, if the path to node $6$ would have been longer a bigger number of push/pops would have been done in the heap. In a extreme case between node $3$ and $6$ there may be 90 nodes so that number of operations must be done in order to reach node $6$ which totally exceeds $4$ which is what is stated in your question.

The assumption that for every node $i$ that is extracted from the heap after any node $x$ follows that $d(s,i) \> d(s,x)$ (where is $d(u,v)$ is the cost of the shortest path from $u$ to $v$) is not correct, because is possible that in the future you may insert another node into the heap that has a smaller distance, in fact that is what makes dijkstra algorithm actually compute optimal paths.
> 2 votes

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


# Question
Title: Algorithm for guessing a word in a dictionary with weighted operators
Suppose I am given a dictionary of words which contains no more than 100 words, and each word has a maximum length of 50 characters. I want to write a program to guess an unknown word, call it S, that is in the dictionary using 2 weighted operators:

* int getOccurrences(char x): return the frequency of the character 'x' in S. This operator costs 1 for each query.
* char getChar(int k): return the character at the position 'k' of S. If the length of S is less than k, it will return '#'. This operator costs 10 for each query.

(those functions will give me feedback when I call them)

It is preferred that the average cost to guess S is minimal.

I completely have no idea with this problem. My thought is that given a list of strings, which operator I should use to divide the set by half like in binary search, but I have no luck yet.

Thank you.

PS: Assume that the words in the dictionary are only containing a-z.

# Answer
> 2 votes
## A good heuristic: greedy choice

Here is a greedy algorithm. It might not be optimal, but I suspect will yield a solution that is good enough. It is basically an instantiation of your thought, but taking into account a bit of information theory. The idea will be to greedily choose which operator to query at each iteration; to tell which operator is best, we'll simulate all possibilities for the choice of operator and see which gives us the best gain.

Basically, we're building a decision tree on the fly, via greedy choice at each step.

Keep a set $T$ of all possibilities for the unknown word. (Initially this is $S$, but you'll narrow down the possibilities as you go.) In each iteration:

* For each possible operator $f$ you could possibly try, compute the "information gain" of using that operator, $$I(f) = H(X) - H(X | f(X)),$$ where $X$ is a random variable that is uniformly distributed on the current set $T$. This tells you the expected number of bits of reduction of the entropy -- roughly speaking, the reduction in uncertainty about the word.
* For each possible operator $f$, compute the cost of that operator, $\text{cost}(f)$. Also compute the gain-per-unit-cost, $I(f)/\text{cost}(f)$.
* Pick the operator $f$ with the largest value of $I(f)/\text{cost}(f)$, and query that operator. Use the response to reduce the set of possible words, i.e., remove from $T$ each word that is inconsistent with the response you got.

Repeat until you are left with only one possibility.

Notice that there are only $26+50=76$ different possible operators, so it is easy to enumerate over them all in each iteration. This algorithm will be pretty fast.

## Information gain

How do you compute the information gain of an operator $f$? Well, you know the set $T$. Also, given any word $w \in T$, you can compute the result $f(w)$ of applying $f$ to word $w$.

It's easy to compute the entropy $H(X)$: that is just $\lg |T|$. The entropy of a uniform distribution on some set is the base-2 logarithm of the size of that set.

To compute $H(X|f(X))$, we partition $T$ into subsets $T\_1,T\_2,\dots,T\_k$ according to what the operator returns (all word that return the same value in response to this operator are grouped into the same subset). Now $H(X|f(X)=y)$ is just $\lg |T\_i|$, where $T\_i$ is the subset corresponding to words that yield response $y$. The conditional entropy $H(X|f(X))$ is the average of $H(X|f(X)=y)$ over all possible values of $y$, weighted by the probability of getting $y$. Thus,

$$H(X|f(X)) = \sum\_i {|T\_i| \over |T|} \cdot \lg |T\_i|.$$

It follows that

$$I(f) = \lg |T| - \sum\_i {|T\_i| \over |T|} \cdot \lg |T\_i|.$$

## Optimal sequence

The algorithm above doesn't guarantee to output the optimal solution. What if we want the optimal sequence of queries? Well, basically this corresponds to building a decision tree, where each node of the tree applies one operator and then branches upon the result.

We can evaluate the "cost" of a decision tree according to the expected cost spent by the decision tree to narrow down the word to a single possibility, with the expectation taken over the random choice of the unknown word. Given a decision tree, it is easy to compute its expected cost. For each of the 100 words, you can simulate what path it will take through the decision tree and the total cost before it hits a leaf; averaging those 100 costs yields the expected cost.

You could now enumerate over all decision trees, and take the one whose expected cost is minimal. Of course, this will be highly inefficient, as there are exponentially many trees, but it does find the optimal solution.

It should be possible to make this more efficient using branch-and-bound. Explore the space of decision trees, by building them up in a top-down fashion (from the root downwards). At any point, you have a partial decision tree (the top of some decision tree, with bottom parts yet to be filled in).

You can get an upper bound for the cost of the best way to complete a partial decision tree to a full decision tree, by applying the greedy heuristic above to complete it to a tree and seeing what the result costs.

Also, you can get a lower bound as follows. Suppose we have any set $U$ of words. Find the letterx such that the number $b$ of different possible results of getOccurrences(x) \[taken over all words of $U$\] is as large as possible. Then the cost of any decision tree for $U$ will necessarily be at least $\lceil \log\_b U \rceil$. For each bottom node in a partial decision tree, find the set $U$ of words that reach that node, compute a lower bound on the cost of the best decision tree to put as a subtree of that node, and average these up over all the bottom nodes of the partial decision tree (together with the cost of reaching that node).

Now use these lower and upper bounds to prune your exploration, following standard branch-and-bound techniques: if the lower bound for a partial decision tree is at least as large as the expected cost of the best complete decision tree seen so far, then you can prune that partial decision tree (there is no need to explore any of the candidate ways to complete it to a complete decision tree).

Whether this algorithm will be efficient enough to use, I don't know. You could implement it and give it a try.

---
Tags: algorithms
---


# Question
Title: Proof that median of an array is the number that minimizes the sum of manhattan distance to all points
Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come up for a proof or explanation for the same ( i.e why its not mean).

Any help is highly appreciated.

# Answer
marks the set of numbers $$P=\\{P\_1,P\_2,P\_3, \ldots ,P\_n\\}$$

need to find number $X$:

$|P\_1-X|+|P\_2-X|+\ldots+|P\_n-X|=D$, which minimizes $D$.

the fact that X is the median can be shown using induction on the number of numbers n in $P$.

Base: $n=1$: trivial to see that the median is $P\_1$ and $|P\_1-P\_1|=D=0$ is minimal ($D\>=0$).

now suppose that this holds for all $P$ of size $|P|=n$, we need to show that this holds for $|P|=n+1$.

In other words:

given that $$|P\_1-X|+|P\_2-X|+\ldots+|P\_n-X|=D$$ is minimal when $X=P\_m$ is the median of $P=\\{P\_1,P\_2,P\_3, \ldots ,P\_n\\}$ show that $|P\_1-X|+|P\_2-X|+\ldots+|P\_n-X|=D$ is minimal when $X=P\_m'$ is the median of $P=\\{P\_1,P\_2,P\_3, \ldots ,P\_{n+1}\\}$. notice that there are two cases $m'=m+1$ ($n$ is even) or $m'=m$ ($n$ is odd).

I suggest drawing a simple example using $n=3$ and $n+1=4$ on an axis. Can you see why this must hold?
> 1 votes

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


# Question
Title: Algorithm for finding all the heaviest edges in a graph
We have a non directed, not necessarily connected graph $G=(V,E)$, that is represented by a adjacency list, and a weight function $w:E \to R$. All edges have distinct weight. An edge is "heavy" if there exists a simple cycle in $G$ that contains it, and it has the maximal weight in that cycle. The question is to give an algorithm which finds all of the heaviest edges in $G$.

My proposed algorithm:

1. Create an array $A$ of size $|V|$ where every cell represents a node $v\_i$ in G. Mark all nodes as 'unexplored'.
2. Select the node $v\_1$ in $G$ and run Prim's MST algorithm from it. Modify Prim's algorithm so that when a node is reached by the MST tree it is marked as 'explored' in $A$.
3. Scan the array $A$ linearly from the last node encountered as 'unexplored'. Each time a node marked 'unexplored' is found, do step 2 for it.
4. When $A$ is traversed completely, mark the group of all the edges in all the MSTs found as $E'$.
5. Return $E/E'$ — this is the group of heaviest edges.

The algorithm's correctness follows from the cycle property for MSTs, and that every edge has a distinct weight.

This algorithm is as efficient as running Prim's MST algorithm on a connected non directed graph — that is $O(E + V \lg V)$ with Fibonnaci heaps.

My questions is, is this is the optimal running time for this problem? I have a feeling this can somehow be done in linear time using DFS.

# Answer
In line with what Amir Nasr said in his comment above, I think the cycle property of MSTs would imply that finding a solution to your problem in linear time would find an MST in linear time.

From the Wikipedia page on MSTs and a few of the specific algorithms, it seems you can only currently do better be exploiting specific properties of your graph or using randomness.

You may find the $O(\left\vert{E}\right\vert\log{}\left\vert{V}\right\vert)$ complexity preferable to the $O(\left\vert{E}\right\vert+\left\vert{V}\right\vert\log{}\left\vert{V}\right\vert)$, and it seems that would just require a different choice of data structures or using either Kruskal's or Borůvka's.

For complexity with no $\log{}$ factors, it seems (for lack of a known general linear, deterministic, MST algorithm) you need either dense graphs, integer weights, or to use the expected linear time MST algorithm below.

https://en.wikipedia.org/wiki/Expected\_linear\_time\_MST\_algorithm
> 2 votes

---
Tags: algorithms, time-complexity, graph-traversal, minimum-spanning-tree
---


# Question
Title: How to label a video for supervised learning?
I have just started discovering the machine learning world! I found many tutorials showing how to deal with different types of data. I walked through some tensorFlow tutorials and I think they have very good way for showing how the (x, y) pair for supervised learning is "formed".

I was not able to find a way for representing the (x, y) pair for a video though. Are there any resources that can help me get started with labeling video sequences?

# Answer
Try Computer Vision Algorithms and Applications by Richard Szeliski and label propagation in video sequences.
To get a good grasp on the topic also Supervised Sequence Labeling with Recurrent Neural Networks. I proposed these resources as they cover the labeling, machine learning and are very in-depth materials (book, dissertation and the paper about propagating labels).

Video is the natural extension of the image, but to get fully working methods we also have to account for scene movement and changes. And I belive that in the video point is referenced by $x, y, t$.
> 1 votes

# Answer
This is studied in the computer vision world. Start by understanding how to do that for an image; then video is a straightforward extension of those techniques. So, read some good textbooks and tutorials on computer vision.
> 0 votes

---
Tags: reference-request, machine-learning, computer-vision, video
---


# Question
Title: The VC dimension when the samples are fixed
The VC dimension is usually used in the following way. There is a space of hypotheses. There is an unknown probability distribution. We sample some training-samples from this distribution. We find the hypothesis that scores best on the training-samples. If the VC dimension is sufficiently small and the number of samples is sufficiently large, then this best hypothesis will also perform probably-approximately-well on any set of test-samples drawn from the same distribution. Specifically, if the VC-dimension is $D$ and the number of samples is at least: $$ N := \Theta\bigg(\frac{D + \ln{1\over \delta}}{\epsilon}\bigg) $$ then, with probability at least $1-\delta$, the test-error will be at most $\epsilon$.

I am interested in the following alternative setting. Instead of a probability distribution, we have a ''fixed'' set of samples, determined by an adversary. We pick half of these samples at random, calculate the best hypothesis on this half, and then test it on the other half.

MY QUESTION IS: is it possible to use the VC dimension in the second setting? I.e, is there a formula, similar to the one above, that relates the total number of samples in the population, the probability of learning, and the learning error?

# Answer
Suppose were in the realizable model, i.e. we want to learn some $f^\*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$.

Let $M(\epsilon,\delta)$ be the minimal number of samples required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any distribution $\mathcal{D}$ over the sample space $\mathcal{X}$, we can treat this case as a uniform distribution with finite support $S=\left\\{a\_1,...,a\_n\right\\}$ (picked by the adversary). The learner picks a set $T\subseteq S$ of $n/2$ samples (chosen uniformly at random), and chooses any consistent hypothesis $h$ (relative to $T$).

There are two issues which prevent us from directly using the known bounds on $err(h)$.

The first is that we are only interested in the error on the set $S\setminus T$, i.e. the training and test samples are not independent. This will add an extra $2$ factor to the bounds on $err(h)$, since:

$err(h)=\Pr\_{x\sim\mathcal{D}}\left(h(x)\neq f^\*(x)\right)= \Pr\left(h(x)\neq f^\*(x) | x\in T\right)\Pr(x\in T)+\Pr\left(h(x)\neq f^\*(x) | x\notin T\right)\Pr(x\notin T)$.

In this case we have $\Pr(x\in T)=\Pr(x\notin T)=\frac{1}{2}$, and $\Pr\left(h(x)\neq f^\*(x) | x\in T\right)=0$ ($h$ is consistent with $T$). So we get $err(h)=\frac{1}{2}\Pr\left(h(x)\neq f^\*(x) | x\notin T\right)$, or equivalently $\Pr\left(h(x)\neq f^\*(x) | x\notin T\right)=2err(h)$, where the left hand side is the probability that we wish to bound.

The second issue is caused by the fact that we don't allow repetitions while picking $T$ (the usual model treats each training sample as chosen independently from the distribution $\mathcal{D}$). To avoid this issue, the learner could choose $T$ by taking $m$ independent samples form $\mathcal{D}$, such that with high probability we see at least $\frac{|S|}{2}$ samples. This can be easily done by picking $m\approx |S|$, and conditioning on the event that we saw at least half of $S$, we can use the regular bounds on $err(h)$ for sample size $\ge|S|/2$.
> 2 votes

---
Tags: learning-theory, vc-dimension
---


# Question
Title: How to convert CFG with Kleene Star, Kleene Plus, and Question Mark to Chomsky Normal Form?
I am fairly new to formal language theory but understand how to convert simple CFGs into both Chomsky normal form and Greibach normal form. However, I have not seen any examples of how to do that when you add the Kleene Star `*`, Kleene Plus `+`, and question mark `?` to that grammar, commonly seen in regular expressions.

How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

Say the grammar is like this:

```
S -> A+
A -> BX?
B -> a+ // letters
X -> ! // exclamation

```

How do you convert this to Chomsky Normal Form, given that it uses `*`, `+`, and `?`? In particular, I am wondering what the general pattern is to convert the Kleene Star/Plus and question mark to CNF, not necessarily how to do it in this example, but whichever is easiest to demonstrate.

Is it something like this?

```
// first step
S -> A+
A -> BX?
B -> a+
X -> !

// replace + with *
S -> AA*
A -> BX | B
B -> aa*
X -> !

// replace * with new rules and ɛ
S -> AI
I -> A | ɛ
A -> BX | B
B -> aJ
J -> a | ɛ
X -> !

// replace X -> aY with X -> ZY and Z -> a
S -> AI
I -> A | E
A -> BX | B
B -> KJ
J -> K | E
X -> !
K -> a
E -> ɛ

```

I am just guessing here, not sure how it is typically done. Also, from the few resources I have found, it sounds like you are supposed to also remove the epsilon rules somehow. There doesn't seem to be many thorough online resources demonstrating this though, any book recommendations?

# Answer
> 3 votes
> How do you do convert CFG's with Kleene Star/Plus, and question mark, to CNF?

I propose a two-step solution:

1. Convert your extra-notation-CFG to a normal CFG
2. Convert the normal CFG to CNF, e.g. as described on Wikipedia.

Do perform step 1, removing the extra notation, apply these rules:

1. Whenever $A^+$ occurs in a production rule, replace it with $AA^\*$.
2. Whenever $A^\*$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow AB$.
3. Whenever $A?$ occurs in a production rule, replace it with a new non-terminal $B$ and add rules $B \rightarrow \varepsilon$ and $B \rightarrow A$.

It should be relatively straightforward to see that the transformed versions of +,\*,? repeat the argument k times, where k is in $\\{1, \ldots\\}$, $\\{0, \ldots\\}$ and $\\{0, 1\\}$, respectively; i.e. the rewritten version has the same meaning (language) as the input.

To perform step 2, read the Wikipedia article; it is reasonably straightforward (if a bit tedious) to translate this into an algorithm.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Implementing Nesetril and Poljak's clique detection algorithm
I want to implement the clique detection algorithm by Nesetril and Poljak described in \[1\].

However, I can't seem to understand how the auxiliary graph $H$ is to be created and how it can be used to detect a clique. For instance, the paper suggests that to detect a clique of size $3\ell$ in a graph of size $n$, we construct an auxiliary graph $H$ of size $n^\ell$. For the detection of a clique of size $6$ in a graph $G$ of size $8$ for example, then the size of $H$ would be $64$ (i.e. $8^2$) and then checking for the presence of a triangle in $H$ which would indicate the presence of a clique of size $6$ in $G$.

Further down, while describing how to construct $H$, they stated that the vertex set of $H$ should be a subset of the vertices of $G$, and that the size of this subset is $\ell$. This is the first conflict. The second conflict is in the construction of the edge set. What is meant by $Y'$ in this sentence: $E(H)=\\{ \\{Y,Y'\\} ; Y \neq Y' \text{ and } Y \cup Y' \text{ forms a complete subgraph in } G \\}.$

The paper did not at any point after this sentence define what $Y'$ was.

Any explanation will be appreciated.

---

\[1\] J. Nešetril, S. Poljak, On the complexity of the subgraph problem, Comment.Math. Univ. Carolinae 14 (1985) 415–419.

# Answer
> 3 votes
The high-level idea is this: the existence of a triangle in $H$ corresponds to the existence of a clique of size $3\ell$ in $G$, and we know how to detect triangles using matrix multiplication.

So let $\ell$ indeed be divisible by three. The auxiliary graph $H$ has a vertex for every $K\_\ell$, and an edge between two vertices precisely when the corresponding vertices form a $K\_{2\ell}$. Then $G$ has a $K\_{3\ell}$ iff $H$ contains a triangle.

> **Example:** Suppose we wish to find cliques of size 6 from a given graph $G$. The trivial algorithm that checks all 6-sets of $V(G)$ runs in time $\Theta(n^6)$. Let's see how we can improve on this.
>
> Observe that $\ell = 2$, i.e., we are looking for cliques of size $3\ell = 6$. To build $V(H)$, we check all 2-sets in $O(n^2)$ time (but of course now the $K\_2$'s are precisely the edges of $G$). Similarly to build $E(H)$, we spend $O(n^4)$ time. The graph $H$ has $\Theta(n^\ell)$ vertices, so a triangle can be detected in time $O(n^{\omega \cdot \ell})$ in it, where $\omega \< 2.376$ is the exponent of matrix multiplication. In our case, this simplifies to $O(n^{4.752})$ time, beating the naive brute-force algorithm above.

---
Tags: graphs, clique
---


# Question
Title: Which of the following regular expressions generate(s) no string with two consecutive 1’s?
This is a GRE practice question.

Which of the following regular expressions generate(s) no string with two consecutive 1’s? (Note that ε denotes the empty string.)

I. (1 + ε)(01 + 0)\*

II. (01+10)\*

III. (0+1)\*(0+ε)

(A) I only

(B) II only

(C) III only

(D) I and II only

(E) II and III only

My understanding is that neither I nor III generates strings with `11`. In I, a string containing `1` is either `1` or `1` surrounded by `0`'s. In III, all `1`'s are preceded by `0`'s. But the correct answer is A, so III must generate a string with `11` somehow. Please explain. Thanks!

# Answer
> 6 votes
III is $(0+1)^\* (0+ \epsilon)$ which means pick a word from $\Sigma^\*$ where $\Sigma = \\{0, 1 \\}$ and then concatenate it with either $0$ or $\epsilon$.

so III Does generate a string with two consecutive $1$'s. In fact it generates every string which contains $1$'s, $0$'s or is empty.

# Answer
> -1 votes
A is correct only. In II:0110 string present which has two consecutive 11 In III also 11 contain from (0+1)\* expression...

---
Tags: regular-expressions
---


# Question
Title: Does a given e-NFA accepts all the Strings?
Given an e-NFA. It is easy to find a string that is accepted by it. But, how do we find if the given e-NFA accepts "All" the strings over the alphabet. Or if there is a string that is not accepted by it.

Of course the usual way is to construct a DFA, or complement the e-NFA but since we are talking about the whole language, I was wondering if there is a much more efficent method in the worst case.

# Answer
> 2 votes
A classical result, attributed to Meyer and Stockmeyer, is that checking whether an NFA accepts all strings is PSPACE-complete. Nevertheless, there are some non-trivial heuristic algorithms. See for example Antichains: A New Algorithm for Checking Universality of Finite Automata by De Wulf, Doyen, Henzinger and Raskin.

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


# Question
Title: Solving Recurrence Relation (quicksort )
I know quicksort to have a runtime of $\mathcal{O}(n \log\_2 n)$

However trying to solve for it I get something different and I am not sure why that is.

Ok, so solving recurrence relations can be done several different ways.

The recurrence relation for quicksort is:

$$T(n) = 2 T(\frac{n}{2}) + \mathcal{O}(n)$$

Reinserting a few times we get:

$$T(n) = 2 \left\[ 2 T(\frac{n}{4}) + \mathcal{O}(\frac{n}{2}) \right\] + \mathcal{O}(n)$$

$$T(n) = 2 \left\[ 2 \left\[ 2 T(\frac{n}{8}) + \mathcal{O}(\frac{n}{4}) \right\] + \mathcal{O}(\frac{n}{2}) \right\] + \mathcal{O}(n)$$

$$...$$

Which can be generalised to:

$$T(n) = 2^kT(\frac{n}{2^k})+\sum\_{i=0}^{k-1} \mathcal{O}(\frac{n}{2^i})$$

Now the sum can be solved like this:

$$\sum\_{i=0}^{k-1} \mathcal{O}\left(\frac{n}{2^i}\right) = \sum\_{i=0}^{k-1} \mathcal{O}\left(n\left(\frac{1}{2}\right)^i\right) = \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}$$

$$\lim\_{k \to \infty} \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}} = \frac{n}{1 - \frac{1}{2}} = 2n$$

So the recurrence can be simplified accordingly:

$$T(n) = 2^kT(\frac{n}{2^k})+2n$$

Assuming $T(1) = C$ we get $$T(n) = 2^{\log\_2 n}T(\frac{n}{2^{\log\_2 n}})+2n = n C + 2n$$

And $ n C + 2n \not \in \mathcal{O}(n \log\_2 n)$

Can somebody explain my error to me?

# Answer
Your mistake is $2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace $\mathcal{O}(n)$ with $An$ for some constant $A$, which can be taken as $1$ without loss of generality. Then we have $$ \begin{align\*} T(n) &\leq 2T\left(\frac{n}{2}\right) + n \\ &\leq 4T\left(\frac{n}{4}\right) + 2 \frac{n}{2} + n \\ &\leq 8T\left(\frac{n}{8}\right) + 4 \frac{n}{4} + 2 \frac{n}{2} + n \\ &\leq \dots \end{align\*} $$ More generally, we get $$ T(n) \leq 2^k T\left(\frac{n}{2^k}\right) + kn. $$ Assuming $n = 2^k$ and $T(1) = C$, this gives $$ T(n) \leq 2^kC + k2^k = \mathcal{O}(n\log n). $$ You can get a lower bound in exactly the same way.
> 5 votes

---
Tags: recurrence-relation, quicksort
---


# Question
Title: L contains the concatenations of all k-bit long strings. Why is it decided in PSPACE(loglogn)?
(This exercise is from Computation Complexity: A Conceptual Perspective by Oded Goldreich):

*For any k* $\in \mathbb{N}$, *let* $w\_k$ *denote the concatenation of all k-bit long strings (in lexicographic order) separated by* \*'s *(i.e, $w\_k = 0^{k-2}00\*0^{k-2}01\*0^{k-2}10\*...\*1^k$). Show that the set $S = \\{w\_k:k\in\mathbb{N}\\} \subset \\{0,1,\*\\}$ is decidable in double-logarithmic space.*

The basic idea of the solution, if my understanding of it is correct, is:

1. iterate from i to k until the structure of the input suits some $w\_k$, for example $\\{0,1\\}^k\*\\{0,1\\}^k\*...\*\\{0,1\\}^k$.
2. For each pair of adjacent binary numbers, make sure $b\_{i+1} = b\_i + 1$

According to the guideline in the book, step 2 takes space $O(log(k))$.

Why do I need $log(k)$ space to check if $b\_{i+1} = b\_i + 1$? Can't it be done in constant space?

# Answer
Try to implement it in constant space to see what goes wrong. You need to be able to count up to $k$, which takes $O(\log k)$ space.

More formally, consider the language $$L = \\{a\ast b : a,b \in \\{0,1\\}^k, b=a+1\\}.$$ This is not a regular language, and so cannot be decided in constant space.
> 2 votes

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


# Question
Title: Subset sum-like problem over boolean vectors
I'm interested in finding maximal solutions to the problem of finding a subset that "sums" to a specific value. The elements of the set are boolean vectors and the notion of "sum" is point-wise or.

Say you had {10, 01, 00} then there are two subsets that sum to 11: {10, 01} and {10, 01, 00}.

In particular, I want maximal solutions. So I don't care about {10, 01} if {10, 01, 00} is a solution, because {10, 01, 00} contains {10, 01}.

What algorithms are known for how to do this? Can you think of an algorithm? One way to do this would be to use the dynamic programming solution mentioned on Wikipedia (modifying it to store maximal sets of subsets rather than true/false): *Pseudo-polynomial time dynamic programming solution*

Is there something that beats this due to using vectors rather than integers? Or is this doomed to be just as inefficient?

# Answer
> 7 votes
Let us say that $x \leq y$ if $x\_i \leq y\_i$ for all $i$. Suppose that your starting vectors are $x\_1,\ldots,x\_n$ and your target is $y$. If $x\_i \not\leq y$ then $x\_i$ cannot belong to any solution, so you can throw away all these vectors. The remaining vectors OR together to a vector $x \leq y$. If $x \neq y$ then there is no solution. Otherwise, take all remaining vectors – this is clearly the maximal solution.

---
Tags: algorithms, reference-request
---


# Question
Title: Why update weights and biases after training a Neural Network on whole set of training samples
I am reading the book *Neural Networks and Deep Learning* by Micheal Nielsen. In the second chapter of his book, he describes the following algorithm for updating weights and biases for a neural network:

In the 2nd step, the algorithm computes the error for a sample and backpropogates it through the layers. This happens for all of the training samples (please correct me if I am wrong because this is what I assume is going on). Then in the 3rd step, the weights and biases are updated. My question is, why does the algorithm wait until the third step to update the weights and biases. That is, why can't it do it after each training sample instead of after a whole set of training samples?

Thank you so much for your help and I appreciate it.

# Answer
> 4 votes
You are right. While you *could* backpropagate for all samples and *then* update the weights, you don't have to. Alternatively, you can iterate through the samples and, for each sample, backpropagate for just that sample and then update the weights.

The latter turns out to be more effective (empirically). It is called stochastic gradient descent. Today, most neural networks are trained using stochastic gradient descent, because it reaches convergence faster than the alternative. This makes neural networks faster to train.

Anyway, you *could* do it either way. Both ways are valid. The stochastic gradient descent approach seems to be faster in practice, but neither one is wrong.

Why did the book describe it this way? That's a pedagogical choice. The author might have considered it more natural or easier to explain this way.

---
Tags: neural-networks, gradient-descent
---


# Question
Title: Using oracle machine to speed up tree solution search
Let $P$ be a boolean problem of size $n$, thus the complete solution search space tree is of size $2^n$. Applying simple tree search for the solution will have take $O(2^n)$ operations, (for simplicity let's assume we do not apply any cuts).

Let $M$ be an *oracle machine* able to solve a problem $P^\prime$ sub-problem of $P$ of size $k \< n$ in time $O(1)$

Is there a **known** approach of applying $M$ during searching for solution of $P$ in order to find it in time $O(2^{n-k})$? If speed-up of factor $O(2^k)$ is not possible, what is the best known achievable result for such problem? Are oracle machines limited to problem size $k$ useful at all to solve problems of size $n \> k$?

Possible application of such approach could be solving NP-Complete problems using a quantum computer that is limited to $k$ cubits as oracle machine. Of course it wouldn't solve sub-problem in time of $O(1)$ but it is just for theoretical simplification.

This question was inspired by *branch and price* algorithm for integer programming, but instead of generating columns, at each node an technically advanced problem solving machine could be applied as an oracle.

# Answer
> 0 votes
### Remarks

Concept of *oracle machine* has been misunderstood in this question. I should have used term a *black-box* machine. An *oracle* does not provide association of values to variables, only *yes* or *no* answer which is used for *self-reducible* problems, which allows to find association of values in *polynomial time*.

### Solution

Such *black-box* machine would work but is not possible to be constructed for all the problems, does not work in general case.

Every time our *black-box* provides us with solution to a sub-problem of size $k$ it should modify the instance of the problem to **forbid** this solution in future runs, otherwise it will loop. For some of the problems such us *independent set problem* this cannot be done without adding additional variables. Since in worst case scenario there is $O(2^k)$ partial solutions, problem size may grow exponentially making it not solvable.

This is the case of *independent set problem* but not *boolean satisfiability problem* since partial solutions can be forbidden by adding additional *clauses*, not *variables*.

### Other answers

@D.W made a good point and good argument, unfortunately it does not work in general case as explained earlier.

# Answer
> 2 votes
Here is an algorithm that will work in some cases: guess the first $n-k$ bits of the solution; fix them; and then solve the sub-problem where you ask what the remaining $k$ bits are. In other words, iterate over all $2^{n-k}$ possibilities for the first $n-k$ bits, and for each such choice, use your oracle to find the remaining $k$ bits.

This works assuming fixing some bits of the problem leads to a sub-problem of the sort that can be solved by your oracle.

---

(I'm also assuming you can verify whether a candidate solution is correct in $O(1)$ time, you can find a correct solution in $O(2^{n-k})$ steps. This seems to be required to achieve your $O(2^n)$ running time for tree search. If the problem is in NP, then there's a way to verify in polynomial time, so instead of $O(2^{n-k})$ you have $O(2^{n-k} \cdot \text{poly}(n))$.)

---
Tags: complexity-theory, decision-problem, oracle-machines
---


# Question
Title: Compact, reversible mapping from set partitions of length k to integers
Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\left\[0, {n \brace k}\right)$.

Ideally this mapping and its inverse would be easy to compute.

# Answer
The idea is to use the recurrence $$ \newcommand{\stirling}{\genfrac{\\{}{\\}}{0pt}{}} \stirling{n}{k} = k \stirling{n-1}{k} + \stirling{n-1}{k-1}. $$ This recurrence holds since either element $n$ belongs to one of the $k$ partitions of a partition of $1,\ldots,n-1$ into $k$ parts (say, ordered by minimal element), or it forms a singleton partition, joining a partition of $1,\ldots,n-1$ into $k-1$ parts.

Accordingly, partition the range $\[0,\stirling{n}{k})$ into $k$ parts of length $\stirling{n-1}{k}$ and one of length $\stirling{n-1}{k-1}$. Given a partition, determine which of the $k+1$ intervals you belong to, remove $n$, encode the remaining partition of $n-1$ recursively, and locate it inside the chosen interval. The base cases are $\stirling{0}{0} = 1$ and $\stirling{n}{0} = \stirling{0}{n} = 0$ for $n \> 0$.

The same algorithm can be reversed and be used to decode a number in $\[0,\stirling{n}{k})$ into a partition of $1,\ldots,n$ into $k$ parts.
> 2 votes

---
Tags: combinatorics, sets, partition-problem
---


title: Quick way to do bit AND mapping

text:
# Question
Title: Quick way to do bit AND mapping
By writing out a number in binary I can arrive at the value of taking the first x number of bits out of it.

```
For example 00001101 (13) taking the first 6 bit would be 3
                          taking the first 5 bit would be 1
                          taking the first 4 bit would be 0 etc

```

This results, I can easily compute by spelling out the bits that makes up the number I am operating on, take the first couple of bits I am interested in and convert to binary.

I was wondering if there is any common short hand step which allows the same operation to be done, but in decimals (more like how we can do addition on decimals by carrying digits over) where I can use it to calculate what the result of taking the first x bits from a value y would be without having to mentally convert to a binary representation.

# Answer
If your number $x$ is $n$ bit long, the number formed by the first $k$ is $x/2^{n-k}$, rounded down. The number formed by the last $k$ is the remainder in that division.
> 1 votes

# Answer
You should observe that the meaning of "the first six bits" depends on your assumptions. The binary numbers 0000 1101 and 0000 0000 0000 1101 are exactly the same, so their "first six bits" should be also the same - which means "first six bits" doesn't really make sense. What you actually mean is the bits from bit 2 to bit 7, with bit 0 being the bit with the lowest value.

Most programming languages have one or more "shift" operators which move bits into other positions, and bit operations like and, or, not, xor which perform common operations on bits.

And integers are not decimal or binary. Integers are integers. Decimal, binary, octal, hexadecimal, hexagesimal or whatever are just the way we write these numbers down.
> 1 votes

---
Tags: arithmetic
---


# Question
Title: Prove that $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ with $M'$ a TM that always halt is undecidable
I've done some other problems by reduction, but I'm quite stuck here. I'm not really sure what to do with $M'$. I know that because $L(M) \nsubseteq L(M')$ there exists $w \in L(M)$ and $w \notin L(M')$ and I'm trying to create the machine that ignores the input and accepts only when M accepts $w$, but I'm kinda stuck on what to do next. Any suggestions?

# Answer
> 1 votes
Don't be confused by this question. Instead of studying $L^{\nsubseteq}\_{M'}=\\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\\}$ you might consider as well the language $L\_G=\\{ \langle M \rangle \ | \ L(M) \nsubseteq G\\}$ for $G$ being any language. It is important to notice that there is always a Turing machines $M$ with $\langle M \rangle \in L\_G$ but always a machine $M'$ with $\langle M' \rangle \not \in L\_G$. So you are looking for a *nontrivial* set of Turing machines. This allows you to apply Rice's theorem and you are done.

If you want to get a proof via reduction just look in the proof of Rice's theorem. It shows you how to get a generic reduction for these cases.

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


title: AVL Tree Height

text:
# Question
Title: AVL Tree Height
What is the height of an AVL Tree? I keep finding contradicting definitions.

I found these two on wiki:

**Height of node**: The height of a node is the number of edges on the longest path between that node and a leaf.

**Height of tree**: The height of a tree is the height of its root node.

But then I find examples like this: http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/avl1.png

In my course, in the lecture notes it uses the height in the way the above picture does. But then in the course textbook it uses the height in the same way the google definition does. So, honestly, I'm not sure which way is correct. What would an AVL tree, of height 5 for example, look like?

# Answer
> 2 votes
You can use either definition of height, so long as you are consistent in which one you use. The difference between the definitions is presumably just an additive factor $1$ (since one definition counts edges and the other appears to count nodes), which is irrelevant for most CS purposes. There is no "correct" definitions as different authors have come up with and used their own definitions.

Of course, it is possible that your course instructor (if you are taking a course) expects you to use a particular definition but the only way to find out which one to use is to ask them (or pay attention to which one they use in their lectures).

---
Tags: data-structures, trees
---


title: Reducing MAX-2SAT to Vertex Cover?

text:
# Question
Title: Reducing MAX-2SAT to Vertex Cover?
In A simplified NP-complete MAXSAT problem, a reduction is given from Min Vertex Cover to MAX-2SAT by replacing each each vertex $x\_i$ by a single-variable clause, and each edge by a two-variable clause:

\begin{align} \Phi = \left(\bigwedge\_{i=1}^n x\_i\right) \wedge \left(\bigwedge\_{\lbrace i,j\rbrace \in E} (\overline{x}\_i \vee \overline{x}\_j)\right) \end{align}

This basically makes sense to me, because the QUBO version of Vertex Cover is to maximize: \begin{align} L = \sum\_{i=1}^N x\_i - \sum\_{\lbrace i,j\rbrace \in E} x\_ix\_i \end{align} and QUBO can be converted to MAX-2SAT quite simply.

However, I would to know how the reverse transformation works.

How do you go from MAX-2SAT to Vertex Cover?

I don't actually know if this is an unsolved problem or not, but I figure it shouldn't be since they are both NP-Complete. Would it be as simple/tedious as trying to force an arbitrary MAX-2SAT instance into the same form as $\Phi$? I don't know if that can be done though.

# Answer
> 2 votes
You can reduce MAX-2SAT to Satisfiability (using Cook-Levin), which can then be reduced to Vertex Cover (Folklore).

---
Tags: complexity-theory, reductions, satisfiability
---


# Question
Title: Understanding non-faulting and faulting software prefetches
What is the difference between a faulting and non-faulting software prefetch. I have read some material in Google but can't understand it deeply. How do we know if a software prefetch is faulting or non-faulting in practice?

# Answer
> 5 votes
A faulting prefetch is one which (as gnasher729's answer notes) generates any translation (e.g., invalid page table entry), permission, or other fault (e.g., ECC failure, data watchpoint match) associated with the access. Such a prefetch acts as if the memory location was accessed normally. For data accesses such a prefetch can be provided by software on architectures that lack prefetch instructions. (For instruction accesses, a return operation would need to be placed in the cache block reducing the amount of useful code that would fit in the block.)

By acting as a normal access, a faulting prefetch effectively guarantees that the chunk of memory will be cached (a non-faulting prefetch may be dropped under high memory use or even a TLB miss) and that its address translation will be cached. This behavior may be preferred if the address is known to be accessed in the near future, especially if a timing critical section is about to be entered.

In some RISC ISAs, a faulting data read prefetch could be provided by a simple load to the zero register. Other ISAs could preform a normal load at the cost of temporary use of a register.

Non-faulting prefetches are purely hints to hardware, allowing hardware to drop the access if it is perceived as too expensive. By avoiding faults, such prefetches can be used without concern about whether the address is valid; prefetching from a null pointer or past the end of an array is safe. A non-faulting prefetch is purely speculative. (Some ISAs provide support for speculative, non-faulting loads. In such an ISA, non-faulting prefetches could be implemented using such a load. Since the speculative load value may be used, hardware will typically treat such as an actual access and merely suppress any exceptions.)

# Answer
> 4 votes
It's unclear what you mean.

A prefetch is faulting exactly when the actual access to the same data would be faulting.

On the other hand, hardware that allows pre-fetches might not actually implement the faults, but only fault if there is an actual access. This is very useful if the official semantics of the prefetch is "no operation", allowing prefetches for example to go beyond the address space of a process without negative side effects, where an actual access would crash the process. So "faulting" vs. "non faulting" could mean that a prefetch will fault just as an access would fault, or not.

---
Tags: computer-architecture, virtual-memory, memory-access
---


# Question
Title: A question on the linear speedup theorem
I am trying to understand the linear speedup theorem:

Let $L$ be a decidable language. Let $X^L$ be the set of all deterministic Turing machines which decide $L$. For a word $x \in \Sigma^\*$ define: $t^L(x) := \min\_{M \in X^L} t\_M(x)$ where $t\_M(x)$ is the time of $M$ on input $x$. Now let's choose some machine $M$ which satisfies $t^L(x) = t\_M(x)$. Then for all $A \in X^L$ we have:

$$t\_M(x) \le t\_A(x)\\,.\qquad(\**)$$

Now let's apply the linear speedup theorem for the machine $M$: We get a new machine $N$ such that:

$$t\_N(x) \le t\_M(x)/2 + |x| + 2\\,.$$

But by (\**) we have: $t\_M(x) \le t\_N(x)$ hence it follows, that $t\_M(x) \le t\_N(x) \le t\_M(x)/2 + |x| + 2$. From this it follows that $t\_M(x) \le 2 |x| + 4$.

But how can this be? It means that, for every word $x \in \Sigma^\*$ there exists a deterministic Turing machine $M$ which decides $L$ such that the time of $M$ on input $x$ is at most $2|x| + 4$.

This seems very absurd. What am I doing wrong?

# Answer
I didn't check your working but your conclusion isn't at all absurd. For every Turing machine that decides $L$, and for every $x\in\Sigma^\*$, there is another Turing machine $M\_x$ that decides $L$ and that runs for exactly $|x|+1$ steps on input $x$. Note that this is more than twice as fast as your conclusion of $2|x|+4$. This also means that, for all languages $L$ and all strings $x\in\Sigma^\*$, $t^L(x)=|x|+1$.

$M\_x$ operates as follows. First, it reads the first $|x|+1$ characters of the input. If these are the string $x$ followed by a blank, it accepts if $x\in L$ and rejects if $x\notin L$; if they are not $x$ plus a blank, it returns to the left-hand end of the tape and does whatever $M$ would do. Note that $M\_x$ does not need to contain any algorithm to decide whether $x\in L$. If $x\in L$, the machine is programmed "If my input is $x$, accept it; otherwise, rewind and do what $M$ would do.", and if $x\notin L$, the machine is programmed "If my input is $x$, reject it; otherwise, rewind and do what $M$ would do."
> 1 votes

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


# Question
Title: Is there an example of an oracle A such that P = NP but $\mathsf{P}^A\neq\mathsf{NP}^A$?
The question is stated in the title, I would like to see a counter example if there is any. Thanks.

# Answer
Jonathan Katz explains the original construction due to Baker, Gill and Solovay in his lecture notes.

The idea is to construct such a language by diagonalization. The first step is to show the lemma that for any deterministic, polynomial-time oracle machine $M$, you can construct a language $B$ so that $M^B$ (that is, $M$ with oracle access to $B$) does not decide the language $L\_B = \\{1^n\textrm{ | }B \textrm{ contains a string of length } n\\}$. For sufficiently large $n$, $M$ can not query all strings of length $n$ of $B$, so it is possible to "hide" (or not) a string of length $n$ in $B$ so that $M$ gives the wrong answer.

Note that $L\_B$ is in $NP$ since for a given $n$ we can guess the string of length $n$ (if any) that is in $B$ and then query the oracle once.

This doesn't give the desired result (it says that for any deterministic, polynomial-time TM there is a language rather than for any language there is a TM). However, we can enumerate all deterministic, polynomial Turing oracle machines $M\_1,M\_2,M\_3,\ldots$. We can (by the lemma) construct a language $B\_1$ for which $M\_1^{B\_1}$ fails to decide $B\_1$. Using a construction similar to in the lemma, we can then modify $B\_1$ to obtain $B\_2$ so that both $M\_1^{B\_2}$ and $M\_2^{B\_2}$ fail to decide $B\_2$, and so on...

We eventually obtain a language $B\_{\infty}$ so that $L\_{B\_{\infty}}$ is in $NP^{B\_{\infty}}$, but not in $P^{B\_{\infty}}$
> 3 votes

---
Tags: np, polynomial-time, oracle-machines
---


# Question
Title: On maximum independent set of line graphs
Are there any special algorithms for maximum independent set of line graphs? Could this special case be in $\mathsf{P}$?

# Answer
> 3 votes
Finding a maximum independent set in $L(G)$ is equivalent to finding a maximum matching in $G$. For more, and a fast polynomial-time algorithm that work for e.g., line graphs, see \[1\].

---

\[1\] Lozin, V.V. and Milanič, M., 2008. On finding augmenting graphs. Discrete Applied Mathematics, 156(13), pp.2517-2529.

---
Tags: algorithms, complexity-theory, graphs, polynomial-time
---


# Question
Title: Fastest way to compute a path from a known cycle with unordered edges and vertices
I have an (undirected) graph isomorphic to $C\_n$ with unordered edges/vertices in some data structure (in particular, a list of tuples representing the edges), etc. I was wondering what is the fastest algorithm to compute a path which begins and ends at some given node in the cycle, given this set of nodes? The simplest thing seems to be to just use DFS, but that seems like overkill for what I'm sure is a relatively simple algorithm.

# Answer
> -1 votes
I understand your question this way:

There is given a graph with nodes and edges. There might or might not be one or more circles in that graph. And there is given a certain start-node within the set of nodes.

You ask, if this start-node is part of at least one circle, and you ask, which nodes (of which one is the given start-node) and edges form the smallest circle.

If this was your question, then I have an answer:

DFS is not the best choice. BFS is. BFS = Breadth-first-search. There is an wikipedia-article that describes this algorithm.

The idea of this algorithm is to begin to test all nodes at the end of the edges that are directly connected with the given node. This gives you a list of all direct neighboring nodes of the start-node. I call them the level-1-neighbors.

In the next step you repeat this search for each level-1-neighbors, but now you ignore all edges that directly lead back to where you did come from. The result are the level-2-neighbors. And then you repeat this for the level-n-neighbors to get the level-(n+1)-neighbors.

This transforms your graph into a new graph, which is a tree. The start-node is the root of this tree, the level-1-neighbors are the roots children, level2-neighbors are children of those children.

If your original graph contains a circle, then nodes will appear twice (or more often) in the resulting tree, because there are (at least) two different ways, that you can move through the circle to reach nodes in the circle (clockwise and counter-clockwise).

So, if a certain node appears a second time in the graph, then you have found a circle. The circle is the path starting at one representation of that node, going up till you reach the first common ancestor of both representations and then go down to the second representation.

If the common ancestor is the root node, you found the circle with the least number of nodes that goes through the given node. If the common ancestor is not the root, then you just have found a circle, that is connected with the given node by a side-arm. In this case you must go on searching.

There is an easier (but longer) algorithm for the case that there are directed edges: Use BFS until you hit the start-node for a second time. Then the path from the root to the second representation of the start-node is the shortest circle. This is simpler (you need not compare every new node with any node you already passed, but only with the root), but probably needs more resources because the tree you have to build will be deeper.

In both versions of the algorithm you must pay attention not to get lost in loops (again and again walking through circles that are not the needed circle)

---
Tags: algorithms, graphs
---


title: Conditions for LL(1) grammar

text:
# Question
Title: Conditions for LL(1) grammar
One of the conditions for A → α | β to be LL(1) grammar states that

> If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one or more steps then β doesn't derive any string beginning with a terminal in FOLLOW(A).

I couldn't understand what is the intuitive meaning of this condition and why this condition should hold? I could easily understand if an example is provided for the answer.

# Answer
Considering the above condition, should α derive a string beginning with a terminal in FOLLOW(A), then it becomes impossible to determine which derivation will be used to produce this symbol with lookahead limited to one symbol.

For instance, should $\mathrm{s}$ be the symbol that is both on FIRST(α) and FOLLOW(A), and $x$ the leftmost substring already parsed, then the following sequences are both possible:

$xA$ω $ \Rightarrow x$βω $ \Rightarrow^\* x$ω $ \Rightarrow^\* x\mathrm{s}$…

$xA$ω $ \Rightarrow x$αω $ \Rightarrow^\* x\mathrm{s}$…ω

Even if the grammar is not ambiguous, you can't decide which path to take by reading just $\mathrm{s}$.
> 3 votes

---
Tags: formal-grammars, parsers, ll-k
---


# Question
Title: Formal notations of equivalencence between floating point expressions
In an informal context, most programmers might call these two expressions "equal" and no one would be mislead:

```
(a + b) + c
a + (b + c)

```

For floating point numbers, we know that these two expressions are not strictly equivalent (in the sense that they evaluate to equal values for any a, b, and c) because floating point addition is not associative. Nonetheless, these expressions seem to be similar in interesting and useful ways. For many inputs, these expressions produce nearly equal or equal outputs. The real number counterparts of these expressions are equivalent. In many programming contexts, these expressions can be swapped without concern.

Are there notions of equivalence between floating point expressions that describe this sort of similarity?

Stating simply that the real number counterparts of these expressions are equivalent is a bit too literal to be a useful answer.

# Answer
One plausible notion of "nearly-equivalent" for floating-point expressions is that the relative error between the two is guaranteed small.

For example, if $x\ne 0$ and $y\ne 0$, define

$$D(x,y) = \max(\left|{x \over y} - 1\right|, \left|{y \over x} - 1\right|).$$

This measures the relative error between two real numbers. Now, say that $x$ is nearly equivalent to $y$ if $D(x,y) \le \varepsilon$ (for some $\varepsilon$ fixed in advance; e.g., $\varepsilon = 10^{-6}$ or something).

Now, we can define two floating-point expressions `e`, `e'` to be nearly-equivalent if, for all possible assignments to the variables of these expressions, we have $D(e,e') \le \varepsilon$.

This implies that replacing `e` with `e'` will have only a small effect on the value of the expression (with "small" measured using relative error, rather than absolute error).

With these definitions, if you know that `a`, `b`, and `c` are positive and bounded away from zero, you should be able to prove that `(a+b)+c` and `a+(b+c)` are nearly-equivalent, for very small values of $\varepsilon$ (dependent on machine epsilon and the specific floating-point format used). However, you can't prove them nearly-equivalent when nothing is known about `a`, `b`, `c`, because it is possible that `(a+b)+c = 0` but `a+(b+c) > 0`, and then the relative error is infinite in this case.

Perhaps a more nuanced definition could allow them to be treated as nearly equivalent in the general case; I don't know. For instance, we could alternatively imagine defining $D(x,y)$ to be the smallest value $\delta\>0$ such that $$\begin{align\*} (1-\delta) x - \delta &\le y \le (1+\delta) x + \delta\\ (1-\delta) y - \delta &\le x \le (1+\delta) y + \delta \end{align\*}$$ (This effectively captures a combination of relative error and absolute error.) I suspect it might be possible to prove that `(a+b)+c` and `a+(b+c)` are nearly-equivalent, under this distance metric. Is this useful? I don't know.
> 2 votes

---
Tags: notation, floating-point
---


# Question
Title: Uniformly sampling from cycles of a graph
I was wondering if, given an arbitrary cycle basis (that's complete, e.g. every cycle in the graph can be expressed as the $\mathbb{Z}/2\mathbb{Z}$ sum of elements from the basis) of some graph $G$, is there some way of sampling all cycles uniformly? I'm not able to find papers on it, and I was wondering if anyone had any results on this.

# Answer
## Exponential-time algorithm

One (slow) approach is to rejection sampling.

Let $c\_1,\dots,c\_k$ be the cycle basis. Then we obtain an isomorphism $\varphi : (\mathbb{Z}/2\mathbb{Z})^k \to \mathcal{E}$, where $\mathcal{E}$ is the set of Eulerian subgraphs of $G$, given by

$$\varphi(\alpha\_1,\dots,\alpha\_k) = \alpha\_1 \cdot c\_1 + \cdots + \alpha\_k \cdot c\_k.$$

This gives us a way to sample uniformly at random from the set of Eulerian subgraphs.

Note that the set $\mathcal{C}$ of simple cycles of $G$. Note that every simple cycle is an Eulerian subgraph, i.e., $\mathcal{C} \subseteq \mathcal{S}$. Thus, a simple procedure to sample uniformly at random from $\mathcal{C}$ is:

1. Sample uniformly at random from $\mathcal{E}$, to get a subgraph $e$. (Namely, pick $\alpha\_1,\dots,\alpha\_k$ uniformly at random and set $e = \varphi(\alpha\_1,\dots,\alpha\_k)$.)
2. If $e$ is a simple cycle, output it. Otherwise, go back to step 1.

This samples a simple cycle uniformly at random from the set of all simple cycles of $G$.

The (expected) running time is proportional to $|\mathcal{E}|/|\mathcal{C}|$. It is known that $|\mathcal{E}|=2^{|V|+|E|-1}$ if $G$ is connected. Thus, if $G$ has $C$ different cycles, this gives an algorithm whose running time is proportional to $2^{|V|+|E|-1}/C$. Depending on the number of cycles in $G$, this might be extremely slow.

I don't know if there is a polynomial-time algorithm or not.

## Counting the number of simple cycles

Counting the exact number of simple cycles in a graph is NP-hard, by reduction from the Hamiltonian cycle problem. Jonathan Katz has some lecture notes that provide a proof.

I don't know whether it is hard to approximate the number of simple cycles in $G$. If it is, then this might imply hardness results for uniform sampling from among the set of simple cycles.

See also https://cstheory.stackexchange.com/q/20246/5038.
> 2 votes

---
Tags: graphs, sampling
---