How to detect plurals in English sentences? I'm wondering how to detect English plurals in natural language sentences.

Such as:

fish
computers
houses
...

Using Earley parsing I'm able to get to the s or no-s, but I have difficulties in understanding how to figure out whether the ending s is because the word is in plural form. Or whether with no-s the word is in plural form.

Is this kind of thing doable without some database of words and their plurals? I could leverage such database though, if such exists.

Morphological parsing requires a lexicon (stems and their part of speech) , morphotactics (ordering of morpheme classes), and orthographic rules (e.g. fox + PL = foxes rather than foxs).

The preferred approach is to use a composition of finite state transducers to map a surface level representation (e.g., foxes) into its lexical representation (e.g., fox +N +Pl).

For a robust method, you are better off using an existing system like Foma, lttoolbox, or SFST than writing your own system since these systems come with rich morphological data sets.


Job Scheduling decision problem I would like to know how to prove that the Job Scheduling decision problem is strongly NP-complete using 3-partition.

Input: A set of $n$ tasks of length $t_1, t_2, \ldots t_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha: \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$  which assigns each task to a processor.

The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.

We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.

In the JS$_{dec}$ decision problem corresponding to JS, the instance is accompanied by a target value $T$ and we are trying to find out if there is a solution where all the processors have a usage time limited by $T$.

Let $X = \{x_1, \dots, x_n\}$ be an instance of $3$ partition where $n$ is a multiple of $3$ and each $x_i$ is strictly between $\frac{3}{4n}\sum_{i=1}^n x_i$ and $\frac{3}{2n}\sum_{i=1}^n x_i$. The problem remains NP-hard even with this restriction.

The instance of the job scheduling decision problem has $n$ jobs, $t_i = x_i$, $k=\frac{n}{3}$, and $T=\frac{3}{n}\sum_{i=1}^n x_i$.

If the 3-partition instance is a "yes" instance, then there is a partition of $X$ into $\frac{n}{3}$ sets $X_1, X_2, \dots, X_{\frac{n}{3}}$ such that, for each $j=1, \dots, \frac{n}{3}$, $\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$.
Let $\alpha(i)$ be the index $j$ of the unique set $X_j$ containing $x_i$.
Then $\alpha$ is an assignment for the job scheduling instance in which, for each $j=1,\dots,\frac{n}{3}$,  $u_j = \sum_{i : \alpha(i)=j} = \sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i = T$. This shows that the job assignment instance is a "yes" instance.

If the job scheduling instance is a "yes" instance, then let $\alpha$ be a corresponding assignment. For each $j=1,\dots,\frac{n}{3}$:

$|\{i : \alpha(i)=j\}| \le 3$, as otherwise $u_i > 4 \cdot \frac{3}{4n}\sum_{i=1}^n x_i = T$.
$|\{i : \alpha(i)=j\}| \ge 3$, as otherwise $u_i < 2 \cdot \frac{3}{2n}\sum_{i=1}^n x_i = T$, implying that $\max_{j' \neq j} u_j \ge \frac{\sum_{i=1}^n x_i - u_i}{\frac{n}{3}-1} > \frac{\sum_{i=1}^n x_i - T}{\frac{n}{3}-1} = \frac{\frac{n-3}{n}\sum_{i=1}^n x_i}{\frac{n-3}{3}} = \frac{3}{n}\sum_{i=1}^n x_i = T$.

As a consequence, the sets $X_1, \dots, X_{\frac{n}{3}}$, where $X_ j = \{x_i : \alpha(i)=j\}$, contain $3$ elements each and form a partition of $X$. Moreover, $\sum_{x \in X_j} x = u_j \le T = \frac{3}{n}\sum_{i=1}^n x_i$ and an argument similar to the one above shows that $\sum_{x \in X_j} x \ge \frac{3}{n}\sum_{i=1}^n x_i$. This proves that $\sum_{x \in X_j} x = \frac{3}{n}\sum_{i=1}^n x_i$ and hence that the $3$ partition instance is a "yes" instance.


Using A* path finding is giving me inaccurate results So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of the must pass nodes, to make sure they always go to each of these. My method for deciding which order nodes come in for their individual run through the algorithm is to use a distance between the person on the graph and the remaining nodes, the smallest distance will be put through the algorithm first.
Here is a diagram of what this looks like:

The person must visit the blue node last, which is why the  distance hasn't been included for that node.
As you can see, the bottom right pink node is the first node to go through the algorithm since they have the smallest distance.
Here is where i come across a problem:
If the algorithm tries to find a path to this node on the bottom right, the person will actually travel across the edge with weight 1, since the distance between the node on the other side of the edge with the weight of 1, to the end node, is 6.25 (using a ruler by hand and making sure the diagram stays the same size on my screen at all times for all distances measured).
Would this not mean the person ends up travelling through all of the other must pass nodes on the graph before they even reach the first must pass node?
Is my criteria for picking the next node for the algorithm wrong?
What am i doing here that is wrong? Or is this a fault with A*?
Note: The weights on each edge are measured fairly accurately by hand with a ruler, so i doubt that is the issue.
EDIT:
The one question i need answered is this. What is the best way to decide which node to path find for first? I'm starting to doubt if Euclidean distance is the best choice here.

Let's start this off with a quick review of A*. A* is a pathfinding algorithm that builds on some of the benefits that greedy searches and dijkstra searches have. Make sure that your implementation correctly combines both basic heuristics A* uses:

g(N) = the cost to get from the starting node to the next node N
h(N) = the estimated cost to get to the goal from N

By expanding the nodes with the lowest g(N) + h(N) first, A* quickly converges on the most efficient path when some costs are unknown. It's great for any graph search and I've used it to implement backtrackers for constraint solving.

Now, our review's over. Let's get to your problem!
You're trying to have a character visit certain subgoal nodes on the graph and finish on the goal node. This is actually a variant of the famous "Travelling Salesperson Problem". It is an example of an NP-complete problem, which means that even A* isn't going to help you solve it quickly; you'll be doing a lot of backtracking or trial-by-error no matter what algorithm you use.
In order to adapt A* to this problem, you will need to rewrite the logic for exiting the search. Instead of checking if N_i == Blue_1, you need to check if {Blue_1, Pink_1, Pink_2, Pink_3} is a subset of the path.
Right now your calculation for h(N) is based on Euclidean distance from Blue. Not a bad start, but it's not as efficient as simply setting h(N) = 0 on this problem; dijkstra search is better than a too-greedy A*. Because you aren't actually aiming for the blue node, you have an 'inadmissable' h(N) so you'll miss the optimal path sometimes:

"If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal."

You can get an admissible heuristic by setting h(N) = the distance to the nearest sub-goal. Once all sub-goals are reached, set h(N) = the distance from the blue goal. This means that each node in the pathfinder needs additional metadata. Add a field to pathfinding nodes that tracks which goals have already been hit.


algorithm time analysis "input size" vs "input elements" I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm

Seems that input length for the algorithm depends a lot of the kind of data and the algorithm you are talking about.

Some authors refer to input length to the size of characters that are required to represent the input, so "abcde" if use as input set in an algorithm will have an "input length" of 6 characters.

If instead of characters we have number (integers for instance) then sometimes the binary representation is use instead of characters so the "input length" is calculated as $N*log(L)$ (Being L the Max number in the input set).

There are other problems that even if the input set are numbers, they describe the "input length" as "decision variables", so for a input set of length N with numbers in the range $0-2^{32}$ the input length is just N (subset sum for instance), or even more complicate the number of binary place values that it takes to state the problem (what I believe is just the same as $N*log(L)$)

So:

it depends on the algorithm?
What means and when to use each input length "version"
Is there are some rule I can use to decide which one to use?

In the most formal sense, the size of the input is measured in reference to a Turing Machine implementation of the algorithm, and it is the number of alphabet symbols needed to encode the input.

This is of course rather abstract, and is very difficult to work with in practice, or at least very annoying - we would need to consider how we're going specify delimeters etc. etc. What happens normally in practice then is that we look for a proxy measurement of the size of the input - something more convenient and accessible, but that does not cause any mathematical problems in our analysis.

Using your "abcde" example, it would normally be the case that the alphabet we use for the input is small, so even using the proxy measurement of $5$ characters, we known that even on a Turing Machine, we can, if we bothered, specify an input encoding that would convert "abcde" to some encoded form that had length at most $5\times c$ for some constant $c$. This expansion by a constant would typically make no difference in our asymptotic analysis, as we routinely discard constant factors.

In a different case, we often measure the size of an input graph by the number of vertices $n$. Clearly if we want to specify arbitrarily large graphs, the size of the encoded input is not simply $n$ - what happened to the edges, for example? What we do know is that we can use a reasonable encoding scheme that represents the graph in $N = c\cdot n^{2}\log n$ bits. This is a bit more of an expansion than constant, but in a lot of interesting cases, we're only dealing with things at a granularity of polynomials, and polynomials compose nicely in a lot of ways - in particular, as an example, if we determine that our running time is $O(p(n))$ where $p$ is a polynomial, then we know that there is some polynomial $p'$ such that $O(p(n)) = O(p'(N))$, so when we move back to the formal measure of the input, we're still in polynomial time.

A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n = O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^{n})$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

So while there's no stated rule for picking a proxy measure for the input size, the requirement is that the expansion or contraction of the proxy size compared to the input size should be compatible with what you're trying to prove. As a rule of thumb, constant factor changes almost never matter, small polynomial factors are normally fine and work for most of the basic theory that you see, large polynomial factors might still work in for theory, but can be a nasty surprise in practice, and exponential amounts of change are normally way too extreme.


$P\ne BPP$ implies $P\ne NP$ Prove: $P\ne BPP$ implies $P\ne NP$.

Obviously $P\subseteq BPP$ so the assumption is really $BPP\subsetneq P$. I'm trying to show the implication by contradiction. Let's assume that $P=NP$ and let's look at some language $L\in BPP$. Then, it has a proper probabilistic TM which decides it.

At first, I thought that I could just show some $NP$ machine which uses the $BPP$ machine but a relation between the two classes it not yet known, so it's probably not what I'm supposed to do.

We did learn Adleman's theorem and I think it could be used here (though we haven't define $P/poly$). Adelman's theorem claims that for every $x$ there's a $y$ s.t.

$$x\in A \implies M(x,y) = 1 \\ x\not\in A \implies M(x,y) = 0$$

so it boils down to the problem of finding such $y$, but I don't think this problem (finding $y$) is in $NP$ (or even possible)

Also, I understood that one can use the polynomial hierarchy theorem but we were not taught it.

Use the fact that $\mathsf{BPP}\subseteq\Sigma_2$. Also note that if $P=NP$ then the entire polynomial hierarchy collapses to $P$.


