# Question
Title: Can partial sorting help with lookup cost in arrays?
Looking something up in an unsorted list is a task with time complexity $O(n)$. However, if the list is sorted, the time complexity is $O(\log(n))$. That means it is sometimes worthwhile to sort an array. However, that is a trade-off as a sorting algorithm has a time complexity of $O(n\log(n))$.

As far as I know, you can not sort an array in less than $O(n\log(n))$ time. I am however wondering if there is any algorithm that can *partially sort* the array in less time than that? I am pretty sure you can not look up a value in such a *partially sorted* array in $O(\log(n))$ time, but can you do better than $O(n)$?

In short, is it possible to process an unsorted array with an algorithm faster than $O(n\log(n))$ such that a lookup algorithm can do a search faster than $O(n)$, though not as fast as $O(\log(n))$?

# Answer
> 12 votes
If you run "balanced Quicksort" (using the exact median at every step) up to depth $k$ (at the cost of $O(n k)$), you get a partition of the original array into $2^k$ sorted parts of $n/2^k$ unsorted elements each. Given an element, we can locate the correct part in time $O(\log(2^k)) = O(k)$ using binary search, and then look it up using an additional $O(n/2^k)$, for a total complexity of $O(n/2^k + k)$.

If $k = o(\log n)$ then the partial sorting takes time $o(n\log n)$. If $k = \omega(1)$ then the lookup algorithm takes time $o(n)$. Thus if $1 \ll k \ll \log n$ we get $o(n\log n)$ preprocessing time and $o(n)$ lookup time. For example, if $k = \log\log n$ then preprocessing takes $O(n\log\log n)$ and lookup takes $O(n/\log n)$.

---
Tags: algorithms, complexity-theory, time-complexity, sorting
---


title: Why neural nets are split into layers?

text:
# Question
Title: Why neural nets are split into layers?
Why is every artificial neural network layered? Why isn't each node just a separate process?

# Answer
A neural net will work with any arbitrary topology, as long as it has no cycles. We often use layers because it is easy to implement and because it allows a human to set parameters for how large the net should be, such as *"four layers with 5, 6, 7 and 10 nodes, respectively"*.

I cannot find anything on the web about neural networks that are not organised into layers, but there is nothing principally impossible about them. Here's an idea for a rainy sunday afternoon: implement a neural net as a directed acyclic graph and use an evolutionary algorithm to find a good topology. Compare it to a layered neural net with similar numbers of nodes and edges.
> 4 votes

# Answer
There are some hand wavy intuitions that adding depth (stacked layers) allows the formation and combination of higher level features. So you can take features from the layer before and build more complex ones by combining them together, rather than starting from scratch.

Conv nets are the poster child for this. You can see that their low level layers learn things like gabor filters and the deeper layer learn things like face detectors.

https://arxiv.org/abs/1512.03965 https://arxiv.org/abs/1602.04485
> 1 votes

---
Tags: neural-networks
---


# Question
Title: How many of the 65536 possible shorts over Z2 have no two consecutive symbols the same?
Probability-related Info theory question that I can't figure out. Thanks in advance!

# Answer
I assume you are talking about the binary digits of all nonnegative integers \< $2^{16}$.

The first binary digit of any positive integer must be $1$, because otherwise it's a leading zero and that means we're counting numbers twice. However, if we do not want two consecutive digits to be the same, this uniquely determines the rest of the bits, because they must alternate: $1010101...$.

So for $b \> 1$, there exists exactly one $b$-bit integer with no consecutive binary digits.

For $b = 1$ there are two strings: $0$ and $1$.

Thus, if we are interested in the number of integers below $2^{16}$ without consecutive digits, there is one 16-bit number, one 15-bit, .. one 2-bit and two 1-bit numbers. So the answer is 17.

For completeness' sake, here they are:

```
0 = 0
1 = 1
2 = 10
5 = 101
10 = 1010
21 = 10101
42 = 101010
85 = 1010101
170 = 10101010
341 = 101010101
682 = 1010101010
1365 = 10101010101
2730 = 101010101010
5461 = 1010101010101
10922 = 10101010101010
21845 = 101010101010101
43690 = 1010101010101010

```
> 3 votes

---
Tags: information-theory
---


# Question
Title: Why are there only NOR and NAND flashes?
According to my lecture and wikipedia NOR and NAND flashes are the most common used. However there isn't really explained why people decided to use these logic gates instead of others. Can someone explain me, what are the factors deciding which gates to use and show how these gates match those properties best?

# Answer
> 10 votes
NAND and NOR are the only two binary gates that are functionally complete, which means that using just one gate type you can implement any circuit.

**This greatly simplifies fabrication**. As long as you can construct a single type of gate many times using the same technique, and can connect them arbitrarily, you can create any circuit.

# Answer
> 9 votes
The underlying reason is that digital circuits are not really digital.

A CMOS gate essentially looks like this:

The inputs are fed into two circuits: the pull-up circuit and the pull-down circuit. These two circuits are complementary, in the sense that the signal combinations which result in the pull-up circuit directing the "one" signal to the output is the exact opposite of the combinations which result in the pull-down circuit directing the "zero" signal to the output. Look up "CMOS circuit design" in your favourite search engine for more on this topic.

When designing a digital circuit, you want them to be as robust as possible. Each component should produce clean outputs no matter how degraded the inputs are. So, for example, in a 5 volt CMOS gate, it's typical to accept as "zero" any signal below 1.5V, and accept as "one" any signal above 3.5V, however the output signal should be less than 0.05V for "zero" and greater than 4.95V for "one".

Adhering to these rules means that the circuit can tolerate a certain amount of signal degradation. You can think of this as a hardware version of Postel's Law: be liberal in what you accept, and conservative in what you send.

Building non-inverting CMOS gates is just as easy as constructing inverting CMOS gates: you simply swap n-channel MOSFETs (hereafter referred to as nMOS) with p-channel MOSFETs (pMOS) and vice versa. And this would work if MOSFETs were perfect switches. However, they are not. Real MOSFETs transmit different signals with different quality due to how they are constructed.

I can't go into all the details here (this is an electronic engineering question), but the short version is that while nMOS transistors transmit a strong "zero" signal, they only transmit a weak "one" signal. Dually, pMOS transistors transmit a strong "one" signal and a weak "zero" signal. As a result, for the cleanest possible output, nMOS transistors are best used for pull-down circuitry and pMOS transistors are best used for pull-up circuitry.

This has the property that the gate is "fully restoring": the output signal is in a strong voltage range no matter what the input voltages were.

Non-inverting CMOS gates are non-restoring because the wrong type of transistor is used for each "pull" direction. The output signal is weak compared to a gate where you used the correct transistor type in each pull circuit. This means that the signal gets more degraded as you chain gates together.

(It is possible to design hybrid circuits, where you have a non-restoring gate followed by a restoring gate to clean up the output signal. You will often find this in non-monotonic gates such as XOR, for example. This is interesting stuff, but it's beyond the scope of this answer because it's not relevant to how flash memory works.)

It's a nice property that inverting gates are functionally complete (you can construct any circuit with them). In particular, you can just put an inverter stage on the output of any gate to get its non-inverting version. However, this is not why CMOS circuits are designed this way, and this is also not relevant to flash memory, which just has to be able to store and retrieve a bit. Inverting gates just behave better in real-world circuits.

Flash memory (and EEPROM memory, for that matter) is designed with a special kind of transistor, called a floating-gate MOSFET (or FGMOS for short). The details are unimportant, but regardless, the FGMOS transistors are still either n-channel type or p-channel type, so everything said above about which transistors should be used where still applies: flash memory cells are still, ultimately, inverting gates.

**Now here's the speculation**

We have officially reached the end of my knowledge of CMOS and flash memory. Now here's some stuff that I think may be true. I'd appreciate an expert opinion on this.

I believe that reading flash memory cells works on a principle closer to that of NMOS logic than CMOS logic, however NMOS gates are inverting for essentially the same reason that CMOS gates are.

I would imagine that while we want to think of a FGMOS as a switch, it probably behaves more like a non-ideal variable resistor in practice. So its "input" is probably already a little bit degraded. It may therefore be even more important to use a fully restoring gate to read its value in practice.

# Answer
> 3 votes
NAND and NOR gates are very simple to build in all the technologies that are currently being used. For example, NAND is a lot simpler to build than AND - if an AND is needed, then you realise that you can build NOT by putting the same value into both inputs of a NAND, and AND (x, y) is usually easiest implemented as NOT (NAND (x, y)).

Lucky enough, not only are NAND and NOR very simple to build, they also give you the advantages of orlp's answer. NAND and NOR are a bit more difficult for the human mind to grasp, but if you design computer chips, that's no problem.

