# Question
Title: How is a procedure application a control structure?
In scheme, a procedure application is considered as a control structure. Why is this?

# Answer
The answer will depend on how you define "control structure", for which there are probably $n+1$ versions out there.

My best guess is this. Control structures *change* the control flow of the program from just incrementing the program counter. In usual machine-level languages, this is implemented using *jumps*.

Calls to functions/procedures/methods compile to jumps, among other things. Hence, they change the control flow, and we can call them "control structure".
> 2 votes

---
Tags: terminology, programming-languages, language-design
---


# Question
Title: Costs of updating arrays to contain only zeroes
To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also?

And in that case, setting an $n$-array to zero inside a loop with $n$ iterations should be $O(n^2)$, right? I am asking because I have written some code that does this, but the runtime only increases linearly when I increase $n$, not quadratically as I would have expected, so I don't quite understand. Is it perhaps to do with the compiler?

# Answer
> 4 votes
> To initialize an array of length n has complexity O(n), as far as I understand. If I set every element to zero (with one code line), does that have time complexity O(n) also?

The answers to both questions depend on the machine model. In common ones, like e.g. the RAM model, writing every memory cell take a constant amount of time $c$. Hence, intializing an array of length $n$ takes time $cn + d \in \Theta(n)$, with $d$ being some constant overhead.

Now, doing

```
arr = new array[n]
for i = 0 to n-1
  arr[i] = some_value
end

```

incurs *both* the cost for initializing `arr` *plus* the cost for the `for`-loop, which is not too hard to analyse. It has, in fact, linear runtime cost (with common RAM-model assumptions).

> setting an n-array to zero inside a loop with n iterations should be O(n²), right?

I don't understand your algorithm perfectly, but if you mean above code with `some_value = 0` then no. The total running-time cost is linear since costs *add up*.

If you mean something like

```
arr = new array[n]
for i = 0 to n-1
  setAllToZero(arr)
end

```

then it depends on how `set_all_to_zero` is implemented. If it contains an explicit loop, then we'd expect quadratic runtime cost. If there are machine-level instructions to set a whole stretch of memory to zero, it may be faster.

The same holds for array initialization, by the way: if the machine (model) does not guarantee any specific value after array intialization, or has some nifty way to ensure zeroes everywhere without extra cost, array initialization may only take constant time.

---
Tags: algorithm-analysis, runtime-analysis, arrays, loops
---


# Question
Title: Bijective algorithm(s) that can shuffle a range of numbers back and forth
I've spent the last hours trying to come up with an algorithm that shuffles an ordered set of numbers (i.e a simple range of numbers) in a way that I can retrieve from a shuffled value the original value that was on that position without the need to store all relationships between shuffled values and their counterparts.

The statement above may not make any sense to you, but I've learned some terms while trying to find such algorithm that may help me to describe what I mean...

First of all I believe that this algorithm/function is bijective, which means it is **deterministic** and one member of $A$ has **only one** correspondent member of $B$ and vice-versa:

Another peculiarity is that input and output domains are exactly the same so, following the above example, $A$ = $B$ = $D$ with $D$ being a range from $m$ to $n$.

To sum everything up (sorry I'm pretending that I know math):

$D = \\{x \in \mathbb N\ | m \le x \le n \\}$

$ \forall x \in D \land \forall y \in D\\ f(x) = y \implies \exists g(y) = x $

**What could be done to simply implement $f$ and $g$ ?**

The closest solutions I've found are some kind of block cipher which I'm unable understand nor tweak to achieve the desired behavior which is much simpler.

As one last attempt to explain this, here is a simple use case:

* Consider integer codes that can range from 1 to 2^31
* On the backend these codes are used sequentially, getting increased one by one
* Instead of sending one of these codes for a client, our function picks another code from that range to represent the original one
* Despite we need to use those codes sequentially we are only sending the random values for the clients so it looks random from his perspective
* When we receive this code back the from the client we're able to tell the original code
* We would also be able to change the way that these codes are "shuffled", so different codes could be exposed over time while leaving the original ones untouched on our side

Sorry if I wasn't clear enough or destroyed math notations forever.

# Answer
> 5 votes
The subject is called format-preserving encryption,
and your last bullet point is addressed by tweaks.

Simple
http://web.cs.ucdavis.edu/~rogaway/papers/feistel.pdf
http://arxiv.org/pdf/1208.1176.pdf
http://web.cs.ucdavis.edu/~rogaway/papers/sr.html
Complex

---
Tags: algorithms, cryptography
---


title: How to denote an array in writing paper

text:
# Question
Title: How to denote an array in writing paper
How can I represent an array when I am writing to show an algorithm in writing paper. Like Pi is represented by Greek letter. We use that Greek symbol to denote the value of Pi, Kind of like a pointer.

So, is there any general symbol for representing array?

# Answer
People often use capital letters to represent arrays. $A$ is a common choice (for the 'a' in 'array'), but by no means mandatory.
> 3 votes

# Answer
No, there's no standard. To enhance readability you should pick something that serves as a mnemonic for your readers, you might want to pick $S\[\ldots\]$ for something representing a string, and perhaps $P\[\ldots\]$ for representing a pattern, and so on... If you are dealing with a general array, then as D.W. suggests you can use $A\[...\]$ but unless you're writing a paper on sorting algorithms there might be something more appropriate.
> 2 votes

---
Tags: algorithms, arrays, notation, didactics
---


# Question
Title: How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?
How are asymptotical time complexities calculated for recursive algorithms?

Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they better taking time complexity into account? If they are better than non-recursive algorithms, then how are they better and why (not)?

# Answer
> 4 votes
When the design of an algorithm is ready, one can evaluate its running time. If one wishes to implement the algorithm, (s)he can do so recursively or iteratively. It's just an implementation detail, it won't affect asymptotical running time.

As an example, consider the problem of sorting an array of size $n$.

There are a lot of algorithms to solve this problem with a lot of different time complexities. Two examples are:

* Merge Sort, which runs in $O(n\times log(n))$;
* Insertion Sort, which runs in $O(n^2)$.

Both algorithms can either be implemented using a recursive approach or an iterative approach. It will not affect their asymptotical running time.

Assume we're given a recursive version of Merge Sort and we wish to evaluate it's running time.

```
func mergesort( var a as array )
     if ( n == 1 ) return a

     var l1 as array = a[0] ... a[n/2]
     var l2 as array = a[n/2+1] ... a[n]

     l1 = mergesort( l1 )
     l2 = mergesort( l2 )

     return merge( l1, l2 )
end func

```

This pseudocode takes an array as input, divides the given array in half, recursively calls mergesort on both halves and then merges both halves. The merging process looks like

```
func merge( var a as array, var b as array )
     var c as array

     while ( a and b have elements )
          if ( a[0] > b[0] )
               add b[0] to the end of c
               remove b[0] from b
          else
               add a[0] to the end of c
               remove a[0] from a
     while ( a has elements )
          add a[0] to the end of c
          remove a[0] from a
     while ( b has elements )
          add b[0] to the end of c
          remove b[0] from b
     return c
end func

```

The (iterative) merge function takes two arrays as input. It will compare the first element of both arrays. The biggest element is added to the last not-yet-filled-in slot of a new array $c$. Then, the biggest element is removed from its array. This is repeated until both given arrays are empty, the now fully filled list $c$, which is sorted, will be returned.

One can calculate the running time of merge sort by solving its recurrence:

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

The running time of any recursive algorithm can be represented by a similar equation above.

$T(n)$ represents our asymptotic running time. The term $2T(\frac{n}{2})$ is there because in our algorithm we recursively call the same algorithm twice and pass it an array with input size which is half of our original input size. The term $O(n)$ is there because we call the algorithm merge after, which runs in $O(n)$ (do you see why?).

To solve the recurrence, we can apply the master theorem. Case two applies here (do you see why?), so we can conclude that merge sort runs in $T(n) = \Theta(n \times log(n))$.

I will not discuss an iterative implementation of merge sort here. But if you would look it up and evaluate its running time; you would see it runs in the same running time.

To summarize, the design/general idea of an algorithm defines its running time. Recursive/Iterative versions of it are just an implementation detail.

I sense you are also wondering what the advantage/disadvantage of a recursive algorithm is over its iterative sibling since they're equivalent in running time anyway.

The disadvantage you mention (it takes more space on the stack) is generally a very small one and is only a significant problem in a few circumstances. The advantage of recursive algorithms could be that their implementation results in much cleaner, less and more readible code. Merge sort is a nice example to express this advantage.

# Answer
> 7 votes
Typically, by writing a recurrence relation for the running time and then solving the recurrence relation. See How to come up with the runtime of algorithms? and Solving or approximating recurrence relations for sequences of numbers. You might also want to read your friendly textbook and Is there a system behind the magic of algorithm analysis?.

---
Tags: algorithm-analysis, runtime-analysis, recursion
---


# Question
Title: How can simulated annealing be related to the vehicle routing problem?
I have been searching through internet how could simulated annealing to solve the vehicle routing problem, but didn't find anything that made it clear to me. Most of what I found are research papers intended to solve some specific variation of the routing problem.

So I would appreciate if someone can make some kind of explanation of possible ways two things can be related and give some links that to so.

# Answer
Simulated annealing is an optimization paradigm, in which (very roughly speaking) you start with some solution, and then try to make local changes that improve it, sometimes making a local change even if it doesn't improve.

Vehicle routing is an optimization problem. It is likely that the simulated annealing paradigm can be applied to it, probably in many different ways (corresponding to different notions of local change).
> 2 votes

---
Tags: algorithms, optimization, randomized-algorithms, routing
---


title: Checking whether a node is expandable

text:
# Question
Title: Checking whether a node is expandable
I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable. A node is said to be *expandable* if it has a child node that hasn't already been visited.

How can I test whether a given node is expandable?

I know you could always try out *every* play possible given a node, and test whether each generated node is already a node in the tree, but that seems inefficient. Is there a more efficient algorithm?

The rules of Quoridor are (quoting from Wikipedia):

> Quoridor is played on a game board of 81 square spaces (9x9). Each player is represented by a pawn which begins at the center space of one edge of the board (in a two-player game, the pawns begin opposite each other). The objective is to be the first player to move their pawn to any space on the opposite side of the gameboard from which it begins.
>
> The distinguishing characteristic of Quoridor is its twenty walls. Walls are flat two-space-wide pieces which can be placed in the groove that runs between the spaces. Walls block the path of all pawns, which must go around them. The walls are divided equally among the players at the start of the game, and once placed, cannot be moved or removed. On a turn, a player may either move their pawn, or, if possible, place a wall.
>
> Pawns can be moved to an adjacent space (not diagonally), or, if adjacent to another pawn, jump over that pawn. If an adjacent pawn has a third pawn or a wall on the other side of it, the player may move to any space that is immediately adjacent to other adjacent pawns. The official rules are ambiguous concerning the edge of the board.
>
> Walls can be placed directly between two spaces, in any groove not already occupied by a wall. However, a wall may not be placed which cuts off the only remaining path of any pawn to the side of the board it must reach.

I'm using the Monte Carlo Tree Search algorithm, which follows these steps:

1. **Selection**: Using a tree policy, like UCT1, nodes are selected while traversing down the tree
2. **Expansion**: From the node selected by the tree policy, create a random child node
3. **Simulation**: Either use a random simulation from the node or a system with a weighing of moves
4. **Backpropagation**: If the simulation is victorious for the computer, add say each node "won" all the way up the tree. If it lost, then each node "lost" up the tree.

During the Selection step, one cannot select a node that is fully expanded. Is there a better way to check whether a node is expandable than just trying out every possible move from that node, and check if it is already in the tree? What algorithms exist for this (if any?)

# Answer
You keep track of your work so far. As you say, a node is expandable if it has a child node which you haven't visited so far. In your program, every time you reach a new node in the expansion phase, you calculate all its children (you can also do this dynamically, but let's keep things simple). As time goes on, you mark each child which has been visited. In order to know whether a node is expandable, you just check whether all its children have been marked.

