# Question
Title: Given a regular language, show another language is regular
I was hoping someone could help me with this question, since I'm having trouble determining what approach to take.

Let $L \subseteq \\{0,1\\}^\*$ be a regular language. Show the language $\\{w \in \\{0,1\\}^\* | 1w \in L\\}$ is also regular.

My idea is that whenever we're at the start state to compensate for the lack of the 1, you do an additional transition as if 1 was part of the input and then carry on reading the input as normal.

Since L is regular it has a NFA that accepts it $(Q,\Sigma, \delta, q\_0, F)$. Then construct a new NFA $(Q,\Sigma, \delta', q\_0, F)$ such that $\delta'(q,a) = \delta(q,a)$ for $q \ne q\_0$ and $\delta'(q,a) = \delta(\delta(q,a),1)$ for $q = q\_0$

Is this correct?

# Answer
> 1 votes
Your idea is right.

However, in general the initial state $q\_0$ of a finite state automaton may also be used in other ways than just as a starting position, so the automaton may return to the state. Those later visits do not want to loose the letter $1$.

Are you sure the order $δ(δ(q,a),1)$ is correct?

# Answer
> -2 votes
we known that L is regular.

1w is a concactenation of 1 and w and is regular.(the concatenation of 2 regular language is regular) then w is Necessarily regular. I think. (Wait for the other answers to see)

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


# Question
Title: Can parameters other than $n$ be always ignored in big $O$ notation?
The Bentley–Ottmann algorithm, for example, has time complexity of $O((n + k) \log n)$. Is the statement $O((n + k) \log n) = O(n \log n)$ true? I know that $k$ is there because it has big enough of an impact on the overall time complexity that it's relevant to include it. But can it be ignored, so that the previously stated equivalence holds, and hence we can without any reservations say that the algorithm has time complexity of $O(n \log n)$?

# Answer
> 3 votes
In general you cannot erase things. A bivariate function $f$ is $O((n+k)\log n)$ if there exists a constant $C\>0$ such that for all legal settings of the parameters $n,k$, we have $f(n,k) \leq C(n+k)\log n$. Here a setting of parameters is *legal* if it can actually happen – for example, if $V,E$ are the number of vertices and edges in a simple graph, then we always have $E \leq V(V-1)/2$, any other setting being illegal. If in some context you know that $k \leq Bn$, then in that context (which restricts the set of legal settings of parameters) $f = O(n\log n)$. In any other context, you cannot drop the $k$.

In your particular case, the Bentley–Ottmann algorithm, it is generally not the case that $k = O(n)$, and so $k$ cannot be dropped.

---
Tags: algorithm-analysis, asymptotics, landau-notation
---


# Question
Title: the maximum value for which combination of merge sort and insertion sort works more efficiently than standard merge sort?
I'm totally new in algorithms and I have a hard time studying how to calculate the time complexity of algorithms.

I'm studying ***Introduction to Algorithms, by Cormen*** on my own. Iam doing an exercise and I faced a problem that I couldn't solved it. first, the book asks for *the worst time complexity of combination of merge sort and insertion sort*. I calculated it truly and the answer is **O(nk + nlg(n/k))**.

second, it says:

> Given that the modified algorithm runs in ***O(nk + nlg(n/k))*** worst-case time, what is the largest value of k as a function of n for which the modified algorithm has the same running time as standard merge sort, in terms of O notation?

this is the part that I have problem. I said the answer may be obtained in this way:

```
worst time complexity of standard merge sort = worst time complexity of modified merge sort

nlgn = nk + nlog(n/k)
k = 2 ^ k

```

but this can never happen and my answer is wrong. how should I solve the problem??

Thanks in advance.

# Answer
> 2 votes
Don't forget that big O notation hides constants. We want $nk + n\log(n/k)$ to be at most $Cn\log n$ for some constant $C\>0$. This means that $k + \log(n/k) \leq C \log n$, and so $k - \log k \leq (C-1)\log n$. You can check that this inequality holds (for some $C\>0$) if and only if $k = O(\log n)$.

---
Tags: algorithms, algorithm-analysis, time-complexity
---


# Question
Title: Logic, "and" operator between a set of formulas and a formula
Consider a set $S$ of formulas $\beta\_i$ and a formula $\alpha$, if we have a condition such as **$S \land \alpha$ is inconsistent** what we have to calculate to check the inconsistency of $S \land \alpha$? In other words, what is the result of $S \land \alpha$?

For example, $S=\\{\beta\_1, \beta\_2, \beta\_3\\}$

# Answer
A set $S$ of formulas (propositional logic) is **consistent** if there is a truth assignment under which all formulas in $S$ are *true*, in other words if there is a *model* of $S$. Alternatively, $\\{\beta\_1, \beta\_2, ..., \beta\_n \\}$ is consistent, iff $\beta\_1 \wedge \beta\_2 \wedge ... \wedge \beta\_n$ is satisfiable.

You could just find a truth assignment such that $\alpha \wedge \beta\_1 \wedge \beta\_2 \wedge \beta\_3$ is true. If the number of variables is small then you can check it by hand by creating a truth-table, or use Method of analytic tableaux. Also, note that the Satisfiability problem (SAT) is NP complete.

You can also use a resolution procedure to show that a formula is unsatisfiable (inconsistent).
> 1 votes

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


# Question
Title: Constructing Turing Machine for division with 8
Can someone help me to construct a Turing Machine for this function:

$f(n) = \frac{n}{8}$. If $n \mod 8 = 0$, then $f(n)$ is undefined.

So the machine should somehow first prove if the number (which is represented in binary) is divisible by $8$ . That means for numbers like $1000$, $10000$, $11000$ and so on. But I don't know how can I check this.

## EDIT:

The result from the division is when we delete the last 3 digits in the binary representation of the number. I think this is not so hard. But I still have a problem with the first part. How can I prove if the number is divisible?

# Answer
A number (in binary) is divisible by 8 if it ends at least by 3 0's. Remember that an integer is divisible by 2 (without remainder) if it ends with 0 and since $8=2^3$ its binary representation must end with at least 3 zeros.

In fact a finite automaton is enough to recognize numbers divisible by 8. The following transitions are for a DFA which can be easily rewritten as TM instructions.

$q\_1$ - start state, $q\_4$ - accept state.
$\delta(q\_1, 0) = q\_2, \delta(q\_1, 1) = q\_1$
$\delta(q\_2, 0) = q\_3, \delta(q\_2, 1) = q\_1$
$\delta(q\_3, 0) = q\_4, \delta(q\_3, 1) = q\_1$
$\delta(q\_4, 0) = q\_4, \delta(q\_4, 1) = q\_1$
> 0 votes

---
Tags: turing-machines
---


title: Is a KNN-Classifier memory intensive?

text:
# Question
Title: Is a KNN-Classifier memory intensive?
In my opinion it seems fairly obvious that a $k$ nearest neighbours (KNN) Classifier would be fairly expensive in terms of memory, as the model is the training set itself. However, any notes I've read have only mentioned that the KNN-Classifier is computationally expensive, and have not mentioned any memory requirements as a disadvantage. I assume this to be true, but I wouldn't want to mention it in any exams or anything without proper confirmation. Are the memory requirements implicit and not worth mentioning, or am I overlooking something?

# Answer
KNN is a memory intensive algorithm and it is already classified as instance-based or memory-based algorithm. The reason behind this is KNN is a lazy classifier which memorizes all the training set O(n) without learning time (running time is constant O(1)).

Inversely, When it comes to querying new points to find the nearest K, the query time will be expensive O(n) in terms of the running time.
> 2 votes

---
Tags: machine-learning, classification
---


# Question
Title: Fenwick Tree Traversal using Binary value of Index
Can someone explain me how do I execute sum query from Index 0 to Index I given the binary value of that Index I. There are some trivial question that I want to know :

1. Do we have to remove last set bit and all the bits following it.
2. How many times do I have to access the temporary array made for the data structure i.e Fenwicktree\[ \] array. I have been trying to think about these from the binary index of the Index I.

For eg I have the binary

> 001100100100100011

I removed the last set bit. I took 0 as left and 1 as right and traverse it . Whenever I take a right , I access the tree elements and accessing the array finally when I reach the node.So the count comes around around 6 times. But when I did the same with

> 1000110111011101100

The answer comes out to be 10 but the the number of times I access the array is ***12***. How do I get to this ? What am I missing out ? Is there a general way to calculate the number of times just looking at the binary value of Index ? Please help me out.

# Answer
> 2 votes
## Answering Question 2:

Simply count the number of 1's in the binary value.

This is part of the beauty of Fenwick trees, they're very simple to implement. The whole algorithm for finding the sum up to some index `i` is:

```
sum = 0
while i > 0:
    sum = sum + f_tree[i]
    i = i - (last set bit of i) // remove last set bit
return sum

```

At each step, we remove the last set bit from the index. Intuitively, the total amount of iterations is equal to however many set bits there are. You can find this in $O(\log i)$.

## Answering Question 1:

Yes you do need to remove the last set bit. That is implicit on the structure of the tree.

Let's say the last set bit of some index $i$ is bit $r$ (e.g. if $r = 0$ it is the least significant bit). The value in the Fenwick Tree at index $i$ is "responsible" for the sum of all values $\[(i - 2^r + 1) \dots i\]$.

Now let's say index $i$ has set bits $\\{r\_0, r\_1, \dots r\_k\\}$, that is, $i = \sum\_{j = 0}^k 2^{r\_j}$. We can then get the sum up to index $i$ in segments (iterations of the sum algorithm). Let $S\_n$ denote the range that the accumulating some covers after the $n$th iteration.

$$\begin{align} S\_0 & = \[(i - 2^{r\_0} + 1) \dots i\]\\ S\_1 & = \[(i - 2^{r\_0} - 2^{r\_1} + 1) \dots (i - 2^{r\_0})\] + \[(i - 2^{r\_0} + 1) \dots i\]\\ & \vdots\\ S\_k & = \[1 \dots 2^k\] + \dots + \[(i - 2^{r\_0} - 2^{r\_1} + 1) \dots (i - 2^{r\_0})\] + \[(i - 2^{r\_0} + 1) \dots i\] \\ S\_k & = \[1 \dots i\] \end{align}$$

### Example

This may be easier to visualize with an example. Take your first one for instance:

> 001100100100100011$\_2$ = 51491$\_{10}$

I'm not going to go through all the math, I encourage you to do that. This is, in short, how it would work out with a total of 7 iterations.

$$\begin{align} S\_0 & = \[51491 \dots 51491\]\\ S\_1 & = \[51489 \dots 51490\] + \[51491 \dots 51491\]\\ & \vdots \\ S\_6 & = \[1 \dots 32768\] + \dots + \[51489 \dots 51490\] + \[51491 \dots 51491\]\\ S\_6 & = \[1 \dots 51491\] \end{align}$$

---

A lot of this information came from this Topcoder Article on Binary Indexed Trees. I would highly recommend reading it if you have confusion with Fenwick Trees.

---
Tags: trees, binary-trees, strings, arithmetic
---


title: MSTs in Christofides Algorithm

text:
# Question
Title: MSTs in Christofides Algorithm
I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST\_1$ and $MST\_2$ where both are Minimum Spanning Trees, because $G$ contains more than one edge with the same weight.

In image \[\] below, the difference between $MST\_1$ and $MST\_2$ is basically the $Arlington \to Somerville$ or $Arlington \to Belmont$ (or vice-versa) connection. Depending on the internal representation of the graph, whether a adjacency matrix or list, this could happen by just altering which node will be the first, e.g. if $Arlington$ will be processed earlier than $Somerville$.

The difference of dealing with one or the other, is the next steps of Christofides algorithm, that requires to apply the Minimum-Weight Perfect Matching algorithm on the **odd nodes**.

The $MST\_1$ has only $4$ odd nodes and the perfect matching result is $Arlington \to Medford$ and $Cambridge \to Everett$, which I will call $MWPF\_1$. The $MST\_2$ has $6$ nodes and the perfect matching result is $Arlington \to Medford$, $Somerville \to Everett$ and $Belmont \to Cambridge$, which I will call $MWPF\_2$.

The next step from Christofides is to merge both edges from $MST$ with the ones from perfect matching.

Now, if we choose to merge both $MST\_1$ and $MWPF\_1$, we will end up with nodes only with even degrees that's what we want as the next step is to calculate the *Eulerian Circuit*.

But, if we choose $MST\_2$ and $MWPF\_2$, we will end up with only one new edge, as other two are already present ($Somerville \to Everett$ and $Belmont \to Cambridge$) in $MST\_2$. The result then will be $4$ odd vertices and no possible *Eulerian Circuit* can be generated out of this merge!

How this should be dealt in Christofides algorithm? Should all the $MSTs$ generated from one graph to be tried out?

# Answer
The important thing to note is that when merging the MST and the Matching, you create a *multigraph*. This means even when you merge, even if there are edges that already exist, you add them anyway. So you will *always* end up with even degree vertices.

This is step 4 of the algorithm as seen on Wikipedia.

So in your second case, you now have a multigraph where edges $(Somerville \rightarrow Everett)$ and $(Belmont \rightarrow Cambridge)$ each show up twice.
> 2 votes

# Answer
The analysis of Christofides' algorithm works for *any* MST. Hence any MST will get you the approximation guarantee of the algorithm.

More generally, if you really had to try out all possible MSTs, then the resulting algorithm wouldn't run in polynomial time, sine there could potentially be exponentially many MSTs.
> 1 votes

---
Tags: graphs, traveling-salesman, minimum-spanning-tree
---


title: Algorithm Basics

text:
# Question
Title: Algorithm Basics
What does "n" or "N" in asymptotic notation actually means? It is usually stated that the "n" is the size of the input. Does it mean that it is the size of the algorithm,that it the size of the whole chunk of algorithm,meaning if a algorithm has 20 lines it's "n" is more than a algorithm which have 10 lines.

# Answer
> 4 votes
The exact value of $n$ depends on the context. Most of the time $n$ is the length of the input in bits or in machine words. Note that the length of a number $x$ in bits is roughly $\log x$, since this is how many bits you need to encode $x$.

# Answer
> 3 votes
No, $n$ is, as you say, the size of the *input* – the data you're working on. Nothing to do with the size of the algorithm – the thing that does the work.

So, for example, if your algorithm adds numbers, the input is the numbers you want to add and the length of the input is the number of characters (bits, decimal digits, whatever format you're using) required to express the input.

# Answer
> 0 votes
Usually $n$ relates an asymptotic order of your algorithm. So, if an algorithm is said to be in $O(n)$, it means it can work in a linear time. This linear time can be simply explained as time taken to read a 1-D array. There are more orders like $ n^2$ ( where the algorithm takes $n^2$ time upon working with an $n$-sized input, preferably an array or so ), $nlogn$, $2^n$, etc. For example, if you write up an algorithm like

```
Algo_Add(Array a[],Size n)
{
    variable sum : integer
    variable i = 1 : integer
    loop while i <= n
    {
        sum = sum + a[i]
    }
    return sum
}

```

Here, the algorithm traverses the array $a\[ \]$ in a linear time $n$. But if the algorithm would have been like

```
Algo_Add(Array a[],Size n)
    {
        variable sum : integer
        variable i = 1 : integer
        loop while i <= n
        {
             variable j = 1 : integer
             variable sum2 : integer
             loop while j <= n
             {
                 sum2 = sum2 + a[j]
             }
             sum = sum + sum2
        }
        return sum
    }

```

Here, the algorithm traverses the array $a\[\]$ in a linear time too. But the difference here is that for every element $a\[i\]$ we get while traversing the array $a\[\]$, we traverse the array in a linear time of $O(n)$ again. So for $n$ elements, we actually traverse the array $n^2$ number of times. So the second algorithm is of order $O(n^2)$.Hope this helps you.

---
Tags: algorithms, asymptotics
---


# Question
Title: What is the complexity of Hamming nearest neighbor to a subspace ...?
Suppose that $F\_2$ denotes the field with $2$ elements. We are given $m$ vectors $\\{x\_1, \ldots, x\_m\\}$ in $F\_2^d$ which are a basis for a subspace $W$.

Suppose we have a vector $v \in F\_q^m$, and we want to find a $w \in W$ that is closest to $v$ in the Hamming metric.

What is the complexity of this problem, as a function of $md$?

1) It's clear that there is an algorithm taking exponentially many steps. $W$ has $2^m$ elements, each of which takes $d$ bits to describe. So we just search through them.

2) It's unclear to me if this problem is even in $NP$. I can verify in polynomial time whether one vector in $W$ is closer to $v$ than another vector in $W$, but I do not know how to verify if one is the closest (or minimizes the distance). I suspect that it is impossible to do. Can anyone outline or refer me to a proof that this problem is not in $NP$?

