# Question
Title: Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A
> Suppose a problem A reduce to problem B and reduction is done in $O(n^2)$ time.
>
> If problem B is solved in $O(n^3)$ time then what about the time complexity of problem A?

Approach:

A is reduced to B . Here reduction is done at polynomial time. Here B is solved in polynomial time. So A should also be in polynomial time.

Now A can not be harder than B, So I think A can be $O(n^3)$ or $O(n^2)$. But logically if I reduced A to B and if B is $O(n^3)$ then it makes no sense for A to be $O(n^2)$, else why would I reduce it to higher complexity? So A is $O(n^3)$.

But my doubt is, we say while reduction that A can not be harder than B then how can we decide whether it is $O(n^2)$ or $O(n^3)$. Or is this argument only valid for P, NP classes of problem when I say A can not be harder than B or B must be at least as hard as A?

Answer given is "A is $O(n^3)$", but why can't it be $O(n^2)$ as "A can not be harder than B" but can be of equal complexity? Or is reducibility just an argument for complexity classes?

Explain if possible how reduction actually works, and why I couldn't apply it to my problem.

# Answer
> 3 votes
You have a reduction, but you don't know what size the new problem will be.

Say you have an instance of problem A of size n. And you can reduce it to an instance of problem B in time O (n^2). If you can reduce it to an instance of size $O(N^{1/2})$ then you are fine: You took O (N^2) for the reduction, and $O(N^{3/2})$ to solve the instance of B.

If you reduce the instance of problem A to an instance of size O (n log n) of problem B, then you will take O (n^3 log^3 n) to solve the instance of B.

