Eliminating useless productions resulting from PDA to CFG converison In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states.

For example, for two transitions, I am getting the following productions

  $$\begin{gather*}
  \delta(q_0,1,Z) = (q_0,XZ) \\
  {}[q_0,Z,q_0] \to 1[q_0,X,q_0][q_0,Z,q_0] \\
  {}[q_0,Z,q_0] \to 1[q_0,X,q_1][q_1,Z,q_0] \\
  {}[q_0,Z,q_1] \to 1[q_0,X,q_0][q_0,Z,q_1] \\
  {}[q_0,Z,q_1] \to 1[q_0,X,q_1][q_1,Z,q_1] \\
\end{gather*}$$

  $$ \begin{gather*}
  \delta(q_1,0,Z) = (q_0,Z) \\
  {}[q_1,Z,q_0 ] \to 0[q_0,Z,q_0] \\
  {}[q_1,Z,q_1 ] \to 0[q_0,Z,q_1] \\
\end{gather*}$$

How do I decide which state makes it into final production, and which one will be excluded ?

It is not very clear what you wish to achieve. Do you wish to reduce the number of productions to the minimal possible? Do you only wish to avoid productions that are "not helpful" i.e., never appear in any valid derivation?

The first question seems difficult (e.g., This Work shows that it is NP-hard to approximate the length of the smallest grammar within a certain constant factor)

If you talk about the second issue, more things can be done. You should look on methods for converting grammar into a normal form (like Chomsky- or Greibach- normal form), since usually the first step in those conversions is to eliminate any unnecessary productions.

To be more specific, the most easy thing we can do, is to eliminate unreachable variables:

  For a given grammar $G=(V,T,S,P)$, we say that some variable $X \in V$ is unreachable if it cannot be reached from $S$, that is, there is no $\alpha \in (V \cup T)^*$ such that $S\to^* \alpha$ and $X\in \alpha$.

You can find unreachable variables by a straightforward BFS search starting from "$S$".

To complete the answer, let me also note that there are another type of variables, which we call unproductive (or "dead"). Those variables will cause the derivation never to terminate. Formally:

  We say that a variable $X\in V$ is unproductive if for any $\alpha \in (V\cup T)^*$ such that $X\to^*\alpha$, $\alpha$ has at least one variable, that is, $\alpha \notin T^*$.

For instance, if $S\to A \mid 1$ and $A\to A1$, then $A$ is unproductive—you can never get rid of it. Unproductive variables are also quite easy to find, and can be removed from the grammar (possibly along with some other productions, in which they appear on the right-hand-side.)


Number of final states in minimal DFA for $a^*b^*+b^*a^*$ How many final states exist in the minimal DFA that accepts the language $a^*b^* + b^*a^*$?

Here are the Myhill–Nerode classes of your language:

$\epsilon$
$a^+$
$b^+$
$a^+b^+$
$b^+a^+$
Everything else.

To show this, you have to do two things:

Show that when in a specific class and reading a specific letter, you go to another specific class. This essentially amounts to constructing a DFA whose states are the classes.
Show that all the classes are distinct. You do this by giving separating words for every pair of classes.

After that, all that remains to be done is counting how many of these classes correspond to words in the language.


What class this graph connectivity problem belong to We are given a Boolean circuit $C(x_1, \dots, x_n,y_1, \dots, y_n)$ with $2n$ inputs and we have to determine if the graph $G_C = (V_C, E_C)$ (specified below) is connected:
$$V_C = \{0,1\}^n, \\ E_C = \{((a_1, \dots, a_n), (b_1, \dots, b_n)) : C(a_1, \dots, a_n,b_1, \dots,b_n) = 1\}.$$
To which class this problem belongs? I know that graph connectivity can be done so fast (as fast as to be in P) and using a small amount of space. Does this is different in this particular graph? Is this problem in P, EXP, PSPACE?

$G$ has $2^n$ vertices, and for any two vertices $v_i,v_j$ we can check whether $(v_i,v_j)\in E$ in polynomial time (since circuit value problem is in P). By executing DFS on $G$ from any vertex you can find out whether $G$ is strongly connected in $O(|V|+|E|)=O\left(2^{2n}\right)$ time, which puts your problem in $E$, as the circuit's description is of size $\Omega(n)$.
Your problem is PSPACE-hard. Given a machine $M$ which uses $\le n^c$ space and input $x$, denote by $G_x$ its computation graph, i.e. the graph whose vertices are all possible configurations using $\le |x|^c$ cells and $(C_i,C_j)\in E_{G_x}$ iff $C_i$ is followed by $C_j$ in the computation of $M$. Now adjust $G_x$ by adding edges from every vertex to $C_x$, the initial configuration of $M$ on input $x$, and from the accepting configuration $C_{acc}$ (assume without loss of generality that it's unique) to all other vertices. Clearly this new graph $G_x'$ is strongly connected iff there is a path from the from $C_x$ to $C_{acc}$ in $G_x$. Given $M,x$ you can construct in polynomial time a circuit $C_{G_x'}$ that takes two vertices $C_i,C_j$ of $G_x'$ and outputs 1 iff there is an edge from $C_i$ to $C_j$ (checking whether one configuration is immediately followed by another is easy). I leave it to you to complete the details here.


Best algorithm for correlation between time series? I have some biological data (ECG), which are quite chaotic in nature, and and some other data; that are not chaotic but related in some way, like fatigue. I want to find out how the time series, chaotic, data are related to each of these other time series.

My undergrad thesis was on string "emotion" classification and time series is a whole other animal. My goal is to understand how the "other data" trend and at what percentage in correlation the biological data, not just classes [A, B, C].

I want to be able to distinct what is happening throughout the biological's phases in retrospect to the other time series. Like in this phase of the ECG there was 20% increase in fatigue, 7% in attention etc. I have all those data I just don't know how to make the connection.

I tried to find on time series ML but all of them jump from pretty basic algorithms and vague narratives to hardcore mathematical implementations.

If you know of a site, blog, docs, anything that ease into such examples and, very important, have code (python would be nice).

Would Random Forest work for such a task or should I be looking more into KNN (K-Means Nearest Neighbour), DTW (Dynamic Time Wrapping), STMF (Shape-based Template Matching Framework)?

Thank you very match for your time. Would be happy to provide and clarification I can, if anything doesn't make sense.

You haven't given us much information about your problem, so let me give you some hints about how to approach this.

First, look for a model.  Ask yourself: Do you have a plausible biological/physical model for how the dependent variables might depend on the independent variables?  Why do you think it's plausible that the independent variables might help in predicting the dependent variables?  This may help you select an appropriate machine learning tool.

If you don't have a model and don't have any physical/biological reason to expect a causal relationship, then you're doing data mining (and maybe you should reconsider why you are doing this project, or maybe you need to study the underlying application domain better to try to investigate candidate explanations why there might be a causal connection between the two).

Second, classify the data you have.  The right algorithm will depend on what data is in the time series.  Ask yourself: What is the value at each point in time, for the dependent variables and the independent variables?  For each, decide whether you have ordinal data, categorical data, or interval data -- that will play a huge role in narrowing down which machine learning algorithm might be applicable.  Also, ask yourself whether you know anything about their distributions.

Third, visualize your data.  Before you start diving into complex machine learning algorithms, do some data visualization.  Try to find as many ways as you can think of to look at your data.  Sometimes when you stare at data in the right way, that suggests hypotheses or relationships that might be relevant.

So, do all of that.  That will help you think more clearly about the problem, and may help you narrow down the scope of machine learning problems.  Once you've done all of that and can answer all of those questions, you might be in a position to ask a better-crafted, more narrowly scoped question.

Last, don't forget to consider some variety of linear regression: for interval data where you hypothesize some kind of linear relationship, it's a natural first thing to try.


Asymptotics of the number of words in a regular language of given length For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that for large enough $n$,
$$ c_n(L) = \sum_{i=1}^k P_i(n) \lambda_i^n, $$
where $P_i$ are complex polynomials and $\lambda_i$ are complex "eigenvalues". (For small $n$, we may have additional terms of the form $C_k[n=k]$, where $[n=k]$ is $1$ if $n=k$ and $0$ otherwise. These correspond to Jordan blocks of size at least $k+1$ with eigenvalue $0$.)

This representation seems to imply that if $L$ is infinite then asymptotically, $c_n(L) \sim C n^k \lambda^n$ for some $C,\lambda>0$. However, this is patently false: for the language $L$ over $\{0,1\}$ of all words of even length, $c_{2n}(L) = 2^{2n}$ but $c_{2n+1}(L) = 0$. This suggests that for some $d$ and for all $a \in \{0,\ldots,d-1\}$, either $c_{dm+a}(L) = 0$ for large enough $m$ or $c_{dm+a} \sim C_a (dm+a)^{k_a} \lambda_a^{dm+a}$. This is proved in Flajolet & Sedgewick (Theorem V.3), who attribute the proof to Berstel.

The proof provided by Flajolet and Sedgewick is somewhat technical; so technical, in fact, that they only sketch it. I attempted a more elementary proof using Perron-Frobenius theory. We can regard the transition graph of the DFA as a digraph. If the digraph is primitive then the result follows almost directly from the Perron-Frobenius theorem. If the digraph is irreducible but imprimitive with index $r$, then by considering the "$r$th power" of the DFA (each transition corresponds to $r$ symbols), we get the same result. The difficult case is when the digraph is reducible. We can reduce to the case of a path of strongly connected components, and then we get the result by estimating sums of the form
$$ \sum_{m_1+\cdots+m_k=m} \prod_{i=1}^k \lambda_i^{m_i}. $$
(Each such sum corresponds to a particular way of accepting a word, going through the different components in a certain way.) This sum, in turn, can be estimated by pinpointing the largest term, which corresponds to $m_i \propto \log \lambda_i$. For every eigenvalue which is repeated $r$ times, we get an extra factor of $\Theta(m^{r-1})$.

The proof has its rough edges: in the reducible case, we need to pass from terms asymptotic to $C \lambda_i^m$ to the sum mentioned above, and then we need to estimate the sum.

The proof by Flajolet and Sedgewick is perhaps simpler, but less elementary. Its starting point is the rational generating function of $c_n(L)$, and it involves induction on the number of pole magnitudes (!). The basic idea is that all eigenvalues of maximal modulus are roots of unity (if normalized by their modulus), due to a (moderately easy) theorem of Berstel. Choosing an appropriate $d$ and looking at words of length $dm+a$, all these eigenvalues become real. Considering the partial fraction expansion, we get that if the eigenvalue of maximal modulus "survives", then it determines the asymptotics, which are of the form $Cn^k\lambda^n$. Otherwise, we find a new rational generating function which corresponds just to words of this length (using an Hadamard product), and repeat the argument. The aforementioned quantity keeps decreasing, and so eventually we find the desired asymptotics; $d$ might have to grow in the process, to reflect everything that happens in the inductive steps.

  Is there a simple and elementary proof for the asymptotic property of $c_n(L)$?

The argument you have sketched appears to be in line with Richard Stanley's treatment of the Transfer-Matrix Method in Enumerative Combinatorics, Volume 1 (link: pp 573; print: pp 500).

He starts with the generating function, and unpacks it by considering digraphs and permissible and prohibited factors. He then abstracts to free monoids, where he uses a refined version of the sums you gave to prove:

  4.7.11 Proposition Let $B$ be a subset of $A^*$ that freely generates $B$. Then $B^*(\lambda)=(I-B(\lambda))^{-1}$

After working through some applications, he likewise closes the section by discussing Hadamard products in relation to horizontally-convex polyominoes.


Set relationship between Big-Oh and Theta notations I was reading "Introduction to Algorithms" by CLRS and it says that:

We write $f(n) = O(g(n))$ to indicate that a function $f(n)$ is a member of of the set $O(g(n))$. Note that $f(n) = \Theta(g(n))$ implies $f(n)=O(g(n))$, since $\Theta$-notation is a stronger notion than $O$ notation. Written set-theoretically, we have $\Theta(g(n)) \subseteq O(g(n))$.

Q1: What do the authors mean by strong notion? What is strong notion, when we use it, how does it help us (here) knowing one implication is stronger than the other and how does it affect when creating implication.

Q2: It seems contradictory in a sense by saying that $\Theta$ is stronger notion than $O$ and then writing $\Theta(g(n)) \subseteq O(g(n))$.How to deduce and then interpret the second sentence from the first?

I would appreciate your answers.

In general, a proposition $P$ is said to be stronger than $Q$ if $P$ implies $Q$ ( symbolically, $P\Rightarrow Q$)  and $NOT$( $Q$ implies $P$).  In the example at hand, $f \in \Theta(g) \Rightarrow f \in \mathcal{O}(g)$ , so that $f \in \Theta(g)$ is a stronger assertion than $f \in \mathcal{O}(g)$.


small size and small depth circuit for set intersections Input: Given sets $S_i \subseteq \{1,2,3,4,\cdots,n\}$ for $1 \leq i \leq n$.

Output: sets intersection with restriction (pick first set $S_1$. If $a \in S_1$ such that $a$ is the least element then do $S_1\cap S_a$. Next go to least element (say $b$) in $S_1\cap S_a$ and do $S_1\cap S_a \cap S_b$)

Finally I want to find the $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-1}}$ where $i_1$ least element in  $S_1$ and $i_2$ least element in  $S_1\cap S_{i_1}$, $i_3$ least element in  $S_1\cap S_{i_1} \cap S_{i_2}$, $\cdots$,
$i_{k-1}$ least element in $S_1\cap S_{i_1}\cap S_{i_2}\cdots \cap S_{i_{k-2}}$.

