Can every algorithm's running time be expressed as $\Theta(f(n))$? That is, can the running time of every algorithm $A$ be written as $O(f_A(n))$ and $\Omega(f_A(n))$, for the same function $f_A$?

The best case running time and the worst case running time on inputs of length $n$ can each be expressed in this way (as can any function of $n$), however, the two measures do not need to coincide. Details follow.

The running time of an algorithm is not a function only of input size $n$ but a function of the input and there are various running time measure that you can define as functions of $n$. You can define $f_A(n)$ as the worst case (=largest) running time over inputs of size $n$ and $g_A(n)$ as the best case (=smallest) running time over inputs of size $n$. Alex's argument is basically that $f_A(n) = \Theta(g_A(n))$ is not true for every algorithm $A$. The big-oh, big-omega and big-theta notations are used to denote the growth rate of a function as its argument goes to infinity - by itself $\Omega()$ doesn't say whether you are talking about worst case running time or best case running time, and neither does $O()$. So for the insertion sort you have:

$f_A(n) = \Theta(n^2)$ because you never need more than $O(n^2)$ steps to finish sorting and for each $n$ there is an input (reverse order) for which the algorithm takes at least $C n^2$ time for some constant $C$.
$g_A(n) = \Theta(n)$ because for each $n$ there is an input (sorted array) for which insertion sort runs in linear time and of course you need at least linear time to read the array.

And of course $f_A(n) = \Theta(f_A(n))$ and $g_A(n) = \Theta(g_A(n))$. However, $f_A$ and $g_A$ need not be monotonically increasing, they can oscillate infinitely often.

If you feel comfortable with all that you might check this discussion too: http://blog.computationalcomplexity.org/2005/01/big-omega.html


Connectedness of points on contour Consider a (smooth) function
\begin{align*}
F: \mathbb{R}^2 \to \mathbb{R}
\end{align*}
with the contour
\begin{align*}
\mathcal{C} = \{x \in \mathbb{R}^2 | F(x) = 0\}
\end{align*}
The function (and possibly derivatives) will be given as analytical expression, and be continuously differentiable everywhere. I am trying to find an algorithm that takes two points $x_1, x_2 \in \mathcal{C}$ that are numerical roots of this function and tells me, if they lie on the same connected component of $\mathcal{C}$ (or maybe some more general set). I am a little lost here. I found some info on a (pretty complicated) algorithm that seemingly would allow me to first construct a graph representing $\mathcal{C}$ with accurate topology, and then I could just check to which connected component my points belong.

However, I don't fully understand the algorithm and it seems a little overboard for what I want to do. Does anyone know of an easier/faster algorithm to achieve this? Will I have to compute the full contour to solve this?

Edit: In case I really have to compute the full contours (or at least trace part of them) and there is no shortcut, my question would be: How can I compute the connected components of the contour? All sources I stumble upon already require me having a graph that encapsulates the correct connectedness informations and tracing seems problematic without any reliable "test" to find out if two points (e.g. one before and after some tracing step) are indeed on the same component. Ideally I would like an algorithm that constructs a function, say $G:\mathcal{C} \to \mathbb{R}$, such that $G(a)=G(b)$ iff $a$ and $b$ lie on the same connected component.

If $F$ is continuously differentiable and smooth, you can use the gradient to walk along the contour.  In this way you could walk on the contour starting at $x_1$ (tracing both directions of the contour) and see if you reach $x_2$.

In particular, if you're currently at a point $x \in \mathcal{C}$ on the contour, then the gradient $\nabla F(x)$ tells you what direction to walk if you want to stay on the contour: you should walk in the direction $(\nabla F(x))^\perp$, where we define $(a,b)^\perp = (b,-a)$.  (In other words, you should walk in the direction perpendicular to the gradient.)  In particular,  when $\epsilon$ is sufficiently small, $x + \epsilon \cdot (\nabla F(x))^\perp$ will be approximately on the contour.  This is because $\nabla F(x)$ points in the direction that most increases $F$, and if we're on a contour and the contour is a line, $\nabla F(x)$ points in a direction perpendicular to that contour.   (See, e.g., https://math.stackexchange.com/q/599488/14578.)

So in principle if the contour was a simple line (whether closed or open), the following would be sufficient: start at $x_1$ and walk in one direction and see if you eventually reach $x_1$.  In parallel, start at $x_2$ and walk in the other direction and see if you eventually reach $x_2$.

In practice there are two complications.

First, the contour is curved, so the gradient only helps you walk in a direction that is approximately along the contour -- but maybe not exactly.  So, I suggest a refined way to walk at the contour.  At you're currently at the point $x$, first to the point $x' = x + \epsilon \cdot (\nabla F(x))^\perp$.  The point $x'$ might not be exactly on the contour, but it'll probably be close.  Next, use gradient descent starting at $x'$ to find a point on the contour that is close to $x'$.  If $F$ is everywhere positive, you might do this by minimizing the objective function $\Phi(x'') = F(x'') + c \cdot \|x''-x'\|^2$ where $c>0$ is a sufficiently small constant; otherwise, you can use $\Phi(x'') = F(x'')^2 + c \cdot \|x''-x'\|^2$.  If you have a better way to find the nearest point on the contour, go ahead nad use that.  Finally, walk to this point $x''$.  This gives you an adjacent point on the contour, that's approximately distance $\epsilon$ away from where you started.  Repeat this.

The second complication is that the contour might not be a simple line; there might be places where two or more lines meet at an intersection.  At this point, $F$ won't be differentiable and the gradient might not be computable or meaningful.  You'll have to figure out how to detect that situation; perhaps you can use your domain knowledge about $F$ to help you detect that.  If you have no other ideas, one possibility is to pick a dozen random points in the neighborhood of $x$, project each one to the nearest point on the contour, check the gradient, and see if all of them seen consistent with a single nearly-straight line or whether their appear to be multiple lines converging.  Once you detect an intersection point, you can use depth-first search (basically, explore all directions out of the intersection point) to traverse the connected component -- then it reduces to the problem of checking whether two vertices in an undirected graph are in the same connected component, and that can be done using DFS.

This uses techniques that are quite similar to that proposed in my answer to your previous question on a 3D version of this situation.


An NP-hard problem reduces to its complement? I found this statement in a true/false test section:

Could someone explain in laymans why this is a true statement?

My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must be $\operatorname{co-\mathcal{NP}}$-hard. However, here we are assuming that a language that is $\operatorname{co-\mathcal{NP}}$-hard ($\overline X$) is reduceable to an $\mathcal{NP}$-complete language (3SAT). This is where I get lost. I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

First note that $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard since $X$ is $\mathcal{NP}$-hard (try to see why).
Since 3SAT is in $\mathcal{NP}$, any problem that can be reduced to 3SAT is in NP as well. So the statement suggests that the $\operatorname{co\mathcal{NP}}$-hard language $\overline X$ is in $\mathcal{NP}$.

On the other hand, saying that $\overline{X}$ is in $\mathcal{NP}$ is equivalent to saying that $X$ is in $\operatorname{co\mathcal{NP}}$. So in total we have $X \in \operatorname{co\mathcal{NP}}$ and $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard. So we get $X \leq_m^p \overline X$ by the definition of hardness.

Here is a bit of intuition of the fact that, if $X$ is $\mathcal{NP}$-hard, then $\overline{X}$ is $\operatorname{co\mathcal{NP}}$-hard.

Let $A$ be an arbitrary language in $\operatorname{co\mathcal{NP}}$. We have to show that $A \leq_m^p \overline{X}$. Let $B := \overline{A}$. Then $B$ is in $\mathcal{NP}$ and hence, $B \leq_m^p X$. This means there is a function $f$ computable in polynomial time, such that for an arbitrary word $x$, $x \in B$ if and only if $f(x) \in X$.

Now we show that $A \leq_m^p \overline{X}$. For a given word $x$. Using the same reduction $f$, we have $x \in A$ if and only if $x \notin B$ if and only if $f(x) \notin \overline{X}$ if and only if $f(x) \in X$.

Another note. Your intuition was right, but in the sentence

  I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

You should have probably said $\mathcal{NP}$ = $\operatorname{co\mathcal{NP}}$.


Complexity of "does a directed graph have <=1 Hamiltonian cycles?" I am studying the complexity classes and I am confused what is the complexity of the following problem: "Does a directed graph G has at most 1 Hamiltonian cycle?"
So, from my knowledge and understanding:

Existence of Hamiltonian cycle is a NP(C) problem.
Existence of exactly $k$ ($k>1$) Hamiltonian cycles in a graph belongs to PSPACE.
The stated problem would be a complement of "Does a directed graph G has at least 2 Hamiltonian cycles?"

However, I still fail to see to which class the mentioned problem belongs. Originally I though it would also belong to PSPACE, but not to any space in PSPACE. However, I have consulted my teacher and she said that, while it belongs to PSPACE, it also belongs to some subset of PSPACE. Which subset that would be? Does it belong to co-NP, and the problem from 3. then belongs to NP? If yes, how to prove it (because for now I'm just guessing it based on my teachers' hint)? If no, where does it belong?

Your problem clearly belongs to $\mathsf{co\text{-}NP}$. An easy "no" certificate consists of 2 distinct Hamiltonian cycles. The certificate can clearly be checked in polynomial-time.
The same certificate is also a "yes" certificate for problem in 3 (i.e., "Does a directed graph G has at least 2 Hamiltonian cycles?"), showing that it belongs to $\mathsf{NP}$.


What kind of growth is $O(0.24\cdot K\cdot 2^w)$ I've calculated the running time of an algorithm I'm interested in to be

$$O(0.24\cdot K\cdot 2^{w})\,,$$

where $K$ and $w$ are both variables.  ($K$ is the number of elements in some set, and $w$ is the log of the largest element, so both are variables.)

What kind of growth does this function have? I'll say it is exponential, however I don't know what the 0.24 implies.

If $K$ is constant and $w$ is variable then $0.24\times K\times 2^w$ and the function is exponential in $w$, therefore it is $O(2^w)$.

If $K$ is variable and $w$ is constant then $0.24\times K\times 2^w$ is $O(K)$ - linear in $K$.

If both $K$  and $w$ are variables then $0.24\times K\times 2^w$ is $O(K2^w)$.

If both $K$  and $w$ are constant then $0.24\times K\times 2^w$ is $O(1)$.

The constant $0.24$ is ignored since it becomes irrelevant when we compare the rate of growth of a function. For more details please see Big-O notation.

We also use $O^*(f(n))$ notation, in particular in analysis of parametrized algorithms, which means that the algorithm runs in
$O(f(n)p(k))$ for some polynomial $p(k)$. So you could also write it is $O^*(2^w)$ in case $w$ is variable.


Finding a pair of non-overlapping bit vectors I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists.

For example, if I give you $[00110, 01100, 11000]$ then the only solution is $\{00110, 11000\}$. Alternatively, the input $[111, 011, 110, 101]$ has no solution. And any list that contains the all-zero bitvector $000...0$ and another element $e$ has a trivial solution $\{e, 000...0\}$.

Here's a slightly harder example, with no solution (each row is a bit vector, the black squares are 1s and the white squares are 0s):

■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

How efficiently can two non-overlapping bitvectors be found, or be shown not to exist?

The naive algorithm, where you just compare every possible pair, is $O(n^2 k)$. Is it possible to do better?

Warmup: random bitvectors

As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random.  Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$).

