# Question
Title: Construct a DFA accepts set of all strings that begins with 01 and end with 11
I have drawn the DFA for language L1 containing strings starting with 01 and language L2 containing strings ending in 11. For the final DFA, I have concatenated both DFA's. The finals DFA does not accept 011. Kindly help!

# Answer
> 2 votes
The reason why your DFA doesn't work is that not all strings that start with 01 and end with 11 can be written as a concatenation of a string $x$ that start with 01 and a string $y$ that ends with 11, as you discovered.

This can happen because $x$ and $y$ might intersect. However the only way for this to happen is for $x$ and $y$ to share a single "$1$". I.e., the only problematic string is $011$. To fix this you can just union your DFA with one that recognizes $011$.

Rephrasing your problem using a regular expression, you cannot obtain a regular expression for you language by simply concatenating $01(0\mid1)^\*$ with $(0\mid1)^\*11$ which would yield $01(0\mid1)^\*(0\mid1)^\*11=01(0\mid1)^\*11$. However, the following regular expression is correct:

$$ ( 01(0 \mid 1)^\*11 ) \mid (011) $$

---
Tags: finite-automata
---


# Question
Title: Prove that the language generated by the grammar $S \to SxS \mid a$ is inherently ambiguous
With the following grammar:

$$S \to SxS \mid a$$

Is L(G) inherently ambiguous? What is the proof?

---

I know how to prove the grammar is ambiguous but I don't know how to prove if the grammar is inherently ambiguous. Can someone help me?

# Answer
> 2 votes
$L(G)$ is regular and hence not inherently ambiguous. In particular $L(G)$ is the language described by the regular expression $a(xa)^\*$.

---
Tags: formal-languages, automata, ambiguity
---


# Question
Title: How can I implement a Deterministic finite automaton which accepts
**Problem**: implement a Deterministic finite automaton which accepts 01 ∪ (2∪10\*2)\*

∪ \<- is union symbol

I have a lot of problem trying to implement that DFA, the union symbol always confuse me Can someone help me

# Answer
> 1 votes
You should take a look at Berry-Sethi's algorithm for the general method (+ powerset construction for a DFA).

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


title: Understanding Time Complexity

text:
# Question
Title: Understanding Time Complexity
I am sorry if these are such stupid noob questions. I am just getting into CS.

I read a passage in a book that says:

> Time complexity is written T(n). It gives the number of operations the algorithm performs when processing an input of size n. We also refer to an algorithm’s T(n) as its running cost. If our code follows T(n) = n2, we can predict how much longer it takes to sort a deck once we double its size:

Questions:

1. Firstly, why does our code follow **T(n) = n2** ? I don't get why we make that assumption
2. I do not understand what this means, n2 means squared, correct? so if `n` is `8` then it's: `T(8) = 64`, right?
3. Next we have the `T(2n)/T(n) = 4`, lets say `n` is `2` then its `T(4)/T(2) = 2`, right?

Again I am a noob so please be gently and I would really appreciate detailed answers. Thank you

# Answer
> 5 votes
1. This is just an example. Easiest to think of an algorithm that has two nested loops over an array of size $n$ (e.g. Bubble Sort).
2. You are correct. Again, if you think of an algorithm that has two nested loops and within the inner loop just one (or constantly many) operation $op$, then $op$ gets executed $n^2$ times. If you array has size 8, $op$ gets executed 64 times.
3. No, the ratio is constantly 4. $\frac{T(2n)}{T(n)} = \frac{(2n)^2}{n^2} = 4$. The intuition here is that quadratic runtime means: By $k$-folding the input size, the runtime gets $k^2$-folded.

# Answer
> 0 votes
It means we try to express the time needed to solve a problem as a function of the problem size, so that we know how to deal with larger problem sizes & scalability issues

* For example if we find it is linear in the problem size (T(n)=an+b) that's probably cool, if n=1000 or even n=10⁹ we can manage (our program will end its run in a acceptable time)
* While if we calculate it to be exponential in n (T(n)= a•2^n), that could cause a scalability problem; if n=10 that's 1024a, but what if n=100? 2¹⁰⁰ is an infinite time, we have to think of another way (algorithm) to solve the problem

That's the explaining, as for ur example

If T(n)=n², then

T(2n)=(2n)²=2²•n²=4•n²= 4•T(n)

If n=2, T(n)=4, T(2n)=4²=16 If n=8, T(n)=64, T(2n)=16²=256 =16•16=4•4•16=4•64

---
Tags: time-complexity, mathematical-programming
---


# Question
Title: Is an AI upscaler incapable of reducing entropy?
I was reading the description of Anime4K (a video upscaler software) and I found a statement triggering my attention:

> \[upscaling is done\] without any meaningful decrease in entropy (lost information is lost).

If someone sits down and redraw a cartoon, they may be perfectly capable of using their experience to undo the effect of a terribly lossy compression, inferring lost information pretty much as the author intended it to be. A well-trained AI is capable of the same process, isn't it?

And, even if the reconstruction process adds details which were not in the original, producing a different but more enjoyable result, can we say that we did not have *any meaningful decrease of entropy*?

# Answer
If the AI upscaler algorithm is deterministic, then the entropy of the output $Y=f(X)$ will be *not larger* than the entropy of the input $X$. This is due to the information-theoretic inequality $$ H(f(X)) \le H(X) $$ where $H(X)$ is the entropy of $X$, which holds for any random variable $X$ and deterministic algorithm $f$. That is, the entropy of a random variable can only decrease when that variable is passed through a (deterministic) function (reference).

When the upscaler algorithm is randomized, the above relation may not hold: for example, the algorithm could output random white-noise images in response to images that are only fully black or fully white. However, as you can see even in this scenario we are not recovering any meaningful information. We can understand even this case as follows. Let $Z$ be a random variable representing the "ground truth": the high-resolution, ideal image or video. Let us assume that the low-resolution image $X$ that is input to the upscaler depends on $Z$, and that the upscaler can only rely on information in $X$ (it cannot access $Z$ directly). Schematically, $$ Z \rightarrow X \rightarrow Y $$ In information theory, this is called a Markov chain of the three random variables $Z$, $X$, and $Y$. Mathematically, it means that the conditional distribution of $Y$ given $X$ is independent of $Z$. One basic result of information-theory is that in this setting, the mutual information $I(Z; Y)$ between the ideal image and the upscaled image can only be lower than the mutual information $I(Z; X)$ between the ideal image and the input to the upscaler: $$ I(Z; Y) \le I(Z; X) $$ This is called the data processing inequality.

Thus, the only possibility if you really want to be able to increase the mutual information between the upscaled image and the ideal image is to have some way to access information in $Z$ that is not in $X$. For example, you might train your upscaling algorithm on a collection of images which you assume will be representative of your ground truth-input pairs $(Z, X)$. If the collection is indeed representative, this gives you the same kind of background knowledge (= experience) that a skilled drawer is using in reconstructing a low-quality drawing. A related problem is the image inpainting problem in image processing, where damaged, deteriorating, or missing parts of an artwork are filled in to present a complete image.
> 3 votes

---
Tags: artificial-intelligence, information-theory, entropy
---


# Question
Title: In what bases is the language $a^n$ regular?
Given $a\in\mathbb{N}$, I wondered for what bases $b$ is the following language regular

$$\\{a\_ka\_{k-1}\ldots a\_0\mid \exists n\in\mathbb{N},\ a\_0+a\_1b+a\_2b^2+\ldots+a\_kb^k=a^n\\}$$

I think it's regular only for bases which are a rational power of $a$, but I couldn't come up with any proof of that.

Is that correct? How can you prove it/find a counterexample?

# Answer
Putting orlp's comment and the Wikipedia article linked in another comment in an answer, this is a direct application of Cobham's Theorem. The theorem states that the representations of a set of natural numbers $S$ in two multiplicatively independent bases $b\_1$ and $b\_2$ form regular languages iff the set $S$ is a finite union of arithmetic progressions (alternatively, $S$ eventually ends up repeating).

Multiplicative independence of two numbers $m$ and $n$ means that there exist no integer powers $p,q\>0$ such that $m^p=n^q$. From this, your assertion that these two bases $m$ and $n$ have to be rational powers of each other can easily be seen.

Your sequence does not end up repeating, so only its representations in multiplicatively dependent bases will be regular, of which one base trivially is $a$.

For proofs of Cobham's Theorem, see the section §*Demonstrations* ("Proofs") on the French Wikipedia and its linked articles, of which a very short and recent proof is by Krebs.
> 1 votes

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


# Question
Title: Why Breadth First Search is used for shortest path
We can read on the internet: `BFS finds the shortest path to the destination.`

But how ? Check this example:

for this example we can get 40 10 20 30 60 50 70

What is going on here ? In my opinion the shortest way to 50 is 40 - 20 - 50 so this algorithm is not good for shortest path.

Could someone explain how this algorithm shows the shortest path ?

# Answer
The algorithm produces a tree. To get the shortest path from the source node (node $40$ in this case), to some other node of your choice (node $50$ for example), follow the path in the tree between the two nodes.

Here, the path will indeed be $40\rightarrow 20\rightarrow 50$. Try to construct the BFS tree and see for yourself that this is the case
> 0 votes

---
Tags: algorithms, graphs, breadth-first-search
---


# Question
Title: How is the reccurence of Max Heapify T(n)= T(2n/3) + $\theta(1)$?
I'm trying to figure out how is the recurrence of $maxheapify()$ is $T(n)=T(2n/3)+O(1)$

If size of max heap is $n$, then calling $maxheapify(A, 1)$ will (at worst case) go through only one element in each level (in the downwards direction) up to level $h$ (where $h = \log n$)

So, the recurrence should be $T(n) = T(n/2)+ O(1)$ since $n/2$ is half size of the heap.

?

***Update: Here is a very good Visual explanation to the recurrence:*** http://www.cs.uvm.edu/~rsnapp/teaching/cs124/notes/cs124notes\_031914.pdf

# Answer
Consider an heap of height $h \ge 1$ having $2^{h-1}$ leaves on its last level. Let $\ell$ (resp. $r$) be the number of vertices in the subtree rooted in the left (resp. right) child of the root.

Then $\ell = 2^{h-1} + 2^{h-2} + \dots + 1 = 2^h -1$ while $r = 2^{h-2} + 2^{h-3} + \dots + 1 = 2^{h-1} -1$. The overall number $n$ of nodes in the heap is $\ell + r + 1 = 2^h + 2^{h-1} - 1 = 3 \cdot 2^{h-1} - 1$.

If we recurse on the left subtree, the ratio between the number of nodes of the whole heap and the number of nodes in the subtree is: $$ \frac{\ell}{n} = \frac{2^h -1}{3 \cdot 2^{h-1} - 1} = \frac{2 \cdot 2^{h-1} -1}{3 \cdot 2^{h-1} - 1}. $$

This ratio is always smaller than $\frac{2}{3}$. Moreover, taking the limit as $h$, and hence $n$, grows to $+\infty$ you get (in the above construction $\ell$ and $n$ can be thought as functions of $h$): $$ \lim\_{h \to \infty} \frac{\ell}{n} = \frac{2}{3}. $$

In other words it is always true that $\ell \le \frac{2}{3}n$ and, for any constant $c \< \frac{2}{3}$ it is false that $\ell \le c n$ (for some heap with sufficiently many nodes).
> 1 votes

---
Tags: heap-sort
---


