# Question
Title: Are all computational complexity results oracle results?
When talking about the complexity of a given operation, say multiplication of numbers, one usually counts the number of "elementary operations" that are required.

For example, a common argument says that multiplying two $n$-digit numbers with the schoolbook standard method takes $O(n^2)$ operations, while more sophisticated techniques give complexities closer to $O(n)$.

In these examples, what is counted is the number of single-digit operations, but then the complexity of those operations themselves is not taken into account. Isn't this then essentially an oracular result, in the sense that it tells us the number of operations we have to perform, *provided we have a magical box solving single-digit operations*?

# Answer
> 4 votes
The issue you are highlighting is that of *computation model*, which is how we measure the resource consumption of an algorithm. The computation model specifies how to assign time complexity, space complexity, and so on to a given program (whose syntax it also specifies). There are three popular computation models:

* Turing machines, of various sorts.
* Boolean circuits.
* RAM machines, of various variants.

A variant of the RAM machine can be specified in terms of the allowable *basic operations*, which is the issue that you encountered. For Boolean circuits, the analog is the set of allowable gates, and for Turing machines there seems to be no such analog.

---

In contrast, here is an actual example of how oracles are used in theoretical computer science.

A *submodular function* is a set function $f\colon 2^U \to \mathbb{R}$ (i.e., a function that accepts a subset of $U$ as input, and returns a real output) that satisfies a technical constraint known as *submodularity*.

*Submodular optimization* is the field which studies how to optimize submodular functions relative to various constraints (including no constraints).

A typical problem is:

> Given a submodular function, find its minimum.

How is the submodular function "given" to us? It could be given to us as a truth table (i.e., the value of $f(A)$ for any $A \subseteq U$), but this is not a realtistic assumption. Rather, there is often an efficient algorithm that computes $f$. In most cases we are interested in an algorithm which is oblivious to the exact algorithm used to compute $f$. In these cases, we are looking for an algorithm which has *oracle access* to $f$, that is, the function $f$ is provided as an input *oracle*.

(In other cases we would like to use the code for $f$. This happens usually when $f$ has a particular structure, for example if it is a *coverage function*. In cryptography we sometimes want to "open the black box" even when $f$ has no particular structure.)

# Answer
> 3 votes
No, this has nothing to do with oracles. We don't use a "magic box" for that; we use a small circuit. Usually our computers work with binary, so "single-digit" means "single-bit". And hopefully you can see how single-bit operations can be implemented with gates: for instance, multiplication of two single bits is just an AND gate, and so on. So there is no need for an oracle; we just implement those single-bit operations directly.

Oracles are something different.

---
Tags: complexity-theory, programming-languages, computation-models
---


# Question
Title: How to restore diagonal-symmetric matrix that has been shuffled?
I have a square matrix M, which originally looked like this: `133 199 101 121
142 133 199 101
156 142 133 199
108 156 142 133` (so symmetric around the diagonal). Not only that, but each diagonal is constant, so `M'[i, j] = M'[p, q] if i + j == p + q` , however it has been shuffled both row-wise **and** column wise. The only solution I could think of was brute forcing all permutations of the rows and columns which is O(n!\*n!), which is obviously suboptimal. I also thought of the fact that in this specific matrix, the value counts are 1 2 3 4 3 2 1, but the original matrix is way bigger and there are many duplicate values.

The last idea I have is some sort of greedy reshufling that would work like so:

1. for each column, find the column that has the most similar values (albeit shuffled).
2. place them together
3. repeat until convergence
4. repeat for rows.
5. repeat 1-4, but this time take into account the ordering too.

That idea seems unsatisfying though.

The full data is not too huge, 5000x5000, and I only need to restore it once, so I'm not nessecarily looking for *the* most efficient way, just a robust and easy to implement solution.

# Answer
> 1 votes
First, note that the matrix can only be restored up to a permutation of the diagonal. To illustrate on your example, when we swap two bottom rows and two left columns, the resulting matrix is also diagonal-symmetric:

```
133 199 101 121                             199 133 101 121
142 133 199 101        transforms to        133 142 199 101
156 142 133 199                             156 108 142 133
108 156 142 133                             142 156 133 199

```

So, the good news is, instead of searching for a row permutation and a column permutation, we can fix the order of the rows and permute only columns. Indeed, if we took the original matrix and permuted the rows in any fixed order, by permuting the columns in the exact same order, we get a diagonal-symmetric matrix.

---

Next, note that, before the permutations, the multiset of numbers in row $1$ was exactly the same as the multiset of numbers in column $1$. The same holds for row $2$ and column $2$, and so on.

After permutations, say row $1$ landed at row $i$, and column $1$ landed at column $j$. Then, the multiset of numbers at row $i$ is still the same as the multiset of numbers at column $j$.

Importantly, the problem seems to be about some large and more-or-less real data, so it is likely that the converse also holds: for any two rows, the multisets of numbers in them are different. If not, perhaps what follows can be tricked to fail by constructing the appropriate data. Anyway, the check is straightforward.

---

Having noted the above, I propose the following simple algorithm:

1. Write down the multiset of numbers $S\_1$ in the bottom row. (A sorted array will suffice for storage and comparison.)
2. Search for the column which contains the exact same multiset of numbers $S\_1$.
3. Swap this column with the leftmost one.
4. Proceed with the next-to-bottom row and find its multiset $S\_2$.
5. Search for the column except the first one which contains the exact same multiset of numbers $S\_2$.
6. Swap this column with the second-to-leftmost one.
7. Et cetera.

---

The algorithm can run in $O (n^2 \log n + n^2)$, with some hashing. First, for each of the $n$ rows and each of the $n$ columns, calculate a hash of the multiset of numbers in it (for example, make a sorted array in $O (n \log n)$ and get its polynomial hash). Then, we can consider hashes instead of the rows and columns of the real matrix. After we find the needed permutation of rows, apply it once in $O (n^2)$.

---
Tags: data-structures, time-complexity, greedy-algorithms, permutations
---


# Question
Title: Is TD-learning considered a model-based algorithm?
Differently from Sarsa and Q-learning, pure temporal difference learning (TD-learning) works with state value functions $V(s)$ and not state-action Q value functions $Q(s,a)$. It means that, in order to select the best action at state $s$, the resulting state $s'$ for every possible action must be computed, so we can get $V(s')$. Thus, we need a model for computing $s'$ from a $(s,a)$ pair. Is that correct? Does that mean that TD-learning can be considered a model-based technique? Or in the case of TD-learning we consider it just a value updating algorithm and ignore the control part, thus removing the need for a model?

# Answer
> 3 votes
The previous answer is wrong. TD-learning is a model-free algorithm.

You compute $V\_{\pi}(s)$ for a fixed policy $\pi$, then you update your policy based on $V$ a la policy iteration.

Source: https://webdocs.cs.ualberta.ca/~sutton/book/ebook/node60.html

# Answer
> 2 votes
Yes. TD learning is a model-based RL algorithm because you can't extract a policy from $V(s)$ without having a transition model $T(s,a,s')$ to sample next states from. I.e., knowing $V^\*(s)$ is useless in terms of decision making if you don't also have a model of the MDP. The reason Q-learning and SARSA are considered model-free is because you don't need such a model of the MDP in order to extract a policy from a Q function.

# Answer
> 1 votes
For prediction problems, in TD(0) we don't need to (greedily) pick a action based on $V(s)$, so it's not a model-based algo.

As for control problems, Q-learning & Sarsa are both TD algos, and it's obivious that they are both model-free control algos.

However, if you want to use $V(s)$ in a control problem -- it's definitely model-based and that is **exactly** why we need a state-action function. (You might turn to David Silver's video. In the Lecture 6 (around 51:20), he said "... we need to use action value function Q, so we can make it model-free and still be able to pick the greedy action." )

---

In short, TD is a really big class of algos, and you cannot simply say "TD is model-free" nor "TD is model-based".

Since MC is generally considered model-free but MCTS is also model-based.

---
Tags: terminology, machine-learning, reinforcement-learning
---


# Question
Title: Ideas on how to approach the construction of a probability-heavy algorithm
## Definitions

Assume we have a Shopping List $L$ which is a list of pairs of Items and Quantities: $L = \[(i\_1, Q\_1), (i\_2, Q\_2), (i\_3, Q\_3) ...$

We also have a Stock List $S$ which is a list of pairs of Containers and Prices: $S = \[(C\_1, p\_1),(C\_2, p\_2), (C\_3,p\_3)...\]$

Each container is a list of 3-tuples of Items, Quantities, and Probabilities: $C\_n = \left\[\left(t\_1,q\_1,\frac{a\_1}{b\_1}\right), \left(t\_2,q\_2,\frac{a\_2}{b\_2}\right), \left(t\_3,q\_3,\frac{a\_3}{b\_3}\right)...\right\]$

Purchasing a container for a given price gives you a chance of getting each item within it. The chance is equal to each item's probability. The probabilities are *independent* of each other (two items with a probability of 1/2 are treated as two coin flips, it isn't "one or the other"), and their quantities are absolute. If we had $C\_1 = \left\[\right(x, 2, \frac{1}{2}\left)\right\]$, then there is a one-in-two chance of getting two $x$s, and no chance of getting only a single $x$.

## The Goal

I'm trying to come up with some algorithm which has the ultimate goal of satisfying a given shopping list from some stock list. Due to the random nature of the problem, it is impossible to construct a definite chain of purchases to make. Thus, I was thinking that `foo(L, S)` should return the best next purchase -- the container to buy which satisfies the most items in the shopping list for the lowest price. Purchasing this container can affect the shopping list in a variety of ways, so upon purchasing, the list will be run through the algorithm again and again until it is empty.

## My Attempts

If I could construct a function which outputs some "instantaneous value" of each container, I could then calculate and sort each container by this value and purchase the one highest-valued one.

This value of a container would be its benefit minus its cost. Calculating the cost of containers which contain only one needed item is simple enough, but I'm stumped on containers with multiple items. Consider this example:

$L = \[(x, 1), (y, 1)\]$

$S = \left\[\\ \left(\left\[\left(x, 1, \frac{1}{2}\right)\right\], 10\right),\\ \left(\left\[\left(y, 1, \frac{1}{2}\right)\right\], 10\right),\\ \left(\left\[\left(x, 1, \frac{1}{3}\right),\left(y, 1, \frac{1}{3}\right)\right\], 20\right)\\ \right\]$

(The first container costs \\$10 and has a 1/2 chance of giving an $x$. The second container costs \\$10 and has a 1/2 chance of giving a $y$. The third container costs \\$20 and has a 1/3 chance of giving an $x$, and a 1/3 chance of giving a $y$.)

