# Question
Title: Understanding Hamiltonian Path, NP vs Co-NP
I am having difficulty understanding the distinction between NP and Co-NP.

According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language:
*HAMPATH = { (G,s,t) | G is a directed graph with a Hamiltonian path from s to t}*, there exists a nondeterministic Turing Machine *M* that can decide this problem in polynomial time. I understood this to mean that for some input *(G,s,t)*, *M* accepts if G has a Hamiltonian Path from s to t, and *M* rejects if G does not have a Hamiltonian Path from s to t, both in polynomial time.

However, the book also says that *!HAMPATH = { (G,s,t) | G is a directed graph with no Hamiltonian path from s to t}* is in Co-NP, so it is not known to be in NP.

Why couldn't the same NTM for HAMPATH be used to decide !HAMPATH, except that it returns the opposite state?

# Answer
> 1 votes
A nondeterministic Turing machine is perhaps more clearly viewed as a Turing machine with two inputs: one is the actual input, in your case $\langle G,s,t \rangle$, and the other a polynomial size "witness", in your case a purported Hamiltonian path $p$. The machine checks, in polynomial time, that $p$ is indeed a Hamiltonian path from $s$ to $t$ in $G$, and if so, accepts; otherwise it rejects.

In what sense does this machine $M$ nondeterministically accept $\mathsf{HAMPATH}$?

* If $\langle G,s,t \rangle \in \mathsf{HAMPATH}$ then there exists a witness $p$ such that $M(\langle G,s,t \rangle,p)$ accepts.
* If $\langle G,s,t \rangle \notin \mathsf{HAMPATH}$ then $M(\langle G,s,t \rangle,p)$ rejects for *all* values of $p$.

Now consider the machine $!M$ which accepts when $M$ rejects and rejects when $M$ accepts.

* If $\langle G,s,t \rangle \in \mathsf{!HAMPATH}$ then $!M(\langle G,s,t \rangle,p)$ accepts for all values of $p$.
* If $\langle G,s,t \rangle \notin \mathsf{!HAMPATH}$ then there exists a witness $p$ such that $!M(\langle G,s,t \rangle,p)$ rejects.

As you can see, $!M$ doesn't have the same promises regarding $\mathsf{!HAMPATH}$ that $M$ has regarding $\mathsf{HAMPATH}$.

# Answer
> 0 votes
Nondeterministic can machines have multiple computation paths for each input. The machine accepts if at least one computation path accepts, regardless of how many reject.

So, consider a nondeterministic Turing machine $M$.

* If all paths on input $x$ accept, then $M$ accepts $x$.
* If some paths on input $y$ accept, and some reject, then $M$ accepts $y$.
* If all paths on input $z$ reject, then $M$ rejects $z$.

Now, suppose that we swap the accepting and rejecting states of $M$ to make a new machine, $M'$.

* All paths on input $x$ reject, so $M'$ rejects $x$.
* Some paths on input $y$ reject, and some accept, so $M'$ accepts $y$.
* All paths on input $z$ accept, so $M$ accepts $z$.

So we see that $M'$ doesn't accept the complement of the language accepted by $M$, since both machines accept $y$.

---
Tags: np, nondeterminism, co-np
---


# Question
Title: "Ways to make change for a dollar": How to optimize with constraints
I'm working on an algorithm that takes a number of unit coins (\[1, 2, 5, 10\] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for it. In the case of this testset the solution is 16.

```
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2
etc
5, 5, 2, 1
10, 1, 1, 1
10, 2, 1
Total number of ways: 16

```

I've first tried making a list of these permutations, but that generally was slow and unwieldy. There is no need to give every permutation just the amount of them: 7/10 test cases were able to be done under 5 seconds.

So I went looking around and found this. Where a Haskell solution to a similar problem was used. I just had to make it more general for my needs and translate it in a language I could actually run (e.g. Python). I did and I ended up with the following:

```
def change(list, number):
    if (number is 0):
        return 1
    if (len(list) is 0):
        return 0
    if (number < list[0]):
        return 0

    return change(list, (number - list[0])) + change(list[1:], number)

print(change([1, 2, 5, 10], 13)) #prints 16 (list needs to be in order btw)

```

This solution is better then the first one: 9/10 test cases succeeded. However this can be done better! I've yet to talk about the constraints of this assignment.

* There are no more then 8 unit coins (`len(unit_coins) <= 8`)
* The unit coins are never more then 250 (`unit_coin <= 250`)
* The amount of money is between 0 and 300 (`0 < money < 300`)
* **There is always a unit coin with a value of 1**