And actually, NAND and NOR are *each* functionally complete, so you can build everything using only one type. And it depends on the technology which one is the one that is very easy to build. (If you need the other, then NAND (x, y) = NOT (NOR (NOT x, NOT y)).

---
Tags: computer-architecture
---


# Question
Title: Are depth-first/breadth-first considered special cases of best-first?
In literature in general, are DFS and BFS considered to be special cases of best-first search?

Suppose the cost function is:

$f(n) = g(n) + h(n)$

Is it correct to reason that if and $g(n) = depth(n)$, then

If $\forall\_n h(n) = 0$, we have a breadth-first search

If $h(n) = i$, where i is the number of nodes visited before visiting, we have depth-first search.

?

Are depth-first and breadth-first search usually considered special cases of best-first search?

# Answer
The answer to your question is, in both cases, *No*.

The reason is as follows: Both *depth-first* search and *breadth-first* search are *uninformed* search algorithms. A distinctive feature of these algorithms is that **they stop once the goal node is generated**.

Now, if all operators are given the same cost (so that you consider them to have the same cost equal to 1), then:

1. Breadth-first search is guaranteed to find the solution, and also to deliver an optimal one. This is, it is both *complete* and *admissible* (some people refer to this also as been *optimal*).
2. Depth-first search, however, is neither *complete* nor *admissible* because it is bounded by a maximum depth. It might well happen that the goal lies beyond it and thus, it cannot guarantee to find it.

Best-First search, on the other hand, uses an OPEN list where nodes are sorted in increasing order of $f(n)=g(n)+h(n)$ where: $g(n)$ is the cost of the current path from the start node to node $n$, and $h(n)$ is an estimate of the remaining effort to reach the goal from $n$. As such, $f(n)$ stands for an estimate of the best path from the start node to the goal that goes through node $n$. However, in contrast with the case of *uninformed search* algorithms, **Best-first search algorithms halt only when the solution is about to be expanded!** This makes a lot of sense. Under a number of assumptions (such as *admissibility* of the heuristic function), sorting nodes in ascending order guarantees that the true cost is above the estimation given by $f(n)$, so that only when expanding a goal you can ensure that all the other nodes stand for potential solutions with a cost greater or equal than the cost of the current solution.

Therefore, from your definitions of $f(n)$ (and assuming unit costs):

1. Making $f(n)=\mathrm{depth}(n)$ would result in an algorithm that expands nodes in the same order than a breadth-first search algorithm (up to tie-breaking). In addition, it will expand more nodes than it since after *generating* the goal, it has to expand all nodes in the current level before *expanding* the goal ---in the next level.
2. Your second choice, $f(n)=\mathrm{depth}(n) + i$, with $i$ been "the number of nodes visited before visiting" is rather confusing to me. I do not know what you might mean by "visited before visiting". In spite of it, however, note that a Best-First search algorithm would proceed further after *generating* the goal node much the same.

Your question makes a lot of sense. In case you want to access additional material related to it, please refer to Robert C. Holte. Common Misconceptions Concerning Heuristic Search". Symposium on Combinatorial Search SoCS 2010. Pages 46--51. See, specifically, the bottom of the left column in page 49.

Hope this helps,
> 6 votes

---
Tags: algorithms, graphs, search-algorithms, heuristics
---


# Question
Title: Any option other recursive search possible to go from one 2d point to another point with fixed set of possible moves?
Problem: Given (a,b) and (c,d), find if you can you reach from (a,b) to (c,d) if we can only have the following moves (a, b) to either (a+b,b) or to (a,a+b).

Example (1,4) to (5,9) is possible because: (1,4) -\> (5,4) -\> (5,9)

Solution: I can think of is recursive search

```
Set 1: TestedPoints, initially empty
Set 2: PointsToTest, initially (a,b)

While (PointsToTest not empty):
   Remove nextPoint (x,y),
   Compare (x+y,y) with (c,d):
          If x+y=c and y=d, return TRUE
          Else if x+y < c and y < d, add (x+y,y) to PointsTotest if it is not present in TestedPoints set

   Compare (x,x+y) with (c,d):
          If x=c and x+y=d, return TRUE
          Else if x < c and x+y < d, add (x,x+y) to PointsTotest if it is not present in TestedPoints set

```

Is there anything faster?

if we can express the progressive X,y points in an expression, I thunk we can do faster. For e.g: Get a as close to c as possible and b as close to d as possible using equations and then do recursive search over smaller interval.

# Answer
> 2 votes
There is a simple method that is often faster: If you have $n$ moves to go from $A$ to $B$, determine the set of all points that you can reach from $A$ in $\lfloor \frac{n}{2} \rfloor$ moves, and the set of all points from which $B$ can be reached in $\lceil \frac{n}{2} \rceil$ moves, and then find if there are points in the intersection of these sets.

# Answer
> 0 votes
**I'm assuming that $a,b,c$ and $d$ are positive natural numbers.**

Suppose that $(c,d)\neq(a,b)$. Observe that if $a$ and $b$ are positive, then $(a+b,b)$ and $(a,a+b)$ are pairs of positive *distinct numbers*. Hence if $c=d$, it is impossible to reach $(c,d)$. Otherwise either $c\>d$ or $c\<d$. Consider the case $c\>d$ (the other case is similar). If $(c,d)$ is reachable, consider the last transition: $(a',b')\to(c,d)$. Since $c \> d$ it must be the case that $c = a'+b'$ and $d=b'$. Hence $a'=c-d$ and $b'=d$. The key insight is that **the shape of the result "tells us" which rule must have generated it**.

So an adaptation of the Euclidean algorithm will be asymptotically faster.

---
Tags: graphs, search-algorithms, recursion
---


# Question
Title: Proof of correctness of divide and conquer clique algorithm
I have the following divide and conquer algorithm that finds a clique in an undirected graph $G = (V, E)$:

```
CLIQUE(G):

1) Number the vertices V as 1,2,3...,n where n=|V|

2) If n = 1, return V

3) Divide V in v1 = {1,2,...,[n/2]} and v2 = {[n/2]+1,...,n}

4) Being G1 the subgraph induced by V1 and G2 the subgraph induced by V2,
   find C1 = CLIQUE(G1) and C2 = CLIQUE(G2)

5) Combine the results in the following way:
   5.1. Initialize C1+ as C1 and c2+ as C2
   5.2. For every vertex v ∈ C2, if v is connected to all vertices in c1+
        then add v to c1+
   5.3. For every vertex v ∈ C1, if v is connected to all vertices in c2+
        then add v to c2+
   5.4. Return the bigger between c1+ and c2+

```

The algorithm is definitive and cannot be changed, and I need to prove that it always returns a subgraph of G that is a clique (don't know how to do it) and find its time complexity, on the time complexity, analyzing the algorithm I have arrived to the following recurrence: $T(n) = n + n·m+2T(n/2)$, which following the master theorem leads to an $O(n·m)$ complexity, but i found that cloque algorithms are exponential, so i must have done something wrong.

Thanks.

# Answer
Assuming you wanted your algorithm to return a maximum clique, here's a small counterexample:

Let $G$ be the triangle $abc$, plus the two isolated points $d$ and $e$. Suppose that $V$ is divided so that $v\_1 = \\{a, d\\}$ and $v\_2 = \\{b, c, e\\}$. Then CLIQUE($G\_1$) will return either $a$ or $d$; suppose it returns $d$. CLIQUE($G\_2$) will return (at best; i.e., if it were in fact implemented correctly) the edge $bc$. But neither $b$ nor $c$ is adjacent to *every* vertex in $c\_1$ (in fact neither is adjacent to *any* vertex in $c\_1$, since $c\_1 = \\{d\\}$ and $d$ is an isolated point), and likewise $d$ is not adjacent to *every* (in fact *any*) vertex in $c\_2$ (since $d$ remains an isolated point), thus step 5 fails to find a bigger clique, despite the fact that $abc$ is a clique of size 3.

This counterexample also shows that the algorithm can fail to find a maxim*al* clique, which is a much weaker requirement.
> 1 votes

---
Tags: algorithm-analysis, correctness-proof, divide-and-conquer
---


# Question
Title: Find long connected similar subsequences in two given sequences
I'm looking for pointers to algorithms which will find long **connected similar** subsequences which two given sequences have in common. For example, in case of two strings:

```
abcaabbaabUVWXYZ
UVWXeYZababababab

```

I'm interested in:

```
**********UVWXYZ
UVWXYeZ**********

```

Not in:

```
ab*aabba*b*****
******aba*ab*bab

```

(which would be one possible *longest common subsequence* for the given strings).

For the example above, `e` represents a (small) difference in the otherwise identical strings `UVWXYZ` and `UVWXeYZ`. This is where the *similarity* comes in. `e` is not necessarily an addition of a single character. It may be a change as well. When thinking on longer strings, multiple characters (even in direct succession) may be different.

The algorithm should probably be driven by a *rating function* for the *length* and the *similarity* of subsequences.

I'm aware that this problem is rather vague, so any pointers to possibly related problem domains and corresponding algorithms are appreciated as well.

**Update:** Removed exclusion criterion "LCS", because it actually seems to be what I'm looking for.

# Answer
> 1 votes
You might be interested in linear-time LCS variant with $k$ mismatches taking gaps with some penalty. Even though the core algorithm is with fixed gaps it is easily converted to your problem by just running algorithm with several gap lengths (naive approach). Better one would be to change the function calculating distance with function over penalties.

Another approach would be to take suffix tree modified to ignore gaps of length at most $k$ and then calculating penalties on the results (starting from longest one and then prunning results based on calculated best so far match including gap penalties). Optimized tree or DAG will decrease the memory footprint.

If you are interested in circular match simply concanate one string with itself.

# Answer
> 1 votes
Let's call this problem LCCS, which is different with LCS. One straightforward way is to use a brute force algorithm with time complexity $O(nm(n+m))$.

```
 1. Input: A[1..n], B[1..m]
 2. Output: Length of the longest common connected subsequence
 3. max = 0
 4. for i from 1 to n
 5.    for j from 1 to m
 6.        if (lowercase(A[i]) = lowercase(B[j]))
 7.           i' = i
 8.           j' = j
 9.           len = 1
 10.          while (i' <= n and j' <= m)
 11.             i'++
 12.             j'++
 13.             if (lowercase(A[i']) != lowercase(B[j'])) break;
 14.             else len++;
 15.          if (len > max) max = len
 16. return max

```

---
Tags: algorithms, optimization, strings, subsequences
---


# Question
Title: I/O cost to traverse a tree stored in preorder form
Let `T` be a binary tree that is stored in the disk following the preorder layout.

For example if this is $T$:

then $T$ will be stored in the disk as follows:

`10, 11, 0, 12, 13, 2, 7, 3, 14, 1, 15, 16, 4, 8, 17, 18, 5, 9, 6`

Every node of the tree is a struct that stores the offset of the left child, the offset of the right child, the id of the node and a size variable. If a node is a leaf the offsets are set to -1.

Suppose that now in every node $u \in T$ we want to know what is the size of the subtree rooted on $u$. Assume that the elements between the disk and the memory are transferred in blocks of size $B$, the size of the memory is $M$ and it holds that $M \geq B$. Is it possible to do that in $O(\frac{N}{B})$ I/Os?

# Answer
> 3 votes
It is possible to do it in $O(\frac{N}{B})$ if you have $B + D$ memory available, where $D$ is the maximum depth of the tree. Algorithm:

1. Read $B$ nodes into a buffer.
2. For each node in the buffer:
    1. Push $(node.id, num\\\_children(node), 0)$ to stack $S$ (respectively $(id, num, d)$).
    2. While $S.peek().num = 0$:
        1. $d = S.peek().d$
        2. Output $(S.peek().id, d)$.
        3. $S.pop()$
        4. $S.peek().num = S.peek().num - 1$
        5. $S.peek().d = max(S.peek().d, d + 1)$.
3. If there are more nodes to process, go to 1.

The idea behind this algorithm is to associate pushing on the stack with going down a child node, and popping coming back up to a parent node.

If we initialize every node with a counter containing the number of child nodes, and we decrement this counter everytime after popping, it means that once the counter hits 0 we have visited every child node as we visit this node: we are in post-order.

We also store a maximum subtree size $d$ with every node. If we pop (go back to visit the parent node) we store the maximum of $node.d$ and $child\\\_node.d + 1$ into this node. This means that once we are in post-order we have the maximum size of all child subtrees + 1 stored in $d$.

---
Tags: algorithm-analysis, data-structures, binary-trees, graph-traversal
---


# Question
Title: Is the set of pairs of TMs at least one of which accepts the empty word semi-deciable?
L = { \< M1,M2 \> | M1,M2 are TM's and Ɛ ∈ L(M1) ∪ L(M2) }

Where Ɛ = Epsilon

**I know that this language is undecidable, but why it is semidecidable too.**

**What i have tried is =\>**

Using Rice's Theorem, part 2

T(no) = (0,1)^+ and T(yes) = (0,1)\*

Which gives that T(yes) is not a subset of T(no), and this says that it is semidecidable.

**Is my understanding right ?**

# Answer
> 2 votes
Rice's second theorem can be used to show for some sets that they are not semi-decidable, but not the opposite.

In order to show that this set is semi-deciable, just follow the definition and construct a semi-decider.

> *Idea:* Simulate both $M\_1$ and $M\_2$ on $\varepsilon$ simultaneaously using dovetailing. If either one halts and accepts, stop simulating and accept.

---
Tags: computability, undecidability, semi-decidability
---


# Question
Title: Why can't we exploite finiteness to prove incompleteness in NP?
It is well established that the class of recursive languages is strictly contained in the class of recursively enumerable languages (Rec $\ne$ RE). Any finite language is decidable and hence can not be RE-complete. My intuition is that an RE-complete language contains infinite number of (finite) strings (information) and can not be reduced to a finite language.

The situation is different for the class NP since we can not rule-out finite NP-complete languages. If P=NP then there is some finite NP-complete language (under Karp reduction).

> Is there an intuition (or evidence) that explains why finite languages can not be complete for NP?

I am looking for an intuition (evidence) that supports the conjecture that all NP-complete languages must be infinite (It should not assume anything about P vs NP). Different notions of completeness inside NP may have significant impact on the properties of complete languages inside NP.

This was moved from a comment. Finiteness of complete languages shifts the focus on using the *right* notion of reduction to define completeness inside NP. The following post on CS Theory shows that defining completeness using injective Karp reductions would prove $P \ne NP$. The reason is that SAT is infinite language and can not be reduced to a finite language using injective Karp reductions.

# Answer
Here is a good reason why finiteness does not help: Let $P\_{inf}$ and $NP\_{inf}$ be the sets of infinite languages in $P$ and $NP$. Then we may focus on proving $P\_{inf}\not=NP\_{inf}$, rather than $P\not=NP$. But $P\_{inf}=NP\_{inf}$ if and only if $P=NP$!

The question as I understand it is, why can't we exploit the fact that these languages are finite in a proof of $P\not=NP$, like we did when we proved $R\not=RE$? But the premise is wrong: the proof that $R\not=RE$, that the Halting Problem is undecidable, does not reference the fact that there are finite languages in $R$. Of course it makes intuitive sense that, since $R$ contains finite languages, it cannot contain $RE$, but in fact $R\not=RE$ follows from the fact that Turing Machines cannot be analysed by other Turing Machines, and, in my view, the fact about finite languages is a quirk which follows from the definitions, as we may as well have considered $R\_{inf}\not=RE\_{inf}$.

If $R\not=RE$ comes from the fact that undecidability cannot be eliminated, then $P\not=NP$, if true, comes from the fact that nondeterminism cannot be efficiently eliminated.

I should clear up some technicalities. If a language contains a finite amount of strings, it can be decided in constant time, $O(1)$, so it is definitely in **P**, as you note. If **P**=**NP**, then every language in P is also NP-Complete (the reduction is simple: given a string, solve it in polynomial time, and then print a fixed yes/no instance of the other problem). So not only is there *some* finite NP-Complete language, *all* nontrivial\* finite languages are NP-Complete if P=NP. On the other hand, if $P\not=NP$, then *no* finite language is NP-Complete. Your intuition about RE-Complete languages containing infinite strings is wrong: those languages contain an infinite number of finite strings.

\*A nontrivial language is one with both yes- and no-instances. The two trivial languages are the empty language $\emptyset$ and the full language $\Sigma^{\*}$, which have no yes- and no no-instances, respectively, which is why no other language can many-one reduce to them.
> 8 votes

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


# Question
Title: # of permutations satisfying special inequalties of each element0
Recently I was solving a counting problem, which needed this subproblem to be solved:

Given integers $n$ and $t$ (where $1 \le t \le n$) and a decreasing function $f$, find the number of permutations $p\_1, p\_2, \cdots, p\_n$ which satisfy:

* for all $1 \le i \le t$, $p\_i \le f(i)$, and
* for all $t \< j \le n$, $p\_j \ge f(j)$.

For my problem, $n$ is quite big (about 40, which enabled me to think of meet-in-the-middle), but $t$ is quite small (about 10-15). So I tried to solve the problem with an algorithm regarding $t$, but failed.

I tried to exploit the fact that, if we consider only one of the conditions, the problem becomes super-easy. So I allocated first $t$ elements of the permutation(tried all possible cases), and then calculated # of possible permutations of the remaining $n-t$ elements. This method could give an answer reasonably faster than iterating all possible $n!$ permutations. However it is still really slow, maybe using an $2^n n^2$ dp approach would be faster than this.

I believe that iterating first $t$ elements is not required to solve the problem, but couldn't find any way. Could you please help me solve this problem?

# Answer
> 2 votes
## A faster approach

It's possible to solve this in $O(\binom{n}{t} \cdot n)$ operations, i.e., at most $O(n^{t+1})$ operations. This is faster than the algorithm you describe in your question by about a factor of $t!$, but probably still not fast enough to be feasible for your parameters.

The idea is to enumerate all possible *subsets* of $t$ elements. We'll try all possible choices for $S$, the set of elements that occur in positions $1,2,\dots,t$ (without regard to what order they appear in). There are $\binom{n}{t}$ such choices for $S$.

For each choice of $S$, we separately (i) count the number of ways to order the elements of $S$ so that the first $t$ elements satisfy the first condition, and (ii) count the number of ways to order the elements of $\\{1,2,\dots,n\\}\setminus S$ so that the last $n-t$ elements satisfy the second condition. Then, we multiply these two counts.

Each of those counts can be computed efficiently. For instance, to compute count (i), we compute

$$g(t) \times (g(t-1)-1) \times (g(t-2)-2) \times \dots \times (g(1)-(t-1)),$$

where $g(i) = |S \cap \\{1,2,\dots,f(i)\\}|$ counts the number of elements of $S$ that could potentially be used at position $i$ without violating the first condition (i.e., the number of elements of $S$ that are $\le f(i)$). Similarly, to compute count (ii), we compute

$$h(t+1) \times (h(t+2)-1) \times (h(t+3)-2) \times \dots \times (h(n)-(n-t+1)),$$

where $h(i) = |\overline{S} \cap \\{f(i),\dots,n\\}|$.

These two counts can be computed using $O(n)$ operations, leading to the claimed running time.

## A further optimization

You can further optimize this, by splitting $S$ into two parts. Decompose $S$ into

$$S = S\_1 \cup S\_2,$$

where $S\_1 \cap S\_2 = \emptyset$, by defining

$$\begin{align\*} S\_1 &= S \cap \\{f(t+1),f(t+1)+1,\dots,n-1,n\\}\\ S\_2 &= S \cap \\{1,2,3,\dots,f(t+1)-1\\}. \end{align\*}$$

Now notice that to count (ii), we don't actually need to know both $S\_1$ and $S\_2$: it's enough to know $|S\_1|$ and $S\_2$: the exact elements in $S\_1$ don't change the count (by a relabelling argument), since they're all $\ge f(j)$ for all $j\>t$.

Furthermore, since $|S|=t$ and $|S|=|S\_1|+|S\_2|$, it suffices to know $S\_2$. Once we know $S\_2$, we can compute $|S\_1|=t-|S\_2|$ and then compute count (ii).

Similarly, once we know $S\_2$, we can also compute count (i).

So, we're going to enumerate all possible values for $S\_2$, i.e., all subsets of $\\{1,2,3,\dots,f(t+1)-1\\}$ of size $\le t$. There are

$$Q = \binom{f(t+1)-1}{t} + \dots + \binom{f(t+1)-1}{1} + \binom{f(t+1)-1}{0}$$

possible choices for $S\_2$. Then we obtain an algorithm whose running time is $O(Q \cdot n)$. The exact value of $Q$ depends on $f(t+1)$, but we have $Q = O(f(t+1)^t)$.

In this way we obtain an algorithm whose running time is $O(f(t+1)^t \cdot n)$. For many choices of $f$, this will be even faster than the basic approach sketched at the beginning of this answer.

Also, it's easy to see that we must have $f(t+1) \ge n-t+1$ (otherwise the count is 0). It follows that there is an algorithm whose worst-case running time is $O((n-t)^t \cdot n)$, regardless of $f$.

---
Tags: algorithms, permutations, enumeration
---


# Question
Title: reduction from the problem "accepts-empty string" to "language of empty string"
9.9. Construct a reduction from Accepts-$\lambda$ to the problem Accepts-$\\{\lambda\\}$: Given a TM $T$ , is $L(T) = \\{\lambda\\}$?

The question is from Martin's *Introduction to Languages and Theory of Computation*.

I know how reductions work though I am unsure of several things. It's easy to see that if the inner machine (computing "accepts-$\\{\lambda\\}$") accepts then the outer must also accept, but it is not clear that the other goes as well. How do I ensure this?

# Answer
> 1 votes
Call $L\_1=\\{\langle M \rangle\mid M\text{ accepts }\lambda\\}$ and $L\_2=\\{\langle M \rangle\mid M\text{ accepts only }\lambda\\}$, where $\langle M\rangle$ denotes the description of the TM $M$. We wish to establish a mapping reduction $L\_1 \le\_\text{M} L\_2$.

To do this, we want a mapping, $f$, from TM descriptions to TM descriptions such that $$ \langle M\rangle\in L\_1 \Longleftrightarrow f(\langle M\rangle)\in L\_2 $$ For a TM description $\langle M\rangle$, we'll define $f(\langle M\rangle)=\langle N\rangle$ where

```
N(x) =
   if x = lambda
      run M on input lambda
      if M accepts
         accept

```

Now what happens with this mapping?

* If $M(\lambda)$ accepts (so $\langle m\rangle\in L\_1)$, $N$ will accept $\lambda$ and no other string, so $\langle N\rangle\in L\_2$.
* If $M(\lambda)$ doesn't accept (so $\langle M\rangle\notin L\_1)$, $N$ will accept no input string, so $L(N)=\varnothing$ and thus $\langle N\rangle\notin L\_2$.

That's exactly what we need to establish the reduction $L\_1 \le\_\text{M} L\_2$.

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


# Question
Title: Large number of layers in a neural network?
How large can the number of layers in a neural network be? Can there be maybe 1000 layers with, say, 1000 neurons in each layer?

I imagine the brain has hundreds of thousands of layers.

# Answer
> 4 votes
In principle, there is no limit on the number of hidden layers that can be used in an artificial neural network. Such networks can be trained using "stacking" or other techniques from the deep learning literature. Yes, you could have 1000 layers, though I don't know if you'd get much benefit: in deep learning I've more typically seen somewhere between 1-20 hidden layers, rather than 1000 hidden layers. In practice the number of layers is based upon pragmatic concerns, e.g., what will lead to good accuracy with reasonable training time and without overfitting.

Don't confuse artificial neural networks with the brain. The behavior of artificial neural networks doesn't necessarily tell us anything about the brain, and you can build artificial neural networks whose structure doesn't match anything found in the brain.

# Answer
> 3 votes
The Universal Approximation Theorem says that a 3-layer network actually suffices to approximate any continuous function on $\mathbb{R}^n$.

# Answer
> 1 votes
To expand on @D.W.♦'s answer.

They are correct in stating

> In principle, there is no limit on the number of hidden layers that can be used in an artificial neural network

There are however multiple challenges when training a very deep neural network. Challenges include the infamous vanishing/exploding gradient, local minima, overfitting, and time/memory restrictions.

Recent advancements have worked to solve these challenges.

While depth seems to improve performance within neural net problems it has also been shown that width plays an important factor as well.

It is important to understand Neural Nets are a relatively new technology and that we are still in the process of learning about them.

Now to address your comment about the brain,

> I imagine the brain has hundreds of thousands of layers.

Like @D.W.♦ mentioned, be careful not to confuse artificial neural networks with the human brain. The two are very different. That being said, researchers are working on making artificial networks like biological networks.

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


title: Is this a hypergraph?

text:
# Question
Title: Is this a hypergraph?
Here is the problem is want to solve:

I want to connect nodes with directed labelled edges, but this two nodes are potentially themselves graphs, hypergraphs or the current structure I don't have a name for.

Here is a simple example with a graph $(v\_1,e\_1,v\_2)$ where nodes $v\_1$ and $v\_2$ are connected by $e\_1$. I want to have the following structure: $((v\_1,e\_1,v\_2),e\_2,(v\_3,e\_3,v\_4))$

in this case, the $v\_i$ hold a single value (i.e. classical graph nodes)

What I don't know is:

* What is the name of such a structure ?
* If it's a well known data structure, are there some efficient implementations ?

# Answer
> 1 votes
No, this isn't a hypergraph. I don't think it has a standard "name". Call it whatever you like: as long as you define your terms clearly, you should be fine.

Yes, you can implement this efficiently using any standard data structure for representing graphs: e.g., adjacency lists. Each node of the "outer" graph will contain a pointer to a data structure that describes the "inner" graph it represents.

---
Tags: graphs, data-structures, terminology
---


# Question
Title: How to satisfy bounded waiting in case of deadlock?
I have a doubt regarding bounded waiting.

Deadlock implies no Progress because the processes take indefinite time to decide who will enter the critical section .

But, Does deadlock implies no bounded waiting ?

I think No because bounded waiting is per process and deadlock is for the system.

Moreover, In a deadlock, bounded waiting conditon is not violated and bounded waiting is not with respect to time, but with respect to the number of times the processes enter the critical section before intended process enters the critical system .

Would anyone at least care to correct me or suggest what is right and not right?

# Answer
You are correct.

Consider the simple synchronization algorithm which denies entry to all processes.

In this case we have both deadlock and bounded waiting, since any process $p$ is not bypassed by some process $p'$ before entering the critical section, so you could say bounded waiting is satisfied with the constant function $f=0$.
> 6 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: Amortized time cost of insertion into an Array list
A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied over into the newly resized array 1, 2, 4, ... , n number of copies. What then is the sum of this sequence? To answer that we see that the sequence written backwards is n + n/2 + n/4 + ... + 1. Until here I understand what has been said. Here is where my confusion starts, how is this sequence roughly equal to 2n? How do we know this? Once we settle that we can say that n insertions take O(2n) time, but from that how do we deduce that the amortized time for each insertion is O(1).

# Answer
> 10 votes
For the estimate, $$ n + \frac{n}{2} + \frac{n}{4} + \cdots +1 \<n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n, $$ since $1 + 1/2 + 1/4 + \cdots = 2$.

If $n$ insertions take $O(n)$ time, then the amortized time per insertion is $O(n)/n = O(1)$. This is by the *definition* of amortized time. (More accurately, the amortized time is at most $K$ if $n$ insertions take at most $Kn$ time, for *every* $n$.)

---
Tags: algorithm-analysis, runtime-analysis, amortized-analysis
---


# Question
Title: Minimize number of circles to cover set of points
I'd like to minimize the number of circles $C$ to cover a set of points $P$ in 2D.

There is no fixed radius however each circle must contain exactly $N$ points. The circles may overlap. A point may be covered by multiple circles. All coordinates are floats.

Problem size: $|P| \leq 1000$, $5 \< N \< 15$

My current approach: I limited the possible center points of the circles to the set of points and just take the center point which covers the most uncovered points as long as there are uncovered points.

Good example with $N=3, |P|=9, |C|=3$ (optimal because $|C| = \lceil|P|/N\rceil$):

Non-optimal but valid example with $N=3, |P|=9, |C|=4$ (using my current approach, numbers indicates step):

I'm aware the problem might be a bit vague. Any hint on how to approach the problem is appreciated. I'm not necessarily interested in an optimal solution. An approximate/heuristic algorithm is totally fine.

# Answer
> 6 votes
## Set Cover

If you restrict the possible center points of the circles to be the set of points, then this is an instance of set cover where the universe has $|P| \le 1000$ elements and where each set contains $N$ elements. While set cover is NP-hard, there are algorithms for set cover that are faster than exhaustive search.

For these parameters, I expect it should be possible to find an optimal or near-optimal solution to the associated set cover problem, using standard algorithms for set cover. I would recommend starting with the integer linear programming formulation and using a standard ILP solver (Gurobi, CPLEX) to find an optimal or near-optimal solution to the set cover problem. That might be efficient enough for your purposes.

Your approach is known as the greedy algorithm for set cover. It is known to give a $\lg N$-factor approximation, i.e., a covering that uses no more than $\lg N$ times as many circles as the optimal covering. Thus, the ILP formulation may yield better solutions. There are also heuristics for improving the greedy algorithm, e.g., BubbleSearch, which makes small random tweaks to the order suggested by the greedy strategy, repeats that some number of times, and takes the best solution found so far. You could try them and compare them to how well the ILP formulation works, if you wish.

## Geometric Set Cover

You could also look at algorithms for geometric set cover; some of those techniques may be useful here. In particular, there are approximation algorithms and fast heuristics for geometric set cover, and you could try seeing if they are useful in your particular setting. They use the extra geometric structure provided by the problem: this is not a totally arbitrary instance of set cover, but there is some additional structure.

## Arbitrary Center Points

The above algorithms have one critical limitation: they only consider circles that are centered at some point in $P$. There's no reason to expect the optimal solution to your problem to have this property. Thus, they might fail to find the optimal solution to your original problem.

Fortunately, it's possible to fix this limitation. It's possible to come up with a not-too-large set $U$ of candidate circles, such that the optimal solution is obtained by taking a subset of circles from $U$; then we can apply set-cover techniques to pick a minimal-size subset of $U$ that covers all of $P$. In particular, we will use the following geometric facts:

**Lemma 1.** Let $C\_0$ be any circle that covers exactly $N$ points. Let $S \subset P$ be the set of $N$ points covered by $C\_0$. Then there exists a circle $C$ that (i) covers exactly $S$ and no other points and either (ii.1) has at least three points of $S$ along its circumference or (ii.2) has two points of $S$ along its circumference and is centered at their midpoint.

*Proof.* Consider any circle that covers exactly $S$ (and nothing more). Pick the point $p \in S$ that is closest to the boundary of this circle. Reduce the radius of the circle until $p$ is on the boundary. Now if this circle doesn't have two points of $S$ along its circumference yet, move the center of the circle towards $p$, reducing the radius at the same rate, until the first time some other point is on the boundary -- call it $q$. At this point we have a circle $C$ that covers all of $S$, contains $p,q$ on its boundary, and doesn't cover any points other than $S$. Now let $m$ be the midpoint between $p,q$, and let $L$ be the line that is perpendicular to $pq$ and that intersects $m$. If $C$ is centered at $m$, we're done. Otherwise, $C$'s center is somewhere on $L$. Move the center of $C$ along $L$ towards $m$, decreasing its radius at the same time so that $p,q$ remain on its circumference, until either the center reaches $m$ or the circumference hits a third point. Either way, we are done. $\Box$

**Lemma 2.** Given any three non-colinear points $p,q,r$, there is a unique circle that is tangent to all three (i.e., has all three on its circumference). This circle can be efficiently computed.

*Proof.* Use the same procedure described in the proof of Lemma 1, but now without worrying about how many points are covered by the circle. $\Box$

**Lemma 3.** Given any two points $p,q$, there is a unique circle centered at their midpoint and tangent to both $p,q$.

*Proof.* Obvious. $\Box$

With these lemmas, we can now suggest an algorithm:

* For each set of three points $p,q,r \in P$, find the circle that is tangent to $p,q,r$. Identify the points covered by this circle (e.g., using a quadtree). If this circle covers exactly $N$ points, add it to $U$.
* For each set of two points $p,q \in P$, find the circle centered at their midpoint and tangent to both. If this circle covers exactly $N$ points, add it to $U$.

Lemma 1 now ensures that we need only consider circles in $U$; any set of $N$ points that can be exactly covered by some circle, can be covered by some circle in $U$. Therefore, there exists an optimal solution to the original problem that uses only circles in $U$. As an optimization, if there are two circles in $U$ that cover the same set of points, you can keep one of them and discard the other.

Therefore, the problem becomes:

Given a set $P$ of points and a set $U$ of circles (each covering exactly $N$ points from $P$), find the smallest subset of $U$ that covers all of $P$.

This is a finite set cover problem, and the solution to *this* set-cover problem is guaranteed to be optimal. We obtain a set-cover instance with a universe of size $|P| \le 1000$ and with $|U|$ sets, each of size $N$. This set cover problem can then be solved using standard algorithms for set cover, e.g., using an ILP solver. We'll have $|U| \le |P|^3/6$ at worst, though in practice I expect $|U|$ will typically be much smaller (closer to $|P|^2$ or so). The running time to create the set-cover instance will be at most $O(|P|^3)$; then we have to solve the set-cover instance. I anticipate that, for these parameters, it might be possible to obtain an optimal or very-nearly-optimal solution to the original problem using off-the-shelf ILP solvers.

My thanks to @j\_random\_hacker for substantial assistance with this answer.

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


# Question
Title: Does an array count as a primitive operation when it is used as an argument in a function call?
Say I have `return A[n-1] + Sum(A, n - 2)`. I counted the following primitive operations:

```
return A[n-2] + Sum(A, n - 2)
   1    2 3   4  5  6   7

```

I know accessing a certain index in A counts as 1 primitive operation, but I am not sure about `A` in the function call. Did I count the right number of operations?

# Answer
As pointed out by Raphael, it depends on the machine model. Under the assumptions of the RAM model of computation ...

> 1. *Simple* operations (+, -, call, return, etc.) take one time step.
> 2. *Loops* and *subroutines* are not simple operations: they may involve many of them.
> 3. *Memory accesses* (e.g., indexing into an array) take one time step.

... you counted correctly operations \[1-4\] and 7. As for operation 5, it depends: the subroutine *call* does count as one single-step operation (according to assumption 1), but the subroutine *itself* doesn't: it is a composite operation (according to assumption 2). Finally, I would not consider passing `A` as a parameter to be an operation: `A` affects running time when it is accessed within the `Sum` subroutine, not in the subroutine call.
> 3 votes

---
Tags: algorithm-analysis
---


# Question
Title: Questions about class of problems that can be solved with unlimited computational power, but access to only logarithmically many bits of the input?
Consider the class $\text{DLOGTIME}^{\text{ALL}}$: the class of problems that can be solved by a machine with unlimited computational power but only access to logarithmically many bits of the input. Which bits of the input it accesses can depend on the values of bits it has already seen, and it has random access to the input. For conciseness, let's call this language $\text{X}$.

Does this class have a name? What is known about it?

Here is what I know so far:

* It includes problems that are very undecideable – it includes padded versions of every language whatsoever!
* $\text{E}^\text{X} = \text{ALL}$ by a padding argument.
* $\text{X}$ does not contain the problem $\text{PARITY}$ (are the number of 1 bits in the input even?). As such, $\text{X}$ does not contain the regular languages.

### Questions:

* Is $\text{X}$ contained in $\text{P}/\text{poly}$?
* Is $\text{X}$ contained in any other well-known complexity class?
* What else is known about $\text{X}$?

# Answer
It is contained in $P/Poly$

Let $M$ be a logarithmic time superoracle machine which decides some language $L$ in your class. We can define it by adding a special tape in which we can specify our desired language by writing some real number. Upon querying the oracle it will determine the membership of the given string to the specified language.

With polynomial length advice, you could provide the choice tree that determines what bits are read from a length $n$ input (if the first bit is x then go read y...). The questions to the oracles are determined by the bits read, and I can ask only a logarithmic number of questions (would work for polynomial too).

In the advice i could also hardcode a table which links any possible logarithmic input to the answers from the desired oracles. Given such advice and some input $x$, read the required bits using the choice tree, and simulate the special machine with the oracle answers given in the advice.
> 3 votes

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


# Question
Title: Finding any path between nodes of implicit, finite, regular, undirected graph
Consider a 4-regular, finite, non-directed, integer-weighed graph $G$. Let each node carry an integer value indicating its distance from zero on a hypothetical axis $X$. Take a given node $N$ for which we know its distance from zero (either negative or positive) and the weights on the edges incident to it. Note, that for each node, two of the edge weights are positive and two are negative. All four are integers. Let $N\_0$ denote the node with distance zero on the $X$-axis. In the graph there is at least one $N\_0$.

To better illustrate it see an outline diagram (apologies to readers with impaired eyesight for not including high contrast image).

Central blue node in the example has some negative distance from zero (black axis). Now, this node (like each node in this graph) has four edges with weights: w1 and w2 are positive-valued (so that if you choose to move along w1 and w2 this will bring you closer to zero on the axis), while w3 and w4 are negative. In the picture the blue node is connected with the target node with distance zero, but this is of course just for illustration.

Although the graph is finite, it is very large ($\>10^{500}$ nodes or so), so one cannot represent the entire graph at once in RAM.

Take any initial node $N$ with weights $w\_1,w\_2,w\_3,w\_4$ and distance $d$. If one traverse along either of the four edges towards neighbour node, then all remaining weights in this neighbour can be easily calculated based on the weighs of the initial node (they form some arithmetic sequences, formulae of which are given).

**Problem:** Find any path (not necessarily the shortest) from $N$ to $N\_0$ for the graph described above. The algorithm should basically provide values of subsequent edges (with their weighs) constituting the relevant path to $N\_0$. What is the expected computational time complexity?

**Additional - strictly related to the problem:** Does one need to map the entire graph into memory in order to launch any suitable search algorithm?

# Answer
The distances of your nodes and the weights of the edges can be used as a heuristic for an algorithm like $A^\*$. That might be reasonably efficient in practice, but in the worst case still looks at the whole graph.

Another possibility is using a random walk with a bias for edges that take it closer to the goal. Then you need memory proportional to length of the path you discover (you can prune cycles to improve this in practice).

If you want to minimize memory consumption (while probably exploding your runtime) you can use the logspace algorithm for graph connectivity.

As you say that your graph is bigger than what can be stored on a universe-sized computer, I assume that you have some efficient representation. Should the input to your algorithm be reasonably big as well, you should be careful to use an IO-optimized algorithm. This blog post might serve as a start.
> 2 votes

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


# Question
Title: Describing the language formed by a particular grammar
* **G → G B ⏐ G N ⏐ ε**
* **B → ( E )**
* **E → E ( E ) ⏐ ε**
* **N → ( L \]**
* **L → L E ⏐ L (⏐ ε**

For this grammar, the prompt asks to describe in the language that this grammar describes and builds.

I got to the point of first trying at defining the language each one builds but the recursiveness of this grammar threw me off a bit.

I'm kind of stuck, thus far I tried to start with let's say **N** and try to describe it as generating a left paren followed by a left paren and right bracket.

I could really use some direction on where to go with this.

# Answer
> 1 votes
There doesn't appear to be a simple description for the language generated by this grammar, but here's what happens.

1. From $E$ we have the productions $E\rightarrow E(E)\mid\epsilon$. The first few strings generated from $E$ are: $$\begin{align} \epsilon &\quad E\Rightarrow\epsilon\\ (\\:) &\quad E\Rightarrow E(E)\stackrel{\*}{\Rightarrow}(\\:)\\ (\\:)(\\:) &\quad E\Rightarrow E(E)\Rightarrow E(E)(E)\stackrel{\*}{\Rightarrow}(\\:)(\\:)\\ (\\:(\\:)\\:) &\quad E\Rightarrow E(E)\Rightarrow E(E(E))\stackrel{\*}{\Rightarrow}(\\:(\\:)\\:) \end{align}$$ It's not too hard to show inductively that $E$ generates all and only the strings of balanced parentheses, i.e., the strings over $\\{(\\;,\\, )\\}$ that could appear in a legal arithmetic expression. Let $\mathcal{B}$ denote this language.
2. From the production $B\rightarrow (E)$ we see that $B\stackrel{\*}{\Rightarrow}(\mathcal{B})$, namely any string of balanced parentheses enclosed in $(\\,)$.
3. From the productions $L\rightarrow LE\mid L\\:(\\:\mid\epsilon$. It's not too hard to see that $L$ generates all strings over $\\{E,\\,\\,(\\,\\}$. Call this language $\mathcal{L}$. In simple terms, $L$ generates all strings of balanced parentheses interleaved with an arbitrary number of left parens.
4. From $N\rightarrow\\,(\\,L\\,\]$ we see that, similarly to step (2), we have $N\stackrel{\*}{\Rightarrow}(\\,\mathcal{L}\\,\]$
5. Finally, it's not too hard to see that from the productions $G\rightarrow GB\mid GN\mid\epsilon$, that $G$ generates all strings over $\\{B,N\\}$, so we have that the language of this grammar will generate all strings made from the concatenation of terms of the form $(\mathcal{B})$ and $\\:(\mathcal{L}\\:\]$ in any order.

For example, a string generated by the grammar is $((\\:)(\\:)((\\:\]\\,(((\\:)(\\:)))$, where I've separated the $N$ and $B$ substrings for clarity.

As I said at the start, not pretty.

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


# Question
Title: Why is Clique NP-complete while k-Clique is in P for all k?
I just stumbled upon this question here Why is the clique problem NP-complete? and I am confused by the given answer. The question about about whether $k$-clique is NP-hard for a fixed $k$ and the answer is no. However, we know that clique in general is NP-hard. Also we know that $0 \leq k \leq n$ must hold (for a graph of size $n$).

What is wrong about the following reasoning: Assume I have some algorithm $A\_i$ that solves $i$-clique for some fixed $i$ in polynomial time. Now given some general clique problem without a specific $k$ (these problems are supposedly NP-hard), I simply run $A\_i$ for $i=1$ to $n$. Now since $n$ is poly and every $A\_i$ runs in polynomial time $p\_i$, the resulting algorithm also runs in polynomial time $\sum p\_i$, but this cannot be the case, since clique is NP-hard.

What is wrong about my reasoning?

# Answer
> 6 votes
The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of $$ \sum\_{k=1}^n n^k, $$ which is no longer polynomial.

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


# Question
Title: Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$
I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow.

I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ using a truth table as it's easy to see.

However, I can't seem to turn $A \vee (\neg A \wedge B)$ into $A \vee B$ using steps such as distributive / absorption etc.

Can someone talk me through the steps that you would take to simplify this?

# Answer
> 8 votes
Note that

$\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$;

you can "multiply out". Add in

$\qquad (A \lor \lnot A) \land B \equiv B$

and you are done.

# Answer
> 6 votes
I'll write your expression as $A\lor(\neg A\land B)$. Then $$\begin{align} A\lor B &= A\lor((A\lor\neg A)\land B) &\text{identity}\\ &=A\lor (A\land B)\lor(\neg A\land B) &\text{distributive}\\ &=(A\lor (A\land B))\lor(\neg A\land B)\\ &= A\lor(\neg A\land B) &\text{absorption} \end{align}$$

# Answer
> 3 votes
$$a \lor (\neg a \land b) \equiv (\underbrace{a \lor \neg a}\_{\equiv \text{True}}) \land (a \lor b) \equiv \text{True} \land (a \lor b) \equiv a \lor b$$

# Answer
> -1 votes
absorption rule: (if P then Q) iff (if P then (P and Q)) identity: (if P then Q) iff ((not P) or Q) so: (A or B) iff (if(not A) then B) (by identity) hence: (A or B) iff (if(not A) then ((not A) and B)) (by absorption) hence: (A or B) iff (A or ((not A) and B)) (by identity)

Basically, (A or B) iff (A or ((not A) and B)) is the absorption rule

---
Tags: logic, arithmetic, boolean-algebra
---


title: How can I assign cooks to customers?

text:
# Question
Title: How can I assign cooks to customers?
I haven't done much algorithm writing till now. I have a specific scenario and I am wondering which approach shall I take.

**Scenario**:

Let us suppose that

1. we have 4 guys (A,B,C,D)
2. We want to assign them a certain task whose duration varies from **40 mins - 1 hr 15 mins**.
3. The task duration varies depending on the number of people (1-6) which he needs to serve. (**i.e 40 mins for 1 person and 75mins for 6**).
4. Now we want to utilise these 4 guys(A,B,C,D) in particular time slots. let's say:
> 06:30 to 11:00 & 16:00 to 22:00

I don't only want the code rather I would love to get some info about good algorithms which are best suited for this scenario following with some code.

* All resources have equal efficiency. Efficiency is not much of our concern.
* We can have any number of customers who are to be served. I'll try to explain this by one scenario:

> A,B,C,D are cooks(assume) who need to work during the mentioned time slots(6:30 to 11:00 & 16:00 to 22:00). Customers(*as an individual or some group who are living together in a flat*) can book the cooks to cook food for them. The cooking time (40 mins to 75 mins) is directly proportional to the number of people for whom it is being cooked. The customer should be able to register himself on some website and the website would allocate the resources(A,B,C,D) to the registered users accordingly.

**Input**:

1. How many people are enrolling for the service
2. Desired time slots

**output**

1. Available cooks as per the selected time slot

**Update 2:**

1. There can any number of cooks.
2. There can any number of customers with no relation to cooks.
3. Once a customer books any cook , its not compulsory that the cook has to serve in both(lunch & dinner) time slots. The customer can select opt for the same cook if he's(the cook) available or else the customer will be asked to select another cook who is available during that time

# Answer
> 1 votes
This looks like an instance of the assignment problem. (No, it doesn't require a square matrix.)

---
Tags: algorithms, assignment-problem
---


# Question
Title: Balanced partition problem for N =< 60 and very large sums
I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S\*N) cant run under available time (1000ms). I talked to the teacher and with N =\< 60 he recommended the brute force (we are learning recursion). I've tried some approaches but I cant find a recursive algorithm that runs under 1 second. Its possible as some students got an solution that runs in less than 100ms.

What is an efficient recursive approach to this problem given data with this magnitude?

# Answer
Would have been better on stackoverflow...

A pseudo-linear algorithm should run below a second with these numbers (sum ≤ 1000000, N = 60), if you represent the numbers that can be written as the sum of the first k integers using a bitmap using 64 bit integers.
> 1 votes

---
Tags: algorithms, optimization, np-complete, partition-problem
---


title: Why doesn't greedy work for Clique?

text:
# Question
Title: Why doesn't greedy work for Clique?
In reference to this problem (equivalently, findind a maximal clique in an undirected graph), I believe greedy approach should work (i.e. removal of people who have maximal qualms with others.). Though I cannot prove that this would always work or won't but I intuitively felt that it should, but eventually some examples could be created that fail this greedy approach.

Can someone prove/disprove whether the greedy approach is correct? Not just a counterexample, but a general explanation would be quite useful.

# Answer
> 4 votes
Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex in the bipartite graph has degree $n/3$. Your algorithm would thus remove all the vertices in the clique. The remaining graph is bipartite, and so its maximal clique contains only two vertices.

So your algorithm finds a clique of size two instead of a clique of size $n/3$.

---
Tags: algorithms, graphs, clique
---


# Question
Title: What is the metadata in microblogging platform?
I'm reading papers regarding microblog credibility perception of non-text cues.

1. Tweeting is believing? Understanding microblog credibility perceptions by Morris et al., 2012
2. Microblog Credibility Perceptions: Comparing the United States and China by Yang et al., 2013

However, Yang et al.\[2013\] refer to some cues, such as location, number of followers, is a reply as **metadata**. Metadata is defined as '*data about data*', but such cues seem normal data to me.

Examples of cues mentioned:

* author location
* contains URL
* number of followers
* is a retweet

Now I'm confused what exactly does metadata include in microblogs, and what is the difference between metadata and normal data in microblogs.

For example: the number of followers - it's a non-text data. But is it a data or metadata?

# Answer
> 1 votes
Metadata is an infamously ill-defined term. Roughly speaking, it's trying to get at a distinction along the following lines: data is the "content" you care about; metadata is other information that is secondary or exists primarily for technical reasons (e.g., addressing information, tags, technical data to facilitate storage or communication).

A classical analogy is postal mail. The contents of the letter is considered "data". The addresses on the envelope might be considered "metadata".

Of course, it's just bits, so at some level it's all data. But when we talk about the data/metadata distinction, we're usually trying to draw a distinction between the main content that users care about, vs secondary information used to enable the system to work.

Again, the term "metadata" is vague, ambiguous, and ill-defined. Don't expect a precise technical definition of the term. Instead, if you plan to use this term in communication and its precise meaning is important, then make sure to state clearly what you mean by metadata and what you do/don't consider to be metadata.

---

See also https://freedom-to-tinker.com/2008/10/20/what-your-mailman-knows-part-1-2/ and https://freedom-to-tinker.com/2008/10/23/abandoning-envelope-analogy-what-your-mailman-knows-part-2/ for discussion about the use of the term "metadata" in the privacy context.

---
Tags: terminology, data-mining, data-sets
---


# Question
Title: Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages
When I take a look at the proofs for pumping lemma, I have a feeling that I am often missing the intuition behind the condition |xy| ≤ p.

What exactly is the reason behind this condition? All the literature I have taken a look at are either silent (no proof, no discussion, only a statement) about this point, or state that we want the first repetition to occur *not too far from the start*.

But when there is an inequality involved, with very precise symbols and operators, don't we expect there to be a clear proof where we ultimately reach this condition?

What I am looking for are,

1. Mathematical proof for the condition, |xy| ≤ p.
2. Intuition behind the same condition.

To make the strings sufficiently long we have the condition string size at least p. My specific issue is why it is needed that |xy| ≤ p? And what does it break if |xy| ≤ p is not true?

*(What's the reason for the second condition of the pumping lemma(s)?, does not exacly answer my question. The question is perhaps alright, but the answers only give some examples without much deep intuition.)*

# Answer
It's not needed for the proof. You can prove the lemma without this condition. Adding this condition makes the statement *stronger* and so more useful.

The intuition here is that if a DFA has $p$ states and there is a list of $p+1$ of them, then the list must contain two states which are the same. The string $x$ is the part that stretches from the beginning of the input to the first occurrence of the double state, and the string $y$ stretches until the second occurrence. By considering the first repeat we can guarantee that $|xy| \leq p$, since after reading $p$ characters we have seen $p+1$ states.
> 10 votes

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


title: Regular language with pumping lemma

text:
# Question
Title: Regular language with pumping lemma
I have that language $S=\\{a^n b^m c^m\mid n,m \geq 0\\}$. How can I prove with the pumping lemma that it isn't regular? Can I use the concatenation closure and say that it's the language $L\_1 = \\{a^n\mid n\geq0\\}$ and $L\_2 =\\{b^m c^m\mid m \geq0\\}$ prove that $L\_2$ isnt regular so $L\_1 L\_2 = S$ is not regular too?

# Answer
> 10 votes
Your concatenation idea doesn't work. Although the concatenation of two regular languages is guaranteed to be regular, the concatenation of a regular language and a non-regular language is not guaranteed to be non-regular. For example, take $L\_1=\Sigma^\*$, $L\_2=\\{a^nb^n\mid n\geq 0\\}$. $L\_2$ is not regular but $L\_1L\_2=\Sigma^\*$ is regular.

To prove that $S$ is non-regular using the pumping lemma, pump a string that contains more $b$s than $c$s.

# Answer
> 9 votes
Raphael is right: you can use a quite standard pumping argument. David Richerby is also right: your argument does not work in this way.

However ... If you want to have a result about closure of non-regular languages you can consider this one.

**Theorem.** If $L\_1$ and $L\_2$ are nonempty languages over *disjoint* alphabets, then their concatenation $L\_1L\_2$ is nonregular iff at least one of $L\_1$ or $L\_2$ is nonregular.

Of course, if either language is empty, then the concatenation will be empty, hence regular.

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


# Question
Title: Is bounded waiting satisfied in this 2 process solution?
Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

```
/*  P1   */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

/*  P2   */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2=false;
}
/* Remainder section */

```

Here, wants1 and wants2 are shared variables, which are initialized to false.

**What i have tried =\>**

Here, mutual exclusion is satisfied and deadlock is there, so no progress .

I am only having a doubt that bounded waiting can also be satisfied here as according to the definition, bound is here 0, so waiting is bounded here ?

**Is my understanding correct ?**

# Answer
Bounded waiting is satisfied, the process $p\_i$ will never be bypassed by $p\_{1-i}$ after changing the value of $w\_i$ (wants $i$) to $1$.

If $p\_i$ set the value of $w\_i$ to $1$, then in order to enter the critical section, $p\_{1-i}$ must pass the while loop. This cannot happen until the value of $w\_i$ is set to 0. The only place where $w\_i$ is set to $0$, is after $p\_i$ has finished, which means he will never be bypassed by $p\_{1-i}$.

When in doubt, try to prove it yourself. If you agree that the number of times a process may be bypassed is at most $0$, then yes, bounded waiting holds.
> 1 votes

---
Tags: concurrency, synchronization, deadlocks
---


# Question
Title: Show that the following tautology is a theorem of natural deduction
I'm struggling to apply the theorems of natural deduction to these two examples.

$$((p \to q) \land (p \to \neg q)) \to \neg p$$

$$((p \to q) \land (p \to r)) \to (p \to (q \land r))$$

Can anyone help? That is, soundness and/or completeness.

# Answer
I won't write natural deduction tree, but make a sketch of the proof.

* (( ⟶ )⋀( ⟶ ¬)) ⟶ ¬
To prove the implication, you fist assume ( ⟶ )⋀( ⟶ ¬). To get ¬, you assume and get a contradiction by getting both ¬ and .
* (( ⟶ )⋀( ⟶ )) ⟶ ( ⟶ (⋀))
Again, to prove an implication, you assume the antecedent ( ⟶ )⋀( ⟶ ). From this asummption you can get ( ⟶ ) (\*) and ( ⟶ )(\**) separately. Now you need again to prove another implication ⟶ (⋀), so you assume and get both and by using (\*) and (\**) with
> 3 votes

---
Tags: logic, propositional-logic
---


# Question
Title: having issue with numbers in Polymorphic Lambda Calculus
It is said that Church Numbers are encoded as following

```
   c0 = λX. λs:X->X. λz:X. z;
   c1 = λX. λs:X->X. λz:X. s z;
   c2 = λX. λs:X->X. λz:X. s (s z);
   c3 = λX. λs:X->X. λz:X. s (s (s z));

```

The church numbers are terms, right? but the terms are given by the following syntax.

```
  t ::=                          terms
       x                          //variable
       λx:T.t                     //abstraction
       t t                        //application
       λX<:T.t                    //type abstraction
       t [T]                      //type application

```

It seems church numbers do not respect the syntax of terms to me, strange.

I think it should be like

```
      c0 = λX<:some type here. λs:X->X. λz:X. z

```

So, how to write church numbers in a consistent way?

If possible provide simple examples to explain, i.e. 2 * 2, how to write this?

source

Thanks in advance!

# Answer
The syntax you written is probably of the System F\<:.

However, the typed Church numerals you written are introduced in the context of System F (a.k.a. λ2) at Fig. 11 of the source pdf.

The terms of System F are defined like below in *Types and programming languages* (Benjamin C. Pierce, MIT press, 2002):

```
t ::=           terms:
      x         variable
      λx:T.t    abstraction
      t t       application
      λX.t      type abstraction
      t [T]     type application

```

The typed Church numerals at Fig. 11 are terms in this definition.

Moreover, in System F\<:, Church numerals are also well-typed and can be more generalized. Below examples are taken from *Types and programming languages*. Top is the maximum type.

```
szero = λX<:Top. λS<:X. λZ<:X. λs:X→S. λz:Z. z;
sone  = λX<:Top. λS<:X. λZ<:X. λs:X→S. λz:Z. s z;

```
> 2 votes

---
Tags: lambda-calculus
---


title: Find Mapping Node in a Graph

text:
# Question
Title: Find Mapping Node in a Graph
Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar.

If we give a node in Graph A, how to find the corresponding one in Graph B?

Finally, we need to find all the node mappings.

Of course, there can be more than one possible mapping. We need to find the similarity (ranking) percentage.

How to design such an algorithm?

The graphs are Control-flow Graphs (Call Graph) extracted from program binaries. However, due to compiler difference (optimization, inline, etc.), the graphs can be a little different.

UPDATE:

To be more clear, as shown in the figure below, we also need to find the matching like B and B',B1' ("-\>" means a node match):

A -\> A'

B -\> (B' , B1')

C -\> C'

D -\> D'

E -\> E'

F -\> F'

As this is not a sub-graph matching, I cannot find good library APIs or algorithms.

# Answer
You want to solve the problem of *graph isomorphism* (GI). GI is not known to be in P or NP-complete; that is, we do not know any efficient algorithms.

Many algorithms have been proposed for GI. None applies to all graphs and is always fast, but you may be able to find one that is sufficiently fast in your application.

In 2015, Babai proposed a quasi-polynomial algorithm for GI \[1\]. As far as I know, peer-reviewed is not yet completed; I also do not know if it is practically feasible. If correct, it is the most "efficient" algorithm known in terms of Landau-style complexity.

---

1. Graph Isomorphism in Quasipolynomial Time by L. Babai (2015) \[retraction note\]
> 3 votes

---
Tags: algorithms, graphs, graph-isomorphism, network-topology
---


# Question
Title: Can I run Dijkstra's algorithm using priority queue?
I think I can run Dijkstra's algorithm using any data structure. I do not see any implementation details of Dijkstra's algorithm.

Is a priority queue a possible data structure? Will running Dijkstra's algorithm using a priority queue reduce or increase the complexity? Will I overshoot the problem?

# Answer
Yes, you can use priority queues to improve the complexity of the algorithm from $O(V^2)$ to $O(|E| + |V| \log|V|)$ where $E$ is the number of edges and $V$ is the number of nodes.

You should consider carefully the number of nodes in your graph and the desired run time before adding complexity to your implementation.

See here for a brief explanation of performance vs difficulty trade offs.

To summarize the blog, using a regular queue can still speed up Dijkstra's algorithm by up to a factor of 4 in most cases, with rarely occurring graphs running in $O(V^3)$. The link says "never" occurring, but that would depend on the actual problem you are solving.

See this for the original research on using min-priority queues to speed up Dijkstra's algorithm, it is the fastest known implementation for Dijkstra's algorithm.
> 7 votes

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


# Question
Title: Relation between witness and problem statement
Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size. For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested. To be a bit more clear, I'll explain what I mean in detail for two of those problems.

**UPDATE:** I assume the problem has a solution. So I am not interested in the decision version, but rather I assume there does exist a (positive) solution and I'm trying to find it.

For example, I give you a SAT problem and I tell you there is a solution, please find at least one. This should also be NP-complete. Now if the SAT Problem has 3 literals, it's easy to solve. If it has n/2 literals and n clauses, it's probably not easy. So my question is at what point it becomes easy and why.

In the case of subset sum. I give you a subset sum problem instance and ask you to find me one of the solutions, which I tell you exist. This is still hard to do, but is it also hard to do if I tell you that the/a solution will be a subset of number of size n/2 for a list of length n? Again, I'm interested in understanding at which sizes of the solution the problem becomes easy.

For hamiltonian cycles, I ask you to find a cycle of size $k$ in a graph of size $n$, for which $k$ is the problem hard and so on...

I looked at the analysis of Fixed Tractable Problems, but they seem to focus on parameters that are fixed to *constants*, which is not necessarily what I want to know I think.

My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $log(n)$ or bigger than $n-log(n)$, but I don't know how to actually support this claim formally.

I hope my question is a bit clearer now.

# Answer
> My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $\log n$ or bigger than $n - \log n$, but I don't know how to actually support this claim formally.

The first part of your intuition is sorta in the right direction, but the second part is wrong.

1. If the witness size is smaller than $\lg n$, then you can enumerate all witnesses efficiently: it takes $2^{\lg n}$ time to enumerate all witnesses, and $2^{\lg n} = n$, which is polynomial. In general, if the witness size is $\le c \cdot \lg n$ for some constant $c$, then you can enumerate all witnesses in $O(n^c)$ time, which is polynomial.

This means that you can solve the *decision* problem efficiently: just search all possible witnesses and see if any is valid. I'm assuming that when you say "the solution to a search problem", that is *defined* to be the witness that proves the answer is "YES".
2. However, if the witness size is bigger than $n - \log n$, there's no reason to expect it would be easy to solve the underlying search problem.

Perhaps you are thinking that the witness can't be any longer than $n$ bits long. That's wrong. Witnesses could be much larger than that, potentially, depending on the problem.
> 1 votes

# Answer
Consider a problem named 3SAT\_NORM which is a version of 3SAT restricted to instances wherein the number of literals used is equal to the number of clauses. For 3SAT\_NORM, every input of $n$ clauses requires the witness to give $n$ values for the satisfying assignment. Thus, you can't simply limit the size of the witness and relate the difficulty of the new problem -- the witness size is a function of the instance size.

But, you could conceive of a different witness than the usual one for 3SAT\_NORM. You could take a convention where if the witness to 3SAT\_NORM only defines some subset of the literals, then the other ones are automatically assumed by convention to be given an assignment of "true".

Now, suddenly, we can limit the size of the witness and make observations about the relationship -- in particular, restricting our witness to be smaller is the same as restricting 3SAT\_NORM to include only formula where satisfying assignments are guaranteed to have a lot of "true" values.

What I'm trying to get at is the witness is a property of a solution to the problem, not a property of the problem itself. SAT and subset sum seem to have "natural" witnesses, but there still could be other witnesses and some problems may have witnesses that are less natural. Some witnesses can be restricted in size, and others can't.

With this in mind, there is still one major observation we can take in mind. If we limit witnesses to size $f(n)$ then there are only $2^{f(n)}$ possible witnesses so for small functions $f$ we can simply evaluate each possible witness to see if it works. In other words, by looking only at small enough witnesses, the problem is easy. This means if witnesses to inputs of size $n$ are guaranteed to be $log(n)$ in size, then the original problem can be solved in pseudo-polynomial time, and if the witnesses are guaranteed to be constant size then the original problem can be solved in polynomial time.
> 1 votes

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


# Question
Title: Use examples to identify the need of join dependency
> Use examples to identify the need of join dependency.

This is what I have gathered from different website's.

1. SQL joins are used to combine rows from two or more tables.
2. A **Join Dependency** (**JD**) over a relation schema R is a statement of the form |\>\<|\[schema(R1), schema(R2), …, schema(Rn)\], where **R** = {R1, R2, …, Rn} is a database schema such that schema(**R**)=schema(R).
3. The general lossless decomposition constraint, involving any number of projections, is also known as a join dependency.

# Answer
Suppose we had a relation $R(A,B,C)$ and we decomposed it into two relations $S\_1(A,B)$ and $S\_2(B,C)$. Then we'd like the decomposition to have the property that the natural join of the projected relations $\Pi\_{A,B}(R)$ and $\Pi\_{B,C}(R)$ would produce $R$. Essentially, we'd like to be able to retrieve the original $R$ from the two relations in decomposition $S\_1, S\_2$, which is exactly what the join dependency in your question requires.

This won't always happen. Suppose we had this instance of $R$: $$\begin{array}{ccc} A & B & C \\ 1 & 2 & 3\\ 2 & 2 & 4 \end{array}$$ Then projecting $R$ onto $S\_1(A,B)$ and $S\_2(B,C)$ would give us, respectively $$\begin{array}{ccccc} A & B &\qquad\qquad & B & C\\ 1 & 2 & & 2 & 3\\ 2 & 2 & & 2 & 4 \end{array}$$ and so in the join $S\_1\bowtie S\_2$ we'd have $$\begin{array}{ccc} A & B & C\\ 1 & 2 & 3\\ 1 & 2 & 4\\ 2 & 2 & 3\\ 2 & 2 & 4 \end{array}$$ Notice that the join contains the original tuples $(1,2,3),(2,2,4)$ of $R$, but we've introduced two spurious tuples in the join, $(1,2,4),(2,2,3)$, which were not in the original relation $R$. This is a situation we certainly don't want to have, which is why any such decomposition should satisfy the join dependency.
> 1 votes

---
Tags: database-theory, databases
---


# Question
Title: Approximation Algorithm for the Unique Coverage Problem
I was reading about the $\mathcal{O}(\frac{1}{\log n})$ approximation algorithm for the Unique Coverage Problem from these notes.

The gist of the algorithm is as follows:

> * Partition the elements into $\log n$ classes according to their degrees, i.e., the number of sets that cover the element. So class $i$ contains all the elements which are covered with at least $2^i$ and at most $2^{i+1}$ sets.
> * Let $i$ be the class of the maximum cardinality.
> * Choose any set with probability $\frac1{2^i}$

Then in Lemma 3, they go on to show that

> **Lemma 3:** The expected number of the elements uniquely covered from class $i$ is $\frac{1}{e^2}$ fraction of the element in class $i$.

I was able to follow the algorithm till here but I am completely stumped as to how they arrived at the statement immediately following lemma 3

> Therefore, the total profit of uniquely covered elements is at least $\frac{1}{e^2 \log n} \times \text{opt}$

How did they arrive to this conclusion? They didn't even show what the upper bound is for this maximization algorithm. What am I overlooking?

It is trivial to prove that the expected number of unique elements covered by the algorithms is $\frac{n}{e^2}$ since it directly follows Lemma 3 but that is about all that I am able to observe :/

# Answer
> 3 votes
Suppose there are $m$ elements and $n$ sets (this is the meaning of your parameter $n$). The algorithm divides the set of elements into $\log n$ classes, so one of these classes, say class $i$, contains at least $m/\log n$ elements. Lemma 3 shows that if you pick each set with probability $1/2^i$, then in expectation you uniquely cover a $1/e^2$ fraction of the elements in class $i$. Thus, you uniquely cover at least $m/(e^2\log n)$ elements in expectation. On the other hand, the optimal cover uniquely covers at most $m$ elements. Thus the approximation ratio of this algorithm is at least $1/(e^2\log n)$.

---
Tags: algorithms, approximation
---


# Question
Title: What simple arguments and insights can I observe that running both BFS and DFS can be achieved in O(|V| + |E|)?
BFS and DFS can be achieved in O(|V| + |E|). I understand the proof but it seems a bit lengthy.

* Can I argue O(|V| + |E|) in a very simply way? e.g. checking each edge at most once?
* Also what does O(|V| + |E|) imply?

I know Dijstrka algorithm and many other algorithm is somewhat like BFS. Does it imply automatically they can be run in |V| + |E| is the lower bound?

# Answer
Intuitively, what a time upper bound of $O(|V| + |E|)$ means is that you spend $O(1)$ time per each vertex and each edge. Taking as an example DFS, there is one recursive call per edge, and the procedure itself runs once per vertex. You can turn this into a full-fledged argument that proves the upper bound.

An upper bound of $O(|V| + |E|)$ is optimal for most graph problems – those that potentially require examining all vertices and all edges. What such an upper bound tells you is that your problem can be solved in the minimal possible time; an $O(|V| + |E|)$ algorithm is an asymptotically optimal algorithm.
> 1 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, graph-traversal
---


# Question
Title: Which m numbers in the range [1, k] have sum equal to n
Given the values of $n, k, m$, you have to check if there are $m$ distinct numbers in the range from 1 to $k$ have the sum $n$ or not ?

$n$ represents the required sum $k$ represents numbers range(1,2,3,... to k). $m$ is the number of elements in the range from 1 to $k$ that has the sum $n$.

Example: n = 12, k = 8, m = 3 ==\> there are 3 numbers in the range from 1 to 8 that have the sum 12 which are 2,3,7.

The problem is taken from hackerrank and called bonetrousle.

# Answer
> 5 votes
Hint:

1. What is the *smallest* number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?
2. What is the *largest* number that can be represented as the sum of $m$ distinct integers from $1$ to $k$?
3. Can all numbers in between be so represented?

---
Tags: algorithms
---


# Question
Title: Example of a language that is neither recognizable nor co-recognizable?
Is there an example of a language that is neither recognizable nor co-recognizable?

A relevant (easy) theorem is that a language is decidable iff it is recognizable and co-recognizable.

An example of an undecidable language is the set "acceptance problem," i.e. the set of strings (Turing Machine = M, string = s) such that M accepts s. It is recognizable and not co-recognizable.

A less "constructive" proof that there exist unrecognizable languages is that there are uncountably many languages and countably many TMs. I believe this also establishes the existence of languages that are not recognizable or co-recognizable.

Is there an "example" of such a language?

I put "constructive" and "example" in quotes because I suspect I am creating a meta-logical contradiction, whereby stripping a language of recognizability and co-recognizability also strips it of the forms of describability that might intuitively constitute a "construction" or "description." I am interested in any results that make rigorous how to "talk" about languages that are not recognizable or co-recognizable, or any hardness results on doing so.

# Answer
> 3 votes
The language TOT of all Turing machines halting on all inputs is $\Pi\_2$-complete, and so is neither recognizable nor co-recognizable. You can find more examples if you search for material on the arithmetical hierarchy. Anything beyond $\Sigma\_1$ and $\Pi\_1$ will fit your bill.

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


title: What actually is Blocking flow problem?

text:
# Question
Title: What actually is Blocking flow problem?
I am facing a hard time understanding Blocking Flow problem. This is what I have understood till now : We have a graph and in blocking flow problem we find all shortest paths from source to destination and saturate atleast one edge in all of the shortest paths respectively \[1\] and we delete that path. In examples I am reading online, it is explained with an example of graph with all edges of unit length \[2\]. Our professor explained the solution to this using dynamic trees. I am unable to apply the concept of dynamic trees (splay) for the solution of this problem. What will be stored in the nodes of the tree and on what basis will we perform the spaly operation?

\[1\] There can only be one shortest path, or many shortest paths of same length. What is the concept of all shortest paths?

\[2\] If a graph has all edges of unit lengths, then all the edges will be deleted (because all will appear in some path from source to sink). Then, source and destination will be disconnected in the end. What would be the use of doing this?

What is the goal for solving this problem? Can someone point in right direction in layman's terms? Also I have read some articles regarding this but unable to understand them and also none of them uses splay trees to solve this problem.

# Answer
A *blocking $s$-$t$ flow* is a flow whose residual network (consisting of all edges not saturated by the flow) contains no $s$-$t$ path. Stated differently, a blocking flow is a flow which, for every $s$-$t$ path, saturates at least one edge. Equivalently, a blocking flow is a flow which, for every simple $s$-$t$ path, saturates at least one edge.

The blocking flow problem is to find a blocking flow in a flow network. Such a flow exists since a maximum flow is always a blocking flow (but not vice versa).

The concept of blocking flow is used in Dinitz's maximum flow algorithm.
> 4 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Difference between capacity miss and conflict miss
Premise:

1. Two types of cache miss: capacity miss, conflict miss\
2. Cache contains only 2 sets, SET 1 and SET 2

Problem:

If data A maps to SET 1 and it doesn't exist in SET 1 while SET 1 is fully occupied and SET 2 is *not* fully occupied, I know this case is called conflict miss. But what should it be called if the same case but entire cache is fully occupied? Is it capacity miss or conflict miss? Once the cache is fully occupied, conflict miss will never happen?

# Answer
> 2 votes
It will be capacity miss because capacity miss means that your cache is full and there is no way to accommodate the data A. Yes it means Once the cache is fully occupied, conflict miss will never happen.

---
Tags: terminology, computer-architecture, cpu-cache
---


# Question
Title: White-space and comment by lexical analyzer
Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in python. But I can't think of practical example where comments are/should be kept by Lexical Analyzer? Is there any such example you can think of?

# Answer
White-space and comments can contain valuable information.

For white-space, you can look at layout sensitive languages, like Python or Haskell. I'm not sure how their lexers work, but off the top of my head I would store an indentation level, not the actual white-space.

For comments, it can be useful to store these if you want to generate documentation from Javadoc-style comments. For Javadoc, the parameter types do not have to be specified in the docblock (unlike PHPDoc, for instance). This means that a documentation generator would have to look at both the comments and the method header (everything before `{`). For the latter the lexer can be used, for the former it cannot (presuming the lexer removes comments).

I'm note sure how Javadoc-based documentation generators work, so perhaps the above is inaccurate, but the general idea is correct. I'm working on the Cloogle project, a Clean function search engine similar to Haskell's Hoogle. We hook into the Clean compiler to parse function types from all standard libraries. It would be nice if we could show comments around the definition as well, but the lexer removes this information. So, if we want to display comments, we have to adapt the compiler's frontend, or write a simplistic program that finds comments around some function, without lexing everything. If the lexer and parser would store comments, we would have a much more elegant solution.
> 5 votes

---
Tags: compilers, parsers, lexical-analysis
---


# Question
Title: Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language?
In programming language theory, there are operations which are distinguished between static and dynamic, e.g. static/dynamic scoping, static/dynamic typing, ....

Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language?

Let me explain the above question and my thoughts and confusions about it.

1. Is it correct that a static operation means the operation is performed at compilation time, and a dynamic operation means it is performed at run time?
2. When an operation is performed by an interpreter, is it at compilation time or run time?

It seems to me that people often says it is at run time.

But if I am correct, an interpreter first translates and then executes a program, so to answer the question, do we need to specify whether the operation is performed when the interpreter translates or executes a program?
3. Does a static operation imply that the language under consideration is implemented by a compiler but not by an interpreter?
4. Does a dynamic operation imply that the language under consideration is implemented by an interpreter but not a compiler?

Thanks.

# Answer
> 3 votes
First, as a commenter mentioned, there isn't necessarily a clear general distinction between compilers and interpreters. A compiler is a program that takes source code, and produces a program which takes the input and produces the output. An interpreter is a program that takes source code and an input and produces the output. Under this definition, there are fairly trivial ways of converting an interpreter into a compiler and vice-versa (this is called the curry/uncurry operation in functional programming). There are also some more interesting general ways like partial evaluation.

What is true is that you may define the execution semantics of many programming languages may be defined on an abstract machine which loses much of the information in the original program. Most interpreters do this in some sense.

Second, keep in mind that all the various uses of "static/dynamic" are different things. For example, a static architecture is one where each component may only be connected to a fixed set of other components, while a dynamic architecture is one where some process connects them (e.g.: dependency injection). Most compilers are completely unaware of your application's architecture, so this question is pretty irrelevant for static/dynamic architecture.

In particular, for your question, "static typing" and "dynamic typing" are not really even on the same dimension. "Dynamic typing" is not a type system, although using it typically requires having an `Any` type. "Static typing" is usually just called "typing."

Anyway, from both a practical and theoretical perspective, anything an interpreter can do a compiler can do, and vice versa.

---
Tags: programming-languages
---