3) If it is in $NP$, then is it $NP$-hard?

I guess this is well known, and presumably already discussed on this webpage. I poked around for a bit and couldn't find it, however. A reference would be welcome.

# Answer
> 3 votes
Your problem is known as the *nearest codeword problem*, and it is NP-hard to approximate. See for example lecture notes of Madhu Sudan. The way to make this problem an NP-problem is to ask whether the distance is *at most* a given distance. Regarding algorithms, I suggest taking a look at a paper of Alon, Panigrahy and Yekhanin, Deterministic Approximation Algorithms for the Nearest Codeword Problem.

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


# Question
Title: Finding a reduction for two-Subset sum problem
I'd like to prove that the following problem is NP-complete. I'd just like to know what reduction I should do:

*Two Subset Sum: Given a set S of integers and an integer T, determine whether there are two subsets of S such that the sum of the numbers of one is T and the other is 2T. The subsets do NOT have to be disjoint.*

And I want to use the classic subset problem to prove this:

*Subset Sum: Given a set S of integers and an integer T, determine whether there is a subset of S such that the sum of the numbers is T.*

I'm slightly struggling with the reduction from Subset-Sum to 2-Subset-Sum, as simply adding to the set the double of each number and using the same T does not work, e.g `S = {1,7,8,5}` and `S'={1,2,5,10,7,8,14,16}` with `T = 10` wouldn't work, as S' would return "true" and S should return "false".

Thank you.

# Answer
> 1 votes
There is a trivial reduction from Partition to your problem: given an instance $S$ of partition, construct the instance $(S,\frac{1}{2} \sum\_{i \in S} i)$ of your problem. This shows that if you take any reduction from Subset-Sum to Partition, you immediately get a reduction from Subset-Sum to your problem. You can find the reduction from Subset-Sum to Partition in many places, or come up with it on your own.

---
Tags: np-complete, np-hard
---


# Question
Title: For any non-trivial $A,B$, finding a language which both are polynomially reducible to
> Given two non-trivial (not $\emptyset$ or $\Sigma^\*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct:
>
> a. There is a language $C$ such that $A\leq\_pC$ and $B\leq\_pC$.
>
> \[..\]
>
> c. There is a language $C$ such that $C\leq\_pA$ and $C\leq\_pB$.

According to two different sources I've seen the correct answer seems to be (a), which is exactly why I'm trying to understand two things:

1. Why is (a) a correct answer? Taking two languages in $EXP$, for example, I do not see why it's obvious they are polynomially reducible to each other.
2. Why is (c) not a correct answer? Taking a language $C\in P$ since $A$ and $B$ are not trivial there are some $a\in A, a'\notin A$ and $b\in B, b'\notin B$, and therefore given a polynomial TM $M$ deciding $C$ I can define a reduction $f$ to $A$ by $f(x)=a$ if $M(x)$ accepts and $f(x)=a'$ otherwise and similarly for $B$, so it seems to me that (c) is a correct answer.

# Answer
Part (a) is correct since you can take the language $$ C = \\{ 0x : x \in A \\} \cup \\{ 1y : y \in B \\}. $$ Here $0x$ is the concatenation of the strings 0 and $x$. This part works even when $A,B$ are trivial.

Part (c) is correct by taking $C = \emptyset$ and using $A,B \neq \Sigma^\*$, for example.
> 2 votes

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


# Question
Title: Why don't these 2 algorithms take the same time to detect duplicate lines in a file?
I'm trying to write a small algorithm to detect and delete duplicate lines inside a subset of consecutive lines in a file. I've come up with 2 similar solutions. After some quick tests, I've noticed that one of them is much faster than the other, especially on large files. But I don't understand why.

Here's the quick solution written in pseudocode, `first_line` and `last_line` are the first and last lines in the file where the algorithm looks for duplicate lines (I don't know exactly how to write pseudocode sorry):

```
i = last_line
while i > first_line
    j = i-1
    while j >= first_line
        if line i = line j
            delete line i
            break
        endif
        j = j-1
    endwhile
    i = i-1
endwhile

```

And here's the slow solution:

```
i = last_line
while i > first_line
    j = i-1
    while j >= first_line
        if line i = line j
            delete line j
        endif
        j = j-1
    endwhile
    i = i-1
endwhile

```

In the first solution, when 2 duplicate lines are detected and whose addresses are `i` and `j`, line `i` is deleted, and the inner loop exits. In the 2nd solution, line `j` is deleted, and the inner loop goes on without being broken.

At first, intuitively, I thought that choosing to delete `i` or `j` didn't matter. But after some tests, it seems deleting `i` results in a much quicker process than deleting `j`. I don't understand the asymmetry. I suspect it's because the purpose of the outer loop is to test the uniqueness of the line whose address is `i`, so it would make more sense to delete it as soon as we have an answer and not let the loop goes on. But I still don't understand completely.

Deleting line `i` and exiting earlier in the inner loop of the first solution save comparison operations. But by deleting line `j` in the 2nd solution, I also save comparison operations, since this `j` line won't be processed by the outer loop later.

Why is the first saving of operations much more important than the 2nd one?

I'm sorry if the question is too simple for this site, but I don't know much about algorithms, and I'm looking for a reasoning which I can understand and would prove that in the general case, deleting `i` reduce the number of operations.

In case it matters, here's the real code I'm using, it's written in vimscript:

```
com! -range=% DelDup call s:del_dup(<line1>,<line2>)

fu! s:del_dup(line1, line2) abort
    let view = winsaveview()
    let p    = a:line2
    while p > a:line1
        let q = a:line1
        while q < p
            if getline(p) ==# getline(q)
                exe p . 'd_' | break
            endif
            let q += 1
        endwhile
        let p -= 1
    endwhile
    call winrestview(view)
endfu

```

---

Edit:

I've compared the 2 algorithms with this simple file:

```
apple
banana
grape
kiwi
orange
tangerine

```

Then, duplicate each line `256` times:

```
for i in range(1, 8) | sil %t$ | endfor