# Question
Title: Fitting arrays into RAM algorithm question
> We'll consider the RAM as a sequence of cells that can contain data. Some cells already contain some data, some are empty. The empty cells form the so-called memory clusters. Thus, a memory cluster is a sequence of some consecutive empty memory cells.
>
> You have exactly $n$ memory clusters, the $i$-th cluster consists of $a\_i$ cells. You need to find memory for m arrays in your program. The $j$-th array takes $2^{b\_j}$ consecutive memory cells. There possibly isn't enough memory for all m arrays, so your task is to determine what maximum number of arrays can be located in the available memory clusters. Of course, the arrays cannot be divided between the memory clusters. Also, no cell can belong to two arrays.
>
> Input
> The first line of the input contains two integers $n$ and $m$ ($1 \le n$, $m \le 10^6$). The next line contains $n$ integers $a\_1, a\_2, ..., a\_n$ ($1 \le a\_i \le 10^9$). The next line contains m integers $b\_1, b\_2, ..., b\_m$ ($1 \le 2^{b\_i} \le 10^9$).
>
> Output
> Print a single integer — the answer to the problem.

I cannot understand the solution to this question from Codeforces, https://codeforces.com/blog/entry/7749. Why are they considering arrays of size 1? The arrays could be any size? Why do we need to consider odd or even. To be honest, I dont understand this solution at all.

# Answer
> The $j$-th array takes $2^{b\_j}$ consecutive memory cells.

Suppose $j=4$ and $b\_4=0$. That means the $4$-th array takes $2^{b\_4}=2^0=1$ consecutive memory cell.

In case it is surprising to you that $2^0=1$, you can understand it as, for example, $1=\frac{2^3}{2^3}=2^{3-3}=2^0$.

Does the word "cells", which is in plural form, require $2^{b\_j}$ be greater than 1? Not necessarily, although "$2^{b\_j}$ consecutive memory cell(s)" could have been clearer. It is very common to use the plural form of a word to refer a group/collection of unknown or variable quantities using the plural form, especially in math and computer science.

**Exercise**: Understand that $3^0=1$. Understand that $a^0=1$ for any nonzero number $a$.
> 1 votes

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: What algorithm is prefered to do a x b mod P with big numbers (256 bits)
I'm trying to implement multiple precision arithmetic operations modulo `P`, with `P < 2^256`. More specifically, `P = 2^256 - 2^32 - 977`.

I want to support the following operations: `+`, `-`, `*`, `/`, `pow` (each mod P)

As P is close to `2^256`, numbers are represented with 8 u32 or 4 u64.

`a + b mod P` can be done like this (in pseudo code):

```
n = a + b
if overflow: # i.e. over 2^256
    # add 2^256 - P to come back modulo P
    n += 2**32 + 977
else:
    if n >= P:
        # P <= n <= 2^256
        n -= P

```

--

For `a * b mod P`, my first intention was to simply do a **long multiplication** but that seems slow as I would need the carry to be 256 bits as well.

Are there any recommended algorithms to calculate `a * b modulo P` efficiently (using arrays of u32 / u64)?

I'm mostly interested in the multiplication because:

* `a^x mod P` can be an optimized version of `a * a * ... * a mod P`
* `a / b mod P` can be calculated as `a * b^{P-2}` using fermats little theorem

Note: Bitcoin implements these operations with numbers represented with 10 x uint26 instead of 8 uint32 so each "digit" keeps 6 bits but I'm not familiar with their methods.

# Answer
> 1 votes
Here is one reasonable method:

To multiply a 32-bit integer by a 256-bit integer modulo $P$, multiply the integers using arbitrary-precision arithmetic (see How do computers perform operations on numbers that are larger than 64 bits? this can be done with 8 32x32 -\> 64 multiplications, and then some 32-bit additions) to get a 288-bit product, then reduce the product modulo $P$ (divide the product by $P$, and keep the remainder).

To multiply a 256-bit integer $X$ by a 256-bit integer $Y$ modulo $P$, write

$$X = 2^{224} X\_7 + \dots + 2^{32} X\_1 + X\_0,$$

then do the following:

* set $B := 0$
* for $i := 7,6,\dots,0$:
    + set $A := X\_i \times Y \bmod P$
    + set $B := 2^{32} \times B \bmod P$
    + set $B := A + B \bmod P$

At the end, $B$ will hold the product $A \times B \bmod P$. Each step can be computed using the method of the first paragraph of this answer as it only involves 32x256 -\> 288 modular multiplications.

# Answer
> 1 votes
Note that with your particular P, $a \cdot 2^{256} + b \mod P = $ $ b + a \cdot (2^{32}+977) \mod P$. The result will only rarely be P or slightly larger, in which case you subtract P once more.

---
Tags: algorithms, cryptography, mathematical-programming, modular-arithmetic
---


title: Why 2^(2n+2) not equal to θ(2^2n)?

text:
# Question
Title: Why 2^(2n+2) not equal to θ(2^2n)?
I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)?
Firstly 0 \<= c1.2^(2n) \<= 2^(2n+2) for this n=1 c1=1 is a solution set.
For n = ∞, 0 \<= ∞.c1 \<= ∞ c1=1 is provide it. So omega notation part is okay.
Second part is Big O notation so it should be 2^(2n+2) \<= c2.2^2n.
For n=1 it's 8 \<= 4c2, c2 can be 3.
For n=∞, it's ∞ \<= c2.∞, c2=1 is provide it.
Why it's not equal? Can anybody explain? I can see the f(n)'s degree bigger than g(n)'s. So it should be only 2^(2n+2)= Ω(2^2n). But I couldn't show it with sample solution sets. Cause my solution sets equations seem to be correct. Can anybody explain it?

# Answer
It is theta of $2^{2n}$:

$$2^{2n+2}=4\cdot 2^{2n}=\Theta(2^{2n})$$
> 2 votes

---
Tags: time-complexity, algorithm-analysis, asymptotics, runtime-analysis, big-o-notation
---


# Question
Title: Best algorithm for Decisional 4-XOR problem?
**Decisional 4-XOR Problem**: Assume $M\>\>n$ (e.g. $M=50n$ ). Let $A\_1,A\_2,A\_3,A\_4$ be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists $a\_i \in A\_i$ such that $$a\_1 \oplus a\_2\oplus a\_3\oplus a\_4=0$$

The standart methods solves the search version of the problem in $O(2^{2n})$. Is there a better way to solve the decisional problem.

(Even a probabilistic algorithm)

# Answer
For this setting of parameters, I don't believe any method with better time complexity is known in the research literature.
> 0 votes

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


# Question
Title: computer science paper: Why t14 and t19 are unreachable and why t19 reachable?
I am reading the paper\[1\] at: https://arxiv.org/abs/1905.07147

The paper says in Overview section 3:

> The figure shows a constructed function Bar, which is written in Solidity and contained in a smart contract. (The comments should be ignored for now.) There are three assertions in this function, on lines 14, 19, and 22. A compiler will typically introduce a conditional jump for each assertion, where one branch leads to a location that fails. Let us assume that we select the failing locations (t14, t19 , and t22) of the three assertions as our target locations. Note that any target locations could be (automatically) selected based on various strategies, e.g., recently modified code (for smart contracts under development), assertions (added manually or by the compiler for checked errors such as division by zero), etc. Out of the above locations, t14 and t19 are unreachable, whereas t22 is reachable when input parameter a has value 42.

Somebody please guide me why t14, t19 are unreachable and why t22 is reachable in Figure2 of the paper?

Zulfi.