We'll consider the following two-set variant of the problem:

Given sets $S,T \subseteq \{0,1\}^k$ of bitvectors, determine where there exists a non-overlapping pair $s \in S, t \in T$.

The basic technique to solve this is divide-and-conquer.  Here is a $O(n^{1.6} k)$ time algorithm using divide-and-conquer:

Split $S$ and $T$ based upon the first bit position.  In other words, form $S_0 = \{s \in S : s_0=0\}$, $S_1 = \{s \in S : s_0 = 1\}$, $T_0 = \{t \in T : t_0 = 0\}$, $T_1 = \{t \in T : t_0 = 1\}$.
Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$.  If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

Since all bitvectors are chosen at random, we can expect $|S_b| \approx |S|/2$ and $|T_b| \approx |T|/2$.  Thus, we have three recursive calls, and we've reduced the size of the problem by a factor of two (both sets are reduced in size by a factor of two).  After $\lg \min(|S|,|T|)$ splits, one of the two sets is down to size 1, and the problem can be solved in linear time.  We get a recurrence relation along the lines of $T(n) = 3T(n/2) + O(nk)$, whose solution is $T(n) = O(n^{1.6} k)$.  Accounting for running time more precisely in the two-set case, we see the running time is $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$.

This can be further improved, by noting that if $k \ge 2.5\lg n+100$, then the probability that a non-overlapping pair exists is exponentially small.  In particular, if $x,y$ are two random vectors, the probability that they're non-overlapping is $(3/4)^k$.  If $|S|=|T|=n$, there are $n^2$ such pairs, so by a union bound, the probability a non-overlapping pair exists is at most $n^2 (3/4)^k$.  When $k \ge 2.5 \lg n+100$, this is $\le 1/2^{100}$.  So, as a pre-processing step, if $k \ge 2.5 \lg n + 100$, then we can immediately return "No non-overlapping pair exists" (the probability this is incorrect is negligibly small), otherwise we run the above algorithm.

Thus we achieve a running time of $O(n^{1.6} \min(k, \lg n))$ (or $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$ for the two-set variant proposed above), for the special case where the bitvectors are chosen uniformly at random.

Of course, this is not a worst-case analysis.  Random bitvectors are considerably easier than the worst case -- but let's treat it as a warmup, to get some ideas that perhaps we can apply to the general case.

Lessons from the warmup

We can learn a few lessons from the warmup above.  First, divide-and-conquer (splitting on a bit position) seems helpful.  Second, you want to split on a bit position with as many $1$'s in that position as possible; the more $0$'s there are, the less reduction in subproblem size you get.

Third, this suggests that the problem gets harder as the density of $1$'s gets smaller -- if there are very few $1$'s among the bitvectors (they are mostly $0$'s), the problem looks quite hard, as each split reduces the size of the subproblems a little bit.  So, define the density $\Delta$ to be the fraction of bits that are $1$ (i.e., out of all $nk$ bits), and the density of bit position $i$ to be the fraction of bitvectors that are $1$ at position $i$.

Handling very low density

As a next step, we might wonder what happens if the density is extremely small.  It turns out that if the density in every bit position is smaller than $1/\sqrt{k}$, we're guaranteed that a non-overlapping pair exists: there is a (non-constructive) existence argument showing that some non-overlapping pair must exist.  This doesn't help us find it, but at least we know it exists.

Why is this the case?  Let's say that a pair of bitvectors $x,y$ is covered by bit position $i$ if $x_i=y_i=1$.  Note that every pair of overlapping bitvectors must be covered by some bit position.  Now, if we fix a particular bit position $i$, the number of pairs that can be covered by that bit position is at most $(n \Delta(i))^2 < n^2/k$.  Summing across all $k$ of the bit positions, we find that the total number of pairs that are covered by some bit position is $< n^2$.  This means there must exist some pair that's not covered by any bit position, which implies that this pair is non-overlapping.  So if the density is sufficiently low in every bit position, then a non-overlapping pair surely exists.

However, I'm at a loss to identify a fast algorithm to find such a non-overlapping pair, in these regime, even though one is guaranteed to exist.  I don't immediately see any techniques that would yield a running time that has a sub-quadratic dependence on $n$.  So, this is a nice special case to focus on, if you want to spend some time thinking about this problem.

Towards a general-case algorithm

In the general case, a natural heuristic seems to be: pick the bit position $i$ with the most number of $1$'s (i.e., with the highest density), and split on it.  In other words:

Find a bit position $i$ that maximizes $\Delta(i)$.
Split $S$ and $T$ based upon bit position $i$.  In other words, form $S_0 = \{s \in S : s_i=0\}$, $S_1 = \{s \in S : s_i = 1\}$, $T_0 = \{t \in T : t_i = 0\}$, $T_1 = \{t \in T : t_i = 1\}$.
Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$.  If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

The challenge is to analyze its performance in the worst case.

Let's assume that as a pre-processing step we first compute the density of every bit position.  Also, if $\Delta(i) < 1/\sqrt{k}$ for every $i$, assume that the pre-processing step outputs "An overlapping pair exists" (I realize that this doesn't exhibit an example of an overlapping pair, but let's set that aside as a separate challenge).  All this can be done in $O(nk)$ time.  The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.

What will the running time of this procedure be?  I'm not sure, but here are a few observations that might help.  Each level of recursion reduces the problem size by about $n/\sqrt{k}$ bitvectors (e.g., from $n$ bitvectors to $n-n/\sqrt{k}$ bitvectors).  Therefore, the recursion can only go about $\sqrt{k}$ levels deep.  However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than $3^{\sqrt{k}}$ leaves), so I'm not sure what running time this should lead to.


Is reservoir sampling unnecessary if you know the length of the stream of integers? I think I understand Reservoir Sampling.  If you have a large stream of integers then it allows you to get a sample of size k from that stream without putting it all in memory.
My question is what if you know beforehand the length of the stream?  Say the length of the stream is n.  In this case I would assume that a much simpler way to get a sample of k would be to just generate k random indices between 0 and n beforehand then as you iterate through the stream just select the integers corresponding to the indices you sampled beforehand.  What would be the downside of this? Slower maybe?

There is no particular downside. It's a perfectly valid approach.


Low for EXP and NEXP What are the largest classes which are low for EXP and NEXP?

For example: I am aware the class P, QP are low for EXP as well as NEXP. We also know that NP is not low for either of them.

Is class BPP low for EXP or NEXP? What is the largest oracle class we can provide to EXP (or NEXP) which doesn't increase its power?

$\mathsf{BPP=NEXP}$ is consistent with our current knowledge, thus, since $\mathsf{EXP, NEXP}$ are not low for themselves, it is not known whether $\mathsf{BPP}$ is low for them. A positive answer would imply $\mathsf{BPP\neq NEXP}$, and a negative answer would imply $\mathsf{P\neq BPP}$ (and in turn, that $\mathsf{P\neq NP}$), so currently, if you're looking for unconditional results, you will have no luck with $\mathsf{BPP}$.

Since even a (possibly weak) class as $\mathsf{BPP}$ is not known to be low for $\mathsf{EXP}$, you will need to look between $\mathsf{P}$ and $\mathsf{BPP}$ (which does not give you much wiggle room), or for classes who are currently incomparable with $\mathsf{BPP}$ (such as $\mathsf{QP}$ as you yourself noted, I doubt you can find a significantly stronger low class for EXP).


Proof by contradiction for greedy algorithms I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never been great at proofs, and maybe this will help me get on the track to becoming more comfortable with them.

Consider section 3.2, Analysis.
https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6note.pdf
The algorithm is very intuitive - choose the highest value/weight and only the last item in the knapsack may need be fractional. I don't have any issues with that. Formally proving that this algorithm is the best thing out there I what I have an issue with.

(note proof is available in more detail: https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6.pdf)

The professor shows that our algorithm chooses items p_1...p_n in various amounts. ALG = (p_1, p_2, ... , p_n). So we choose p_1 much of item 1, p_2 much of item2... all the way to p_n. Only the last item in the knapsack could be fractional. All good.

Now we assume that there exists a better algorithm, OPT. We say OPT makes the same choices as ALG up to a certain point OPT(q_1, q_2,...q_n). At some point, q_i, OPT makes a different choice that ALG. Why in the notes does the professor say q_i cannot be p_1. Surely OPT could take a different choice immediately. Anyway, that aside, I agree that OPT, like ALG will be putting as much of the items it can into the knapsack upto i. After i, OPT starts doing something else. The professor doens't talk about this, but maybe OPT changes the ordering of the items it puts into the knapsack - that wouldn't be a big deal as long as it chose all the same items and put the same amount of the very last item ALG put in the knapsack last.

However changing the order of items chosen wouldn't make OPT better, just the same. Right? (professor doesn't talk about this, at least not explicitly). For OPT to be better there must be some item, i it chooses less than ALG did of. And similarly some item j we take more of than ALG did, to keep the capacity the same. Another aside: haven't we made the implicit assumption that we must use all of the capacity, W, to be optimal. Is this self evident or something? Intuitively I can see why, but formally I cannot.

