Degree Reduction in Max Cut and Vertex Cover I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be different.

Here are the two gadgets in question. The Min Vertex Cover gadget simply divides a degree $n$ node $v$ into a chain of nodes $v_1,u,v_2$, where $v_1$ and $v_2$ share the edges of $v$, increasing the Min Vertex Cover by 1 in the process. The Max Cut gadget on the other hand is rather more complicated and involves cycles. What I don't understand is why the simple Min Vertex Cover gadget can't be used for Max Cut?

Consider a degree 4 vertex $v$ in Max Cut. If you unfold the vertex as $v_1,u,v_2$ (as in the Min Vertex Cover example) you are adding 2 edges to the graph, both of which can be cut by placing $u$ on the opposite side of the cut to $v_1$ and $v_2$, so wouldn't the Max Cut just increase by 2? I'm probably missing something but I don't know what it is.

This is a counterexample.

Suppose you have this graph:

The maximum cut in this graph has four edges. If you follow the procedure used for vertex cover you get this cut:

In the image, the maximum cut has seven edges.


Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$) I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem.

What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow input~ \varepsilon$

Emptiness problem:
$E_{TM} = \{\langle M \rangle | ~M~ is~ a~ Turing~ machine~ and~ L(M)= \emptyset \}$
$E_{TM}$ is undecidable
$E_{TM}$ is recognizable but not co-turing-recognizable
$E_{TM}$ is not recognizable but co-turing-recognizable

Blank tape halting problem:
$H_0 = \{\langle M \rangle ~ |~ M~ is~ a~ Turing~ Machine~ that~ halts~ on~ input~ \varepsilon  ~\}$
$H_0$ is undecidable
$H_0$ is recognizable but not co-turing-recognizable

any help is greatly appreciated

Yes, they are different. $L(M)$ is the set of all inputs accepted by a Turing machine, so $E_{TM}$ asks if a Turing machine doesn't accept any inputs. $H_0$ asks whether a particular input (the empty string) is accepted. BTW, $E_{TM}$ should be co-Turing-recognizable, but not Turing-recognizable.


Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2 Given (n) , what is the Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2.
Is there any way I can re-write this code just without using nested loop?

int counter=0;
    int x=0;

    for (int i =(int) n-1; i>=0 ; i--){

        if(i == x)
            break;

        for (int j = 1; j< (int)n ; j++){

            if (Math.pow(i,2)+Math.pow(j,2) == Math.pow(n,2)){
                counter++;
                x = j;
            }
        }
    }
System.out.print(counter);

Your approach is to try every possible $x$ and $y$ and see if $x^2+y^2=n^2$. However, $n$ is fixed and, for any $x$, either $n^2-x^2$ is a perfect square or it isn't. You can calculate what $y$ is, instead of looping and trying every possible value.

Actual code is off-topic but it's confusing that you're trying to solve a problem about $x$ and $y$, but you've represented those quantities in variables called i and j. And even worse that you have a variable called x that represents something else entirely. (In fact, I'm not sure it's even correct. You seem to be using x to avoid reporting, e.g., $x=3$, $y=4$ and $x=4$, $y=3$ as separate solutions for $n=5$. But they are separate solutions and the question, at least as you've summarized it, doesn't say that they should be counted as the same.)


What makes it so difficult to prove P =/≠ NP? — The subset sum issue I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to prove that P = NP.

Let's take the subset sum problem, which is NP-complete. It says that given a set such as $\{-7, -3, -2, 5, 8\}$, we're able to find out if there exists a subset of this set summing to zero, within exponential time (and obviously check a solution, for instance $\{-3, -2, 5\}$ within polynomial time).

So if someone finds an polynomial-time algorithm for this task, he'll show that P = NP, right?

EDIT: I removed:

  Assuming, that opinions whether P = NP or P ≠ NP amongst computer scientists are about 1:1 (this site claims that they're ~ 52% and ~44% respectively)...

As the guys noticed in comments, it's wrong. I should say the proven cases are like 1:1.

Okay, so it gets more intuitive now. I mean, P ≠ NP actually seems to be 'more likely now':

However, assuming that there are still, say, 5-10% of formally educated people who believes that P = NP and the cited problem is not, say, the most complex one, how is that even possible that no one  of them had found a polynomial-time algorithm yet OR (maybe more likely?) no one of their opponents proved that there's no such an algorithm? Or, does it also mean that (in terms of those people's opinions, again) the 'chances' of there being  such an algorithm are like 1:1, too?

From my (maybe naive) point of view, the subset sum problem seems so simple to crack – at least for advanced computer scientists.

As you're probably aware of, searching in the Net would not help me much as I just can't deeper into this problem. I've got no such mathematical knowledge to even comprehend it more.

Many simple-seeming problems turn out to have solutions that are extremely complicated and deep. That's not a bad thing, in fact it's what keeps mathematics interesting. One of the best known examples is Fermat's Last Theorem, which states that the equation $x^n+y^n=z^n$ has no solution in positive integers $x, y, z$ whenever $n\ge 3$. One could hardly ask for a simpler problem, but despite the efforts of some of the brightest mathematicians it remained unsolved for 358 years! On the plus side, three centuries of trying (and failing) to prove Fermat's Last Theorem led to the development of a lot of what's known as algebraic number theory.

Indeed, the subset sum problem is easy to state. Finding a poly-time solution, though, has turned out to be really hard, to the extent that no one has yet been able to demonstrate one. One could say, "Okay, I'll turn the problem around and show that there is no poly-time algorithm possible." Ugh! That sounds even worse: how could one establish that among the infinitely many algorithms to solve subset sum, there are none that run in time polynomial in the length of the instance to be solved?

I don't necessarily recommend this, but you could just try inventing an algorithm of your own that always finds the correct answer to subset sum. You'll almost certainly find, as others have, that no matter how much cleverness you throw at the problem, you'll fail to come up with a "fast enough" algorithm. That, at least, should disabuse you of the notion that simple questions should have simple solutions.


Finding two words of lengths that are relatively prime in a regular language? Given a regular language $L$ over a unary alphabet $\Sigma = \{ a \}$.

How to decide whether there are two words $w,w' \in L$ such that
the length of $w$ is relatively prime to the length of $w'$ ?