```

Which gives a file with `1536` lines.

Then, I've measured the time it takes for the `:DelDup` command to delete duplicate lines with the fast algorithm which I wrote earlier:

```
:Time DelDup

```

On my machine, the time reported is around `0.1s`.

But if I replace the lines:

```
if getline(p) ==# getline(q)
    exe p . 'd_' | break
endif

```

With these lines:

```
if getline(p) ==# getline(q)
    exe q . 'd_'
endif

```

Then `:Time DelDup` reports that the command took more than `8s` on average.

In case it matters, here's how the `:Time` command is defined:

```
com! -count=1 -nargs=+ -complete=command Time call s:time(<q-args>, <count>)

fu! s:time(cmd, cnt)
    let time = reltime()
    try
        if a:cnt > 1
        let i = 0
        while i < a:cnt
            exe a:cmd
            let i += 1
        endwhile
        else
            exe a:cmd
        endif
    finally
        redraw
        echomsg matchstr(reltimestr(reltime(time)), '\v.*\..{,3}') . ' seconds to run :' . a:cmd
    endtry
endfu

```

# Answer
> 0 votes
When you delete line `j`, each line which was after that line will be moved by one line upwards. That means, that your line `i`, which is below, also will be moved. So, since it was moved, it has changed it's number. And it means that you need to decrease `i` : `i = i - 1`.

As an example see this:

```
Given file:    Lines 2 and 3 are equal    Remove line 2:
1 00                                      1 00
2 01
3 10                                      2 10
4 01                                      3 01