Anyway we remove a little amount from qj and give it to qi, hence those equations involving epsilon. i.e. if we remove e units of weight of j then we can add (e * wj / wi) units of value. Fine.

Now why on earth is this called OPT'. Isn't this still OPT? I'm confused here. Why did we bring OPT' in there? Why do we need yet another modified version of ALG. I thought OPT (not OPT') is where we modified qi and qj by changing how much of each we picked.

Thanks all!

Just think like this. Without loss of generality, assume

$\begin{equation*}
   \dfrac{v_1}{w_1} > \dfrac{v_2}{w_2} > \dotsb > \dfrac{v_n}{w_n}
\end{equation*}$

(item types with same $v_i/w_i$ can be merged, it doesn't matter in the end).

Let ALGs choices be $p_1, p_2, \dotsc, p_n$, OPTs choices be $q_1, q_2, \dotsc, q_n$.

Assume ALG doesn't give an optimal solution, so $\mathbf{p} \ne \mathbf{q}$. As they are different, there is $i$ such that $p_k = q_k$ for $1 \le k \le i$ and $p_i \ne q_i$. By the way ALG works, it adds as much of $i$ as it possibly can, so $p_i > q_i$.  What OPT looses by this against ALG on $i$ is $(p_i - q_i) \cdot v_i / w_i$, and it more than makes up the loss by adding $(p_i - q_i)$ weight of items that are all worth less per weight than $i$. That is impossible.


Read and write ports in a register file? How many read and write ports in a register file? Moreover, what is the difference between a register and a register file?

A "register file" is an aggregation of registers. That is, it is one component that holds several different registers.

How many read/write ports?  Well, this depends. It can be 1 and 1, or more, according to the specific system. If you are the engineer, you can design a register file with as many read and write ports as you desire. The maximal number would probably be the number of registers in the file because there is no point in placing more read/write ports than actual registers (=memory cells).


Demonstrate that DPDA is closed under complement by construction I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I got has something that at the end does not fit. Could you give me a hand?

The main problem happens with the ε-moves. A PDA could finish reading its input in a non-final (rejecting state) but can still move to a final (accepting) state through an ε-move and end up accepting the string. This means that just adding a dead state and complementing the states does not work. I already solved the problem of possible infinite sequences of ε-moves, so that is not a main part of my question.

EDIT: As far as I understand, if the DPDA reaches end of input and is in an accepting state and moves to a rejecting state through an ε-move it would still accept it (as it reached a final state with no input symbol left to read).

Please let me know if I can be more clear.

I didn't have time to write this before but I found an answer. Here is what I did:

Let $O$ be the original $PDA$. We will construct a new $PDA$, call it $M$ ($M$ stands for modified).

To find the complement of $O$, we can flip final states to be non-final states and vice-versa. It is the same procedure as for finite automatas. However, there is a subtlety. The main problem is that in the original PDA $O$ the input $w$ can lead to a state $S$ which is not a final state but could perform an $\epsilon-move$ and get to an accepting state $S'$. Flipping states as mentioned above, would make $M$ end in $S$ with the input $w$ which would be a final state (causing $M$ to accept accept the input) even though it will later make an $\epsilon-move$ to $S'$, a non-accepting state. Therefore, both $O$ and $M$ will accept $w$. Something similar happens if $S$ was a final state and $S'$ a non-final state reachable from $S$ through an $\epsilon-move$.

In order to overcome this problem, we must make sure that all $\epsilon$-moves happen before we read the next symbol. That is, we will enter a reading state only when a path of $\epsilon$-moves is followed and we reach a state which has no $\epsilon$-move available. We call these latter states reading states, as they need an actual symbol to perform a new transition.

Define $M$'s states to be tuples of the form $<q, n>$ where $q \in Q$ ($Q$ is the set of states of the original $PDA$) and $n \in \{1, 2, 3, 4\}$.

If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$ if $q \in F_O$.
If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$ in $M$ if $q \notin F_O$.
If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$.
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$ in $M$
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$ in $M$

In those definitions, we let states of the form $<q, 2>$ and $<q, 3>$ consume $\epsilon$-moves imitating $\epsilon$-moves of $O$ until there are no more. Then, perform an $\epsilon$-move to a reading state. Now for the reading states,

If $\delta(q, a, X) = <q', \alpha>$ in $O$, let $\delta(<q, 1>, a, X) =  \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$ in $M$.

By making this definition, we consume a symbol of the input and move to a state of the form $<q, 3>$ to begin a new series of $\epsilon$-moves.

Finally, make states of the form $<q, 4>$ be accepting states of $M$ if $q \notin F_O$. Also, make $<q_0, 3>$ the initial state of $M$ if $q_0$ is the initial state of $O$.

What we did is the following:

Create 4 "floors" of states (the second element of the tuple in states of $M$ determines in which floor we are). Floor 3 imitates $\epsilon$-moves of $O$ possibly reaching an accepting state $q$ of $O$. If that is the case, we move to floor 2; otherwise, we remain in floor 3. When there are no more $\epsilon$-moves to follow of $O$, we define $\epsilon$-moves of $M$ to reach a reading state. Floors 1 and 4 correspond to reading states. If we were on floor 3, we go to floor 4. If we were in floor 2, we reach floor 1. Only states $<q, 4>$ (states that are in floor 4) are accepting states of $M$, provided that $q$ is not an accepting state of $O$.

Please let me know if I made a typo at writing this. I could've easily mistaken. Also, my English is not very good so feel free to edit and rephrase things better.


Sensitivity and Block sensitivity May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity.

Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function.

Let $[n]=\{1,2,\dots,n\}$.

If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position.

If $B\subseteq [n]$, then $\Bbb 1_B$ be the length $n$ vector with $1$s only in positions marked by $B$.

If  $i\in[n]$ and $x\in\{0,1\}^n$, let $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

If  $B\subseteq [n]$ and $x\in\{0,1\}^n$, let $x^{B}=x\oplus\Bbb 1_B$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Block Sensitivity of $f$ at input $x$, $BS_x(f)$ is maximum $r$ such that there is a set of disjoint subsets $\{B_i\}_{i=1}^r$($\forall i\neq j$, $B_i\cap B_j=\emptyset$) such that  $$\forall j\mbox{, }f(x)\neq f(x^{B_j})$$

Block Sensitivity of $f$ is $$BS(f)=\max_xBS_x(f)$$

It is clear that $S(f)\leq BS(f)$ since we can take size $1$ blocks at coordinates of input $x$ that are modified to achieves $S(f)$.

So why can't I say $BS(f)\leq S(f)$? That is, suppose we found a maximum set of blocks $B_i$ that are disjoint, then cant I say:

There is no other bit position outside of $\cup_{i=1}^rB_i$ where we can change an input in order to change the input (Or else there is a size $1$ block that is disjoint and we can add to list $B_i$ incrasing $r$).
It is clear $S(f) = |\cup_{i=1}^rB_i|$ since if we change all bit positions in $B_i$ we change inputs and there is no other extra bit position by $1$.
Split the $B_i$ in to size $1$ blocks to get $S(f)=BS(f)$?

Am I wrong in the definition that $2$ DOES NOT HOLD since we can only consider $1$ block at a time and hence we can only say $S(f)\geq max_i|B_i|$? Anything else I am missing?

Is there any example for which $BS(f)\leq S(f)^{1+\epsilon}$?

2 does not hold as stated. All you know is that if you flip the all bits in a given block $B_i$, the output flips. Without additional conditions, I don't think you're guaranteed anything about flipping any individual bit within $B_i$.

EDIT: In fact, if $B_1, B_2, \ldots, B_i, \ldots$ represents a maximal set of blocks, then for any $B_i$, there cannot be more than one index within $B_i$ such that flipping the bit at that index will flip the output. Suppose that within $B_i$ there are two indices, say $j$ and $k$, such that flipping either $x_j$ or $x_k$ will flip the output. Then $B_i$ can be replaced by the two singletons $j$ and $k$, thus contradicting the assumption that the set of blocks was maximal.

Meanwhile, the first function found to have a quadratic gap between $BS(f)$ and $S(f)$ is due to Rubinstein (1995). You can find a quick summary of the construction in this blog post by Scott Aaronson. A function with slightly bigger separation was found later by Virza (2011).


P vs NP problem (Student example) Hello dear stackexchangers,

I have a simple question, and I would like to say that I am not a scientist. When I read the problem statement on this link: http://www.claymath.org/millennium-problems/p-vs-np-problem

  Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

I understand the problem, but in order for the finder to prove he solve the problem, if we take 100 students from 400, how many "incompatible" pairs and how many combinations of 100 students without these pairs should be proposed and generated in order to make something really "probing"? In a polynomial way of course.

Because the statement is not really clear about it, in my humble opinion.

Sincerely yours

Formally, this is a special case of the "$k$-independent set problem", and can be stated as follows:

  Given a graph with 400 vertices, can you pick 100 vertices such that no two of them are adjacent?

(A "graph" is a set of vertices (students) and edges (students who are incompatible). Two vertices are "adjacent" if there is an edge between them (they're incompatible).)

You can find easy solutions for some groups of students: for instance, if there are no incompatibilities at all, any choice of 100 students will work. But the difficult problem is solving this in general, coming up with an algorithm that can solve it for any selection of $k$ students from a group of $n$, with a "polynomial runtime" (which basically means it can be solved reasonably quickly even for large values of $n$).

"Proving" that the problem is solved involves a formal mathematical proof, a way of demonstrating that your algorithm works for any group of students, no matter what the incompatibilities are, no matter how many there are, and takes only polynomial time to run.

Examples won't work as a proof, because no matter how many examples you show, it's always possible that your algorithm would fail on the next one you haven't tried.

If you're actually interested in approaching this problem, the formal problem description explains it more thoroughly. (You will need some mathematical background though.)


Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time? The description of this game is already exists in this link

I am quoting from this link the description of the game to ease the reading of this question:

In a game, where there are m active bombs, each one with a number above zero, and n standing levers, where each can be either pushed forward or pulled backward, and each lever is connected to some bombs with green wires/cables and connected to some bombs with red wires/cables.

If any lever is pushed forward then all bombs that are connected to this lever via green wire/cable are defused and all bombs that are connected to this lever via red wire/cable, their number is decremented by 1.

If any lever is pulled backward then all bombs that are connected to this lever via red wire/cable are defused and all bombs that are connected to this lever via green wire/cable, their number is decremented by 1.

A defused bomb cannot explode, but any active bomb that it's number reaches zero explodes immediately.

Only standing levers can be touched (either pushed forward or pulled backward). You shouldn't touch already touched (either pushed forward or pulled backward) levers.

To win/beat the game the purpose is to defuse all the active bombs without exploding any of them.

My greedy algorithm described in this question suppose to run in polynomial time, but it's not proven if it is correct.

Even though proving it's correctness is very difficult for me I am attempting to prove it, but this question isn't about this greedy algorithm at all.

Now this question is more general:

Can deterministic Turing machine beats/wins the game described in this question in polynomial time?

If yes, then there should exist polynomial time algorithm that returns all steps that should be followed to beat/win the given instance of this game (if it is possible).

The deterministic Turing machine or the algorithm doesn't have to be greedy necessarily.

Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time

We reduce 3-SAT to your problem.

We have a lever for each variable and a bomb for each clause, the red cables are connected to clauses/bombs that have positive literals belonging to that variable/lever and the green cables are connected to clauses/bombs that have negative literals belonging to that variable/lever.

Each bomb has the number 3 written on it, meaning that the bomb will explode if it is decremented three times. Whenever we set a lever that is connected to the bomb in the direction that doesn´t deffuse the bomb we decrement the counter in the bomb. This is the same as setting a variable true if the literal in a clause is false or viceversa. If we do this three times that means that the clause has not being satisfied in the original 3-SAT problem and the bomb explodes.

If the instance is satisfiable, you can always choose the right positions for the levers so that no bomb explodes. If there is a variable assignment that satisfies the clauses that means that the bombs can be defused. A defused bomb cannot explode anymore so that we don´t have to worry about a defused bomb anymore.

So, can your problem be solved in polynomial time? We don´t know. People will have to give a solution to the P vs NP problem first, come back in a hundred years and maybe we will have an answer


Structure of a Pumping Lemma proof: contradiction or counterexample? This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact structure of a proof where you show a language is not regular or context-free?

Wikipedia and most proofs start with "Suppose $L$ is a regular language", which would mean it is a proof by contradiction, because it isn't.

But the lemma has the quantifiers $\exists, \forall, \exists, \forall$ in order. And in the proof you assume a given constant given by the first $\exists$, and then you come up with some word (the first $\forall$), format it in some given substring division (the second $\exists$) and again come up with some $k$ (second $\forall$) for which you show it is not in $L$.

This seems to me like a counterexample proof ("this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma"), and not a proof by contradiction?

this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma

You are missing that in order to construct this counterexample you have to assume that $L$ is regular. Then you apply the Pumping lemma, which yields the Pumping length $p$. Only then do you construct your (counter)example string (using $p$!) and show that it contradicts the Pumping lemma. Hence, the assumption must be false.

So while you can say that you derive the contradiction using a counterexample, the outer-most proof is by contradiction.
With the assumption, you wouldn't have $p$!

Note that proofs can be nested, so you don't need to see only one proof technique. For instance, induction proofs often use a proof by contradiction inside the inductive step.


How can $ww = www$ hold for any word $w$? Speaking in terms of automata and regular languages, how would it be possible for a string repeating some $w$ twice equal a string repeating that same $w$ thrice? That is, why is the language

$\qquad L = \{w \in \Sigma^ * \mid ww = www\}$

not empty? The only thing I can think of is $w = abab, ww = abababab, www = abababababab$, but I don't think this is correct.

The only way that $w w = w w w$ is that $w = \epsilon$. Algebra of strings (for mathematician types, the free monoid on $\Sigma$) isn't that different from multiplication...


Regular expression for a language which doesn't look regular I'm trying to find a regular expression for the following language:

$$L=\{x0y : \text{$x$ contains same number of 0's as $y$ contains 1's}\}. $$

The trick is to write $L$ as a different language. Let's consider the following similar language
$$ L' = \{ xy \in \{0,1\}^* : \#_0(x) = \#_1(y) \}, $$
where $\#_0(x)$ is the number of 0's in $x$.

I claim that $L' = (0+1)^*$. Indeed, let $w = w_1\ldots w_n$ be some arbitrary word, and define $\delta_w(i) = \#_0(w_1\ldots w_i) - \#_1(w_{i+1}\ldots w_n)$. The following properties are not hard to check:

$\delta_w(0) \leq 0$.
$\delta_w(n) \geq 0$.
$\delta_w(i+1) = \delta_w(i) + 1$ for $0 \leq i \leq n-1$.

This shows that $\delta_w(i) = 0$ for some $0 \leq i \leq n$, and so $w \in L'$.

Your case is very similar - I'll leave you to figure out the details.


Lower bound for finding kth smallest element using adversary arguments In many texts a lower bound for finding $k$th smallest element is derived making use of arguments using medians. How can I find one using an adversary argument?

Wikipedia says that tournament algorithm runs in $O(n+k\log n)$, and $n - k + \sum_{j = n+2-k}^{n} \lceil{\operatorname{lg}\, j}\rceil$ is given as lower bound.

I am going to briefly outline a sketch of an adversary argument.

Consider your selection algorithm playing against an opponent that we will call the adversary.The aim of the adversary is to provide an input $X$ for your algorithm that maximizes the number of comparison operations done by your algorithm. Indeed, your algorithm can be seen as a comparison tree, in which a path corresponds to a partial order. When the algorithm asks the adversary about a pair $(x, y)$ of elements, the adversary returns either $x < y$ or $y < x$. The adversary answers can never contradict previous outcomes.

Assume that the $k$-th largest element is $x^*$: considering the partial order associated to any leaf of the comparison tree, then $x^*$ must be comparable with every other element in order for the algorithm to be correct, so that the algorithm must have made at least one comparison $(y, z)$ $\forall y \neq x^*$ whose outcome is either $y < z \leq x^*$ or $x^* \leq z < y$. Call such a comparison crucial for an element $y$. Obviously, the adversary wants to maximize the number of non crucial comparisons done by your algorithm.

Let $L$ be the set of $k−1$ largest elements; your algorithm needs to correctly identify all of the elements in $L$ and also the largest element in $X \setminus L$, i.e. $x^*$. Observe that each element in $X \setminus L$ has lost at least one crucial comparison. Now, the adversary has a strategy that forces each of the $k - 1$ elements in $L$ to win at least $\left\lceil {\lg \frac{n}{{k - 1}}} \right\rceil$ comparisons, none of which is crucial for $X \setminus L$. Adding the remaining $n - k$ crucial comparisons for $X \setminus L$ you obtain the lower bound. For details, please read the following, excellent, Jeff Erikson notes.


Undecidability: writing a symbol on Turing Machine's tape I wonder to know if given a Machine $M$, a string $x$ and a symbol $\phi$, would $M$ ever write $\phi$ ?

My approach

Maybe i can show if the problem is undecidable by contradiction using $M$ to prove $\operatorname{HALTING PROBLEM}$, but i'm stuck here. Any hints ?

First take a Arbitrary Turing Machine M and modify it so that on stopping state it will first write a new symbol $\phi$ that it won't write at any other time.

If you can decide that Machine M' will write that symbol then you can decide whether machine M halted.


Two red children in a red-black tree My data structures exam contains the following question:

Which of the statements below about red-black trees is true? (select one or more)

Every path from the root to a leaf has the same amount of red links.
A node never has two red links to his childs.
Using a red-black tree, you can always draw the associated 2-3 tree.
All leafs of a red-black tree are at the same height.

The correct answer is: 2 and 3.
I don't understand why a node can never have two red links to his child. On the image below (from Wikipedia), I can see two red childs at node 25.
Could someone explain this to me?

If 2 and 3 are both true, then the red-black trees you are sudying are not the standard ones, i.e., the ones from wikipedia.

The red nodes are usually assumed to be "satellites" of the black node above. If there is at most one red node attached to a black one that means either one or to keays belong together (with altogether either two or three pointers to their children). That nicely corresponds to a 2-3 tree.

The "usual" red-black trees can have two red children (but no red child to a red node) and correspond to 2-4 trees.


How can maximum number of minimum cuts of a graph be exactly $n \choose 2$? According to my instructor, $n\choose 2$ is the maximum number of minimum cuts we can have on a graph. To prove this, he showed the lower bound using an n-cycle graph. To prove the upper bound, he drew the argument from two facts:

Probability of finding $i^{th}$ min cut $\geq\frac{2}{n(n-1)}=\frac{1}{n\choose 2}$
Event of finding $i^{th}$ min cut is disjoint.

So just adding up the probabilities he proved the upper bound of $n\choose 2$.

Now if we consider a tree, as a graph, with $n$ nodes, then we will be able to conclude $(n-1)$ min cuts which is less than $n\choose 2$ cuts ($ n\geq3)$. Am I missing something here?

"Maximum" here means that no graph can have more than $n \choose 2$ minimum cuts. Obviously, you can come up with graphs (or infinite families of graphs) that have fewer minimum cuts, like say $n-1$. This is less than $n \choose 2$ which is perfectly fine, so this is no contradiction. In other words, the result only means that you can't come up with graphs that have more than the maximum number of minimum cuts.


What course in CS deals with the study of RAM, CPU, Storage? I watched the Crash Course playlist of Computer Science. It was teaching about RAM, CPU, Storage etc but I felt it was way too fast and only people who have studied the course first hand understood it better.
So I wanted to ask what CS couse actually teaches the details of CPU, RAM and how it is build from the scratch with the help of Logic Gates.

The subject you're describing often goes under the names computer architecture, computer systems, computer organization and design, and the like. One example is Elements of computing systems, based on a course From Nand to Tetris originating in the Hebrew University. The Amazon page on the book links to other popular textbooks on the topic.
Generally speaking, this area is at the intersection of computer science and electrical engineering. Some aspects are much closer in spirit to electrical engineering, for example the physics behind memory and storage architectures. Other aspects, such as cache coherence algorithms and error-correcting codes, are more likely to be considered an integral part of both disciplines.


What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array? There is D-dimensional array A. The number D and the size Sd of every dimension d=1..D is input from keyboard. There is also 1-dimensional array E of size N. It consists of unique integer numbers 0..N-1. N is also input from keyboard.

First we need to fill A with elements of E so that every element is presented at least once (see comment on this). Then we need to generate all possible permutations of A. Every unique permutation (transpositions are considered as unique permutations) need to be stored in a file.

Please explain what algorithms/theoretical methods will be helpful here. I need the fastest possible solution (minimum time-complexity). Is there a way of counting the number of all possible permutations first? I will be really grateful for the pseudocode.

Comment: If there are several fillings possible, we need to work with all of them (this happens when N < S1*S2*..*SD). If there is impossible to fill an array (N > S1*S2*..*SD) the error need to be returned.

It is well-known that the number of non-negative integer solutions to $x_1+\dots+x_a = b$ is $\binom{a+b-1}{a-1}$, and the number of positive integer solutions is $\binom{b-1}{a-1}$. To see the latter, notice that a set $1 \leq i_1 < i_2 < \cdots < i_{a-1} \leq b-1$ corresponds to the solution $x_1 = i_1$, $x_2 = i_2 - 1$, ..., $x_{a-1} = i_{a-1} - i_{a-2}$, $x_a = b - i_{a-1}$.

Therefore the number of ways to fill your array is
$$
\binom{S-1}{N-1} \cdot S!, \text{ where } S = S_1 S_2 \cdots S_D.
$$
Indeed, if you sort each filling then you get $x_i$ many $i$'s for $0 \leq i \leq N-1$, where $x_i \geq 1$ and $\sum_i x_i = S$.

You can generate all the fillings by first generating all solutions to $x_0 + \cdots + x_{N-1} = S$ (which you can do recursively, for example, or using an algorithm for generating all subsets of $[S-1]$ of size $[N-1]$, and converting each subset to a solution in the obvious way), filling the array in nondecreasing order accordingly, and then generating all permutations (a well-known problem).


Can anyone give me an instance of 3SAT with exactly one solution? I need an instance of 3SAT with exactly one solution but I cannot think of or find one anywhere. Can anyone please give me an example?

The empty 3SAT instance (over no variables) has one solution.


Is deciding whether the language of a TM contains all strings of length 4 computable? I was going through some Halting Problem reduction and I found the following problem:

  Given a semi-decider TM $M$, does the language $L(M)$ contain all strings of exactly length $4$?

The question later asks to prove whether this is recursive or r.e. Going through some practicing, I came to the conclusion that this is must be r.e., since otherwise such problem would solve the Halting Problem.

So, I attempted this question by showing that $$HP < 4LENGTH$$

My approach is to show that $4LENGTH$ is recursive and then showing the contraddiction, that $HP$ is not recursive, so is $4LENGTH$.

However I can't understand how to construct such machine. Moreover, by looking at some similar proof I see that they suggest to build a machine $M'$ that erases the tape, writes $I$ (input) on the tape and simulate $M$. However, I can't follow such proof.

Can someone describe how to solve such problem or give any direction?

This might help you understand a standard proof technique for such problems. An instance of HP is a pair, $(\langle M\rangle, x)$ where $\langle M\rangle$ is a description of a TM $M$ and $x$ is a string. To reduce HP to 4LENGTH we require a function $f$ that maps instances of HP to instances of 4LENGTH such that $(\langle M\rangle, x)\in HP\Longleftrightarrow f((\langle M\rangle, x))\in 4LENGTH$. In other words, an instance $I = (\langle M\rangle, x)$ will have a "yes" answer ($M$ halts on $x$) if and only if the transformed instance will have a "yes" answer ($f(I)$ accepts all strings of length 4).

Given $(\langle M\rangle, x)$, we'll define a TM $M'$, using $M$ and $x$, that acts as follows:

M'(y) =
   if |y| = 4
      erase y
      write x on the tape
      simulate M
      return accept

Now if $(\langle M\rangle, x)\in HP$, then $M$ will halt on $x$ and so $M'$ will accept any string of length 4, so $M'\in 4LENGTH$.

On the other hand, if $(\langle M\rangle, x)\notin HP$, then $M$ will never halt on $x$ and so $M'$ will never get to the return accept statement and so will accept nothing. Hence if $(\langle M\rangle, x)\notin HP$, then $M'\notin4LENGTH$.

To summarize, we have established a faithful mapping from instances of HP to instances of 4LENGTH.

Now to show that 4LENGTH is not recursive, we argue by contradiction. Suppose that 4LENGTH were recursive. Then there would be a decider, $D_4$, for 4LENGTH namely, given any TM description $\langle N \rangle$, $D_4$ would take that description as input and halt and either return "yes" if $\langle N \rangle\in 4LENGTH$ and "no" if $\langle N \rangle\notin 4LENGTH$.

We can then use $f$ and $D_4$ to build a decider for HP. It would work like this:

Given an instance $I=(\langle M\rangle, x)$ of HP, use $f$ to produce an instance $f(I)=\langle N\rangle$ of 4LENGTH.
Run the decider $D_4$ on $f(I)$.
If $D_4$ answers "yes" to $f(I)$, then by the construction of $f$, $I$ must have been in HP. Similarly, if $D_4$ answers "no", $I$ must not have been in HP. In short, we've built a decider for HP, contradicting the fact that HP is not recursive.


Prove that Hitting Set is NP-Complete The Hitting Set Problem (HS) is defined as follow. Let $(C,k$)

$C = \{ S_1, S_2, ..., S_m \}$ collection of subset of S i.e. $ S_i \subseteq S , \forall i$
$k \in \mathbb{N}$

We want to know if exists ${S}' \subset S$ where $|{S}'| < k$ such that $S_i \cap S' \neq \emptyset $, $i = 1,2,...,m.$

Prove that HS is Np-Complete.

Hint: When $|S_i| = 2$, HS becomes Vertex Cover, already know to be NP-complete.

3SAT is reduced to the Hitting Set problem. Given a 3SAT $\phi$ having $m$ clauses and $n$ variables, define

$$S = \{ x_1, \dots x_n, \overline{x_1}, \dots , \overline{x_n}\}$$
$$S_i=\{y_1, y_2, y_3\}, \text{ if } y_1,y_2,y_3 \in S \text { and } (y_1 \lor y_2 \lor y_3) \text{ is a clause.} $$
$$S_x=\{x, \overline{x}\}, \text{ for all variable } x.$$
$$k=n$$

Assume $\phi$ is satisfiable, then there a is true-value assignment for $n$ variables. So, add $x$ to $S'$ if $x=true$, otherwise add $\overline{x}$ to $S'$.

Now, assume the HS problem has a solution $S'$. Then since for every variable $x$, $S' \cap S_x \neq \emptyset$, $S'$ has at least $n$ literals of the form $x$ or $\overline{x}$ for each variable $x$. Furthermore, no $x$ and $\overline{x}$ may belong to $S'$ at the same time since the size of $S'$ is at most $n$. Also, for each clause $C_i$, $S' \cap S_i \neq \emptyset$ and so for each clause we select $y_i\in S' \cap S_i$, and set $x=true$ if $y_i=x$ and $x=false$ if $y_i=\overline{x}$.


To detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices? Given two lists of non directional graph edges e.g.
 [(1,3),(3,5),(5,1),(5,7)] [(4,5),(2,3),(3,4),(4,2)]
In order to check if the two graphs are isomorphic is it enough to count the vertices with the same degree between them?

e.g. Vertice   1: 2    1: 0
               2: 0    2: 2
               3: 2    3: 2
             4,6: 0    4: 3
               5: 3    5: 1
               7: 1    6,7: 0

So in our example: both graphs have 2 vertices with 2 edges 1 with 3, one with one and 3 with 0

No. If two graphs have different degree sequences, they are definitely not isomorphic, so the algorithm "half-works". But consider a six cycle versus two three-cycles. Both graphs have six vertices, all of degree two; they are not isomorphic.  Indeed, this counterexample shows that nothing based solely on degrees can work.


Which of the following languages is accepted by this Pushdown Automaton? This is a question from a past paper. I am struggling to get my head around the concept of a PDA. I understand that it is a Finite Automaton with a stack but am stuck as far as answering questions like this one. Thanks.

I think the answer is a, $\{a^n b^{2n} | n > 0\}$.

First, the machine pushes $a$'s onto the stack until the first $b$. Then, for every two $b$'s in the string, it pops off one $a$. Then, if the machine is at the end of the string and the stack is empty, it accepts.

If the stack of $a$'s runs out while the machine is still popping pairs of $b$'s or there are $a$'s left in the stack when the last $b$ is popped, then the machine rejects.

  I am struggling to get my head around the concept of a PDA.

Notation varies, but in the diagram you provided, I think nop means "read the thing on top of the stack and leave it there" and pop means "read and remove the thing on top of the stack".

For more info, you could read the chapter on PDA's in Michael Sipser's book Introduction to the Theory of Computation.


Given a set C of set P of sets R, find the smallest set S such that at least one subset R from each P is a subset of S Given a universal set of elements $\mathbf{U} = \{a_1, a_2, .., a_n\}$, a set $\mathbf{R} = \{a_i\} \subset \mathbf{U}$ where $i ϵ \{1, .., n\}$, a set $\mathbf{P} = \{R_1, .., R_m\}$ and a set $\mathbf{C} = \{P_1, P_2, .., P_l\}$, how do I go about finding a set $\mathbf{S} = \{a_1, .., a_n\} \subset \mathbf{U}$ such that at least one set $\mathbf{R}$ from each  $\mathbf{P}$  is satisfied and such that the size of $\mathbf{S}$ minimal?  I consider the set $\mathbf{R}$ to be satisfied by $\mathbf{S}$ if $\mathbf{R} \subseteq \mathbf{S}$.

This seems similar to set cover problem, but I am not sure how I can approach this.

Your problem is NP-hard, by reduction from Monotone SAT.

Recall that Monotone SAT is (the decision version of) the following problem: given a CNF formula $\varphi$, find a satisfying assignment with the fewest variables set to true.

Now, map each clause, say $x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}$, in $\varphi$ to a set $P=\{R_1,R_2,\dots,R_k\}$ where $R_1=\{x_{i_1}\}$, $R_2=\{x_{i_2}\}$, etc.  Finally, form $C$ to be the set of $P$'s obtained in this way from the clauses of $\varphi$.  Then a set $S$ satisfies $C$ iff it corresponds to a satisfying assignment for $\varphi$ (including the element $x_i \in S$ corresponds to setting $x_i$ to true in the assignment), so the minimal-size set $S$ that satisfies C corresponds to the minimal-size satisfying assignment for $\varphi$.

Since Monotone SAT is NP-hard, your problem is NP-hard, too.

If you need to try to find an exact solution in practice, you could try formulating your problem as an instance of SAT and feed it to a SAT solver (using binary search over the size of $S$), or you could formulate it as an instance of integer linear programming and feed it to an ILP solver.


Rearrange a sequence of real numbers to satisfy polynomial inequalities Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$).
Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$, such that for all $i\leq n-k$
$$ f(a_{\pi(i)},a_{\pi(i+1)},\ldots,a_{\pi(i+k-1)}) \geq 0$$

How hard is this problem?

Let's assume that the numbers $a_1,\ldots,a_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs).

Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. Pick the first $n$ primes larger than $7$, $p_1,\ldots,p_n$. We construct the following sequence $\mathbf{a}$:

For each edge $(i,j)$, the numbers $p_i,p_j,p_{ij}$
For each vertex $i$, the numbers $p_i,p_i^3$
$m$ copies of $3$
$n-m$ copies of $5$
$9n/2$ copies of $2$
$11$ copies of $7$

Note that some numbers appear more than once. The intended solution sequence consists of eleven copies of $7$ followed by $n$ segments of length $12$ of the following two forms:
either
$$ 5,p_i,p_i^3,2,2,2,2,2,2,2,2,2 $$
where $1 \leq i \leq n$, or
$$ 3,p_i,p_i^3,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3 $$
where $1 \leq i \leq n$ and for $\alpha \in \{1,2,3\}$,
$$ x_\alpha,y_\alpha,z_\alpha = 2,2,2 \quad \text{or} \quad p_i, p_ip_j, p_j \text{ for some edge } (i,j).$$
A sequence of that form encodes a vertex cover given by the vertices appearing in the second position in segments of the second form. It should be clear that such a sequence exists if and only if a vertex cover exists. It remains to show how we can test that a sequence is of that form using a single polynomial $f$ which is "run" on all chunks of length $12$.

We let $f = -f'$, where the function $f'(u,v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3)$ is a non-negative function which attains zero on exactly inputs of the following forms:

$3 \in \{v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3\}$
$5 \in \{v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3\}$
$u = 5$, $w=v^3$ and $x_1=y_1=z_1=x_2=y_2=z_2=x_3=y_3=z_3=2$
$u = 3$, $w=v^3$ and for each $\alpha \in \{1,2,3\}$, either $x_\alpha=y_\alpha=z_\alpha=2$ or $x_\alpha=v$ and $y_\alpha=x_\alpha z_\alpha$

This polynomial can be constructed using the following three rules:

A condition $I = J$ is represented by $(I - J)^2$
Given two non-negative polynomials for the conditions $C_1,C_2$, the condition $C_1 \lor C_2$ is represented by $C_1 C_2$
Given two non-negative polynomials for the conditions $C_1,C_2$, the condition $C_1 \land C_2$ is represented by $C_1 + C_2$

Let $\mathbf{b}$ be any permutation of $\mathbf{a}$ for which your condition holds. Since $f'$ is non-negative, it must be that one of the above conditions holds for each segment of length $12$. In particular, any segment of length $12$ must contain $3$ or $5$ somewhere. Considering the number of these compared to the length of the sequence, we see that its general form is: eleven arbitrary elements followed by $n$ segments starting with $3$ or $5$. Each segment starting with $5$ is of the form
$$ 5,q,q^3,2,2,2,2,2,2,2,2,2. $$
We conclude that $q = p_i$ for some $1 \leq i \leq n$. Each segment starting with $3$ is of the form
$$ 3,q,q^3,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3. $$
As before, $q = p_i$ for some $1 \leq i \leq n$. Furthermore, for each $\alpha \in \{1,2,3\}$, either $x_\alpha = y_\alpha = z_\alpha = 2$ or $x_\alpha = p_i$ and $y_\alpha = p_i z_\alpha$. In the latter case we conclude that $z_\alpha = p_j$ and $y_\alpha = p_ip_j$ for some edge $(i,j)$.

In both cases, none of the elements in the segments are equal to $7$, and we conclude that the first eleven elements in the sequence must be $7$. Let $S$ be the set of $i$ such that there is a segment of the form $3,p_i,\ldots$. Since there are exactly $m$ copies of $3$, $|S| = m$. For every edge $(i,j)$, the number $p_{ij}$ appears somewhere, and the only legal place is a $3$-segment. We conclude that $S$ is a vertex cover of length $m$.

This shows that if your condition holds then the graph has a vertex cover of size $m$. Conversely, if the graph has a vertex cover of size $m$ then we can construct a sequence satisfying your condition by assigning each edge to one of the vertices covering it. This proves the validity of the reduction. The reduction is also polynomial time (note that the primes $p_1,\ldots,p_n$ can be found using brute force), showing that your problem is NP-hard, and so NP-complete.


Generating 3SAT circuit for Integer factorization example I read somewhere that 3SAT can be used to solve Integer Factorization.

If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given the number 6, then the factors are 2 and 3.

First we reduce the task of factorization to finding any factor of $n$ (or showing that it's prime). Once we know how to do this, we divide $n$ by such an factor and repeat the process until all factors are broken down to primes, and this takes $O(\log n)$ steps.

Let $k=\lceil\log_2 n\rceil$ the number of bits in $n$.

Next, we design a binary multiplication circuit that accepts two $k$-bit numbers and produces $2k$-bit results. The size of the circuit is obviously polynomial in $k$.

To the output of the circuit we add a $2k$-bit comparator that returns true if the result is equal to $n$ and false otherwise. We also add comparators to the inputs that check that the inputs are $>1$. So the combined circuit takes two $k$-bit numbers and returns true if they're both $>1$ and their product is equal to $n$.

Such a circuit can be described by a propositional formula, so this way we convert it to SAT.

Finally, we convert it from SAT to 3-SAT by a standard procedure. The result will be a 3-SAT formula with $2k$ propositional variables. If it is satisfiable, the propositional variables will just encode two factors of $n$. If it's unsatisfiable it means that $n$ is prime.


The language of any constant-time Turing machine is regular Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular.

This seems to be a pretty well-known fact, but despite my research, I cannot seem to find a proof of this anywhere. Does someone know of one?

Hint: If the machine runs in time $t$ on all inputs then its decision only depends on the first $t$ symbols of the input.


Can Nondet Rabin Tree automaton be determinized? In other words, are they equally powerful?

(for word automata the answer is "yes"; this question is about tree automata).

(i am talking about tree automata that work on $in$finite trees)

The answer is no, nondeterministic Rabin automata are more expressive than deterministic ones.

As an example, consider the language of $\{a,b\}$-labeled binary trees that contain at least one $b$.

It's easy to construct a two-state Büchi tree automaton for this language (and hence a Rabin automaton), but there is no deterministic equivalent.

You can look at Lemma 6.1 here, for a start.


Counting number of permutations respecting partial order Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ represent $A_i < A_j$ and $A_i \geq A_j$ respectively.

Is there an efficient algorithm that counts the number of partitions of $A$ that respect the partial order? E.g. for the all-zero matrix (totally undefined partial order) it's simply $n!$ and for a matrix  containing a total order it's simply $1$.

We can assume that the partial order does not contain contradictions, e.g. we won't have $A_i < A_i$ or some chain of comparisons that violates transitivity.

Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.


Why does computer have branch and jump instructions I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist.
I am asking what theory or purpose for implementing branch and jump instructions is there?
I've tried to get rid of branch and jump instructions and what effect it will cause on the computation, but I could not get the result.

Theoretically speaking you do not need any branch and jump instructions. This is so because you can encode them into artihmetic. For instance, instead of writing

if p:
   x = a
else:
   x = b

you can write (assuming that $0$ stands for "false" and $1$ for "true"):

x = p * a + (1 - p) * b

Gödel was the first to have realized that when he proved his incompleteness theorem, namely that arithmetic sufficies for all of programming, theoretically speaking. So in this sense you are correct.

Supplemental: we do need some sort of iteration or recursion, as was noted in the comments. By "arithmetic" here I mean general recursive functions which have recursion built in. There is a form of "conditional" in recursion, namely the distinction between zero and a successor.

However, it is impractical to insist that arithmetic is somehow the most important thing. There are many different ways to do computation. For instance, we do not even need any arithmetic or recursion, we could use just pure $\lambda$-calculus, which is a pure theory of functions, without any numbers, booleans, or any other form of data (they can all be built up). Which paticular form of computation should be used actually depends on many factors: What does the hardware support? What makes programming most maintainable? How do we make programs efficient? And so on. The actual programming languages and CPUs that we know today are the result of many years of experience. It's turned out that it's better to have conditional branching than not.


Network density vs connectivity I was reading this paper where they mention about undirected networks:

  "The total connectivity of a network is defined as
  $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total
  number of nodes."

However, this is just another way of talking about network density is it not? You could just change the denominator and refer to network density for directed and undirected networks.

Or is this "total connectivity" anything different than density?

Yes, $C$ here is the density of (simple) directed graphs. You can see the Wikipedia entry on dense graphs for more details. In this context, total connectivity is just another name for density.


Best case analysis for Shell sort The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my own derivation or one copied from an authoritative source.

I have elaborated upon the same below. Could you let me know if the reasoning is right here?

The least number of comparisons occur when the data is completely sorted.
For a particular value of the increment, say, $h_i$, each of the $h_i$ sub-sequences require at most one less comparison than the number of elements in the sub-sequence(as insertion sort is used) which is,${N \over h_i} - 1$ ,where N is the total number of data items.
For the given data in this situation $h_i \times \left (N \over h_i - 1 \right ) = N - h_i$ number of comparisons are needed as there are $h_i$ sub-sequences.
If the increment sequence selected is has $k$ increments(such that $h_k = 1$), the total number of comparisons required would be $C(N) \ge (N - h_i) + (N - h_2) + ... + (N - h_k) = kN - \sum h_i = O(N)$

The best case for Shell sort is when the array is already sorted.
In that case the inner loop does not need to any work and a simple comparison will be sufficient to skip the inner sort loop.

A best case of $Θ(N)$ is reached by using a constant number of increments.
But the problem is that the best value for the gapping depends on the input. Therefore you cannot choose a single best value for the gap and must suffer a $log^2(N)$ delay due to repeated compares.

So you are almost correct. Obviously there is no way to compare fewer than N-1 elements before we can conclude that the array is already sorted, so $Θ(N\space log^2(N) )$ it is.

Note that this best case is for randomized Shell sort which is subtly different from the original.

See: https://arxiv.org/pdf/0909.1037.pdf

All this means that Shell sort is not a particularly good algorithm for a (nearly) sorted array. The gapping introduces redundant compares whereas other sorting algorithms only have to go over the array once in the best case.
When the array is random, the gapping works in your favor, and these other algorithms that perform so wonderfully on a (nearly) sorted array perform at a dismal $O(N^2)$


Fastest Algo to separate the 0s and 1s Suppose, I have an array of length 100.
I have 0s at some positions and 1s at some other positions.
What is the fastest method by which I can separate the 0s and 1s, so that we get all the 0s at the beginning and all the 1s at the remaining positions / vice-versa?

i=0, j=size(ar)-1;
while(true)
   increase i to position of first 1;
   decrease j to position of first 0;
   if(i>=j) break;
   ar[i]=0, ar[j]=1;


Best (Fastest) Arithmetic Algorithms What are the best arithmetic algorithms out there (addition, subtraction, multiplication, division, power, root)?

I am looking for algorithms that could be easily extended to multiprecision and arbitrary precision settings.

The concept of a "best" algorithm is not as simple as you'd expect. It depends on at least two more parameters: the machine model and the numbers involved (i.e., how large are the numbers being operated on). For a thorough discussion of this as regards integer multiplication, see Fürer's paper How Fast Can We Multiply Large Integers on an Actual Computer?

There is a wikipedia page devoted to the computational complexity of mathematical operations, including everything you mention. However, from a practical point of view, I would rather look at the source code of a strong library for multiprecision arithmetic like GMP. Such a library is optimized for fastest performance on actual computers. The source code of GMP is readily available, and you can peek under the hood.


Numbering of vertices in RAM model I have read few research papers in which given a graph $G$ where $V$ denotes its vertex set and $E$ denotes its edge set. Model of computation is word RAM. "Without loss of generality assume that vertices are numbered from $1$ to $n$"

Question : How to justify the above mentioned assumption? I am not getting why this assumption is valid?

Typically, graph problems don't depend on the "names" of the vertices. Finding a route from Paris to Berlin doesn't get any easier or harder if you rename the cities Sirap and Nilreb, or 6 and 32, or anything else.  Indeed, in many cases, the vertices of the graph don't even have explicit names: they're just a set.  Since changing the names of the vertices makes no difference, an algorithm doesn't become less powerful by assuming that the names are $1, \dots, n$, where $n$ is the total number of vertices. That is, there is no loss of generality in doing this.

$1, \dots, n$ is a useful choice of names because computers are good at dealing with numbers and because, typically, the vertices will be stored in some kind of array anyway (an array of adjacency lists or just an adjacency matrix).  It makes sense to name the vertex after the array cell it occupies, so that the algorithm never has to worry about the distinction between "vertex $x$" and "the place where vertex $x$ is stored".


DFA which accepts all strings starting and ending with 'aa' I have to construct a DFA which accepts set of all strings over {a,b} which start and end with 'aa'.
I have constructed the following DFA, but it does not accept 'aa' and 'aaa'. How can I make it accept all strings in the language.

One solution could be putting the final state right after the first two states.
From there, if an $a$ is read you stay in the final state, otherwise you move to a state analogous to $q_2$; from there, with two $a$s you return to the final state and with a $b$ you go back to $q_2$.

In short, just picture ($q_1, a$) going to $q_4$ instead of $q_2$. The rest should go unchanged.

This way, the automata should accept strings such as 'aa', 'aaa' and so on. And of course if it reads a 'b' it'll need two more 'a's to return to the final state.


Maximize length of side of triangle from points on a circle Given a circle with $n$ points, among all triangles we can make using these points, we want to find a triangle with maximum length of its shortest side in $o(n^2)$.
We try to make a relation between this problem and convex hull but we can't. Any help be appreciated.

You could transform the question into finding the biggest minimum angle of the triangle vertices relative to the centre.
Preparatory work:

Find centre $(x_C, y_C)$, if not already known (intersect bisectors of randomly-chosen pairs of points). $o(1)$

a) Make list of angle position for each point, $a_i = \text{atan2}(y_i-y_C, x_i-x_C)$. $o(n)$
b) Sort angle list. $o(n \log n)$

Main determination:

In succession for each point:
a)  find points closest to $\pm 120^\circ$ points  from the list, $o(\log n)$ per point
b) record max minimum angle with this point, update overall maximum if needed. $o(1)$ per point

