# Question
Title: Shortest Path in a Graph with Interacting Edge Weights
Suppose we have a graph $G = (V,E)$.

Every edge $e \in E$ has a unary cost $f(e) \> 0$.

Also, for every two edges $e\_1,e\_2 \in E$ we have a binary reward function $g(e\_1,e\_2) \geq 0$.

Given two vertices $s$ and $t$, is it possible to find the path that minimizes the following objective function efficiently?

$ \sum\_{e \in \text{Path}} f(e) \- \sum\_{e\_1 \in \text{Path}} \sum\_{e\_2 \in \text{Path}} g(e\_1,e\_2) $

---

Update:

According to @xavierm02's answer this problem seems to be NP-hard. But is there any heuristic that can at least partially deal with this? If it helps, this is the context for which I want to use this problem.

This shortest path simply represents a sequence of curves for a piecewise curve fitting as in the paper: http://www.mit.edu/~ibaran/curves/ .

The final goal is to fit a sequence of curves to a bunch of points. As we cannot fit just one curve, we also have to decide where the transitions occur. In this approach, we basically fit every possible curve. Then, we construct a graph, where each curve is associated with an edge, and the points to be fitted are the vertices (not exactly the same as the paper). The weight of each edge is basically its error in the least square fit. We then find the shortest path from the first point, to the last, which in turn tells us the best sequence of curves.

What I am trying to do is to use this reward function to encourage certain curve pairs to be inside the final selected sequence of curves. For example, the ones that are symmetric.

---

Further updates:

$g$ has very few non-zero values, and we can safely assume $g(e\_1,e\_2)\<f(e\_1)$ and $g(e\_1,e\_2)\<f(e\_2)$. The graph has cycles, and we might have $s=t$.

# Answer
It's NP-hard.

We reduce 3SAT to your problem (where $f$ is constant). Let $c\_1,\dots ,c\_m$ be an instance of 3SAT. Let $v\_1,\dots,v\_n$ be the variable in the clauses. For each clause $c\_i$, call $l\_{i,j}$ the $j^\text{th}$ literal of $c\_i$. Now, build this graph:

(Note that we allow several edges between the two same nodes, but if you don't want to, you can just add dummy nodes)

Now, if we look at paths from $0$ to $n+m$ in this graph, clearly, they will pick a value per variable (true if it picks $v\_i$ and false if it picks $\lnot v\_i$), and a literal per clause. Set $f:=e\mapsto 1$ to be constant. Now set $g((l,c),l)=1$ and $g(e,e')=0$ in all other cases, i.e. reward taking a literal in a clause that's been made true by the valuation defined by the first $n$ edges. Note that the cost of a path from $0$ to $n+m$ is $\le n$ (or equivalently $=n$) if and only if the initial formula is satisfiable (because the cost due to $f$ is $n+m$ and the reward due to $g$ is the number of satisfied clauses). So the problem "Is there a path of cost $\le n$" is NP-hard.
> 3 votes

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


# Question
Title: Algorithm for shortest continuous line to join N points
I have a set of points in a 2D plane. I'm searching for an algorithm that:

* Draws a continuous line passing through all the points starting from a random point.
* Optimizes for the minimum total line length in Euclidean distance.
* The line should end at the point it started but not cross any other point more than once.

In plain terms, suppose we had a paper with N dots on it. We'd take a pencil starting from a random point and try to go through all the points without lifting the pencil and conclude by reaching the point we started at.

I looked into Euclidian minimum spanning tree, but what I'm looking for is a closed loop and not a graph-tree like line. What I'd like in approximation is a Convex Hull that would go through all the points and not just form the perimeter.

Can someone direct me to the right family of algorithms?

# Answer
Turns out what I'm looking for is the Travelling salesman problem.
> 1 votes

---
Tags: algorithms, optimization, euclidean-distance
---


# Question
Title: simulation of PDA with 2-tape Turing machine
Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?

# Answer
> 3 votes
The first tape for input and the second for storing symbols (like on a stack). The first tape should be read-only so that the TM reads symbols one by one from left to right.

Every time your PDA writes a symbol on the stack, your TM moves the second head right and writes a symbol on the rightmost empty cell. When the PDA removes a symbol from the stack the TM replaces the rightmost symbol with the blank symbol (erases) and moves the second head left. On each state transition the first head should always move right.

In addition, your TM shouldn't be allowed to arbitrarily move heads right and left violating PDA rules.

Consider the following formal definition of moves for PDA (assume deterministic for simplicity):

**UPDATE**

**Definition of PDA moves**

$\delta(q, a, Z) = (p, \alpha)$: the PDA in state $q$ with input $a$ and $Z$ on the top of the stack. The PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the string $\alpha$. So, $\delta(q, a, Z) = (p, \epsilon)$ means remove the top stack symbol (pop). Advance the input head one symbol.

$\delta(q,\epsilon, Z) = (p, \alpha)$: the PDA in state $q$ with $Z$ on the top of the stack. Independent of the input symbol, PDA enters the state $p$ and replaces the top symbol $Z$ with the symbols of the strings $\alpha$. Input head does not advance in this case.

**Examples of translation of PDA moves into TM moves**

**Example 1.** PDA move $\delta(q\_1, 0, A) = (q\_2, B)$ is translated as: TM in state $q\_1$, head 1 (input head on the tape 1) reads $0$, and head 2 (stack head on the tape 2) reads $A$. Replace $A$ with $B$ (head 2 writes the symbol $B$ while it is on $A$). Advance head 1 one symbol. Enter state $q\_2$.

**Example 2.** $\delta(q\_1, 0, A) = (q\_2, BC)$ is translated as: TM in state $q\_1$, head 1 reads $0$, and head 2 reads $A$. Head 2 writes $B$ (replaces $A$), advances head 2 one symbol, TM enters state $q\_{21}$. Then, while TM in state $q\_{21}$ and head 1 reads $0$, and head 2 reads the blank symbol: head 2 writes symbol $C$, enters state $q\_2$. Advance head 1 one symbol.

The basic idea: in order to write $BC$ we introduced a new state $q\_{21}$.

Analogously, $\delta(q,\epsilon, Z) = (p, \alpha)$ means head 2 just writes the blank symbol and moves left.

$\delta(q,\epsilon, Z) = (p, \alpha)$ means that you define the same transition **for every input symbol**.

This is how a multitape Turing machine is defined.

---
Tags: turing-machines, pushdown-automata
---


# Question
Title: Are fractions more computationally "expensive" than whole numbers?
I have a problem where the values are represented to humans as \[0, .5, 1, ..., 8\]

But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering is it more computationally efficient to use the values \[0, 1, 2, ..., 16\] and only divide by 2 when outputting for humans?

*(Possibly this is a non-issue with high level languages and modern processors. The hardware we'll be running on is smartphones, but everything has to be local.)*

# Answer
This link below compares all arithmetic operations between floating point and integer variables on various architectures and processors.

With the general conclusion drawn that additions and subtraction are roughly equal, the performance impact arises in multiplication and division operations; with integer being faster. (Except for x86-64 AVX and POWER8 AltiVec where it is faster in the former for floating point and equal in the latter.)

Integer and Floating-Point Arithmetic Speed vs Precision: http://nicolas.limare.net/pro/notes/2014/12/12\_arit\_speed/
> 2 votes

# Answer
It's the wrong question.

Floating point numbers may be a bit more expensive than integer arithmetic, but this is unlikely to matter in your application. Do whatever is better for your application. Use the values that make most sense in your application.

Writing an application is difficult enough. Do whatever you can to make it as simple as possible. If you are worried about the speed (floating point vs. integer), the simpler your code is, the easier it is to make it faster - because making code faster is not a matter of floating point vs. integer, but a matter of how much time to spend on it, and the simpler the code, the more time you can spend to make it fast.
> 1 votes

---
Tags: arithmetic, performance
---


title: Is Gale Shapley globally optimal?

text:
# Question
Title: Is Gale Shapley globally optimal?
Let us have a set of N men and N women, and we have two matrices of affinities $M$ and $W$ such that $M(i,j)$ is the affinity of the ith man towards the jth woman and $W(i,j)$ is the affinity of the ith woman towards the jth man.

The problem at hand is to find an optimal stable marriage, which satisfies that:

1. There is no couple of man and woman not married such that they would prefer to be with each other (have higher affinity towards) rather than their actual partners.
2. The sum of the affinities of each couple is maximal among the stable marriages.

Does vanilla Gale Shapley solve this problem? If not, is it NP-complete or is there any hope of solving it polynomially?

# Answer
> 2 votes
No, Gale-Shapley optimizes a different set of criteria; see https://en.wikipedia.org/wiki/Stable\_marriage\_problem. It maximizes the men's happiness, which doesn't necessarily maximize the total happiness sums. It is easy to come up with counterexamples by taking any stable marriage solution where some woman doesn't get her first choice -- say, Alice's first choice is Bob, but she isn't assigned to Bob in the assignment output by Gale-Shapley -- and then making Alice's affinity towards Bob be some enormous number, far larger than all other affinities.

I don't know if it can be solved in polynomial time. Without the stability requirement, it's an instance of the assignment problem. With the stability requirement added on, I don't know whether it can be solved in polynomial time.

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?
I'm reading through the RMIT course notes on state space search. Consider a state space $S$, a set of nodes in which we look for an element having a certain property. A heuristic function $h:S\to\mathbb{R}$ measures how promising a node is.

$h\_2$ is said to *dominate* (or to be more informed than) $h\_1$ if $h\_2(n) \ge h\_1(n)$ for every node $n$. How does this definition imply that using $h\_2$ will lead to expanding fewer nodes? - not only fewer but subset of the others.

In Luger '02 I found the explanation:

> This can be verified by assuming the opposite (that there is at least one state expanded by $h\_2$ and not by $h\_1$). But since $h\_2$ is more informed than $h\_1$, for all $n$, $h\_2(n) \le h\_1(n)$, and both are bounded above by $h^\*$, our assumption is contradictory.

But I didn't quite get it.

# Answer
> 11 votes
So it seems you are intrigued about the relationship between the *informedness* of a heuristic function and its *pruning power*.

This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award).

As you already mentioned, $h\_1$ is said to be more *informed* than $h\_2$ if and only if $h\_1(n)\geq h\_2(n), \forall n$ in the state space. Now, provided that the heuristic function is also admissible (i.e., $h\_1(n)\leq h^\*(n)$ so that it never overestimates the effort to reach the goal, where $h^\*(n)$ is the optimal cost to reach the goal state from node $n$), $h\_2(n)$ is admissible as well since $h^\* (n) \geq h\_1 (n)$ by definition and $h\_1(n)\geq h\_2(n)$ by hipothesis, so that $h^\* (n) \geq h\_2 (n)$.

When considering that both heuristics are admissible, the following result applies to all $A^\*$-like search algorithms: $f (n)\<h^\*(n)$ is a sufficient condition for expansion so that they expand all nodes meeting this property ---other algorithms expanding them as well include IDA$^\*$ and RBFS. Since $f (n) = g(n) + h (n)$ where $g(n)$ is the (known) cost from the start state $s$ to node $n$ and $h(n)$ is your heuristic function (either $h\_1$ or $h\_2$) so that $f(n)$ is the estimated cost of the path $s-t$ when going through $n$, it immediately follows that there are, at least, as many nodes meeting this propertiy when $h\_2$ is used instead of $h\_1$.

The property mentioned above was already demonstrated in the original paper of the A$^\*$ search algorithm and it is quite simple. In response to your comment, I posted a proof at the end of this message.

Hope this helps, this is my first post in this site,

---

**Theorem**: $f(n) \< h^\*(n)$ is a sufficient condition for expansion of node $n$ in A$^\*$-like search algorithms provided that $h(n)$ is an *admissible* heuristic function.

**Proof**: I will proof this by induction on the number of steps of the A$^\*$ search algorithm. Since the proof relies on the monotonicity of $f(n)$ I will first prove it.

$f(n) = g(n) + h(n)$ is a monotonically increasing function (when solving minimization problems). Recall the definitions of $g(n)$ and $h(n)$ provided above.

If $h(n)$ is a *consistent* heuristic function (i.e., a heuristic function is said to be consistent if it satisfies the triangular inequality $|h(n) - h(m)| \leq c(n,m)$ where $c(n,m)$ is the cost of the operator from $n$ to $m$), then the $f$-value of a node $m$ which is a descendant of node $n$ lies in the interval $\[g(n)+c(n,m)+h(n)-c(n,m), g(n)+c(n,m)+h(n)+c(n,m)\]=\[g(n)+h(n), g(n)+h(n)+2c(n,m)\]\geq g(n)+h(n) = f(n)$.

Incidentally, the wikipedia says: "If $h(n)$ is consistent then the value of $h(n)$ for each node along a path to goal node are non decreasing" but this is not strictly speaking true, this is just a result of the original definition provided above.

If $h(n)$ is an $inconsistent$ heuristic function (so that it that does not satisfy the aforementioned property) then $f(m)$ can be arbitrarily smaller than $f(n)$. However, since $h(n)$ is an admissible heuristic function, $max\\{h(n)-c(n,m), h(m)\\}$ is an admissible heuristic function for node $m$ and using it the same interval results.

Now, bearing in mind that $f(n)$ increases along a path to the goal and that $h(n)$ never overestimates the effort to reach the goal state, it is straightforward to prove the theorem by induction

**Base case**: the start node $s$ is introduced in the OPEN list and it is selected for expansion. Since $f(s)=g(s)+h(s)=h(s) \leq h^\*(s)$ (by hypothesis of the admissibility of $h(\cdotp)$) the theorem has been proved for the base case.

**Induction step**: at each iteration of the A$^\*$ search algorithm the first node $n$ in OPEN is selected for expansion. By induction, it is assumed that $f(n) \leq h^\*(n)$. If $n = t$ (the target state), the search immediately terminates and $f(n)=g(n)+h(n)=g(n)$ is the optimal cost of the path $s-t$. Otherwise, the descendants of node $n: n\_1, n\_2, ... n\_k$ are inserted into the OPEN list in increasing order of $f(\cdotp)$. I will now proof that the expansion of $n$ leaves the OPEN list in such a state that the first node $m$ has $f(m) \leq h^\*(m)$, because it will be expanded in the next iteration this would proof the theorem by induction. Two cases might arise:

*Case 1*: one of the descendants of node $n, n\_i$ has an $f$-value $f(n\_i) = f(n)$ (recall that $f(n)$ is a monotonically increasing function). In this case, it would be ranked first (maybe along with other nodes in case of a tie), since it has the same $f$-value of its ancestor which was already first in the OPEN list.

*Case 2*: all the descendants of node $n, n\_i, \forall i=1, \ldots k$ have $f(n\_i) \> f(n)$. In this case, these nodes would be arranged in OPEN after the second state in OPEN when $n$ was selected for expansion. Since $f(n\_i)\leq h^\* (n\_i)$, but they are larger than the second best node in OPEN, node $m$ has to verify that $f(m) \leq h^\*(m)$ and this concludes the proof.

# Answer
> 0 votes
Every descendant of n that is reachable from n by a—wrt h2 strictly C\*-bounded path will also be expanded by A2\* and possibly not by A1\*. h\*\>=h2\>=h1 A2\* algorithm A\* using h2 A1\* algorithm A\* using h1

Do you have an example for that and its a statement from judea pearl only. For the Answer to original question i think A2\* will dominate A1\* strictly only when h2\>h1, not allowing equality between the heuristics functions.

---
Tags: artificial-intelligence, heuristics, search-problem
---


title: Limit on table size - perfect hashing

text:
# Question
Title: Limit on table size - perfect hashing
Let us define a ***"root universal family"*** as a family of hash function which for every two items $k\_i,k\_j$ the probability $P(h(k\_i)=h(k\_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table.

Now, let us have $|U| = n$ - (the size of the given universe, note that it is **perfect** hash).

Define an efficient perfect hash algorithm, for which the total sizes of the tables is $\le O(n^2)$.

Now, we note that if we have a table of size $n^2$, then the expected number of collision of a random hash function from that family is $\le \frac{n}{2}$. This is because:

$$\mathbb E\[\text{number of collisions}\] = \sum\_{\\{k\_i,k\_j\\} \subset U, k\_i\ne k\_j}P(h(k\_i)=h(k\_j)) \le \frac{\binom{n}{2}}{\sqrt {n^2}} \le \frac{n}{2}$$

So, we define the "first-level" hash table to be of size $n^2$. The expected number of hash function we need to draw in order to have less than $n$ collisions is $2$ (since it is a geometric variable).

Now, this is where I get stuck:

After a hash family that satisfies less then $n$ collisions is chosen, for each table that has items colliding, we make a "second-level" table of size $|\text{number of collisions in table}|^4$. (It is easy to prove that in order to get no collisions when the size is $x^4$ we need again two draws for the second function.

The problem I having is showing that all the "second-level" tables + the "first-level" tables are $O(n^2)$ of total size. Would like help in proving that, Thanks!

# Answer
Ok, I managed to prove it:

We note that the total size of the tables = $$n^2 + \sum\_i n\_i^4$$ where $n^2$ is the first table and $n\_i$ is the size of the $i$th index of table with collisions. Therefore we get:

$$n^2 + \sum\_i n\_i^4 = n^2 +\sum\_i (n\_i^2)^2 \le n^2 + \sum\_i (4\binom{n\_i}{2})^2 \le n^2 + 16(\sum\_i \binom{n\_i}{2}) = n^2 +16(\text{number of collisions})^2 = n^2 + 16n^2 = O(n^2)$$
> 0 votes

---
Tags: data-structures, probability-theory, hash-tables
---


title: Efficient implementation of sets

text:
# Question
Title: Efficient implementation of sets
Let *U* be a **pre-determined and fixed universal set** (and *|U| = n = 2k* for some integer *k*, so the set may be huge).

I create many arbitrary subsets of *U* in running time (These sets may be or may not be sparse).

I do not need to check whether an element is in a set.

But I need to be able to

* check whether a set is **empty**,
* do the basic set operations **difference** and **intersection**, and
* calculate the **cardinality** of a set.

What is the most time-efficient data structure for this? It should be also space-efficient, if possible.

I have **bit vector** in my mind. Elements of *U* are numbered from *0* to *n-1*. Each of *n* bits represents the existence of the corresponding element.

* For *k ≤ 5* or *k ≤ 6* (depends on the computer architecture and the programming language) I can implement these sets as \[unsigned\] integers.
* But there will be a need for multi-word arithmetics in general case. So I believe, the space complexity of any set is **ϴ(n)** and time complexities of operations are **ϴ(n)** using bitwise operations and hamming weight.

# Answer
Yes, using a bitvector, the running time will be $\Theta(n)$, i.e., $\Theta(2^k)$, for all operations.

If most sets are small in cardinality, a better option may be to use a sorted list of the elements in the set. In this way, you can compute the intersection or difference of two sets of size $m\_1,m\_2$ in $\Theta(m\_1+m\_2)$ time (they work similar to the "merge" operation in mergesort). You can compute the cardinality of a set of size $m$ in $\Theta(m)$ time, and test emptiness in $O(1)$ time. If the size of the sets is small compared to $n$, this might be much faster.

You can make the cardinality operation take $O(1)$ time when using a sorted list by augmenting the data structure: when you construct the list, compute its cardinality and store that in a separate slot along with the list. Now cardinality lookup takes $O(1)$ time. It is easy to keep track of the cardinality of the new set when performing an intersection or differencing operator.

If there is some "pattern" to the set of elements in the set, another option might be to use a binary decision diagram (BDD). You think of each element of $U$ as a $k$-bit vector, and think of a set as a set of $k$-bit vectors. Then, you can use a BDD to represent that set. Alternatively, we can associate to any set $S$ of a function $f:\\{0,1\\}^n \to \\{0,1\\}$ so that $f(x)=1$ if $x \in S$; then represent $f$ as a BDD (this is equivalent, and just a different way of thinking about the same thing). If there is sufficient "structure" in the elements of the set, this might allow a more concise representation of the sets and more efficient operations. The running time to compute the intersection or difference of two BDDs is related to the sizes of those BDDs. In many contexts BDDs might be ineffective (they add implementation complexity with no improvements in performance), but in some special cases they might be useful.
> 4 votes

# Answer
If you want a class that can be generally used without any special casing, and which is as efficient as possible, you'd use different data structures depending on which kind of set it is.

For the general case, you store a set as a bitmap: Assume we can store k bits in one word efficiently (whatever a "word" is, for example 32, 64, 128, 256 bits). If all set elements are less than n then we need n / k words, rounded up to the nearest integers. If there are no elements ≤ m then we can not store m / k words, rounded down to the nearest integer. Storage is about n - m bits. Emptiness and first or last element are O (1). Element count is O (n - m) but can be cached. Union, intersection etc. are O (n - m) depending on the values of n, m of both operands.

For sets with few elements, we can store an array containing the sorted list of elements instead. Storage is proportional to the number of elements. Set operations are proportional to the number of elements in both sets (the smaller set for intersection). Instead of elements you could store the difference between elements. Combining both kinds of sets is still fast.
> 1 votes

---
Tags: algorithms, data-structures, sets
---


# Question
Title: Compression for set of integers preserving their sequence
For a given positive number `n`. Numbers from `0` up to `n`, are streamed one by one in some order without repetition.

What would be recommended a strategy to store the order of these `n` numbers in the most space conservative way?

Highest priority is to consume minimal bits to store the order. Second highest priority is to have minimal effort in adding the incoming number to the current order Least priority is the computational complexity in retrieving the order.

Retrieval will be done only when all `n` numbers have been added.

Deletion operation will not be performed.

# Answer
> 2 votes
Given that all the numbers form 0 to N-1 are to be stored, and their order, there will be N! permutations. The minimum number of bits needed to store any combination and its order from an randomly selected order will be

$$\lceil \frac{\log(n!)}{\log(2)}\rceil$$

For example give a range of {0..99} (N=100) the Number of bits to store the permutations is $\lceil \frac{\log(100!)}{\log(2)}\rceil = 525\text{bits}$.

This can be encoded using a Mixed-Radix Calculation, or can be done using Arithmetic Coding (with a slight extra few bits).

In short using a LIST of the numbers to choose from. Each time one of the numbers is eliminated, to take the last number in the list, move it to fill in the eliminated number, adjust the "stats" for Arithmetic coding. Since All the symbols are equally, the same percent applies to all the symbols, and makes easy and Linear time to encode.

Each elimination increase percent chance of the next symbol (IE Number) occurring in the remaining of the list using list of the 0..(N-1) and using the move the last item to the empty position, and shorten the list.

A hash table can be used to make finding the number to replace be done in $\mathcal O(1)$ expected time, for the $\mathcal O(N)$ sequence.

---
Tags: data-compression
---


title: Is this a legal Fibonacci heap?

text:
# Question
Title: Is this a legal Fibonacci heap?
> Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? In other words, does there exist a series of actions that lead to this sort of heap structure.

My intuition tells me no, because it just seems too "unstructured". On the other hand, it doesn't seem to violate the max degree property or any other basic properties of a Fibonacci heap.

I thought about extracting the minimum and seeing if that'll lead to an illegal heap, but it doesn't seem to be the case.

# Answer
It's not possible. You propose a root node with degree 4 and size 7 (including itself).

From CLRS 3ed pp 525:

> *Lemma 19.4*
>
> Let $x$ be any node in a Fibonacci heap, and let $k = x.degree$. Then $size(x) \geq F\_{k + 2}$.

$$ \begin{align} k & = 4\\ F\_{6} & = 8\\ 7 & \ngeq 8\\ \end{align} $$
> 3 votes

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: Algorithmic complexity of a Maximum Capacity Representatives variant
I have been trying to find the algorithmic complexity of a problem that I have. I am almost sure it is either NP-hard or NP-complete but I cannot find any proof. Recently, I found that my problem can be something similar to a special instance of the Maximum Capacity Representatives problem, which is NP-complete. However, the objective function to optimize in my case is different than the one in the MCR problem.

The problem that I am trying to solve is the following:

INSTANCE: Disjoint sets $S\_1, \ldots, S\_m$ and, for any $i \neq j$, $x \in S\_i$, and $y \in S\_j$, a nonnegative capacity $c(x,y)$.

SOLUTION: A system of representatives $T$, i.e., a set $T$ such that, for any $i$, $\vert T \cap S\_i\vert=1$.

MEASURE: $\min \\{c(x,y): x,y \in T \\}$.

And my goal is to maximize $\min \\{c(x,y): x,y \in T \\}$.

Do you know any way to determine the complexity of my problem? Is there any well known problem in the literature that can be reduced to this one?,

Thanks in advance.

# Answer
I'm assuming that the goal of your optimization problem is to maximize $\min \\{ c(x,y) : x,y \in T \\}$. The decision problem is then:

> Given a system $S\_1,\ldots,S\_m$ of disjoint sets, a cost function $c\colon S \times S \to \mathbb{R}\_+$ (where $S = S\_1 \cup \cdots \cup S\_m$) and a number $\gamma \in \mathbb{R}\_+$, decide whether there is a choice of representatives $t\_i \in S\_i$ such that $c(t\_i,t\_j) \geq \gamma$ for all $i \neq j$.

This problem is NP-hard (and so NP-complete), by reduction from max clique. Given a graph $G = (V,E)$ and a number $m$, let $S\_i = \\{i\\} \times V$, define $c((i,v),(j,w))$ to be 1 if $(v,w) \in E$ and 0 otherwise, and let $\gamma = 1$. The graph $G$ contains an $m$-clique if and only if the answer to your decision problem is affirmative.
> 2 votes

---
Tags: complexity-theory, optimization, sets
---


# Question
Title: Why is the assumption in the max heapify procedure crucial to its implementation?
While watching MIT's 6.006 Lecture # 4 which is on heaps and heapsort, the professor was explaining why the time complexity of the max\_heapify procedure is $O(\lg n)$. It's quite intuitive that it's bounded by $\log n$. But there's a lurking reason also, that affects the implementation, and that reason was the key assumption which has imposed to the procedure, namely the trees rooted at left(i) and right(i) are max heaps. Why is that? Why the assumption plays a role in its implementation? Is it even necessary?

# Answer
> 2 votes
Heaps support several operations. Among them is the operation of extracting the maximal element. Heaps are constructed so that all supported operations have low complexity. In particular, in order for us to maintain the property that the maximal element is at the root after extracting the maximum, we need the left and right subtrees to be max-heaps as well.

There are other data structures which handle this differently, such as self-balancing binary trees, but these tend to be more complicated, and as a result slower in practice (even though they have the same asymptotic complexity).

---
Tags: algorithms
---


title: What is a fixpoint?

text:
# Question
Title: What is a fixpoint?
Could someone please explain me, what is a fix point?

I caught the minimum explanation about fix point from the website:

> After infinitely many iterations we should get to a fix point where further iterations make no difference. It means that applying one more ExprF would't change anything -- a fix point doesn't move under ExprF. It's like adding one to infinity: you get back infinity.

But could not configure it out, what does it mean.
Can please someone explain me in a very easy for a dummy like me.

# Answer
> 11 votes
Putting it very simply, a fixed point is a point that, when provided to a function, yields as a result that same point. The term comes from mathematics, where a fixed point (or fixpoint, or "invariant point") of a function is a point that won't change under repeated application of the function.

Say that we have function $f(x) = 1/x$. For $x = 2$ we get result $\tfrac12$. If we applied the function again, we find $f(f(2))=2$. It's back to where we started, but we're alternating between these values. However, for $x = 1$ a single application of the function yields $1$ again. This means that $f(1) = f(f(1)) = f(... f(f(1))... )$. The value $1$ is a fixed point for function $f(x) = 1/x$.

A fixed point $x$ for a function $f(x)$ is some point that satisfies the equation $x = f(x)$. There might be no fixed points for a function, one, or multiple. For example, every $x$ is a fixed point for function $f(x) = x$ (which is actually the definition itself).

In computer science, more specifically combinatory logic, a fixed point for a function $f$ is some value that won't change under application of $f$ (or more precisely, that returns an identical value for $f$). For recursion, for example, it would be useless to apply a further recursive call to the function because the returned value would be identical to the argument. Another example of where it might hold meaning is in the gradient descent algorithm, where a fixed point would be the local minimum sought through the descent. Repeated applications of the algorithm would yield the same result every time, at which point we can stop because there will be no further refinement of the result.

# Answer
> 4 votes
Formal definition: a **fixed point** of a function $g : D \rightarrow D$ is an element $d : D$ such that $(g \ d) = d$ (source: *Design Concepts in Programming Languages*, p. 167).

Make it simple: a fixed point is simply a solution to the equation $f(x) = x$.

Intuitively: say $D = \[0, 1\]$. Then, imagine the unit square and its diagonal (which is the line $y = x$. If a function $g : \[0, 1\] \rightarrow \[0, 1\]$ does have a fixed point, it means that the graph of $g$ intersects the diagonal some way.

Say, for example, $g = x^2$. We know that the solution to $g(x) = x$ on $\[0, 1\]$ are $x = 0$ and $x = 1$. Thus, $x$ is a fixed point for $g$.

Why is it important for PL people? Everything in $\lambda$-calculus is anonymous, so, to do recursion, we need to have a function that gives back the function we recurse on every time we do a recursive call, i.e. one that has the recursive function as a fixed point. See this page for example.

For even more on fixed points, see, e.g., *Design Concepts in Programming Languages*, ch. 5.

---
Tags: terminology, type-theory, fixed-point
---


# Question
Title: Number of Retransmission in case of Go Back N
While Going through **Exercise problem** of " **Computer Networking** A Top-Down Approach" by Kurose and Ross, i encountered this problem.I am giving my approach and the point where i am stuck at.

## Question

> Suppose Host A sends 5 data segments to Host B, and the 2nd segment (sent from A) is **lost**. In the end, all 5 data segments have been correctly received by Host B.How many segments has Host A sent in total and how many ACKs has Host B sent in total for **Go Back N**

### Given Answer

> GoBackN: $A$ sends $9$ segments in total. They are initially sent segments $1, 2, 3, 4, 5 $and later resent segments $2, 3, 4, $and $5$. $B$ sends $8$ ACKs. They are $4$ ACKS with sequence number $1,$ and $4$ ACKS with sequence numbers $2, 3, 4,$ and $5.$

## My Approach /Doubt

I agree with the number of transmission of data segment by Host $A$.But i have doubt regarding **the Acknowledgement by Host $B$.**

### Why?

> We know that GBN has sender side window size=$N$ while reciever side as only$1$ which is the reason that it cannot recieve Out of order packet.

Now When Host $A$ sends entire packet $1,2,3,4,5$ where $2^{nd}$ gets lost then Host $B$ which is expecting Sequence number $1$.On recieving sequence number $1$, it will send ack as $2$i.e expecting sequence number $2$.As Sequence number gets lost , host $B$ will recieve sequence $3,4,5$ for which it will discard the packet as it is not the packet it is expecting.

On recieving again sequence number $2,3,4,5$(retransmitted packet), Host $B$ will send the Acknowledgement.

Total Acknowledgement i am getting is $5$ i.e ACk no for sequence number $1,2,3,4,5$ not $8$.

Please help me out where i am wrong ??

Thanks

# Answer
> 1 votes
GBN is resending ACK's for the discarded packets .

Excerpt from what I can find:

The receiver's actions in GBN are also simple. If a packet with sequence number n is received correctly and is in-order (i.e., the data last delivered to the upper layer came from a packet with sequence number n-1), the receiver sends an ACK for packet **n** and delivers the data portion of the packet to the upper layer. **In all other cases, the receiver discards the packet and resends an ACK for the most recently received in-order packet.** Note that since packets are delivered one-at-a-time to the upper layer, if packet k has been received and delivered, then all packets with a sequence number lower than k have also been delivered. Thus, the use of cumulative acknowledgements is a natural choice for GBN.

---
Tags: computer-networks
---


# Question
Title: LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$
I want to construct a linear bounded automata for the language $L = \\{a^nb^{2n} \mid n\geq1 \\}$ . I know how LBA works but I don't have an idea how it can count the numbers of a's and check if the b's are 2 times more than a's. I would like to to hear some suggestions.

# Answer
> 2 votes
Repeatedly remove an $a$ from the beginning and a $bb$ from the end until the string becomes empty. If you cannot do it at any point, reject, otherwise, accept.

---
Tags: linear-bounded-automata
---


title: Complexity of multiplying matrix

text:
# Question
Title: Complexity of multiplying matrix
Let's consider the following algorithm to multiply squares matrix: `A` is a matrix of `NxN`. `r_i, r_j` defines interval of rows. For example `r_i = 2, r_j=3` means the second and the third rows. `c_i, c_j` means the same as `r_i, r_j` but for columns. We assume that `N = 2^s` for some `s`.

```
mul(A, B, r_i, r_j, c_i, c_j){
if(r_i != r_j){
   r_m = floor((r_i+r_j)/2)

   mul(A, B,  r_i, r_m, c_i, c_j)
   mul(A, B, r_m+1, r_j, c_i, c_j)
} else if(c_i != c_j){
   c_m = floor((c_i+c_j)/2)
   mul(A, B, r_i,r_j, c_i, c_m)
   mul(A, B, r_i, r_j, c_m+1, c_j)
}else{
 for i = 1 to N:
    C[r_i][c_i] += A[r_i][i] * B[i][c_i]
 }

}

```

And the most important:

Complexity of that algorithm takes: T(n) = 4T(n/2) + n = O(n^2)

And it is not correct. The correct answer is O(n^3). Why my computation is incorrect.

# Answer
> 1 votes
Your calculation is not right... $$ U(R,C) = 2U(\frac{R}{2},C)\textrm{ or } 2U(R,\frac{C}{2})\\ U(1,1) = O(n) $$

Basically, you have $N^2$ unique positions (which you drive your way down to recursively, rather than just looping) - for each of those you do a loop of O(N) so you have $O(N^3)$

# Answer
> 0 votes
Your algorithm can be unrolled to the usual $O(N^3)$ matrix multiplication algorithm. If you open up all the recursive steps you will get a recursion tree whose $N^2$ leaves are of the form `mul(A, B, r, r, c, c)`, each of which has running time $\Theta(N)$, for a total of $\Theta(N^3)$.

---
Tags: algorithm-analysis, runtime-analysis, matrices
---


# Question
Title: Approximation rate for Greedy Set Cover algorithm (RESOLVED)
**Set Cover**: Consider a set of points X and Si a subset of X. The goal is to get the minimum number of subsets Si such as all points in X are covered. An example is shown by figure bellow. In this case, optimal solution should be OPT = {S3, S4, S5}.

**Greedy Algorithm**:

`greedy(X, F = {S1, S2, ...})
 G_OPT = {}
 U = X
 while U = empty set
 Pick s in F with greatest coverage in U
 G_OPT = G_OPT + s
 U = U - s
 return G_OPT`

**Goal:** To find approximation rate of greedy set cover algorithm above.

**What I have so far:** Let **t** be the size of optimal soltion, $t = |OPT|$.

* At the beginning of step k + 1, the number of uncovered items in X is given by $|U\_{k+1}| = |U\_{k}| -$ # of newly covered items;
* By pigeonhole principle, # of newly covered items $\leq \frac{|Uk|}{t}$ and then $|U\_{k+1}| \leq |U\_{k}| - \frac{|U\_{k}|}{t} = |Uk|(1 - \frac{1}{t})$;
* Taking the Taylor's Series of $\exp(-\frac{1}{t})$, one can easily see that $exp(-\frac{1}{t}) \geq (1 - \frac{1}{t})$;
* So, $|U\_{k+1}| \<= |U\_{k}| \times exp(-\frac{1}{t})$;
* $|U\_{0}| = |X| = n$ (none item is covered at step 0);
* Taking $|U\_{1}| = n \times exp(-\frac{1}{t})$, gives $|U\_{2}| = |U\_{1}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{2}{t})$, $|U\_{3}| = |U\_{2}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{3}{t})$ so on and so forth. Therefore, $|U\_{k}| = n \times exp(-\frac{k}{t})$;
* Lets say there is no item uncovered at k-th step. So, $|U\_{k}| = 0$ and $n \times exp(-\frac{k}{t}) \< 1$ (otherwise, there could be a remaining uncovered item in $U\_{k}$, and this would be a contradiction of $|U\_{k}| = 0)$;
* It is possible to get $\frac{k}{t} \> ln(n)$ by taking log over the previous inequality.

The expected answer is $\frac{k}{t} \leq ln(n) + 1$. I have seen some lecture videos and lecture notes on the internet that give raise to the same results as I described above. However, they are all vague while getting from $\frac{k}{t} \> ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$.

All I can see about k, t and n is:

* $k \geq t$
* $t \leq n$

Does anyone know the "trick"?

# Answer
> 2 votes
I have figured out the answer.

The trick is not really coming from $\frac{k}{t} \> ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$ directly. Lets take 1 step back.

* Lets say there is no item uncovered at k-th step. So, $|U\_{k}| = 0$ and $n \times exp(-\frac{k}{t}) \< 1$ (otherwise, there could be a remaining uncovered item in $U\_{k}$, and this would be a contradiction of $|U\_{k}| = 0)$;

The step above can be rewritten as:

* Lets say there is no item uncovered at k-th step. So, $|U\_{k}| = 0$ and we are done. We are interested in how much steps we can take before that happens. So, find the upper bound of k such as $|U\_{k}| \geq 1$;
* $|U\_{k}| \geq 1 \Leftrightarrow n \times exp(-\frac{k}{k}) \geq 1$. This results in $k \leq \frac{ln(n)}{t}$. So, $k = \frac{ln(n)}{t}$ is our upper bound for iterations. If $k = \frac{ln(n)}{t}$, $|U\_{k}| = 1$. It's almost done. There is only 1 last item to cover and, consequently, 1 last round to run.
* Therefore, $k \leq \frac{ln(n)}{t} + 1$ in order to get $|U\_{k}| = 0$. It's easy to see that $\frac{k}{t} \leq ln(n) + \frac{1}{t}$.

One can still get a cleaner solution and say $\frac{k}{t} \leq ln(n) + 1$ since $t \geq 1$.

k is the number of steps taking to get G\_OPT. At each step, G\_OPT increases by 1. Then, $|G\\\_OPT| = k$. We defined $t = |OPT|$. We end up with

Approx. rate $= \frac{|G\\\_OPT|}{|OPT|} \leq ln(n) + 1$

---
Tags: approximation, set-cover
---


# Question
Title: Semantic readings of the Lambek sequent calculus
I am reading *Categorial Grammar: Logical Syntax, Semantics, and Processing* by Glyn Morrill and I am stuck with the Fig. 3.9:

**Can someone explain this set of formulas and |.| function specifically?**

This figure displays the definition of the |.| function that maps some proof (of some formula) in Lambek calculus (as fragement of intuitionistic logic) into lambda-term (by Curry-Howard correspondence there is correspondence between proof in some logic and terms in lambda calculus). I understand Lambek calculus and lambda calculus but I can not understand this picture? It is said in this book, tht |.| function is applied to **proof**, but this picture say something different - this function is applied to **proof rules**, that is completely different structure. What does small indices mu(ni, psi) and so on mean?

This was very good book up to this chapter, I am completely lost.

# Answer
> 7 votes
What constitutes a proof in a system like this is a *derivation* which is a tree of rule applications. The above translation function is defined by (structural) recursion over that tree. Note, this is why it labels the premises in the rules with $\delta$. This is intended to be mnemonic for "derivation".

I'm guessing but $\mu$ and $\nu$ appear to need to be sequences of lambda terms, while $\phi$ is a specific lambda term (or, equivalently, a single element sequence of lambda terms). $\Gamma$ is a sequence of formulas, and $\mu$ has a lambda term for each element of that sequence. Constructs like $x,\mu$ correspond to sequence extension, extending the sequence $\mu$ with the (particular) lambda term $x$ on the left, symmetrically for $\mu,x$. The parenthesis notation, e.g. $\Gamma(C)$ and $\mu(\dots)$ correspond to (consistently) operating on an element at an arbitrary location in the sequence.

So, for example, an instance of the $\bullet R$ case would look like: $$\left|\cfrac{\cfrac{\delta}{X,A,B,Y,Z\Rightarrow W}}{{X,A\bullet B,Y,Z\Rightarrow W}}\right|\_{t\_X,t\_{AB},t\_Y,t\_Z} = \left|\cfrac{\delta}{X,A,B,Y,Z\Rightarrow W}\right|\_{t\_X,\pi\_1(t\_{AB}),\pi\_2(t\_{AB}),t\_Y,t\_Z}$$

A translation of a complete derivation would look like: $$\begin{align} \left|\cfrac{\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}}{\cfrac{A\Rightarrow (A\bullet B)/B}{\Rightarrow ((A\bullet B)/B)/A}}\right| & = \lambda a\left|\cfrac{\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}}{A\Rightarrow (A\bullet B)/B}\right|\_a \\ & = \lambda a\lambda b\left|\cfrac{A\Rightarrow A \qquad B \Rightarrow B}{A,B\Rightarrow A\bullet B}\right|\_{a,b} \\ & = \lambda a\lambda b(\left|A\Rightarrow A\right|\_a, \left|B \Rightarrow B\right|\_b) \\ & = \lambda a\lambda b(a, b) \end{align}$$

---
Tags: formal-grammars, logic, lambda-calculus, natural-language-processing, category-theory
---


# Question
Title: Lambda calculus : what about the bound variables in substituting expression?
I found the following set of lemma in my lambda calculus textbook :

> **Lemma 1.16** Let $x, y, v$ be distinct (the usual notation convention), and let no variable bound in $M$ be free in $vPQ$. Then
>
> (a) $\[P/v\]\[v/x\]M \equiv \[P/x\]M$ if $v \notin \mathrm{FV}(M)$;
>
> (b) $\[x/v\]\[v/x\]M \equiv M$ if $v \notin \mathrm{FV}(M)$;
>
> (c) $\[P/x\]\[Q/y\]M \equiv \[(\[P/x\]Q)/y\]\[P/x\]M$ if $y \notin \mathrm{FV}(P)$;
>
> (d) $\[P/x\]\[Q/y\]M \equiv \[Q/y\]\[P/x\]M$ if $y \notin \mathrm{FV}(P), x \notin \mathrm{FV}(Q)$;
>
> (e) $\[P/x\]\[Q/x\]M \equiv \[(\[P/x\]Q)/x\]M$.

In the first lemma , the first stage of substitution can be done because $x$ is a free variable in $M$ and and no variable bound in $M$ is free in $V$. But what about variables which are free in $M$ but bound in $V$? In that case, the substitution would carry the risk of changing the semantics, like if there were a free variable in $V$, let's say $K$, and there were a term in $M$ like $\lambda.k$ then it would definitely make $K$ a bound variable in $M$ if the $X$ being replaced is at a position right to the $ \lambda .k$ and the substitution will be wrong.

How is this resolved? I am unable to see through this clearly.

# Answer
> 5 votes
$x$, $y$, and $v$ are *variables* not (arbitrary) terms. To the extent that it makes sense to say so, the only variable free in $v$ is $v$. There could still be an issue with, say, $M = \lambda v.x$, i.e. $\[v/x\]\lambda v.x$, but, by assumption, $v$ is not bound in $M$, so this is not a valid case; $v$ is clearly free in $vPQ$.

---
Tags: lambda-calculus
---


# Question
Title: P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?
Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model.

The *weakness* of this statement can be illustrated by NP-complete problems, which we think require way more time. But I'm looking for the easiest-to-solve decision problem in P that probably has $\Omega (n \log n)$ as lower bound in the Turing machine model (I say "probably", because proving it would be a scientific breakthrough). Such a problem would best illustrate the *power* of the statement "$NP \geq O(n \log n)$".

It inspired me to ask about a candidate: Deterministic linear time algorithm to check if one array is a sorted version of the other, but it may not be the simplest because Yuval pointed out it probably requires more than $O(n \log n)$ in the Turing machine model.

# Answer
> 2 votes
We know that there *exists* some problem in $P$ that can't be solved in $O(n \log n)$ time on a Turing machine; this follows from the time hierarchy theorem. As a result, there definitely exists some problem in $NP$ that can't be solved in $O(n \log n)$ time on a Turing machine. So your "it is not proven that..." statement is wrong; that *is* proven.

# Model of Computation

When dealing with relatively "small" running times, like $O(n \log n)$, the model of computation can make a big difference. For instance, there might be problems that are solvable in $O(n \log n)$ time on a multitape Turing machine but not on a single-tape Turing machine. Also, some researchers have studied problems that can be solved by circuits.

For circuits, the situation is rather depressing. We cannot identify any computable function $f:\\{0,1\\}^n \to \\{0,1\\}$ where we have a lower bound on circuit complexity that is $\omega(n)$. We know there exist problems that can't be solved by any circuit of size $O(n)$, but we can't identify any specific problem where we can prove this is the case. See, e.g., https://cstheory.stackexchange.com/q/21400/5038. This illustrates just how hard it is to prove lower bounds (see, e.g., https://cstheory.stackexchange.com/q/17789/5038 and references therein).

# Plausible candidates

Nonetheless, there are many plausible candidates where it might not be possible to solve them in $O(n \log n)$ time. For instance, 3SUM and other similar problems don't appear to have any $O(n \log n)$-time algorithm that we can find, so they might be reasonable candidates. Other examples include all-pairs shortest paths and linear programming.

For more, see https://cstheory.stackexchange.com/q/1284/5038 and https://cstheory.stackexchange.com/q/17578/5038.

# Careful with those Omegas!

You wrote that you wanted to find a problem that can't be solved in $O(n \log n)$ time. You also wrote that you wanted to find a problem that takes $\Omega(n \log n)$ time to solve. Beware that those aren't the same thing. The former is equivalent to looking for a problem that takes $\omega(n \log n)$ time to solve.

It is known that any language (decision problem) that can be solved in $o(n \log n)$ time on a single-tape Turing machine is in fact a regular language. Thus if you take any language that is not regular but is in $P$, it follows that the running time for a Turing machine to decide it is $\Omega(n \log n)$. Beware that this might not be what you want: this means the running time might be $\Theta(n \log n)$ or it might be even larger. I suspect you meant to ask for a problem that cannot be solved in $O(n \log n)$ time, i.e., that requires $\omega(n \log n)$ time.

---
Tags: turing-machines, polynomial-time
---


# Question
Title: How to derive the size of $k = \log n$ base from $\frac{1}{2^k} = O(\frac{1}{n})$?
"We need $k$ to be large enough so that $(\frac{1}{2})^k = O(\frac{1}{n})$, and to do this we can choose $k = \log\_2 n$. Thus, when $k = \log\_2 n$, the size of the active region has been reduced to a constant, at which point the recursion bottoms out and we can search the remainder of the array directly in constant time."

Im not certain on how they determine that $k$ needs to be $\log\_2 n$ from $(\frac{1}{2})^k = O(\frac{1}{n})$. Can someone please clarify the logic for this please?

# Answer
> 1 votes
Think about it if we remove the fraction. We need a $k$ large enough so that $2^k = O(n)$. We could do this simply by solving for $k$ in the expression $2^k = n$. Which is simply $k = \log\_2 n$. This is because $2^{\log\_2 n} = n$.

Now apply the same logic to your expression, with $k = \log\_2 n$ we see that: $$\frac{1}{2^{\log\_2 n}} = \frac{1}{n} = O\left(\frac{1}{n}\right)$$

---
Tags: algorithms, asymptotics
---


# Question
Title: How to show that $L=\{ wa^kw | w \in \{ a,b,c \}^* ,k \geq 0 \}$ is not regular using the pumping lemma for regular languages?
I'm trying to show that the language in the title is not regular but I don't know how to chose a decomposition $x = abc$ to express the word in the language because the $w \in \\{a,b,c\\}^\*$ is kinda tricky for me, I know it means $ \\{ a,b,c\\} \cup\\{ a,b,c\\}^2 \cup ... \cup \\{ a,b,c\\}^k $ but I don't know how to chose the decompositons for a word in the language and proove that is not in the language by pumping lemma. Any tips ?

# Answer
> 0 votes
After $n$ is fixed, you could choose $x = b^na^nb^n$. This string is clearly in $L$. By the Pumping lemma $x$ can be written as $uvw$, where $|uv| \leq n$ and $|v| \geq 1$. So for any choice of $u$ and $v$, $uv$ is a string consisting of only $b$s, and so is $v$. Thus $uv^iw = b...b(b...b)^ib...ba^nb^n$ which is not in $L$.

**On @DavidRicherby comment:**

**The Pumping Lemma:**

Let $L$ be a regular set. Then **there is a constant** $n$ such that if $z$ **is any word in** $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and **for all** $i \geq 0$, $uv^iw \in L$.

**How to use**

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$ in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = b^na^nb^n$.

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

In my proof the prefix of $z$ consists of $n$ $b$'s, so any choice of $u$, $v$, and $w$ implies that $v$ consists solely of $b$s.

5) You achieve a contradiction to the pumping lemma by showing that **there exists** $i$ such that $uv^iw \notin L$.

Just choose $i=2n$ and we have unequal number of $b$s on the left and right sides of the substring $a^n$: $b^{2n + d}a^nb^n \notin L$.

This is how we prove.

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


# Question
Title: What algorithm to use for training combinations
I would be very glad if someone could help me with my machine learning task. I have palettes of 5 colors each (in RGB format), and would like to train the neural network so that I can input a color, and the model would give me 4 other colors that would go best with it.

My training set consists of 1500 palettes (1500 * 5 = 7500 examples - each color from palettes is combined with four other). I've trained the network with multi-label classifier: one color as input (3 variables RGB) and one-hot encoded vector as output (I've predefined 68 classes, so it looks like \[1 0 0 ... 1 1 1\]). So basically, I have two questions:

1) Very strange, but when I try to predict colors that go best with my color, I always get the same colors, just with different probabilities (with sigmoid activation function). Why could this possibly happen? Why my probabilities never reach over 30%?

2) This still doesn't solve my problem - I get only suggestions on different colors, but these colors may not match between them. I need an algorithm that would take into account all 5 colors at once. What kind of algorithm could possibly solve this problem? Maybe combine several?

Thank you for your time reading this!

# Answer
> 1 votes
Your current setup might not be the best one for this. You need to think about the structure of the model, and the set of features you use.

# Model

I would suggest a different approach: see if you can construct a model that captures how well a set of 5 colors match. In particular, perhaps you can fit a model $f$, where $f(c\_1,\dots,c\_5)$ describes how well the five colors $c\_1,\dots,c\_5$ match each other (larger values of $f$ correspond to a better match). For instance, one plausible model for $f$ is

$$f(c\_1,\dots,c\_5) = \prod\_{i\<j} g(c\_i,c\_j)$$

where $g$ is some function (that you try to fit to the data). Then, given a training set that describes many different combinations of five colors and how well they match, you could try to fit a model to that (e.g., find $g$ such that $f$ matches the training set as closely as possible). You can then consider some architecture for $g$, e.g., a small neural network with a few hidden layers, and use gradient descent to train the model.