The cost of getting an $x$ from the first container is \\$20. This would satisfy one out of two of our list's requested items. If our strategy for satisfying the list was to brute-force the first container, then the second, the total cost of the list would be \\$40.

What gives me trouble is that third choice. There is a 1/9 chance of spending only \\$20 and getting both of our $x$ and $y$ in one move. There is a 4/9 chance of spending \\$20 and getting either our $x$ or $y$ -- we could then get the remaining one for \\$20 and be done for \\$40. Finally, there is another 4/9 chance of getting nothing.

I suspect that the best path in this case is to buy the third container until at least either an $x$ or $y$ is obtained, then buy the remaining one from the first or second container. (Edit: A simulation shows that solely buying containers 1 and 2 leads to an average cost of \\$40 to satisfy the list, as expected, but buying the third container then one or two leads to an average cost of \\$52 to satisfy the list. Besides simulating, I'm unsure of how to derive that 52)

Any ideas on how to approach this?

# Answer
> 1 votes
One plausible approach would be to use integer linear programming. The following won't be optimal, but it might be decent.

We could try to find quantities $x\_1,x\_2,\dots$ for the containers, so that if we buy that many containers, the expected number of each item is at least the desired quantity. This leads to an integer linear program, with one inequality per item

$$\sum\_i x\_i q\_{i,j} p'\_{i,j} \ge Q\_j$$

where $q\_{i,j}$ is the number of item $j$ in container $i$, and $p'\_{i,j}$ is the corresponding probability. Then, we want to minimize $\sum\_i x\_i p\_i$, the total price of these containers, where $p\_i$ is the price of the $i$th container. You could use an off-the-shelf ILP solver to solve for the $x\_i$'s, or as a heuristic, use a linear programming solver and ignore that the $x\_i$'s need to be integers.

Then, you could randomly sample a container, with container $i$ sampled with weight proportional to $x\_i$. This is a heuristic, but it might help identify which container you most want to buy, so it might work well enough in practice.

You shouldn't expect any efficient algorithm that gives the optimal solution; this problem is NP-hard, by reduction from the knapsack problem.

---
Tags: algorithms
---


# Question
Title: How to find the virtual pages and physical memory frames?
So i am given a system of 20 bits virtual addresses and 18 bits physical addresses using paging with pages size 4Kbytes. I am told to find the maximum number of virtual pages that a process can have and the maximum number of physical memory frames the system can have.

So 2^12 page size makes 12 bits for offset and 8 bits for page number right? and 2^8 is 256 is the maximum virtual pages that a process can have? Correct me if im wrong.

And for the second one im having kind of trouble. Ive seen a post about a similar question but didn't really understand it. Is it 2^18 bits for physical address multiplying it with the page size like (2^18)\*4096 to get the maximum physical memory frames?

Also a last part gives me the following:

00110110011110111100

and says the virtual page containing the address is mapped onto physical frame 45, give the corresponding physical address in binary format. How do i find that?

# Answer
> So 2^12 page size makes 12 bits for offset and 8 bits for page number right? and 2^8 is 256 is the maximum virtual pages that a process can have? Correct me if im wrong.

you are correct

> maximum number of physical memory frames the system can have.

the size of frames is the same as the size of pages

so you have 18 bit for physical memory, which 12 bit of that is needed for the offset, now you are left with 6 bit which means you can have $2^6$ frames.

> Also a last part gives me the following:
>
> 00110110011110111100
>
> and says the virtual page containing the address is mapped onto physical frame 45, give the corresponding physical address in binary format. How do i find that?

**00110110** 011110111100

so the 12 bits from the right are for the offset which you dont need to change, the remaining 8 bit which is 00110110 needs to be replaced with 45 and instead of 8 bit we would use 6 bit to map into physical address

therefore the physical address would be **101101** 011110111100

this means that in the 54th row (00110110) of our page table for that process we would find the corresponding frame for that page to be 45 (101101)
> 1 votes

---
Tags: paging
---


# Question
Title: Find if a sequence of nodes is yielded by a preorder traversal of a binary tree
Assume we have a sequence of $0$s and $1$s: $n\_1, n\_2, ..., n\_N$, in which $0$ stands for a leaf node, and $1$ stands for an uncertain node that may or may not be a leaf node. How can we check if this sequence is a valid result of a binary-tree preorder traversal?

Ex. $1, 1, 0, 1, 1, 0, 0, 1$ is a valid sequence.

```
          1
         / \
        1   1
       /   / \
      0   1   1
         / \
        0   0

```

# Answer
> 1 votes
The idea of construction in fade2black's answer is correct (while the pseudocode may be buggy). I rewrite it here:

```
FOR i = 2 to n:
  IF root.left is free:
    root.left = make_node(n[i])
    IF n[i] == 1:
      root = root.left
  ELSE:
    # backtrack until root.right is free or we reach the ROOT - highest node
    WHILE root is not nil AND root.right is not free:
      root = root.parent
    IF root is nil:
      RETURN failure
    root.right = make_node(n[i])
    IF n[i] == 1:
      root = root.right

```

Its correctness can be proved by mathematical induction on $n$. Base cases are trivial.

Assume a sequence of length less than $n$ is valid if and only if a tree can be constructed by the algorithm. Now consider a sequence of length $n$.

If a tree can be constructed by the algorithm, the sequence is obviously valid.

On the other hand, if the sequence is valid, it must be $1, a\_1,\ldots,a\_p, b\_1,\ldots,b\_q$ where $a\_1,\ldots, a\_p$ and $b\_1,\ldots,b\_q$ are both valid sequences ($p$ or $q$ may be 0). By inductive assumption, the algorithm can construct a tree as the left subtree of the root from $a\_1,\ldots,a\_p$. Then the algorithm is handling $b\_1$. Note the right child of the root is free, so the algorithm will not return "failure" during backtracking and successfully constructs $b\_1$. By inductive assumption again, the algorithm sequentially constructs a subtree from $b\_1,\ldots,b\_q$. As a result, a tree is successfully constructed from the sequence $1,a\_1,\ldots,a\_p,b\_1,\ldots,b\_q$.

# Answer
> 0 votes
### Idea of a tree construction

If the length of the sequence is $1$ then just make the first symbol root and stop with SUCCESS. If the first symbol of the sequence is $0$ then construction is not possible, otherwise make it the ROOT and set the root to the ROOT.

```
for i = 2 to n
 if n[i] is 1 then
   if root.left is free
     root.left = make_node(n[i])
     root = root.left #go to left
   else if root.right is free then
     root.right = make_node(n[i])
     root = root.right #go to right
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 else if n[i] is 0 then
   if root.left is free
     root.left = make_node(n[i])
   else if root.right is free
     root.right = make_node(n[i])
   else
     # backtrack until root.right is free or we reach the ROOT - highest node
     root = root.parent until root is nil OR root.right is free
   end
 end

 if root is nil then break
end

if i < n the construction impossible

```

### Checking without a tree construction

The basic idea is at each step to count how many nodes we can add to the tree. When we read $1$, we add one internal node which allows to add two new nodes and hence $-1+2 = 1$ and so we increment the counter by one. When we read $0$ we add a new leaf and so we decrement the counter.

```
if a[0] == 0 then
  return FAILURE
else
  counter = 2

for i=2 to n
  if a[i] == 1 then
    counter = counter + 1
  else
    counter = counter - 1
  end

  if counter == 0 then break
end

if i < n then
  return FAILURE
else
  return SUCCESS
end

```

### Construction example

$1,1,0,1,1,0,0,1$

```
  1 =>  1  => 1  => ... =>  1
       /     /             /
      1     1             1
           / \           / \
          0   1         0   1
                           / \
                          1   1
                         / \
                        0   0

```

### Checking example

c=2, c=3, c=2,c=3, c=4, c=3, c=2, c=3, SUCCESS

At the end c=3 means we still can add 3 leaves.

---
Tags: algorithms, binary-trees, graph-traversal, backtracking
---


# Question
Title: Making 5-tuples out of their respective 4-tuples
Let's take integer numbers from \[1..36\]. We can generate 376992 different (order is not important) five-number-combinations like (1,3,5,7,12), etc. Such five-number-combinations always have five distinct (unique) numbers. Each such five-number-combination always contains 5 four-number-combinations (like (1,3,12,7), etc.). All 376992 different (unique) five-number-combinations have 58905 different (unique) four-number-combinations. All these four-number-combinations also have all (four) distinct numbers - being a subset of a set with unique numbers.

**Five-number-combinations and four-number-combinations (tuple-4) always have 5 or 4 distinct (unique) numbers respectively. This is prohibited: (1,1,2,3,4) or (2,3,5,2)**

Then I take at random approximately half of those 58905 different four-number-combinations - let's call them "unused 4-tuples".

Finally I need to generate *all possible* five-number-combinations each being such that it always consists of 5 unused four-number-combinations. That is all five four-number-combinations within such five-number-combination are from the "unused 4-tuples" set.

Direct (brute-force) algorithm is like this: I take a set of n=28000 unused 4-tuples, generate all combinations from that set by k=5 (binomial(n,k)) and then check that all five 4-tuples in such combination give exactly five numbers from \[1..36\] (say, I add individual numbers from every 4-tuple \[out of every five 4-tuples\] into a set and then check if the set contains exactly five numbers). Having checked all possible combinations (of five 4-tuples) I have solved my task.

The only problem is that binomial(30000,5) = 143368518402340005600 :)))

Could you think of some math trick to somehow sieve and shortcut that process, or maybe a tip to a more clever algorithm?

# Answer
> 4 votes
Go over all $\binom{36}{5}$ possible five-number combinations. For each one, calculate the five four-number combinations, and check whether all of them are unused.

In order to check whether a given four-number combination is unused, you can use a table. This will allow each such test to proceed very quickly. You can either use an array of size $36^4$ using the trivial encoding, or a slightly more sophisticated one of size $\binom{36}{4}$.

---
Tags: algorithms, combinatorics
---


# Question
Title: Artificial intelligence and undecidibility
Can artificial intelligence solve problems like Post correspondence problem?

# Answer
No. The Post correspondence problem is undecidable. That means that no computer program can solve it (in all cases). "Artificial intelligence" is just a computer program. Actually, "artificial intelligence" is a name for something that we're not even sure how to do with a computer program; but even if we knew how to achieve it, it would still be a computer program. Artificial intelligence isn't magic -- anything that can be done is still constrained by the laws of physics and mathematics.
> 6 votes

---
Tags: undecidability, artificial-intelligence
---


# Question
Title: Different context-free grammars for the same language
In context-free grammar, are both the following grammars correct for the same language?

$$L = \\{a^mb^n : m, n \in N\_0 \text{ and } m \ne n\\}$$

**(grammar one)**

$S \to S\_1 | S\_2$

$S\_1 \to A\_1B\_1$