Post process

Convert angle back into distance (either directly or by retrieving the indices of the appropriate points). $o(1)$

Explaining #3 a little more: you should find four points from the two binary searches, one either side of the $+120^\circ$ & $-120^\circ$ points. That gives you four triangles to examine for angles (differences), composed of the base point plus choices from left/right of each of the $\pm 120^\circ$ lines.  (If any of the points are the same (few/crowded points) , there will be fewer triangles to check).

For convenience you might add extra copies of the points either side of the wraparound $0^\circ=360^\circ$ to avoid special cases in the search - eg. duplicate the point at (say) $+358^\circ$ to also be seen at $-2^\circ$.


A,B decidable: proof that A\B is decidable too For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too.

My idea is as follows:
If B is empty or doesnt have elements in common with A, then A\B is decidable because A\B=A.

If B is not empty and intersects with A, A\B is just a smaller subset of A and therefore decidable.

I have a feeling that this is either the wrong idea or not formalized enough.
I would really appreciate any hints regarding that.

EDIT:
A subset of a decidable language is NOT always decidable too, this was a misconception.

Thanks in advance

Let $M_A$ and $M_B$ be deciders for $A$ and $B$ respectively. You can construct a TM $M$,

$M$ = "On input x,

$\qquad$ 1. Simulate $M_A$ on x.