Closed form solution for optimization problem Consider the problem of finding the real-valued matrix $C$ so that

$$\|S-AC\|_F^2\qquad(1)$$

is minimal. ($S$ and $A$ are real valued matrices and $_F$ denotes the Frobenius norm). This problem has a closed form solution of $C=A^+S$, where $A^+$ is the pseudo-inverse of $A$.

I need to control the magnitude of the elements in $C$, that is an extra regularization term $\varepsilon\|C\|_F^2$ must be added to (1). Is it there a closed form solution for minimizing

$$\|S-AC\|_F^2 + \varepsilon\|C\|_F^2\,?\qquad(2)$$

There is a closed-form solution to your problem, but first it helps to know two facts to derive the minimizer. The first fact is that we can re-write the Frobenius norm squared as a trace operation. Namely,
$$\|C\|^2_F = \text{Tr}\left[CC'\right],$$
where $C'$ denotes the transpose of $C$. The second fact is the derivative of the Frobenius norm squared, which is given by $$\frac{\partial}{\partial C} \text{Tr}\left[(S - AC)(S - AC)'\right] = -2A' (S - AC).$$

Luckily for us the derivative of sums is equal to the sum of the derivatives (i.e., the derivative is a linear function). So we can take the derivative of the objective with respect to $C$ piecemeal. We end up with $$\frac{\partial}{\partial C} \|S - AC\|^2_F + \lambda\|C\|^2_F = -2A' (S - AC) + 2\lambda C.$$ Setting this equal to 0 and solving we have, $$\begin{align*} -2A' (S - AC) + 2\lambda C &= 0 \Leftrightarrow \\ -2A'S + 2A'AC + 2\lambda C &=0 \Leftrightarrow \\ -2A'S + 2(A'A + \lambda I)C & = 0 \Leftrightarrow \\ C &= (A'A + \lambda I)^{-1}A'S,
\end{align*}$$ where $I$ is the identity matrix.

An eigendecomposition of this result gives more insight into the behavior. Put simply, you add $\lambda$ to the eigenvalues of the $A'A$ matrix which should shrink your final estimates. This is a form of regularization known as ridge regression. Except here we are applying it for multivariate multi regression instead of linear regression.


"Searching and sorting" algorithm to find the natural logarithim of a number? Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm not allowed to use strategies that involve integration, bit manipulation, approximation formulas, or Taylor Series. Instead, we're asked to generate an array of values where at least one of them will be the answer, and then to find the correct value in that array. There must be some kind of established algorithm for this, but this and other resources haven't been helpful. I'm stuck. What should I be thinking about here?

Suppose you have an array $A = [e^0, e^1, e^2, \dots]$. You do a search in this array, and try to find the biggest value in the array that's smaller than or equal to $x$.

You find this value at position $n$. What is the value of $A[n]$?
What can you say about $\ln(x)$ in relation to $n$?
Can you find the correct $n$ quickly? Does it help that $A$ is sorted?


What is the difference between shortest distance and shortest path? I am studying graph currently. I found a question, which asks for

The List A[] which shows shortest distances between $V$ and every
other vertex
The List B[] which shows shortest paths between $V$ and every other vertex

as subpoints. I don't think the question wants me to compute the same values twice, but I don't know what the difference between shortest distance and shortest path is. Can anyody explain?

As @randomA already indicated in a comment, a shortest path from $v$ to $w$ is a sequence of vertices (that describes a path from $v$ to $w$, which is shortest among such sequences).
The shortest distance on the other hand is the length of a shortest path, i.e. a number.

As a sidenote, be aware that there can be multiple shortest paths (but only one shortest distance). Thus, you might want to check, if the the question requires you to find one or all of them.


How to group intervals which overlap by some amount? I have an algorithm that generates a list of intervals. The algorithm is run m times. Lets mark the intervals as tuples (s1, e1), (s2, e2), .., (sn, en). It is possible to add the run ID to the tuple (though I don't think it helps).
The goal is to "clean" spurious ranges (appearing in few runs) and to find groups of at least k almost perfectly overlapping intervals out of m runs of the algorithm, where k is close to m. E.g. if we have 10 runs, k will be 7-9.
By almost perfectly overlapping I mean >0.95 overlap, but exact requirement is user-defined (won't be 0.5 or such). The overlap should be between all intervals in the group (i.e. intersection). However, since I am trying to translate an eyeball analysis into exact requirements this requirement might be too strong ..
The differences in the intervals generated by multiple runs of the algorithm stem from a random factor (seed) as well as slightly different ranges may passing requirements, therefore there is some 'wiggling room' in the results. It also detects some ranges infrequently (think local minima), ranges which should be ignored as spurious.
The origin of the problem is running multiple times some algorithm that searches a range for "interesting" areas. By the nature of the algorithm, each run may return slightly different ranges as well as, at times, a range not seen before.
The intervals can be viewed as integers, though in reality the intervals I get may be real number in any range. I assume I can always use a min-max scaler to, for example, have the ranges have (approximated) integer values in the 0-1000 range or similar.
Below is a (very simple) example of the problem marked as I would do manually. The three green intervals and the three red intervals should be reported as groups, whereas the other three are a group on their own. The overlap of the blue interval is too small. The Yellow interval is not "similar" to the red ones in size.

There may be problems like in the diagram below which I am not sure how to address.
The green (bottom) interval and the one above it are certainly "the same" as are the red one and the one below, however the green and red are already too far apart to be considered a group.

My initial idea was to build an interval graph. On that I can greedily find the point at which most intervals intersect, than somehow (no clear idea how yet) I would remove intervals which should not belong to the group. Once done I remove the group from the graph and repeat.
Another method I thought about, but which is O(N^3) (and not guaranteed to yield a good result) is to calculate the overlap of all pairs, selecting the best and merging (union? intersection? average start/end?) then repeating until there are no more "interesting" overlaps.
I consider an overlap interesting if it is larger than some percentage, e.g. 95%.
Are there any algorithms already achieving something similar?
Any direction someone can point me in?

Here is one interpretation of your problem:

Given $n$ observed intervals $I_1,\dots,I_n$ and $k$, find $k$ disjoint inferred intervals $J_1,\dots,J_k$ that maximizes the number of observed intervals are covered by at least one of the inferred intervals.  Say that $I_i$ is covered by $J_j$ if they have at least 95% overlap, where the overlap between $I_i,J_j$ is measured as $|I_i \cap J_j|/|J_j|$ where $|\cdot|$ denotes the length of an interval.

This problem can be solved with dynamic programming.  Sort the endpoints of the observed intervals.  For each endpoint $e$ and each $k_0$ with $0 \le k_0 \le k$, let $f(e,k_0)$ denote the maximum number of observed intervals that can be covered by $k_0$ disjoint inferred intervals that are all in $[-\infty,e]$.  Then you can write a recurrence relation for $f$: in particular,
$$f(e',k_0) = \max(f(e^*,k_0), \max \{f(e,k_0-1) + \eta : e<e'\})$$
where $e^*$ is the endpoint immediately before $e$, and $\eta$ is the number of observed intervals that are covered by $[e+1,e']$.

That said, I suspect a more pragmatic approach might be to use some standard clustering algorithm, adapted for this problem.  For instance, you might use k-means on the centers of the intervals.  Given a set of intervals that have been clustered together, you might use the median of their left endpoints and median of their right endpoints to define a new interval that serves as the clusterhead.  You can probably come up with other heuristics.  It's plausible that this might be adequate in practice.


Finding the average time complexity for a max algorithm I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max.
find_max(L):
     max = -oo # negative infinity
     for k = 0 to len(L)-1:
          if L[k] > max:
               max = L[k]
     return max

However, I'm struggling to come to a solution.  So far, this is what I have done:
I'm defining the sample space to be L containing values which are between 1 and 100, and having them uniformly distributed.
The worst-case running time is $T(n) = n + 1$ because of the initial max assignment, and the case where every element is larger than the previous one.
The best-case running time is $T(n) = 2$ which is the case where all elements have the same value, so there is the initial max assignment and one assignment in the for loop.
So, the running time is distributed between 2 and n+1 inclusive.
Then, the average-case running time is:
$E[t_{n}] = \sum_{2}^{n+1} t \cdot P(t)$
However, I am having difficulty defining the Random Variable T and the probability formula for values of T.

Let $\small n = \mathsf{len}(L)$ and $\small t_n$ be the times that $\small \mathsf{max}$ is assigned a value. For $\small 0 \leq i < n$, define a random variable $\small X_i$ as
$$
\small
X_i = \begin{cases}
1 & \text{if } L[i] > \text{$\mathsf{max}$ in the $i$-th iteration of the algorithm}\\
0 & \text{otherwise}
\end{cases}
$$
Then we have
$$
\small
t_n = 1 + \sum_{i=0}^{n-1} X_i
$$ By linearity of expectation,
$$
\small
\mathbb{E}[t_n] = 1 + \sum_{i=0}^{n-1}\mathbb{E}[X_i]
$$
Observe that $\small X_i = 1$ if and only if $\small L[i] > \max\{L[0], L[1], \cdots, L[i-1]\}$. Therefore
\begin{align}
\small
\mathbb{E}[X_i] = \Pr[X_i = 1]  =&\small \sum_{v=1}^{100} \Pr[L[0] < v, L[1] < v, \cdots, L[i-1] < v, L[i] = v] \\
\small= &\small \sum_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot \frac{1}{100}
\end{align}
We thus conclude
\begin{align}
\small
\mathbb{E}[t_n] =&\ \small  1 + \sum_{i=0}^{n-1}\sum_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot\frac{1}{100} \\
\small =&\ \small 1 + \frac{1}{100}\sum_{v=1}^{100}\sum_{i=0}^{n-1}\left(\frac{v-1}{100}\right)^i \\
\small =&\ \small 1 + \frac{1}{100}\sum_{v=1}^{100}\frac{1 - \left(\frac{v-1}{100}\right)^n}{1 - \frac{v-1}{100}} \\
\small\text{(for sufficiently large $n$)}\quad\quad\approx&\ \small1 + \frac{1}{100}\sum_{v=1}^{100} \frac{1}{1 - \frac{v-1}{100}} \\
\small = &\ \small 1 + \sum_{v=1}^{100}\frac{1}{101-v} \\
\small =&\ \small 1 + H_{100}
\end{align}
where $\small H_{100}$ is the $\small 100$-th harmonic number.


least significant bit,and most significant bit if a,b are both binary bit. a=0, and b=0, what is least significant bit,and most significant bit of a+b, which means 0+0?
if c is the carry bit, and c=1, what is the least significant bit,and most significant bit of a+b when a=0,b=1

My thought is 0+0=0, thus least significant bit,and most significant bit are same, which is 0. and if C is carry bit, than a+b=1, then add carry bit, which is 10, so the the least significant bit is 0, and msb is 1..am I right? someone help

"Most significant bit" is a concept that depends on the size of the machine word. If $a + b + c = 10$ and the machine word has size $64$, then the MSB is $0$. It is $1$ only if the machine word has size $2$. (Under your definition, the MSB is always $1$, unless the number is $0$, in which case it is undefined.)


Maximization problem on finite collection of finite sets Problem
I am considering the following maximization problem:

Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$.
Goal is to find a subset $G \subseteq \mathcal{F}$ that maximizes $|G| \times |\bigcap G|$ where

$|G|$ is the cardinality of the set $G$, and
$\bigcap G = \bigcap \{X_{i_1}, X_{i_2}, \ldots, X_{i_m} \} = X_{i_1} \cap X_{i_2} \cap \cdots \cap X_{i_m}$.

As an example, for the collection
$$
\mathcal{F} = \{ \{a, b, c\}, \{a, b, c, x\}, \{b, c, y\}, \{a, b, c, z\} \},
$$
the maximizing subset is $G = \{ \{a, b, c\}, \{a, b, c, x\}, \{a, b, c, z\} \}$
and the score is $3 \times |\{a, b, c\}| = 9$.
Note: the score of $\mathcal{F}$ itself is $4 \times |\{b, c\}| = 8$.
Question
I am planning to use a procedure of this problem for compressing data (represented by finite collections of finite sets).
However, I don't have any good idea to solve this problem efficiently.
As yow know, we can solve this by enumerating all the collections of $\mathcal{F}$; but, it's too slow for practical use.
Is there a polynomial-time or some kind of efficient algorithm for this problem?
Or, does this problem belong to the complexity class that cannot be solved in polynomial time?

This problem is NP-complete. Let's reformulate it first: we have a bipartite graph, where

The left side corresponds to elements
The right side corresponds to sets
The edge $(u,v)$ means that $u \in v$.

Our goal is to find the bipartite clique with the maximum number of edges. As stated in Rene Peeters, "The maximum edge biclique problem is NP-complete", the decision problem is NP-complete.


Can context-free grammar generate $a^{2^n}$? Context-free grammar can generate the string a 2 n    for n≥0 .

The production rule P is S→SS|a .

The derivations is, for example:

1) S⇒a  (this is when n = 0)

2) S⇒SS⇒aa  (this is when n = 1)

3) S⇒SS⇒SSSS⇒aaaa  (this is when n = 2)