Consider a minimal DFA for $L$. Each state in the DFA has one outgoing edge, so the DFA looks like a path entering a cycle. That means that $W = \{ n : a^n \in L \}$ is eventually periodic: for some $k,l$, for all $n \geq k$ it holds that $n \in W$ iff $n + l \in W$. We are now left with a problem in number theory, which I leave for you to ponder. (Try a few examples to see when an eventually periodic $W$ can fail to satisfy the property you're looking for.)


Returning a random subset with length k of N strings while only storing at most k of them Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, $k$. The subset must contain exactly $k$ strings selected uniformly at random from the entire input set.

It's easy to do this if every single string is stored in memory. (Memory proportional to N). The question is how to only store at most $k$ strings, and still ensure that the output is perfectly random.

I've tried to work it out with the following base case. Say $k = 1$.

> Subset 1
A
B
C

A will always be added, since the queue contains less than k items.
If I only operate on what I know, which is the current number of items in the queue, the required length $k$, and the encountered strings $n$. So I've tried doing this: ($k$ - items in queue)/$n$.

Using that, the probability of A being replaced by B is $1/2$. Then the probability of B being replaced by C will be $1/3$. The problem there is that there's no way of reducing the probability of A being replaced before I've seen all of the strings.

I'm sure this question must have a clever answer. The problem of writing this Subset program to use memory $<= k$ is a bonus question on an Algs course I'm taking, and I really hope they wouldn't ask something unanswerable.

Use reservoir sampling.  This is a good description in Wikipedia, or in Knuth.

Let's start with the simple case, where $k=1$.  You always have one string in memory. When you read the first string, you store it in memory.  Each time you read a new string, you replace it with the one in memory with probability $1/i$, if this is the $i$th string you've read so far.  At the end, output whatever is stored in memory. The end result is that each string in the input is equally  likely to be output.  See also Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space for description of this approach (thank you, Juho!).

This extends to arbitrary $k$.  See Wikipedia's description for details.


CSMA/CD with binary exponential backoff: Do both back off or just the loser? I've been given two PC's that are connected via Ethernet, and as such are using CSMA-CD with binary exponential backoff.

Now, both PC's, let's call them $A$ and $B$, are trying to send data simultaneously. So, the first time both randomly choose a number from $\{0,1\}$. Let's say $A$ wins (i.e. $A$ picks 0 and $B$ picks 1) and sends the first frame of its data.

Instantly after sending the frame, the next collision between $A$ and $B$ occurs.
Now, in my given scenario, for some reason $A$ only picks from $\{0,1\}$, while $B$ picks from $\{0,1,2,3\}$.

Why is that the case? I don't see how this algorithm is any better than if $B$ gave up right away after losing once.
First: Just using a wider range doesn't stop the two PC's from colliding at all. If only $A$ has enough frames to send, the next collision will occur eventually anyway.
And for every collision afterwards, the chance of $B$ losing just ever increases.
So, $B$ will starve and give up eventually anyway as well.

Why not just let $B$ give up instantly, and let $B$ wait till $A$ certainly has finished? Is my given scenario somehow wrong, or am I missing the point?

You are right.  This does seem like an undesirable consequence of the CSMA-CD protocol.

I suspect this behavior was selected because it is implementable, and because it is not so easy to come up with an alternative that is simple and avoids this problem.

Recall, the only thing that is observable to B when it tries to send is whether that send was successful or a collision occurred.  B can't see anything about whether it "wins" or "loses"; it has no visibility of the other parties.  It doesn't know that A is also trying to send at the same time.  If B tries to send and succeeds, then B doesn't know whether that's because no one else wanted to send; or A wanted to send and previously "won" (already finished sending); or A wants to send but has "lost" (hasn't sent yet and has a backoff time that is still in the future) -- B has no way to distinguish between those cases.

It sounds like one of your alternative proposals is that B should give up permanently as soon as it is involved in a two consecutive collisions.  That doesn't seem to make sense to me.  When B gives up permanently, that means that it just powers down and never sends on the network again?  You can't have permanent disconnection -- that wouldn't be useful.  There has to be some point at B is going to try to send something again, so it's just a question of what that condition is.

It sounds like another of your proposals is that if B collides with A, and A gets to send first, then B should wait until A is finished.  That's harder to implement, and I'm not sure it has much benefit for B (B is still stuck waiting).  Why is it hard to implement?  It's hard to implement, because it's not clear how B would know when A is "done" transmitting.  It's not even clear what "done" means.  Even A won't know when it is done; A doesn't necessarily know what other packets it might want to send in the near future.  So now we get into some design space where we try to figure out what we mean by "done", and how B would know when A is done (maybe it's that A hasn't sent anything in the last 20ms?).  It's not enough to have A declare how much more it currently has to send as soon as it succeeds on a retransmission attempt and then require B to wait until that much has been sent, because what if after A finishes sending that much, A discovers it has more that it wants to send?  (Presumably, there's some application running on A that periodically wants to send stuff.  A's ethernet card can't predict what future sends the application will want to do.  Maybe the application will end up continuously trying to send packets, one after another, rapid-fire.)  If A tries to send some new message as soon as it finishes the previous one, you'll be back to the same scenario where A is more likely to win, so this doesn't eliminate the problem.

Or, if you were proposing that each PC remembers who won the last time and you alternate, that is also problematic, for a different reason.  It doesn't scale well to more than two PCs on the same network.

The standard protocol is memoryless; it doesn't require keeping track of past history.  This makes it simple, scalable, and reasonably efficient in many scenarios.


Does infinite length strings lead to uncountable languages? This answer says:

  We can have uncountable languages only if we allow words of infinite length.

So does that means any (finite / infinite) language or any (finite / infinite) set of languages over any (finite / infinite) alphabet will be uncountable of words have infinite length?

Let me simplify this by asking specifically for the simplest language of infinite length string:

  Does the language of "finite" number of words, each of which can be of "infinite length" and are based on "finite" alphabet is uncountable?

A finite language is finite. Every finite set is countable, by definition.

A language of finite-length strings over a finite alphabet may be infinite but is always countable.

A language of infinite-length strings over a finite alphabet might be uncountable.


How to prove $c = a + b$ using Program Verification Techniques I am trying to prove an elementary thing, but it seems at some point you get down to atoms where you can't prove anything else. This is why I am wondering about proving $c = a + b$, it seems like an atom.

\begin{align}
  \{a, b\}\\
  c = a + b\\
  \{a, b, c = a + b\}
\end{align}

This is my attempt at a Hoare assertion. It says "given $a$ and $b$, if I assign $c$ to $a + b$, then I end up with $a$ and $b$ unchanged, and $c$ assigned to $a + b$." That is, it's saying "if I do $c = a + b$, then I end up with $c = a + b$," which feels reduntant. In addition, this seems hard to formalize in programming. If the form is $\{P_1\}\ Q\ \{P_2\}$, then $Q$ and the $c$ part of $P_2$ is the same code, namely $c = a + b$. So I don't see there being any need to write an assertion for addition, we can just state it's properties (that it returns a number) and it is proven by definition. That is, it's an axiom.

Wondering if this is true, or where I am missing something. Because when I tried writing this out in software I end up with basically what it looks like in that definition of the Hoare assertion above, $c = a + b$ twice.

We can prove the Hoare triple

\begin{align}
  \{{\sf true}\}\\
  c = a + b\\
  \{c = a + b\}
\end{align}

using the assignment rule. We take the postcondition $c = a + b$ and we substitute backwards $\{(a+b)/c\}$, so we get $(c = a + b)\{(a+b)/c\} = (a+b=a+b)$. That's the weakest precondition. Hence, we proved

\begin{align}
  \{a+b = a+b\}\\
  c = a + b\\
  \{c = a + b\}
\end{align}

We can then use the weakening/strengthening/pre-post rule to rewrite $a+b=a+b$ as $\sf true$, since they are equivalent logical formulae.


Rewriting gates such as XOR into three basic gates? How would I rewrite an XOR gate into the three basic logic gates (AND, OR, NOT). To be more specific, I have to write it in such a way with 2 NOT gates, 2 OR gates, and 1 AND gate. I also have to do it with 1 OR gate, 2 AND gates, and 1 NOT gate.

I'm not looking for just the answer, I'm looking for a way to come up with the answer.

Thanks!

Hint:  $a \oplus b = \neg \big( (a \land b) \lor (\neg a \land \neg b)\big)$  (you can't have both true and you can't have both false).  Using De Morgan's, you should be able to break up the negation and the main $\lor$.


Ford-Fulkerson Algorithm not "pushing back" flow I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of the edges). I am wondering how that can be possible. Can we choose augmenting paths that allow us to never "push back"?

No, it is not true that "the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges". If you look at the wiki article of Ford and Fulkerson method you will see the following pseudocode:

Algorithm Ford–Fulkerson
Inputs: Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$
Output: Compute a flow $f$ from $s$ to $t$ of maximum value

$f(u,v) \leftarrow 0$ for all edges $(u,v)$
While there is a path $p$ from $s$ to $t$ in $G_f$, such that $c_f(u,v) > 0$
  for all edges $(u,v) \in p$:
    Find $c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}$
    for each edge $(u,v) \in p$
      $f(u,v) \leftarrow f(u,v) + c_f(p)$ (Send flow along the path)
      $f(v,u) \leftarrow f(v,u) - c_f(p)$ (The flow might be   "returned" later)

In the last line $f(v,u)$ is clearly decremented.

In the example below one will have to decrease flow in the middle edge to get max-flow. There is no other way.

If you want to know, if there exist a sequence of augmenting paths that never decrease the flows, then the answer is possibly yes. Proof might be non-trivial though.


Time complexity of a recursive function which generates all combinations of an array The following function getCombinations, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would appreciate the workings or simply an idea about how to approach this. Thanks in advance
function getCombinations(chars) {
  var result = [];
  var f = function(prefix, chars) {
    for (var i = 0; i < chars.length; i++) {
      result.push(prefix + chars[i]);
      f(prefix + chars[i], chars.slice(i + 1));
    }
  }
  f('', chars);
  return result;
}

Denote by $T(n)$ the running time of your function on an input of length $n$, assuming that all operations are $O(1)$. Then $T(0) = O(1)$, and for $n > 0$,
$$
T(n) = O(n) + \sum_{m=0}^{n-1} T(m).
$$
Let us replace $O(n)$ with $Cn$. Then
$$
T(n) - T(n-1) = Cn + \sum_{m=0}^{n-1} T(m) - C(n-1) - \sum_{m=0}^{n-2} T(m) = C + T(n-1),
$$
and so $T(n) = 2T(n-1) + C$, implying that $T(n) + C = 2(T(n-1) + C)$. Therefore $T(n) = 2^n(T(0) + C) - C = O(2^n)$.


Turing recognizable language between languages that aren't recognizable? Let $L_{1},L_{2}$ be languages that are not Turing recognizable, and let $L$ be a language such that $L_{1} \subseteq L \subseteq L_{2}$.

Is $L$ also not Turing recognizable?

I am inclined to believe it is, but I really have no idea how to show this. It seems that non-recognizable languages have very little about them that could  be used to solve a problem like this. Ideas?

The answer is no, of course.

Consider, for instance, the following languages:

$L_1 = \{ \langle M \rangle \# \langle M \rangle \mid \, \text{$M$ is a TM which does not halt on input $\langle M \rangle$} \}$
$L = \{ \langle M \rangle \# \langle M \rangle \mid \, \text{$M$ is a TM} \}$
$L_2 = L \cup \{ \langle M \rangle \# w \mid \, \text{$M$ is a TM which does not halt on input $w$} \}$

Then it is easy to see neither $L_1$ nor $L_2$ are recursively enumerable (i.e., Turing-recognizable), despite $L$ being even context-sensitive. (In fact, you could even make $L$ context-free by replacing the second $\langle M \rangle$ with its reversed copy.)

The upshot is that set inclusion (on its own) tells us very little about the sets involved being recursively enumerable or not, unless the symmetric difference between them is finite. In the case of $L_1 \subseteq L \subseteq L_2$, we do know, for instance, that $|L \setminus L_1|$ or $|L_2 \setminus L|$ being finite implies that $L_2$ is also not recursively enumerable.


What is an example of a Turing-recognizable infinite word, which is not Turing-decidable? I am confused about Turing Machines that are able to decide languages that contain infinite words.

Are languages with an infinite amount of only finite strings always decidable?
How can a Turing Machine halt on an infinite input string?
Can Turing Machines loop on finite strings?
What is the difference between an infinite input string that a Turing Machines can halt on and an infinite input string that a Turing Machine cannot halt on (decidable vs recognizable)?

It's a lot of questions but they are related, please help me.

There's is a significant difference between "arbitrarily long" and "infinite".

As a simple example, an integer can have an arbitrarily great magnitude; formally, for every integer, there exists a larger integer (its successor), which in turn has a successor, and so on. But all integers are finite; $\omega \notin \mathbb{N}$. (Or, if you prefer, $\infty \notin \mathbb{N}$.)

Similarly, the Kleene star operator $A^*$ represents the concatenation of an arbitrarily large number of elements from $A$, but not an infinite number of elements of $A$.

There is an interesting part of formal language theory which deals with sets of infinitely-long strings (ω-strings), but such strings cannot be produced by any regular expression. (You can use ω-regular expressions, which include the infinite repetition operator $A^\omega$.) But you might want to master the material you're currently studying before venturing onto Buchi automata, interesting though they may be.

To answer your questions:

No, there are undecidable languages consisting only of finite strings. Indeed, since such languages are undecidable, it is not necessarily even decidable whether they are finite sets. A classic example of an undecidable language is the set of (descriptions of) Turing machines which halt on every input. Note that every Turing machine (like every integer) has a finitely-long description, so the language is a set (an infinite set, in this case) of finite strings.
A Turing machine is under no obligation to read its entire input. Consider the language of ω-strings which start with an $a$. This is clearly a set of infinitely-long strings, but only a single character needs to be examined to determine whether a string belongs to the language.
Sure, why not. For example, the Turing machine trying to determine whether its input describes a Turing machine which halts on every input could simulate the described machine using every possible input, but that is going to go on forever even if the language describe a Turing machine which always halts.
See, for example, deterministic Buchi automata. Basically, an ω-language $L$ can be deterministic if there is a language $L' \subset Pref(L)$ of finite prefixes which can deterministically predict inclusion in $L$.


Regular Expressions with at least 2 0's and at most 1 I think the answer should be:

$(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon)$

But I am not sure if this is the right answer. Can someone explain the correct answer?
And if it is correct how can I shorten this up?

Also what is the nfa for the regular expression:
∅*

i have one more problem:  i can't surely understand the meaning of Σ* symbol. As far as I understand it should be (0+1)* if Σ = (0, 1) and (a+b+c)* if
Σ = (a,b,c) and so on. Please someone clarify this.

Your answer is correct. You can obtain a slightly shorter expression by deleting two of the $\epsilon$ in your expression. Indeed
\begin{align}
(1+ \epsilon)000^* + 0^*0(1+\epsilon)00^* + 000^*(1+\epsilon) &= (1+ \epsilon)000^* + 0^*0100^* + 000^*1 \\
&= 1000^* + 0^*0(1+\epsilon)00^* + 000^*1\\
&=1000^* + 0^*0100^* + 000^*(1+\epsilon)
\end{align}
Finally, if you want to avoid $\epsilon$, you could use one of the expressions
$$
000^* + 1000^* + 0^*0100^* + 000^*1 \quad \text{or} \quad 0^*(00 + 100 + 010 + 001)0^*
$$
which might be easier to read.


Injective burrows wheeler We know that the Burrows-Wheeler Transform is reversible, in the sense that, given
s=BWT(w) and an index I, it is possible to recover w by an algorithm. But how to prove that w is unique? In other way how to prove that Burrows-Wheeler is injective?

Let $\mathsf{BWT}^{-1}$ be the inverse Burrows-Wheeler transform, that is, $\mathsf{BWT}^{-1}(\mathsf{BWT}(w)) = w$.

If $\mathsf{BWT}(x) = \mathsf{BWT}(y)$ then
$$
x = \mathsf{BWT}^{-1}(\mathsf{BWT}(x)) = \mathsf{BWT}^{-1}(\mathsf{BWT}(y)) = y.
$$


Is there an undecidable language that is mapping reducible to its complement? Is there an undecidable language A that is mapping reducible to its complement?
If it is possible, since A is an undecidable language, so A's complement must also be an undecidable language. But i don't know whether undecidable languages is closed under complement or not.

Yes, it is possible. Enumerate the set of all possible Turing machines and let $H$ (resp. $\overline{H}$) be the set of indices of the Turing machines that halt (resp. do not halt) on empty input.
Let $L = \{ \langle T, 1 \rangle \, : T \in H \} \cup \{ \langle T, 0 \rangle \, : T \in \overline{H} \}$.
Clearly $L$ is not decidable but it is possible to reduce $L$ to $\overline{L}$ since $\langle T, r \rangle \in L \iff \langle T, 1-r \rangle \in \overline{L}$.


Question about spanning trees and creating them through BFS and/or DFS algorithms The question is as follows:
True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the root v.

What about if instead of DFS I used BFS?

I have no clue where to begin with this one. I feel like I'm overlooking some basic characteristic of the algorithm or the tree that it produces. Any help would be appreciated!

If you get to pick, each time, an ordering of the vertices, then statement is trivially true - just choose the ordering that gives that tree, but this is not interesting.

Assuming the vertices do have some fixed order (so the DFS/BFS can't arbitrarily pick which vertex it has to choose next), then statement is false. We can see this via a simple counting argument. As the ordering is fixed, the DFS/BFS produces a unique spanning tree for each starting vertex, i.e. we can produce at most $n$ spanning trees (per algorithm), where $n$ is the number of vertices in the graph.

However if our input graph is $K_{n}$ with $n > 3$ (the complete graph on $n$ vertices), the graph has $n^{n-2}$ spanning trees, clearly far more than what we can produce from the DFS/BFS.


Complexity of finding the pseudoinverse matrix How many arithmetic operations are required to find a Moore–Penrose
  pseudoinverse
  matrix of a arbitrary field?

If the matrix is invertible and complex valued, then it's just the inverse. Finding the inverse takes $O(n^\omega)$ time, where $\omega$ is the matrix multiplication constant. It is Theorem 28.2 in Introduction to Algorithms 3rd Edition.

If the matrix $A$ has linearly independent rows or columns and complex valued, then the pseudoinverse matrix can be computed with $A^*(A A^*)^{-1}$ or $(A A^*)^{-1}A^*$ respectively, where $A^*$ is the conjugate transpose of $A$. In particular, this implies an $O(n^\omega)$ time for finding the pseudoinverse of $A$.

For general matrix, the algorithms I have seen uses QR decomposition or SVD, which seems to take $O(n^3)$ arithmetic operations in the worst case. Is there algorithms that uses fewer operations?

First of all, people tend to forget that $\omega$ is an infimum. Whenever we write $O(n^\omega)$, we actually mean for all $\gamma > \omega$, there is an algorithm running in time $O_\gamma(n^\gamma)$.

Keller-Gehrig showed (among else) how to present a matrix $A$ in rank normal form in time $O(n^\omega)$. If $A$ has rank $r$, then a rank normal form of $A$ is
$$ S \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} T $$
for some invertible $S,T$ of the appropriate dimensions; see also Algebraic Complexity Theory, Proposition 16.13 on page 435.

Rank normal form is similar to the rank decomposition mentioned in the Wikipedia article, $A = XY$ where $X$ has $r$ columns and $Y$ has $r$ rows. Indeed, we can take $X$ to be the first $r$ columns of $S$, and $Y$ to be the first $r$ rows of $T$. Given this decomposition, Wikipedia gives a formula for the pseudoinverse using only Hermitian adjoint, matrix multiplication and matrix inverse. Therefore the pseudoinverse can be computed in time $O(n^\omega)$.


Linear programming with absolute values I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ?

Example of use of absolute values:

Minimize |a+b+c| + |a-c| s.t.
 |a| + b > 3
 | |a| - |b| | <= 5
 | |b| - 3 | = 0

All constraints in a linear program are convex (if $x,y$ satisfy the constraints, then $tx+(1-t)y$ also does for all $0 \leq t \leq 1$). The constraint $|a|+b > 3$ is not convex, since $(4,0)$ and $(-4,0)$ are both solutions while $(0,0)$ is not. It is also not closed, which is another reason why you cannot use it in a linear program (change $>$ to $\geq$). The constrict $|a|+b \leq 3$, however, can be used, since it is equivalent to the pair of constraints $a+b \leq 3$ and $(-a)+b \leq 3$.

So absolute values can sometimes be expressed in the language of linear programming, but not always.


Are interrupts only found in BIOS? I may be misunderstanding here-- but are interrupts only found in BIOS and not UEFI systems?

More context:
"Through standardized calls to the BIOS (“interrupts” in computer parlance), the operating system can trigger the BIOS to read and write to the disk and interface with other hardware components."

I read this in a paper I'm reading and thought that interrupts may only be accessible in BIOS.  I found some old stackoverflow answers (https://stackoverflow.com/questions/15101183/does-booting-in-efi-mode-mean-that-i-shall-not-have-access-to-bios-interrupts) that also confused me into thinking that interrupts are not programmable/accessible in UEFI.

Almost all CPUs contain interrupt lines. Both Bios and UEFI provide services for handling interrupts on these lines. UEFI is an extended version of the old Bios. So, UEFI provides all services provided by Bios.


DFA impossible problem? As you can see from the title this is the impression that i have on this problem, but probably it isn't impossible.

The required DFA is :

"The set of the strings with equal number of 0 and 1 such that for each prefix the difference between the number of 0's and the number of 1's is minor(<) than 2".

Maybe I've misread the requirements I've thought of them as follows :

by prefix I thought of all the strings with length < than the original one, for example in my opinion the prefixes for "cat" are "c" and "ca" but not "cat";

"the difference between the number of 0's and the number of 1's is minor(<) than 2" by this i thought that we should have (number of 0 - number of 1) < 2, but now I'm realazing that even (number of 1 - number of 0) < 2 should be fine.

One user suggested to do this :

"Note that you can build a simple DFA which checks if the difference between the number of ones and the number of zeroes never exeeds 2 for any prefix of the input string: Add accepting states qk for −2≤k≤2 (where q0 is the initial state) and a rejecting sink state qs with transitions qk→qk+1 via 1 and qk→qk−1 via 0 for appropriate values of k and qk→qs for the other values."

but I don't understand quite well what it means, I've tried some solutions on my own and they don't work properly :

Any possible solutions? EDIT The DFA should be impossible as a matter of fact : here is the explanation

Note: I am the user who gave the comment cited in the OP on the CSTheory thread. Also, I am writing this as an answer rather than a comment to JohEker's post as I do not have enough reputation here to comment.

The idea is to exploit that we have a finite, local bound on the difference between zeroes and ones in the input word, i.e. we accept every word where this difference does not exceed 1 at any point. Note that if we drop the requirement that this holds for all prefixes, then the language is not regular (and thus not recognized by a DFA) by the Myhill-Nerode theorem as pointed out by JohEker.

So let $\#0(w)$ and $\#1(w)$ denote the number of ones and zeroes in the word $w$ respectively. To build a DFA from the idea above, we see that a word $w$ should be accepted if every prefix $v$ of $w$ satisfies $|\#1(v) - \#0(v)| \leq 1$, or equivalently $-1 \leq \#1(v) - \#0(v) \leq 1$.
We can keep track of the value $\#1(v) - \#0(v)$ by creating a state for every value of it that we care about and specifying transitions between these states to model how the counter changes when we read a $0$ or a $1$.
Combining this with our previous idea that we only need to know if the value of the counter is between $-1$ and $1$, we create three states $q_{-1}, q_0$ and $q_1$.

Clearly we want the initial value of the counter to be $0$, so we use $q_0$ as the initial state of our automaton and we transition from $q_k$ to $q_{k+1}$ if we read a $1$ (for $k \in \{-1, 0\}$ -- else we leave the space of values that we are interested in; more on this later) and similarly we transition from $q_k$ to $q_{k-1}$ (for $k \in \{0, 1\}$). As we want to accept the words for which the counter ends up at 0, we also define $q_0$ as the only accepting state.

Now, what happens if the counter does not stay within $\{-1, 0, 1\}$? We want to reject the input.

In our automaton, this corresponds either to reading a $0$ while we are in the state $q_{-1}$ (i.e. we have $\#1(v) - \#0(v) = -1$ that for the input $v$ before reading the $0$ and thus $\#1(v0) - \#0(v0) = -2$) or reading a $1$ while we are in the state $q_1$. So we introduce a new, "rejecting" state $q_s$ (also called a sink-state as the DFA cannot escape from this state once it is reached) which we transition to in case we detect one of the above-described scenarios. This now completes the description of our DFA, which looks like this:


Does DFS have better constants/complexity than Backtracking on a Graph? I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step by step while DFS on a graph may directly jump some nodes backwards, is DFS a faster algorithm? If so, only in terms of constants or complexity wise?
Edit:
Maybe the original writeup was a bit confusing. What I mean specifically is this.
DFS:

A normal implemetation of DFS should traverse the following tree in this manner A->B->C->D. This implies that the implementation for what we normally refer to as DFS visits each node exactly once, giving it a time complexity O(V) where V is the number of vertices.
By Backtracking, what I have in mind is this:

This I feel is a more bare bones approach where one step of backtracking actually goes to a parent node and explores its other children, instead of skipping over some parent nodes which had only one child (node B here) to begin with. This results in a traversal sequence of A->B->C->B->A->D. This particular example shows that this is always going to require more nodes to be visited than the standard DFS and hence the question.

When you explore a graph of $N$ vertices and $E$ edges, you basically need to store the visited vertices in a $N$ boolean array. But eventually (when you are interested in retrieving path and not only connection), you will use instead a $N$ bactrack array, containing for each vertex, the one that let you reach it (the parent vertex in the exploration tree).
Exploration methods BFS and DFS needs an extra storage for a queue of vertices to visit which size is $O(N)$. One can consider that the difference between BFS and DFS is just that they respectively use a FIFO and LIFO queue. Note that DFS algorithms often use a recursion hiding the additional storage.
Now, what you call "backtrack" is just a simpler way to do the DFS as you don't have a "todo" queue. When a vertex is fully explore, you just go back in the exploration tree. Of course, it is less efficient than DFS as you will run the exploration loop several times on some vertex. One can argue that it is slightly more efficient in space as you save the queue storage, but practically, this is negligible.


Fastest algorithm for finding the longest palindrome subsequence First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the answer is 7 ("abababa").

Postscript: the size of the word is smaller than 3000.

There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.

See Wikipedia's reference

Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.

Edit

I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the longest palindrome subsequence of a string, so dynamic programming seems good:
\begin{align*}
f_{j,k}&=\max(f_{j,k+1},f_{j+1,k},2[S_j=S_k]+f_{j+1,k-1}),\qquad j<k\\
f_{k,k}&=1\\
f_{j,k}&=0,\qquad j>k\\
\end{align*}
where $f_{j,k}$ denotes the length of the longgest palindrome subsequence of $S_{j..k}$, and $[P]$ is Iverson bracket I think it's just like LCS.


When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state? A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current character being read.
If the machine halts when it's in an accepted state and at the same time the whole input has been consumed the input string is considered to be accepted.
Now, when introduce $\epsilon$ transitions the machine doesn't necessarily halt when the whole input string has been consumed, for it is possible that there are still $\epsilon$ transitions available.
Suppose we have a NFA that is in an accepted state and also that the whole input has been consumed, but there are still $\epsilon$ transitions available in this state, can we considered the input string to be accepted or do we need to "follow the trail" of $\epsilon$ transitions until we reach a state where no other transition is available?

One issue is that the way you're using the English language is appropriate for talking about DFAs but not appropriate for NFAs.
With a DFA, we can say "the DFA is in state $q$ after reading the input".  That is well-defined for a DFA.
That is not well-defined for NFAs.  There may be multiple possible runs, each of which ends in a different state.  So it doesn't make sense to say "the NFA is in an accepting state after reading the whole input", because there may be multiple possible runs, some of which are in an accepting state and some of which are not.
The formal definition of a NFA gives a precise definition of under what conditions a string is considered to be accepted.  Please consult any good textbook.  The short answer to your last question is yes, the input string is accepted in that situation, as there exists a run of the NFA that ends in an accepting state and where the whole input has been consumed.  But there's little point in us repeating material that's already covered in standard textbooks, and if you work through the definitions, you should be able to figure this out for yourself.


Are regular languages closed against an intersection that keeps words with the same number of ones? How can we show that the class of regular languages is closed under the following operation?

Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$.

The operation is: $$\{x \in L_1 \mid \text{ for some } y \in L_2, \text{ strings } x \text{ and } y \text{ contains equal numbers of } 1s \}$$

Is the only way to show this to create a NFA of the new language?

I have done the following:

Let $M_{L_1}=(Q_{L_1},\Sigma ,\delta_{L_1},q_{L_1},F_{L_1})$ the DFA that recognizes $L_1$ and $M_{L_2}=(Q_{L_2},\Sigma ,\delta_{L_2},q_{L_2},F_{L_2})$ the DFA that recognizes $L_2$.

Let $M=(Q,\Sigma ,\delta,q,F)$ the NFA that recognizes the operation.

$Q=Q_{L_1}\times Q_{L_2}, \ \ q=(q_{L_1},q_{L_2})$.

Is this correct? Which is the transition function?

Let
$$
  L = \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } |x|_1 = |y|_1\}
$$
Let $\pi: \Sigma^* \to a^*$ be the homomorphism defined by $\pi(u) = a^{|u|_1}$.
I claim that
$$
  L = L_1 \cap \pi^{-1}(\pi(L_2))
$$
Since regular languages are closed under homomorphisms, inverses of homomorphisms and intersection, it will follow that $L$ is regular.

Proof of the claim.
\begin{align}
  L_1 \cap \pi^{-1}(\pi(L_2)) &= \{ x \in L_1 \mid \pi(x) \in  \pi(L_2) \} \\
  &= \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } \pi(x) = \pi(y)\}\\
  &= \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } |x|_1 = |y|_1\} \\
  &= L