```

And your second algorithm didn't see that their positions have changed. However, if it wouldn't be file, but an array/list/etc, you'd got an error.

---
Tags: time-complexity
---


# Question
Title: Is this restricted promise-3SAT version coNPComplete?
Given a $3SAT$ problem the decision version of the problem (if it has a solution or not) is $NPComplete$. Now, given that we consider the promise version of the $3SAT$ problem, the promise is every $3SAT$ problem provided always has at least 1 solution.

**Query**: Does every solution of the above $3SAT$ problem instance have a particular property (one that can be tested in polynomial time. For eg: 'for any solution $A\_i$, $N$ numbers immediately smaller than A are co-prime' or something similar; where $N$ is the input length)?

The problem and property can be encoded as a pair consisting of $3SAT$, and another $N$ input circuit of polynomial size ($N^c$ for some constant $c$)

This promise version is definitely in $co-NP$ (as if there is a solution that does not satisfy the given property, that solution is the $co-NP$ certifcate of polynomial length).

Is this problem also $co-NPComplete$ (as it still involves getting the failing solution first)?

# Answer
> 2 votes
Your problem is coNP-complete when the property is "all variables are zero". Given a SAT formula $\varphi$ on $x\_1,\ldots,x\_n$, construct a new SAT formula $\psi$ by replacing each clause $C$ of $\varphi$ with $\lnot y \lor C$ (where $y$ is a new variable), and adding clauses $y \lor \lnot x\_i$ for $1 \leq i \leq n$. The satisfying assignments of $\psi$ are obtained from those of $\psi$ by setting $y = 1$, and there is an additional satisfying assignment in which all variables are zero. Hence $\varphi$ is satisfiable iff not all satisfying assignments of $\psi$ satisfy the property.

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


# Question
Title: If M is recognizing L in polynomial time, is it also deciding it in polynomial time?
> Assume that a given turing machine $M$ accepts words in the language in $n^k$ or less steps, but words that aren't in the language are rejected in unknown number of steps (the machine might even loop).
>
> $k$ is unknown.
>
> Is $L(M)\in P$?

Well, obviously $L(M)$ is recognized in polynomial time. The question is whether it's possible to decide $L(M)$ in polynomial time.

It seems to me that the answer is no, but I can't figure a way to prove it.

# Answer
> 1 votes
It is indeed possible. Simulate $M$ for $n^k$ steps. If it has accepted so far, accept. Otherwise, reject. You can simulate $M$ for $n^k$ steps in polynomial time (perhaps $O(n^{2k})$), hence this is a polynomial time algorithm.

---
Tags: turing-machines, time-complexity, decision-problem, polynomial-time
---


# Question
Title: Amortized time of insertion into an Array list
According to Amortized time cost of insertion into an Array list,

> A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

Can anyone kindly explain me the logic of this? If we consider the n(number of elements)=7 then we resize array at sizes 1,2,4 but according to above statement "1,2,4....7".

# Answer
> 4 votes
The question might be a little misleading.

> So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

This is only true if $n = 2^k$ for some $k \in \mathbb{N}$, because for a growth factor of 2, we only need to resize when $n$ is a power of 2.

So in your case we would only resize at 1, 2, 4. Not 7.

---

You should keep in mind this only applies to a growth factor of 2. We could change the growth factor however we wish. For example we set the growth factor to 3. Then we resize at powers of 3; $\\{1, 3, 9, \dots 3^k\\}$. You can still use the same analysis procedure to get a constant amortized time though.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, arrays, amortized-analysis
---


# Question
Title: Closure of context-free languages under "removal of a regular language from the right"
I have a homework that I can't solve can somebody help me?

If $\Sigma$ is an alphabet, $R$ is regular and $L$ is context-free. Is the language $$P = \\{\alpha\in\Sigma^\*\mid \alpha\beta\in L\text{ for some }\beta\in R\\}$$ context-free?

# Answer
Let me prove that if $L$ is regular then so is $P$. The proof in your case is similar. Let $\Sigma' = \\{ \sigma' : \sigma \in \Sigma \\}$ be a copy of the alphabet $\Sigma$. Let $s$ be the $\Sigma$-substitution $s(\sigma) = \\{\sigma,\sigma'\\}$, let $t$ be the $\Sigma$-homomorphism $t(\sigma) = \sigma'$, and let $d$ be the $\Sigma \cup \Sigma'$-homomorphism $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then $$ P = d(s(L) \cap \Sigma^\* t(R)). $$

As an aside, the class of languages obtained by dividing a context-free language by a context-free language consists of all r.e. languages. See for example The family of one-counter languages is closed under quotient by Latteux, Leguy and Ratoandromanana.
> 1 votes

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


title: What is Simultaneous Multithreading

text:
# Question
Title: What is Simultaneous Multithreading
I come from an electronics background. I know that there are three types of implementations of multithreading (see *Computer Architecture: A Quantitative Approach, 5th Edition*):

1. **Fine-grain multithreading** issues instructions for different threads after every cycle.
2. **Coarse-grain multithreading** only switches to issue instructions from another thread when the current executing thread causes some long latency events (like page fault etc.)
3. **Simultaneous multithreading** issues multiple instructions from multiple threads in one cycle. The processor must be superscalar to do so.

Does that mean that SMT is an extension of fine-grain and coarse-grain multithreading, and fine-grain and coarse-grain multithreading are only suitable for single core processor?

What is the exact difference between SMT and the other approaches?

# Answer
Hennessy and Patterson (Computer Architecture: A Quantitative Approach) use the term "multithreading" to refer to running more than one thread on a single core.

Their distinction between "fine-grain", "coarse-grain" and "simultaneous" involves different approaches for how the threads share the issue logic (the logic that moves instructions from the decode pipeline stage to the execute pipeline stage.)

In "coarse-grain multithreading" the issue stage will issue instructions from one thread for many cycles (dozens or hundreds) and then switch to issuing from another thread only when the first thread gets a cache miss or some other long-latency operation.

In "fine-grain multithreading" the issue stage can issue instructions from a different thread each cycle, but all the instructions issued together in a cycle must come from the same thread.

In "simultaneous multithreading" the issue stage can issue instructions from different threads in the same cycle. The restriction is lifted that instructions issued together in the same cycle must come from the same thread. The distinction between fine-grain multithreading and simultaneous multithreading only matters on machines that can simultaneously issue two or more instructions.
> 9 votes

# Answer
Fine-grain multithreading and coarse-grain multithreading are two approaches that can be implemented even on single-core processors. The idea is that you "time-share" the different threads on the single core. Fine-grain multithreading switches between the threads every so often, while coarse-grain multithreading transfers control only when the executing thread is waiting for some operation to resolve.

Simultaneous multithreading, which can only be implemented on a multicore system, executes the different threads on different cores, or on different processing units on the same core ("superscalarity").

Hopefully I've explained the concepts clearly enough, and now you can answer the questions yourself.
> 3 votes

# Answer
A physical processor is made up of a number of different resources, including the architecture state — the general purpose CPU registers and interrupt controller registers, caches, buses, execution units, and branch prediction logic. However, in order to define a thread, only the architecture state is required. A logical processor can thus be created by duplicating this architecture space. The execution resources are then shared among the different logical processors.

This technique is known as ***simultaneous multi-threading,*** or SMT.

See Intel's Multi-core programming.
> 1 votes

---
Tags: terminology, operating-systems, computer-architecture
---


# Question
Title: Fastest search algorithm in a sorted list with certain error rate-limiting constraints
This problem came up during the Google CTF 2017. For background information about the challenge you can search for `GoogleCTF A7 ~ Gee cue elle`.

Problem description:

* A random number `N` between `0` and `39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815` (`~3.9*10^115` or `64^64`) is selected
* You have to find the correct number `N`
* You can take a guess `X`, and get a response whether the number `X` is greater or lower than `N`
* The twist:
    + you can only perform 13 guesses in 30s without hitting a 90s timeout - `13/30`
    + if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - `2/30`
    + you have only `2240s` time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the broken egg problem. His algorithm basically runs in constant time. As max number is `64^64`, he divides the problem in 64 buildings with 64 floors. And a broken egg is an error. This means it takes overall pretty constant 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side `2/13=0.15` 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

1. I thought the `0.15` skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around `~0.22`. My calculation is obviously wrong, but what would have been the correct calculation to find `~0.22`?

2. Why does the egg problem algorithm perform better (as in faster on average)?
3. What is the on average fastest algorithm here? And why is it not based on a skewed binary search?

Any thoughts and comments are welcome.

# Answer
> 2 votes
For simplicity of analysis I will say that 'too high' is the error condition, which is just the problem inverted, $64^{64}-n$. I also assume that requests are instant.

It takes some thinking, but waiting is never an optimal strategy. So we view the problem as just a series of guesses, done in blocks of 13 (unless we hit the 90 second timeout). Instead of timeouts our penalty will be losing guesses, and instead of minimizing time we will minimize guesses used. I write $V\_2$ for the value of a guess (in bits) when we are in the state where we guessed too high twice in this block. Similarly I will write $V\_1, V\_0$. I write $g \in \\{0\dots13\\}$ for the number of guesses left in the block, including the current one.

I will evaluate a strategy where we pick three numbers $p\_0$, $p\_1$, $p\_2$, where each $p$ encodes how skewed the binary search is for when we've guessed $0$, $1$ or $2$ wrong times in this block.

The expected value (in bits) of a guess $p \in \[0, 1\]$ (where $0$ is the lowest guess and $1$ is the highest) is the binary entropy function $H(p) = -p \log\_2 p - (1 - p)\log\_2(1-p)$.

However, for $V\_2(g)$, if we guess wrong we lose the rest of this block and the next two blocks, $B$ is the value of a block in bits.

$$V\_2(g) = H(p\_2) - 2p\_2B - p\_2\sum\_{k=1}^{g-1}V\_2(k)$$

If we write $E\_2(g)$ as the value in bits of being in state $2$ with $g$ guesses left:

$$E\_2(g) = \sum\_{k=1}^{g} V\_2(k) = \sum\_{k=1}^g \big( H(p\_2) - 2p\_2B - p\_2E\_2(k-1)\big ) $$ $$E\_2(g) = g(H(p\_2) - 2p\_2B) - p\_2 \sum\_{k=1}^g E\_2(k-1)$$

This recurrence can be solved:

$$E\_2(g) = (H(p\_2)/p\_2 - 2B)(1-(1 - p\_2)^g)$$

Similarly, if we guess wrong for $V\_1$, we lose our advantage from state $1$:

$$V\_1(g) = H(p\_1) - p\_1(E\_1(g-1) - E\_2(g-1))$$ $$E\_1(g) = \sum\_{k=1}^{g} V\_1(k) = \sum\_{k=1}^{g} \big( H(p\_1) - p\_1(E\_1(k-1) - E\_2(k-1))\big )$$

$$E\_1(g) = g(H(p\_1) - p\_1E\_2(g-1)) - p\_1\sum\_{k=1}^{g}E\_1(k-1)$$

$$E\_1(g) = (H(p\_1)/p\_1 - E\_2(g-1))(1-(1 - p\_1)^g)$$

And $E\_0$ is directly analogous. Now, since $B = E\_0(13)$ we have:

$$E\_0(g) = (H(p\_0)/p\_0 - E\_1(g-1))(1-(1 - p\_0)^g)$$ $$E\_1(g) = (H(p\_1)/p\_1 - E\_2(g-1))(1-(1 - p\_1)^g)$$ $$E\_2(g) = (H(p\_2)/p\_2 - 2E\_0(13))(1-(1 - p\_2)^g)$$

Oh boy... With a CAS I found:

$$E\_0(13) =\frac{1}{2P\_0P\_1P\_2 + 1} \left(\frac{P\_0H(p\_0)}{p\_0} - \frac{P\_0P\_1H(p\_1)}{p1} +\frac{P\_0P\_1P\_2H(p\_2)}{p\_2}\right)$$

where $P\_0 = 1-(1-p\_0)^{13}$, $P\_1 = 1-(1-p\_1)^{12}$ and $P\_2 = 1-(1-p\_2)^{11}$. This is the expression we want to maximize.

Numerically maximizing this expression gives $E\_0(13) \approx 6.72$ bits with:

$$p\_0 \approx 0.1854365,\quad p\_1 \approx 0.1422816,\quad p\_2 \approx 0.0000899$$

This means that in order to get $\log\_2(64^{64}) = 384$ bits we expect to need 57.1 blocks, or 1714.3 seconds.

---

This isn't even optimal yet, though. $p\_0, p\_1, p\_2$ should actually be functions of $g$ (consider that if you are on your last guess in state $0$, then you can be really greedy and not get punished). I will see if I can improve my answer.

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


title: Gauss-Newton algorithm implementation

text:
# Question
Title: Gauss-Newton algorithm implementation
I am trying to implement a Gauss-Newton algorithm for non-linear optimisation. Unfortunately despite searching through the library and the internet I can't figure out quite how to use it in my case. As such I am hoping that I have come to the right place to ask for some assistance? Thank you to anyone willing to help me.

My problem consists of minimising a function $f(\vec x)$ where $\mathbb R^n \ni \vec x = (x\_1, \dots ,x\_n)$ and $f:\mathbb R^n\rightarrow \mathbb R$. Physically $f$ is a chi squared value $f=y-e(\vec x)$ where $y$ is the target value and $e(\vec x)$ is the test function evaluated at guess $\vec x$.

I begin by computing $f(\vec x+\delta \vec x)$ and $f(\vec x)$. Here $\vec x+\delta \vec x=x\_1+\delta x\_1,\dots , x\_n+\delta x\_n$. I then evaluate numerical derivatives using the following quotient formula, \begin{equation} \frac{\partial f(\vec x)}{\partial x\_i} = \frac{f(x\_1,\dots , x\_i+\delta x\_i,\dots ,x\_n)-f(\vec x)}{\delta x\_i}\qquad \forall i =1,\dots ,n \end{equation} I must then combine this into the Jacobian $\vec J$, \begin{equation} \vec J = \bigg(\frac{\partial f(\vec x)}{\partial x\_1}\ \frac{\partial f(\vec x)}{\partial x\_2} \cdots \frac{\partial f(\vec x)}{\partial x\_n}\bigg) \end{equation} I can take the transpose of $\vec J$ denoted $\vec J^T$.

So far I can code the above (in C++). However The next part becomes confusing for me personally. In particular I do not know how to write the following matrix equation. \begin{equation} (\vec J \vec J^T)\delta \vec x = \vec Jf \end{equation} In fact I am not certain that this is the correct procedure?

Therefore, with numerical derivatives in place how can I obtain $\delta \vec x$ for the next iteration of the descent? Again many thanks for your time.

# Answer
Solve the equation multiplying both terms of the equation for the inverse of the hessian matrix $\vec{J} \vec{J}^T$ on the left side:

$$ \delta \vec{x} = (\vec{J} \vec{J}^T)^{-1} \cdot \vec{J}f $$
> 2 votes

---
Tags: optimization
---


# Question
Title: General name for linked lists based on hashes
I am thinking of a particular datastructure, but don't know the name of it.

A sequence of elements may be modeled by a collection of some X, where each X consists of:

1. The element, serialized as a bunch of bytes.
2. \[a\] The hash of the previous X in the sequence, based on the bytes of both parts of that X in a predictable way or \[b\] some mechanism to denote no such X exists, i.e. that this is the first element.

Given a database that contains (at least) all relevant Xs, and a lookup mechanism by hash, we can take a single X and reconstruct the sequence of elements from it.

What is the general name (if it exists) of this datastructure in the literature? I.e.

* What is the general name of X?
* What is the general name of a sequence of Xs.

Note that although this looks like (and is inspired by) a blockchain or git commit object, it is more general: any list sequence could be so rewritten.

In comparison with the blockchain / git, the above does not make any statement about distributed databases, timestamps or contents of each element. It also notably differs from git at least in the sense that it is single-parent.

# Answer
This is known as hash chaining. The blockchain uses this technique, as do some kinds of timestamping schemes (see, e.g., Haber & Stornetta) and in some cryptographic schemes for append-only audit logs.
> 2 votes

---
Tags: data-structures, terminology, hashing, lists
---


title: Construct a loop program for equality

text:
# Question
Title: Construct a loop program for equality
I want to construct a loop-computable program for this construction:

IF x1 = c THEN P ELSE P'

I know how to transform if else construction in loop , but I can't understand how to check the equality.I have idea for x1 \>= c , but how can I check if the both numbers are equal ?

# Answer
Do you have idea how to check $x\_1 \leq c$ as well? Then just check $(x\_1 \leq c) \wedge (x\_1 \geq c)$ which implies $x\_1 = c$.
> 2 votes

---
Tags: computability, loops
---


# Question
Title: Minimum number of intersections to arrive at specific set
Say I have a large number of sets (on the order of ~1000) with a smaller number of potential entries (~200), and a widely varying number of entries per set. An example:

$s\_1 = \\{1, 42, 133\\}$

$s\_2 = \\{27, 283, 292, 172, 66, 62\\}$

$s\_3 = \\{1, 42, 292, 66\\}$

$...$

$s\_{1000} = \\{1, 133, 72\\}$

Is there an algorithm more efficient than Monte-Carlo / brute force to find the **minimum set of sets that I need to intersect to get a result containing exactly one specific item**?

For example, given the above four sets, I would need to intersect $s\_1, s\_3,$ and $s\_{1000}$ to arrive at a result containing only the element $1$ - the algorithm would need to find this solution (or a different solution requiring the same or a smaller number of sets), for arbitrary elements appearing in at least one set.

I have a feeling that this could be transformed into a set packing problem (which would make it an NP problem), but I am not an expert on this topic. Any input would be appreciated.

# Answer
> 2 votes
Your problem (or rather, its decision version: are there $k$ sets whose intersection is a singleton) is NP-complete, so I doubt there is a simple solution that always works, even for your numbers.

The problem is clearly in NP. We show that it is NP-hard by reduction from SAT. Let $\varphi$ be a CNF on variables $x\_1,\ldots,x\_n$ and clauses $C\_1,\ldots,C\_m$. We form an instance of your problem on the universe $x\_1,\ldots,x\_n,C\_1,\ldots,C\_m,\Delta$. For every $x\_i$ and every truth value $t$, there is a set $S\_i^t$ which contains (1) $\\{x\_1,\ldots,x\_n\\} \setminus \\{x\_i\\}$, (2) all clauses not satisfied by $x\_i=t$, and (3) $\Delta$.

All sets contain $\Delta$. In order to get rid of all $x\_i$, we need to choose at least one set $S\_i^t$ for each $i$. The intersection consists only of $\Delta$ if and only if the choice corresponds to a satisfying assignment. Hence there are $n$ sets whose intersection is a singleton iff $\varphi$ is satisfiable.

---
Tags: sets
---


# Question
Title: CFL Closure Properties prove or disprove for the following languages
I have following statements which I must prove or disprove :

1) Let $L$ be a CFL and $k \in N$ then $L^k$ is also a CFL.
2) $L\_1 \subseteq L\_2 \subseteq L\_3$ are Languages, if $L\_1$ and $L\_3$ are DCFL, then $L\_2$ is also a DCFL

The first one I have no idea how to start or whether it is also a CFL

For the second one I think that this is false, because the CF contains the REG and DCF which means $L\_2$ can be a REG-Language or a CFL or DCFL?

Is this right? at least this is how I understand it

# Answer
1) Since the context-free languages are closed under concatenation, a simple induction shows that if $L$ is context-free then so is $L^k$, for all $k \geq 0$.

2) Let $L\_2$ be a language over an alphabet $\Sigma$ which is not context-free. Then $\emptyset \subseteq L\_2 \subseteq \Sigma^\*$, refuting the statement (since $\emptyset$ and $\Sigma^\*$ are regular and so deterministic context-free).
> 0 votes

# Answer
1) If $L$ is a CFG then assume $S$ is the start symbol of the grammar rules. Then introduce a new start symbol $S' \rightarrow SS\dots SS$ ($k$ times). So if $w \in L^k$ then $w$ can be written as $u\_1u\_2\dots u\_k$ where $S \Rightarrow^\* u\_1$, $\dots$, $S \Rightarrow^\* u\_k$ and so $S' \rightarrow SS\dots S \Rightarrow^\* u\_1u\_2\dots u\_k$. Now suppose that $S' \Rightarrow w$. Then since $S' \Rightarrow SS\dots S \Rightarrow^\* w$, $w$ clearly in $L^k$. Thus, $L^k$ is CF.

2) $L\_1 = \\{ 0^i | i \in N\\}$, $L\_2 = \\{ 0^i1^j2^k | i,j,k \in N, i=j \ or \ j=k\\}$, $L\_3 = \\{ 0^i1^j2^k | i,j,k \in N\\}$. Clearly $L\_1 \subset L\_2 \subset L\_3$. But $L\_2$ is not CFL, so not DCFL.
> 1 votes

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


title: Is the complement of MAX-CLIQUE in NP?

text:
# Question
Title: Is the complement of MAX-CLIQUE in NP?
> Let $$MAX-CLIQUE = \\{\ \<G,k\>\ |\ G\ is\ an\ undirected\ graph,\ and\ the\ largest\ clique\ of\ G\ has\ k\ vertices\\}$$
>
> 1. Does $MAX-CLIQUE\in coNP$? If it does, can you think of a verifier?
> 2. If $NP=P$, does $MAX-CLIQUE\in P$?

I cannot think of a polynomial verifier for $MAX-CLIQUE$'s complement. There might not be a max clique of size k due to two reasons:

1. There's a bigger clique than k (and then the verifier will get such clique and verify it).
2. There's no clique of size k in the graph (and this is cannot be verified in polynomial time).

Regarding the second question: it's known that $MAX-CLIQUE$ is just $NP-HARD$ and not $NP-COMPLETE$. I understand from that that probably $MAX-CLIQUE \notin NP$, therefore even if $P=NP$, so $MAX-CLIQUE \notin NP=P$.

So does it mean that the answer to all the question is simply "no"?

# Answer
> 2 votes
1. $MAX-CLIQUE \in \mathsf{coNP \Leftrightarrow NP = coNP}$.
2. The answer is yes: your variant of $MAX-CLIQUE$ is in $\mathsf{P^{NP}}$, since knowing the size of max clique you can solve your problem.

There is no polynomial verifier (if $\mathsf{NP \neq P^{NP}}$) for this problem, because it is not in $\mathsf{NP}$.

Classic $MAX-CLIQUE$ which only asks if there is a clique of size **at least** $k$ is $\mathsf{NP}$-complete. But if $\mathsf{P = NP}$ you can ask a machine if there is a clique of size $|V|, |V| - 1, |V|-2...$ until the answer is "YES" to find max clique. Of course, you can use binary search instead of linear.

So, $\mathsf{P = NP}\Leftrightarrow MAX-CLIQUE\in \mathsf{P}$.

---
Tags: turing-machines, time-complexity, decision-problem, polynomial-time, p-vs-np
---


title: Complexity of $FP^{NP}$

text:
# Question
Title: Complexity of $FP^{NP}$
what is the complexity of $FP^{NP}$ w.r.t. $FPSPACE$?

Also can someone please provide a few examples of Problems complete for $FP^{NP}$? If possible let the examples be natural.

# Answer
1. I don't think it's correct to write "w.r.t. $\mathsf{PSPACE}$" since $\mathsf{PSPACE}$ is a set of decision problems, while $\mathsf{FP^{NP}}$ is a set of functional problems which is contained in $\mathsf{FPSPACE}$. These (which you are interested in) problems can be solved by polynomial amount of queries to $\mathsf{NP}$ oracle (that returns YES/NO answer).
2. A simple example of such problem is:

Given a DNF find an equivalent DNF which has as it's terms only prime (those which cannot be shortened) implicants. It can be solved with linear amount of queries to TAUT/SAT oracle.
> 1 votes

# Answer
Both $\mathrm{FP}$ and $\mathrm{NP}$ are included in polynomial space so $\mathrm{FP^{NP}}$ is, too, since you can simulate the computation and its oracle. Note that, strictly speaking, you need to compare against $\mathrm{FPSPACE}$, since $\mathrm{FP}$ is a set of function problems, whereas $\mathrm{PSPACE}$ is a set of decision problems.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: What is the best known data structure for online dk-NNG?
I want to build the *distance constrained k-Nearest Neighbours Graph*, i.e. for every point $p$ in the data cloud $P$ there are at most $k$ undirected edges to points that are closest among all possible vertices using $L\_2$ metric with additional constraint that are no further than $d$.

There are only insertions (in batches of $10^6$ points) and neighbourhood retrieval queries used. The results have to be exact - I cannot use approximate nearest neighbours or reduce dimensions.

The setting is following:
There are 50 dimensions, not correlated. The $k=9$ is number of neighbours, $d$ is given distance. The data is sparse in every dimension, mean and median are meaningful, data is random and unstructured in any way (but for sure not from uniform or Gaussian distribution).

So far I have tried to build parallel kd-tree with partial rebalancing, the ball trees, m-trees, r-trees, Sparse ktree (octree with more dimensions) partitioning and two-projection hashes. But I am facing problem, that either insertion time is far too long or k-nng queries are too long. I think this happens because the structures are either static or not really prepared to maintain full neighbourhood graph.

I have tried linear scan, it performs good for very small data, worse than z-curve localised version or sparse ktree. Up to some $n$ it outperforms any treelike structure. I made one modification to naïve algorithm: used one AVL (right threaded) per dimension keeping nodes connected among trees and checked only points within distance $d$ at each dimension - this one performs well, but due to its memory consumption and lack of multidimensional structure scales poorly.

**What data structure would be the best in practice for dk-NNG?**
If this is not enough, I would like to optimize the number of neighbours checked, for localised data the number of bins traversed.

# Answer
I'm not familiar with dk-NNG, but have you tried a PH-Tree? It has excellent insertion times and very good kNN search. I tested several scenarios with up to 40 dimension and $10^6$ and $10^7$ points. It usually competes with R\*Tree (R-Star-Tree) for kNN-search, but has much better update performance.

You could also try an R\*tree, they are almost always faster than a standard R-Tree. An implementation in Java can be found here.
> 2 votes

---
Tags: data-structures, online-algorithms, nearest-neighbour
---


# Question
Title: Solving consensus for a known number of processes
I was given an object with exactly 2 operations `test-and-reset` that sets the value of the object to 0 only if it was previously set to 1 and does not return a value and `fetch-and-add(v)` which adds `v` to the value of the object and returns the previous value.

I am almost sure the consensus number of this object is 2 and I think I found an algorithm for it (I should mention the problem is binary consensus):

```
if input = 0
    test-and-reset(obj)
    prev = fetch-and-add(obj, 3)
    if (prev != 2)
        decide(0)
    else
        decide(1)