# Features

Constructing a model based solely on the RGB values might be a lot to ask. I suspect you can do a lot better by choosing some features that are likely to be relevant to color matching.

Often it helps to have some domain knowledge. Do you know anything about color matching? Are there any properties of colors that are relevant or informative or affect whether they match?

I would suggest that you pick multiple plausible features, then let the model training process work out which ones are most relevant. Here are some ideas for you to consider:

* Consider adding other color space as additional features. I would suggest you consider adding the CMYK, HSV, and CIELAB.
* It appears that primary colors are best matched with primary colors, and secondary colors best matched with secondary colors, etc. Therefore, when determining how well two colors $c\_i,c\_j$ match, perhaps the difference between their hues (modulo 360 degrees) might be relevant. You could add this as an additional feature that is input to $g$.

Maybe your study of the art of what colors match will suggest other features you can try as well.

# Answer
> 1 votes
So far, I have come to the following conclusions:

1) It is not correct to mix all colors with all, usually palettes are compiled the way that only neighbor colors match really good.

2) I have found a similar problem which is solved here http://colormind.io/. They use Conditional GANs. As input, they use pairs of two images (color palettes are treated as images with colors order preserved) - one full palette, and another with one or more colors filled into palette. The goal of the network is to learn to generate palettes from the second partial palette. I would suggest looking into this project https://phillipi.github.io/pix2pix/

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


