# Question
Title: NP-hardness of modified distance-colouring of graphs
Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\\{0,1,2,3,...,c-1\\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must be colored) in such a way that each node can find all distinctive colors around it within a radius of $r$, i.e., for every vertex $v \in V$, $N^r\[v\]$ has all colors of $\mathcal{C}$.

How should I prove that this problem is a NP-complete problem(it is fairly easy to show the certificate part and NP part, but I have difficulty reducing this problem to well know NP-complete problems.)

Note that this problem is different from the $k$-coloring problem. Note that it is not a problem to have same colors on neighbors. I solved the NP part but I do not know how to reduce this problem.

# Answer
> 0 votes
I don't have an answer to your problem, but I have an answer for a different problem.

Let the *Annotated Colorful Neighborhood*-problem be as follows.

**Annotated 2-Colorful 1-Neighborhood**
**Input**: $G = (V, E), k, S \subseteq V$
**Output**: Is there a coloring of vertices of $V \setminus S$ such that every vertex $v \in S$ has at least one red neighbor and one blue neighbor.

This problem is NP-hard when $G$ is a bipartite graph and $S$ is one of the sides, and even if every vertex in $S$ has degree 3.

The reduction is from *NAE-3-SAT without positive literals*. In NAE-3-SAT without positive literals, the input is a set of $n$ variables $x\_1, x\_2, ..., x\_n$ and a set of relations $$R(x^1\_1, x^1\_2, x^1\_3), R(x^2\_1, x^2\_2, x^2\_3), ... R(x^m\_1, x^m\_2, x^m\_3)$$ and the question is if it is possible to assign truth values to $x\_i$ such that not all $x^j\_1, x^j\_2, x^j\_3$ have the same truth value for any $1 \leq j \leq m$.

The problem can be seen as a special case of *Set Splitting*. In the Set Splitting problem, we are given a set $\mathcal U$ and a set of subsets $\mathcal F \subseteq 2^{\mathcal U}$, and the question is whether there exists a partitioning of $\mathcal U$ into $S\_1$ and $S\_2$ such that for every set $F \in \mathcal F$, $F \cap S\_1 \neq \emptyset$ and $F \cap S\_2 \neq \emptyset$.

# Answer
> 0 votes
The problem you describe (for $r=1$) falls under the $\[\sigma,\rho\]$-partitioning framework with several hardness results available (see e.g., \[1\]). In such a problem, we want to color the vertices of a graph in $k$ colors such that for each vertex, the number of neighbors it has with its own color in in $p$ and the number of neighbors it has with each different color than its own is in $\rho$. So note that $\sigma$ and $\rho$ are sets here.