$\qquad$ 2. Reject if $M_A$ rejects. Else simulate $M_B$ on x.

$\qquad$ 3. Accept if $M_B$ rejects. Else reject."

$Correctness$:

$\qquad$ $M$ always halts as $M_A$ and $M_B$ always halts. $M$ accepts if $M_A$ accepts and $M_B$ rejects i.e, $x \in A$ and $x \notin B$. $M$ rejects otherwise.


Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$?

I'm sorry I can't give any approach of what I did, but it's because I don't even know where to start with this ex. in particular. I tried to search anything on my books, but couldn't find nothing at all. Any suggestion is welcome.

The idea behind the construction is very simple: when the number of $a$'s and $b$'s read so far is equal, the stack will contain $\bot$. When $k$ more $a$'s were read, the stack will contain $\bot A^k$. When $\ell$ more $b$'s were read, it will contain $\bot B^\ell$.

Our automaton will accept by clearing the stack. We assume that the stack is initialized with $\bot$. The automaton has a single state and the following transitions:

When reading $a$ and the top of the stack is $\bot$, replace it with $\bot A$.
When reading $a$ and the top of the stack is $A$, replace it with $AA$.
When reading $a$ and the top of the stack is $B$, replace it with $\epsilon$.
When reading $b$ and the top of the stack is $\bot$, replace it with $\bot B$.
When reading $b$ and the top of the stack is $B$, replace it with $BB$.
When reading $b$ and the top of the stack is $A$, replace it with $\epsilon$.
There is an $\epsilon$ transition which, when the top of the stack is $\bot$, replaces it with $\epsilon$.