4) S⇒SS⇒SSSS⇒SSSSSSSS⇒aaaaaaaa  (this is when n = 3).

Am I right?

Someone told me yes but it takes a very long time for big enough n;

someone told me no - that this grammar actually generates $a^+$ because it can be $S \Rightarrow SS \Rightarrow SSS \Rightarrow aaa$.

So, does this mean context-free grammar cannot generate the string $a^{2^n}$?

Is there exist any other context-free grammars that can generate this language?

It is well known (and not very difficult to prove) that a context-free language over a unary alphabet $\{a\}$ is regular.

Thus, your question is essentially, "is $\{a^{2^n}:n\in \mathbb N\}$ regular?"
And the answer to that is no (easy to prove using the pumping lemma).


Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can I just use the given $M$ as a decider?

  $M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is
  an empty string ($L(w)=\emptyset$):

  Mark the start of the DFA as $q_0$.
  Simulate B on input w a finite number of times:

  First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
  Recursively: mark states that can be obtained within a finite $δ$
  operations from any marked states.

  If no accept state marked - accept. else, reject."

Is this correct?

Definitions:
$$\begin{align*}
A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\
E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\}
\end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.

If you want to reduce $E_{DFA}$ to $A_{DFA}$, you should use the following theorem:

  If a DFA with $n$ states accepts some word, then it accepts some word of length less than $n$.

But a much more efficient algorithm would just run DFS from the initial state, and check whether some accepting state is reachable from it.


Designing less than and less than or equal operators for Map with value being a Set I am trying to come up with less than and less than or equals operators for a Map where values are Sets. These are the hints I was able to get from the Professor.
{A -> {1,2}, B -> {3,4}} < {A -> {1,2}, B -> {3,4}, C -> {5,6}}

{A -> {1,2}, B -> {3,4}} < {A -> {1,2}, B -> {3,4,5}}

My solution was this:
val v_compare = (x, y) => (x.keySet intersect y.keySet).forall(key => x(key) subsetOf y(key))

val v_compare_equal = v_compare

I am wondering can I get some hints? I don't know what should the "<=" be

I think that actual code is off-topic here.
In general you can define a strict total order relation on (sub)sets of a known universe $U$: pick an arbitrary order for the elements of $U$ then, given two distinct subsets $X,Y$ of $U$, you can compare $X$ and $Y$ by first sorting the elements of $X$ (resp. $Y$) and then comparison the sorted version of $X$ with the sorted version of $Y$ lexicographically.
In your particular example the sets seem to contain integers, so you can just sort the set using the standard "less than" relation between integers.
To extend this total order to a map you can notice that a map is essentially a container of pairs of the form (key, value). We just defined a linear order over the values (sets), and you probably already have a natural order over the keys. Then two (key, value) pairs can be again compared lexicographically.


Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same? HAMPATH/UHAMPATH is A directed / undirected graph G and 2 nodes s and t and is there a hamilton path from s to t?

Likewise with HAMCYCLE/UHAMCYCLE but has a hamilton cycle on $G'$

The reduction for directed is

$HAMPATH \leq_p HAMCYCLE$

function(G, s, t)
    G' = G
    add node t' to G'
    add edges (t, t') and (t', s)
    return (G')

$(\Rightarrow)$If $(G, s, t) \in HAMPATH$, then $\{(s, v_1), \dots, (v_n, t)\}$ is a hamilton path in $G$ from $s$ to $t$ and our reduction for $G'$ has a path $\{(s, v_1), \dots, (v_n, t), (t, t'), (t', s)\}$ which is a hamilton cycle $(G') \in HAMCYCLE$