\end{align}


Finding the most efficient paths to cover an area from multiple starting locations I'm looking to design an algorithm for a problem I have, and was hoping there may be someone that could provide some insight on where to start.

In my picture above, the grid is the area they needs to be explored by the circles. Each cell is a unit of work, so currently I've got lat/lng coordinates for the exact center of each of the grid cells. The goal is to visit every cell in the grid. Circles must start in their home locations, and must end in their home locations.

In my current algorithm (SUPER simple, but it works), I'm simply taking the center coordinates of each of those grid cells, splitting them up into lists (number of lists = number of circles), then adding the home location to the beginning and end of each of those lists. As you can imagine, this leads to some very inefficient routes.

The grid areas can vary wildly, as well as the location of the "Homes", so an algorithm that simply determines the best possible route, by minimizing the total distance travelled for each circle to complete the entire task, is what I'm looking for.

I'm thinking this may be some sort of variant of Dijkstra's algorithm, where the distances between all the different center points as well as the home locations are all calculated before determining the lowest possible solution. Where my understanding kind of falls apart is Dijkstra's algorithm is shortest path from A to B, whereas this algorithm is more of a "shortest path from A to A, given that an individual circle can complete X many units of work, with the end goal of the entire grid area being completed".

With this algorithm, I'm picturing that it would take into account the return trip, since its part of the calculated distance I'm trying to minimize, so it would try to complete units of work that are on the way back home.