Of course, you don't really need to check all children. You can keep a counter at each node that counts the number of unvisited children. The next question would be – how do I find an unvisited child. It's a nice elementary exercise finding a way to achieve this efficiently.
> 1 votes

---
Tags: algorithms, trees, efficiency, board-games
---


# Question
Title: Markov Chain Mixing Time of the Complete Graph
I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn).

We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/degree(vi). This is assuming the edges have no weights and there are no self-loops.

Also, the stationary distribution pi exists such that pi\*P=pi.

For the complete graph, pi can be defined as a 1xn vector where each element equals 1/(n-1). I got this from defining each element to be deg(vi)/sum(deg(N(vi))) - the degree of node i divided by the sum of the degrees of its neighbors.

What would be the mixing time? I'm not sure how to go about finding it.

# Answer
> 2 votes
Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p\_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the transition matrix of $M$. The *variation distance* between $\pi$ and $p\_x^t$, which is a measure of the similarity between the distributions, is given by the formula $$ \\|\pi - p\_x^t\\| = \frac{1}{2} \sum\_{\sigma \in M} |\pi(\sigma) - p\_x^t(\sigma)|. $$ The sum goes over all states in $M$. The *mixing time* of a Markov chain $M$ is the smallest $t$ such that for every state $x$, $\\|\pi - p\_x^t\\| \leq 1/(2e)$ (your account may use a different constant).

Given a graph $G$ without disconnected nodes, we can define a Markov chain as follows. The state space is the vertex set of $G$. When at state $x$, the next state is chosen uniformly at random from the neighbors of $x$.

In the particular case of the complete graph $K\_n$, the random walk simply chooses a random vertex different from the current vertex. As you mention, $\pi$ is the uniform distribution. Let us compute some variation distances, for some vertex $x$ (the results are the same for all vertices): $$ \begin{align\*} &\\|\pi - p\_x^0\\| = \frac{1}{2} \left\[|\tfrac{1}{n} - 1| + (n-1) |\tfrac{1}{n}-0|\right\] = 1 - \frac{1}{n}. \\ &\\|\pi - p\_x^1\\| = \frac{1}{2} \left\[|\tfrac{1}{n} - 0| + (n-1)|\tfrac{1}{n} - \tfrac{1}{n-1}|\right\] = \frac{1}{2} \left\[\frac{1}{n} + \frac{n-1}{n(n-1)}\right\] = \frac{1}{n}. \end{align\*} $$ In both cases we have split the sum into two parts: $\sigma = x$ and $\sigma \neq x$. For all $n$ we have $\\|\pi - p\_x^0\\| \> 1/(2e)$. For $n \> 2e$ (i.e., $n \geq 6$), we see that $\\|\pi - p\_x^1\\| \< 1/(2e)$. Therefore for $n \geq 6$, the mixing time is $1$.

---

With some effort, we can compute explicitly the variation distances for larger $t$. The transition matrix of the Markov chain is $(J-I)/(n-1)$ (where $J$ is the all ones matrix and $I$ is the identity matrix). Denoting by $e\_x$ the basis vector corresponding to $x$, we have $p\_x^t = (J-I)^t/(n-1)^t e\_x$. Next, notice that $(J-I)/(n-1) \cdot \mathbf{1} = \mathbf{1}$ (where $\mathbf{1}$ is the constant 1 vector), and all other eigenvectors have the eigenvalue $-1/(n-1)$ (the corresponding eigenspaces being all vectors with zero sum). In particular, we can write $e\_x = \frac{1}{n} \mathbf{1} + (e\_x - \frac{1}{n} \mathbf{1})$, and so $$ p\_x^t = \left(\frac{J-I}{n-1}\right)^t e\_x = \frac{1}{n} \mathbf{1} + \left(-\frac{1}{n-1}\right)^t (e\_x - \tfrac{1}{n} \mathbf{1}). $$ Explicitly, we have $$ p\_x^t(y) = \begin{cases} \frac{1}{n} + \left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right) & \text{if } y = x, \\ \frac{1}{n} - \left(-\frac{1}{n-1}\right)^t \frac{1}{n} & \text{otherwise}. \end{cases} $$ Therefore $$ \begin{align\*} \\|p\_x^t - \pi\\| &= \frac{1}{2}\left|\left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right)\right| + \frac{1}{2} \left|\left(-\frac{1}{n-1}\right)^t \frac{1}{n}\right| \\ &= \frac{1}{2(n-1)^t} \left\[1 - \frac{1}{n} + \frac{n-1}{n} \right\] \\ &= \frac{1}{(n-1)^{t-1}n}. \end{align\*} $$ Using this explicit formula, we find that the mixing time of $K\_2$ is infinity (indeed, the chain is periodic), and the mixing time of all of $K\_3,K\_4,K\_5$ is $2$. For $n \geq 6$, as commented above, the mixing time of $K\_n$ is $1$.

---
Tags: graphs, probability-theory, markov-chains
---