The final transition is used when the input is exhausted, to conform with the acceptance condition of emptying the stack. If we want to use acceptance by final state, we need to add a new state which will be the only final state, and modify the last transition by transitioning into this state.


Greedy Heuristic for the Traveling Salesperson Problem We're studying Heuristic in my Theoretical CS class, more specifically Greedy-Algorithms for the Traveling Salesperson Problem. The first one is the "next neighbor heuristic", where you start at any given point and connect it with the nearest point and then connect that to the next nearest one until all points are covered - then going back to the first point.

Where "P" is the starting and ending point.

The second approach, which gives the optimal answer, is the "closest pair of points" or "Engstes-Paar-Heuristic". I don't understand how this approach works because from the looks of it, you simply make a straight line but I don't understand this approach.

Sorry about the possible name changes, it's originally in German.

First let's name your points $P_A$, $P_B$, $P$, $P_C$, and $P_D$ (from left to right).

With the first heuristic you start at one point ($P$) and move to the closest point. From that new point, you move to the next closest point, and so on and so forth.

With the second heuristic you again start at one point ($P$) but you move to the point closest to one of the two ends of your current path. It is a simple improvement over the first heuristic.

For your example:

Current path: $P$. Closest point to $P$: $P_B$.
Current path: $P-P_B$. Closest point to $P$ or $P_B$: $P_C$.
Current path: $P_B-P-P_C$. Closest point to $P_B$ or $P_C$: $P_A$.
Current path: $P_A-P_B-P-P_C$. Closest point to $P_A$ or $P_C$: $P_D$.
Current path: $P_A-P_B-P-P_C-P_D$. The only choice left is to connect $P_A$ to $P_D$.