Any insight or guidance is greatly appreciated. Thank you.

If I understand your description correctly, there is no polynomial-time algorithm that solves each instance optimally. Intuitively, if you had an efficient algorithm for your problem, we could use it to find a Hamiltonian cycle (i.e., a cycle that visits each vertex exactly once) in a grid graph which is known to be NP-complete [1]. (The paper also contains hardness results for various "grids"; see whether some of the definitions actually capture your concept of a "grid").

In other words, we can reduce the problem of determining whether a grid graph has a Hamiltonian cycle to your problem where we have single circle.

You should not be discouraged too much by such a result though. It is perfectly possible you can do considerably better than your current algorithm, i.e., perhaps maybe even most of your instances are actually quite simple to solve. For instance, you could look at various metaheuristics and consider using (say) a genetic algorithm to find a good solution.

[1] Arkin, Esther M., Sándor P. Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. "Not being (super) thin or solid is hard: A study of grid Hamiltonicity." Computational Geometry 42, no. 6-7 (2009): 582-605.


Annotated type system problem about conditional branch I am reading the book "Principle of Program Analysis" by Flemming Nielson for annotated type systems. In the first chapter, section 1.6 they mentioned the simple type system for various statements(S). And S maps a state to a state, and may therefore to have type Σ --> Σ where Σ denotes the type of state. So they mentioned a system of axioms and inference rules like below for sequential statements and if-else block:

And later it is explained, an if-else statement in terms of Reaching Definition as below,
Also, I can visualize the sequencing rule seems natural, but they mentioned conditional rule is more dubious. I am not able to understand how this is dubious? As per my understanding reaching definition after after 'if' block execution will may execute then block or else block, then how this is even conflicting? S1 may have different statements and S2 will also have different statements but these two blocks would not execute at same time. I am not getting this scenario, can you please help me with this

With the above expression, two branches (if and else) have the same analysis information at their respective entry and exit points i.e. In simple terms we can say that then-branch gives rise to the same set of reaching definitions as the else-branch does.
So, this is dubious, depending on the condition of if-block it is decided control will go to then or else block which will become the exit of if-block. To follow this idea we can modify the equation like below.

We assume that if if-block gets executed as true then final(S1) is executed i.e. RD2 and for false statement final(S2) i.e. RD3 is executed. The exit of the if-block is the subset of the union of then-block and the else-block.