Can we build circuit for this above problem?

What happens if $k$ is fixed?
what happens if $k$ is $\log n$?

Can we have logspace algorithm for this problem?

I am familiar with circuits and logics and please help out.

I tried as follows:

first construct a matrix $A$ with $n \times n$ with entries zero's and one's.
Find the entry $(i,j)$ is one if $S_i$ have element $j$. other wise zero.

Now we need to find the first non zero entry (say a) in $S_1$ row in $A$ and do or gate $S_1$ row with $S_a$ row in $A$.
Again find the first non zero entry (say b) in $S_1 \vee S_a$ row and
do $S_1\vee S_a \vee S_b$.

Now this process I can not able to find the depth and size of circuit. Please let me know what is the circuit size and depth in this process.

You are asking many different questions. The usual rule is one question per post. To help you get started, here is how to compute $S_1 \cap S_{\min S_1}$ (defined as $\emptyset$ if $S_1 = \emptyset$).

The input to the circuit is the $n^2$ variables $x_{i,j}$, indicating $i \in S_j$ (this means that they are TRUE if the condition holds, and FALSE if it doesn't hold). The output to the circuit are $n$ variables $y_i$, indicating whether $i \in S_1 \cap S_{\min A}$.

Let $f_a$ indicate $\min S_1 = a$. Then
$$
f_a = \lnot x_{1,1} \land \cdots \land \lnot x_{a-1,1} \land x_a.
$$
Given these, we can calculate
$$
y_i = x_{i,1} \land \bigvee_{a=1}^n (f_a \land x_{i,a}).
$$
We can implement each $f_a$ as a depth 2 circuit with unbounded fan in of size $O(a)$, and each $y_i$ as a depth 2 circuit (with inputs $f_a$ and $x_{i,j}$) with unbounded fan in of size $O(n)$. The circuits for $f_a$ take $O(n^2)$ in total and the circuits for $y_i$ take $O(n^2)$ in total, so altogether we get a depth 4 circuit of size $O(n^2)$.

This circuit is equivalent to a depth $O(\log n)$ circuit of size $O(n^2)$ with bounded fan-in, by replacing each large fan-in gate by a balanced binary tree.


Longest sequence of dominoes Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the same as $\langle 0, 3\rangle$.
A sequence of length $n$ of dominoes is a sequence $(d_0, d_1, …, d_{n-1})$ where $d_i = \langle a_i, b_i\rangle$ is a domino, and $\forall i \in [\![0, n-2]\!], b_i = a_{i+1}$. For example, $\langle 2,3\rangle\langle 3,5\rangle\langle 5,2\rangle\langle 2,1\rangle$ is a sequence of length 4.
Given $k$ and $N$, and a set $S$ of $N$ distincts $k$-dominoes, I want to find the longest sequence of dominoes constructible using each domino in the set $S$ at most once.
My ideas so far are to use some kind of backtracking algorithm: I try to complete a sequence of dominoes with a new domino – among those not used, or not eliminated – and if it is valid, I continue; if there is no valid domino, I delete and elimininate the last domino to try again. I am using hash table to keep track of the remaining dominoes.
I wondered if there is a more efficient/elegant way to do it, maybe by pre-sorting the set $S$ before trying to construct sequences of dominoes, or using dynamic programming in a way I haven't found yet.
I also thought of constructing a graph with each domino as a vertex, but I don't really know how to put edges because of the two faces of the domino: if I add an edge between two dominoes that have a common value, then I risk to find $\langle 1,2\rangle\langle 2,3\rangle\langle 2,0\rangle$ as a valid sequence…
One of the ideas proposed in the comments is to construct a graph where vertices are integers of $[\![0,k-1]\!]$ and edges are dominoes of $S$ (domino $\langle a , b\rangle$ is an edge between $a$ and $b$, possibly a loop if $a = b$). The question is now equivalent to finding a longest path in this graph. The problem is that it is not similar to longest path problem because the path are not necessarily simples (meaning a path can cross the same vertex multiple times). One would need to keep track of used edges to find the longest path, so it does not really simplify the problem.
The problem is difficult and seems even $NP$-hard, but I still want to find an efficient algorithm solving it. My current backtracking solution find the answer for $k = 20$ and $N = 30$ in 10 sec (for a randomly generated set of distinct dominoes), but it increases quickly if I lower the value of $k$ or increase the value of $N$ (even $k = 15$ and $N = 30$ is taking ~30 minutes).

Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of degree at most $2$ (the problem remains hard in this case).
W.l.o.g., let $V=\{3,\dots,k-4\}$, $s=3$, and $t=k-4$.
Create the dominoes $(0,1)$, $(1,2)$, $(2,3)$, $(k-4, k-3)$, $(k-3, k-2)$, and $(k-2, k-1)$. Create one "edge" domino $(a,b)$ for each edge $(a,b) \in E$.
There exists an Hamiltonian path in $G$ if and only if there is a sequence of $k-1$ dominoes.
Indeed, notice that any sequence of dominoes that only uses the dominoes from $E$ traces a (not-necessarily simple) path $P$ in $G$.
But then, all vertices except the endpoints of $P$ must be traversed at most once (since their degree is at most $3$). The two endpoints can extend the path by at most $2$. Then the number of edges of $P$ can be at most $|V|+1 = k-6+1 = k-5$. This implies that a sequence of $k-1$ dominoes must use all "non-edge" dominoes, i.e., the sequence of dominoes must start with $(0,1), \dots, (2,3)$ and end with $(k-4, k-4), \dots, (k-2, k-1)$.
Then, the path induced by the sub-sequence obtained by dropping the "non-edge" dominoes must be simple and traverses $k-1-6 = k-7 = |V|-1$ edges of $G$, i.e., it is an Hamiltonian path in $G$.
Conversely, we can create a sequence of $\ell+6$ dominoes from any simple path of length $\ell$ from $s$ to $t$ in $G$ (simply prepend $(0,1), \dots, (2,3)$ and append  $(k-4, k-4), \dots, (k-2, k-1)$). For an Hamiltoniam path we have $\ell=|V|-1=k-7$, therefore the sequence has length $k-1$.


Reference for an undecidability proof I'm searching for a reference of an undecidability proof that is as simple as possible and starts "from scratch".

With "from scratch" I mean that it does not use some other undecidable problem to prove some undecidability (which is the usual case), I cannot wrap my mind about how proving undecidability that way (without a previous proof) could be possible.

This question may be inspiring: An example of an easy to understand undecidable problem

Also, I know this is probably not very objective, but it is important to me, it should be something as simple as possible, hopefully enough so that even I can understand it.

to some degree all refs on the subject have a formidable inherent complexity due to the subject matter. however, here is a classic, highly accessible ref on Gödel's thm that may be helpful, written in "popular science" style by a philosopher & mathematics historian for a broad audience, breaking it down into intuitive everyday language.

Gödel's Proof Nagel/Newman

here are some other similar but more technical refs that may be helpful

An Introduction to Gödel's Theorems Smith
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse Franzén

there are also many refs on Turing's halting problem. one worth mentioning, a step-by-step walkthrough/tour of the original proof, but which is very advanced due to retaining all the mathematical complexity/detail:

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine Petzold

on the other hand most of the proof complexity of the halting problem is associated with the proof of the existence of the Universal TM, wikipedia has a pretty good outline. this can be understood as a simulation or emulation of one machine by another. therefore studying the theory of machine emulation (now quite frequently applied with video games) may be helpful.


Is {a^n (a+b)^n | n>0} a Deterministic CFL? $L = \{  a^n (a+b)^n   | n>0\}$

A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using a DPDA? Like after reading the first part ($a^n$) how can we be sure that it's the end of the first part or not considering the second part can also start with $a?
$

Is this Deterministic?

You needn't determine the end of "first part".

Note $L$ is exactly the set of strings satisfying the following three constraints:

Its length is even.
It only contains $a$ and $b$.
The first $b$ appears in its latter half.

Constraints 1 and 2 are easy to check. To check constraint 3, the DPDA can push a symbol to its stack each time it reads a character until the first $b$ appears (excluding), and then pop a symbol each time it reads a character. Constraint 3 is satisfied if and only if the initial stack symbol is never read during the popping process.


Convert regular expression to Automaton I'm trying to construct a finite-state automaton from the following regular expression:

$$
(a|ba)(a|ba)^*(b|ab)^*
$$

I know that from
$$
(a|ba)
$$

the automaton should look something like this:

automaton http://cdn.imghack.se/images/5ab1437745d2a53d4630619819074d6c.jpg

from
$$
(a|ba)^*
$$

it should look like this I guess:

automaton2 http://cdn.imghack.se/images/e1dc6ac63c6d967086d1f40aebf62c51.jpg

and from
$$
(b|ab)^*
$$

is pretty much the same as the last one, the thing is I don't know how to unite them in one automaton.

I would appreciate any help in this matter

PS: I'm sorry for the images I'm still learning how to work with the automata editor jflap...

Regular expressions can be turned into (nondeterministic) finite automata very easily. What your automata are missing are start- and final states.

Once you have marked those, its very simple: If you have the automaton $A_1$ for $(a|ba)$ and $A_2$ for $(a|ba)^*$, to get an automaton for $(a|ba)(a|ba)^*$, just add $\varepsilon$-transitions from all finite states of $A_1$ to the start state of $A_2$. (This is btw part of the Thompson-construction, in case you want to look it up :) ) If needed, you can then remove all $\varepsilon$-transitions.