# Question
Title: What does it mean for a problem to be solved in polynomial time "relative to" an oracle?
I came across the following theorem in page 12 of the following pdf :

> There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a quantum computer, but any probabilistic Turing Machine with bounded error probability solving this problem (using the oracle) will require exponential time (at least $2^\frac{n}{2}$ steps on infinitely many inputs (of length n).

My question is what does it mean to say "There exists an oracle relative to which there is a problem". My take on it is that if we try to solve the problem using a non deterministic T.M. or non deterministic Quantum computer (I don't know if such a thing even makes sense as I just started studying Quantum Computing) the oracle is a black box which tells the machine which path to take in the non deterministic step. Is this the correct interpretation?

# Answer
> 3 votes
Oracles have nothing to do with non-determinism. They are just a communication mechanism between the algorithm (or Turing machine) and an outside entity, the oracle $O$, which is just a language. In the classical case, the algorithm can query the oracle on a specific input $x$, and it immediately gets the (Boolean) value of the oracle at that input: 1 if $x \in O$, and 0 if $x \notin O$. I'm not quite sure how this works in the quantum case, but perhaps the PDF explains that.

The theorem states that there is some oracle that allows quantum algorithms to solve some problems much faster than classical ones. That is, if a quantum algorithm is given access to this oracle, then it can solve some problem in time Q, but a classical algorithm which is given such access can only solve the problem in time C$\gg$Q.

---
Tags: complexity-theory, terminology, quantum-computing, probabilistic-algorithms, oracle-machines
---


# Question
Title: Language of CFG: $S \to aS | aSbS | \varepsilon$
I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\\{ w \in \\{a,b\\}^\*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \\}$.I proved the first inclusion $w \in L(G) \implies w \in L$. I can't prove the vice versa. By induction on the lenght of $w \in L$, I could say:

BASE: $|w|=0$, i.e. $w=\varepsilon$ and it's clear.

IND: suppose the thesis is true whenever $|w|\<n+1$ and prove for a word of lenght $n+1$. Given $w \in L$, $w=a\_1\dots a\_{n+1}$ one has $a\_1=a$ since $a\_1$ is a prefix of $w$. Thus I can first apply the rule $S \to aS$ or $S \to aSbS$. But what now?

Any suggestion would be helpful. Thanks.

# Answer
> 1 votes
Let $w \in L$ be a word of length $n$. If $n = 0$ then clearly $w \in L(G)$, so suppose that $n \> 0$. For $0 \leq i \leq n$, let $\delta\_i$ be the difference between the number of $a$s and $b$s in the first $i$ characters of $w$; thus $\delta\_i \geq 0$ for all $i$. We now consider two cases:

**Case 1: $\delta\_i \> 0$ for all $i \> 0$.** In that case $w = ax$ for some $x \in L$. Induction tells us that $x \in L(G)$, and so $w \in L(G)$.

**Case 2: $\delta\_i = 0$ for some $i \> 0$.** In that case $w=axby$, where $|axb| = i$ and $x,y \in L$. Induction tells us that $x,y \in L(G)$, and so $w \in L(G)$.

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


# Question
Title: Was it known that $\mathsf{LTIME \subsetneq NLTIME}$?
$\mathsf{LTIME = DTIME(\log n), NLTIME = NTIME(\log n)}$.

For example, it seems that NTM can find an element in *unsorted* array in log-time by use of non-deterministic binary search (check if first half leads to solution and if second half leads to solution).

Obviously, it can't be done by log-time deterministically. I couldn't find anything about this despite the fact this is so simple.

So, was it known and does it imply any consequences? (DFA vs NFA, for example).

I also believe it doesn't imply $\mathsf{P \subsetneq NP}$ because $\mathsf{LTIME}$ is smaller class than $\mathsf{P}$ and inequality between bigger classes is stronger statement (maybe it's some kind of *any* hierarchy rule). Or does it?

# Answer
The other answer is quite misleading. The classes $\mathrm{DTIME}(\log n)$ and $\mathrm{NTIME}(\log n)$, usually denoted DLOGTIME and NLOGTIME, do indeed have a sensible and well-accepted meaning in the literature.

When discussing sublinear time classes (deterministic, nondeterministic, alternating, etc.), it is standard to use a Turing machine model that does not have an input tape, but a query tape on which one can write (in binary) the index of an input position, and obtain the input symbol at that position by entering a special state. (The query tape is not cleared or otherwise modified after a query.) This is essentially the same mechanism as used by oracle Turing machines, and the model is sometimes called the random-access Turing machine.

And yes, it is known that $\mathrm{DLOGTIME\subsetneq NLOGTIME}$: a simple NLOGTIME language not recognizable in DLOGTIME is $$L=\\{w\in\\{0,1\\}^\*: \text{$w$ has at least one $1$ at some position}\\}.$$ There are unconditional separations like this even for some bigger classes, for example $\mathrm{AC^0}$, whose uniform version coincides with languages recognizable by an alternating TM in time $O(\log n)$ with $O(1)$ alternations.
> 5 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Computational Complexity of Not All Equal SAT variant
Not All Equal SAT is an NP Complete problem. Let us now consider another variant of the problem.

Given a Not All Equal SAT (NAESAT) problem (arbitrary number of literals allowed per clause) with an additional constraint that each pair of clauses share at least 1 literal (not variables but literals).

Is this problem still NP-hard? It seems so, but I am unsure about the reduction.

# Answer
> 9 votes
**Your problem is NP-hard**, as can be seen by a (known, I believe) reduction from CNF-SAT: Reduce from (for example) $3$-SAT as follows. Given a formula $F$, create a formula for your special NAE-SAT by introducing exactly one additional variable, say $y$. Add $y$ to every clause in $F$ to obtain $F'$.

Example: $F = (x\_1 \vee x\_2 \vee \neg x\_3) \wedge (\neg x\_2 \vee x\_3 \vee \neg x\_4)$ becomes $F' := (x\_1 \vee x\_2 \vee \neg x\_3 \vee y) \wedge (\neg x\_2 \vee x\_3 \vee \neg x\_4 \vee y)$

After doing this, every clause contains $y$ and thus shares (at least) one literal.

**Proof sketch:** If $F$ is satisfiable, use the same satisfying assignment to satisfy $F'$, together with $y = false$.

If $F'$ is satisfiable, there are two options

* $y = false $, in this case the same assignment satisfies $F$ ($F'$ has at least one true literal per clause, and it is never $y$, thus $F$ has at least one true literal per clause as well)
* $y = true$, negate the satifying assignment for $F'$ to satisfy $F$ (at least one false literal per clause in $F'$, after negating the assignment we have at least one true literal per clause)

---
Tags: complexity-theory
---


# Question
Title: Is quick sort the best algorithm in average case compared to other comparison-based sorting algorithms?
I know that quick sort has an average case of O(nlogn). And I also know that the average case of comparison-based sorting algorithms are Omega of nlogn. Can we say that quick sort is the best sorting algorithm in average case compared to other comparison-based sorting algorithms? (I think the answer is yes. However, I cannot justify my answer with a convincing argument)

# Answer
> 1 votes
Depends. Quicksort is not one algorithm. Performance depends on the details. You would adjust the algorithm slightly if moving items is expensive.

You might assume that items are in random order. That is often not the case. You may be able to sort items with non-random items faster than using quicksort. For example if an array starts or ends with many items in ascending or descending order sorting in linear time may be possible.

---
Tags: algorithms, algorithm-analysis, sorting, average-case
---


# Question
Title: On what abstraction is a filesystem actually built on?
Data is read in terms of a **block** from a storage device(magnetic, optical, flash). Size of the **block** depends upon the **filesystem** and **os**. The physical device may have different units of storage like **sectors**.

Do **filesystems** create the abstraction layer directly over the physical device, or do they work over something called as a **block device**?

If they work over the **block device** then does it mean that when we create a **partition table**(gpt, msdos, mac) then **block device** abstraction is created and **filesystems**(fat, ntfs, ext) are then created for partitions of the device over the **block device** layer?

# Answer
You usually have several layers. You will have a physical level, where complete sectors can be read or written - except on SSD drives, you can only write into an area that is zeroed, and you can only zero sectors 32 or 64 at a time. Much more interesting than a hard drive.

On top of that you have a level that is still in the hard drive. Caches on a hard drive, highly complex controllers on an SSD drive. SSD drives especially need to be handled right to get maximum performance, and that is built into the controller instead of the operating system.

On top of that you usually have one level handling partitioning, possibly one level handle fusioning of partitions on several drives, and a level handling full disk encryption. And you'll build your file system on the highest of those levels.
> 1 votes

# Answer
Some physical devices are already block devices: they move data in blocks and present a uniform view of the storage as a bunch of blocks. For instance, hard drives and SSDs basically provide a block device abstraction: they let you read or write a block (sector) at a time. Filesystems are responsible for organizing the data and storing it on the storage device, by using the block-level operations provided by the storage device.

Partition tables are a way to store multiple filesystems on a single storage device. They're not really about creating a block device abstraction; they're orthogonal to the issues you're asking about.

The link you gave in a comment is not very helpful for understanding the answer to this particular question.
> 0 votes

---
Tags: filesystems, os-kernel
---


# Question
Title: Is Supervised Learning Better than Unsupervised Learning (For Recommendation Systems)
I am working on a Recommendation System as a personal project (I finish it on time, I'll present it as my final year project). I devised mathematical methods that estimated User's ratings of products based on their previous ratings, without using ML. I developed a host of such algorithms for recommendation (I developed a paradigm that allowed me to generate an infinite number of distinct recommendation systems). I intended to assign weights to a select few of them (maybe the ones with the highest accuracy), and take the weighted average of the estimated user ratings.

I realised that Machine Learning could be used to best determine the appropriate weight to assign each of the algorithms on a per user basis, and decided to start learning ML yesterday. It seems what I'm intending to do, is supervised learning.

From what I can tell, it seems existing recommendation systems on the market use unsupervised learning. I am curious to how the two paradigms compare in my case. Would supervised learning work better than unsupervised learning, or is unsupervised learning a better paradigm for recommendation systems?

# Answer
It doesn't make sense to ask if supervised learning is better or worse than unsupervised since they are used in different contexts.

In the most simple terms, supervised learning is used when you have a dependent variable, so you're investigating the relationship between this dependent variable and one or more independent variables. Often you're trying to predict something about the dependent variable using the independent variable(s).

In unsupervised learning, you are essentially looking for certain kinds of structure in the data or trying to find various kinds of relationships between variables, but none are considered special in the sense of being a dependent variable.
> 5 votes

---
Tags: machine-learning, recommendation-systems
---


# Question
Title: Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?
**Definitions:**

An up down language is a language whose alphabet is a set of **pairs**, but not characters, of two characters, where the one character in the pair is the opposite of the other character in the pair.

Each word in the language is concatenation of some characters from the alphabet given in the pairs of the alphabet set.

An up down language is emptible **if and only if** you can empty it, so it becomes **Φ** phi, **without getting an empty word**, which is marked as **ε** epsilon, before **by only doing the "reduce" action only.**

The "reduce" action is an action which removes a pair from the alphabet and then removes all words from the language that own/contain one character in the removed pair and also removes the other character in the removed pair from all words that were left/remaining in the language (after the first removal) that own/contain the other character in the removed pair. As a result the language becomes a set with fewer/lesser shorter words. This way it is possible to empty the language by repeating this action, i.e. the "reduce" action **only**, but it is also possible to get an empty word, i.e. epsilon **ε**.

Summary/In conclusion:

When given non empty up down language that doesn't own/contain the empty word **ε** epsilon, your objectives are/goal is:

1. Get the empty language **Φ** phi, which is a **must**.
2. Do **not** get the empty word **ε** epsilon before, which is **forbidden**.
3. You can only do the "reduce" action as defined above to achieve the first objective 1.

**Examples:**

The following up down language is **emptible**:

L={abc,bxd,ye} where Σ={(a,z),(b,y),(c,x),(d,w),(e,v)}

Because

Reduce(b,L)={e} where Σ={(e,v)} Note that the words that owned/contained the letter 'b' were removed from the language and the letter 'y' was removed as well, because 'b' was paired with 'y', so the word "ye" was shorten to "e"

and

Reduce(e,{e})=Φ

I could get Φ without getting ε so the above up down language is indeed **emptible**

**But** the following up down language is **not** emptible:

L={ab,ay,zc,zx} where Σ={(a,z),(b,y),(c,x)}

Because:

Reduce(a,L)=L'={c,x} where Σ={(c,x)} again words with the letter 'a' were removed, but 'a' is paired with 'z', so the letter 'z' was removed as well and the word "zc" was shorten to "z" and the word "zx" was shorten to "x".

Reduce(c,L')={ε}, because the word "c" was removed and 'x' was paired with 'c', so the letter 'x' was removed as well. Because the only word left was "x" and 'x' was removed, so it became the empty or **ε** in other words. So this attempt was failure, because we didn't get **Φ**, but **ε** instead.

Of course it shouldn't say that the above up down language is not emptible, because I tried only one option. Instead of Reduce(c,L'), I could try Reduce(x,L') instead, but also Reduce(x,L')={ε}, because the word "x" was removed this time and "c" was remained, but 'x' is paired with 'c', so 'c' must be removed as well and thus "c" becomes ε. So again, I got ε, but not Φ. So starting with Reduce(a,L) wasn't the right choice. I could start with **Reduce(b,L)** or **Reduce(c,L)** or **Reduce(x,L)** or **Reduce(y,L)** or **Reduce(z,L)** instead. I won't try the other options, because this will take too long, but you can try and you will see that in the all options, you get ε, but not Φ

**What I have tried already:**

I wrote the following **recursive** algorithm/function/procedure, **in pseudo code** that is bit similar to C/C++, to determine whether or not the given up down language is emptible or not, where the algorithm/function/procedure "Reduce" modifies the given up down language and then returns a clone/copy of it without updating the original given up down language, in other words, it clones/copies the given up down language, modifies the clone/copy and then returns the clone/copy. Assume that there is garbage collector that frees up unused allocated memory:

```
bool MyIsEmptible(up_down_language udl)
{
    if (udl.IsEmpty)
        return true;
    if (udl.Owns(epsilon))
        return false;
    for each (pair 'p' in udl.alphabet)
       if (MyIsEmptible(Reduce(p,0,udl)) or MyIsEmptible(Reduce(p,1,udl)))
          return true;
    return false;
}

```

The above algorithm/function/procedure is working, because it iterates **recursively** over all the possible options, but the problem is that the time complexity of this algorithm/function/procedure is **not** polynomial **in the worst case** where the given up down language is **not** emptible, and the time complexity, in the worst case, is big O notation of multiplication/product of exponent of n by base 2 and factorial of n and this is too expensive.

**Proof:**

Assume that 'n' is the number of pairs in the alphabet. In the first iteration, the algorithm walks over all pairs and each pair twice for the first and its opposite the second character in the iterated pair, so right now the time complexity of this algorithm is Ω(2•n). But the recursive calls do exactly the same thing for n-1.

So the time complexity of this algorithm can be expressed as: T(n)=2•n•T(n-1)

This evaluates to: 2•n•2•(n-1)•T(n-2)=22•n•(n-1)•T(n-2)=2n•n!

So

**T(n) = O(2n•n!)**

I **believe** that only **greedy** algorithm can solve this **decision/search** problem in **polynomial time**, but it will have to use some temporary data structure to accomplish this, so the **space complexity** of this algorithm is **not** O(1), but it can be **polynomial**.

# Answer
Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word.

e.g.

* 3 SAT: (a,b,-c) && (-b,c) =\>
* pairs: (a,-a), (b,-b), (c,-c).
* words: (a,b,-c), (-b,c)

Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding clauses are removed (they are satisfied) and the remaining clauses that contain the negation of that character/literal have that literal removed, as those clauses need to be satisfied with one of the remaining literals.

It is NP-hard.
> 7 votes

---
Tags: time-complexity, space-complexity, greedy-algorithms, search-problem, search
---


title: Uniformly Random Nested Subset Pairs

text:
# Question
Title: Uniformly Random Nested Subset Pairs
## Main Question

We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example

```
A B C D E F
1 0 0 1 0 1
1 0 0 0 0 1

```

is a nested subset, where the first mask tells us inclusion in the first set and the second mask tells us inclusion in the first. In this case the first set is `{A,D,F}` and its subset is `{A,F}`. I am trying to uniformly generate such subset pairs.

## Some Thoughts

One could try naively to generate two random masks, use the first for the union, then the second for the intersection where it overlaps. However, this would generate subsets uniform in the initial subset, and not the pair.

Mathematically speaking this can be done by weighting each mask by the number of possible subsets it has (`2^n` where `n` is the size of the subset), randomly drawing a subset, then randomly drawing an intersection from it. However this is very challenging/inefficient to implement in practice

My first idea was to find some (efficient) hash function from integers into subset pairs, however I have not had much success with this. I am wondering if there is a superior way to do this. I don't need code (I don't have implementation issues); I am looking a conceptual approach. Any advice?

# Answer
For the sake of simplicity, I will assume that: 1) empty sets are allowed, 2) we count a set as a subset of itself (i.e.: both the big set and small set can represent the same set). If these assumptions don't hold, the math gets a little messier but the basic principles still hold.

