Strahler of tree like refutations I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the last part of the demonstration of the Lemma 3 (in bold). For this, I get an example. Let be $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$ then its tree-like refutation is:

Following the demonstration of the last part of the Lemma 3 (in bold), $[b\rightarrow 1]\Gamma=(1)(a)(a'+c)(a'+c')$, and adding the literal $b'$ where $[b\rightarrow 1]$ has removed it, we get $\Gamma' = (1)(a+b')(a'+c)(a'+c')$. In accordance the paper the tree-like refutation of $\Gamma'$ is a proof for $\Gamma \vdash b'$. According to the paper, similarly, for $[b\rightarrow 0]$, $[b\rightarrow 0]\Gamma = (a)(a'+c)(a'+c')$, and adding the literal $b$ where $[b\rightarrow 0]$ has removed it, we get $(a+b)(a'+c)(a'+c')$. My questions are,

1) Is there any difference between these Strahlers? for me there is not any difference, but why the author consider the function $\max$?

2) From the demonstration,

  Adding a cut of $x$ to these two proofs, we get a proof of $\Gamma \vdash \Box$.

Is it a rule of sequente calculus, if yes, following wikipedia Could you help to identify who are $\Sigma$, $\Pi$, $\Delta$ and $\Sigma$?

What means cut of $x$?

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.

You have asked (at least) two questions. The answer to your first question is that sometimes it is much easier to refute a formula given that $x=0$ compared to given $x=1$. Hence the $\max$. In other cases, $x=1$ is easier. That's why we need to go over both possible values of $b$. Finally, the reason why the formula in part 3 of the lemma also maximizes over the variable $x$ is that $x$ represents the last variable which is cut (the one at the root of the tree).

The answer to your second question is as follows. The cut rule allows deriving $a \lor b$ given $a \lor x$ and $b \lor \bar{x}$. Here $a,b$ are arbitrary formulas, in this context clauses. In particular, from $x$ and $\bar{x}$ you can conclude contradiction. The cut rule is the only rule in the resolution proof system.


Finding lowest point in circles Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking  for a simple randomized incremental algorithm.
There are some circles in the plane, these circles have an intersection R, the point with the lowest y in R is what i mean.
Why i thought of RIC is that maybe we can add circles incrementaly and updating the intersection area each time and also the optimal point should be updated if it possible with the lower time.
I think this problem have some similarity with 2D half-plane intersection (2D LP). In that problem we were looking for an optimal point in respect of the cost vector.  But subproblems in that problem was finding the intersection between a half-plane and a convex region with can be reduced to a simpler 1D problem. That 1D problem is half-line intersection, which is easier to solve.
Here but i have trouble to define a simpler subproblem. Also in the Analysis for expected time, i don’t see how to use backward analysis here.
I also guess maybe we can solve this problem with finding the convex-hull of those circles, then we look for it’s core with half-plane intersection, but i really uncertain about this idea.

I suspect you should be able to solve this with a sweepline algorithm, probably in $O(n \log n)$ time or something like that.
In particular, I suggest you build a data structure so that for any $x$, you can find the range of $y$-values that are in the intersection of all the circles.  You should be able to build such a data structure by mimicking the Bentley-Ottmann algorithm.  Decompose each circle into four quarter-circles (arcs that cover one-fourth of the perimeter of the circle).  Each quarter-circle takes the place of a line segment.  Each intersection between two quarter-circles is an "event".  Then it is easy to answer your original question; each interval of $x$ values between two consecutive events corresponds to a single leaf in the tree, and you can quickly compute the lowest $y$ value in the intersection for that range of $x$ values, then do that for each such interval.  I haven't tried to work through all the details, so I suggest you check the specifics to see if this works out or if there is some challenge I've overlooked.


Help with performance and speed-up question related to number of cores and their areas There is a question in my exam that said:

Consider the following three processors (x, y, and z) that are all of varying areas. Assume that the single-thread performance of a core increases with the square root of its area.

Processor X, core area = A

Processor Y, core area = 4A

Processor Z, core area = 16A

You are given a workload where S fraction of its work is serial and 1 - S of its work is infinitely parallelizable.
a. If executed on a die composed of 16 Processor X's, what value of S would give a speedup of 4 over the performance of the workload on just Processor X?
b. Given a homogenous die of area 16A, which of the three processors would you use on your die to achieve maximal speedup? What is the speedup over just a single Processor X? Assume the same work load as in part b.

My progress with this part so far:
In an area of 16A, 4 cores of Y would fit. The square root of its area is $2\sqrt{A}$, which each of the four cores' performance would increase by a factor of two? Using Amdahl's law,
Overall speed-up for this choice $=\dfrac{1}{\dfrac{1 - S}{4(2)?} + S}$
And likewise, the overall speed-up for choosing 1 core of Z $=\dfrac{1}{\dfrac{1 - S}{1(4)?} + S}$
I am assuming that 1 core of area 4A is like 2 cores of area A, is this a valid assumption? For S = 0.2, 4 cores of Y would yield a higher speedup than one core of Z. Is this reasoning correct?

The problem in an exam is that you need the answer that is expected from you - something I’d have a real problem with. So keep this solution to yourself.

Speed up is always hard to calculate - calculating execution time avoids lots of fractions and is equivalent. Assume your task would take one second on one processor X.

Since S is serial, you need at least S seconds. In that time, your 15 remaining cores can do 15S worth of work. If 15S >= 1-S or S >= 1/16 then all work is done after S. if S <= 1/16 then all cores can work on the task simultaneously, so the work takes 1/16 time. So time = max(S, 1/16) and speed up = min (1/S, 16). Speed up = 4 when S = 1/4.

You can have four processors of type Y at twice the speed or 1 of type Z at four times the speed. The work takes half of max(S, 1/4), that is max (S/2, 1/8) on 4 processors of type Y and it takes 1/4 on one processor of type Z.

X is fastest when S <= 1/8. Y is fastest for 1/8 <= S <= 1/2, and Z is fastest for S >= 1/2.


How to determine if a state is a fixed point in a Hopfield network? I have been reading a lot and I am still unsure of how to determine this. Let's say I have an initial binary state vector (1, 1, 1). How would I go about determining whether (1, 1, 1) is a fixed point in the network?

My initial understanding was to put the state through the network and if it converged to (1, 1, 1) then it is a fixed point. However I have a feeling it is not as simple as that.

Thanks.

It's as simple as that.  Write out the state equation.  Substitute the state vector.  Verify that equality holds.   If it does, then you have a fixed point.

Note that what you're calling a state vector probably isn't one in the typical definition of that term.  The vector of neuron inputs is usually called the state vector. It would be unusual (though of course not impossible) for this to be all 1's.

If what you actually have is the output vector, then you can solve for the state vector using the feedback function.  Then verify the resulting state vector is consistent with the outputs.  If so, then you have a fixed point.


AdaBoost - why using such alpha function? I'm reading the paper where AdaBoost was invented (link), and I couldn't understand why they have chosen the formula α_t = 1/2 * ln((1-ε_t) / ε_t).
snippet:
AdaBoost algorithm from the paper
What is the motivation behind that specific formula?
Why not using something that feels more natural like ε_t?

Recall that the final hypothesis after $T$ rounds is $h_T(x)=sign\left(\sum\limits_{i=1}^T \alpha_t h_t(x)\right)$, i.e. $\alpha_t$ is the weight of $h_t$ in $h_T$. If $\epsilon_t$ is high (near one) you want to answer the opposite of $h_t$, so you want $\alpha_t$ to be negative and very large in absolute value. If on the other hand $\epsilon_t$ is very low then you want $\alpha_t$ to be very large. The worst case is $\epsilon_t=\frac{1}{2}$, in which case $h_t$ is of no use to you.
The function $\log\frac{1-\epsilon_t}{\epsilon_t}$ satisfies those properties. This magnitude is known as log odds (where the probability considered is $p=1-\epsilon_t$, the success probability). Intuitively, the odds ratio tells you how often an event with probability $p$ occurs, in our case if e.g. $\epsilon_t=1/3$ then $\frac{1-\epsilon_t}{\epsilon_t}=2$, i.e. $h_t$ is expected to succeed with ratio $2:1$.


Time complexity to check if there is an edge between two nodes in an adjacency list I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why time complexity in an adjacency list to check would be $O(|V|)$, where $V$ represents the vertices. Shouldn't it be $O(|E|)$ instead? Because in the worst case, it needs to traverse through all of the elements (edges) in a linked list of a certain vertex.

In an adjacency list each vertex $u \in V$ is associated with a list of adjacent vertices.
Given a graph $G=(V,E)$, in order to check if the edge $(u,v) \in E$ you need to check whether $v \in \text{adjacent[u]}$.
A node can have at most $O(|V|)$ neighbors, from here the complexity follows.


Bipartite graph minimal amount of vertices required I have a bipartite graph made of two sets (SET 1 and SET 2) and I want to determine how many vertices from the SET 1 I can remove while still having
every vertex of the SET 2 connected to at least one vertex of the SET 1.

In this example, E and F can obviously be removed as D and C are connected 5 and 6.
But we could also remove B as A and C together cover more points. But so far I only have a very slow implementation of this which is to compare every vertex of SET 1 to every combination of vertices of SET1.
Is there any smart way to do this? I've been thinking about Kőnig's theorem but I didn't find a way to use it in this context as it seems to be made for undirected bipartite graphs.

Also, there are some constraints the input follows:
-Every element of SET 2 is connected to SET 1
-Every node of SET 2 is connected exactly to two vertices of SET 1

Let's define a graph $G=(V,E)$, for which:

Set of vertices $V$ is identical to your SET1.
Two vertices $v_1,v_2 \in V$ are connected by an edge, if and only if there exists a vertex from the SET2, incident to both $v_1$ and $v_2$ in your bipartite graph.

For instance, the graph below corresponds to the bipartite graph from the example in your question:

Now, your problem is reduced to the Minimum Vertex Cover problem on the graph $G$, defined above, so you'll be able to use known algorithms to find minimum vertex cover in your SET1 only.

This graph $G$ doesn't have any special structure, which could be used to find its minimum vertex cover more effectively than in general case. Also, any graph can be transformed to your bipartite graph form by splitting each edge by a new vertex. So, it means that your problem is equivalent to the minimum vertex cover problem, which is NP-complete - thanks to @narekBojikian for mentioning that in his answer.