else
    prev = fetch-and-add(obj, 1)
    if (prev = 0 or prev = 3)
        decide(0)
    else
        decide(1)

```

The problem was to find a wait-free algorithm an algorithm for `n` processes using any number of these objects (`n` is known).

The problem is that I an not sure if I am right (I'm pretty sure and this holds me back on this idea)? And if I am right no idea how to use this to solve the problem.

Thanks

# Answer
> 0 votes
I was wrong the object has an infinite binary consensus number.

```
if (input = 0) test-and-reset(obj)
prev = fetch-and-add(obj, 2)
if (prev mod 2 = 0)
    decide(0)
else
    decide(1)

```

---
Tags: concurrency, consensus
---


# Question
Title: Give one example where it takes Non- deterministically exponential time to solve the problem?
I am a starter in complexity theory though I have fair knowledge in Turing machine. I know what it means to be non-deterministically polynomial time solvable but I am trying to understand where the time goes beyond polynomial time even using non-deterministic concept. Is it possible or we can do everything in polynomial time using non-deterministic concept though in reality it can not be implemented. Therefore, I am looking for an example where we can't do it in polynomial time rather it takes exponential time even after using non-deterministic concept. Please explain clearly why it takes exponential time(non-deterministically).

# Answer
> 10 votes
There are problems that cannot be solved in polynomial time on a nondeterministic machine. Indeed, there are problems that cannot be solved on *any* Turing machine, such as the halting problem.

We know from the nondeterministic version of the time hierarchy theorem that there are things that can be done in exponential time on a nondeterministic TM that cannot be done in polynomial time. That is, $\mathrm{NP}\subsetneq\mathrm{NEXP}$.

Wikipedia gives several examples of $\mathrm{NEXP}$-complete problems: these are examples of problems that are provably not in $\mathrm{NP}$.

# Answer
> 5 votes
According to the Nondeterministic time hierarchy theorem, $\mathsf{NEXP\neq NP}$, which means there are languages decidable in nondeterministic exponential time, but not with nondeterministic polynomial time. A simple consequence is that no $\mathsf{NEXP}$ complete problem can lie inside $\mathsf{NP}$, which means that the following language requires exponential nondeterministic time to solve:

$L=\left\\{\left(n,\langle M\rangle,x\right) \big|\hspace{1mm} \exists w\in\\{0,1\\}^{\le n} : M(x,w)\right\\}$

Note that if in the above you replace the binary representation of $n$ with its unary representation $1^n$ then the problem becomes $\mathsf{NP}$ complete rather then $\mathsf{EXP}$-complete. This is an example of a more general phenomena, where many $\mathsf{NP}$ complete problems can be turned into $\mathsf{EXP}$-complete problems by giving a succinct description of the inputs. More details about this and some examples of more natural $\mathsf{EXP}$-complete problems can be found in this question from cstheory.

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


# Question
Title: A systematic approach to creating a simple test parser
I need to create a simple text parser that replaces `{tokens}` with text from a table. The more complicated bit is the `{?text?}` tag where `text` must be included only if the preceding AND the following tokens exist and are not empty. You could do `{?text}` where it looks for a non-empty neighbouring tag only on that side.

I am not a CS student and I don't have any formal education, but I am interested in this stuff.

I know I can bodge this via common sense and general logic but I would like to approach this in a more systematic manner, as this seems simple enough and like an excellent learning opportunity.

I am aware of the concept of formal languages and grammars, but I'm not sure where to start apart from randomly jumping over wikipedia pages that seem relevant(like Context-free grammars and Parse trees), until something starts making sense.

# Answer
> 1 votes
As far as I can tell, you can model this easily using any number of formalisms. Of course, if you insist on the specific syntax you have invented, you may be out of luck and may have to build your own engine.

I wouldn't to that if I were you: you have both forward and backward references, and your "data access" tokens closely resemble your "logic" tokens, so processing may become troublesome.

Consider this instead:

```
{if weight}; Weight is: {weight}kg{endif}