$(\Leftarrow)$ If $(G') \in HAMCYCLE$, then $\{(s, v_1), \dots, (v_n, t), (t, t'), (t', s)\}$ is a hamilton cycle in $G$. Remove the edges $(t, t')$ and $(t', s)$ and we are left with a hamilton path $\{(s, v_1), \dots, (v_n, t)\}$, $(G, s, t) \in HAMPATH$

Wouldn't this reduction also work for the undirected version i.e. $UHAMPATH \leq_p UHAMCYCLE$? I've seen on the internet another reduction where they add another node and add an edge between every vertex in G for $G'$ but wouldn't this simpler version work as well?

Your reduction is correct. However, the standard Hamiltonian path problem does not specify the endnodes $s$ and $t$, which is a bit different from your definition. This is possibly why the internet does not use your simple reduction.


Storage in computers? If i want to save something in a computer such as a number 1 that would be 001 but if i save 001 in a computer how would the computer know that 001 is 1. Should we first save  the number 1 in memory and tell the computer that hey this is 1 and it is 001 in your language. Basically if we want to save something, how would a computer know what are we saving to determine its output. Like if i say the computer hey i wanna save 10011 and i actually intended it to be The letter A how would the computer know 10011 is A?

Nowadays, all computers are built following certain conventions. One of those conventions is the use of zero and one (i.e. low voltage and high voltage): it's perfectly possible to make computers that don't use zeroes and ones, and in fact the Soviets did so (look into the Setun project). Another of those conventions is that text-based data comes in units of eight bits each, called "bytes".

Each byte holds a number from zero to 255, and more conventions define what each number means. The ASCII standard, for example, says that 65 means "A", while the UTF-8 standard says that 195 followed by 184 means "ø". But there's nothing intrinsically "A"-like about the number 65: it's just a convention people have agreed to follow, to make it easier for programs to work together.

(P.S. When two programs are using different conventions, you get a garbled mess called "mojibake". Nowadays most text data is stored in UTF-8, which helps avoid this, but there are still some holdouts (cough Windows API) who insist on using other conventions instead. It's a headache when you have to deal with that.)


How to Solve TSP Given Length of Path? I am trying to devise an algorithm in which given the length of a path that satisfies the constraints of the Traveling Salesman Problem, I can find the path.  Currently, my only solution is to find a cost matrix of every possible path and brute force adding them up until I get a solution that equals the length of the path.

Is there a better way to find a TSP path given the length?

This decision problem ("does this graph contain a tour of length at most this?") is NP-complete, so you won't find a polynomial-time algorithm most likely.

In addition to the brute-force method you describe, you can have a look at Held-Karp, which solves the problem in $O^*(2^n)$ time using dynamic programming. For an even more practical solution, you can have a look at the Concorde TSP solver, which has been successfully used to solve instances with tens of thousands of cities optimally.


A question about the work per recursive call in FPT vertex cover of size k algorithm I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows:
VertexCoverFPT$(G, k)$
if $G$ has no edges then return true
if $k=0$ then return false
let $uw$ be some edge of $G$
if VertexCoverFPT$(G-u, k-1)$ then return true
if VertexCoverFPT$(G-w, k-1)$ then return true
return false
Its said that this algorithm has $2^k$ recursive calls each with $O(n)$ of work in each recursive call. My question is how is it that there is only $O(n)$ work in each recursive call when we need to create the 2 graphs ${G-u}$ and ${G-v}$ (u and v are the vertices we are currently checking) which takes $O(V+E)$ time (Doing a deep copy of graph G excluding the node and the edges connected to it). Is there a more efficient way than constructing ${G-u}$, ${G-v}$ from G or am I missing something?

You do not need to create any new graph.
You can simply maintain an additional array $VT$ of size $|V| = n$ such that $VT[i] = 1$ if the vertex $i$ is deleted from the graph. Otherwise, $VT[i] = 0$.
While accessing an edge $(i,j)$, first the algorithm can check if $VT[i]$ and $VT[j]$ are both $0$ or not. If both are $0$ then the algorithm access that edge. Otherwise, it does not.
In addition to it, maintain the count of edges a vertex $i$ is currently connected to. Suppose the count is stored in an array $C$ of size $n$. In the beginning of the algorithm $C[i]$ is initialized to the $degree(i)$.

Accessing an Undeleted Edge: Go to the adjacency list of that vertex which has $VT[i] = 0$ and $C[i] \neq 0$. Since we know that at least one edge in the list is not deleted, the algorithm will find an undelete edge in $O(n)$ time. Updating the count array after deleting a vertex takes $O(n)$ time. Overall operation is $O(n)$ time.


Origin of using ">" to represent child in a tree What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child

e.g.

CSS Child Combinator (initial definition)
Breadcrumbs

It comes from set theory. To see that these ideas were around before computers and that they were explicitly called trees consider the following famous tree. The convention set theorist sometimes use (some use use the convention you gave) is the opposite (the root $\hat{0}$ is the smallest, i.e. $\hat{0}<x$ for all $x\neq \hat{0}$, not the biggest ... this is keeping in line with the equivalence of the principle of induction and the well-ordering principle and is more natural ... i.e. a "zero-like" object is the root ... I will keep that convention so just replace all of the $<$ with $>$ in the proceeding discussion) The idea is the following:

  Theorem From any partial (well)-order we can construct a tree and from any tree we can construct a partial (well)-order.

Remark Partial (well)-order is a name I made up so as to artificially distinguish between trees and the relation I am about to define:

Let $P =  (V, E) =(V, \leq_E ) $ be a partial (well)-order then it satisfies the following

$(\forall x) \ x \leq x$
$(\forall x,y) \ x \leq y \implies y \leq x $
$(\forall x,y,z) \ x \leq y \land y \leq z \implies x \leq z $
$(\exists \hat{0} )(\forall x) \ \hat{0} \leq x$
$(\forall x) \ (\exists 0_{x} ) \ y \in \{ t \in V \ | \ t \leq x\} \implies  0_{x} \leq y $ ,

The first 3 state that $\leq$ is a partial order and the last states that the predecessor sets are well ordered.

(Proof of Partial implies Tree) Let $P =  (V, \leq_E ) $ be a well partial order then connect $v$ to $w$ if $w$ is the least element such that $v \leq w$, i.e. $ w = \min \{x \in V \ | \ v \leq x\}$ or $w$ covers v. It is easy to see that there are no cycles (because of rule 3) and that the graph is connected (there is always a path from $\hat{0}$ to any $v$ by induction because $\leq$ is a well order)

(Proof of Tree implies Partial) Let $x \leq y$ if there exists a path from $x$ to $y$, it is tedious but easy to see that all of the rules above are satisfied.

You may thinking, "man I didn't want an explanation involving set theory"

Let me help you dispel those heretical thoughts with the following observations

  Most of the famous early famous computer scientists got most of their
  techniques from set theory

The solution to the halting problem is an adaptation of a very beautiful proof by Georg Cantor that there are different sizes of infinity
Similarly so is the Entscheidungsproblem
Similarly, the proof that exponential time does not equal polynomial time
Von Neumann (Von-Neumann architecture) also came up with the Von-Neumann Universe of sets

This should come as no surprise set theory is concerned with the ontological status of the mathematical universe and the idea that all of the objects of our mathematical experience can be constructed via recursion ... and isn't that the big idea behind every algorithm/computer program ... some recursive construction ... trees are the simplest recursively constructed objects other than the natural numbers ... set theory is like a programming language for the platonic realm.

  We can take this whole idea further and prove that every set is a tree and every tree is a set (because of Von Neumann's axiom of regularity) but I will just leave you with the following: set data structures are tree data structures which hopefully will have you convinced of the truly inexorable relationship between the two.

I hope that I have whet your curiosity towards the beauty of sets. Good luck on your mathematical voyages! Bon Voyage!


Why can the state space of the 15 puzzle be divided into two separate parts? I am trying to understand the proof here of why the state space in 15 puzzle is divided into two separate parts, but the explanation is complicated for me.

Could someone please explain it in simpler terms? I have been struggling with this for days :(

Perhaps the simplest way to understand the proof is by the idea of a conserved quantity : find some quantity that can be derived from a configuration and show that every move preserves that quantity.  A static version of the idea is found in the following old puzzle:

  Remove the northeast and southwest corner squares from a standard 8x8 checkerboard.  Can the remaining 62 squares be tiled using 31 dominos?

Here, the parity principle is simple: each domino takes up exactly one black and one white square on a checkerboard, so any shape that can be tiled by the dominos has to have exactly as many white squares as black.  Since the 62-square shape has 32 squares of one color and 30 squares of the other, there's no way of tiling it.

The conservation principle for the 15-puzzle is a bit more complicated, but it's fairly close to this: it's also a parity principle.  Let's number the blank square '16' for the time being and imagine it being filled in; then we can talk about the state of the puzzle as a permutation of the numbers (1...16).  Now, given an arbitrary permutation of the numbers (1...$n$), we can count how many pairs of numbers we have to swap to return all the numbers to their 'original place'.  There are many different possible sets of swaps that can be made - for instance, if you have the permutation (3, 2, 1) you can get back to (1, 2, 3) by either swapping the first and third positions (3 with 1) or by swapping the first and second positions (3 with 2), then the second and third positions (3 with 1), then the first and second positions (1 with 2).  (The minimum number of swaps that need to be made is called the number of inversions of the permutation, and it's an interesting quantity in its own right, but that's not important here).  However you swap numbers around, though, the total number of swaps will either always be odd (like it is for (3, 2, 1)) or always be even; we call this number the parity of the permutation.

Now, going back to the fifteen puzzle: every move is to swap the blank square (the one we've labeled as '16') with some other square, one unit away from the blank square's current position.  This means that a swap always comes with a move of one square - so if you consider the quantity 'total number of swaps I have done' + 'moves the 16 is away from its home square', then this quantity will always be even.  In particular, when the 16 is back at its home square (0 moves away) then the overall number of swaps that's been performed must be even.  This means that the parity of the permutation of the numbers (1..16) corresponding to our resulting position is always even.  But now imagine the position of the original puzzle where the 14 and 15 have exchanged places; the 16 is at home but there's been only one 'swap' made.  Since this is an odd number of swaps rather then an even number, it can't possibly be reachable from the base configuration.

There's one more minor catch: this shows that there are at least two categories that 15-puzzle positions can fall into, but it doesn't show that there are only two.  For that, a slightly more complicated result is needed: namely, that any even permutation can be decomposed as a product of what are known as 3-cycles (i.e. swaps $a\rightarrow b\rightarrow c\rightarrow a$).  I won't try to prove this here, but the simplest proofs work algorithmically - similar to how bubble sort shows that every permutation can be generated by swapping only adjacent elements.  With this result in hand, though, it's easy to get any even permutation: we can get an arbitrary 3-cycle by moving our three elements into positions 11, 12, and 15 on the puzzle (with the blank square in position 16, of course), and then moving the blank square Up, Left, Down, Right - you can convince yourself that this motion cycles the three elements.  Once we've done this, we just undo the same motions that got the three elements into those positions, leaving the final positions of all the other elements unchanged from their starting positions.  This way of getting an arbitrary 3-cycle, along with the theorem allowing any even permutation to be expressed in terms of 3 cycles, then gives a way of getting every reachable (i.e., corresponding to an even permutation) position.


Shared Elements Algorithm I have a problem that I am working on an algorithm for:
I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets)
$S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\in S,\ A_i=\{a_{i1},a_{i2},a_{i3},...,a_{in_i}\},\ a_{ik}\in \mathbb{Z}^+, a_{ip}=a_{iq}\iff\ p=q$
(so $n_i$ would be the amount of numbers in each set)
The algorithm should find 5 sets in $S$ I will call $B_1,B_2,B_3,B_4,B_5$ where the following pairs of sets share an element:
$B_1,B_2$
$B_1,B_3$
$B_1,B_4$
$B_1,B_5$
$B_2,B_3$
$B_3,B_4$
$B_4,B_5$
$B_5,B_2$
where the element each of these pairs share is distinct
So if $A_2=\{4,5,7,37\},\ A_5=\{8,11,37\},\ A_7=\{4,11,21\},\ A_{12}=\{7,21,131\},\ A_{19}=\{5,8,131\}$
Then those 5 sets would be a potential output of the algorithm.

The way I would do it currently would seem very inefficient which would be to iterate through the sets of $S$. I would take $A_1$ and find all the sets in S that share an element with it. I would take one of those sets, $A_m$, find the sets that share an element with it that isn't that element that $A_1$ and $A_m$ shared. And continue that until I found 5 sets that worked.
There must be a more efficient solution but I am unaware of this type of problem and googling didn't help much. So if anyone knows a good way to do this or can point me in the right direction with analogous problems or topics I should learn about that would be very appreciated.

Construct an undirected graph with $k$ vertices, where each vertex represents a set $A_i$, and you draw an edge between two vertices if their sets share an element.  Now you have an instance of subgraph isomorphism: you have a graph $H$ on five vertices (of the shape shown in your question), and you want to enumerate all subgraphs of $G$ that are isomorphic to $G$.  You do have an additional distinctness condition, but if you can enumerate all isomorphic subgraphs, you can check whether they satisfy that additional condition in post-processing (and in most cases I expect they typically will).
This subgraph isomorphism problem looks challenging.  A naive approach has $O(k^5)$ running time: enumerate all 5-tuples of vertices.  You can improve this slightly, to $O(k^2m^{1.5})$ time, where $m$ counts the number of edges in the graph (note that $m\le k^2$, and might be much smaller, so this might be better).  First, enumerate all 3-cliques (triangles).  This can be done in $O(m^{1.5})$ time (see http://complexnetworks.fr/wp-content/uploads/2011/01/triangles.pdf and https://users.soe.ucsc.edu/~sesh/pubs/conf-triangle-enum.pdf).  These will be your candidates for $A_1,A_2,A_3$.  Next, enumerate all possible candidates for $A_4,A_5$ and check to see if they meet the requirements.  This might not be much faster, but maybe it would help a little bit.


A special case of subset sum I came across the following problem in my complexity-theory course:

Given a set of numbers $A := \{a_1, \dots, a_n\} \subset_{\mathrm{finite}} \mathbb{N}$ and a number $b$ also in $\mathbb{N}$ such that the following condition applies: $a_i$ divides $a_{i+1}$ for all $i < n$ and $a_i < a_{i+1}$. Prove that this special case of subset-sum is decidable in P.

Due to the given condition, $b$ has to be a multiple of the first $a \neq 1$. Taking $a_1 \neq 1: b = a_1 \cdot x$. Finding this x takes me back to the subset-sum problem though which is surely not in P.

Any help would be appreciated.

In short, the greedy algorithm works, where in each step you find the largest number in $A$ and subtract it from $b$. If $b$ becomes zero, you get a solution. If you reach a point where all numbers in $A$ are greater than $b$ output no.

In the following I list a formal description of the algorithm and a proof of correctness.

Here is a formal description of the algorithm. Let $A_0 = A, b_0 = b$ and $b_i$ be the value of $b$ after the $i$-th iteration. Let $A_i$ be the numbers left in $A$ after the $i$-th iteration. Then the algorithm goes as follows. In each step $i = 1,\dots$ find the largest number $a_j$ in $A_{i-1}$ not greater than $b_{i-1}$. If no such number exists output no. Otherwise, set $b_{i} = b_{i-1} - a_j$ and $A_i = A_{i-1} \setminus \{a_j\}$. If $b$ becomes equal to zero then output yes, else iterate.

Claim 1. The previous algorithm output the correct answer of the given instance of the restricted case of the subset sums described in the question.

Before we prove the claim we prove an auxiliary claim.

Claim 2. Let $a_1, \dots a_n$ be the numbers in $A$ in ascending order. Then $\sum\limits_{i=1}^{k-1}a_i < a_k$ for all $k \in [n]$.

Proof.(Claim 2). Proof with induction over $k$. For n = 1, the sum is empty. Now we prove it for $k$.
$$\sum\limits_{i=1}^{k-2}a_i + a_{k-1} < 2a_{i-1} \leq a_i,$$
 where the first inequality holds due to the induction hypothesis and the second one holds by assumption since $a_{k-1}$ divides and is smaller than $a{k}$.

Proof.(Claim 1) If the algorithm outputs yes, then it is clearly a yes-instance, since it only chooses numbers from the given sets and subtract there values from $b$.

Now we prove that, if our algorithm outputs no, the given instance is a no-instance. To this end we prove that if at step $i$ we choose an element $a_j$, then any solution of the given instance must contain this element. We prove this by induction over $i$. Note that any $a_j', j'>j$ is strictly greater than $b_i$ and hence can never be included, assuming by induction hypothesis, all previous selections of $a$ were a part of a solution if there exists one. Now using Claim 1, $\sum\limits_{i=1}^{j-1}a_j$ < $a_j$ and since we only remove elements, $A_i$ contains no other elements smaller than $a_j$ and hence, if we do not choose $a_j$ choosing all smaller elements will not suffice to get a sum equal to $b$. Hence, we have to choose $a_j$.


Is the language that accepts strings concatenated with their reverse regular? If the set of regular languages is closed under the concatenation operation and is also closed under the reverse operation ($x^R$ is the reverse of $x$) then is the language generated by $$\{ww^R|w\in\Sigma^*\}$$ for some input alphabet $\Sigma$, also regular? If not, why not?

I've been trying to find a proof for this using the pumping lemma, but it seems that selecting any substring towards the middle of the string being pumped could also be of the form $\{ww^R|w\in\Sigma^*\}$, causing the original string to remain in its original form.

Here's a try:

$\textbf{Theorem:}$ The language, $A$, generated by $\{ww^R|w\in\Sigma^*\}$ is not regular.

$\textbf{Proof:}$ Assume $A$ is regular (We will use the Pumping Lemma for Regular Languages to show a contradiction). Let the input string $s$ be $ww^R$ and let $p = |w|$.

When splitting $s$ into substrings $x, y, z$ such that $s=xyz$ we see that $xy$ must be a substring of $w$ by the third condition of the Pumping Lemma ($|xy|\le p$).

By the first condition of the Pumping Lemma, we see that all strings of the form $xy^iz$ must be in $A$ for all $i \ge 0$. Taking $i$ to be zero, we obtain the string $xw^R$. $|x| < |w^R|$ so $xy^0z \notin A$.

QED? What if $xw^R$ can still be split so that for some substring $k$, $kk^R = xw^R$?

I think I may be overthinking this but it's really bugging me.

You're over-thinking it on the $xw^R=ww^R$ thing, that's a red herring. But you're not over-thinking it by looking for a contradiction, you're looking in the wrong place.

First, your proof that the language is irregular is correct. You're aiming to show a contradiction. All you need is one counterexample; just one! And you found it already. This may seem paradoxical, but your understanding of how to operate on languages is a little off. As you noted, regular languages are closed under reversal:

$L^R = \{w^R|w\in L\}$

They are also closed under concatenation:

$L\circ L^R = \{wv|w\in L, v\in L^R\}$

But, you see, that's a little different from $L_{mirrored} = \{ww^R|w\in L\}$. Look:

$L = \{$ cat, dog$\}$

$L^R = \{$ tac, god$\}$

$L\circ L^R = \{$ cattac, catgod, dogtac, doggod$\}$

$L_{mirrored} = \{$ cattac, doggod$\}$

There's your contradiction! You must have thought those last two were the same, when they're not. Rather,

$L_{mirrored} \subseteq L\circ L^R$

And the subset of a regular language is not necessarily regular.

edit: I removed a large chunk of this answer, so the comments below will probably be confusing...


Is there a complexity metric for finite state machines? I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each Turing machine as one of the criteria to guide the evolution process.

However, I couldn't find any references as to a canonical complexity metric for FSMs. I imagine the metric would include some combination of the number of states, number of transitions, and number of input symbols, but I'm not sure how these would be combined appropriately into a normalized metric.

Is there a canonical (ideally normalized) complexity metric for finite state machines?

Yes, there is a canonical complexity metric for finite state machines: the number of states.  It's as simple as that.

The number of transitions or input symbols don't matter (for this standard, canonical metric).  We don't use a normalized metric based on the combination of such values.  We just count the number of states.


Show that the following language is not recursive: $L = \{w \mid M_w \text{exists and it accepts a word } x_1 = 0x \text{ if and only if it accepts } x_2 = 1x\}$ ($x \in \Sigma^*$, so $x_1$ is starting with a 0 and $x_2$ is obtained from $x_1$ by changing the first 0 to a 1).

We say a language $L$ is good if "$0x\in L$ if and only if $1x\in L$". Let $\mathcal{L}$ be the set of all good languages. Then you are trying to determine whether the language recognized by a given TM belongs to $\mathcal{L}$. Since $\mathcal{L}$ is non-trivial, according to Rice's theorem, this is undecidable.

If you want a proof without Rice's theorem, you can take a look at the proof of Rice's theorem and try to write a proof for this specific problem. This is not hard.


Is the language with decreasing numbers of a, b and c context-free by pumping lemma? So I've been given the following language on an assignment.  It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours.

$$L=\{w:w\in(a+b+c)^*, n_a(w) > n_b(w)>n_c(w)\}$$

where $n_x(w)$ represents the number of character $x$ found in $w$.  The problem statement is: prove or disprove that the language is context-free.  Context-free grammars or pushdown automata are acceptable proofs.  Use pumping lemma to disprove.

I've extensively explored both possibilities and I'm fairly certain that it is context-free.

The approach I've taken in finding a context-free grammar for the language involves using rules which preserve the constraint $n_a(w) > n_b(w) > n_c(w)$ (ie. whenever a $b$ is added, add an $a$; whenever a $c$ is added, add a $b$).  Then, I've attempted to enforce that there are at least two $a$s and at least one $b$ (base case for the constraint).

The grammar I've used is:

$S\implies XaXaXbX | XaXbXaX | XbXaXaX$

$X \implies XX| A | B | C | \lambda$

$A \implies a$

$B \implies ab | ba$

$C \implies abc | acb | bac | bca | cab | cba$

(where $\lambda$ is the empty string)

My grammar fails for strings like $cccaaaaabbbb$.

I'm confused as to where to go from here.

I would really like a push in the right direction, not an answer.
 Any help is greatly appreciated!

If your language is context free, so is its intersection with the regular language $a^* b^* c^*$. And your proof in the answer that this isn't context free does go through. Your proof omits the cases where one of the strings straddles the $a/b$ or $b/c$ boundaries.


Why can't we solve the dinner party problem by finding a maximum matching? Consider the following dinner party problem:

  Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of acquaintances you can invite to a dinner party such that you do not invite any two who are not on speaking terms.

I have read in Arora-Barak that is not possible to find an efficient solution for the dinner party problem. I'm confused because I thought that it was easy to solve with Edmond's Blossom algorithm (it finds a maximum matching).

This is what I thought (of course it must be wrong):

We create a graph where vertices are acquaintances, and edges are "not on speaking terms with each other".
We exchange vertices with edges.
We find a maximum matching, and these edges are the guests I can invite.

EDIT: I explain it better:

We create a graph where  edges are acquaintances and vertex are "not on speaking terms with each other" If the resulting graph has edges at the ends (it could be possible) we add extra vertex at these ends.
We find a maximum matching, and these edges are the guests I can invite.

But I'm not sure why I'm wrong.

The problem is that you can not model all instances of the problem in the way you suggest: A person can be 'not on speaking terms' with arbitrarily many other persons, but an edge in a graph can only be connected to two vertices. So instances where someone doesn't want to speak to 3 or more other people cannot be modeled.


What are the recents topics of research that combine both systems research and theoretical computer science? I am an undergraduate majoring in Computer Science and Mathematics.
For my undergraduate research, I would like to work on something that lies in the overlap between systems research and theoretical computer science. Something that could satisfy this requirement is cache-oblivious algorithms because it is about the analysis and design of algorithms without completely ignoring how actual systems work (memory hierarchy and so on). But there could be many other fields in systems research which involve a lot of theory, or vice versa.

One of my seniors suggested distributed systems - he seemed to indicate that things like Paxos and Raft have a lot of underlying theory, but I haven't taken the time to dig into it.

You could also suggest some field in systems research which can gain a lot from some rigorous mathematical foundations and analysis. A senior will be going to graduate school at Johns Hopkins University to do a PhD on the math behind deep learning. So maybe I could try something like "the math behind --some systems research field--".

Another example I found is "Distributed Computing using Combinatorial Topology".

TL;DR: What fields/topics of research lie in the intersection of theoretical computer science and systems research?

This might not be what you mean by "theoretical computer science", but there's some rich interaction between Programming Languages Theory and Distributed systems going on with Session Types. They basically are a way to use type systems to specify communication protocols, increasing safety in distributed languages.

For example, The Imperial Mobility Group has many publications in session types, this should at least get you started on finding research in the area.


Difference between Time-sharing computers and computers which use Round Robin scheduling algorithm? So maybe I'm confused in these concepts

but i thought that time sharing computer is a computer which the processor switches between different processes quickly to achieve a good response time

but isn't this the same as Round Robin algorithm?! i mean aren't we scheduling between different processes   in Time sharing computer just like Round robin? or am i missing something here? what is the difference?

No, they are not equivalent, but you are right to note a similarity.

Yes, a time sharing computer is one in which the computer switches between different processes.  The schedular is the part of the operating system that determines when to switch between processes, and which process to switch to.   A round robin scheduler is one particular type of scheduling strategy that could be used in a time sharing computer, but there are other possible scheduling strategies as well.


Why is the most probable assignment for all variables in MRFs called MAP assignment? I am new to graphical model, especially Markov Random Fields. I have a question about MAP assignment. Let say we have the graph structure and all the potential functions. MAP assignment in MRFs is defined as the most probable assignment for all variables (no given evidence in this case). My question is why it is called MAP (why not MLE or anything else). What is the connection between them? I know MAP and MLE share a lot in common except for one thing that MAP uses the prior distribution of the parameters. But I cannot figure out the connection between the most probable assignment in MRF and MAP.

MLE is a point estimate $\hat{\theta}_{\text{MLE}}$ that resides at a mode of the likelihood density. That is,
$$L(\theta; X) = \Pr(X | \theta)\\
\hat{\theta}_{\text{MLE}} = \arg \max_{\theta} \Pr(X | \theta)$$

MAP stands for maximum a-posteriori. It is a point estimate $\hat{\theta}_{\text{MAP}}$ that resides at a mode of the posterior distribution (the distribution over the parameters themselves conditioned on our observed data). We can perform MAP estimation by incorporating a prior distribution for our parameters.

$$ \Pr(\theta | X) = \frac{\Pr(X | \theta) \Pr(\theta)}{\Pr(X)} \\
\Pr(\theta | X) \propto \Pr(X | \theta) \Pr(\theta) \\
\hat{\theta}_{\text{MAP}} = \arg \max_{\theta} \Pr(X |\theta)\Pr(\theta)$$

This is a simple application of Bayes' Theorem. The reason we use "proportional to" is that we don't care about the marginal likelihood constant. Since it is only a constant our point estimate for this "psuedo-MAP" still corresponds to a point-estimate for the true MAP. By definition $\hat{\theta}_{\text{MAP}}$ is the (at least locally) most-probable estimate under the posterior distribution.

The key take-away is that the Maximum Likelihood estimate is the point estimate that maximizes the probability of observing your data. The MAP estimate is the point estimate that is the (at least locally) most probable under your posterior distribution of parameters. In the end deciding whether to use the MLE or MAP estimate is up to you and your model. It really depends on what you are more interested in.

To stress the difference one last time, look at the difference between the two definitions for the distributions being maximized over. In ML estimation we are maximizing over the distribution of observing our data; in MAP estimation we are maximizing over the distribution of parameters themselves. Hence why we can say MAP estimates are the most-probable estimate whereas we cannot for the ML estimate.


Is Phong shading a pixel-first computational model? Wikipedia says that:

  If a mesh covers more pixels in screen space than it has vertices, interpolating colour values from samples of expensive lighting calculations at vertices is less processor intensive than performing the lighting calculation for each pixel as in Phong shading.

Why does it matter that there are more pixels than there are vertices? In the quote it also says that Gourand shading performs lighting calculation "at vertices" while Phong does it in pixels.

I have always thought that both shading schemes are the same, just that Gourand interpolate colours along vertices, while phong creates a reflection vector to interact with the light sources for specular reflection. Is this correct?

I agree that it is a bit superfluous to have the "[i]f a mesh covers more pixels in screen space than it has vertices". Basically, if it doesn't then no interpolation is needed since the color of a pixel can be determined by the vertices it contains. But this is just a degenerate case of interpolation and there isn't much reason to call it out.

Your final paragraph is roughly correct, but it does imply that you need to calculate the Phong reflection model at each pixel using the interpolated normal in the Phong shading case while you don't in the Gouraud shading case. In the latter case, you are linearly interpolating colors calculated using the Phong reflection model at the vertices to produce pixel color values. In the former case, you are linearly interpolating normal vectors calculated at the vertices to produce pixel normals which you then use in the Phong reflection model per pixel.

The Phong reflection model is the "lighting calculation".


How to prove that non-antipodal vertices cannot be a diameter of a convex polygon? I am learning Shamos's rotating calipers algorithm for finding the diameter of a convex polygon in his Ph.D. thesis; Page 78.

It reads

  Consult Figure 3.23 and notice that parallel lines of support cannot be made to pass through every pair of points. For example, no lines of support through vertices $D$ and $F$ can be parallel. This means that $DF$ is not a diameter. A pair of points that does admit parallel supporting lines will be called antipodal.

Problem: How to prove that non-antipodal vertices cannot be a diameter of a convex polygon?

My Informal Attempt: See Figure 3.23. Intuitively, by rotating the line $DC$ about $C$ and then $CB$ about $B$, we can get two parallel lines of support passing through $F$ and $B$. However, is $FB$ necessarily longer than $FD$? If so, how to prove it?

  A line $L$ is a line of support of a convex polygon $P$ if it meets the boundary of $P$ and $P$ lies entirely on one side of $L$. (Definition 3.6; Page 69)

I find it easier to prove the equivalent statement 'any pair $A,B$ such that the segment between them is a diameter of $P$ must be anti-podal':

If the segment $s$ between $A,B$ is a diameter, construct the lines $k,l$ as follows: line $l$ is the unique line perpendicular to $s$ and through $A$. Line $k$ is the unique line perpendicular to $s$ and through $B$.

I claim that the lines $l,k$ are parallel lines of support. These lines are parallel, as they are perpendicular to the same segment. To see that they are lines of support, suppose to the contrary that $l$ is not a line of support. As $A$ lies on the boundary of $P$ and in $l$, $l$ intersects the boundary of $P$. So $l$ can only not be a line of support if it intersects the interior of $P$. But this means that there is a point $X$ in $P$ ('beyond' the line $l$) such that $|XB|>|AB|$, contradicting the fact that $s$ is a diameter of $P$!

So $l$ is a line of support. Analogously, $k$ is a line of support as well. So, as there is a parallel pair of lines of support through $A$ and $B$, $A$ and $B$ are anti-podal.

$\square$

The picture below sketches the situation where $A,B$ are endpoints of a diameter of $P$. A position where the hypothetical point $X$ could lie is also shown (it is clear that here there can be no point $X$ such that it lies in $P$!)  Note that while $C,D$ are not endpoints of a diameter, they are anti-podal!

Be careful though, as the converse of the statement, 'Any segment such that the endpoints $A,B$ of that segment are antipodal in $P$ is a diameter in $P$' is false. As a counterexample, take a (non-square) kite (or take the sketch above). Clearly, the two pairs of opposing corners are anti-podal, but only one of the segments between the pairs is a diameter! Your informal attempt seems to try to prove this. As what you're trying to prove is false, it isn't surprising that formalizing the proof fails!

Note that I don't use the fact that $P$ is convex. You can check that this proof also works for non-convex, but simple polygons (it might even work for non-simple polygons, but these things are awful, so I'd rather not make claims about them). Note that in the case of convexity, the diameter need not necessarily be contained within the polygon, but all definitions still apply.


Can I prove that I have x such that f(x) < c without revealing x? I'm interested in applications to verifiable computing. Let's say Alice would like to find an x such that f(x) < c for some real-valued function f and some c of Alice's choosing, so she hires Bob who has a powerful computer. Bob finds such an x, but he doesn't want to give it away before receiving payment from Alice, but at the same time Alice doesn't want to pay Bob before she is sure he has a sufficient value of x.

Is there a way for Bob to prove to Alice that he has such an x without revealing what the value of x is?

This can be done with a fully homomorphic encryption of f, right? For example Bob can demonstrate the equivalent inequality on the encrypted f and encrypted c for the encrypted x, and Alice can verify the encryption scheme on f and c, but this does not reveal x.

Is there any way that is less computationally expensive - even if for only certain types of functions f? Is there a partially homomorphic encryption scheme that will suffice? Or some other type of zero knowledge proof?

If the function $f$ is publicly known and is efficiently computable, it is possible for Bob to prove that he knows a value $x$ such that $f(x)<c$.  This is known as a zero-knowledge proof of knowledge.  There's lots written on zero knowledge proofs; you can go read about them.

In particular, given any predicate $\varphi(x)$ that is computable in polynomial time, there exists a polynomial-time zero-knowledge proof of knowledge that you know $x$ such that $\varphi(x)$.  If $f$ can be computed in polynomial time, then the predicate $f(x)<c$ can certainly be tested in polynomial time, so it can also be proven in zero knowledge in polynomial time.

However, that is not enough to solve the ultimate problem you want to solve.  It sounds like what you ultimately want is a fair exchange protocol.  Sadly, such protocols typically aren't super-realistic, if you want them to be "all-digital" and avoid any trusted parties; if Alice and Bob know each other and have some kind of relationship, you're probably better off signing a contract.  But if you want to read about the topic, you can start with https://crypto.stackexchange.com/q/8333/351 and https://crypto.stackexchange.com/q/8352/351 and continue reading from there.


Is a balanced binary tree a complete binary tree? Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.

All I know is this:

A binary tree is balanced (or height balanced), if the height of any node’s right subtree and left subtree differ no more than $1$.
A complete binary tree of height h is a binary tree that is full down to level $h-1$, with level $h$ filled in from left to right.

A complete binary tree is a binary tree of length $h$ such that all the levels from $1$ to $h-1$ are completed and the last level gets completed from left to right. As in the image below.

A balanced binary tree is a binary tree of height $h$ such that the height of any node’s right subtree and left subtree differ no more than $1$. So it doesn't say anything about it having to be completed from left to right.

The figure above describes this trees very clearly in a recursive way.


The Partition Problem: Reducing to prove NP-Completeness I am struggling with the below problem. Curious to hear any guidance.

The Partition Problem is the following:

$\textbf{Instance:}$ A multiset of numbers $S = \{a_1, a_2, \ldots , a_n \}$.

$\textbf{Question:}$ Can $S$ be partitioned into two multisets $A$ and $B$ such that the sum of the numbers in $A$ is equal to the sum of the numbers in $B$?

Prove that the Partition Problem is NP-complete.

Things I could reduce from that I know of are 3-SAT, Vertex Cover, Subset Sum, Independent Set, and the clique problem. My assumption is that I should be reducing from the Subset Sum problem, but I struggle with that problem as well.

Is anyone able to help shed some light on this? Also, any explanation in plain English (maybe with some notation) would be greatly appreciated as I'm struggling with the concepts here. Just mathematical notation alone might make it more difficult for me to understand at the moment.

Thank you in advance!

Partition is equivalent to a special case of the subset-sum problem: $S$ can be partitioned into two sets $A$ and $B$ such that $\sum_{x \in A} x = \sum_{x \in B} x$ if and only if $\exists S' \subseteq S$ such that $\sum_{x\in S'} x = \frac{1}{2}\sum_{x \in S}x$.

Proof of $\implies$: Given $A$ and $B$ that partition $S$ and are such that $\sum_{x \in A} x = \sum_{x \in B}$ you must have $\sum_{x \in S}x =\sum_{x \in A} x + \sum_{x \in B} x = 2 \sum_{x \in A} x \implies \sum_{x \in A} x = \frac{1}{2}\sum_{x \in S}x$. The claim follows by picking $S' = A$.

Proof of $\Longleftarrow$: Given $S' \subseteq S$  such that $\sum_{x\in S'} = \frac{1}{2}\sum_{x \in S}x$ you must have $\sum_{x\in S \setminus S'} x = \sum_{x \in S}x - \sum_{x \in S'}x = \frac{1}{2}\sum_{x \in S}x$. The claim follows by picking $A=S'$ and $B = S \setminus S'$.

To show that this special case of subset sum (i.e. partition) is in $\mathsf{NP}$ notice that a subset $S' \subset S$ such that $\sum_{x \in S'} x = \frac{1}{2}\sum_{x \in S}$ is a yes-certificate.

To see that this special case of subset sum is still $\mathsf{NP}$-hard consider an instance $\langle S, T \rangle$ of subset sum where $S$ is a (multi-)set and $T$ is the target value. Let $M = \sum_{x \in S} x$.

Create a new instance subset sum $\langle \overline{S}, \overline{T} \rangle$ where $\overline{S} = S \cup \{ M-2T \}$ and $\overline{T}=M-T$.

If there is a solution $S' \subseteq \overline{S}$ to $\langle \overline{S}, \overline{T} \rangle$ then $\sum_{x \in S'} x = \sum_{x \in \overline{S} \setminus S'} x= M-T$ (since the sum of the elements in $\overline{S}$ is $2(M-T)$). At least one of $S'$ and $\overline{S} \setminus S'$ contains element $M-2T$, call this set $S^*$. Then the $S^* \setminus \{M-2T\}$ is a subset of $S$ and the sum of its elements is $(M-T)-(M-2T)=T$, showing that the original instance $\langle S, T \rangle$ is a yes instance.

On the other hand, if there is a solution $S' \subseteq S$ to $\langle S, T \rangle$, then the set $S' \cup \{ M-2T \}$ is a subset of $\overline{S}$ and the sum of it's elements is $T + (M - 2T) = M-T = \overline{T}$, showing that $\langle \overline{S}, \overline{T} \rangle$ is a yes instance. This concludes the proof.


Context Free Grammar for Try-Catch-Finally Statement and Throw I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "Type", "Expression", and "Statement", as well as a terminal "Ident". I do not understand how this is possible using so few nonterminals and only one terminal

You need more terminals, for the reserved words try, catch, finally, and throw, and possibly for braces and for semicolon (depending on the interpretation of Statement).

Here is an example to help you get started. It gives the syntax of a simple if statement, assuming that Statement also includes compound statements (i.e. { ... }), and that statements do not end in a semicolon.

IfStatement → if ( Expression ) Statement


Computer science problems related to music? Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a scale or a tonality or general what is considered harmony in frequencies and physics, electromagnetism and waveforms.

Can you give examples of the area I want to know of?

For instance, given an algorithm that guesses a melody, how successful will the melody be in resembling an artist or likewise decision problem that could be feasible or what do you think?

It is easy to think of many different problems:

Converting sound to scores.
Converting scores to sound.
Automatic music composition.
Music analysis, for example key recognition.
Music classification, such as style recognition and artist recognition.

All of these things are actually being done.


Simplest way to check edge set for transitivity I'm playing around with tournaments and currently have the problem that I need to check whether a given subset of the edges of a tournament is transitive (it need not be acyclic). I'm aware that I can always take the transitive closure of the edge set and see whether it terminates without adding a single edge or not, but I was wondering if there might be a simpler way than that.

Note that I'm specifically going for simplicity, not efficiency; the tournaments I want to check are over a maximum of $7$ vertices, so complexity really isn't an issue. I would prefer simple, easy to implement ways. The simplest I could find so far is Floyd-Warshall, but maybe someone knows anything that's simpler still.

There's a very simple algorithm for this:

for each edge (u,v) in the graph:
    for each edge (v,w) in the graph:
        if (u,w) is not in the graph, return "Not transitive"
return "Transitive"

Basically, if the graph is not transitive, then you can always find some path of length two $u\to v \to w$ such that the edge $u \to w$ is not present in the graph.  If the graph is transitive, there won't be any such path of length 2.  So, just check this condition.


Prove that the total distance is minimised (when travelling across the longest path) Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have to return where I started.

As my specification is not really clear I made up an example: Consider the graph (which is a tree here - undirected weighted acyclic graph) to have nodes as cities and edges as roads between cities. I need to deliver something to every city (visit every node at least once). I can start from any city and end at any city that I choose to.

I read the following result. Find the two cities in the graph that are the farthest apart (call them $c1$ and $c2$). Start from one of them ($c1$ or $c2$), visit every other city along the way until I reach ($c2$ or $c1$). This minimises the total distance to travel.

How should I prove that this is the minimum distance ?

I attempted the following. I have the final route and I call edges, $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$. Where $m_1, m_2, ..., m_i$ are the edges along the cities that are the farthest apart ($c1$ and $c2$) and $e_1, e_2, ..., e_j$ are everything else in the graph. As I start from $c1$, I travel along edges labelled m exactly once and everything else labelled e is a digression and go back and forth twice on those edges, before I reach $c2$.

We know that $m_1, m_2, ..., m_i$ and $e_1, e_2, ..., e_j$ taken together include all the edges on the graph (as it is a tree, there's only a unique path between every two nodes). So the distance I travel could be given as $2(e_1 + e_2 + .... + e_j) + (m_1 + m_2 + ... + m_i)$.

I need to prove that this sum is less than every other route that I can take to reach all the cities. My intuition says that this has to be the shortest route. I feel that have to use the fact that $(m_1 + m_2 + ... + m_i)$ is the maximum between any two nodes in the graph somehow (is that called the diameter ?), and arrive at a contradiction.

This is the kind of picture I have in my mind (red edges are in ($m_1, m_2, ..., m_i$) and the grey ones are everything else),

That graph is still a tree (please ignore the arrow head in the edges that show how I decide to travel). I don't to where to go from here. I would appreciate a proof that is simple to understand (This is not a homework or anything related to coursework.)

Let $x$ be a vertex of your tree and consider a shortest route that visits every vertex and returns to $x$. It's easy to see that, regardless of the choice of $x$, any minimal route walks along every edge exactly twice: it must use each edge at least twice, or it wouldn't be able to get back to $x$; if it uses an edge more than twice, you can rearrange to avoid the backtracking.  Therefore, all such minimal routes have the same length, regardless of the choice of $x$.  Call that length $L$ (which is $2(n-1)$ if the tree is unweighted and there are $n$ vertices, but this isn't important).

Now, given a minimal route from $x$, let $y$ be the last vertex to be visited for the first time (i.e., the vertex which, when you first visit it, you say "Aha, now I've been to every vertex!").  The minimal route visits every vertex on its way from $x$ to $y$, and then returns immediately to $x$ along the unique shortest path.  Let $L_{xy}$ be the length of the walk taken from $x$ to $y$.  We know that $L=L_{xy}+d(x,y)$, and $L$ and $d(x,y)$ don't depend on how we got to $y$, so $L_{x,y}$ also doesn't depend on the route and we can say that $L_{xy}$ is the length of any minimal walk from $x$ to $y$ that visits every vertex.

The vertex $y$ must be a leaf: if it wasn't, when you first visited $y$, you wouldn't have visited any of the vertices "beyond" it.  Further, for any leaf $z$ of the tree, there are minimal routes from $x$ back to itself such that $z$ is the last vertex visited for the first time: let $v_1v_2\dots v_t$ be the path from $v_1=x$ to $z=v_t$ and don't go to $v_{i+1}$ until you've already visited every other descendant of $v_i$.

So, to get the longest walk from $x$ that visits every vertex, pick a route whose $y$ is the leaf at greatest distance from $x$.  None of the above depends on which vertex was chosen as $x$, $L_{xy}=L-d(x,y)$ is minimized by choosing $x$ and $y$ to be the vertices at greatest possible distance in the tree, which are both leaves.


Question about mapping reducibility I am working on an assignment where one of the sub questions is:

  Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \Sigma^* \to \Sigma^*$ such that for all $w \in \Sigma^*$, $w \in A$ iff $f(w) \in B$. Is it possible that $B$ is regular?

My take on this is that since context-free languages are on a 'higher' level than regular languages this is not possible. Apparently this is not the case, but I do not understand why.
Does anyone have a good explanation?

If $A$ is computable and $B$ is any nontrivial language (that is, $B \neq \emptyset,\Sigma^*$) then $A \leq_m B$. Indeed, pick $x \in B$ and $y \notin B$, and construct a computable reduction which decides whether its input is in $A$ or not, and outputs $x$ or $y$ accordingly.

Another issue you seem to be confused about is the meaning of context-free. The fact that a language is context-free doesn't preclude it from being regular. On the contrary, all regular languages are context-free.


Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n Could someone help me with these 2 questions?

I do not understand the case 3

$T(n) = T(n/2) + n \log n$
$T(n)=T(n/8)+2 n$

Let me show you how to solve these without using the master theorem. For the first item:

$$
T(n) = n\log n + \frac{n}{2} \log \frac{n}{2} + \frac{n}{4} \log \frac{n}{4} + \cdots \leq \left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) \log n \leq 2n\log n.
$$
This shows that $T(n) = O(n\log n)$. Since clearly $T(n) = \Omega(n\log n)$, we can conclude that $T(n) = \Theta(n \log n)$.

The second item can be solved in the same way.


Bloom filter variant I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits to set, this structure uses $m$ hash functions, and sets each bit with probability $p$.

This structure doesn't produce as low a false-positive rate as Bloom filters, but it seems to be extremely fast to compute, particularly if $m$ is some multiple of the machine word size and $p = 2^{-b}$ for some integer $b$: The hash functions can be computed in parallel by AND-ing $b$ independent $m$-bit hashes, and no dependent indexing or variable bitshifts are required.

I'm certain someone's come up with this idea before me, and done a lot more advanced analysis and comparison of it than I'm qualified to do. Is there a particular name for this type of structure?

Let's analyze how many hash bits you need in your new scheme versus a Bloom filter.

First of all, we need to agree about terminology.  I will use $q$ to represent the probability of a false positive.

For a Bloom filter the design problem of choosing $m$ and $k$ given that you want to hold $n$ elements with false positive rate $q$ is solved by $k = -\lg_2 q$ as the number of hashes, and $m=\frac{n k}{\ln 2}$ bits for the table.  (See the wikipedia page or several of the previous cs.se questions about Bloom filters.)  (This works out to a table with maximum entropy: your table is about half 1s and half 0s after $n$ insertions.)  The number of hash bits you need to produce per insertion is $k \lg_2 m$

Now your structure:  Let's assume that the desired $n$ and $q$ are the same.  $k$ and $m$ are going to be about the same, but now $k$ is going to be the average number of bits that remain set after ANDing your $b$ independent $m$-bit hashes.  How big does $b$ need to be?  Well you want the probability of any particular bit in your final hash to be about $k/m = p = 2^{-b}$.  So $b = -\lg_2 k/m = \lg_2 m - \lg_2 k$.  But that means that you have to generate $b m = m(\lg_2m-\lg_2k)$ hash bits, which is way more than $k \lg_2 m$.  For example, if $n = 709$ and $q = 1/16$ then $k = 4$ and $m = 4096$.  So a bloom filter would require $4 \times 12 = 48$ bits of hash, while your scheme requires $b = 10$ and a total of $40960$ bits of hashing.

Worse, there are some elements whose hash works out to 0 (i.e., whenever you look them up the probability of getting a false positive is 100%).  Suppose I AND together 10 different bit vectors of length $m$.  The probability that each bit will be set to 1 is 1/1024.  The probability that all the bits will be set to 0 is $(\frac{1023}{1024})^{4096}\approx e^{-k} \approx 0.0183$.


Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true? I'm trying to figure out if:

$\log^2n = O(n)$ and
$ n = O(\log^2n)$

are true or if one or both are false.

So far I've concluded that both are false because if $n = 8$ for the first one, then $\log^2 8 = O(8)$ which is false since it simplifies to $9 = O(8)$ which does not belong to $O(n)$.

For the second one, I believe it to be false as well because if $n = 1024$ or (some other big number), you get $1024 = O(\log^2 1024)$ which simplifies to $1024 = O(100)$. And 1024 does not belong to $O(100)$.

Am I right or is one of these true? Thanks.

You're right about the second one, but your reasoning for both is sketchy. The definition of $f(n)=O(g(n))$ is that there exist constants $c,N$ both greater than zero such that $f(n)\le c\cdot g(n)$ for all $n\ge N$.

Trying a single value for $n$ won't generally give anything in the way of an answer. Consider, though, the intuition we get from trying $n=4, 8, 16, 32, \dotsc$:
$$\begin{array}{lcccc}
n: & 4 & 8 & 16 & 32 & 64 & 128\\
\log^2 n: & 4 & 9 & 16 & 25 & 36 & 49
\end{array}$$

It seems to be the case that $n$ grows much faster than $\log^2n$. In fact, for this example we have that at least for powers of 2, $\log^2(n)=\log^2(2^k)=k^2\le 1\cdot2^k=1\cdot n$ for all $n \ge 16$, so we might suspect that $\log^2n=O(n)$, which is indeed the case, as it happens.

What is most helpful is to get an intuition of the big-O relationship between frequently-used functions. Here are some examples (all of which should be proved, but that'll be up to you do do or look up). Assuming everything in sight is positive, then:

$\log n = O(n^k)$ for any $k>0$. (polynomials beat logs, eventually)
If $a \le b$, then $n^a=O(n^b)$. (polynomials behave as expected, by degree)
If $a>1$, then $n^k=O(a^n)$. (exponentials beat polynomials)

and so on. The point here is that it's far better to develop your intuition and only use the definition of big-O when faced with a problem where intuition doesn't give you any help. That's what the experts do.


Hardness of problem related to number of subsets that satisfy a particular property I have the following algorithmic problem.  I am given a set of elements.  Each element has a set of properties.  For example:

A: has properties p1, p2, p4
B: has properties p2, p4
C: has properties p2, p1

The task is to find the number of subsets of elements, where the union of the properties of the elements in the subset are equal to some predefined set.

For example if the predefined set is:

{p2}, then the answer is 0, because there are no subsets with a union of {p2}
{p1, p2, p4}, then the answer is 5, because we can take {A}, {A, B}, {A, C}, {B, C}, {A, B, C}

This problem seems like it might be hard (e.g., NP-hard), but I can not find anything similar in this list of NP-complete problems.  I do realize  that this is only small subset of NP complete problems.

Is there an efficient algorithm for this problem?  Or, is it NP-hard, and if so, how can we prove that?

The problem is NP-hard: in fact, it is #P-complete.  Therefore, it is unlikely you'll be able to find an efficient solution for this problem.  The proof is by reduction from #Monotone-SAT.

As Ricky Demer explains, without loss of generality we can take the "predefined set" to be equal to the union of all properties.  (If the predefined set is larger than that, the answer to your problem is 0.  If the predefined set is smaller than that, then we can remove all elements that mention a property not found in the predefined set, and we get a new problem instance with the desired property.)  So let's focus only on this case.

Here is the reduction from #Monotone-SAT.  Suppose we have a CNF formula $\varphi$ over $n$ variables and with $m$ clauses, where all of the literals in each clause are positive (i.e., no variable is negated).  Then we can define an instance of your problem that corresponds to $\varphi$.  The problem instance has $n$ elements, one element for each variable, and $m$ properties, one property for each clause.  The set of properties of a variable is just the set of clauses that mention that variable.  Then the number of solutions to this problem instance is exactly the number of satisfying assignments to $\varphi$.

It follows that your problem is exactly as hard as #Monotone-SAT: any algorithm for your problem gives a solution to #Monotone-SAT.  However, it is known that #Monotone-SAT is #P-complete.  (In fact, we can make a stronger statement: #Monotone-2SAT is also #P-complete.)  It is widely believed that #P-complete problems cannot be solved in polynomial time.  Thus, there is unlikely to be any polynomial-time algorithm for #Monotone-SAT -- or for your problem.

That's the bad news.  Now one slight bit of hope.  There are off-the-shelf #SAT solvers out there that you could try applying to your problem.  See, e.g., https://cstheory.stackexchange.com/q/1295/5038 for some pointers.  Now you shouldn't expect them to be efficient -- they are subject to the same hardness result, and so they might be very slow for all but small problem instances.  However, if you absolutely must solve your problem in practice, this is something you could try.  There are also tools for approximate model counting, which could be used to compute an approximation/estimate for the number of solutions to your problem -- however, again, this is a hard problem and you shouldn't expect algorithms with a good worst-case running time.

My thanks to Ricky Demer for the key insight that enabled me to recognize the relationship to #Monotone-SAT.


How can there be undecidable languages in P/1? I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me.
as I learned in class,
a turing machine M accepts language L with advice $ {a_n} $ if
$\qquad\displaystyle M(x, a_{|x|}  ) = 1 \iff x \in L$.

Does it mean that M with the advice decides L (halts on every input)?
or recognizes L? (accept every x in L but may not halt on x that is not in L)

Generally, if a language L is in P it means that there is polynomial time machine that decides it right? I feel like it really confused me.
then we defined:
$ P/POLY $ = union of (DTIME($n^{k_1}),  n^{k_2})$ on every $k_1,k_2$ in $N$ .
we proved in class that there is a unary language which is undecidable,
and that every unary language is in $P/1$.
that means that there is language in $P/1$ which is undecidable.

I don't understand it because $P/1$ is in $ P/POLY $ . as I understand by the definition, there is poly time machine that decides it.. so what do I get wrong?

if $L\in P/poly$ then there is a machine that decides any input $x$,  given the advice $a_{|x|}$.

However, if the advice is not given, maybe no machine can decide $L$. This is what happens in the unary case. Note that the machine doesn't know the advice and cannot compute it, i.e.,  the set of advices (for a specific $L$) may be an undecidable language.

On the other hand, if someone gives you this (possibly undecidable) set, you have more power at hands. Similarly, if you can compute this set (for a certain $L$), say get $a_n$ in $f(n)$ time, then $L$ clearly belongs to $DTIME(poly(f(n)))$.


What is the complexity of timing a turing machine? I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$.
It returns yes if $F(i)$ halts in less than $n$ steps, otherwise it returns no.
What is the time complexity of this problem in terms of $n$, is it $n\log n$ as it is similar to a universal Turing machine, or does the counting each step mean it takes longer.

Let S (F, i, n) = the number of steps that F (i) takes until it halts, if it halts in n or fewer steps, and n if F (i) doesn't halt in n steps. Then you can simulate the Turning machine and get the result in O (S (F, i, n)) steps.

If this were important to you, then you could examine a few Turing machines, and see if you can detect patterns in their operation. For example, you might detect a pattern that indicates the Turing machine is trying to add two numbers x and y, and you might be able to analyse how many steps this will take and what state the Turing machine is afterwards; if you do this then you might often get a result in substantially fewer than c * N steps.

Or in your simulation, you might detect that the Turing machine enters the exact same state that it entered before; in that case it won't ever halt.


Are there FPTASs for the min cost flow problem? In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs for the min cost flow problem?

Possibly, there is no need for an FPTAS here since an optimal solution can be computed very fast (using double scaling or the enhanced capacity scaling algorithm, for example). But from a theoretical point of view, this would be interesting to know.

If an optimal solution can be calculated in polynomial time, then the same algorithm gives you an FPTAS.

There might, however, be quasilinear time algorithms which give better and better approximations, running faster than algorithms for computing the min cost flow exactly.


Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence

$$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$

by applying the Master Theorem.

I am very confused by how it is done. So, $a=3, b=4, f(n) = n\cdot \log(n)$
First step is to compare $n^{\log_b a} = n^{\log_4 3}= O(n^{0.793})$ with $f(n)$.

I have no clue on how they compared this. The book explains:

  $f(n) = \Omega (n^{\log_4 3+\epsilon })$, where $\epsilon \approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n).$

Followed by:

  For sufficiently large n, we have that: $af\left(\frac{n}{b}\right) = 3\left(\frac{n}{4}\right)\log\left(\frac{n}{5}\right) \le\left(\frac{3}{4}\right)n \log n = cf(n)~ for~ c=\frac{3}{4}.$

Where did $3\left(\frac{n}{4}\right)$ come from?

If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold:

  $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

Our recurrence is defined as $$T(n) = 3T(n/4) + n \log n.$$

By definition we have, $a = 3, b = 4, f(n) = n \log n$.

We now need to show that $f(n)$ is polynomially larger than $n^{\log_b a}$. That is the "$f(n) = \Omega(n^{\log_b a + \epsilon})$" part from above. Defining $\epsilon \approx 0.2$ achieves this. The reason being that $\log_4 3 \approx 0.793$ and $f(n) = \Omega(n^{0.793 + \epsilon})$.

We are left to show that $f(n)$ satisfies the regularity condition. That is the "$a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$" part.

We simply plug in our values of $a,b$ to get: $$a f(n/b) = 3(n/4) \log (n/4).$$ All we did was take the "$n$" in $f(n)$ and plug in "$n/4$".

To make this easier to see, let $k = n/4$ and observe that $a f(k) = a k \log k$. Swapping $k$ with $n/4$ we have $$3(n/4) \log (n/4) \leq (3/4)n \log n = c f(n)$$ where $c = 3/4$.

This finishes our necessary requirements and we have that $T(n) = \Theta(n \log n)$.