Going deeper with pseudo-polynomial time algorithm for set partitioning If I have a set of (edit) positive integers, and I'm sure that the pseudo-polynomial time algorithm for partitioning the problem will not give me an answer - what would I do next?
To illustrate this problem let's take a look at this example: {100,1,2,3}.
The p-p algorithm will give an answer False, and then I can end with result: This set can be partitioned into two set with difference 100-6 = 94
(The 6 is the last result from p-p algorithm on with [_][vector.size()] = True, the 106 is the sum of all digits).
But what if I really would like to know the maximum by sum two-split of this set in which every subset has the same sum - for example the result that I'm looking for should be 3. This set - {100,1,2,3} can be split (by bypassing the 100) into two subset with the same sum - {1,2} and {3}.
How can I achieve this result?

You can extend the dynamic programming algorithm to handle this variant. Suppose that the weights are $w_1,\ldots,w_n$. You are looking for a vector $x \in \{0,\pm 1\}^n$ such that $\sum_{i=1}^n x_i w_i = 0$, and $\sum_{i=1}^n |x_i| w_i$ is as large as possible. This suggests two possible approaches. The first approach is to construct a large table keeping track of all possible pairs of values $(\sum_{i=1}^m x_i w_i, \sum_{i=1}^m |x_i| w_i)$, where $x_1,\ldots,x_m \in \{0,\pm 1\}^m$. This leads to an $O(nM^2)$ algorithm, compared to the $O(nM)$ subset-sum or partition algorithms.