First, we observe that there are $2^i{n\choose i}$ pairs of subsets where the bigger subset has cardinality $i$ and that there are a total of $\sum\_i 2^i{n\choose i} = 3^n$ such pairs.

We proceed as follows:

1) We choose $k$ (between $0$ and $n$), the size of the bigger subset. This will not be a uniformly random choice but our initial observation lets us know the correct probabilities, i.e.: $P(k = i) = 2^i{n\choose i} / 3^n$.

2) We choose uniformly among the ${n \choose k}$ subsets of cardinality $k$ to be our bigger subset. Reservoir sampling should do the trick.

3) We choose uniformly among the $2^k$ subsets of the bigger subset to be the smaller subset. Simply choosing a random number from $0$ to $2^k-1$ and using the natural correspondence between sets and binary representations of integers should suffice.

EDITED TO ADD:

I just realized an even slicker way to do this but it depends heavily on the first two assumptions I stated. Unlike my originally provided method, I don't see an obvious way to adapt it if either of those assumptions fails to hold.

Recall that we deduced that the total number of eligible subset pairs was $3^n$. We can identify a bijection between each subset pair and $\\{0,1,2\\}^n$, i.e.: vectors of length $n$ with entries in $\\{0,1,2\\}$. Let $v$ be such a vector. If the $i^{th}$ entry of $v$ is $2$, then put $i$ in both sets; if it's $1$, then put it only in the bigger set; if it's $0$, ignore it.