\[1\] Valentin W{"u}stholz and M. Christakis, Targeted Greybox Fuzzing with Static Lookahead Analysis,2020 IEEE/ACM 42nd International Conference on Software Engineering (ICSE),2020,789-80.

# Answer
I found the answer here. What I understand is that conditions of both the assertions (line#14 and line#19) coincides with the loops. If the loop does not end we can't access the assertion. But line#22 has no such problem.

Zulfi.
> 0 votes

---
Tags: randomness, software-testing
---


# Question
Title: How does Wolfram Alpha solve functional equations?
Wolfram Alpha is able to solve a few basic functional equations. For example, it knows how to solve equations like this. My question is: how does it do this? I am planning on creating a program to find solutions to functional equations (doesn't have to be anything too fancy -- start with just testing for polynomial solutions, etc.).

Note: By "functional equation" I mean this.

# Answer
While I don't know how Mathematica solves all such cases, it's worth noting that you need to impose some conditions on Cauchy's functional equation $f(x) + f(y) = f(x+y)$ for it to have a unique solution, such as that $f$ is continuous.

Nonetheless, what's probably going on in this case is that Mathematica turned the system into a recurrence, solved that, and then tested to see if that solution also works on negative numbers, rationals and reals.

Let me show you what I mean. Consider the (more complex) functional equation:

$$f(x+y) + f(x-y) = 2\left\[ f(x) + f(y) \right\]$$

Set $x = y = 0$ to find:

$$2 f(0) = 4 f(x) \Rightarrow f(0) = 0$$

Set $x=n$ and $y=1$ to find:

$$f(n+1) + f(n-1) = 2\left\[ f(n) + f(1) \right\]$$ $$\Rightarrow f(n+1) = 2f(n) - f(n-1) + 2f(1)$$

Assuming that $f(1)$ is a free constant, what we have now is a linear inhomogeneous recurrence, and there are well-known reasonably mechanical ways to solve these. Once you've found a potential most-general solution for natural numbers, test to see if the solution is still true for negative numbers, rationals, and reals.

In the cause of the Cauchy functional equation, set $x = y = 0$ to find:

$$2f(0) = f(0) \Rightarrow f(0) = 0$$

and set $x=n$ and $y=1$ to find:

$$f(n + 1) = f(n) + f(1)$$

I'll leave the rest as an exercise.
> 3 votes

---
Tags: mathematical-programming
---


# Question
Title: Choosing which connection to travel down efficiently
Suppose i want to check if my position is enclosed in a closed loop by following the connection of waypoints that surround it:

Now if i travel from node 0 to node 1. I'm at node 1 and i need to find the next connection of which as you can see i have multiple choices this time.

I can rule out where i came from quite easily, but that still leaves me with other options. How can I optimally pick which connection to follow next based on knowing that the connection from node 1 to node 2 is the only allowed option here anyway since as it's an enclosed loop you can consider them equivalent to being walls. I just am not sure how to check which is the most viable choice next logically speaking.

If node 1 to node 2 connection didn't exist, naturally the first logical choice would be to just go straight on ahead which is easy to tell visually just not so easy when thinking in code.

# Answer
> 1 votes
It seems that you are trying to construct a Eulerian circuit in your network. First, check that every node has an even number of incident edges, otherwise there will not be a Eulerian circuit. Then, use Hierholzer's algorithm to find the Eulerian circuit.

Roughly speaking, you don't need to check anything, you just pick any unused edge from the current node $v$, and sooner or later you will be forced to come back to $v$. However, this might leave out some edges of the network, so in case you want to cover them all, you have to start a new circuit from a node that you already reached and "paste it in" your old circuit.

---
Tags: algorithms
---


title: Does the problem belong to NP class?

text:
# Question
Title: Does the problem belong to NP class?
So I am studying for my Algorithm theory exam and this is the problem i could not solve:

> Given numbers $x\_1, x\_2, ..., x\_n$ which are the sizes of $n$ files and disk capacity $D$. Determine if you can seperate these files into $3$ disks so that, in every disk sum of doesn't exceed $D$. Justify that this problem belongs to class NP

So i am thinking you can seperate only if:
$x\_i \< D$ and if $x\_1 + x\_2 + ... + x\_n \> 3\cdot D$
Are these the only rules?

# Answer
> 0 votes
Nobody asked you to give conditions on when that happens. Also, your second condition is incorrect: if all $x\_1,...,x\_n$ are 0 then for any $D$ there is a solution.

What you are asked is to show this is in NP, hence, show a "prover-verifyer" solution:

The proof will be the following: for each $1\le i\le n$, the proof at index $i$, is $p\_i$ and will be one of three numbers ($1,2,3$ for example) that will indicate in which disk we want to put the file $x\_i$. Then, just check that for every one of the three disks, the sum of the $x$'s in it do not exceed $D$.

Its not hard to show why this algorithm is correct, so I will leave it for you to try on your own.

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


# Question
Title: NP problem: certificate concept clarification
When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {\<G,k\>| G has a clique of size *at least k* }, from what I understand is that all we assume for the certificate "c" to be is some string that is of polynomial length of the size of the input.

My question is when designing the verifier, does this verifier (algorithm) only accepts as input a certificate "c" to be a particular desirable string i.e. for the k-clique problem a **subset of nodes of G of size k** (check below (1)) OR
is this just an idea we put in our head that help us figure out the verifier and in reality "c" can be anything and not necessarly a subset of nodes nor should it be of size k, it could be some string quadratic in size of input?

(1) Hence we choose the Guessed Solution if it exists i.e. a clique of "size K" and if the solution doesn't exist then we choose any **subset of nodes of size k** and this already will not form a clique, so we are sure the verifier will reject...

Thank you in advance

# Answer
> 2 votes
The second approach is technically the correct interperation. When we say "a verifier gets a certificate $c$ that looks like \[...\] and computes something", then we actually mean that this verifier checks whether $c$ is of the required format (e.g, check that $c$ is representing a subset of nodes from the graph), and if it isn't it will immediately reject. Otherwise, it will continue to work how you specified it to.

---
Tags: turing-machines, time-complexity, np, polynomial-time
---


title: Angular line sweep algorithm

text:
# Question
Title: Angular line sweep algorithm
I am trying to implement a `radial/angular` sweep algorithm that finds all segments (segments are disjoint) that are visible from one particular point in $O(n \lg n)$. So I am trying to order vertices by their angle with point P that we are checking visibility from. But I am uncertain with which point to start first with. If I am selecting them by their angle I have the following situation:

These are the first two points that are being checked:

But the problem is that I can't check them with lines before and thus they seem to be visible by the algorithm I found online $O(n \log n)$ algorithm for disjoint segment visibility problem. Those lines will end before the first line that's covering them ends so all 4 of them should be visible by this algorithm. So which criteria should I use to start my angular sweep algorithm?

**Algorithm so far:** I sorted points by the polar angle they make with initial point P. The approach is to start with a minimum degree. I am adding them to the binary search tree which has a custom comparator that adds them by comparing that segment with all other segments in a binary tree. If the segment we're inserting is $T$ and $O$ is comparing the segment, I'm checking whether $PT\_{start}$ and $O$ have intersections. If they don't intersect then $T$ should be before $O$ in BST. That segment is visible. The problem is when I encounter lines like in the pictures above. It marks right segments as visible because there is no first line in BST so it can't check them with the biggest one on the left. I have no idea what should be my starting point and how to differ those problems.

# Answer
You can "split" each of those lines (that you see their endpoint before their starting point), into $2$ lines: one totally below the $x$ axis, and one totally above it.

Notice that this adds a small caveat: you will need to create a "tie breaker" in your algorithm, that will take the closest point to the origin from a set of points with the same "angle".
> 1 votes

---
Tags: algorithms
---


# Question
Title: Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws
I tried to prove this by starting at RHS:

$$ϵ+a(a+b)^\*b = ϵ+a(a^\*b^\*)^\*b$$
But I dont know how to convert $(a^\*b^\*)^\*$ to something else that will be helpful.
Any ideas?

# Answer
We will not use regex equivalences, but rather show this directly by showing language equality:

First, we want to show that $L((aa^\*bb^\*)^\*)\subseteq L(\epsilon + a(a+b)^\*b)$: Take any word $w\in L((aa^\*bb^\*)^\*)$. Its not hard to show that either $w=\epsilon$, or $w$ must start with $a$ and end with a $b$ (rewrite $bb^\*$ as $b^\*b$, it will help to prove this). Then, it will be clear that $w\in L(\epsilon+a(a+b)^\*b)$.

Now we want to show that $L(\epsilon + a(a+b)^\*b)\subseteq L((aa^\*bb^\*)^\*)$: Take any word $w\in L(\epsilon + a(a+b)^\*b)$. If $w=\epsilon$ its obvious why $w\in L((aa^\*bb^\*)^\*)$. Otherwise, prove by induction over $|w|$ the length of $w$, that you can split $w$ in the following way: $$w=x\_1x\_2,\dots,x\_k$$ for some $k\in\mathbb{N}$ such that $x\_i \in L(aa^\*b^\*b)$.

Hint: define $x\_1$ to be the substring of $w$ starting at the first element, and stopping at the first index $l$ such that $w\_l=b$ but $w\_{l+1}=a$. If there is no such index $l$, then take $x\_1:=w$.
> 0 votes

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


# Question
Title: Algo to match students to universities (only students choose & rank)
I'm trying to develop an algorithm in Ruby to allocate one university to each student of a list. As opposed to Gale-Shapley algorithm, universities do no choose nor rank students; only students make a 6-wish ordered list.

* There are 336 students
* There are 151 cities, each with an available number of places between 1 & 6

I think this boils down to computing a minimum sum of 'distances', a student's distance being the rank of the university he was attributed (in his ordered list). E.g: if a student is given his first choice, then his 'distance' is 0. If a student is given his last choice, then his 'distance' is 5.

I see 2 possibilities:

* brute-force to compute all the possibilities and find the one with the minimum sum of distances. But I think it would take too much time/very bad performance & complexity.
* determine criterion beforehand to allocate universities. E.g: we start by giving all non-disputed 1st choice cities to students (e.g if 4 students put 'Paris' as their first choice and Paris has more than 4 seats, we give these 4 students the Paris university). And then we can do the same all the way down to the 6th choices. But this will not give a university to all students, so we then need to find another criteria (or several other criterion) to allocate a university to each of the remaining students. There is another downside of this method: the allocation will depend on the criterion chosen and the algo will maybe not give the best output (minimum of sum of distances).

My questions are:

* do I **need** to use brute-force to find the optimal solution?
* if not, what are the 'best' criterion to allocate universities in this algorithm? ('best' meaning it will allow me to end up with the optimal solution, or if it can't, at least with a pretty good solution overall)

NB:

* I'm a beginner in Ruby & algo, I've read posts on different websites with a lot of theoretical knowledge required but that didn't help me, so if you could vulgarize that would be awesome :)
* I originally posted my question on StackOverflow
* For now, I'm not considering weighing choices non-linearly (e.g. a last choice 'costs' 10 instead of 5), as I think it will be easy to add once I know the right way to proceed

# Answer
You can use the assignment problem.

Construct a bipartite graph, where one side corresponds to students, and the other side corresponds to spots in cities: if a city has $n$ spots, there will be $n$ vertices corresponding to the city. If student $x$ is interested in city $y$, connect $x$ to all spots of $y$ with an edge whose weight corresponds to the "distance". Now compute a maximum weight perfect matching (or a maximum weight matching, if you want to allow students to be unmatched).
> 1 votes

---
Tags: algorithms, matching
---


# Question
Title: How can we formulate an anti-knight Sudoku as an exact cover problem?
Formulating standard Sudoku as an exact cover problem is easy and well documented. All of the constrained groups contain every digit which makes it natural to express the problem this way. Wikipedia claims without citation that:

> Although other Sudoku variations have different numbers of rows, columns, numbers and/or different kinds of constraints, they all involve possibilities and constraint sets, and thus can be seen as exact hitting set problems.

How would one formulate other variants as exact cover problems with an incidence matrix? I'm focusing on the anti-knight variant, but with the goal of learning about expressing arbitrary variants.

The anti-knight Sudoku variant includes all of the standard rules, and additionally requires that no two squares which are a knight's move (in chess) apart may contain the same digit. I don't know how to approach this because a constraint between two squares cannot be expressed as requiring all digits to be present in some permutation. I can imagine a version of Algorithm X that solves this by removing additional rows by manual application of the anti-knight rule, but I believe Wikipedia is claiming this constraint should be expressible in the matrix alone without modifying the algorithm.

Is Wikipedia's claim that all variants can be expressed this way correct, and how would one approach the anti-knight example?

# Answer
We start with the regular sudoku exact cover problem:

### Sudoku Set Cover

* 729 sets, each `(row, col, num)` triple.
    + Each set contains 4 elements: `(row, col)`, `(row, num)`, `(col, num)`, `(box, num)` -- corresponding to the below.
* 324 elements:
    + 81 elements, each `(row, col)` pair.
    + 81 elements, each `(row, num)` pair.
    + 81 elements, each `(col, num)` pair.
    + 81 elements, each `(box, num)` pair.

This creates a 729 x 324 matrix with 2916 ones.

### Anti-Knight Constraints

There are 152 non-redundant anti-knight moves (24 in 4 corner boxes, 38 in 4 edge boxes, and 56 in the middle box, all divided by 2 to avoid double-counting).

The anti-knight moves are like boxes that only contain two cells. However we only want to avoid an intersection, we don't care about covering all 1-9 nums. To allow this we add dummy sets which each contain a single element corresponding to a knight constraint. (This is the extension described in the comments).

* 1368 (9 * 152) new sets, each `(knight-move, num)` pair, each containing the 1 corresponding element.
* 1368 new elements, each `(knight-move, num)` pair.
* Each existing set `(row, col, num)` gets *up to* 8 more elements added which are the knight jumps with number `num` either starting or ending at that cell. Total is 2736 additional set members.

The final result is a 2097 x 1692 matrix with 7020 ones.
> 1 votes

---
Tags: algorithms, constraint-satisfaction
---


# Question
Title: Prove ALL$_{\text{TM}}$ is undecidable reduction problem
Given ALL$\_{\text{TM}}$ = { \< M \> | where M is a TM and L(M) = $Σ^\*$ } show this is undecidable. I'm also told not to use Rice's theorem. I'm having difficulties with reduction type problems. How would you do a proof for this using a reduction of A$\_{\text{TM}}$? Any pointers to resources are much appreciated.

# Answer
> 2 votes
It is possible to show ALL$\_{TM}$ is undecidable by Rice's theorem.

Where ALL$\_{TM}$ = {\<M\>, M is a TM and L(M) = $\Sigma^\*$}

Take two TMs M$\_1$ and M$\_2$ where L(M$\_1$) = L(M$\_2$).

Because both recognize the same language,

* if $\<M\_1\>$ $\in$ ALL$\_{TM}$ then $\<M\_2\>$ is too.
* if $\<M\_1\>$ $\notin$ ALL$\_{TM}$ then $\<M\_2\>$ isn't as well.

So they either both have descriptions in ALL$\_{TM}$, or none of them.

It is non-trivial:

* There trivially exists a TM M$\_1$ that accepts on all inputs $w \in$ $\Sigma^\*$.
* There trivially exists a TM M$\_2$ that recognizes $L(M\_2) = \\{ab\\}$, which is clearly not in $\textit{ALL}\_{TM}$

Now, by Rice's theorem, it is proven that ALL$\_{TM}$ is undecidable.

# Answer
> 2 votes
You can reduce from $H\_{TM}$:

For input $\<M,w\>$ return (the encoding) for a machine $M\_ {M,w}$ such that on input $x$:

1. Simulate $M(w)$
2. $Accept$

It’s easy to show $M\_{M,w} \in ALL\_{TM} \leftrightarrow \<M,w\>\in H\_{TM}$

---
Tags: computability, reductions, undecidability
---


# Question
Title: If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x
**Statement:** If G has no simple path on x vertices ,then the treewidth of G is upper bounded by x.

Hint: Begin by computing a DFS tree, and prove an upper bound on its height.

I am supposed to prove the above statement. I tried but without success. I would be happy If you can help me to solve, thanks in advance.

# Answer
> 3 votes
Suppose for simplicity that $G$ is connected. Otherwise the following argument works for each connected component of $G$.

Pick an arbitrary vertex $v$ of $G$ and let $T$ be any DFS tree of $G$ rooted at $v$. If the height $h$ of $T$ was larger than $x$ then there would be a simple path from $v$ to a leaf of $T$ of length at least $x+1$, which is a contradiction. Therefore $h \le x$.

Define a tree decomposition by replacing each vertex $v$ of $T$ with a bag containing all the (not necessarily proper) ancestors of $v$ in $T$. Notice that the endpoints of each edge $(u,v)$ in $G$ are in an ancestor-descendant relation in $T$, therefore either $u$'s bag contains $v$ or $v$'s bag contains $u$. The other properties of a tree decomposition are trivial to check.

The size of the largest bag is then at most $x+1$, and hence the treewidth of $G$ is at most $x$.

---
Tags: graphs, trees, treewidth
---


# Question
Title: Path connecting certain vertices in a neural graph
Consider a special kind of graph where the nodes can be partitioned into $n$ layers. There are edges only between successive layers and no edges between the nodes of any given layer. So for example, the nodes in layer-1 are connected only to the nodes in layer-2, the nodes in layer-2 are connected only to the ones in layer-3 and so on. I call such a graph a "neural graph" since neural networks happen to look like this. Also note that such graphs are bi-partite since all nodes can be colored with two colors in a way that no edge has the same color on both ends.

I'm given a set of nodes, each belonging to different layers in the graph. I need to find any path (represented as an array of nodes) that starts at layer $1$, ends at layer $n$ and necessarily goes through all these nodes in the set. If no such path exists, the algorithm should return an empty array. Any ideas for doing this efficiently?

The graph can be represented in any representation, but adjacency list is preferred.

# Answer
Use BFS from some arbitrary node $v$ in that set. Then, denote by $u\_1,\dots,u\_k$ the nodes that you want to go through, and take the path $u\_1\rightsquigarrow v\rightsquigarrow u\_2 \rightsquigarrow v \rightsquigarrow\dots\rightsquigarrow u\_k$.

If you want to start at the first layer and end at the last layer then just append a path from any node on the first layer to $v$ and then to $u\_1$, and also append a path from $u\_k$ to $v$ to some node on the last layer.
> 1 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Is the statement "Control unit controls overall operations of computer." true or false
I was tutoring a grade 4 student about CPU and I got confused as there are also the other units of a cpu like arithmetic and logic unit and memory unit. So, is the above statement actually true even if ALU is the one which does the arithmetic and logical operations?

# Answer
> 0 votes
Well true, sort of.

In simple terms: The control unit, regardless of how it is implemented, directs the activities of all of the other processor units.

However: It does so by decoding the instructions fetched from memory, the program.

So ultimately the program controls what gets done.

# Answer
> 0 votes
Oh well. To be honest, I haven't heard any part of a computer being called a general "control unit" for a while. There are parts like a "power control unit" which controls power, your car may have an "engine control unit", etc., and there are wikipedia articles about a "control unit", but you won't have a control unit in a modern computer.

Your computer has a CPU (Central Processing Unit) which will execute instructions. The CPU will be divided into several units: A unit controlling memory, a unit controlling cache memory, a unit reading and decoding instructions and distributing the instructions to usually several execution units, and so on. Certain units will be connected to certain other ones, instructing one unit what to do and taking instructions from some other unit, but there is no unit having overall control.

So right now, with a current non-trivial CPU, I'd say there is no control unit controlling overall operations of a computer.

# Answer
> 0 votes
A short answer would be – yes, you can say that the control unit is responsible for the overall operation of the CPU.

More specifically, it controls the retrieval of instruction from the primary memory as well as the sequence of their execution. It is responsible for *providing* the ALU with the data that needs to be processed as well as the *instructions on how* the data should be processed. So in the machine instruction cycle (fetch-execute cycle), the CU is responsible for loading new commands and instructions from the primary memory (RAM), decoding these commands, and then later storing them back in the primary memory (through buses). So even though the ALU actually executes the instructions while carrying out the arithmetic and logical calculations, I guess it's safe to say that the overall control of the CPU is done by the control unit.

---
Tags: computer-architecture
---


# Question
Title: Proof the probability of a collision for a hash function
I don't know how to prove the following:

Let $a$ be randomly chosen out of $\\{ 1,..., p-1\\}$ and $b$ randomly chosen out of $\\{ 0,..., p-1\\}$. Let $m$ be a natural number smaller than a prime number $p$. Let $ h\_{a,b}:$ $\\{ 0,..., p-1\\} \to \\{0, ..., m-1 \\}$ which is defined as $ h\_{a,b} = (ax + b \mod p) \mod m$. Prove for all natural numbers $x, y$ with $x \< y \< p$: $ P\_{a,b}(h\_{a,b}(x)=h\_{a,b}(y)) \le \frac{1}{m}$ where $P$ is the probability.

# Answer
Let $k\_{a,b}(x) = ax + b \bmod{p}$. If $x \neq y$ then $k\_{a,b}(x), k\_{a,b}(y)$ is a random pair of distinct numbers in $\\{0,\ldots,p-1\\}$. Therefore we have reduced your question into the following one:

> Show that if $x \neq y$ are random distinct numbers in $\\{0,\ldots,p-1\\}$, then $$\Pr\[x \bmod m = y \bmod m\] \leq \frac{1}{m}.$$

Suppose that $p = dm + r$, where $1 \leq r \leq m-1$. Then $\Pr\[x \bmod m = c\]$ is either $d/p$ (for $c \ge r$) or $(d+1)/p$ (for $c \< r$). It follows that $$ \Pr\[x \bmod m = y \bmod m\] = r \frac{(d+1)d}{p(p-1)} + (m-r) \frac{d(d-1)}{p(p-1)} = \frac{(p-m+r)d}{p(p-1)}. $$ Since $r \< m$, we have $\frac{p-m+r}{p-1} \leq 1$. Also, $\frac{d}{p} \leq \frac{d}{dm} = \frac{1}{m}$. Altogether, we obtain an upper bound of $\frac{1}{m}$.
> -1 votes

---
Tags: hashing
---


# Question
Title: What will happen to LOGSPACE if P=PSPACE?
If P=PSPACE then by padding argument EXPTIME=EXPSPACE.But what about class L(Logarithmic space)?What will it be equal to?I can't think it as equal to DLOGTIME.There are problems that can be solved in constant space which are contained in L.But many of them can't be solved in logarithmic time like linear search. So do they belong to a certain subclass of P?

# Answer
> 1 votes
Equalities between complexity classes transfer *upwards* by padding arguments, not *downwards*. The assumption $\mathrm{P = PSPACE}$ is not known to imply the collapse of $\mathrm L$ to anything else. (It does, however, imply $\mathrm{L\ne P}$.)

---
Tags: complexity-theory
---


# Question
Title: Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters
I am looking for the computational complexity of the following problem.

Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same cluster are satisfiable together.

Constraints can be in any type, such as Boolean logic or CSP and you can assume that there is an `S()` function that takes a set of constraints and decides the satisfiability of these constraints.

For instance assume that the following set of constraints in Boolean logic for the Boolean parameters p1, p2, p3, and p4 are given.

```
C = {“p1”, “p1 & p2”, “!p1 & p2”, “p3 & p4”, “!p4”}

```

This set can be divided into 2 satisfiable clusters as follows:

```
 // A solution for C1 can be p1=True, p2=True, p3=True, p4=True
C1 = {“p1”, “p1 & p2”, “p3 & p4”}

// A solution for C2 can be p1=False, p2=True, p3=True, p4=False
C2 = {“!p1 & p2”, “!p4”}

```

Another example would be:

```
C = {"x>1", "x!=y", "y==1", "x+y<1", "x+1<2*y", "x==1"} // where both x and y are integers.

```

This constraint set can be divided into 3 satisfiable clusters as follows:

```
 // A solution for C1 can be x=5, y=1
C1 = {"x>1", "x!=y", "y==1"}

// A solution for C2 can be x=0, y=-1
C2 = {"x+y<1"}

// A solution for C3 can be x=1, y=2
C3 = {"x+1<2*y", "x==1"}

```

Here is my informal approach for the computation complexity of the problem:

> First, I consider the decision version of the problem: Given a set of constraints, can this set be partitioned into k satisfiable clusters? Since we assume that an `S()` function is always provided for the given constraint type, a solution can be easily verified whether it becomes satisfiable or not using the given `S()` function. Then, it becomes NP. About the hardness of the problem, let's assume that we are concerned with SAT (Boolean satisfiability problem). In this scenario, considering that the SAT problem is NP-Complete, the problem itself becomes NP-hard since deciding whether a set of constraints can be partitioned into 1 satisfiable cluster is a harder problem than SAT. Therefore, the computational complexity of my problem depends on the constraint used in the problem. That is, satisfiability of any constraint problem that is NP-complete makes my problem is NP-hard.

What do you think about my approach? And if you think it is not correct or not complete, can you suggest another approach?

# Answer
I think your problem is NP-hard for k = 1 since that is equivalent to SAT, but it is in P for k \> 1.

For example, a SAT instance can be easily decomposed into two satisfiable subformulas. Go from SAT to 3SAT using the usual methods, unit propagate, then sort what remains into Horn and anti-Horn sets, each of which is trivially satisfiable (or can be made so by tossing one of any $x \land \lnot{x}$ pair into the other pile). The Horn and anti-Horn sets can be further divided into as many satisfiable subsets as desired.
> 1 votes

---
Tags: complexity-theory, np-complete, np-hard, satisfiability, decision-problem
---


# Question
Title: Find strong connected components of a Graph in O(V^2 + V*E) time complexity
Given is an algorithm that finds the transitive shell of a graph:

```
Transitive Shell(G)
 for v in V
   BFS(G,s)
   for w in V with d(w) < infinity
   E* = E* U (s,w)

```

I've been knacking at this problem for a while, and I can't come up with a solution. Also no results for this on Google either. Any help is appreciated

# Answer
> 1 votes
Take a look at this explanation. It is pretty well known that we can find all strongly connected components in $O(|V|+|E|)$.

The basic "gist" is to use DFS from a node $v$, and then transpose the graph, and apply DFS again. The nodes that have been explored in **both** DFS instances, *must* be the strongly connected component that $v$ resides in. Apply this a few times, and you will end up finding all strongly connected components (but you need to be a bit more careful in order to ensure the time complexity stays $O(|V|+|E|)$).

---
Tags: algorithms
---


# Question
Title: Show why the following post's correspondence problem is unsolvable
We have the following pairs of strings. $$\begin{bmatrix} aa\\b \end{bmatrix} \begin{bmatrix} ba\\baa \end{bmatrix} \begin{bmatrix} aba\\a \end{bmatrix}$$

The problem is now, to find a concatenation of those pairs, such that the resulting string of the upper row equals the string of the lower row. E.g. if $$\begin{bmatrix} aa\\aab \end{bmatrix} \begin{bmatrix} bb\\ba \end{bmatrix} \begin{bmatrix} abb\\b \end{bmatrix}$$

The solution would be 'aabbaaabb' $$\begin{bmatrix} aa\\aab \end{bmatrix} \begin{bmatrix} bb\\ba \end{bmatrix} \begin{bmatrix} aa\\aab \end{bmatrix} \begin{bmatrix} abb\\b \end{bmatrix}$$

The initial problem seems unsolvable. My argumentation is, that the solution can't end on $b$, because in the upper row no string ends on $b$. Thus, the solution has to end with an $a$ and only $\begin{bmatrix} ba\\baa \end{bmatrix} \begin{bmatrix} aba\\a \end{bmatrix}$ are left. I have been trying to continue on this argumentation for quite some time now, but could not end up with a logic explanation. Is this approach even correct or am I completely off track?

# Answer
Let $x,y,z$ be the number of times that we use the first, second and third pair, respectively. Equating the number of $b$s we get $$y+z=x+y$$ and hence $$x=z$$ Therefore, the number of times the first pair is used in a solution must be equal to the number of times the third pair is used.

Let me call the three given pairs $p\_1,p\_2,p\_3$, respectively. Note that any occurrence of a $p\_1$ cannot followed by a $p\_2$, a $p\_1$, or be the last pair. This is because in the top string a $b$ is always followed by an $a$, while any of these cases would produce in the bottom string either two consecutive $b$s or a $b$ that is the last character. Therefore the occurrences of $p\_1$ and $p\_3$ in a solution must appear as the patter $p\_1p\_3$.

Finally, note that the last four pairs of a solution must be $p\_3\mathbf{p\_3}p\_1p\_3$. This cannot be since we computed that the number of $p\_1$ pairs must be the same as the number of $p\_3$ pairs and the third to last pair is a $p\_3$ that is not preceded by a $p\_1$.

---

To show that a solution must end with $p\_3p\_3p\_1p\_3$ we look at the top and bottom strings that get formed. You saw that $p\_1$ cannot be the last pair used. Likewise $p\_2$ cannot be the last pair, since the second to last character in the top would be $b$, while it would be $a$ for the bottom string. Using $p\_3$ as last pair we have $$\begin{array}{r}\color{red}{aba}\\\color{red}{a}\end{array}$$ We need a $b$ as second to last character for the bottom string. So, we use $p\_1$ as second to last pair. We get $$\begin{array}{r}\color{green}{aa}\color{red}{aba}\\\color{green}{b}\color{red}{a}\end{array}$$ Now we need an $a$ for the bottom string. If we use $p\_2$ we would get a $b$ as a fifth to last character in the bottom string, but the top string has an $a$ in that position. Therefore, the third to last pair must be $p\_3$. We get $$\begin{array}{r}\color{red}{aba}\color{green}{aa}\color{red}{aba}\\\color{red}{a}\color{green}{b}\color{red}{a}\end{array}$$ Once again we cannot use $p\_2$ to provide the $a$ that is needed next in the bottom string, since it would give a $b$ in the sixth to last character in the bottom. However, the top string has an $a$ in that position. Therefore, we are forced to use another $p\_3$. So, we got the ending $p\_3p\_3p\_1p\_3$.
> 3 votes

---
Tags: decision-problem
---


# Question
Title: Given an array arr[] of N integers. Do the following operation n-1 times
For every Kth operation: Right rotate the array clockwise by 1. Delete the (n-k+1)th last element.

eg:

A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, 3, 4, 5} and delete the last element that is {5} so A = {6, 1, 2, 3, 4}. Again rotate the array for the second time and deletes the second last element that is {2} so A = {4, 6, 1, 3}, doing these steps when he reaches 4th time, 4th last element does not exists so he deletes 1st element ie {1} so A={3, 6}. So continuing this procedure the last element in A is {3}, so outputp will be 3

How to solve this?

# Answer
> 1 votes
It seems some kind of problem with mathematical solution (try to find the position with a closed math formula). However, here is an algorithmic approach that runs in $O(n \log^2 n)$.

Using segment tree / Fenwick tree, you can find the number of removed elements in a range (using prefix sums). Keep track of the offset (imagine having a pointer on the first element (imagine a cyclic arry and in each step we push it one element to the left instead of rotating right). Using binary search on the Fenwick tree, you can find the index of element having the distance you are looking for the offset element. Nite that after deleting half of the elements $k$ will be greater than the size and hence you can directly output the first unremoved element before the offset.

# Answer
> 0 votes
there's some problem with the question.There shouldnt be n-k+1 th element rather it shiuld be (current value of n)-(current operation no.)element

here's the code in c++:

#include using namespace std; int main() { //perform operation n-1 times // first right rotation // then deletion of element

```
int n;
cin >> n;
int arr[n];
int aux[n];

for (int i = 0; i < n; i++)
{
    cin >> arr[i];
} //taking input of the array
for (int i = 0; i < n; i++)
{
    aux[i] = arr[i];
} //aux array creation
int temp = n;
for (int j = 1; j <= temp - 1; j++)
{
    //right rot first
    for (int z = 0; z <= n - 2; z++)
    {
        arr[z + 1] = aux[z];
    }
    arr[0] = aux[n - 1];

```

for(int t=0;t\<n;t++){aux\[t\]=arr\[t\];}

```
    //now delete the reqd element
    int x = n - j; //deletion of this idx(left shift)
    if (x > 0)
    {
        for (int d = x; d < n - 1; d++)
        {

            arr[d] = aux[d + 1];
        }
    }
    else
    {
        for (int f = 0; f < n - 1; f++)
        {
            arr[f] = aux[f + 1];
        }
    }
    n--;

    for (int u = 0; u < n; u++)
    {
        aux[u] = arr[u];
    }
}

cout << arr[0];
return 0;

```

} ////PLZ LET ME KNOW IF U LIKED MY APPROACH

---
Tags: arrays
---


# Question
Title: Why is it useful to transform 0-1 integer programming problem into SAT problem?
There are several researches studying translating 0-1 integer programming into CNF form. For example, this paper and this C++ library. As the lecture notes here goes, translating 0-1 integer programming problem into CNF form might introduce $O(n\log^2 n)$ extra variables. However, it seems that the time complexity of solving satisfiability problem is connected to the number of variables. For example, to my best knowledge, the fastest algorithm to solve 3-SAT problem has time complexity about $O(1.3^n)$ which is to the power of $n$. Therefore, if we introduce $n\log^2 n$ more auxiliary variables, the time complexity of solving the 0-1 integer programming problem may be kind of like $O(c^{2n}n^{\log n})$, which seems to be a huge cost. Also, the time complexity of the translating process might also be taken into consideration. I was wondering if it is still efficient to transform the 0-1 integer programming first rather than using other tools, for example, this paper to solve it directly.

I am new to theory of satisfiability and its connection to 0-1 integer programming. I do apologize that this question might be trivial. Thanks for any help!

# Answer
> 4 votes
One important thing to know about ILP and 3SAT is that, often, on problem instances that arise on practice, they can be solved faster than a worst-case analysis would indicate. As such, worst-case running time analysis isn't necessarily predictive of what you'll see in practice.

Your big-O running times reflect worst-case running time of certain algorithms. The worst case is certainly terrible. However, off-the-shelf ILP solvers and SAT solvers have heuristics that sometimes do significantly better -- though their worst case remains terrible.

So, if you care about worst-case running times, converting to CNF might not be the best approach. But if you care about practical solutions, you could try either using an ILP solver, or you could try converting to CNF and using a SAT solver. Depending on the problem, it is possible that either might be effective, or that neither one is effective.

---
Tags: logic, satisfiability, integer-programming
---


# Question
Title: Is it correct to perform feature distillation when both the teacher and student model architectures are completely different
When the architectures of the teacher and student networks do not just vary by network depths but are completely different, is it logically correct to distill knowledge at feature level (say from middle layer) in such scenario? Thanks in advance

# Answer
There is no such thing as "correct" or "incorrect". The only question is whether it works well enough or not. The only way to figure that out is to try it and see. (It's not clear to me why you'd distill at the middle layer as opposed to the last or next-to-last layer, but you can do it.)
> 0 votes

---
Tags: computation-models, computer-vision
---


# Question
Title: How to search all possible combinations for a product?
I'm looking for the name of the problem stated below or, if available, even the algorithm to solve it. This is a hypothetical idea of mine, I don't actually have the necessary data to implement it. But I like the algorithm challenge behind it and would like to know more about it. I just can't find the name of the problem to look for further information on it.

I have the idea to build a search for computer builds that are dynamically generated from components. So the database knows that there are CPUs, Motherboards, RAMs etc and how these components can work together (e.g. an Intel 10th gen cpu can only work with specific motherboards). Based on that it can generate a complete build, it combines a CPU with a fitting motherboard, adds some compatible RAM, and a PSU with enough power to run the whole thing, tadaa a computer build. There would be very many such builds since you can combine the same cpu with many other motherboards, RAMs and PSUs. To limit the results, the user should be able to search based on some parameters and get complete computer builds suggested. For example if he searches for a computer that has a specific Motherboard, then the result only contains Builds with that motherboard and compatible CPUs/RAMs. Now he can further limit the total power consumption of the build to say 300 W and then the result has to contain all combinations of the given Motherboard with CPUs/RAMs that do not use more than the given amount of power. e.g. RAM r may not be possible with CPU c but with CPU d, because d uses less power.

Brute force searching this would require to calculate all the possible builds which can be very many. I can improve on this a bit by using backtracking. I would like to have the name of this problem class to search for other solutions on the internet. Thank you.

# Answer
> 1 votes
In full generality (no/little compatibility restrictions), this means you have to explore all possible combinations. The time to do that will be huge if there are many classes of components with many alternatives each.Your best bet is to order the component classes in some way, and then use a backtracking type search to explore the alternatives. It doesn't look like you can use some way to divide the subtasks into independent parts and apply e.g. dynamic programming, but perhaps you can split it into partial tasks (e.g. CPU/motherboard, GPU, storage subsystem, ...) and solve the parts separately.

* Order the component clases in order of increasing compatibility with the next type, so as to narrow down the search tree early
* Use heuristics, i.e., order each component class by some measure of how likely they are to satisfy the overall goal
* See how to to evaluate (or at least bound) your overall goal for incomplete designs, so you can abort a branch of the search early if it can't be fulfilled (if optimizing, perhaps use branch and bound).

---
Tags: reference-request, search-algorithms
---


# Question
Title: Turing machine halts on input $a^m$ with $a^{m^2}$ written on tape
I am learning Turing machine in automata. Following problem might be simple, as that's the first question on Turing machines in my textbook, however I am not sure if I am doing it efficiently.

> Give Turing machine with input alphabet {a} that on input $a^m$ halts with $a^{m^2}$ written on its tape.

My approach: The machine will first move right seeing an a on each position on tape. So there will be $m+1$ states $q\_0$ to $q\_m$ defined, on which the machine will move sequentially seeing an $a$. If machine meets the end of the string seeing an empty position at state $q\_m$, it will move left $\sqrt{m}$ times, and halt.

The problems,

1. $m$ is not given here, so m can be anything, $1,4,9,25,..$, infinite possibilities. How many states shall I define then?
2. As the Turing machine can not calculate $\sqrt{m}$, I am defining newer states like $q\_{41},q\_{42}$ etc (If the Turing machine sees end of string at state $q\_4$, then it moves left to state $q\_{41}$, then to $q\_{42}$, then it halts). This way also, many numbers of states to be defined, as $\sqrt{m}$ increases with $m$. So my transition table is becoming huge and infinite.

Can someone suggest a better way to define this Turing machine?

# Answer
What you give is not a Turing machine since the number of states is not fixed but rather it depends on the length of the input.

Here is a possible Turing machine that solves the problem. Its tape alphabet is $\\{\varepsilon, a, a', b, t, t'\\}$ where $\varepsilon$ denotes the blank symbol, $a'$ can be thought as a special $a$ symbol that has been already "processed", and $t$, $t'$ are temporary symbols.

It is convenient to first describe a simpler subroutine. If the tape contains $m$ symbols that are either $a$s or $a'$s then the following subroutine appends $m$ $b$s to the tape. First repeat the following:

* Search for the leftmost $a$ or $a'$, if any. This can be done by moving left until $\varepsilon$ is found, then moving right until one of $a$, $a'$, or $\varepsilon$ is found.
* If no $a$ or $a'$ exists then exit the loop.
* If the current symbol is $a$, replace it with $t$. Otherwise replace it with $t'$.
* Move right until the first $\varepsilon$ symbol is encountered.
* Replace the current symbol with $b$.

At the end of the loop replace all $t$s with $a$s and all $t'$s with $a'$s.

The final Turing machine repeats the following steps:

* Search for the leftmost $a$, if any.
* If no such $a$ exists then exit the loop.
* Replace the current symbol with $a'$.
* Invoke the above subroutine.

At the end of the loop replace all $a'$s with $\varepsilon$s and all $b$s with $a$s. Halt.
> 0 votes

---
Tags: turing-machines, automata
---


# Question
Title: Is $B=\{a^n b^m \mid n \not= 2m\}$ a context free grammar
I was trying to find a grammar that generates $B=\\{a^n b^m \mid n \not= 2m\\}$ but I couldn't so I'm not sure that it is a CFG.
This is what I did : $$ S\rightarrow X \mid aX \mid a \mid b \mid \epsilon $$ $$ X\rightarrow aa Xb \mid Y \mid Z $$ $$ Y\rightarrow aY \mid a $$ $$ Z\rightarrow bZ \mid b $$

# Answer
If $n \neq 2m$ then either $n \< 2m$ or $n \> 2m$.

A grammar for the former case is: $$ S\_1 \to XY \mid aXY\\ X \to aaXb \mid \varepsilon \\ Y \to bY \mid b $$ where $X$ generates all words of the form $a^{2k} b^k$ for some positive $k$.

A grammar for the latter case is: $$ S\_2 \to ZX \mid Z\\ X \to aaXb \mid \varepsilon \\ Z \to aZ \mid a $$

A grammar for your language can be obtained as the union of the above two grammars.
> 3 votes

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


# Question
Title: Is Programming Witchcraft or Actual Magic?
I may sound stupid, but few people say that programming is witchcraft (maybe Joking) as a Christian I Must take it seriously, because I am planning to become Software Architect in the future. Honestly I do not think it is like Witchcraft, since it has nothing to do with evil spiritual world. How can compiler translate Code into machine code... Please take seriously and answer ASAP. Thank you !

# Answer
In my opinion, programming is magic: you get into a small dark room and smash keyboards and poof you got infinite money.

Just kidding! programming isn't magic at all, nor witchcraft. If you will learn computer science or electronics, you will know how computers actually work. There is a lot of complex physics going on behind the scenes, that allows computers to actually compute. Programmers just know what kinds of things the computer can compute, and they know how to specify it in the computer so it will do what they want: this is called programming.

Higher level programs will all get compiled into something called "machine code", which basically is just all operations a computer knows how to calculate. Of course, this "compilation" process is also some program people wrote, that is also running in "machine code". In fact, the very first compiler just *had* to be written in machine code, because there was nothing to compile it to machine code otherwise. Then, all other programs and compilers will build upon previous ones, until we reach what we have today.
> 2 votes

---
Tags: programming-languages
---


# Question
Title: Can this recursive algorithm be converted to an iterative algorithm in O(1) space?
I am trying to convert this recursive algorithm

```
isqrt(n){

    if(n==0){
        return 0;
    }
    a = 2*isqrt(n/4)+1;
    if(n<(a*a)){
        return a-1;
    } else {
        return a;
    }

}

```

into an iterative algorithm. So far I was able to do this:

```
isqrt(n){

    vector c;
    for(d = n; d>0; d = d/4){
        c.push_back(d);
    }
    res = 0;
    for(con = c.size(); con>0; con = con-1){
        a = 2*res+1;
        if(c[con-1]<(a*a)){
            res = a-1;
        } else {
            res = a;
        }
    }
    return res;

}

```

This could be a solution to my problem, but my approach was simply "simulating the function stack" inside the function itself with the vector, which works but still runs in O(floor(log4(n))) space, which in my use case is greatly undesirable. Is there any way to modify this algorithm in an iterative algorithm that runs in O(1) space? If possible the time complexity should remain the same.

# Answer
Converting it into an iterative algorithm is somewhat vague and there could be many different ways to do it. One way could be the following:

```
isqrt(n){
  if (n==0){
    return 0;
  }
  a = 1;
  b = a*a;
  while (true){
    if (n < b){
      return a-1;
    } else {
      b += 2*a+1;
      a += 1;
    }
  }
}

```

Other options can be applying Newton's algorithm.

There was the question in the comments about which number to use for the initial point in Newton's algorithm. One can use $x\_0=n//2$. Any positive number will work.

---

There was also the question of ensuring logarithmic time complexity. Observe that in the set $\[n\]=\\{0,1,2,\ldots,n\\}$ the elements satisfying $x^2\leq n$ are all less than or equal to those satisfying $x^2\geq n$. The integer square root is the largest element of $\[n\]$ satisfying $x^2\leq n$. Therefore, we can find it using binary search.

```
isqrt(n){
  if (n==1){
    return n;
  }
  L = 0;
  R = n//2;
  while (L < R){
    m = L + (R-L)//2;
    s = m*m;
    if (L == m){
      if (s <= n){
        return L;
      } else {
        return R;
      }
    }
    if (s < n){
      L = m;
    } else if (s > m) {
      R = m;
    } else {
      return m;
    }
  }
  return L;
}

```
> 1 votes

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


# Question
Title: Mistake in Karp's paper on NP-Complete problems?
I read on a blog that there are mistakes in Karp's paper where he proved that 0-1 programming is NP-Complete, but I couldn't find it, can anyone explain? And I doubt that there are also mistakes where he proved Steiner Tree Problem is NP-Compelete but not sure.

The blog post a little old and I thought asking the writer of the blog may not receive answer quickly enough. I didn't find any referrence in other places so I thought this question may worth asking.

# Answer
To cite the blog post:

> For arguments sake, lets say that in Karp's classic paper Reducibility Among Combinatorial Problems, where he proves 21 problems NP-compete, he made a mistake on 0-1 programming.

That is, the blog author does *not* state that there *is* a mistake. It is just a gedankenexperiment.

That is, of course, not to say that there is none.
> 6 votes

# Answer
It seems that reduction SAT to 0-1 programming contains a mistake. Let we have a simple formula of 1 clause: (x V y V z). Following the Karp's reduction, we will get the equation x + y + z = 1, which is not eqivalent to the source boolean formula, However the unequality x + y + x \>= 1 is equivalent.
> 1 votes

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


title: Recursive languages

text:
# Question
Title: Recursive languages
I need to prove if the following languages are recursive:

1. $A\_1 \subseteq \\{0, . . . , 9\\}^∗ $ consists of all finite sequences of $\pi$ without the decimal point.

We may thus write $A\_1 = \\{3,31,314,3141, 31415, 314159,... \\}.$ The idea is to apply the Turing machine and prove if it can recognize a given string or word belongs to the language or not.

2. $A\_2 \subseteq \\{0, . . . , 9\\}^∗ $ consists of the decimal representation of all natural numbers $n \in \mathbb{N}$ such that in the decimal represenation of $\pi$ there is a sequence of at least $n$ fives, i.e. 555...5.

Since we assume that $ n$ is finite, $n \in \mathbb{N}$, we exclude sequences of infinity length. Here again, we may want to use Turing machines for deciding if an input string belongs or not to the language.

Can somebody provide some hints or a solution proposal? Many thanks.

# Answer
For (1) you can take the length of the input. There are many algorithms to compute digits of $\pi$. Use any of them to compute the same number of digits as the input and compare.

For (2) we observe that when some $n\in A\_2$, then all $k\<n$ also are in $A\_2$. Therefore, either all $n\in A\_2$ or there is a maximum $n=n\_0$ that belongs to $A\_2$. Therefore, either the machine that immediately halts or the machine that halts if and only if $n\leq n\_0$ decides $A\_2$. It is however, very hard to tell which machine is the right one.
> 1 votes

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


# Question
Title: Approximate duplicate sampling from a stream
The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal.

> Design an algorithm that takes in a stream $z\_{1}, . . . , z\_{M}$ of $M$ integers in $\mathbb{Z\_{n}}$ and at any time $t$ can output a uniformly random element in $z\_{1}, . . . , z\_{t}$ . Your algorithm may use at most polynomial in $\lg(n)$ and $\lg(M)$ space.

This is an instance of Reservoir Sampling with reservoir size of $1$.

> For a stream $S = z\_{1}, . . . , z\_{2n}$ of $2n$ integers in $\[n\]$, we call $j ∈ \[n\]$ a duplicate element if it occurs more than once. Design an algorithm that takes in $S$ as input and with probability at least $1 − \frac{1}{n}$ outputs a duplicate element. Your algorithm may use at most polynomial in $\lg(n)$ space.

Attempts

Consider the naive approach of consuming the entire stream and sampling. At least $n$ elements in the stream have duplicates. Since each of the $2n$ elements in the stream is equally likely to be sampled, the probability of sampling a duplicate element is at least $\frac{n}{2n} = \frac{1}{2}$, which is not nearly as tight a bound as $1 - \frac{1}{n}$.

On the other hand, Reservoir sampling produces a simple random sample, so maybe we could model the reservoir as sampling from a multiset and compute the probability of there being a duplicate using multinomial distribution? Although, the multinomial requires independent trials.

I don't see a path forward for part $b$ of the problem yet. Any hints?

# Answer
Since I realized too late you only asked for a hint, I spoilered my full answer. The hint is: use reservoir sampling with $\log n$ integers and check for duplicates during the sampling.

> Perform your reservoir sampling algorithm with $\log n$ integers. This takes $O\left(\log{\left(n\right)}^2\right)$ bits of space and is thus allowed. However, at each step, before (potentially) replacing your reservoir, check if the new element from the stream equals one in the reservoir. If yes, return the found duplicate immediately.
> Let's assume we face an adversary that does not output a duplicate unless it has to. So we assume the first $n$ integers do not contain any duplicate. After those first $n$ integers at any point we store a completely uniform random sample of $\log n$ distinct integers from the first $k$ elements from the stream. Thus the probability that the next element of the stream is a duplicate of a currently stored one is $\frac{\log n}{n}$, and the adversary can do nothing to decrease these odds. So overall the probability that we fail to find a duplicate this way is at most ${\left(1 - \frac{\log n}{n}\right)}^n$.
> Now using the inequality $(1-x)^r \leq e^{-xr}$ we have $${\left(1 - \frac{\log n}{n}\right)}^{n} \leq e^{-\log n} = 1/n.$$
> 1 votes

# Answer
Let us denote by $S(m,c,\epsilon)$ the space (number of words) needed to find a duplicate in an array of size $cm$ which contains at most $m$ distinct integers, with error probability at most $\epsilon$. We assume that $c \> 1$.

Let $\delta \> 0$. We consider two possibilities:

* Both halves of the array contain at least $(1 + \delta)(m/2)$ distinct integers.
* One of the halves of the array contains at most $(1+\delta)(m/2)$ distinct integers.

In the first case, the two halves have at least $\delta m$ elements in common. If we sample an element from the first half, the probability that we sample one of these common elements is $\frac{\delta m}{c(m/2)} = 2\delta/c$. If we sample $k$ elements from the first half (using reservoir sampling), we hit one of these elements with probability $1 - (1-2\delta/c)^k$. Choosing $k = \log\_{1-2\delta/c} \epsilon \approx \frac{c}{2\delta} \log (1/\epsilon)$, the failure probability is at most $\epsilon$.

In the second case, we simply run the same algorithm on each of the halves. Each of these halves is of size $cm/2$ and contains at most $(1+\delta)(m/2)$ distinct integers. Since $$ \frac{cm/2}{(1+\delta)(m/2)} = \frac{c}{1+\delta}, $$ we run the algorithm with $c \gets \frac{c}{1+\delta}$.

Since we don't know which of the two cases holds, we run the two strategies in parallel. In total, we obtain $$ S(m,c,\epsilon) \leq \frac{c}{2\delta} \log(1/\epsilon) + S\bigl(m/2,\frac{c}{1+\delta},\epsilon\bigr). $$

We are interested in $S(n,2,1/n)$. We choose $\delta = \gamma/\log n$ to ensure that the value of $c$ along the process is always at least $$ \frac{2}{(1 + \gamma/\log n)^{\log n}} \approx \frac{2}{e^\gamma}, $$ which will be larger than $1$ for an appropriate constant $\gamma$. The total space is $$ \frac{1}{\delta} \log(1/\epsilon) \cdot \log n = O(\log^3 n). $$ (We take as base case $m = 1$, which requires no memory.)
> 1 votes

---
Tags: algorithms, approximation, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: Does higher cpi give better performance?
Does higher cpi give better performance?

Lets say there is a code and we can run it by 3 methods.

1 cpi for single cycle

99 cpi for multi cycle

70 cpi for pipeline

Multi cycle has the highest cpi for this code. So is multi cycle method the best for this code?

# Answer
CPI = cycled per instruction. Higher CPI = more cycles = more time to get the work done. So it’s worse.
> 1 votes

---
Tags: cpu-pipelines, mips
---


# Question
Title: How do I search for Verification of Quantum Computing
So, in quantum computing, each qbit has a 50/50 chance of being in either the state of 1 or 0 when you measure it. Simple enough.

But I've heard reports a while ago about some company having successfully added two relatively small numbers and gotten out the right answer the majority of the time. The question I am trying to solve is: How? How would you verify a quantum result (without assuming you have the answer already available that you can compare it to)?

That, however, is not what I'm asking of this Stack Exchange. Instead, I am wanting to know what search terms in Google I can use to find this answer. "how to verify quantum computing results" doesn't turn up anything more than 1 academic paper (which I am actually reasonably confident has the answer I'm looking for). At least with the search, I get nothing more that is relevant to what I'm actually looking for.

Thus why I come here in hopes that someone might actually know what I would need to search to get more relevant results.

# Answer
> 1 votes
The answer is, when working with sufficiently small numbers, we can simulate the quantum process on a classical computer. It might take exponentially longer on the classical computer, but for small numbers, that's still feasible (the exponential of a small number is still not too large).

See Question 6 at Scott Aaronson's FAQ (https://www.scottaaronson.com/blog/?p=4317) as well as part (2) of https://www.scottaaronson.com/blog/?p=4372.

# Answer
> 0 votes
My logic may be off, but here is my take. Consider the following:

1. We want to find possible seeds for an existing and known hashed value.
2. We have a superposition of all possible seed values.
3. We run the superposition through the hashing algorithm to generate a waveform.
4. Run grovers algorithm (or similar) on waveform to reveal likely hash values

Verification process:

```
5. Remove values from the superposition that are not "near" a correct value.

6. Run the algorithm again.

7. Repeat until the waveform is a straight line representing the correct state.

```
8. The seed values remaining in the superposition have a 100% chance of generating the desired hash value.

---
Tags: quantum-computing
---


# Question
Title: Spanning tree whose sum of edge weights are between two boundries
I saw this problem: $\langle G,w,k\_1,k\_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k\_2$ and greater than $k\_1$. The problem says that we can prove this problem is NP-complete with reduction from Subset-Sum problem. First i cant see how is that possible. Second i know that we can solve Minimum Spanning Tree with kruskal , and i saw that we can compute Maximum Spanning Tree by negating the weights for each edge and applying Kruskal’s algorithm. So both of these problems can be solved in polynomial-time. But how this problem could not solved in polynomial-time ?

# Answer
Let $\langle S, t\rangle$ be an instance of subset sum, where $S = \\{x\_1, \dots, x\_n\\}$, and $t, x\_1, \dots, x\_n \in \mathbb{N}^+$.

Create a graph $G = (V,E)$ where $V = \\{u,v\\} \cup S$ and $E$ contains:

* The edge $(u,v)$ of weight $0$.
* For each $x\_i \in S$, an edge $(u, x\_i)$ of weight $x\_i$.
* For each $x\_i \in S$, an edge $(v, x\_i)$ of weight $0$.

There exists a spanning tree of $G$ of total weight between $k\_1 = t$ and $k\_2 = t$ (i.e., exactly $t$) if and only if $\langle S, t \rangle$ is a yes-instance of subset sum.

To see this let $M$ be the edges in a spanning tree $T$ of $G$ of weight $w(T)=t$ and define $X = \\{ x\_i \mid (u, x\_i) \in M \\}$. Clearly $X \subseteq S$ and $\sum\_{x\_i \in X} x\_i = w(T) = t$.

Consider now a set $X \subseteq S$ such that $\sum\_{x\_i \in X} x\_i = t$ and consider the set of edges $M = \\{ (u,x\_i) \mid x\_i \in S \\} \cup \\{ (v,x\_i) \mid x\_i \not\in S \\} \cup \\{(u,v)\\}$. It is easy to see that $M$ induces a tree of total cost $t$.
> 2 votes

# Answer
First of all, when we reduce problem $A$ to $B$ in polynomial time, we display it by $A\le\_p B$, it's means that complexity of any algorithm for solving problem $B$ is at least hard as problem $A$. From this we act as follow:

Suppose you are Given un-dircted weighted graph $G=(V,E,M,\omega)$ with weight function $\omega:E\to \mathbb{R}$, and $k\_1=k\_2=M$. Then reduce finding spanning tree $T$ of $G$ to Integer programming as follow:

$$x\_{ij} = \begin{cases} 1 & \text{if edge $(i,j)$ in } T, \\ 0 & \text{otherwise.}\\ \end{cases}$$

$$\min 1$$

$$\text{S.t }\sum\_{(i,j)\in T}x\_{ij}=n-1$$ $$ \sum\_{(i,j)\in T}x\_{ij}\omega(i,j)=M$$ $$ x\_{i,j}\in\\{0,1\\}$$

Now we formulate Subset-sum with problem as Integer programming as follow:

Suppose given numbers $S=\\{a\_1,a\_2,\dots,a\_n\\}$, and target value $M$, the goal is to find a $S'\subseteq S$ :

$$x\_{i} = \begin{cases} 1 & \text{if } a\_i\text{ appear in solution}, \\ 0 & \text{otherwise.}\\ \end{cases}$$

$$\min 1$$

$$ \text{S.t }\sum\_{i\in S'}a\_ix\_i=M$$ $$ x\_{i}\in\\{0,1\\}$$

So, if we look at the above formulation of the two problems there are some relation between them. Now, i try to convert an instance of Subset-sum to spanning tree problem, to show that finding spanning tree at least hard as subset-sum.

Construct a graph $G'$ with $n+1$ vertices,and weight function $\omega:E\to \mathbb{R}$, and un-dircted edge set $E$ as follow:

$$V=\\{s,a\_1,a\_2,\dots,a\_n\\}$$ $$E=\\{(s,a\_1),(s,a\_2),\dots,(s,a\_n)\\}\cup\\{(a\_1,a\_2),(a\_2,a\_3),\dots,(a\_{n-1},a\_n)\\}. $$ Finally assign weight to each edge as follow $$\forall i\in\\{1,2,\dots,n\\} $$ $$\omega((s,a\_i))=0,\omega((a\_i,a\_{i+1}))=a\_i.$$

Clearly our reduction can be done in polynomial time in size of the input size. So if there is a algorithm $\mathbb{A}$ to find a spanning tree $T$ in $G'$ with $$\sum\_{e\in T}\omega(e)=M$$ in polynomial time of the input size, then we solve subset-sum problem in poly time. **As a result your mentioned problem is NP-complete**.
> 2 votes

# Answer
Try to think what happens when $k\_1=k\_2$. It makes the question much more difficult.

In fact, consider the following reduction from subset sum: Say we have a set of numbers $S=\\{a\_1,\dots,a\_n\\}$ and a target value $t$. Let us choose $k\_1=k\_2=t$, and build the following graph $G$:

$G$ will have $n+1$ nodes: a special node will be called $v$, and another node $u\_i$ for every $1\le i\le n$. We will put an edge between $v$ and $u\_i$ with the cost of $a\_i$, and another edge between $v$ and $u\_i$ with a $0$ cost.

Finding a spanning tree $T$ in this case would be the same as choosing a subset $A$ of $S$, and the sum of the weights of $T$ will be the sum of the values in $A$. Hence, finding a spanning tree $T$ with weight sum equal to $k\_1=k\_2=t$ is equivalent to finding a subset $A\subseteq S$ with sum $t$.

Note: its not hard to do a similar reduction if you want the graph to be simple (i.e, every two nodes have at most one edge between them).
> 1 votes

---
Tags: complexity-theory, time-complexity, np-complete, np-hard, polynomial-time-reductions
---


# Question
Title: Multi Source/Sink Max Flow Alternative Reduction
When solving a multi source/sink max flow problem, the classic reduction to the single source/sink problem is to add a new source and sink node with infinite capacities that connect to/from the existing source/sink nodes.

I was curious about an alternate reduction. It is kind of silly buy I just wanted to sanity check it.

Is it possible to group all the source nodes into one big source node, with all the outgoing edges of the original source nodes now added to the mega source node. We can collapse repeated edges by adding up their capacities. A similar thing can be done for sink nodes.

Let's say I have a solution to the mega source/sink problem. You would have to keep track of which edges in the mega source/sink node correspond to which edges in the original sources/sinks, and choose the same corresponding flow for the original source nodes' edges. For two edges that you collapsed in the mega node by summing their capacities, you can just distribute the flow arbitrarily amongst the original source nodes (maintaining the capacity constraints).

Does this approach fail catastrophically or sound reasonable?

# Answer
That would actually work as well, but it is more cumbersome than just adding a new source and sink.
> 1 votes

---
Tags: network-flow, ford-fulkerson
---


# Question
Title: Convert a PDA with transition for a state to itself to another PDA
Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this?

EDIT (My thoughts):
I guess we can do it. for example in a PDA  we might be able to do this(?)

# Answer
If you replace the $\epsilon$'s with $a$'s then what you did is a possible solution (that is, cloning the transition from $q\_0$ to itself into two identical transitions: $q\_0\rightarrow q\_1$ and $q\_1\rightarrow q\_0)$. **however**, notice that any transition *from* $q\_0$ must also be duplicated to be a transition from $q\_1$. In addition, don't forget to make the duplicated state an accepting state if the original was an accepting state

So, doing this while cloning all transitions and other properties, will ensure that the DFA/PDA/TM will be equivalent.

Notice that in the special case of TM the accepting state will never be duplicated, since it doesn't have any transitions at all.
> 1 votes

---
Tags: turing-machines, finite-automata, pushdown-automata
---


# Question
Title: Dynamic Programming for Feedback Vertex Set - bounded treewidth
Saw it on another post that there is a way of solving FVS in polynomial time if the treewidth is constant, using dynamic programming?...

If I'm given the treewidth of a graph, how do I solve it in time $tw^{O(tw)}\cdot n^{O(1)}$ ?

thank you very much!

# Answer
> 3 votes
I assume you already know how to obtain a tree decomposition. Make the underlying tree directed by picking an arbitrary node as the root.

For a node $t$ of the tree decomposition, let $b(t)$ be the bag at $t$ and $G(t)$ the subgraph of the input graph induced by the bags in the subtree rooted at $t$.

In a bottom-up fashion you compute, for all tree nodes $t$ and all $m\leq n$, the following: The set of all $(P,S)$, such that

* $S$ is a subset of $b(t)$
* $P$ is a partition of $b(t)\setminus S$
* there is a FVS $F$ of $G(t)$ of size $m$ such that
    + $F\cap b(t)=S$
    + for $v,w\in b(t)\setminus S$, they are in the same connected component of $G(t)-F$ if and only if they are in the same part of $P$

So in essence you compute all possible FVSs for subgraph of the form $G(t)$, but at every bag you apply data compression such that you only know how the FVSs interact with the bag.

The running time per $t$ and $m$ is polynomial in the number of possibilities for $(P,S)$. Let $k:=|b(t)|=O(tw)$. The number of possibilities for $S$ can be bounded by $2^k$. For the number of partitions, let us use the crude bound $2^k\cdot k!$. (It can be established as follows: For a partition of $b(t)$, choose an arbitary order of $b(t)$ such that each part of the partition is contiguous wrt. the order. Then, the partition can be retrieved from the order if we know, for each element of $b(t)$, whether the next element is in the same part of the partition or not.) Thus, the overall running time is $$O(n^2)\cdot(2^{O(tw)}\cdot 2^{O(tw)}\cdot {O(tw)}!)^{O(1)} = tw^{O(tw)}\cdot n^{O(1)}$$

---
Tags: algorithms, graphs, parameterized-complexity, treewidth
---


# Question
Title: Prove that up to isomorphism there are exactly two graphs s.t. there at most two vertices with same degree
I've proven the following: For each $n\in\mathbb{N},n\geq 2$ there exists a graph on $n$ vertices such that all degrees are distinct except two. Formally for each $n$ there exists a graph on vertices $v\_1,\ldots,v\_n$ such that there exists at most one pair $i\neq j$, such that $\deg v\_i = \deg v\_j$. The construction goes by induction. Either the graph contains a degree $0$ vertex, so the highest degree is $n-2$, and adding a vertex and joining it to everyone else gets the thing done. If it does not contain a degree $0$ vertex, then adding a new vertex and joining it to no one gets the thing done.

I am curious whether this construction leads to a unique graph. More precisely, I would like to show the following:

For each $n\in\mathbb{N}$ there are, up to isomorphism, exactly two graphs on $n$ vertices $v\_1,\ldots,v\_n$ whose degree sequence satisfies that for at most one pair $i\neq j$ $\deg v\_i = \deg v\_j$. One of them is disconnected and one of them is connected.

I tried approaching this by induction. The base step for $n=2$ is trivial. There are exactly two graphs on $2$ vertices. Either there is the edge or there isn't. Denote $G\_{n,c}$ and $G\_{n,d}$ the two graphs for degree $n$. (c - connected, d - disconnected). Assume a graph on $n+1$ vertices satisfying the conditions. Then either it has a vertex of degree $0$, then by removing it I get a graph on $n$ vertices, and using the induction hypothesis, I can say it is isomorphic to $G\_{n,c}$ because there was a vertex of degree $n-1$. Similarly, I can argue if there was no vertex of degree $0$, then there was a vertex with degree $n$ so by removing it, I get a graph on $n$ vertices that is isomorphic to $G\_{n,d}$ because there's a degree $0$ vertex left. How to argue that this implies "uniqueness" for the $n+1$ vertices?

As a corollary, this would imply that $G\_{n,c}$ is complement of $G\_{n,d}$ for each $n$.

# Answer
$G\_{n,c}$ and $G\_{n,d}$ are effectively two sets of graphs.

What you want to prove is that if $G\_{n-1,c}$ and $G\_{n-1,d}$ are sets of isomorphic graphs, i.e., sets of graphs such that there is an isomorphism between each pair of graphs in the set, then so are $G\_{n,c}$ and $G\_{n,d}$. An isomorphism is a bijection $f$ from the vertices of one graph to those of another such that for each pair of vertices $n\_1,n\_2$, there is an arc from $n\_1$ to $n\_2$ iff there is one from $f(n\_1)$ to $f(n\_2)$.

$G\_{n,c}$ and $G\_{n,d}$ are constructed by extending graphs in $G\_{n-1,c}$ and $G\_{n-1,d}$ with a node and possibly arcs. You can describe this extension as a mapping $R\_n$ that maps each extended graph in $G\_{n,c} \cup G\_{n,d}$ to the graph in $G\_{n-1,c} \cup G\_{n-1,d}$ it was extended from.

What you need to prove is that for any two graphs $G\_1, G\_2$ in $G\_{n,c} \cup G\_{n,d}$, if $R(G\_1) \cong R(G\_2)$, then $G\_1 \cong G\_2$.

For this, it suffices to prove that each isomorphism from $R(G\_1)$ to $ R(G\_2)$ can be extended to an isomorphism from $G\_1$ to $G\_2$. The idea of your proof is that this is easy: extend each isomorphism by mapping the new node to the new node; now prove that the extended mapping is an isomorphism by distinguishing three cases: pairs of vertices none of which are new, one of which is new, and both of which are new.

This will prove the graphs you construct are unique up to isomorphism. It doesn't prove the graphs have the desired property (but you already sketch that proof), nor does it prove that no other graphs have the desired property (the *exactly* in the title) (I think you meant to sketch that, too, it's a pigeonhole argument; but that wasn't obvious to me).
> 1 votes

---
Tags: graphs, induction
---


# Question
Title: Minimal state DFAs for a regular expression of length $n$
I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering though if there are any known bounds on the number of states in the DFA even without going through with a construction.

Specifically, let $R$ be a regular expressions having length $n$ (by length here I mean the length of the whole string $R$ including alphabet symbols, parentheses, etc.). Is there a known general sub-exponential upper-bound function $f(n)$ such that for any such $R$, the minimal state DFA accepting $L(R)$ always has $\leq f(n)$ states? Or can it be proven that there are always counterexamples?

# Answer
According to Theorem 11 of Gruber and Holzer, From Finite Automata to Regular Expressions and Back – A Summary on Descriptional Complexity, $f(n) = 2^{\Theta(n)}$ (essentially; the lower bound is only for infinitely many $n$). While the theorem is stated for alphabetic width, according to Theorem 2 in the same paper, this measure is within constant factors of the length.
> 3 votes

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


# Question
Title: Is it NP-hard to check whether for a $k$ there exist both a Cut and a Bisection of value $k$?
Input: An undirected, unweighted graph $G=(V,E)$.

A cut is defined as a partition $V=A\dot\cup B$.

A bisection is defined as a partition $V=A\dot\cup B$ with $|A|=|B|$ if $|V|$ is even (or $|A|= |B|+1$ if $|V|$ is odd).

We define the value of a cut/bisection $V=A\dot\cup B$ as $E\[A,B\]$, i.e. as the number of edges between the partitions.

Question:

Is it NP-hard to solve the following problem:
Given an integer $k$, do there exist both a Cut and a Bisection of value $k$?

The problem is in NP, because given a cut and a bisection, we can efficiently check whether both have value $k$.

I'm also wondering whether there are somewhat general techniques that help one decide the NP-hardness of a problem which is more or less two NP-hard problems slapped together by an equality.

---

Literature:

NP-completeness of Max-Cut: DOI:10.1016/0304-3975(76)90059-1

NP-completeness of Vertex Bisection: DOI=10.1.1.154.5438

# Answer
Your problem is equivalent to the following:

Given an integer $k$, does there exist a bisection of value $k$?

In particular, every bisection is a cut, so if there exists a bisection of value $k$, then there also exists a cut of value $k$; if there does not exist a bisection of value $k$, then there does not exist both a cut and a bisection of value $k$.

This revised problem is NP-complete -- it follows from the NP-hardness of the maximum bisection problem. So, your problem is NP-complete, too (since it is the same problem).
> 2 votes

---
Tags: np-hard, decision-problem
---


# Question
Title: Equally coloring the edges of square tiles that form a grid
I need to generate a set of square tiles that are colored and are grid-able. Each square tile must have a unique set of 4 colors and each exterior edge of each tile is colored with a different color. There are 8 colors, so that leaves us with 8 choose 4 (70) tiles.

In order for these tiles to be placed into a grid, orthogonal tile edges must share a matching color. For example, if we look at just four square tiles in a 2x2 grid, the right edge of the top left tile must be the same color as the left edge of the top right tile. Additionally, the top edge of the bottom left tile must be the same color as the bottom edge of the top left tile. Most importantly, to place the bottom right tile, it must match the bottom of the top right tile AND the right of the bottom left tile. This gives a lot of importance to the pairs of coloring on consecutive edges of a tile.

If we ignore rotation (0, 90, 180, 270), there are only 6 ways to color each specific tile given the unique set of four colors derived above from the 8 choose 4 combinatorics. So if we color a tile with red on the top and move clockwise with green, yellow and blue, we end up with the following four colored edge pairs relating to each corner: red|green, green|yellow, yellow|blue, and blue|red. Because order matters for each corner when we place in a grid and we started with 8 colors, there are 8 * 7 (56) colored edge pairs possible.

The question is the following: **Is it possible to color all 70 tiles in such a way that all 56 colored edge pairs are equally distributed?** Since each tile generates 4 color pairs and there are 70 tiles, this generates 280 color pairs. Dividing by the 56 unique colored pairs possible would leave us with 5 colored edge pairs for each two color combination. Apologies if this is a known and solved problem but my searches have not yielded an answer or good approach to solving this. It is also possible that this is NP and may only be approached by approximations. I have written a solver that uses a Las Vegas algorithm approach with different heuristics. It has gotten close but is not completely balanced. I'd be grateful for any pointers or knowledge about this type of problem.

# Answer
I would suggest you try to search for a coloring using a SAT solver or ILP solver.

To solve with an ILP solver: use zero-or-one (boolean) variables $x\_{i,j}$, where $x\_{i,j}=1$ means that the $i$th tile is colored with the $j$th of the 6 possibilities. This gives you $70 \times 6 = 420$ variables. Next, for each colored edge pair $p$, add a linear equality constraint $\sum x\_{i,j} = 5$, where the sum is over all $(i,j)$ that correspond to a tile coloring that contains the colored edge pair $p$. Also, for each $i$, add the constraint $\sum\_j x\_{i,j} = 1$. Ask the ILP solver whether it can find feasible solution.

Alternatively, you could use a SAT solver. You'll need to use 1-out-of-n and 5-out-of-n constraints; see Encoding 1-out-of-n constraint for SAT solvers and Reduce the following problem to SAT and Can a propositional threshold connective be expressed by standard connectives? and Recipe book for SAT encodings? for methods, or use a solver like Z3 that has built-in support for these kinds of constraints (sometimes called pseudo-boolean constraints).
> 1 votes

---
Tags: combinatorics, colorings
---