If you directly want to construct a $\varepsilon$-free NFA, you can use Glushkovs construction.


What is cold-start penalty ? What are some ways to reduce it? when a new process is created using a fork() function, there is a cold start penalty, what is this and why does it happen?

"Cold start penalty" is the penalty for starting a process that has never run. The operating system has to read the code from disk, page tables have to be set up, caches filled in as instructions are executed/data fetched, and so on. If the process has run before, some of the above will already have been set up (and perhaps not fully evicted).


What are analog and digital in computer science? I once thought that any analog computer is any computer which "doesn't need electrical current to work".
I once thought that any digital computer is any computer which "does indeed need (a correctly distributed) electrical current to work".
I found out both assertions as wrong.
What are analog and digital in computer science?

I'll try to answer your remaining question: what are analog and digital in computer science?
The trouble is that these terms aren't from computer science. They are from the field called "signal processing". When someone says "analog computer", they simply mean that the computer is designed on principles of analog signal processing and built from analog components. The same goes for digital computers: they are designed with digital signal processing in mind and built from digital components.
So what does "analog" means? The word is taken from Greek word "proportional". To clarify what it means, let's look at the sum operation implemented with graduated cylinders:

Say you want to compute $13 + 38$. First, you take an empty cylinder and fill it up to $13$ ml mark. Then you take another empty one and fill it up to $38$ ml mark. Then you pour one into the other and look how much ml of liquid is there, which you announce as the result of the sum operation.
This is "proportional", because if you want to use $26$ instead of $13$ as an input, you use double amount of liquid. Double amount of liquid means twice as large number. An electrical analog computer could use the voltage of electric current is a similar way.
Now let's take a look on a digital computation implemented with Soldier Crabs. Here's how you make logical OR:

And here's logical AND:

You put a swarm of crabs where you want logical $1$ as an input and you leave empty places where you want logical $0$. Then you look where the swarm ball ends up and interpret it as $0$ or $1$. This is built on principles of (binary) digital processing:

No crabs (no electric current, no water flow) means $0$.
A swarm of crabs (5V, steady water flow) means $1$.
What if you can't decide which is the case? You just say that your digital component is broken.


Number of nodes of a parse tree when the Grammar is in CNF? There happened to be a following question -

  In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n>0$ generated by G have?

I tried for some examples & arrived at the answer $2^{n}+1$ but it is incorrect & obviously trying examples is not a sophisticated way. The correct answer given is $3^{n}-1.$ Can anyone explain how this answer comes?

Both of the answers are wrong. To find the correct answer, let us consider the grammar
$$ S \to SA \mid a \\ A \to a $$

You can check that the tree corresponding to $S \to a$ has 2 nodes, the one corresponding to $S \to SA \to aA \to aa$ has 5 nodes, and the one corresponding to $S \to SA \to SAA \to aAA \to aaA \to aaa$ has 8 nodes. This corresponds to the formula $3n-1$ (rather than $3^n-1$, the formula you quoted).

Let us now prove that this formula is correct. The proof is by induction, where we allow varying the starting nonterminal. When $n = 1$, the derivation must be of the form $A \to \sigma$, which includes 2 nodes. When $n > 1$, the first step must be $A \to BC$, where $B$ gives rise to a word of length $k$, and $C$ gives rise to a word of length $n-k$. The entire tree is formed from the trees corresponding to $B,C$ by adding the root, and so the total number of nodes is $$1 + (3k-1) + (3(n-k)-1) = 3n-1.$$


Proving NP hardness in Puzzle with SAT reduction Introduction

I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on circular matrix shift of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1 and  Here-2 and Grid generation and Grid generation written in Python

SAT Instance Used

I have taken this SAT instance from this linked pdf  on page 3 and reduced to a 3-SAT instance.

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3) ∧ x5

SAT reduced into 3-SAT

(x1 ∨ x2 ∨ ¬x4) ∧ (x2 ∨ ¬x3 ∨ x1)

Here are the definitions for the variables.

shift(L) = the circular shifts

  x1 = shift(L) to generate valid n^2 x n^2 grid and puzzle

  x2 = shift(L) to generate another valid n^2 x n^2 grid and puzzle

  ¬x4 = valid grids and puzzles not following shift(L)

  ¬x3 = another valid grid and its puzzle not following shift(L)

Explanation of the purpose of the 3-SAT instance

When x1 and x2 are true (shift(L) grids and puzzles)

Then the output is True (shift(L) puzzles/grid)

When x1 and/or x2 is not shift(L)... false.

While the negated form is basically a "not false"

Therefore the output is false because no two puzzles are made from shift(L)

Question

Did I prove correctly that my puzzles are NP-hard assuming that the language used to generate these grids never have missing instances?

As far as I can tell, no, you have not proved NP-hardness of your puzzle. NP-hardness is precisely defined. If you want to prove a mathematical statement, you must do mathematical work and can't get there by only hope and intuition.

If you want to show that problem X is hard by a polynomial-time reduction from 3-SAT, you should proceed as follows. Take any arbitrary instance $I$ of 3-SAT and construct, in polynomial-time, an instance $I'$ of X. Once you've done this, prove that $I$ has a solution if and only if $I'$ has a solution. This is the "mathematical part", where you use the properties of $I$ and $I'$ to argue for both implications; you need some insight and practice in writing mathematical proofs, where in the argument the next step follows from the previous.

For example, contrary to what you seem to say, you can't show hardness by reducing one fixed instance of 3-SAT to your problem X.

If all this feels confusing but you are still excited, I recommend that you:

Read the relevant definitions of NP, NP-hardness and polynomial-time reductions. Think about what they mean intuitively as well.
Look at examples of reductions and NP-completeness proofs. Don't expect to get it straight away, but be willing to do some work. There are plenty of exercises out there and many questions on this site too.
Come back to your original problem later, perhaps after getting a little bit more familiar with writing proofs in general.


Are empty-set languages recursively enumerable? Are languages whose sets are empty recursively enumerable or recursive? For example, consider the language $L$ $\subseteq$ {0,1}*:

  $L$ = { $w$ | $w$ consists of only 0's} $\cap$ { $w$ | $w$ consists of only 1's }

I believe this language creates an empty set. There are many different ways to design a Turing Machine that decides that whether word $w$ is in $L$. In that sense, $L$ seems recursive. Further, there are many different machines that can return the empty set. Any of these them would effectively "enumerate" the members of L, even though there are none.

My gut tells me to reject these conclusions. Could anyone steer me in the right direction? Any guidance would be much appreciated.

The empty language is recursive. The TM accepting this language just returns $0$/REJECT on any input. Similarly, the language $\Sigma^*$ is also recursive. Just return $1$/ACCEPT on any input.

Basically, it does not matter how a language is defined. What makes them recursive/RE is the fact that we can effectively decide its membership. For
a recursive language $L$ there is a TM that always accepts $x$ if $x \in L$ and rejects $x$ if $x \notin L$. For a recursively enumerable language $L$  there is a TM that always accepts $x$ if $x \in L$.


Fixed base exponentiation with precomputations I'm trying to compute $g^m$ mod $n$ where $m,n$ are 1024-bit numbers. The method I want to use is fixed base exponentiation with precomputations, also known as fixed-base windowing.The paper I'm following is Brickell et. al. "Fast Exponentiation with Precomputation: Algorithms and Lower Bounds" which can be found here.

Basically the idea is to precompute $g^{b^i}$ where $b$ is a radix. Now if we write $m$ in the radix base: $m=\sum_{i=0}^k e_i b^i$ then $g^m=\prod (g^{b^i})^{e_i}$. For example: say we want to compute $g^{142}$ and we have chosen as radix $b=3$ (I'm aware of the more natural example of radix 2, but I'm experimenting with different radices to see if there is any speed-up). I write $m=(12021)_3$ and compute $g^{142}=g^{3^4}\times(g^{3^3})^2\times (g^3)^2 \times g^3$.

The pseudo code given in the paper is:

b ← 1
a ← 1
for d = h to 1 by −1
    for each i such that a_i = d
        b ← b ∗ g^{x_i}
    a ← a ∗ b.
return a.

where $h$ is the range of $e_i$, and $a_i=e_i$ and $x_i=g^{b^i}$.

My question is: instead of going through $e_i$ by tier as the pseudo code suggested, why don't we go through the base $b$ representation of $m$ one digit at a time and multiply as we go?

When I looked up fixed-base exponentiation in Henk and Tilborg "Encyclopedia of Cryptography and Security," they say that "there is time saved by multiplying together powers with identical coefficients, and then raising the intermediate products to powers step by step." I believe this is hinting at the answer to my question, but I don't understand the reasoning.