So, the problem reduces to generating a number between $0$ and $3^n-1$ and examining its ternary representation.
> 6 votes

---
Tags: algorithms, combinatorics, randomized-algorithms
---


# Question
Title: Is $DSPACE(f) \subseteq DTIME(f)$ always?
Is $DSPACE(f) \subseteq DTIME(f)$ always?

For example, if we have a language $A\in DSPACE(log^2(n))$ can we say that $A\in P$ (and subsequently in NP and coNP) since $DSPACE(log^2(n))\subseteq DSPACE(n^3) \subseteq DTIME(n^3)$?

I know about $ DTIME(f) \subseteq DSPACE(f) \subseteq DTIME(2^{O(f)})$ but $DTIME(2^{O(f)})$ is too big in this case.

# Answer
> 5 votes
We don't know that $\mathrm{DSPACE}\[f(n)\]\subseteq\mathrm{DTIME}\[f(n)\]$ is *ever* true and we suspect that it's never true.

A Turing machine that uses space $f(n)$ can run for $2^{O(f(n))}$ steps without getting stuck in an infinite loop, so it should be able to do much more than a Turing machine that can only run for $f(n)$ steps. As you've observed, if $\mathrm{DSPACE}\[f(n)\]\subseteq\mathrm{DTIME}\[f(n)\]$, then $\mathrm{DSPACE}\[f(n)\]=\mathrm{DTIME}\[f(n)\]$ and we have no reason to think that would ever be true for reasonable functions.

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


# Question
Title: How to find number of permutations of 1-N length, each [1-N] with k values
This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values.

A real-world example might include 5 different single-digit combination locks.

How many different ways could I lock a single gate, assuming that I can use any number of locks?

Assuming that each lock takes values `([1-3], [1-3], [1-3], [1-3], [1-3])` There would be `3^5 == 243` possible combinations. But I'm also interested in calculating the total number of combinations possible by using subsets of the 5 locks, so adding the solution for each *combination* of four locks, each combination of 3 locks and so on. The solution would also ideally be generalisable so that each list of values can differ i.e. `([1-2], [1-10], [A-C] ... )`

Does there exist a mathematical solution to this problem?

---

edit:

In the main, the question is about a general purpose mathematical solution. For example, to find the number of combination of a set of length (3), one uses `3!` ie. 6 combinations of \[1,2,3\].

I was wondering if there exists a general purpose solution to the above scenario. If not, I would think it could be possible to program something to recurse over the possibilities, which I guess is why I decided to post it here first as my search for a mathematical solution came up empty handed.

---

Some examples of inputs and outputs as requested:

input = \[A,B,C\] \[1,2,3,4,5\] \[G,H\]

output combinations are all possible combinations of those three lists, without needing to sample all three lists. Note combinations, hence \[A1G\] == \[G1A\]

i.e. (this is not all the combinations): A B C A1 A2 A3 ... C4 C5 A1G A1H A2G A2H ... C5G C5H ... 1 2 3 4 5 1G 1H . . 5G 5H .. G H

# Answer
(Your lock values are all distinct. We could instead consider the locks distinct.)

We add a `nil` value to each lock, representing the lock *not* being included. Using your example, we get ...

```
input = [A,B,C,nil] [1,2,3,4,5,nil] [G,H,nil]

```

... to choose from. There are ...

$$4 \times 6 \times 3 = 72 $$

... ways to do this.

