# Question
Title: Bakery algorithm: what is the choosing[] boolean array for?
I'm studying the bakery algorithm.

```
do {
     choosing[i] = true;
     number[i] = max(number[0], number[1], …, number [n – 1])+1;
     choosing[i] = false;
     for (j = 0; j < n; j++) {
         while (choosing[j]); //
         while ((number[j]!= 0) && (number[j],j)<(number[i],i)));
     }
     critical section
     number[i] = 0;
     remainder section
} while (1);

```

Please help me know what exactly this `choosing` doing here. I checked this for all conditions that I could generate to understand its use. But it doesn't seem to be making any difference. Please help me with a case.

# Answer
> 10 votes
`choosing[i]` is true while `number[i]` is being updated to be larger than all the other values in the `number` array — the new ticket value that the thread is taking. In the body of the for loop, the code first waits for `choosing[j]` to be false, which indicates that thread number `j` has chosen its ticket for this round. If thread `j` goes on executing while thread `i` hasn't entered the critical section yet, then `number[i]` won't change, so:

* If thread `j` is still in the same round and hasn't finished the critical section yet, then `number[j]` is the result of a `max` computation which may or may not have taken the *current* value of `number[i]` into account, depending on the interleaving of the execution of threads `i` and `j`.
* If thread `j` is in the remainder section then `number[j]` is 0.
* If thread `j` has begun a new round then its `number[j]` is the result of a `max` computation that took the current value of `number[i]` into account, thus `number[j] > number[i]`.

In the first case, threads `i` and `j` are running their for loop concurrently; only one of them will win the `(number[j],j)<(number[i],i)` comparison and proceed into the critical section, and the other will wait for the winner's `number` value to become acceptable again. In the second case, thread `j` is not competing for the critical section. In the third case, thread `j` has a higher number and will wait in its own `for` loop while thread `i` hasn't reset its `number[i]` value.

The `choosing` array works around the lack of atomicity in the computation of `number[]` values. If it was removed, then you could have two threads computing the same value concurrently and each finding that it had the smaller value at the point of testing. This could happen with as little as two threads (I use the notation `k.tmpX` to designate local storage of the thread `k`):

```
initially: number[1] = number[2] = 0

thread 1                                   thread 2
//choosing[1]=true
1.tmp1 = number[1]
1.tmp2 = number[2]
                                           //choosing[2]=true
                                           2.tmp1 = number[1]
                                           2.tmp2 = number[2]
                                           number[2] = max(2.tmp1,2.tmp2)+1 = 1
                                           //choosing[2]=false
                                           //while (choosing[1]) {}
                                           while (number[1]≠0 &&
                                                  (number[1],1)<(number[2],2)) {}
                                           critical section ...
number[1] = max(1.tmp1,1.tmp2)+1 = 1
//choosing[1]=false
//while (choosing[2]) {}
while (number[2]≠0 &&
       (number[2],2)<(number[1],1)) {}
critical section ...
                                           critical section ...

```

The two threads computed the same ticket number. The bakery algorithm uses the thread number to determine the priority in this case. However, thread 2 decided to the critical thread while thread 1 was still preparing, whereas thread 1 saw the new ticket number of thread 2 when deciding whether to enter the critical section but had computed its own ticket number based on thread 2's old ticket number. So thread 1 incorrectly entered the critical section.

The `choosing` array solves this problem by preventing thread 2 from entering the critical section. Since thread 1 is computing its ticket number at the time thread 2 is preparing to enter the critical section, thread 2 will block on `while (choosing[1]) {}`, after which it will see the updated value of `number[1]` and allow thread 1 to enter the critical section first, while thread 2 waits on `while (number[1]≠0 && (number[1],1)<(number[2],2)) {}`.

---
Tags: algorithms, concurrency, synchronization
---


title: Solving a Variation of knapsack

text:
# Question
Title: Solving a Variation of knapsack
I'm working on a problem which to me, seems very similar to a knapsack problem:

> A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store and bought $2k$ items: $f\_1, f\_2, ...f\_{2k-1}, f\_{2k}$. The items are priced: $p\_1, p\_2,...p\_{2k-1}, p\_{2k}$ respectively.
>
> Help David arrange the items in pairs such that the price of the $2k$ items is minimal.
>
> Suggest an algorithm which solves the problem in $O(klogk)$. Prove correctness and running time.

So this seems very similar to the knapsack problem, but I have not been able to find a good solution.

Any help will be appreciated. Thank you!

# Answer
> 0 votes
I'll do the cases $k = 1$ and $k = 2$ for you. First, $k = 1$. Suppose there were two items, $f\_1,f\_2$, priced $p\_1,p\_2$. Without loss of generality, assume that $p\_1 \> p\_2$. Then whatever you do, you will pay $f\_1$.

When $k = 2$, there are four items $f\_1,f\_2,f\_3,f\_4$ and four prices $p\_1,p\_2,p\_3,p\_4$. Suppose again that $p\_1\>p\_2\>p\_3\>p\_4$. There are three possible ways of pairing items: $(f\_1,f\_2),(f\_3,f\_4)$, $(f\_1,f\_3),(f\_2,f\_4)$, $(f\_1,f\_4),(f\_2,f\_3)$. You will pay $f\_1+f\_3,f\_1+f\_2,f\_1+f\_2$, respectively. The lowest number here is the first $f\_1+f\_3$ (why?). So you should choose the pairing $(f\_1,f\_2),(f\_3,f\_4)$.

The general case is very similar. Try to figure out what step takes time $O(k\log k)$ (I have hidden this step in the description above), and then what is the best pairing. Try to solve it on your own.

---
Tags: algorithms, complexity-theory, knapsack-problems
---


title: Bubblesort generalization

text:
# Question
Title: Bubblesort generalization
I was comparing and analyzing the sort algorithms thereby came across a machine which took 200 secs to sort 200 names but to generalize, in 800 secs wouldn't it sort 800 names?

# Answer
Two main points: First of all, you fell in the "trap of universal linearity" (see here for other manifestations of the trap). If you double the input, the computation time only doubles *if your algorithm takes linear time*. Sorting with Radix Sort actually takes linear time, so in that case it would be correct to simply double the time. You never explicitly stated how you sort (which you should, otherwise how should we answer your question?), but your *Bubblesort* appearance in the title lets me assume that it's Bubblesort-related.
Which brings me to the second point: What could that $O(n²)$ that is probably mentioned somewhere in your literature have to do with your question?
> 1 votes

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: Hungarian Assignment Algorithm Implementation
I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows:

```
S(0) <- appropriately sized matrix filled with 1's
for k=1 to 10 do:
    S(k) = Y*S(k-1)*X^T + Y^T*S(k-1)*X
    k++
Apply Hungarian assignment algorithm on similarity matrix S.

```

where X^T means the transpose of the matrix X.