Convergence of Simulated Annealing Based Algorithms I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge fast (based on satisfying some properties) to global/local optimal point and doesn't oscillate in the optimal points (or any related fast about its stability). Are there any useful literature about it?

I copied this answer from computational science

There is a theorem that syas that a black box algorithm is guaranteed to find the global minimum of an arbitrary smooth (i.e., twice continuously differentiable) function if and only if it samples points densely in the search space.

Here dense is meant in the topological sense, i.e., it must sample points in arbirarily small neighborhoods of every point.

In this case, the worst case complexity is O((dδ)−n), [the Latex parser chokes with nested big brackets] where d is the diameter of the search space and δ the guaranteed error in x

Edit: While this looks like being the worst case complexity for locating an δ-accurate x rather than for locating a point for a ϵ-accurate f, the complexity for the latter is as bad (even for the rather big value of ϵ=(ffirst−fglobal)/2), as one can easily construct a smooth function which interpolates all data points so far but takes much smaller values in the center of the largest open ball not containing one of the points evaluated.

Thus guaranteed convergence to a global minimum is worthless in practice. (For example, uniformly random search has a convergence guarantee to the global minimizer, whereas most practically fast algorithms don't have one.)

Note that simulated annealing usually performs much worse than modern methods. Rather use code recommended in:

Comparison of derivative-free optimization algorithms (2012, by Nick Sahinidis)

Black-Box Optimization Benchmarking (BBOB) 2012 (by Auger, Hansen, et al.)


Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free grammar that describes this language. After defining a context-free grammar I want to formally prove that this context-free grammar describes this language.

I've came up with the context-free grammar production rules:
$$
\begin{align*}
&S\to0S1S \\
&S\to1S0S \\
&S\to\epsilon
\end{align*}
$$
Is this the correct context free grammar to define this language?

Im kind of stumped for the proving part. I'm guessing I will need some sort of induction?

Your grammar does work. And you are correct in assuming that induction is a worthwile proof-technique. As a hint, you can use the following induction hypothesis:

IH: All the words of length at most $n$ that can be derived from $S$ have an equal amount of $0$'s and $1$'s.

Can you fill in the anchor and step from here?

As D.W. pointed out, the above is only enough to prove that the grammar will not produce any wrong words, or $L(G) \subseteq L$. In order to complete the proof, you also need to show that $L \subseteq L(G)$, i.e. all the words in the language are generated by the grammar.

For this part you can try an induction with the hypothesis

IH: All the words of length at most $n$ that have an equal amount of $0$'s and $1$'s can be derived from $S$.

(Of course, you can combine these two inductions, but having them seperate may be easier to handle if you are unexperienced.)


How to be sure of a good solution in hyperparameter optimization I have a very expensive black-box function and at least 15 parameters that I want to explore (usually 5-6 at a time). So far I have tried Genetic Algorithms and Gaussian Process Surrogate Optimization (bayesian optimization). Both methods work fine and efficiently up to 5-6 parameters. However, I am having an issue on how can one be sure that a solution found by GA/GPSO is a good solution, without basically knowing nothing about the output space. I don't really want to go for an exhaustive grid search since even with 5 parameters, it requires incredible amounts of evaluations, yet I cannot come up with anything better.

I would also very much appreciate suggestions/keywords for literature reading, or event different methods for hyperparameter optimizations.

Thanks in advance

The short answer: You can't.  These are heuristics.  There are no guarantees.  They might fail badly; and there's no reliable way to detect that.


Closed-form expression for the sums of the rows of the Trinomial triangle There is a question in the second chapter of the book that I'm unable to solve, and unfortunately algorist.com does not provide a rigorous enough solution, or maybe I can't quite understand it.
Here is the question:

I've noticed the sums of rows are the powers of 3, and it's intuitively obvious that the sums of rows are multiples of 3, however I can't prove that they are powers of 3.
Any help would be much appreciated.
The Algorithm Design Manual from Steven S. Skiena
You can get it from here.
Also here is the solution I found on algorist.com .

Intuitively, each integer on the $i$-th row participates exactly three times in the sum of the integers on the $(i+1)$-th row. This means that the sum $S_{i+1}$ of the integers in the $(i+1)$-th row must be exactly $3$ times as large as the sum $S_i$ of the integers in the $i$-th row, i.e., $S_{i+1}=3S_i$ (and $S_1=1)$.  A formal argument is as follows:
Let $x^{(i)}_j$ be the $j$-th integer on the $i$-th row and define $S_i = \sum_{j=1}^{2i-1} x^{(i)}_j$. For simplicity define $x^{(i)}_j = 0$ whenever $j \le 0$ or $j \ge 2i$. You can show by induction on $i$ that $S_i = 3^{i-1}$.
The base case $i=1$ is trivially true since $S_1 = x^{(1)}_1 = 1 = 3^0 = 3^{1-1}$.
Suppose now that the claim holds for $i\ge 1$. Then, the claim must also hold for $i+1$. Indeed:
$$
\begin{align*}
S_{i+1} &= \sum_{j=1}^{2i+1} x^{(i+1)}_j = \sum_{j=1}^{2i+1} \left( x^{(i)}_{j-2} +  x^{(i)}_{j-1} + x^{(i)}_{j}\right)
= \sum_{j=1}^{2i+1}  x^{(i)}_{j-2} +  \sum_{j=1}^{2i+1}  x^{(i)}_{j-1} + \sum_{j=1}^{2i+1}  x^{(i)}_{j} \\
&= 3 \sum_{j=1}^{2i-1} x^{(i)}_{j} = 3S_i = 3 \cdot3^{i-1} = 3^i.
\end{align*}
$$


probability of collision my data's range is from 1 to 9 and I have two subsets of integers from this range.
the hash function takes each of this subsets and calculate product of these three integers and maps this set to the result of this multiplication.I want to know the probability of collision by this hash function with this two subsets of integers that they are from 1 to 9 and the size of each subset equals 3.

I made a program to brute force this.

This means that a very close low bound of this would be $\frac{36}{441}$, so a not that big chance.

If you wanted to avoid overlaps, I suggest you either use a different algorithm or block out all the duplicates, because the chance of this overlapping is pretty high ($8\%$).


Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones? Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages.
Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free languages as well?

Before giving the answers, some discussion on your direction for the proof:

It is highly unlikely that a proof of this claim would use the containment $REG\subseteq CFL$, since the pumping lemma is not an exact characterization, and if a language satisfies the regular pumping lemma, it doesn't proof that the language is regular.

Thus, the proof will have to go into the "guts" of the lemmas.
Now for the proof:

Consider a language $L$ that satisfies the regular pumping lemma. Thus, there exists some $p>0$ such that for every word $w\in L$, if $|w|>p$, then there exists a partition $w=xyz$ such that $|xy|\le p$, $|y|>0$ and for every $i$ it holds that $xy^iz\in L$.

We want to prove that there exists some $q>0$ such that for every word $w\in L$, if $|w|>q$, then there exists a partition $w=uvstr$ such that $|vst|\le q$, $|vt|>0$ and for every $i$ it holds that $uv^ist^ir\in L$.

Seeing things stated as above, the rest is just "pattern matching":
Let $q=p$, and consider a word $w\in L$ such that $|w|>q$, then there exists a partition $w=xyz$ as above. Let $u=x,v=y,s=\epsilon,t=\epsilon$, and $r=z$. Clearly $uvstr=xyz=w$. Also, $|xy|\le p$, so $|vst|=|y|\le p$ and $|y|>0$ so $|vt|=|v|=|y|>0$. Finally, for every $i$ it holds that
$$uv^ist^ir=xy^iz\in L$$
and we are done.


Graph Traversal Solutions for "Find all unique paths" Problem I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with the constraint that it can only move down or to the right.

It looks like the standard way to solve this is with the top-down dynamic programming approach but I was wondering if a graph traversal algorithm could also work.

The problem with graph traversal algorithms is that you do not revisit nodes that you have already seen but many unique paths can visit the same node.  So if you got rid of the constraint that you cannot revisit a node, would a graph traversal method work here? This is also a special case where you cannot get stuck in an infinite loop because the robot can only go down or right so it can never go back to a node it has already been to.

There could be many paths. For example, if the grid is $n \times n$ and all edges are present, then there are $\binom{2n}{n} = \Theta\left(\frac{2^n}{\sqrt{n}}\right)$ paths. You don't want to be going through all of them. Using dynamic programming, you can come up with the answer without going over all paths individually. In other words, dynamic programming is much more efficient than your suggested algorithm.


Longest substring with consecutive repetitions I want to find the longest substring which is repeated without any gap between the repetitions.  That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring of $x$.

What I mean is the following cases:

In "aa"         I want "a"    with a position of 0 and repetition of 2
In "aaab"       I want "a"    with a position of 0 and repetition of 3
In "abc"        I want ""     (false or whatever)
In "abababc"    I want "ab"   with a position of 0 and repetition of 3
In "aaabbbb"    I want "b"    with a position of 3 and repetition of 4
In "eabcdabcde" I want "abcd" with a position of 1 and repetition of 2
In "cababcab"   I want "ab"   with a position of 1 and repetition of 2 (not 3, because of the "c" between the three "ab"'s)

I've been looking at various suffix and prefix algorithms, but none of them has the "no gaps" part build into it. Both LCP arrays and Suffix arrays seems to suffer from this.

Googling for "Longest repeated substrings" gives me algorithms which e.g. find "hello" in "abcdehellofghijhelloklmn", but this is not what I want.

From what I understand you are looking for maximal substrings of the form $y^k$ for $k\ge 2$. By some this is called a repetition in a string. One of the first to give an algorithm for finding these is Maxime Crochemore: An optimal algorithm for computing all the repetitions in a word, Inform. Process. Lett. 12 (1981) 244-248. From what I understand his approach has been reformulated in terms of suffix trees and arrays.


LCA from children using bottom up approach? I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom up without using depth.

How would I go about traversing the tree, starting from any 2 arbitrary nodes, each of which points to a previous node as shown without a depth variable?

Here is one approach. Given leaves $\alpha,\beta$, first compute the depths $d(\alpha),d(\beta)$ of both leaves (to compute the depth of a leaf, measure how many times you need to apply the parent operation until you reach the root). Suppose without loss of generality that $d(\alpha) \geq d(\beta)$. Replace $\alpha$ with $\alpha$'s $(d(\alpha) - d(\beta))$'th parent. The least common ancestor doesn't change, and so we can assume without loss of generality that $\alpha$ and $\beta$ are at the same depth.

If $\alpha = \beta$, then $\alpha$ is the least common ancestor. Otherwise, replace both $\alpha$ and $\beta$ with their parents. This doesn't change the least common ancestor. Continue like that, and eventually you will find the least common ancestor.


is it possible to reduce $HALT_{TM}$ to $E_{TM}$? I am wondering, if it is even possible: is it possible to reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$?

$HALT_{\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }w\}$

$E_{\text{TM}} =\{\langle M\rangle\mid M\text{ is a TM and } L\left(M\right)=\emptyset \}$

I tried to look online, in summaries and handouts and even in several books (including Sipser's book), but couldn't find any indication on it.

is it possible? if so, how?

Nice question.
No, you cannot reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$, although you can reduce $HALT_{TM}$ to $\overline{E_{\text{TM}}}$. Here we are talking about Turing reduction.
$HALT_{\text{TM}}$ can be reduced to $\overline{E_{\text{TM}}}$
Let $\langle M,w\rangle$ be such that $M\text{ is a }TM\text{ and }M\text{ halts on input }w$.
Now let us construct a TM $M'$. On an arbitrary input $u$, $M'$ will check whether $u$ is the same as $w$.

if it is not, $M'$ will run forever.
if it is, $M'$ will simulate $M$ on input $w$. Then once $M'$ halts, $u$ is considered as accepted.

We can make the transformation from $M$ to $M$ be algorithmic, thanks to the existence of a universal TM machine.
It is routine to verify that $\langle M,w\rangle$ is in $HALT_{TM}$ if and only if $M'$ is in $\overline{E_{\text{TM}}}$.
$HALT_{\text{TM}}$ cannot be reduced to $E_{\text{TM}}$
For the sake of contradiction, suppose $HALT_{\text{TM}}$ is reduced to $E_{\text{TM}}$ by reduction $f$. Then $\overline{HALT_{\text{TM}}}$ is reduced to $\overline{E_{\text{TM}}}$ by reduction $f$ as well. Since $\overline{E_{\text{TM}}}$ is Turing-recognizable, so is $\overline{HALT_{\text{TM}}}$. Since $HALT_{\text{TM}}$ is Turing-recognizable, we have $HALT_{\text{TM}}$ is decidable, which is known to be false, however. This contradiction shows that $HALT_{\text{TM}}$ cannot be reduced to $E_{\text{TM}}$.


Why does the cut $(V_C,V-V_C)$ respect $A$? Corollary 23.2
Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, and let $C = (V_C,E_C)$ be a connected component (tree) in the forest $G_A = (V,A)$. If $(u,v)$ is a light edge connecting $C$ to some other component in $G_A$, then $(u,v)$ is safe for $A$.
Proof The cut $(V_C,V-V_C)$ respects $A$, and $(u,v)$ is a light edge for this cut. Therefore, $(u,v)$ is safe for $A$. $\quad\blacksquare$

I did understand the original proof for the Cut property in CLRS (Theorem 23.1). But I am unable to grasp how does the above corollary follow from the original proof? Why does the cut $(V_C,V-V_C)$ respect $A$?

The cut $(V_C,V-V_C)$ respects $A$ since $C$ is a connected component in $(V,A)$.


Matrix multiplication in recurrent neural networks I was looking at a tutorial for recurrent neural networks in Python, and I have a question in regards to multiplying matrices of different sizes. Specifically, why does S[t] have 100 elements in it?

  s[t] = np.tanh(self.U[:,x[t]] + self.W.dot(s[t-1]))

Earlier in the tutorial, the author lists the dimensions for each variable:

  \begin{aligned} x_t & \in \mathbb{R}^{8000} \\ o_t & \in \mathbb{R}^{8000} \\ s_t & \in \mathbb{R}^{100} \\ U & \in \mathbb{R}^{100 \times 8000} \\ V & \in \mathbb{R}^{8000 \times 100} \\ W & \in \mathbb{R}^{100 \times 100} \\ \end{aligned}

From how I understand the above line of code, it multiplies U by x[t] and adds it to the product of W and s[t-1], then computes tanh for each element.

Sources like this say that you cannot add matrices of different dimensions, however that seems to be what is happening here (because multiplication is just repeated addition). In fact, it seems that U is 2D and x[t] is 1D. How are these added? Also, how is the sum of the two products then 100 elements?

Matrix-by-matrix multiplication is very different from scalar-by-scalar. It has no connection to repeated addition, and in fact isn't even commutative: it's entirely possible that $AB \neq BA$. It's only called multiplication because it has some similar properties to repeated addition of scalars.

Matrix multiplication requires that the inner dimensions match. Nothing more, nothing less. You can multiply an (a×b) matrix by a (b×c) matrix, for instance, and the result is an (a×c) matrix. For the full details, Wikipedia has a good summary.

In addition, that code isn't adding or multiplying $U$ and $x[t]$. Rather, it's removing one dimension from $U$, taking only the columns (or rows depending on your definitions) which correspond to 1s in $x[t]$.


Trying to verify the solution to a lambda calculus equation I am going through the following introduction to lambda calculus :

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf

At page 12 , the following has been asked to prove

$ \exists $ $ G $ $ \forall X $ such that

$GX$ = $GG$

This means to find a function which takes a function as an argument and returns the same expression irrespective of the function .

The book posits the solution to be $ G $ = $Y$ $(  \lambda gx. gg) $

On trying to verify this I first evaluated the L.H.S to be

$ GX $ = $ Y ( \lambda gx.gg ) $ $X$.

Now $X$ being the argument will be picked up by the first bound variable  so .

$L.H.S $ = $ Y ( \lambda x . XX) $ =  $( \lambda x . XX)$  $ Y ( \lambda x . XX)
$ = $ Y ( \lambda x .$ $ Y ( \lambda x . XX)$ $ Y ( \lambda x . XX)$)

Here  due to the presence of the form $ YF $ , I can carry on the reduction continuously  by replacinf $YF$ with $FYF$

$R.H.S$ =  $Y$ $(  \lambda gx. gg) $ $Y$ $(  \lambda gx. gg) $
           = $Y$$ \lambda  x.$ $( Y(  \lambda gx. gg) $ $Y(  \lambda gx. gg)) $

Now similarly  the reduction can be carried on further by again consuming the first $g$ that comes in the expression with  $Y(  \lambda gx. gg)) $ and this can on perpetually and it will look like   $ Y ( \lambda x .$ $ Y ( \lambda x . XX)$ $ Y ( \lambda x . XX)$).....
So I couldn't completely ascertain that they ( L.H.S and R.H.S) will turn out to be equal but I can  see that L.H.S and R.H.S are going to be infinitely long  and will resemble each other more and more as the number of reductions go on since  the $ g$ 's in the R.H.S will continually get replaced .

Is this logic correct ? If not , where did I err ?

P.S. : On a general and on a lighter note , how are this lambda calculus equations solved ? (They look analogous to differential equations ).

On trying to verify this I first evaluated the L.H.S to be

  $ GX $ = $ Y ( \lambda gx.gg ) $ $X$.

  Now $X$ being the argument will be picked up by the first bound
  variable  so .

  $L.H.S $ = $ Y ( \lambda x . XX) $

This is where you went wrong, and the reason is that you've got the association the wrong way round. $Y ( \lambda gx.gg ) X$ means $(Y ( \lambda gx.gg )) X$.

Taking that into account, the only evaluation step possible is to apply $Y$, giving $$( \lambda gx.gg )(Y ( \lambda gx.gg )) X$$ which is $( \lambda gx.gg )GX$, from which the desired conclusion is immediate.


What makes lambda calculus relevant to study? I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based on this definition from the Stanford Encyclopedia of Philosophy, it's just another notation for functions.

If it is just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?

In computer science we want to analyze and understand source-code with mathematical rigour. That's the only way to prove interesting properties (such as termination) with absolute certainty. For that we need a language with a very well-defined meaning for every construct.

In theory this could be any language with a good formal semantics. But to make things less complicated and less prone to error, it's best to use a language that is as simple as possible but still able to express any program (i.e. is Turing complete). For reasoning about imperative code, there are Turing machines. But for reasoning about functional programming, there is the $\lambda$-calculus.

The basic $\lambda$-calculus is like a functional programming language, but with a lot of 'baggage' taken out. It's not important that this be a nice language to actually write programs in, nor that it be an efficient language. Just that it is simple and expressive. For example, we don't need loops, because we can simulate them with recursion. And we don't need functions with multiple parameters, since we can simulate them with Currying.

Now, at some point you may want to prove properties about constructs that are not part of the basic (untyped) $\lambda$-calculus. That's why computer scientists have extended it in different directions over the years. For example, to reason about type-systems there are a great many variations of typed $\lambda$-calculi.


DFA to regular expression conversion I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.

The question, I was trying to solve is:

I have got the following equations:

$Q_0=aQ_0 \cup bQ_1 \cup \epsilon$

$Q_1=aQ_1 \cup bQ_1 \cup \epsilon$

When solved, we will get $Q_0=a^*b(a \cup b)^* \cup\ \epsilon$

But my doubt is that, in the DFA starting state is also the final state so, even if we dont give any $b$, it will be accepted, if we give some $a$. But in the regex we have $b$, instead of $b^*$. Why is it so? Is it because,we have that regex $\cup$ $\epsilon$ ?

I'll be using the solution to $Q = \alpha Q \cup \beta$ given by $Q = \alpha^* \beta$, essentially as you would go solving a system of linear equations by hand:

$$
\begin{align*}
Q_0 &= a Q_0 \cup b Q_1 \cup \epsilon \\
Q_1 &= (a \cup b) Q_1 \cup \epsilon
\end{align*}
$$
From the first equation you have $Q_0 = a^* (b Q_1 \cup \epsilon)$, the second one reduces to $Q_1 = (a \cup b)^* \epsilon = (a \cup b)^*$. Replacing $Q_1$ in $Q_0$ gives:
$$
Q_0 = a^* (b (a \cup b)^* \cup \epsilon)
    = a^* b (a \cup b)^* \cup a^*
$$


If the language of a TM is TMs which cannot self recognize, can the original TM? I've been thinking about this one for a while:

  Consider the language of TMs which do not recognize themselves: $L_{s}=\{ \langle M\rangle ~|~ M \text{ does not accept } \langle M\rangle \}$. If $N$ is a TM where $L(N) \subseteq L_s$, then is $\langle N\rangle \in L_s$?

Intuitively, I'm pretty sure it is true. I pictured $N$ as a compiler, and imagined some machine $P$ that $N$ compiled. It seemed that if $P$ was not able to bootstrap, then $N$ wouldn't be able to either. But I'm having trouble thinking about this problem more formally.

Am I on the right track? A hint would be really helpful.

You have to argue formally. Intuition can be helpful in pointing the way, but you need a formal argument in the end.

Hint: Suppose that $\langle N \rangle \notin L_s$. Then $N$ accepts $\langle N \rangle$, and so $\langle N \rangle \in L(N) \subseteq L_s$, a contradiction.


Schedule tasks from a weighted list with time frame constraints I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points:

Each task has been given a priority beforehand and the algorithm should try to maximize the total 'priority points' it can get from the tasks it schedules.
There should be no overlap between any tasks.
Each task might have several time constraints.

Here's an example:

$$
\begin{array}{c|c|c|c}
\text{Task} & \text{Duration (min)} & \text{Time Frames} & \text{Priority} \\
\hline
\text{Read a book} & 80 & \text{5:00pm-8:00pm} & 2 \\
\text{Go to the store} & 45 & \text{5:00pm-7:00pm} & 5 \\
\text{Eat popcorn} & 15 & \text{6:00pm-8:00pm} & 1 \\
\text{Ask the internet} & 25 & \text{5:00pm-6:00pm,7:00pm-8:00pm} & 8 \\
\text{Exercise} & 60 & \text{5:00pm-7:00pm} & 6
\end{array}
$$

And a schedule it could make would be (each character is 5 mins):

| 5:00-6:00 | 6:00-7:00 | 7:00-8:00 |
| Store || Exercise |   |Ask||E|    |

Which scores a total of 20 points (which I believe is the maximum in this example)

I realize this problem may be NP-Hard so, because of the nature of this project, the solution doesn't need to be optimal.

What I've come up with so far is something like the following:

Sort the task list based on priority (t*lg(t))
Find each 'block' of time, divided on each time frame boundary of the tasks (t) and store in a set. Then sort the set (f*lg(f)).
For every block, attempt to place a task, starting with the highest priority, at the earliest point available in the block. Repeat until there is no room for any task in the block. (t)
Extend the end of the block to the end of the next block and repeat 3. If no task can fit into the earliest point, move the earliest point to the beginning of the next block used for the beginning. (For instance, block 1 is filled as much as possible, so it is expanded to the beginning of block 1 to the end of block 2. No tasks can start at the beginning of the remaining space between blocks 1 and 2, so it moves the beginning of the active block up to the beginning of block 2).
Repeat 4 until there are no more blocks. (f)

Total: f*t + f*lg(f) + t*lg(t)

This greedy algorithm doesn't seem ideal and it will certainly fail horribly in some scenarios (such as a 60 min, high priority task from 1:00-3:00, and a lower priority task from 1:00-2:00). What is the best way to approach this problem?

I'd be inclined to punt the problem to an integer linear programming problem solver. (Note that many solvers will take a timeout argument that'll return the best solution they've found so far if/when the timeout triggers)

Encode each task as a rational (or potentially integer, depending) for the time of the start of the task and a boolean for if the task is going to be done, with appropriate bounds constraints predicated on if the task is going to be done (note that when you have multiple possible time slots for a task you'll need to encode the bounds as "at least one of these time slots are valid").

Then for each pair of distinct tasks add a constraint that either the first task starts after the second one finishes or vice versa.


How to express the data structure in the pesudocode of your algorithm If I stored the output for my algorithm as a data structure as a cell array. How can I express that when I am writing the pseudocode for my algorithm.

For example, I have a set of $n$ values like {2,4,6} and for each value, I run the algorithm and output a matrix.

I want to express in the pseudocode of my algorithm how I stored the matrix for each value and output these values and the matrices corresponding to it.

There are no set rules, but these type of details are sometimes omitted from the pseudocode listing. You might see something like

ALGORITHM(S, n):
For i = 1 to n do
   S = ADD(S, i)
EndFor

Then followed by something like "... the algorithm performs $\Theta(n)$ units of work assuming that the set $S$ is implemented as blah so that the addition of an element ADD(S,i) runs in blah time ..."


Minimize sequence storage by overlapping prefixes I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great.  Can you beat my best answer?

The Real-World Impetus

Given a set of data $C$ that consists of nonoverlapping, nonempty, unique sequences $S_1, S_2, S_3, ...$ of atomic values.  Each sequence tends to have a lot of repeated values.

For example, in the code where I bumped into the problem, the sequences were initially something like this:

    9, 1, 1, 1, 1, 1;
    5, 5, 5, 3, 2;
    1, 1, 1, 1, 4;
    1, 7, 5, 5;
    4, 4, 4;
    ...

To access the data, there's a secondary table of offsets into the overall data to show where each sequence starts:  i.e., sequence $S_1$ starts at 1, and $S_2$ at 7, and $S_3$ at 13, and so on.  But this means that the sequences may occur in any order, and they may even overlap.

Given that the data could overlap, it occurred to me that by reordering the sequences, I could reduce the storage required.  For example, in the above data, I can reduce the size of the required storage by reordering the sequences as $S_1, S_3, S_5; S_4, S_2$:

    9, 1, 1, 1, 1, 1, 4, 4, 4;
    1, 7, 5, 5, 5, 3, 2;
    ...

By overlapping the prefixes and suffixes, we can store 16 values instead of the original 23, a considerable savings.

The Problem Statement

Generalizing this, the problem, then, is to find an algorithm for ordering an arbitrary set of sequences, so that the resulting ordering will have the maximum overall overlap of those sequences' prefixes and suffixes.

(And for what it's worth, I don't actually have to solve this for the code I was working on:  This is purely a question of academic interest at this point.)

My Best Answer

It's easy to "see" an optimal answer for trivial examples like the one above, but in the general case of a large number of sequences of arbitrary values, it gets hard quickly.  A greedy algorithm could likely at least give an acceptable answer in polynomial time, but that wouldn't be the true minimal answer.  And obviously, you can simply try every possible ordering, but $O(n!)$ is not a very nice solution either.

It occurred to me a possible solution might exist as a variation on a longest-path-through-a-weighted-graph problem.  You consider each sequence $S_1, S_2, S_3, ...$ as a node in a graph, and construct a directed edge anywhere $S_n$ has a prefix that matches a suffix of $S_m$ for all $n$ and $m$, weighted by the match length.  This results in a two-step solution:

Calculate all the edge weights.  The edge weights can be calculated trivially in $O(n^2)$, or maybe even in $O(n)$ using a trie constructed via dynamic programming.
Then for each vertex, use Dijkstra's shortest-path algorithm (or similar), inverted, to find the longest path for that vertex.  Of all the possible longest paths, then take the overall longest.  This is $O(n^3)$, or maybe $O(n^2\ log\ n)$ using priority queues.

I think this might work, with an overall time of $O(n^3)$ or maybe $O(n^2\ log\ n)$, but I haven't attempted to prove it for real (or implement it).  There might also be a better technique than Dijkstra's algorithm for "longest path in the graph when you don't care what node it starts or ends on."

Can you do better?

Here's the problem statement again:

  Find an algorithm that can efficiently order a set of sequences $S_1, S_2, S_3, ...$ such that there is maximal global overlap of their prefixes and suffixes.

Good luck; I'm curious to see if you can solve it better than I could!

This problem is known as "Shortest Common Superstring" (or sometimes just "Shortest Superstring"). It is an NP-complete problem in general, though good approximations are known (e.g.: via approximations of weighted set cover, as outlined in the linked Wikipedia article).


Sorting in sub-quadratic time and logspace simultaneously On a standard computing model that reflects reality for sequential processing, such as a RAM machine with penalized access time for growing memory, can a comparison sort algorithm work in both logspace yet sub-quadratic time?

Standard algorithms for sorting are O(n*log(n)) time yet I've found that once these programs are restricted to only read-only input, write-only output, and pointers for indexing into the I/O, they seem to suddenly require quadratic time.

Another question on cstheory prompted answers giving model-independent lower bounds for famous complexity classes such as NP requiring a product of time and space resources to be nearly quadratic. Does that same argument apply here to non-trivial problems in L?

The following paper proves that any comparison-based sorting algorithm must satisfy $TS = \Omega(n^2)$, where $T$ is the running time and $S$ is the amount of read-write space used.

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa.  A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.  Journal of Computer and System Sciences, vol 22 pp.351--364, 1981.

In particular, if $S = O(\log n)$, then $T = \Omega(n^2/\log n)$, i.e., if you have only logarithmic space, then the running time has to be nearly quadratic.


Composing $L$ and $NL$ Let $A$ be a problem. I would like to solve $A$ in $NL$. So, I am trying to construct Turing machine working in $NL$:

Let $w$ be a input of length $n$. Firstly, we run machine $M_1$ that working in $LOGSPACE$. It produces a output $o$ of length $P(n)$ where $P$ is a polynomial.
Secondly, a machine $M_2$ working in $NL$ reads the output $o$ written by $M_1$.

Does t work in $NL$? Why?

P.S. If machine $M_2$ worked in $L$ it would be obvious that problem is solvable in $L$. But, I am not sure if that algorithm solves $A$ in $NL$.

$M_2$, while running on $w$, calls $M_1(w)$ as a subroutine. So if $M_1(w)$'s output is stored on $M_2$'s working tape then it requires polynomial space, not logarithmic space. So, $M_2$ does not work in logarithmic space no matter it is deterministic or nondeterministic.

Of course you could design your machine $M_2$ so that $M_1(w,i)$ would return $i$th bit on demand (on each call). In this case it would work in logarithmic space. But it depends on the problem you solve.


Prerequisites of computational complexity theory what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical background and good book suggestions for each topic ... thanks

Here are some prerequisites:

Mathematical maturity. You get this by taking math courses.
Mathematical induction. Important.
Rudimentary calculus. That also includes all you need to know about big O notation, which you can learn as part of your study of algorithms and complexity. Calculus is mainly used for estimating sums and in general asymptotic analysis.
Rudimentary linear algebra. Not relevant for everything, but common enough.
Basic discrete probability theory (linearity of expectation, Markov's and Chebyshev's inequalities, Bernoulli random variable, binomial distribution, indicator variables). Very helpful. Part of it (Chernoff's bound) you will learn as part of your study.
Basic graph theory. Most people probably don't actually have any background in graph theory to begin with, and learn whatever they need as part of their algorithms course.

Since calculus and linear algebra are common enough, what is probably most challenging is discrete probability theory. There are many textbooks covering this, and probably all of them are fine. Whatever you don't learn ahead of time you will pick up in your algorithms and complexity classes.

On the other hand, it is important to be proficient in induction and arithmetic manipulations, and to have some basic level of mathematical maturity. The only way to achieve this is to gather experience in doing basic proof-based math.


What's the difference between a stream and a queue? What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of 'insert'/'extract' (streams) vs. 'enqueue'/'dequeue' (queue). Are these interchangable? Do they suggest different concepts or patterns? If so, what are the differences?

Concrete example of 'stream insertion':
https://www.cplusplus.com/reference/ostream/ostream/operator%3C%3C/

Potentially useful conceptual pieces?

Stream as sequence of time-function data: https://web.archive.org/web/20160603162316/https://mitpress.mit.edu/sicp/full-text/sicp/book/node69.html
Stream as IO channel: https://en.wikipedia.org/wiki/Standard_streams

A queue is an abstract data type with two operations: enqueue() and dequeue() (or sometimes push() and pop()) that have first-in-first-out semantics.

A C stream is hard (for me) to describe abstractly.  My best cut at it is that it is an abstraction representing a buffered file (where "file" is understood in the Unix sense of the word as something that is usually (but not always) a sequence of bytes and a current file position.)

At it's most general a stream is like a sequence of bytes numbered from 0, that can be arbitrarily extended at the end, but that has some additional state (the current position).  There are some basic operations (fread() and fwrite()) that read or write an arbitrary number of bytes starting at the current position, and then reset the current position to point just after the most recently read or written byte.  The current position can also be changed with fseek() and queried with ftell().

Now here's where it gets "icky."  At the time a stream is opened a variety of factors determine which of the above operations are enabled or disabled.  If you open your stream only for read then calling fwrite() will cause an error.  If you open your stream only for write then calling fread() will cause an error.  If your stream is actually a pipe or a socket, or is opened in mode append then you are not allowed to fseek().   You are only allowed to read or write from the current file position.  stdin, stdout, and stderr are pipes so you can't fseek() them.  You can't fwrite() stdin and you can't fread() stdout or stderr.

C++ fixed most of that mess by giving us a hierarchy of types (for example: http://www.cplusplus.com/reference/istream/basic_iostream/), so that we can do error recovery with RAII and can also tell whether the file is readable or writable by looking at the type (although I don't know offhand whether they fixed the seeking mess.)

But then there's the whole other question of formatted output.  C has fprintf() which formats some stuff and puts some bytes into a writable stream (starting at the current file position).  C++ replaced fprintf() with the (IMHO) really-much-too-cute operator<<().  operator<<() has the advantage of being strongly typed, but the extreme disadvantage of requiring the use of manipulators.  So operator<<() puts some bytes to the output stream starting at the current file position, but formatted based on a whole bunch of state that is mutated by manipulators.  So a C++ stream actually has a bunch of extra state that you need to know about.  (Whether integers are going to get formatted hex or decimal from now on, how much precision floats are printed with, etc.)

So: a queue inserts and removes individual items of a well defined type from its front or its back.  A stream is random access extendable array of bytes where you can read and write arbitrary numbers of bytes from the current file position (except when it isn't random access and except when you either can't read or can't write).


Variation to spanning tree called Group Spanning Tree Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree under the constraint that at least one node will be present from each group ("group spanning tree").

How to  write an efficient algorithm for this, making sure it is a tree (no cycles), without iterating over the entire node set, on every pass checking presence of cycles, and also making sure that at least one node from each group is represented?

A spanning tree connects all nodes, so in particular it connects nodes of each color.

Are you sure that is the problem you are facing?


Is $x^2+x+1 (mod 2)$ a one-way function? Given that $x^2+x+1 (mod 2) = 1$ and $x^2+x (mod 2) = 0$ for ${|x\rangle}_{x=0,1} \xrightarrow{F} \frac{1}{\sqrt{2}}[(-1)^{x}|x \rangle + |1-x \rangle]$ (Fourier transform). So, the 1-1 correspondence $x^2+x+1 = NOT(x^2+x)$ holds over $F_{2^3}$, where the input is the zero polynomial $x^2+x$ and the output is the positive polynomial
$x^2+x+1$ (arXiv:1609.01541, eprint.iacr.org/2017/681). Notice that the bijection $x^2+x+1 (mod 2)$ = $x^2 \oplus x \oplus 1$ = $x \land x \oplus x \oplus 1$ = $ x \oplus x \oplus 1$ = $x \oplus NOT(x)$, which corresponds to a coin toss.

It is important to note that the construction works for bit strings of any length because any positive polynomial is reduced to $x^2+x+1(mod2)$ and any zero polynomial is reduced to $x^2+x(mod2)$.

Considering that pseudorandom generators exist if and only if one-way functions exist (pseudorandom generator theorem) is $x^2+x+1 (mod 2)$ a one-way function ?

A one-way function is a function from $\{0,1\}^*$ to $\{0,1\}^*$ which satisfies certain properties. Your function only accepts a single bit as input, so in particular isn't a one-way function.

We don't know whether one-way functions exist, though many people conjecture that they do. Proving that one-way functions exist is harder than proving $\mathsf{P} \neq \mathsf{NP}$, that is, if one-way functions exist then $\mathsf{P} \neq \mathsf{NP}$. Therefore proving that a given function is one-way is expected to be very difficult, though some candidates do exist.


How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts? I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt:

  When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing table may involve FIRST-FIRST and/or FIRST-FOLLOW conflicts, whereas LR parsing table may involve SR and/or RR conflicts. When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar. Does this means, eliminating LL conflicts also somehow eliminates LR conflicts? If yes how this happens? Or in other words, how LL conflicts are mapped to LR conflicts? (I believe there should have some minimum connection between LL conflicts and LR conflicts, shouldnt there be?)

When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar.

To say that the grammar "becomes a valid LR grammar" implies that it was not a valid LR grammar before. But I will argue that if a mechanical procedure is used to transform a non-LL grammar $G$ into the LL grammar $G'$, then it is likely that both $G$ and $G'$ are LR grammars. In other words, the elimination of the LL conflict did not have any effect on LR conflicts, because there weren't any.

I'm not going to attempt to prove this assertion for all possible mechanical procedures. Indeed, it might not be correct for all heuristics. But it's pretty clear that the assertion is correct for the procedure used to left factor a grammar, because failure to left factor does not introduce any LR conflicts.

Both types of LR conflicts require that at least one production be reduceable. If left-factoring involves a factor which is not an entire right-hand side, then it does not apply to any SLR state including a reduceable production, and thus substituting a new non-terminal for the non-common part of the right-hand sides has no effect on any hypothetical LR conflict. Of course, it is possible that the factor is the entire right-hand-side of one production $A\to\beta$, and there is another production $A\to\beta\gamma$. So left-factoring will use a newly-created non-terminal $A'$ to produce:

$$\begin{align}A&\to \beta A'\\
A'&\to\gamma\mid\epsilon\\
\end{align}$$

The new grammar no longer has a prediction conflict on $A$, but there is no guarantee that the result is LL. For it to be LL, the parser needs to determined which alternative for $A'$ to use, which requires that $FOLLOW(\gamma)$ and $FOLLOW(A')$ be disjoint. But if that is true, there is no LR conflict; the shift and reduce actions are clearly differentiated by the lookahead.

So, if left-factoring results in an LL grammar, the grammar was originally LR. Left-factoring has not "made the grammar LR".

Left-recursion elimination is a bit more complex. To start to come to terms with that, consider a very simple left-recursive grammar $G_{sub}$:

$$\begin{align}S &\to E\\
E &\to T\\
E &\to E - E\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

That grammar is ambiguous because $5 - 2 - 1$ has two parses: (for clarity, I put the subnode evaluation [brackets] beside each operator, to indicate that the two different parses lead to different program semantics):

     - [4]                        - [2]
   /   \                        /   \
  /     - [1]                  - [3] \
 /    /   \                  /   \    \
5    2     1                5     2    1

Since $G_{sub}$ is ambiguous, it cannot be LR, and indeed when we try to construct the parsing automaton we find a shift-reduce conflict on lookahead $-$ in the state $\{[E\to E\bullet-E], [E\to E-E\bullet]\}$. The ambiguity also implies that the grammar cannot be LL, but in this case we can immediately see that it is not LL because no LL grammar has a left-recursive production.

We might chose to eliminate ambiguity by adding a precedence specification and using the precedence algorithm implemented in Yacc (and other parser generators). The precedence algorithm does not perform a transformation on the grammar. Rather, it transforms the parse automaton generated by the LR algorithm by removing all but one action from each conflict. (Hence, it is only applicable to LR parsing.) The resulting automaton could be transformed back into a deterministic CFG, but this is rarely done because the parse automaton is sufficient to implement a parser. (The procedure to convert a DPDA to a DCFG is outlined in Sipser, Introduction to the Theory of Computation, in Theorem 2.57; you can take that as an exercise.)

$G_{sub}$ has only a single operator, $-$, so there are only two possible precedence declarations: either we declare the operator to be left-associative or we declare it to be right-associative. Normally, we would choose left-associativity, since that is how we were taught in school to understand expressions like $5 - 2 - 1$. That produces the parse tree on the right above, the one which evaluates to 2.

But right associative operators are also plausible. For example, in many programming languages, assignment is right associative, because $a = b = 7$ must be evaluated by first setting $b$ to 7 (subexpression on the right) and only then setting $a$ to the result of the first assignment.

As I said, actually constructing the parse automaton, removing the conflicts, and then turning it back into a grammar is a bit tedious, although it is probably a good exercise; for the purposes of this answer, I didn't do it. But I can provide CFGs which will produce the same parses, and probably differ from the full procedure only in minor details.

Here is the usual left-associative grammar:
$$\begin{align}S &\to E\\
E &\to T\\
E &\to E - T\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

And here is the right-associative grammar:
$$\begin{align}S &\to E\\
E &\to T\\
E &\to T - E\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

The only difference from the original ambiguous grammar is the second production for $E$. In the ambiguous grammar it is $E\to E - E$. The left associative grammar turns that into a left-recursive production $E\to E - T$, and the right associative grammar tuns it into a right-recursive production $E\to T - E$.

Both of the above associative grammars are LR, and neither is LL. The right-associative grammar can easily be transformed into an LL grammar by left factoring:

$$\begin{align}S&\to E\\
E&\to T E'\\
E'&\to - E\\
E'&\to\epsilon\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

Again, this is an example of turning an non-LL grammar which was LR into an LL grammar (which is still LR).

To turn the left associative grammar into an LL grammar, we could try eliminating left recursion:

$$\begin{align}S&\to E\\
E&\to T E'\\
E'&\to - T E'\\
E'&\to\epsilon\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

In this case, the resulting grammar is indeed LL. (And once again, both the original and the transformed grammar are LR.)

But here is something interesting. Left-factoring the right-associative grammar and eliminating left-recursion from the left-associative grammar produced virtually the same result. The only difference is that the first one has the production $E'\to - E$; in the second one, this production has had the $E$ pre-expanded, so it reads $E'\to - T E'$. Evidently, these two grammars parse the every input in the same way, despite the fact that we started with two grammars which produced different parses.

That's because the left-recursion-elimination algorithm does not preserve the parse tree. Or, to put it another way, you can turn a left-associative grammar into an LL grammar, but you sacrifice left-associativity.

Interesting though that is, it's really a side issue, since the point here was to try to find a relationship between LL and LR conflicts. And so far, we have found nothing even vaguely similar to a relationship. To close the circle, lets go back to the ambiguous grammar $G_{sub}$, which was neither LL nor LR, and try to turn it into an LL grammar by eliminating left-recursion. We get

$$\begin{align}S&\to E\\
E &\to T E' \\
E'&\to - E E' \\
E'&\to\epsilon \\
\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

That successfully removed the left-recursion, but the resulting grammar is still not LL. We did not remove the ambiguity, and the resulting grammar is neither LL nor LR.

In summary:

An ambiguous grammar is neither LL nor LR. There will be conflicts produced by both algorithms, but it may be that they manifest in different ways.
If you can transform a non-LL grammar to an LL grammar using standard heuristics, then it probably had not LR conflicts to begin with.
LL and LR conflicts are completely different phenomena.


What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution? I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of
$$
O\left(n^{2.376}\right).
$$
How much easier is it to simply determine whether the same system has any solution?

More precisely, given a system of $m$ equations and $n$ unknowns, what is the complexity of establishing whether it has any solution?

Whether or not Coppersmith-Winograd is the "best" algorithm depends on your circumstances, of course. CW and algorithms like it are usually considered impractical due to high constant factors. Strassen's algorithm is more common in practice.

But since computational complexity is what you are interested in, CW was beaten quite recently.

Virginia Vassilevska Williams (2014), Multiplying matrices in $O(n^{2.373})$ time, Stanford University.

As far as we know, calculating the determinant of a matrix, or eigenvalue estimation, or anything else that could be used to determine if a matrix is singular or not are at least as complex as matrix multiplication.


Can we represent all computer programs as graphs? I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an abstract syntax graph.

It occured to me that perhaps any computer program can be represented as one of these graphs + evaluation semantics attached to it.  I'm curious if anyone knows if this is universally true for a turing machine (I assume you can get a potentially infinite graph, but this is math so that's OK).  I've been pondering on it and a lot of things like strong type systems and such fit well in this abstraction (they impose structural constraints on the graph).  You might even be able to consider the type system its own program and represent that as a different graph + evaluation semantics operating on the program graph...

Just curious if this is a known equivalence or not.

I don't know if it's a particularly well known equivalence, but it's fairly simple when you think about it.

Turing Machines are known to be equivalent to the (untyped) Lambda Calculus. The Church-Turing thesis proposes that this is they are the most powerful form of computation.

The Lambda Calculus is a syntactically defined term re-writing system. Essentially, it's a very simple programming language. So, it can be parsed into an abstract syntax tree (graph).

So, we have:

Every computer program is representable in the untyped lambda calculus.
Every lambda calculus program can be parsed into an abstract syntax tree

This means that every computer program can be represented as a Lambda Calculus abstract syntax tree.

These trees might not have much in the way of interesting properties. For example, they're definitely not unique i.e. two different trees can perform identical computations.


Are there any articles or software which can infer original shapes from overlapping shapes? Given that some shapes overlap in an image, are there any papers or articles or code which can infer the original shapes from the overlapping?

I am thinking to apply some machine learning to this since I can generate overlapping shapes using code and use a neural network to try to work out the original shapes. Perhaps another way is just heuristic rules.

I'd suggest you start with image segmentation, to identify each of the separate (potentially occluded) shapes in the image.

If there was no occlusion, the problem would then be easy.  For each shape in the image, you could compare it each possible shape in your library of shapes and see if it's a match.  If you don't have to deal with pose/rotation, only possible variation in the size and location of the shape, that will be easy to do: given a shape $S$ from the image and a shape $S'$ from your library of shapes, you first normalize their sizes, then check if they are a match using normalized cross-correlation or something similar.  If you do have to deal with variation in pose/rotation as well, you could use something like SIFT to align $S$ to $S'$, then proceed from there.

However in your example you have to deal with occlusion, and it's occlusion that makes the problem more challenging.  So, let's re-formulate the problem.  You get a bunch of partial shapes $S_1,\dots,S_k$ from your image.  For each $S_i$, you can also derive an occlusion mask $M_i$ that indicates which pixels were occluded by other shapes.  Now you want a way to test whether $S_i,M_i$ is a match to some shape $S'$ in your library.  How to do this?

If you only had to deal with variation in location but not rotation/size/pose, then this would be easy.  It basically comes to checking that $S_i$ matches $S'$ at the non-occluded pixels (they don't have to match at the pixels indicated by $M_i$, but they do have to match elsewhere), i.e., whether $S_i \lor M_i = S' \lor M_i$, where $\lor$ denotes bitwise OR.

So the remaining challenge is how to deal with variation in size and/or rotation/pose.  One approach that might work is to extract all the points on the boundary of $S_i$ (ignoring "boundaries" caused by occlusion) and all points on the boundary of $S'$, and then see if there's a way to make them line up.  Note that we'll have to allow an incomplete match, because the occlusion may mean that the inferred boundary of $S_i$ is incomplete.  One approach for finding a match might be to use RANSAC to estimate a homography between the two sets of points.  (This is vaguely reminiscent of SIFT, but we're using the points on the boundary as the keypoints rather than using SIFT's methods to derive keypoints.)

If you have to deal with more complex images, more complex shapes, or other more complex situations, you could look at the literature on shape analysis and shape context.


Can all packing/covering problems be rephrased as set packing/covering problems? Can all packing problems be rephrased as set packing problems?

Can all covering problems be rephrased as set covering problems?

In other words, I was wondering if set packing/covering problems are the most general forms of packing/covering problems?

If we restrict ourselves to problems in NP, then yes. There are NP-complete problems of either category, so (many-one poly-time) reductions exist; we can view these as "rephrasing".

Since integer programming is also NP-complete, these same is true for that one.

Problems outside of NP do not reduce to integer programming, but I am sure that any (meaningful) complexity class contains examples of both covering and packing problems.

It's not the "type" of a problem that determines its hardness. There are satisfiability problems all the way from linear complexity to undecidability, to name just one example.


Time Complexity proof for Segment Tree implementation of the ranged sum problem I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here.

However I'm not able to prove that the querying time is indeed $\mathcal{O}(\log n)$. This link (and many others) say that we can prove that at each level, the maximum number of nodes processed is $4$ and so $\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$.

But how do we prove this, perhaps by contradiction?

And if so, if we were to use segment trees for ranged sum of higher dimensional arrays, how would the proof be extended?

For example,
I can think of finding a sub matrix sum by dividing the original matrix into 4 quadrants (similar to halving intervals in linear arrays) building a quadrant segment tree but the proof eludes me.

The claim is that there are at most $2$ nodes which are expanded at each level. We will prove this by contradiction.

Consider the segment tree given below.

Let's say that there are $3$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to the right most node, then the full range of the middle node is covered. Thus, this node will immediately return the value and won't be expanded. Thus, we prove that at each level, we expand at most $ 2 $ nodes and since there are $ \log{n} $ levels, the nodes that are expanded are $ \boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)} $