Your question hits at the main part of the faster algorithm presented in the paper. Many people know the usual (base-2) "repeated squaring" algorithm to compute $g^n$ is to write $n$ in binary:
$$
n=\sum_{i=0}^m e_i2^i\qquad e_i\in\{0,1\}
$$
so
$$
g^n=g^{e_02^0+e_12^1+e_22^2+\dotsm}=(g^{2^0})^{e_0}(g^{2^1})^{e_1}(g^{2^2})^{e_2}\dotsm
$$
and observe that $g^{2^k}=(g^{2^{k-1}})^2$ so computation of the $g$ terms can be accomplished by repeated squaring, either in the body of the loop or by precomputation.
The paper simply generalizes this using a base, $b$, other than $2$. If we keep with your example of $b=3$, then we're doing the same thing as the usual algorithm, only using repeated cubing, rather than repeated squaring, so if we have, in general
$$
n=\sum_{i=0}^m e_ib^i\qquad e_i\in\{0,1,\dotsc,b-1\}
$$
then we can write
$$
g^n=(g^{b^0})^{e_0}(g^{b^1})^{e_1}(g^{b^2})^{e_2}\dotsm
$$
and do the usual algorithm, forming the product seriatim, from $0$ up to the limit $m$, using repeated exponentiation of the terms, since $g^{b^k}=(g^{b^{k-1}})^b$ as above. This is your proposal and it will work just fine.

The key idea in the paper relies on the observation that the $e_i$ are now not just $0$ or $1$, so we often have another exponentiation step for each term. Rather than do several of those, the paper just does it once, for each possible value of $e_i$.

Here's your example, with $n=142$ and $b=3$. Since $142_{10}=12021_3$ we'll have $e_4=1$, $e_3=2$, $e_2=0$, $e_1=2$, $e_0=1$. Looping from $i=0$ to $4$ you could successively form the product
$$
g^{142}=(g^{3^0})^1(g^{3^1})^{2}(g^{3^2})^{0}(g^{3^3})^{2}(g^{3^4})^{1}
$$
The paper instead loops first by the nonzero values of the $e_i$, effectively grouping several exponentiations into one, doing this:
$$
g^{142}=\left [(g^{3^1})(g^{3^3})\right ]^2\left [(g^{3^0})(g^{3^4})\right ]^1
$$
obviously saving some multiplications.


How to find time complexity for functions in lazy functional languages? So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict imperative languages, and there seems to be very little about finding time complexity in lazy functional languages.

The former resources are somewhat unsuitable for finding the time complexity of lazy functions. E.g.:

minimum = head . sort

For a good definition of sort, minimum will run in $\cal{O}(n)$ time even though head runs in $\cal{O}(1)$ time and sort can run in $\cal{O}(n * log(n))$ or $\cal{O}(n^2)$ time.

However if I wrote this function in a strict imperative language as

fun minimum(list):
    sort(list);
    return head(list);

and then tried to combine the complexities of the sort and head functions the way it is done with algorithms in strict imperative languages, then I would get that the minimum function will run in $\cal{O}(n * log(n)) + \cal{O}(1) = \cal{O}(n * log(n))$ or $\cal{O}(n^2) + \cal{O}(1) = \cal{O}(n^2)$ time.

Which is of course correct for the strict function, however it doesn't have to be very accurate for the lazy version of the same function as shown above. So using the same technique in lazy programming languages wouldn't be all that useful.

I think the difference comes in from the laziness, because it causes data to be computed only as much as they are required by the function using them. This is opposite to how it works in strict languages, where the function using the data has no control over how much the data gets evaluated by the function creating them.

This means that knowing the time complexity of fully evaluating a function, which is what one usually looks for when figuring out the time complexity of a function, isn't necessarily useful for knowing the time complexity of a function using data from this function unless said function evaluates the data fully.

So what is useful to know about one function to figure out the time complexity of another function using the resulting data from it inside a lazy functional language?

Is there a formal system that helps out with finding out the time complexity in this situation?

I know I could probably try evaluating the whole function by hand if I have source to all the functions that it uses, but I don't necessarily have that.

On similar note, if I don't have the source of a function and I only have a documentation to it, then what would the writer of said documentation need to include in the documentation for me to be able to accurately find the time complexity of a function that uses their function?

As said before, the time complexity of evaluating the function fully isn't enough. But what if they included time complexity of evaluating the first i elements of the list the function is generating? Would that be enough? If yes, then how could this be generalized to other data structures as well?

I would consider an approach based on potential. Note that lazy evaluation changes the internal state of an object and therefore takes away an important advantage of functional programming.

As an example, imagine the following three functions

sort : List $\rightarrow$ List. Sorts the list using Selection Sort.
unique_special : List $\rightarrow$ List. For every odd position $i$ in the input list, the element at that position is removed from the list if it is equal to the element at $i+1$.
head : List $\rightarrow$ X. Finds the first element of the list.

Given a list $L$, I will use $\Phi(L)$ for its potential. $\Phi(L) : \{1, \dots, |L|\} \rightarrow \mathbb{N}$ is a function describing the cost of each element.

A "clear" list has a constant potential, i.e. $\Phi(L)(i) = 1$ for all indices $i$.

Let L be a list and sort(L) = L'. Then $\Phi(L')(i) = \sum\limits_{j=1}^{|L|} \Phi(L)(j)$, because Selection Sort will have to look at every element in $L$ to find a minimal one. After this, $L$ is completely evaluated, i.e. it is not "lazy" anymore. This means the potential of every element is reduced to $\Phi(L)(i) = 1$. Here you can see the importance of the fact, that lazy evaluation can change within an object. If you assume that is not possible, for example by disallowing variables (e.g. via "where" in Haskell), the analysis becomes easier.

For unique_special, consider again L' = unique_special(L). To evaluate the first element, the next one has to be evaluated as well (to compare them). $\Phi(L')(1) = \Phi(L)(1) + \Phi(L)(2)$. Of course, would $L'(1)$ be evaluated, the potential of $L(1)$ and $L(2)$ would become 1.

Later elements require additional knowledge of whether the previous elements were deleted. You have $L'(2) = L(1)$ if the first element was deleted and $L'(2) = L(2)$ otherwise. Hence, $\Phi(L')(2) = \Phi(L)(1) + \Phi(L)(2)$ and $\Phi(L')(3) = \Phi(L)(1) + \Phi(L)(2) + \Phi(L)(3) + \Phi(L)(4)$.

Generalizing this formula results in $\Phi(L')(i) = \sum\limits_{j=1}^k \Phi(L)(j)$, where $k = \lfloor \frac{i}{2} \rfloor \cdot 2$.

Finally, consider head(L). This does not create a new list, it just requires you to pay the potential of $\Phi(L)(1)$.

As you can see, this clearly increases the complexity of function definitions, especially if you want to include changing potential of the same data structure in your analysis. It gives you the opportunity for a more abstract analysis though:

Let $L$ be a completely evaluated / non-lazy list and the call head(sort(L))). The cost of this call will be $\Phi(\text{sort}(L))(1) = \sum\limits_{j=1}^{|L|} \Phi(L)(j) = |L|$.

A second example: What is the cost of the call head(unique_special(L')), where $L' = \text{sort}(L)$?

\begin{align*}
& \Phi(\text{unique_special}(L'))(1) \\
=& \Phi(L')(1) + \Phi(L')(2) \\
=& \sum\limits_{j=1}^{|L|} 1 + \sum\limits_{j=1}^{|L|} 1 \\
=& 2 |L|
\end{align*}

You can put more detail into the description of $\Phi$ to observe more accurate results.

Regarding generalization to other data structures, I didn't think about that too much so far. It should be clear that similar structures such as queues work in a similar way. However, for example for a Union-Find structure, I can't think of a way my approach would give you any advantage.

An addition regarding non-linear data structures, for example binary search trees. While it is the easiest option, there is no definite need to use a set $\{1, \dots, n\}$ as the domain of $\Phi$. A common way to index the nodes of a binary tree is to use strings in $\{0,1\}^*$. The root is labelled with the empty string $\varepsilon$ and for a node $v$, the left successor is $v0$ and the right successor is $v1$. For example, the following tree

   5
 4   8
1   6 9

would have the domain $\{\varepsilon, 0, 00, 1, 10, 11\}$.

Imagine a function delete : Tree $\times$ Node $\rightarrow$ Tree to remove a certain node from the tree. You need to check if either of the subtrees is empty. Let delete($T$, $v$) = $T'$, then the potential is $\Phi(T')(v) = \sum\limits_{\substack{w \in \{0,1\}^* \\ w \text{ is a descendant of } v}} \Phi(T)(w)$, where we assume $\Phi(T)(w) = 0$ if $w$ is not a node of $T$.


Edit distance for huge strings with bounds My question is simple but I don't know if the answer is.

  If you have two strings of length 10 million each, is there an algorithm that would allow you in
  practice to compute their edit distance (Levenshtein) if you are told
  it is at most 100?

You can use the usual dynamic programming algorithm. Instead of computing the edit distance between all prefixes of the input strings, compute only the edit distance between prefixes whose length is at most 100 apart. This reduces the number of entries to compute from $10^{14}$ to roughly $2\cdot 10^9$, which is feasible.


Python: A doubt on time and space complexity on string slicing This qns is from my school's exam paper.

Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase.

The function remove takes as inputs 2 strings, a letter and a word, and outputs the word with all occurrences of letter removed.

Provide an iterative implementation of the function remove and briefly explain the time and space complexity of the function you have written.

Attached below was my code, which is the same as the solution provided.

However I got stumped when I tried to explain the time and space complexity as O(n) and O(1) respectively as the answer given was O(n^2) and O(n).

The explanation provided by the examiner is:

Time complexity: O(n^2) where n is the length of the input string. This is because in every loop iteration, the string concatenation of new_word gets longer until it is at worst, length n.

Space complexity: O(n), even though there are no delayed operations or new objects being created every iteration, the new string created at worst can be the same length as the original string if there are no letters removed.

My practice is when I explain something, I should be able to map it out mathematically.

Time: Sum of time taken for each iteration OR Sum of time for each recursion

1)I do not understand why string concatenation contributes to time complexity. For recursive codes its clear cut as there is string slicing involved(s[0] and s[1:], formation of s[1:] will take O(n-1),O(1) from s[0] is negligible) in every recursive call, sum of time is n+(n-1)+…+1=O(n^2). For the explanation of iterative, should I just accept it or is there a theory behind why concatenation adds to time complexity.

Space: Sum of space taken for each recursion OR sum of space taken for each iteration

2) I initially thought space for recursion and iteration is calculated the same way. Is it correct to accept that for iteration, space should be calculated as the space needed for the most demanding iteration instead of the accumulative sum of space for all iterations. Most demanding would then be when new_word and word are equivalent.

3) I actually accepted the fact that iteration usually takes up O(1) space and would bomb it everytime I can. What is really the reason behind deeming the space complexity of iterative to be O(1)?