The last part is important (you can tell, because I've highlighted it). The current solution is absolutely not taking advantage of that, and I thing there's a lot to be gained when this is used in the function.

Does anyone have an idea how to to the thing I just described. Any help would be greatly appreciated. More general answers are also welcomed as this type of optimization isn't exclusive to this perticular algorithm.

P.S. I know Python isn't a very quick language, but that's not the point of this exercise. This exercise is about making the whole algorithm better, not just a specific implementation in a certain language.

# Answer
The way I understand this, it seems to be the classic coin change problem with a few constraints which you have provided. Although if we try to consider all the subsets of the available coins this problem will definitely take exponential time in terms of number of coins available. (The size of the power-set , each subset has to be considered although few optimizations exist but still it doesn't reduce the time to polynomial). For reducing the time taken we can employ the optimization called memorization.

> return change(list, (number - list\[0\])) + change(list\[1:\], number)

If you see the line closely in your solution you can see the problem has overlapping subproblems which will be computed again and again. For optimization we try to remember the results of the subproblems and return this precomputed result if we encounter the same sub-problem again.However, as you can guess there is a space-time trade-off here. For speeding up we need to remember the results for this we need atleast $\mathcal{O}({n})$ space (n is the sum which we are trying to make.).

For overlapping subproblems consider the example of making a sum of N using coins 2,3 and, 5.

Suppose solution is given by F(n), then

let us choose the permutations i can make using 2:

Then F(n) = 1+F(n-2)

Now let us choose coin 3:

F(n) = 2+F(n-5) . . . . We calculate this quantity and return the result. However suppose if we choose 5 in the starting step.

then F(n) = 1+ F(n-5)

We now have to calculate F(n-5) again. Hence overlapping subproblems exist.

For the constraints which you have mentioned we can add those constraints by maintaining a count of each coin as well as total count of the coins used at each step of the recursive call to our function (In the function which is named $change(list, number)$ in your implementation ) we can check the constraint and add zero as the result of that particular function call as it generated an invalid permutation. valid permutation contributes to a 1 in our function. Our function will look something like this :

```
def change(list, number, countCoinsList, totCount):
if (number is 0):
    return 1
if (len(list) is 0):
    return 0
if (number < list[0]):
    return 0
if(countCoinsList[i]<8)
     countCoinsList[i]+=1
     tmp1= change(list, (number - list[i]),countCoinsList,totCount+1)

 tmp2= change(list[i+1:], number,countCoinsList,totCount)
return  tmp1+tmp2;

```
> 1 votes

---
Tags: algorithms, efficiency, coin-change
---


# Question
Title: DES encryption - what happens if all sub-keys are the same?
What will happen if we change the DES encryrption algorithm to use the same key in each round ?

How will it affect the encryption - will it **only** make the encryption same as decryption or are the more effects ? I couldn't find any other possible effects in the DES standard description.

Thanks

# Answer
> 2 votes
It will make the algorithm insecure.

It will be become vulnerable to slide attacks.

It will make encryption become equivalent to decryption, which is a weakness. This is sometimes called a "weak key"; with your scheme, every key will be "weak".

It will also reduce the keyspace to 48 bits, which is too small to be secure.

---
Tags: algorithms, cryptography, encryption
---


# Question
Title: Run Christofides algorithm by hand with wrong result
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides\_algorithm#example

The graph:

Calculate minimum spanning tree T:

Calculate the set of vertices O with odd degree in T. They are the same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O (as all are odd, this should give us the original graph):

Construct a minimum-weight perfect matching M in this subgraph (**I am not sure if I did this right**)

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

This is definitely not right. ***What went wrong?***

# Answer
> 3 votes
In fact, **you have been correct all along**. However, you have not finished Christofides algorithm yet.

The next step is "Calculate Euler tour".
In the last picture, you have obtained a multigraph all of whose vertices have even degrees. So it must have an Eulerian path. For example, let us select the Eulerian path A -\> F -\> A -\> C -\> B -\> D -\> E -\> D -\> A.

The last step is "Remove repeated vertices, giving the algorithm's output".
Removing the second A and the second D on that above path, we obtain a wanted output, A -\> F -\> C -\> B -\> D -\> E -\> A. Done.

---

Please note it is not very meaningful to apply Christofides algorithm on the given graph.

"The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality". The given distances do not obey the triangle inequality, since d(B,D) + d(D, E) = 1 + 4 \< 6 = d(B,E). Moreover, the (direct) distance between A and B is not given, raising doubt whether this is a travelling salesman problem at all.

---
Tags: algorithms, graphs, approximation, traveling-salesman
---


# Question
Title: Reusing variable in converting grammar to Chomsky Normal Form
I'm not sure if reusing variable is allowed in CNF.
For example, I have this grammar not in CNF. So I have to convert it to CNF. `1. S->abAB|abB|abA|ab
2. A->bAa|ba
3. B->BAa|bAa|ba|Ba|Aa|a`
For conversion, I'm using a convention where new variables and terminals are in the form `(V1,V2,V3,...,Vk) for k > 0
Ti where i are terminals (a,b,c,...,z)` `Introduce new terminals for each terminal in the grammar
S->(Ta)(Tb)AB|(Ta)(Tb)B|(Ta)(Tb)A|(Ta)(Tb)
A->(Tb)A(Ta)|(Tb)(Ta)
B->BA(Ta)|(Tb)A(Ta)|(Tb)(Ta)|B(Ta)|A(Ta)|a
Ta->a
Tb->b`
For the purpose of my question, I'm only focusing only on `B` productions due to the repetition of `A(Ta)`. `...
B->BV1|(Tb)V2|(Tb)(Ta)|B(Ta)|A(Ta)|a
V1->A(Ta)
V2->A(Ta)
...`
See `V1` and `V2`, they have the same right-hand side that is `A(Ta)`.

# Answer
> 0 votes
"Chomsky normal form" is something a grammar *is*, rather than the specific procedure used to make it. So nothing prevents you from reusing a symbol like that; the grammar will still be CNF if you do.

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


# Question
Title: Variance of MAXSAT clause satisfiability
For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment.

Is it likewise possible to compute the variance of the number of clauses satisfied? And I mean an exact computation, not an estimate.

In general, which moments are easy to compute, and which are hard?

I would prefer an answer for general MAXSAT but would also be interested in the special case of MAX-3-SAT.

# Answer
> 2 votes
Suppose that the MAXSAT instance consists of clauses $C\_1,\ldots,C\_m$. Denote by $X$ the expected number of clauses satisfied by a random assignment. Then $$ \mathbb{E}\left\[\binom{X}{d}\right\] = \sum\_{\substack{S \subseteq \[m\] \\ |S|=d}} \Pr\[C\_i \text{ is satisfied for all } i \in S\]. $$ This gives a roughly $O(m^d)$ algorithm for computing the $d$th moment.

---
Tags: satisfiability, probability-theory
---


# Question
Title: What's the connection between the two "Fast Walsh Transform"?
First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$ in $O(n \log n)$ time, using an algorithm called **Fast Walsh Transform**, where $n$ represents the length of the binary digits.

However, when looking at wikipedia page, it says that the Walsh Transform is to accelerate the evaluation of an $n \times n$ Matrix called Walsh Matrix. I also found it reasonable.

My question is, what's the connection between the two evaluations? I know that a convolution is a linear transformation and can be represented as a vector multiplied by a matrix. But **where's the matrix in the First convolution**? I am so confused, and does it represent that some multiplications with specified matrixed could be accelerated to $O(n \log n)$? (Thus the matrix is $n \times n$)

# Answer
> 2 votes
Suppose that $A$ and $B$ are vectors of length $n$, where $n$ is a power of 2. We index $A$ and $B$ using binary vectors of length $\log\_2 n$, and define their convolution $C$ as $$ C\_i = \sum\_{j \oplus k = i} A\_j B\_k. $$

You can calculate the convolution of $A$ and $B$ using the following algorithm:

* Compute the Walsh transform of $A$: $\alpha = H\_n A$.
* Compute the Walsh transform of $B$: $\beta = H\_n B$.
* Multiply $\alpha$ and $\beta$ pointwise: $\gamma(S) = \alpha(S)\beta(S)$ for all $S$.
* Compute the inverse Walsh transform of $\gamma$: $C = H\_n^{-1} \gamma$.

(Note that up to normalization, $H\_n^{-1}$ and $H\_n$ are the same matrix.)

The way we compute the convolution of $A$ and $B$ is using the Walsh transform and its inverse. The Walsh transform itself simply consists of multiplying a vector by the Walsh matrix, which can be done in $O(n\log n)$ time. Since the third step takes only $O(n)$ time, the entire algorithm runs in $O(n\log n)$.

---
Tags: discrete-mathematics, linear-algebra, fourier-transform, matrix
---


# Question
Title: Practical applications of Weighted Independent Set in path graph?
Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path.

Does this problem have practical applications? What are some? This problem is used in many CS courses as an intro to the dynamic programming paradigm, but I don't see any mention about whether this is useful practically or whether it is only mentioned for didactic purposes.

# Answer
> 3 votes
I don't think that the weighted independent set problem in paths has many applications. However, as you point out yourself, it is a very good introduction to dynamic programming *and* to algorithmic graph theory; This is one of very many problems that are NP-complete on general graphs but become simpler (or indeed trivial) on restricted input instances.

When you know, and understand, the algorithm for (weighted) independent set in paths, it is not too hard to generalize this to (weighted) independent set in trees and even to graphs of bounded pathwidth and treewidth.

I think that this problem on paths (maybe even on trees, but here I'd love to be corrected) is purely educational. Indeed, I have hard times finding reasonable applications to Independent Set as well as Vertex Cover, Clique and Dominating Set.

# Answer
> 1 votes
This amounts to an application: Suppose there are service areas on a certain long highway, every 20 miles. A company wants to open up restaurants at some of these sites. It estimates a potential revenue from each site. The company would not want to open up restaurants that are within 30 miles of each other (to avoid self-competition).

This can be modeled as node weighted path graphs where each site is a node, weight is the estimated revenue from the site and two successive sites make edges between them. A max node weighted independent set in this graph is the revenue maximizing non competing sites.

---
Tags: algorithms, graphs, dynamic-programming
---


# Question
Title: Avoiding underflow when identifying neighbours of a cell in a grid by using modulo
I'm going through a tutorial that is using the Game of Life as example code. It has a function in it that finds the neighbor of a given cell. It is explained quickly that "When applying a delta of -1, we add self.height - 1 and let the modulo do its thing, rather than attempting to subtract 1" which would require a bunch of conditional logic to check for edge cases (when the cell we are checking is on the edge and simply adding or subtracting from its position would put it out of bounds)... This is the algorithm:

for a given 0-indexed `row` and `col` in a 2d space with area `width * height`:

```
for delta_row in [height - 1, 0, 1]
    for delta_col in [width -1, 0, 1]
        if delta_row == 0 && delta_col == 0
            continue // this is the cell we are checking

        neighbour_row = (row + delta_row) % height
        neighbour_col = (col + delta_col) % width

```

Anyways, I'm just wondering, how does someone figure this out from the naive case, where you just add and subtract and check for bounds? I'm not great with math but I'm assuming there might be a way to explain this algebraically? I worked through this with actual numbers for a while to verify it and just want to get a better understanding of how this works so maybe I can use this concept again later.

# Answer
Using modular arithmetic here is equivalent to playing the game of life on a torus. Suppose you start with a $100\times 100$ grid with rows and columns numbered $0, \dots, 99$. The modular arithmetic says that $0-1\equiv 99$, which means that row $99$ is above row $0$ as well as below row $98$ and, similarly, column $99$ is to the left of column $0$ as well as to the right of column $98$.

This isn't equivalent to saying that there is nothing above row $0$ and nothing below row $99$.
> 1 votes

---
Tags: linear-algebra
---


# Question
Title: My code works, But how do I make this code run in a deterministic time?
**The Problem: Given 3 inputs Bounce, Ball drop height, and ball view height.**

How do I calculate the number of times the observer can see the ball pass. So my code gives correct output, but it takes a longer time as bounce approaches 1, how do I make it deterministic in nature.

```
def bouncingBall(h, bounce, window):
    BounceFactor = bounce
    BallDropHeight = h
    ViewerHeight = window
    BounceLeft = h
    BallSeenTimes = 1
    if bounce > 1 or bounce < 0 or window >= h or h ==0:

        return -1
    else:
        while (BounceLeft > ViewerHeight):
            BounceLeft = BounceLeft * BounceFactor
            if (BounceLeft > ViewerHeight):
                BallSeenTimes = BallSeenTimes + 2
            else:
                break
        return BallSeenTimes

```

*I am not looking for code answers, just the direction in which I need to think. Currently, I think If I could somehow establish a linear relationship and create a function to "guess" the passes it would be faster.*

# Answer
> 0 votes
Your code *is* determinstic: it uses no randomness. But I assume you want the running time to be essentially independent of the input.

Assuming I've understood the problem correctly, you're dropping a ball from height `h` and, when dropped from height `x`, it bounces to height `x*Bouncefactor`. You want to know how many times it passes through the height you're calling `window`. Your approach is, essentially, to simulate the bouncing ball and count.

Instead of doing that, you should just calculate how many times the ball bounces before it's at height less than `window`. This is the least `k` such that `h * Bouncefactor^k < window`, so you just need to solve this equation and then convert the number of bounces into the number of times that the ball is seen.

---
Tags: algorithms, time-complexity, runtime-analysis, python
---


# Question
Title: Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?
Having two bit strings $x,y \in \left\\{0,1\right\\}^n$, where $x$ is selected following a uniform distribution but $y$ is not.

Is $z = x \oplus y$ uniform?

# Answer
Yes, if $x$ and $y$ are chosen independently of each other.

One way to quickly see this is to note that the map $x \mapsto x \oplus y,$ for some constant $y,$ is a permutation of $\\{0,1\\}^n.$ This means that if $x$ is uniformly distributed over $\\{0,1\\}^n$ and $y$ is constant, then $x \oplus y$ is also uniformly distributed. And since $x \oplus y$ is uniformly distributed for *every* constant $y,$ it follows that, if we make $y$ itself a random variable (independent of $x$), then the distribution of $x \oplus y$ will be a mixture of uniform distributions, and thus uniform.

Or we can just do the math:

$$\begin{aligned} {\rm P}(x \oplus y = a) &= \sum\_{b \in \\{0,1\\}^n} {\rm P}(x \oplus y = a \land y = b) \\ &= \sum\_{b \in \\{0,1\\}^n} {\rm P}(x = a \oplus b \land y = b) \\ &= \sum\_{b \in \\{0,1\\}^n} {\rm P}(x = a \oplus b)\ {\rm P}(y = b) & (x \perp y) \\ &= \sum\_{b \in \\{0,1\\}^n} \frac1{2^n}\ {\rm P}(y = b) & (x \sim \mathcal U\\{0,1\\}^n) \\ &= \frac1{2^n} \sum\_{b \in \\{0,1\\}^n} {\rm P}(y = b) \\ &= \frac1{2^n}. \end{aligned}$$

However, the assumption of independence is absolutely necessary here — without it, it's easy to come up with counterexamples, such as letting $x$ be uniformly distributed over $\\{0,1\\}^n$ and letting $y = x,$ which of course implies that $x \oplus y = 0^n.$
> 3 votes

---
Tags: probability-theory, cryptography, xor
---


# Question
Title: Does a subcubic algorithm exist for the following problem?
Given a symmetric real $n \times n$ matrix $A=(a\_{ij})$, is there an algorithm which computes the sum $$\sum\_{i,j,k}\max(a\_{ij},a\_{ik},a\_{jk})$$ over all $1\leq i\<j\<k\leq n$ with time-complexity better than $O(n^3)$?

# Answer
There exists a quite practical approach that works in $O(n^3 / w)$ time, where $w$ is the number of bits in the processor word. The main idea is that you iterate over the elements of the matrix one by one in the increasing order (break ties arbitrarily) and "switch them on". Consider the moment when the largest element of some triple $a\_{ij}, a\_{ik}, a\_{jk}$ is switched on. For simplicity, let's assume that the said element is $a\_{ij}$. It is natural to add the value of the triple to the answer now, when the last element is switched on. So we have to count the number of possible $k$'s such that $a\_{ik}$ and $a\_{jk}$ are already switched on (that would be the number of triples, here $a\_{ij}$ is the largest element, so they were completely switched on just now). Here we can speed up the naive $O(n)$ implementation by using bit optimisation.

For details you can refer to the following implementation in C++11 that should work for $n \leqslant 5000$, $|a\_{ij}| \leqslant 10^9$ (it is not very optimized; however, it still beats naive summation for $n = 5000$ by large margin at least on my machine).

```
// code is not very elegant,
// but should be understandable
// here the matrix a has dimensions n x n
// a has to be symmetric!
int64_t solve (int n, const vector<vector<int32_t>> &a)
{
        std::vector<boost::dynamic_bitset<int64_t>> mat
        (n, boost::dynamic_bitset<int64_t>(n));

        vector<pair<int, int>> order;
        for (int j = 1; j < n; j++)
        for (int i = 0; i < j; i++)
            order.emplace_back(i, j);
        sort(order.begin(), order.end(),
            [&] (const pair<int, int> &l, const pair<int, int> &r)
            {return a[l.first][l.second] < a[r.first][r.second];});

        int64_t ans = 0;
        for (const auto &position : order)
        {
            int i, j;
            tie (i, j) = position;
            mat[i][j] = mat[j][i] = 1;
            // here it is important that conditions
            // mat[i][i] = 0 and mat[j][j] = 0 always hold
            ans += (mat[i] & mat[j]).count() * int64_t(a[i][j]);
        }

        return ans;
}

```

If you consider using bit optimisations cheating, you can use four russians method to the same result here, yielding a $O(n^3 / \log n)$ algorithm, which should be less practical (because $w$ is pretty large on most modern hardware) but is theoretically better. Indeed, let's choose $b \approx \log\_2 n$ and keep each row of the matrix as an array of $\lceil \frac{n}{b} \rceil$ integers from $0$ to $2^b - 1$, where the $i$-th number in the array corresponds to the bits of the row ranging from $ib$ inclusive to $\min(n, (i + 1)b)$ exclusive in $0$-indexation. We can precalculate the scalar products of every two such blocks in $O(2^{2b} b)$ time. Updating a position in the matrix is fast because we are changing only one integer. To find the scalar product of rows $i$ and $j$ just iterate over arrays corresponding to that rows, look up scalar products of the corresponding blocks in the table and sum up the obtained products.

The above paragraph assumes that operations with integers $\leqslant n$ take $O(1)$ time. It is quite common assumption, because it usually does not actually change the comparative speed of the algorithms (for example, if we don't use that assumption, brute force method actually works in $O(n^3 \log n)$ time (here we measure time in bit operations) if $a\_{ij}$ take integer values with absolute values at least up to $n^{\varepsilon}$ for some constant $\varepsilon \> 0$ (and otherwise we can solve the problem with $O(n^{\varepsilon})$ matrix multiplications anyway); however the four russians method suggested above uses $O(n^3 / \log n)$ operations with numbers of size $O(\log n)$ in that case; so it makes $O(n^3)$ bit operations, which is still better than brute force despite the change of the model).

The question about existence of $O(n^{3 - \varepsilon})$ approach is still interesting, though.

Techniques (bit optimisations and four russians method) presented in this answer are by no means original and are presented here for completeness of the exposition. However, finding a way to apply them was not trivial.
> 4 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Do multiple transitions over the input give finite state machines more power?
In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state to another without reading a character. However, the movement over the input string is still unidirectional.

Is there a formal model of a FSA that reads the input string K times, and only then reaches its final state? is this model more powerful than FSA, e.g., can it recognize context-free languages that are not regular?

I think the option of adding an epsilon transition for every transition edge in the FSA means the models are equivalent in power (since we can model K iteration over the input by epsilon transitions from the last state back to the first -- although I am not sure), but if this is so, are there any results regarding the number of states needed in a regular FSA and a FSA with K transitions?

# Answer
> 5 votes
Multiple passes do not add any power.

It's possible to do all the passes in parallel, using a state machine whose states are vectors of states in the original machine. Each vector has one element for each state in the original machine, and represents the result of performing the transitions starting at the state corresponding to the position of the element in the vector. A vector state is an accepting state iff there is a path of length $k$ starting at the original machine's starting state and linking the state at each position to that position.

Specifically, let the original machine be $(Σ, Q, q\_1, δ, F)$, where $Q = \\{q\_1, \ldots, q\_n\\}$. Define the new machine $(Σ, Q^n, q'\_s, δ', F')$ with

$$\begin{align} q'\_s &= \langle q\_1, \ldots, q\_n\rangle \\ \delta'(\langle q\_{i\_1},\ldots,q\_{i\_n}\rangle, s) &= \langle \delta(q\_{i\_1}, s),\ldots,\delta(q\_{i\_n}, s)\rangle \\ \langle q\_{i\_1},\ldots,q\_{i\_n}\rangle \in F' &\text{ iff } \exists t\_1,\ldots,t\_k \text{ with } t\_1 = 1, q\_{t\_k} \in F \text{ and } t\_j = i\_{t\_{j-1}} \text{ for } j \in \\{2,\ldots,k\\} \end{align}$$ Although that's a lot of states, it's still a finite number, and the set of accepting states is well-defined and can be enumerated. So the multiple-pass machine is still a finite-state machine.

---
Tags: formal-languages, automata, finite-automata
---


title: Largest rectangle problem

text:
# Question
Title: Largest rectangle problem
Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (stated in my own words) is as follows:

> In each testcase you are given N (6 \<= N \<= 10) sticks.
>
> Each stick has length L (1 \<= L \<= 20) provided. The lengths are represented by space separated integers.
>
> Print the maximum area that can be created by forming a rectangle from these sticks.
>
> Example input:
>
> 1 // testcase count
>
> 6 // number of sticks
>
> 1 1 2 2 3 1 // lengths

I have managed to solve this problem using brute-force method (which's complexity I didn't dare estimate), stacking multiple `for` loops and lots of `if` conditional statements.

However, I believe there must be some algorithm that would be suitable for this kind of a problem - there usually is one smart solution in those algorithm puzzles.

I tried to think of a solution for the past few days and didn't come to any meaningful conclussion.

I would greatly appreciate any suggestions - I don't need no code or ready solutions, only a hint about whether there is some algorithm that could be used here to make the solution more elegant, and with better computational complexity than a simple brute force.

**EDIT**

You are supposed to form 4 edges of a rectangle. Sticks can be stacked on top of each other to form a longer stick. Eg.

* a1 = 2+2
* a2 = 3+1
* b1 = 1
* b2 = 1
* a\*b = 4

The problem is to maximise the value of a\*b.

# Answer
> 1 votes
Unfortunately this problem is NP-hard, so no computer scientist knows (or is admitting that they know! :-P) a way to solve it in time polynomial in the number of sticks. Don't feel bad about using brute-force here -- it's essentially the best you can do.

First, let's reframe the rectangle problem as a decision problem, that is, a problem to which the answer is either YES or NO:

**Rectangle:** Given a multiset $Y = (y\_1, \dots, y\_m)$ of stick lengths and an area threshold $k$, is it possible to build a rectangle from the sticks in $Y$ having area at least $k$?

## Squares are optimal solutions when they exist

Before getting into the reduction, we will need a property about what a maximal solution to the Rectangle problem looks like. Under the constraint that $a+b=c$, $ab$ is maximised precisely when $a=b$, i.e., squares have uniquely maximum area among all rectangles of fixed perimeter. You can verify this by substituting $b=c-a$ into $ab$ and then differentiating w.r.t. $a$: the derivative becomes zero at $a=c/2=b$, and this is clearly a maximum since the coefficient of the $a^2$ term is negative. The practical significance of this fact is: If and only if it is possible to partition the stick lengths into 4 equal-size subsets, then the maximum-size area achievable is $s^2/16$, where $s$ is the sum of all stick lengths.

## Reduction from Partition

I'll show this is NP-hard by reducing the NP-hard problem Partition to it. In Partition, we are given a multiset of $n$ integers $X=(x\_1, \dots, x\_n)$, and our task is to partition this multiset into two parts having equal sum.

Given an instance $X=(x\_1, \dots, x\_n)$ of Partition, with total sum $t=\sum x\_i$, we construct an instance $Y = (y\_1, \dots, y\_{n+2})$ of Rectangle by taking each $x\_i$ as a stick length $y\_i$, and adding two more "big" sticks, $y\_{n+1}$ and $y\_{n+2}$, both of length $t/2$. (That is, $m=n+2$.) Finally, we set $k$ to $t^2/4$.

If the answer to the constructed Rectangle problem instance is YES, then by the maximal-square property, it must be possible to partition $Y$ into four equal-sum parts, each having sum $t/2$. Let $(A, B, C, D)$ be such a partition. Two of these four multisets must each contain a "big" stick and nothing else, since the big sticks have to go somewhere, and combining one of them with any other sticks would mean that one side exceeds $t/2$, meaning that some other side must fall short of $t/2$, meaning that the rectangle is not square and thus of size strictly less than $t^2/4$ -- a contradiction. Remove these two big sticks, leaving two remaining multisets of sticks, which must also be of equal sum (that is, also $t/2$): these two multisets represent a valid partition of the original $X$ into two equal-sum parts, showing that the answer to the original Partition instance is also YES in this case.

In the other direction, if the answer to the original Partition problem is YES, meaning that there is a way to partition $X$ into two equal-sum parts $U$ and $V$, then clearly the answer to the constructed Rectangle problem instance is also YES: We could simply use the four multisets $U$, $V$, $\\{y\_{n+1}\\}$ and $\\{y\_{n+2}\\}$.

Since a YES to either problem instance implies a YES to the other, it must also be that a NO to either instance implies a NO to the other: in other words, the answers to both problems are always the same. And since the Rectangle problem instance can be constructed in polynomial time from the Partition instance, any algorithm that can solve Rectangle in polynomial time could also be used as a subroutine to solve Partition (any, by extension, every other NP-hard problem) in polynomial time. Since Partition is an NP-hard problem, this implies that Rectangle is too.

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


# Question
Title: Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).

I know that the class of decidable languages is closed under symmetric difference, because it is closed under union, complement and intersection. However, does this also apply to the class of partially decidable languages?

# Answer
> 3 votes
Assume partially decidable languages are closed under symmetric difference, and let $A$ be a language that is partially decidable but not decidable. Then, where $U$ is the language that includes everything,

$A \otimes U = (A - U) \cup (U - A) = \overline{A}$.

Then $\overline{A}$ must also be partially decidable, and $A$ is decidable; this is a contradiction. (This builds on an answer above, which suggested investigating complementation.)

---
Tags: complexity-theory, computability, sets, semi-decidability
---


# Question
Title: (OCR ) How to Recognise Handwritten fractional numbers using Neural networks
I want to be able to recognise handwritten math numbers using images of the numbers , i was able to do create a ANN model for recognising simple decimal numbers , but i have no idea on how to recognise fractional number. What kind of ML model do i need to recognise fractional numbers (p/q forms). As i am relatively new to machine learning, i have no idea how to do it. Any study material will be appreciated.

# Answer
Usually one of the steps is "segmentation", where we separate the image into smaller images, one for each character/symbol. Thus the fraction "1/13" would have four character, "1", "/", "1", and "3". Then, you apply a neural network separately to each of those four smaller images.

See https://en.wikipedia.org/wiki/Optical\_character\_recognition for an introduction. OCR is covered in many standard sources. I suggest reading the literature on the subject to learn more about standard methods.
> 2 votes

---
Tags: machine-learning, neural-networks, image-processing, ocr
---


# Question
Title: Asymptotic time complexity for finding maximum element in an array
Consider a simple algorithm to find the maximum element of an array containing integers. We just loop through the array, storing the maximum found so far and updating it whenever an element larger than the existing maximum is encountered.

This algorithm is often considered to have $O(N)$ complexity. But doesn't accessing the array take $O(\log N)$ time in each iteration of the for loop? After all, an array of size $N$ requires $\log N$ address bits, so accessing each element should take $\log N$ time steeps? So the total time complexity should be $O(N \log N)$, unless I'm missing something here?

# Answer
> 1 votes
The usual model of computation used to analyze algorithms is the *unit-cost RAM model*, in which machine words have width $O(\log n)$, and operations on machine words (including dereferencing) take constant time.

In this model of computation, you can find the maximum of an array of length $n$ words in linear time.

# Answer
> 0 votes
In most analyses, reading a $\log n$ length pointer (where $n$ is the pointer) is defined to be constant time ($O(1)$), therefore finding the maximum is $O(N)$.

Also, you are mixing variables here. The $N$ refers to the number of elements in the array, but when you say $\log N$, you really mean the number of bits to represent a pointer to some array element.

# Answer
> 0 votes
It all depends on the model of computation. Usually, array elements are taken to be a fixed size and stored contiguously, so you can simply move the tape head, disk platter, etc. by that constant amount in each step.

In case you need to maintain the address of the location pointed to, incrementing an $O(n)$-bit value by the same constant on $n$ different occasions takes $O(1)$ amortized time per increment in most reasonable models of computation (proof: consider the number of times various right-most bits change; can you find the geometric series?).

---
Tags: time-complexity
---


title: Find a grammar for this language

text:
# Question
Title: Find a grammar for this language
Assume the language: $$L=\left\\{w\in\\{0,1\\}^\*\\,| \text{ w has odd length and 111 right in the middle}\right\\}$$

This is my attempt for constructing a grammar $G$ for this language:

$$G: S \rightarrow A111B,\\, A \rightarrow 01B |10B|00B|11B,\\, B \rightarrow 01A |10A|00A|11A$$

This process adds random even strings of $\\{0,1\\}^\*$ to both sides of $111$.

However, it must assign $\varepsilon$ to $A$ and $B$ simultaneously, for the even strings to be of equal length and for $111$ to stay in the middle of the resulting string.

How can I achieve the last step?

# Answer
> 1 votes
If you do not want a more complicated (non-context-free) grammar, you cannot coordinate the two steps. The trick is to work the other way around: generate the two "side strings" from one central non-terminal and put the $111$ in the end.

Further problems with your grammar are:

* you miss $111$,
* since your intention is to generate 2 symbols both at the front and at the end, you would add 4 instead of 2 and thus miss every second odd number.

I propose the grammar $$\[ \\{0,1\\}, \\{S\\}, R, S\]$$ where $R$ has the rules $S\rightarrow 0S0\ |\ 1S1\ |\ 0S1\ |\ 1S0\ |\ 111$.

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


# Question
Title: Gerrymandering Problem: Variant on Set Partitioning
I was recently helping a friend with homework from a dynamic programming class, and this was the question:

> Given a set of n precincts P1 ,... Pn , each containing m votes, with `n` being even. We want to divide each precinct into two districts, each consisting of $\frac{n}{2}$ of the precincts. For each precinct, we know the number of citizens who will vote for party A and B. A set of precincts is susceptible to gerrymandering if it is possible to perform a division into two districts s.t. the same party holds a majority in both districts. For a given set of precincts, return whether they are susceptible to gerrymandering.

*Readers who have Kleinberg & Tardos' Algorithm Design, note that this is the following exercise in the book: Chapter 6, Exercise 24, "Gerrymandering".* (Also here, problem #2.)

Of course, this is a classic DP-style question, and we arrived at a DP solution, but I was intrigued by an $O(n \log n)$ sorting approach.

**Intuition and training suggests to me that this problem is NP-hard, so my $O(n \log n)$ sorting solution must be an approximation heuristic. Yet I cannot find or think of a counterexample to it.**

**My hope is that someone here can provide a counterexample of precincts such that my solution fails. And perhaps give me some intuition on the conditions for it to fail, how good of a heuristic it is, etc.**

The basic strategy of my solution is this:

1. Sort the precincts in ascending order. (Precincts are expected to be in the form of an array of integers representing the delta of votes `A - B` for each precinct.)
2. Beginning with the right-most (highest) precinct, add it to the left district, popping it from our precinct collection.
3. While the left precinct sums to a greater number than the right precinct, add precincts from the left of the array (most negative precincts). If we would fill this district and put it to a sum below zero, we do not do so, and instead elect to place that precinct into the right district.
4. While there remains precincts, pop the rightmost precinct and add it to a district, preferring: "helping" the district with the lesser sum; the district with less precincts (maximizes future decision potential).
5. Do all of this above, with the same precincts' values multiplied by `-1`. (Effectively checking to see if it's possible to gerrymander for party `A` first, then party `B`.)

The general strategy is to always keep each district barely above a sum of zero. The underlying assumption is that if it is possible to gerrymander the precincts, it must be possible to do so in a way such that the maximum winning margin between the districts is minimized. Furthermore, one would expect that most non-trivial solutions involve minimizing the winning margins, otherwise you're "wasting" votes.

---

# Here's the code:

```
from collections import deque

def left_is_greater(greater, precincts, n):
    return (
        greater
        and len(greater) < n / 2
        and (sum(greater) + precincts[0] > 0 or len(greater) < n / 2 - 1)
    )

def maximize(precincts):
    n = len(precincts)
    left, right = [], []
    while precincts:
        greater = left
        if sum(right) > sum(left):
            greater = right
        elif sum(right) == sum(left):
            greater = None

        if left_is_greater(greater, precincts, n):
            greater.append(precincts.popleft())
            continue

        p = precincts.pop()

        # if either of the districts is "full", we don't have a choice
        # and must select the opposite district
        if len(right) == n / 2:
            left.append(p)
        elif len(left) == n / 2:
            right.append(p)

        # we always prefer the lesser summed district. if gerrymandering
        # is feasible, we won't want to put all of our party's votes
        # into one district, but prefer to have each district barely win.
        elif sum(left) < sum(right):
            left.append(p)
        elif sum(right) < sum(left):
            right.append(p)

        # if the districts sum to the same amount, we prefer the district
        # with less precincts, as this maximizes future decision branches
        elif len(right) < len(left):
            right.append(p)
        elif len(left) < len(right):
            left.append(p)

        # we choose left as the default seed case, all else equal
        else:
            left.append(p)

    if sum(left) > 0 and sum(right) > 0:
        return True, left, right
    else:
        return False, left, right

def solve(precincts):
    maximized = deque(sorted(precincts))
    minimized = deque(sorted(x * -1 for x in precincts))
    for polarized_precincts in [maximized, minimized]:
        is_gerrymanderable, left, right = maximize(polarized_precincts)

        if is_gerrymanderable:
            print("It's gerrymanderable! Take a look: ", left, right)
            return

    print("Sorry, doesn't seem to be gerrymanderable.")

def main():
    test_cases = [
        [-10, -1, 0, 1, 2, 10],
        [-3, -3, -3, -1, 0, 1, 2, 9],
        [55 - 45, 43 - 57, 60 - 40, 47 - 53],
        [4, 5, 6, 7, 8, 9],
        [-1, -1, 0, 0, 1, 1],
        [-4, -1, -1, 1, 2, 6],
    ]
    for case in test_cases:
        solve(case)

if __name__ == "__main__":
    main()

```

# Answer
As your intuition and training suggests, a simple greedy algorithm should not solve this seeming hard problem.

Here is a counterexample, \[-3, -2, -2, 0, 4, 5\]. This is probably the simplest counterexample. Your algorithm will return "Sorry, doesn't seem to be gerrymanderable". However, there is a division, \[-2, -2, 5\] and \[0, -3, 4\].

How can we beat this greedy algorithm? You probably have verified all cases of 4 precincts. Let us try making the first two greedy choices of 6 precincts a bad choice. Luckily there we have found it.
> 1 votes

---
Tags: algorithms, dynamic-programming, np-hard
---


# Question
Title: Is there any better way to find the closest points' distance?
The problem is:

> Suppose you're given $n$ points in the coordinate plane, and for convenience assume that no two of their $x$ or $y$ coordinates are the same. Design an algorithm that finds the shortest possible distance between a pair of these points. What is the time complexity of your algorithm?

Ofcourse there is a easy way to find the shortest distance in $\mathcal{O}(n^2)$. But, is there any better algorithm? I am out of idea.

*Note*: I am a Math major and not familiar with CS way to solve problems very much.

# Answer
> 2 votes
This is the well-known closest pair of points problem, and you can solve it for $n$ points in $O(n \log n)$ time by divide and conquer.

A pretty cool randomized algorithm due to Rabin is also available.

---
Tags: algorithms
---


# Question
Title: reducing a decision problem to a local search problem
Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states:

> If a **PLS** problem is **NP**-hard then **NP** = **P**

So assuming *L* is a **PLS** problem (polynomial local search problem) that is **NP**-hard, then every **NP** problem can be reduced to *L*.

Usually if *$P\_1$* is reducible to *$P\_2$* (being two decision problems) then there is a polynomial time function $f$ such that:

$I\_1$ is a positive instance of *$P\_1$* $\qquad$ if and only if $\qquad$ $f(I\_1)$ is a positive instance of *$P\_2$*

However I'm not completely sure how would a reduction from a decision problem to a local search problem be.

I guess my question is: if $P$ is a decision problem which is reducible to the problem $L$, mentioned above, with the polynomial time function (or procedure) $g$ then complete the sentence:

$I$ is a positive instance of *$P$* $\qquad$ if and only if $\qquad$ $g(I)$ is ....................

# Answer
To compare search problems, polytime many-one reductions work as follows: $A$ is reducible to $B$ if there are polynomial-time computable functions $f$, $g$ such that for any $A$-instance $x$, if $y$ is a $B$-solution to $g(x)$, then $f(x,y)$ is an $A$-solution to $x$.

We can view decision problems as special cases of search problems with unique binary answers, but note that the reduction notions disagree. In particular, we cannot really see the difference between yes and no instances in the search problem view.
> 1 votes

---
Tags: complexity-theory, reductions, decision-problem, search-problem
---


# Question
Title: How can I represent the following mathematically? (Eigenfaces reconstrcution)
I got the following from a web site:

> The feature vectors represent each image as a linear combination of the eigenfaces defined by the coefficients in the feature vector; if we multiply each eigenface by its corresponding coefficient and then sum these weighted eigenfaces together, we can roughly reconstruct the input image.

The link is: https://blog.cordiner.net/2010/12/02/eigenfaces-face-recognition-matlab/

Some body please guide me.

Zulfi.

# Answer
> 1 votes
Have you followed my recommendation in my answer to another question of yours to "read *a tutorial on Principal Components Analysis* by Lindsay I Smith, which is self-contained and easy to read"? Trust me, that is the fast way for you to learn and understand PCA. I might appear arrogant or opinionated. However, I want to emphasize you should follow my suggestion. **That is probably the best help/answer you can get from asking all your recent questions.**

Let me explain the quoted sentence a little bit. (It seems you are not familiar with linear algebra.) A linear combination of some eigenfaces means the sum of each of them multiplied by its corresponding coefficient. If this sum is the original image vector, we say the original image is represented by that linear combination. In particular, if we multiply all possible eigenfaces by its corresponding coefficient and then sum these weighted eigenfaces together, we will get **exactly** the original image vector, that is, we can **exactly** reconstruct the input image.

Why was "roughly" used in that article then? It was used only because we only have "20 eigenfaces that my training set generated". However, those are the most significant eigenfaces in the sense that their corresponding eigenvalues are the biggest 20. With only 20 eigenfaces, we can still reconstruct the input image but only "roughly". Another connotation of "roughly" comes from the fact that almost all numerical computations are approximations since, for example, we cannot expressed $\sqrt 2$ or even $1/3$ exactly in standard floating binary numbers.

---
Tags: machine-learning
---


# Question
Title: How to think when devising a TM that decides if a DFA rejects some string?
The title should explain my question thoroughly enough. I can't seem to get started anywhere. Intuitively it seems like some kind of brute-forcing would work i.e if the DFA has the symbols $\Sigma$ you would simply be passing strings from $\Sigma^\*$ until the DFA rejects. What would even be the time complexity of this though? Or am I completely out and about?

# Answer
> 2 votes
The problem with your approach is that there are infinitely many strings in $\Sigma^\*$. If the automaton keeps accepting and accepting, how would you know hen to stop?

Instead, consider how an automaton can reject: it rejects by getting to a rejecting state.

---
Tags: turing-machines
---


# Question
Title: Why can we write almost any nonzero 2-adic integer in the same form?
The title was difficult to formulate (I am open to suggestions). Two things bug me about this:

1. "is almost any" is imprecise, which goes against Volume 1's statement on *definiteness*.
2. When he writes, "in other words", this means Prof. Knuth explained it to me in two ways and I still do not understand it.

What is going on here in Plain English?

---

> If $x$ is almost any nonzero 2-adic integer, we can write its bits in the form $$x = (\alpha01^a10^b)\_2 $$
>
> in other words, $x$ consists of some arbitrary (but infinite) binary string of $\alpha$, followed by a $0$, which is followed by $a+1$ ones, and followed by $b$ zeros, for some $a \geq 0$ and $b \geq 0$. (The exceptions occur when $x = -2^b$; then $a = \infty $)
>
> Consequently
>
> $$ \bar{x} = (\bar\alpha10^a01^b)\_2 $$
>
> $$ x-1 = (\alpha01^a01^b)\_2 $$
>
> $$ -x = (\bar\alpha10^a10^b)\_2 $$
>
> and we can see that $\bar{x} +1 = -x = \overline{x-1}$, ...
>
> With two operations we can therefore compute relatives of $x$ in several useful ways:
>
> * $x \mathbin{\\&} (x-1) = (\alpha01^a00^b)\_2$
> * $x\mathbin{\\&} -x = (0^\infty00^a10^b)\_2$
> * $x \mathbin{|} -x = (1^\infty11^a10^b)\_2$
> * $x \oplus -x = (1^\infty11^a00^b)\_2$
> * $x \mathbin{|} (x-1) = (\alpha 01^a11^b)\_2$
> * $x \oplus (x-1) = (0^\infty00^a11^b)\_2$
> * $\bar{x} \mathbin{\\&} (x-1) = (0^\infty00^a01^b)\_2$
> * ...
> * $((x|(x-1))+1) \mathbin{\\&} x = (\alpha 00^a00^b)\_2$

2009. Knuth, Donald. *The Art of Computer Programming*. Volume 4, Fascicle 1. p. 8.

# Answer
Addressing first the explicitly asked questions:

> Two things bug me about this: 1. "is almost any" is imprecise,

The meaning of “almost any” here is given in the next sentence, in the same paragraph: the paragraph goes as *“If $x$ is almost any nonzero 2-adic integer, \[...\]. (The exceptions occur when $x = -2^b$; \[...\].)”* So “almost any” here means “any, except for the specific exceptions stated”.

> which goes against Volume 1's statement on *definiteness*.

Aside: Although definiteness is always good and I'm sure the author agrees, note that the statement in Volume 1 is specifically in the context of the definition of an algorithm, not about writing in general. :-) Computers need everything to be spelled out for them; humans can be more robust.

> 2. When he writes, "in other words", this means Prof. Knuth explained it to me in two ways and I still do not understand it.

Yes: in the sentence *“\[...\] we can write its bits in the form $x = (\alpha01^a10^b)\_2$; in other words, $x$ consists of some \[...\]”*, the form of $x$ is described in two ways: (1) in notation, and (2) in words.

---

Longer explanation with context:

# What is a 2-adic integer?

Although some people (IMO incorrectly) describe *The Art of Computer Programming* as a reference book, in fact it is written to teach, so one cannot look up a random page or section and expect to understand it in isolation.

In this case, the “$2$-adic integers” mentioned here are first briefly described on page 2 of Fascicle 1 (page 134 when part of Volume 4A), where it is said:

> Negative integers are to be thought of in this connection as infinite-precision numbers in two’s complement notation, having infinitely many $1$s at the left; for example, $−5$ is $(\dots1111011)\_2$. Such infinite-precision numbers are a special case of *2-adic integers*, which are discussed in exercise 4.1–31, and in fact the operators $\\&$, $|$, $\oplus$ make perfect sense when they are applied to arbitrary 2-adic numbers.

This may be enough context for what is in the question here, but to understand this more completely, it would be best to look up (as mentioned) Exercise 31 of section 4.1 (**Positional Number Systems**), which is on page 213 of Volume 2. The exercise covers three-fourths of a page and is very instructive, but let me just quote part of it:

> A generalization of two’s complement arithmetic, called “2-adic numbers,” was introduced by K. Hensel \[…\] A 2-adic number may be regarded as a binary number $$u = (\dots u\_3u\_2u\_1u\_0.u\_{−1}\dots u\_{-n})\_2,$$ whose representation extends infinitely far to the left of the binary point, but only finitely many places to the right. Addition, subtraction, and multiplication of 2-adic numbers are done according to the ordinary procedures of arithmetic, which can in principle be extended indefinitely to the left. For example,
>
> Here 7 appears as the ordinary binary integer seven, while −7 is its two’s complement (extending infinitely to the left); it is easy to verify that the ordinary procedure for addition of binary numbers will give $−7+ 7 = (\dots00000)\_2 = 0$, when the procedure is continued indefinitely. The values of $\frac{1}{7}$ and $\frac{-1}{7}$ are the unique 2-adic numbers that, when formally multiplied by 7, give 1 and −1, respectively. The values of $\frac{7}{4}$ and $\frac{1}{10}$ are examples of 2-adic numbers that are not 2-adic “integers,” since they have nonzero bits to the right of the binary point. The two values of $\sqrt{-7}$, which are negatives of each other, are the only 2-adic numbers that, when formally squared, yield the value $(\dots111111111111001)\_2$.

I hope this makes clear what is a 2-adic integer. (If that was too much, just focus on the $−5 = (\dots1111011)\_2$ and $-7 = (\dots111111111111001)\_2$ and $7 = (\dots000000000000111)\_2$ examples.)

# The first sentence

Now, with this background, the quoted sentence (that the question is about) will hopefully be clearer. It occurs on page 8 in a section titled **“Working with the rightmost bits”**, so that should also help orient your attention.

If you consider any 2-adic integer $x$ other than the stated exceptions ($0$ and $-2^b$), then the sentence says that it can be written in the form $x = (\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$. What this means is that looking from the right, the bits of $x$ (you may want to look at the examples above) consist of some (possibly empty) sequence of $0$s (“$0^b$”), to the left of which there is a $1$ (so “$\color{#c00}{1}0^b$”), to the left of which there's some (possibly empty) sequence of $1$s (so “$1^a\color{#c00}{1}0^b$”), to the left of which there is a $0$ (so “$\color{blue}{0}1^a\color{#c00}{1}0^b$”), to the left of which there is some infinite string of arbitrary $0$s and $1$s that we don't care about (so “$\alpha\color{blue}{0}1^a\color{#c00}{1}0^b$”).

In other words, if you consider the sequence of bits of $x$:

* $b$ is the number of $0$s that it ends with, i.e. the sequence of $0$s after the last $\color{#c00}{1}$ in the sequence. ($b \ge 0$)
* $a$ is the number of $1$s immediately to the left of that last $\color{#c00}{1}$, i.e. between “the last $\color{blue}{0}$ before the last $\color{#c00}{1}$” and “the last $\color{#c00}{1}$”. ($a \ge 0$)
* $\alpha$ is the arbitrary sequence that comes before this, i.e. before “the last $\color{blue}{0}$ before the last $\color{#c00}{1}$”.

# Examples

* When $x = 1392 = (\dots000101\color{blue}{0}11\color{#c00}{1}0000)\_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$ with $\alpha = \dots000101$ and $a = 2$ and $b = 4$.
* When $x = −5 = (\dots1111\color{blue}{0}1\color{#c00}{1})\_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$ with $\alpha = \dots1111$ and $a = 1$ and $b = 0$.
* When $x = -7 = (\dots1111111111110\color{blue}{0}\color{#c00}{1})\_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$ with $\alpha = \dots1111111111110$ and $a = 0$ and $b = 0$.
* When $x = 7 = (\dots00000000000\color{blue}{0}11\color{#c00}{1})\_2$, then $x$ can be written as $(\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$ with $\alpha = \dots00000000000$ and $a = 2$ and $b = 0$.

## The rest

This just gives the bit patterns of various functions of $x$, like $x-1$, $-x$, $\bar{x}$ (the bitwise complement of $x$; recall definition from page 3 earlier), $x \oplus (x-1)$, etc.

All of these are straightforward; e.g. if $x = (\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$ then when you subtract $1$ from it, the final $\color{#c00}{1}0^b$ becomes $\color{#c00}{0}1^b$ and the rest remains the same, so the result is $x - 1 = (\alpha\color{blue}{0}1^a\color{#c00}{0}1^b)\_2$. (For example, think about what happens when you subtract $1$ from $1392 = (\dots000101\color{blue}{0}11\color{#c00}{1}0000)\_2$ to get $1391 = (\dots000101\color{blue}{0}11\color{#c00}{0}1111)\_2$ — and so on.)

I assume your main difficulty was in understanding the $x = (\alpha\color{blue}{0}1^a\color{#c00}{1}0^b)\_2$ notation, so you should be able to work out these functions now.
> 2 votes

# Answer
The pattern $x = (\alpha01^a10^b)\_2$ is very easy to match. For example, the number $1=0^\infty1$ matches the pattern with $\alpha=0^\infty, a=b=0$. Try matching some other numbers yourself. The only thing this pattern asks for, is for the string "$01$" to appear somewhere in the sequence of bits. The only numbers to fail this condition are $0=0^\infty$ and $-2^b=1^\infty0^b$.
> 3 votes

---
Tags: number-formats
---


# Question
Title: Closure properties between two languages from different grammars
We know that if we have two languages produced by one regular grammar, then any language produced from the union, intersection, and so on would be regular.

What if we have a regular grammar that produces language A and a different regular grammar that produces language B. Then could the closure properties still be used in order to produce another regular language C?

For example, is $A\cap B$ a regular language (intersection)? Is $A\\|B$ a regular language (concatenation)?

# Answer
> 1 votes
A grammar produces exactly one language; it makes no sense to speak of two languages produced by the same grammar.

The closure properties of regular languages apply to any regular languages.

---
Tags: regular-languages, formal-grammars
---


# Question
Title: Complexity of finding a majority element
I was given a question that is stated that;

> Suppose you’re consulting for a bank that’s concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank cards that they’ve confiscated, suspecting them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank cards corresponding to it, and we’ll say that two bank cards are equivalent if they correspond to the same account. It’s very difficult to read the account number of a bank card directly, but the bank has 1 a high-tech ‘equivalence tester’ that takes two bank cards and, after performing some computations, determines whether they are equivalent. Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another? Assume that the only feasible operations you can do with the cards are to pick two of them and plug them into the equivalence tester. Show how to decide the answer to their question with only O(nlog n) invocations of the equivalence tester.

I proposed an algo for this problem that is like this;

> For the equivalent majority there must be majority of the equivalent cards on one side of the n cards if we divide them into two halves. So one of the two sides must return one card that has majority more than n/2 in whole list.
>
> Let’s say equivalentTest is the function that takes two bank cards and, after performing some computations, determines whether they are equivalent.

```
Function checkMajority(c, M)
    i = count = 0
    While i less than length of M:
        if (M[i] is not actual c) and (equivalentTest(M[i], c) == true) then:
            count ++
        Endif
    Endwhil
    If count is greater than half the length of M then:
        Return true
    Else
        Return false
    Endif

Function divide_and_find(M)
    If M.length = 1
        Return M[0]
    Else if M.length = 2
        If equivalentTest(M[0], M[1]) == true
            Return M[0] or M[1]
    Divide M
    M1 = assign first half
    M2 = assign second half
    c = divide_and_find(M1)
    if c is returned then
        found = checkMajority(c, M)
        If found = true then
            Return c
        Else
            c = divide_and_find(M2)
            found = checkMajority(c, M)
            If found = true then
                Return c
            Else
                Return ‘not found’
            Endif
        Endif
    Endif
    Return ‘not found’

```

According to my understanding,

> The algorithm complexity is O(nlogn) because we have used divide and conquer strategy. There would be (logn) steps and each step would take O(n) time for checking the majority. So the complexity would be O(nlogn)

But at the same time, I think it will take O(n\*n).. that is big O of n square, In worst case scenario. Because then it will check n cards for n cards, to find duplicate cards.

Can any one help me out in resolving my confusion??

# Answer
Let us denote the running time of your algorithm on arrays of size $n$ by $T(n)$. Then $$ T(n) = \begin{cases} T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n), & \text{if } n \> 2, \\ O(1), & \text{if } n \leq 2. \end{cases} $$ The master theorem now shows that $T(n) = O(n\log n)$.

---

Here is an $O(n)$ algorithm:

```
find-majority-element(A):
  n = len(A)
  if n = 0:
    return "none"
  if n is odd:
    y = last element of A
    if y is a majority element:
      return y
    A' = A with last element removed
    x = find-majority-element(A')
    if x is a majority element:
      return x
    otherwise:
      return "none"
  partition A into m = n/2 pairs (a_1,b_1),...,(a_m,b_m)
  construct an array B consisting of all a_i such that a_i = b_i
  x = find-majority-element(B)
  if x is a majority element:
    return x
  otherwise:
    return "none"

```

Clearly if there is no majority element, the algorithm returns "none". Now suppose that $x$ is a majority element. We will show that the algorithm returns $x$. We will do this by proving the following claim by induction on $n=\mathrm{len}(A)$:

> If $A$ contains a majority element $x$, then `find-majority-element`($A$) returns $x$.

Suppose first that $n=2m+1$ is odd, so that $x$ appears at least $m+1$ times. If $x$ is the last element, then `find-majority-element`($A$) will return it. Otherwise, $x$ is a majority element of $A'$ as well, and so `find-majority-element`($A'$) will return $x$, causing `find-majority-element`($A$) to return it as well.

We can now assume that $n = 2m$ is even. Suppose that $B$ contains $k$ many $x$'s and $\ell$ many other elements. We can upper-bound the number of copies of $x$ in $A$ by $2k + (n-2k-2\ell)/2 = m + k - \ell$. On the other hand, the number of copies is at least $m+1$, and so $k \> \ell$. In other words, $x$ is a majority element in $B$ as well. Therefore `find-majority-element`($B$) will return $x$, causing \`find-majority-element($A$) to return it as well.

Denoting by $T(n)$ the maximum running time of the procedure on arrays of length at most $n$, we get the recurrence $$ T(n) \leq \begin{cases} O(1), & \text{if } n = 0, \\ T(n-1) + O(n), & \text{if $n$ is odd}, \\ T(n/2) + O(n), & \text{if $n$ is even}, \end{cases} $$ whose solution is $T(n) = O(n)$.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, recursion, divide-and-conquer
---


# Question
Title: Is the class NP closed under complement?
Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.

# Answer
The answer is "not known to science". It is known that P is closed under complement. So if P = NP then NP is closed under complement as well. Also, if NP is not closed under complement, then P != NP.
> 6 votes

# Answer
First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.

If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we **cannot** say whether $\sf NP = coNP$ or not. Notice that $\sf NP = coNP$ implies that the polynomial hierarchy collapses to the first level. However this would not imply that $\sf P= NP$.
> 17 votes

# Answer
It is unknown. A proof of the P vs. NP problem would give you an answer.
> -2 votes

# Answer
"Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases". Source
> -2 votes

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


# Question
Title: Binary Search Tree – Number of comparisons when element is not found
I am confused regarding Binary Search Trees (BST) when an element does not exist in the tree.

For example, to search for element "6", would it take 5 comparisons to search for this element?

My understanding is:

1. Compare root (Not found - move left)
2. Compare left node (Not found - move left)
3. Compare left node (Not found - move right)
4. Compare right node (Not found, move right)
5. No right node (6 does not exist)

Is my understanding correct? Would it take 5 comparisons to attempt to search for 6 in this BST?

# Answer
There are only 4 comparisons: the element 6 is compared to the elements 9,7,4,5.
> 0 votes

---
Tags: binary-search-trees
---


title: NP-Hard on Complete Graphs

text:
# Question
Title: NP-Hard on Complete Graphs
I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A *with a complete graph* that solves B.

Since undirected graphs generalize complete graphs, am I safe in saying that A is NP-Hard for undirected graphs? Something about that doesn't seem right to me, since problem A on complete graphs is essentially the "non-graphical" version of the problem. Am I missing something?

Disclaimer: I am new to proving hardness results.

# Answer
> 1 votes
Usually, when reducing problem B to problem A, not all possible instances of problem A appear in the image of the reduction. This is absolutely not an issue.

In your case, you can say that problem A is NP-hard even if restricted only to complete graphs. This is a stronger result, which is a good thing, and definitely allowed.

As an example, 3-coloring is hard even for 4-colorable graphs, and even just for planar graphs. You show this (say) by reduction from SAT to 3-coloring, in which all the resulting graphs are planar. This is not a drawback – in fact it's a bonus.

---
Tags: algorithms, graphs, np-complete, np-hard
---


# Question
Title: NP-Completeness reduction, using a same input
We have problem X and Y that we know is NP-Complete. Problem X uses graph G as an input and Problem Y uses graph G and constant k as an input.

Problem we are trying to reduce to, which I will call Z, is reasoning whether given a graph G and constant k, does G have X or Y.

I have been trying to solve this problem and an idea I came up with is to use an input G and k which can serve as an input for both X and Y, and reduce it to G' and k' where G=G' and k=k' for problem Z

Is it a valid thing to reduce without changing an input?

# Answer
You can do whatever you want as long as you satisfy the definitions.

For example, a polynomial time reduction from a language $A$ to a language $B$ is a function $f$ satisfying the following two properties:

1. $f$ can be computed in polynomial time.
2. For every $x$, we have $x \in A$ iff $f(x) \in B$.

*Any* function $f$ satisfying these conditions is a polynomial time reduction from $A$ to $B$.

In particular, if $A$ is NP-hard and there exists a function $f$ satisfying these two conditions, then $B$ is also NP-hard.

The definition doesn't specify anything beyond these two properties. In mathematics nothing is left unsaid; everything which is not forbidden is actually allowed. All the cards are open. The rules of the game are public, and there is no need to ask a judge about any of them.
> 1 votes

---
Tags: np-complete, reductions
---


# Question
Title: Variant of an approximation algorithm for vertex cover
Here is an approximation algorithm that finds vertex cover of a graph.

```
 C = {}
 E' = {Edge set}
 while E' =/ 0
   Let (u,v) be an arbitrarily edge of E'
    C = C U {u,v}
    remove E' incident on u and v.
return C

```

A variant: what if instead of removing edges incident on both $u$ and $v$, we removed only $u$. Would this affect the optimal vertex cover? If so, how?

I somehow feel the optimal vertex cover remains the same whereas only the number of steps to remove the edges would increase increasing time and space complexity. Am I right?

# Answer
Consider a star consisting of a center $x$ connected to the vertices $y\_1,\ldots,y\_n$. Your modified algorithm could act as follows:

1. Choose the edge $(x,y\_1)$; add $x,y\_1$ to the vertex cover; remove all edges incident to $y\_1$.
2. Choose the edge $(x,y\_2)$; add $x,y\_2$ to the vertex cover; remove all edges incident to $y\_2$.
3. ...

I'll let you take it from here.
> 0 votes

---
Tags: graphs, np-complete, np-hard, approximation
---


# Question
Title: How to avoid having to store extra information about padding (for byte size alignment) with Huffman coding
When storing the encoded Huffman bit stream in bytes, in general, either

1. the final byte gets padded or
2. a pseudo end-of-file symbol gets used

In the former case, the number of bits padded needs to be stored somewhere, requiring another 3 bits. In the latter, you will lose some efficiency due to the additional pseudo symbol.

So how can I avoid the extra cost of a pseudo symbol, and also avoiding the need to store/transmit extra bits to hold the number of pad bits?

---

N.B. On the one hand, I'm interested in compressing short strings, so saving 3 bits on average can shave off another 1% or so of the data.

But more importantly, getting rid of the need to send the padding info (which is only known after compressing the whole string) *before* the encoded data means I can more easily perform the algorithm in a streaming fashion. This is not really necessary for short strings, where everything may be kept in memory, but sometimes my strings actually do get much longer, and I don't want to have to keep that in memory (considering there are hundreds of simultaneous encodings going on).

# Answer
There's a way that neither needs to store the number of padded bits, nor - in most real life scenarios \*) - add a pseudo symbol.

The idea is this: The maximum padding is 7 bits, so if after the last encoded symbol, we pad with the first bits of a symbol that is encoded as 8 or more bits, the decoder will stop in the middle of decoding when the bit stream finishes, so no extraneous symbol gets decoded.

For this to work, the total byte length of the Huffman encoded data needs to be known when decoding.

\*) If there is no existing symbol of length 8 or longer, then an end-of-file pseudo-symbol needs to be created. This should be added with the least possible frequency, in order not to make the encoding of real symbols grow in length, if possible. The length of the end-of-file symbol does not matter. If it is shorter than 8 bits, it can just be repeated multiple times to pad the last byte, and if longer than 8 bits, only the first bits necessary to pad the final byte will be used.
> 4 votes

---
Tags: huffman-coding
---


# Question
Title: Context Free Grammer and PDA (Palindrome but without characters repeating in a row)
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"**L contains palindromes that don’t ever have the same character occur twice in a row."**

Let $\Sigma = \\{a, b, c\\}$.

Let $L = \\{w \in \Sigma^∗| w = w\_1w\_2\cdots w\_n \mbox{ is a palindrome and } w\_i \neq w\_{i+1} \forall 0 \le i\lt n\\}$.

In other words, $L$ contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea?

# Answer
> 1 votes
The language in question consists of all palindromes in which no two consecutive characters are the same. For example, $aa$ is a palindrome, but doesn't belong to the language since $a$ repeats; but $aba$ is OK.

When the alphabet consists only of $a$ and $b$, you can modify the grammar $S \to aSa|bSb|a|b|\epsilon$ of palindromes to accept your language by using two nonterminals $A,B$ which generate the following languages:

* $A$ generates all palindromes starting with $a$ in which no two consecutive characters are the same.
* $B$ generates all palindromes starting with $b$ in which no two consecutive characters are the same.

I'll let you complete the construction, and generalize it to larger alphabets.

(In the particular case of an alphabet of size 2, the language is actually regular, but this doesn't happen when the alphabet is larger.)

The simplest way to construct a PDA is to use to use the production construction: starting with a PDA for the palindrome language and a DFA for the language of strings with no repeated characters, you can construct a PDA accepting the intersection. This is a standard construction that appears in many textbooks.

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


title: Context Free Grammer and PDA

text:
# Question
Title: Context Free Grammer and PDA
So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says

"**L contains palindromes that don’t ever have the same character occur twice in a row."**

Let Σ = {a, b, c}

Let L = {w ∈ Σ∗| w = {w1, w2, . . . , wn} is a palindrome, and wi 6= wi+1 ∀ 0 ≤ i \< n}.

In other words, L contains palindromes that don’t ever have the same character occur twice in a row.

In the second part can someone guide me how to make it's PDA or give an idea.

# Answer
The grammar $S \to aSa \mid bSb \mid cSc \mid a \mid b \mid c \mid \epsilon$ would generate (normal) palindromes.

A simple way to extend this to generate palindromes with non-repeating would be to add for each letter $x$ a new non-terminal $S\_{not\text{-}x}$, and adapt the grammar:

$S \to aS\_{not\text{-}a}a \mid \dots$

$S\_{not\text{-}a} \to bS\_{not\text{-}b}b \mid \dots$

There are probably more efficient ways.
> 1 votes

---
Tags: pushdown-automata
---


title: provably optimal search algorithms?

text:
# Question
Title: provably optimal search algorithms?
In practical applications, search algorithms are often strengthened using heuristics. e.g., Deep Blue beat gary kasparov by searching through possible chess moves by "guiding" its search with human-chosen heuristics. **These heuristics are not proven to be the optimal heuristics.** (they're not optimal obviously).

I am wondering however:

> Is there *some* kind of search problem (ideally a non-trivial one), where (1) there is a specific known algorithm that solves it, and (2) a proof that the algorithm is optimal in the sense that **there does not exist an algorithm that solves it faster** **in expectation**, where (3) the probability distribution for that expectation is the relevant one for that practical search problem?

I'm interested in anything related to this. If you know something that seems partially relevant, please say so.

**EDIT**: Alternatively, please suggest a different notion of "optimality" if you think it is more relevant. I am not sure how relevant my notion of optimality is.

**EDIT 2:** I'm also interested in how this question relates to the 'No free lunch' theorems in search and optimization.

# Answer
> 2 votes
Finding an optimal solution for a problem is very difficult. for example in sorting you can prove that the optimal solution with comparison is $O(n \log n)$ but may be you can find an algorithm with $O(n)$ without comparison like hashing! another good example is NP Complete problems we even can't prove they haven't polynomial algorithm. so it is very hard to find an optimal solution for deep blue and similar algorithms and proving that the algorithm is optimal is very hard too.

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


# Question
Title: Is this an abuse big O notation as a power of a number?
Theorem 7.11 in Introduction to the theory of computation 3rth edition says

> Let $t(n)$ be a function where $t(n)\>n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(t(n))}$ time deterministic single tape Turing machine.

I can understand that in this proof when we have a nondeterministic TM which every node in it can at most go to $b$ other nodes in its computation tree, then the time complexity of a deterministic Turing machine simulating it would be $O(t(n)b^{t(n)})$. But I'm not sure if I understand the $2^{O(t(n))}$ correctly.

Does it means that if $f(n) \in 2^{O(t(n))}$ then $\exists b\in \mathbb{N} \\; f(n)\in O(b^{t(n)})?$

On the other hand, the claim 1.5 in the Computational complexity book says

> For every $f : \\{0, 1\\}^∗ \rightarrow \\{0, 1\\}$ and time-constructible $T : N\rightarrow N$, if $f$ is computable in time $T(n)$ by a TM $M$ using alphabet $\Gamma$, then it is computable in time $4 log |\Gamma|T(n)$ by a TM $M$ using the alphabet $\\{0,1,\square,\rhd\\}$.

So every nondeterministic TM M running in $t(n)$ time can have an equivalent nondeterministic TM using $\\{0,1\\}$ alphabet running upper hand in $|\Gamma|^2t(n)$. Thus this equivalent TM's computation tree has at most 2 different branches in each step. Then we can have a deterministic simulator of that TM running in time $O(2^{|\Gamma|^2t(n)})$.

The intersection of 2 above statement suggests that carelessly we can say $O(2^{t(n)})=2^{O(t(n))}$, but we know $\forall b\>2,\\; b^{t(n)}\notin O(2^{t(n)})$.

Unfortunately, I didn't find any definition of $2^{O(t(n)}$. I wish to know is there any formal definition for $2^{O(t(n))}$?

\- Edit: There is a similar question here. But I'm doubting its answer is the same since the big O notation in the power is not just $O(1)$.

Suppose we have nondeterministic TM that each node of it goes to 3 other nodes. Then there is a deterministic Turing machine that simulates it in time $t(n)3^{t(n)}$. So we can't say that there is a constant $k$ that $t(n)3^{t(n)} \< 2^{kt(n)}.$

Meanwhile, when I think more, this definition holds if we ignore the Sipser proof. I mean if we begin the proof by the statement that every nondeterministic TM has a version $\\{0,1\\}$ alphabet running in $c.t(n)$ then the answer's definition is correct.

I wonder if there is bad use of big O notation in the Sipser's book or $2^{O(t(n))}$ has a different definition.

# Answer
This is perfectly standard use of big O notation, despite some purists disliking it. Here is what the passage you quoted means:

> Let $t(n)$ be a function where $t(n) \> n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) = O(t(n))$.

This is still somewhat ambiguous, since it’s perhaps not clear what variables the big O depends on. In this case, big O hides a *universal* constant:

> There exists a constant $C\>0$ such that the following holds.
>
> Let $t(n)$ be a function where $t(n) \> n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{f(n)}$ time deterministic single tape Turing machine, for some function $f(n)$ satisfying $f(n) \leq Ct(n)$ for all $n$.

This allows us to rephrase the statement in yet another way:

> There exists a constant $C\>0$ such that the following holds.
>
> Let $t(n)$ be a function where $t(n) \> n$. Then every $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{Ct(n)}$ time deterministic single tape Turing machine.

(This assumes that by “$f(n)$ time machine” we mean a machine running in time *at most* $f(n)$.)
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Do white box methods for feature extraction exist for facial recognition?
Part of something I'm working on (or rather begin working on) involves white box approaches to facial recognition. I previously worked on something for character recognition using scene segmentation and neural networks but for faces I'm trying to challenge myself by not using neural networks or other AI strategies.

Consider a potential algorithm that takes a headshot photo as an input and the outputs are some metrics about said face. Like the eye color, skin color, hair color, philtrum width and height, distance between eyes, etc. What techniques exist that I should look into on how to implement this?

My concern is mostly with feature extraction from points of interest from a face. I think my difficulty is algorithmically describing the composition of a face to pull metrics.

# Answer
> 1 votes
For every feature $F$ you want to extract you need an algorithm extracts $F$.

the color histogram is good for color. For example if you need to extract eye color you need find eye in face (you can use open cv and see documentation) that is a 3 2D-matrixes for pixels(Red and Green and Blue filters) and if you find the histogram of these 3 matrixes you can use this histogram as eye color feature.

If you find face (with open cv) and extract the histogram, this feature isn't bad for skin color.

I think the heights and distances are not good features.

For finding face's shape HOG feature is good and also HOGColor

---
Tags: reference-request, computer-vision, facial-recognition
---


# Question
Title: General structure of solutions to 3-SAT circuits
Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any three solutions to an XOR-SAT circuit, their bitwise XOR is also a solution. Lastly, given any two solutions to a HORN-SAT circuit, their bitwise AND is also a solution.

Does there exist a similar situation for 3-SAT, where given some subset of solutions, one can somehow generate additional solutions?

If not, does there exist a related SAT problem that 3-SAT can be reduced to, and hence which is also NP-complete, which have solutions of the form specified? For instance 1-in-3 SAT, or exactly-3-SAT, or NAE-3-SAT, or etc.

# Answer
The theory you are after is *universal algebra*. See the excellent expository article of Hubie Chen, A rendezvous of logic, complexity, and algebra, which contains a streamlined proof of Schaefer’s dichotomy theorem, which was recently extended to arbitrary alphabets.

3SAT has no polymorphisms. NAE-3SAT has only negation as a polymorphism. All other classes of polymorphisms correspond to CSPs solvable in polynomial time. See Allender et al., The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem.
> 4 votes

---
Tags: satisfiability, 3-sat, constraint-satisfaction, 2-sat
---


title: 2SAT Problem using Implication Graph

text:
# Question
Title: 2SAT Problem using Implication Graph
I was doing a practice question. As you can see below there is an Implication graph. To check whether the problem is satisfiable, I checked whether there were any 'bad loops'. To do so, for each literal/variable in the boolean formula, I see if there is a path from X ---\>-X and from -X----\>X if both exist then a 'bad loop' exists and thus the problem is not satisfiable. I did that and saw that there were no such loops and thus I came to the conclusion that the 2SAT problem was satisfiable. See below:

**I realized that option d (The 2SAT problem is satisfiable if a,b,c and d are set to false.** I'm struggling to come to this conclusion by looking at the graph. My understanding is that you take all the paths in the graph, and see if you come to a contradiction? **Can someone please let me understand how to understand option d being correct.**

Thanks in advance!

**The method I have come up with is to write out the arcs/edges for each implication and work backwards to derive the 2SAT boolean formula and see if it works. Does anyone know a quicker way? :)**

# Answer
For any variable $X$, if there is a path from $X$ to $\neg X$ then you cannot set $X$ to $True$, since otherwise you would end up with a $True \Rightarrow False$ implication somewhere along the path. For the same reason, if there is a path from $\neg X$ to $X$ you cannot set $X$ to $False$.

Hence, in the first case you must set $X$ to $False$, in the second you must set it to $True$. If there are paths in both directions, as you already know, the formula is not satisfiable.

In your example, there are only paths from $X$ to $\neg X$ for all variables, hence the only assignment that satisfies the instance is the one where all variables are $False$.
> 0 votes

---
Tags: complexity-theory, np, satisfiability, 3-sat, 2-sat
---


# Question
Title: challenge: Closing hash, linear probing, probe length 1
The challenge says that there is a hash algorithm with a bug, the bug is given if it reaches the end of the array and did not find space to save the element, it discards it directly (that is, it does not try to place it in positions 0, 1, 2 ... as it would be correct)

In a hash table using closed hash, linear probing, probe length 1.

**What is the probability that with this test we discover that the implementation n has a bug, if N = 27 and K = 42?**

Example K=2, N=2: The only case is if both hashes are 1. In this case, the first element in array \[ 1 \] is first saved. Then, the next element does not have space in array \[ 1 \] and since it is the last position of the array, will discard it

I made a script to bruteforce all combinations and find the probability for the firsts N / K

The pseudocode is:

```
function bruteforce(array):
  hashtable=
        {0="" , 1="" , ..., ..., k-1=""}
  for element in array:
      canStoreThisCombination=False
      for j in range (element,len(hashtable)):
          if (empty(hashtable[j])):
              hashtable[j]="used"
              canStoreThisCombination=True
              break
  if not canStoreThisCombination:
      tot=tot+1

for each combination of N elements:
  bruteforce(actualCombination)

print tot/(k^n)

```

and got the following results:

table

Combinations for K=3

Combinations for K=4

Combinations for K=5

I'm looking for probability as an irreducible fraction

# Answer
This problem was formulated and solved in 1962 by Donald Knuth; apparently, it was his first exercise in algorithmic analysis. It's often referred to as the "parking problem".

Knuth's analysis is beautifully simple. (Note: Knuth, and I think most computer scientists, used $n$ as the size of the hash table, and $k$ as the number of items inserted. So do I, even though the question is expressed differently.)

Let's start with the set $A$ of hash values of $k$ items, consisting of all sequences $\langle a\_1, \ldots, a\_k \rangle$, where $0 \le a\_i \< n$. Clearly there are $n^k$ possible sequences.

Now, suppose we have a bug-free hash table of size $n+1$, and look the set $B$ of all possible hash sequences for $k$ items, $\langle b\_1, \ldots, b\_k \rangle$ with $0 \le b\_i \< n+1$. There are $(n+1)^k$ such sequences.

Of those sequences, we select the subset $B'$ for which the last table entry ($n$) is empty at the end of the insertion. Since once a slot is occupied, it remains occupied at the end, we know that for every sequence in $B'$, every $b\_i \< n$. Therefore, every sequence in $B'$ is also in $A$.

Moreover, we know that in the course of the insertion, no probe passes through position $n$. In other words, every sequence in this subset of $B$ is a sequence in $A$ in which there is no wrap-around, which are precisely the sequences in $A$ which do not trigger the bug.

So it will only remains to count these sequences. But that's trivial, because all of the slots in the (bug-free) hash table are identical. So the probability that a particular slot will be unoccupied after inserting $k$ items is $1 - {k \over {n+1}}$, with the result that there are $(n+1-k)(n+1)^{k-1}$ such sequences.

Thus, the probability that a random sequence of $k$ insertions into the buggy hash table will trigger the bug is $1 - {(n+1-k)(n+1)^{k-1}\over n^k}$.

By the way, the output of the program you paste-binned is not correct. For example, it lists $4, 4, 4$ twice in the list for three insertions into a table of size 5.
> 2 votes

# Answer
You are basically trying to map $\\{0,N-1\\} \rightarrow \\{0,K-1\\} \space , \space N\le K$ with no collisions. You are calling collisions a bug. So basically you want to calculate the probability of finding atleast 1 collision.

Total number of ways to map with no collisions
= (No of ways to arrange N numbers in K places leaving other unoccupied places as 0) * (No of ways to permute the N values in those arranged places)
$$ = ^KP\_N * N! = \frac{K!\*N!}{(K-N)!}$$ Total number of ways to map with 1 collision (Two keys to one value) $$ = \frac{K!\*N!}{(K-N)!} * \frac{1}{2!}$$ Total number of ways to map with 2 collision (Three keys to one value) $$ = \frac{K!\*N!}{(K-N)!} * \frac{1}{3!}$$ and so on gives us the total number of ways to map with or without collisions $$ = \frac{K!\*N!}{(K-N)!} * (1 + \frac{1}{2!} + \frac{1}{3!} ... + \frac{1}{(N-1)!}$$ $$ \approx \frac{K!\*N!}{(K-N)!} * e $$ for large enough N. Hence the probability of getting a collision/finding your bug $$ = 1 - \frac{1}{e}$$
> 0 votes

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


# Question
Title: Matrix of a graph and computational complexity
Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A\_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ otherwise. Now, suppose we define a special kind of matrix product for matrices whose entries are only 0 or 1. In this special matrix product we replace addition by OR and multiplication by AND. With this being our definition of the matrix product answer the following questions:

1. If $B\_2 = (A+I)^2$ then argue that $B\_2 = C\_2 +I$ where $C\_2$ is the adjacency matrix of the graph $G′ = (V,E′)$ with the same vertex set as $G$. We say that $(i,j) ∈ E′$ if $(i,j) ∈ E$ or there exists a $k ∈ V$ such that $(i,k),(k,j) ∈ E$.
2. Is it possible to compute $C\_2$ (by some other way perhaps) in time which is $o(n^2)$? Or is there some example on which the time taken to compute $C\_2$ has to be $Ω(n^2)$? Cause I think that in this case the time taken would be $θ(n^2)$

I tried manipulating $B\_2$ and then applying the new matrix product properties, but I wasn't able to give a concrete argument about $C\_2$. As far as the complexity goes, I have no idea on how to go about with it. Any help is appreciated. Thanks!

# Answer
> 1 votes
Let $B\_1 = I + A$. Then $B\_1(i,j) = 1$ iff $d(i,j) \leq 1$, where $d(i,j)$ is the distance between $i$ and $j$ in the graph. Now $B\_2 = B\_1^2$, and so by definition, $$ (B\_2)\_{ij} = \bigvee\_k (B\_1)\_{ik} \land (B\_1)\_{kj}. $$ In words, $(B\_2)\_{ij} = 1$ iff there exists a vertex $k$ such that $(B\_1)\_{ik} = (B\_1)\_{kj} = 1$, i.e. $d(i,k) \leq 1$ and $d(k,j) \leq 1$.

We can now prove that $(B\_2)\_{ij} = 1$ iff $d(i,j) \leq 2$. Indeed, if $(B\_2)\_{ij} = 1$ then there exists $k$ such that $d(i,k),d(k,j) \leq 1$, and so $d(i,j) \leq d(i,k) + d(k,j) \leq 2$. Conversely, suppose that $d(i,j) \leq 2$. We consider two cases. If $d(i,j) \leq 1$ then $k := j$ satisfies $d(i,k) \leq 1$ and $d(k,j) = 0 \leq 1$, and so $(B\_2)\_{ij} = 1$. If $d(i,j) = 2$, choose a shortest path from $i$ to $j$, and let $k$ be the vertex in the middle. Then $d(i,k) = d(k,j) = 1$. In both cases, $(B\_2)\_{ij} = 1$.

You cannot compute $C\_2$ faster than $n^2$, simply because it contains $n^2$ many entries. The asymptotically fastest way known to compute $C\_2$ is by squaring $I + A$ (using the usual matrix multiplication), zeroing the diagonal, and replacing each entry larger than 1 with 1. This takes time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.

---
Tags: graphs, data-structures, time-complexity
---


# Question
Title: How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time
To go with $O(n)$, we can use the **linear sieve** according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want to get $\sum\_{i=1}^n \mu^2(i)$.

I am interested that is there any solutions that are faster than $O(n)$ to work $\sum\_{i=1}^n \mu^2(i)$ out.

# Answer
$\mu^2(i)$ is 1 if $i$ is square-free, or 0 otherwise. Therefore, your question is equivalent to asking how to count the number of square-free numbers in the range $1..n$. That has been studied before; see, e.g.,

Counting Square-Free Numbers, Jakub Pawlewicz, arxiv 1107.4890.

That paper claims it can be computed in $\tilde{O}(n^{0.4})$ time (ignoring polylogarithmic factors).
> 2 votes

---
Tags: time-complexity, discrete-mathematics, number-theory
---


# Question
Title: Why does the cut $(V_C,V-V_C)$ respect $A$?
> ***Corollary 23.2***
>
> Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, and let $C = (V\_C,E\_C)$ be a connected component (tree) in the forest $G\_A = (V,A)$. If $(u,v)$ is a light edge connecting $C$ to some other component in $G\_A$, then $(u,v)$ is safe for $A$.
>
> ***Proof*** The cut $(V\_C,V-V\_C)$ respects $A$, and $(u,v)$ is a light edge for this cut. Therefore, $(u,v)$ is safe for $A$. $\quad\blacksquare$

I did understand the original proof for the Cut property in CLRS (Theorem 23.1). But I am unable to grasp how does the above corollary follow from the original proof? Why does the cut $(V\_C,V-V\_C)$ respect $A$?

# Answer
> 1 votes
The cut $(V\_C,V-V\_C)$ respects $A$ since $C$ is a connected component in $(V,A)$.

---
Tags: minimum-spanning-tree
---