How to (Efficiently) Sort a List of Items with Parent/Child Relationship I have a list of items that have a parent/child/grandchild/etc. type of relationship. Each item has a list of descendants, and an _.isDescendentOf(other) member function that returns true when a node is a descendant of another node (they have a list of immediate parents, and can sweep upwards to find grandparents). Some of the items may not have a relationship with one another. I need to sort these items such that no item comes before an item it is a descendant of.
Consider items of the format (a, [b, c]) which indicates that a has descendants b and c. If we had the unsorted list (with an invalid ordering): [(c, []), (a, [b, c]), (b, [c]), (d, [])]
Valid orderings would be: [(a, [b, c]), (b, [c]), (c, []), (d, [])] or [(d, []), (a, [b, c]), (b, [c]), (c, [])]
(Note, (d, []) can technically be placed anywhere since it does not have a relationship with the others.)
(Note, a, b, etc. are randomly-assigned placeholder names and, though they are alphabetically ordered here, in reality they are random.)
I am quite unsure how to achieve this in an efficient way. My (current) solution involves maintaining a list of "placed" and "unplaced" items (the former is empty at the beginning, and the latter initialized with a copy of the unsorted list), and then greedily moving "unplaced" items to the "placed" list when they do not have any ancestors in the "unplaced" list (until the "unplaced" list is empty). That being said... I am curious whether there is a more efficient way to achieve these results. Thanks in advance!