```

This can easily be parsed using standard techniques, and is immediately familiar to many people. It also supports nesting (if you use a context-free parser).

---

That all said, here is a sketch of an algorithm that will parse your syntax, assuming that there is no nesting at all (which you don't seem to specify).

We simply work in two phases:

1. Lex the input into tokens: regular text, and your special tokens. Represent the former by `text(text)` latter by two types, `data(name)` and `conditional(left, right, text)`.

2. Go over the token list, evaluating each token according to these rules:

    ```
     eval text(t) ==> t
     eval data(n) ==> value(n)
     eval conditional(left, right, text) ==>
        if   (!left || (eval predecessor) != "")
          && (!right || (eval successor) != "") {
            text
        } else {
            ""
        }

    ```

You see that you have to keep two copies in memory, at least for a time.

I think it's straight forward to transform this solution so that you move a three-token window over the token stream; this way, you can forget old tokens, and only need to lex one token in advance. So, as long as your conditional tokens only depend on their immediate neighbours, this can be efficiently parsed.

---
Tags: formal-languages, language-design
---


# Question
Title: Clarification of Definition for Functional version of TSP
The decision version of $TSP$ is $NPComplete$. I was reading about the functional version of $TSP$ i.e. the class $FP^{SAT}$.

It is mentioned in the original paper that TSP is complete for the class $FP^{SAT}\[n^{O(1)}\]$. By definition of the class, it means TSP can be solved in polynomial time by making $\[..\]$ calls to an $NP$ Oracle.

But I am still confused what $n$ is in case of a TSP instance?

# Answer
> 3 votes
In definitions of complexity classes, $n$ is always the input length in bits.

Often the definitions are invariant under polynomial blowup (for example, polytime and logspace), and in such cases you can also take $n$ to be other parameters of the input, the resulting class being the same. For example, if the input is an unweighted graph, you can take $n$ to be the number of vertices.

---
Tags: complexity-theory
---


title: Solving T(n) = 2T(n/3) + 2 T(2n/3) + n

text:
# Question
Title: Solving T(n) = 2T(n/3) + 2 T(2n/3) + n
The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed:

1. Recursion tree. We see that $$\begin{align} \sum\_{i = 0}^{\log\_{3}(n)}n2^i & = \Theta(n^{1+\log\_3(2)})\\ & \ll T(n) \\\\[1em\] & \ll \sum\_{i = 0}^{\log\_{\frac{3}{2}}(n)} n2^i \\\\[0.5em\] & = \Theta(n^{1+\log\_{\frac{3}{2}}(2)}) \end{align}$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.
2. Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$, as far as I can see there is no way to get a closed form for p from this equation (but it gives a numerical approximation consistent with 1, $p$ is about $2.19$ so that is good).

What I want is to find a closed form for $p$, one better than $2+2^{p+1}=3^p$. I believe such a closed form does exist, it might be found with domain transformations or something like that.

This is problem 2(m) from Jeffrey Erickson's notes on recurrences: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf

Any help is appreciated.

# Answer
> -2 votes
Completely unscientifically, the 2T (N/3) can be ignored. The 2T (2N/3) doubles whenever N is multiplied by 1.5, which starting with T(1) happens log N / log 1.5 times, so the result is about $2^{\log N / \log 1.5}$ or $N^{\log 2 / \log 1.5}$ which is about $N^{1.709}$. The n that is added is less than this, so $\Theta(N^{1.709})$ is my unscientific answer.

It just so happens that $p = \log 2 / \log 1.5 = 1.709$ also solves your equation $2 + 2^{p+1} = 3^p$. At least up to 9 decimals according to my spreadsheet.

---
Tags: asymptotics, recurrence-relation, discrete-mathematics
---


# Question
Title: What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus)
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and was wondering, what guarantees Paxos to converge and not run forever without a consensus/agreement on a value? Is it guaranteed to converge always or is it a probabilistic bound that the probability that it does not converge is really really small?

Because I was reading condition $P2^c$ and it seems possible to me that because of that condition, Paxos might loop forever if we are not careful (I think, maybe I am wrong, but I would love to know why!) Take the following case:

I was a little worried about the case when, say that a majority was close to forming but there is a new node that wants to propose his new value but was unlucky and did not happen to communicate with that growing set that nearly formed a majority (its not a majority yet, but it was reaalllyyy close!). That node was ready to prepare his value but was that unlucky and reasoned "Ok, none of the nodes I spoke to had a value, thus, time to propose my value!" but his sequence number is much higher than the previous one that was forming on the other side and it starts to spread, wouldn't it be because we want to satisfy (b) in $P2^c$? i.e. doesn't it damage the convergence to a decision (never mind the run time, it might never converge...)? Even in the case of a very good quality network..?

Because now this new node has a higher value and his value spreads like a disease and it *could* happen again, right before it was about to form a majority with his own value. That situation could happen again and again and again no value is decided! Right? What prevents Paxos from being in this situation? Or what is the argument to convince me that its really unlikely to happen many times and that it converges in polynomial time most of the time?

Recall condition $P2^c$ is the following:

$P2^c$

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

# Answer
> 2 votes
There is no guarantee that Paxos will converge. In fact, more strongly, it can be shown that it is impossible to guarantee convergence of a distributed consensus algorithm in an asynchronous network. See for example Fischer, Lynch and Patterson's short paper ‘Impossibility of Distributed Consensus with One Faulty Process’.

In practical implementations it is usual to rely on the fact that, as long as enough nodes are working and communicating with each other, if exactly one node sends out a `PREPARE` (phase 1a) message for a sufficiently large ballot, and there are no other messages in flight, then the system will converge in a small number of round-trips. These conditions can be arranged, eventually-almost-certainly, by using randomised timeouts and maybe some kind of backoff.

---
Tags: algorithms, distributed-systems
---


# Question
Title: Finding the $k$th largest element in an unsorted array
What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k \< n. Is there a way of finding the kth largest element without sorting the list?

# Answer
> 1 votes
Yes, there is. Selection algorithm. There are two versions: running in worst-case linear time, and in expected linear time (see Cormen's chapter 9). You can also implement this algorithm to run in sublinear time using data structures.

# Answer
> 0 votes
You don't need to sort the list for finding $k$-th largest element. You can use Max Heap data structure .

Algorithm $(A,k)$

1. Build Max-Heap (Running time - $\mathcal{O}(n)$).
2. Remove root element and heapify (maintain heap) ( Running time - $\mathcal{O}(\log{}n)$).
3. Repeat above two steps for $k$ times.
4. Return removed root element at $k$th step.

Total Running time : $\mathcal{O}(k \log \ n + k n )$

# Answer
> 0 votes
There is another different way to find k-th largest in an array.
Use Cartesian Tree, build Cartesian tree using array index and not keys. To search start from root, whose position you know, you can decide whether to move left sub-tree or right tree
If you are moving right sub-tree you have to search for k-root\_index in right sub-tree
Check https://habrahabr.ru/post/102006/ for details

# Answer
> 0 votes
A binary heap will insert and remove minimum in $\mathcal{O}(\log{}n)$

1. Inset the first K elements into a binary heap
2. Starting at K+1 to n compare the element in the input array to the minimum in the binary heap
If \> minimum then remove the minimum from the binary heap and insert the element in the binary heap

I think it is order $\mathcal{O}(n \log{}k)$

```
for(int i = 0; i < input.count; i++)
    if(i < k)
       BinaryHeap.Add(input[i])
    else if (input[i] > BinaryHeap.min)
       BinaryHeap.Add(input[i])
       BinaryHeap.Remove(BinaryHeap.min)

return BinaryHeap.min