Correct me at any point as I find that I am memorising and not understanding many things at this point.

def remove(letter,word):
    new_word=""
    for i in word:
        if letter!=i:
            new_word+=i
    return new_word

The running time of string concatenation depends on how it is implemented. It is impossible to tell whether new_word += i takes $O(1)$ or $\Theta(|\text{new_word}|)$ or anything else unless you know more about Python. Moreover, looking around stackoverflow, it seems that the complexity depends on which version of Python you are using.

In contrast, it is quite clear that the procedure uses $\Theta(|\text{word}|+1)$ space, since it builds new_word from scratch, not reusing the memory of word. This has nothing to do with the loop; the statement new_word = word[:], which makes a copy of word, also uses up $|\text{word}|$ space. Space consumption is the amount of memory used. If you're constructing a new string of length $|\text{word}|$, then it uses up memory proportional to $|\text{word}|$.

I suggest forgetting about what you call the "mathematical perspective", and focusing instead on the intuitive meaning of time and space complexity. Time complexity is the number of instructions executed by the program. Space complexity is the amount of memory that needs to be allocated in order to run the procedure. You are stating some rules for calculating these quantities, but it's much more important for you to understand what you are calculating rather than specific tricks which are dubious when applied mechanically.


A question on oracle turing machines I am trying to solve a question from the exercise of this book, pg. 46,section 7.4.

Let $M$ be a deterministic Turing machine that only queries oracle strings
that are shorter than the input string. Show that if $A = L(M^A)$ and $B = L(M^B)$ then $A = B$.

I think I have to apply induction. Does it involve self-reducibility concept? Just hints would be sufficient.

You can prove by induction that for all $n\in\mathbb{N}$, $A$ and $B$ agree on all the strings in $\{0,1\}^{\le n}$, i.e. $A\cap\{0,1\}^{\le n}=B\cap\{0,1\}^{\le n}$.

The case of $n=0$ follows from the fact that $M$ does not query its oracle on the input $\epsilon$, which means $M^A$ accepts $\epsilon$ iff $M^B$ accepts it. For $n>0$, let $x\in\{0,1\}^{n+1}$ be some length $n+1$ string. We need to prove (under the inductive hypothesis) that $x\in A\iff x\in B$. Suppose $x\in A$, then $M^A$ accepts $x$. Note that on input $x$, $M^A$ queries strings in $\{0,1\}^{\le n}$ alone, where $A$ and $B$ agree. This means that replacing the oracle from $A$ to $B$ won't change $M$'s outcome on $x$, hence $M^B$ accepts $x$ and therefore $x\in B$, since $B=L(M^B)$. The same arguments apply in the $x\notin A$ case, which concludes the proof.


Kleene star Empty language I had a test a couple of days ago and one of the question had 2 statements :

$L^+ = L^\ast$
$L$ contains $\varepsilon$

I had to say does 1 imply 2, does 2 imply 1 or do they both imply each other.

I answered that only 2 implies 1 but the answer is that they both imply each other.

But I don't understand, if $L = \emptyset$ (Empty Language), then $L^\ast = \{\varepsilon\}$ and $L^+ = \{ \varepsilon \}$, they are equal and $L$ doesn't contain $\varepsilon$.

Am I wrong?

You're wrong about $L^+$:

$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$


When is the minimum spanning tree for a graph not unique Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G?

I know that the MST is unique when all of the weights are distinct, but you can't reverse this statement. If there are muliple edges with the same weight in the graph, there may be multiple MSTs but there might also be just one:

In this example, the graph on the left has a unique MST but the right one does not.

The closest I could get to finding conditions for non-uniqueness of the MST was this:

Consider all of the chordless cycles (cycles that don't contain other cycles) in the graph G. If in any of these cycles the maximum weighted edge exists multiple times, then the graph does not have a unique minimum spanning tree.

My idea was that for a cycle like this

with n vertices, you can leave out exactly one of the edges and still have all of the vertices be connected. Therefore, you have multiple choices to remove the edge with the highest weight to get a MST, so the MST is not unique.

However, I then came up with this example:

You can see that this graph does have a cycle that fits my condition: (E,F,G,H) but as far as I can see, the minimum spanning tree is unique:

So it seems like my condition isn't correct (or maybe just not completely correct). I'd greaty appreciate any help on finding the necessary and sufficient conditions for the non uniqueness of the minimum spanning tree.

in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2.

Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$.

If there exists an edge $e=\{v,w\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest edge-weight from $F\cap C$, then we can create a second MST by swapping an edge from $F\cap C$ with edge-weight $m$ with $e$. Thus we do not have uniqueness.


Finding "entrance" points in a set of d-dimensional points. Can I do better than O(N^2)? I am given a set of d-dimensional points, and need to find the set of entrance points in them.
Definitions:

A point p1 captures p2 if 1) All dimensions of p1 is smaller or equal to p2; and 2) At least one dimension of p1 is strictly less than its corresponding dimension of p2. (e.g. p1 = <1.0, 2.0, 3.0>, p2 = <1.0, 3.0, 3.0>, since 1.0 == 1.0, 2.0 < 3.0, 3.0 == 3.0, we say p1 captures p2.
An entrance point is a point which it is not captured by any other points in the dataset.

For example, in the following dataset:
n = 4, d = 2
=============
p1 = <0.3, 1.5>
p2 = <0.2, 1.4>
p3 = <0.1, 1.7>
p4 = <0.8, 0.9>

The entrance points are {p2, p3, p4} because:

p1 is captured by p2 because all dimensions of p2 is less than p1.
p2, p3, p4 cannot capture each other.

Assuming d is a constant. Now I can only think of a naive O(N^2) solution, that is, take every possible pair of the points and compare the dimensions one by one. If a point is captured by the other, eliminate it from the final set.
I also thought of a divide-and-conquer solution. That is, recursively break the points down into two partitions, perform the previous O(N^2) algorithm to eliminate some candidates from the final set, then recursively merge each pair of the partitions, say part1 and part2, back by comparing each possible pair of points one from part1 and one from part2. However, even though the running time is a little faster with the aid of multi-threading, I found that it is still an O(N^2) algorithm because T(N)=2T(N/2)+O(N^2) ==> O(T(N)) = O(N^2).
I wonder if there exists an algorithm with lower time-complexity for this problem.
Also, is there any well-known name for this problem? Or are there any well-known problems similar to this one so I can look into?

Your problem is similar to finding Maxima of a point set in a $d$-dimensional space. In $2$-$D$ and $3$-$D$ there is a simple Divide and Conquer algorithm that has a $O(n \log n)$ running time. For higher dimension, there is $O(n (\log n)^{d-3}\log \log n)$ time algorithm as given in the Wikipedia page.
You can covert your problem to the Maxima problem, by simply negating the coordinate values of the input points. In other words, your problem is a Minima problem.


Black Box Decision problem for NFA Suppose we are given an NFA $M$ (without $\epsilon$-transitions) that we only know the alphabet $\Sigma$ and the number of states $|Q|$ but we do not know any other details of the NFA. We want to develop a black box algorithm that can test if $L(M)=\Sigma^{*}$.
My idea is that we can feed every string up to size $|\Sigma|^{|Q|-1}$, if every strings are accepted, then $L(M)=\Sigma^{*}$. Since all strings up to size $|\Sigma|^{|Q|-1}$ must go through every reachable state in $M$, if all of them get accepted then no matter what string is input, it will be accepted. Am I correct?

Ellul, Krawetz, Shallit and Wang construct in their paper Regular Expressions: New Results and Open Problems a regular expression of length $n$ (for infinitely many $n$) such that the shortest string missing from its language has length $2^{\Omega(n)}$. Since a regular expression of  length $n$ can be converted to an NFA having $O(n)$ states, this gives, for infinitely many $n$, an NFA having $n$ states such that the shortest string not accepted by the NFA has length $2^{\Omega(n)}$.

Conversely, if an NFA having $n$ states doesn't accept all strings, then it must reject some string of length shorter than $2^n$. This follows from the pumping lemma once you convert the NFA to a DFA. Hence the construction in the paper mentioned above is optimal up to the constant in the exponent.


Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops? Say I have 3 simple tasks, to find the min, the max, and the average of an array of numbers.

A modular approach would be to write one function for each, thus iterating over the array thrice. However, that seems wasteful when all the information can be collected in a single iteration.

I understand that both approaches take 3n time but am wondering if one approach is better than the other in the general case and why.

Collecting the information in a single iteration would be way better, but you'll only notice the difference if your array contains a large number of numbers. On a small scale, it just won't make a difference.


What is the term for two file formats that describe the same amount of information? I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not take into account some data or meta-data or use approximated values.
I was looking for a term to describe the first case, where two formats describe the same amount of information. I'm aware of the term isomorph that seems to describe the case quite well but I couldn't find any reference to any isomorph file format. Is there any other term used for describing the case?

I think that many programmers would look at it in terms of the conversions between the two formats, and say that each format can be converted to the other losslessly, and that it's possible to make a round-trip without losing any data. It's not a standard usage, but if you said that the two formats were round-trippable wrt each other, you would probably be understood. That said, you should still explain what that means!


What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion? After reading Lamport Algorithm for Mutual Exclusion, I can not understand the purposes of reply messages. I think they are not necessary because the assumption of the algorithms is that all messages are delivered in order and no message is lost. In addition to that, the algorithm uses Lamport logical clock, so the requests will always be processed in order.

I believe the purpose is to fulfill the first condition of entering the critical section (site $S_i$ must receive a message from all other sites with timestamp greater than its own request) in case some other site never requests to enter the critical section.

If $S_i$ sends a critical section request to $S_j$, but $S_j$ never requests the critical section and doesn't send a reply, $S_i$ will never receive a message from $S_j$ thus causing it to wait forever to enter the critical section. In this scenario, $S_i$ cannot know for sure that $S_j$ does not have a pending request with a timestamp lower than $S_i$'s request.


Showing NP-hardness by reducing from a search problem I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem.

But we can also have NP-hard search problems. For example, it is claimed in the introduction of this paper, that finding a $k$-coloring of a $k$-colorable graph is NP-hard for $k \geq 3$. Let me call 3-COL-SEARCH the problem in which we are given a 3-colorable graph $G$, and have to output a valid 3-coloring for $G$.

For concreteness, suppose $X(G)$ is asking for the minimum number of operations to achieve something fancy for a graph $G=(V,E)$. We wish to show computing $X(G)$ is NP-hard. Technically, I should be able to do this by a reduction from 3-COL-SEARCH.

But what would we show in the reduction now? If this was a decision problem (3-COL) we are reducing from, perhaps we'd be showing "the graph $G$ is 3-colorable if and only if $X(H) \leq |V|$, where $H$ is some new graph we construct". But now I'm confused: would we show "we can find a 3-coloring for the 3-colorable graph $G$ if and only if $X(H) \leq |V|$"?

Is there perhaps some paper or resource that gives an example of such a reduction as well? I'd guess this is not so exotic.

Basically, you pick any convenient decision problem known to be NP-complete and reduce from that problem to 3-COL-SEARCH.  In other words, informally, you prove that if it was possible to solve 3-COL-SEARCH in polytime, then it'd also be possible to solve that other problem in polytime.

For your particular example, a very convenient choice of decision problem is 3-COLORABLE.  It's known that 3-COLORABLE is NP-complete.  Now you just need to reduce 3-COLORABLE to 3-COL-SEARCH.  The reduction will be super-easy: take the hypothetical algorithm for 3-COL-SEARCH, run it on the graph, check whether it has output a valid 3-coloring or not, and if yes, output "Yes", otherwise output "No".  This will be a valid solution to the decision problem 3-COLORABLE, if the hypothetical algorithm correctly solves 3-COL-SEARCH.

Usually you can do the same thing with other NP-hard problems: often there is a natural decision problem associated with it, so you prove that the decision problem is NP-complete and then find a reduction from the decision problem to your search problem.

The other thing that's going on in your example is that, the way you defined 3-COL-SEARCH, it's a promise problem.  A promise problem is one where we have a promise that the input will be within some set -- and the algorithm is allowed to do anything it likes on other inputs.  Promise problems can be a bit counter-intuitive, or at least harder to think about, from a complexity-theory perspective, so if you're able to frame your problem so it's not a promise problem, I think that will usually be cleaner.


Counting common values in two arrays given two arrays of integers A and B of size m, with values in the
  range [-n,n]. I want an algorithm to count how many common values are
  in A and B , if a value is repeated we only count it once , for
  example :  $A=\{2,2,14,3\}$ and $B=\{1,2,14,14,5\}$ the algorithm
  should return 2 . Problem is I need to do this in $O(m)$ time.

My attempt was to create an array $C$, of size $2n$.
and increment all the values of $A$ and $B$ by $n$, and count the values of $A$ like:
$C[A[i]] = 1$
that would take me $O(m)$ time , and $O(1)$ time to create the array.
then going over $B$ and counting how many $1's$ I encounter in $C$.

So far it sounds good, however I have no idea what's in $C$ in the first place and it could be that there's a $1$ in there already and that would increment the counter falsely , and initializing $C$ would take $O(n)$ time.

Any ideas?
Thanks ahead.

Try the following algorithm:

For $1 \leq i \leq m$: $C[A[i]] = 0$
For $1 \leq i \leq m$: $C[B[i]] = 1$
Initialize answer to $0$
For $1 \leq i \leq m$:

If $C[A[i]] = 1$ then $C[A[i]] = 2$ and increment answer

Return answer


Link-cut trees: using access() and link() I am having some trouble on understanding link-cut trees, so I need some help.
Suppose that we have nodes $A, B, C, D$ and we want to do the following operations:

Link(A,B)

Link(B,C)

Link(C,D)

Following instructions of https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/MIT6_851S12_L19.pdf, I get

However, when we draw preferred paths, I should get

Am I doing something wrong when doing access(X)?
Thanks in advance.

I think you might be mixing up the represented tree, $R$, and the auxiliary tree representation of the represented tree, $T$.

Recall the definition of $LINK(v, w)$:

  $link(v, w)$ - Makes vertex $v$ a new child of vertex $w$.

This happens in the represented tree. Then to keep the auxiliary representation consistent we make $w$ the left child of $v$ because they are keyed by their depth in the represented tree (i.e. left children are higher, right children are lower in the represented tree). So your proposed linking should happen like so:

$link(A, B)$ - Make $A$ the child of $B$ in $R$. Make $B$ the left child of $A$ in $T$ (assumptions are omitted).

$link(B, C)$ - Make $B$ the child of $C$ in $R$. Rebalance the splay tree in $T$ and make $C$ left child of $B$.

$link(C, D)$ - Similar to step 2.

Then we have the preferred path in the represented tree is simply $D \rightarrow C \rightarrow B \rightarrow A$.


Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value The question was asked in an interview, and I'm not sure if this is the most optimized answer, but here goes-

You have an undirected acyclic graph, where each node has a non-negative value x and the edges have 0 value. You need to find a path with any number of nodes on it such that the total sum of all node values is exactly k. There are N nodes in the graph. You can start at any node.

I gave the brute-force solution for this problem, which is basically do a dfs on each node until you find a valid "root" node, such that it has a path to one of the other nodes, with a total sum being k. The time complexity of this solution would be n^2, since we are doing DFS on each node.

The question was posed as a delivery problem, where you have N connected houses, each having a package of weight within the range 1 to k, and the truck can start at any house and should follow a path, and has to pick the package from every house that is on that path. The weights should sum exactly to k.

There's a solution in pseudo-polynimial $O(nk)$. First, you can safely delete every node of the graph with weight bigger than $k$.  For each node $v$ keep an array $A[v]$ of size $k$, where $A[v][i]$ says how many children $u$ of $v$ have paths that start in $u$ (a node $u$ is the start of a path $u_1, \ldots, u_m$ if $u = u_1$ and $u_{i+1}$ is a child of $u_i$ for all $i$) and whose weight is exactly $i$.  Also, let $w$ be the function that maps nodes to their weights.

Your graph is a bunch of trees, and you can process each of them individually. For a given tree, choose an arbitrary node as the root, and do dynamic programming in the following way to fill up $A$. For any node $v$ we have that

$$
A[v][i] = \sum_{u \text { is a child of } v} \big[ A[u][i - w(u)]  \geq 0\big]
$$

If for some $v$ it holds that $A[v][k-w(v)] \geq 1$ we are done. This corresponds to the case where there is a path that starts in $v$ and has weight $k$. It could be however, that the path of weight $k$ we are looking for does not start in $v$, but it rather has $v$ as its closest node to the root. In order to detect this, we can process the tree from bottom to top. We denote the parent of a node $u$ as $p(u)$. For each node $u$, if there is some $j$ such that $1 \leq j \leq w(u)$ and $A[u][j-w(u)]$, then we know there is a path of weight $j$ that starts in $u$. We call this path $\pi_1$. So we only need to check whether there is a path $\pi_2 \neq \pi_1$ of weight $k-j-w(p(u))$ that starts from a child of $p(u)$. This corresponds to check the value of $A[p(u)][k-j-w(p(u))]$. Note that it could happen that $w(\pi_1) = w(\pi_2)$, in which case we would need to check whether $A[p(u)][k-j-w(p(u))] \geq 2$.

Thanks to @j_random_hacker for the suggestions on how to improve the algorithm.


Question about pointer in PCB structure and meaning of job queue PCB structure exists inside kernel area. And in ready queue, which is Linked List, each Node of the queue is PCB.
And this mean PCB Node has the next address of PCB in the queue, right?? Then My question is this..

Does PCB structure has pointer field that has address of next PCB structure??

According to Wikipedia, Job Queue consists of process waiting to be allocated to Memory. But, in terms of 'process',
process means the program loaded on the Memory waiting to be executed or being executed. And how can Job Queue consists of process, that is not loaded onto the memory(I think we can't say it is process because it is not on the Memory)

PCB structure exists inside kernel area. And in ready queue, which is Linked List, each Node of the queue is PCB.

This is correct, however in most operating systems, ready tasks are sorted by priority to ensure that the most important task will run next. So the design of the ready queue may be more sophisticated than this in practice.

Does PCB structure has pointer field that has address of next PCB structure??

This is the way that it's usually done. Of course, if it is implemented as a doubly-linked list, it will have a "previous" pointer too.

According to Wikipedia, Job Queue [...]

I can see why this may be confusing. The Wikipedia page that you're talking about is about batch processing systems. This is a related idea, and there are batch processing systems without user interaction, but it's not relevant to what you're trying to understand.


mapping function to map the index of Lower triangular matrix If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the mapping function to map the index of Lower triangular matrix Aij in 1D.

Index of $A_{i,j}$ in $1$-$D$ will be $\frac{i(i-1)}{2} + j$ assuming $1$ based indexing.


How does a=2 twice in this code sample? I am just starting out learning code.

The output of the following code is OOOXOXOO, but I don't see how X can be printed twice. How does a=2 more than once?

a = 1
while a < 3:
    b = 1
    while b < 3:
        if a == 2:
            print ("X"),
        print ("O"),
        b = b + 1
    print ("O"),
    a = a + 1

Think carefully about the flow.

Your innermost While loop runs through b = 1, 2, each time it hits.

It does this for EACH value of a in the outermost loop.

So when a == 2, we progress inward and run through that loop twice. a == 2 both times.


Validity of □(P→ Q) → (◊P → ◊Q) in linear temporal logic How can I prove that $\Box(P\rightarrow Q)\rightarrow (\Diamond P\rightarrow\Diamond Q)$ is valid in linear temporal logic (LTL)?

Think about what the formula means. The first part says that it's always true that $P$ implies $Q$; the second part says that, if $P$ is true somewhere, then $Q$ must be true somewhere, too. Well, if $P$ implies $Q$ then, if $P$ is true somewhere, then $Q$ had better be true in that place, too!


MIPS control signal table(R-type add) I've been going through the control signal table and I noticed something
confusing on when I should set the value as 'don't care' or 0 for control signal.

For example when doing the R type add instruction, we don't go through the
data memory. When we are done with addition inside the ALU, the result will justbypass the data memory and will be written on the destination register.

So I thought, being 'don't care' for the MemWrite and MemRead would also be ok
rather than being 0. But on the signal table, it says 0.

I wonder where the differences are made when deciding rather to put 'don't care' and 0.

Thanks!

For certain instructions in certain pipeline stages, we don't care about the results or operation of one or more of the hardware's many functional units.

Let's say the processor implementation has several functional units, e.g. in the ALU, for addition/subtraction, one for and/or, one for multiplication, one for division, one for shifting, and maybe even (separate from the ALU) one for computing addressing, e.g. combined shift & add for the various load & store instructions.  there may also be a completely separate adder next to the PC for doing pc-relative branches.

All that hardware is always there, but not all is always being used.

So, for example, when doing an unconditional branch instruction, the regular ALU is still there doing something, but we don't care about it.  All we have to do is ignore the unit's output, e.g. don't write it to a register.

So, at the times when we don't care about the regular ALU's output, we also don't care about the signals going into the ALU — the source operands, and the code that says whether to add vs. and vs. other.  We need to ignore not just the ALU's output, then but also any signals like overflow.  However, that is pretty easy to do, so sometimes this is done (ignoring output while giving "don't care" input), instead of instructing the ALU to do something specific during don't care, like adding 0 + 0.

However, when it comes to memory we never want to initiate a memory reference with a potentially garbage address, even a read, let alone a write, which could be destructive of program state.  Keep in mind that the memory reference goes thru the cache and then potentially off-chip, to the memory devices, and/or to I/O devices.  We don't even want to issue a read to a known or hard-coded address (like 0).  If the instruction isn't a memory reference, we should not touch memory at all!!  And we do that by forcing both the read and write signals to 0.


If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well? I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-complete, can I say that A is NP-complete too?
Actually, I would say yes, because if I can convert a problem that I don't know how to solve to one that I know, then that problem must be at least as hard as the reducible one. So, A should be NPC.
However, I got to another idea that I can convert an easier problem to a hard one, so I could say that A is NP, but I couldn't guarantee that it's NPC.
Which ideia is correct?

You can indeed not guarantee that A is NP-complete.
Problem A: Given is a single number X ≥ 1. Is X equal to 1? Clearly in P, and in NP, but of course not NP-complete.
Problem B: Given n items of size $s_i$ ≥ 1, a bin size B ≥ 1, and an integer k ≥ 1, can the n items be put into k bins of size B? This one is NP complete.
A can be reduced to B in polynomial time: Just take 1 item of size X, let B = 1 and k = 1.


How can one search in O(log n) time in a red-black tree? How does the search operation for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ rotations, but I was specifically interested in a good description of its search operation.

The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are not special.

The complexity of the search operation is equal to the height of the tree.

Different varieties of binary search trees differ in what guarantees on height of the tree they give, and in how exactly they maintain these guarantees. Red-black trees and AVL trees give you guaranteed O(log n) height, which is why search is O(log n).


What is the difference between strong normalization and weak normalization in the context of rewrite systems? In the context of rewriting systems, how does strong normalization differ from weak normalization?

Weak normalization means that any term has a terminating rewriting sequence, i.e. admits a finite amount of rewritings which lead to a normal form (no more rewritings from that).

Strong normalization means that any term can never be rewritten infinitely many times. Any maximal rewriting sequence eventually reaches a normal form (hence it is finite).

For instance:

$$
    S \rightarrow (SS) \qquad
    S \rightarrow A
$$

is weakly normalizing (given any term, we can rewrite every $S$ into an $A$, after which normal form is reached) but not strongly normalizing ($S \rightarrow (SS) \rightarrow ((S S) S) \rightarrow \cdots$).

It is immediate to prove that strong normalization implies weak normalization.


Why do Shaefer's and Mahaney's Theorems not imply P = NP? I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ?

Here's my reasoning:  Create a language $L$ which is equal
to SAT intersected by an infinite decidable sparse set.  Then $L$ must also be
sparse.  Since $L$ it is not trivial, affine, 2-sat, or Horn-sat, by
Shaefer's theorem it must be NP-complete.  But then we have a sparse
NP-complete set so by Mahaney's theorem, P=NP.

Where am I going wrong here?  I suspect that I am misunderstanding/misapplying Shaefer's theorem but I don't see why.

Schaefer's theorem applies only to a specific type of languages, those of the form $\mathrm{SAT}(S)$ for a finite set of relations over the Boolean domain or $\mathrm{CSP}(\Gamma)$ for a finite constraint language over the Boolean domain (the two notations are equivalent; see the Wikipedia page for a description). Any other language is not covered by the theorem, and the theorem has nothing to say about it. In particular, Schaefer's theorem doesn't say anything about your language $L$.


Grammars and Parsing: Ambiguity in Sequences BACKGROUND

I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches.

Given terminals:

"a": KEYWORD
"b": INTVAL
"c": DECVAL
"d": STRVAL

Given rules:

"E": VALUE <- INTVAL
"F": VALUE <- DECVAL
"G": VALUE <- STRVAL
"H": VALUES <- VALUE
"I": VALUES <- VALUES VALUE
"J": LINE <- KEYWORD VALUES

Not complicated, right? This specific subset of terminals and rules should be able to parse the following line:

KEYWORD DECVAL DECVAL DECVAL DECVAL

In other words, a keyword followed by one or more values should be a grammatically-correct line. DECVAL tokens should reduce to VALUE tokens, which are in turn aggregated into a series of VALUES, at which point the line reduces under rule "J".

PROBLEM

However, consider the following parse state, after the first two tokens have been shifted and the lookahead is the next DECVAL:

KEYWORD DECVAL | DECVAL

This is a shift-reduce conflict, because it could shift the lookahead DECVAL under rule "F" or reduce the DECVAL on top of the stack under the same rule ("F"). By default, most parsers will perform the shift--in which case the series will never reduce because there is a DECVAL too "deep" on the stack.

QUESTION

But how would you (for example) define a precedence in such a way as to indicate a specific rule should reduce when in conflict with itself? Is that even a good idea? Based on my own limited understanding, there should be a way to restructure the grammar rules, right? But it's not obvious to me what that is.

This parser state

KEYWORD DECVAL DECVAL
               ^
               |---------- Lookahead

is not a conflict because a shift action is not possible. There is no production in which A DECVAL follows another DECVAL. There is not even a production in which a VALUE follows another VALUE. Before the lookahead DECVAL can be shifted, the DECVAL at the top of the stack must be reduced to something which can be followed with DECVAL.


Algorithm for idempotent algebra A boolean algebra expression can be converted into an idempotent algebra using
$$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$

where $\otimes$ is the idempotent product (no powers).  For example, $$(a+b)\otimes(a-b) = a -ab +ab - b = a-b.$$

The CNF formula

$$\phi = (a\vee b) \; (b \vee c)(b \vee \bar c)(\bar b \vee   \bar c) \; (a \vee c)(\bar a \vee \bar c)$$

can be converted into what I would call the idempotent expression
$$\phi = (a + b - ab)\otimes (b-bc) \otimes (a+c-2ac).$$

This expression expands to give $\phi = ab - abc$.  I would like an algorithm that, given a CNF formula as input, outputs the term with the lowest homogeneity.  In this example, the oracle would return $ab$.  (If there are multiple terms all with minimal homogeneity, the algorithm can return any one of them.)

Question 1: What is the complexity of this task?  How high in the polynomial hierarchy is it?

Secondly, given a different idempotent expression $$\phi = ac+ad+bc+bd-abc-abd-2acd-2bcd + 2abcd,$$

I am interested in summing over the terms with equal homogeneity. By letting all variables be $\epsilon$ we get
$$\phi = 4\epsilon ^2 - 6\epsilon^3 + 2\epsilon^4.$$
This yields a homogeneity vector of $[0,0,4,-6,2]$.

Question 2: What is the complexity of computing the homogeneity vector, given an idempotent expression as input?   How high in the polynomial hierarchy is it?

Let us consider the following decision version of your first problem:

  Given a SAT instance, does its multilinear representation have a term of degree at most $d$?

I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones.

Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear representation of the instance. Substituting 1 for the variables in $m$ and 0 for the variables outside of $m$, we get 1, that is, that the instance is satisfied. This shows that if the multilinear representation has a term of degree at most $d$, then the instance has a satisfying assignment with at most $d$ ones.

Now suppose that all terms in the multilinear representation have degree more than $d$. If we substitute any assignment with at most $d$ ones, then all monomials equal 0, and so the assignment falsifies the instance.

Therefore the decision version is equivalent to MIN-ONES-SAT, which is the following problem:

  Given a SAT instance, does it have a satisfying assignment with at most $d$ ones?

The problem is in NP (it is easy to count the number of ones in a satisfying assignment), and it is clearly NP-hard (take $d = n$). Hence the problem is NP-complete.

Using an NP oracle, we can easily find a monomial with minimal degree, equivalently, a satisfying assignment with the least ones. Just substitute a 0 in one of the variables, and see if it increases the minimum weight of a solution. If so, set this variable to 1, otherwise set it to zero, and continue to the next variable. This answers your first question.


Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?) I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially taking exponential time (2^P(n) where P is polynomial).

Moreover, can it be generalised to EXPTIME in general?

The reason I am asking this is that I wrote some programs to solve degenerate cases of an NPC problem, and they can consume very large amounts of RAM for hard instances, and I wonder if there is a better way. For reference see https://fc-solve.shlomifish.org/faq.html .

Generally speaking, the following is true for any algorithm:

Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain nothing by running more than $2^{f(n)}$ time.

It follows that:

  $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

The statemement is known as part of the relations between the classes, as depicted by the following diagram:

The explanation is simple: a problem $Q$ $\in$ $\mathbf{NP}$ has a polynomial length certificate $y$. An algorithm that tests all possible certificates is an algorithm that decides $Q$ in time $\large 2^{n^{O(1)}}$.

Its space requirement is:

$y$ (polynomial in $n$)
space required to verify $y$. Since $y$ is a polynomial certificate, it can be verified in polynomial time, hence cannot possibly require more than polynomial space.

Since the sum of two polynomials is also a polynomial, $Q$ can be decided with polynomial space.

Example:

Suppose $\varphi$ is an instance of 3-CNF on literals $x_1 \dots x_n$, with $m$ clauses. An assignment $f$ is some function $f:\{x_1\dots x_n\} \rightarrow \{0,1\}$.

It holds that:

There are $2^n$ different assignments.
Given an assignment $f$, it takes $O(m)$ time to calculate the value of $\varphi$, therefore it cannot require more than $O(m)$ space.

So an algorithm $A$ that checks all possible assignments will use polynomial space, run in exponential time and decide 3-SAT.

It follows that:

3-SAT $\in \mathbf{PSPACE}$, and since 3-SAT is NP-Complete, $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$


The expectation of the total number of pairs of keys in a hash table that collide using universal hashing I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$

where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys in position $j$. I don't understand why we can directly conclude that

$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]\leq{n\choose{2}}\frac{1}{m}
$$