Condition of square root algorithm (Newton's method) I am reading the book Algorithm 4th and see this square root algorithm using Newton's method (java sample code):

public static double sqrt(double c)
{
    if (c < 0) return Double.NaN;
    double err = 1e-15;
    double t = c;
    while (Math.abs(t - c/t) > err * t)
        t = (c/t + t) / 2.0;
    return t;
}

I wanna know what's the rule behind the while loop condition,

Math.abs(t - c/t) > err * t

Why is it (|t-c/t|)/t > err?
For exmaple, can't the condition simply be  |t-c/t| > err?

I know that, t-c/t -> 0 when loop count -> ∞.

I remember that I encouter many "manually choose approximation condition" when learn Probability Theory. But now I totally forget it. So any related,basic background knowledge explanation or introduction would be much appreciated.

Newton's method from my original math textbook:

$$ a>0, x_0>0, \\ \{X_n\}: X_n = \frac{1}{2}(x_{n-1} + \frac{a}{x_{n-1}}) \\ \lim{x_n} = \sqrt{a}\ $$

Try calculating the square root if 1e-100 with the changed loop condition and see what result you get. Then try calculating the square root of 1e100. Do you run into any problems?

This is numerical mathematics, limits won’t work well. Print out the value of t -c/t and check whether it actually converges, and check if it converges to 0. For some different values if c.

From a wiser man than me: The problem are not the things we don’t know. The problem are the things we know that ain’t so.


Why is universal turing machine considered with only one head? While defining the following time hierarchy theorem (for deterministic case ) :

  If $f(n)\log{f(n)}=o(g(n))$ then there are languages decidable in $O(g(n))$ which cannot be decided in $O(f(n))$

The $\log$ factor comes due to the overhead of simulation by universal Turing machine, as the universal Turing machine has only one head. But what if the universal Turing machine uses same number of tapes and tape heads as some Turing machine $M$, when $<M,x>$ is given as an input to it ? Does the $log$ factor vanish ? Am I missing something ?

There are two (related) answers to your question. The first answer is that the time complexity classes are traditionally defined using one-head Turing machines. For the diagonalization argument to work, we need the simulating machine to be of the same kind as the simulated machines.

The second answer is that even if you consider time complexity classes defined using $N>1$ heads, then you are going to encounter a similar problem with the universal Turing machine who only has $N$ heads but has to simulate both the original $N$ heads and to read the program. (It could be that the performance hit is not as bad for more than one head.) Making the number of heads finite but unbounded will make things even worse, since the universal Turing machine has a fixed number of heads.


What will i obtain if i apply a xor-ing a one way function and it's input? I know that a one-way function is informally a function that it's easy to compute but hard to invert.
If f(x) is a one way function the function  $g(x) = x\oplus f(x)$ is a one-way function?
My intuition is that it's but i not really sure.

Let $h$ be any one-way function, and define $f(x) = 0^{|x|} h(x)$. Note that $f$ is also one-way: it is easy to compute, and if you can invert $f$ you can invert $h$ (so since $h$ is hard to invert, so is $f$). But $g(x) = xh(x)$ is easy to invert.


Efficiently compute parallel matrix-vector product for block vectors? I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product
$$w = (E\otimes I_N)v$$
in parallel, where $\otimes$ is the Kronecker product, $v = (v_1, ..., v_P)^T$ is the stacked vector consisting of all local vectors $v_p$, $E = (e_{pj})_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I_N$ is the identity matrix of size $N\times N$.

So, to do this, each processor $p=1, ..., P$ has to compute
$$w_p = \sum_{j=1}^P e_{pj} v_j$$
and for this, all $P$ vectors $v_p$ have to be sent to all $P$ processors.

Now, $N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v_p$ together) does not fit into each processor's memory. Also, sending all these vectors $v_p$ in an all-to-all fashion seems pretty hard on the network.

Is there a standard and/or particular efficient way to compute this sum for a general matrix $E$? What would be the complexity of this approach?

Any help, suggestions or links to publications are appreciated!

You can do this as a parallel sum. You want to compute

$$w_i = \sum_{j=1}^P e_{ij} v_j,$$

where processor $j$ has the vector $v_j$.

One way to do this is to have each processor compute $e_{ij} v_j$ locally.  Then, use a binary tree to compute the sum.  In particular, processor 1 sends $e_{i1} v_1$ to processor 2, which computes the sum $e_{i1} v_1 + e_{i2} v_2$; processor 3 sends $e_{i3} v_3$ to processor 4, which computes the sum $e_{i3} v_3 + e_{i4} v_4$; and so on.  Then, processor 2 sends $e_{i1} v_1 + e_{i2} v_2$ to processor 4, which computes the sum $e_{i1} v_1 + e_{i2} v_2 + e_{i3} v_3 + e_{i4} v_4$; and so on.  Repeat until you have computed the final sum.  Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication.  Each processor only needs memory for $\Theta(N)$ data.  So, it looks like it meets all your requirements.  It may still be hard on the network, but that seems unavoidable given what you are trying to compute.  You'll do this $P$ times, to compute $w_1,\dots,w_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.


Show that the class of regular languages is closed under shuffle For languages A and B, let the shufﬂe of A and B be the language
$ \{w| w = a_1b_1···a_kb_k,$ where $a_1···a_k ∈ A$ and $b_1···b_k ∈ B,$ each$ a_i,b_i ∈ Σ^∗\}$.
Show that the class of regular languages is closed under shufﬂe.

Approach: If A and B are regular, then there exists an NFA R and T that recognizes them. I was thinking I could run R and T in parallel, so I would start running R by processing $a_1$ and then by using non-determinism, I would jump to the NFA T to process $b_1$. In this process I make sure that both NFAs aren't executed the original way because that would result in accepted strings that are not in the language, so I try to disconnect the edges in each NFA to jump to the other NFA and then disconnect again the edges of this NFA to come back to the previos NFA.. Is this process clear?

Here is the proof, but some lines are a bit unclear to me.

I can't understand d)i. I don't understand how the transition function works. How does it detect whether we are at DFA A OR B?

Suppose, we have a simple string like $w = a_1b_1$ then what I understand you want to do is process $a_1$ in $D_A$ then jump to initial state of $D_B$ using $\epsilon$-transition and the process $b_1$ in $D_B$ but we don't know where $a_1$ ends and $b_1$ starts. So using non determinism we check all possibilities of where $a_i$ can end and $b_i$ can start.

To do that we start with a combined starting state $(q_A,q_B)$.
We have all the states possible by making $Q = Q_A \times Q_B$
Now we two kind of transitions from any state from $Q$ first we make transition in $D_A$ ignoring the transition in $D_B$ that way we can handle the case where the symbol is part of $a_i$. In a similar way we will add second kind of transitions assuming symbol is part of $b_i$.

Going this way there won't be any possibility left unchecked.

  How does it detect whether we are at DFA A OR B?

we don't have a marker between $a_i$ and $b_i$ so we make 2 guess at every state. First, The symbol is part of $a_i$ or $b_i$ we are currently in and second, that the current symbol is first symbol of the next $b_i$ if we currently checking $a_i$ and next $a_{i+1}$ if currently checking $b_i$


Optimizing electoral votes in a political simulation... 200,000+ possibilities, how to run through them? So basically, in my government class, we are simulating a presidential election. Our grade comes from the presentation of our candidate, but as an added challenge our teacher has a running count of electoral votes garnered. How it works is like this:

there are only 18 states amounting to 286 delegates, so 144 needed to win
Candidates get a +1 'influence' in certain states (for example home state or somewhere they're popular) and -1, as do VP candidates.
Some states (CA and TX) have a pre-existing leaning of up to 2 'influences'.
You need to choose 4 issues you're against and 4 you're for, out of a list of 14. Each state has an issue they're against or for. As expected, being in agreement with a state nets you +1 in that state and disagreement nets you -1.
If you have more influence in the state, you win it. If it's tied at 0, then the popular vote (the class) gets to decide)

I'm trying to lock up the nomination without even needing to get the popular votes, and I'm trying to figure out what software I could use to do this. I know excel and python 3 at a basic level, but I'm wondering if there's some other way to do it.

Here is an image of what I'm talking about (as you can see, I'm playing as the republicans here). Also, the for and against positions formulas link to here. Now, if I need to choose 4 issues to be for and against, I think that's 14 choose 4 times 10 choose 4, which gives me 210,210 possible combinations. Is there a way to run through all of these to see which will give me the highest Net Electoral Vote count with the lowest closeness factor? Obviously, I don't know my opponents topics yet, but I'd like to have the largest margin of error possible to prevent them from flipping states.

Thanks for any help. tips, advice or comments!

TL;DR: Political simulation, have to find best possible combination of issues to talk about out of 200,000+ possibilities, how do I run through them?

200000 is not a terribly large number, a brute force solution in Python would probably run in reasonable time. You'd have to implement a function that calculates your influences depending on your answers to the 14 issues and then just check all the possibilities. Python has some nice library functions that can help in the itertools package, but programming questions should better be asked on Stackoverflow.

A solution that is requires more learning to implement would writing down the problem as an Integer Linear Program and feeding it to a solver. That would probably scale much better than a naive brute force solution. It also sounds more sciency. But as I said, your problem instance is reasonably small.


What's the theoretical difference between class and type? This question stems from my effort trying to learn ASN.1.

After I went through the PKCS#1 standard for RSA cryptosystem and X.680~X.683 side-by-side, I noticed that, they've defined

ALGORITHM-IDENTIFIER as a class, and
AlgorithmIdentifier as a sequence type that can be encoded using BER the basic encoding rule.

I've went through the Wikipedia pages on the subjects, in both computer science and mathematical fields. It seems to say that a "class" is more general than a "type" while "type" is more concrete than "class" on the other hand.

So what's the difference from a theoretical perspective? What are the examples? And possibly why the standard developers elect to use such terminology?

I am sure that the mentioned standard is using the terms "class" and "type" according to their basic English meaning, without referring to the scientific terms from mathematics and computer science.

In a standard you might have a parameter which identifies the general "form" of a packet, a message, a subprotocol, or even an algorithm. To name the possible "variants" allowed by the standard, one might refer to those as "classes", "forms", "kinds", "types", "groups", or similar English terms.

These terms are not used according to any scientific meaning, but become technical terms within the standard. E.g. the standard might consistently use "algorithm class" to refer to the value of a certain field of a packet, stating which algorithm was used to encrypt the payload. The standard might have instead used "algorithm type", or "algorithm kind" for the same thing, with no effect on the meaning. Usually the standard chooses a term and uses it consistently to help the reader understand it's referring to that field: using "algorithm" alone wouldn't be as effective.

It's only a coincidence that "type" is also used in type theory, and "class" is used in set theory.


Non-deterministic algorithms and Tautologies I am studying the lecture The Complexity of Propositional Proofs. Here there is a definition together with a discussion (page 3). I don't understand
that discussion.