$A\_1 \to aA\_1 | a$

$B\_1 \to aB\_1b | \epsilon$

$S\_2 \to A\_2B\_2$

$A\_2 \to aA\_2b | \epsilon$

$B\_2 \to bB\_2 | b$

**(grammar two)**

$S \to S\_1 | S\_2$

$S\_1 \to \epsilon | aA\_1$

$A\_1 \to aA\_1 | aB\_1$

$B\_1 \to aB\_1b | a$

$S\_2 \to \epsilon | A\_2b$

$A\_2 \to A\_2b | B\_2b$

$B\_2 \to aB\_2b | b$

Is there a rule I could use to check whether the grammar is correct for the given language (other than trying all the strings that come to my mind)?

# Answer
Grammar 1 matches `a`. Grammar 2 does not. So they are not identical, and at least one of them is not a grammar of your indicated language.

As Yuval Filmus indicates in a comment, the general question of whether two CFGs produce the same language is undecidable. Obviously, it can be decided in certain cases (such as this one); searching for a counterexample is usually straightforward, although it obviously won't terminate if the two grammars turn out to produce the same language.

For simple exercises like this one, you should be able to prove (or disprove) that a grammar produces a given language. A simple technique which often works is induction over the length of the string.
> 2 votes

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


# Question
Title: Does data entropy depend on the arrangement of the characters in a file?
From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing 256 different symbols and we made a bigger file consisting of many copies of that file, And because the small file has the maximum entropy a file of its size can have, the big file will also have that high entropy (because all characters have the same probability). Although that file has high entropy it still can be compressed to a very smaller size. What did I misunderstand here?

# Answer
> 1 votes
Entropy is a property of the source of the data, i.e., of the distribution that the data is drawn from -- not a property of the particular file. You can't calculate the entropy given a single file. Instead, you need to know the distribution that file came from. Or, to put it another way, the entropy is a measure of the process used to generate the particular file, not a measure of one particular file you happened to get from that process; and observing one output from that process isn't enough to let you calculate the entropy of the process. So, the question isn't well-formed.

You might be thinking of forming the empirical distribution of characters, then assuming the file came from a memoryless iid source (where each character was drawn independently according to that distribution), and then calculating the entropy under that assumption. But that assumption doesn't hold for your bigger file, so this isn't a valid way of calculating the actual entropy of the process that was used to generate the bigger file.

To learn more: How to practically measure entropy of a file?, https://en.wikipedia.org/wiki/Entropy\_(information\_theory).

---
Tags: terminology, information-theory
---


# Question
Title: why it said the "The left recursion has been removed at the cost of an extra non-terminal symbol(E1) and a little extra complexity"?
When I read the book **"A Practical approach to compiler construction"** the chapter 4 "approaches to syntax analysis" and the section 4.2.3.3 **Left Recursion**, it says:

> "The left recursion has been removed at the cost of an extra non-terminal symbol"

I have no idea why say that, since $A\_1$ still contain recursion?