For example, if you mean that you want a coloring where each vertex $v$ sees each of the $k$ colors in its neighborhood (again, I'm speaking only about $r=1$), we have $\sigma = \mathbb{P} = \\{1, 2, \ldots \\}$ and similarly $\rho = \mathbb{P}$. If you think about what the color classes are in this case, you are actually partitioning the vertex set into total dominating sets. By Theorem 3 in \[1\], this problem is NP-complete for 2 colors. If you just search online for "partitioning into total dominating sets", you will find more hardness results. In short, the problem is NP-complete for $k \geq 2$, and remains hard for many restricted graph classes as well.

I don't know if anyone has studied the problem explicitly for $r \> 1$ as you describe.

---

\[1\] Heggernes, Pinar, and Jan Arne Telle. "Partitioning graphs into generalized dominating sets." Nord. J. Comput. 5.2 (1998): 128-142.

---
Tags: graphs, np-complete, trees, np-hard, colorings
---


# Question
Title: Regarding CPU ILP: what actually consistitutes "the current instruction"?
If a CPU is able to execute multiple instructions in parallel, and fetching/decoding/scheduling instructions happen in batches, and there's multiple execution units, etc. What does the IP register points to among all the instructions being executed at the same time?

# Answer
When you read about the instruction set of a processor, in order not to blow up the brain of the reader, we pretend that instructions are executed one after the other. AND whatever the processor does, it acts AS IF that’s how it works.

In reality there are multiple different states related to the IP. There is an instruction reader that reads instructions fro memory. It has a next instruction to read, and probably reads many instructions in one go. Then you have an instruction decoder which decodes instructions and determines where each one starts (simple on an ARM processor where each instruction is four bytes, difficult on x86 where each instruction is 1 to 15 bytes. Anyway, at this point you have several instructions and know where each starts.

There are many other stages, each keeping track of instructions and their addresses. The last stage is the *retire* stage. If an instruction sets a register of memory cell, the instruction is retired when the results are moved to this location. When an instruction is retired, that’s the point where we can say it has been executed.

You could take the instruction that is the next one to be retired as “the instruction pointer”. If something interrupts your processor, it can throw away what it was working on and start over from the address of the first unretirrd instruction.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: If Q* can break encryption would that prove P=NP?
At 12:11 in this video the creator talks about unverified rumors the **Q\* algorithm** can break AES-192 encryption. If this is true, would this mean **P = NP**?

# Answer
You would have to show how being able to break AES-192 encryption would make it possible to solve some NP-complete problem. There would have to be an algorithm like this:

“Given is an instance P of an NP-complete problem. Given P we construct one or more instances of AES-192 encryption, break them all, and use the result to solve the instance P”.

For “breaking encryption” there is another problem: We consider encryption to be broken if a significant number of encryptions can be broken, not all. So even if being able to break *all* instances of AES-192 could prove P=NP, breaking enough instances to consider AES-192 broken might not be enough.
> 2 votes

---
Tags: np, artificial-intelligence, cryptography
---


# Question
Title: What is the practical use of list.clear() method in Python?
I was wondering if there is a reason behind clearing all the values in a list and reusing it, as opposed to deleting the list and creating a new one. Are there any practical advantages of using `clear()` method, aside from situations where the list is referenced in multiple locations, and deleting it might lead to unintended consequences?

# Answer
What do you mean by deleting a list? for example, if you go on another iteration in the loop, however you want cleared list and not with some random items from previous iteration. my answer is more useless, because you can use some other language features to achieve exactly same result. interesting discussion about list.clear() method can be found here: https://stackoverflow.com/questions/1401933/why-is-there-no-list-clear-method-in-python , notice that question was asked when list.clear() method wasn't added in python and updated discussion followed after it was added. https://bugs.python.org/issue10516 _ I think this will also be useful.
> 0 votes

---
Tags: python
---


# Question
Title: What is the simplified form of this big o
$O(\sum\_{l=0}^{log\_2n} l\*2^l)$. I took the integral of the term which I think is $O(n\*log(n))$

# Answer
Let's give an upper and a lower bound:

1. Lower bound: $$ \sum\_{l=0}^{\log\_2 n} l\cdot 2^l \ \geq \ \log\_2n \\, \cdot 2^{\log\_2 n} \ = \ n \log\_2 n \ , $$ so we can say that $\sum\_{l=0}^{\log\_2 n} l\cdot 2^l = \Omega(n\log n)$.
2. Upper bound: \begin{align} \sum\_{l=0}^{\log\_2 n} l\cdot 2^l \ &\leq \ \sum\_{l=0}^{\log\_2 n} \log\_2 n \cdot 2^l = \log\_2 n \sum\_{l=0}^{\log\_2 n} 2^l \\ \\ &\leq \ \log\_2n \cdot 2^{1+\log\_2 n} \ = \ 2n\log\_2 n \ , \end{align} where the second inequality derives from the fact that $\sum\_{i=0}^n 2^i = 2^{n+1}-1$. Thus, we have $\sum\_{l=0}^{\log\_2 n} l\cdot 2^l = O(n\log n)$.

Summing up, we have that $\sum\_{l=0}^{\log\_2 n} l\cdot 2^l = \Theta(n\log n)$.
> 6 votes

---
Tags: summation
---


# Question
Title: Turing machine for language $\{a^p | p~\text{is a prime number}\}$
I am trying to find a Turing Machine for the above language. I am trying to do it with one tape, to start with. However, I am not quite sure about how to keep track of the number of a's in the string. Any help is appreciated.

# Answer
> 0 votes
There is a *very* slow turing program that works on binary numbers at http://morphett.info/turing/turing.html (just go to the example programs); it could easily be adapted to unary.

# Answer
> 0 votes
We'll try to construct the TM below. Given input $a^p$, our TM will accept if and only if $p$ is prime. This TM will contain an input tape and a tape for its factors, and it starts with $a^p$ on its input tape.

1. If the input is $\varepsilon$ or $a$, the TM rejects right away. (Why? Because $0$ and $1$ are not primes.)
2. If (1) above does not hold, then initialise the factors tape with the string $aa$.
3. If the input length is the same as the length of the string on the divisor tape, then the Turing machine halts and accepts. (How would we implement this? The TM seeks to the starts of the strings on both the input and factors tapes, and both heads move together at once. If one head sees some character $\mathfrak{c}$ before another, then the strings have different lengths; otherwise, they have the same length.)
4. The TM then determines whether the length of the value on the input tape is divisible by the length of the value on the factors tape - it halts and rejects if this is the case. (How might we implement this? The TM would move all the way to the starts of both the input and the factors tapes and moves the heads together at once. If the factors head sees $\mathfrak{c}$ while the input head sees $a$, then the TM will reset the factors head to the beginning of its string and continues reading. If the input head sees $\mathfrak{c}$ while the factors head sees $a$, then the factor isn't really a factor (it doesn't uniformly divide the input). If both heads see $\mathfrak{c}$ at once, then the factor actually does divide the input.)
5. If the current factor doesn't divide the input, then the TM increments the value on the factors tape and reverts to step (3) above, repeating the loop. (How would you implement this? Just go all the way to the end of the factor and append an $a$.)

Depending on which TM model you're following, the TM will vary a bit, but should still be a variation of the above. I used two tapes, but there are a number of routines you can use to compress it all to one tape (for example by adding a marker $\mathfrak{m}$ after a number of steps on the tape etc). Regardless, the point is that as the TM rejects the numbers $0$, $1$, and every $p \in \[2, p-1\]$ such that $p$ has a factor (i.e. all unary strings $a$ of composite length), it only accepts those $p \geq 2$ that do not pass trial division for all numbers $\< p$; namely the prime $p$.

---
Tags: turing-machines
---


# Question
Title: Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$
I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\\{a^{n}b^{2n}c^{3n}|\ n\ge0\\}$, but how do you verify this? Likewise, how do you verify that this machine rejects any string not in the given language?

# Answer
> -1 votes
you should test it with different combinations of a,b and c. This is the only method I know till now to validate the turing machine you've constructed.

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


# Question
Title: What's the Time Complexity and total no of iterations?
**for a=1 to m means for(a=1;a\<=m;a++)**

```
for i=1 to n
 for j=i to n
   c= c+1;

```

The total no of iterations is O(n^2)

```
i=1,j executes n times.
i=2,j executes n-1 times.
.
.
.
i=n, j executes 1 times.

```

So Total No of iterations = n+n-1 + n-2+ ..... + 1 = Sum of n natural numbers = O(n^2)

For the Time complexity of the given algorithm, i executes n times and j executes from i to n so it will be O(n\*(n-i+1)) = O(n^2). Am I correct in my answer and approach for both of the solution?

# Answer
> 0 votes
The first approach is correct. The idea is that the sum of the first $n$ numbers can be computed as $$\dfrac{n(n+1)}{2} = \dfrac{n^2 + n}{2} = O(n^2)$$

I would not consider the second one as complete, as since $i$ is a free variable in your complexity expression, the result does not immediately follow unless you quantify over $i$ (which would result in you obtaining the expression above).

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


# Question
Title: Transitioning from mathematics to computer science
I'm a mathematics undergraduate interested in theoretical computer science, machine learning, and neuroscience. I wish to pursue graduate studies in computer science but I fear I might not be able to since I haven't and won't be allowed to take any computer science courses for the rest of my undergraduate years. My curriculum is made up of the traditional pure and applied mathematics courses (analysis, algebra, topology, differential equations, vectors and tensors, probability, etc.) without emphasis on computer science.

My question is, would I be able to apply, generally, for graduate studies in computer science with my degree only as a starting point? I am also taking classical courses in computer science (data structures, algorithms, etc.) online (e.g. Coursera) and I'm very good in programming. Would these add to my chances of being considered for the admissions? In all, if there are any ideas of what I could do, I'd love to hear it.

Thanks.

# Answer
> 1 votes
I think you should take some time after you graduate, and study some selected topics. I think you should necessarily know:

* Some foundations: basic logic, automata and grammars, structural induction on lists and trees and recursion.
* Some algorithm theory, which you can learn from the Cormen Leiserson Rivest Stein book. In particular focus on sorting, searches, basic data structures like linked lists, trees graphs and hash tables, graph algorithms, greedy algorithms and dynamic programming.
* Some computability and complexity. You should develop an intuition for the complexity of algorithms (which you can also get from CLRS), and know about Turing Machines, the Lambda Calculus, some notions of computability (Halting problem, Rice's theorem) and some basic knowledge of complexity classes (P, NP,...)
* C programming; you should be able to reason with pointers and to implement data structures. "The C programming language" by Kernighan and Ritchie is a good reference.
* Some OOP and Functional programming. I suggest Java and OCaml. In particular you should focus on types, inheritance and polymorphism. Check if there is a course about this in the curriculum you want to apply to; If so, don't go too much into the details. You should stop reading about a subject as soon as you read "Category Theory".
* Some concurrent and parallel methods (locks, condition variables, semaphores...), and in general how various programming languages implement synchronization mechanisms. You should be able to write multi-process and multi-threaded programs in C, and multi-threaded applications in Java. Here too, don't delve too much into the details, or you'll never finish. Just try to have an intuition for this, before you start taking more advances courses.
* If you're into AI, you should read something about some advanced graph algorithms (the so called "informed" search algorithms), something about SAT-solvers and some selected machine learning techniques (polynomial fitting, K-NN...) but you're probably not required to know these to be accepted. Considering your background, you will likely have no problems learning even more advanced topics like backpropagation.

You may also be required to know some database theory, software engineering and networks. If you manage to, read something about these topics, but I'd say, for theoretical CS with a mathematical background, the above are more important. Good luck :)

# Answer
> 1 votes
I did so and I had no problems. But of course it all depends on the level of the master degree you are transitioning.

I had some basics of Computer Science both from school (I did an IT school) and from my Bachelor, where I studied automatas, regular languages and grammars, C programming, a basic Algorithm and Data Dtructures course (sorting, searching, basic to medium data structures like heaps, graphs, skip lists, etc, routing algorithms, computational complexity and similar stuff), operational research (linear (integer) programming, algorithms on graphs (flows, routing, etc), simplex algorithm, relaxations, NP problems and approximations (greedy, heuristics,...), etc), OOP, compilers, a glimpse on functional programming and numerical analysis (both theoretical and practical). I didn't study deeply these topics on my bachelor but the ideas and way of thinking needed in Computer Science were enough for me.

Of course it depends on the Master degree you are aiming at, if the level is very high and the courses are really deep and requires a very well knowledge of CS basics it is hard to do it without fundations. But for a mid-level CS Master degree I think having some introductory courses on Coursera and a bit of practicality with the subject is enough

# Answer
> -3 votes
Actually you can study computer science and mathematics All you have to do is search for institution that offers computer science and statistics. Or if that will not help you can learn Data analyst Data science Machine learning And many other thou these are short courses, they are heckit i would advice just try to advance you mathematics too in other institution's

---
Tags: career
---


title: Why isn't SAT in coNP?

text:
# Question
Title: Why isn't SAT in coNP?
I understand why NP=coNP if SAT is in coNP (How do I prove that SAT in coNP implies NP=coNP?).

But I'm missing why the following machine doesn't turing recognize the complementary of SAT:

Given a turing machine M that recognizes SAT, the following turing machine recognizes coSAT:

1. Run M on the input word w.
2. If M accepts - reject.
3. If M rejects - accept.

Because coSAT is the language of all unsatisfiable formulas, a formula is unsatisfiable if it doesn't have a satisfiable interpretation, which is exactly the opposite of what M outputs.

What am I missing in here?

# Answer
> 2 votes
You are missing a major part of the definition of $CoNP$: you need a proof that your machine $M$ runs in nondeterministic polynomial time for all "yes" inputs. Because you have simply taken the NP SAT algorithm and flipped it, it runs in nondeterministic polynomial time for all "no" inputs. But we have no such guarantees for the "yes" inputs.

The real answer is, nobody knows that SAT isn't in $CoNP$. If we knew that, we would know that $CoNP = NP$, but this is still an open problem. So, nobody can point to a specific reason that you *can't* build a machine that decides the complement of SAT it nondeterministic polynomial time. It's just that nobody has been able to do it yet, or prove that it's impossible.

# Answer
> 2 votes
Always remember that for questions involving NP, instances with a "Yes" answer are treated totally different from instances with a "No" answer. Basically, a problem is in NP if any instance with a "Yes" answer can be proven to have the answer "Yes" in polynomial time, as long as we are able to make a fantastically lucky guess to help us. But instances with a "No" answer - no idea how to prove the answer is "No".

Your Turing machine solves SAT in the slow way, without using that lucky guess. For example, in exponential time by trying out all possible combinations of inputs for the SAT problem. And you're right, based on this Turing machine, we can build another one that solves the opposite of SAT in the exact same exponential time. But that doesn't prove that either is in NP or co-NP:

To be in NP, you'd need a Turing machine that doesn't just solve SAT in exponential time. You'd need one that starts by writing a fantastically lucky hint on the tape, and then using the hint and the SAT problem, finds out that the SAT instance can be solved, and all that in polynomial time - as long as the answer is Yes. If you just reuse this turing machine to solve co-SAT, it would find solutions quick if the answer to the original SAT problem is "Yes", and therefore the answer to the co-SAT problem is "No". But that doesn't help: We need a Turing machine that can solve co-SAT problems with the answer "Yes" or equivalent, SAT problems with the answer "No", and we don't have that.

# Answer
> 1 votes
So far as we know, NP and co-NP are separate complexity classes under Karp reduction, aka many-one polynomial-time reduction. Your procedure is a Turing reduction, not a Karp reduction. Turing reductions are too powerful for NP and co-NP to be separate classes under them.

# Answer
> 0 votes
Three years late to the thread but here's another from a Turing Machine perspective:

# Defining NP with NTMs and showing that certificate/verifier implies membership of NP

We define $NP$ as the set of decision problems that can be solved in polynomial time by a nondeterministic Turing machine (NTM). We can show that a decision problem $X$ (such as $\text{SAT}$) is a member of $NP$ if the following conditions are satisfied:

* For each "Yes" instance $w$, there exists a binary string $C\_w$ that serves as proof that indeed $w\in X$. We require that $|C\_w|=p(|w|)$ where $p(x)$ is some polynomial. In the case of $\text{SAT}$, $w$ encodes a boolean formula $\phi$ on $n$ boolean variables $x\_1,x\_2,\ldots,x\_n$, and $\phi\in\text{SAT}$ if and only if there exists a truth assignment of the variables which results in $\phi$ evaluating to true. A straightforward choice of $C\_w$ would then be an encoding of that truth assignment, and $|C\_w|$ would then be linear in $|w|$ because you only need one bit for the truth assignment of each boolean variable.
* There exists a deterministic, polynomial time algorithm $\text{verifyX}(w,C)$ that uses $C$ to confirm that $w\in X$. This is to say, if argument $C$ is sufficient proof that $w\in X$, $\text{verifyX}()$ accepts, otherwise it rejects. In the case of $\text{SAT}$, this algorithm would simply plug the assignment $C$ into the boolean formula $\phi$ and accept if and only if $\phi$ evaluates to true.

Given these two conditions, we can construct a nondeterministic Turing machine that *decides* decision problem $X$ by implementing the following algorithm:

$ \text{NPDecideX}(w)\\ 1.\text{ initialize }C\[1,\ldots,p(|w|)\]\\ 2.\text{ for }i\gets 1\text{ to }p(|w|)\\ 3.\quad\quad \text{nondeterministically choose }c\in\\{0,1\\}\\ 4.\quad\quad C\[i\]\gets c\\ 5.\text{ return verifyX}(w,C) $

This algorithm essentially just nondeterministically chooses the entire certificate $C$ one bit at a time and then uses $\text{verifyX}$ using said certificate $C$. It works in polynomial time because it takes $p(|w|)$ iterations to choose $C$, then a polynomial amount of time to verify $w$ using $C$.

"An NTM accepts an input string if and only if at least one of the possible computational paths starting from that string puts the machine into an accepting state."

So on input $w\in X$, our NTM accepts because there exists a path it could take where $\text{verifyX}()$ accepts, namely the path where $C\_w\[i\]$ is chosen on the $i^{\text{th}}$ iteration for all $i$. On input $w\notin X$, our NTM rejects because there does not exist a certificate $C\_w$ which proves $w\in X$, thus no such path can exist where $\text{verifyX}()$ returns true.

All of this is to say we've constructed an NTM that decides $X$ in polynomial time, thus $X\in NP$ by definition. In short, certificate-verifier $\implies X\in NP$. The Cook–Levin theorem tells us that the reverse implication also holds, but we don't have to get into that here.

# We can't easily show SAT is in CoNP

So let's say we construct an NTM $M$ that *decides* SAT using this certificate-verifier method. What happens if we construct a new machine $M'$ by negating the output of $M$?

$ \text{NPDecideXbar}(x)\\ 1.\text{ initialize }C\[1,\ldots,p(|w|)\]\\ 2.\text{ for }i\gets 1\text{ to }p(|w|)\\ 3.\quad\quad \text{nondeterministically choose }c\in\\{0,1\\}\\ 4.\quad\quad C\[i\]\gets c\\ 5.\text{ return NOT}(\text{verifyX}(w,C))\quad // \gets \text{We added a NOT}()\text{ here} $

The question is, does the resulting machine then decide $\overline{\text{SAT}}$? Well, no. Here's why:

Let's consider a *nontrivial* "Yes" instance $w$. By *nontrivial* I mean not all possible certificates $C$ work to prove that $w\in X$, but at least one does. In the case of SAT, $w=\phi=x\_1\vee \neg x\_1$ would be trivial because any truth assignment results in $\phi$ evaluating to true. Conversely, $w=\phi=x\_1$ is a nontrivial "yes" instance because assignment $x\_1$=true makes $\phi$ evaluate to true but assignment $x\_1=$false makes $\phi$ evaluate to false.

The key is to realize that not only does $M$ accept $w$ because $w\in X$, but also $M'$ accepts $w$ because there exists a computational path where $M'$ ends in a halt-accept state, namely one where an invalid certificate is chosen, thus $\text{verifyX}(w,C)$ returns false and $\text{NOT}(\text{verifyX}(w,C))$ returns true. This is to say $M'$ accepts $w\in X$ and $w\notin \overline{X}$ so $M'$ does not decide $\bar{X}$. Our nondeterministic turning machine $M'$ doesn't decide $\overline{\text{SAT}}$ (i.e. the language of all boolean formulas $\phi$ which are unsatisfiable), rather it decides the language of all boolean formulas $\phi$ which are not *trivially* satisfiable, which includes many formulas that are satisfiable.

This is not to say that $\text{SAT}\notin CoNP$. We didn't show that there doesn't exist a NTM that decides $\overline{\text{SAT}}$ in polynomial time, we just showed that our nondeterministic machine $M'$ doesn't work. Hypothetically, if one were to show that for every unsatisfiable boolean expression $\phi$, there exists a way to certify that indeed $\phi$ is *unsatisfiable* using a certificate of polynomial size, and there also exists a deterministic polynomial time algorithm which verifies that $\phi$ is indeed unsatisfiable given said valid certificate, then that person would have shown that indeed $\overline{\text{SAT}}\in NP$ and thus $\text{SAT}\in CoNP$. However, that would not at all be easy to show and that's evidenced by the fact that at the time of writing this, it's still an unsolved problem in computer science.

---
Tags: np, satisfiability, co-np
---


title: CFGs and Pushdown Automata

text:
# Question
Title: CFGs and Pushdown Automata
Is this the CFG for part (a),

```
                         S -> AxxyxxA
                         A -> Ax|ε

```

If this is the answer then this grammar would accept "xxyxxx" also which is wrong. How to do it if this is wrong?

# Answer
> 0 votes
As you noticed, the CFG you have given accepts words not in the language $L$. Therefore, no, it is not correct. We will not do your homework for you, but I will give you the hint that your current CFG is looking at the language "inside-out".

---
Tags: pushdown-automata
---


title: Complexity of multiplying 3 matrices

text:
# Question
Title: Complexity of multiplying 3 matrices
There are algorithms that speed up matrix multiplication over the naive $n^3$ algorithm. But supposing you have 3 matrices $A$, $B$ and $C$, is there a way to compute $ABC$ that is asymptotically faster than first computing $AB$ and then computing $(AB)C$? Let's assume the matrices are square and dense.

This question was inspired by this post on math stack exchange.

# Answer
No. If you can multiply two $n \times n$ matrices in time $O(f(n))$ then you can also multiply three matrices $A,B,C$ in the same asymptotic running time by first computing $M=AB$ and then $MC$.

Conversely, if you can multiply three matrices in time $O(f(n))$ then you can also multiply two matrices in the same asymptotic running time by letting one of the matrices be the identity matrix.
> 1 votes

---
Tags: matrix-multiplication
---


# Question
Title: Could this novel algorithm be qualified to be published in Nature or Science
I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also supports negative weights and helps check the negative weight cycle.

The runtime ratio is `SPFA : Mine : Bellman-Ford = 5 : 11 : 90` in the python test case. Since the algorithms Bellman-Ford and SPFA are basic and widely used, I want to know whether this algorithm is qualified to be published in Nature or Science or not?

The principle uses two swapped and scrolling queues of relaxed vertices and two arrays of vertice weights inspired by Bellman-Ford and SPFA. You wouldn't get my point if you are not familiar with Bellman-Ford and SPFA. I would certainly explain the detailed principle in the paper but not here because it takes pictures and long words.

For example, AB = 2, AC = 1, CD =1, BD = 2

```
A
⬇ ↘
C   B
⬇ ↙
D

```

```
A B C D
-------
0 ∞ ∞ ∞
  2 1
      2

```

In the last table at vertice D, its `2` is got from 4(BD) first, and changed to 2(CD) next. Besides, each row index represents the edge number of the path.

Python code:

```
from collections import deque
import time
import random

class Edge:
    def __init__(self, from_vertex, to_vertex, weight):
        self.from_vertex = from_vertex
        self.to_vertex = to_vertex
        self.weight = weight

class MyQueue:
    def __init__(self, count):
        self.vertices = deque()
        self.statuses = [False] * count

    def __contains__(self, i):
        return self.statuses[i]

    def offer(self, i):
        self.statuses[i] = True
        self.vertices.append(i)

    def poll(self):
        if self.vertices:
            res = self.vertices.popleft()
            self.statuses[res] = False
            return res
        return None

    def any(self):
        return bool(self.vertices)

    def none(self):
        return not self.vertices

def mine(edges, n, source_vertex, k):
    current = [float('inf')] * n
    following = [float('inf')] * n

    current_level_queue = MyQueue(n)
    next_level_queue = MyQueue(n)

    current_level_queue.offer(source_vertex)
    current[source_vertex] = 0
    following[source_vertex] = 0
    round = 0

    while True:
        from_vertex = current_level_queue.poll()
        if from_vertex is None:
            continue

        for edge in edges[from_vertex]:
            new_dist = current[edge.from_vertex] + edge.weight
            if new_dist >= following[edge.to_vertex]:
                continue

            following[edge.to_vertex] = new_dist
            if edge.to_vertex not in next_level_queue:
                next_level_queue.offer(edge.to_vertex)

        if current_level_queue.any(): continue

        if next_level_queue.none(): break

        round += 1

        if round == n:
            raise ValueError("Graph contains a negative weight cycle.")

        if round == k: break

        tmp = current_level_queue
        current_level_queue = next_level_queue
        next_level_queue = tmp

        current = following.copy()

    return following

def bellman_ford_with_limited_edges(edges, n, src, k):
    current = [float('inf')] * n
    current[src] = 0
    following = [float('inf')] * n

    for i in range(k):
        following[src] = 0
        is_updated = False

        for edge in edges:
            if current[edge.from_vertex] < float('inf') and following[edge.to_vertex] > current[edge.from_vertex] + edge.weight:
                following[edge.to_vertex] = current[edge.from_vertex] + edge.weight
                is_updated = True

        if not is_updated: break

        assert i != n, "Graph contains a negative weight cycle"

        current = following.copy()

    return following

def spfa(edges, vertices_count, source_vertex):
    weights = [float('inf')] * vertices_count
    in_queue = [False] * vertices_count
    queue = deque()

    weights[source_vertex] = 0
    queue.append(source_vertex)
    in_queue[source_vertex] = True

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for edge in edges[u]:
            new_dist = weights[u] + edge.weight
            if new_dist >= weights[edge.to_vertex]:
                continue
            weights[edge.to_vertex] = new_dist

            if in_queue[edge.to_vertex]:
                continue
            queue.append(edge.to_vertex)
            in_queue[edge.to_vertex] = True

    return weights

edges = []

vertex_count = 4000

for i in range(vertex_count):
    for j in range(i + 1, min(i + 100, vertex_count)):
        weight = random.randint(1, 100)
        edges.append(Edge(i, j, weight))
        edges.append(Edge(j, i, weight))

grouped_edges = [deque() for _ in range(vertex_count)]
for edge in edges:
    grouped_edges[edge.from_vertex].append(edge)

src = vertex_count // 2

print("Whether my my result equals to Bellman-Ford:")
myRet = mine(grouped_edges, vertex_count, src, 20)
bellman_ford_ret = bellman_ford_with_limited_edges(edges, vertex_count, src, 20)
print("When edge number is limited to {}: {}".format(20, myRet == bellman_ford_ret))

myRet = mine(grouped_edges, vertex_count, src, 30)
bellman_ford_ret = bellman_ford_with_limited_edges(edges, vertex_count, src, 30)
print("When edge number is limited to {}: {}".format(30, myRet == bellman_ford_ret))

myRet = mine(grouped_edges, vertex_count, src, vertex_count)
bellman_ford_ret = bellman_ford_with_limited_edges(edges, vertex_count, src, vertex_count)
print("When edge number is unlimited: {}".format(myRet == bellman_ford_ret))

print("\nRuntime ratio of unlimited edges:")

start_time = time.time()
mine(grouped_edges, vertex_count, src, vertex_count - 1)
end_time = time.time()

print("Mine: {:.2f} seconds".format(end_time - start_time))

start_time = time.time()
bellman_ford_with_limited_edges(edges, vertex_count, src, vertex_count - 1)
end_time = time.time()

print("Bellman-Ford: {:.2f} seconds".format(end_time - start_time))

start_time = time.time()
spfa(grouped_edges, vertex_count, src)
end_time = time.time()

print("SPFA: {:.2f} seconds".format(end_time - start_time))

```

Kotlin code

```
import java.util.*
import kotlin.math.min
import kotlin.time.measureTime

data class Edge(val from: Int, val to: Int, val weight: Int)

fun bellmanFordWithLimitedEdges(edges: List<Edge>, n: Int, src: Int, isWarmUp: Boolean, k: Int): IntArray {
    var current = IntArray(n){ Int.MAX_VALUE }
    current[src] = 0
    val next = IntArray(n){ Int.MAX_VALUE }

    for (i in 0..< k) {
        next[src] = 0
        var isUpdated = false

        for ((from, to, dist) in edges) {
            if (current[from] < Int.MAX_VALUE && next[to] > current[from] + dist) {
                next[to] = current[from] + dist
                isUpdated = true
            }
        }

        if (!isUpdated) {
            if (!isWarmUp) println(i)
            break
        }
        require(i != n){
            "Graph has a negative weight cycle!"
        }

        current = next.clone()
    }
    return next
}

fun spfa(edges: List<List<Edge>>, verticesCount: Int, sourceVertex: Int): IntArray {
    val distances = IntArray(verticesCount) { Int.MAX_VALUE }
    val inQueue = BooleanArray(verticesCount) { false }
    val queue: Queue<Int> = LinkedList()

    distances[sourceVertex] = 0
    queue.offer(sourceVertex)
    inQueue[sourceVertex] = true

    while (queue.any()) {
        val u = queue.poll()
        inQueue[u] = false

        for ((_, to, weight) in edges[u]) {
            val newDist = distances[u] + weight
            if (newDist >= distances[to]) continue
            distances[to] = newDist

            if (inQueue[to]) continue
            queue.offer(to)
            inQueue[to] = true
        }
    }
    return distances
}

class MyQueue(count: Int){
    private val vertices = LinkedList<Int>()
    private val statuses = BooleanArray(count)

    operator fun contains(i: Int): Boolean = statuses[i]

    fun offer(i: Int){
        statuses[i] = true
        vertices += i
    }

    fun poll(): Int {
        val res = vertices.poll()
        statuses[res] = false
        return res
    }

    fun any(): Boolean = vertices.any()
    fun none(): Boolean = vertices.none()
}

fun myImpl(edges: List<List<Edge>>, verticesCount: Int, sourceVertex: Int, isWarmUp: Boolean, k: Int): IntArray {
    var currentLevelVerticeInfo = IntArray(verticesCount){ Int.MAX_VALUE }
    val nextLevelVerticeInfo = IntArray(verticesCount){ Int.MAX_VALUE }

    var currentLevelQueue = MyQueue(verticesCount)
    var nextLevelQueue = MyQueue(verticesCount)

    currentLevelQueue.offer(sourceVertex)
    currentLevelVerticeInfo[sourceVertex] = 0
    nextLevelVerticeInfo[sourceVertex] = 0
    var round = 0

    while (true) {
        val from = currentLevelQueue.poll()

        for ((_, to, weight) in edges[from]) {
            val newDist = currentLevelVerticeInfo[from] + weight
            if (newDist >= nextLevelVerticeInfo[to]) continue

            nextLevelVerticeInfo[to] = newDist

            if (to !in nextLevelQueue)
                nextLevelQueue.offer(to)
        }

        when{
            currentLevelQueue.any() -> continue

            nextLevelQueue.none() -> break

            ++round == verticesCount -> error("Graph contains a negative weight cycle.")

            round == k -> break

            else -> {
                currentLevelQueue = nextLevelQueue.also { nextLevelQueue = currentLevelQueue }
                currentLevelVerticeInfo = nextLevelVerticeInfo.clone()
            }
        }
    }

    if (!isWarmUp) println(round)
    return nextLevelVerticeInfo
}

fun main() {
    val edges = mutableListOf<Edge>()

    val vertexCount = 4000

    for (i in 0..< vertexCount) {
        for (j in i+1..< min(i+100, vertexCount)) {
            val weight = (1..100).random()
            edges += Edge(i, j, weight)
            edges += Edge(j, i, weight)
        }
    }

    val groupedEdges = MutableList(vertexCount){ LinkedList<Edge>() }
    edges.forEach {
        groupedEdges[it.from] += it
    }

    val src = vertexCount / 2

    check(
        bellmanFordWithLimitedEdges(edges, vertexCount, src, true, 20).toList() ==
                myImpl(groupedEdges, vertexCount, src, true, 20).toList()
    )

    check(bellmanFordWithLimitedEdges(edges, vertexCount, src, true, vertexCount).toList() ==
            myImpl(groupedEdges, vertexCount, src, true, vertexCount).toList()
    )

    // warm up
    repeat(5){
        bellmanFordWithLimitedEdges(edges, vertexCount, src, true, vertexCount)
        spfa(groupedEdges, vertexCount, src)
        myImpl(groupedEdges, vertexCount, src, true, vertexCount - 1)
        measureTime {  }
    }

    measureTime {
        bellmanFordWithLimitedEdges(edges, vertexCount, src, false, vertexCount)
    }
    .let{ println("${::bellmanFordWithLimitedEdges.name}: $it") }

    measureTime {
        spfa(groupedEdges, vertexCount, src)
    }
    .let{ println("spfa: $it") }

    measureTime {
        myImpl(groupedEdges, vertexCount, src, false, vertexCount - 1)
    }
    .let{ println("myImpl: $it") }
}

```

# Answer
> 2 votes
I recommend you write it up, prove its correctness and running time, state explicitly the dataset you used for your experiment, as well as your assumptions about the dataset.

Then upload it to Arxiv. I would personally skip Nature and Science and rather aim at an actual algorithms journal. Perhaps even better is a conference where you can present the results first and discuss with peers.

Look at SEA (Symposium for Experimental Algorithms) or ALENEX or others.

Remember to write your paper in a similar style as papers in the aforementioned conference proceedings, as unusual styles or formatting is the easiest way of getting (desk) rejected. Do a proper lit review first.

# Answer
> 1 votes
I very much doubt this is suitable for publication in Nature or Science.

Theoretical computer scientists will care about proofs of correctness and the best provable upper bound on the worst-case running time. Until you have that, you don't have much, and it is unlikely that researchers will pay attention.

I don't believe your claim about "runtime ratio". Surely that depends on the graph (or distribution on graphs), so if you give me a fixed ratio like 5 : 11 : 90, I simply do not believe it, and I will assume that you have misunderstood something.

You haven't defined what "transfers" are.

We're not a coding site, so we don't review code here. Researchers will be interested in concise pseudocode and clear proofs of why it is correct.

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


# Question
Title: What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long string using a deterministic polynomial time compression algorithm.

As far as I understand, such a machine would be a $BPP$ machine, even though the source of bits is not necessarily a random number generator.

In this case the amount of independent bits is polynomial. I suppose, if we allow only a constant amount of independent bits (e.g. how it happens with most existing PRNGs using system time - a fixed length independent string - for a seed) then the PRNG gives no extra computation power. However, can it be above constant and still keep the machine equal to a polynomial time deterministic machine?

# Answer
> 1 votes
I think there must be some confusion in the problem setting. Given an input of $n$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average shorter than $n$ bits. This is a pure information theoretic fact, that holds regardless of how much computation power you throw at the problem. So I think your formulation in terms of compression is not accurately capturing what you actually care about.

---

Any program that uses only a random seed of length $O(\log n)$ can be derandomized, by trying all $2^{O(\log n)}=O(\text{poly}(n))$ possibilities for the seed. So a seed length of up to $O(\log n)$ bits does not add extra power.

It is an open question to what extent derandomization is possible. There is work relating derandomization and the existence of pseudorandom generators, which might be of interest to you.

---
Tags: complexity-theory, time-complexity, randomized-algorithms, randomness, probabilistic-algorithms
---


title: Uniform-cost Search Problem

text:
# Question
Title: Uniform-cost Search Problem
Suppose that we take an initial search problem and we add $c \> 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?

Definitions: Uniform-cost search is also known as lowest cost first. Initial search problem can be any graph with a start and a goal state. You just apply the uniform cost search algorithm on the graph.

# Answer
The shortest path may indeed change. This is not because of some property of the uniform cost search, but rather, the property of the graph itself. Note that adding a constant positive cost to each edge affects more severely the paths with more edges. Here is an example, where the shortest path has cost $5$:
Adding a cost of $1$ to each edge changes the shortest path in the graph as:
The original shortest path has a new cost of $10$, whereas the other path has a cost of only $9$. Therefore, any optimal shortest path algorithm, such as Dijkstra's or uniform cost search, will find a different shortest path.

The shortest path will not change if it also has the least number of paths among all paths from source to destination. If the shortest distance is $d\_{min}$ and $k\_1$ edges, and there is some other path with distance $d\_{min} + \Delta$ with $k\_2$ edges ($k\_2 \< k\_1$), it can be shown that adding any $c \> \frac{\Delta}{k\_1 - k\_2}$ to all the edges will change the shortest path, and therefore your result.

*Scaling* the edges by a constant positive factor (multiplying all edges by $c\>0$) will not change the shortest path.
> 6 votes

# Answer
The answer is no, solutions may differ. If suppose your optimal solution in a graph was $s \in \mathbb{R}$ for a path of length $\ell$. If you add $c \> 0$ to all edges, this new path will get cost $s + \ell c$.

If there is a different (worse) solution of cost $s - \epsilon$, where $0 \< \epsilon \< c$, and with a path length $\< \ell$, you will now get an alternate solution of cost $\leq s + \epsilon + (\ell - 1) c$ which is less then the optimal solution before adding $c$ to every edge.
> 2 votes

# Answer
A more intuitive example. Optimal path changed from ABCDE to AE after addition of the cost of each step
> 0 votes

---
Tags: graphs, search-algorithms, search-trees, search-problem
---


# Question
Title: Visiting all nodes of a directed graph exactly once (not dfs)
Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should go back to it's parent node and try other paths. But what's an algorithm that doesn't get back to the parent node at all and just traverse each node once. Consider someone who is going different places(as nodes of a graph) and can only use path given in the problem. But when he visits someplace, can't go back there no matter what.

I tried DFS on different nodes (minimum in\_degree,... ) , topological sorting nodes, tried to find MST but nothing worked. Is there any greedy way you can think about? (considering such a way exist for this problem)

# Answer
> 2 votes
You are asking for a Hamiltonian Path (or a Hamiltonian cycle if you need to return to your original starting point).

https://en.wikipedia.org/wiki/Hamiltonian\_path

It is NP-hard to determine whether a graph has such a Path. That is, there is no known polytime algorithm for it, and if you are trying to code up your own solution, you basically should perform a brute-force backtrack search through all possibilities. There will not be a greedy way to solve this with full certainty.

It is a well-studied problem and you might be able to find some implementations or libraries that have this function or approximations of it.

---
Tags: greedy-algorithms, minimum-spanning-tree, hamiltonian-path
---


# Question
Title: Complexity of satisfiability for relational logic on the booleans
I know that propositional satisfiability is NP-complete and that if I add first-order quantifiers I get the complete problems for the polynomial hierarchy and PSPACE. What happens if my formulas are relations $R(x\_1,...,x\_n)$ over boolean variables?

# Answer
In NP I could guess the disjunctive normal form of the formulas, that would look like

$\bigwedge\_i R\_i(x\_1^i, \ldots, x\_{n(i)}^i) \land \bigwedge\_j \lnot R\_j(x\_1^j, \ldots, x\_{m(j)}^j)$

The question is then how to decide satisfiability of this term.

One could then take the relation to be the tuple of variables with which they appear in the formula and reduce the problem to finding a satisfying solution of terms of the form $\lnot (x\_1 = x\_3 \land x\_2 = x\_4)$ where $R(x\_1,x\_2)$ and $\lnot R(x\_3, x\_4)$ occur in the formula above. There are $O(n^2)$ such terms thus the problem remains in NP.
> 0 votes

# Answer
Nothing much changes. Every relation $R(x\_1,\dots,x\_n)$ is equivalent to $\exists t\_1,\dots,t\_m . \varphi(x\_1,\dots,x\_n,t\_1,\dots,t\_m)$ for some fresh variables $t\_1,\dots,t\_m$ (see the Tseitin transform). Consequently:

Satisfiability remains NP-complete. In particular, satisfiability of $R(x\_1,\dots,x\_n)$ is equivalent to satisfiability of $\varphi(x\_1,\dots,x\_n,t\_1,\dots,t\_m)$.

Checking formulas with first-order quantifiers remains PSPACE-complete. In particular, the formula $\forall \cdots \exists . R(x\_1,\dots,x\_n)$ is equivalent to $\forall \cdots \exists . \exists t . \varphi(x\_1,\dots,x\_n,t\_1,\dots,t\_m)$, so the problem is in PSPACE, and it is obviously PSPACE-complete as every formula is itself a relation.

Tautology becomes harder. Tautology of a CNF formula $\varphi$ is $\forall x . \psi(x)$, which is NP-complete. Tautology of a binary relation $R$ is $\forall x . R(x)$, which is equivalent to $\forall x . \exists t . \varphi(x,t)$, which is believed to be harder than $\forall x . \psi(x)$ (NP-complete) or $\exists x . \psi(x)$ (co-NP-complete) \[unless the polynomial hierarchy collapses\].
> 1 votes

---
Tags: complexity-theory, logic, satisfiability
---


# Question
Title: (Co)-induction, fixpoints and inference systems
I'm learning about induction and co-induction. From what I know, given a set of judgments $U$ and an inference system $\Phi \subseteq \wp(U) \times U$, where $(\left\\{ h\_1,\dots,h\_n \right\\}, c) \in \Phi$ stands for the rule $\frac{h\_1 \quad \dots \quad h\_{n}}{c}$, we can define the function:

$ F\_{\Phi}(X) = \left\\{ c \mid \exists (H, c) \in \Phi \\;.\\; H \subseteq X \right\\}, $

and the least fixpoint $\mu F\_{\Phi}$ is the set of all judgments that have a finite proof in $\Phi$.

The induction principle states that $F\_{\Phi}(X) \subseteq X \Rightarrow \mu F\_{\Phi} \subseteq X$. It is a consequence of the Knaster-Tarski theorem, which requires that $F\_{\Phi}$ be monotone.

However, not all inference systems seem to be monotone; they would be if they contained "identity" rules of the form $(c,c)$ for all $c \in U$. For instance, take $U = \left\\{ 0,1 \right\\}$ and $\Phi = \left\\{ \frac{}{0}, \frac{0}{1} \right\\}$: $F\_{\Phi}(\varnothing) = {0}$ and $F\_{\Phi}(\\{1\\}) = \varnothing$, so $F\_{\Phi}$ is not monotone.

On the other hand, if an inference system has identity rules then co-induction is meaningless, since the greatest fixpoint of $F\_{\Phi}$ is $U$ in that case.

There's clearly some flaw in my understanding, I would be grateful if somebody could point out my mistakes.

# Answer
> 0 votes
Intuitively, you can see that $F\_\Phi(X)$ is monotone in $X$ by carefully looking at the body of the definition

$$ \exists (H, c)\in \Psi,\ H\subseteq X$$

If there is an $H, c$ with $H\subseteq X$, then definitely the same $H$ will work if $X$ is taken to be larger!

You are correct about the identity deduction rules making co-induction trivial.

---
Tags: logic, fixed-point, coinduction
---


# Question
Title: Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.

Any subarray `array[start, end]` with `0 <= start <= end < n` will have a unique element. The algorithm will return :

* `True` for `array = [1, 3, 5, 3, 1]`
* `False` for `array = [1, 3, 5, 3, 5]` because the sequence `[3, 5, 3, 5]` does not contain any unique element.

My idea (that does not seem to work in the competition) is to use divide and conquer as following :

* Create the following hash map : `hash map[element] = [list of the index of the element in the array]`
* Considering a recursive function that use `start` and `end` as array bounds
* Then iterating though the keys, and as soon as it finds, using the hash map, an element that is unique (only one index is in the range `[start; end]`), the index will be used as a `pivot`
* Recursively calling the function on `array[start;pivot-1]` and `array[pivot+1; end]`

As a subsequence can be the whole array, the array must contain one unique element. Then if each side of the pivot respect the condition, any subarray that contains the pivot obviously contain a unique element.
I simply want to know the my reasoning is valid. If yes, it means the problem comes from my code. Any thoughts ?

# Answer
Pivot is unique in the whole array, therefore every sub array containing pivot contains a unique item. Subarrays not containing pivot are the subarrays of the array from start to pivot-1 and the subarrays of the array from pivot+1 to end.

In case you have more than one unique item, say at pivot1, pivot2 and pivot3, you would examine start to pivot1-1, pivot1+1 to pivot2-1 and so on.

Yes, your argument is correct.
> 1 votes

---
Tags: algorithms, complexity-theory, recurrence-relation, hash, divide-and-conquer
---


# Question
Title: Is Determining the Number of distinct Prime Factors Polynomial?
Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. But since 3 is repeated, we only count it once.

But what about a slightly easier problem---finding how many prime factors a number has. Is there an efficient algorithm to do such a task?

In the 18 case, we still don't double count 3. So our algorithm should output 2 (the two prime factors are 3 and 2).

# Answer
> 6 votes
No problem involving factorization is known to be polynomial time, and these problems (formulated as decision problems in any reasonable way) are suspected to be NP-intermediate. The only problem which is known to be polynomial time is primality testing.

# Answer
> 0 votes
It’s easy to find small prime factors. Pollard-rho can find a factor p in $O(\sqrt p)$ which finds many prime factors. And for large n with no known small prime factors we can do a primality test which finds there is one factor only.

The problem is when n is so large that we cannot prove there are no factors up to $n^{1/3}$ so we don’t know if there are 2 or 3 prime factors.

---
Tags: number-theory, primes, factoring
---


# Question
Title: Max flow, min cost with upper and lower bounds
I am trying to implement an algorithm that fairly distributes people into groups, given their ranking of those groups, while also taking into account their preference for partners.

I have modeled this as a directed graph with upper and lower bounds and costs on edges representing their ratings. Finding a solution would simply mean maximizing the flow between a source and a drain.

However finding an algorithm that can actually solve this has proven difficult. The only one I came across that seems to match all my requirements is the Out-Of-Kilter algorithm.

Literature about this algorithm is very sparse and dense though. I could also not find a good implementation of it.

I found this one https://github.com/MichalNowicki/NumericalAlgebraCodes but it seems to have some errors, since it produces solutions that do not conserve flow.

What am I missing here? Is there an easier algorithm? Is there a good implementation somewhere out there?

Any help would be greatly appreciated.

# Answer
> 0 votes
If I understand correctly, your problem can be formulated as a minimum cost flow problem, but with lower bounds (demands) on the flow through each edge.

For details how to handle the lower bounds, see Determine whether a flow can satisfy node demands in a directed acyclic graph or the corresponding part of Jeff Erickson's Algorithms textbook; or see Network flow - minimum flow through edge.

---
Tags: network-flow
---


# Question
Title: What is the name of the diagram used in JSON spec for representing a context-free language?
If you go to the JSON spec page : https://www.json.org/json-en.html, then you'll see the language represented by some diagrams showing graphically what the language looks like. I wondered, does this kind of diagram has a name ?

# Answer
It's called a "syntax diagram", "syntax chart", or "railroad diagram".

Of these three, "syntax diagram" is the most common term. They're sometimes called "Pascal syntax diagrams" because the first time that most people saw them was in the 1973 Pascal report.

I can't find a definitive source to back this up, but it wouldn't surprise me if Niklaus Wirth invented them.
> 4 votes

---
Tags: context-free
---


# Question
Title: What is a real life analogy of busy waiting by process "i" when "turn=i"?
```
#define N 2
#define TRUE 1
#define FALSE 0

int flag[N]={FALSE}
int turn;
void process(int i)
{
    int j=NOT(i);
    while(1)

    {
        a) NON-Critical Section();
        b) flag[i]=TRUE;
        c) turn=i;
        d) while(flag[j]==TRUE && turn==i)
        {
            //wait
        }
        e) Critical section
        f) flag[i]=FALSE;
    }
}

```

While I can trace the solution and verify it works, what's confusing is probably the name of variables or the way they're used.

when turn==i , why should process"i" wait? That just sound ridiculous to me.

Can you give a real life analogy to this? If turn==i then i should enter the critical section is what I think logically because it's his turn.

Maybe it's the variable name?

# Answer
> 0 votes
Alternative representations of this algorithm use variables `victim` rather then `turn` and `level` rather than `flag`. This algorithm ensures mutual exclusion because it employs the Peterson's principles inductively, that is, there is a competition on some level $j$ and at most one process is stopped from accessing the level $j+1$. Applying this idea for each competition enforces at most one process will enter CS. Consequently, the idea is that the `victim` process at level $j$ is forced to wait and loses the chance to enter the next competition on level $j+1$. CS corresponds to the competition at the topmost level.

---
Tags: operating-systems, synchronization
---


# Question
Title: Does the Halting Problem Explain the Fermi Paradox?
The Fermi Paradox asks why we have not yet encountered other intelligent life given the high chance of intelligent life emerging.

I recently had the following thought:

Evolution shapes the behaviour of an organism so that the organism behaves in ways that increase the organism's chance of survival.

When evolution created humans, it created a being that possessed general intelligence, or put another way, a Turing machine in its head.

We know from the halting problem that we cannot, in general, determine if a Turing machine will halt. In other words, the behaviour of Turing machines is, in general, unpredictable.

Since a human is a Turing machine, its behaviour is, in general, unpredictable. This means that evolution can no longer alter the human code in ways that are guaranteed or likely to work. Thus evolution can not longer "adapt" humans. As evolution can no longer reliably adapt humans to their environment, humans will go extinct.

In general, once life becomes intelligent, evolution loses control of it, and thus can no longer shape it to be adaptive.

# Answer
> 0 votes
I don't find this argument persuasive, but it sounds like a matter of opinion. I'm not sure this is a matter of computer science -- it sounds speculative and a matter of opinion to me.

I have a problem with the way the word "unpredictable" is used. The halting problem tells us that there is no algorithm that can always predict the outcome of a Turing machine. There might still be algorithms that can do so some of the time, or even most of the time. The halting problem only tells us that the algorithm cannot work 100% of the time, but it still remains possible that some algorithm might work 99% of the time.

I don't think it follows that evolution is unable to alter the human code in ways that are likely to work. Of course there are no guarantees, but evolution can still change us, and it's entirely consistent with everything we know about computer science that those changes might be more likely to be positive (specifically, enhance survival and reproduction) than negative.

There is plausible evidence of evolution affecting humans recently, and specifically in the period after humans have been able to think. For instance, it is plausible that there have been changes to malaria resistance, starch digestion, lactose digestion, eye color, skin color, hair color, hair shape, sweat glands, protection from disease, and more in the past few ten thousands of years. Whether or not this has actually happened, hopefully those examples point to a gap in your logic. It seems quite plausible that evolution could have changed us in those ways. I see no reason that the halting problem would render such evolutionary changes impossible.

Moreover, even if it were true that humans were unable to evolve further, I don't think it follows that humans would inevitably go extinct. For instance, I've read that some sharks and crocodiles seem to have been around for 80-150 million years, with few changes by evolution.

Ultimately, most of this does not appear to be a matter of computer science, so I'm not sure whether the question is appropriate here. Perhaps I should not have posted this answer.

---
Tags: halting-problem
---


# Question
Title: Are there associative cryptographic / collision resistant hashes?
Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key.

For content `c` with length `l(c)`, `SHA(c)` can be computed in time `O(l(c))` and uses constant space.

I am curious if there are hashes with a similar extremely low probability of collision that can be considered to be "associative".

What do I mean by "associative"?

I am looking for something with an additional constraint over SHA. Given any bisection of `c` in to two parts `c_l, c_r`, which can be recombined so `c = c_l + c_r`, I want a hash `H` that is able to compute `H(c)` based on `H'(c_l)` and `H'(c_r)`. I'm writing `H'` here because perhaps it is necessary for there to be some intermediate hashed value from which a final hash is computed.

`H'` should also require time linear to the content and have constant space.

---

The use case of this is that I have a tree with content in the leaves and intermediate hash values (the H\` results) in its nodes. I want to be able to compute the root hash over all of the elements. But I want the root hash to be equal for all trees that have the same order of elements.

```
      a          b

     H'          H'
    /  \        /  \
   H'   3      1   H'
  /  \            /  \
 1    2          2    3

```

Trees `a` and `b` should have the same root hash because while they have different structure, they have the same leaves in the same order.

More specifically, I want to be able to compute the hash of the leaf elements of a BTree based on partial hashes stored in its non leaf nodes. The root node's hash should be equal for all trees that have the same leaf elements, regardless of the exact structure of the tree.

---

Ideally this hash scheme would be "cryptographic" in that it is impractically costly to engineer content that deliberately causes a collision. However, this is not a hard requirement.

Also, if no such linear time and constant space sceheme exists, then log time and log space could be acceptable.

Thank you!

# Answer
There is a plausible construction of such a hash. At design time, randomly choose two $2\times 2$ matrices with entries in $\mathbb{F}\_{2^n}$ that have determinant 1, fix them, and call them $h(0),h(1)$. Then, for any string $x \in \\{0,1\\}^\*$, define

$$h(x\_1 \cdots x\_k) = h(x\_1) \times \cdots \times h(x\_k),$$

where the product is of $2 \times 2$ matrices with entries in $\mathbb{F}\_{2^n}$.

Then, the hash of a tree can be defined as the result of hashing the concatenation of all leaves, in left-to-right order. You can store, in each internal node, the hash of the leaves under it, which allows you to efficiently update the hash of the tree as you insert or delete into the tree.

For security, I suggest choosing $n \ge 256$. For example, for $n=256$, the output of the hash is 1024 bits long (though it can be compressed to 768 bits by using the fact that the matrix has determinant 1). Of course, for equality checking, it's enough to store the SHA256 hash of the output of $h(\cdots)$, which is even shorter.

As far as I can tell, there are no known attacks in the literature on such a scheme, so this scheme seems like it might be cryptographically collision-resistant -- though the security of such schemes appears to be quite tricky, and I am not an expert on this subject, so there might be fatal flaws in the scheme that I am unaware of.

References:

---

Separately: I also encourage you to check out Canonical representation of finite maps on non-overlapping finite rational intervals and Can ropes (AVL trees) be interned?, which address closely related problems, and might suggest alternate approaches to your problem.
> 9 votes

---
Tags: algorithms, hash
---


# Question
Title: How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?
$\mathsf{RP}$ can be deterministically defined as:

> A language $L\in\mathsf{RP}$ iff there exists a polynomial $p$ and deterministic Turing machine $M$, such that:
>
> * $M$ runs for polynomial time $p$ on all inputs,
> * $\forall x \in L$, the fraction of strings $y$ of length $p(\vert x\vert)$ which satisfy $M(x, y) = 1$ is greater than or equal to $\frac1 2$,
> * $\forall x \not\in L$, and all strings $y$ of length $p(|x|)$, $M(x, y) = 0$

In contrast, $\mathsf{UP}$ can be defined as:

> A language $L\in \mathsf{UP}$ if there exists a two-input algorithm $A$ and a constant $c$ such that:
>
> * $x \in L\Rightarrow\exists! y:${$\vert y\vert = \mathcal O(\vert x\vert^c),A(x,y) = 1$},
> * $x \not\in L\Rightarrow\not\exists y:${$\vert y\vert = \mathcal O(\vert x\vert^c), A(x,y) = 1$},
> * algorithm $A$ verifies $L$ in polynomial time.

Therefore, a satisfying $L\in\mathsf{RP\cap UP}$ would have to satisfy both:

> * the fraction of strings $y$ of length $p(\vert x\vert)$ which satisfy $M(x, y) = 1$ is greater than or equal to $\frac1 2$,
> * $\exists! y:${$\vert y\vert = \mathcal O(\vert x\vert^c),A(x,y) = 1$}

It seems these are mutually exclusive requirements. So, how does it happen that $\mathsf P$, a class containing satisfying languages, contains only such languages?

# Answer
> 2 votes
The $\mathsf{RP}$ machine and the $\mathsf{UP}$ machine don't have to be the same. That is, there might be one machine which shows that $L \in \mathsf{RP}$, and another one which shows that $L \in \mathsf{UP}$.

As an example, every language in $\mathsf{P}$ lies in $\mathsf{RP} \cap \mathsf{UP}$. The easiest way to see this is to take the advice string to be empty, but if you insist that the advice string have size $|x|$, say, then you can construct an $\mathsf{RP}$ machine which ignores the advice and just runs the $\mathsf{P}$ machine, and a $\mathsf{UP}$ machine which runs the $\mathsf{P}$ machine and only accepts if the advice is the all-zero string.

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


title: Guess the output of a c program

text:
# Question
Title: Guess the output of a c program
I have come across a c program like this .

```
int main()
{
  int a,i=4;
  int z=5;
  a=--i+ --i+ --z;
  printf("%d %d",a,i);

  return 0;
}

```

What will be the output? I need some explanation.

# Answer
Just to make it tidy.

```
int main() {
    int a, i = 4;
    int z = 5;
    a = --i + --i + --z;
    printf("%d %d", a, i);

    return 0;
}

```

As gnasher729 said, it is undefined (by the standard)

This means it is entirely compiler-dependent.

But, you said to take a guess. Working left to right, the following has a certain logic to it:

1. “- - i”: this decrements i before its value is used. So, it becomes 3.
2. “- - i”: this again decrements before it is used. So “i” is now 2.
3. “- -z”: “z” is decremented before use. So, “z” becomes 4.
4. “a” = 3+2+4 = 9
5. printf("%d %d", a, i) will print i and z, therefore 2 and 9

After using 3 compilers, I got the answer 3 times of 2 and 8.

That gives a better idea of undefined.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: What is the hit rate of the cache when executing this code?
C++ code:

```
int main()
{
short int arr[4][4];
for (int i = 0; i < 8; i++)
{
  for (int j = 0; j < 8; j++)
  {
    arr[i][j] = i+j;
  }
}
return 0;
}

```

Is there going to be a difference in hit time if it is loading data from arrays or storing data into array. For example for `arr[i][j] = i+j;` and `a = arr[i][j];` ?

Also what is difference in hit time if it is `arr[j][i] = i+j;`

# Answer
Your program will most likely crash because you access non-existing array elements.
> 1 votes

---
Tags: memory-management, mips, caching
---


# Question
Title: Shortest Hamiltonian Path in a Complete Graph
I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm in P. Being in a complete graph does give the knowledge that a Hamiltonian path exists in the first place.

My guess is that if such an algorithm exists, it will be some modification of a DFS or potentially modifying a minimal spanning tree in some way to arrive at the solution.

# Answer
It is NP-hard. It is as hard as the standard Hamiltonian path problem (testing the existence of a Hamiltonian path in an arbitrary graph).

Here is the reduction. Suppose you have an arbitrary graph $G$, with no edge weights/lengths, and we want to know whether it has a Hamiltonian path or not. Treat every edge of $G$ as having length 1. Then, add all missing edges, but with edge length of some huge number (larger than $|V|$, the number of vertices in $G$), so now you have a complete graph. Suppose you had an efficient way to find the shortest Hamiltonian path in any complete graph. Then you could find the shortest Hamiltonian path in this complete graph. If its total length is less than $|V|$, then it is a Hamiltonian path for $G$ (it obviously can't include any of the huge-length edges); if its total length is $\ge |V|$, then $G$ has no Hamiltonian path.

Your problem is almost the same as the Travelling Salesman Problem, but for a path instead of a cycle.
> 0 votes

---
Tags: shortest-path, weighted-graphs, hamiltonian-path
---


# Question
Title: Find Minimum Transformation Between Multisets of Lists of Cards
**Brief:** I have two configurations, `a` and `b`, of the same set of Rummikub tiles (`a` may not be a valid Rummikub config) and want to find the fewest number of pickup-\>place tile operations to transform `a` into `b`.

**Type Definitions:**

* `C = Pair<int, int>`: Card represented as a suit and value pair.
* `CL = List<C>`: Card list.
* `S = MultiSet<CL>`: A collection of card lists.

**Problem Statement:** You are given two collections `s0`, `s1`, and one card list `h`. (`s0 union {h}` = `a` and `s1` = `b`) Find a minimum number of "move" operations needed to convert `s0 union {h}` into `s1`. Note, `s0 union {h}` will be a rearrangement of `s1`. That is, if you flatten `s0 union {h}` into a `CL` and similarly flatten `s1` into a `CL` then the two `CL` are equivalent up to permutation. Note, there is at most 3 copies of any `C` in `s1`.

**Move Operation:**

```
Move(C c,          // the card to move
     CL src,       // the CL to move c from
     CL dst,       // the CL to move c to
     int dstIndex) // the index in dst to insert c to

```

If `dst` is empty then this operation can be said to create `dst`. Similarly if, after the movement, `src` is empty then the operation can be said to delete `src`. Basically, creation and deletion of `CL`s is free and happens implicitly. I do not want to consider the creation of a `CL`, by itself, an operation. Only movement of cards is an operation.

**First attempt:** My first attempt at solving this was to linearize (i.e. flatten) `s0 union {h}` and `s1` and compute their edit distance using only insertions & deletions (insert & delete pairs form a move op). However, the total number of edit operations depends on the order between the `CL` in the linearization. Since I want the minimum number of edit ops I would need to check each permutation of `CL`s, right? Doing so is not tractable in my application since I may have collections containing 20 or more differing `CL`s.

**Additional Consideration:** If it helps, changing the type of `CL` to `Set<C>` is possible in my application. Basically, `s0` and `s1` could have inner type of `Set<C>`. But I've used `List<C>` since I'm unsure if, in intermediate steps of the solution, there would be a need to have duplicates in a `CL`. Note if `Set<C>` is used, then the `dstIndex` argument to `Move` is not needed. Also, I would prefer if the input `h` was only moved from and not moved to, but this is a soft requirement.

Any help or pointers in the right direction would be greatly appreciated!

# Answer
> 5 votes
I think the variant with sets can be solved using bipartite matching.

Build a complete bipartite graph, with one left vertex per set in s0 and one right vertex per set in s1. Also, if there are fewer sets in s0 than in s1, add additional left vertices, corresponding to empty sets, until both sides have the same number of vertices. The edge between a left vertex and a right vertex corresponding to sets $L,R$ is assigned the weight $-|L \bigtriangleup R|$, where $L \bigtriangleup R$ is the symmetric difference of $L,R$.

Find the maximum weight matching in this graph.

I believe that this minimizes the number of moves. In particular, if this matching has total weight $w$, then you can solve your problem with $w/2$ moves. If the matching associates a set $L$ in s0 and a set $R$ in s1, then in your problem, $L$ becomes $R$ after all move operations; each element in $L \setminus R$ is moved to its new destination (according to s1), and each element in $R \setminus L$ is moved from its original source (according to s0).

Please double-check my logic and try it on some examples to verify that it appears to work correctly.

---

As for your original problem with lists can, I suspect, be solved by using

$$-|L \bigtriangleup R| - \pi(L \cap R)$$

as the weight on the edge between $L,R$, where $|L \bigtriangleup R|$ denotes the number of items present in only one of $L,R$, and $\pi(L \cap R)$ denotes the number of moves needed to sort the items that are common to $L,R$ from the order given by $L$ into the order given by $R$. I don't know how to compute $\pi(\cdots)$, but Inuyasha Yagami appears to have explained how it can be computed.

(This is different from computing the number of swaps needed to re-order the items common to $L,R$, from the order in $L$ to the order in $R$. The number of swaps is analyzed in Rearrange an array using swap with 0 (see also Algorithm for generating sorting instructions, Sort array with minimum swaps, Minimum number of swaps in sorting sequence). However, you are asking about the number of moves, which is a different problem.)

It's particularly important to check my reasoning for this variant of the problem, as I have not checked this approach at all and it could easily be bogus.

---

My thanks to Inuyasha Yagami for multiple improvements and bugfixes to this answer.

# Answer
> 3 votes
Update (or possible correction) to the answer of D.W..

Since we are given the move operations and not the swap operations, we can compute $\pi$ in polynomial time. The problem is known as the permutation edit distance problem. $\pi(L,R) = |L| - |LCS(L,R)|$, where $LCS$ denotes the longest common subsequence, which can be computed in polynomial time.

---
Tags: algorithms, data-structures, optimization, combinatorics, board-games
---


# Question
Title: Knapsack problem 0/1 with even number of items
So I need to solve the knapsack problem, but I need to make sure that the end solution consists of an even number of items.

I found this on an already existing question:

You can keep two tables with $n$ rows and $C$ columns:

$DP\_{even}$ that saves the best knapsack solution with an even number of itens. $DP\_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP\_{even}$ you look at the previous best solution of $DP\_{odd}$ plus a new item, or of $DP\_{even}$ if you don't take the item: $$DP\_{even}\[i, j\] = max(DP\_{odd}\[i - 1,j - c\[i\]\] + v\[i\], DP\_{even}\[i - 1, j\]) $$ The same idea goes for $DP\_{odd}$ $$DP\_{odd}\[i, j\] = \max(DP\_{even}\[i - 1,j - c\[i\]\] + v\[i\], DP\_{odd}\[i - 1, j\]) $$

Your solution will be in $DP\_{even}\[n, C\]$

But how do I initialize both arrays, since when I intitialize them with 0 in the first row both arrays are going to be the same? Or am I making a false conclusion?

Edit: I already know how to solve the knapsack problem normally, so you don't need to explain that.

# Answer
> 1 votes
For the base case, the value is often decided manually based on the context of the problem. What *should* be the base value?

It is easy to see that $DP\_{even}\[0,0\]$ should be $0$, and $DP\_{even}\[0,j\]$ for $j\>0$ should be $-\infty$. This is because the highest value you can get with considering none of the items and cost nothing is trivially 0, but the case where you consider none them but still cost *something* is impossible, hence we can safely assign it $-\infty$.

Now let's look at $DP\_{odd}$. You might think that $DP\_{odd}\[0,0\]$ is $0$, but following your definition, $DP\_{odd}\[0,0\]$ means the highest value you can get with considering none of the items, and take an odd number of items and costs nothing. Notice the contradiction in this statement? You don't consider any items, then obviously you couldn't have taken an odd number of items! The same argument holds for all $DP\_{odd}\[0,j\]$ for $j\geq 0$. Hence, they are all assigned $-\infty$.

To summarize, the base case is very similar. Both $DP\_{even}\[0,j\]$ and $DP\_{odd}\[0,j\]$ are mostly $-\infty$, except $DP\_{even}\[0,0\]$ which is $0$. Now, you can safely run your recurrence relations on top of the base cases.

# Answer
> 0 votes
*Note: At the time of my writing, the only other answer to this question seems incorrect. I do not agree that $DP\_\text{e}(0,j) = -\infty$ for all $j \> 0$. Whether the backpack is full ($j = 0$) or has space remaining ($j \> 0$) after all items are considered is inconsequential. Provided the total number of items in the knapsack is an even number, the solution is feasible but no further value may be gleaned. Hence, $DP\_\text{e}(0,j) = 0$ for all $j \ge 0$.*

Let's suppose the 0-1 knapsack problem takes the following form: \begin{align} \max~ & \sum\_{i=1}^n c\_i x\_i \\ \text{s.t.}~ & \sum\_{i=1}^n a\_i x\_i \le b, \\ & x\_i \in \\{0, 1\\}, \quad i=1,\ldots,n. \end{align} Then the value functions for the dynamic programming approach may be defined as follows: \begin{equation} DP\_\text{e}(i, j) = \begin{cases} -\infty, & j \< 0 \\ 0, & j \ge 0~\text{and}~i = 0 \\ \max\left\\{ DP\_\text{e}(i-1,j), DP\_\text{o}(i-1,j-a\_i)+c\_i \right\\}, & j \ge 0~\text{and}~i \> 0 \end{cases} \end{equation} and \begin{equation} DP\_\text{o}(i, j) = \begin{cases} -\infty, & j \< 0~\text{or}~i = 0 \\ \max\left\\{ DP\_\text{o}(i-1,j), DP\_\text{e}(i-1,j-a\_i)+c\_i \right\\}, & j \ge 0~\text{and}~i \> 0 \end{cases}. \end{equation} In these functions, $i$ indicates the item under consideration and $j$ indicates the remaining knapsack capacity. Items are considered in descending order, and the value $i=0$ indicates that no items remain for consideration (*i.e.*, $i=0$ is a base state regardless of $j$).

The function $DP\_\text{e}(i,j)$ represents the answer to the following question: With an even number of items already in the knapsack and with $j$ space remaining, how much value may yet be gleaned from items $1,\ldots,i$ if an even number of items must end up in the knapsack? The function $DP\_\text{o}(i,j)$ represents the answer to the same question but starting with an odd number of items already in the knapsack. If $\sum\_{i=0}^n x\_i$ must be even, then the best objective value is $DP\_\text{e}(n, b)$. If odd, then the best objective value is $DP\_\text{o}(n, b)$.

---
Tags: dynamic-programming
---


# Question
Title: Create a Deterministic Finite Automaton for a regular expression
I want to create a finite state machine that accepts the following language:

$$ L=\\{w\in\\{a,b\\}^\* | w \text{ contains abb but not on the first position}\\} $$

So I began by writing a regular expression from this and this is what I came up with:

$(a+b)(a+b)^\*abb(a+b)^\*$

And for the finite state machine I tried to do this:

But it doesn't work since I can go from qo-\>(a)q1-\>(b)-\>(b)q1 and have $abb$ at the begining. How should I approach this? How should I approach to create a finite state machine when for example I have the regular expression? How should I develop an intuition without using algorithms such as FollowPos?

# Answer
I think your problem could be understood in two ways:

1. $abb$ is a subword of $w$ and the word $w$ doesn't start with $abb$
2. $abb$ is a subword of $w\[1:\]$, but the word $w$ can start with $abb$

I will assume the first one but correct me if I'm wrong.

One way to create an automaton for this language would be as follows:

1. From the start state $q\_0$ go to $q\_a$ on input $a$ and to $q\_{abb?}$ on input $b$
2. From $q\_a$ go to $q\_{ab}$ on $b$ and to $q\_{bb?}$ on $a$
3. From $q\_{ab}$ go to $q\_{reject}$ on $b$ and to $q\_{bb?}$ on $a$
4. From $q\_{abb?}$ loop on $b$ and go to $q\_{bb?}$ on $a$
5. From $q\_{bb?}$ go to $q\_{b?}$ on $b$ and loop on $a$
6. From $q\_{b?}$ go to $q\_{accept}$ on $b$ and to $q\_{bb?}$ on $a$
7. Loop on $q\_{accept}$, which is the accepting state

The graphical representation would look as follows:

So what we are doing, in essence, is first checking if the word $w$ starts with $abb$ and if it does reject it and if it does not, then look for the subword $abb$.

Answering the other part of your question:

1. There is an algorithm that transforms regular expressions to Nondeterministic Finite Automata
2. Developing intuition is just a matter of practice. You have to write as many automata for regular languages as possible and see what are the common tricks and methods, and what are some traps that await you when constructing automata.
> 1 votes

# Answer
Tentukan Bahasa regular dan gambarkan Finite Automata dari Regular ekspresi berikut :

```
 a. a (ba)*

 b. (ab)* a

```
> -1 votes

---
Tags: formal-languages, regular-languages, finite-automata, logic, regular-expressions
---


# Question
Title: How to avoid costly square root operations in A* algorithm?
As a reminder, in an A\* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is an estimation on remaining cost to get from this vertex to the destination vertex. In my specific A\* path finding algorithm, my estimation function has a square root operation. It isn't the standard $h = \sqrt{a^2 + b^2}$; for simplicity, let's say it's $h = \sqrt{d}$ where $d$ is some easily computable value. My problem is that my algorithm can take quite some time on some instances. Should I have a look at replacing my estimation function for a faster one, say without any square root operations?

I've looked around and some people simply ignore the square root (so $H = d$) which makes A\* run faster but then it may overestimate, resulting in non-optimal solutions. I'd like to keep optimality, so next I was thinking about the priority function $F = f^2$ so as to accommodate for this overdominating $H = d$ (note that $F$ overestimates as well, but since the priority queue order for $f$ is the same as for $F$ optimality is preserved). However, since $f^2 = g^2 + 2gh + h^2 = g^2 + 2gh + H$, I would still need to compute $h = \sqrt{d}$. My first question is: could I use priority function $F\_2 = g^2 + 2g + H$ instead? It's missing the $h$ from priority function $F$, could this create a problem, like $g$ being too dominant and the A\* algorithm regressing too much to a Dijkstra algorithm?

Another idea I had was to construct an array during precomputation with the square root values of $d$ up to some upper bound on $d$, say $D$. I have such a bound, of about 500 say, so I could construct an array of values $1^2$, $2^2$, $3^2$, ..., $24^2= 576$. Then, when I need to compute a square root of $d$, for example $d=200$, a binary search in my array could give me highest value $\leq 200$, being $196$ at index 13, implying $h = 14$ with possibly some decimal notation which I don't care too much about. My second question is: would this method, of time complexity $\log(\sqrt{D})$, be faster than the standard (Java) square root?

Finally, more generally speaking, my third question is: how would one generally avoid such costly square root computations in A\* algorithms?

# Answer
> 1 votes
Here’s a suggestion to verify that the square root is a problem: Measure how fast your code is. Replace sqrt(d) with sqrt(sqrt(d\*d)). How much slower does your code get?

# Answer
> -1 votes
If you can use square root with limited precision, then you may try this approach:

1. use g^2 + 2gh + H formula, so you have exact value of H
2. compute leading zeroes in H so you can represent H=x\*2^n
3. shift H so only 10 bits remain: H2 = H \>\> (n-10)
4. compute sqrtH2 = sqrt\_table\[H2\]
5. now h = sqrtH2 * 32 * 2^(n/2)

---
Tags: algorithms, program-optimization, a-star-search
---


# Question
Title: Asymptotics of the sum of a geometric series
I have a parameter $q$ which is the probability of selecting a vertex (among $n$ vertices...) to be in a certain set.

I am constructing the sets in an iterative way, having the vertex $v\_i$ be in the set with probability $\leq \left(1 - q\right)^i$ (I'm not going into details about the order of the vertices for which this is performed, as I don't think its vital).

By that I can tell that the expected size of my set is $\Sigma\_i \left(1-q\right)^i$.

Now the part which baffles me is where it says: $$\Sigma\_i \left(1-q\right)^i = O\left( \frac{1}{q} \right)$$

So I know $q$ represents the probability for a vertex to be selected. So $q\<1$.... But as I recall the formula for the sum of a geometrical series is:

$$\frac{a\_1 \cdot \left( \left(1-q\right)^i -1\right)}{1-q-1} = \frac{\left(1-q\right) \cdot \left( \left(1-q\right)^i -1\right)}{-q}$$

Seems more like $O\left( q^i \right)$ than $O\left( \frac{1}{q} \right)$.

This is a silly question, but I would like to know where I got confused...

# Answer
There is an abuse of notation in your question: you are using $i$ as both the index for the summation and as the total number of terms in the sum (in the closed formula).

Anyway, the ratio of the geometric series is $1-q$, but you mixed it up with $q-1$ in the closed formula. For simplicity consider the infinite sum $\sum\_{i=0}^{\infty} (1-q)^i$, which is clearly an upper bound to the quantity you are after (and only affect the result by a multiplicative constant): $$ \sum\_{i=0}^{\infty} (1-q)^i = \frac{1}{1 - (1-q)} = \frac{1}{q}. $$
> 8 votes

---
Tags: asymptotics
---


# Question
Title: Context free grammar $\{0^n 1^m : n,m \geq 0\}$
I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$.

I thought that the simple answer would have the production rules: $S \rightarrow \epsilon \ | \ 0S \ | \ S1$

Since I thought this implies that whichever string you have, you can always place a $0$ in front of the string or a $1$ at the end of the string. However it seems that you can also create the string $0101$ with these production rules, could someone explain to me why my production rules won't give the desired outcome?

# Answer
> 0 votes
You can't produce $0101$ because every time you use $0S$ you are putting a $0$ at the beginning of the string. Whenever you want to insert a $1$, it directly goes to the end of the string and it will remain the last element of the string. This holds also in the opposite way. You can add $1$s and, if you add a $0$, it became the first element of the string and you can only add characters to the right of this $0$.

The proposed production rules are correct and it can be easily shown by induction on the number of times a production rule is applied $ \ell$.

The strings obtained by the production rules (starting from empty string) $S\rightarrow \epsilon \ | \ 0S \ | \ S1 $ are in the form $0^n1^m$.

a) Base case: $\ell=0$ this is true because $S=\epsilon = 0^0 1^0$.

b) Inductive step: Assuming the thesis true for $\ell$ applications of the production rules, we show it for $\ell +1$ applications. Assume $S$ is the results of $\ell$ applications of the production rules, thus, by inductive hypothesis $S=0^n1^m$. Now, we have three possibilities, one for each production rule:

1. $S\rightarrow \epsilon$, in this case the thesis remains true.
2. $S\rightarrow 0S$, then we added a starting $0$, so if by inductive hypotesis $S=0^n1^m$, we obtained $0^{n+1}1^m$.
3. $S\rightarrow S1$, as previous case, we obtain $0^n 1^{m+1}$.

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


title: Non-dominated maximal paths in a DAG

text:
# Question
Title: Non-dominated maximal paths in a DAG
Let $D(V, A)$ be a DAG. We call a *dominated* path in $D$ a path $P$ such that

$P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$

that is, $P$ is a dominated path iff $P$ is maximal and there exists another path $P^{'}$, also maximal, containing all the nodes of $P$, along with at least one additional node. If such path $P^{'}$ doesn't exist, we say that $P$ is a *non-dominated* path. For instance, let's take the below example:

The paths:

* $(1, 5)$ is a dominated;
* $(1, 6, 5)$ is a non-dominated;
* $(1, 2, 4, 5)$ is a dominated; And
* $(1, 2, 3, 4, 5)$ is a non-dominated.

My question is, how can we find all the non-dominated paths? Obviously, a straightforward solution would be to enumerate all maximal paths in $D$, and apply a dominance check to each retrieved path. However, I am trying to find a more efficient way of doing so, even if no "polynomiality" is possible.

# Answer
> 1 votes
After some hours of paper sketching, I think I could come up with somethig.

Let $P = (v\_1, \dots, v\_n)$ be a path in $D$. Then we have

**Lemma 0:** Any other permutation of $P$ results in an invalid path for $D$.

**Proof:** The replacement of $v\_{j}$ by $v\_{k}$ in $P$, such that $j \< k$, resulting in the following permutation $(v\_1, \dots, v\_k, \dots, v\_j, \dots, v\_n)$, implies that the paths from $v\_j$ to $v\_k$ (as $P$ indicates), and from $v\_k$ to $v\_j$ (as the new permutation shows), exist simultaneously. What gives a contradition, since $D$ is a DAG.

Let $S\_{k} = (v\_k, \dots, v\_{k + 1})$ be a path between $v\_k$ and $v\_{k + 1}$ in $D$, $\forall k \in \\{1, \dots, n - 1\\}$. Then

**Lemma 1:** $(v\_1, \dots, v\_{k-1}) \cap S\_{k} = \emptyset$

**Proof:** If there exists a node $v\_m \in (v\_1, \dots, v\_{k-1}) \cap S\_{k}$, then there exists, simultaneously, paths from $v\_k$ to $v\_m$, and from $v\_m$ to $v\_k$, which forms a cycle. Thus, a contradiction, given the DAG property of $D$.

**Lemma 2:** $(v\_{k + 2}, \dots, v\_{n}) \cap S\_{k} = \emptyset$

**Proof:** Same reasoning as above.

**Corollary 1:** Path $P^{'}$ dominates $P$ iff. $\exists\_{k \in \\{1,\dots,n - 1\\}} (|S\_k| \> 2 \wedge P^{'} = (v\_1,\dots,v\_k)\cup (S\_k \backslash \\{v\_k, v\_{k + 1} \\}) \cup (v\_{k + 1}, \dots, v\_n))$.

**Proof:** This is a consequence of Lemmas 0, 1, and 2. Because,

1. According to Lemma 0, any path $P^{'}$ dominating $P$ would have to maintain the order of the nodes in the permutation given by $P$;
2. According to Lemmas 1 and 2, any node inside $S\_k$ (disregarding the endings), cannot belong to the dominated path $P$;
3. Therefore, the only possible expansion for $P$, is to find a $S\_k : |S\_k| \> 2$ and to append it accordingly in $P$, resulting in a $P^{'}$.

For instance, in the picture given above, we have that

$P^{'} = (1, 2, 3, 4, 5)$ dominates $P = (1, 2, 4, 5)$, since the extract $(2, 3, 4)$ can be appended to $P$. The same is valid for $(1, 6, 5)$ and $(1, 5)$.

**Corollary 2:** A path $P^{'} = (v\_1, \dots, v\_n)$ is a non-dominated path iff. $\nexists\_{k \in \\{1,\dots,n-1\\}} (|S\_k| \> 2)$ and $P^{'}$ is maximal.

**Proof:** This is a consequence of Corollary 1.

Let $D\_R$ be the transitive reduction of $D$, then:

**Corollary 3:** $P^{'}$ is a path in $D\_R$ iff. $\nexists\_{k \in \\{1,\dots,n-1\\}} (|S\_k| \> 2)$.

**Proof:** This is a consequence of the definition of transitive reduction.

**Theorem 0:** $P^{'}$ is non-dominated iff. $P^{'}$ is a maximal path in $D\_R$.

**Proof:** Every arc of $P^{'}$ belongs to $D\_R$.

Please, feel free to suggest and point corrections.

---
Tags: algorithms, graphs, dag
---


title: Edge being in the MST

text:
# Question
Title: Edge being in the MST
Does an edge never being the largest weight in any cycle imply that it is included in the MST? I believe the answer is not, but can't think of a counterexample. I know that one guarantees an edge is in the MST with the cut property, but was wondering if this is equivalent.

# Answer
> 0 votes
Consider $G = (V, E, w)$ an undirected weighted connect graph, and $T = (V, F)$ a minimum spanning tree of $G$.

Assume there exists $a\in E$ such that $w(a)$ is never the largest in any cycle containing $a$, and $a\notin F$.

Then $(V, F\cup \\{a\\})$ contains a cycle. Do you see how to construct a spanning tree of $G$ with weight less than $w(T)$?

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


# Question
Title: Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}
I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to the DFA the full string so for example 1001 or is it multiple inputs of length 3 in this example 100 and then 001. I've made multiple DFA's now but they all seem incorrect to me. Below is my latest attempt which doesn't seem to work for me. Since when trying the string 1001 it goes to an accepting state but the last 1 puts it back into a non accepting state. I'm really struggling with checking for every substring of length 3 since you leave the final state when you have a length which is not a multiple of 3, but it should still be accepted. How would I make a DFA that accepts strings of minimal length 3 but then also of length 4 which satisfies these conditions? (I know the DFA is not yet fully finished) I have created a dead state for whenever a string has 2 1's within a substring of length 3.

Thanks!

EDIT: The last DFA is correct :)

# Answer
An automaton should come with a plan. What is stored or represented in each of the states?

When the requirement asks us to check all substrings of a certain length the plan might start with a substring automaton that keeps in its state the last $k$ symbols seen. A window, sliding over the input string. Below an example for $k=3$. From state $xyz$ after reading $a$ we move to state $yza$.

In the current question all states should contain two or more $0$'s. That means that all four states to the right fail, and can be lumped together to form a garbage state. There are no longer outgoing states from the garbage back to the four states at the left.

Initially the automaton has not read any symbols. That means we add initial states with less than three letters read, in the form of a tree. Any string shorter than $3$ should be trivially accepted (having no substrings of length $3$).

One finds this automaton in the context of De Bruijn sequences. Languages that can be recognized by a sliding window automaton are called locally testable.
> 0 votes

# Answer
You need seven states:

The error state - once in the error state you always go to the non-accepting error state.

States 00, 01, 10, 11: These are the last two characters processed. If we process 0 then we move from 00 or 10 to 00, from 01 to 10, and from 11 to error. (11 will only be encountered if the first two characters are 11). If we process a 1, we move from 00 to 01, and from the other states to error.

Now what do we do if no or one character have been processed: We add a start state and a state 1. From the start state we go to 00 or 1. From 1 we go to 10 or 11. All states except the error state are accepting.
> 0 votes

---
Tags: finite-automata
---


title: Mergesort time complexity

text:
# Question
Title: Mergesort time complexity
Using the regular mergesort algorithm for a list, say $a\[1...n\]$, we call the merge function to merge, mergesort($a\[1...\lfloor \frac{n}{2} \rfloor\]$) and mergesort($a\[\lfloor{\frac{n}{2}}\rfloor+1...n\]$). Let $T(n)$ be the time complexity for mergesort. Then, the first sublist needs $T(\lfloor \frac{n}{2} \rfloor)$ time and the second one needs $T(\lceil \frac{n}{2} \rceil)$ time. Since merge needs linear time, we have the recurrence relation for the time complexity: $T(n)=T(\lfloor \frac{n}{2} \rfloor)+T(\lceil\frac{n}{2} \rceil)+ O(n)$.

Am I wrong ? If no, the answer should be $T(n)=2T(\frac{n}{2})+O(n)$. How are the two relations the same ?

Thank you in advance.

# Answer
You are right, but ignoring floor and ceiling does not affect the asymptotic behavior of your recurrence, so you can consider $T(n) = 2 T(n/2) + O(n)$ instead of $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ while still obtaining the same (asymptotic) solution.

This might feel a bit hand-wawy, but it can be justified formally using a technique known as "domain transformation".

Consider the recurrence $T(n) \le 2 T(\lceil n / 2 \rceil) + O(n)$, since $\lceil n/2 \rceil \le n/2 + 1$ we have $T(n) \le T(n/2 + 1) + O(n)$. Define $S(n) = T(n+\alpha)$ for some constant $\alpha$ to be fixed later. You have: $$ \begin{align\*} S(n) = T(n+\alpha) &\le 2 T\left( \frac{n+\alpha}{2} +1\right) + O(n) \\ &= 2T\left(\frac{n + \alpha + 2}{2}\right) +O(n) = 2S\left(\frac{n - \alpha + 2}{2} \right) + O(n), \end{align\*} $$ therefore we can choose $\alpha=2$ to obtain $S(n) \le 2S(n/2) + O(n)$, which has solution $S(n) = O(n \log n)$. Substituting back, we get: $$ T(n) = S(n-2) = O( n \log n ). $$
> 0 votes

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