I understand that since $h$ is randomly chosen from a universal hash function family, $\Pr{(h(x_i)=h(x_j))}\leq{\frac{1}{m}},\forall{i\neq{j}}$. I don't understand why we can use the total number of pairs (the combination part) directly because if $h(x_i)=h(x_j)$ and $h(x_j)=h(x_k)$, then we have $h(x_i)=h(x_k)$ immediately instead of a probability of $\frac{1}{m}$.

Someone can help me out? Thanks!

I'm assuming that there is a (non-uniformly) random function $h\colon [n] \to [m]$, and $n_j$ is the number of preimages of $j$.

Notice that $\binom{n_j}{2} = \sum_{1 \leq a < b \leq n} 1_{h(a) = h(b) = j}$. We have
$$
\mathbb{E}\left[\binom{n_j}{2}\right] = \frac{1}{2} \sum_{a \neq b} \Pr[h(a) = h(b) = j] = \frac{1}{2} \sum_{a=1}^n \sum_{b \neq a} \Pr[h(a) = h(b) = j] \leq \frac{n-1}{2m} \sum_{a=1}^n \Pr[h(a) = j].
$$
Summing this over $j$, we get
$$
\sum_{j=1}^m \mathbb{E}\left[\binom{n_j}{2}\right] \leq \frac{n-1}{2m} \sum_{a=1}^n \sum_{j=1}^m \Pr[h(a) = j] = \frac{n(n-1)}{2m} = \frac{1}{m} \binom{n}{2}.
$$