I think you already have implemented some sort of adjacency list representation of a directed graph. You can use a topological sorting (https://en.m.wikipedia.org/wiki/Topological_sorting) to order the items.


Many-One Reducibility of decision problems for complexity theory? A many-one reduction of problem $A$ to problem $B$ is essentially a function that converts a problem instance in problem $A$ to an instance in $B$. This allows you to use a $B-$solver one time to solve this converted instance, in order to solve an $A$-instance.

To show that $A$ is in NP-complete, people use reducibillity arguments to reduce (in polynomial time) an arbitrary problem in NP to $A$, but as far as I know this is not necessarily a many-one reduction.

My question is: How many of these reductions in the context of NP-completeness are many-one reductions? How significantly would the complexity class change if we would require many-one reductions?

NP-hardness (and so NP-completeness) are defined using many-one reductions. When you show that a problem is NP-hard, you have to follow the definition and use many-one reductions. All proofs that you see of NP-hardness use many-one reductions.

One thing to note is that usually, one does not show how to reduce an arbitrary problem in NP to the target problem. Rather, one reduces a problem already known to be NP-hard to the target problem. The starting point of this endeavor is Cook's theorem (independently proved by Levin), which shows that SAT is NP-hard.

The other common type of reduction is oracle reduction (there are other types as well, but they are less common). Oracle reductions cannot distinguish NP from coNP: every coNP-hard problem in the many-one sense is NP-hard for oracle reductions. Most researchers believe that NP is different from coNP, and this is one of the reasons we insist on using many-one reductions.


Are there any garbage collectors that take into account paging? Garbage collections have to visit all objects that are alive, so as to find the memory that can be reclaimed.  (Having many generations’ just delays this a bit)

All things being equal, it is clearly better to first visit the object that are already paged into RAM, before paging other block in and therefore paging out some object.

Anther possibility is that when the OS wishes to take a page of ram away from the process, the GC is first asked if it has a page that can be given up without needing to be paged out.   The GC may  be mostly done with moving objects from a page, so can clear that page within the time limit the OS has for needing a page.

Yet, I cannot recall any garbage collector that integrates with the OS paging system that drive the order the GC works in.

As I recall, copy collectors are supposed to be paging friendly, as
the tracing by copying tends to improve the locality of pointer
references. This has a positive effect on the program (mutator) that
will cause less page faults when following links, and will also
improve the next collection cycle as tracing will also cause less page
faults. The tracing agenda (which pointers should be processed first) can have an impact on the effectiveness for improving data locality. This may be improved by mesuring statistics on the number of access to different pointers in different types of cells.

Now, if you consider a tracing collector in general, you must usually
maintain a structure that keeps track of the pointers that have not
been traced yet. It may be possible to organize this structure so that
all waiting pointers pointing in the same page will be kept together
(though that may take more space, in some cases, depending on the
available techniques to keep the list of such pointers).  A possible
policy is then to always trace first the largest set of waiting
pointers pointing to the same page, when there is no waiting pointer left to the pages in memory.

Regarding the question in the third paragraph, that was added after I answered, copy
collection is again an answer. The OS may reduce the number of
allocated physical pages at collection time, since the pages are completely
freed. With a mark and sweep collector, the event of a full page
beeing free is probably much rarer, thus not worth a specific
machanism to be taken into account.

This kind of ideas is natural, and is probably described in some of the
papers. But I do not recall it off hand. I think the early papers on Lisp GC contain some of these ideas (such as: should car or cdr be followed first?).

The good news in this role of copy-collection is also that paging is
friendly to copy collection since it increases the available storage
space. Recall that the copy collector requires in principle twice as
much space as used for actual data storage. Now, the effect of paging depends also on the address
space of the machine, and the physical memory available. In older
computer, physical memory was much less than available address space,
so that paging was really a space bonus, allowing policies such as
copy GC. Even when physical space is as big as the address space,
one might want to share it, so that the process using a GC would have
less address space without paging (see paging). These remarks are somewhat superseeded by the use of generational collectors. They generally use copy collection for the young generation precisely because of these qualities, and because the young generation is mostly short lived.

Then you have all the interactions of generational GC with the cache
system, that has been discussed in a previous question: Are generational garbage collectors inherently cache-friendly?

For more information on these issue, I would search the web with, for example, the keywords garbage collection and locality.


Well-Characterized vs NP-Complete Definition: Well-Characterized also known as Good-Characterized is defined as follows:

  Problem that have Yes and No certificates i.e., are in NP $\cap$ co-NP, are
  said to be Well-Characterized. (Reference: V.Vazirani,
  Approximation Algorithm)

Does exist any Well-Chracterized problem that is also being NP-Complete? I don't looking for any proof, I just want a real-world example of such problem.

We don't know. If any NP-complete problem were in co-NP, then we'd have NP$\,=\,$co-NP and we don't know whether that's true or not.


Reduction between $\Sigma^*$ and $\emptyset$ Throughout the subject of reductions, I was wondering:

  If we take $L_1 = \Sigma^* $ and $L_2 = \emptyset$, is $L_1 \leq L_2$? is $L_2 \leq L_1$?

What I mean is, Is there some sort of reduction between any of the two with the other one?

I tried this:

  Let us try $L_2 \leq L_1$, we need to show that such a reduction exists. Suppose f(x) is that reduction function in which $x \in L_2$ iff $f(x) \in L_1$.

But there aren't any $x$ in $\emptyset = L_2$, does that show that such a reduction doesn't exist?

Let $f : \Sigma^* \to \Sigma^*$ any total function. Then, the statement $x \in L_2$ is always false since $L_2 = \emptyset$, and conversely $f(x) \in L_1$ is always true since $L_1 = \Sigma^*$. So, clearly, the equivalence

$\qquad\displaystyle x \in L_2 \iff f(x) \in L_1$

is false for $f$ and all $x \in \Sigma^*$ (it would have been sufficient to find one example-$x$); in fact,

$\qquad\displaystyle x \in L_2 \iff f(x) \notin L_1$

holds for all $x$. So $f$ is not a reduction function.

Since we picked $f$ arbitrarily, there can be no reduction from $L_2$ to $L_1$. A similar argument works for the other direction.


concurrency in multiple core I know the basic definition between parallelism and concurrency. But there is not much information about
concurrency in multiple core.
what is the difference between concurrency in single-core vs concurrency in multiple-core?
Is there much difference performance-wise between concurrency in multiple core vs parallelism in multiple core?

Concurrency is not parallelism: indeed, concurrency refers to the sharing of resources in the same time frame. As an example, several processes may share the same CPU or share memory or an I/O device.
Two processes (or threads) can be defined concurrent if an only if the second process starts execution before the first has terminated (assuming that the execution happens on the same core of a multi-core CPU).
Therefore, if the two processes both run on the same core of a multi-core CPU the processes are concurrent but not parallel: in this case, parallelism is only virtual and refers to the OS doing timesharing. The OS seems to be executing several processes simultaneously. But, since the processes execute on the same core, only one instruction from one process can be executing at any particular time. Since the human time scale is billions of times slower than that of modern computers, the OS can rapidly switch between processes to give the appearance of several processes executing at the same time.
If you instead run the two processes on two different CPUS, the processes are parallel: there is no sharing in the same time frame, because each process runs on its own CPU. The parallelism in this case is not virtual but physical.
Finally, it is worth noting here that two processes running on different cores of the same multi-core CPU can not be classified as fully parallel, because the processes share the same CPU caches and will even contend for them.
It should now be clear that performance-wise, parallelism is better than concurrency.


The complement of $\{w: w\text{ has equal numbers of $a$'s, $b$s' and $c$'s}\}$ is context-free Let $L$ be the language $\{w \mid w \text{ has equal numbers of \(a\)'s, \(b\)'s and \(c\)'s}\}$. Prove that its complement $\overline{L}$ is context free.

So let us remember the closure properties of context-free languages, gone over in class and stated by the TFS:

* closed under union
* closed under concatenation
* closed under Kleene Star

Now I will show that my language $L'$ is the same as the language $L$. Let $NE(x,y,z)$ be an operation that generates a language such that the number of x's is not the same as the number of y's, with as many z's as one wants anywhere in the language. Thus my language $L'$ is defined as:

$$ NE(a,b,c) \cup NE(c,a,b) \cup NE(b,c,a) $$

This language is obviously $L$. It is all instances of a not equal to b, b not equal to c, and c not equal to a. The nice thing here is that if we prove $NE()$ is context free, then because of symetry and closure under union operation. Let us represent NE as a PDA here:

$$ (s,\epsilon,\epsilon) \rightarrow (p,\$) $$
$$ (p,a,\epsilon) \rightarrow (p,1) $$
$$ (p,b,1) \rightarrow (p,\epsilon) $$
$$ (p,b,\$) \rightarrow (m,1\$) $$
$$ (p,c,\epsilon) \rightarrow (p,\epsilon) $$
$$ (m,c,\epsilon) \rightarrow (p,\epsilon) $$
$$ (m,b,\epsilon) \rightarrow (m,1) $$
$$ (m,a,1) \rightarrow (m,\epsilon) $$
$$ (m,a,\epsilon) \rightarrow (p,1\$) $$
$$ (p,\epsilon,a) \rightarrow (f,\epsilon) $$
$$ (p,\epsilon,b) \rightarrow (f,\epsilon) $$
$$ (m,\epsilon,a) \rightarrow (f,\epsilon) $$
$$ (m,\epsilon,b) \rightarrow (f,\epsilon) $$

So now that I have represented this language as a PDA, all I need to show is that the language I represented corresponds to $NE()$.

First I will show that my PDA, $X$ is $X \subseteq NE$. This is quite easy to see. The only way that one can enter a final state in $X$ is when, under one of our rules, we hit the end of the string, and there is something left on the stack (meaning that there is an unequal number of either a's or b's). we can see here that this is a subset.

Next I will show that $X \supseteq NE$, or in other words, all strings that are part of $NE()$ can be made by $X$. One can see that one can have as many c's as one wants in this model, by the rules:  $ (p/m,c,\epsilon) \rightarrow (p/m,\epsilon) $, so that is not a problem. But how does it promise that all strings of unequal number of a's and b's are not in this language. Again, the grammar only keeps track of how many excess a's or b's there are, and can accept any string of arbitrary length with any permutation of letters as long as one of a or b, has an excess. Thus $X \supseteq NE$.

I have shown that $NE$ is Context Free by building a PDA, and I have shown that $L$ is a finite union of $NE$s, thus $L$ is context-free.


Converting Boolean Expression for NAND Gate Implementation - DeMorgan's Law If I have the sum-of-products expression B~CD + ACD how would I convert this so it could be implemented using 3-input NAND gates through DeMorgan's Law? Would this not generate the expression: ~(~(B~CD) ^ ~(ACD))?

It would seem I could implement this and use a 3-input NAND gate with 3-C inputs to act as a NOT gate but this seems wrong.

If this isn't the right place for such a question, let me know and direct me elsewhere if possible, I'll remove it.

You have the basic rule that (a or b) = not (not a and not b), so you use that repeatedly. The first application gave you B~CD + ACD = NAND(~(B~CD), ~(ACD)). You're almost there:

NAND(~(B~CD), ~(ACD)) = NAND (NAND (B, ~C, D), NAND (A, C, D))
 = NAND (NAND (B, NAND (C, C, C), D), NAND (A, C, D))


Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?

No. If you could do that in linear programming then you could force a variable to have binary values, so you'd be able to solve integer linear programs using LP solvers.
Indeed, we can simulate $x \in \{0,1\}$ with:
$$
\max\{x, 1-x\} \ge 1, \\
x \ge 0, \\
x \le 1.
$$


The 50 value problems in TAoCP This is just a question for fun and specifically for those who have read the reference pervasively.

I have been reading the work of Knuth's The Art of Computer Programming and struggling and having a lot of fun with its exercises. I was very impressed that Fermat's Last Theorem had a difficulty of 45 in Knuth's difficulty scale.

I was wondering, if anyone of you have seen exercises with rank ≥50.

Perhaps a more interesting question, what is the current status of such problems nowadays!?

Knuth's scale goes up to 50 (for "unsolved research problems"). Note that the scale is meant to be (roughly) logarithmic, i.e., adding 10 to the number multiplies the work required by a factor, with 50 meaning some so ridiculously large amount of work to be done that it can be taken practically as "infinite".

Fermat's Last Theorem used to be 50 as an example in the preface, with Wiles' proof it is now "just" extremely hard, i.e., it got demoted to 45 in later editions.

So the answer to the question is "no". By definition 50 is the highest value on the scale.


Showing that a language is not recursive I was given the next function CH(x) that is defined like this:

$CH(<M>)$ outputs the computation history of the run of M on epsilon if M halts on epsilon. If it doesn't the function returns epsilon.
 I was asked to prove that the language

{$ M, CH(<M>) |$ M  is a turing machine } is in co-RE\R

I can't seem to understand why the language isn't recursive enumerable
I do see why it's not in R (The halting problem becomes decidable)

In order to prove $L \in coRE$ you could prove that $\overline{L} = \{\langle M,w \rangle | M \text{ is a TM and } w \neq CH\left( \langle M \rangle \right) \}$ is r.e.

Given input $\langle M,w \rangle$

reject if input is not well-formed including $\epsilon$
if $w \neq \epsilon$. Then $w$ must be a history. If it is not a legal history, just accept since $CH(\langle M \rangle) \neq w$. Otherwise inspect the history, and assume it runs for $k$ steps. Then simulate $M$ for $k$ steps and compare its history with $w$. If they are NOT equal then accept, otherwise reject/loop forever.
if $w = \epsilon$. Then run $M$ until it halts. If it halts then accept since $CH(M)$ must be a legal history different from $\epsilon$ which means $CH(\langle M \rangle) \neq w = \epsilon$. Otherwise, i.e. $M$ does not halt. But our TM which simulates $M$ also runs forever which means that $CH(M) = \epsilon = w$, but it will never halt and so never accept.


Representation of 8-Puzzle for (A*) Search Algorithm in C I am trying to complete CS50's hacker edition pset3, where you have to make a program that will solve the game of eight or fifteen from its current state, this must be written in C.
https://en.wikipedia.org/wiki/15_puzzle

I first tried an approach of straight going for the step that get's you closest to the goal, but found it got caught in a loop. So I added a condition of not repeating the last move which just led to a longer loop!

I am going to need a search algorithm, and have researched and now understand some of the main ones. I think breadth or depth first would be too computationally expensive on larger boards and so, as the specification recommends I am going to try A* search. Manhattan distance works easily for the heuristic as it is admissible and no. of moves from initial state for g(state).

However I am struggling mainly with the open and closed sets. So these must have the cost amount, but what representation of the game moves for that state? The whole board? But then how do you keep track of moves to get to that board for the final solution? I thought about having a massive array of like 200 to store the moves list, but for so many nodes this would be crazy. So how is the best way to represent the system and process of the game in a way that I can implement the search algorithm?

Many thanks

First of all, the $N$-puzzle is hard to solve with A$^*$ using the Manhattan distance. Instead, we use IDA$^*$. To see the technical details involved in the design of IDA$^*$ specifically for solving the 15-Puzzle see Korf, Richard E. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, 27 (1985), 97-109. Artificial Intelligence. As a matter of fact, Richard Korf provided a wonderful implementation of his algorithm where he used various tricks to make his solver really fast: a pre-computed table stores the results of all operators to all states; another table stores the variation in the value of the Manhattan distance for each operator, and such. His implementation is publicly available here and you are very welcome to use it provided that you preserve the name of its author, Richard Korf, along with the copyright notice.

If you insist in using A$^*$ for solving the $N$-puzzle then see Matthew Hatem, Ethan Burns, and Wheeler Ruml, Problem Solving with Heuristic Search and Java, IBM developerWorks, July, 2013. The source code is publicly available here. True, their implementation is in Java and their solution considers various issues which are not straight forward in C such as templates. However, most of the ideas are generically discussed (and, indeed, various issues regarding the open and closed lists are considered to a large extent) so that an implementation in C should not be hard.

Finally, let me stress that Manhattan distance is a rather poor heuristic for this domain. On one hand, it can be significantly enhanced with the so called conflict-based heuristic. On the other hand, Pattern Databases are a wonderful means for efficiently solving even the 25-Puzzle (even if some instances can take hours to be optimally solved).

Hope this helps,


Is finite abelian group isomorphism in Log Space? Definition :  An abelian group is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written

Input : Two finite abelian groups $|G| =n$ and $|H|=n$ by their table representation

Find : Is $G \cong H$?

There is an $O(n)$ running time algorithm for this problem, due to Kavitha [1].

Question : Is this problem known to be in Log Space?

I tried to google but did not get anything related to log space.

[1] T. Kavitha, Linear time algorithms for Abelian group isomorphism and related problems. Journal of Computer and System Sciences 73(6):986–996. (Science Direct)

The finite abelian group-isomorphism when groups are given in the form of multiplication tables known to be in $L$ and in $TC^0 (FOLL)$. For more detail you can see the thesis of the Dr. Fabian.

PhD  Thesis of Dr. Fabian ( see page number 180 and 185 )


Common data structure examples I recently began working as a tutor with my college, helping younger students struggling in intro classes get their footing.

Many of my students particularly struggle with basic data structures (linked lists, heaps, binary [search] trees, hash tables, etc.); I'll call them DS's for short. I can often explain a DS where they make sense of it how it works (with a little help from Wikipedia). To further help them develop an understanding of these DS's, I'd like to provide simple examples for them to work through (think 3-layer binary search tree with 5-7 nodes), as well as some common applications of these data structures.

This leads me to my question. Do you know of a collection of basic data structure examples I could use for tutoring students? To clarify, I am not searching for implementations of these DS's, but specifically written/diagrammed problems of the common data structures such as the ones your professor might work through in lecture during the first two years in a university program.

If you want diagrammatic material on data structures like binary search trees etc. then Introduction to Algorithms by C.L.R.S. (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein) should do the job.


Show that a Language can be Generated by a regular grammar I'm looking for hints on the following exercise from Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.

  Let $G$ be a grammar where all the productions are of the form $A\to xB$ and $A\to x$, where $A$ and $B$ are single variables and $x$ is a string of terminals. Show that $L(G)$ can be generated by a regular grammar.

This is from the second chapter of the book, so the solution should just require grammars (automata don't appear until chapter 3).

I assume that "Show that $L(G)$ can be generated by a regular grammar" means that I have to show the language generated, since this can be shown as regular grammar just by pointing out the productions.

This is where I get a bit confused...

Edit: Wrong usage of production so this is wrong, therefore what i did below is the wrong way to tackle this exercise

If i start doing the productions:
\begin{align*}
A&\to xB\\
\text{(with second)} A&\to AB\\
\text{(with  first)} A&\to xBB
\end{align*}
And so on... so in the (n)th step
$A^* → x^{n-1}B^n$ Since There would always be one $B$ more than $x$.

I was thinking that maybe I could change $xB$ for $A$ then for $x$ again to have just the string of terminals $x$ resulting in what the language generates, and this is where I think I am probably not understanding something right. I assume I am wrong because there cant be a non terminal when generating a Language...Right? Or am I just doing it all wrong?

Thank you for your time. I'm learning in Japan and my professor's English isn't very good so I can't ask him.

The only thing that prevents your grammar from being a regular grammar is that $x$ is a string rather than a single terminal. That means that you have to deal with two kinds of problems:

$x$ is a string containing more than one terminal.
$x$ is the empty string.

To deal with the first problem, replace each problematic rule by a chain of equivalent rules of the proper form. For example, $A \to \alpha \beta$ is the same as $A \to \alpha X$ and $X \to \beta$.

To deal with the second problem, you have to get rid of rules of the form $A\to B$ and of rules of the form $A \to \epsilon$. Hopefully this is something you already know how to do. If not, notice that $A \to B$ means that whenever you have $A$, you can replace it with $B$, and $A \to \epsilon$ means that whenever you have $A$, you can remove it. Doing so recursively will allow you to get rid of these rules.