So the time for the reduction and the time for solving B are not enough. You need to know the size of the new problem as well. (Of course you can't create an instance greater than O (n^2) in O (n^2) time, so the worst case is O (n^6), but it could be much better).

The answer that was given (O (n^3)) is definitely wrong. It doesn't follow from the information you were given.

# Answer
> 1 votes
Given an $O(n^2)$ reduction from $A$ to $B$ and an $O(n^3)$ algorithm for solving $B$, you can solve $A$ as follows:

* Given an instance of $A$ of size $n$, reduce it to an equivalence instance $B$ of size $N = O(n^2)$.
* Apply the algorithm for $B$, which runs in time $O(N^3) = O(n^6)$.

If we know more about the size of the $B$-instance produced by the $O(n^2)$ reduction, we might be able to tighten this analysis.

Also, all of this only gives an *upper* bound on the complexity of $A$. There might be other ways of solving $A$. Stated differently, the complexity of $A$ could be much smaller than $O(n^6)$.

---
Tags: reductions, p-vs-np
---


title: Getting N top scores from a matrix

text:
# Question
Title: Getting N top scores from a matrix
I start with a matrix, lets say 4x4. So I want the N top scores, with the sum of one element of each row. For example:

`M[4][4] = {
 (13, 8, 5, 3),
 (11, 9, 7, 4),
 ( 8, 6, 2, 1),
 ( 6, 5, 4, 1)
}`

So the top 6 scores of that matrix will be:

`top_scores = {
 (13, 11, 8, 6), // 38
 (13, 11, 8, 5), // 37
 (13, 11, 6, 6), // 36
 (13, 11, 8, 4), // 36
 (13, 9, 8, 6), // 36
 (13, 11, 6, 5), // 35
}`

What I want is to get the best scores directly, not calculating all the possible combinations and picking the top ones, because the matrix can be much bigger. I've tried to solve it with different approaches, but I failed in all of them.

# Answer
What you want to do is view your problem as a problem on a directed layered graph. This will allow you to solve the problem using algorithms for the $k$-th shortest paths problem.

In your example you would construct this graph:

The arcs with no label have weight zero.

Finding the $k$-th shortest paths from $s$ to $t$ will find the $k$ top scores according to your definition. There are many efficient algorithms for obtaining the $k$-th shortest paths, including a variation on Dijkstra's algorithm which is probably the easiest to implement.

PS. Some of these algorithms require that the weights of the arcs be non-negative. That can be easily achieved in your case, by adding a large enough constant to every weight, e.g., shifting every weight by +13 in your example. The result is equivalent, since all the paths from $s$ to $t$ contain the same number of arcs.
> 3 votes

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


# Question
Title: Counterexample for simple parity automaton reduction
I am dealing with deterministic parity automata and state space reduction (not minimization).

If we define $\equiv\_L$ to be the equivalence relation that sets two states equal iff starting from those states the automaton recognizes the same $\omega$-language, merging those states is in general not an operation that preserves language. The canonical example is a parity automaton with two states $q\_a, q\_b$ that moves to $q\_a$ whenever reading an $a$ and to $q\_b$ whenever reading a $b$. Giving both states a different parity yields a counter example.

Now what if we refine this relation so that $p \sim q$ is true iff $p \equiv\_L q$ and in addition the two states have to have the same color assigned to them. I feel like there has to be a counter example but I can't think of one. That is my question; what is a simple counter example that shows that merging states like this can alter the langauge?

(in case it is not clear what I mean by "merging": merging $p$ and $q$ means removing $q$ from the automaton and redirecting all transitions that would move into $q$ to target $p$ instead)

# Answer
After some thought, I found a counter example. It has four states and there might be one with only three states, but this one works too.

States 1, 2, and 3 are language equivalent. 1 and 3 also have the same color, so they can be merged. If we merge 3 into 1, this is the result:

In the original automaton, $(aab)^\omega$ has the run $(103)^\omega$ which only sees color 1. In the reduced automaton, $(aab)^\omega$ has the run $101(201)^\omega$, which also visits color 0 infinitely often.
> 1 votes

---
Tags: automata, omega-automata
---


# Question
Title: Is it decidable whether one language is polytime reducible to another?
Let $L\_1$ and $L\_2$ be two decision problems.

Is there an algorithm deciding whether $L\_1 \leq\_P L\_2$, that is, whether $L\_1$ is reducible to $L\_2$ in polynomial time?

# Answer
> 4 votes
I'm going to assume that your question is whether the language $$L = \\{\langle M\_1\rangle; \langle M\_2\rangle\mid L(M\_1)\leq\_\mathrm{p} L(M\_2)\\}$$ is decidable, where $\langle M\rangle$ is the description of Turing machine $M$ and $\leq\_\mathrm{p}$ denotes polynomial-time many-one reducibility.

**This language is undecidable.**

The only language that is many-one reducible to $\Sigma^\*$ is $\Sigma^\*$ itself. This is because a many-one reduction from $X$ to $\Sigma^\*$ must, by definition, map all "no" instances of $X$ to "no" instances of $\Sigma^\*$. However, $\Sigma^\*$ has no "no" instances, so the reduction can only exist if $X$ also has no "no" instances, i.e., if $X=\Sigma^\*$.

So, now let $Y$ be any Turing machine that accepts every input. The language $H=\\{\langle M\rangle\mid \langle M\rangle;\langle Y\rangle\in L\\}$ is clearly reducible to $L$. But $H$ is the language of Turing machines that accept every input, which is undecidable.

# Answer
> 1 votes
Let $L\_2$ be some easy to decide language. For example,

$$L\_2 = \\{ \omega : |\omega| \equiv 0 \mod 2 \\}$$

Then reducing instances of $L\_1$ to instances of $L\_2$ is as hard as deciding $L\_1$ itself, and your question boils down to:

> Given a description of a TM halting on every input, can you simulate it in polynomial time?

This is undecidable, which you can prove by the same argument as for the Halting problem.

---
Tags: complexity-theory
---


title: Rate Monotonic maximum execution time

text:
# Question
Title: Rate Monotonic maximum execution time
There are several periodic tasks (Period, Execution time),

e.g.:

* A = (20, 9)
* B = (12, 4)
* C = (4, X)

What methods/tests can be used for finding the maximum execution time X for which the task set will be schedulable by Rate Monotonic.

# Answer
> 1 votes
First of all, this problem is (weakly) NP-hard, see this paper by Ekberg and Yi, because it generalizes the problem of deciding which task sets are schedulable by Rate Monotonic.

However, assuming that your periods and execution times are integers, you can find the answer in pseudopolynomial time. Simply try all values of $X$ from $0$ to $p$, where $p$ is the period of the task with variable execution time. For each of these values, simulate the Rate Monotonic algorithm until time $\max\_{i=1}^n p\_i$ (that is, the largest period in your task set), to check that the task set is schedulable. The largest value of $X$ for which your task set results schedulable in the simulation will give you the answer.

You might be able to do somewhat better if you have more information about your tasks. For example, if the variable task is the one with largest period (not true in your example), I think the following will work:

Simply simulate the Rate Monotonic algorithm time step by time step, as if $X$ was infinitely large, and doing the following in addition:

1. Initialize a counter $K$ to zero.
2. At every time unit in which Rate Monotonic tells you to run the lowest priority task, you increase the counter $K$ by one.
3. After $p\_n$ time units (where $p\_n$ is the period of your lowest-priority task), stop the simulation.

The value of $K$ at the end of the simulation will be the largest possible value of $X$.

---
Tags: scheduling, process-scheduling, real-time
---


title: Minimum number of components in graph

text:
# Question
Title: Minimum number of components in graph
Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only one edge for 2 vertices. Correct?

# Answer
Yes, this is correct.

The easiest way to get to the result is to look at a graph with $v$ vertices and $0$ edges. It obviously has $v$ components. Adding an edge between two vertices $a$ and $b$ reduces the number of components if $a$ was not reachable from $b$ before adding the new edge.

Concerning "best" solution: Your approach yields an optimal solution, though it is only one way to do it - there are other ways (e.g. 26 components with either 2 or 3 vertices) that work equally well.
> 1 votes

# Answer
It looks like you are on the right track.

Let us use a bit of arithmetic or counting to find the minimum number of components.

Suppose that graph has $k$ connected components that have $v\_1, v\_2, \cdots, v\_k$ vertices and $e\_1, e\_2, \cdots, e\_k$ edges, respectively. Then we know $v\_1 + v\_2 + \cdots + v\_k = 69$ and $e\_1+e\_2+\cdots+e\_k=43$.

What is the relation between the number of vertices and the number of edges in each connected component? I would assume you have learned the fact that the latter must be at least the former minus one. If you have not learned it, it can be proved easily by mathematical induction on the number of vertices.

* The base case when there is only one vertex is clear.
* For the induction step where you add a new vertex, at least one new edge is needed to connect the new vertex to the existing vertices.

So $e\_i\ge v\_i-1$ for all $i$. If you sum all such inequalities, you will get $43\ge 69-k$, which means $k\ge26$.

I will let you check when the equality $k=26$ holds. Hint, it holds if and only if all inequalities are equalities. What does an equality here mean?
> 1 votes

---
Tags: graphs
---


# Question
Title: Hadamard transformation and measurement of one qubit
I also came across something, which is not completely understandable for me, so I ask here.

Given is a qubit in an entangled state, this is: $$ \frac{1}{\sqrt{2}}(\left|00\right\>-\left|11\right\>) $$ Now it is said that one could also apply the Hadamard transformation to the first bit and measure the first bit of the pair. That would mean so far: $$ \frac{1}{\sqrt{2}}(\left|H(0)0\right\>-\left|H(1)1\right\>) $$ My question is, where does the measurement start now?

Do I have to measure H (0) and H (1) and if so how does that work? For a single qubit, I know what a measurement looks like, say, we have $$ \frac{1}{\sqrt{2}}(\left|0\right\>-\left|1\right\>) $$ Then my qubit is 50% in state 0 and 50% in state 1

But how is that applied to the entangled particle?

Alternatively, I've multiplied this step out $$ \frac{1}{\sqrt{2}}(\left|H(0)0\right\>-\left|H(1)1\right\>) $$ $$ \frac{1}{2}(\left|00\right\>-\left|01\right\>+\left|10\right\>+\left|11\right\>) $$

Now my second question, what is the first bit of the entangled pair here? and how is the probability that the first bit is in $ \left|0\right\>$ calculated?

I hope you can help me a bit. Thank you!

# Answer
I'm not the best person to answer your question but I'll give it a try.

**1st Question:**

You do not yet make a measurement after applying the Hadamard Operator on your first qubit. Afterwards say you make a measurement on your 1st qubit, the state you'll end up with is:

$|\psi\>\_{post-measurement}$ = $1/\sqrt{p\_1(m)}$ $\sum\_{j} c\_{mj} |m\>\_1 |j\>\_2$

whereby $m$ is the measurement result of your 1st qubit (either 0 or 1) , $p\_1(m)$ is the probability of getting that result on your 1st qubit, $c\_{mj}$ the usual coefficient infront of your ket.

**2nd Question:**

This will answer how to get ${p\_1(m)}$. Write out the density matrix of $|\psi\>\_{pre-measurement}$, then trace out the 2nd qubit. Then apply bra-ket to your reduced density matrix:

${p\_1(m)}$ = $\<m|\_{1}$ $\rho\_{1} |m\>\_{1}$

Or equivalently:

${p\_1(m)}$ = $\sum\_{n}|\<m|\_1\<n|\_2 \sum\_{ij} c\_{ij} |i\>\_1|j\>\_2|^2$
> 1 votes

# Answer
After applying $H$ to the first qubit you have this state:

$$\frac{1}{2}(\left|00\right\>-\left|01\right\>+\left|10\right\>+\left|11\right\>)$$

You square the absolute values of the amplitudes to obtain probabilities of each of possible outcomes. In this case it is $1/4$ for each of the outcomes. Half of them has $\left|0\right\>$ for first qubit, so its sum probability is $1/2$.
> 1 votes

---
Tags: quantum-computing
---


# Question
Title: Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$
I am looking for an unrestricted grammar which generates the following language:

$\\{ a^1\\#a^2\\#a^3\\# \dots \\#a^k \mid k \>0 \\}$

That is, words like $a\\#aa\\#aaa\\#aaaa\\# \dots \\# \text{$k$ times '$a$'}$.

# Answer
If the grammar can be really unrestricted (meaning the variables are allowed to totally disappear) the design of the grammar is not complicated.

Start with left and right boundaries. Assume the string already is of the wanted form (with boundaries): $L a^1\\#a^2\\#\dots\\#a^k R$.

We can obtain the next string by adding one $a$ to each of the segments of $a$'s. We do this by having a symbol $W$ walking over the string from left to right while adding an $a$ after each $\\#$. Basically this uses the production rule $W\\#\to \\#aW$. Of course $W$ starts at the left $L$ and disappears at the right $R$. Of course when the walker starts an extra $a\\#$ at the left end must be generated.

A little tuning will make this work. At the end check that you did not forget to generate the string $a$.
> 1 votes

---
Tags: formal-languages, turing-machines, automata, formal-grammars
---


# Question
Title: Find a schedule with lowest total penalty
> Given a set of n jobs with \[arriving time, service duration time, penalty per unit of time\] find a schedule with lowest total penalty.

Notes:

* Arriving time is the time when objects aarivies to processing system.
* All objects can arrive at the same time
* Processor is able to process only one object at the same time
* Servicing time is the time required to process the object
* Penalty is calculated as (penalty * time spent in the system), i.e. departure time - arrival time

The easiest way to understand the problem is to imagin a loggistic company with a number of trucks that are waitings loading/unloading of the cargo. Trucks arraives at a given time and can wait on a parking. There is only one terminal that process loading and unloading. It's required to find an optimal schedule of processing.

Example of the input data:

```
t,tau,a
5,4,12
4,6,2
9,2,1
11,4,5
13,4,5
16,3,2

```

**The question here - which approach is required to solve this and similiar problems? I assume these algorithms are providing solutions close to a brute force.**

# Answer
This problem is called "minimization of total weighted flow time". It is very hard, especially when jobs cannot be preempted by the processor. Even when jobs can be preempted, it is NP-hard, so you cannot expect to have algorithms that construct optimal solutions efficiently.

If you are willing to accept non-optimal solutions, then there are efficient heuristics that find a solution of cost equal to $C$ times the optimal cost, for some large constant $C$, but they are not very practical (see the first link). A more practical approach might be to resort to a local search heuristic.
> 2 votes

---
Tags: algorithms, scheduling
---


# Question
Title: More efficient maximum bipartite matching
I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and papers, I've noticed that the Hungarian/Kuhn's algorithm tends to get mentioned a lot as a solution/approach. My sticking point is that it runs in $O(n^3)$ time and I've read in a few sources that there are better implementations.

My challenge is that these sources will often just mention these better approaches at the very end of a discussion and offer little insight into the implementation. So I guess my question is: are there indeed better than $O(n^3)$ runtimes? I think I remember coming across references that $O(nm\log n)$ and better exist, just having a hard time finding either reference implementations or more direction. Any help would be appreciated, especially examples as that's how I tend to grok things best after going through the theory.

# Answer
The Hungarian method can be implemented in time $O(mn + n^2 \log n)$. Details are found for example in Alexander Schrijver's book on Combinatorial Optimization, Chapter 17. For a more implementation-oriented guide to this version of the algorithm, have a look in Chapter 7 of Mehlhorn and Näher's book.

The running time is dominated by the time it takes to compute $n$ shortest paths via Dijkstra's algorithm. Each invocation of Dijkstra's algorithm costs $O(m + n \log n)$. (This assumes that Dijkstra's algorithm is implemented with Fibonacci heaps; the simpler implementation based on standard heaps would give $O(m \log n)$ for each invocation.)
> 1 votes

---
Tags: algorithms, graphs, reference-request, weighted-graphs, bipartite-matching
---


# Question
Title: Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.
...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.

---

I had this problem on my exam. From my understanding, the halting problem involves a program with some input, and that program will either output yes or no as output when comparing the input to the desired value. Then there's another program that must determine if the original program will ever halt based on the input given to it.

Thing is, I'm not sure if I understand the entire concept here. It's undecidable because we are unable to write a program that can determine if a program will always halt or stay in an infinite loop? Since it will always output as a "yes, it halted" even though the original program either halted or remained in an infinite loop.

So, I'm pretty new to all this, so bare with me. If the original question was asking me to "reduce" from the halting TM, do I apply the same principles? Or am I working out the problem differently? What is a reduction exactly, and what was I supposed to do here?

# Answer
Since you seem to want only a hint rather than a full solution, here is my attempt:

1. Undecidability of the Halting problem is one of the most famous impossibility results. It is not the most powerful one in the series (consider Rice's theorem) but it is a relatively simple in layman's terms and IMHO pretty impressive (in a bad way). The undecidability of the halting problem means that no matter which algorithm you try for the halting problem, it will fail on some inputs. It does not say that you can't predict if the program will halt for each (program, input data) pair, for example there are some very predictable programs. But it says that for every deciding program there will be some bad pair (possibly different for different programs, but even if you "combine" many such deciding programs, there still will be some bad cases).
2. Reduction is a general concept in math with several overlapping meanings. Here is one related famous joke about mathematicians:

> An engineer and a mathematician were shown into a kitchen, given an empty pan, and told to boil a pint of water. They both filled the pan with water, put it on the stove, and boiled it.
>
> The next day they were shown into the kitchen again, but this time given a pan full of water, and told to boil a pint of water. The engineer took the pan, put it on the stove, and boiled it. The mathematician took the pan and emptied it, thereby reducing it to a previously solved problem.

On a more serious note, reduction to the Halting problem is an argument that shows that a perfect anti-virus is impossible: the virus potentially can do its harm at any time during its whole runtime. So if the antivirus can catch all the viruses, it has to be able to solve the halting problem because I can put my virus "at the end" of any other program which the antivirus has to analyze first.

If you want a similar but I bit more formal argument take a look at wiki reduction of the Rice's theorem to the Halting problem

Generally in the CS-world reduction is mostly used in two ways:

1. To prove that some problem is undecidable by reducing it to some other well-known undecidable problem (and the Halting problem is often used here). In other words, if we could solve the problem X, we also must be able to solve the problem A which is known to be undecidable so X must be undecidable as well.
2. To prove some boundaries on complexity of some problem. For example, problem X is NP-complete because here is how to transform (reduce) an arbitrary input for a known NP-complete problem A into an input of the problem X and then how to transform the answer back.
> 1 votes

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


# Question
Title: Proving that a spanning tree of graph is not a minimum
Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w\_1 \le, w\_2 \le ... \le w\_{n-1}$ which are responing to the edges. $e\_1,e\_2,...,e\_{n-1}$.

Now I assume that there exists a spanning tree of $G$, let's call it $T'$, that has a path from node $u$ to node $v$ with all edges in a path from weight $\<w\_i$ for some $1 \le i \le n-1$. And I assume that the path from $u$ to $v$ in $T$ has at least one edge with weight $\ge w\_i$. I other words, the path from $u$ to $v$ in $T$ has an edge which is heavier than all the edges in the corresponding path in $T'$.

I need to prove formally that $T$ is not a MST.

What I've tried is to somehow find a tree which is of less wight than $T$ using Kruskal's algorithm, but I couldn't manage to do it.

# Answer
If you remove that edge you mentioned with weight $\geq w\_i$ from $T$, then the new $T$ has two components (because it's a tree). But one of the edges on the cheap path connecting $u$ and $v$ in $T'$ would reconnect these two components in $T$. And the substitution saved you a bit in terms of weight.
> 2 votes

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


title: First Order Logic : Predicates

text:
# Question
Title: First Order Logic : Predicates
I have a small problem with the first order logic, in particular, predicate logic

Let us take this sentence as an example:

```
Each teacher has given a form to each student.

```

From this sentence, can we have different reading?

This is my try to solve such problem, I did not know if this is the answer for such question:

```
Every Teacher has given a form to each Student.

(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Student then he has received a form from a teacher

Student(x)→(∃y)  Teacher(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Teacher then he has gave a from for all his students

Teacher(x)→(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a form then a teacher gave it to all student.

Form(x)→(∀y)  Employer(y)^(∃z)Teacher(z)^Give(x,y,z)

```

**EDIT**

To clarify my needs !

I think that the form is in logical dependency, either of student, either of teacher, or both, so we can find three other readings; so What are those reading? (Look at the begining to find what I did)

And How can I transform this sentence in predicate logic?

```
Each teacher has given a form to each student.

```

because it seems that

```
(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

```

is wrong.

# Answer
> 3 votes
> Each teacher has given a form to each student.

becomes

$$\forall x\forall y\[\mathrm{Teacher}(x)\wedge\mathrm{Student}(y)\to\exists z(\mathrm{Form}(z)\wedge\mathrm{Give}(x,y,z))\]$$ The main thing is to understand this table:

$\begin{eqnarray\*}\text{every } A\quad & \forall x(A(x)\to\dots) \\ \text{some } A\quad & \exists x(A(x)\wedge\dots) \end{eqnarray\*}$

---
Tags: logic, first-order-logic, propositional-logic
---


# Question
Title: Does the following operation makes the language regular?
I came across a question stated as $L = \\{wxwy \mid w \in \\{0,1\\}^\* , x,y \in\\{ 0,1\\}^\* \\}$ is regular and I have no problem understanding it.

However I thought what could happen if the language is modified to $L = \\{wxw \mid w \in \\{0,1\\}^+ , x \in\\{ 0,1\\}^\* \\}$.

In my opinion the above language is regular and it represent not what is seen by naked eyes, by that I mean the above language could be written as $L=(0+1)^\*$. Please correct me if I am wrong.

# Answer
> 3 votes
Interesting question. As Orlp pointed out, $L$ does not contain 01. So it cannot be $(0+1)^\*$.

In fact $L$ is not regular. Consider $M=L\cap L(0^+110^+1)$.

**Claim.** $M=\\{0^i110^i1\mid i\gt0\\}$.
Proof. Since $(0^i1)1(0^i1)\in M$ for $i\>0$, we have the "$\supseteq$". Now suppose $wxw=00^i110^j1$, $w\in\\{0,1\\}^+$, $x\in\\{ 0,1\\}^\*$, $i,j\ge0$. then $w$ must starts with 0 and ends with 1. Since there only three 1's in $wxw$, $w=00^i1$ and $x=1$. So $wxw=00^i1100^i1$, $i\ge0$. We have the "$\subseteq$".

There is a counting requirement for words in $M$. So, intuitively, $M$ cannot be regular. I will let you prove it rigorously using, for example, the pumping lemma for regular language.

Since $M$ is not regular and $0^+110^+1$ is regular, $L$ cannot be regular.

---
Tags: automata, regular-languages
---


# Question
Title: Minimizing sum of recursive pairwise sums
What is the best algorithm for this?

We are given an array of positive integers and we want to **minimize the total cost** of recursively adding together all the integers to one integer, **two integers at a time**. The cost of each addition is the sum of the two integers, and this sum adds up cumulatively. **After each addition, the two integers are removed from the array, but their sum is added, until only one value remains.**

I think I have figured out so far that the optimal solution is to add up the two smallest values in the array at every step (as the earlier the figure is used the more times it is included in the cumulative cost.) Perhaps there is another way to think about the problem, though.

Is there some mathematical fact that trivializes the solution perhaps?

**Example A:**

```
Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

```

**Example B:**

```
Input: [1, 1, 1, 1, 1]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 1, 1, 2]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 2, 2]
Adding 1 and 2 together (Cost 1+2 = 3)
State: [2, 3]
Adding 2 and 3 together (Cost 2+3 = 5)
State: [5]
Total cost: 2 + 2 + 3 + 5 = 12

```

(I made these examples up myself; let me know if the examples are not actually the optimal solutions, although I am pretty confident they are.)

# Answer
> 1 votes
This problem can be solved using a `min heap`. You have to construct a `min heap` initially with all the elements of array. Now you simply take the top element of this heap and add it to the next top element of heap. Then reinsert the sum obtained in the heap. Keep a variable to track the total cost. This will ensure that you are adding the minimum elements and the final cost is minimum. This is analogous to the problem of connecting n ropes with minimum cost.

---
Tags: algorithms, optimization
---


# Question
Title: Concentration bound for sum of dependent geometric random variable?
consider following persudocode:

```
i=0
while(i< k):
    uniformly pick u,v in V
    if(uv in E):
        remove uv form E;
        i++;

```

let $T$ be the number of iteration of this process, I know how to compute the expectation, but what is well bound for $P(|T -E\[T\]|)$? And is this process independent?

# Answer
No. It is not true. If the uniformly picked edge $u$ have more neighbors, the probability of edges which have $u$ is more than others! Hence, it's not uniform. Moreover, the number of neighbors of each node is changing over time, and this can be more unbiased over the time. Therefore, your selections are not independent of each other.

A solution to uniformly removing an edge can be indexing all edges from $1$ to $|E|$ (using an adjacency list for example) and then pick a random number from $1$ to $|E|$ as your uniformly picking edge in your graph. And do it for the new graph after removing the randomly picked edge.

**Hint:** As uniform version will remove an edge each time, the probability in this version can be an upper-bound for the $\mathbb{P}(|E\[T\]-T|)$ in your solution.
> 2 votes

---
Tags: randomized-algorithms, randomness, probabilistic-algorithms
---


# Question
Title: Why Does The Division Alorithim Need [Register Size] + 1 Iterations
Following this flow diagram for division hardware I made a program to "simulate" division on $N^+$.

```
# 4 bit version
def div(dividend, divisor)
  quotient = 0
  remainder = dividend
  divisor <<= 4

  for i in 1..5
    remainder -= divisor
    if remainder >= 0
      quotient <<= 1
      quotient |= 1
    else
      remainder += divisor
      quotient <<= 1
    end
    divisor >>= 1
  end

  return quotient
end

```

What I don't understand is why there needs to be an "extra" iteration of the loop. If the divisor is being shifted down the register by 1, and the register is say 64 bits, then it would take 64 iterations to clear the register. Or in my case 4. However without that extra step the algorithm does not produce the correct result. Why is that?

# Answer
"Why is that?"

Because `divisor <<= 4` means `original_divisor * (2**4)`, where I use `original_divisor` to denote the value of `divisor` when you began computing `div(dividend, divisor)`.

Every time you do `divisor >>= 1`, you divide that `divisor` by 2. So you will get `original_divisor * (2**3)`, `original_divisor * (2**2)`, `original_divisor * (2**1)`, `original_divisor * (2**0)`.

Notice there are 5 of them, corresponding to `original_divisor` times $2^4, 2^3, 2^2, 2^1, 2^0$ respectively or 16,8,4,2,1 respectively. You should have noticed how 4 is changed to 5 by now. There are 4 possible shifts to the left, by 4 bits, by 3 bits, by 2 bits and by 1 bit. There is also a non-shift, or shift by 0 bit.

What you have experienced is the most famous/infamous error in computer programming, off-by-one error or off-by-one errors. I must have made this error hundreds if not thousands of times.

Just in case you have not heard of the most famous joke in computer programming, here it is. "There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors." Or a shorter version, "There are two kinds of errors, off by one errors".
> 1 votes

---
Tags: algorithms, arithmetic, memory-hardware
---


title: Data Structures - Segment Trees

text:
# Question
Title: Data Structures - Segment Trees
I was learning about segment trees and came across this:

> We have an array arr\[0 . . . n-1\]. We should be able to
> 1 Find the sum of elements from index l to r where 0 \<= l \<= r \<= n-1
>
> 2 Change value of a specified element of the array to a new value x. We need to do arr\[i\] = x where 0 \<= i \<= n-1.
>
> A simple solution is to run a loop from l to r and calculate sum of elements in given range. To update a value, simply do arr\[i\] = x. The first operation takes O(n) time and second operation takes O(1) time.
>
> **Another solution is to create another array and store sum from start to i at the ith index in this array. Sum of a given range can now be calculated in O(1) time, but update operation takes O(n) time now. This works well if the number of query operations are large and very few updates.**

This is quoted from this web page.

The paragraph which I'm confused with is marked as bold. I think that the sum of a given range will only be calculated in O(1) time if l = 0, which is not always the case. Also, I can't seem to understand why did the update operation now takes O(n) time.

I hope it's just a small problem that can be easily explained. You can even explain the whole concept of segment trees here. I appreciate any help in any ways. Thanks.

# Answer
> 1 votes
Suppose you have created another array $S$ and stored sum from start to $i$ at $S\[i\]$. The sum of elements from index $l$ to $r$ inclusive is $S\[r\]-S\[l-1\]$ for $l\ge1$, which takes two lookups and one subtraction, or $S\[r\]$ for $l=0$, which takes one lookup. So it takes $O(1)$ time.

Suppose you set $arr\[k\]$ to a new value, where $k=n/3$. Then you have to update $S\[k\], S\[k+1\], \cdots, S\[n-1\]$, which are roughly $n-n/3=2n/3$ numbers. That is, it takes $O(n)$ time. You can figure out all other cases of $k$.

"You can even explain the whole concept of segment trees here." That is exactly the purpose of that article and its follow-ups. Try reading them. Follow the recommendations thereof.

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


# Question
Title: Tracing a polynomial algorithm for the problem of maximum-weight independent set
It should be a very easy question, but I am a little bit confused. According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using Dynamic Programming (the Algorithm is also explained on page 562 of the book Algorithm Design). Now, imagine that we want to trace the algorithm on a random graph like the figure below where the numbers in the balls show the weight.

I want to know, does it matter which node I am selecting as the root? Can you please guide me through the steps of this algorithm's tracing on this graph?

# Answer
> 1 votes
It won't matter which node you select as the root, in the sense that the algorithm will always find a maximum-weight independent set. The actual set of nodes selected by the algorithm might differ, if there are multiple maximum-weight solutions.

Let's say the root is the node with weight 2. Either it is in the optimal solution, or it isn't.

* If it is, then 7, 10, and 7 are not; the remaining tree only contains 4. Thus this solution has weight 2 + 4 = 6.
* If it is not, then the answer is the maximum-weight independent set on the forest in which the components are the subtrees with weight 7, 10, and (7, 4). Solving the problem recursively on the subtrees gives 7 + 10 + 7 = 24.

Since 24 \> 6, the answer is 24.

---
Tags: algorithms, graphs
---


title: What is an instruction bus?

text:
# Question
Title: What is an instruction bus?
I understand how the control, data and instruction buses form the system bus in von Neumann architecture but in the context of Harvard architecture, my textbook refers to "parallel data and instruction buses". The Wikipedia article for Harvard architecture also refers to an instruction bus: "TMS320 C55x processors, for one example, feature multiple parallel data buses (two write, three read) and one instruction bus."

What is an instruction bus? Based on its name, I'd guess it allows the processor to send instructions to components but in that case, how does it differ from a control bus?

# Answer
I believe you have one bus too many. Taking the image from teach-ict.com:

The diagram shows two buses with memory and one internal bus. One memory bus fetches instructions (stored in memory) to the Control Unit and data (stored in the same memory) to the ALU. The second bus is the Address Bus which says *which* memory to read or write (both for instructinos and data).

The Control Unit decodes the instruction and tells the ALU what to do (add, subtract, divide...). The Control Unit and the ALU together are called the CPU.

There is no separate Control Bus with the memory. The Control "Bus" is internal in the CPU.

In the Harvard Architecture there is physically separate memory for instructions and data. It means there are 4 buses, 2 data buses (1 for instructions and 1 for data) and two address buses (1 to address the instruction memory and 1 to address the data memory). The "Control Unit" in the diagram is the combined Control Unit and ALU from the previous diagram, the CPU. Any Conrol "Bus" is internal to that unit.

To summarize the answer: a Control Bus is internal to the CPU and should not be considered in discussing interactions with memory. There is no Control Bus with memory.

(Note: The Input and Output shown in the Von Neumann diagram should be ignored, or should be considered also present in the Harvard Architecture.)
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Finding shortest path between two nodes with a set of forbidden nodes
I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am allowed to visit **at most** one node from the set of forbidden nodes?

# Answer
Here is an answer by hbejgel from the StackOverflow:

> 1. Do a BFS starting from END - Whenever it reaches a Forbidden node, update its distance\_from\_end and don't add its neighbors to your queue. All forbidden nodes that are not visited should not have a valid distance\_from\_end.
> 2. Do the same as (1) but starting from START and updating distance\_from\_start
> 3. For all forbidden nodes take the one with minimal distance\_from\_start + distance\_from\_end. (note that this node may not exist since nodes can have non valid values in those fields and thus should be disconsidered)
> 4. Do a BFS from start to finish, disconsider all forbidden nodes except the one found in (3).
> 5. From the BFS performed in 4 you'll either:
>
> * find a path that does not cross any forbidden node which is shorter than the one that would cross it.
>     * find a path that does cross the forbidden node, in this case its length should be equal to (distance\_from\_start + distance\_from\_end) for that node.
>     * find no path at all, meaning that you did not find a node in step (3) and that after removing all forbidden nodes from the graph, you get a graph where START and END are in different partitions.
> 0 votes

# Answer
Create two directed copies of the graph, one without the forbidden nodes. Connect the outgoing edges of the "forbidden" nodes to the second graph.
> 0 votes

---
Tags: graphs, shortest-path
---


# Question
Title: Soundness and completeness w.r.t. programming languages
I'm studying programming languages (more specifically type systems) and came across a concept I couldn't quite wrap my head around: **soundness** and **completeness**.

I'm taking a class, and according to my instructor:

> Soundness is an analyzer's ability to prove the absence of errors. If a program is accepted by an analyzer, then the program is guaranteed to be safe.
>
> On the other hand, completeness is an analyzer's ability to prove the presence of errors. If a program is rejected, then that program has errors.

An example that I thought of is: If an analyzer is designed to accept all programs, does this mean the analyzer's system is **sound but incomplete**? I'm not quite sure if my reasoning is correct.

I've taken a look at other answers on this community:

Is there a relationship between “sound and complete” in logic and “type safety” in PLs? and

Example of Soundness & Completeness of Inference

but still am not quite sure how the logical concepts apply to type systems of programming languages.

Would anyone be kind enough to explain the differences?

Thank you.

# Answer
> 8 votes
I'll focus on your question:

> An example that I thought of is: If an analyzer is designed to accept all programs, does this mean the analyzer's system is sound but incomplete? I'm not quite sure if my reasoning is correct.

No, your reasoning is not correct. Let's take the definition your instructor gave you:

> Soundness: \[...\] If a program is accepted by an analyzer, then the program is guaranteed to be safe.

If a sound analyzer accepts every program, by definition every program must be safe. This is not the case -- so a sound analyzer must *not* accept everything.

> Completeness: \[...\] If a program is rejected, then that program has errors.

By definition, the always-accepting analyzer is complete: since it accepts everything, it rejects nothing, so all programs it rejects (i.e., none) have errors. This follows because from a false hypothesis ("a program is rejected") we can logically infer anything at all (including "the program has errors").

So, the always-accepting analyzer is complete, but not sound.

By contrast, an always-rejecting analyzer would be sound but not complete.

---

My preferred way to describe soundness and completeness is pretending we have an analyzer which, given an input program, returns "SAFE" (technically, accepts) or "NOT SAFE" (technically, rejects). A sound analyzer is one that can be trusted when it says "SAFE". A complete analyzer is one that can be trusted when it says "NOT SAFE".

A sound & complete analyzer can always be trusted, so (if it always halts) it is a decider for program safety. (Actually, by Rice's theorem, such a perfect analyzer can not exist.)

A sound but not complete analyzer, can be trusted only on "SAFE" answers. So, we can pretend it reliably answers "SAFE" or "DO NOT KNOW". (Indeed, "NOT SAFE" answers can not be trusted, so they actually mean "DO NOT KNOW")

A complete but not sound analyzer, can be trusted only on "NOT SAFE" answers. So, we can pretend it reliably answers "NOT SAFE" or "DO NOT KNOW". (Indeed, "SAFE" answers can not be trusted, so they actually mean "DO NOT KNOW")

# Answer
> 1 votes
I am really not an expert and just joined this site (I am a member of Stack Overflow C community for quite some time now), but this problem intrigues me and I tried to formulate an answer.

> Soundness is an analyzer's ability to prove the absence of errors. If a program is accepted by an analyzer, then the program is guaranteed to be safe.

Seeing the analyzer as a Turing machine, it may not halt on a program that has errors.

> On the other hand, completeness is an analyzer's ability to prove the presence of errors. If a program is rejected, then that program has errors.

Seeing the analyzer again as a Turing machine, and "reject" meaning the Turing machine halts (i.e. accepts), then it may not halt on a program without errors.

So if the analyzer is sound (accepts only true programs) *and* complete (rejects all false programs), then a program accepted by the analyzer is both `true` and `not false`. This means the Turing machine (analyzer) halts/decides on all input.

Note:

* "accept" means a Turing machine that has consumed its inputs and that halts.
* "reject" here also means a Turing machine that has consumed its inputs and that halts, but note we talk about an analyzer whose task is to detect invalid programs, so its task is to reject the program by saying "invalid" and then halt, i.e. accepts.

# Answer
> 0 votes
This definition of soundness and completeness could be helpful for you.

> *Soundness* is the property of only being able to prove "true" things.
>
> *Completeness* is the property of being able to prove all true things.

These are two properties of a logic system and about the ability of that system and not about any specific language or analyzer.

---
Tags: logic, programming-languages, type-theory
---


# Question
Title: Context free grammar to Chomsky's normal form
\begin{align\*} S&\to AACD\\ A&\to aAb\\ C&\to aC\mid a\\ D&\to aDa\mid bdb\mid\varepsilon \end{align\*}

I think that this grammar is infinite so it is not possible to convert it into cnf. Am I correct ?

# Answer
Every context-free grammar can be converted to Chomsky normal form. Also, note that grammars are by definition finite: a grammar might describe infinitely many strings, but the grammar itself is finite.
> 2 votes

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


# Question
Title: Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'
I'm working on solving an algorithm problem defined as follows (important parts in bold):

> Your task is to construct a building which will be a **pile of n cubes**. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.
>
> **You are given the total volume m** of the building. Being given m can you **find the number n of cubes** you will have to build?
>
> The parameter of the function findNb will be an integer m and you have to **return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n**.

Okay, so here's how I've been approaching the problem from a theoretical standpoint:

1. The summation `1^3 + 2^3 + ... + n^3` is equal to `[n(n+1)/2]^2 = m`.
2. Taking the square root of both sides yields `|n(n+1)/2| = sqrt(m)`. We can disregard the absolute value sign because `n` will always be positive. So `n(n+1)/2 = sqrt(m)`.
3. Therefore, `n(n+1) = 2*sqrt(m)`. This problem is essentially asking us to find two consecutive numbers, `n` and `n+1`, such that their product is equal to `2*sqrt(m)`.

**My code**

`def find_nb(m):
 target = 2*math.sqrt(m)
 for n in range(1, int(math.sqrt(target))+1):
 if n*(n+1) == target:
 return n
 return -1`

Here, I've defined `target` to be `2*sqrt(m)`. I'm looping from `n=1` to `n=sqrt(target)` (inclusive) because there is no point in going beyond the square root of the target when trying to find two numbers, `n` and `n+1`, whose product equals the target.

**The issue...**

This code runs into floating-point precision issues that are fairly consistent across all tests that failed. Here are some screenshots of tests that failed:

Notice that in all of these cases, the value I end up returning is 1 less than the value I stopped looping at. This is quite odd, and I'm not sure what could be causing this behavior.

If you compute the values using a good calculator, you'll find that it is indeed an issue of floating-point imprecision. I'm not sure how to deal with that. My code fails for 33/69 test cases.

**Alternative approach**

In yet another attempt, I tried doing the most straightforward solution possible: looping from `n=1` to `n=m` and calculating `[n(n+1)/2]^2` for each iteration, then comparing this to `m`. And, unsurprisingly, that solution is not accepted because it takes too long to execute for very large values of `m`!

So I tried looping from `n=1` to `n=sqrt(m)` to at least simplify the range of values I'm working with. But clearly, the exponentiation, division, and multiplication add up in terms of complexity, and thus this revised approach also results in an execution timeout.

**Question**

How am I supposed to solve this problem? Is it possible to solve this problem without introducing floating-point errors and without the algorithm taking an unreasonable amount of time for large input values?

# Answer
> 3 votes
Here is a Python function that is about as simple as possible and as fast as possible, assuming the input is valid.

```
def find_nb(m):
    return int(math.sqrt(2 * (math.sqrt(1.0 * m))))

```

If the input can be invalid, such as 10252519345963644753026 in the question, and the function should return None accordingly, the Python program can be the following.

```
def find_nb(m):
    # Use float since math.sqrt is wrong for big integers.
    target = int(math.sqrt(2 * (math.sqrt( 1.0 * m))))
    # or target = int(1.4142135623730951 * m ** 0.25)

    if (target * (target + 1) // 2) * (target * (target + 1) // 2) == m:
        return target
    else:
        return None

```

---

What is happening? According to Daniel Castle's comment, for $m\ge1$,

$$ n=\frac{-1+\sqrt{1+8\sqrt{m}}}{2}=\frac{-1}2+\sqrt{\frac14+2\sqrt{m}} $$ It can be checked easily that $$ n + 0.4 \< \sqrt{2\sqrt m} \< n + 0.5$$

That means, $n = \lfloor \sqrt{2\sqrt m} \rfloor$ with plenty of room to prevent an error.

# Answer
> -1 votes
Use the ideas of your first approach, but complete them with **binary search** in order to avoid floating point computations. Start with a large enough interval such as $\[a,b\] = \[0, \lceil m^{1/3} \rceil\]$ in which you search for the correct value of $n$ (if it exists). Test $n = \lfloor (a+b)/2 \rfloor$:

* If $n^2 (n+1)^2 \> 4m$ then you need to look in $\[a,n-1\]$; update $b$.
* If $n^2 (n+1)^2 \< 4m$ then you need to look in $\[n+1,b\]$; update $a$.
* If $n^2(n+1)^2=4m$ you are done.

---
Tags: algorithms, optimization, floating-point
---


# Question
Title: Why not do these checks on the number of clauses in 3-SAT?
I've been writing a 3-SAT solver for fun and comparing its performance against the solver pycosat. My solver vastly outperforms pycosat in two special cases, where I solve by doing simple, obvious checks, which pycosat doesn't seem to do (based on the time it takes to solve these cases).

I presumed that these checks would be known and commonly incorporated into solvers. Is that the case? Why would a solver not bother doing them?

The checks are based on the following:

Let $\phi$ be a CNF with $n$ variables and $m$ disjunctions, where each disjunction has exactly 3 distinct variables and no two disjunctions have the same literals.

1) If $m \< 8$, then $\phi$ is satisfiable.

2) If $m \> 7\* \binom{n}{3}$, then $\phi$ is unsatisfiable. ($\binom{n}{k}$ is the binomial coefficient.)

The proof is simple but tedious. I can provide it if needed.

# Answer
There's no real reason not to do your checks given that they are computationally tractable, but there's very little point in doing them either. Your checks make determining the satisfiability of easy random 3-SAT instances easier. SAT solver authors are interested in algorithms that make *hard* SAT instances easier.

For random 3-SAT, the hardest instances are known to be near the phase transition point where instances on one side are almost always satisfiable and instances on the other are almost always unsatisfiable. That transition point has been observed empirically to be when the ratio of the number of clauses and the number of variables is around 4.26. Your checks would never be helpful with such instances.
> 1 votes

---
Tags: satisfiability, 3-sat, sat-solvers
---


title: MST Proof (Kleinburg & Tordos)

text:
# Question
Title: MST Proof (Kleinburg & Tordos)
Consider the Minimum Spanning Tree Problem on an undirected graph G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all be different. If the costs are not all distinct, there can in general be many distinct minimum-cost solutions. Suppose we are given a spanning tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some minimum-cost spanning tree in G. Can we conclude that T itself must be a minimum-cost spanning tree in G? Give a proof or a counterexample with explanation.

# Answer
> 0 votes
Here is the simplest counterexample. The edge set $\\{10, 12\\}$ is not a minimum spanning tree (MST). However, edge 10 is in the edge set $\\{10, 02\\}$, an MST. Edge 12 is in the edge set $\\{12, 02\\}$, an MST.

---

Note that there are two edges of equal weight in the above counterexample.

(**Question.**) What if no edges have the same weight?

# Answer
> 0 votes
Consider the following non-minimum spanning tree.

```
           1
 +-------------------+
 |                   |
 |                   |
 |                   |
2|←                 →|2
 |                   |
 |                   |
 |         ↓         |
 +-------------------+
           1

```

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


# Question
Title: Is it possible for a hash table's load factor to exceed 100%?
Using probing, is it possible for for a hash table's load factor to exceed 100%? I don't too much about Hash Tables. Is this possible?

# Answer
The load factor of a hash table is defined as:

$$\lambda = \frac{n}{k}$$

where $n$ is the number of items stored in the table and $k$ is the number of buckets. So the load factor is greater than 1 if there are more entries than buckets.

Storing more than one entry in a bucket is very common. The most familiar example is separate chaining (e.g. a linked list of entries in the bucket), used for in-memory hash tables.

For disk-based hash tables (as found in database servers or some file systems or file management systems), a "bucket" is typically a page (possibly a disk page or a virtual memory page) in size, so for typical use cases, you can easily fit more than one item into it. A scheme such as extendible hashing is typically used to manage buckets in a way that minimises disk traffic.
> 2 votes

# Answer
In theory, yes. As far as were told in practice, no (**SHORT ANSWER AT BOTTOM**).

A hash table's load factor is defined, as Pseudonym states, as:

$LF = \frac{elements}{array.length}$.

That is, $LF$ is the number of elements present in the array by the length of the array itself.

But for any person who may stumble across this and have no idea what Hash Tables are, perhaps we should be clear exactly what a Hash Table entails...

*Hash Tables* are nothing more than arrays that store elements.

We usually have an array of length $n$. Each array index will usually hold elements of some type. When we add elements to the array, we determine where they will go based on the hashCode() of that element. We take the hashCode() and mod it by the length of the array. Whatever this number is will be the index we store our element in.

Now one of the major problems of hash codes is that there are a finite amount of hash codes, so we're bound to have two objects "collide" - that is, both objects will have the same hash code and end up at the same array index. In this case, we develop "collision resolution" strategies to counteract this. These strategies are, but not limited to:

**COLLISION RESOLUTION STRATEGIES** -

1. **External/separate chaining** : Every array slot can hold a List, traditionally a Linked List of elements of some given type. This allows us to store/add multiple elements with the same hash code in the same index by adding to the List present in that index. You can imagine each List of elements as a *chain* of elements, hence the terminology.
2. **Probing (Linear)** : In this strategy, we restrict our Hash Tables to hold only one element at any given index. If we find that the initial index provided by element.hashCode % array.length is full, we iterate through the array (modding the number by array.length each time, to restrict us to the array indices only) until we find an empty spot and place our element there.
3. **Probing (Quadratic)** : Similar to linear probing, except instead of iterating linearly over the array until we find an empty spot, we add exponentially to the initial given index (1, 4, 9, etc...) and mod the number by array.length, and find an empty spot that way.

Now, how does this affect Load Factor? Every time we add an element successfully, we increase the load factor because the number of elements goes up by one.

Now, according to a resource by University of Texas from one of their Data Structure classes, one can have the Load Factor exceed 1 (exceed one hundred percent). Imagine an array of *length* 5 where each index holds a list of five elements. Clearly:

$LF = \frac{25}{5} = 5$

I only just found out it's okay to have the load factor exceed one in this case as performance apparently does not decrease. You learn something new everyday!

**However**, as we were taught in our data structures course, we focused on the implications of load factor as it pertains to probing collision resolution strategies.

It makes sense that the more we tend towards 1 with LF, the slower our retrieval, addition, and removal times may be. Consider that for any given element we're trying to remove, we are not guaranteed that that element is in the spot we've initially calculated - if not, we need to potentially iterate through the entire array to find/remove the element, which is of course O(n).

In order to counteract this, we traditionally institute some bound on how large the Load Factor can be. I've seen it be .75, but it can be lower. It's mostly always above 1/2, at least.

If the load factor increases past a certain bound, this triggers an immediate resizing of the array (usually doubling the size), and all elements in the array are then re-added to the new array.

**NOTE:** Resizing involves recalculating the initial indexes for all elements all over again! Remember our formula for calculating initial index is:

$initIndex = element.hashCode() % array.length$.

If the array length as doubled, you can best be assured the initIndex will be changed.

You can convince yourself that adding (which is the only way to increase LF, and therefore trigger resizing) is in the worst case $O(n^{2})$, as you will need to potentially recalculate locations of all elements and then go through the process of trying to add one element.

One edge case I did see when I had to implement a HashMap for a homework assignment (where the resolution strategy was *linear probing*) was that it is indeed possible to have *every* array index be *filled*, yet have the LF be within the bounds? How is this possible?

One nuance of linear probing involves our removal process. When we remove an element, we don't actually remove it from the hash table. What we do is we *mark* it as removed, and then move on. If we add to the same index later on and we find a removed element, we overwrite it.

Removing an element decreases size by one, and decreases LF appropriately. But what you can do is you can have a mixture of removed elements and regular elements in your array, such that no index is TRULY empty, and still have the LF be less than the bound you've established. I myself didn't even think it was possible, but lo and behold, after writing the diagrams down on paper, I realized this was an edge case I had not foreseen.

---

**SHORT ANSWER (THANKS FOR READING)**

It's not really possible with a probing strategy to exceed LF = 1 given that you'll have only one element in every spot at the absolute maximum.

If you implement the Hash Table at any point, you'll probably be told to institute some bound where if LF = .75 or greater, you need to trigger resizing. This necessarily implies that some array indices will be empty or have removed elements. With this in mind, it is clear to see that unless you implement the Hash Table incorrectly, you'll never really reach an LF of 1.

The reason we do this is to keep the Hash Table's super-fast retrieval/search times (usually O(1) in the best case). Having an LF that continuously increases decreases the effectiveness of searching processes, and forces us to increase our search time to an O(n) process.

Hopefully this helps! Sorry for the long answer. If you want, I can cut out portions of it deemed unnecessary to the answer, but I wanted to make sure Hash Tables were explained (somewhat) well.
> 0 votes

---
Tags: hash-tables
---


# Question
Title: Calculate the number of cycles of a Cactus graph?
Considering a cactus graph $G = (V, E)$, defined as:

> A graph is a cactus if every edge is part of at most one cycle.

There is a way to calculate the number of cycles in this graph given only $n= |V|$ and $m = |E|$?

I did some examples before posting this, but now I think I got somewhere. If $G$ is connected, $m = n-1$ results that $G$ is a tree (we can not have less as $G$ will be disconnected). If $m \> n-1$, then the number of cycles is equal to $m - n + 1$.

If $G$ is not connected, then we can take each connected component $C\_{1}, ..., C\_{k}$ and deal with them as a separated cactus graphs and then the number of cycles in the original graph is $\sum\_{i=1}^{k} cycles(C\_{i})$, where $cycles(H)$ is the function described above and $H$ a connected cactus graph.

Intuitively, I think that is because each edge added create exactly one cycle, as adding more than one cycle goes against the definition of the cactus. And to add a edge without adding a cycle you must connect a vertex that was previous isolated, not changing $m - n + 1$.

But I am not sure how to formalize this now.

# Answer
If a graph is a cactus, then the number of cycles is $c = m-n+x$, where $x$ is the number of connected components and $c$ is the number of cycles.

The proof is by induction on the number of edges. If $m = 0$, then the graph contains no cycles, and furthermore $n = x$, and so $m-n+x = 0$.

Suppose now that $m \> 0$, and remove an arbitrary edge $(u,v)$. There are two cases:

* The edge was not on a cycle. In that case, removing the edge increases the number of connected components by one: otherwise, $u,v$ are connected by some simple path not involving $(u,v)$, which together with $u,v$ would form a cycle. Therefore by the induction hypothesis, the number of cycles in the new graph is $(m-1)-n+(x+1) = m - n + x$. Since the original graph has the same number of cycles by assumption, this proves the induction hypothesis in this case.
* The edge was part of a unique cycle. In this case, removing the edge does not increase the number of connected components, since $u,v$ are connected by the rest of the cycle. By the induction hypothesis, the new graph has $(m-1)-n+x = m-n+x-1$ cycles. The original graph has one more cycle, for a total of $m-n+x$ cycles, proving the induction hypothesis in this case as well.
> 5 votes

# Answer
Another proof of the statement from Yuval Filmus' answer.

Using the algebraic topology based techniques that I briefly describe in this answer, we can reason as follows.

$n-m$ is the Euler characteristic (for any graph). A connected component of a cactus is either a tree, in which case its Euler characteristic is $1$, or it's cycle with some trees hanging off it, in which case its Euler characteristic is $0$. The Euler characteristic for the whole graph is the sum of the Euler characteristic of the components. Therefore the Euler characteristic of the whole graph is the number of connected components minus the number of cycles, i.e. $x-c=n-m$ using the variables from Yuval Filmus' answer.
> 2 votes

---
Tags: graphs
---


title: Two's complement general formula

text:
# Question
Title: Two's complement general formula
In college, we've seen some general formulas to compute the decimal value a of a binary representation $a\_{N-1} \dots a\_2 a\_1 a\_0$ in two's complement, $N$ being the number of bits. For $a \ge 0$ we've seen $a= \sum\_{i=0}^{N-2} a\_i 2^i$, which seems correct to me if I work it out. But for $a \< 0$ our book says $a=-2^{N-1}+\sum\_{i=0}^{N-2} a\_i 2^i$ and this is where I go wrong.

Can someone explain with an example why this is correct or which formula is right?

# Answer
Let $a\_{N-1} \cdots a\_0$ be the two's complement representation of the number $a$. The more general formula is: $$a = -a\_{N-1}2^{N-1} + \sum\_{i=0}^{N-2} a\_i 2^i$$ (I am sure you can figure out how your formulas can be derived from this one.)

Why does this hold? For $a \ge 0$, $a\_{N - 1} = 0$ and then the value of $a$ is simply the value of the binary representation $a\_{N-2} \cdots a\_0$. For $a \< 0$, on the other hand, let $b = -a \ge 0$ have binary representation $b\_{N-1} \cdots b\_0$. Then $$\sum\_{i=0}^{N-1} a\_i 2^i = \sum\_{i=0}^{N-1} (1-b\_i) 2^i + 1 = \sum\_{i=0}^{N-1} 2^i - \sum\_{i=0}^{N-1} b\_i 2^i + 1 = 2^N - b$$ since the two's complement is defined as the complement of the representation $b\_{N-1} \cdots b\_0$, plus one, and $\sum\_{i=0}^{N-1}2^i = 2^N - 1$. Since $a$ is negative, $a\_{N-1} = 1$ and then: $$a = -b = -2^N + \sum\_{i=0}^{N-1} a\_i 2^i = -2^N + 2^{N-1} + \sum\_{i=0}^{N-2} a\_i 2^i = -2^{N-1} + \sum\_{i=0}^{N-2} a\_i 2^i $$

---

I have refrained from giving an explicit example as you had asked; I believe explaining why the formula works in the first place is far more instructive.
> 4 votes

---
Tags: binary, numeral-representations
---


title: Grammar with same variables

text:
# Question
Title: Grammar with same variables
If a grammar has the same variable multiple times, is it the same as adding a $\mid$ between them? For example, is

$$\begin{align\*}S &\to bB \\ S &\to \varepsilon \\ B &\to cB \\ B &\to \varepsilon \end{align\*}$$

equal to the following?

$$\begin{align\*}S &\to bB \mid \varepsilon \\ B &\to cB \mid \varepsilon \\ \end{align\*}$$

# Answer
Yes. (you are right, the "$\mid$" sign is a classical notation for the alternative rules for a variable.)
> 0 votes

---
Tags: formal-grammars
---


# Question
Title: The difference between compiler and interpreter
I am reading dis, It reads:

> The dis module supports the analysis of CPython bytecode by disassembling it. The CPython bytecode which this module takes as an input is defined in the file Include/opcode.h and used by the **compiler** and the **interpreter**.

In wikipedia

> In computer science, an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.
>
> A compiler is computer software that transforms computer code written in one programming language (the source language) into another programming language (the target language).

I really unable to figure out the difference.

# Answer
> 6 votes
In basic terms the difference between an interpreter and a compiler is the point at which a source text is actually executed.

An interpreter interprets a language by reading the text or source code and then performing computations as it processes the text to execute the text. So as the interpreter is reading the source of the program, the program runs or executes as the interpreter reads lines of code and performs those actions.

A compiler compiles a language by reading the text or source and transforms the source code into another form which is typically machine code.

To make things a bit more complicated you will see that some interpreters have a Just In Time (JIT) compiler component to them. So the process then is the interpreter reads the source code and converts it to an intermediate, more machine friendly, form which is then fed to a JIT compiler which creates a machine code which is then executed by the target hardware. Most interpreters of this form have a Virtual Machine which is hardware independent that uses a JIT compiler to target the actual hardware when the program is executing. The Virtual Machine is hardware independent but the JIT compiler must be tailored to the particular hardware. The JIT compiler compiles the Virtual Machine code or instructions into the target hardware machine code which is then executed by the hardware.

And by the way this kind of Virtual Machine is different from the virtual machine used with Docker and other types of containers which has hardware virtual machine support. The Virtual Machine used by these interpreters is an application which emulates some abstract hardware.

For examples of this kind of Virtual Machine look to the Java Virtual Machine. Or the Python Virtual Machine. See Java “Virtual Machine” vs. Python “Interpreter” parlance?.

And this document, Python (2.5) Virtual Machine: a guided tour has some of the gritty details about the Python Virtual Machine though an older version of Python.

A compiler will normally compile the source text to actual hardware machine language. So the output of a compiler depends on the actual target hardware. The machine code of a compiler that targets an x86 architecture is different from one that targets an ARM architecture.

Using a compiler will require additional software tools as the process for a compiler is generally something like the following:

* create the source code file or files
* compile the source code file or files to generate one or more object code files
* link the object code files with various libraries to generate an executable
* run the executable application

Using an interpreter will be a simpler procedure something like the following:

* create the source code file or files
* execute the interpreter program, specifying the source code file

The C programming language is normally a compiled language using a compiler. The python programming language is normally an interpreted language using an interpreter.

However there is nothing to stop someone from writing a compiler for what is normally an interpreted language nor writing an interpreter for what is normally a compiled language. And you can see examples of this all over the internet.

To make things even a bit more complicated in the naming of things, there are applications called compilers that translates one programming language into another.

A classic example is the first C++ compilers which would transform C++ source code into C source code and then compile the C source code into machine language. It's not done like that anymore and the C++ language was a subset of modern C++ (C++11/17) but it worked for a proof of concept.

I have also seen a translator that would transform C source code into JavaScript.

# Answer
> 0 votes
**Compiler:**

* It translates program written in one language(source language) into an equivalent program in another language(target language).

**Interpreter:**

* It performs the operations $implied$ by the source program. Operations are usually implied in form of intermediate code representation.

---
Tags: programming-languages, compilers
---


# Question
Title: Can a RE language be reduced to a non-RE language?
In our lecture notes about many-one reduction we showed that the following statements hold: $$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$ $$(I)\space L' \in RE \implies L\in RE$$ $$(II)\space L \notin RE \implies L'\notin RE$$

Now I was wondering if this would also be true if you'd reverse these statements i.e. $$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$ $$(I)\space L \in RE \implies L'\in RE$$ $$(II)\space L' \notin RE \implies L\notin RE$$

# Answer
First, note that if $p$ and $q$ are any two statements, the implication $p\implies q$ is logically equivalent to $(\lnot q)\implies(\lnot p)$. This equivalence is known as "taking the contrapositive".

Because of this, your statements $(I)$ and $(II)$ are equivalent. That is, the first two properties you mention are equivalent (and they follow from $L \leq\_m L'$). The second two properties are also equivalent. Your question then becomes:

$(I)$ If $L \leq\_m L'$ and $L \in RE$, can we conclude $L' \not\in RE$ ?

In general, no, we can not conclude that.

For instance, take $L=\\{0\\}$. This is a decidable language (we can test the input string against $0$, and accept iff they are equal), so it is also a $RE$ language.

Now, note that we can many-one reduce $L$ to absolutely any set $L'$ except the empty set and the full set ($\Sigma^\*$). This includes non-$RE$ sets like the complement of the halting problem.

Indeed, to find a reduction, take any word $w\in L'$ and any other word $x\notin L'$. Then, the reduction function behaves as follows: it tests its input, if it is equal to $0$, then it returns $w$, otherwise it return $x$.

By construction, this is a reduction, so $L \leq\_m L'$, even if $L\in RE$ and $L'\notin RE$.
> 1 votes

# Answer
The first statement:

$$(I)\space L' \in RE \implies L\in RE$$

says if L' is an element of RE, then L is an element of RE. This is true because L is contained in L'.

The second statement:

$$(II)\space L \notin RE \implies L'\notin RE$$

syas that if L is not an element of RE, then L' cannot be an element of RE. This is true because L is contained in L' and if the property does not hold for the smaller set, then it can't be true for the larger set it is contained in.

Your statement I:

$$(I)\space L \in RE \implies L'\in RE$$

says that if the smaller set is in RE, then the larger set is also in RE. That does not need to be true. There can be elements of the larger set for which the propety does not hold.

Your second statement is true, though:

$$(II)\space L' \notin RE \implies L\notin RE$$

and says that if the larger set is not in RE, then the smaller set cannot be in RE.
> 0 votes

---
Tags: computability, reductions
---


title: AVL Rotations Abbreviations

text:
# Question
Title: AVL Rotations Abbreviations
I read that there are 4 types of rotations:

* Left rotation
* Right rotation
* Left-Right rotation
* Right-Left rotation

What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to rebalance AVL trees?

# Answer
Please skip that article at tutorialspoint. Instead, read this article at GeekforGeeks, which is much better. You may want to check my answer to another question.

The common abbreviations for Left rotation, Right rotation, Left-Right rotation, Right-Left rotation are L, R, LR and RL respectively, as expected. These rotations can be applied to all kinds of binary search trees. For example, they are applicable to red-black trees, too.

Please note that there is minor confusion about the terminologies. However, I would say that more than 9 out of 10 times, you will encounter the mainstream terminologies as explained in that GeekForGeeks article.

A common reference to rebalance AVL trees is the Wikipedia entry on AVL trees.
> 2 votes

---
Tags: terminology, reference-request, binary-trees, avl-trees
---


# Question
Title: What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?
The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace `d[u] + weight(u,v) < d[v]` with `d[u] + weight(u,v) <= d[v]`. What would be an example of the algorithm working incorrectly with that replacement?

```
def dijkstraShortestPath(G,s,t):
  d[v] = Infinity for all v in G.vertices
  d[s] = 0
  unsureVertices = G.vertices
  while len(unsureVertices) > 0:
    u = a vertex in unsureVertices so that d[u] is minimized
    if d[u] == Infinity:
      break
    for v in u.getOutNeighbors(): //all v are in unsureVertices
       if d[u] + weight(u,v) < d[v]:
         d[v] = d[u] + weight(u,v)
         v.parent = u
    unsureVertices.remove(u)
  if d[t] == Infinity:
    return "Can't reach t from s!"
  path = []
  current = t
  while current!= s:
  path.append(current)
  current = current.parent
  path.append(current)
  path.reverse()
  return path

```

# Answer
I would argue that this does not matter. Consider the case where there are multiple shortest paths from $s$ to $t$ in $G$. In the case of using $\<$, we define the shortest path to be the *first* shortest path we come across. This is because latter paths will only be equivalent in length and thus not satisfy the invariant. However, in the case of using $\leq$ we define the shortest path to be the *last* shortest path we come across. This is because latter paths will be equivalent in length and thus trigger the invariant.

My point is that with $\<$ or $\leq$ we could essentially flip the ordering of nodes in the adjacency list of adjacency matrix to mimic what the other comparison operator would do.
> 0 votes

---
Tags: graphs, shortest-path
---


# Question
Title: What does it mean to logically imply another predicate?
* Consider the following predicate formulas.

$F1: \forall x \exists y ( P(x) \to Q(y) ).$

$F2: \exists x \forall y ( P(x) \to Q(y) ).$

$F3: \forall x P(x) \to \exists y Q(y).$

$F4: \exists x P(x) \to \forall y Q(y).$

Answer the following questions with brief justification.

(a) Does $F1$ logically imply $F2$?

(b) Does $F1$ logically imply $F3$?

(c) Does $F1$ logically imply $F4$?

(d) Does $F2$ logically imply $F1$?

(e) Does $F2$ logically imply $F3$?

(f) Does $F2$ logically imply $F4$?

(g) Does $F3$ logically imply $F1$?

(h) Does $F3$ logically imply $F2$?

(i) Does $F3$ logically imply $F4$?

(j) Does $F4$ logically imply $F1$?

(k) Does $F4$ logically imply $F2$?

(l) Does $F4$ logically imply $F3$?

---

Logically implies really confuses me. Attempt:

Writing it in English first:

F1: We have that $x$ never satisfies $P$ or there is a $y$ that satisfies $Q$

F2: For some $x$ $P$ isn't satisfied, or $y$ always satisfies $Q$

F3: Some $x$ doesn't satisfy $P$ or some $y$ satisfies $Q$

F4: $x$ never satisfies $P$ or $y$ always satisfies Q

By definition of logically implies: A formula $F$ logically implies a formula $F'$ iff every interpretation that satisfies $F$ satisfies $F'$

So:

(a) So for $F1$ $x$ never satisfies $P$ meaning it'll always be true whereas some $x$ can satisfy P in $F2$, thus this doesn't logically imply.

(b) ... yeah I don't know how to explain any of this - any assistance even tips are appreciated I'm stumped

Apparently $b$ is true I don't get it though.

according to $F1$, $x$ never satisfies $P$ and by prepositional logic of $p \to q$ is not p or q.

then $F1$ is always true whereas $F3$ there can exist a P that satisfies Q and some y that doesn't satisfy Q so every interpretation doesn't satisfy? I'm understanding this poorly.

# Answer
$F\_1$ says for all $x$, there exists a y such that $P(x)$ implies $Q(y)$.

$F\_2$ says for there exists a $x$, for all $y$ such that $P(x)$ implies $Q(y)$.

$F\_3$ says that for all $x$, if $P(x)$ holds, then there exists a $y$ such that $Q(y)$.

$F\_4$ says that there exists a $x$, such that if $P(x)$, then for all $y$, $Q(y)$ holds.

The first one means that for all values of $x$, there exists *some* value of y such that the $P(x)$ implies $Q(y)$.

The second one says that there exists a *common* $x$ for all $y$ such that $P(x)$ implies $Q(y)$.

Both of them aren't the same, which is what you have pointed out too and you can solve the rest of them in the same way.

Also, a good way would be to some concrete example and see if it holds or not. It makes the intuition a bit easier.

EDIT: If you want more help with logical implications, there's a book called How To Prove It by Daniel Velleman whose first two chapters deal with logic, which is a good read.
> 0 votes

---
Tags: predicate-logic
---


# Question
Title: Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L
I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.

**PROBLEM STATEMENT:**

> For a string $w = a\_1 a\_2 a\_3 a\_4 a\_5 a\_6 a\_7 \dots$, define $third(w) = a\_3 a\_6 a\_9 \dots$
>
> Then, for a language $L$, define $third(L) = \\{third(w) : w ∈ L\\}$.
>
> Show that if $L$ is regular, then $third(L)$ is also regular.
>
> (Hint: Construct an ϵ-NFA from the DFA for $L$.)

**TEACHER'S SOLUTION:**

If $L$ is regular, it is accepted by some DFA, say $A = (Q,Σ,δ,s\_0,F)$.

We will construct an ϵ-NFA $B$ such that $L(B) = third(L(A))$.

Here, you need four copies of $A$.

Formally, $B = (Q × \\{1,2,3,4\\}, Σ, ρ, F × \\{2,3,4\\})$,

where $ρ =$

${\\{(⟨p, 1⟩, ϵ, ⟨q, 2⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\\}}$ ${∪}$

${\\{(⟨p, 2⟩, ϵ, ⟨q, 3⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\\}}$ ${∪}$

${\\{(⟨p, 3⟩, a, ⟨q, 4⟩) : (p, a, q) ∈ δ\\}}$ ${∪}$

${\\{(⟨p, 4⟩, ϵ, ⟨p, 1⟩) : p ∈ Q\\}}$.

(Do not confuse ρ and p.)

**WHAT I DO UNDERSTAND:**

• I understand how Cartesian products work.

**WHAT I MAY OR MAY NOT UNDERSTAND:**

• Are the ${(p, a, q) ∈ δ}$ parts another way of saying ${δ(p,a) = q}$?

• I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed. And, I suspect that that's the purpose of the stuff with the angle brackets.

• I suspect that the purpose of taking the Cartesian product of Q and ${\\{1,2,3,4\\}}$ and the purpose of taking the Cartesian product of F with ${\\{2,3,4\\}}$ is to have a state for each copy of A, where ${⟨p, 1⟩}$ represents the state p of the first copy of A (but is technically a state of B, not A).

• Should ${⟨s\_0, 1⟩}$ be the start state of B, such that B's n-tuple is a 5-tuple, rather than a 4-tuple, and that that 5-tuple is ${B = (Q × \\{1,2,3,4\\}, Σ, ρ, ⟨s\_0, 1⟩, F × \\{2,3,4\\})}$?

**WHAT I DON'T UNDERSTAND:**

• I don't understand what the transitions regarding the four copies (defined by B's transition relation, ρ) achieve exactly.

• Also, why does one need four copies of A? Can't one just add those additional transitions to a single copy of A?

Any input would be GREATLY appreciated!

Edit for adding new information (#1): Thanks to all of you for responses. :)

I have a comparatively small question: The transition relation, ρ, is also function in this case, because each state of the NFA B only has one transition to another state, per input, right?

# Answer
> And, I suspect that that's the purpose of the stuff with the angle brackets.

This is just a way to write elements of a cross product. For example: $$\lbrace 1,2\rbrace\times\lbrace 3,4\rbrace = \lbrace \langle 1,3\rangle,\langle 1,4\rangle,\langle 2,3\rangle,\langle 2,4\rangle \rbrace$$

> I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed.

Basically yes. The construction creates four copies of $A$. The first three copies behave just as $A$ behaved originally with a minor twist: If state $q$ is reached, instead afterwards the state $q$ in the next copy of $A$ is reached. (I will ignore the $\epsilon$ edge inscriptions for now. I come back to this later.)

Thus, initially we are in state $s\_0$ of the first copy of $A$ (written as $\langle s\_0,1\rangle$). Then, some letter $a$ is read. Let's say that in $A$ this would lead from $s\_0$ to state $p$. Now, in the new automaton, this leads to state $p$ in the second copy of $A$, i.e. $\langle p,2\rangle$. Next, some letter $b$ is read. Let's say that this would lead from $p$ to $q$ in $A$. In the new product automaton, this leads from $\langle p,2\rangle$ to $\langle q,3\rangle$, i.e. it also moves on to the next copy of $A$.

The effect of this construction so far is that we not only "behave as $A$ would behave", but also that we know if the current letter position is exactly a multiple of three, or a multiple of three plus one, or a multiple of three plus two: All multiplies of three end up in the first copy of $A$, all multiplies of three plus one in the second copy, etc.

Now, let's go back to the $\epsilon$ edge inscriptions: So far, the automaton that was constructed just behaves as the original automaton $A$. But we want it to read just every third letter and skip the other two. We do this by replacing all edge inscriptions in the first two copies of $A$ with $\epsilon$. This will lead to a lot of non-determinism, because now all outgoing edges have the same label. The idea here is that when we have an input $a\_3a\_6a\_9\dots$ the automaton "guesses" what the missing symbols $a\_1, a\_2, a\_4, \dots$ could be. Each such guess is represented by taking an $\epsilon$-labelled edge. Only the third copy of $A$ is not modified, so this copy still actually reads $a\_3a\_6a\_9\dots$

> What does the fourth copy do?

(No one actually wrote this question, but I need it for structure ;-) )

The fourth copy in the construction from the question actually does not do anything. When the automaton is in state $\langle q,4\rangle$, the only option to continue is to go to state $\langle q,1\rangle$ (via an $\epsilon$-transition). Thus, the fourth copy can just be removed and instead we go directly to $\langle q,1\rangle$.

> Can't one just add those additional transitions to a single copy of A?

First, there are no additional transitions (well, okay, the transitions from $\langle q,4\rangle$ to $\langle q,1\rangle$ can count as additional transitions). Instead, the construction keeps the original transitions but replaces some of the inscriptions with $\epsilon$.

Next, a single copy is not enough. The automaton still has to keep track on the position in the input. As an exercise, construct a DFA accepting $(abcd)^\*$ and try out the construction on it.
> 2 votes

# Answer
The answer by Uli is excellent. It gives a detailed intuition behind the three-step construction. Still I was wondering whether it was possible to avoid the product construction.

We can "summarize" the three step construction as follows. Construct a new automaton $C$ with state set $Q$, the original state set of $A$; initial state $s\_0$.

Now for every three consecutive transitions $(p,a\_1,p\_1), (p\_1,a\_2,p\_2), (p\_2,a\_3,p\_3)$ in $A$, add the transition $(p,a\_3,p\_3)$ to $C$. A state $q$ in $Q$ is final in $C$ if in $A$ from $q$ we can reach a final state in $F$ in zero, one or two steps (letters).

Now $C$ is a nondeterministic automaton (without epsilon-transitions) for the language $third(L)$. The above construction basically is the product construction with the standard construction for removing epsilon transitions merged into it. Sort of.
> 1 votes

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


# Question
Title: What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.

Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best bound. In the solution, we get around 85-90 binaries which have value of 1 and others are zero. The objective value is around 20 to 30 million. I have created an algorithm in which I am predicting (fixing their values) 35 binaries (with the value of 1) one by one and letting the remaining ones solved through the Cplex. This has reduced the time to get the same objective to around 24 hours (the best bound is slightly compromised). I have tested this approach with the other (same type of problems) and it worked with them also. I call this approach as "Probabilistic Prediction", but I don't know what is the standard term for it in mathematics?

Below is the pseudocode:

```
Let y=ContinousObjective(AllBinariesSet);
WriteValuesOfTheContinousSolution();
Let count=0;
Let processedbinaries= EmptySet; //Binaries processed per iteration.
while (count < 35 ) {
    Let maxBinary =AllBinariesSet.ExceptWith(processedbinaries).Max();//Having Maximum Value between 0 & 1 (usually lesser than 0.6)
    processedbinaries.Add(maxBinary);
    maxBinary=1;
    Let z = y;
    y = ContinousObjective(AllBinariesSet);
    if (z > y + 50000) {
        //Reset maxBinary
        maxBinary.LowerBound = 0;
        maxBinary.UpperBound = 1;
        y = z;
    } else {
        WriteValuesOfTheContinousSolution();
        count=count+1;
    }
}

```

Explanation of the pseudo code:
Step 1: Initialize an empty list of processed binaries.
Step 2: Run the continuous solution and get the binary which has maximum value and not the part of processed binaries. Add that binary to processed binaries list.
Step 3: Fix the value of that binary to 1 and run the continuous solution again.
Step 4: If the objective is not around 99.75% of previous objective then revert to Step 1 and add the fixed binary to the list of ignored binaries.
Step 5: Repeat from Step 1 to Step 3 until we have fixed 35 binaries in the LP.
Step 6: Start the integer optimization run (mipopt in cplex) of the fixed LP.

So basically we are predicting around 40% of the binaries (with the value of 1) and at every iteration we are ensuring that the continuous objective is not reduced below 0.25% (approx. 50000) of its actual value before the previous prediction. According to me, it's working because the solution matrix is very sparse and there are too many good solutions.

# Answer
I would say that this approach falls under the umbrella of **iterative rounding**. I believe that the seminal paper regarding this kind of strategy is \[1\]. The heuristic outlined here differs in signifcant ways from the algorithm described in Jain's paper but I think the basic idea is in the same vein.

1. Jain, K. (2001). A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1), 39-60.
> 3 votes

---
Tags: optimization, reference-request, linear-programming, integer-programming
---


# Question
Title: Directed HAM Cycles with Additional Constraints to SAT
The $n$ dimensional hypercube $Q\_n$ is a graph that has a vertex $v\_s$ for each string $s \in \\{0, 1\\}^n$ and an edge between two vertices $v\_s$ and $v\_t$ if and only if the Hamming distance between $s$ and $t$ is $1$.

I would like to find directed hamiltonian cycles in this graph that satisfy a certain property, and was thinking of feeding my problem to a SAT solver. The problem can be encoded as follows. We define a variable $x\_{si}$ to denote that the vertex $v\_s$ appears in the $i$-th position of the cycle. Then, for each $s \in \\{0,1\\}^n$, we define the contraints $\bigvee\_{i} x\_{si}$ (each vertex appears in one position of the cycle) and $\neg x\_{si} \vee \neg x\_{sj}$ for all $i \neq j$ (each vertex appears at most once in the cycle). Finally, we also require the constraints $\neg x\_{si} \vee \neg x\_{t(i+1)}$ for all pairs of strings $s$ and $t$ that have Hamming distance greater than $1$ (i.e pairs of vertices that do not have an edge cannot appear consecutively in the cycle ordering).

Now, I would like to add the following requirement on my cycle. For some specified integer parameter $k$, we must be able to partition the vertices of the graph into vertex disjoint copies of $Q\_k$ such that the vertices in a specific copy of $Q\_k$ are all assigned the same "direction". How can I capture this set of requirements easily in my reduction?

# Answer
> 3 votes
Encodings like this are notoriously slippery, so (of course) please carefully verify any outputs in case I've made a mistake somewhere.

Please assume that all unbound variables are universally quantified; i.e., I write $\bigvee\_i\ p\_{si}$ instead of $\forall s\ \bigvee\_i\ p\_{si}$.

# Defining the partitions

First, define partition variables:

$p\_{si} = \text{vertex $s$ is in partition $i$}$.

## Basic partition constraints

Partitions are disjoint:

for $s \neq t$: $\lnot (p\_{si} \land p\_{ti})$.

Every string is part of one partition:

$\bigvee\_i\ p\_{si}$.

## Coordinate matching within partitions

This is a little tricky. First, we need to define which hypercube each partition corresponds to. We specify this by defining which coordinates each partition matches on:

$m\_{ij} = \text{partition $i$ requires coordinate $j$ to match}$.

Now we need to say that partition $i$ requires exactly $n-r$ coordinates to match (I'm going to use $r$ where OP uses $k$, because I need to use k as an index below):

$\sum\_j m\_{ij} = n - r$.

## Computing the sum

Sums, of course, are not directly supported in the SAT model. We can handle this by computing the sum with propositional logic:

$a\_{ijk} = \text{for partition $i$, the sum over the first $j$ bits of $m$ is $k$}$.

The sum across the first $j$ bits for partition $i$ must be uniquely defined:

for $k\_1 \neq k\_2$, $\lnot (a\_{ijk\_1} \land a\_{ijk\_2})$.

We could require each sum to be defined at least once, but we don't need to; we take care of that for free when we define how addition works:

$a\_{i1k} \iff m\_{i1}$

$a\_{ijk} \land m\_{ij} \implies a\_{i(j+1)(k+1)}$

$a\_{ijk} \land \lnot m\_{ij} \implies a\_{i(j+1)k}$

Now we can set what the sum needs to be:

$a\_{in(n-r)} = \texttt{true}$

(Again, I use $r$ where OP uses $k$ to avoid confusion with $k$ as an index.)

## Constraining matches

Strings in the same partition match at the required coordinates:

$(m\_{ij} \land p\_{si} \land p\_{ti}) \implies \text{strings $s$ and $t$ match at position $j$}$.

The RHS of that implication is just a set of constants that we can precompute as true or false.

# Enforcing cycle direction within partitions

To encode direction, we can precompute constants for a neighbor relation between strings:

$d\_{sti} = \text{$s$ and $t$ are identical, except at position $i$, where $s$ is 0 and $t$ is 1}$.

We'll also define a variable to encode which strings follow which strings:

$f\_{st} = \text{$t$ immediately follows $s$ in the cycle}$.

$f\_{st} \iff \bigvee\_i x\_{si} \land x\_{t(i+1)}$.

Now we're ready to encode cycle direction:

$\[\bigvee\_i (p\_{si} \land p\_{ti})\] \implies \[\bigvee\_{uvj}\ (f\_{su} \land f\_{tv} \land \[(d\_{suj} \land d\_{tvj}) \lor (d\_{usj} \land d\_{vtj})\]$.

If $s$ and $t$ are in the same partition, then there is one specific bit position $j$ where the strings $u$ and $v$ that follow $s$ and $t$ in the cycle differ (and specifically differ in the same direction: 0 to 1 or 1 to 0).

I don't know that much about SAT solvers, but it may be that the last line produces an unwieldy number of terms. It may be possible to define further 'intermediate' variables like $f\_{st}$ that break things up more and reduce the combinatorial explosion.

---
Tags: graphs, reductions, satisfiability
---


# Question
Title: Oven cooking queue problem: need help to determine its nature
CS community!

I'm more of a practical programmer than a computer scientist, so I need your help to find a solution (or at least point me into the right direction) to an **extremely practical problem related to cooking food in the oven**.

### Problem

I have N ovens and I have multiple various ingredients to cook in them. Each ingredient has certain preparation (e.g. peel the potato, cut the meat, etc.) time and oven cooking time. At time 0 we start preparing ingredients and putting them into the oven to cook. I need an algorithm to find the most optimal arrangement for the queues of these N ovens, so that it takes minimum time to finish cooking all of the ingredients.

Additional note: each ingredient is cooked at specific temperature, so no 2 ingredients can be cooked simultaneously.

### Example

2 ovens: O1, O2

7 ingredients:

A (PT 200, CT 400)

B (PT 180, CT 380)

C (PT 80, CT 240)

D (PT 60, CT 180)

E (PT 40, CT 120)

F (PT 20, CT 60)

G (PT 0, CT 20)

*Where: PT - preparation time, minutes; CT - cooking time, minutes.*

I solved it simply visually and found that optimal solution looks like this:

```
Time: action

0: put G in O1
20: take G from O1, put F in O1
40: put E in O2
80: take F from O1, put C in O1
160: put take E from O2, put D in O2
320: take C from O1, put A in O1
340: take D from O2, put B in O2
720, take A from O1, take B from O2 -- finished in 720 min!

```

Visually it looks like this:

### Conclusion

In a search for an answer I found that problem cannot be solved by simply sorting ingredients in some order, as changing the timing on one of the ingredients can dramatically change the cooking order: sometimes ingredients need to wait for certain time, even though they are prepared and ready to be cooked -- the priority queue can change completely!

### Question

Whoever sees any similarities with certain mathematical or CS problems (Knapsack? Packing?), please point me in the right direction. Or, preferably, point me to the solution, which surely must exist for such an obvious problem.

Thank you!

# Answer
> 0 votes
This problem is NP-hard: it is a more general version of Minimum Multiprocessor Scheduling. You should not expect efficient algorithms that compute the optimal solution in all cases.

The main difficulty is finding out what is the "best" oven in which to cook an ingredient. Once you know (in some way or the other) which ingredients should go in which oven, you can not go wrong by queueing them based on their preparation time.

So one way to compute the best solution is as follows: perform a cycle in which you try all possible assignments of $K$ ingredients to $N$ ovens, which is $N^K$ possibilities. For each of these possibilities, compute the solution based on queueing by preparation time in each oven. The best of all solutions you generate is the optimal solution. This of course will only be practical if $N$ is very small (like in your example) and $K$ is also small.

---
Tags: knapsack-problems
---