```

---
Tags: algorithms, complexity-theory, linked-lists, selection-problem
---


# Question
Title: How large would a database containing perfect knowledge of chess be?
Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-bit integer, how many bytes would the database need to be to guarantee that it can store every possible game state of chess?

# Answer
> 2 votes
Claude Shannon indicated that the State Space Complexity (number of legal positions reachable from the initial position in chess) has a lower bound of approximately $10^{43}$. If each entry consists of $20$ bytes, as indicated in your question. The total number of bytes for your database would have a lower bound of $2 * 10^{44}$ which is a very large number indeed.

I would suggest reading *Section 2: General Considerations* of Shannon's paper, Relevant quote:

> Another (equally impractical) method is to have a "dictionary" of all possible positions of the chess pieces. For each possible position there is an entry giving the correct move (either calculated by the above process or supplied by a chess master.) At the machine's turn to move it merely looks up the position and makes the indicated move. The number of possible positions, of the general order of $64! / 32!(8!)^2(2!)^6$ , or roughly $10^{43}$, naturally makes such a design unfeasible.

References:

---
Tags: data-structures, space-complexity, database-theory, databases, space-analysis
---


title: Set cover problem with sets of size 2

text:
# Question
Title: Set cover problem with sets of size 2
I have a question about the Set Cover problem: If I get a universe $U$, and $m$ subsets of size exactly $2$, and an integer $k$. Is this problem is still NP-C or I can solve it on a polynomial time?

Thanks.

# Answer
> 3 votes
This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching. Then, for each unmatched vertex, add an arbitrary edge containing that vertex.

In fact, if all you want to know is whether there's an edge cover of size at most $k$, you don't need to construct the cover: the size of a minimum edge cover is $M + n - 2M = n-M$, where $n$ is the number of vertices in the graph and $M$ is the number of edges in a maximum matching. (The reasoning here is that the cover is the $M$ edges of the matching plus one more edge for each unmatched vertex, and there are $n-2M$ unmatched vertices.)

---
Tags: np-complete, set-cover
---


# Question
Title: Algorithm which finds the maxmal solution that satisfies the following constraints
I have $a\_1, a\_2,\dots,a\_n$ and $b\_1,b\_2,\dots,b\_n$ and an upper bound $U$ and $n$ linear equations of the form:

$k\_1 * a\_1 + b\_1 = x$

$k\_2 * a\_2 + b\_2 = x$

$\dots$

$k\_n * a\_n + b\_n = x$

Additional info where $r \in \\{ 1,2,\dots , n \\}$:

* $a\_r$ is prime
* $0 \leq b\_r \< a\_r $
* $k\_r b\_r, U, n, \in N\_0$ and $(a\_r\in N)$

I'm looking for an algorithm that computes the largest $x$ which satisfies all of the given equations such that for the given upper bound $U$ the additional constraint $x \leq U$ holds. If there is no such $x$ a simple "no solution" as output is fine.

**First Example:**

Given data: $a\_1 = 3, a\_2 = 5$ and $b\_1 = 1, b\_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k\_1 * 3 + 1 = x$

$k\_2 * 5 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is 7 (set $k\_1 = 2$ and $k\_2=1$)

**Second Example:**

Given data: $a\_1 = 11, a\_2 = 17$ and $b\_1 = 1, b\_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k\_1 * 11 + 1 = x$

$k\_2 * 17 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is "no soluton" (there is no way to set $k\_1$ and $k\_2$ such that the equations are equal)

I'm struggling to come up with an algorithm which solves this efficiently. Currently my best approach is to compute all values of x which satisfy the first equation, then I compute all values of $x$ which satisfy the second equation and so on until I have $n$ sets, set $i$ represents the values of $x$ which satisfy equation $i$. Then I simply intersect all of them, if the result is an empty set then I output "no solution" otherwise I output the max element of the resulting set. This approach is very inefficient :/

What do you think about my approach how could I compute the largest x which satisfies all of the constraints above more efficiently?

**Note:** the reason I know that there is a more efficient solution is because I have encountered this problem during a programming competition. I'm expecting that the solution will use elementary number theory since prime numbers are involved. I just don't know how else to approach this.

# Answer
You want a solution $x$ such that

$$x \equiv b\_i \pmod{a\_i}$$

for all $i$. By the Chinese remainder theorem, this is either impossible or it is equivalent to

$$x \equiv b \pmod{a}$$

where $a = \text{lcm}(a\_1,\dots,a\_n)$ and $b$ can be computed using the Chinese remainder theorem. In other words, the solutions are all of the form $b$, $b+a$, $b+2a$, $b+3a$, etc. From there it is easy to find the largest solution $x$ such that $x\le U$.
> 2 votes

---
Tags: algorithms, number-theory, mathematical-programming, primes
---


# Question
Title: What is the reasoning behind magic constancs in hash code calculations found in programming practice?
In real-world programming, we frequently need to compute hash codes for complicated objects. The main desired properties are that the values should

* be deterministic and
* have few collisions.

Let's assume we have access to robust hashing for basic data types such as integers, strings, etc. How do we combine multiple such hash codes to a single one, say for an array or a struct with several properties?

I immediately went for XOR-ing all "child" codes, figuring that the "spread" of the original hash function should be maintained, roughly. Apparently, I'm not alone.

However, if you google around, you find other approaches.

* Here an answerer proposes *adding* hash codes after perturbing them by some multiplication.
* This asker uses XOR but multiplies the individual codes with some numbers, apparently consciously choosing "large" primes.
* Here, the author states that "\[things\] have low values (favour the lower bits), so they should be combined with a multiplication to spread them across a wider bit range of the hash code".

The reasons given, if any, seem vacuous to me. Does multiplying already "random" values with a (small) constant really serve any purpose? Does it matter if the factor is a prime (which everybody seems to assume)?

# Answer
XOR is not a good method, because then the hash of $(a,b)$ will be equal to the hash of $(b,a)$. Also, the hash of $(a,a,c)$ will be equal to the hash of $(b,b,c)$ and to the hash of just $c$. That's not good.

A better method is to make the hash of $(a,b)$ be equal to $H(H(a) || H(b))$, where $H$ is your hash function on basic objects (ints, strings, etc.) and where I am using $||$ to represent concatenation of bit strings. This avoids all of those degeneracies.

The particular constructions you mention can be viewed as instances of that approach:

* The first link basically proposes using $H(a) + 37 \times H(b) \bmod 2^{64}$. That's equivalent to the construction $H'(H(a) || H(b))$ where $H'$ is a standard Rabin-Karp hash function.
* The second link is $1013 \times H(a) \oplus 1009 \times H(b) \bmod 2^{64}$. That has the form $H''(H(a) || H(b))$ where $H''(x||y) = c\_1x \oplus c\_2y$, which is also a reasonable hash function (though it takes a little bit of algebra to prove it).
* The third link is $(c \times H(a)) \oplus H(b) \bmod 2^{64}$ where $c$ is a prime. That's the same as the previous one, but with $c\_2=1$. It also turns out to be a reasonable hash function.

Does the constant multiplier (e.g., 37) need to be prime? No, it only needs to be relatively prime to the modulus. If the modulus is a power of two (as in these cases), it only needs to be odd. A prime is sufficient but not necessary. To obtain provably good results, the constant multiplier should be chosen at random; in practice, we fix a particular value and hope that will be close enough for practical purposes.

Another reasonable method is to use $H\_1(a) + H\_2(b)$ or $H\_1(a) \oplus H\_2(b)$ as the hash of $(a,b)$, where $H\_1,H\_2$ are two independently chosen hash functions. This also works.. but is a little more annoying to implement, because it requires us to have multiple hash functions.

Is there some theory here? Yes, you can prove that if $H\_1,H\_2$ are drawn uniformly at random from a 2-universal hash family, and $+$ is a group operator, then $H\_1(a)+H\_2(b)$ will be a 2-universal. The same is true for $H\_1(H\_2(a)||H\_2(b))$. I am not sure about what one can prove about $H(H(a)||H(b))$; I suspect it's not provably good in a generic sense, but is normally fine in practice.
> 6 votes

# Answer
You want to make sure that each distinct change to the data has a different effect.

This also means avoiding that changes in multiple fields can cancel each other out. If you simply summed the fields then {3,5} will be equal to {2,6}, if you add a factor of 7 to the second field then it's {9,5} that collides with {2,6} and everything in between won't collide.

Using factors that are mutually prime will reduce the number of collisions between objects that differ very little. Prime numbers are all mutually prime.
> 0 votes

---
Tags: data-structures, hash
---


# Question
Title: Must a deadlock necessarily occur if the four conditions exist?
I understand the four necessary conditions, mutual exclusion, hold and wait, no preemption, and circular wait, for deadlock to occur. However, does there exist a situation where the four conditions are true and the system is not in a deadlock state?

If a deadlock occurs, there exist the four conditions. However, if there exist the four conditions, is there necessarily a deadlock? What is an example where the four conditions exist, and a system is not in a deadlock state?

# Answer
> 3 votes
If you have a set of processes that wait for each other in a circular way, than you have a deadlock **in this particular moment**. This means that there is no situation where the four conditions are satisfied and there is no deadlock.

It may happen that a process stops waiting, for example due to some timeout mechanism realized by the developer. This breaks the circular wait relationship and the system continues to work.

The confusion often comes from the fact that conditions 1-3 are prerequisites for condition 4:

* Without mutual exclusion in the resource access, there is no reason for the processes to wait on anything, so the circle is never created.
* Without hold and wait, you have either only outgoing or only incoming connections for all the nodes (processes) in the dependency structure. Given that, you cannot form a circle.
* With preemption in place, you can always break the circle by taking a resource your are waiting for away from another process. Given that, you never end up in a waiting circle.

This shows that conditions 1-3 are system design properties, while condition 4 is a run-time situation. There is programming language research that tries to ge rid of the three design conditions, so that condition 4 becomes impossible by default.

# Answer
> 1 votes
If the four Coffman conditions exist, you have an existing deadlock. The circular wait condition guarantees at least two blocked processes exist, each waiting for a resource held by the other. The other conditions guarantee that there is no way the processes can ever leave the blocked state. Hence, deadlock.

---
Tags: operating-systems
---


# Question
Title: What does it mean the norm symbol applied to a concept?
I'm reading this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.14 or http://www.jmlr.org/papers/volume10/kontorovich09a/kontorovich09a.pdf

On page 1101 are introduced 2 functions without a precise definition. It is said that they are functions of the type $\textrm{f}:\mathbb{A} \rightarrow \mathbb{N}$ where $\mathbb{A}$ is a set. For example $\mathbb{A}$ can be a concept or an instance. For regular languages an instance can be a string on the alphabet and the concept a specific DFA (between all DFA on that alphabet) (alternately the concept can be defined as a subset of the set of sets made of all subsets on all the possible instances (namely a subset of $2^X$ where $X$ is the instance space namely all the possible instances). The instances on the subset are the $accepted$ instances, the others are $rejected$ ).

(http://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1655&context=cse\_research for precise definitions of instance and concept, look at definitions)

The 2 functions are : $\vert \bullet \vert$ that works on a instance (for example a string). Does mean this function? Can be the length of that instance?

The other function is : $\lVert \bullet \rVert$ and works on a concept (namely yours input is a concept). But I'm not able to imagine what this function means in this context and in the paper isn't explicated.

# Answer
> 3 votes
The only property that the functions $|\cdot|$ and $\\|\cdot\\|$ need to satisfy is that for every $n$ there is a finite number of $x$'s in the domain such that $|x|=n$ or $\\|x\\|=n$. The difference between the two is the domain: $|\cdot|$ is defined on $\mathcal{X}$ while $\\|\cdot\\|$ is defined on $\mathcal{C}$.

These functions are instantiated on page 1115: for $\mathcal{X} = \Sigma^\*$, $|\cdot|$ is the length of the word; and for $\mathcal{C}$ being the set of all DFAs on $\Sigma$, $\\|\cdot\\|$ is the number of states.

---
Tags: formal-languages, automata, regular-languages, notation, learning-theory
---


# Question
Title: Where have I gone wrong in "proving" this big-O identity?
(From CLRS -- 3-4,d)

Let $f(n)$ and $g(n)$ be asymptotically positive functions.

I tried to prove that $$f(n) = O(g(n)) \implies 2^{f(n)} = O\left(2^{g(n)}\right) .$$

I know that the above statement is false, so where have I gone wrong in my proof?:

> Suppose $f(n) = O(g(n)).$ Then there exist positive real numbers $c, n\_0$ such that for all $n \geq n\_0:$ $$0 \leq f(n) \leq c g(n).$$ Raising all sides to the power of 2, we have: $$0 \leq 2^{f(n)} \leq 2^{cg(n)}$$ (we can do this because $2^n$ is an increasing function).
>
> From this, we can say that $$0 \leq 2^{f(n)} \leq \underbrace{2^c}\_{\text{arbitrary constant}}\cdot 2^{g(n)}$$ so if $d = 2^c$, we can say that $2^{f(n)} = O(2^{g(n)})$.

(I now know that $f(n) = 2n, \ \ g(n) = n$ is an easy counterexample, but I'm still struggling to find the flaw in my "proof").

# Answer
> 1 votes
You should be able to work out the answer yourself. Here's the general procedure:

Since you know of a counterexample to the original claim, plug those $f,g$ into each step of your proof and find the first step in your proof where the proof goes wrong. In other words, find the first claim made in the proof that isn't correct for that choice of $f,g$. That will help you pinpoint the step in your proof that is flawed, i.e., that makes a conclusion that doesn't follow logically from the previous steps.

# Answer
> 0 votes
Your mistake seems to be in assuming that $a^n \cdot a^m = a^{nm}$. Rather, we have $a^n \cdot a^m = a^{n + m}$.

---
Tags: asymptotics
---


# Question
Title: Check if a binary tree is a perfect tree
I'm trying to write an algorithm to check if a given binary tree is a perfect binary tree, and of course with the lowest complexity.

I was thinking to calculate the height of the tree $h$ and the number of the nodes $n$, then if $2^{h+1} -1 = n$, it's a perfect tree. But then again, it's not very efficient.

The I thought to find the minimum tree height, and maximum tree height, and if they are equal, it's a perfect tree. But also this case, isn't much of improvement.

Any idea how to make it better?

# Answer
> 4 votes
Assuming you are given the root and nothing else, this problem has a lower bound of $\Omega(n)$.

---

An informal proof:

Consider an adversary who creates a perfect tree of height $h$ and size $n$. Now this adversary also has one extra node whose parent has yet to be determined.

The adversary, being sneaky, doesn't determine the parent of this node until you've checked every other node in the tree. To be more precise, the parent of this extra node will be the very last leaf node you check.

Clearly this will take $\Omega(n)$ time for any algorithm to determine this adversary has an imperfect tree.

---

That being said, you could find algorithms with a better *expected* time. For example, you could try non-deterministic algorithms such as random walks of the tree, then compare the lengths of these random walks to give a probability of perfectness. Although in any case, you won't do better than $O(n)$.

---
Tags: algorithms, binary-trees
---


title: Equivalent definitions of big O

text:
# Question
Title: Equivalent definitions of big O
> Let $A = \\{ g(n) \mid \exists c,n\_0 \\, \forall n \ge n\_0\colon g(n) \le cf(n) \\}$, and $B = \\{ g(n) \mid \exists c,n\_0 \\, \forall n \geq n\_0 \colon g(n) \< cf(n) \\}$.
>
> Prove $A = B$.

My solution:

* Let $f(n)$ and $g(n)$ be functions from $\mathbb{N}$ to $\mathbb{N}$.
* $g(n)\le cf(n)$ for all $n \> n\_0$.
* $g(n) = O(f(n))$ means $\exists c, n\_0 \forall n\colon n \> n\_0 \Rightarrow g(n) \le cf(n)$.
* To prove A, choose values for $c$ and $n\_0$ and prove that $n \> n\_0$ implies $g(n) \le cf(n)$.
* Choose $n\_0 = 1$.
* Assuming $n\>1$, find a $c$ such that $g(n)/f(n) \le cf(n)/f(n) = c$.
* This shows that $n\>1$ implies $g(n)\le cf(n)$.
* $n\>1$ implies $1\<n$, $n\<n^2$, $n^2\<n^3$, and so on.

My problem: Given an equation I know how to get $c$ and $n\_0$. But now given the definition, how can I prove that there exist $c$ and $n\_0$ in that big O definition in order to get the result A=B?

# Answer
Clearly, $B \subseteq A$, since $\lt$ implies $\le$.

Assuming that $f(n)$, $g(n)$ and $c$ are always positive,

If $g(n) \le c f(n)$, then $g(n) \lt (c + 1) f(n)$.

So, if we can find a $c$ that satisfies $A$, we can find one that satisfies $B$.

It follows that $A \subseteq B$, hence that $A = B$.
> 2 votes

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


title: Transitive Amstrong Rules

text:
# Question
Title: Transitive Amstrong Rules
I have R={A,B,C,D,E} with functional dependencies ABCD → E and AC → ABCD,with Axiom of transitivity rule is AC → E a transitive dependency? Thanks before and sorry for this simple question

# Answer
> 0 votes
From the definition of transitive dependency -

A functional dependency is said to be transitive if it is indirectly formed by two functional dependencies. For e.g.

X -\> Z is a transitive dependency if the following three functional dependencies hold true:

```
X->Y
Y does not ->X
Y->Z