# Answer
That grammar has recursion but not left recursion. Check the definition of left recursion (e.g., https://en.wikipedia.org/wiki/Left\_recursion, or consult your favorite textbook on formal languages).
> 1 votes

---
Tags: automata
---


# Question
Title: Data structures that store efficiently detected features of an image
I struggle to find this, suppose I apply any feature detection algorithm. From my references it seems to me it's not usually explained what kind of data structures would be suitable for storing such features.

For example in opencv it seems to me that the Canny Edge detector will return a matrix (I assume the code/gray level code is like relating high pixel value with the the feature in that specific pixel). I think it would be useful to know what data structures could actually be useful in this case to navigate through all the extracted features instead of iterating through all the pixels.

So the question is... in general (or at least line features) what data structure is usually useful? and how is such data structure constructed?

As a specific example... I'd like to extract all the edges of a given image, name such edges $e\_1,\ldots,e\_n$. Then I need to access to the pixels that lie both to the left and right of such edge(not all, just pixels that are close enough to $e\_i$, for all $i$). Finally I need to perform some operations on such pixels.

To summarize something like:

$e\_1,\ldots,e\_n \leftarrow extractEdges(I)$

$\forall i \in \left\\{ 1,\ldots, n\right\\}$

$\\;\\; S\_l \leftarrow pixelsLeft(e\_i)$

$\\;\\; S\_r \leftarrow pixelsRight(e\_i)$

$\\; \\; doSomething(S\_l,S\_r)$

Above $I$ representes the input image.

Thank you

# Answer
> 1 votes
A simple solution would be a 2D array containing a 1 in the locations that are detected as an edge, or a sparse 2D matrix. A more sophisticated solution would be a quadtree.

---
Tags: data-structures, image-processing
---


title: detectEigenFeatures with polygon ROI

text:
# Question
Title: detectEigenFeatures with polygon ROI
I am using detectEigenFeatures in the Matlab command to obtain the corner points. This function only can provide the corner points within a rectangular boundary region. But I want to extract the corner points within a polygon. I have thought about using small rectangles in order to obtain a polygon. But it seems time-consuming.

# Answer
If corner points are to be found inside a polygonal region of interest using detectEigenFeatures command, it's not possible directly. However, getting all the corner points from the above command, points inside the polygonal ROI can be extracted using the 'inpolygon' command in MATLAB.
> 0 votes

# Answer
Find the bounding box of the polygon. Find all corner points within the bounding box. Iterate over the resulting corner points, test each one to see whether it is within the polygon, and if not, throw it away.

Or, implementing your own code to do corner point detection.
> 0 votes

---
Tags: computer-vision
---


# Question
Title: What is tight NSPACE complexity of $ALT\text{-}SPACE(a(n),s(n))$?
According to Ryan Williams's answer $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(a(n)\log n)$.

> Does there exist any better bound (for example something like $ALT\text{-}SPACE(a(n),\log n)\subseteq NSPACE(\log (a(n))\log n)$), or is it tight or an open problem?

# Answer
> 2 votes
It's open, at least for the inclusion $ALTSPACE(\alpha(n),\log n)\subseteq NSPACE(f(n))$ with $\Omega(\log n)\leq f(n)\leq \alpha(n)^{o(1)}$. According to Chandra, Kozen, and Stockmeyer, we know $$DTIME(n^k)\subseteq ALTSPACE(n^{2k},\log n)\subseteq \mathsf{P}.$$

Therefore if it is true, then $\mathsf{P}\neq \mathsf{NPSPACE}$ which is not known to be true. On the other hand, rejecting it will yield $\mathsf{P}\neq \mathsf{NL}$, which is also not known to hold.

---
Tags: space-complexity
---


# Question
Title: Need help understanding which values can be inserted into a specific node in a binary tree
I am studying binary trees and I am failing to see what numbers can be inserted into this specific node position. The values to pick from are : 16, 24, 36, 45, 49, 51, 58.

I have tried values 24, 36, 45, and 16, 24, 36. I have tried these values because going from left to right, they go in increasing order. Though this is not working and I'm not quite sure why. I'm not sure why what I am selecting is wrong. Any help trying to solve my confusion is appreciated.

# Answer
Binary trees can serve many different purposes. They don't *necessarily* need to be in an ordering like such.

Note that below, I hid key parts of the solution. You can view them by hovering over with your mouse, but I encourage you to try to solve it using clues from my response without seeing the actual answer.

For your particular problem, it appears that the ordering of the tree is such that all nodes to the 'right' have a value greater than our root (global or local root, doesn't matter) and all nodes to the 'left' have a value less than our root.

With this in mind, $u$ must be greater than our root node, so

> $16$

is ruled out. Then, by taking $u$ to be our next (local) root node, $u$ must be greater than the maximum value of its left subtree and $u$ must be less than the minimum value of its right subtree. From this, we can see that

> $28 \< u \< 50$.

This rules out

> $24, 51, 58$.

Therefore, the answer to your problem is

> $36, 45, 49$
> 2 votes

---
Tags: binary-trees
---


# Question
Title: Lower Bounds for the Set Disjointness Problem
Consider the set disjointness problem. Alice and Bob hold n-bit strings $a$ and $b$ respectively. They would like to compute the function $$ \text{Dis}(a,b) = \begin{cases} 0 &\text{if } \exists i : a\_i = b\_i = 1 \\ 1 & \text{Otherwise}\\ \end{cases} $$

It is well known that this problem has communication complexity exactly $\Theta(n)$ (see here for example). This means that it cannot be solved with communication overhead sublinear in $n$.

Many times this result is informally stated as "Computing disjointness has communication overhead linear in the size of the inputs"

**Question:** How do I go from the formal definition and result for set disjointness to the informal statement above. My issue is the following: Assume Alice and Bob hold sets of 64-bit integers. In this case writing them as characteristic bit vectors would require them to send around 2^64 bits. However, clearly I can trivially solve the problem by sending my total set, which would have a communication overhead of $\text{set-size} \cdot 64$. How is this communication overhead related to the bit-strings of the set disjointness problem?

# Answer
> 1 votes
That's simply a different problem. The set disjointness problem is defined, by common agreement, to be the problem where the universe has size $n$ and the inputs (sets) are represented as a bitvector of length $n$. In other words, when you hear the phrase "set disjointness problem", you can know that's what they're referring to, and not the problem you care about.

It's fair to ask about the communication complexity of your problem. I don't know what its communication complexity is. There is no reason to assume your problem will necessarily have the same complexity as the set disjointness problem.

(There's a natural randomized protocol for your problem: if Alice and Bob each have a set of $n$ 64-bit integers randomly pick a universal hash function $f$ from the space of 64-bit integers to the set $\\{1,2,\dots,2n\\}$, transmit a description of $f$, hash the elements, and check disjointness of the hashed elements. If there is a common element among the hashes, use binary search to find all common elements and check if the unhashed elements match as well. The expected communication cost is $\Theta(n)$. It's also clear that any algorithm must have communication complexity $\Omega(n)$. This still leaves open what is the communication complexity for deterministic protocols, or the worst-case communication complexity for randomized protocols.)

# Answer
> 1 votes
This answer refers to a previous version of the question, in which the condition $a\_i = b\_i = 1$ was replaced by the condition $a\_i = b\_i$.

First of all, your problem is *EQUALITY* in disguise (complement one of the vectors to see why). The complexity of EQUALITY is still $\Theta(n)$ in the deterministic case, but it drops down to $\Theta(\log n)$ in the randomized setting.

Second, in communication complexity we are almost always interested in *worst case* complexity. Indeed, for any two inputs $x,y$ you can concoct a protocol which solves the problem correctly for them using only $O(1)$ communication, whatever the problem is (exercise). Your protocol is actually worse than the trivial protocol when Alice's input is very dense (depending on how Alice encodes her input).

You can define average case measures in communication complexity in various ways. The two ways that come to mind are:

* The average number of bits communicated given a specific distribution of Alice and Bob's inputs.
* The maximum, over all inputs, of the average number of bits communicated (in a randomized protocol).

In both cases, by truncating the protocols, we get a randomized protocol with some error probability and a worst case guarantee. This shows that for set disjointness, you cannot save anything in this way (since its randomized complexity is still $\Theta(n)$). For EQUALITY, savings are possible, though with a protocol different than what you described (if you're interested, look up the randomized protocols for EQUALITY, and try to fit them into these average case settings).

---
Tags: communication-complexity
---


# Question
Title: How does cycling happen in the simplex method?
I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below:

Solving $\max\\{cx\mid x \geq 0; Ax \leq b\\}$ At each stage a set $C\_k$ is maintained, which consists of $n$ linearly independent equalities from $Ax = b$, such that $x\_k$ the current vertex is determined by $C\_kx\_k = b\_C$.

$u$ is the unique vector $u\_kA = c$ where $u$ is zero in the components corresponding to equalities outside $C\_k$. if $u \geq 0$ then $x\_k$ is optimal. Otherwise we choose an index $i^\*$ where $u\_{i^\*} \<0$, $y$ is the unique vector such that $C\_ky$ is zero in all components except $i^\*$. Then $\lambda$ is defined as $\min\\{\frac {b\_t - (Ax\_k)\_t}{(Ay)\_t}, (Ay)\_t \> 0\\}$, where $t^\*$ is the index acquiring the minimum. Now $x\_{k+1}$ is calculated from $x\_k + \lambda y$ and $C\_{k+1} = C\_k + t^\* \setminus i^\* $. Also notice $cy = uAy = -u\_{i^\*} \> 0$ so $cx\_{k+1} \> cx\_k$.

So the book explains when choosing $i^\*$ and $t^\*$ and there are several options, there are different methods for breaking ties, some of which may cause cycling that is the algorithm wouldn't terminate. **Here is what I don't understand:** given there are finitely many vertices and $cx\_{k+1} \> cx\_k$ how is it possible to visit the same vertex twice hence encountering cycling??

Later, when the average time of Simplex method is being analyzed due to Borgwardt, the book explains cycling can happen only if the LP problem is degenerate. And provides a condition for being non-degenerate there is no set of $n$ linearly dependent rows in the matrix $\begin{bmatrix}c\\A\end{bmatrix}$ and there is no set of $n+1$ linearly dependent rows in $\begin{bmatrix}A &b\end{bmatrix}$. can you please explain why is this?

# Answer
> 3 votes
Cycling happens in a different scenario: when $cx\_{k+1} = cx\_k$. This happens when the current solution is *degenerate*, that is, when the set $C\_k$ is not unique.

For a worked out example, see Cycling in linear programming problems or The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling. There are many other resources which are available online.

---
Tags: linear-programming
---


# Question
Title: Looking for a succinct dynamic sorted dictionary
I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset $S$ of a universe $U = \\{0, \ldots, u\\}$ with member/predecessor/successor queries), but sadly I was able to find none. I did find succinct solutions to the following problems:

* Dynamic non-sorted dictionary
* Dynamic indexable bitvector (which is no good if the universe, say $\[2^{64} - 1\]$ is too big to store), not to mention storing a simple set, $\\{u\\}$ uses up the maximum amount of space
* Static indexable dictionaries

Dynamic succinct sorted/indexable dictionaries, however, do not seem to exist. (I do not actually need indexable dictionaries, just sorted ones with predecessor/successor queries, but it looks like this isn't really any easier to solve, either.)

What are some viable succinct data structures for solving this problem? Time bounds are not too important as long as they're not overly large (like $O(|U|)$). If there's no such data structure (yet), what is the second best option? Exponential search trees? Dynamic fusion trees? Multiple underlying data structures based on sparseness? (I prefer data structures with worst-time operation guarantees to those with amortized ones.)

# Answer
If you can tolerate $O(\sqrt{n})$ time complexity, I'd go for bi-parental heaps by Munro and Suwanda. This seems like an elegant implementation that should have $O(\sqrt{n})$ memory overhead in practice.

If your sets are too large for that, I'd try this data structure by Frederickson. You'll need a Hashed Array Tree to make it work with malloc.

Theoretically, a solution with $O(\log n)$ time per operation is possible. See this extended abstract by Franceshini and Grossi, and my bachelor's thesis that goes into greater detail and fixes some of the bugs.

Note that, apart from the bi-parental heap, I am not aware of any implementations. The asymptotically optimal solution probably has excessive multiplicative constants and I still need to complete it (which shall be my master's thesis).
> 3 votes

---
Tags: sets, succinct-data-structures
---


# Question
Title: What is the average size of a jump in a binary tree?
Assume that a full binary tree is layed out in memory recursively in the following way. First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. Assume tree is complete and full.

If a search path requires to go from array location $a\[i\]$ to $a\[k\]$, then its referrred to as a jump and its of size $k-i$, since you travelled $k-i$ units of memory.

Given this arrangement of the tree, what is the expected size of a jump in this tree?

# Answer
Consider a binary search tree with layers $0,\ldots,h$, where layer $\ell$ contains $2^\ell$ nodes. The left child of a node $x$ is located next to it (at distance 1). If $x$ is at layer $\ell$, then its left subtree contain $2^{h-\ell}-1$ nodes, and so the right child of $x$ is at distance $2^{h-\ell}$. These observations are illustrated in the figure:

Here $h = 3$, and the root ($\ell = 0$) has a left child at distance $1$ and a right child at distance $2^{h-\ell} = 8$.

We will calculate the average size of a jump in a random root-to-leaf path. This corresponds to searching for a random leaf.

The expected jump at level $\ell$ is thus $\frac{1+2^{h-\ell}}{2}$. Since there are $h$ jumps overall (at levels $0$ to $h-1$), the average jump is $$ \frac{1}{h} \sum\_{\ell=0}^{h-1} \frac{1+2^{h-\ell}}{2} = \frac{1}{2} + \frac{1 + \cdots + 2^{h-1}}{h} = \frac{1}{2} + \frac{2^h-1}{h}. $$ Since the number of nodes in the tree is $n := 2^{h+1}-1$, the average jump is $\Theta(n/\log n)$. The same holds for the number of leaves $m := 2^h$.
> 1 votes

---
Tags: binary-trees, probability-theory, binary-search-trees
---


# Question
Title: Point and Application of Recursive and Recursive Enumerable Languages
What is the point and application of recursive and recursive enumerable languages. Finite Automaton is used for pattern matching, designing computer architecture and protocols, CFG is used for designing compilers but what about Recursive and Recursive enumerable languages?

# Answer
> 1 votes
Recursive languages correspond to whatever can be computed in your favorite programming languages. Recursively enumerable languages correspond to whatever can be enumerated in your favorite programming languages — for example, all provably true mathematical theorems.

Your question assumes a particular list of canonical language classes, including four classes: regular languages, context-free languages, recursive languages, and r.e. languages. However, this list is rather arbitrary, and it omits modern complexity classes, including the all-important classes $\mathsf{P}$ and $\mathsf{NP}$.

The class $\mathsf{P}$ is intended to capture what can be computed efficiently (whether it succeeds in this goal is another question). The class $\mathsf{NP}$ captures problems which can be solved using "exhaustive search", that is, SAT solvers, IP solvers, and the like.

It turns out that $\mathsf{NP}$ captures many natural combinatorial problems, many of which are "equally hard". This leads most researchers to think that these "equally hard" problems are actually hard, that is, cannot be computed efficiently, a conjecture known as $\mathsf{P} \neq \mathsf{NP}$.

Computational complexity theory mentions many other complexity classes of interest. Practically speaking, a relevant class of languages are those which can be decided in quasilinear time (broadly construed) in the RAM machine model. This class roughly corresponds to problems which can be solved in practice even on "big data".

---
Tags: automata, computation-models
---


title: When is a 1-in-3 SAT clause satisfied?

text:
# Question
Title: When is a 1-in-3 SAT clause satisfied?
How does exactly 1 in 3 sat work given the variables Xi, Xy, Xz if one of the variables in the formula are negative. We know that the results are if they are all positive given that: R(Xi, Xy, Xz) = TFF FTF FFT

How would the result look like if one or two of the variables were negative? R(-Xi, Xy, Xz) or R(-Xi, Xy, -Xz)

# Answer
> 1 votes
A 1-in-3 clause consists of three literals. It is satisfied if exactly one of these literals is true. For example, if the three literals are $\bar{x}\_1,x\_2,x\_3$, then the three truth assignments (for $x\_1,x\_2,x\_3$) which satisfy the clause are $(F,F,F)$, $(T,T,F)$, $(T,F,T)$.

---
Tags: satisfiability, boolean-algebra
---


# Question
Title: Explanation for the regular expression for the set of all string over the alphabet {0,1}
Why does set of all strings over the alphabet {0,1} is represented by (0+1)\*? As per my understanding (0+1) means either 0 and 1 and * means 0 or more occurrence of the given string. Now when we do (0+1)\* it looks like we have to select either 0 or 1 and do a * on that so the resulting should be something like

***$\\{\epsilon,0,1,00,11,000\dots\\}$***

but why is it following?

***$\\{\epsilon,0,1,00,01,10,11\dots\\}$***

# Answer
It is a Klenee operator and it means all number of $(0 + 1)(0 + 1)\cdots$ with all possible length. As $(0+1)^{10}$ means $(0+1)(0+1)\cdots(0+1)$ for ten times. Hence, All possible combinations of $0$ and $1$ are comming in $(0+1)^\*$.

In the other words by the definition, it means the union of all $(0 + 1)^i$ for all $i$ from $0$ to $\infty$.
> 2 votes

---
Tags: regular-expressions
---


# Question
Title: $\tilde \Omega$ for division by logarithmic factor
Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?

# Answer
> 2 votes
The notation $\tilde\Omega$ isn't completely standard, and should be explained whenever used. Usually it hides logarithmic factors, and in that case, what you wrote holds.

---
Tags: asymptotics, notation
---


# Question
Title: Priority queue of constant size fit for extraction of K highest priority elements
In an algorithm I'm designing, I need to do this cycle on a priority queue of constant size N many times, as quickly as possible:

1. get $K$ highest priority elements (do on them some outside calculation)
2. append $4K$ kind-of-sorted elements back into the priority queue, removing and ignoring the first $K$ elements from step 1
3. remove the $3K$ lowest priority elements (in order to keep constant queue size), and return them

In reality, steps 2-3 will probably be merged somehow and so on, but these are the main implementation details.

I'm looking for the fastest implementation of these actions on a priority queue, for a relatively large $N$ and relatively small $K$ (E.G $K=32$, $N=2048$), that can be tweaked a little if needed (E.G change $N\rightarrow 2500$ if it's faster).

I'm not so familiar with data structures, but here's an assortment of things that might work:

* a sorted array, using $O(1)$ extracts and $O(N)$ merges
* a pairing heap? weird extract times, but $O(1)$ merges
* a more exotic heap type? I've found this question for example, with priority queues that technically are quicker at extracts

# Answer
One approach: Store them in a sorted array. To do steps 2 and 3, first sort the list of 4K items, then merge the sorted array of N items with the sorted array of 4K items, then discard the 3K lowest. Merging sorted arrays is easy and can be done in a simple linear scan. As Bulat says, this should be cache-friendly. The asymptotic running time is $O(N)$ per cycle, but since it is cache-friendly it might be fast in practice for the sizes you mention.

Another approach: use a self-balancing binary search tree. Then you can remove the highest K items in $O(K \log N)$ time, and you can append 4K items and then remove the lowest 3K in $O(K \log N)$ time, so the asymptotic running time will be $O(K \log N)$ per cycle. Thus in asymptotic terms this is faster, at least when $N$ is sufficiently large. However, due to the need to follow pointers and the resulting impact on the cache, for the size parameters you mention it might be slower in practice.
> 0 votes

# Answer
If that's practical question, sorted array may be faster than other approaches. The only O(N) operation you will do is memcpy in L1 cache whose speed using AVX2 is 32 bytes per CPU cycle, i.e. ~100 GB/sec.

You will need 2 arrays to make merge. But then you can use spare space for other computations. More complex data structure may easily run out of L1 cache size.
> 1 votes

---
Tags: data-structures, heaps, priority-queues
---


# Question
Title: How the Abstract DPLL Algorithm Works in SAT Solving
I have come across many definitions of the DPLL algorithm but haven't been able to follow them. The ones that are closest to making sense to me are the ones based on state-transition systems with transition rules such as defined here:

$F$ is a CNF formula, $C$ is a clause, and $M$ is a model. A description of it is as follows:

> Here, a DPLL procedure will be modeled by a transition system: a set of states together with a relation, called the transition relation, over these states. States will be denoted by (possibly subscripted) $S$.... A state is either fail or a pair $M \parallel F$, where $F$ is a finite set of clauses and $M$ is a sequence of *annotated literals*.... We will not go into a complete formalization of annotated literals; it suffices to know that some literals $l$ will be annotated as being decision literals; this fact will be denoted here by writing $l^d$ (roughly, decision literals are the ones that have been added to $M$ by the Decide rule given below). Most of the time the sequence $M$ will be simply seen as a set of literals, denoting an assignment, i.e., ignoring both the annotations and the fact that $M$ is a sequence and not a set.

I understand that a *literal* is an atom or its negation, but I don't understand what an *annotated literal* is, which is a core part of understanding what a model $M$ is in $M \parallel F$. I also don't understand what the decision literals are.

Two examples are as follows.

This is as much as I can gather. This:

$$\emptyset \parallel 1 \lor \bar{3}, \bar{1} \lor \bar{4} \lor 5 \lor 2, \bar{1} \lor \bar{2}$$

Is essentially an implementation of this:

$$M \parallel F$$

Also, the commas are really $\land$, as in:

$$\emptyset \parallel (1 \lor \bar{3}) \land (\bar{1} \lor \bar{4} \lor 5 \lor 2) \land (\bar{1} \lor \bar{2})$$

So each of the blocks between the commas or $\land$ are clauses. On the left is a growing list of literals (atoms or their negation). On the right are the rules being applied (like `Decide`). But I don't understand (a) how the rules are being applied / why they are chosen at the time they are chosen, (b) how it results in an annotated literal for $M$ on the left, and (c) why some of them are marked in bold as the "decision" literals.

The final result, from my understanding, is the model $M$ (on the left) that satisfies the formula $F$ on the right. Essentially, it's a valuation.

Wondering if one could clarify how the first example works, how the annotated literals get added to the model $M$ on the left.

# Answer
Describing DPLL as a series of state-transition rules is the worst way I've ever seen to aid understanding the algorithm. The pseudocode provided in the WIkipedia article on DPLL is much easier to understand if you're approaching the algorithm for the first time.

```
;Algorithm DPLL
;Input: A set of clauses Φ.
;Output: A Truth Value.

function DPLL(Φ)

if Φ is a consistent set of literals
   then return true;
if Φ contains an empty clause
   then return false;
for every unit clause {l} in Φ
   Φ ← unit-propagate(l, Φ);
for every literal l that occurs pure in Φ
   Φ ← pure-literal-assign(l, Φ);
l ← choose-literal(Φ);
return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

```

*Decision literals* are the literals returned by the choose-literal function called above. *Annotated literals* are just literals that are members of M that are marked in some way so the DPLL implementation can distinguish decision literals from literals added to M by unit propagation. This marking is for the sake of the backjumping code which must unroll assignments until the one responsible for the current conflict is found and then replace it.

Note that the original DPLL algorithm did not have backjumping in it. It simply backtracked, either reversing the current assignment or returning false if the algorithm had run out of assignments to try. Backjumping was a later innovation.

Note also that pure literal assignment isn't usually done in modern SAT solvers that implement some form of DPLL. It is a fairly expensive check to do in an algorithm expected to recurse and backtrack an exponential number of times and the benefits of doing the check don't outweigh the costs.
> 4 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: Insert into binary tree and keep it balanced
Assuming each node stores its depth, how can I achieve this? Note that I'm not talking about a binary search tree so I shouldn't need rotations. All I want is filling the tree from left to right.

# Answer
> 1 votes
You can keep all leaves in a queue, and on insertion set the new node as a child for the q.front(), add the new node to the queue and check if the numbers of children of the node in front of the queue = 2 then pop the node out of the queue. To remove a node you can swap the node you are removing and the last added node delete the last one (you should remove it from the back of the queue as well).

However, I would implement it as an array where a\[0\] is the root of the tree and a\[i\*2 + 1\], a\[i\*2 + 2\] are the children of a\[i\]. Inserting would be in this case to add an element to the back of the array and to remove an element you can swap it with the back of the array and pop the back of the arrray

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


# Question
Title: How to graph search a LTL-generated Buchi automaton to generate valid execution paths
I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification.

For example, suppose there are two tasks, A and B, and the LTL spec `<>(A&<>B)` is. This spec says that A should eventually be done and after A eventually B should be done. In this case, there is only one legal sequence: (A,B).

We can convert the LTL formula to a Buchi automaton, as shown above. Then since this example is so trivial, it is easy to see that the only legal sequence is A--\>B.

But what if we had a more complex LTL formula? How could we enumerate all legal sequences (permutations) of the tasks that satisfy the spec? Is there an efficient algorithm to do this?

# Answer
> 0 votes
The obvious naive approach is to enumerate all $n!$ permutations, and for each, check whether it meets the LTL spec. The latter check can be done in a standard way. So, the running time of this naive approach is approximately $\Theta(n!)$.

In the worst case, any algorithm might need to take at least this much time. For instance, if the LTL spec allows all schedules, then you'll have to output all $n!$ permutations, so it takes $\Omega(n!)$ time even just to write them down on the output.

You could ask for an output-sensitive algorithm: e.g., one whose running time is $O(k \text{poly}(n))$, where $k$ is the number of legal schedules that meet the LTL spec. Unfortunately, even this does not appear to be achievable in the worst case, as the problem is NP-hard. In particular, even checking whether there exists a legal schedule is NP-hard, by reduction from Hamiltonian cycle. In particular, given a graph $G$ on $n$ vertices, treat each vertex as a task; you can construct a LTL spec that captures the requirement that the sequence of tasks form a valid path through the graph; and then there exists a valid schedule (permutation of the tasks that meets the LTL spec) iff the graph has a Hamiltonian cycle. So, if we could detect the existence of a legal schedule, we could solve the Hamiltonian cycle problem, which is NP-hard. Obviously, enumerating all legal schedules is at least as hard as detecting whether any legal schedule exists.

These hardness results imply that there is no algorithm that will be efficient in all cases. You'll have to settle for an algorithm that is sometimes efficient, or a heuristic.

# Answer
> 2 votes
I would interpret your problem as follows:

*Given a non-deterministic Büchi automaton representing some language $L$, you want to enumerate all shortest good prefixes of $L$ such that in every character of the good prefix, only at most one atomic proposition has a $\mathbf{true}$ value.*

A good prefix of $L$ is a finite word such that every infinite extension of it is in $L$. I call a good prefix a shortest good prefix if and only if every prefix of the prefix is not a good prefix. A schedule is typically *finite* even though LTL and Büchi automaton "talk" about *infinite* executions. Hence this interpretation of your problem.

Note that this is actually a difficult problem -- take for example two Buchi automata for the languages \[\]\<\>p and \<\>\[\]!p -- you can take their disjunction by merging the state sets and having two initial states. You do not see syntactically that every word is a good prefix.

The best way to enumerate good prefixes would thus be to construct a **deterministic automaton over infinite words**, such as a deterministic Rabin automaton, and enumerating all paths to a strongly connected component in which every state represents the universal language.

Enumerating the paths can be done by a simple depth first search, where you do not abort the search after you found a path to a state with the universal language. Whenever you found a path to such a component, you print it out, and return to the next recursive step. Along the way, you ignore characters with more than one proposition set.

Now in *practice*, you may have a good luck using LTL-to-Buchi converters. They typically do not guarantee that they find all simplifications of the LTL formula, but enumerating paths to accepting states *may* do the trick. Note that for non-deterministic automata, you can get duplicate schedules. If you use modern tools for LTL-to-deterministic-automaton translation (such as *Rabinizer*), they should also make sure that states belowing to a strongly connected component for the universal language are self-looping on all characters, which makes them easy to detect. But I don't think they guarantee this.

---
Tags: automata, search-algorithms, graph-traversal, linear-temporal-logic, temporal-logic
---


# Question
Title: Binary search with alternative comparison cost
I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A\_i$ is $\Theta(i^2)$. I do not directly care about the number of comparisons, I just want to minimize the sum of the costs of the comparisons in the expected case (worst-case would also be nice).

Let's assume that each element in $A$ is unique and that $A$ does not contain $c$.

What is the optimal algorithm?

# Answer
@Willard Zhan explains the asymptotic complexity.

If you want to optimize the constant factor, you can work out the optimal schedule of queries using dynamic programming. Let $B\[i,j\]$ denote the worst-case cost of the optimal strategy when $c$ is already known to be in the range $A\[i\]...A\[j\]$, and let $\text{cost}(i)$ denote the cost of comparing $c$ to $A\[i\]$. Then we have the recursive relation

$$B\[i,k\] = \min\\{\text{cost}(j) + \max(B\[i,j-1\], B\[j+1,k\]) : j=i,i+1,i+2,\dots,k\\}$$

with the base case that $B\[i,k\] = 0$ if $i \ge k$. The $B$ array can be filled in using dynamic programming, and from that you can compute the strategy whose worst-case cost is minimal. You can use a similar strategy ot compute the strategy whose expected cost is minimal; you just have to adjust the recursive relation above (the specific relation will depend on your assumptions on the distribution of $c$).

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

# Answer
Let's say I told you in advance that $c$ is in the larger half. You still need $\Omega(\log n)$ comparisons, while now every helpful comparison takes $\Omega(n^2)$ cost, so the cost is always $\Omega(n^2\log n)$, which can be achieved with simple binary search.
> 3 votes

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


# Question
Title: Is this scheduling problem with arrival times, deadlines, and costs NP-hard?
There are $n$ jobs where each job $i$ has an arrival time $r\_i$, a deadline $d\_i$ and a cost $c\_i$. The problem is to find a scheduling time $t\_i$ (where $r\_i\leq t\_i\leq d\_i$) for each job $i$ in order to minimize $$\sum\_i\max\_{j\in S\_i}(c\_j),$$ where $S\_i$ is the set of jobs scheduled at time $t\_i$.

Can we solve this problem in polynomial-time or is it NP-hard?

For example, if all jobs can be scheduled at the same time $t$, then the objective will be $\max(c\_1,c\_2,\ldots,c\_n)$. The issue is that all jobs cannot always be scheduled at the same time $t$ because of their arrival times and deadlines. If I schedule the jobs as they arrive, I may end up with the objective of $\sum\_{i=1}^nc\_i$, which is the largest possible. So, the problem is somehow how to partition the jobs into sets $S\_i$ (where jobs in $S\_i$ are scheduled at the same time) for which we obtain the minimum objective. As such, I am trying to reduce Partition to this scheduling problem but still did not find the right reduction. Do you have any hints?

# Answer
The following observation enables a polynomial-time algorithm:

Whenever the time slot $t\_i$ for a job $i$ has been chosen, it's optimal to assign the same time slot for all lower-cost jobs that overlap $t\_i$, as doing so will incur zero additional cost. Therefore, choosing the time slot for the most costly job "magnetises" all the jobs that can be assigned the same time slot, and partitions the remaining jobs into two sets: those whose intervals are completely to the left of this time slot, and those whose intervals are completely to the right. The subproblems for these two sets of jobs can then be solved independently.

A general subproblem can be described by an interval $(a, b)$ and a maximum cost $c$: the jobs in this subproblem consist of all those jobs whose intervals fall within $(a, b)$ and which have cost at most $c$. The optimal solution for a subproblem can be found by trying every possible time slot for the most costly job in the subproblem, and solving the corresponding 2 subproblems for each attempt. A plain recursive strategy would take exponenential time, but there are only $O(n^3)$ distinct subproblems to solve: There are only $O(n)$ "basic intervals" (maximal intervals that do not cross the beginning or end of any job interval) to consider, so there are at most $O(n^2)$ possible intervals (blocks) of these, and $O(n)$ possible different job costs. Thus dynamic programming can be applied. It should be possible to test each of the $O(n)$ possible time slots available for the most costly job in $O(1)$ time each, excluding the time needed to solve subproblems, for $O(n^4)$ time and $O(n^3)$ space overall -- not fast, but certainly polynomial.
> 1 votes

---
Tags: algorithms, np-hard
---


# Question
Title: Complexity of closest set of points in plane problem
Given a set of points on a plane find the set of $n$ points that are closest to the origin. (Points are pairs of integers.)

> 1. Input: list of points.
> 2. Initialize a priority queue $Q$, where priority is measured according to the distance from origin (larger distance is higher priority).
> 3. For each point $p$:
>     * Add $p$ to $Q$.
>     * If $Q$ contains $n+1$ points, remove the point with highest priority.
> 4. Return $Q$.

The priority queue is implemented using a heap.

I'm thinking the runtime is $O(n + k \log n)$, and space is $O(n + m)$. Where $n$ is the number of points examined, $m$ is the number of points being returned and $k$ is $\max(0, n - m)$. Space is both the priority queue and the output.

My understanding is that a heap can be constructed in $O(n)$ hence the $O(n)$ in the runtime complexity. I find it hard to reason why heap construction, which has an upper bound $O(n \log n)$ can be reduced to $O(n)$, but $k$ deletions should be $O(k \log n)$.

I might be overthinking this, but thought I would ask.

# Answer
There seems to be some confusion regarding parameters. There is $n$, which is the number of points we wish to return; and there is another parameter, let's say $N$, which is the number of points in the input. Assuming that $N \geq n$, the output would consist of $n$ points, so we can dispense with your $k$.

Since the heap contains at most $n$ points, all operations take $O(\log n)$ time. Therefore the running time can be upper-bounded by $O(N\log n)$. It should be easy to construct matching hard instances which show that the worst-case time complexity is indeed $\Theta(N\log n)$.

Regarding space consumption, the usual convention is to measure only the "work tape", that is, only the auxiliary space taken by the procedure, without the input and output. In this case, this is only the heap, which uses up $\Theta(n)$ space.
> 1 votes

---
Tags: time-complexity, heaps, priority-queues
---


# Question
Title: Integer Problem Solving with two boolean selection variables
I am trying to solve a two dimensional combinatorial problem. Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible variations for each of these elements {1,2}. I have an objective function to maximize and i have some constraints. Based on these i have to make above selections. Can anyone please tell me if there is any optimization algorithm already available which serves my purpose. In reality i have a huge input space, so any existing algorithm is prefered

# Answer
> 1 votes
Sure, try integer linear programming. Let $x\_{RA1}$ be a zero-or-one variable that is 1 if you select RA1, or 0 if you don't. Then each of your constraints can be expressed as linear inequalities with these variables. You can then try applying an off-the-shelf ILP solver.

There are a bunch of other questions on this site with further examples of using ILP to solve combinatorial problems (e.g., Express boolean logic operations in zero-one integer linear programming (ILP)), so feel free to look around.

---
Tags: optimization, combinatorics, integer-programming
---


title: Algorithm to fill a truck with pallets

text:
# Question
Title: Algorithm to fill a truck with pallets
At work we build large machines, these get deconstructed, placed i crates and shipped away to the client. Now we are just guessing how many trucks we need and how we lay the crates out to fit as many of them inside a truck.

For example:

We have a truck and want to load 8 crates of equal size into it. There are 2 possible "solutions" to this problem.

But here you can see that the second option is better in space used (all pallets fit).

Now the real question. Is there a algorithme out there that can do this, even with irregular crates (meaning diffrent in size). Or do i need to invent one myself?

EDIT: Some more details:

The crates can vary in dimensions. But are always rectacles or squares.

The crate dimensions voor in the form of an Excel file where width height and lenght are defined.

# Answer
> 3 votes
This already exists, but might not be what you are looking for.

While this might not be a problem for your application, notice that this is a more general problem than the (already NP-hard) bin packing problem, so for a large amount of crates finding the optimal solution will be hard.

On the other hand, for a small enough number of crates, brute force might be sufficient. For example, you could round all dimensions to multiples of 10cm and look at the trucks in terms of 10x10 tiles that crates can occupy, giving you a finite (hopefully small enough) number of potential solutions.

---
Tags: algorithms
---


# Question
Title: Find a straight line to divide two convex polygons by equal area
Suppose, we have two non-overlapping convex polygons $A$ and $B$. How can we draw one straight line which divides $A$ into two parts of equal area and also divides $B$ into two equal area parts? Also, can we do this in complexity $O(n^2)$ or better? ($n = |A| + |B|$)

# Answer
> 11 votes
This is known as the Ham-Sandwich theorem:

> Given two measurable objects in $2$-dimensional Euclidean space, it is possible to divide each of them in half with a line.

Note: Convexity is not needed. And $\mathbb{R}^2$ can be replaced by $\mathbb{R}^d$ with "line" replaced by a $(d{-}1)$-dimensional hyperplane.

---

<sup> (Image from curiosity.com.) </sup>

---

See the Wikipedia link for computational versions.

**Added** in response to @WillardZhan's request:

> Ivan Stojmenovíc. Bisections and ham-sandwich cuts of convex polygons and polyhedra. *Inf. Process. Lett.* 38(1): 15-21. 1991. (CiteSeer PDF download.)
> **Abstract**. We present a linear time sequential algorithm for finding a straight line that bisects two given disjoint convex polygons (i.e. cuts both of them into parts of equal area).
>
> Abbott, Timothy G., Erik D. Demaine, Martin L. Demaine, Daniel M. Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung. "Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane." In *CCCG*, pp. 61-64. 2005. (PDF download.)

---
Tags: computational-geometry
---


title: What are some of the functions in TC1?

text:
# Question
Title: What are some of the functions in TC1?
Are there any non-trivial functions in TC1? Apart from that are there functions which are known to be in NC2 but not in TC1?

# Answer
According to wikipedia, topological sorting is in NC2. Note sure whether this is trustworthy, the proposed algorithm seems to require AC2:

> One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering (Dekel, Nassimi & Sahni 1981).

To check whether this algorithm is really in NC2 instead of just AC2, note that even so a single addition could take log log n time, all the additions of a max-plus matrix multiplication can be done in parallel. However, it is unclear how to do a single binary max operation in constant time.

It looks as if the max operations of a max-plus matrix multiplication cannot all be done in parallel. Maybe there is some trick to get the max of n numbers with log n bits in log n time, but I cannot see it at the moment. **Edit:** Here is the trick: Expand the numbers from binary to unary, then the maximum can be computed independent for each bit. Since conversion between unary and binary can be done in AC0 in both directions, it looks like we don't just get NC2, but even AC1. So this is even an example for the real question, i.e. a non-trivial function in TC1.

As Emil Jeřábek pointed out, there is no end to functions in TC1:

> all context-free languages, determinants over Z and over finite fields, various related problems in linear algebra (matrix powering, matrix inverse, characteristic polynomial, solvability of linear systems)

However, I have the impression that all those examples are also in AC1 or even weaker classes like SAC1. Just like my example which initially was even unclear whether it is in NC2, they don't need the power of TC1.

Coming up with examples which are in TC1 (or NC2) and really need TC1 (or NC2) will be extremely challenging.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Are all MST minimum spanning trees reachable by Kruskal and Prim?
I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for Prim's algorithm?

EDIT: To be more precise, I want to know if given an MST for a connected, undirected, weighted graph, is it guaranteed that there is a sequence of steps using Kruskal or Prim which generates this MST. E.g. There are different choices for Kruskal when there are multiple edges with the same weight. Similarly for Prim.

# Answer
As indicated by Raphael's comment and j\_random\_hacker's comment, the answer is positive. In fact, **any MST is reachable by any MST algorithm** with some minor exceptions.

For a graph $G$, two weight functions on all edges (to real numbers) are defined as (weakly) **comparison-compatible** (to each other) if we can extend the strict weak ordering on the edges induced by either weight function to the same strict total order. That is, we can devise consistent tie-breaking rules with each weight function so that the result of comparison of any two edges by one weight function and its tie-breaking rules is the same as the result by the other weight function and its tie-breaking rules.

> **Lemma 1**: Let $w\_1$ and $w\_2$ be two weight functions. The following five statements are equivalent to each other.
>
> 1. $w\_1$ and $w\_2$ are comparison-compatible.
> 2. In any set of edges, there is a common lightest edge by $w\_1$ and by $w\_2$.
> 3. In any set of edges, there is a common heaviest edge by $w\_1$ and by $w\_2$.
> 4. There exists a weight function $w\_3$ that assign distinct weights to distinct edges such that $w\_3$ is comparison-compatible to $w\_1$ and to $w\_2$.
> 5. for any edge $e\_1$ and $e\_2$ such that $e\_1$ is lighter than $e\_2$ by one weight function, $e\_1$ is as light as or lighter than $e\_2$ by the other weight function.

Proof of lemma 1 is left as an easy exercise.

> **Lemma 2**: Let two weight functions $w\_1$ and $w\_2$ be such that if $e\_1\lt\_{w\_1}e\_2$, then $e\_1\lt\_{w\_2}e\_2$. Then they are comparison-comptible.

(Hint to) Proof: One approach is to verify the condition 5 of lemma 1. Another approach is to verify the condition 2 of lemma 1 by showing that in any set of edges, a lightest edge by $w\_2$ is also a lightest edge by $w\_1$,

A comparison-based algorithm on a graph $G$ is defined as **comparison-compatible** if for any two (weakly) comparison-compatible weight functions on all edges, we can run the algorithm with one weight function in a way that can be repeated without any change with the other weight function. In particular, those two runs of the algorithm will have the same output.

Please note that most if not all MST algorithms can be stated in two flavours. The first flavour assumes that distinct edges of $G$ have distinct weights, which is used when the main concern is to find one MST (which is in fact also the unique MST). The second flavour allows distinct edges of $G$ to have same weights. Of course in this answer, where the main concern is to find all MSTs, we will only care MST algorithms in the second flavour.

## A comparison-compatible MST algorithm can find all MSTs.

To prove the above proposition, we just need to adapt slightly the section, "Kruskal can find every MST" in the computation of the number of MSTs. For any MST $m$ of $G$ with weight function $w\_1$, choose a positive weight that is lighter than the absolute difference between any pair of unequal edge weights. If we subtract that weight from the weight of each edge in $m$ without changing weights of other edges, we obtain a new weight function, say, $w\_2$. If edge $e\_1$ is lighter than $e\_2$ by $w\_1$, $e\_1$ must be lighter than $e\_2$ by $w\_2$ as well. By lemma 2, $w\_1$ and $w\_2$ are comparison-compatible. Note that $m$ is the unique MST with $w\_2$. (One way to show this uniqueness is to prove that whenever the weight of one MST edge is reduced, any MST with the new weight function must contain that edge.) So any run of the algorithm on $w\_2$ will find $m$. Because the algorithm is comparison-compatible, we can run the algorithm the same way with $w\_1$ or with $w\_2$. Since that run will find the unique MST, $m$ with $w\_2$, it will find $m$ as well with $w\_1$.

## Every MST algorithm is comparison-compatible

The above proposition sounds overbroad. Well, by every MST algorithm, I mean any general comparison-based MST algorithm that I have seen, excluding those apparently pathological ones such as wrong or having unnecessary steps. Since a comparison-compatible MST algorithm can find all MSTs, every MST algorithm can find all MSTs. In particular, **each of the four classic MST algorithms, namely Borůvka's, Prim's, Kruskal's and reverse-delete algorithms can find all MSTs.**

Here are three more comparison-compatible MST algorithms.

* the delete-heavy-edge algorithm. Start with all edges. Repeatedly find a cycle and remove one of its heaviest edge until no cycle remains.
* the add-non-heavy-edge algorithm. Start with the empty set. Iterate through all edges. Each edge is added and, if a cycle is formed, remove one of it heaviest edges.
* the replace-by-lighter-edge algorithm. Start with any spanning tree $T$. Find the cycle in $T$ plus an edge $e$ not in $T$. If an edge $t$ in that cycle is heavier than $e$, remove $t$ from $T$ and add $e$ to $T$. Repeat until we cannot reduce the weight of $T$ any more.

The following MST algorithm is not comparison-compatible.

* the degree-biased Kruskal's algorithm, which is Kruskal's algorithm with the following modification. Suppose when we are going to remove an edge with the minimum weight from $S$ as in the wikipedia's description of Kruskal's algorithm, we have multiple edges with the minimum weight to choose. The edge we choose to remove will be an edge whose sum of degrees of its two vertices is the largest among all choices. This algorithm cannot be comparison-compatible since it does not find the MST $\\{ab,bc,cd\\}$ of the graph with vertices $a,b,c$, and edge $ab$ of weight $1$ and edges $bc, cd, db$ of weight $2$. This algorithm is considered pathological because of that unnecessary modification.

Please note that all eight MST algorithms mentioned above are comparison-based.

## How to show an algorithm is comparison-compatible?

I will use Kruskal's algorithm as an example. Here is the description of Kruskal's algorithm (in the second flavour) on a weighted undirected connected graph $G$.

* create a graph $F$ that has the same vertices as $G$ but without edges. So $F$ is a forest of separated trees of a single vertex.
* create a set $S$ containing all the edges in the graph.
* while $S$ is nonempty and $F$ is not yet spanning
    + select an edge with minimum weight from $S$.
    + remove that edge from $S$.
    + If that edge connects two different trees then add it to the forest $F$, combining two trees into a single tree
* output $F$.

Let $w\_1$ and $w\_2$ be two comparison-compatible weight functions on $G$. Kruskal's algorithm involves the weight function only in the step that "select an edge with minimum weight from $S$". The condition 2 of lemma 1 tells us that we can select a common lightest edge in this step. We can then check easily by induction that we can run all steps in the same way with $w\_1$ and with $w\_2$. So Kruskal's algorithm is comparison-compatible.

An algorithm is comparison-compatible if, in loose terms, it can be described in three kinds of steps.

1. do something that does not involve weight.
2. select an edge with the minimum weight in a given set of edges
3. select an edge with the maximum weight in a given set of edges

This sufficient condition covers Borůvka's, Prim's, Kruskal's, reverse-delete, delete-heavy-edge and add-non-heavy-edge algorithm. Note that in order to fit this sufficient condition, we may have to change certain descriptions of an algorithm without affecting the set of reachable MSTs. Because of the exception of the degree-biased Kruskal's algorithm being comparison-compatible, let me emphasize this sufficient condition is described in loose terms
> 12 votes

---
Tags: algorithms, graphs, minimum-spanning-tree
---


title: Identification of Formal Language

text:
# Question
Title: Identification of Formal Language
$$L = \\{a^{m+n}b^{m+k}c^{n+k}\mid m,n,k\ge 1\\}.$$

Is $L$ DCFL or not?

According to me it should be DCFL since we can write $L$ as $\\{a^{n}a^{m}b^{m}b^{k}c^{k}c^{n}\mid m,n,k\ge1\\}$. So, now after push and pop on the stack, it will be empty. So, according to me it will be DCFL but I have doubt since DPDA can't count $n$ and $m$ after reading symbol $a$ so machine can't know how many $a$'s should have to be popped. According to this logic, one stack is not enough for this language. So, it should be CSL. Please tell me whether it should be DCFL or CSL?

# Answer
$L$ is CFL because there is a CFG generating it:

$$ \begin{align} S&\rightarrow aAc\\ A&\rightarrow aAc \mid BC\\ B&\rightarrow aDb\\ C&\rightarrow bEc\\ D&\rightarrow aDb \mid \epsilon\\ E&\rightarrow bEc \mid \epsilon \end{align} $$

---

$L$ is not DCFL. To prove this, we give some lemmas firstly:

> *Lemma 1.* $$ \begin{align} L &=\\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\\}\\ &=\\{a^x b^y c^{|x-y|+2+z}\mid x,y\ge 2, z\text{ is even},0\le z\le x+y-|x-y|-4\\}. \end{align} $$

*Proof.* Let $L'=\\{a^x b^y c^z\mid x,y\ge 2, x+y+z\text{ is even},|x-y|+2\le z\le x+y-2\\}$. Easy to see $L\subseteq L'$. Now let $a^xb^yc^z\in L'$, then we can choose $m=(x+y-z)/2, n=(x-y+z)/2, k=(y-x+z)/2$. Because $x+y+z$ is even, $m,n,k$ are all integers. Because $|x-y|+2\le z\le x+y-2$, we have $m,n,k\ge 1$, so $a^xb^yc^z\in L$. As a result, $L=L'$.

> *Lemma 2.* $M =\\{a^x b^y c^{|x-y|+2}d^z\mid x,y\ge 2, z\text{ is even},z\le x+y-|x-y|-4\\}$ is not context-free.

*Proof.* Suppose it is context-free, according to Odgen's lemma, there exists some $p\ge 1$ such that $s=a^{p+2}b^{p+2}c^2d^{2p}\in M$ can be written as $s=uvwrt$, such that

1. the number of $d$s in $vwr$ is at most $p$ (i.e. we mark all $d$s),
2. there is at least one $d$ in $vr$, and
3. for all $q\ge 0$, $uv^qwr^qt\in M$.

From condition 3, $v$ and $r$ each contains at most one character. Together with condition 2, as $q$ grows, the number of $d$s in $uv^qwr^qt$ grows infinitely. To satisfy the condition $z\le x+y-|x-y|-4=2\min\\{x,y\\}-4$, the number of $a$ and $b$ must **both** grow, i.e. $a$ and $b$ must both in $vr$. However, $vr$ contains at most two characters, while $d$ is already in it, $vr$ cannot contain both $a$ and $b$, a contradiction.

---

Now let's come back to $L$. Suppose there is a DPDA $D$ accepting $L$, we create two copies $D\_1$ and $D\_2$ of $D$ and change the input character $c$ in $D\_2$ to $d$. We then construct a new PDA $P$ as follows:

1. The states of $P$ are the union of states of $D\_1$ and $D\_2$. The start state of $P$ is the start state of $D\_1$. The accepting states of $P$ are the accepting states of $D\_2$.
2. For a transition in $D\_1$, if the destination is an accepting state in $D\_1$, change the destination to the corresponding state in $D\_2$. Other transitions keep unchanged.

Now run $P$ on a string $a^xb^yc^{|x-y|+2}d^z\in M$. According to lemma 1, after reading $a^xb^yc^{|x-y|+2}$, it enters a state in $D\_2$ for the first time. Since $a^xb^yc^{|x-y|+2+z}\in L$ according to lemma 1, $P$ will finally accept.

On the other hand, if a string $s$ is accepted by $P$, let $s=s\_1s\_2$ where after reading $s\_1$, $P$ enters a state in $D\_2$ for the first time. According to lemma 1, $s\_1$ must have the form $a^xb^yc^{|x-y|+2}$ ($x,y\ge 2$). Also, $s\_2$ does not contain $c$, and after changing all $d$s in $s\_2$ to $c$s, $s\_1s\_2$ belongs to $L$. This means $s$ must have the form $a^xb^yc^{|x-y|+2}d^z$ where $x+y+|x-y|+2+z$ is even (i.e. $z$ is even) and $|x-y|+2+z\le x+y-2$ (i.e. $z\le x+y-|x-y|-4$). Hence $s\in M$.

As a result, $P$ recognizes $M$, which contradicts to lemma 2.
> 3 votes

---
Tags: formal-languages, context-free
---


# Question
Title: Prove that $L^r$ is context free without alphabet
I'm stuck with this problem:

Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\\{x^r|x\in L\\}$, where for each $a\in\Sigma$ and $y\in\Sigma^\*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$ is context free or not.

Since I don't have the alphabet I cannot think of a grammar that generates this language, so I decided to prove that it's not context free by applying the pumping lemma for CFL. So I started with the hypothesis that $L^r$ is context free, thus if $x\in L^r$ that $x^r\in L$.

Then I tried to find different possible strings that once pumped didn't belong anymore to $L^r$, but I'm not able to find such string.

Is this a bad aproach? Where am I wrong?

# Answer
> 2 votes
Informally, by construction $L^r$ consists of the strings in $L$ reversed. Since $L$ is context-free, it has a Grammar in Chomsky normal form. All production rules in this grammar will fall in one of three classes:

1. $A \rightarrow BC$
2. $A \rightarrow a$
3. $S \rightarrow ε$

Thus by reversing the order of non-terminals in the RHS of all rules of category 1., a new grammar can be derived that produces $L^r$.

This new grammar is also in Chomsky normal form, thus $L^r$ is context-free.

---
Tags: context-free, proof-techniques, pumping-lemma
---


# Question
Title: Operating System: replace the process's memory space with a new program
What does it mean that "replace the process's memory space with a new program"? So who's memory space will be replaced by whom?

# Answer
> 3 votes
A process memory space is :

and when you call fork with a process, the entire address space of that process gets copied, and we allocate some part of the memory to it, and when we call exec after doing fork, it replaces that copy (the child) with a new program. (note that we usually call exec only with the child, we do this in our code using the fact that the child will return 0 to the fork value and the parent will return the process id of that child, so we use the if command and use exec if its the child)

so to answer your question, we basically replace the address space of the child that was created, with another program.

---
Tags: operating-systems
---


# Question
Title: How do modern Operating Systems detect process starvation?
So first off do the modern operating systems like windows and linux have a method for detecting starvation? if not, why? and if they do, then how are they going to detect starvation of a process? (this was a question in our exam)

my take was this so correct me if this is not good or not possible:

i said we should implement a linked list of waiting processes (that are waiting for a resource or etc) then we periodically run a function(using interrupts) which checks this list and we have a variable for each process and we increase that everytime, when it reaches certain point then we would know its starving(but i still dont know how to know this "certain point")

so is this correct? if so then how can we know this "certain point"? ( I suppose one way is just look at the statistic of average waiting time of processes and do a little math?)

if not, what is your solution?

# Answer
Inline with @chi 's comment; lets say process "x" gets starved in linux or windows, then for example if we are in the windows, wouldn't we get an error message saying the process "x" is not responding? Approximately no.

Now let's assume we want to detect process "x",before starvation nor aging;we have to read it's arrival time, burst time,process id, priority from the text file and calculate the average waiting time and show the central processing unit utilization of each cycle,for instance;

Time 1 process X arrives

Time 2 process X runs

Time 3 process B arrives

Time 4 process X finishes..........,randomly.

Hope this can give you a little bit of insight.
> -1 votes

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


# Question
Title: How important is to formulate a convex optimization for a proposed algorithm?
I proposed a new sparse coding algorithm which has good results compared to the baselines, however, it has a non-convex optimization framework. I solved the problem using a general solver (e.g. Matlab), and although the solution is local optimum, it is still better than other relevant approaches. So how important is to formulate the problem in a convex setting? especially for publishing the work.

# Answer
I don't know whether any of us can predict how reviewers or your community will react, especially without seeing the manuscript; probably your best bet is to talk to your advisor or to collaborators or colleagues and ask them for their advice. You might also ask them if they'd read a draft of your paper.

My expectation is that it might depend on whether your field values provable results ("theory"), or pragmatic empirical results ("engineering"). The benefit of a convex formulation is that it allows proving some theorems about the approach, e.g., that it will always find the optimum under certain conditions. The benefit of your approach is that it seems to get better results in practice, at least on the workloads you've been testing it on. I can't tell you which your community will value more highly.
> 2 votes

---
Tags: optimization
---


# Question
Title: What exactly representational bottleneck in InceptionV3 means?
I am trying to understand the concepts behind the InceptionNet V3 and got confused with the meaning of representational bottleneck. They said

> One should avoid bottlenecks with extreme compression. In general the representation size should gently decrease from the inputs to the outputs before reaching the final representation used for the task at hand.

and one thing I get from this is that we should not use polling or convolutions with large strides. But when I arrived in the section 5 (Efficient Grid Size reduction) they said that doing polling before the convolution violates that mentioned principle but doing polling after convolution don't violate.

Doing the left one we decrease the number of features by a factor of one quarter and then the features are doubled. In other words a decrease of 35\*35\*320\*0.75 = 294K features and then an increase of 17\*17\*320 = 92.48K features. And doing the one in the right the features are doubled and then decrease by the same factor of one quarter. And doing this one, the real decrease in the pooling phase is bigger: 35\*35\*640\*0.75 = 588K.

**So, why one approach violates the principle and the other don't? What am I missing here?**

Another thing that confused me is the solution found by them to avoid the computational cost of doing conv. before polling.

**The polling part of the solution is not violating the principle of representational bottleneck once it make the exactly same operation with dimensionality reduction mentioned earlier?**

# Answer
Cool question! I managed to start thinking about its meaning thanks to your asking.

I believe you would like to consider it in the sense of information flow. As the information is compressed to a same size in both cases, the question is which one is more effective. Information with amount of 35\*35\*640 can flow through a wider pipe more freely. A pooling layer just prunes information directly in the left solution, while doing Inception in the right case expands the representation to a more sparse space and makes meaningful inferences before get pruned. Think of the pooling operation in left as a neck or a narrow path, and the middle representation in right as a broad lake. The pooling layer in right can also select better output since the source has more abstract (semantics) information.

As to figure 10, I consider it as a balance between the representation size and the computation burden.
> 1 votes

# Answer
The usual rule is one question per post. I'll answer your first question.

With the architecture shown on the left, we first push everything down to 17x17x320, losing a lot of information. Then we expand to 17x17x640, but once information is gone, it can't be reconstructed, so with the left architecture, effectively the narrowest pipe is 17x17x320.

With the architecture shown on the left, we never go down to 17x17x320; the narrowest part of the pipe is 17x17x640. 17x17x640 potentially allows representing twice as much information as 17x17x320. Therefore, with the right architecture, we haven't lost as much information as with the left architecture.

In particular, the left architecture probably loses about twice as much information as the right architecture. It's bottleneck is twice as "narrow". So, it might have lower accuracy as a result.
> 0 votes

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


# Question
Title: Solve T(n)=T(√n)+ n using substitution method
I am confused how to solve this recurrence equn. after a particular step (step involving ? in the picture)

(Plz help me solve the question with same method which I have used and correct if any of the steps are wrong!)

Attached is what I have done so far..

# Answer
As you mention, $$ T(n) = n + \sqrt{n} + \sqrt\[4\]{n} + \cdots, $$ and the number of terms is at most $\log \log n$. Hence $$ n \leq T(n) \leq n + \sqrt{n} \log\log n. $$ This implies that $T(n) \sim n$.
> 3 votes

---
Tags: time-complexity, recurrence-relation
---


title: Storing Specific data on DB Table(s)

text:
# Question
Title: Storing Specific data on DB Table(s)
I have an Excel with 40columns and 20k rows, and i have to store it in a database but i cant figure the best approach for it, the excel format is like this:

This table has 30 columns for days, then 11 columns for the next 11 weeks and then 9 columns for the next 9 month, in resume the first month is in days the next 3 months are in weeks and the rest of the year is in months.

Each column has the number of pieces that i need to produce certain product in that span of time.

```
Part number | 1/1/2018 ||||| 30/1/2018 | Week6 ||| Week16 | Month4 ||||||Month12
PART1             2             5          10        12        40          50
PART2             3             4          13        11        50          70
PART3             4             3          13        15        60          60
PART4             1             3          16        12        40          30

```

This Excel file has to be pasted in to a datagridview and then save it in a DB, should i use 1 table or more? what shold be my table design to store this data?

# Answer
> 1 votes
In my mind when you start using a "DB" I'm assuming that you mean a relational/SQL database, and then the design of how the information is stored might change entirely.

It seems like you're using this Excel file to track a master production schedule for some kind of parts manufacturing, so it's how many parts you need, and when you need them by.

I'm not sure it makes sense to have multiple time scales in the same table for that purpose. So my reflex would be to say, we should create a table that stores information about, the date, how many parts need to be produced on that date, and which part needs to be produced.

```
CREATE TABLE production_schedule (
    prod_date date,
    part_no   int,
    part_qty  int
);

```

Then if you need to build reporting or gather the information about how much in a week, a month, six months, or a year. You could do that with queries when you need that information or you could create views that are based on such queries.

For example, a query like the following would return the total amount of parts to be created in January 2018.

```
SELECT SUM(part_qty) FROM production_schedule WHERE prod_date BETWEEN '01/01/2018' AND '31/01/2018';

```

Hopefully, this helps you understand the way you should think about creating a database to solve your problems, and perhaps a verbatim transfer of the information isn't the best solution.

It can help when getting started to think of databases as spreadsheets because they store information in a way that can be thought of as "column and row". The fact that you can store information in them and also ask sometimes simple and sometimes complicated questions of them can throw off people who are new to working with databases.

---
Tags: data-structures, database-theory
---