Basically, given two graphs G1, G2 (not necessarily the same # of vertices), create their adjacency matrices X and Y. Then, do this iterative process 10 times, and then apply the Hungarian assignment algorithm. The result would be a similarity matrix where entry (i,j) represents a real number between 0 and 1 that gives how "similar" vertex i is of G1 to vertex j of G2.

My question is: how would this algorithm be implemented? I looked up the algorithm on Wikipedia, and the explanation seems as though all entries in S would be integers, but what is expected is real numbers between 0 and 1.

# Answer
The article you linked assumes that the reader knows how to apply the Hungarian algorithm on a similarity matrix because they have note in the introduction to Section 3 that Zager et. al. used the Hungarian algorithm for this purpose in the paper here.

Furthermore, there is no requirement in the Hungarian algorithm that necessitates integral entries; neither the Wikipedia article and this slide deck mention any requirement for the entries to be integers. Authors may use integer values for examples because they're easy to work with, but that does not mean the algorithm requires them.
> 3 votes

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


title: Lovasz theta of even cycle

text:
# Question
Title: Lovasz theta of even cycle
How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could someone provide a derivation for even cycle Lovasz theta number. It is clear that the Shannon Capacity is $\frac{n}{2}$. why is the cosine form tight only for odd cycles?

# Answer
The Lovász theta function is bounded between the independence number and the clique covering number (the chromatic number of the complementary graph). For even cycles, both numbers are $n/2$. For example, for the $6$-cycle with vertices $1,2,3,4,5,6$, there are independent sets of size $3$, e.g. $\\{1,3,5\\}$, and the graph can be covered with the $3$ cliques $\\{1,2\\},\\{3,4\\},\\{5,6\\}$.
> 2 votes

# Answer
See Lovasz' definition of theta in terms of orthonormal representations of graphs. Even cycles have an orthonormal representation in two dimensions in which the odd nodes are mapped to (0,1) and the even nodes are mapped to (1,0). Odd cycles, on the other hand, do not have two-dimensional orthonormal representations. They have three-dimensional ones that take the form of an "umbrella".
> 2 votes

---
Tags: graphs, information-theory
---


# Question
Title: How do deal with the following situations using Prim's algorithm?
Consider the following Graph

We want to generate the MST using Prim's algorithm.

Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other alternatives.

1. Do we ever take the self loop? Why not?

Suppose we just moved from C to D

2. D only has one edge connecting to E, under Prim's algorithm we will take that edge right?

Now we have travelled from C to D to E, now I am making a choice at E. By picking the edge with the lowest weight we are back at C and the loop from C, D, E continues on forever

3. What should we do if we enters an in-terminating loop?

# Answer
> 1 votes
First of all , MST of a connected graph is a subgraph with the following properties:
i. Spanning Tree: No cycles -\> n-1 edges(easy to prove)
ii. If we sum up the weights, we get the lowest possible.

Prim's algorithm is a greedy algorithm, which means that we always choose the best choice in every step(greedy).

1. From i, you can see that you never get self loops (acyclic).
2. Yes, because it's the edge with the lowest weight not because it is the only edge in this moment from D to connect in E; there maybe exist another edge eg. C-\>E would have been the next choice had the weight between D-\>E is 5.
3. No, it does not get to a non-terminating loop, you never choose the same edge again. Think like, there is a set S with all the edges that have not been discarded, after you choose the edge e then S is changed to S-e. In your example the best choice is to choose E-\>F.

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


# Question
Title: Given $T(n) = \sum_{i = 0}^{\log n} i 2^i$, what is $O(T(n))$?
I'm trying to perform an asymptotic analysis on a function:

$T(n) = \sum\_{i = 0}^{\log n} i 2^i$

The above expression came about when I began with:

$T(n) = \sum\_{i = 0}^{\log n} 2^i \log (2^i)$

Is there a tight, closed-form expression for $O(T(n))$?

# Answer
There are two ways to calculate the sum. The first way is to write it as $$\sum\_{i=1}^{\log n} \sum\_{k=1}^{i}2^{i}.$$

You change the order of sum and the calculation is the sum of geometric series.

Another way is to write it as $f(x)=\sum\_{i=1}^{\log n} x^{i}$, and find the $xf\`(x)|\_{x=2}$, again a sum of geometric series.
> 2 votes

---
Tags: asymptotics
---


title: Inferring Shannon Capacity of pentagon

text:
# Question
Title: Inferring Shannon Capacity of pentagon
Can we infer from the fact that the number of independent sets in product of $5$-cycle two times is $5$ and in product of $5$-cycle four times is $25$, that the capacity of pentagon is $\sqrt{5}$? That is does $\alpha(C\_5 \boxtimes C\_5)=5$ and $\alpha(C\_5 \boxtimes C\_5\boxtimes C\_5 \boxtimes C\_5)=25$ imply $\theta(C\_5)=\sqrt{5}$? Why? Or why not then?

Here $C\_5$ is pengtagon, $\alpha(G)$ is independence number of graph $G$, $\boxtimes$ is strong product and $\theta(G)$ is Shannon capacity of graph $G$.

# Answer
From the givens you can only deduce that the Shannon capacity is at least $\sqrt{5}$. For example, it could be that $\alpha(C\_5^8)^{1/8} \> \sqrt{5}$, which doesn't contradict your data.

As an aside, the Shannon capacity is usually denoted by $\Theta$, whereas $\theta$ is the Lovász function, which is an upper bound on the Shannon capacity. From the givens you can only deduce that $\theta(C\_5) \geq \sqrt{5}$.
> 1 votes

---
Tags: information-theory
---


# Question
Title: What are some fundamental issues computer science tries to address?
I was wondering, if physics has the origins of the universe or the nature of space, time, and matter, biology has the existence of the cell and the origin of life, are there mysteries that computer science could seek to unravel?

This question does not concern the theories and technologies developed by computer science, but more existential, ontological issues.

# Answer
Computer science addresses the mystery of computation (but not computers): what is computable, what is not-computable, how difficult it is to solve certain problems, when are programs correct, how can programs be effectively written, what's the best way of solving problem X (for many Xs), ...
> 5 votes

---
Tags: philosophy
---


title: What is the Certificate for Set Cover?

text:
# Question
Title: What is the Certificate for Set Cover?
Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\\{1, \ldots, m\\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\\{1, \ldots, m\\}$. My question is: what would be a certificate for this problem? That is, if I wanted to convince someone that it is not possible to do this with fewer than $k$ sets, what information could I provide that would allow someone to verify that this is the case in polynomial time?

# Answer
The set cover is not a decision problem, so it doesn't necessarily have a certificate. Rather, it is an optimization problem.

To make it a problem in NP (a decision problem, with a certificate), you need to apply the standard trick to convert an optimization problem to a decision problem: introduce a budget. Thus, the decision budget is: given a collection of sets and an integer $k$, determine whether there exists a subset of $\le k$ sets whose union is all of $\\{1,\dots,m\\}$. That *is* a decision procedure, and *does* have a certificate: the subset of size $k$ is the certificate.

See also Optimization version of decision problems and standard textbooks.
> 6 votes

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


# Question
Title: How can I make sense of amortized accounting method?
Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read).

In the example of the Stack with Multiple Pops (From CLRS, for reference: http://chuck.ferzle.com/Notes/Notes/AlgorithmAnalysis/Amortized.pdf), we arbitrarily "assigns" a credit of 2 two the Push operation, 0 for pop and 0 for multipop, and each push we arbitrarily "spend" 1 credit and the objected pushed onto the stack "stores" 1 credit.

This has to be the most insane thing I have ever seen in my life! Even if I get pass the "why 2 but not 100 credits" stage, how can I rationalize the fact that the object somehow stores a credit? How can we just arbitrarily assign these costs to these operations? Also how could you possibly gain anything insightful from this?

It is like imagining that typing on this computer will earn me $100 USD and shutting off the computer will make me spent 20 USD. Can someone please shed a light on how this technique works?

# Answer
> 7 votes
> Amortized analysis is a strategy for analyzing a sequence of operations irrespective of the input to show that the average cost per operation is small, even though a single operation within the sequence might be expensive.

As it is shown in the above quote, amortized analysis is applicable particularly to a sequence of operations in which cheap operations occur frequently and expensive ones occur rarely. Moreover, in an operation sequence, the expensive operation is often related to (*OR caused by*) the cheap ones before it. For example, in your "Multi-Pop Stack", the cost of the expensive operation `multi-pop(S,k)` depends on the number of elements in the stack and thus on the earlier `push(S,x)` operations.

If we focus on a single `multi-pop(S,k)`, we may be disappointed by its expensive cost. Worse still, its cost varies, depending on the current state of the stack when it is issued: if it has popped $t$ elements, then its cost is $t$. By accounting method, we turn to a sequence of operations and attribute (*average*) the varying cost $t$ of `multi-pop(S,k)` to the $t$ `Push(S,x)`.

> Even if I get pass the "why 2 but not 100 credits" stage, $\ldots$

Yes, you can use `100 credits`. However, `2` is tighter in terms of worst-case time complexity.

> $\ldots$ how can I rationalize the fact that the object somehow stores a credit?

"Credit" is only an analogy. We are charging the cost of some (expensive) operations to earlier (cheap) ones. From a different perspective, the earlier (cheap) operations had better save credits for further use of some (expensive) ones.

> How can we just arbitrarily assign these costs to these operations?

They are of course not arbitrarily assigned. Instead they are well chosen.

---
Tags: algorithm-analysis, proof-techniques, amortized-analysis
---


title: Longest Path in a directed rooted graph

text:
# Question
Title: Longest Path in a directed rooted graph
A directed rooted graph is defined as graph for which there exists a vertex r such that to every vertex x there is a unique path (Equivalently dfs tree with source r has only back edges and has all vertices). I need an algorithm to find the longest path in such a graph.

I know that in general longest path problem is NP-hard. I want to know whether for this special case there exists a polynomial time algorithm.

# Answer
> 1 votes
The problem falls into one of the following cases:

**case (a):** There is a unique path from the root to all other nodes (it means that there is only one single path from root to others; this implies that there is only one single path between any other pair of nodes too). If there is only a unique path from source to each node, then there is $O(n^2)$ number of different paths in the graph, you can just find them pick the longest one as the optimal solution using a polynomial time algorithm. You just need a DFS traversal from root and find the length of path to each leaf and choose the longest one.

**case (b):** But if it's a general rooted graph, i.e. there can be multiple paths from root to other nodes but there is no path from them to the root, then the following theorem holds. This problem is NP-complete as the actual longest path problem reduces to it. The reduction is as follows. Given an instance of longest path problem $I=(G(V,E), k)$, we build an instance of your problem $I'=(G'(V \cup \\{s\\},E \cup \\{(s,v\_1),(s,v\_2),...(s,v\_n)\\}),k+1)$ (The reduction is very strightforward, I keep it short).

In the later case, if you are just looking for a feasible solution. I suggest removing the source node from your directed graph and using the available heuristics for the longest path problem in the resulting graph. Then adding the source to that path.

---
Tags: algorithms, graphs
---


# Question
Title: Minimizing total distance to a point from a set of points
I've read about a problem:

> There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal.

I've written a Monte-Carlo algorithm, but that can't be the optimal approach.

Is there a solution other than approximating the position with Monte-Carlo method? Especially by using a graph or is that a wrong approach?

Is there a way to *calculate* the optimal position?

What is the name of this problem?

# Answer
It's a two-dimensional facility location problem. In this case, the optimum location is the centre of gravity (also known as the barycentre or centroid) of the locations of the houses, which is easily calculated from their co-ordinates.
> 2 votes

---
Tags: computational-geometry, shortest-path, monte-carlo
---


title: Finding optimal price in a sale

text:
# Question
Title: Finding optimal price in a sale
A furniture store is having a sale: purchase two items at the price of the more expensive one. John, having just moved to a new house, rushed into the store and chose $2k$ items of furniture, $f\_1, f\_2, \dots, f\_{2k}$. The items are priced $p\_1, p\_2, \dots, p\_{2k}$, respectively. Help John arrange the items in pairs so that the overall cost of the $2k$ items is minimal. Suggest an algorithm that runs in time $O(k\log k)$ and prove its correctness and running time.

Ok, so it sounds not too complicated: first, I will sort all the $2k$ items by their prices to array, and then each cell and his next are one couple. This takes time $O(k\log k)$.

How can I prove the correctness of what I suggest? I thought about assuming that there is a cheaper solution to get a contradiction but I dont know how to prove this.

# Answer
Let's do the case $k = 2$. If the prices are $p\_1 \geq p\_2 \geq p\_3 \geq p\_4$ then there are three possible pairings $(p\_1,p\_2),(p\_3,p\_4);(p\_1,p\_3),(p\_2,p\_4);(p\_1,p\_4),(p\_2,p\_3)$ with cost $p\_1+p\_3;p\_1+p\_2;p\_1+p\_2$. So the first pairing is the best.

There are several ways to show that this pairing strategy is optimal in general. You might start by showing that given an arbitrary pairing in which $p\_1$ is not matched with $p\_2$, there is a way to modify it so that $p\_1$ is matched with $p\_2$, and the overall cost is lower. This leads to one proof.

Another idea is to show directly that the cost is always at least $p\_1+p\_3+\cdots$. For example, $p\_1$ is always the largest in its pair, and $p\_3$ is either the largest in its pair, or it is paired with $p\_2\>p\_3$ or with $p\_1\>p\_3$. You have to modify this argument so that you don't double count prices (for example, if $p\_1$ is paired with $p\_3$ and you follow the argument as stated, you will count $p\_1$ twice).

There might be other ways to prove it, so if you have other ideas, by all means go ahead and try them out.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Loop invariant: decreasing a variable and swapping it
As an example exercise, we were asked to find the loop invariant for this bit of code.

```
def mystery(a,b):
    # Precondition: a >= 0 and b >= 0
    while a >= 0 and b >= 0:
        if a < b:
            a, b = b, a
        else:
            a = a - 1
    return a

```

From what I can see, it first ensures that `a >= b`.
After that, each loop iteration decreases the value of `a` by 1.

This will continue until `a` and `b` are 0.

Then one final iteration terminates the loop with `a == -1`.

However from what I can tell, if the loop invariant is something like `a >= b`, it fails upon termination as `a = -1 and b = 0`.

Could anyone tell me the actual loop invariant of this function as I'm a bit confused.

# Answer
> 2 votes
There isn't a single loop invariant: any property that remains true during the execution of the loop is a loop invariant. For example, “I am not the Pope” is an invariant of this loop, but it is not a useful one. A useful loop invariant is one that helps in proving some property of the program.

Here, presumably, the ultimate point of the exercise is to determine the return value of the function (as a function of the arguments `a` and `b`). The only way this function can return is on normal exit of the `while` loop, returning `a` in a state of the program where the condition `a >= 0 and b >= 0` is false.

The property `a >= b` isn't likely to be relevant because it's neither true at the start of the function nor when the function returns.

Given the objective to figure out the value of `a` when the loop exits, it is useful to look at what happens in the last iteration of the loop. We know that `a >= 0 and b >= 0` is true on entry to the function, so there will be at least one loop iteration. Let $a'$ and $b'$ be the values of `a` and `b` at the start of the last iteration, and $a''$ and $b''$ the values at the end. We know from the loop condition that $a' \ge 0$, $b' \ge 0$, and $a'' \lt 0 \vee b'' \lt 0$. This can only happen when the `else` branch is taken. Therefore $a'' = a' - 1$ and $b'' = b'$. Plugging these equalities into the inequalities we had, we get that $b'' \ge 0$ so $a'' \lt 0$ and also $a'' \ge -1$.

It appears that `b >= 0` and `a >= -1` are two invariants of the loop — they're true on entry and they're true on return. Furthermore, if the initial values of `a` and `b` are integers, the property “`a` and `b` are integers” are also loop invariants. If `a` and `b` are integers, then the only possible value for $a''$ given the inequalities above is $-1$, so this function can only return the value $-1$.

Follow-up exercices:

1. If `a` and `b` aren't constrained to be integers, what does the function return? You'll need to find another invariant to determine the value of $a''$.
2. If `a` and `b` are nonnegative integers, I've proved that this function can only return the value `-1`. I haven't proved that this function is equivalent to `return -1`, however: it might also loop infinitely. Prove that (given the precondition that the arguments are non-negative) the function always terminates.

---
Tags: algorithm-analysis, loops, loop-invariants, imperative-programming
---


# Question
Title: Pumping Lemma for Context-Free Languages for reversal language
Show that the language L = {ww^Rw: w in {a,b}\*} is not a context-free language.

# Answer
> 3 votes
Let's call the first $w$ of a word $ww^Rw \in L$ "part A", the middle part $w^R$ "part B" and the remaining $w$ "part C".

Use the word $$z=\underbrace{0^n10^n}\_{A} \underbrace{0^n10^n}\_{B} \underbrace{0^n10^n}\_{C} \in L$$ with $|z|\geq n$.

The pumping lemma states that if $L$ is context-free, $z$ can be written as $z=uvwxy$ and

(1) $|vwx| \leq n$,

(2) $|vx| \geq 1$,

(3) $\forall i \in \mathbb{N}: uv^iwx^iy \in L$.

However, when setting $i=0$, the resulting word $z'=uwy$ cannot be element of $L$ as one of the following situations occurs:

1. Exactly one "1" has been deleted from $z$, possibly among other "0" symbols (another "1" cannot have been deleted due to $|vwx|\leq n$). Then two parts of $z'$ contain a "1", but the third one, A, B or C doesn't, therefore, $z' \notin L$.
2. "0"s from at most two parts of $z$ have been deleted, but not from the third part (again due to $|vwx|\leq n$). So, in this case too it hold that $z' \notin L$.

Therefore we have to give up the assumption that $L$ is a context-free language.

# Answer
> -1 votes
Let $1 \leq p$ and let $p\leq|w|$ if we take the $ww^{R}w \in L$ then by the pumping leemma we are going to have that : $\forall n\ uv^{n}wx^{n}y \in L $ and $|vwx|\leq p$ and |vx|\>0 so we can see that either $v,x$ are letters of $w^{R},w$ or one is in $w$ and the other in $w^{R}$ . if we take $n=0$ we get to contraction. So it isnt context-free.

---
Tags: context-free
---


# Question
Title: Complexity of variation of partition problem
I want to know whats the complexity of the following variant of the partition problem:

Partition problem:

http://en.wikipedia.org/wiki/Partition\_problem

Suppose we have one set formed by integers and we want to partition the set in two subsets of the same size, the same cardinality(the same number of integers in each subset) in such a way that each subset equal a given number called S.

Let's call this problem "2-partition" like the 3 partition problem

What's the complexity of the problem is easier,is in P?

Is still in NP?

I tried looking on google but i didn\`t found anything, i dont even know if the problem is mentioned in some book or publication

Thanks

# Answer
> 4 votes
Is it in NP? Yes - *any* restricted version of an NP problem is also in NP.

Is it still NP-hard? Yes. 2-partition (without the constraint that both subsets should be equal cardinality) is NP-hard. Let's call your form of the problem "equal cardinalty 2-partition". To reduce from regular 2-partition to equal cardinalty 2-partition, we can pad the 2-partition problem by adding lots of extra 0's to the set, so that the 0's can be used to balance out any valid 2-partition solution to a solution that is an equal cardinality 2-partition.

You might object to the use of 0's in the input, and define "positive balanced cardinality 2-partition" where the input must be positive (so 0's are not allowed). But I can reduce any balanced cardinalty 2-partition problem to positive balanced cardinalty 2-partition by incrementing all numbers in the input by 1. This does not change the solution because of the equal cardinality constraint (each part of the partition gets increased by equally much).

Now you might still object that this reduction requires that you allow duplicate numbers in the input set. Even if you disallow duplicates in the input it remains NP-hard, and you can show so by a reduction from Positive 1-IN-3 SAT.

Is it in P? Answering this question would settle the P vs. NP problem so you're not very likely to get an answer any time soon.

---
Tags: complexity-theory, np, partitions
---


title: How was counted one second in computers

text:
# Question
Title: How was counted one second in computers
I would like to know how was counted 1 second in computers. I mean how machine can understand period of 1 second. Who and when resolved this problem, and more important how ?

# Answer
Basically, the computer has a "clock". This is a chip that generates a pulse every fixed period of time, say, every 1 millisecond, generated usually via a crystal.

With sophisticated techniques of clock multiplying, one can get to higher (internal) clock rates. (see e.g., frequency divider and CPU multiplier)

Counting second (or any long enough time) is now simple - the computer can count the number of "clock ticks" to estimate the time that has passed. If the external clock signal has a pulse every 1 millisecond, then after $10^6$ such pulses, about 1 second has passes. This is not precise, because the computer takes some time to count each pulse, but such an impreciseness is order of magnitudes smaller than milliseconds.)
> 1 votes

---
Tags: computer-architecture, clocks
---


title: 3-Coloring Problem Question

text:
# Question
Title: 3-Coloring Problem Question
So I understand that finding a solution to the 3-coloring problem takes exponential time. However, say you had a friend who you could give a graph G to and he can say in constant time whether it is 3-colorable or not. Is it possible to find a 3-coloring of G in polynomial time with his help? I think it might be possible but I'm not sure if my approach is correct.

Say the 3 colors are RGB. You assign some vertex R and give G back to your friend. If he says Yes, then keep it colored R, if No then leave it be. Go through every vertex this way assigning R, and then with G and B afterwards. The graph will be 3-colored at the end, but this would only take O(V\*3) time.

# Answer
> 1 votes
First, it is not known that 3-coloring takes exponential time. Even if P is different from NP, it could still be the case that 3-coloring can be solved in subexponential time, though the Exponential Time Hypothesis (ETH) precludes this possibility (if you assume the hypothesis).

Second, regarding your suggested solution. The black box only accepts graphs, it doesn't accept partially colored graphs. You need to give a reduction which only feeds the black box actual graphs.

Third, if a graph is 3-colorable, then there is always a 3-coloring in which a particular vertex is red. So what you're really trying to do is ask whether there is a 3-coloring in which a given set of vertices has the same color, another set of the vertices has a different color, and yet another one has the remaining color. See if you can somehow encode some of these constraints using graphs rather than partial colorings.

---
Tags: algorithms, 3-sat, colorings
---


# Question
Title: What to expect in a Computer Science and Mathematics course?
I'm a high school student. I'm really into programming and mathematics and planning to study CS and mathematics when finished with high school.

I have a couple of questions concerning this issue:

Firstly, from maths point of view, what are the prerequisites and what subjects do I get in the first 2 years? I understood that Linear Algbera and Discrete mathematics are very important! So can you name an example of a maths textbook I may get?

Secondly, from a CS point of view, I already 'know' C#, F# and sometimes I play around with JS. Is it obligatory to learn ANOTHER language like python, java or c++? since knowing C# and F# already fulfils the 'need' of knowing different languages, F# with it's elegant functional-first programming paradigm and C# for imperative-first programming (technically, both F# and C# are multi-paradigm, which is awesome!)

To be more specific, I am into computer vision and ML. what textbooks do you think I may get in this area?

# Answer
> Firstly, from maths point of view, what are the prerequisites and what subjects do I get in the first 2 years? I understood that Linear Algebra and Discrete mathematics are very important! So can you name an example of a maths textbook I may get?

You want to select a textbook that "meets you where you're at" in terms of "mathematical maturity." Selecting too basic of a textbook will bore you, but selecting one that is too advanced will allow you to progress only at a suboptimal rate.

If you don't already know stuff that's in a typical discrete math course, I would suggest looking at this thread on Math.SE. My first Discrete Math course used Epp's book, but I found it somewhat basic.

If you already know some of what is covered in a typical discrete math course (e.g. elementary set theory, basic methods of proof, etc.--the stuff that would be covered in AoPS coursework), then I would *highly* recommend Graham, Knuth, and Patashnik's *Concrete Mathematics*. It is literally **the** book on math with respect to computer science theory. (If you learn everything in that book, I'd nearly guarantee you would know more math than 70-80% of CS students.)

However, graph theory and linear algebra are not covered in GKP's book. For linear algebra, I don't really know of a "great" textbook. For Graph Theory, I'd recommend looking at an algorithms textbook (CLRS's Introduction to Algorithms is *really* good), and perhaps going through this Coursera class and it's sequel. I learned *so much* in that course.

Also, take a look at Project Euler; it gives some fun math-based challenges that build quite nicely on each other. By solving those problems, I self-taught a *ton* of math from a very wide/eclectic basis.

> Secondly, from a CS point of view, I already 'know' C#, F# and sometimes I play around with JS. Is it obligatory to learn ANOTHER language like python, java or c++? since knowing C# and F# already fulfils the 'need' of knowing different languages, F# with it's elegant functional-first programming paradigm and C# for imperative-first programming (technically, both F# and C# are multi-paradigm, which is awesome!)
>
> To be more specific, I am into computer vision and ML. what textbooks do you think I may get in this area?

You'll probably be required to learn one of Java, C++, or Python depending on your school--most schools have a "favorite language" that they use by default in most of their classes. This "favorite language" is typically one of those three. (For example, University of Virginia uses Java as the language they assume all CS students know.) If you're really into computer vision, you'll probably want to learn C++; it's speed is important in that field, or so I've heard.

I wouldn't worry too much about learning other languages; having a foundation in a procedural and a functional language is great, and if you're comfortable with OOP, you'll be fine. When it comes time to use another language, you'll be able to pick it up really quickly with your background.
> 2 votes

# Answer
I'd say that most, if not all higher learning facilities, will have you learning at least one of the more legacy-ish languages, in my current one its C then transfer over to C++, I've heard other schools line up for point of Java though. Also if you really want to get a head up in the studying portion, linear algebra and discrete would definitely help you along, in the sense of learning basic and complex algorithms which are in themselves fundamental to the learning and proper implementation of many aspects of the languages, not just the ones listed above. This is me speaking from experience so far, and the fact that most people that I know who've attempted entry level positions are most always asked to implement some type of search, or sorting algorithm as a prelim for even a hint of interest from the hirer. In regards to the text to employ I'd recommend Practical \__ Programming by Oreilly media as a lifesaver and a good tool to self teach, because at one point or another you'll have to start focusing on the application of the language in a manner that will most likely not go in tune with the given curriculum.
> 0 votes

# Answer
**First year** Your first year is carefully designed to manage the step up from school to university mathematics, focusing on the key ideas you will need later in the programme. Alongside core calculus and algebra, other modules develop discrete mathematics, mechanics, pure mathematics, statistics and computational mathematics - you do not need to have studied these subjects before. As a Single Honours student, you also have the option to study a completely different subject, such as a foreign language, alongside your maths.

**Second year** As well as having some choice of modules, you’ll now be introduced to some of the more advanced areas of mathematics, such as complex analysis, allowing you to develop your particular strengths and interests in the third year.

> http://www.birmingham.ac.uk/undergraduate/courses/maths/mathematics.aspx#CourseDetailsTab

If you want to know more about JS

> https://www.khanacademy.org/computing/computer-programming

I think you should firstly learn c++ , then go for java.
> 0 votes

---
Tags: education, books
---


# Question
Title: Is complexity of $GI_{di}$ same as $GI_{un}$?
Does the graph isomorphism problem for directed graphs($GI\_{di}$) reduce to the graph isomorphism problem for directed graphs($GI\_{un}$)?

It is clear $$GI\_{un}\leq GI\_{di}$$ since the set of undirected graphs is subset of set of directed graphs. Does the converse hold true? That is, can an algorithm for undirected graphs used to test for problems in $GI\_{di}$ with polynomial increase in complexity? Is $$GI\_{di}\leq GI\_{un}?$$

# Answer
The Wikipedia page mentions that digraph isomorphism is GI-complete, and gives a reference. For the proof, something along the following lines should work. Replace each $u\to v$ edges with a path $u\to x\to y\to v$, and attack a clique of size $A$ to $x$, and a clique of size $B \neq A$ to $y$. Choose $A,B \> n$ to ensure to these are the only cliques of that size. Instead of a clique you can have a long path or a large star.
> 6 votes

---
Tags: complexity-theory, reductions, graph-isomorphism
---


title: Theta estimation of two functions

text:
# Question
Title: Theta estimation of two functions
I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and everything I can find online expects more prior knowledge than I feel I have. Can someone just explain this in beginners terms for me? I don't know what Big-O or theta even refer to in this notation. I think I have a loose idea of what "complexity" refers to (a measure of how efficient code is, depending on how long a function will take in different circumstances?)

The problem in question:

Demonstrate the $\Theta$-complexity of the functions below. In order to demonstrate that $f(n) = \Theta(g(n))$ you must find two constants $C\_1$ and $C\_2$ such that $$ C\_1g(n) ≥ f(n) ≥ C\_2g(n). $$

a.) $f(n) = n^3 - 3n^2 + 5$.

b.) $f(n) = 2\log\_2 n - 4$.

# Answer
The exercise being asked about is pretty stupid (this is criticism against the person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log\_2 n - 4 = \Theta(4\log\_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

> For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general a function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$ Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.
> 1 votes

# Answer
The Complexity of an algorithm is the behavior that it have in memory or time (execution). This means that, for example, if you have an algorithm to explore a matrix of dimensions *nxn* to find a number, then the algorithm have a Complexity equals to Big-O(n^2). This because, in the worst case, you need to explore the *nxn* locations of the matrix. The theta complexity, refers to algorithms that have an exact behavior, i.e., if you have an algorithm to explore everyone of the locations of a Matrix with *nxn* dimension, that algorithm have a Complexity Theta(n^2), because you are exploring (no more, no less) the complete matrix *nxn*.

This is very abstract, I recommend you read about Asymptotic analysis
> -1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: How do I use induction to show that the language of a grammar is contained in a given set?
Given that I have the grammar

$\qquad\displaystyle G\_1 = (\\{a, b, c, d\\}, \\{S, X, Y \\}, S, \\{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\\})$,

how am I supposed to prove that

$\qquad\displaystyle S(G1) ⊆ \\{a^{n+1} b^{n+1} c^{m+1} d^{m+1} \mid n, m ≥ 0\\}$

by using Induction?

# Answer
When proving something about a language generated by a grammar, your induction should be on the number of derivation steps.

Here, the induction hypothesis should be: $S=\>^i a^kAb^kc^jBd^j $ for $i,j \< i, A \in \\{ X, \epsilon\\}, B \in \\{ Y, \epsilon\\}$ .

base: for $i=1$ we have that $S=\>^1 XY = a^0Xb^0c^0Yd^0$. and the hypothesis holds.

step: Assume $S=\>^i a^kXb^kc^jYd^j =\> a^{k'}Xb^{k'}c^{j'}Yd^{j'}$. We have 4 case for the last derivation step.

* if it was $X \rightarrow aXb$, then $k' = k+1$ and $S=\>^{i+1} a^{k+1}Xb^{k+1}c^jYd^j$
* Similar case if it was $X \rightarrow ab$, and then $S=\>^{i+1} a^{k+1}b^{k+1}c^jYd^j$
* If last derivation was $Y \rightarrow cYd$, then $j' = j+1$ and $S=\>^{i+1} a^{k}Xb^{k}c^{j+1}Yd^{j+1}$
* Similar case if it was $Y \rightarrow cd$, and then $S=\>^{i+1} a^{k}Xb^{k}c^{j+1}d^{j+1}$

Since $L(G1)$ contains terminal words, the last derivations must be $X \rightarrow ab$ or $Y \rightarrow cd$.

By that we proved that $L(G1) \subseteq \\{ a^nb^nc^md^m | n,m \> 0\\}$
> 2 votes

---
Tags: formal-grammars, proof-techniques, induction
---


# Question
Title: What happens if the holder of a lock tries to acquire a lock?
In a system, suppose there is a process and a resource with only one instance.

Let us assume that the process holds the instance and requests the same instance of that resource. Will there be a deadlock? Under what circumstances?

# Answer
> 4 votes
Resources that can only be used by a single process at a time are usually protected by a lock. If the process that currently holds the lock attempts to acquire it a second time, what happens depends on the type of lock.

* If the lock is reentrant, then it can be acquired multiple times by the same process. The process will need to call the release function as many times as it called the acquire function.
* If the lock is not reentrant (for example if it's a simple semaphore or an atomically-modified boolean), then a second attempt will block. You can call this a single-process deadlock.
* In some mutex implementations (probably not in what is studied in Concurrency 101 though), a process can acquire the same lock more than once, and the second time is a no-op, so the process must only call the release function once. Another thing that sometimes happens is that calling the acquire function from the same process twice puts the implementation in a bad state after which anything can happen — the semantics doesn't define what happens in that case.

Thus, it depends on what semantics your locks have. You can build non-reentrant locks on top of reentrant locks or vice versa if all you have is the wrong kind for what you want to do.

---
Tags: concurrency, mutual-exclusion, deadlocks
---


# Question
Title: Working out the connectives (And, Or, Not) in a Truth Table that has the outputs
I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g

* **P | Q | Output**
* 1 | 1 | 1
* 1 | 0 | 0
* 0 | 0 | 0
* 0 | 1 | 0

I need to find the logical operators and connectives (and, or, not, implies etc.) that is equivalent to the output. Please guide me through the steps or teach me how to work out how to do this. Thanks.

---

---

# Answer
Generally speaking, there is no unique boolean function $f(p, q)$ that produces your output. For your example, the function $f(p, q) = p$ would be a valid solution, as well as $f(p, q) = (p \vee q) \wedge (p \vee \neg q)$, and $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$. You can find an equisatisfiable function to the one that produced the given output, and there are a number of approaches to do so.

A simple approach would be the enumeration of variable constellations that produce $\top$, and disjunct them. For your example that would mean first finding the constellations that produce $\top$:

* $p \wedge \neg q$
* $p \wedge q$

and finally producing $f(p, q) = (p \wedge q) \vee (p \wedge \neg q)$

This way you produce a function in disjunctive normal form (DNF). A similar approach works for CNF, but in both cases you end up with a fairly large function.

More complex approaches are Karnaugh Maps and the Quine McCluskey algorithm. They can produce much more concise, even minimal equisatisfiable functions.

As far as I know, most approaches focus on CNF (and sometimes DNF), i.e. use only conjunctions, disjunctions and negations, and don't nest operators any further.
> 1 votes

# Answer
The formula that produces your truth table is: $P$ (which you might also be calling $A$). More generally, you can produce the CNF and DNF representations, which in this case are $(P \lor Q) \land (P \lor \lnot Q)$, $(P \land \lnot Q) \lor (P \land Q)$ respectively. There is an algorithm for producing them that you might have learned in class.
> 0 votes

---
Tags: algorithms, logic
---


# Question
Title: Dynamic programming to find the least possible balance of a full binary tree
I am given $n$ positive integers $x\_1,x\_2,\cdots,x\_n$ as input. These are the weights of the leaves in a full binary tree, $x\_1$ being the leftmost leaf and $x\_n$ the rightmost leaf. The weight of an internal node $v$ is defined as the sum of weights of the leaves in the subtree rooted at $v$. The balance of an internal node is defined as the larger ratios of the weights of its two children. The balance of a tree is the maximum of the balances of its internal nodes.

I need to find the least possible balance of any full binary tree with $x\_1,x\_2,\cdots,x\_n$ as the weights of its leaves. I don't need to output the tree, just the value.

I am having trouble finding the sub-problems. I have tried doing some examples, say the input is: $(5, 4, 3, 4, 4)$. I found the least possible balance of this to be $1.5$ by drawing all the possible trees. The tree that I ended up with is below and I put the balance beside each internal node:

For the example input, a smaller sub-problem would obviously be $(4,3,4,4)$, but I don't see how knowing the least possible balance of that helps me find the least possible balance of the tree with leaves $(5, 4, 3, 4, 4)$. I tried finding the balance for $(4,3,4,4)$ which came to be $1.33$. The tree I ended up with is:

I am looking for some hints as to what the sub-problems might be.

# Answer
You should think about how your binary tree can be arranged. For each tree you have some nodes $x\_1,\dots,x\_k$ to the left and some $x\_{k+1}, \dots, x\_n$ to the right of the root. Now, the best possible imbalance for that root will be the arrangement that gives you the smaller ratio. So, you have to figure out a way of doing this evaluation in every internal node of your tree (considering the subtree rooted there). Another tip is to consider growing your tree while preserving the minimum imbalance. The "matrix-chain" problem is quite similar to this one, so you should take a look at it too. Good luck.
> 2 votes

# Answer
The crucial fact is that you are given the leaves *in order*. The obvious way to use dynamic programming is to compute for all $i,j$ the best tree which has leaves $x\_i,\ldots,x\_j$ in order. This leads to an $O(n^3)$ algorithm. I'll let you think over the details.

If you remove the constraint that the leaves are ordered, then the problem looks much harder, and is probably NP-complete. A dynamic programming approach would consider all subsets and would take time $\tilde{O}(2^n)$, which is better than exhaustive search.
> 1 votes

---
Tags: algorithms, dynamic-programming, binary-trees
---


title: Balancing a Binary Search Tree

text:
# Question
Title: Balancing a Binary Search Tree
I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it can be valid like this but surely the "8" could branch to "13" instead, then "10" and "14" could become the descendants of "13". It seems like this would be far more balanced. So I researched around for more information about binary search tree balancing and I'm still unsure. Why is the diagram in the Wikipedia article was favored? Is my suggestion wrong?

Depth-first in-order traversal still works as I presume the same for all other traversal methods.

# Answer
> 5 votes
Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the tree one-after-another without balancing. So in your example first the $10$ was inserted, then the $14$, then $13$. Of course there are plenty of other algorithms that balance the tree (they are also linked in the Wiki-article).

# Answer
> 0 votes
Yes, @john\_leo is right. I like to add to his answer.

When one is interested in building balanced trees, one usually does not insist on the best balanced tree, with completely filled levels except the last level. When building balanced trees one adds some "slack" in the definition to avoid excessive rebalancing every addition. As an example, I add a picture of an AVL-tree (with its balance factors) that is within the limits imposed by the definition.

The purpose of various types of *balanced* search trees is to keep performance (adding, deleting, searching) within logarithmic time.

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: Does a coin tossing algorithm terminate?
Suppose we have an algorithm like:

```
n = 0
REPEAT
  c = randomInt(0,1)
  n = n + 1
UNTIL (c == 0)
RETURN n

```

(Assumuing the random number generator produces "good" random numbers in the mathematical sense.)

I understand that there is no number $n \in \mathbb{N}$ such that the algorithm is guaranteed to terminate after fewer than $n$ steps. However, the probability of terminating after *some* finite number of steps is 1.

Is there a convention among computer scientists to call an algorithm like this either "terminating" or "non-terminating"?

# Answer
The formal, unambiguous way to state this is “terminates with probability 1” or “terminates almost surely”. In probability theory, “almost” means “with probability 1”.

For a probabilistic Turing machine, termination is defined as “terminates always” (i.e. whatever the random sequence is), not as “terminates with probability 1”. This definition makes decidability by a probabilistic Turing machine equivalent to decidability by a deterministic Turing machine supplied with an infinite tape of random bits — PTM are mostly interesting in complexity theory. In applied CS, though, computations that always give the correct result but terminate only with probability 1 are a lot more useful than computations that may return an incorrect result.
> 11 votes

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


title: Property of two ANEAs is in NP

text:
# Question
Title: Property of two ANEAs is in NP
I have two arbitrary acyclic nondeterministic finite automata $\mathcal{A\_1}$ and $\mathcal{A\_2}$ and want to show that the problem $L(\mathcal{A\_1}) \not \subseteq L(\mathcal{A\_2})$ is in NP by specifying a polynomial proof system.

We defined a polynomial proof system in the following way:

For $L \subseteq \Sigma^\*$ the relation $R \subseteq \Sigma^\* \times \Gamma^\*$ is a proof system for $L$ if $(w,b) \in R \Rightarrow w \in L$ and $w \in L \Rightarrow \exists b \in \Gamma^\*: (w,b) \in R$. $R$ is polynomial if there is a polynomial $p$ with $|b| \le p(|w|)$ for all $(w,b) \in R$ and $R \in P$.

Unfortunately I have no idea how to get the relation and any help would be appreciated.

# Answer
Hint: Suppose that $\mathcal{A}\_1$ has $n$ states. Since it is acyclic, all the words it accepts have length at most $n-1$ (why?). Therefore if $L(\mathcal{A}\_1) \nsubseteq L(\mathcal{A}\_2)$ there must exist a word $w$ of length at most $n-1$ that $\mathcal{A}\_1$ accepts but $\mathcal{A}\_2$ rejects.
> 2 votes

---
Tags: complexity-theory, finite-automata, decision-problem, np
---


# Question
Title: Best sort method for median: median heap or insertion sort on a vector
I'm trying to decide between two methods of calculating a median, that will optimize the following operations:

* Add integer to data structure (insert)
* Get the median of all integer (getMedian)

The program will add a random number of integers (no limit on how many, but generally going to be relatively small amount) to the data structure before trying to access the median, and then repeat this process an indefinite amount of times.

With the median heap method, insert will take O(log(n)) on average and getMedian will be O(1).

What I'm wondering is what would happen if instead I simply used a vector. Insert would be amortized O(1). Then when getMedian is called, the vector is sorted with insertion sort, followed by simply accessing the middle element, O(1).

Would this be faster in the long run? There will almost always be more calls to insert than getMedian in the program, but I'm not sure if the insertion sort will be faster. I believe it is a relatively fast sort, O(n), on a partially sorted array, but I'm not sure.

For instance, if I had a vector with 100 million integers that were sorted followed by 4 unsorted elements, would insertion sort be O(n)? What if I had 50 million unsorted elements (very unlikely in the program, but possible)? And at how many unsorted elements would it be better to use another sort, like quicksort?

# Answer
> 1 votes
You are asking many questions, and I will only answer two of them. If you have a sorted vector of length $n$ followed by $m$ unsorted elements, the best way to sort the entire vector is to use an $O(m\log m)$ sorting algorithm on the tail, and then merge the two sorted lists in $O(n+m)$. The total running time is $O(n+m\log m)$, which is $O(n)$ if $m = O(n/\log n)$. If $m = \omega(n/\log n)$ then the problem is more complicated; asymptotically optimal bounds are known in the decision tree model, but I'm not sure they can be implemented efficiently enough (see for example Kahn ad Kim, Entropy and Sorting).

Another question, which you haven't actually asked, is about lower bounds. Suppose that you have a data structure in which *insert* takes (amortized) time $\alpha(n)$ and *median* takes (amortized) time $\beta(n)$, where $n$ is the number of elements in the structure. Suppose further that $\alpha(O(n)) = O(\alpha(n))$ and $\beta(O(n)) = O(\beta(n))$, and that $\alpha,\beta$ are monotone (this is the case for functions of the type $\Theta(n^s\log^t n)$). Then $\alpha(n) + \beta(n) = \Omega(\log n)$, assuming the operations are implemented using the comparison model (two datums can be compared, but are otherwise completely opaque).

For the proof, here is how to sort a list of length $n$. First insert the list. Then, extract the median, add $-\infty$ (or the minimum value) twice, and repeat. You recover the sorted lower half of the list. Now add enough copies of $+\infty$ (or the maximum value), and recover similarly the upper half of the list. This requires at most $O(n\alpha(O(n)) + n\beta(O(n))) = O(n(\alpha(n)+\beta(n)))$. In the comparison model, there is a lower bound of $\Omega(n\log n)$, so $\alpha(n) + \beta(n) = \Omega(\log n)$.

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


# Question
Title: If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?
If all infinite r.e. languages have an infinite recursive subset, then can we logically take co-r.e. languages to not have such subsets by complemence?

# Answer
In one word: no. It doesn't follow logically. It is also definitely not the case that no infinite co-r.e. language can have infinite recursive subsets: every infinite recursive set, say $0^\*$, is also r.e. and co-r.e.

It is easy to show that any infinite r.e. set contains an infinite recursive subset: run the enumerator and accept a word if it is longer than any previously accepted word. This approach doesn't work for co-r.e. sets, and leads to the conjecture that there exists an infinite co-r.e. set that doesn't contain an infinite recursive subset. When trying to prove this using diagonalization, we see that since there is no way of distinguishing infinite recursive sets from infinite r.e. sets, the property we are after is an infinite co-r.e. set that doesn't have any infinite r.e. subset.

It is not too difficult to prove that such sets, called *co-simple*, exist, following the footsteps of Post (1944). Instead of constructing an infinite co-r.e. set which doesn't have an infinite r.e. subset, we will construct a co-infinite r.e. set $S$ which intersects every infinite r.e. set. Simulate all Turing machines, and for Turing machine $e$, put in $S$ the first $x \> 2e$ such that $e$ halts on $x$ (if any); here we think of $e,x$ as integers. This is clearly an r.e. set, which clearly intersects every infinite r.e. set. It is co-infinite since for every $n$, we put in $S$ at most $n/2$ integers, at most one from each of the programs $1,\ldots,n/2$.
> 5 votes

---
Tags: computability
---


title: If P = NP, then is NP = FNP?

text:
# Question
Title: If P = NP, then is NP = FNP?
I read

> FP = FNP iff P = NP

which makes sense.

But if P = NP, does it mean FNP = NP?

Intuitively, I think no because P = NP would mean that decision problems in NP would become decision problems in P. But I don't see how that would reduce search problems to decision problems.

# Answer
> 5 votes
No, it doesn't mean that FNP = NP. NP is a class of decision problems; FNP is a class of function problems. See the definition of FNP (e.g., on Wikipedia, or in any textbook). Therefore, the elements of NP have a different type than the elements of FNP.

It's like asking whether the set of tart apples is equal to the set of seedless oranges; one is a set of apples, the other is a set of oranges, so they're certainly not equal, and you don't need to know anything about exactly which apples are tart or which oranges are seedless to know that.

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


# Question
Title: Extract Max for a max-heap in $\log n + \log\log n$ comparisons
Given a **max heap** with **extract-max** operation.

The basic version takes $2 \log n$ comparisons. How can I make the running time just $\log n + \log\log n$ comparisons? How about $\log n + \log\log\log n $ comparisons?

I thought of putting $-\infty$ on the heap root but not really sure what to do with it as it can go anywhere.

To be more precise, I'm only counting comparisons between array item values. I'm reading CLRS Chapter 6 (**MAX-HEAPIFY** and **HEAP-EXTRACT-MAX**).

# Answer
Elmasry et al. discuss reducing the number of comparisons for extract-max to $\log n + o(\log n)$ in "A Framework for Speeding Up Priority-Queue Operations". See also Elmasri's "Layered Heaps", Edelkamp et al.'s "Two Constant-Factor-Optimal Realizations of Adaptive Heapsort", Carlsson's "An optimal algorithm for deleting the root of a heap", and Gonnet and Munro's "Heaps on heaps".
> 5 votes

# Answer
Explanation for log n + log log n comparisons:

1) First, remove the max element from the heap, leaving a hole at the root.

2) Next, remove the last element of the heap (at the bottom right), and hold it in a temp.

3) Reconstruct the heap by iteratively replacing the hole with the greater of its 2 children. This loop takes log n comparisons (comparing the children at each level of the tree). Here is an example implementation:

```
p = root;
while (p->left != NULL) {
    if (p->right == NULL || p->left->val > p->right->val) {
        p->val = p->left->val;
        p = p->left;
    } else {
        p->val = p->right->val;
        p = p->right;
    }
}

```

4) Now, you have a hole at the bottom of the heap, and you have an element that you removed in step #2. Insert the element into the hole. This element needs to be fixed because it could be greater than its parent.

5) Fix the heap in log log n time. Where you inserted the element, if you take all of its parents, it forms a sorted list of log n elements. You can do a binary search to find the correct position of the inserted element in this list of parents. This takes log log n comparisons (binary search in a log n list). Once you find the position, you can insert the element in the correct place, moving the rest of the elements down.

Total number of comparisons: log n (step 3) + log log n (step 5)
> 7 votes

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


# Question
Title: Where does the terminology of open addressing resp. closed hashing come from?
One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books).

Why the names "open" and "closed", and why these seemingly contradictory names for the same method?

# Answer
The short answer is that the terms were coined by different people for different purposes, and it's because hash tables historically had two different contexts: in-memory data structures (I believe that compiler symbol tables was one of the first "killer app" uses) and external-memory data structures (file-based databases).

According to Knuth, the first mention of hashing in the literature is from an internal IBM memo from 1953, and it describes hashing with separate chaining. I don't have a copy of the memo, so I don't know what it was used for. I also don't know (possibly nobody does) who coined the term "closed hashing", but it makes sense to me that with "closed hashing" everything is stored in the table itself, with no need for secondary data structures to do collision resolution. In that sense, the hash table is "closed". From the context, it seems that this was an in-memory use.

We do know who coined the term "open addressing scheme". It's from W.W. Peterson's 1957 paper *Addressing for Random-Access Storage* (IBM Journal of Research and Development 1.2), though the idea goes back a bit further. The context here is clearly searching in files. The addressing scheme that Peterson analysed was "open", as opposed to "structured" (e.g. sorting the data and using binary search).
> 5 votes

---
Tags: terminology, data-structures, reference-request, hash-tables
---


title: Time/Space cost of Taxicab algorithm?

text:
# Question
Title: Time/Space cost of Taxicab algorithm?
The following is an algorithm for generating "Taxicab numbers" using a priority queue (`pq`). `Vector` is an arbitrary data type that allows for storage of two number and their cubed sum. For those unaware (although you really don't need to know), a taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: $a^3+b^3 = c^3+d^3$. An example would be $1729 = 12^3 + 1^3 = 10^3 + 9^3$.

```
for i = 1..n
 pq.insert( Vector(i^3+i^3,i,i) )

prev = Vector(0, 0, 0)

while not pq.empty()
 curr = pq.deleteMin()
 if prev[0] == curr[0]
      print curr[0] is a Taxicab number that can be expressed as
      prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3
 prev = curr
 if curr[2] < N
     j = curr[2] + 1
     pq.insert( Vector(curr[1]^3 + j^3, curr[1], j) )

```

I know inserting an item into the priority queue is $O(\log n)$ but I am not sure how this relates to space usage and runtime. Can someone help?

# Answer
> 1 votes
If you think about this program, you will realize pretty quickly that the vectors you're pushing onto the stack iterate over the values `[a^3 + b^3, a, b]` for all $1\leq a, b\leq N$ This means you're pushing $N^2$ items onto the stack over the course of the program.

Since each removal (and push, depending on the implementation of the PQ) takes $\Theta (\lg N)$ time, your algorithm would run in $\Theta (N^2\lg N)$ time. There's a straightforward $\Theta (N^2)$ solution, so you're not optimal yet.

---
Tags: algorithm-analysis, runtime-analysis, space-analysis
---


# Question
Title: The language of any constant-time Turing machine is regular
> Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular.

This seems to be a pretty well-known fact, but despite my research, I cannot seem to find a proof of this anywhere. Does someone know of one?

# Answer
Hint: If the machine runs in time $t$ on all inputs then its decision only depends on the first $t$ symbols of the input.
> 3 votes

---
Tags: formal-languages, turing-machines, regular-languages
---


title: Are there any coP problems

text:
# Question
Title: Are there any coP problems
Is there a notion of coP problem?

Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?

# Answer
Take it as an exercise to prove that P=coP. In fact, any deterministic computation model is closed under complement.

Regarding your second question, P-completeness is a well-studied notion, and there are even books on it. We say that a problem in P is *P-complete* if every problem in P is logspace-reducible to it. Assuming that NC is different from P, any P-complete problem is not in NC. Back in the day, the class NC was considered to represent what can be solved in parallel, so P-complete problems were interesting since they provably (under the assumption that NC is different from P) couldn't be solved in parallel. Nowadays this interpretation of NC is less popular.

You might be tempted to define P-completeness the same way NP-completeness is defined, that is, using polytime reductions. However, under this definition all non-trivial problems in P are P-complete, the two sole exceptions being the empty language and its complement, another simple exercise.
> 5 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, polynomial-time
---


# Question
Title: Does $f(n) + g(n) = O(g(n) \cdot f(n))$ hold?
I would like to know if this statement is true: $f(n) + g(n) = O(g(n)\cdot f(n))$.

I thought of giving a counter example by defining: $f(n) = 3n^2$ ; $g(n) = n$ which will give us that $O(3n^3) = n^3$ but i'm not sure if it's possible to say that $O(3n^3) = 3n^2 + n$ because I suspect that it might be right because of the definition of Big O. And if that's right that means that the counter example i gave is not good.

Is this a valid approach?

# Answer
I don't get what you do with your choice of $f$ and $g$ but they don't work as a counter-example.

Here is how you see that:

$\qquad f(n) + g(n) = 3n^2 + n \in \Theta(n^2) \subseteq O(n^3) = O(f \cdot g)$.

See our reference question on how to show this.

It is easy to see that the same happens for all pairs of increasing functions:

$\qquad f+g \in \Theta(\max(f,g)) \subseteq O(f \cdot g)$.

So if you want to have a chance at disproving the claim, you'll have to look for *decreasing* functions -- if your definition of Landau symbols admits such.
> 4 votes

# Answer
For your choice of $f,g$ the statement is correct: $3n^2 + n = O(3n^3)$. However, if you choose $f(n)=g(n)=1/n$ then $f(n)+g(n)=2/n$ while $f(n)g(n) = 1/n^2$, the latter being much smaller.
> 3 votes

# Answer
An easy counterexample would be:

```
f(n) = 1/n
g(n) = n

```

Then:

```
f(n) + g(n) = (n + 1/n)  = O(n)

```

Note that:

`O(f(n) * g(n))` is `O(1)` which is not the same as the above.

(This is based on the mathematical notion of `O(n)`.)
> 1 votes

# Answer
I'd like to clarify first that Big O notations aren't tighter bounds and hence,you are free to assume that

```
f(x) = x^2 + 2x + 4
     = O(x^2)
     = O(x^3)... and so on...

```

As an example, n² + 3n + 4 is O(n²), since n² + 3n + 4 \< 2n² for all n \> 10 (and many smaller values of n). Strictly speaking, 3n + 4 is O(n²), too, but big-O notation is often misused to mean "equal to" rather than "less than". The notion of "equal to" is expressed by Θ(n).

So,if you're going with the misuse, then your definition doesn't hold as posted by `user 1952500`. But,if you're going with the exact definition, then your example is well valid and hence, it satisfies the formula...

Now,coming to actual practice, we should go with the formal definition which will be always verified as

```
f(n) + g(n) = O(max(f(n) , g(n)))  // maximum in terms of power of n.

```

Also, O(max(f(n) , g(n))) \<= O(f(n)\* g(n)) // this is a generalised result and will always be correct as understood by your example...

One more thing to make others understand is f(x^-n) is always considered to be O(1).
> 0 votes

---
Tags: asymptotics
---


title: 3SAT analogous problem in P

text:
# Question
Title: 3SAT analogous problem in P
Is there a problem like 3 SAT like problem in P where if we find an algorithm for this problem, we can solve all problems in P?

For instance if we solve this problem in P, may be we can solve prime detection quickly instead of using AKS algorithm or linear programming quickly?

# Answer
You might find Greenlaw, Hoover and Ruzzo's "Limits to Parallel Computation: P-Completeness Theory" interesting. It obviously goes a lot further than the limits of this question, but most pertinently includes in Appendix A a compendium of P-complete problems in the style of Garey & Johnson. There are far too many to be worth listing here, but some key ("interesting") problems are:

* The Circuit Value Problem
* Linear Inequalities (this is one way to get a decision version of Linear Programming)
* Maximum Flow
* Context-free Grammar Membership
* Point Location on a Convex Hull
> 6 votes

# Answer
Just like you perhaps know **NP**-completeness, you can consider **C**-completeness, for a complexity class **C**. Indeed, a problem **X** is **P**-complete if (1) **X** is in **P**, and (2) every problem in **P** reduces to **X** with a suitable reduction. For instance, linear programming is **P**-complete. From the world of logic, HORN-SAT is **P**-complete.
> 4 votes

# Answer
Yes, there are **P**-complete problems just as there are **NP**-complete problems. Wikipedia has an article on this, which gives several examples, such as the circuit value problem (determining whether a given Boolean formula is true or false for given values of the variables).

However, the existence of such problems doesn't necessarily give you new, more efficient algorithms for problems in **P**. A simple version of the time hierarchy theorem says that there are problems that, for all constants~$k$, can be solved in time $O(n^{k+1})$ that *cannot* be solved in time $O(n^k)$. Using reductions doesn't get around this. For example, to solve a problem that requires time $n^5$ by reduction to a complete problem that can be solved in time $n^2$ would require a reduction that increased the length of the input to about $n^{5/2}\\!$, and the whole process would therefore still take time $n^5\\!$.

As usual, there's no free lunch.
> 4 votes

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


title: Composition for Functional Depedencies

text:
# Question
Title: Composition for Functional Depedencies
Suppose I have the following Functional Dependencies for a Relational Model:

> $A \to C$
>
> $B \to C$

According to the composition rule for functional dependencies we have:

```
If X → Y and Z → W, then XZ → YW

```

For the case above would it be correct to say:

> $AB \to CC$

Leads to:

> $AB \to C$

Would the composite $CC$ be the same as just $C$? And for a relational model would it be proper to separate $C$ into a relation such that $AB$ is the Primary Key? Or should I simply drop either of the relations $A \to C$ or $B \to C$?

I was told by my database professor that $AB \to C$ is wrong and I should dropped one of them when I have created a Logical Data Model. But I don't understand how what I said above is wrong.

# Answer
> 0 votes
In a relational model, CC would be redundant, it's like saying that 1 = 1 * 1. Using a real example, if A = person ID, B = person fingerprint, C = person name, then you would say that "given a person ID and fingerprint, the name of a person is Bob, Bob is the name of the person". Thus, I would argue that AB -\> CC and AB -\> C are equivalent, and the composition AB -\> CC is not necessary.

given both A -\> C and B -\> C, then If you know did a search for "Bob" in the database, you would get both results for person ID's and person fingerprints. If fingerprints are stored together with person ID's, this means that your search result has one redundant entry for every result. Therefore it is much better design to only have the relation A -\> C or B -\> C to reduce the number of lookups. If A and B are in seperate entities, however, you might want both relations.

If you *only* specify AB -\> C, you would not be able to use A -\> C or B -\> C, which are both true. Therefore you should not put this statement alone. However, if A -\> B and B -\> A, it might be valid, but usually inefficient. Now, to find AB given C (searching for all relations that match "Bob"), you need to lookup both person ID and person fingerprint, and match these two together (checking if A -\> B or B -\> A). It is faster to just check one attribute (look for only A or B, not both).

---
Tags: database-theory
---


# Question
Title: Find all neighbors at a certain distance, in 3 dimensions
I have two algorithms which I would like to implement:

First, given a (very long) list $\\{\mathbf{r}\_{i}\\}\_{i=1}^{n}\subset \mathbb{R}^{3}$, a point $p \in \mathbb{R}^{3}$, and a distance $d\>0$, find all $i$ such that $|\mathbf{r}\_{i} - \mathbf{p}| \< d$.

Currently, I sort the list over the $x$-coordinate, so that if $x\_{i}$ is the $x$-coordinate of $\mathbf{r}\_{i}$, then $x\_{1} \le x\_{2} \le \cdots \le x\_{n}$. Then I use the condition $(x\_{i}-\mathbf{p}\_{x})^{2} \> d^2 \implies |\mathbf{r}\_{i} - \mathbf{p}|^2 \> d^{2}$. This allows me to filter the list by binary search. This leaves me with a subset $\\{\mathbf{r}\_{i}\\}\_{i=j\_{1}}^{i=j\_{2}}$ of the original list where for all $i \in \[j\_{1}, j\_{2}\]$, $(x\_{i}-\mathbf{p}\_{x})^{2} \<= d^2$. Then I have to bite the bullet and do an explicit test on each one of these to see if $|\mathbf{r}\_{i} - \mathbf{p}| \< d$.

This algorithm strikes me as weird and not optimal; is there a better way?

Next: A related problem: Given a list $\\{\mathbf{r}\_{i}\\}\_{i=1}^{n}\subset \mathbb{R}^{3}$ and a point $\mathbf{p} \in \mathbf{R}^{3}$, find $j \in \[1,n\]$ such that $d\_{j}:=|\mathbf{r}\_{j} - \mathbf{p}| = \min\_{i} |\mathbf{r}\_{i} - \mathbf{p}|$. Is there an efficient algorithm to find $j$?

Finally, I should note that any one-time \`\`sorting'' expense is tolerable, since this operation is repeated many times.

# Answer
> 2 votes
I recommend using a k-d tree or an octree to store the list of points. They support efficient nearest neighbor search.

If you need to update the list, look at R-trees, which allow your list to be dynamic: you can add or delete from the list and efficiently update the R-tree data structure.

# Answer
> 0 votes
The best solution for this problem would be to use a grid. Round every point down by 1/d and then when you query just search all buckets containing the query sphere.

---
Tags: algorithms, computational-geometry, search-algorithms
---


title: Is there an anti-Bloom filter?

text:
# Question
Title: Is there an anti-Bloom filter?
A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in a significant memory saving over a hash table. The main feature of a Bloom filter, which it shares with a hash table, is that it always says "not new" if an item is not new, but there is a non-zero probability that an item will be flagged as "not new" even when it is new.

> Is there an "anti-Bloom filter", which has the opposite behaviour?

In other words: is there an efficient data structure which says "new" if an item is new, but which might also say "new" for some items which are not new?

Keeping all the previously seen items (for instance, in a sorted linked list) satisfies the first requirement but may use a lot of memory. I am hoping it is also unnecessary, given the relaxed second requirement.

---

For those who prefer a more formal treatment, write $b(x) = 1$ if the Bloom filter thinks $x$ is new, $b(x) = 0$ otherwise, and write $n(x) = 1$ if $x$ really is new and $n(x) = 0$ otherwise.

Then $Pr\[b(x) = 0 | n(x) = 0\] = 1$; $Pr\[b(x) = 0 | n(x) = 1\] = \alpha$; $Pr\[b(x) = 1 | n(x) = 0\] = 0$; $Pr\[b(x) = 1 | n(x) = 1\] = 1 - \alpha$, for some $0 \< \alpha \< 1$.

I am asking: does an efficient data structure exist, implementing a function $b'$ with some $0 \< \beta \< 1$, such that $Pr\[b'(x) = 0 | n(x) = 0\] = \beta$; $Pr\[b'(x) = 0 | n(x) = 1\] = 0$; $Pr\[b'(x) = 1 | n(x) = 0\] = 1 - \beta$; $Pr\[b'(x) = 1 | n(x) = 1\] = 1$?

---

**Edit:** It seems this question has been asked before on StackExchange, as https://stackoverflow.com/questions/635728 and https://cstheory.stackexchange.com/questions/6596 with a range of answers from "can't be done" through "can be done, at some cost" to "it is trivial to do, by reversing the values of $b$". It is not yet clear to me what the "right" answer is. What *is* clear is that an LRU caching scheme of some sort (such as the one suggested by Ilmari Karonen) works rather well, is easy to implement, and resulted in a 50% reduction in the time taken to run my code.

# Answer
Going with Patrick87's hash idea, here's a practical construction that *almost* meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can be easily made negligibly small.

Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$. Let $H$ be a secure cryptographic hash function producing (at least) $n+k$ bits of output.

Let $a$ be an array of $2^k$ $n$-bit bitstrings. This array stores the state of the filter, using a total of $n2^k$ bits. (It does not particularly matter how this array is initialized; we can just fill it with zeros, or with random bits.)

* To add a new value $x$ to the filter, calculate $i \\,\\|\\, j = H(x)$, where $i$ denotes the first $k$ bits and $j$ denotes the following $n$ bits of $H(x)$. Let $a\_{i} = j$.
* To test whether a value $x'$ has been added to the filter, calculate $i' \\,\\|\\, j' = H(x')$, as above, and check whether $a\_{i'} = j'$. If yes, return true; otherwise return false.

**Claim 1:** The probability of a false positive (= new value falsely claimed to have been seen) is $1/2^{n+k}$. This can be made arbitrarily small, at a modest cost in storage space, by increasing $n$; in particular, for $n \ge 128$, this probability is essentially negligible, being, in practice, much smaller than the probability of a false positive due to a hardware malfunction.

In particular, after $N$ distinct values have been checked and added to the filter, the probability of at least one false positive having occurred is $(N^2-N) / 2^{n+k+1}$. For example, with $n=128$ and $k=16$, the number of distinct values needed to get a false positive with 50% probability is about $2^{(n+k)/2} = 2^{72}$.

**Claim 2:** The probability of a false negative (= previously added value falsely claimed to be new) is no greater than $1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) \< N/2^k$, where $N$ is the number of distinct values added to the filter (or, more specifically, the number of distinct values added *after* the specific value being tested was most recently added to the filter).

---

**Ps.** To put "negligibly small" into perspective, 128-bit encryption is generally considered unbreakable with currently known technology. Getting a false positive from this scheme with $n+k=128$ is as likely as someone correctly guessing your secret 128-bit encryption key *on their first attempt*. (With $n=128$ and $k=16$, it's actually about 65,000 times less likely than that.)

But if that still leaves you feeling irrationally nervous, you can always switch to $n=256$; it'll double your storage requirements, but I can safely bet you any sum you'd care to name that nobody will *ever* see a false positive with $n=256$ — assuming that the hash function isn't broken, anyway.
> 15 votes

# Answer
No, it is not possible to have an efficient data structure with these properties, if you want to have a guarantee that the data structure will say "new" if it is really new (it'll never, ever say "not new" if it is in fact new; no false negatives allowed). Any such data structure will need to keep all of the data to ever respond "not new". See pents90's answer on cstheory for a precise justification.

In contrast, Bloom filters *can* get a guarantee that the data structure will say "not new" if it is non-new, in an efficient way. In particular, Bloom filters can be more efficient than storing all of the data: each individual item might be quite long, but the size of the Bloom filter scales with the *number* of items, not their total length. Any data structure for your problem will have to scale with the *total length* of the data, not the number of data items.
> 9 votes

# Answer
What about just a hash table? When you see a new item, check the hash table. If the item's spot is empty, return "new" and add the item. Otherwise, check to see if the item's spot is occupied by the item. If so, return "not new". If the spot is occupied by some other item, return "new" and overwrite the spot with the new item.

You'll definitely always correctly get "New" if you've never seen the item's hash before. You'll definitely always correctly get "Not New" if you've only seen the item's hash when you've seen the same item. The only time you'll get "New" when the correct answer is "Not New" is if you see item A, then see item B, then see item A again, and both A and B hash to the same thing. Importantly, you can never get "Not New" incorrectly.
> 6 votes

# Answer
In the case where the universe of items is finite, then yes: just use a bloom filter that records which elements are out of the set, rather than in the set. (I.e., use a bloom filter that represents the complement of the set of interest.)

A place where this is useful is to allow a limited form of deletion. You keep two bloom filters. They start out empty. As you insert elements you insert them into bloom filter A. If you later want to delete an element you insert that element into bloom filter B. There is no way to undelete. To do a lookup you first lookup in bloom filter A. If you find no match, the item was never inserted (with probability 1). If you do find a match the element may (or may not) have been inserted. In that case you do a lookup in bloom filter B. If you find no match, the item was never deleted. If you do find a match in bloom filter B, the item was probably inserted and then deleted.

This doesn't really answer your question, but, in this limited case, bloom filter B is performing exactly the "anti-bloom filter" behavior you are seeking.

Real Bloom filter researchers use much more efficient ways of representing deletion, see Mike Mitzenmacher's publication's page.
> 4 votes

# Answer
I just want to add in here, that if you are in the fortunate situation, that you know all of the values $v\_i$ that you might possibly see; then you can use a counting bloom filter.

An example might be ip-addresses, and you want to know every time one appears that you have never seen before. But it is still a finite set, so you know what you can expect.

The actual solution is simple:

1. Add all your items to the counting bloom filter.
2. When you see a new item, it will have values $\ge1$ in all slots.
3. After seeing an actual new item, subtract it from the filter.

So you might have 'false positives' values that were actually old, but recognized as new. However you will never get 'not new' for a new value, since its value will still be in all the slots, and nobody else could have taken that away.
> 1 votes

---
Tags: reference-request, data-structures, hash, bloom-filters, dictionaries
---


title: Type checking relation to logic

text:
# Question
Title: Type checking relation to logic
I am learning **logic and functional programming** and there is a topic called **Type checking and their relationship to logic** , I am unable to find any source that can help me in understanding this topic. Please help .

# Answer
https://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ \- This book.

A type for a parameter is like a precondition, and a type for a return value is like a postcondition. Structs function as an AND operator, and Unions function as an OR operator. When you say

performTransaction(x : DollarAmount) : Result

If x had to be constructed as a valid DollarAmount type, then this function is only callable if that was possible. Also, the Result type is guaranteed to have some fields on it (error codes, transaction id, etc); and performTransaction has to construct the object to give it to you. So, if you view statements like "x : int" as "x is proven to be an integer", then it is not a stretch to have something more elaborate like: " x : int, x \> 0, x \< MAXINTEGER " to assert that x is a positive integer (a DependentType is a type that depends on the value, typically notNull, notZero, etc).

You can make functions take in very specific types that indicate an initial state, and return new types that indicate new states; and use types to enforce constraints on following a state machine - at compile time in many cases.
> 2 votes

---
Tags: logic, type-checking
---


# Question
Title: How can it be decidable whether $\pi$ has some sequence of digits?
We were given the following exercise.

> Let
>
> $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$
>
> Prove that $f$ is computable.

How is this possible? As far as I know, we do not know wether $\pi$ contains every sequence of digits (or which) and an algorithm can certainly not decide that some sequence is *not* occurring. Therefore I think $f$ is not computable, because the underlying problem is only semi-decidable.

# Answer
> 146 votes
There are only two possibilities to consider.

* For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$. In this case, the algorithm that always returns 1 is always correct.
* There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$. In this case the following algorithm (with the value $N$ hard-coded) is always correct:

```
Zeros-in-pi(n):
 if (n > N) then return 0 else return 1

```

We have *no* idea which of these possibilities is correct, or what value of $N$ is the right one in the second case. Nevertheless, one of these algorithms is guaranteed to be correct. Thus, there is an algorithm to decide whether a string of $n$ zeros appears in $\pi$; the problem is decidable.

---

Note the subtle difference with the following proof sketch proposed by gallais:

> 1. Take a random Turing machine and a random input.
> 2. Either the computation will go on for ever or it will stop at some point and there is a (constant) computable function describing each one of these behaviors.
> 3. ???
> 4. Profit!

Alex ten Brink explains:

> watch out what the Halting theorem states: it says that there exists no single program that can decide whether a given program halts. You can easily make two programs such that either one computes whether a given program halts: the first always says 'it halts', the second 'it doesn't halt' - one program is always right, we just can't compute which one of them is!

sepp2k adds:

> In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is. 10

# Answer
> 17 votes
Just posting a slight elaboration on JeffE's answer.

We know that two functions/cases exist that can compute the function f(n):

1. A function that always returns true (for all n, there exist n number of consecutive 0's)
2. A function that will return true if n is smaller than an integer N, where N is defined as the maximum length of consecutive 0's that exist in the given irrational number (otherwise it returns false).

One and only one of these functions can be correct. We do not know which, but we know for certain that an answer exists. Computability requires that a function exist that can determine the answer within a finite amount of steps.

The number of steps in case 1 is trivially bound to just returning 1.

In case 2 the number of steps are also finite. For every integer $N$ we can construct a Turing machine $T\_N(n)$ that accepts if $n \< N$ and otherwise rejects in finite time. So not knowing an upper bound on $N$ doesn't matter. For every $N$ there exists a Turing machine, namely $T\_N(n)$, that computes correctly whether $n \< N$ (we don't know which of these are correct, but it doesn't matter, one exists).

While it may not be possible to choose between the two cases (though one seems more likely than another), we know that exactly one of them must be correct.

As a side note: our solution supposes that while we can not determine which function will elicit a correct value the essence of computability does not rely on the constructability of the proof. Pure Existence is sufficient.

# Answer
> 6 votes
Step 5 of the following proof attempt is unjustified, and in fact **wrong** \- a counterexample can be found here. (thanks, Yuval; it did feel like the sketchiest part of the sketch). I've left the answer here as I think the mistake is instructive.

---

First off: JeffE's pair of answers is sufficient; **f** is computable either way.

A brief detour, though, into an attempt at a sketch of a proof by induction:
Premise **R**: $\pi$ does not repeat.
1. Look at $\pi$ in base 2. This is mostly to cut down on the number of cases.
2. No matter how far down the line you go, you will always find another **1** somewhere: the alternative is all zeros, which would mean $\pi$ starts repeating, which goes against **R**.
3. Same goes for going down the line and finding **0**.
4. Expand to two-digit sequences: you can't stop finding either **01** or **10** (that is, places where it switches), because otherwise $\pi$ would start repeating on **1**'s or on **0**'s. Similarly, you can't stop finding **11** or **00**, because otherwise it starts repeating on **1010101**...
5. The inductive step: each finite sequence has to appear an infinite number of times, because the alternative is that $\pi$ starts repeating on one of the shorter sequences, which contradicts **R**.

---
Tags: computability, undecidability
---


# Question
Title: Does a greedy task selection algorithm find a c-approximate solution?
I was told this question may be better suited here.

> A scheduling problem can be stated as: Given a set $\\{(s\_i,f\_i)\\}\_{1\le i\le n}\\}$ of tasks identified by their start and end times, choose the maximum size subset of non-overlapping tasks. Choosing tasks greedily by earliest finishing time gives an optimal solution, but what about heuristics: earliest starting time, shortest length, and fewest incompatibilities? Does each heuristic find a $c$-approximate solution, for some constant $c$?

How do you typically solve problems like this? How can we know whether a $c$-approximate solution is found (i.e. a subset of tasks whose size is at least 1/$c$ of the optimum)? I don't see how we can bound a heuristic, it seems like there are a lot of possibilities for the answers that it will return.

For example, in the earliest start time heuristic, we can always guarantee that it will select one task (the first one- with earliest start time), but it doesn't seem like we can guarantee anything more.

For the shortest length, it seems like we can get closer to the optimal solution, and to me it seems like we can always guarantee that if the optimal solution is $m$ tasks, shortest length will select $m-1$ tasks.

# Answer
> 3 votes
The shortest-task-first heuristic is a 1/2-approximation algorithm.

For a tight example, image that a compatible set $\\{T\_i\mid 1\leq i\leq m\\}$ sorted by their finish time and the other shorter tasks $Y\_i$, $1\leq i\leq m/2$, such that $Y\_i$ overlaps with $T\_{2i-1}$ and $T\_{2i}$ for each $i$. The shortest-first heuristic finds $m/2$ tasks while the optimal solution contains $m$ tasks.

To show the approximation ratio: For any compatible set $T$ sorted by their finish time, a task in the approximation solution overlaps with at most two tasks in $T$ since it cannot contain any task as a sub-interval of it. In fact, you can always obtain a 2-approximation if you select no tasks \`\`covering'' another task.

---
Tags: algorithms, algorithm-analysis, approximation, greedy-algorithms, scheduling
---