Let $F$ denote the set of propositional formulas over the connectives $\wedge$, $\vee$, $\rightarrow$ and $\lnot$, with a countably infinite supply of propositional variables. An abstract propositional proof system is a polynomial time function $V: F \times \{0,1\}^* \to \{0,1\}$ such that for every tautology $\tau$ there is a proof $P \in \{0,1\}^*$ with $V(\tau, P) = 1$ and for every non-tautology $\tau$, for every $P$, $V(\tau, P)=0$. The size of the proof is $|P|$.
Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies.

Why does the author conclude "Definition equates propositional proof systems with non-deterministic algorithms for the language of tautologies."?

An algorithm computing $V$ can be thought of as a non-deterministic algorithm which gets only the first parameter $\tau$ and guesses $P$, verifying that $P$ is a proof of $\tau$.

If you've ever seen the definition of NP using witnesses, in this definition $V$ is accepts the language of all tautologies $\tau$ with proofs in a certain proof system. The witness that such a proof exists is the proof itself $P$, and the function $V$ verifies that the proof is valid for $\tau$.

Another equivalent way of defining a proof system is as a polynomial time function which accepts a proof $P$ and outputs a proposition $\tau$. The two properties satisfied by such a system $S$ is (i) for all $P$, $S(P)$ is a tautology, (ii) for every tautology $\tau$ there exists a proof $P$ such that $S(P) = \tau$. It is an easy exercise to convert between the two definitions.

If you want to learn more, look up Cook–Reckhow proof system.


Can't wrap my head around on building a suffix table for Boyer Moore My resources were the following video, as well as this video.
Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:

k
suffix
d2

1
B
2

2
AB
4

3
BAB
4

4
CBAB
4

5
BCBAB
4

and for "DRIDI":

k
suffix
d2

1
I
2

2
DI
5

3
IDI
5

4
RIDI
5

If all of the above is correct, I can't understand why in the first table, for k = 5, we have d2 = 4 (because we match the A with the suffix "BCBAB"?), where as in the second table for k = 4, we cannot do the same (match D with the D inside the suffix "RIDI"), hence why the value for d2 is the length of the pattern, i.e 5 and not 3.
What's going on here?

The shift rules of Boyer–Moore algorithm come from the bad character rule and the good suffix rule.
While the bad character rule exploits a single character that is in the text but not in the pattern, the good suffix rule exploits multiple contiguous characters that appear in both the text and the pattern.
"In the first table, for k = 5, we have d2 = 4." This is because "AB" is both a prefix of "ABCBAB" and a suffix of "BCBAB". So if some text contains "BCBAB", it is possible that text extends to right to contain "BCBABCBAB", thus containing the pattern "ABCBAB". It is not simply because 'we match the A with the suffix "BCBAB"'. That B after A should be matched as well.
In the second table for k = 4, although we can match the D at the beginning with the D inside "RIDI", a shift of 3 cannot possibly match the whole pattern, since it will lead to the mismatch between the I after D and the R after D. So there is no need to consider a shift of 3.
          T:    ***RIDI̲***
  current P:      DRIDI̲
P shifted 3:         DR̲IDI


What is the difference between "definition" and "inductive" in Coq? In Coq, you can use two different kinds of keywords to do definitions--Inductive and Definition.  I do not understand the difference between an inductive and a definition, or when it is appropriate to use one instead of the other.

Could someone with experience in Coq please shed some light on this, or provide a reference that is more succinct/informative on this point than the standard Coq tutorial?

Update:

Here are some additional, generally quite basic questions I have about Coq:

How do you force a set to be finite?  Is there a "finite set" data type?
What exactly do ":" and ":=" mean?

Inductive creates a new type and gives it a name. It is similar to datatype in SML, data in Haskell, type (defining an ordinary variant or a record) in Ocaml.

In addition to defining the type, Inductive also defines induction principles for that type. These induction principles aren't necessary from a theoretical point of view: all they do is to give a name to a particular well-typed term. They are provided because while you could write that term in your proof, it is mechanical and repetitive.

Definition gives a name to a term. It's broadly similar to let in SML or Ocaml or Haskell (but it doesn't let you write recursive definitions as such). Since Coq is pure (no side effects), if you write two definitions with the same right-hand side, the resulting names are equal. You can use Definition at any level of the sort hierarchy, including for types (in which case the definition is similar to type aliases in SML, Ocaml or Haskell).

Fixpoint is similar to Definition, but allows a recursive definition (like let rec in ML). It's in fact syntactic sugar for Definition plus the explicit fixpoint combinator fix, but definitions made using Fixpoint are easier to read and write.

The best way to understand these is to write a few proofs about some datatype. Try to rewrite some parts of the List library, for example.

There are several ways to implement finite sets in Coq. To to set theory proofs, try Sets.Finite_sets. If you want to have decent extracted code, use MSets.MSetAVL.


Why is And-Or-Graph-Search called a search algorithm? An algorithm in Artificial Intelligence: A Modern Approach for planning in stochastic, fully observable environments is called And-Or-Graph-Search, implying that it's a search algorithm. However, I don't see how it is one. Wikipedia defines search algorithms as, "an algorithm for finding an item with specified properties among a collection of items," but And-Or-Graph-Search doesn't do that. It instead finds multiple items (goals states) in order to guarantee it will reach a goal state no matter what the results of its stochastic actions are.

So, why is it a search algorithm?

Here's its pseudo-code:

function AndOrGraphSearch(problem) returns a conditional plan, or failure
    OrSearch(problem.initialState, problem, [])
function OrSearch(state, problem, path) returns a conditional plan, or failure
    if problem.GoalTest(state) then return the empty plan
    if state is on path then return failure
    for each action in problem.Actions(state) do
        plan = AndSearch(Results(state, action), problem, [state | path])
        if plan does not = failure then return [action | plan]
    return failure

function AndSearch(states, problem, path) return a conditional plan, or failure
    for each si in states do
        plani = OrSearch(si, problem, path)
        if plan = failure then return failure
    return [if si then plani else if s2 then plan2 else . . . if sn-1 then plann-1 else plann]

AndOrSearch is an algorithm for searching And-Or graphs generated by nondeterministic environments. It returns a conditional plan that reaches a goal state in all circumstances. (The notation [x|l] refers to the list formed by adding the object x to the front of list l.)

The function is from the book Artificial Intelligence: A Modern Approach.

You can view And-Or Graph search as a search algorithm in two ways:

As search in the state space: Here, the "items" from the Wikipedia definition are the states, and an "item with specified properties among a collection of items" is a goal state. With And-Or Graph search, finding one such item is generally not enough. Under this view, the definition on Wikipedia is a bit too narrow.
As search in the space of partial conditional plans: Here, the "items" are partial conditional plans, and an "item with specified properties among a collection of items" is a total conditional plan, i.e., a partial conditional plan with the specified property that it is guaranteed to reach a goal state after a finite number of steps. Unlike a total conditional plan, a partial conditional plan may contain leaf nodes that are neither goal nodes nor have an associated action in the plan. Search steps in this search space are extensions of partial conditional plans by one action, i.e., these steps take a partial plan P and return a new partial plan P' that is like P, but with one non-goal leaf replaced by a valid action assignment to that leaf node.

Both views are legitimate, and the second one is perfectly consistent with the Wikipedia definition.

The analogous distinction in regular graph search would be between searching for a goal state and searching for a path to a goal state.


Define a grammar to emmulate chess rules Is it possible to define a 《chess language》:
language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}?

I looked online but I cannot find a way to define the grammar. Every way I can think of, is either stupidly long and complicated, or does not cover all the rules.

I presume the hard part is that the grammar has to take in consideration the state of the board before evaluating a move as valid or not.

Do you have insight how to approach this problem i.e: define a grammar that emulates chess rules?

The way chess apps work(not engines), is that at every move they calculate all possible moves and then check if the user's move is among the calculated moves, else it is invalid.

I want to accept the user's move and only then check if it's a valid one.

"The way chess apps work(not engines), is that at every move they calculate all possible moves and then check if the user's move is among the calculated moves, else it is invalid."

No, no, no, no, that's not how you check if a move is valid.

If you want all possible moves, then you generate all possible moves. If you want to check if a move is valid, then you check if that move is valid, and nothing else. There's no reason to know anything about all the other moves if all you want to know is to check if one move is valid.


Number of different binary search trees storing n distinct keys? How many different binary search trees are possible that store the values 1,2,...,n ?