# Question
Title: What theorem are these? (from Scott Aaronson's blog)
Browsing Scott Anderson's blog, I found this list of theorem. Among them are:

> If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a static, unchanging program; and a counter that could only be set to 1, 2, 3, 4, or 5, it would still be possible (given enough time) to carry out an arbitrarily long computation — just as if the memory weren’t being wiped clean each second. This is almost certainly not true if the counter could only be set to 1, 2, 3, or 4. The reason 5 is special here is pretty much the same reason it’s special in Galois’ proof of the unsolvability of the quintic equation.
>
> It would be great to prove that RSA is unbreakable by classical computers. But every known technique for proving that would, if it worked, simultaneously give an algorithm for breaking RSA! For example, if you proved that RSA with an n-bit key took n5 steps to break, you would’ve discovered an algorithm for breaking it in 2n^1/5 steps. If you proved that RSA took 2n^1/3 steps to break, you would’ve discovered an algorithm for breaking it in n(log n)^2 steps. As you show the problem to be harder, you simultaneously show it to be easier.

I learnt a bit of computer science in college, but I had never heard of these 2. I am very interested in knowing these. Any know what theorems are these? Thanks.

(since I can't comment...can you be more detailed about how "natural proof" do anything here?)

# Answer
The first excerpt hints at Barrington's theorem. The second is probably about natural proofs.
> 4 votes

# Answer
Scott Aaronson, in a comment on the blog post those came from, gives a reference for each of the theorems. I quote directly from his blog. The first: "Width-5 branching programs can compute NC1 (Barrington 1986); corollary pointed out by Ogihara 1994 that width-5 bottleneck Turing machines can compute PSPACE."

The second: "Natural proofs (Razborov-Rudich 1993); in particular Wigderson’s observation about natural proofs for discrete log."
> 4 votes

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


# Question
Title: Algorithm for finding two smallest numbers in an array
I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like `Quicksort`(Average case complexity: `nlogn`) and then access the first two members of the array in `O(1)`.

Is my approach optimal or there are some alternative better approaches?

# Answer
> 14 votes
If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few operations per element in the array as you traverse the array, so it's $O(n)$ with a very small constant. It's probably impossible to come up with a sort-based approach that ever runs faster, except maybe for an array of size 4 or 5 or less.

# Answer
> 6 votes
The optimal number of comparisons (not necessarily the fastest one) goes like this for $n = 2^k$:

1. Compare $a\_1$ and $a\_2$, $a\_3$ and $a\_4$, and so on. Store only the smallest of each pair in a list $b\_1,\ldots,b\_{n/2}$.
2. Repeat $k-1$ more times to get the minimum $a\_{\min}$.
3. Let $L$ be the set of all $k$ elements which were compared to $a\_{\min}$ and were larger. Find the minimum of $L$. This is the second minimal element.

This algorithm uses $n + \log\_2 n - 2$ comparisons, which is the optimal number of comparisons. However, implementing the logic isn't trivial, so in practice it might be slower than the algorithm in user2566092's answer.

# Answer
> 5 votes
No, it's not optimal. Do you know an efficient way of finding the smallest number in an array? Knowing the smallest number, could you adapt that method to find the second smallest?

# Answer
> 4 votes
Hoare's algorithm, which Wikipedia calls Quickselect, can find the $k$ smallest elements of an array in $O(n)$ time for any fixed $k$.

It is a modified Quicksort algorithm that sorts the array but stops early, leaving the beginning part correct (in this case the first two elements) and the rest of the array in whatever partly-sorted state is most convenient.

# Answer
> -2 votes
Sorting would consume extra time if it was an array with small size.! It would be better if you would just traverse through the array once and keep track of the first smallest and use the first smallest for comparison so that you get 2nd largest. But for an array of large size.. It would be better to sort using some algorithms like heap sort, merge sort or heap sort.. Because, if the smallest element in the array would be at the end of the array, it will take you O(n) time.

---
Tags: algorithms, search-problem, selection-problem
---


# Question
Title: Why do I need a base case for n=3 when solving a d&c recurrence?
I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example:

$T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ where $T(1) = 1$

They assume that $T(n) = O(n \log n)$ and go on to prove it by using induction.

I understand the inductive step, but I do not understand how they find the base case.

For $n=1$ we have $T(1) \leq c1 \log 1 = 0$, which is wrong because $T(1) = 1$. So we can not use $T(1)$ as a base case.

For $n=2$ we have $T(2) = 2T(1) + 2 = 4$, so $4 \leq c2 \log2$. The last inequality holds for every $c \geq 2$.

In the book they write that we also need $n=3$ to be the base case. However, they do not really explain why. Why isn't $n=2$ sufficient?

# Answer
> 3 votes
They do not want $T(1)$ to occur as a base case as it causes troubles. $T(3)$ depends on $T(1)$, so if they didn't take $T(3)$ as a base case *in addition* to taking $T(2)$ as one, they'd run into trouble when applying the inductive step to $T(3)$ as the hypothesis does not hold for $T(\lfloor{\frac{3}{2}}\rfloor)=T(1)$.

---
Tags: recurrence-relation, induction
---


# Question
Title: Are those definitions of universal hash family equivalent?
I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.

Definition 1:

$H$ is a universal hash family if and only if $$\mathbb{Pr\_{h \in H}}\[h(k) = h(l)\] = 1/m$$

where $k \neq l$ and $k,l\in Key$ and $m$ is the Size of the Hashtable

Definition 2:

The same as above just substitute the equals sign with a less or equal sign.

Well, i think those definitions are equivalent, because i think the probability for a collision can't possibly be strictly less than 1/m or am i missing something?

P.S. I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

# Answer
> 1 votes
> I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

There are still families with collision probability less than $1/m$, e.g., with three keys and two buckets,

$$\\{(2, 1, 1), (1, 2, 1), (1, 1, 2)\\}$$

has collision probability $1/3 \< 1/2$, and there are other counterexamples for all other parameter settings. The most plausible path to your intuition being true would be if $h(k)$ and $h(l)$ were necessarily independent, but they're not and can in fact be anti-correlated.

# Answer
> 0 votes
There not the same. For example the identity hash table $h(x)=x$ you have: $$\mathbb{Pr}\_{h \in H}\[h(k) = h(l)\] = 0$$ which answer definition 2 but not 1.

\[Edit\] A more interesting answer I hope :)

Let $H\_n$ be the set of all functions of $\\{1..n\\}\to \\{1..m\\}$.

For $s\in \\{1 .. m\\}, i\in \\{1..n\\}$ we have $$\mathbb{Pr}\_{h\in H\_n}\[h(i)=s\]=\frac{\text{nbr of function s.t. }h(i)=s}{\text{total number of function}}=\frac{m^{n-1}}{m^n}=\frac{1}{m}$$ also for $s\_1,s\_2\in \\{1 .. m\\}, i,j\in \\{1..n\\},i\neq j$ we have $$\mathbb{Pr}\_{h\in H\_n}\[h(i)=s\_1\wedge h(j)=s\_2\]=\frac{\text{nbr of function s.t. }h(i)=s\_1\wedge h(j)=s\_2}{\text{total number of function}}=\frac{m^{n-2}}{m^n}=\frac{1}{m^2}=\mathbb{Pr}\_{h\in H\_n}\[h(i)=s\_1\]\mathbb{Pr}\_{h\in H\_n}\[h(j)=s\_2\]$$

It follows that $\forall i,j\in \\{1..n\\},i\neq j$ $$\mathbb{Pr}\_{h\in H\_n}\[h(i)=h(j)\]=\sum\_{s=1}^m \mathbb{Pr}\_{h\in H\_n}\[h(i)=s\wedge h(j)=s\]=\sum\_{s=1}^m\mathbb{Pr}\_{h\in H\_n}\[h(i)=s\]\mathbb{Pr}\_{h\in H\_n}\[h(j)=s\]=\frac{1}{m} $$

Hence $H\_n$ is universal in the sense of definition 1.

Let $H\_n'$ be the set of all function of $h:\\{0..n\\}\to \\{1..m\\}$ such that $h(0)=h(1)+1 \mod m$.

We the same proof as above it is obvious that $\forall i,j\in\\{1,n\\},i\neq j$ $$\mathbb{Pr}\_{h\in H\_n}\[h(i)=h(j)\]=\frac{1}{m}$$ and that $\forall j\in\\{2..n\\}$ $$\mathbb{Pr}\_{h\in H\_n}\[h(0)=h(j)\]=\sum\_{s=1}^m \mathbb{Pr}\_{h\in H\_n}\[h(0)=s\wedge h(j)=s\]=\sum\_{s=1}^m \mathbb{Pr}\_{h\in H\_n}\[h(1)=s-1\mod m\wedge h(j)=s\]=\sum\_{s=1}^m\mathbb{Pr}\_{h\in H\_n}\[h(0)=s-1\mod m\]\mathbb{Pr}\_{h\in H\_n}\[h(j)=s\]=\frac{1}{m} $$

**BUT** $$\mathbb{Pr}\_{h\in H\_n}\[h(0)=h(1)\]=0$$

Hence $H\_n'$ is universal in the sense of **definition 2** but not definition 1.

Sorry for the long answer. I hope I didn't made a mistake ...

# Answer
> 0 votes
No they are not equivalent. As a matter of fact, they are not definitions the same thing. The one with the less than or equal sign is called "universal hashing" and the one with the equal sign is called "pairwise independent hashing". Pairwise independent hashing is strictly stronger than universal hashing, and so both definitions are not equivalent.

---
Tags: algorithms, algorithm-analysis, hash, hash-tables
---


title: Probabilities, Unigram and Bigram

text:
# Question
Title: Probabilities, Unigram and Bigram
Assume that we have these bigram and unigram data:( Note: not a real data)
**bigram:**

#a(start with a) =21
bc= 42
cf= 32
de= 64
e#= 23

**unigram:**

\# 43

a= 84

b=123

c=142

f=161

d=150

e=170

what is the probability of generating a word like "abcfde"? I think for having a word starts with a the probability is 21/43. How about bc? is it like bc/b?

# Answer
> 2 votes
Augment the string "abcde" with # as start and end markers to get #abcde#. Now, as @Yuval Filmus pointed out, we need to make some **assumption** about the kind of model that generates this data. Because we have both unigram and bigram counts, we can assume a bigram model. In a bigram (character) model, we find the probability of a word by multiplying conditional probabilities of successive pairs of characters, so:

$\Pr\[\\#abcde\\#\] = \Pr(a|\\#)\*\Pr(b|a)\*\Pr(c|b)\*\Pr(d|c)\*\Pr(e|d)\*\Pr(\\#|e) $

To find the conditional probability of a character $c\_2$ given its preceding character $c\_1$, $\Pr(c\_2|c\_1)$, we divide the number of occurrences of the bigram $c\_1c\_2$ by the number of occurrences of the unigram $c\_1$.

So, for example $\Pr(e|d) = count(de)/count(d) = 64/150$

# Answer
> 0 votes
The probability depends on your generative model for words. Usually it is assumed that there is a probability distribution $p\_1$ over the alphabet and another one $p\_2$ over pairs of symbols, and the probability of a word is $$ \Pr\[w\_1\ldots w\_n\] = p\_1(w\_1) \prod\_{i=2}^n p\_2(w\_i|w\_{i-1}) = p\_1(w\_1) \prod\_{i=2}^n \frac{p\_2(w\_{i-1}, w\_i)}{\sum\_\sigma p\_2(w\_{i-1},\sigma)}. $$ You estimate the unknown probabilities $p\_1,p\_2$ using unigram and bigram counts. The obvious way would be to estimate $p\_1(\sigma) = N\_\sigma/N$, where $N$ is the number of occurrences of $\sigma$, and $N = \sum\_\sigma N\_\sigma$. However, this assigns probability zero for symbols not occurring, so usually $p\_1$ is slightly mixed with a uniform distribution. The distribution $p\_2$ is estimated in a similar way.

Assuming this generative model, and that there is no mixing, the probability of your word is estimated to be $0$, since (for example) $ab$ never appears in the training data.

---
Tags: formal-languages, probability-theory
---


# Question
Title: Is there a non-recursive and uncountable language L?
Does there exist a non-recursive language, L, such that the cardinality of L is uncountable?

I would really like an explanation as to why this question is true or false because at the moment, I have no idea. My understanding is that all recursive languages have to be countable since the set of all finite strings is countable. But I'm not sure if there is a non-recursive language which is uncountable. Any help would be greatly appreciated,

# Answer
> 7 votes
Definition: a *word* over an alphabet $A$ is a finite sequence of elements of $A$.
Definition: a *language* over an alphabet $A$ is a set of words over $A$.

With these definitions, if $A$ is a finite set, then any language is countable (either finite, or countably infinite). This is because any language is a subset of the complete language $A^\*$ (set of words over $A$).

Direct proof sketch: you can enumerate all the words in the language, in order of increasing length (and in lexicographic order for each given length, having defined an order of $A$). This process is well-defined because set of words of a given length is finite. This process assigns an index to all the words in the language because all words have a finite length.

Follow-up exercise: if $A$ is countably infinite then a language over $A$ is countable. Adapt the proof above (change the enumeration order to cover the whole language in finite batches).

# Answer
> 2 votes
Per your comment, you say a language is a collection of words of finite length. So you can encode each word as a natural number (for example interpret is as an integer in base size-of-your-alphabet). As you've just assigned a number to each element of your set, your set is countable.

---
Tags: formal-languages, uncountability
---


# Question
Title: Express semantic duplicates of records formally
I'm working on a paper about record linkage and duplicate detection and want to visualize my definitions of "hard" and "semantic" duplicates. Hard ones are a 100% match; where's only true or false- Semantic ones have different variations but still are representing the same thing.

Now I'd like to write it as a set but actually I have forgotten all about this.

Here are my thoughts about it. All 4 records are part of the Set **"Persons" p**

For both: Values are already filtered according to custom settings.
**Hard Duplicates**

> {\[Name\]Max; \[Surname\] Mustermann} ≙
>
> {\[Name\]Max; \[Surname\] Mustermann} ≠
>
> {\[Surname\]Max; \[Name\] Mustermann} ≠
>
> {\[Name\]Max; \[Surname\] M.}

**Semantic Duplicates**

> {\[Name\]Max; \[Surname\] Mustermann}
>
> {\[Name\]Max; \[Surname\] Mustermann} ≙
>
> {\[Surname\]Max; \[Name\] Mustermann ≙
>
> {\[Name\]Max; \[Surname\] M.} ≙

Any help is appreciated

# Answer
> 3 votes
The basic mathematical concept at play here is a binary relation. For a certain measure of similarity, two records are either similar or not. Formally, a binary relation assigns a truth value (true or false) to every ordered pair of records. The usual notation to state that two records are similar is $r\_1 \approx r\_2$ where $\approx$ is the notion of similarity. There can be multiple notions of similarity (allowing for more or fewer differences between records).

Given the intended purpose, any notion of similarity should be *reflexive*: a record is similar to itself. Any notion of similarity should probably be *symmetric*: if $r\_1$ is similar to $r\_2$ (for a given notion of similarity) then $r\_2$ is similar to $r\_1$ for that same notion of similarity. It's less clear whether the similarity relation should be *transitive*, which would make it an *equivalence relation*. If $r\_1$ is similar to $r\_2$ and $r\_2$ is similar to $r\_3$, does that make $r\_1$ similar to $r\_3$? Or in other words, is a duplicate of a duplicate a duplicate? If your intuition of similarity is that the records are at most a certain distance from each other, then no (this thread on Math.SE discusses this intuition). But if you think of all records falling into a well-defined bucket, with sufficiently similar records ending up in the same bucket, then you have an equivalence relation, and the buckets are called *equivalence classes*. If you have a way of defining a privileged element in each equivalent class (a “completed” or “presentation” version of the record), that's called a *canonical representation*.

*Equality* is the finest (i.e. most discriminating) equivalence. It is normally written $=$. A generic equivalence relations is typically written $\equiv$. If you need to consider more than one equivalence relation, then the typical notation scheme is to use $=$ or $\equiv$ with some ornaments on it.

The terminology “hard duplicate” or “soft duplicate” isn't standard, but it's comprehensible. “Equal” vs. “equivalent” or “equal” vs. “similar” are more standard terms.

To define an equivalence, a typical approach is to give rules: “if $r\_1$ and $r\_2$ are such that … then the two records are equivalent”. For example, you might have a rule that if two records are the same except for letter case variations on the name field then they're equivalent. Two records are equivalent if there's a way to find a chain using those rules plus the “built-in” reflexivity, symmetry and transitivity rules from one record to the other.

To define a non-transitive similarity, a typical approach is to define a distance between records.

The general problem of determining when records in a database should be treated as representing the same entity is called data normalization. With respect to database design, that's database normalization.

---
Tags: sets, notation
---


# Question
Title: GATE CS 2009, question 11, does the grammar produce odd-length palindromes?
This is question 11 from GATE CS 2009.

Find the language generated by the following grammar over the input alphabet = $\\{a,b\\}$.

$S \to aSa \mid bSb \mid a \mid b $

The language generated by the above grammar over the alphabet {a,b} is the set of
(A) All palindromes
(B) All odd length palindromes.
(C) Strings that begin and end with the same symbol
(D) All even length palindromes
the ans is b. i want to know the language for the grammar

# Answer
> 2 votes
> $$S \to aSa \mid bSb \mid a \mid b$$

**Hints:**

(A) All palindromes

* Can you generate the string $abba$ from the languege?

(B) All odd length palindromes.

(C) Strings that begin and end with the same symbol

* Can you generate the string $ababaa$ from the languege?

(D) All even length palindromes.

* Same hint as in (A)

Just add one more production to this grammar i.e S-\>^(Epsilon) and this grammar works

# Answer
> 0 votes
* Two cases:

1. Both B and C are appropriate, but since B is a more specific answer, B is correct.
    2. In case of S-\>a or S-\>b, there is only a begin symbol and no end symbol. Correct me if I am wrong.

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


# Question
Title: Is it possible that the halting problem is solvable for all input except the machine's code?
This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help.

Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself? Basically:

```
Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

```

This seemingly resolves the contradiction. When we call the paradoxical Halts'(Halts'), we can't expect consistent behavior, but all other calls to Halts (and Halts') are legitimate and solvable.

I understand that this is highly unintuitive. If some pattern in the bits could reveal the behavior of all possible programs, why would it suddenly fall apart when the TM and input match? But can we mathematically eliminate this as a possibility?

And this reduced halting problem would not be uninteresting at all. Even if there were some meaningful program that took its own code as input it could trivially be rewritten to work on slightly different input. Of course this suggestion makes it even less understandable why a halting solution could exist with this one caveat but again, can we really mathematically eliminate this possibility?

Thanks for any help.

# Answer
But we can easily get round your restriction. Suppose a program $G$ that reverses the bits of the input and calls your $H'$ on the result, then define $!H$ with all bits reversed (i.e. 0 for 1s, 1s for 0s). Then we can call your $H'$ with $G(!H)$ and we're back to the original problem.
> 4 votes

# Answer
Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ uses $H$ to determine if $M(\langle M\rangle)$ halts and, if so, $Q$ loops; otherwise, $Q$ halts. Now, $Q(\langle Q\rangle)$ halts if, and only if, it doesn't halt.

> Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself?

No. If you change the definition of the halting problem in this way, the proof still works. We don't care what happens when $H$ receives $\langle H\rangle$ as input because the contradiction comes after we give input $\langle Q\rangle, \langle Q\rangle$ to $H$.

Second, if you modified $H$ to detect *that* input, we could get the same contradiction by using any other machine $Q'$ that is equivalent to $Q$ in the sense that, for any input $w$, $Q'(w)$ halts if, and only if, $Q(w)$ halts. There are infinitely many of these and $H$ can't detect all of them because it's undecidable whether two Turing machines are equivalent.
> 14 votes

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Why do we have different algorithm for MST when graphs are directed?
What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not covered in using Prim's algo for finding MST for directed input?

# Answer
> 13 votes
Your question was already asked before it seems, but got no explicit examples. I try to give these here.

First note the question only makes sense if we consider a node $u$, and there exist spanning trees starting with $u$. The algorithms of Prim and Kruskal make choices in a greedy way. Once the choice is made, it will not be reconsidered. We show how this choice will go wrong for certain example.

The left picture has two spanning trees, with weight $6+2$ and weight $6+4$. Starting with node $u$ Prim will consider the two edges $4$ and $6$ and choose the lightest one. Now, only one spanning tree remains, not the best one.

The right picture has three spanning trees, with weight $4+2$, weight $6+1$, and weight $6+4$. Kruskal will choose the lightest edge $1$. Now, only one spanning tree remains, not the best one.

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


# Question
Title: Turing Machines: decidability and bounds checking
I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w.

I'm assuming I construct a TM which shifts the input on the tape on cell to the left, write the cell at the right-hand end with a new symbol (like "!") that's not in the alphabet for input w. Then add a transition for the head to move left on e cell on reading the extra symbol?

Thoughts?

# Answer
I can construct a machine $D$ which on input $\langle M,w\rangle$ tells if $M$ moves its head past the right end on input $w$, $D$ accepts if the head does not move past the right end of input, and rejects otherwise. As configurations of length $|w|$ are finite if $M$ ever enters same configuration of length $ \le |w|$ accept. Or if it does not repeat such configuration at some point $M$'s head will move past $|w|$ tape cells. So yes your problem is decidable.
> 4 votes

---
Tags: turing-machines, strings
---


# Question
Title: How did 'Isabelle' (the theorem prover) get its name?
The title says it all, but I'm curious because it isn't obvious how a theorem prover came to be named 'Isabelle'. Was it named for a person? I couldn't find out by some Google searches.

# Answer
A little google-fu (and my own memory) tells me it was apparently named by Larry Paulson after Gerard Huet's daughter.

Gerard Huet happens to be one of the people behind the less poetically named Coq theorem prover.

Small world!
> 10 votes

---
Tags: history, automated-theorem-proving, isabelle
---


# Question
Title: Removing $\epsilon$ transitions in a NPDA
NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions.

However, NFA's with $\epsilon$ transitions could be converted to those without any $\epsilon$ transitions and hence they can be made to halt.

I was wondering if this is possible even for the case of NPDA's.

Is there a canonical epsilon-free form for PDAs

# Answer
This effect I would not consider this a "halting problem" but there is a point here. A pushdown automaton can end its computation in an unbounded sequence of $\varepsilon$-moves. This behaviour can be avoided for general PDA, indeed. For each PDA there is an equivalent PDA without $\varepsilon$-moves. This is equivalent to Greibach Normal Form for grammars.

For deterministic PDA, DPDA, the situation is different. We would like to avoid this unbounded behaviour, in particular for the construction of the complement of the language of the DPDA. As you might know DPDA are closed under complement. Quite involved constructions can avoid infinite computations, but we cannot avoid $\varepsilon$-moves.

The language $\\{ a^mb^nc^n \mid m,n\ge 1\\} \cup \\{ a^mb^nd^m \mid m,n\ge 1\\}$ can be accepted by a DPDA but it has to use $\varepsilon$-moves.
> 5 votes

---
Tags: finite-automata, pushdown-automata, nondeterminism, halting-problem
---


# Question
Title: Two definitions of universal hash functions
I have seen two definitions of universal hash functions in the literature.

For any $i \geqslant 2$ let $\[i\]=\\{1,\ldots,i\\}$.

Definition 1:

> A family $\mathcal H$ of hash functions from $\[n\]$ to $\[m\]$ is a *$k$-universal family of hash functions* if for any distinct $x\_1,\ldots,x\_k\in\[n\]$ and any possibly identical $v\_1,\ldots,v\_k\in\[m\]$, $$ \Pr\limits\_{h\in\mathcal H} \[h(x\_1)=v\_1\wedge \cdots \wedge h(x\_k) = v\_k\] \leqslant 1/m^k \enspace . $$

Definition 2:

> A family $\mathcal H$ of hash functions from $\[n\]$ to $\[m\]$ is a *$k$-universal family of hash functions* if for any distinct $x\_1,\ldots,x\_k\in\[n\]$, $$ \Pr\limits\_{h\in\mathcal H} \[h(x\_1)=\cdots=h(x\_k) \] \leqslant 1/m^{k-1} \enspace . $$

In both definitions if equality holds then it is called strongly $k$-universal or alternatively $k$-wise independent hash family.

Clearly the first definition implies the second. But is the other direction true?

It is easy to see that this is not the case for $n\leqslant m$.

> This is a counter example when $\[n\]\subseteq \[m\]$:
>
> Consider the family $\mathcal H$ composed of only one element, the identity function: $x \mapsto x$. It satisfies the second definition since for all $x \neq y \in \[n\], \Pr\_{h\in\mathcal H} \[h(x) = h(y)\] = 0 \leqslant 1/m^{k-1}$. However, it does not satisfy the first definition since for all $x,y\in\[n\], \Pr\_{h\in\mathcal H}\[h(x) = x \wedge h(y) = y\] = 1 \> 1/m^k$.
>
> This answer is inspired by this other answer.

However, hash functions are usually employed in applications where $n\>m$. So my question is whether this is also the case for $n\>m$.

# Answer
> 4 votes
The two definitions are not equivalent. The second definition does not imply the first. You can take $\mathcal{H}$ to be the collection of all functions $h$ such that $h(1) = 1$.

---
Tags: probability-theory, hash, hashing
---


# Question
Title: Showing that an algorithm is 2-approximation
I'm having trouble showing that this algorithm is 2-approx.

> We are given a set P of n points on the plane, and a positive integer k. We want to partition these points into k sets such that the largest distance between any two points which belong to the same part is minimized. Show that the following is a 2-factor approximation algorithm.
>
> Set S = ∅.
>
> For i = 1, . . . , k do
>
> Select the farthest point from S and add it to S.
>
> EndFor
>
> Put each point p ∈ P in the same part as the closest point in S to p.

I honestly don't know where to start. I can see that after each iteration, the distance between any point in P and the points in S become smaller. But after that I can't really see any good observations.

# Answer
The place to start is at the simplest case: $k = 2$. Suppose that the points in $S$ are $x,y$. Consider some optimal solution of value $1$. We consider two cases.

* $x,y$ belong to the same cluster. Thus $d(x,y) \leq 1$. Since $y$ is the farthest point from $x$, all other points are at distance at most $1$ from $x$, and in particular at distance at most $1$ from $\\{x,y\\}$. This means that in the clusters generated by the algorithm, each point is at distance at most $1$ from its base (either $x$ or $y$), and so the diameter of each cluster is at most $2$.
* $x,y$ belong to different clusters. In this case, since the optimal solution has value $1$, each point other than $x,y$ is within distance $1$ of either $x$ or $y$ (the one which shares cluster with it). This means that in the clusters generated by the algorithm, each point is at distance at most $1$ from its base, and so again the diameter of each cluster is at most $2$.

See if you can generalize these ideas for $k \> 2$.
> 3 votes

---
Tags: algorithm-analysis, approximation
---


# Question
Title: About the interpretation of the SOS hardness results of the planted Max-Clique problem
One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then *both* these papers are talking of the planted-Max-Clique problem and the second one is improving the detection threshold from $n^{1/3}$ in the first paper to $n^{1/2}$.

* Does any of these results imply or do they implicitly contain the hardness threshold for say just the Max-Clique problem w.r.t even just the degree-4 SOS?

Or are both these results totally specific to the planted problem and say nothing about the Max-Clique?

---

If I say look at the corollary 2.1 (bottom of page 10) in http://arxiv.org/pdf/1502.06590v1.pdf then this seems to be a hardness threshold for just the Max-Clique problem but I am not feeling very sure since the authors never put in these same words. Am I missing something? The same can be said about Theorem 1.1 (page 2) in the second paper.

If one sees the section 2.4 in the second paper, where they construct the SDP witness it feels that their construction would make sense only in the "planted" setting and then contrary to my feeling from theorem 1.1 now I start feeling that the result applies only with planting.

# Answer
> 2 votes
The planted clique problem and the maximum clique problem are different problems, though the former was introduced as an average case version of the latter. A paper addressing the planted clique problem doesn't address the maximum clique problem, and vice versa.

In particular, the papers you mention concern the planted clique problem, not the maximum clique problem.

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


# Question
Title: Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2
I stumbled upon the following problem during my research.

I have a bipartite graph, and I want to determine the minimum number of edges to to remove so that the maximum path length in the resulting graph is 2.

Is this problem NP-hard? I was trying to come up with a polynomial time algorithm (and failed) and also tried to prove its NP-hardness, but also having a hard time.

# Answer
> 2 votes
Figured out this is indeed NP-hard. This is equivalent to finding the maximum spanning star forest in a bipartite graph, which in turn is as hard as finding the minimum dominating set in a bipartite graph, which is NP-hard.

---
Tags: graphs, np-hard
---


# Question
Title: Reconstructing a screen of permuted pixels
## **Reconstructing a screen of permuted pixels**

### Summary

Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture?

Let:

* $n=w\times h$ pixels.
* $m=\text{number of frames}$

### Details

* You are given an LCD screen with $n = w \times h$ pixels, that has been altered so that the pixel locations are permuted, *once*, in some random manner.
* Watching a video on this LCD screen would obviously result in quite a garbled picture.
* The permutation is mapped by some unknown function, we shall call $\text{permute}\left(x\_0,y\_0\right) \implies (x,y)$
* Each pixel on the screen has some permuted coordinate $(x,y)$ and some unknown original coordinate $(x\_0,y\_0)$ (such that $\text{permute}\left(x\_0,y\_0\right)=(x,y)$).
* You (and your computer) are given to watch a particular video of an average film (movie) of average length, with $m$ frames, and having the same resolution as the LCD screen; however for simplicity, assume the video will be in grayscale (for example, each pixel is a single color in the range $\[0,256)$).
* You do not know *\*which\** film is being played.
* You (and your computer) can rewatch the garbled film as many times as you like.
* As a frame of reference, you are also informed which pixel is the lowest location in the original non-permuted screen (i.e you are given the values $x$ and $y$, such that $(x\_0,y\_0) =(0,0)$, and $\text{permute}\left(0,0\right)=(x,y)$).

### Goal

* Algorithm to (efficiently) compute the mapping of the pixels to their original locations.
* Can this be done in $o\left(n^2\right)$ space (i.e in better than $\mathcal O\left(n^2\right)$ space?)
* Can this be done in $o\left(n^2f(m)\right)$ time?
    + I'm not sure how to ask this question correctly, but I am mostly wondering about reducing the $n^2$ factor.
* Is this a known problem, or similar to any known problems?

**PS.** What about same question but for the case of ***binary images*** for each frame instead of grayscale.

### Appendix

**Figure 1** Example permuted "LCD screen", side view

**Figure 2** Example permuted "LCD screen", front view

**Figure 3** Example video frame (color)

**Figure 4** Example permuted video frame (color)

**Figure 5** Example video frame (grayscale)

**Figure 6** Example permuted video frame (grayscale)

**Figure 7** Example video frame (binary, using most-significant-bitplane)

**Figure 8** Example permuted video frame (binary)

### Related source codes are on gist.github.com

### Credits:

# Answer
> 3 votes
One approach is to exploit fact that if two pixels are adjacent, then their intensities will be highly correlated: the intensity of the first pixel (as a time series) will be highly correlated to the intensity of the second pixel (as a time series).

In other words, let $I(p,t)$ denote the intensity of pixel $p$ at time $t$. Then you can compute a correlation coefficient between $p,q$ as

$$C(p,q) = \sum\_t I(p,t) I(q,t).$$

(Detail: you probably actually want to use the normalized correlation coefficient, as explained at bottom.)

For each pair of pixels $p,q$, compute $C(p,q)$, the correlation between these two pixels.

Next, for each pixel $p$, you could identify the four other pixels $p\_1,\dots,p\_4$ that have the highest correlation to $p$ (i.e., that maximize $C(p,p\_i)$). A reasonable heuristic would be to assume that those are the four neighbors of $p$. Do this for every pixel.

Now you have a pretty good guess at which pairs of pixels are adjacent. At this point, you several options. One approach would be to pick a random pixel, then start trying to expand outward from there: find its four neighbors, then find their neighbors, and so on.

At each step you will need to decide how to orient the neighbors. Here a plausible heuristic might be: the distance between two pixels $p,q$ in the original image is likely to be related to the correlation $C(p,q)$: larger $C(p,q)$ is associated with pixels that are further apart. Thus, given a pixel $p$ and its four neighbors $p\_1,p\_2,p\_3,p\_4$, I expect you can tell which pairs of those neighbors are on opposite sides of $p$ vs which pairs are kitty-corner to each other (as opposite pixels are at distance 2 apart while kitty-corner pixels are at distance 2). You probably won't be able to tell which is up and which is right, so just make an arbitrary guess; later you can have a human tell you whether the picture appears to be reflected.

So now suppose that you've mapped some pixels to their original locations, and you want to add one more to the set. You can get at most three candidates for what it might be, then use the distance heuristic to form a guess about which of the three this is.

Continue this process until you've mapped out a guess at how to reconstruct a large patch of the original image. Now have a human look at the unpermuted video (unscrambled using your guess at the mapping for those pixels). If you're lucky, most of that will be correct. A human should be able to tell you whether this looks correct, and identify the region that appears to be correct.

So, you have a process that given a starting pixel, finds a region surrounding it that appears to have been correctly unscrambled. Repeat from multiple starting pixels until you have a large collection of such regions. Now fitting those regions together is basically just a jigsaw puzzle, so should be solvable.

I would expect that the longer the image is, the more effective this will be -- the fewer mistakes this approach will make, and the larger these regions will be and the easier the jigsaw reconstruction process will be.

But the only way to find out for sure is to test this. Ultimately, this is probably not a question that can be answered by proving a theorem, as the effectiveness of the technique depends on empirical facts about the properties of typical videos.

---

Footnote: In computer vision applications, it is usually more effective to use the normalized correlation coefficient (NCC). So, I recommend that you use NCC for this. The NCC is essentially

$$C(p,q) = \sum\_t {(I(p,t) - \mu(p)) (I(q,t) - \mu(q) \over \sigma(p) \sigma(q)},$$

where

$$\begin{align\*} \mu(p) &= {1 \over m} \sum\_t I(p,t)\\ \sigma(p) &= {1 \over m-1} \sum\_t (I(p,t) - \mu(p))^2 \end{align\*}$$

---

What's the running time of this approach? The most expensive part is to compute the correlation between every pair of pixels. Naively, this takes $O(n^2 m)$ time.

However, if computation time is at a premium, it might be possible to speed that up using locality-sensitive hashing or K-D trees to find pairs of pixels for which $C(p,q)$ is larger than some threshold.

---

If you're looking for research literature on this problem, I would look into video descrambling. Some video scrambling methods (e.g., for copy protection or cheap video "encryption") permute the pixels, basically along the lines you outlined. I think there might be work in the research literature on descrambling such videos; a literature search might turn up something useful.

---
Tags: algorithms, reference-request, probability-theory, image-processing, information-theory
---


# Question
Title: Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?
At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure have computed shortest paths with $k$ length. However, the part that I don't quite understand is why not only relaxing the edges that are directly connected to the source on the first iteration and then the neighbors' edges of those on the second iteration, and then the neighbouring eges of those and so forth?

The idea, is a similar algorithm to BFS I guess. We start from the frontier of edges relaxed and we make sure that we are connected to a node that we have computed its shortest path and since we are always relaxing edges that are connected like that, then we compute the shortest path in 1 pass rather than $O(EV)$ passes. I am sure I am wrong but I don't understand why. Of course it works in a straight line graph, but what type of worst-case input does it make that we need about at least $\Omega(EV)$?

I am mostly interested to understand, is the EV runtime in the **worst case**. I also do not care about improvements in practice or constant factors. Only asymptotics.

# Answer
> 3 votes
This would work, with a minor modification. In other words, the resulting algorithm would be correct: it would correctly compute distances.

However, it doesn't help much. It doesn't change the asymptotic running time of the algorithm. In many graphs, after about $O(\lg n)$ iterations, essentially every vertex is reachable from the starting point. Therefore, you might save a little bit on the first $O(\lg n)$ iterations, but after that, you still have to relax all edges. Thus, this makes only a minor improvement -- far too small to show up in the asymptotic running time. And, in practice, on most graphs, the improvement will probably be small -- perhaps so small as to be outweighed by the extra bookkeeping required.

Finally, this makes the algorithm more complicated. From a pedagogical perspective, when the purpose is to teach algorithms, unnecessary complications are best avoided, as they just make it harder to understand an already-challenging subject.

The minor modification you need to make is: in the $k$th iteration, relax all edges $(u,v)$ where $u$ is *at most* $k$ edges from the source \[rather than where $u$ is exactly $k$ edges away from the source\]. This is important, because the shortest path from $s$ to $u$ (the one where the sum of the distances on the edges in the path) need not be the same as the path from $s$ to $u$ with the fewest edges.

---
Tags: algorithms, graphs, shortest-path, dynamic-programming, weighted-graphs
---


title: Axioms - proof of halt

text:
# Question
Title: Axioms - proof of halt
I am new to this forum and this is my first post. I am interested in solving a problem, but cannot find the way to think about it. If anyone can guide me through it, I would be obliged:

Let F be some system of axioms. You can assume F is sound (that is, it only proves true statements), and also that F is strong enough for Godel's Incompleteness Theorem to apply to it. Let G ( F ) be the mathematical encoding of "This sentence is not provable in F ." Also, let MF be a Turing machine that generates all possible F -proofs, one by one, and that halts if and only if it encounters a proof of G ( F ).

a) Does MF halt? Why or why not?

b) Is there a proof in F that MF halts, or a proof in F that MF does not halt? Why or why not?