The second approach is to explicitly list all vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$ (using dynamic programming), and choose the one maximizing $\sum_{i=1}^n |x_i| w_i$. This takes time $O(nM + nS)$, where $S$ is the number of vectors $x$ such that $\sum_{i=1}^n x_i w_i = 0$. In practice $S$ might be small enough for this approach to be practical.


Express a "complex" IF-Statement to Linear Programming In our current project we need to model the following if-statement in linear programming:

If T1 < b < T2 then z = s else z = 0

where T1 and T2 are two integer values (e.g. T1 = 10 and T2 = 100) and s is also an integer value (e.g. 5).

We already know how to model a simpler if-statement with for example A > 0 but we can not figure out how to model an if-statement with a condition t1 < b < t2.

Can someone help us?

Here is a little more detailed explanation of the problem:

In our problem we have several different ranges, each range with a lower and an upper bound, and for each of these steps we have to multiply another value to a variable (lets call this variable k and the result of this multiplication z). For example we have the following range and if-statements:

Ranges:
0   - 10 : 0
11  - 100: 9
101 - 200: 8.5
201 - 300: 8

IF-Statements
if 0   < b < 10  then z = k * 0
if 11  < b < 100 then z = k * 9
if 101 < b < 200 then z = k * 8.5
if 201 < b < 300 then z = k * 8

The lower and the upper bounds as well as the multiplication values are constants and known upfront. The rest (i.e. b, z, k) are integer variables for which we don't know the exact upper bound (lower bound is 0), but we know that they will not get too big. So, we are able to define M values for the M technique.

We already figured out how to do an if-statement like the following (T1 and T2 are the thresholds of the ranges from above, e.g. T1=0 & T2=10):

if T1 < b then z = k * something

and

if b < T2 then z = k * something

For this we transform T1 < b to 0 < b - T1 and b < T2 to 0 < T2 - b and then we use the way described here.

But we are stuck at how we can do the:

0 < b - T1 && b < T2 to 0 < T2 - b

The whole problem is a mixed integer linear programming problem, because we have also boolean decision variables and integer values like for example b.

You can solve this by introducing some temporary variables ($t,u,v$) and applying the big-M method.

For each expression L <= b <= U, we'll introduce 0-or-1 variables $t,u,v$, with the intent that $u=1$ if and only if $L \le b$ holds, $v=1$ if and only if $b \le U$ holds, and $t=1$ if and only if $L \le b \le U$ holds.  We'll enforce this with the inequalities

$$L \le b + M(1-u), L > b - Mu, b \le U + M(1-v), b > U - Mv, 0 \le u+v - 2t \le 1,$$

where $M$ is a sufficiently large constant (you can take it to be at least the largest possible value of $b$, and at least $L$ and at least $U$).  How does this work?  The first two inequalities define $u$ so that $u=1 \Leftrightarrow (L \le b)$ using the technique from Boolean variable true iff equation is satisfied in ILP.  The next two inequalities define $v$, similarly.  The last inequality ensures that $t$ is the logical-AND of $u$ and $v$, using the technique from https://cs.stackexchange.com/a/43884/755.

Now, we'll enforce the constraint if t=1 then z = k*c for some constant c.  We can enforce this using the inequalities

$$ck - M(1-t) \le z \le ck + M(1-t)$$

where $M$ is a sufficiently large constant (in particular, it needs to be at least $c$ times the largest possible value of $k$, and at least the largest possible value of $z$).  Why does this do what we want?  The argument is similar.  If $t=1$, then the inequality is equivalent to $ck \le z \le ck$, which implies $ck=z$; if $t=0$, the inequality is equivalent to $ck-M \le z \le ck+M$, which imposes no restrictions on $z$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for more techniques for handling other sorts of inequalities.


Proving a language as undecidable without using reductions Let's say our Σ is 0 and 1. I want to disprove the following:

  There can be Turing Machines that accept only 1's, i.e. 1, 11, 111,
  etc. Therefore, all languages that have strings of 1's are
  recognizable.

My first step to proving this is by providing a language such as $One$, that accepts only if $w$ contains only $1$'s. There is a theorem that stated that $One$ is decidable iff $One$ and $\overline{One}$ are recognizable.

So, if I were to prove either one of them as unrecognizable, then I should be good. $\overline{One}$ I'll define as the set that doesn't contain 1 in it (i.e. episolon, 0, 00, etc). Creating a turing machine that simply goes right and accepts if we reach end without hitting a one, rejects if we do hit a one seems to work for this case. Could a language be created that isn't recognizable?

It isn't recognizable because it is infinite, therefore it'll loop infinitely. Does this work?

No, because that claim is false. And your writing isn't at all clear, here. Recognizability is a property of languages, so your first two "it"s must refer to languages; but "loops infinitely" is a property of Turing machines, so your third "it" must be one of those.

Ultimately, though, your whole approach is doomed because the languages you call $One$ and $\overline{One}$ are both decidable. You can easily see that $One$ is decidabe just by designing a Turing machine that decides it.


Show that Knapsack-like problem on directed graph is NP-hard Let $G=(V,A)$ represent a directed acyclic graph, where a value $v_i \ge 0$ is assigned to every vertex $u_i$. Let $T$ represent a threshold and $N = |V|$. Problem statement:

maximize: $\sum_{i=1}^{N}v_i x_i$

subject to: $\sum_{i=1}^{N} x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

and $x_i(x_j-1) = 0 \quad \forall a\in A: u_i \to u_j$

In other words, we want to choose up to $T$ vertices that maximize the sum of their values, with the restriction that if a vertex $u_i$ is chosen, any reachable vertices $u_j$ must also be chosen. Therefore, $x_i(x_j-1) = 0$ for a given arc $u_i \to u_j$ represents that if $u_i$ is chosen ($x_i = 1$) then $u_j$ must be chosen as well ($x_j = 1$).

I want to prove that this is a NP-hard problem. To do that, I have taken the 0-1 knapsack problem, which is NP-hard:

maximize: $\sum_{i=1}^{M}v_i x_i$

subject to: $\sum_{i=1}^{M} w_i x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

The 0-1 knapsack may be reduced to an instance of the original problem. Assume an instance of the original problem, with the following properties of $G$:

$v_i = 0$ for every vertex $u_i$ with incoming arcs.
All vertices have at most 1 incoming arc.

The 0-1 knapsack may be reduced to this instance by the following polynomial transformation:

There are $M$ items, where $M$ is the number of vertices $u_i \in G: v_i > 0$.
The value $v_i$ of each item the value $v_i$ of vertex $u_i$.
The weight $w_i$ of each item is $1+$ the number of reachable vertices from $u_i$.

Explanation:

Since vertices with a non-zero value have no incoming arcs, they may be chosen independently, as there is no possibility for such a vertice to be chosen twice, as a "dependency" of another one. Thus, individual items in the knapsack problem may be mapped to these vertices.
As no vertice has more than 1 incoming arc, no vertice may be reached by multiple vertices. This guarantees that the weights of each knapsack item are independent of each other.

Questions

Have I formulated the original problem correctly, using the mathematical notations? It's been quite some time since I have formally formulated a graph theory problem.
Is this reduction enough to prove that the original problem is NP-hard? I only have reduced the 0-1 knapsack only to an instance of the original problem, not the original problem itself. Does this imply that the original problem is "at least as hard, if not harder" than the 0-1 knapsack?
Assuming that question (2) stands, is my reduction correct?
Alternatively, could I demonstrate my case via another reduction?

$x_i \leq x_j \forall (i,j) \in A$ is a linear constraint that represents your requirement (if $x_i=1$ it would push $x_j$ to take value $1$ as well). You get a constrained knapsack problem. You can easily reduce a knapsack to it by considering a graph that simply has no arrows.


Linear-time algorithm for solving a set of inequalites We have a set $A$ of $n$ distinct numbers. We want to determine for all  $x,y,z \in A$ whether the following relations hold.

$$
x+y>z\qquad x+z>y\qquad y+z>x
$$

Anyone could describe $O(n)$ Algorithm?

for this algorithm it's enough to check sum of two smallest element is bigger than the maximum element.

We find Min1, Min2, Max.

if Min1 + Min2 < Max there is no. O(n)
else all of them is true.


How can an approximation ratio be less than 1? A question in my algorithms text-book requires that we,

  Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this
  problem.

It is my understanding that $(1 - \frac{1}{k})$ being $p(n)$ is the approximation ratio and that an approximate solution differs from an optimal solution by a factor of $p(n)$. In that case, if $p(n)< 1$ wouldn't the approximation be better than optimal?

How can the approximation ratio be less than $1$?

For maximization problems, if the optimal solution is $O^*$ and the worst possible approximate solution is $O$, then the standard way is to consider $O^*/O$ as the approximation ratio. But in some text books, the ratio $O/O^*$ is considered for both minimization and maximization problems and it causes the ratio to be smaller than 1.

You may refer to Approximation Algorithm for more details.