# Question
Title: Count number of automata with 3 states and alphabet of size 2
How many different finite automata are there that have 3 states $q\_0$, $q\_1$ and $q\_3$, have an alphabet of size 2, and where $q\_0$ is starting state?

# Answer
Total number of distinct transition functions from $Q \times \Sigma \rightarrow Q$ is $3^6 = 729$. This is because $Q \times \Sigma $ has $|Q| \times |\Sigma| = 3 \times 2 = 6$ elements, and $|Q| = 3$. Every one of $6$ elements has $3$ choice for transition.

Even if there are 3 different choice of start state, that will not give us different automata, as these automata are already counted in 729 different automata with renumbering of states. So let us assume $q\_0$ is the start state. Now $q\_0$ is always reachable. We will remove those automata where some of the states are reachable (because we can compute these numbers easily, that is why, otherwise if we are not interested in that, we can straight away have $3^6 \times 2^3 = 5832$ distinct automata).

Number of distinct transition functions where 2 states are unreachable = $1^2.3^4 = 81$

Number of distinct transition functions where $q\_1$ state is unreachable = $2^4.3^2 = 144$

Number of distinct transition functions where $q\_2$ state is unreachable = $2^4.3^2 = 144$

Number of distinct transition functions where every state is reachable = $729 - 2\times144 + 81 = 522$.

Now let us count different final states.

3 final states = $522$ different automata (though language is same, however we are counting different automata, language being same is irrelevant).

1 final state = $522$ ($q\_0$ final) + 522 ($q\_1$ final) = $1044$ ($q\_2$ final state is counted in $q\_1$ final state, as it will just be renaming of state $q\_1$).