# Answer
> 1 votes
Let $CON(F)$ denote the sentence: "F is consistent".

You can prove $CON(F)\rightarrow \text{ MF does not halt}$, since if MF halts you have $F\vdash G(F)$ and thus by soundness $F\not\vdash G(F)$.

You cannot however, prove this unconditionally (unless your system is inconsistent), since this would mean $F\not\vdash G(F)$ which implies consistency (why?).

---
Tags: computability, logic, halting-problem, incompleteness
---


title: Short certificate analogy of PH?

text:
# Question
Title: Short certificate analogy of PH?
We know that for problems in NP if the problem is an yes version then there is a short certificate and for coNP if the problem is a no version then there is a short certificate.

Is there a short certficate analogy for higher levels in Polynomial Hierarchy?

# Answer
> 3 votes
The correct analogy for higher levels of the polynomial hierarchy is that of a *game* between two players, the $\exists$ player and the $\forall$ player. The $\exists$ player wants to prove that the input is in the language, and the $\forall$ player wants to disprove it.

For a language $L \in \Sigma\_k^P$, the game is as follows. On input $x$, the $\exists$ and $\forall$ players alternate in presenting strings $y\_1,y\_2,\ldots,y\_k$ (the $\exists$ player starts). After $k$ rounds, the referee runs a polynomial time procedure $f$ (set in advance) on $x,y\_1,\ldots,y\_k$, and declares $\exists$ to be the winner if $f$ returns YES, and $\forall$ to be the winner if $f$ returns NO. Since $L \in \Sigma\_k^P$, when $x \in L$, $\exists$ has a winning strategy, and when $x \notin L$, $\forall$ has a winning strategy.