Understanding the Sipser-Gacs-Lautemann theorem The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input.

The class $\Sigma^p_2$ contains all the languages for which there is a polinomial time Turing machine $M$ and a plynomial function $q : \mathbb{N} \rightarrow \mathbb{N}$ such that:
$$ x \in L \iff \exists u \in \{0,1\}^{q(|x|)} \forall v \in \{ 0,1 \}^{q(|x|)} M(u,x,v)=1$$
Define $\Pi^p_i=\{\bar{L} : L \in \Sigma^p_2 \}$

The theorem states that the class $BPP$ is contained by the intersection of $\Sigma^p_2$ and $\Pi^p_2$.

To prove the theorem it is proved that for every set $S \subseteq \{0,1\}^m$ with $|S| \leq 2^{m-n}$ and every k vectors $u_1, \ldots, u_k$
$$\bigcup_{i=1}^k(S+u_i) \neq \{0,1\}^m$$
Where $S+u = \{ x+u : x \in S \}$ and + denotes addition modulo 2 i.e. bitwise XOR.

It is also proved that for every set $S \subseteq \{0,1\}^m$ with $|S| \geq (1-2^{-n})2^m$ and every k vectors $u_1, \ldots, u_k$
$$\bigcup_{i=1}^k(S+u_i) = \{0,1\}^m$$

I don't get why this claims imply that if a language is in $BPP$, then
$$ \exists u_1, \ldots,u_k \in \{ 0,1 \}^m \forall r \in \{ 0,1 \}^m \bigvee_{i=1}^k M(x,r \oplus u_i) = 1 $$

How does the claims about sets of binary strings imply the computation above?

What I don't understand is how the translations preserve the original random strings and how can a small set of translates cover all possible random strings.

First of all, it's not clear to me that every language of the form given by your last formula is in BPP. Fortunately, we only need the reverse direction: every language in BPP can be written in this form. This will show that BPP is contained in $\Sigma_2$. Since BPP is closed under complementation, this will complete the proof.

Start with a BPP machine with some small error probability. For appropriate $k$ (depending on the error probability), a union bound shows that the formula doesn't hold. The other direction looks more complicated, and this is probably where the other results they prove come in. Basically, you have a set of good random strings covering almost all strings, and you want to cover all of them by finitely many translates of the set. Perhaps that's what these lemmas show.


Why is this function computable I'm struggling to understand why this function is computable.
This is the requirement:

Consider the following program P, written in a pseudo-C language:

P:
{
    int x, y, z;
    read (x, y, z);
    while (x != y)
    {
       x = x - y;
       z = z + y;
    }
    write z;
}

Let $f(x, y, z)$ be the function computed by P. Is the following function g computable?

$g(x, y, z) = \begin{cases}
  1 & f(x,y,z)\ halts \\
  0 & else
   \end{cases}
$

Whenever I encounter a problem like this, I try to imagine a program that does exactly what $g$ does. In this case, a P2 program that checks if $f(x,y,z)$ halts.

Now, P halts if, basically, $x>y \ and \ y=1 $ or $x=y$ (there are probably more cases). In the other cases, P would just remain in the while loop, so $f$ is not total.

But how would P2 return $0$ if P wouldn't even halt? P2 would have to wait, and never return 0, so for some values the function is not computable, and x,y,z isn't always computable.

What am I thinking wrong here?

You can check that P halts iff $x = ty$ for some integer $t \geq 1$. Hence $g(x,y,z)$ is just the following function:
$$
g(x,y,z) = \begin{cases} 1 & \text{ if $x = ty$ for some integer $t \geq 1$}, \\ 0 & \text{ otherwise.} \end{cases}
$$
Given integers $x,y$, it is not hard to check whether $x = ty$ for some integer $t \geq 1$. Hence $g$ is computable (even in polynomial time!).


Stroke Width Transform: Gradient Direction and Rays I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .

Having a simple image with random texts, that underwent gray scaling. Then I have produced two edge maps using two different algorithms for output comparison (for later) , Sobel and Canny (I'm also planning on Prewwit or other edge detection algorithms). I also have gradient maps x and y, using sobel.

Now, up to this point I got lost on the second paragraph of section 3.1 of the paper, which is getting a gradient direction and finding the other point for the ray:
" ...then dp must be roughly perpendicular to the orientation of the stroke... " and " ... dp(dq = -dp±π/6) ... ". Does this mean I'll have to take a wild guess as to where the direction of dq is? or have I misinterpreted it?

You basically have to sample points from p in the direction of p's gradient dp.
You get the dp from the x and y gradient maps. And sample from where? from the edge map and the gradient maps. First check if it is a edge from the edge map. If it is not then take another step in the dp direction. If it is an edge then compute the gradient direction from the x and y gradient map. If that gradient points back to p with about π/6 of tolerance then that is the q you are looking for.

Be careful with back over while vs white over black. The gradients will point in opposites directions when you invert the image. That is why you have to run the algorithm twice since SWT does not know which case are we dealing with. One with the original gradient directions and another flipping the gradients in the opposite direction.


How to solve an optimization problem that deals with the optimal combination of given ratios? I'm volunteering for a non-profit, and was asked to write a program for this problem, but I'm having a little trouble tackling it. Here's the problem:

So they're a daycare, and they get paid by the government depending on specific ratio's of staff to children. Here are the possible ratios and their pay:

one staff to 3 children (3:1). Pays 14.71 dollars per hour
one staff to 2 children (2:1). Pays 9.10 dollars per hour
one staff to 1 child (1:1). Pays 7.28 dollars per hour

With every possible number of staff and number of children in the daycare, there is a combination of ratios that will give the maximum profit. How do I find those ratios? Are there any clever ways to approach this problem?

The inputs of this ideal program would be number of staff and number of children, and the output would be the combination of ratios that produces the maximum profit.

If the number of children $n$ is fixed and there is no limit on the number of staff members you can potentially hire, here's one way you can maximize the amount the government pays you:

You can use linear programming (LP).  Let $s_1$ denote the number of staff you hire to manage one-child classrooms; $s_2$ the number of staff you hire to manage two-child classrooms; and $s_3$ the number of staff you hire to manage three-child classrooms.  The number of children you can handle, with this configuration of staff, is $s_1 + 2s_2 + 3s_3$.  Also, the amount paid by the government is $7.28 s_1 + 9.10 s_2 + 14.71 s_3$.  You want to maximize the payoff, subject to the constraints $s_1 \ge 0$, $s_2 \ge 0$, $s_3 \ge 0$ and to the constraint $s_1 + 2 s_2 + 3 s_3 \ge n$ (i.e., you have capacity to take care of $n$ children).

Of course, this formulation is silly, because under this formulation the way to maximize your profit is to maximize the number of staff chosen.  That's because this formulation doesn't take into account the cost of hiring staff or any other consideration.  So you'll need to adjust it to incorporate the additional constraints you have.

Fortunately, this LP formulation makes it easy to incorporate additional constraints.  For instance, suppose there are only 100 qualified people who you'd possible be willing to hire as staff, so you simply can't hire more than a total of 100 staff members.  That can be handled by adding the additional constraint $s_1 + s_2 + s_3 \le 100$.

In practice there's probably some cost per staff member you hire, so in practice we probably want to maximize not the amount the government pays us, but the amount of "profit" left over after paying the staff members.  Suppose each staff member costs 5 dollars per hour.  Then you would adjust the above by maximizing the revenue minus the costs, i.e., $(7.28 s_1 + 9.10 s_2 + 14.71 s_3) - (5.00 s_1 + 5.00 s_2 + 5.00 s_3)$.

In practice you want to only hire an integer number of staff, so you might want to use an integer linear programming (ILP) solver rather than a LP solver.

I still question whether this is the right metric for a non-profit to be maximizing.  Instead of focusing only on "profit", I would anticipate that a non-profit would care about the benefit to stakeholders or soceity: e.g., the benefit to the children served, or the number of children served, or some combination of benefit and leftover "profit".  For instance, all else being equal, is the benefit greater if a child is cared by a single staff member rather than sharing a staff member with two other children? I suspect so, but that isn't incorporated in your "profit maximization" formulation.  Thus, I suspect the right objective function to maximize might be something different, chosen to take into account that the goal of a non-profit is not to derive a profit but to accrue some social benefit.


How can a set offer better search performance than an array While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer faster performance than arrays do when it comes to testing for membership."

The author doesn't mention the underlying data structure and as it stands, I don't see how the second part of this statement can be inferred from the first.

If the NSSet class is implemented using a hash table, I agree that it will have faster lookup performance than an NSArray class but in principle both classes could be implemented using arrays, in which case both would have a lookup performance of O(n).

Am I missing something or is this just an incomplete statement?

I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order.  Because NSSets don't offer those kinds of accesses the implementation is free to use hashing, trees or anything else that gives speedier membership checks.


How a TM can represent any algorithm? As I remember:

A decision problem is a problem that has the answer yes or no.
An algorithm (in the context of automata theory) answers yes or no; it halts on all inputs, accepted or not.
A TM represents an algorithm. The TM accepts an input string and executes with that input. If the machine ends up in an accept state, the answer is yes, otherwise no.

How does a yes/no problem relate to general algorithms we are doing that have more than yes/no problems? Or is that every problem can be thought as a yes/no problem, i.e. is this a function f produce 5 (or whatever input) with input 2 (or whatever output)?

Don't forget that the final content of the tape can be treated like the output of the algorithm that the TM computes; in other words, a TM is able to compute a function: there is no "reject state" but only an "accept state" and the function result is the content of the tape at the end of the computation.

But if you want to learn more on the relation between decision problems and function problems , (quickly) read the Decision Problem - Equivalence with functions problems entry on Wikipedia, and then search some lectures online on the subject.