2 final states = $522$ ($q\_0$ and $q\_1$ final states) + $522$ ($q\_1$ and $q\_2$ final states) = $1044$ (again we won't count $q\_0$ and $q\_2$ as final states).

0 final states = $522$ (perfectly valid different automate, and again languages are all same).

So total number of distinct automata is $522 + 1044 + 1044 + 522 = 3132$.

As an added note, the case of all possible two state automata is also interesting, with any alphabet size. The interesting two cases of FA will be as following:

In the automata above, $S$ is the set of all "Set" transition symbols, $R$ is the set of all "Reset" transition symbols, $T$ is the set of all "Toggle" transition symbols, and $U$ is the set of all "Unchanged" transition symbols. We set two automata depending on whether we want set condition or reset condition to be the final state. The corresponding regular expressions are

$(R+U)^\*(S+T)((S+U)+(R+T)(R+U)^\*(S+T))^\*$ for first automata, and,
$((R+U)+(S+T)(S+U)^\*(R+T))^\*$ for second automata.

It is difficult to do such neat analysis for 3-state automata mainly because there will be 3^3=27 different classes of transition symbols.
> 3 votes

---
Tags: automata, combinatorics, counting
---


title: Properties of self-dual code

text:
# Question
Title: Properties of self-dual code
Let $C $ be a self-dual binary $\[n,k,d\]$ code.

I want to show that if $ c=(c\_1, \dots, c\_n) \in C $ then $ \sum\_{i=1}^n c\_i=0$ and that all the words of the code have an even weight.

We know that $ x \in C^{\perp} \Leftrightarrow Gx=0$ where $ G $ is the generator matrix.

Since $ C=C^{\perp}$ we have that $ G=H $ where $ H$ is the parity matrix of the code.

So we have that $ c=(c\_1, \dots, c\_n) \in C \Rightarrow c \in C^{\perp} \Rightarrow Gx=0 \Rightarrow Hx=0 $

Do we get from that, that $ \sum\_{i=1}^n c\_i=0$?

If so how?

# Answer
> 1 votes
By definition, the dual code $C^\perp$ consists of all words $x$ such that $\langle x,y \rangle = 0$ for all $y \in C$. If $C = C^\perp$ then in particular $\langle x,x \rangle = 0$ for all $x \in C$, which implies that $x$ has even weight.

---
Tags: coding-theory
---


# Question
Title: Need to remove indirect left recursion from CFG
I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$

In the following solution, I have expanded all the non-terminals to get them converted to direct recursion, instead of indirect recursion (if applicable), so that I may apply Rule for removal of direct left recursion:

$$A → Ba → Cda → Dfda → Aafda$$ $$C → Df → Cgf$$ $$D → Df$$ $$D → Cg → Dfg$$ $$D → Aa → Dfdaa$$ So, it becomes: $$A → Aafda| b$$ $$B → Cd | e$$ $$C → Cgf | g$$ $$D → Df | Dfg | Dfdaa | ba | gg$$ So, it becomes (after removal of direct left recursions): $$A → bA'$$ $$A' → afdaA'| eps$$ $$B → Cd | e$$ $$C → gC'$$ $$C' → gfC' | eps$$ $$D → baD' | gg D'$$ $$D'→ fD' | fgD' | fdaaD' | eps$$

My specific Question is: Do I have to follow this way (convert all production rules emanating from all non-terminals or should I do that for only one, e.g. D?

# Answer
> 3 votes
You should focus on trying to only modify productions that aren't "good". A production is "good" if it :

1. Starts with a terminal,
2. Is an epsilon production, or
3. Is in the form `A->B` (followed by a series of terminals and non-terminals) and we can partially order the non-terminals so that `A<B`. We'd also have to do some extra checks if `B` being nullable. That is, if `B` is nullable, we'd have to consider all productions in which `B` occurs and is nulled. For example, suppose we have the grammar:

```
A -> BAa
B -> b | esp

```

At first glance, the rule `A->BAa` might appear good (because we can assert that `A<B`), but if `B` is nulled, we end up with the production `A->Aa` which is bad. This is usually not a big problem, but you've got to make sure you cover all your cases. Note that this doesn't apply to your example, but I'd figure I'd be thorough.

For your grammar:

* `A->Ba` is good since we can assert that `A<B`.
* `b` is good because this is a terminal.
* For similar reasons, all the productions of `B` and `C` are also "good", so we shouldn't change them.
* For `D`, there are several problems. Obviously, we cannot assert that `D<D`, and we also can't assert that `D<A` or `D<C` (since we assumed that `A<B<C<D` in our previous step). However, the productions for `A`, `B`, and `C` are all "good", so we can substitute those in and expose the hidden left recursion (as you've done in your work).

In short, you should only worry about modifying "bad" productions and leaving any "good" ones as they are. It's not always possible to do this, but in general, it'll save you work.

---
Tags: formal-languages, formal-grammars, parsers, left-recursion
---


# Question
Title: Can this CFG be written into an equivalent LL(1) grammar?
I have the following CFG which I suspect cannot be rewritten to one which is LL(1):

$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$

I've thought about it for a while, and can't seem to make any progress. I know that the simpler grammar here can be rewritten into LL(1), but it seems like there is something different about the above grammar which prevents a rewriting in a similar style. Is it possible? If not, is there an easy way to prove that this is the case?

# Answer
The comment above is correct. What is referenced here is generally called a "first-follow set clash" and occurs when a non-terminal is nullable, and has non disjoint first and follow sets. You can try to remove these by substituing for the nullable non terminal (shown for your grammar below). However, this process might result in a loop. If that happens, your grammar can't be transformed to LL(1).

Note that . simply denotes esp.

```
S → a S b S
|   c S2 S
|   d S1 S
|   .
S1 →    a S b S1
|   c S2 S1
|   d S1 S1
|   c .
S2 →    a S b S2
|   c S2 S2
|   d S1 S2
|   d .

S2 =    S d. (uh-oh, we've gone in a loop here)
S1 =    S c.

```
> 1 votes

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


title: About the notation of XOR-SAT

text:
# Question
Title: About the notation of XOR-SAT
I am a bit confused by the notation here, http://www.boazbarak.org/sos/files/lec3.pdf

* Given 3 Boolean variables $x\_i, x\_j, x\_k$ what is supposed to be the meaning of $x\_i \oplus x\_j \oplus x\_k$?

Is this to be understood as say $((x\_i \oplus x\_j )\oplus x\_k )$? And hence this is true for only $2$ cases $x\_i =0, x\_j = 1, x\_k =0$ and $x\_i = 1, x\_j = 0, x\_k = 0$ ?

But then we could have bracketed it as $(x\_i \oplus (x\_j \oplus x\_k))$ and then the only true assignments would have looked as $x\_i = 0, x\_j =1, x\_k = 0$ and $x\_i = 0, x\_j =0, x\_k = 1$ and these are different.

Also one could have used commutativity to write it in other re-arranged forms and gotten different true selections!
* But then the note above seems to claim that if the $x\_a$s are coming as coordinates of a vector $x \in \\{\pm 1\\}^n$ then the product $x\_ix\_j x\_k$ is the same as having a linear equation in those $3$ variables. Why so? (for example an assignment $x\_i = x\_j = x\_k =1$ will evaluate to $1$ for the product but under mod 2 arithmetic $x\_i + x\_j + x\_k = 0$ for this assignment!)

Also it is being claimed that the value of $x\_ix\_jx\_k$ can only be $\pm 1$ (which they denote as $a\_{ijk}$) for $x \in \\{\pm 1\\}^n$ and that is okay only if one ignores the first claim that these are supposed to be linear equations!

---

This $x\_ix\_j x\_k$ product notation looks more confusing later on when they say that corresponding to two subsets $S, T \subset \\{1,..,n\\}$ one can take two expressions of the form $x\_S = \prod\_{i \in S} x\_i$ and $x\_T = \prod\_{i \in T} x\_i$ and construct $x\_U = x\_S x\_T$ and that this somehow corresponds to doing \`\`$U = S \oplus T$" - and I don't know what it means to take a XOR of two subsets!

# Answer
> 5 votes
XOR is an associative operation, so $x\_i \oplus x\_j \oplus x\_k$ is unambiguous. There are in fact four satisfying assignments, given by $$ (x\_i,x\_j,x\_k) \in \\{(0,0,1),(0,1,0),(1,0,0),(1,1,1)\\}. $$

XOR satisfies the useful property $$ (-1)^{x \oplus y} = (-1)^x (-1)^y. $$ Therefore $x\_i \oplus x\_j \oplus x\_k = 1$ is the same as $$ (-1)^{x\_i} (-1)^{x\_j} (-1)^{x\_k} = (-1)^1.$$ If we think of our variables as $X\_i = (-1)^{x\_i}$, then the equation $x\_i \oplus x\_j \oplus x\_k = 1$ is completely equivalent to $X\_i X\_j X\_k = -1$. Since XOR is really just addition in the group $\mathbb{Z}\_2$, you can think of both formulations as linear equations.

---

Yet another interpretation of XOR is in terms of sets. Just as AND corresponds to intersection and OR to union, the XOR operation corresponds to *symmetric difference*, sometimes denoted $\triangle$ or $\Delta$. You can easily check that $x\_S x\_T = x\_{S \triangle T}$, essentially using $x\_i^2 = 1$.

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


title: Wang tile turing machine tile placement

text:
# Question
Title: Wang tile turing machine tile placement
I've read numerous links on the fact that wang tiles are turing complete, and details about them (links at end).

However there is little talk of how to actually place the tiles. One place i read mentioned (paraphrasing) "by placing tiles only where they are uniquely able to fit, you'll evaluate the program", but I'm finding there is actually ambiguity in what tiles can fit where.

Another link mentions that they personally place tiles in a spiral pattern, and when they hit a spot that needs a tile which doesn't exist (isn't valid) they backtrack and make a different choice earlier on.

Does anyone know if there's any reliable algorithm for placing the wang tiles when simulating turing machines with wang tiles?

I first believed that i could just go tile by tile, systematically matching empty spots to tiles that would fit there, but there are times when it is ambiguous which tile should go there.

Please let me know if more information is needed, such as a specific case when it's ambiguous, and I will provide it. Thanks!

Links I've read include: http://www.math.oregonstate.edu/~math\_reu/proceedings/REU\_Proceedings/Proceedings1989/2\_Michie89.pdf

https://moyix.wordpress.com/2012/04/06/computing-with-tiles/

How to convert a Turing Machine program to a tiling using Wang Tiles?

http://grahamshawcross.com/2012/10/12/wang-tiles-and-turing-machines/

https://because0fbeauty.wordpress.com/2014/02/28/wang-tiles-1/

# Answer
> 2 votes
Any proof that the Wang tiling problem is undecidable by reduction from undecidability of the halting problem of Turing machines will contain instructions on how the Wang tiles simulate the operation of the machine, and indeed a proof that a tiling exists if and only if the machine doesn't halt.

There is more than one such proof. If you look at different proofs, you will see different reductions. There is absolutely no reason to expect that different reductions correspond to the same tiling placements. Indeed, there is no canonical way of converting Turing machines to tiling problems. Therefore there is no "reliable algorithm" for the problem; any specific proof should include such an algorithm that works for the specific proof.

I suggest you try to look up a technical paper with such a proof. Perhaps you can find a university library with Berger's original paper, or one of the later papers cited in the Wikipedia article.

---
Tags: computability, turing-machines, tiling
---


title: Array covering problem

text:
# Question
Title: Array covering problem
Suppose that we have $N$ integer points on coordinate line: $X = \\{x\_1, ..., x\_N\\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \\{ y\_1, ..., y\_M \\}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max\_{i=1,...,N} ~~ \min\_{k=1,...,M} ~ |x\_i - y\_k|$$

I would like to make $d(X,Y)$ minimum possible. Which algorithm should i use for choosing points $y\_1, ..., y\_M$ ?

Thanks in advance.

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

# Answer
Your problem is known as the unweighted one-dimensional $k$-center problem. See for example a recent paper by Chen, Li and Wang.
> 1 votes

---
Tags: optimization
---


# Question
Title: Running Build-Heap Algorithm on given numbers
I don't fully understand this build-heap function. Lets assume we have array 3, 4, 5, 13, 16, 32.

It seems like we swap the parent when it is less than the current A\[j\] but which number does the loop start with? Maybe somebody can go through 2-3 loops and show how the array changes after 1st loop, 2nd loop, 3rd loop. Much appreciated. Oh, also, what would be the runtime?

```
for i=2 to n
    j = i
    while (j>1) and A[parent(j)]<A[j] do
        swap A(parent(j)] and A[j]
        j = parent(j)

```

# Answer
> 1 votes
It appears you're building a max-heap, where every element is greater than or equal to its child elements (if any). With that understanding, let's trace the action. First, the parent node of $A\[j\]$ will be $A\[j/2\]$ (integer division: discard any remainder) so we'll have $$\begin{array}{r|cccccccc} j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \dotsc\\ parent(j) & \\\_ & 1 & 1 & 2 & 2 & 3 & 3 & \dotsc \end{array}$$ To keep things simple, we'll let the initial array be $\[3,4,5,13\]$:

**Insert at $i=2$**.

$A\[parent(2)\]=A\[1\]=3 \< 4=A\[2\]$ so we swap $A\[1\]$ and $A\[2\]$, giving us the array $$ \[4,3,5,13\] $$

**Insert at $i=3$**.

$A\[parent(3)\]=A\[1\]=4 \< 5=A\[3\]$ so we swap $A\[1\]$ and $A\[3\]$, giving us the array $$ \[5,3,4,13\] $$

**Insert at $i=4$**.

$A\[parent(4)\]=A\[2\]=3 \< 13=A\[4\]$ so we swap $A\[2\]$ and $A\[3\]$, giving us the array $$ \[5,13,4,3\] $$ and now $j=parent(4)=2\>1$ so we see if we need another swap.

$A\[parent(2)\]=A\[1\]=5 \< 13=A\[2\]$ so we swap $A\[1\]$ and $A\[2\]$, giving us the array $$ \[13,5,4,3\] $$ and we're done, the array is now a max-heap.

---

The runtime of this algorithm is no worse than a multiple of $n\log n$ since none of the elements are further than $\log\_2n$ from the root at $i=1$ so you'll need at most $\log n$ swaps for each of the $n$ elements. This, by the way, is not as good as possible: there's different algorithm that builds a heap in no more than a multiple of $n$ time.

---
Tags: algorithms, arrays, heaps
---


# Question
Title: Feedback polynomial of 7-bit Linear Feedback Shift Register
My friend gave me a question to solve. The question he asked me was: the following sequence has been generated by a 7-bit linear feedback shift register. He asked me to find the feedback polynomial. I went through some lectures on LFSR on youtube. But still I am unable to solve this. Can anyone point out how to approach or crack this kind of question?

> 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1

# Answer
The feedback polynomial is $x^7 + x^6 + x^5 + x^1 + 1$ and can be computed using the Berlekamp-Massey algorithm.
> 7 votes

# Answer
There is a comprehensive and excellent answer in this earlier “Cryptanalysis of Linear Feedback Shift Registers” question. Alternatively, if you know the order of the recurrence is $n$, you can solve a linear system of the form $$ \left( \begin{array}{lllll} z\_i & z\_{i+1} & \cdots & z\_{i+n-1} \\ z\_{i+1} & z\_{i+2} & \cdots & z\_{i+n} \\ & & \vdots & & \\ z\_{i+n} & z\_{i+n+1} & \cdots & z\_{i+2n-1} \\ \end{array} \right) \left( \begin{array}{c} c\_n \\ c\_{n-1}\\ \vdots\\ c\_2\\ c\_1 \end{array} \right) = \left( \begin{array}{c} z\_{i+n}\\ z\_{i+n+1}\\ \vdots\\ z\_{i+2n}\\ \end{array} \right) $$ where $(z\_t)\_{t \geq 1}$ are the sequence bits, and $i\geq 1$. Here $c\_i$ are the recurrence coefficients, to be determined. This should be done over $GF(2)$ i.e., with mod 2 arithmetic.

If the recurrence is order $n$ then $c\_n=1.$ If the recurrence is of lower order the system becomes singular and you need to work with a smaller square left upper submatrix.

The polynomial you want is $1+c\_1 x+\ldots+c\_n x^n.$

Note that the matrix method is of higher complexity than the recursive Berlekamp Massey algorithm in the linked question.
> 5 votes

# Answer
Denote the sequence by $X\_0,X\_1,\ldots$. If the minimal polynomial is $x^7 + a\_6 x^6 + \cdots + a\_0 x^0$, then (by definition) for every $N$ it will hold that $X\_{N+7} = a\_6 X\_{N+6} + \cdots + a\_0 X\_N$ (modulo 2). (Your definition may vary slightly.) Since the first few values are $1,0,0,0,1,0,1,0$, this implies that $0 = a\_6 + a\_4 + a\_0$. Collect enough such equations and solve them to recover the minimal polynomial.
> 2 votes

---
Tags: algorithms, pseudo-random-generators
---


# Question
Title: Why to implement Open list in Heuristic search with priority queue
I don't understand why do we need to implement Open list using priority queue? There could be other data structure.

I understand the usage of priority queues from this example clearly. The newly discovered node would always be inserted at the head of the Open List. Then why do we need priority queue?

This article has mentioned everything about open list.

Usually Open Set contains the states. Its more convenient to assume Open Set as a list. However, the when we were to implement it in some programming language, we use priority queue as data structure.

By states, I mean assume rubix cube of 6 faces. When we rotate it we could have 3 possibilities: 90, 180, 270 degree rotations.

Total states 6x3 = 18

# Answer
Your question is not perfectly clear to me, so maybe I answer a different question from what you intended. The article you linked talks about A\* as a search algorithm that uses a heuristic to speed up searching, so I'll talk about this.

In a naive search you explore a graph for example in breadth first order: You start at some node, then visit its neighbors, then the neighbors of the neighbors and so on until you reach your goal state (or there is nothing more to explore).

Now suppose you had some function (the "heuristic") that can tell you more or less accurately how close a particular node is to your goal node. Then you can speed up your search by visiting nodes that are closer to your goal first. Now it depends on the quality of your heuristic how you should do that.

If your heuristic is perfect, that is, it tells you the distance to the goal accurately for every node, then you can just look at the neighbors of your start node and proceed to the node with the smallest distance to the goal. From there again you look at the neighbors and proceed to the one with the smallest distance to the goal. You don't need to keep any memory of possible alternative routes, because your heuristic exactly tells you which node you have to go to.

If the heuristic is not perfect however, the picture changes. Say your heuristic is optimistic, that is, it always underestimates the distance to the goal. Then can't assume that the neighbor with the smallest heuristic distance to the goal is always the correct node to which to proceed, because it might turn out that the true distance is much larger than what your heuristic told you. So you have to remember some alternative routes.

You can do that as follows: Maintain a set of nodes to which you could proceed (the neighbors of all nodes that you have already seen but not visited). This is you open set. In each step you continue searching from the node in the open set where the distance from the start plus the heuristic distance to the goal is smallest.

Now how do you find this node in the open set? You could store the open set as a list look at all nodes in each step to find it, but that is inefficient. Instead you could maintain the open set as a heap, where finding the minimum is cheap.

So this is why you want to use a heap in a heuristic search. It speeds up finding the next node from which to proceed with your search.
> 1 votes

---
Tags: algorithms, search-algorithms, heuristics
---


# Question
Title: How many times can you pour milk among 3 buckets?
This is a problem from usaco, which I solved, but I don't know how to estimate the number of times you can pour milk among the jugs, my solutions just uses a big enough number.

Here's the problem statement:

> Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.
>
> Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.
>
> For example, if the input is 8, 9, 10 then the output is 1, 2, 8, 9, 10.
>
> Another example: if the input is 2, 5, 10 then the output is 5, 6, 7, 8, 9, 10.

My approach is to recursively try all possible move sequences, keeping track of the contents of bucket C each time bucket A is empty. Currently I stop the recursion at the arbitrary depth 200. What is the correct depth to stop the recursion at?

# Answer
> 2 votes
Since the total amount of water is C liters (C being the capacity of bucket C), the number of possible states is at most the number of non-negative integer solutions of $x+y+z = C$, which is $\binom{C+2}{2}$. Any sequence of moves longer than that must repeat a state. Therefore it is enough to recurse up to level $\binom{C+2}{2}$.

---
Tags: algorithms
---


# Question
Title: Producing an algebric equation from a graph
I'm writing a computer game and one of my game's objects must follow a movement path that is very similar to the following graph.

The bold lines are the Y and X axis. In order to be able to code this movement thought I need the algebric equation that translates to this graph. For example f(x) = x^2.

Is there any mathematic technique I could use to obtain the algebric from of this function?

# Answer
> 1 votes
We can start from $\sin(x)$ which has a nice regular graph. To avoid negative values you can simply use the absolute value $|\sin(x)|$. This produces a graph similar to your but with constant height.

To decrease height as $x \to \infty$ we want to multiply that function by something that decrements. For example $\frac{1}{1+|x|}$ goes to $0$ as $x \to \infty$ and is symmetric. So $\frac{1}{1+|x|}|\sin(x)|$ is something similar to what you want with a maximum height of $1$.

If you multiply by a constant $A$ you "set" the maximum height to $A$. If you want to change the *width* of the bumps you can simply multiply the argument of the $\sin$ function, for example $\frac{A}{1+|x|}|\sin(2x)|$ will have maximum height $A$ and a width that is *half* the width of the normal $\sin$, while using $\sin(x/2)$ would produce a bump that is *twice* the width of the normal $\sin$.

See this wolfram alpha's graph for an example result.

---

You can also change the degradation of height by setting a different power for the $|x|$. For example using $\frac{1}{1+x^2}$ you'd have a faster drop to $0$, while using $\frac{1}{1+\sqrt{|x|}}$ would produce a slower change in height.

---
Tags: algebra
---


# Question
Title: Give a specific case where calling a polynomial time function n times gives an exponential time algorithm
We were asked this question in exam and I am not satisfied with the answer the teacher gave.

Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c\_1}$. If we call the function polynomial times, say $n^{c\_2}$ times, then the time complexity of the algorithm becomes $n^{c\_1+c\_2}$. Which is clearly polynomial.

Now the answer our teacher gave. Let there be a subroutine $S\_i$ with time complexity $2^{i-1}n$ where $n$ is the input size. Therefore the time complexity of $S\_n$ is $2^{n-1}n$. Which is exponential.

I am not satisfied with this answer because firstly the variable $i$ seems shady. We are not even calling any subroutines polynomial times, we are just assigning some value arbitrarily.

If our teacher's answer is correct could someone elaborate? If not, is there any answer to this question?

# Answer
> 14 votes
A concrete example is repeated squaring. Squaring an integer of length $n$ takes time $O(n^2)$ (using the naive algorithm; you can do much better with more complicated algorithms). If you square an $n$-bit integer $i$ times in a row, its length becomes $2^i n$. So if you square it $n$ times in a row, the complexity is $O(4^n n^2)$, which is exponential.

The source for confusion is the input length. If the polynomial time function increases the length, then the behavior can be exponential. If it doesn't, the behavior stays polynomial.

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


# Question
Title: A function computable using a circuit of size $10s$ but not of size $s$
I'm studying Computational Complexity and I have stumbled upon the following question which I have no idea how to even start proving. I would appreciate any help.

> Prove that for every function $s(n)$ such that $n \le s(n) \le \frac{2^n}{100n}$ there exists a Boolean function $f\colon \\{0,1\\}^n \to \\{0,1\\}$ such that $f$ doesn't have a Boolean circuit of size $s(n)$ that computes it but has a Boolean circuit of size $10s(n)$.

# Answer
> 2 votes
One possible approach is as follows. A counting argument shows that there are function on $n$ bits that require circuits of size $\Omega(2^n/n)$, and on the other hand a non-trivial construction that you probably saw in class shows that every function on $n$ bits can be computed using a circuit of size $O(2^n/n)$. This takes care of the case $s(n) = 2^n/{100n}$.

For general values of $s(n)$, you can use functions depending on $m \leq n$ variables, making sure that the resulting lower bound $\Omega(2^m/m)$ and upper bound $O(2^m/m)$ fit snugly around $s(n)$.

---
Tags: complexity-theory, circuits
---


# Question
Title: One-dimensional k-center problem. Finding minimum distance
This is a follow-up to this question: Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \\{x\_1, ..., x\_N\\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \\{ y\_1, ..., y\_M \\}$. Let's define distance between sets $X$ and $Y$ to be $$d(X,Y) = \max\_{i=1,...,N} ~~ \min\_{k=1,...,M} ~ |x\_i - y\_k|$$

Which algorithm should i use to get minimal possible value of $d(X,Y)$?

I tried do develop dynamic programming algorithm but didn't succeed. In my previous question i was told that this problem is known as unweighted one-dimensional k-center problem. I've looked through some papers on the net but all of them offered the ways to find some particular $Y$. But my current problem seems to be easier: i need only the optimal value of $d(X,Y)$. So i expect the solution to be rather standard and rather easy.

Thanks in advance.

P.S. The original problem is taken from here: http://www.e-olymp.com/en/problems/3208

# Answer
Hint: Turn the problem upside down and ask yourself: can I easily check if the answer is less than or equal to $t$?
> 2 votes

---
Tags: optimization
---


# Question
Title: Which tree decomposition of a graph is preferrable?
In this page, there are two examples of tree decomposition of a graph $G$.

Could there be another decomposition such as:
$\\{A,B\\}, \\{C,E,F\\}, \\{D,F,G\\}$

or did I get the rules of decomposition wrong? Must two adjacent vertices of the tree share two vertices of the graph?

And considering these decompositions, which one is better than the others? Or is there no "better" decomposition as long as it is a correct decomposition?

# Answer
> 4 votes
A tree decomposition of smaller width is generally preferable over one of larger width.

The "decomposition" you've listed is not a tree decomposition since (a) you haven't given the tree structure and (b) it violates the requirement that for each edge $(u,v)$ there is a bag containing both $u$ and $v$. For instance, there's no bag containing both $B$ and $C$.

In general, a tree decomposition must satisfy these 3 requirements:

* Every vertex must be contained in some bag
* For every edge $(u,v)$ there must be a bag containing $u$ and $v$
* The subgraph of the tree induced by bags containing a specific vertex is connected

---
Tags: graphs, trees
---


# Question
Title: Algorithm to find a subgraph such that all of its edges has an anti edge
> Let $G=(V,E)$ be a directed graph. The "invertible" part of $G$ is the subgraph $H=(V,E\_2)$ such that $(u,v)\in E\_2 \iff (u,v)\in E \land (v,u)\in E$.
>
> Find an algorithm that generate $H$ from $G$ in a linear time, where $G$ is represented with an adjacency list. Non linear memory is allowed.

Obviously the brute force approach won't be linear, and I thought to use an adjacency matrix but that would be at least $\Omega (n^2)$.

I also thought maybe it's possible to create a forest of DFS trees and then, checking each edge if it has an anti edge would be a lot more easier, but I'm not sure if it would be possible to keep all the information from the original graph...

Another way is to generate the anti graph of $G$, then intersect it with $G$ and then subtract the intersection from $G$, we'll be left with all edges that didn't have an anti edge, it sounds too complicated too work in linear time though and I'm not sure how to implement this algorithm..

Am I on the right track? Is there another way?

# Answer
Here is one approach, which assumes that the adjacency lists are sorted. First, compute the reversed graph (your anti graph) in linear time. Then, compute the intersection by first merging the adjacency lists from both the original graph and the reversed graph, and then looking for edges which appear twice. This takes linear time since the lists are sorted.
> 1 votes

---
Tags: algorithms, graphs
---


title: calculating overlap of modular ranges

text:
# Question
Title: calculating overlap of modular ranges
So, this might be a really simple problem but I can't seem to find a nice algorithm to solve it:

> Given two ranges, *\[a1, a2\]*, *\[b1, b2\]* (all real numbers) and a real number *n*, find the length of the overlapping segment between the two ranges over a modulo of *n*.

For example, consider a **24**-hour clock and the range **\[20, 4\]** (night time); for a given range, calculate the number of hours within that range that are night hours:

\[13, 21\] ==\> 1 #\[20,21\]

\[0, 6\] ==\> 4 #\[0, 4\]

\[11, 19\] ==\> 0

I tried to think of it in terms of predefined segments \[a1,b1\], \[b2, a2\] and do some math with them but it didn't work. Maybe I should sort them somehow?

I will appreciate any help or direction, thanks!

# Answer
Here is how I understand your problem. We have a modulus $n$. A generalized interval $\[\\!\[a,b\]\\!\]$ consists of $\[a,b\]$ if $a \< b$, and of $\[a,n) \cup \[0,b\]$ if $a \> b$ (assume for simplicity that $a != b$). You want to know the size of the intersection of two generalized intervals $\[\\!\[a\_1,b\_1\]\\!\],\[\\!\[a\_2,b\_2\]\\!\]$.

One way to solve this is to decompose each generalized interval into a disjoint union of one or two intervals, and then compute the size of the pairwise intersections (which I will let you work out yourself), and sum them up.
> 1 votes

---
Tags: algorithms
---


title: Implementation of Naive Bayes

text:
# Question
Title: Implementation of Naive Bayes
I am implementing a Naive Bayes algorithm for text categorization with Laplacian smoothing. The problem I am having is that the probability approaches zero because I am multiplying many small fractions. Therefore, the probability eventually yields zero. This is because there are several words within the documents and training sets.

Because of this, I am not able to categorize the texts. Is there a way I can get around this problem? Am I doing something wrong in my implementation?

# Answer
> 14 votes
The usual trick to avoid this underflow is to compute with logarithms, using the identity $$ \log \prod\_{i=1}^n p\_i = \sum\_{i=1}^n \log p\_i. $$ That is, instead of using probabilities, you use their logarithms. Instead of multiplying them, you add them.

Another approach, which is not so common, is to normalize the product manually. Instead of keeping just one floating point number $p$, you keep a floating point number $p\_0 \in \[1,2)$ (say) and a negative exponent $x$ such that $p = p\_0 2^x$. After each operation you normalize the resulting number.

---
Tags: machine-learning, natural-language-processing, floating-point, numerical-algorithms
---


title: Combine $k$ sorted lists into one

text:
# Question
Title: Combine $k$ sorted lists into one
Say I have $k$ sorted lists of the same size $n/k$, and I want to combine them into one sorted array in $O(n\log k)$ time.

The solution I came up with is to recursively halve the lists until you have sections of two lists. Then you combine them by setting a pointer at the start of each one, and placing the smaller element into a new array and incrementing its pointer until you've gone through every element, then return that sorted array.

The combine part does at most $2n$ comparisons, so it's $O(n)$. The recursion depth is $\log\_2 k$, since you're halving the remaining lists at each combination. This would give a total of $n\log\_2 k$.

Is this a correct implementation and time analysis?

# Answer
What you describe is a sort of *recursive merge* which generalizes merge sort, and indeed results in the advertised complexity. The pointer procedure which you are trying to describe is usually just called *merge*.

Another approach is using a min-heap of size $k$, which stores the current "contenders" for the $k$ smallest elements. It is initialized with the smallest elements of each of the lists, and at each step you pop the smallest element and add it to the merged array, replacing it with the next smallest element in the corresponding list.
> 3 votes

---
Tags: time-complexity, sorting
---


# Question
Title: Finding a simple cycle that goes through two vertices
Given a directed graph $G$ and two vertices $u$ and $w$, how can we find a simple cycle that goes through $u$ and $w$?

One can try putting together paths from $u$ to $w$ and $w$ to $u$ — but these might have edges or nodes in common, even if they are chosen to be shortest paths.

# Answer
The decision version of your problem (deciding whether such a cycle exists) is NP-complete. See Proposition 9.2.1(P3) on page 477 (495) in Digraphs – Theory, Algorithms and Applications by Bang-Jensen and Gutin.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Does a non deterministic Turing machine which is a decider halt on all branches for all inputs?
Does a non deterministic Turing machine which is a decider halt on all branches for all inputs??

I know it must halt on all branches for a string not in language, but for a string in language, NDTM requires only one accepting branch so even if some other branch is infinite, NDTM will still accept the string

# Answer
> 4 votes
You can define it either way. The simple way to define it is to say that *every* branch must halt for every input. Alternatively, you can say that, if the input is in the language, at least one branch must accept, so you don't care if the others reject or just fail to halt; if the input is not in the language, then every branch must reject.

Both in terms of computability and complexity, you can show that the two definitions are completely equivalent.

---
Tags: turing-machines, computation-models, nondeterminism
---


# Question
Title: Difference between deterministic and nondeterministic universal turing machine
It is known that a nondeterministic universal turing machine (UTM) can simulate another nondeterministic TM with running time $t(n)$ in time $c t(n)$, where $c$ is a constant. It is also known that a deterministic UTM can simulate another deterministic TM with running time $t(n)$ in time $ t(n)\log(t(n))$.

My question is: why is there a $\log(t(n))$ slowdown in the simulation of a deterministic TM by a UTM, as opposed to a constant factor slowdown in the nondeterministic case?

# Answer
> 1 votes
Please refer to the answer in the similar question, "Why is simulation by non deterministic Turing machine faster than a deterministic one?".

Basically, in the non-deterministic universal Turing machine we guess the contents of the tape and check if the guess is correct later on. This allows us to save time going to and fro in the work tape.

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


# Question
Title: Randomized Meldable Heap - Expected Height
Randomized Meldable Heaps have an operation "meld", which we then use to define all other operations, including insert.

The question is, what is an expected height of that tree with $n$ nodes?

Theorem 1 of Gambin and Malinkowski, *Randomized Meldable Priority Queues* (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF) gives the answer to this question with proof. However, I do not understand why we can write: $$\mathbb{E} \[ h\_Q\] = \frac{1}{2} ((1 + \mathbb{E}\[h\_{Q\_L}\]) + (1 + \mathbb{E}\[h\_{Q\_R}\]))\\,.$$

For me the height of the tree is

$$h\_Q = 1 + \max\\, \\{ h\_{Q\_L}, h\_{Q\_R}\\}\\,,$$

which I can expand to:

$$\mathbb{E} \[ h\_Q\] = 1 + \mathbb{E}\[\max \\,\\{ h\_{Q\_L}, h\_{Q\_R}\\}\] = 1 + \sum k \mathbb{P}\[\max\\, \\{ h\_{Q\_L}, h\_{Q\_R}\\} = k\]\\,.$$

The probability that the maximum of a height of two subtrees is equal to $k$ can be rewritten using the law of total probability:

\begin{align\*} \hspace{2em}&\hspace{-2em} \mathbb{P}\[\max\\, \\{ h\_{Q\_L}, h\_{Q\_R}\\} = k\] \\ &= \mathbb{P}\[\max\\, \\{ h\_{Q\_L}, h\_{Q\_R}\\} = k \mid h\_{Q\_L}\leq h\_{Q\_R}\]\\,\mathbb{P}\[h\_{Q\_L} \leq h\_{Q\_R}\]\\ &\hspace{2em} + \mathbb{P}\[\max\\, \\{ h\_{Q\_L}, h\_{Q\_R}\\} = k \mid h\_{Q\_L} \> h\_{Q\_R}\]\\,\mathbb{P}\[h\_{Q\_L} \> h\_{Q\_R}\] \\ &= \mathbb{P}\[h\_{Q\_R} = k \mid h\_{Q\_L} \leq h\_{Q\_R}\]\\,\mathbb{P}\[h\_{Q\_L} \leq h\_{Q\_R}\]\\ &\hspace{2em}+ \mathbb{P}\[h\_{Q\_L} = k \mid h\_{Q\_L} \> h\_{Q\_R}\]\\,\mathbb{P}\[h\_{Q\_L} \> h\_{Q\_R}\]\\,. \end{align\*}

So at the end I get:

\begin{align\*}\mathbb{E} \[ h\_Q\] &= 1 + \sum k \\{ \mathbb{P}\[h\_{Q\_R} = k \mid h\_{Q\_L} \leq h\_{Q\_R}\]\\,\mathbb{P}\[h\_{Q\_L} \leq h\_{Q\_R}\]\\ &\hspace{2em}+ \mathbb{P}\[h\_{Q\_L} = k \mid h\_{Q\_L} \> h\_{Q\_R}\]\\,\mathbb{P}\[h\_{Q\_L} \> h\_{Q\_R}\] \\}\\,. \end{align\*}

This is where I am stuck. I can see that $\mathbb{P}\[h\_{Q\_L} \> h\_{Q\_R}\]$ is more or less equal $\frac{1}{2}$ (However we need at most $\leq \frac{1}{2}$). But except that nothing leading to the formula from the beginning.

The heights of the subtrees do not seem to be independent to me.

Thanks for help.

# Answer
In the paper, $h\_Q$ isn't the height. It's the length of a random walk away from the root in a full binary tree (they insist every leaf is "nil"), so the expression they have is the right thing.

Also, you can avoid induction. The probability of ending at a specific leaf of depth $d$ is just $2^{-d}$. So the expected length of the walk is

$$ \sum\_{\ell\in \text{leaves}(Q)} \text{depth}(\ell)2^{-\text{depth}(\ell)} $$

which the entropy of a distribution a set of size $|\text{leaves}(Q)|$.
> 4 votes

---
Tags: algorithm-analysis, data-structures, randomized-algorithms, heaps
---


# Question
Title: Showing that a language satisfies the pumping lemma
I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma

If L = {ambncndn | m,n \>= 1 }

Should I have n be the constant of the pumping lemma? Is z=ambncndn and |z|= m+3n\>n ?

By the pumping lemma, there exist u,v,w,x,y such that z=uvwxy, |vwx| \<=n, |vx|\>=1 . I'm just a little thrown off by the two different letters for the exponents, can I treat m and as another n?

# Answer
> 0 votes
You want to show that the language $L = \\{a^mb^nc^nd^n \mid m,n\ge 1 \\}$ does satisfy the Pumping Lemma (for context-free languages) while it is not context-free.

In order to do so, you must show that every string can be pumped within the language, so for every string $z=a^mb^nc^nd^n$ (for large enough $m+3n$) you must find a decomposition $z=uvwxy$ that can be pumped. The problem however is that your language $L$ does *not* satisfy the Pumping Lemma. Possibly?) you wanted to pump the first $a$ in a string (taking $u=x=y=\lambda$, $v=a$, $w=a^{m-1}b^nc^nd^n$). Generally that works, but not if the string contains a single $a$, like $ab^nc^nd^n$. Then we can pump the letter $a$ \`down' choosing $i=0$ which results in a string outside of $L$. All other decompositions will fail (they will destroy the $abcd$ order or the equal numbers of $b,c,d$).

An example of a non-regular language that satisfies the Pumping Lemma (for regular languages) can be found here: Languages that satisfy the pumping lemma but aren't regular? .

It is of a very specific form $\\$\cdot K \cup \\{\\$^k \mid k\neq 1\\}\cdot \Sigma^\*$ (for a complicated language $K$) that can be used for context-free pumping examples too.

# Answer
> 0 votes
Assume that pumping lemma is satisfied for $L$. Let $N$ be the pumping length.

Now take $z = ab^Nc^Nd^N \in L$. $|z| = 3N+1$ and hence this string can be pumped.

For this string, every choice of $u,v,w,x$ and $y$ that satisfies the conditions of pumping lemma will have a choice of $i \in \mathbb{N}$ such that $uv^iwx^iy \not\in L$. This is a contradiction. Hence $L$ is not context-free.

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


title: Brzozowski algebraic method for NFA

text:
# Question
Title: Brzozowski algebraic method for NFA
Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA

* some nodes have multiple in/outgoing edges
* single start state
* there might be multiple final states
* a state can contain self loops where a symbol is consumed
* no epsilon transitions

What i'm trying to do is generate a regular expression from this graph. I've found the following topic using Brzozowski algebraic method: https://cs.stackexchange.com/q/2392

However, it seems to be for DFA's, so my question:

can I use **Brzozowski algebraic method** OR **Transitive closure method** with my NFA, or do i need conversion first?

I need an algorithm that can be done by a computer to automatically generate a regex from a given graph.

# Answer
Brzozowski's algebraic method is safe as long as you don't have epsilon transitions. It even works if your transitions are labelled by languages not containing the empty word. It may also work if some transitions contain the empty word, as long as you can eliminate them, as in the example below:

the system can be written as \begin{align\*} X\_1 &= (a^\*b + a)X\_2 + b^\*X\_3 \\ X\_2 &= (a+b)X\_1 + bX\_3 + 1 \\ X\_3 &= aX\_1 + aX\_2 + 1 \end{align\*} Replacing $X\_3$ by $aX\_1 + aX\_2 + 1$, and observing that $a + b^\*a = b^\*a$, we obtain the equivalent system \begin{align\*} X\_1 &= (a^\*b + a)X\_2 + b^\*(aX\_1 + aX\_2 + 1) = b^\*aX\_1 + (a^\*b + b^\*a)X\_2 + b^\* \\ X\_2 &= (a+b)X\_1 + b(aX\_1 + aX\_2 + 1) + 1 = (a + b + ba)X\_1 + baX\_2 + b + 1\\ X\_3 &= aX\_1 + aX\_2 + 1 \end{align\*} We deduce from the second equation $$ X\_2 = (ba)^\*((a + b + ba)X\_1 + b + 1) $$ and replacing $X\_2$ by its value in the first equation, we obtain \begin{align\*} X\_1 &= b^\*aX\_1 + (a^\*b + b^\*a)(ba)^\*((a + b + ba)X\_1 + b + 1) + b^\*\\ &= (b^\*a + (a^\*b + b^\*a)(ba)^\*(a + b + ba))X\_1 + (a^\*b + b^\*a)(ba)^\*(b + 1) + b^\* \end{align\*} Finally, the language recognised by the automaton is $$ X\_1 = \bigl(b^\*a + (a^\*b + b^\*a)(ba)^\*(a + b + ba)\bigr)^\*\[(a^\*b + b^\*a)(ba)^\*(b + 1) + b^\*\] $$ since $1$ is the unique initial state.

Now, if you want to implement this algorithm, you may end up with more complicated regular expressions. For instance, the sentence "observing that $a + b^\*a = b^\*a$" might be difficult to implement. Other useful simplifications like $a^\* + 1 = a^\*$ or even $K + K = K$ or $K + L = L + K$, where $K$ and $L$ are regular expressions, are also not easy to implement and require more sophisticated rewriting systems.
> 5 votes

---
Tags: algorithms, finite-automata, regular-expressions, nondeterminism, simulation
---


# Question
Title: How can I do an optimization problem that involves finding a sequence?
The problem I am trying to solve is to find the fastest way to produce an total amount of something. There are several different producers that each have a different production and cost (based on the number of the item that is already owned) which can be purchased during production.

For example, assume that the goal is to produce 1000 units total (including the amount spent on buying new producers), and the three producers that can be bought $A$, $B$, and $C$, have productions and base costs of $1$ per second and $20$, $7$ per second and $50$, and $14$ per second and $100$, respectively. Buying a producer multiples the price of the next producer of the same type by 1.1 (so, for example, buying an $A$ for the base price of 20 means the next $A$ will cost $1.1 \cdot 20 = 22$, and the next $1.1 \cdot 22 = 24.2$, et cetera). When a producer is bought, the price of the produced is subtracted from the current units produced, but not the total production (so if you have 30 units, and you buy an A, you now have 10 units left). Selling a producer returns half of the units used to purchase it, and reduces the cost by 1.1 times (so if the cost was at 24.2, it would go down to 22). By starting with 1 $A$, what is shortest amount of time to produce 1000 units and in what order should you purchase producers?

The shortest time is 68 seconds, buying producers in the following order: A,B,B,B,C,C,C,C.

My first solution was simply to try all the different sequences, then determine the one that will be the fastest after $n$ purchases, but, naturally, this was very slow. My second solution was to try a greedy search where I just look for the best solution in terms of time at every step. My third solution was to try a search where I used the increased in production as the score for each sequence, and backtrack to earlier solutions if any of them had better scores.

Are there any other problems or generalizations I can make to find an optimal (or near optimal solution faster)?

# Answer
# Graph search

I recommend you formulate your problem as a graph search problem. Each vertex represents a state of the system. The state of the system lists the number of units you currently have and the number of each producer you currently have (e.g., "20 units, 1 A, 3 B's, and 0 C's"). You add an edge $s \to s'$ if you can get from state $s$ to state $s'$ in a single step. The start state is "0 units, 0 A's, 0 B's, 0 C's". The goal states are all states with 1000 units.

You can now use breadth-first search to find the shortest path from the start state to a goal state.

For better performance, use A\*. It's not too hard to construct a consistent and admissible heuristic that always underestimates the distance to the goal state.

As long as the number of producers is not too large, I expect this to be pretty efficient.

# Greedy algorithm

It might be possible to build a greedy algorithm for your problem.

Consider a simplified variant where you are not allowed to sell producers you own, and where the number of units you have is allowed to go negative (you can still buy a producer even if it would put you in debt). This has an efficient greedy solution. In particular, consider the decision problem variant: given $t$, determine whether there exists a sequence that gets you to the goal within at most $t$ seconds. This can be answered greedily.

Consider our first action. We have $k$ options for actions: "buy $P\_1$", "buy $P\_2$", ..., or "buy $P\_k$". Note that it's always advantageous to make all your producer-buys as early as possible; there's no point in waiting. Assume that for producer $P\_i$ we have base cost $b\_i$ and production $p\_i$. If we buy $P\_i$, the net profit from that purchase (over the entire $t$-second time window) is $(t-1) p\_i - b\_i$. So, for your first action, choose the action with largest net profit. Now, for your second action, we have the same problem, except that $t$ is one smaller, so we can continue iteratively. After $t$ seconds, we check whether the resulting sequence has reached a goal state.

\[You can also consider a kind of exchange operation, where you compare "buy $P\_i$ then $P\_j$" to "buy $P\_j$ then $P\_i$". You'll find that the decision rule for making that choice is as follows. Associate to the action "buy $P\_i$" a 'profit foregone if we defer buying $P\_i$' value of $0.1 b\_i + p\_i$. Determine which of $P\_i$ or $P\_j$ has lower 'profit foregone', and then choose to do that one first.\]

You could check whether you can generalize this analysis to the case where you're allowed to sell producers and where you're not allowed to let the number of units owned go negative. It looks a little tedious, so I'll leave the case analysis to you.
> 2 votes

---
Tags: optimization
---


# Question
Title: Generating integer vectors sorted by total weight
I am trying to implement an algorithm that finds the key of the RC4 cipher from the inner permutation. For each key byte I have several options, each with different weight. Is there any way, to test first the possibilities with highest weight, than with second highest, and so on?

Basically what I need is to generate vectors like this (for 3 byte key):

```
[0,0,0]
[1,0,0]
[0,1,0]
[0,0,1]
[1,1,0]
[1,0,1]
[0,1,1]
[1,1,1]
[2,1,1]
...

```

So it is sorted by sum.

(I have the bytes stored in a table sorted by weight, highest weight on the top.)

A similar problem is solved here: application of Dijkstra's algorithm, but I don't know how to apply it to my problem.

The paper only mentions that they do it in iterative depth manner.

Is there any algorithm which solves this problem?

# Answer
> 1 votes
I'm assuming the following version of the problem. We are considering all vectors in the set $\[N\_1\] \times \cdots \times \[N\_d\]$ (of which there are $N\_1\cdots N\_d$). We are given weights $w\_{i,1} \leq \cdots \leq w\_{i,N\_i}$ for each of the $d$ sets (if you prefer, you can index the elements starting from 0 instead of starting from 1). Our goal is to enumerate $\[N\_1\] \times \cdots \times \[N\_d\]$ in non-decreasing order of weight, where the weight of $(x\_1,\ldots,x\_d)$ is $w\_{1,x\_1} + \cdots + w\_{d,x\_d}$.

One possible approach uses a heap. The heap is initialized with $(1,\ldots,1)$. At each step, we extract the element $(x\_1,\ldots,x\_d)$, output it, and insert the up to $d$ elements obtained by increasing each of the coordinates by 1 (unless it equals its maximum). It is hard to estimate the complexity of this algorithm, but it might work reasonably well in practice.

---
Tags: algorithms, arrays, enumeration
---


title: Does a reduction with $\infty$ work?

text:
# Question
Title: Does a reduction with $\infty$ work?
Lately, I saw an NP-complete proof that involves creating an instance of a problem using $\infty$. Is this a polynomial-time reduction?

More precisely, let a problem $\Pi$ has an instance $I=(n, A, v)$ where $A$ is a matrix of size $n\times n$, $A=\[a\_{ij}\]$, and $v$ is positive.

The proof that $\Pi$ is NP-complete works by reducing the independent set problem (an instance is a graph $G=(V,E)$ and an integer $k$) to $\Pi$ as follows: $n=|V|,v=k$ and

$$a\_{ij} = \begin{cases} \infty \text{ if } \\{i,j\\}\in E\\ 0, \text{ otherwise } \end{cases}.$$ Also, $G$ has an independent set of size $k\iff\Pi$ has a value $v= k$.

I do not see how one can set $a\_{ij}$ to $\infty$.

# Answer
> 4 votes
In most cases in which such a reduction is presented, the reduction also works with $\infty$ replaced by a large enough number $M$ which is at most exponential in some power of $n$. If you replace $\infty$ by $M$ then you get a bona fide instance of $\Pi$, and this instance has polynomial size (and so the reduction runs in polynomial time) since $|M| = O(n^C)$ for some $C$, where $|M|$ is the length of the binary encoding of $M$.

You are right that using $\infty$ instead of $M$ is a bit sloppy, but it often results in a cleaner description, it being understood that the "real" reduction uses some large enough finite $M$.

---
Tags: reductions
---


# Question
Title: Categorization of Binary search as Divide and Conquer
Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.

# Answer
This might seem silly but here we go.

Let our array be $A$ and the current range we are searching in be denoted as $\[L,R\]$ and let $mid = \frac{L+R}{2}$.

* The divide step - We divide our search space into two ranges - $\[L,mid-1\]$ and $\[mid,R\]$.
* The conquer step - Let's assume that WLOG the element $x$ that we are searching for is such that $x \< A\[mid\]$. Then we combine the knowledge that $x$ can be in $\[L,mid)$ and $x$ cannot be in $\[mid,R\]$ to reduce our search space to $\[L',R'\] = \[L,mid-1\]$
> 9 votes

# Answer
There is no accepted formal definition of the divide and conquer paradigm (see this question for some suggestions), and so we must regard this paradigm as an informal concept. The main idea in divide and conquer is to split the original problem into smaller subproblems of a similar nature, and then combine them to deduce the final answer. In the case of binary search (or of quickselect), we split the original problem into one smaller subproblem. In other cases the number of subproblems is larger than two, for example Strassen's fast matrix multiplication algorithm, which splits into 7 subproblems.

Since divide and conquer is an informal concept, it is possible to disagree about what counts as divide and conquer. Describing binary search as divide and conquer is supposed to help you conceptualize the algorithms that you learn in the course. If you don't find this helpful in this case, just ignore it.
> 5 votes

# Answer
We *do* combine results with binary search. Each recursive call can return either a found location, or it can return `None`. This `None` value is the identity element for the combination operator `++`, defined such that

```
result ++ None == result
None ++ result == result
(None ++ None == None, implied by the preceding)

```

(`result` can be a simple Yes, or it can be the position where the key was found.)

The key benefit of binary search *on sorted data* is that one of the two recursive searches is guaranteed to return `None`, and that one is guaranteed to do so in O(1) time. This means that for our search operation defined as

```
bs(A, x, x, key) = either result or None
bs(A, x, y, key) = bs(A, x, mid, key) ++ bs(A, mid, y, key)

```

the running time is defined by `T(n) = T(n/2) + O(1) + O(1) = O(lg n)`, not `T(n) = 2*T(n/2) + O(1) = O(n)`.

In practice, we are less precise and simply say that each call to `bs` only makes a single recursive call, ignoring what the unmade call would return. We do this to avoid the overhead of making an actual function call whose return value we can predict.
> 1 votes

---
Tags: divide-and-conquer, binary-search
---


# Question
Title: What does ⊢ mean in operational semantics?
I have been reading a couple of texts on operational semantics.

In \[1\], the evaluation of expressions is done as in this rule:

$\frac{\<e\_1,s\>\\;\Rightarrow \\;n\_1\\;\\;\\;\<e\_2,s\>\\;\Rightarrow \\;n\_2} {\<e\_1+e\_2,s\> \\;\Rightarrow \\; n\_3}$,

where $n\_3 = n\_1+n\_2$.

That is, the state $s$ is represented in a tuple with the expression to be evaluated.

But in \[2\] a rule for evaluation of a function as this:

$\frac{\rho\\; \vdash\\; e \\;\Rightarrow\\; v, \\;\\;\\;\\;\rho\[v'/x\]\\;\vdash\\;e \\;\Rightarrow\\; v} {\rho\\; \vdash \\;F(e) \Rightarrow v}$

I am confused: why in the first case, the state $s$ was passed along with the expression as a pair, and in the second case, the environment $\rho$ was not (it was to the left of $\vdash$). Does $\vdash$ here have the same meaning as in formal logic? Are the two notations that I have shown (using a pair/tuple and using $\vdash$) interchangeable in operational semantics?

In this text (\[2\]), the author writes, before the first time he uses $\vdash$,

> In a given environment an expression will evaluate to a numeral. We will write this as $\rho \\; \vdash\\; e \\;\Rightarrow \\;v$

But he doesn't explain why, and in another text (\[1\]) the same author uses the pair notation for the same purpose.

# Answer
> 15 votes
This is something that I think is not explicitly pointed out or not pointed out with enough emphasis in many, even introductory, CS/type theory/logic texts.

$\vdash$ doesn't mean anything.

Instead, in this example, the three place relation $- \vdash - \Rightarrow -$ is what has meaning.

Except that was a lie. It doesn't *a priori* have meaning either. That relation is what is *being defined*. $- \vdash - \Rightarrow -$ is just a (mixfix) name. It does, of course, have some informal meaning we are hoping to capture with this definition, and after it is defined it does have meaning.

In most cases, such relationships are being inductively defined which makes them *identical* to inductive families in a dependently typed language. For example, here are the rules for the arithmetic language fragment from figure 3.2 in section 3.1: $$ \frac{}{\langle n,s \rangle \Downarrow n} \qquad \frac{\langle e\_1, s\rangle \Downarrow n\_1 \qquad \langle e\_2, s\rangle \Downarrow n\_2}{\langle e\_1 + e\_2, s \rangle \Downarrow n\_1+n\_2} \qquad \frac{}{\langle \mathtt{L}, s \rangle \Downarrow s(\mathtt{L})} $$

and here's Agda code for this fragment:

```
data Expr : Set where
    Num : Nat -> Expr
    Add : Expr -> Expr -> Expr
    Lookup : Label -> Expr

data Eval : (e : Expr) (s : Label -> Nat) (n : Nat) -> Set where
    EvalNat : {n : Nat}{s : Label -> Nat}
        -> Eval (Num n) s n
    EvalAdd : {e1 e2 : Expr}{n1 n2 : Nat}{s : Label -> Nat}
        -> Eval e1 s n1
        -> Eval e2 s n2
        -> Eval (Add e1 e2) s (n1+n2)
    EvalLookup : {l : Label}{s : Label -> Nat}
        -> Eval (Lookup l) s (s l)

```

A proof of a statement like $\langle 3+4,s \rangle \Downarrow 7$ looks like:

```
threePlusFourIsSeven : {s : Label -> Nat} -> Eval (Add (Num 3) (Num 4)) s 7
threePlusFourIsSeven = EvalAdd EvalNum EvalNum

```

Rule induction, which is the topic of section 2.3, is induction over data types like this.

I hope at this point that you can see that the answer to:

> Are the two notations that I have shown (using a pair/tuple and using ⊢) interchangeable in operational semantics?

is "yes, but only because whenever you see such notation it is being or has been defined, and we can use whatever notation we want to mean whatever we want if we define it." In other words, nothing is stopping us from having used the syntax $s \vdash e \Rightarrow n$ instead of $\langle e, s\rangle \Rightarrow n$. We'd just be defining a relation named $- \vdash - \Rightarrow -$ instead of being named $\langle -,- \rangle \Rightarrow -$.

That said, there are (unwritten) *conventions**naming* conventions no less – that are commonly abided by. So $\vdash$ is normally used to separate some "context" or "environment" from "terms". The tuple notation is often used for state components because we (denotationally) model state as a function from the old state to the output plus the new state. If we also have input, this results in a function `(Input, State) -> (Output, State)`. This intuition gets reflected in the naming of the operational semantics, as in, for example, figure 3.6 which includes rules like $\langle \mathtt{skip};C\_2, s\rangle \rightarrow \langle C\_2, s\rangle$. Nothing *stops* us from writing that $s \vdash \mathtt{skip};C\_2 \rightarrow s \vdash C\_2$, but I think you can agree that that is harder to read.

I got around to posting a blog article that goes into this notation in more detail.

---
Tags: notation, operational-semantics
---


title: Regular expression of a given language

text:
# Question
Title: Regular expression of a given language
Could somebody please confirm if a regular expression of language: $$ L := \\{b(ab)^n a^m \mid n, m \geq 0\\} $$ is $$\\{b, (ab)^\* a^\*\\}? $$

And if not, could somebody please tell me why?

# Answer
> 1 votes
In short, your answer is No. For explanation about **Regular language** and **Regular expression**, you can check this link. And the correct answer to your question would be: $b(ab)^\*a^\*$

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Is it possible to reduce the number of variables in bin packing?
The bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum\_{i=1}^n y\_i\\ & \text{subject to} & & B \geq 1,\\ & & & \sum\_{j=1}^n a\_j x\_{ij} \leq V y\_i,\forall i \in \\{1,\ldots,n\\}\\ & & & \sum\_{i=1}^n x\_{ij} = 1,\forall j \in \\{1,\ldots,n\\}\\ & & & y\_i \in \\{0,1\\},\forall i \in \\{1,\ldots,n\\},\\ & & & x\_{ij} \in \\{0,1\\}, \forall i \in \\{1,\ldots,n\\}, \\, \forall j \in \\{1,\ldots,n\\},\\ \end{align}

where $y\_i = 1$ if bin $i$ is used and $x\_{ij} = 1$ if item $j$ is put into bin $i$.

Why do we use $x\_{ij}$ and $y\_{i}$? We can just use $x\_{ij}$.

* if $x\_{ij}=1$ than bin $i$ is used and item $j$ is put into bin $i$; and
* if $x\_{ij}=0$ than bin $i$ is not used.

Is that correct? If so, why can't I find any formulation with only $x\_{ij}$?

# Answer
An integer program, or more properly an integer *linear* program, consists of a linear program together with integrality constraints stating that some of the variables are integers. As such, its objective function is always a linear combination of variables.

When the objective is minimization, it is *admissible* to have $\max$ operators (appearing positively) in the objective function. This means that there is an equivalent proper integer program. This program is obtained by introducing auxiliary variables, just as the variables $y\_i$ are introduced in your example to implement $\max\_j x\_{ij}$.

To answer your question, it all depends on what you consider as an integer program. The standard definition only allows linear objective functions, and in this case the $y\_i$ are necessary. If you also allow $\max$ operators in the objective function, then the $y\_i$ are not necessary.
> 3 votes

# Answer
Decided to post an answer here:

You can get by with only $x\_{ij}$s in this case. However, the objective function now becomes harder to define.

A cleaner way to work with bin packing is to turn it into a decision problem (you can convert it back to optimisation problem by doing a binary search, hence it doesn't add an exponential factor).
> 2 votes

---
Tags: np-complete, integer-programming
---


# Question
Title: Polynomially reducing NP-Complete problem clarification
I am having trouble solving the following question.

I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable.

I want to show that $X \leq\_p 3Col$

My attempt is to look at the complement of G, and say that the complement of G shows us that the graph plus the edge is not 3-colorable if and only if the G - e is 3-colorable.

Does this make sense and is it correct?

# Answer
> 2 votes
Since 3COL is NP-hard and X is clearly in NP, by definition there is some many-one reduction from X to 3COL, though it may be awkward to state. There is a simple oracle reduction along the lines outlined in the other answer: remove each edge at a time, and check if the resulting graph is 3-colorable.

More interesting, perhaps, is a reduction going the other way, thus showing that X is NP-hard (and so NP-complete). Given a graph, we adjoin to it $K\_4$, the clique on 4 vertices. The new graph is a Yes instance of X iff the original graph is 3-colorable (exercise).

# Answer
> 1 votes
Try removing each edge and checking if the remainder of the graph is 3-colorable. In this way you have shown that $X \leq E. 3Col$ in which $E$ is the number of edges and therefore polynomial.

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


# Question
Title: Why are diploid (dominant/recessive) genes not used widely in genetic algorithms?
In most implementations of genetic algorithms, the focus is on crossover and mutation. But somehow, most of them leave out diploid (dominant/recessive) nature of genes. As far as my (limited) understanding goes dominant/recessive nature of genes is a very important factor in deciding the actual characteristics of an organism.

So my question is why is the diploid nature of genes left out of genetic algorithms in most implementation?

Is it because:

* it doesn't provide much benefit
* it adds unnecessary complexity to an otherwise simple algorithm
* it's difficult to implement

Or something else entirely?

# Answer
I don't *know* the actual reason, but it feels intuitive: let's think about what the diploid nature of genes does in RL. In essence it allows the recessive gene to remain in the gene pool even if it's currently at disadvantage to exist, and occasionally resurface, giving two things - first, it doesn't go extinct and can re-multiply if it becomes advantageous; and second, it ensures some population variety as you'll continuously have both phenotypes - a part of population that exhibits the gene and part that doesn't.

Both of these things can be achieved in simpler ways by the mutating/crossover engine - you can directly 'fetch' random good-performing items from 100000 generations ago (which nature usually can't); and you can keep multiple varied subpopulations while protecting the non-primary ones from extinction, which nature usualy doesn't do.
> 17 votes

# Answer
See Occam's Razor

> Among competing hypotheses, the one with the fewest assumptions should be selected. Also: Entities must not be multiplied beyond necessity.

If both hypotheses are equally good, choose the more simple version because the more complex version makes assumptions about something which you cannot be sure.

The question is, do diploid dominant and recessive genes provide more functionality that allows us to describe a richer hypothesis space?

* Could we do something that cannot be achieved through simple mutation? No. Mutation can create any new sequence.
* Could we do something with mutation that cannot be achieved through diploid dominant and recessive genes? Yes. Mutation allows any random new sequence while diploid genes would only recover something seen before and lost.

The only possible benefit left to explore is whether or not diploid genes would somehow be more efficient. It seems from their lack of use that this isn't the case. Mutations are usually small changes in an answer. The benefit of keeping a past, good answer around is small. It can easily pop up again.

Biology can be used as inspiration for computer models, but it rarely has the best answer. Biology generates solutions by chance and natural selection where DNA is concerned. Biology is also solving different problems with different raw materials and tools. Look at the way birds and bats fly. Why aren't our airplanes designed to move their wings up and down to take off or move higher? Because it would be horribly inefficient. Jet propulsion and helicopters are more suited to our needs. We can carry heavier payloads and travel at much faster speeds than birds and bats.
> 1 votes

---
Tags: machine-learning, genetic-algorithms
---


# Question
Title: On relation between FFT and polynomial multiplication
Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ of length $n$ vectors with entries bound by $M$ can also be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words?

Note that the converse is trivial since polynomial multiplication reduces to $FFT$.

# Answer
Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries.

$$M = |u\rangle\langle v| = \begin{bmatrix} u\_0 v\_0 & u\_1 v\_0 & u\_2 v\_0 & \dots & u\_{n-1} v\_0 \\ u\_0 v\_1 & u\_1 v\_1 & u\_2 v\_1 & \dots & u\_{n-1} v\_1 \\ u\_0 v\_2 & u\_1 v\_2 & u\_2 v\_2 & \dots & u\_{n-1} v\_2 \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ u\_0 v\_{n-1} & u\_1 v\_{n-1} & u\_2 v\_{n-1} & \dots & u\_{n-1} v\_{n-1} \\ \end{bmatrix}$$

The convolution $u \ast v$ of the two vectors is a vector of the values you get when summing along each anti-diagonal of this grid. For example:

$$(u \ast v)\_2 = \sum \begin{bmatrix} & & & & & & u\_{n-3} v\_0 & 0 & 0\\ & & & & & u\_{n-4} v\_1 \\ & & & & \ddots \\ & & & u\_2 v\_{n-5} & \\ & & u\_1 v\_{n-4} & & \\ u\_0 v\_{n-3} & & & & \\ 0 &\\ 0& \text{ } \end{bmatrix}$$

We can also think of the FFT of a vector as summing entries in a grid defined by multiplying two vectors' entries. The second vector is the sequence of roots of unity.

$$M = | u \rangle \langle e^{\tau i k/n} |\begin{bmatrix} u\_0 & u\_1 & u\_2 & \dots & u\_{n-1} \\ u\_0 e^{\tau/n} & u\_1 e^{\tau/n} & u\_2 e^{\tau/n} & \dots & u\_{n-1} e^{\tau/n} \\ u\_0 e^{2\tau/n} & u\_1 e^{2\tau/n} & u\_2 e^{2\tau/n} & \dots & u\_{n-1} e^{2\tau/n} \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ u\_0 e^{-\tau/n} & u\_1 e^{-\tau/n} & u\_2 e^{-\tau/n} & \dots & u\_{n-1} e^{-\tau/n} \end{bmatrix}$$

The Fourier transform doesn't track along the diagonals, though. Its row-hop is different from its column-hop. For the $k$'th entry of the output we go through each column $c$ and sum up the cell from that column and the $k \cdot c$'th row (wrapping around).

$$FFT(v)\_2 = \sum \begin{bmatrix} u\_0 \\ &&&&u\_4e^{\tau/7} \\ & u\_1 e^{2\tau/7} \\ &&&&&u\_5e^{3\tau/7} \\ & & u\_2 e^{4\tau/7} \\ &&&&&&u\_6e^{5\tau/7} \\ &&& u\_3 e^{6\tau/7} \\ \end{bmatrix}$$

So our question becomes: can we somehow re-arrange our vectors so that the each-stride sums $\sum u\_i v\_{k \cdot i}$ correspond to the each-diagonal sums $\sum u\_i v\_{k-i}$? Can we turn index-multiplication into index-adding?

We can, as long as we're operating in a context that allows for a logarithm. Suppose our vector size is $n$ and $g$ is a multiplicative generator for the integers modulo $n$. Then we can use the powers of $g$, i.e. the base-$g$ discrete logarithm, to define a permutation of the non-zero elements that does most of what we need. Our transformation goes roughly as follows:

* Define permuted vectors $a$ and $b$ so that $a\_k = u\_{g^k}$ and $b\_k = v\_{g^{k}}$.
* Compute the convolution $c = a \ast b$. So $c\_k = \sum\_{d=0}^{n-1} a\_d b\_{k-d} = \sum\_{d=0}^{n-1} u\_{g^d} v\_{g^{-k} \cdot g^d}$.
* Now un-permute $c$, and also un-permute the sum over $d$. $x\_{g^{-k}} = c\_{k}$ and $e=g^d$. So $x\_k = c\_{\log\_g k} = \sum\_{e=0}^{n-1} u\_{e} v\_{k \cdot e}$.

In other words: define a permutation $P$ based on when indices are reached when iteratively multiplying by $g$. Permute the input vector and the vector of $e^{\tau k /n}$ powers by $P$. Convolve. Unpermute by $P$. The result is the Fourier transform.

... Except that I've ignored one important issue. Our permutation doesn't work for $k=0$, because $g^k \mod n$ is never 0. Also, $g^0 = g^{n-1} = 1$. Fixing this hole requires special-casing the edges of the grid. But hopefully I've communicated the core idea of performing an FFT by delegating the heavy-lifting to a convolution and a permutation.

Note that, if you care about bit complexity instead of the number of arithmetic operations, computing the permutation may also be an obstacle. If multiplying by $g \pmod{n}$ costs $\log n$ time, and you don't have the permutation ahead of time, then overall the algorithm will still cost $O(n \log n)$.
> 6 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Two threads are waiting on a mutex. Which one is unblocked?
Suppose there are three threads A, B, C and thread A has acquired a mutex lock and it is processing. If threads B and C try to acquire the same mutex, they will be blocked according to the mutex lock concept. But once thread A completes, which of the threads will be unblocked? Is there any scheduling policy?

# Answer
> 4 votes
The short answer is "it depends".

If there is truly nothing to distinguish thread B from thread C, then the answer on most scheduler implementations will likely be either "could be B or C, and you can't predict which one in advance", or "the one which tried to acquire the mutex first" (i.e. first-come, first-served).

However, there may be something which distinguishes them in some way, and that's where it gets more interesting. In particular, if the implementation supports priority scheduling, one of the threads may have a higher priority than the other, in which case the higher-priority thread should be scheduled first.

Sometimes the programmer will decide that thread B should have a higher priority than thread C. Some schedulers assign higher priorities to tasks which have earlier deadlines, or periodic tasks with shorter periods (known as rate-monotonic scheduling).

In other circumstances, even if two threads have the same nominal priority, the scheduler may give one a higher effective priority than the other.

For example, in a non-realtime system, a scheduler may decide that one thread is more of a background task than the other (e.g. in a pre-emptive multitasking environment, a thread which seems to exhaust its quantum is probably a "background thread"), and so should have a lower effective priority than a more "interactive" thread. This is a common heuristic to make a system more responsive (or appear more responsive!) because interactive jobs are given priority.

Another common scenario is if one of the threads is already holding a priority-aware synchronisation object (say, a priority inheritance mutex or a priority ceiling mutex). In that case, the thread may have its effective priority raised to ensure that it releases the critical object more quickly.

---
Tags: operating-systems, synchronization, process-scheduling
---


# Question
Title: How to calculate the mergesort time complexity?
Recently while reading a book (Skienna) I came across the following statement:

> Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we would need to do this would be $\lceil\log\_{2}{n}\rceil$ and for each level we perform $O(n)$ work hence total time taken will be $O(n \log n)$

How to understand the above statement? Also, I am always confused about when to take ceil or floor. I am not a math major therefore it seems intimidating to me at first. I don't know about generating functions etc.

# Answer
Imagine that we have an array $A$ of size $n$. Mergesort splits this array into two equal halves and sorts them individually. So in context of the paragraph you have provided, each node corresponds to some chunk of the original array that we want to sort. We divide a node $A\[L,R\]$ to two nodes $A\[L,M\]$ and $A\[M+1,R\]$ with $M = \frac{L+R}{2}$

The splitting of a node $A\[L,R\]$ into two nodes takes $R-L+1$ time and then merging the two child nodes $A\[L,M\]$ and $A\[M+1,R\]$ again takes $A\[R-L+1\]$ time. Thus for every node, the number of operations the algorithm performs is equal to twice the size of the array corresponding to that node.

Thus we have that on any particular level if we have an array of size $k$, splitting and merging of the array can be done in $k + 2\times \frac{k}{2} = 2k$ operations.

Now note that we keep splitting the array till we have arrays of size $1$ since we can't split them further.

Draw a binary tree with the root node corresponding to the array $A\[1,N\]$ and with each node having two children corresponding to its left and right halves and recursively draw the structure for each child till we have arrays of size $1$. Denote each node by the size of the array that it corresponds to. We will get something that looks like this

(Taken from Khan Academy)

This is the recursion tree for merge sort.

The computation time spent by the algorithm on each of these nodes is simply two times the size of the array the node corresponds to. Therefore the total running time $S$ of mergesort is just the sum of all the sizes of the arrays that each node in the tree corresponds to i.e. $$S = 2 \sum\_{i=0}^k 2^i\frac{n}{2^i}$$

(How did we get this sum? There are $2^i$ nodes of size $\frac{n}{2^i}$ in the tree and it takes $2k$ time to finish computation on an array of size $k$)

Observe that when $i=k$, $\frac{n}{2^k} = 1 \implies n = 2^k \implies k = \lceil{\log n}\rceil$ Thus $S$ reduces to $$2 \sum\_{i=0}^{\lceil{\log n}\rceil} n = 2n\lceil{\log n}\rceil = \mathcal{O}(n\log n)$$
> 5 votes

# Answer
The response of Banach is quite precise, here is a description how to imagine merging sort as splitting sequence into halves and watching them as a binary tree.

Consider the sequence of $ n $ elements. First step divides the sequence into two groups of $ \frac{n}{2} $ elements. The second step divides those two groups into four groups of $ \frac{n}{4} $ elements. Third step divides these four groups into eight groups of $ \frac{n}{8} $ elements, and so on. If you look into this division as binary tree, it's of height $ \lceil \log{n} \rceil $. At each level of this tree, the cost of merge is $ 2n = O(n) $. Thus, the total cost is $ \lceil \log{n} \rceil O(n) = O(n \log{n}) $.
> 1 votes

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


# Question
Title: What is the significance of a Θ-bound on the running time of Mergesort?
While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it. Given:

> Mergesort takes $\Theta(n \log n)$ compares to sort $n$ elements.

What insight can we get from the above statement?

# Answer
> 3 votes
The insight you get from that statement is that the number of comparisons that merge sort uses behaves like a constant time $n\log n$. That's exactly what the statement means. In many cases the running time is captured by the number of comparisons, so the running time of merge sort behaves like a constant time $n\log n$. You can use this to estimate how long merge sort will take on a given number of elements (though you'll have to empirically estimate the constants involved). You can also use this estimate to compare merge sort to other algorithms, which might use asymptotically more comparisons.

# Answer
> 4 votes
> Mergesort takes $Θ(n \log n)$ compares to sort n elements \[in the worst case\].

Just unfold definitions. Step one:

> Mergesort takes $O(n \log n)$ and $\Omega(n \log n)$ compares to sort $n$ elements \[in the worst case\].

Step two (and three, I guess, since I recombine the unfolded definitions of $O$ and $\Omega$):

> For some $n\_0 \in \mathbb{N}$ and $a,b \in \mathbb{R}\_{\>0}$, the number of comparisons $C\_n$ Mergesort uses to sort $n$ elements \[in the worst case\] is bounded by $a \cdot n \log n \leq C\_n \leq b \cdot n \log n$ for all $n \leq n\_0$.

That's it. Would I call that insight? Hardly.

Adding the justification for why we ignore constant factors in the first place and that comparisons are a *dominant* operation in Mergesort, I guess the intended statement is something like this:

> If you implemented this Mergesort algorithm on a machine \[that fits the RAM model and can compare all input numbers in constant time\], its running-time cost would be roughly proportional to $n \log n$ for large enough $n$.

Note that neither the proportionality constant nor the sense of "roughly" and "large enough" are specified by the formal definitions. It may very well be that the algorithm is utterly unusable for all instances relevant to you. Hence, statements about algorithm performance using Landau notation are, for practical purposes, *mostly vacuous* -- formally speaking.

Implicitly, "we know" that "usually" constants are small and lower-order terms behave "nicely" (see e.g. here for a more precise result on Mergesort) so comparing Landau bounds is a somewhat meaningful criterion for choosing algorithms in practice. It has serious limitations, though, and it is important to keep those in mind.

---
Tags: algorithm-analysis, runtime-analysis, sorting, landau-notation
---


title: Reducing co3SAT to UNIQUE-SAT

text:
# Question
Title: Reducing co3SAT to UNIQUE-SAT
I am having trouble with this problem:

> Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq\_p UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique satisfying assignment for φ.

I am given a hint that for every 3CNF ψ, I should construct a CNF φ (in polytime) such that ψ is a NO input for 3SAT if and only if φ is a YES input for UNQ.

What I'm having problem with is constructing the CNF from a 3CNF. Isn't a 3CNF just a case of a CNF.

So, from what I understand, once I get a CNF φ that gives a yes for UNQ, then that corresponding 3CNF will give a NO for 3SAT. So somehow the truth assignments will work out in a way that both conditions are solved.

Can someone help me out?

# Answer
> 1 votes
You are right that a 3CNF is, in particular, a CNF. The hint you give suggests that you find a reduction that, given a 3CNF $\psi$ on $n$ variables, constructs a CNF $\varphi$ such that $N(\psi) = 0$ iff $N(\varphi) = 1$, where $N(\chi)$ is the number of satisfying assignments of $\chi$. I can give a stronger hint: the reduction constructs a 4CNF $\varphi$ on $n+1$ variables such that $N(\varphi) = N(\psi) + 1$.

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


title: heapify last 3 lines

text:
# Question
Title: heapify last 3 lines
I'm following http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6\_006F11\_lec04.pdf

Last 3 lines of `heapify` pseudocode are:

```
if largest =! i
    then exchange A[i] and A[largest]
    Max_Heapify(A, largest)

```

What is the aim of the last line? Since `largest` still holds value of largest leaf, which is now root, what would the recursive run achieve? Just an empty run, it seems.Max-heap is already built.

# Answer
> 2 votes
You are asking several related questions. I will only answer the first one. The heapify procedure gets an almost-heap $A$ and a node $i$. The heap property is satisfied for all nodes except for $i$. Heapify proceeds as follows:

1. Determine the largest child $j$ of $i$.
2. If $A\[i\] \geq A\[j\]$, the heap property is already satisfied.
3. Otherwise, exchange $A\[i\]$ and $A\[j\]$, and run heapify on $A$ and $j$.

After the exchange, the heap property is no longer violated for $i$, but might be violated for $j$. For this reason we have to call heapify recursively on the node $j$.

I suggest you try a few examples and see for yourself that sometimes the recursive call is necessary.

---
Tags: algorithms, sorting, heaps
---


# Question
Title: A criterion for the planar graph to have unique dual
I get stuck with the following two criteria both about the uniqueness of plane embeddings of a given planar graph. The first one says that a planar graph admits unique plane embedding iff it is a subdivision of 3-connected planar graph (e.g. from the book "Planar Graphs: Theory and Algorithms"). The second one (is from paper "The uniquely embeddable planar graphs") tells that uniqueness holds iff it is 3-connected planar plus some exclusions. I suppose they are based on two different definitions of equivalence. As for me I consider plane embeddings equivalence as an equivalence of the respective complexes. Indeed, each plane graph is in fact a triple $(V,E,F)$ where $F$ denotes set of faces. So the equivalence means that there is a map that translates the first complex to another one that keeps incidence between vetices and edges, edges and faces, vertices and faces.

My question is particularly under what definition the first criterion holds ? The proof that the book gives is a bit untransparent for me in that matter because the definition of uniqueness that it gives is not that strict.

# Answer
> 1 votes
First let me mention that the definition of being uniquely embeddable requires ANY graph isomorphism (e.g. just renaming symmetric vertices or any other automorphism permutation) to be (not necessary uniquely) extendable to topological (or combinatorial) one (see Diestel Graph Theory chapter about planar graphs for these definitions) in contrast to usual understanding of this definition that for any two planar embeddings there EXISTS some topological (or combinatorial) isomorphism. Difference between the topological and combinatorial isomorphism definitions is negligible for 2-connected planar graphs (see Diestel book). This particularly means that if we reflect or twist some symmetric graph (as done in the proof of necessity of the aforementioned criterion "subdivision of 3-connected planar graph if and only if condition to be embeddable" in the book "Planar Graphs: Theory and Algorithms") we get topologically non-isomorphic graph in general. Though $K\_{2,3}$ graph witnesses that the necessity proof here is wrong but the sufficiency is hold.

What I mean by complex-based isomorphism is just combinatorial one from Diestel book.

If we allow my unusual definition of uniqueness that any two embeddings are topologically isomorphic then there is an example of 2-connected non-subdivisions that are uniquely embeddable.

As for aforementioned paper "Uniquely embeddable planar graphs" the special definition which is given there is tougher (not robust to transposition of symmetric vertices) (but close to as Yuval assumed) than topological isomorphism according to its Theorem 3.5.

---
Tags: graphs, planar-graphs
---


title: For what $N$ does $2^N$ overflow?

text:
# Question
Title: For what $N$ does $2^N$ overflow?
Consider the following computation: 2^N (TWO TO THE POWER OF ‘N’, for Int. N\>0), being executed on a processor with 32 bit internal, user and ALU registers. The registers rightmost bit is bit 0 and the leftmost bit(the sign) is bit 31. WHAT is the SMALLEST value of ‘N’ that will cause the Overflow Status Flag (V) to be set?

Seems like the calculation should be as simple as plugging values in for N but I don't quite understand if there are any other components to take into account, any help is appreciated.

# Answer
You don't explain how $2^N$ is calculated, so I'm assuming you repeatedly multiply by 2 (or equivalently, you repeatedly add the number to itself, or shift it left). Here's how this process looks on a 4-bit signed register. You start with $0001$, the answer for $N=0$. Doubling it, we reach $0010$, the answer for $N=1$. Doubling again, we reach $0100$, the answer for $N=2$. Doubling again, overflow occurs (why?).

If the register was unsigned, we could double one more time, obtaining $1000$, the answer for $N=3$. Then we would overflow when doubling again (why?).

I believe you now have the tools to solve your own exercise. I won't verify your answer, so no point asking about it below.
> 1 votes

---
Tags: computer-architecture, shift-register
---


# Question
Title: Metaheuristic for NP-complete problem without exact algorithms other than brute-force
Computing Pure Nash Equilibria (PNE) is a Game Theory related problem. Deciding if there exists PNE in a given game has been shown to be NP-Complete (Gottlob et al.).

I want to design a metaheuristic algorithm that spits out a strategy that is either a PNE or an approximation of such. A metaheuristic algorithm would not guarantee a global optimal solution but might produce a sufficiently good solution. i.e. I want to view the problem as an optimization problem.

To the best of my efforts, I couldn't find any exact algorithms that solves the decision problem other than iterating over all possible strategies (brute-force).

I've tried implementing some basic metaheuristics (evolutionary algorithm, GSAT-like algorithm, ...) and find 'good' solutions in a 'timely' fashion. I put quotation marks because I can't prove if the algorithm is in fact good and/or fast (it uses metaheuristics). Hence the following question:

Is it useful to design metaheuristic algorithms for a problem like this when its performance can not be shown by comparing it to other (exact) algorithms?

# Answer
> 1 votes
Thanks to user AdrianN (see comments) I was able to find a paper which presents a Mixed 0-1 Linear Program to find all Pure Nash Equilibria in n-player games. The method is an exact method and the authors provide performance results.

Zhengtian Wu et al. “A Mixed 0-1 Linear Programming Approach to the Computation of All Pure-Strategy Nash Equilibria of a Finite n-Person Game in Normal Form”

This, however, only answers half the question. This question remains:

> Is it useful to design metaheuristic algorithms for a problem like this when its performance can not be shown by comparing it to other (exact) algorithms?

I realize this is a subjective question as, I think, D.W. tried to point out. I would like to answer this question myself by agreeing to D.W. and saying: It might be, it depends.

As a lot of references on metaheuristics will point out, it is important to be fully aware of the state-of-the-art before trying to design one. Metaheuristics tend to perform better than alternatives in certain (preferably interesting) situations, which should be shown by comparing them to said alternatives. Even if there is only a brute-force algorithm, it is likely that the brute-force algorithm will perform better in certain (interesting) situations and your metaheuristic will perform preferably much better in other situations. As D.W. said: "It depends what you're looking for, but sure, \[metaheuristics\] might be (useful), if you can accept the limitations."

---
Tags: np-complete, decision-problem, heuristics, game-theory
---


title: Running time of selection sort

text:
# Question
Title: Running time of selection sort
I wrote pseudocode for `Selection Sort`, but I'm not sure what is the running time of my algorithm, can you help me with that?

---

**My Pseudocode: Selection Sort(int a\[\], int n)**

Input: array of length $n$

Output: sorted array

```
for r=1 to n
    min=a[r]
    for i=r to n
        if (a[i]<min)
              min=a[i]
              k=i
              a[k]=a[r]
              a[r]=min

```

The external `for` takes $\Theta (n)$ but I'm not sure about the internal `for` because it depends on $r$.

# Answer
If the body of the outer loop gets executed $A$ times and the body of the inner loop gets executed $B$ times, then your algorithm runs in time $\Theta(A+B)$. After calculating $A$ and $B$, you will discover that $B$ grows faster than $A$, and so the running time of your algorithm is dominated by the number of times the body of the inner loop gets executed. It remains to calculate (or estimate) $A$ and $B$. You already mentioned that $A = n$. So all you need to complete the exercise is to calculate $B$, a task which I leave to you.
> 1 votes

# Answer
The inner loop will iterate $n - r + 1$ times for each iteration of the outer loop. To find the total runtime, we can sum this expression over $r = 1$ to $r = n$: \begin{align\*} \sum\_{r = 1}^{n} (n - r + 1) &= n^2 - \left(\sum\_{r = 1}^{n} r\right) + n \\ &= n^2 - \frac{n(n + 1)}{2} + n \\ &= \frac{1}{2}n^2 + \frac{1}{2}n \end{align\*} which is $\Theta(n^2)$.

To simplify the proof, we can note that the sequence $(n - r + 1)\_{r \in \[1, n\]}$ is just the sequence $1, 2, \ldots, n$, which you can see by substituting $r = 1$ and $r = n$ into $(n - r + 1)$. We know that this sum $\sum\_{i = 1}^{n} i$ equals $\frac{n(n + 1)}{2}$, giving the same result as the first method.
> 2 votes

---
Tags: algorithms, data-structures, runtime-analysis
---


# Question
Title: Runtime of a recursive algorithm to find a path in a DAG
About the following algorithm:

```
reach(Vertex s, Vertex t):
    if s = t return TRUE
    else
        for v in Adj(s) do
            if reach(v,t) return TRUE
        return FALSE

```

Why can we say that its runtime on a directed acyclic graph is $O(n!)$?

I can see why there are $n!$ different paths in the graph, is it because in each of those $n!$ paths, the loop will run at most $n$ times?

# Answer
> 1 votes
If you take each recursive call and trace it back to the original call `reach(s,t)` then you get some directed path starting at $s$. Hence the running time of the algorithm is $\Theta(N)$, where $N$ is the number of directed path starting at $s$ in which $t$ is not an internal vertex.

The number of paths of length $k$ (containing $k$ edges) is at most $(n-1)(n-2)\cdots(n-k)$, since each such path consists of distinct vertices different from $s$ (here we use the DAG property). Since paths have length between $0$ and $n-1$, we get that $$ N \leq \sum\_{k=0}^{n-1} (n-1)\cdots(n-k) = (n-1)! \sum\_{k=0}^{n-1} \frac{1}{k!} \leq e(n-1)!. $$ In particular, $N = O(n!)$.

---
Tags: algorithms, graphs, runtime-analysis
---


# Question
Title: In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?
I´ve been reading the paper "SOKOBAN and other motion planning problems" by Dorit Dor and Uri Zwick.

This is a link to the paper: Sokoban+ is pspace complete

In the paper, they proved that a problem called sokoban+ is pspace complete, they did it by reducing simulation of a turing machine with bounded tape to that problem.

sokoban+ is like sokoban, but the player can pull and push obstacles and all pieces are 2 x 1 rectangles (instead of 1 x 1 like in normal sokoban).

In figure 7, they show a drawing of the cell gadget, this represents a cell of a turing machine.

In the cell, the player enters, chosses a simbol (0 or 1) and if the player chooses correctly, he can go to a simbol gadgdet which will be open only if he has chosen the correct symbol. He goes through the symbol gadget, closing it, and then he goes to a gadget that forces the player to go to the next cell.

My question is, if in this cell and state the symbol of the tape has to change, how does the cell gadget registers that the symbol has changed?

Thanks for your help!

# Answer
> 2 votes
In the paper they created gadget called a gate. This gadget has two entrances, from one entrance the player can open the gate, the other entrance can be traversed only if the gate its on the open state.

In the cell gadget, there are $2k + 2$ gates where $k$ is the number of states the turing machine has and the other two gates correspond to the symbols ($0$ or $1$) that the tape of the turing machine can have.

When the player enters the cell gadget, he accesses a chamber corresponding to the state the turing machine is at that moment. In the chamber, there are two gates that correspond to the two possible symbols that the turing machine can have. There, the player can open one of the gates, the opened door has to coincide with the symbol that the turing machine has in that cell. He opens the gate by entering through one of the two entrances of the gate, he cannot access the other entrance from here. After opening the gate, he can traverse one of the two symbol gates, closing it.

After traversing the gate, the player reaches a different corridor, from that corridor he can access only the "state gates" that have the same symbol that the symbol gadget has (if they are opened), so he must have chosen to open the correct gate gadget in order to continue. Assuming that the player decided to open the correct state gadget, he can return to the same gate he opened before by entering through the second entrance of the gate (I thought that the player went to a different gate after that, the figure confused me).

After traversing the gate from this second entrance, the player closes the gate. From here he goes to a corridor that allows the player to open one of the symbols gadgets he visited previously (not a different one), and he will only be allowed to open the symbol gadget that the turing machine will write in that state and symbol configuration (if he decides not to open the symbol gate, he will be trapped if he decides to return to the gadget).

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