For a language $L \in \Pi\_k^P$, the only difference is that $\forall$ starts.

When $k = 1$, there is no communication, and so we can talk in terms of witnesses. For larger $k$, we can still use the witness terminology, but with different semantics. Consider again $\Sigma\_k^P$, for $k = 2r$ or $k = 2r+1$. The witness of $\exists$ consists of $r$ functions $Y\_1,Y\_2,\ldots,Y\_r$ which are used to generate the strings produced by $\exists$ as follows: $y\_1 = Y\_1(x)$; $y\_3 = Y\_2(x,y\_1,y\_2)$ (or $y\_3 = Y\_2(x,y\_2)$, since $y\_1$ is known); and so on. You can think of these functions as implicit witnesses, since $\exists$ doesn't reveal the entire functions $Y\_2,\ldots,Y\_r$, but only the relevant values.

For $x \in L$, the property that these witnesses satisfy is that for any reply by the $\forall$ player, the referee declares $\exists$ to be the winner. For $x \notin L$, the $\forall$ player has a similar kind of witness. Thus "witness" here is really the same as a winning strategy.

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


# Question
Title: Why do we study closure properties of formal languages?
In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is important to study such properties?

# Answer
> 7 votes
I think that the more fundamental question here is why study specific kinds of formal languages at all. One answer is that formal languages of specific kinds have been found useful in the construction of compilers. Another answer is that in the past they played an important part in artificial intelligence (nowadays statistical methods are more important).