```

Given, ABCD-\>E and AC-\>ABCD, or simply AC-\>BD

So, ABCD -\> E can be written as AC -\> E, as AC-\>BD.

So, the transitive rule is not required to prove AC -\> E

Also, if we take X= AC, Y=ABCD, then X-\>Y (given) but X is subset of Y

So, Y-\>X (failing the second rule for transitivity)

---
Tags: database-theory
---


title: Is there always a worse algorithm?

text:
# Question
Title: Is there always a worse algorithm?
Is the following true?

> Given a problem with a known algorithm of time complexity $g(n), \exists$ another algorithm to solve said problem with time complexity $f(n). \\,\\,\\, f(n): g(n) = o(f(n)) $

If true, it implies that:

1. For all problems, there are algorithms of arbitrarily high complexity that can solve it.
2. For all problems, the number of distinct algorithms that can solve it is infinite.
3. It is always possible to do worse (implicit in $1$).

# Answer
> 6 votes
Given any algorithm $A$, the algorithm "run $A$ $n$ times" has asymptotically worse running time.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Does this problem offer any insight into $P$ vs $NP$
> What is the input of a given hash?

The problem can be verified in polynomial time (using a hash that executed in polynomial time), and I suspect that it may be possible to prove that there is no algorithm that can solve it in polynomial time.

Take a binary string $X$ of length $n$.
The number of possible values for $X$ is $2^n$.
Solving the problem by using a hash table still involves initially calculating the hashes for all $2^n$ variations, so I'm not sure if it can be counted. But if hash tables are permitted, and generation of the hash table is not included in the cost, then time complexity goes down to $O(n)$, (binary search on the elements of the (sorted) hash table gives a time complexity of $O(\log(2^n)) = O(n)$.
I feel if we permit hash tables to reduce the asymptotic complexity, then we should permit similar methods to reduce the asymptotic complexity of problems. Hash table generation is $O(2^n)$ and I feel this should be accounted for.

# Answer
> 7 votes
It depends what your hash function is. If your hash function is the identity function, it's trivial to invert without constructing the hash table.

Your question seems to be essentially reinventing the idea of one-way functions. A one-way function is a function that can be computed in polynomial time but whose inverse cannot be. It is well known that the existence of one-way functions would imply that $\mathrm{P}\neq\mathrm{NP}$.

# Answer
> 1 votes
If a problem has a polynomial reduction to another problem known to be in P then the problem is also in P.

The transformation from the problem of reversing the hash to hashtable lookup is not polynomial (generating all the entries). Which means you can't say anything about P-ness of the original problem.

The problem of reversing a hash is usually stated by giving as input the algorithm of the hash and an output of that algorithm. That is the actual problem.

Adding a hash table means spending exponential time to speed things up later. however from the perspective of the original problem statement it's still a $O(2^n + 1)$ algorithm.

As a comparison finding a wether a value is in an unordered array takes $O(n)$ time. You can sort the array in advance but that takes $O(n \log n)$ time but speeds up the actual finding operation down to $O(\log n)$ time. The end result is an algorithm that takes $O(n \log n + \log n) = O(n \log n)$ time.

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


title: Never Brute Force?

text:
# Question
Title: Never Brute Force?
> Does there exist a more optimum algorithm to solve every problem than brute force (or an equivalent)?

A brute force algorithm for the purpose of this question is defined as an algorithm of time complexity $N^\*$, there $N^\*$ is the cardinality of the set of all possible solutions.

# Answer
No. For every decision problem, the cardinality of the set of possible solutions is two: "yes" and "no". It is not the case that all problems can be solved in constant time.
> 2 votes

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


# Question
Title: Aren't the servers that store MYSQL database in Facebook down for maintenance ever as Facebook is always on?
I have never seen my account not being able to login!

# Answer
The databases of any large service are replicated across many machines. This means that the service itself will be available unless many of those machines fail simultaneously, which is very unlikely. Also, by spreading those machines around the world, it becomes very unlikely that something like a power cut will take out all the servers; it also means that customers in Australia don't have lots of lag from having to authenticate against a server in the USA, for example).
> 1 votes

---
Tags: distributed-systems, databases
---


title: What does "Quick" mean?

text:
# Question
Title: What does "Quick" mean?
> What does quick/fast mean in the context of computer science?

I couldn't find a definition online (poor google fu), and I want to provide a referenced/cited definition for fast for an article I'm writing.

# Answer
> 8 votes
It's a completely informal term. It has no fixed definition. Just as "He was driving quickly" doesn't define any exact range of speeds.

And, just like the driving example, what would be considered "quick" depends on context. If you gave me a $\Theta(n^3)$ algorithm for graph isomorphism, I'd bite your hand off; if you gave me a $\Theta(n^3)$ algorithm for sorting, I'd think you were an idiot.

# Answer
> 1 votes
Sometimes "a fast algorithm" means "a polynomial-time algorithm". But this is always informal, and depends on the context.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Finding all edges of an undirected graph which are in some cycle in linear time
As a reduction from another problem, I am trying to deal with finding all edges which are part of some cycle in an undirected graph $G=(V,E)$ in time $O(|V|+|E|)$.

My first idea is to use DFS and search for back edges closing cycles, but then the issue is how to add all edges found to the cycle, if we just naively add all edges each time we find a cycle the algorithm might not be linear as each edge can appear in multiple cycles (a k-clique, for example).

So my current "best" approach of counting the cycles is first building the entire DFS tree, noting where back edges are present, and then traversing the tree in DFS from the root, where each time a back edge (going forward down the tree this time) is encountered, mark all edges as being part of a cycle, and if an edge is already marked break the loop.

I can prove the approach is linear, but I'm having issues proving it actually finds all edges as required. And was wandering if there is either an easier approach or a relatively simple proof that my approach works I'm missing.

# Answer
> 5 votes
It is not difficult to prove that an edge is a cut-edge if and only if it does not lie on a cycle. So you can find the set $E'$ of cut edges, and what you are then looking for is $E \setminus E'$.

For finding $E'$, there are several well-known linear-time algorithms. Wikipedia gives e.g., Tarjan's bridge-finding algorithm.

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


title: BVL Balanced Tree

text:
# Question
Title: BVL Balanced Tree
I have an issue about proving the next problem:

Let's define a BVL tree, which is a binary tree, who satisfied the feature that the difference between the heights of the children of a node, is at most 2.

Meaning|height(node.left) - height(node.right)| \<= 2 Prove that BVL tree is a balanced tree.

Now I do know it's some kind of extension of AVL tree. Well, as we know, the defenition of a balanced tree is related to its height, which is O(logn)

However, trying to perform an induction on N for BVL tree, ends with failure..

Can someong turn on the light and give me a hint?

Thanks!

# Answer
> 4 votes
If you want to show that the height is $h=\mathcal O(\log(n))$ then I would suggest the following:
Define $n\_h$ as the minimum vertices in tree with height $h$
Then to get the minimum vertices for given height:
$n\_h = n\_{h-1} + n\_{h-3}\\ n\_h \ge 2n\_{h-3}$

Now from the inequality you know that:

$n\_{h-3} \ge 2\*n\_{h-6}$

(Just changing index)

Placing it to the former inequality doing it again and again:

$n\_h \ge 2n\_{h-3} \ge 2 * (2n\_{h-6}) \ge 2 * 2 * (2n\_{h-9}) \ge ...\ge 2\*2\*...\*2\*c\\\$
So lets say that you did 'i' iterations, then $n\_h \ge 2^i\*c$

$\Rightarrow n\_h \ge 2^i\*c$
where $c$ is the minimum amount of vertices in the base case and $c \ge 1$
The recursion will stop when the index will be ($0/1/2$):

$\Rightarrow h - 3 - 3i = 0\\ \Rightarrow i = \frac{h-3}{3}\\ \Rightarrow n\_h \ge 2^\frac{h-3}{3}\\ 3(1 + \log(n\_h)) \ge h\\ \Rightarrow h = \mathcal O(\log(n))$

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


title: Finding errors in weighted graphs

text:
# Question
Title: Finding errors in weighted graphs
I have a weighted graph where each edge is a 1d vector eg if weight going from A to B is 1 then from B to A it is -1. In the graph each cycle should add to zero though sometimes the weights have errors and in that case a cycle will not add to zero.

So for example if the weight from A to B is 1 and B to C is 1 then for the cycle to sum to zero C to A must be -2 and there is an error if it is anything else. Please note that in general the cycles can involve an arbitrary amount of nodes.

What is the best algorithm for detecting these errors? IE what is the best algorithm for finding all weights that have errors and so are causing the cycles to add to a non zero value?

# Answer
One approach is to compute the distance $d(u,v)$ between each pair $u,v$ of vertices using an all-pairs shortest paths algorithm, such as Floyd-Warshall. Then, if $d(v,v) \< 0$, you know that there exists a cycle through $v$ that doesn't add to zero. You can explicitly find one such cycle by augmenting the shortest-paths algorithm with predecessor links to keep track of an example shortest path from $v$ to $v$. Then you know that at least one of the edges along that cycle has an error.

Unfortunately there doesn't appear to be any way to uniquely determine *which* edges are in error. For instance, consider a graph with edge $a \to b$ of weight $1.01$ and edge $b \to c$ of weight $-1.48$ and edge $c \to a$ of weight $0.50$; you know that at least one of those edges has an error, but there's no way to know which one; it could even be all of them that have an error.
> 2 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: Rules of converting a weighted digraph to an undirected graph?
What are the rules of converting a weighted digraph to a weighted, undirected graph?

I understand that the edges should go in both directions from vertex to vertex. However, do the weights of each edge to/from other edges need to be the same? If not, how does one decide which weight to attach to the undirected vertices?

For example, can this adjacency matrix representation of a weighted digraph be converted into an undirected weighted graph?

# Answer
There aren't any rules. Do whatever is most appropriate to your specific situation. What do the weights *mean*? That should probably tell you what weights to use in the new graph.

If there is no meaning, translation doesn't make sense: translation is, by definition, an operation that preserves meaning. For example, suppose I give you the following exercise:

> Translate the program `function int int (hello_) repeat end begin int` into Java.

The program doesn't mean anything so it can't be translated. You can't possibly give me a Java program and say "This is the right one" because there's no definition of "right". Similarly, without saying what the edges and weights of some digraph mean, there's no way to justify the claim "This undirected graph is the correct translation."

There's no intrinsic equivalence between directed and undirected graphs. Usually, one associates an undirected graph with the directed graph in which every edge is replaced by a directed edge in each direction. In many contexts, these behave the same way (e.g., if I can get from A to B in the graph, I can follow the same route in the digraph). In other circumstances, though, they might be different. For example, an undirected edge might represent the existence of a two-way road between two cities, whereas a pair of directed edges might represent separate one-way roads in each direction.
> 2 votes

---
Tags: graphs, weighted-graphs
---