In general, from sets $Locks$, there are ...(

$$\prod\_{l \in Locks} (\vert l \vert + 1)$$

... ways.

---

So far, so mathematical. Now let's generate the possibilities. I'll have to use a programming language. My choice is Clojure, a Lisp. We should be able to at least verify the above result.

```
(def locks '[[A,B,C] [1,2,3,4,5] [G,H]])

(defn combos [ls]
  (if (empty? ls)
    [()]
    (let [[l & ls] ls
          sub-list (combos ls)]
      (concat
        sub-list
        (for [x l, y sub-list] (cons x y))))))

```

Now

```
(count (combos locks))
=> 72

```

... as expected.

There are better ways to depict the problem space, but this'll surely do.
> 1 votes

---
Tags: combinatorics, permutations
---


# Question
Title: Is it decidable whether a Turing Machine will visit every non-end state from input x?
L = {w#x | w,x ∈{0,1}∗ and Turing Machine Mw with input x visits every non-end state at least once}

I believe this problem is undecidable.

My proof would consist of me reducing L to a Halting Problem; however, the structure of these proofs seem incosistent and inconclusive. I would appreciate if I could have some constructive feedback.

My understanding of the proof:

1. Create R which decides L
2. Construct algorithm S, which decides Atm (which we reduce to L)
3. Contradiction because Atm is undecidable

This is the skeleton to most Turing Machine dicidibility related proofs I have read on the internet.

# Answer
> 1 votes
It's undecidable because you could use it to decide halting.

Because the number of states in a Turing machine is finite you can enumerate all $2^n$ combinations of possible non-end states. Run the algorithm against all of them.

If the algorithm returns yes for a group of states that includes an original end state then the machine halts.

Halting problem is undecidable so the algorithm cannot be executed by a Turing machine.

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


# Question
Title: Lambda calculus :Will there be any x left after first substitution?
I found the following set of lemma in my lambda calculus textbook :

> **Lemma 1.16** Let $x, y, v$ be distinct (the usual notation convention), and let no variable bound in $M$ be free in $vPQ$. Then
>
> (a) $\[P/v\]\[v/x\]M \equiv \[P/x\]M$ if $v \notin \mathrm{FV}(M)$;
>
> (b) $\[x/v\]\[v/x\]M \equiv M$ if $v \notin \mathrm{FV}(M)$;
>
> (c) $\[P/x\]\[Q/y\]M \equiv \[(\[P/x\]Q)/y\]\[P/x\]M$ if $y \notin \mathrm{FV}(P)$;
>
> (d) $\[P/x\]\[Q/y\]M \equiv \[Q/y\]\[P/x\]M$ if $y \notin \mathrm{FV}(P), x \notin \mathrm{FV}(Q)$;
>
> (e) $\[P/x\]\[Q/x\]M \equiv \[(\[P/x\]Q)/x\]M$.

I am stuck at (e) .I wonder if there is any order to be followed while evaluating this kind of expressions or there isn't any .What I think is that in $\[P/x\]\[Q/x\]M $ we would replace all the $ x $ in $ M $ by $ Q $ and as such we wouldn't be having any more $ x $ to be replaced by $ P $ . Then there is no point in the the exterior substitution expression ,i.e. $ \[P/x\] $ . How to explain this ?

# Answer
After $\[Q/x\]M$ we no longer find free occurrences of $x$ ... **unless** $x$ is free in $Q$! The simpler example is $Q=x$, where $\[x/x\]M=M$ can have free occurrences of $x$.

In such case, the free $x$s due to $Q$ can be replaced by $\[P/x\]$ in your example.

E.g. $\[z/x\]\[(\lambda y.\ x)/x\](x(yx)) = ((\lambda y.\ z)(y(\lambda y.\ z)))$.

According to (e) we have indeed

$$ \begin{array}{l} \[z/x\]\[(\lambda y.\ x)/x\](x(yx)) \\ = \[\[z/x\](\lambda y.\ x)/x\](x(yx))\\ = \[(\lambda y.\ z)/x\](x(yx))\\ = ((\lambda y.\ z)(y(\lambda y.\ z))) \end{array} $$

Finally, note that when $x$ is not free in $Q$, we have $\[\[P/x\]Q/x\]M = \[Q/x\]M$ as an immediate consequence of $\[P/x\]Q=Q$.
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD)
In the Geometric Spanner Networks book by Giri Narasimhan and Michiel Smid Page 153 says

> ***Definition 9.1.3 (Well-Separated Pair Decomposition).*** Let $S$ be a set of $n$ points in $\mathbb R^d$, and let $s \> 0$ be a real number. A well-separated pair decomposition (WSPD) for $S$, with respect to $s$, is a sequence
>
> $\\{A\_1, B\_1\\},\\{A\_2, B\_2\\}, \cdots , \\{A\_m, B\_m\\}$
>
> of pairs of nonempty subsets of $S$, for some integer $m$, such that
>
> 1. for each $i$ with $1 \leq i \leq m, A\_i$ and $B\_i$ are well-separated with respect to $s$, and
> 2. for any two distinct points $p$ and $q$ of $S$, there is exactly one index $i$ with $1 \leq i \leq m$, such that
>     * $p \in A\_i$ and $q \in B\_i$ or
>     * $p \in B\_i$ and $q \in A\_i$

Look at the following image

The points $x\_1, x\_2, x\_3$ are given in the plane and the split tree is drawn. Suppose for some $s$ the WSPD is built as shown. In this way the well separated pairs are going to be

$ A\_1 = \\{x\_1, x\_2\\}, B\_1 = \\{x\_3 \\} $

$ A\_2 = \\{x\_1\\}, B\_2 = \\{x\_2 \\} $

The $x\_1,x\_2$ together are well separated to $x\_3$ and $x\_1$ is well separated to $x\_2$. As you see $x\_1 \in A\_1$ and $x\_1 \in A\_2$, so it is in more than one pair which contradicts the definition.

I would like to know what is the problem with my example and why every point is in exactly one pair in Well Separated Pair Decomposition?

Thanks in advance.

# Answer
> 1 votes
OK, I found it. The definition says

> for any **two** distinct points ...

It means I must consider two points, not a one solitary. $x\_1$ is well separated with $x\_3$, and it is well separated with $x\_2$ as well, But there is exactly one pair that separates $x\_3$ from $x\_1$ and also there is exactly one pair that separates $x\_2$ from $x\_1$

---
Tags: algorithms, graphs, computational-geometry
---


# Question
Title: Is Weighted Averages the Best Method to Aggregate Information?
I'm working on a recommendation system. My system uses user's past rating data, to predict future ratings.

I designed mathematical methods for generating recommendation algorithms that allows me to generate an unlimited number of recommendation algorithms (given a large enough set of relevant ratings).

I intend to aggregate the results from all this algorithms to compute a final expected rating of the user. So I thought of taking the weighted averages of the expected ratings of each algorithm to use to calculate a final expected rating.

Basically I either:
1. Assign weights based on the amount of information (ratings collected).
2. Assign weights based on the accuracy of the algorithm used.

The algorithms arrive at their answer via different means, and it is possible that two may give the same answer, but they may take into account different information and/or use different inferential techniques on that information.

So if an accuracy of 1 means there's no deviation between the algorithm's expected ratings, and the user's actual ratings, and an accuracy of 0 means there's maximum deviation between an algorithm's expected ratings and user's actual ratings, we may get $\\{Al\_1, Al\_2, Al\_3\\}$ with accuracies of $(0.9, 0.85, 0.92)$.

I have a minimum information and/or accuracy threshold that I would use to filter the algorithms to assign weights to (I have not yet figured out what this threshold would be, and as it may vary on a per user basis, I want to leave determining the threshold to an ML system.

My question is this:

> Is weighted averages the Best methods for me to aggregate the data provided by my various algorithms/infer from it?
> If not, what other methods are more apt for the problem at hand?

# Answer
A weighted average might or might not be the best method. This will depend on (a) the nature of the algorithms, and (b) what objective function you are trying to minimize.

Let me give you a sample set of assumptions. Suppose we treat the predictions from the recommendation algorithms as independent random variables (e.g., because each recommendation algorithm was trained independently). Also, suppose we wish to minimize the variance of the final prediction. In other words, our loss function is the $L\_2$ loss: if our prediction was $Y$, and the correct value was $\tilde{Y}$, then the loss (penalty) is $(Y-\tilde{Y})^2$.

Then in this case we can find the optimal set of weights. In particular, in this case, if we restrict ourselves to linear combinations, the optimal set of weights is inversely proportional to the variance of each estimator. Suppose $X\_1,\dots,X\_n$ are the predictions from our $n$ recommendation algorithms. Suppose that we have measured the accuracy of each recommendation algorithm by measuring its $L\_2$ loss on a validation set; in other words, we know the variance $\text{Var}(X\_i)$ for each $i$. Here $\text{Var}(X\_i)$ is a measure of the accuracy of the $i$th recommendation algorithm: the larger the variance, the larger the expected $L\_2$ loss, and thus the less accurate the prediction is. Then the optimal linear weighting is to select a final prediction $Y$ by

$$Y = c\_1 X\_1 + \dots + c\_n X\_n,$$

where we choose the weights

$$c\_i = {a\_i \over a\_1 + \dots + a\_n}$$

where

$$a\_i = {1 \over \text{Var}(X\_i)}.$$

Is a linear combination optimal (as opposed to other, nonlinear methods of combining the predictions)? In this situation, if we additionally know that the errors made by each recommendation algorithm have a Gaussian distribution, then yes, a linear combination is optimal. If the errors have a different distribution, then some other combination might be better.

As you can see, this will depend on the loss function we select, and on other assumptions. That said, in practice, a linear combination (i.e., a weighted average) is often a reasonable choice.

There's lots written about this sort of thing in the statistics literature. For instance, the above discussion is just a restatement of the fact that the average is the optimal estimator of the mean of a Gaussian distribution (i.e., it minimizes the mean squared error). See, e.g., https://en.wikipedia.org/wiki/Estimator, https://en.wikipedia.org/wiki/Mean\_squared\_error, https://stats.stackexchange.com/q/81571/2921, https://stats.stackexchange.com/q/97765/2921, https://stats.stackexchange.com/q/48864/2921, https://math.stackexchange.com/q/9032/14578.
> 2 votes

---
Tags: machine-learning, recommendation-systems
---


# Question
Title: Computation of normalized first derivative in discrete case
I am reading a paper on recognition of online handwritten characters. One of the features proposed in the paper is "normalized first derivatives, $(\hat{x}'\_t,\hat{y}'\_t)$", which they have defined as follows:

$$ \hat{x}'\_t=\frac{x'\_t}{\sqrt{(x'\_t)^2+(y'\_t)^2}}\quad\quad \hat{y}'\_t=\frac{y'\_t}{\sqrt{(x'\_t)^2+(y'\_t)^2}}\\,, $$ where

$$ x'\_t=\frac{\sum\_{i=1}^2i(x\_{t+i}-x\_{t-i})}{2\sum\_{i=1}^{2}i^2}\quad\quad y'\_t=\frac{\sum\_{i=1}^2i(y\_{t+i}-y\_{t-i})}{2\sum\_{i=1}^{2}i^2}$$ I have couple of doubts with respect to these definitions:

1. If the derivatives are to be normalized, what is the significance of the denominators in the definition of $x'\_t$ and $y'\_t$?
2. Why is the difference scaled by $i$ in the numerator? What I understand is that this scaling gives more weight to the points farther from the central point.

# Answer
For the first part of your question, the significance is just to guarantee that the vector $(\hat{x}'\_t,\hat{y}'\_t)$ has length $1$. This means that it tells us in which direction $(x\_t,y\_t)$ is changing, but not by how much. For example, $(\hat{x}'\_t,\hat{y}'\_t)=(1,0)$ tells us that $x\_t$ is increasing and $y\_t$ is constant; $(\hat{x}'\_t,\hat{y}'\_t) = (-\sqrt{2}/2, \sqrt{2}/2)$ tells us that $x\_t$ is decreasing, and $y\_t$ is increasing at the same rate.

The second part isn't something I know about, so I'll leave that for somebody else.
> 1 votes

# Answer
As you have noticed, the denominators in the definition of $x'\_t,y'\_t$ ultimately have no effect, as they will be normalized away.

Nonetheless, they do have significance. This definition ensures that $x'\_t,y'\_t$ represent the derivatives. If you omitted the denominators in the definition of $x'\_t,y'\_t$, you'd get the same value for $\hat{x}'\_t,\hat{x}'\_t$, but the expression for $x'\_t,y'\_t$ would look less familiar and $x'\_t,y'\_t$ would no longer correspond to the derivatives (they would be some scaled version of the derivative), so it might be harder for some readers to see what's going on.

In other words, think of this explanation as optimized for ease of understanding for readers. There are often many ways to describe something, and hopefully we choose the one that's easiest on our readers.

I don't know why the authors scaled the difference by $i$. It doesn't have any advantage that I can see. The expression given there approximates the first derivative, up to an error term of third order, which is better than the simpler expression $x'\_t = (x\_{t+1}-x\_{t-1})/2$... but the same would be true even if the difference wasn't scaled by $i$, so that can't be the explanation. You might need to ask the authors. It appears that an even better approximation would be

$$x'\_t = -\frac{1}{12} x\_{t+2} + \frac{2}{3} x\_{t+1} - \frac{2}{3} x\_{t-1} + \frac{1}{12} x\_{t-2}$$

and similarly for $y'\_t$. This approximation is accurate up to a fourth-order term, which is better than the one in your question. See https://en.wikipedia.org/wiki/Finite\_difference\_coefficient.
> 1 votes

# Answer
You are given a stroke passing through points: $(x\_{t-2}, y\_{t-2}), (x\_{t-1}, y\_{t-1}),(x\_{t}, y\_{t}), (x\_{t+1}, y\_{t+1}), (x\_{t+2}, y\_{t+2})$. You fit a straight line to these points, to obtain $x'\_t$ and $y'\_t$ ($dx$ and $dy$), and then normalize these vectors.

It looks like a regression formula computing $x'\_t$ and $y'\_t$, but I am not sure how it is derived. The following picture may give you idea. The middle point on $X$-axis is $(x\_t, y\_t)$.

> If the derivatives are to be normalized, what is the significance of the denominators in the definition of $x'\_t$ and $y'\_t$?

The denominators are used to normalize the vector $(x'\_t,y'\_t)$, to convert $(x'\_t,y'\_t)$ to the unit vector providing the direction of the vector does not change. Please look here for significance of normalization.

You should check references of the paper how these formulas are derived.
> 0 votes

---
Tags: machine-learning, pattern-recognition, features
---


# Question
Title: List count of occurrences pairs, triplets, etc. from sets
A receipt is an array of products. I have an array of receipts.

I need to generate a report in where I can find the products often bought together.

For instance, for a single receipt where the products bought are `[A, A, B, B, B, C]`, a report would look like

```
Pair - count
A&B - 2
A&A - 1
B&B - 1
A&C - 1
B&C - 1

```

Notice that pair B&A is no longer counted because this is the same as A&B, and similar occurrences. It also has to be sorted by count, decreasing. Also notice that this is just from one receipt rather than multiple, which is what is required.

I also need the algorithm to scale to triples and quadruples, not just pairs.

How would I create an algorithm like this?

There are no set time efficiency constraints. In fact, a more readable solution is preferred over more efficient solutions although efficiency is also appreciated. A python solution is also appreciated, but any language or pseudocode will do.

# Answer
This is the itemset mining problem. Use any standard algorithm for that problem. Follow the links to learn more about standard algorithms for that task.
> 1 votes

---
Tags: algorithms, arrays, data-mining
---