Once we agree that regular languages and context-free languages are an interesting object of study, closure properties are basic mathematical properties of these objects. In fact, part of the beauty and appeal of the subject of regular languages is the large number of properties that they satisfy, including closure properties. Regular languages serve as a model for other families of languages, and one tries to mimic one's knowledge of regular languages on other families of languages.

Closure properties are also interesting beyond formal languages — Tychonoff's theorem in topology is one example.

Specific closure properties of regular languages have given rise to a new type of algebraic structure, Kleene algebras, which abstract some of the closure properties of regular languages and of context-free languages.

---
Tags: formal-languages, automata, closure-properties
---


title: Prove n! is fully time constructible

text:
# Question
Title: Prove n! is fully time constructible
We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) Turing machine that for $n$ given, halts after exactly $f(n)$ steps, and just asked if we could now prove that $n!$ is fully time constructible (and moved on).

I am not sure how the proof goes, but I am thinking it has to use $n^k$ time constructability to some extent, or some identity involving factorials, since we showed $n^k$ is (fully) time constructible using $n^k = n + \sum\_{i=1}^{i=k-1}(n - 1)n^i$.

Hints would be appreciated too, really. Thanks in advance.

# Answer
> 1 votes
Let us assume we have find $n!$ on input $n$. Our complexity is terms of length of the input ( we assume it to be $L=O(logn)$ ). Multiplication of a $k$ bit by $l$ bit number via standard multiplication takes $O(kl)$ operations ( also after multiplication number of bits in the resultant if $O(k+l)$ ) . We multiply linearly in a loop from $1$ to $n$ to get $n!$. So number of operations carried out are upper bounded by $\\# = L^2 ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Thus it is space and time constructible.

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


title: PSPACE and DTIME $2^{cn}$

text:
# Question
Title: PSPACE and DTIME $2^{cn}$
This is a HW question that I'm stuck on and was hoping for some help. we're supposed to prove that:

> PSPACE not equals DTIME($2^{cn}$) for every $c\>0$ (or actually for the union of all $c\>0$)

# Answer
This can be proved by contradiction. You can use the fact that $PSPACE$ language remains $PSPACE$ if we remove polynomial length padding, where as $DTIME$ does not.
> 1 votes

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


title: Typical file structure

text:
# Question
Title: Typical file structure
# Short version

The question & answers relate to the following topics:

* File as a collection of records vs. file as a stream of bytes
* Sequential File
* Distinction between file data and metadata
* Transfer of metadata along with the file
* File size measurement

# Original question

According to William Stallings' `Operating Systems`, the most common structure for a file is the `sequential file`, which consists of a collection of records. All files have the same amount of records and each record has a predetermined length. This seems very inefficient and doesn't match my previous understanding of files at all.

For example: if I have a JPG file, it would have records indicating things like resolution, creation date, etc. Some record fields would not be relevant for a JPG file and would be empty, but space would be reserved for those fields regardless. Since the actual data of the JPG file would be too large for any record, there would be an "overflow pointer" to where the data actually is.

Stallings also presents an alternative to file-as-a-collection-of-records: file as a stream of bytes. While the book claims it's rare, it is more in line with my understanding of files: a file is just raw data with no universal structure. However, if I move a file from one computer to another, things like "creation date" move along with it, indicating that files have some attributes which are saved within the file (as opposed to in the file management system). If all files have some header information like creation date, and that information is saved within the file, why is it that my Ubuntu claims an empty text file takes 0 bytes space?

I'm guessing that a typical file is simply a stream of bytes with no predetermined structure and that header information like the creation date is somehow transferred along with the file when it is moved. I'm guessing that the chapter about sequential files in the book is some kind of remnant from the 80's. Please correct any misconceptions that I have.

# Answer
> 2 votes
I've never heard of sequential files, but apparently the term can mean two things:

* Data which can only be accessed sequentially, for example the contents of a backup tape.
* Record-based files (what Stallings refers to). Apparently this is still used in databases (see for example this COBOL page), but not on your desktop.

File names and other metadata such as the creation date is stored as part of the filesystem. An empty file doesn't really "waste" only zero bytes, since the metadata is stored somewhere. When you move data from filesystem to filesystem, an attempt will be made to copy the metadata, but how successful this attempt is depends on the filesystem. For example, when moving a file from one server to another, the user and group attributes may be lost, since a given user or group can exist on one server but not the other one.

# Answer
> 7 votes
First, let me state that you may have things to unlearn. Files that are a stream of bytes are very much the rule, and have been for a long time. Almost all filesystems store a sequence of bytes, and leave the interpretation of that sequence of bytes up to applications or at least to higher-level libraries. Sequential files, consisting of a sequence (typically of variable length) of fixed-size records, went out of fashion in the 1980s if not in the 1970s. They still exist in big iron¹ (running VMS or “bigger” systems such as IBM mainframe OSes), but most programmers can go through their whole career without seeing one of those. Any book teaching sequential files as common is good only to teach operating system history, not operating systems.