So far I found a recursive formula for the number (by case distinction what's at the root):

$ T(n) = 2T(n-1) + \sum_{i=2}^{n-1}T(i-1)T(n-i), n > 1 $ and $ T(1) = 1 $

But I have no idea how to solve this recursion. Our task was only to find the recursion and I believe this to be a correct solution. But I am very interested in a closed formula of it. Can anyone link me to some resources/books or give a general hint on how it can be solved?

The solution to your recurrence is
$$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$
also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the OEIS to identify the sequence.


Church-Turing thesis is a dualism Church-Turing thesis : Every effectively calculable function is a TM-computable function.

But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the paper.

Does this imply that, for one who believes in the Church-Turing thesis, there is only two options :

There is two distincts worlds : The effective one (where Church-Turing thesis applies) and the paper
one (where Church-Turing thesis doesn't apply necessarily). That is the physical world and the ideas world of the classical
dualism theory.
All the hypercomputation models are inconsistent. Using an hyper-TM in a reasoning is the same than, for instance, using an integer both even and odd in a reasoning, this can lead to false conclusions.

?

There's another possibility: hypercomputation is not implementable in the real world, and is only an imaginary/theoretical concept.  If this is the case, then there is no contradiction with the Church-Turing thesis.

Of course, anyone can invent imaginary worlds where strange things are true.  For instance, there's the computer scientist's Superman: not only can he leap tall buildings in a single bound, he can also solve undecidable problems in his head!  I suppose one could imagine such a thing, but that doesn't mean it has any correspondence to the real world, and the possibility of imagining such a Superman doesn't contradict the Church-Turing thesis.  The study of hypercomputation can be thought of as asking, well, ok, so Superman might not be real, but what if he were?

The Church-Turing thesis is a hypothesis about the real world, so imaginary schemes that can't be implemented in the real world don't contradict it.


Trying to figure out if a modern computer is capable of manipulating arbitrarily large pointers I was just thinking about Turing-completeness and its relationship with modern computers.  I've always thought that a real computer is not technically Turing-complete.  It is equivalent to a linear-bounded automaton; a Turing machine has infinite memory, whereas a real computer has only finite memory.

However, you can add memory to a computer through expansion cards, external mass storage drives, etc.  The limiting factor then becomes the maximum size of pointers.  Obviously, a 64-bit CPU can store a 64-bit pointer in its general-purpose registers, and languages like C/C++ can easily be modified to support 64-bit pointers.  However, I'm not sure if they would be able to manipulate arbitrarily large pointers, and thus an arbitrarily large address space.

My thoughts are as follows: Most modern CPUs include instructions that allow for arithmetic involving arbitrarily large integers.  For example, the Intel architecture has the ADC and SBB instructions, where the carry flag from the last operation is added or subtracted from the result of the current operation.  This allows for addition and subtraction of arbitrarily large numbers in a piecewise fashion.

Theoretically, this could also be done with pointers.  Say you want to increment a 1024-bit pointer by some amount.  You simply add an immediately addressed value to the pointer using the ADC instruction in 16 successive operations.

The problem comes when you actually have to dereference the pointer.  Intel CPUs, and probably most other CPUs as well, are incapable of operating directly on variables in memory, while simultaneously being incapable of storing an entire arbitrarily large pointer in the registers all at once.  You can't dereference a pointer in a piecewise fashion; you have to dereference the entire thing.  So it all boils down to the question of whether a pointer can be dereferenced in this fashion.  It has occurred to me that I don't actually understand how pointer dereferencing is done at the machine level, and I would like someone to explain how this works.

Of course, this question is of no practical importance, because simply having 64-bit pointers allows for an address space that probably surpasses all the memory currently in existence.  I am simply interested in this question from a theoretical standpoint.

The universe is finite, so you can't build a real turing complete computer.

The best you can do is build a computer which observes whether the program it is running is getting close to the limitations of the computer, and when it exceeds them, builds a new, bigger computer, with higher limits, transfers the code to the new computer, and starts all over again.

PS. It is quite possible (and not really very difficult) to build a computer with 256 bit pointers. Since the universe is not just finite, but has a known size, 256 bit pointers are enough for anything.


Min Fibonacci Heap - increase key I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps. I know that min-heaps generally support decrease-key. I was able to write the increase-key operation for a binary min-heap, wherein, I exchange increased key with the least child recursively. In the case of the Fibonacci heap, In this reference, they say that the Fibonacci heap also supports an increase-key operation. But, I couldn't find anything about it in the original paper on Fibonacci Heaps, nor could I find anything in CLRS (Introduction to Algorithms by Cormen).

Can someone tell me how I can go about implementing the increase-key operation efficiently and also without disturbing the data structure's amortized bounds for all the other operations?

First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap.

If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\omega$ with $\forall x:\omega > x$ to push the head to the end.

Now, knowing that $\text{increase-key}$ must be $O(\log n)$ we can provide a very simple asymptotically optimal implementation for it. To increase a node $n$ to value $x$, first you $\text{decrease-key}(n, -\infty)$, then $\text{delete-min()}$ followed by $\text{insert}(n, x)$.


How do you prove that polynomial reductions are not symmetric? How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other way round, but am not sure what such problems could be.

You have a good plan of approach.  Now you need to spend some more time pursuing this.  Try to come up with a list of languages $L$ you've seen before, and try different pairs to see if they satisfy the condition.  After some trial and error you should be able to solve your problem.


Decision Tree with Unbalanced Data I have a data set with two classes: one class has at most 2000 members while the size of the second class is unlimited, though it is typically in the hundreds of thousands.  I have read that it is problematic to use a decision tree to naively classify this data.  My question is, how how I modify the data or the classification scheme to classify such data, using a decision tree at some point?

Most common approach to such problems is some form of sub-sampling: randomly draw equal numbers of examples for each class. For model tuning you can use Stratified Cross-validation which in essence uses exactly this approach.

Other possibility is to weight the examples according to the ratio of class sizes. However, since on of your class has infinite number of samples this is impossible, unless you'll first employ sub-sampling anyway, at least for this infinite class. One example for decision tree context is modified information gain: "A Robust Decision Tree Algorithm for Imbalanced Data Sets" by Wei Liu, Sanjay Chawla, David A. Cieslak, Nitesh V. Chawla (PDF)


A non-polynomial reduction Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say that $P_2$ is NP-complete?

No. As a counterexample pick any non-trivial problem $P_2$, i.e., a problem with at least one yes instance $I_{\text{yes}}$ and at least one no instance $I_{\text{no}}$.

To reduce an instance $I_1$ of $P_1$ to an instance $I_2$ of $P_2$ first solve $I_1$ (e.g., by brute force). If the answer to $I_1$ is yes, then let $I_2 = I_{\text{yes}}$, otherwise $I_2 = I_{\text{no}}$.


Area preserving distance optimization I stumbled across the optimization problem described below and I am looking for how to approach it efficiently. I have the feeling that the problem at hand might be known, but I was not able to find its name or further information on it. So any help to find an efficient algorithm for its solution or a pointer to the name of the problem at hand would be very helpful.
Given $ n \times m $ matrix $ M $ of integers from $ [0, w) $ and a set $ P $ of $ w $ points (i.e. tuples of indices in the matrix),
find a permutation $ M' $ of the values of $ M $, such that the global distance function $ f(M') = $
$ \sum_{i=0}^{n-1}{  \sum_{j=0}^{m-1} } {  \left(i - x\left(P[M'[i, j]]\right)\right)^2 + \left(j - y\left(P[M'[i, j]]\right)\right)^2  } $ is minimal.
Explained in a different way, consider an image with $ n \times m $ pixels, where each pixel is of one of $ w $ distinct colors. We then want to rearrange the pixels such that all pixels of the same colors from a group around the seed point of the same color. We are allowed the swap the colors of pixels as long as the total number of pixels for each colors stays constant. Below you find an example of the resulting image from a random initial image with a hundred equally likely color as starting point located around randomly pixed seed points. The result was obtained by iteratively picking two points at random and swapping them if the global distance function after swapping is reduced. Doing this for millions of times approaches (at least a local) optimum depicted in the images. However this approach is rather slow for larger values of $ n $ and $ m $. So I am looking for a faster solution to obtain the result. Also a non-discrete solution where polygons would describe the final areas would be appreciated. I was also considering Voronoi tesselations (which can be computed much faster), however they do not work in my case due to the fixed area constraint (i.e. the colored sections should be of equal size in this example).

This appears to be an instance of the assignment problem, where you are trying to match up the $nm$ cells of $M$ with the $nm$ cells of $M'$.  For each place where $M[i,j]$ may get permuted to, you can compute the cost of that: namely, if it is permuted to $M'[i',j']$, then its cost is $(i'-x P[M[i,j]])^2 + (j' - y P[M[i,j]])^2$.  Then you can use standard algorithms for the assignment problem, such as the Hungarian algorithm.  Whether this is practical or not may depend on how large $nm$ is.  If it's not practical, you could instead try a heuristic, such as local search algorithm based on making swaps.


What exactly is a linear function, and what is a nonlinear function? I am learning a bit about machine learning, and I frequently see things labeled "linear function" or "nonlinear function."

For example when discussing a neural network created by combining individual logistic regression nodes, a book I read noted that logistic regression is a linear function, and that the entire network would be no more powerful than a linear model except that a nonlinear function (such as relu or tanh) is applied to each node. I don't really appreciate this, because I don't have a firm grasp on the definition of linear function.

To use a simpler (to me) example, I was confused when I learned that both SVM and linear regression are linear models. It is easy for me to see how linear regression is a linear model, because its calculations are similar to the definition of a line, y = mx + b, that I learned in middle school. SVM seems more exotic to me.

So how can we know if something is a linear function/model versus a nonlinear one? Does it have to do with how the inputs are gathered, or the nature of the calculations afterward?

A linear function is a function of the form
$$
\ell(x_1,\ldots,x_d) = \sum_{i=1}^d a_i x_i + a_0,
$$
where sometimes the constant term isn't allowed.

A linear classifier is a classifier which is of the form "$\ell(x_1,\ldots,x_d) \geq 0$", where $\ell$ is linear.

Using the "kernel trick", you can masquerade non-linear classifiers as linear classifiers; SVM with a non-linear kernel is linear in that sense. In brief, we fix a mapping $\Phi\colon \mathbb R^d \to \mathbb R^D$ (where $D$ is possibly infinite), and then use a classifier of the form "$\ell(\Phi(\vec{x})) \geq 0$". The kernel trick is a way to evaluate the classifier (and train the model) without actually computing $\Phi$.


What can be concluded from a full application of resolution? I know that resolution is refutation complete,
but what can we conclude if a resolution procedure leads to a situation with no more chance to operate the resolution?

Given a propositional formula which we want to check its satisfiability,

( a + b ) ( ¬a + c )

after one resolution the formula become

( a + b ) ( ¬a + c ) ( b + c )

what can we conclude at  this point?

By definition if a proof system is refutation-complete then once you've applied it to the maximum extent and not found a contradiction, you have proven that there are no refutations, i.e. the formula is satisfiable.  To find a satisfying assignment, add a unit clause that asserts a value for one of the variables, e.g. $(a)$, and use resolution on the resulting formula.  If you find a refutation (produce an empty clause), then replace the asserting clause with its negation e.g. $(\lnot{a})$, otherwise leave the original assertion in the formula.  Repeat the procedure with a different variable.  Eventually you'll have successfully asserted values for all the variables and found a satisfying assignment.


MST: Is there such an example of a graph with unique mst and not unique light edge? The problem is the following:

Give an example of a graph that has a unique minimum spanning tree but for every cut of the graph, there is not a unique light edge crossing the cut.

I am trying to find such a graph, but I have not find any example. Is it possible to have such a graph? If not, why?

If there is not a unique light edge crossing any cut, it means that every node has at least 2 edges of minimum weight. If you use Prim's algorithm to build your MST which is:

Grow the tree, adding nodes one by one.
On each step, select the minimum weight
edge leading to a new node.

You realise that whatever is the starting node, you have at least 2 choices. If the MST was unique, there would be leaf nodes having only one possible edge. Therefore there are several possible MST.


Solving using the master theorem I am wondering why this

$T(n)=3T(n/4)+n⋅lg(n)$

recurrence can be solve by Master Theorem case 3 but this
$T(n)=2T(n/2)+n⋅lg(n)$
recurrence can not be solve by Master Theorem what is the difference between this two recurrences.
When I searched on google I found tow questions related with this two recurrence
First Question:
Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
Second Question:
T(n)=2T(n/2)+nlognT(n)=2T(n/2)+nlogn and the Master theorem

But both of them say something in contrast with  each other and I could't find out the main reason.

In these cases it's always a good idea to look at the statement of the master theorem. The statement on Wikipedia states regarding case 3 that if
$T(n) = aT(n/b) + f(n)$ where

$f(n) = \Omega(n^c)$ for some $c > \log_b a$ (i.e. $b^c > a$), and
$af(n/b) \leq (1-\epsilon) f(n)$ for some $\epsilon > 0$ and large enough $n$,

then $T(n) = \Theta(f(n))$.

Let's see whether the theorem applies in your two cases. In your first case $a = 3$, $b = 4$, and $f(n) = n\log n$. We have $f(n) = \Omega(n^1)$ and $1 > \log_4 3$, and furthermore $$3f(n/4) = 3(n/4)\log(n/4) \leq (3/4)n\log n = (3/4)f(n).$$
Both conditions are satisfied, and so we can conclude that $T(n) = \Theta(n\log n)$.

In your second case $a = b = 2$ and $f(n) = n\log n$ is the same. In this case $f(n) = \Omega(n^c)$ only for $c \leq 1$, whereas we need $c > \log_2 2 = 1$, so we cannot apply case 3. The second condition also doesn't hold, since $2f(n/2) = 2(n/2)\log(n/2) = n\log n - \Theta(n)$, and so it is not true that $2f(n/2) \leq (1-\epsilon) f(n)$ for any $\epsilon > 0$.

However, in this example case 2 of the master theorem applies, showing that $T(n) = \Theta(n\log^2 n)$.


Given n strings, is one of them a substring of another? Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$.  I would like to know whether any of those strings is a substring of any other string in the collection.  In other words, I'd like an algorithm for the following task:

Input: $S_1,\dots,S_n$

Output: $i,j$ such that $S_i$ is a substring of $S_j$ and $i\ne j$, or None if no such $i,j$ exist

Is there an efficient algorithm for this?

If we replace "substring" with "prefix", there is an efficient algorithm (sort the strings, then do a linear scan to compare adjacent strings; sorting will ensure that substrings are adjacent).  But it seems more challenging to test whether any string is a substring of any other string.  A naive algorithm is to iterate over all pairs $i,j$, but this requires $\Theta(n^2)$ substring tests.  Is there a more efficient algorithm?

I guess we could call this "all-pairs substring testing", or something like that.

My ultimate goal is to prune the collection so no string is a substring of any other, by removing each one that is a substring of something else in the collection.

You can build a suffix tree in linear time and check if there's an inner node that corresponds to a full string (constant time per node).

In more detail, assume we are given strings $s_1, \dots, s_n \in \Sigma^*$.

Build a (generalised) suffix tree of $s_1\$_1, s_2\$_2, \dots, s_n\$_n$ with $n$ pairwise distinct terminal markers $\$_1,\dots,\$_n \notin \Sigma$.

Using Ukkonen's algorithm, this can be done in linear time; linear in the sum of all string lengths.
Assuming that you label leaves with $(i,j)$ if they represent suffix $s_i[j..|s_i|]$ of $s_i$, traverse the tree and find those $n$ leaves labelled $(i,0)$, i.e. the leaves that correspond to the full strings.

This takes time linear in the tree size, which itself is linear in the input size.
The descendant leaves of the parent of $(i,0)$ (which is reached by an edge labelled $\$_i$) represent all matches from the set; this follows from the basic invariant of suffix trees. Find any one match by descending to any leaf (but $(i,0)$).

This again takes linear time.

The distinct terminal markers are not really necessary; a single one used to terminate all strings is quite sufficient as long as you allow multiple labels per leaf.


Determine whether a context-free language is deterministic or not I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown automata for this  language like below.

first I read $a$ and push it to stack till it ends. right know number of $a$ in the stack is $x = k + m$ or $x = n$. now for each $b$ we can erase a $a$ from stack and there will appear tree case

case 1:
stack will be empty and we can still read $b$ so the string should be in $\{a^n b^n b^k c^k\}$
case 2:
stack will be contain some $a$s and string should be in $ \{a^k a^m b^m c^k \}$
case 3: stack will be empty and there is no $b$ to read so $k$ should be zero.

in case one we can push $b$ into stack and after that we have $k$, $b$s in the stack and we can pop each one of $b$ instead of reading a $c$.
in case two the number of $a$ in the stack is $k$ and like case one read $c$ and pop $a$ until stack will be empty.
so I think this $DPDA$ should accpet language $L$ but I heard from someone that this language is not deterministic context free language. is my $DPDA$ wrong? where is the problem?

The language that is usually cited as not accepted by any DPDA is $\{a^mb^nc^nd^m\} \cup \{a^mb^mc^nd^n\}$. This is because we don't know whether to push or pop when $b$ arrives. The language you describe seems to be accepted by the DPDA you have constructed.


Would a class in Linear Optimization/Programming be useful for a CS degree? Would a class in Linear Optimization/Programming be useful for a CS degree?

What is it used for or how useful is it.

Can someone please help me decide.  Thanks in advance

I think it depends on what do you want to do after graduating. Linear Optimization/Programming is more theoretical  than practical, it will definetly be useful (take it) if you want to work as an academic/researcher but it won't be that helpful if you want to be a software developer.


Algorithm to determine whether a given graph is a caterpillar tree I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree.

A caterpillar tree is a tree that has a path to which all nodes are connected by a maximum of one edge. So for every vertex v there is a vertex u on the path so that the disctance between v und u is at most 1. In other words, removing all the leaves results in a simple path.

The only progress I've made so far is that I could use breadth-first search or depth-first search to traverse the graph. They have a complexity of $\mathcal O(|V|+|E|)$, but in a caterpillar tree, $|E|=|V|-1$, so I end up in $\mathcal O(2|V|)$ = $\mathcal O(|V|)$.

Is that idea correct? If so, then how can I modify BFS/DFS to do what I want? I am thinking of adding a branch depth counter of some sort and allowing only one branch with length >1 (the central path of the caterpillar), but I have no idea how to implement that without changing the original algorithm too much.

When considering such recognition algorithms, it is sometimes helpful to consider equivalent characterizations of the graph in question. Your observations and ideas are valid.

In other words, we can first prove that caterpillars are such trees that when you delete all the leaves and incident edges, you are left with a path graph. This immediately suggest a simple linear time algorithm: check that your input graph is a tree, remove all the leaves, and check that you have a path.

In fact, I suggest you divide your problem into 3 subtasks you can work on independently:

Implement a function that outputs YES/NO based on whether the input graph is a tree.
Implement a function that removes all the leaves and the edges incident to them from the input graph.
Implement a function that outputs YES/NO based on whether the input graph is a path.


The best approach to search for closest object in hash map holding arraylist without changing data structure Imagine the game handled server sided, don't think of a visual problem.

Given a game 2D map, with size of n * n.
The game contains objects (such as door, wall, a table).

Each tile position (x,y) can contain multiple objects, but this is not the catch of the question, it can even be limited to one.

The data structure for the game objects linked to the map is designed like this:

HashMap<Integer, ArrayList<GameObject>>

Where the Key integer represents X position of the object, and the value represents a list of all objects with the same X position, different Y position.

Now, I have a player location, I want to fetch a list of all 10 closest object to the player's position, within 100 tiles distance of the player.

My way of doing so:

Starting from player's position, and simply going x - 1 and x + 1 grabbing the objects lists limited to Z or until you have 10 closest objects collected, and then performing a position distance comparing search on each object. (Note, the objects lists are not sorted)

But this way is not stable, in my opinion, but I am not sure how can you solve this without changing the data stucture?

If it is for some reason important to use hashing, there is a concept called locality sensitive hashing, however it is somewhat complicated. Typically, nearest neighbor search is done with tree indexes, such as quadtrees, R-Trees or kd-trees.


Time complexity of recursive function I am trying to find out how they calculated the time complexity of this small function .
I am studying for an exam and found this question and the final answer is given, but I am trying to understand how they got to this answer,
I tried solving this problem using Iterative but when I tried to find the number of Iterations of this function I got stuck !

What I tried: let $T(n,k)$ represent the time complexity of $g$. It satisfies the recurrence

$$    T(n,k)=ck+\sum_{j=1}^i(2^j-1)k + T(n-i,2^ik)$$

when $i$ is the number of iteration in this function, so according to this function the iteration ends when $n\le k$, which means $n-i=2^ik$,
but I couldn't extract $i$ from the equation.

Here is the function, whose time and space complexity are stated to be $\Theta(n)$ and $\Theta(\log n)$:

   int g(int n, int k) {
      if (n <= k) return 1;

      int result = 0;
      for (int i = k; i > 0; --i, ++result);

      return result + g(n - 1, 2 * k);
    }

    int f2(int n) {
      return g(n, 2);
    }

Let $k_i = 2^i$, and define $m$ to be the minimum value such that $n-(m-1) \leq k_m$. It's not hard to check that the running time of $f_2$ is $\Theta(k_1 + \cdots + k_{m-1})$. Since $k_i$ grows exponentially, $k_1 + \cdots + k_{m-1} = \Theta(k_m)$, and so the running time of $f_2$ is $\Theta(k_m)$.

It remains to find the minimum integer value of $m$ which satisfies $n-m < k_m = 2^m$. Clearly this minimum value is at most $\log_2 n$, implying that $2^m \leq n$. This also means that the critical value of $m$ satisfies $2^m > n-\log_2 n = \Omega(n)$. Therefore $k_m = \Theta(n)$, and so the running time of $f_2$ is $\Theta(n)$.

Regarding the space complexity, it is proportional to the depth of the recursion, which as we have seen is very close to $\log_2 n$.