Unix sees all files as byte streams. Simplifying operating system interfaces was one of Unix's major contributions, and that one stuck. Windows also sees all files as byte streams. Between them, that's essentially the whole server ecosystem, the whole workstation ecosystem, the whole mobile ecosystem², and a large chunk of the embedded ecosystem. Small embedded operating systems may have structured files, but if so I think they're generally files with a fixed structure (a single record, if you like, with set of possible formats imposed by the system) rather than a sequence of records.

In a sequential files, all the record play equivalent roles. There isn't a record for different *kinds* of data, but a record for different elements in a list. You can see an example in the VMS documentation. In modern terms, a sequential file is a table, a record is a row, and tables are stored in databases, not in filesystems. Although filesystems and databases are conceptually related, databases are focused on data with structure (and relations between data elements), while filesystems are focused on independent files. These approaches have different desirable security and stability guarantees, different interfaces, different performance goals, etc.

Things like the creation date³, the access permissions, etc. are generically called metadata. They are also stored in the filesystem, but outside the file's main data area. Operating systems generally report only the size of the “main” data when they report a file's size: the size isn't how much space the file occupies on the disk, but how much data is in the file. Accounting for disk usage completely accurately is rather complex — have a look at this, and keep in mind that this is only on one specific operating system.

A basic way to store files is to have every directory entry be a fixed-size structure containing the file name, other end-user metadata (timestamps, ownership information, access permissions, etc.), and some internal metadata that lets the operating system know where on the disk the file data is. A common extension to this approach is to create a level of indirection, where each directory entry contains just the file name and a pointer to another location (called an inode in the Unix world) containing the rest of the metadata.

The technical term for having multiple parts in a file with different roles (the data, the access control list, the timestamps, etc.) is a *fork* or *stream* (beware that both of these words also have different meanings). Many filesystems support only a single stream per file (the data stream), plus some fixed-size metadata. The metadata can be viewed as a stream from a conceptual point of view, but there's often no way to access it as a stream of bytes, only through dedicated functions. Some examples of uses of alternate streams are the resource fork on Mac OS, and extended (variable-size) security attributes on Linux.

The reason many file copy tools copy metadata together with the file content is that they're programmed to do so, i.e. rather than “open existing file, create new file, read data from existing file, write data to new file”, the copy algorithm also includes steps such as “read existing file's permissions, set new file's permissions to those, read existing file's timestamp, set new file's timestamp to that”.

¹ <sub> Mainframes — or mainframes emulated on x86 hardware, but running a 20-year-old emulator in which a 40-year-old operating system is running a 50-year-old application written in COBOL that nobody dares touch! </sub>
² <sub> Maybe add Symbian — where files are byte streams too. </sub>

# Answer
> 1 votes
A little bit different view here. What a file is, is very loosely defined. There are several levels at which files mean different things.

1. Inside file-system. From file-system perspective files can be wildly different things. For example, SunRPC Networking File System (a.k.a. NFS) sees files as messages sent on network, which have some representation on server and clients. OverlayFS (file-system used in Docker containers) sees files as collections of layers made of some read-only and some writable streams. File-system understanding of files may differ based on what storage is used (if at all), whether deduplication, compression or some other common techniques are used and so on. Not to mention physical location of data describing the files.
2. In operating system kernel files must receive their properties, which kernel then exposes to user-space programs. Kernel functions may present same files differently to different user-space programs, depending on access permissions for example.
3. User-space programs will often create their own presentation of files. It is customary to associate icons with files, or information such as what program is registered to deal with files.

So, depending on your view of what a file is, you will get different answers as to what its size or metadata are.

---
Tags: filesystems
---


# Question
Title: PDA for all non-palindromic strings of even length
I had a homework assignment where I had to build a PDA over the alphabet $\\{a,b\\}^\*$, accepting $L = \\{x \mid x \text{ is even but not a palindrome}\\}$.

I already turned it in, but I know I had it wrong and it's driving me insane that I can't figure out this construction.

I tried a Cartesian product construction of the following languages and then deselected the accepting states of $L\_2$, but I obviously did it wrong:

$L\_1 = \\{x \mid x \text{ is even}\\}$

$L\_2 = \\{xx^R\\}$, where $x^R$ denotes $x$ reversed.

I kept running into a problem where it would still accept because Palindromes are even and I was basically accepting all even numbers.

# Answer
> 1 votes
The solution is very much similar to PDA for palindromes of even length, except at atleast one place you have mismatched symbols.

---
Tags: finite-automata, pushdown-automata, nondeterminism
---


# Question
Title: Can element uniqueness be solved in deterministic linear time?
Consider the following problem:

*Input*: lists $X,Y$ of integers

*Goal*: determine whether there exists an integer $x$ that is in both lists.

Suppose both lists $X,Y$ are of size $n$. Is there a deterministic, linear-time algorithm for this problem? In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?

Unfortunately, you cannot assume that the list elements are all small.

---

I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable. The expected running time will be $O(n)$. However, I can't see how to find a deterministic algorithm with $O(n)$ running time. If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time. The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time. Can we achieve linear running time?

Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $\[1,n\]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.

If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation. I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.

# Answer
> 1 votes
You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y. This does not impose any restrictions of the ordering of X and Y.

1. Initially all bits are unset.
2. Iterate over X setting the corresponding bit.
3. Iterate over Y checking if the corresponding bit was set above.

# Answer
> 0 votes
Since you are saying that the two lists contain integers, I guess we can run a radix sort on the two lists and then do a linear search comparing the two lists for equivalent items.

# Answer
> 0 votes
Why not insert the integers of each list into a simple bitwise trie? Would this not be optimal, in the sense that it is $\mathcal O\left(n\cdot \overline m\right)$, where $\overline m$ is the average bit size of the integers; specifically, I do not see how you can do better, as simply *\*reading\** the two lists would take this amount of time.

# Answer
> -1 votes
It is similar to the Elemet Uniqueness problem, where you have a set of n numbers and you want to determine whether all of the elements are distinct. The problem has an algebraic computation tree lower bound of $O(n\log n)$.

---
Tags: algorithms, complexity-theory, lower-bounds
---


# Question
Title: What problem is to the set packing problem, as the hitting set problem to the set cover problem?
Wikipedia says that

> Set covering is equivalent to the hitting set problem

What problem is to the set packing problem, as the hitting set problem is to the set cover problem?

Is it that given the ground set $U$, and a collection of its subsets, $S \subseteq \mathcal P(U)$, find a $H \subseteq U$, so that $|H \cap S\_i | \leq 1, \forall S\_i \in S$, and maximize $|H|$.

What is the name of a set $H$ that satisfies $|H \cap S\_i | \leq 1, \forall S\_i \in S$ in this problem? I.e. the counter part of a hitting set in the hitting set problem?

Thanks.

# Answer
Let $E$ be indicator matrix $e\_{ij}=\[u\_j\in S\_i\]$ and $w\geq 0$ be boolean vector. What you have written is $Ew\leq 1$ where $(1,w)$ is being maximized. If we relax this to linear programming and get respective dual $E^tv\geq 1,\\, v\geq 0$ where $(1,v)$ is minimized. Latter problem under constraints $u\in\\{0,1\\}^m$ would be Set Cover problem. To get respective Hitting Set consider new sets $S'\_j=\\{S\_i:u\_j\in S\_i,\\,i=1,\ldots,m\\}$ and new ground set $U'=\\{S\_i:i=1,\ldots,m\\}.$ The Set Cover reduces to Hitting Set for sets $\\{S'\_j\\}$ over ground set $U'.$ So Set Packing and Set Cover are dual in some way. But their optimal values do not coincide but they do coincide for their convex relaxations. More on this topic see e.g. in Wlliamson

You could also consider $H$ as being maximum independent families of sets $S\_i.$ Let $F\_h=\bigcup\limits\_{h\in S\_i}S\_i,\\,h\in H.$ These families are non-intersecting. Set Packing optimum is the lower bound for Set Cover.

As for $H$ interpretation. I suppose $S\_i$ represents class of some useful things to take. Overall utility is maximized while the only one thing can be taken from each class.
> 1 votes

---
Tags: algorithms, optimization
---


# Question
Title: Why closedness of complement of randomized classes imply containment of complement of contained classes?
Suppose if class $\mathcal C$ is in $PP$ or $BPP$ does it mean complement also belongs to $PP$ or $BPP$ respectively? Does it immediately follow from $PP=coPP$?

# Answer
Yes, you should follow the definitions, if $L\in \mathcal{C}\subseteq PP$, then $\overline{L}\in PP$. It immediately follows that $co-\mathcal{C}=\\{L | \overline{L}\in \mathcal{C}\\}\subseteq PP$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Is it admited to give the complexity of a function regarding the resulting data structure?
Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$.

The time complexity of $f$ is $O(n\_{\_{old}})$ = $O(\log\ n\_{\_{new}})$, is it admited to say that $f$ is a $O(\log n)$ function ?

# Answer
The running time of a function is usually measured with respect to the length of the input, which is represented by the parameter $n$. In your case, if the input is the integer $m$ then the input length is $n = \log m$ and the running time is $O(m) = O(2^n)$.

For functions whose output is much larger than the input, it makes sense to measure the complexity with respect to the size of the output. In your case, the function runs in linear time with respect to the size of the output.

In other cases it might be meaningful to use other parameters to measure the running time of a function. For example, functions on graphs are sometimes measured with respect to the number of vertices and the number of edges. The end goal is usually to analyze the running time of some function in terms of its input length, but on the way it is OK to measure the running time of subroutines in terms of other parameters.
> 5 votes

# Answer
No. The input for $f$ is $n\_{\text{old}}$, which, as you mentioned, is stored using $O(\log n\_{\text{old}})$ space. Thus the upper bound $O(n\_{\text{old}})$ on the time complexity of $f$ is actually exponential in the input size, so all you can say is that $f$ is computable in $O(2^n)$.
> 2 votes

---
Tags: complexity-theory, data-structures
---


# Question
Title: Increasing Cache Line and Programs with bad Spatial Locality
I'm reading on caches and I'm feeling a bit lost with spatial locality.

From my understanding, increasing the cache line with a program that has high spatial locality reduces the miss rate.

But for a program that has low spatial locality, does an increase in cache line have any effect on the miss rate?

# Answer
> 1 votes
There will be minimal, to no effect on the miss rate of a program with low spatial locality.

# Answer
> 0 votes
> From my understanding, increasing the cache line with a program that has high spatial locality reduces the miss rate.

This is correct. Think of a dot product of two vectors, both with 16 values. Assume a cache line of 8 words. Now, on the first try, neither of the values from any vector will be in the cache. This will cause two read misses (one per vector) and require the first 8 values of each vector to be loaded into the cache. Now the ALU goes through and multiplies and accumulates 8 words. On trying to read the 9th words, it will incur a miss again (cache line size was 8) and will repeat the process. OTOH, if the line size was 16 words, both vectors in their entirety would have been read in on the first set of misses.

> But for a program that has low spatial locality, does an increase in cache line have any effect on the miss rate?

Now think of two matrices that are 1024x1024 and have to be multiplied up. If you do it the way I was taught in high school, you'd have high spatial locality on the first matrix (since you are reading it row-wise) but **low** spatial locality on the second one (since you have to read the first column). Now, how do the number of read misses incurred because of the low spatial locality of this column-wise read change with a cache line of 8? 16? 32?

---
Tags: memory-management, cpu-cache, memory-hardware
---


# Question
Title: Algorithm for compressing binary data that can efficiently be partially decompressed
So I have been given the following problem and since I have no experience at all in this field, I would really appreciate some advice/guidance.

These are the requirements:

So three times per second a certain amount (fixed per session) of 32-bit values come in. These values have to be stored into a file with a timestamp per data-entry and it must be possible to at any time, with a given timestamp and interval, read out the values that are stored in that file.

This is all relatively simple to do, but this produces a 5GB file every 24 hours. If this file is zipped, it just leaves a 500MB file, so it is compressable but in that case you can't instantly retreive datapoints because you would have to unzip the entire file.

So I was thinking that this could be solved like this:

* Buffer the first 10MB of sensor data.
* Then sort all the values by the amount of times that they contain the same value. (Sensor data, so quite a few of the channels will mostly contain stable values)
* Run an algorithm that detects recurring patterns, replaces those patterns with shorter values and defines a table with the recurring patterns and their replacements.
* The compress the buffer and save it to the disk and compress every new series of sensor data with the pre-defined table.

If this would be implemented properly, it should be possible to uncompress an individual datapoint and the file is sorted by timestamp so finding the right one should be trivial with a binary search.

So I guess the questions I'm having are the follwing

1. Is this at all possible? I do not expect compression results near Zip and 2x - 5x would be enough.
2. What is a good (and if possible semi-easy to implement) algorithm to find patterns in binary data? I have been doing some research and I mostly ran into algorithms that only apply to text data.

Any form of help is greatly appreciated!

# Answer
> 0 votes
Sorry to you guys who posted such a detailed answer, I ended up solving this in a quite simple way.

I ended up just compressing the data points individually and because the entries are quite large (60-600 kb) compression rates up to 12x are possible. (using zlib)

When a new file is created, I reserve the first part of the file to serve as "table of contents". The file starts with a "file-header" that contains the first and last timestamp that can be found in the file and the current amount of data points put in the file. Following that is a long list of equally sized "data-pointers" containing the timestamp and the offset in file. Due to all the reserved space for the headers this initially gives a file of 4MiB even when there is no data in it, but this is quickly negligable by the space saved by the compression. After the "table of contents" is each datapoint in compressed form one after another.

This makes it possible to do a binary search for the right data, and even in a file of several GB's the right data can be found in a matter of milliseconds. I initially set zlib to MAX\_COMPRESSION, but this took up way more time than MAX\_SPEED and just resulted in a minor change in compression rate. And at maximum stress (600KiB entries at 20Hz) it was barely keeping using MAX\_COMPRESSION.

# Answer
> 3 votes
## Eliminate timestamps

If the data is sampled at regular intervals (e.g. three times per second), it is sufficient to store the timestamp of the first point and the interval. This enables you to calulate the offset from a timestamp and vice versa and grants you access to any datapoint in constant time.

## Compression schemes

As others have already laid out, you will always lose the ability to seek when using a compression scheme. Compress blockwise and search within the blocks.

### Lempel-Ziv-like algorithms

The Lempel-Ziv family and similar algorithms provide good compression for data with many/long reoccurring strings, but fail to recognize the relationship between integers in noisy or slowly changing sequences. Below are three sequences of integers: the first consists of constant values, the second counts upward and somehow resembles timestamps, and the third is noisy and represents a sensor reading.

$$\[900, 900, 900, 900, 900, 900, 900, 900, 900, 900\]$$ $$\[890, 892, 894, 896, 898, 900, 902, 904, 906, 908\]$$ $$\[900, 890, 905, 901, 918, 892, 919, 916, 904, 920\]$$

Zip will greatly reduce the size of the first sequence, have a hard time on the second and won't provide any compression on the third.

### Delta encoding

To reduce the number of bits per number, the range of possible numbers must get smaller. If we incorporate the knowledge that values change slowly, we conclude that storing only the difference to the previous value yields values close to zero. The three example sequences above become:

$$\[900, 0, 0, 0, 0, 0, 0, 0, 0, 0\]$$ $$\[890, 2, 2, 2, 2, 2, 2, 2, 2, 2\]$$ $$\[900, -10, 15, -4, 17, -26, 27, -3, -12, 16\]$$

If we know the rate of change is approximately constant, as in case of timestamps, we can apply delta encoding twice. Below is a sequence of timestamps in original form and after applying delta encoding once/twice.

$$\[96, 296, 497, 701, 904, 1102\]$$ $$\[96, 200, 201, 204, 203, 198\]$$ $$\[96, 104, 1, 3, -1, -5\]$$

All we need now is a way to make the (on average) smaller numbers into less disk space.

### Variable width integers

We can reduce the number of bits by using variable width integers that use less bits for smaller (by magnitude) numbers. The usual encoding is:

* For numbers that fit into 7-bit signed integers, use one byte.
* For larger numbers
    + store the 7 least significant bits in one byte.
    + set the MSB (continue-flag).
    + encode the remainder in the following bytes, using the same encoding.

This way 32-bit integers are encoded in 1-5 bytes, dependent on the actual value.

## Conclusion

* If possible, don't store timestamps at all (independent of compression).
* Compress in blocks. Trade-off between access time and compression.
* If the sensor readings are **exactly** constant for some periods of time, zip is the way to go.
* If the sensor readings are approximately constant, use delta encoding.
* If the timestamps are changing at approximately constant rate, use delta encoding twice.

# Answer
> 2 votes
One way is to compress the file in smaller chunks. Store the contents of the files in some sort of index to facilitate search. Alternatively, since data is stored 3 times per second, you can just reflect the time chunk of each file through its name, and then search is also easy.

# Answer
> 2 votes
> If this would be implemented properly, it should be possible to uncompress an individual datapoint

That is clearly (well, knowing how compression workds) only possible if you compress each data point by itself, which will not do much if these data are small.

> I do not expect compression results near Zip and 2x - 5x would be enough.

Keep in mind that *no* lossless compression algorithm can guarantee *any* such rate. There's an easy-to-prove no-free-lunch theorem; every such algorithm has to make some inputs *longer*.

> What is a good (and if possible semi-easy to implement) algorithm to find patterns in binary data?

The concept of how humans think about "patterns" is misleading. General-purpose compression algorithms are application- and encoding-agnostic; they won't use any pattern you'll see as such.

> it must be possible to at any time, with a given timestamp and interval, read out the values that are stored in that file

The solution is clearly to save smaller files. The size depends on how small you need the resulting files to be, that is how long decompression may take. Say, files with one hour of sensor data are small enough; then you just save one (compressed) file per hour.

You should look into the Lempel-Ziv family of compression algorithms. They work with any string data, and binary strings are just that.

---

That said, there *is* research on searchable compressed data. I think that is overkill in your situation, though.

---
Tags: algorithms, data-structures, data-compression
---


# Question
Title: A question about halt (or stop) of Turing machine
I try to understand something:
At Turing machine we have two stats: $q\_{accept}$ and $q\_{reject}$.

Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: $C(w,q\_t,\varepsilon )$,
and $q\_t =Q-\\{q\_{accept},q\_{reject}\\}$.

Of course $M$ don't accept $w$ and don't reject $w$, but my question is:
We can say that $M$ **Stops** on $w$?

I try to look for an answer but I didn't found...

Thank you!

# Answer
No, Turing machine are defined in a different way than finite-automata: they don't "stop" at the end of the input, they stop whenever they reach a *final* state $q\in F$. Usually, there are two final states, $q\_{acc},q\_{rej}$ – if the machine transitions to one of these final states it stops; but until then, it keeps running.

Therefore, $\delta(q,\cdot)$ must be defined for any $q\in Q\setminus F$ and and letter the head points on. This will tell us how the machine behaves when in the state $q\_t$ (using your symbol, assuming it is not a final state; see below if it is).

---

regarding halting without accepting/rejecting: the answer is yes. If, say, $F=\\{q\_{acc},q\_{rej}, q\_{inconclusive}\\}$, and the machine reached the third final state, we can say it neither accepted nor rejected, but it halts indeed since it reached a final state in $F$. Of course, $F$ can be as large as $Q$. It may make sense for computing other task than yes/no decision problems.
> 4 votes

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


title: Check Cycles- On adding an edge in DAG

text:
# Question
Title: Check Cycles- On adding an edge in DAG
Given a DAG N, if an edge $(U \rightarrow V)$ is added between any existing nodes U and V. Then, by performing DFS from the node $U$ and checking whether there is a cycle or a not, should be sufficient to conclude that this addition of edge didn't violate the acyclic property of the given DAG. Is it correct?

Or there is a need to perform DFS from other nodes in the network to verify the cyclic property of DAG?

Trying to find the most efficient way to verify whether addition of an edge to an existing DAG introduces cycles or not?

# Answer
> 2 votes
If you start with a dag then the only thing you need to check is whether adding the edge $U\to V$ will not create a cycle. That is, there should not exist a path from $V$ to $U$ in the original graph.

---
Tags: graphs
---


# Question
Title: What does the $\leq_{\mathrm{P}}$ symbol mean?
What does $\leq\_{\mathrm{P}}$ mean? Is it supposed to mean less than or equal polynomial time?

# Answer
It should have been defined wherever you've seen it used. It normally stands for polynomial-time reducibility of one kind or another; usually many-one reducibility.
> 7 votes

---
Tags: complexity-theory, notation
---