Parse Trees and Operator Precedence I have the following basic BNF grammar:

<A>   -->  <id>  = <E>
<id>  -->  A | B | C | D | F
<E> --> <E> + <T> | <T>
<T> --> <T> * <F> | <F>
<F> --> <E> | <id>

Operator (*) should have higher precedence over (+).
However, see this statement:

A = A + B + C + D * F

The leftmost derivation (and parse tree) indicate the opposite! i.e., (+) has higher precedence than (*) since it will show up lower in the parse tree!

What am I missing here?

Due to the path

<E>  ->  <T>  ->  <F>  ->  <id>,

you can completely circumvent the "check" for whether there are *.

Think about it in a bottom up manner: only if there's no * nearby can you parse a +.


How to stop genetic algorithm population converging to a single value I've written a genetic algorithm (GA) that solves a 7-dimensional optimisation problem.  All seven variables are floating point numbers.  The problem is that the entire population seems to converge to very nearly the same point in the solution space within about 20 generations, even if I increase the population size by 10x.

Attempted solutions

Starting with a parent population $\vec{x}^{(j)}$, where $j$ is the individual's index in the population, I take the best 10% (i.e. highest fitness scores) to reproduce.  First I perform cross-over producing 2 children for every randomly selected pair of parents.  The parents can be re-used (is that a problem?).  About 5% of the children get mutated randomly.

I've tried two variations of cross-over but both have the same problem:

Calculating a 7 element weights vector $[w_i]$ and calculating the children's elements as $c_i^{(1)}=w_i x_i^{(1)} + (1-w_i)x_i^{(2)}$ and $c_i^{(2)}=(1-w_i)x_i^{(1)} + w_i x_i^{(2)}$.  The parents ith elements are $x_i^{(1)}$ for parent 1 and $x_i^{(2)}$ for parent 2.  Each weight is a sample from a uniform random variable in $[0.0;1.0)$.
Confining the weights $w_i$ to be either $0.0$ or $1.0$, i.e. randomly exchanging elements of the two parents genomes to create the children.

The mutation operation consists of randomly choosing one of the child's 7 elements and adding some Gaussian noise to it.  The standard deviation of that noise differs for each element since the elements have different physical units.

Afterwards, I evaluate the fitness of the children and keep the best few hundred or thousand (setting that I choose at the start of the algorithm) out of the combined population of parents and children to give the next generation.  Note that the parents do not get mutated, especially since I want to preserve the best from the parent generation in case none of the children improve on it.

I've tried population sizes from 1024 to 20480 and have also tried increasing the probability of mutating a child from 5% to 50% but I still have the problem that all the individuals in the population become very similar within the first 20 or so iterations.  Please advise on what I'm doing wrong.

I should point out that the algorithm, despite this problem, does get fairly close to the optimal solution.  I know this because the quantity to maximise is the correlation between between two things (no more details, sorry) and I can get to about 0.94 (the maximum physically possible is always 1.0).  However, I am concerned that the GA is not covering enough of the solution space, causing it to miss the global maximum.

My questions

Are either of the above cross-over methods correct?
Is it ok to re-use parents in cross-over?  Stated another way, is polygamy a good idea in this algorithm or should I change that part to ensure that no parent gets used more than once?
Should I mutate the parents as well?
What should I do with the 90% of parents that did not get used in the reproduction?

Your selection method may lie at the root of this. You are currently using truncation selection, which applies a very high selective pressure and reduces diversity by not allowing elements from worse solutions to be preserved to possibly be useful again in future generations.

You should try different selection methods, in particular roulette selection or tournament selection, and see if that makes a difference. Most implementations I have seen also keep all generated offspring, regardless of quality. The intuition is that, if a child has low quality they will eventually die out anyway, and they might still carry useful information.


Why does quicksort work well with virtual memory? Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is it just because quicksort sorts in place?

The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this:

  The hardware feature on modern computers that has
  the most drastic effect on the performance of algorithms
  is paging. Quicksort actually does not perform badly in
  a virtual memory situation (see [2]) because it has two
  slowly changing "localities" around the scanning
  pointers. In some situations, it will be wise to minimize
  page faults by performing the extra processing necessary
  to split the array into many partitions (instead of only
  two) on the first partitioning stage. Of course, the programs
  should be changed so that small subfiles are
  "insertionsorted" as they are encountered, because otherwise
  the last scan over the whole file will involve
  unnecessary page faults. Many internal sorting methods
  do not work well at all under paging, but Quicksort can
  be adapted to run quite efficiently.

The reference [2] cited there for further details is:

B.S., Gustavson, F.G., and Mankin, E. "Sorting in a paging environment." Comm. ACM 13, 8 (Aug. 1970), 483-494.

As it was suggested in the other answer, in more modern terms, the same property is phrased as quicksort having good cache locality; this is said for example in the 1994 paper "AlphaSort: A RISC Machine Sort" by Nyberg et al.; summary; the full text of this is found for example in Readings in Database Systems by Hellerstein and Stonebraker.


Maximum Stacking Height Problem Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it?

  Problem ("Maximum Stacking Height Problem")

  Given $n$ polygons, find their stable, non-overlapping arrangement
  that maximizes their stacking height on a fixed floor under the
  influence of gravity.

Example

Three polygons:

and three of their infinitely many stable, non-overlapping arrangements, with different stacking heights:

Clarifications

All polygons have uniform mass and equal density
Friction is zero
Gravity is acting on every point into the downwards direction (i.e. the force vectors are all parallel)
A configuration is not considered stable if it rests on an unstable equilibrium point (for example, the green triangle in the pictures can not balance on any of its vertices, even if the mass to the left and the right of the balance point is equal)
To further clarify the above point: A polygon is considered unstable ("toppling") unless it rests on at least one point strictly to the left and at least one point strictly to the right of its center of gravity (this definition greatly simplifies simulation and in particular makes position integration etc. unnecessary for the purpose of evaluating whether or not an arrangement is stable.
The problem in its "physical" form is a continuous problem that can only be solved approximately for most cases. To obtain a discrete problem that can be tackled algorithmically, constrain both the polygon vertices and their placement in the arrangement to suitable lattices.

Notes

Brute force approaches of any kind are clearly infeasible. Even with strict constraints on the placement of polygons inside the lattice (such as providing a limited region "lattice space") the complexity simply explodes for more than a few polygons.
Iterative algorithms must bring some very clever heuristics since it is easy to construct arrangements where removing any single polygon results in the configuration becoming unstable and such arrangements are unreachable by algorithms relying on every intermediate step being stable.
Since the problem smells at least NP- but more likely EXPTIME-complete in the total number of vertices, even heuristics would be of considerable interest. One thing that gives hope is the fact that most humans will recognize that the third arrangement in the example is optimal.

While I don't know of any specific algorithms for this problem, you could approach this in a pretty efficient method by breaking it down into separate parts.

I would start by finding the rotation for each individual shape that provides a maximum height while maintaining a valid balancing orientation (is: not on a point like with the triangle).  If a shape has multiple equal heights, i would go with the configuration that gives the greatest surface area on top of it. Once you have this, you can then figure out how to best stack each object in a manor that is able to be balanced.


Closest pair of points between two sets, in 2D I have two sets $S,T$ of points in the 2-dimensional plane.  I want to find the closest pair of points $s,t$ such that $s \in S$, $t \in T$, and the Euclidean distance between $s,t$ is as small as possible.  How efficiently can this be done?  Can it be done in $O(n \log n)$ time, where $n = |S|+|T|$?

I know that if I'm given a single set $S$, then it's possible to find the closest pair of points $s,s' \in S$ in $O(n \log n)$ time using a standard divide-and-conquer algorithm.  However, that algorithm doesn't seem to generalize to the case of two sets, because there's no connection between the distance between the two closest points within $S$ or $T$ vs. the distance between the two closest points across those sets.

I thought of storing the set $T$ in a $k$-d tree, then for each $s \in S$, using a nearest-neighbor query to find the closest point in $T$ to $s$.  However, the worst-case running time of this might be as bad as $O(n^2)$ time.  There are results saying that if the points of $T$ are randomly distributed, then the expected running time for each query is $O(\log n)$, so we'd obtain an algorithm with expected running time $O(n \log n)$ if we were guaranteed that the points are randomly distributed -- but I'm looking for an algorithm that will work for any collection of points (not necessarily randomly distributed).

Motivation: An efficient algorithm would be useful for this other question.

Yes, this can be $O(n \log n)$ time.  Build a Voronoi diagram for $T$.  Then, for each point $s \in S$, find which cell of the Voronoi diagram it is contained in.  The center of that cell is the point $t \in T$ that is closest to $s$.

You can build a Voronoi diagram in $O(n \log n)$ time, and each query (find the cell containing $s$) can be done in $O(\log n)$ time, so the total running time is $O(n \log n)$ time.


To prove the recurrence by substitution method $T(n) = 7T(n/2) + n^2$ I have done the proof until the point when $T(n) \leq cn^{\log7}$.

But when it comes to finding the value of constant $c$, I am getting stuck.

The given recurrence relation is $T(n) = 7T(n/2) + n^2$.

Since we already calculated the solution above which is $cn^{\log 7}$.

Inductive step:

Now we have to prove that $T(n) \leq c n^{\log7}$ where $c$ is a positive constant.
If we consider that the solution holds good for $n/2$ then we can prove that it works  for $n$ also:
$$T(n/2) \leq c(n/2)^{\log7}.$$
Substituting these values in the recurrence relation:

$$
\begin{align*}
T(n) &\leq 7c/(2)^{\log7} \times (n)^{\log7} + n^2 \\
     &\leq cn^{\log7}, \text{ since $7/(2)^{\log7}$  is constant so can be ignored and $cn^{\log7} \gg n^2$ for large $n$} \\
     &\leq cn^{\log7} \text{ assuming $c$ is a constant $\geq 1$.}
\end{align*}
$$

Finally to find constant $c$,

$$(7/(2)^{\log7}) \times cn^{\log7} + n^2 \leq cn^{\log7}. $$

I am not able to find appropriate $c$ for which the condition holds true.

You're headed in the right direction, but you need an intermediate step. Permit me to simplify things a bit by defining $\lg n = \log_2n$.

A Dead End

Your substitution method, where you want to establish that $T(n) \le cn^{\lg7}$ inductively, using the assumption $T(n/2)\le c(n/2)^{\lg 7}$ runs into problems, as you've already seen. Here's what happens:
$$\begin{align}
T(n) &= 7T\left(\frac{n}{2}\right)+n^2&\text{by definition}\\
 &\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]+n^2&\text{by the inductive assumption}\\
 &=7\left[c\frac{n^{\lg7}}{7}\right]+n^2&\text{since $2^{lg 7}=7$}\\
 &=c\,n^{\lg7}+n^2
\end{align}$$
and you'll obviously never be able to find a $c$ for which $c\,n^{\lg7}+n^2\le c\,n^{\lg 7}$.

A Way Out

The problem is that the $n^2$ term is messing you up. If it weren't there, then substitution would work. Suppose, for instance, that we had the simpler recurrence $S(n)=7\,S(n/2)$. Now life would be easy, since then the proof above would go through nicely. Assume that $S(n)\le c\,n^{\lg7}$. Then we'd have
$$\begin{align}
S(n) &= 7S\left(\frac{n}{2}\right)&\text{by definition}\\
 &\le 7\left[c\left(\frac{n}{2}\right)^{lg7}\right]&\text{by the inductive assumption}\\
 &=7\left[c\frac{n^{\lg7}}{7}\right]\\
 &=c\,n^{\lg7}&\text{as required}
\end{align}$$
and if you do this again and again, driving $n$ down to $1$, you'll find that you can choose any $c\ge S(1)$.

Transforming the Dead End Into the Way Out

Let's make the $n^2$ term go away. Let $S(n) = T(n)+k\,n^2$. Then from
$$
T(n)=7\,T(n/2)+n^2
$$
we have, substituting and simplifying,
$$\begin{align}
S(n)-k\,n^2&=7\,[S(n/2)-k(n/2)^2]+n^2&\text{and so}\\
S(n) &= 7\,S(n/2)+n^2(k-7k/4+1)
\end{align}$$
and it's not hard to see that $k=4/3$ will make the $n^2$ term vanish, giving the $S$ recurrence we just solved above. Putting these together we have
$$
T(n)+\frac{4}{3}n^2=S(n)\le c\,n^{\lg7}
$$
and so
$$
T(n)\le c\,n^{\lg7}-\frac{4}{3}n^2<c\,n^{\lg7}
$$

Lessons Learned

Truth to tell, I'd attack this problem by iterative expansion, namely the way Yuval did it in his answer, but these "substitution method" questions come up often enough that I thought this cautionary tale was warranted. The lessons to be learned here are

The method of substitution often doesn't work when applied to a recurrence relation.
It always applies to recurrences of the form $S(n)=p\,S(n/q)$ as long as $q\ne0$
A useful tool to have in your kit is knowing that sometimes you can transform a complicated recurrence into a simple one by suitable addition (or, sometimes, multiplication).


Changing a matrix to become an ancestry matrix An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some rooted tree (and create the tree) or not.
The question is if $X$ is not an ancestry matrix, how hard is the problem of modifying elements of $X$ so that it becomes an ancestry matrix. The aim is to modify as few elements as possible.
Note 1: Stated problem can be seen as using Hamming distance on the matrices. A related problem  would be: "For what metrics on the matrices this problem can be solved efficiently?"
Note 2: $X$ can be assumed to be a matrix containing only 0 and 1 elements. But a more general form of $X$ is more desirable!
Note 3: Any results about some characteristic matrix like adjacency matrix instead of ancestry matrix would be appreciated!

TL;DR: I prove the variant of this problem in which we can only change matrix entries from 1 to 0 is NP-complete. (I think the original version is NP-complete too, but haven't proved this.)
Rooted Transitive Tree Editing
Another way of stating this problem is to ask for the minimum number of edge changes (additions of new edges or deletions of existing edges) needed to change a given digraph into the transitive closure of a rooted tree -- that is, a rooted tree augmented with all edges $uv$ whenever there is a path from $u$ to $v$. Let's call this graph a rooted transitive tree, and the decision form of this problem "Rooted Transitive Tree Editing":
Given a digraph $G=(V',E')$ and an integer $q$, is it possible to turn $G$ into a rooted transitive tree with at most $q$ edge edits?
I'll call the variant of the problem in which we are only permitted to delete edges "Rooted Transitive Tree Deletion". In the language of the original problem, in this variant we are only allowed to flip matrix entries from 1 to 0. This deletion variant of the problem is NP-complete by reduction from a slightly restricted form of Partition Into Triangles (PIT), as I'll show below. I suspect the full editing version can be shown to be NP-complete using a similar reduction, probably involving making the "handle" gadgets longer paths -- suggestions/extensions welcome!
The basic idea is to create a "triangle handle" vertex for each of the $O(n^3)$ triangles in the input graph, make each input vertex a descendant of the handle of every triangle it belongs to, and then look for a way to keep only the edges from the input graph that are used in a partition into triangles, and only the edges to handle vertices of triangles in this partition, deleting all other edges.
Partition Into Triangles
In Partition Into Triangles, we are given an undirected graph with $3n$ vertices, and ask whether it is possible to partition the vertices into triangles. P. 192 of "Computers and Intractability: A Guide to the Theory of NP-Completeness" (Garey and Johnson, 1979) indicates this problem is NP-complete. Here we need a slightly restricted form of the problem in which every vertex is covered by some triangle. The following simple reduction from the general problem shows the restricted version is still NP-complete. Attach a separate "diamond" to each vertex -- that is, for each $v_i, 1 \le i \le |V|$, add the vertices $x_i$, $y_i$ and $z_i$, and the edges $v_ix_i$, $v_iy_i$, $x_iy_i$, $x_iz_i$ and $y_iz_i$. Every vertex in the modified graph is covered by a triangle, and since the only triangle covering $z_i$ is $x_iy_iz_i$, it must always be chosen, leaving $v_i$ available as before.
Construction
Let $G=(V,E)$ be the input PIT instance, with $|V|=3n$. Let $t$ be the number of triangles in $G$. Note that $t \le {|V| \choose 3}$ and can be computed in polynomial time. We construct an instance $R=(V', E', k)$ of RTTD as follows:

Create a "plain" vertex $v_i'$ for every vertex $v_i \in V$.
Create the directed "plain" edges $u_i'v_i'$ and $v_i'u_i'$ for every undirected edge $uv \in E$.
For the $j$-th triangle $v_av_bv_c$ in $G$:

Create a "handle" vertex $h_j$.
Create the directed "handle" edges $h_jv_a'$, $h_jv_b'$ and $h_jv_c'$.

Create a root vertex $r$, and directed edges from it to every other vertex.
Set the threshold parameter $q$ to $3t+2|E|-2|V|$.

$G$ is a YES-instance of PIT $\implies$ $R$ is a YES-instance of RTTD. First notice that between any two adjacent vertices $u'$ and $v'$, at least one of the two opposite-pointing directed edges must be deleted. Also, for any triangle $v_iv_jv_k$ in $G$, 3 of the 6 resulting directed edges in $R$ can be deleted so as to produce a transitive 3-path, e.g.:
vj
| \      Edges are directed from high to low
|  \
|   vi
|  /
| /
vk

A partition into triangles uses exactly $|V|$ edges in $G$. Given a partition of $G$ into triangles, we delete all $2(|E|-|V|)$ of the directed edges in $R$ corresponding to edges not used by the partition. For each triangle, we also delete 3 of the 6 directed edges so as to produce a transitive 3-path as shown in the above figure (the order of the vertices in the path is unimportant) -- this deletes a further $|V|$ edges. Finally, we delete directed edges from handle vertices to plain vertices for all unused triangles: There are $t-|V|/3$ unused triangles, each of which has 3 such edges. The final digraph is a rooted transitive tree, and we have deleted in total $2(|E|-|V|)+|V|+3(t-|V|/3)=3t+2|E|-2|V|=q$ directed edges, so $R$ is a YES-instance of RTTD.
$R$ is a YES-instance of RTTD $\implies$ $G$ is a YES-instance of PIT. We know there exists a subset of at most $q=3t+2|E|-2|V|$ directed edges, the deletion of which from $R$ yields a rooted transitive tree $R'$.
No directed edge from the root $r$ to any handle vertex can be deleted, since that handle vertex would then become a second vertex with indegree 0 (in addition to $r$), and a rooted transitive tree must have exactly one such vertex. Nor can a directed edge from $r$ to a plain vertex $v_i'$ be deleted, since by the assumption that every vertex is covered by a triangle, $v_i$ has some handle vertex $h_j$ for an ancestor, and the deletion of $rv_i'$ would imply the deletion of $rh_j'$, which fails as just described.
The budget of directed edge deletions must therefore be allocated between handle edges and plain edges. If a vertex in $G$ participates in multiple triangles, its corresponding plain vertex in $R$ will have multiple handle vertices as ancestors -- but since no handle vertex is the ancestor of any other handle vertex, each plain vertex can choose at most one handle vertex to be its parent in the edited digraph $R'$, and must delete directed edges from all other handle vertices. Thus at most $|V|$ handle edges can survive, meaning that at least $3t-|V|$ handle edges must be deleted in any solution.
We now wish to show that plain edges will be deleted so as to ensure that each handle vertex is either totally "full" or totally "empty" -- that is, that for any handle vertex, either all 3 of its out-edges are preserved, or all 3 are deleted. Say that a vertex in $G$ is assigned to triangle $j$ if $h_jv_i'$ is preserved in $R'$ (not deleted). Each triangle is assigned between 0 and 3 vertices, inclusive. We will show that any valid assignment -- that is, an assignment in which every triangle is assigned either exactly 0 or exactly 3 vertices -- preserves strictly more plain edges, and thus requires strictly fewer deletions of these edges, than any assignment in which some triangle is assigned 1 or 2 vertices.
A valid assignment preserves $|V|$ plain edges, meaning that $2|E|-|V|$ plain edges must be deleted, which together with the $3t-|V|$ handle edges that must be deleted requires a total of $3t+2|E|-2|V|$ edges.
Notice that for any pair of vertices assigned to distinct triangles, there must be no directed edges between their corresponding plain vertices in either direction in $R'$, so if these 2 directed edges exist (i.e., if the vertices are adjacent in $G$) they must both be deleted. IOW, triangle assignments group plain vertices into connected components in $R'$.
Take the assigned vertex counts of the $t$ triangles and sort them in decreasing order. Doing so with a valid assignment produces a list $L^*=333\cdots3000\cdots0$, with $|V|/3$ 3s followed by $t-|V|/3$ 0s. Suppose we have an invalid assignment, producing a list $L$ containing at least one 1 or 2. We will walk along these 2 lists 3 or 6 vertices at a time, comparing the number of preserved plain edges.

Each triangle assigned 3 vertices preserves 3 plain edges (see ASCII art diagram).
Each triangle assigned 2 vertices preserves 1 plain edge.
Each triangle assigned 1 or 0 vertices preserves 0 plain edges.

The longest common prefix of $L$ and $L^*$, consisting of 3s, preserves an equal number of plain edges. Following this, $L$ continues with one of the following cases (with cases having trailing 0s promoted to equivalent cases having trailing 1s):

111: Preserves 0+0+0=0 edges (vs. 3 edges for the corresponding 3 from $L^*$).
21: Preserves 1+0=1 edge (vs. 3 edges for the corresponding 3 from $L^*$).
2211: Preserves 1+1+0+0=2 edges (vs. 6 edges for the corresponding 33 from $L^*$).
222: Preserves 1+1+1=3 edges (vs. 6 edges for the corresponding 33 from $L^*$).

Each case preserves strictly fewer edges than does the valid assignment, and any subsequent cases are at least as bad due to the decreasing order. Thus any invalid assignment requires strictly more plain edge deletions and at least as many handle edge deletions, so a solution with $3t+2|E|-2|V|$ edge deletions implies a valid triangle assignment, from which a solution to the original PIT instance can be immediately read off.
The above establishes NP-hardness of the RTTD problem. Clearly the construction takes polynomial time, so the problem is furthermore NP-complete.


PRECISE DPLL algorithm definition I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently:

In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M., Van Maaren, H., Walsh, T. Feb 2009. Volume 185 of Frontiers in Artificial Intelligence and Applications) it defines it as backtracking + unit propagation.

Also can be accessed from: http://reasoning.cs.ucla.edu/fetch.php?id=97&type=pdf (pages 106-110).

In wikipedia: https://en.wikipedia.org/wiki/DPLL_algorithm#:~:text=In%20logic%20and%20computer%20science,solving%20the%20CNF%2DSAT%20problem.
it defines it as backtracking + unit propagation + pure literal elimination.

And in original 1962 paper: https://archive.org/details/machineprogramfo00davi/page/n5/mode/2up
it mentions 3 rules: one-literal clause rule(unit propagation), affirmitive-negative rule(pure literal elimination) and rule for eliminating atomic formulas(creating resolvents).

Therefore, I am looking for a clear and strict definition of DPLL algorithm. Maybe it should be considered as purely backtracking algorithm and unit propagation and pure literal elimination as its extensions? Or maybe unit propagation is essential part of the algorithm and pure literal elimination is considered to be extention..?

What you are finding is that there are multiple versions of DPLL, all of which might have the name DPLL attached to them, even though they are a little different in some specifics.  If you need to distinguish between them, then I suggest you introduce your own terminology.  I don't think it really matters which one you call the "one true DPLL algorithm".  If you have to pick one, you could use the specification in the original paper, but I suspect it's probably best to understand "DPLL" as referring to a family of closely related algorithms that are very similar to each other but not identical.
"backtracking + unit propagation" is not a definition of an algorithm; it is at best a high-level summary.


How to solve this job scheduling programming problem? I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time Ti and individual deadlines Di. A process can be executed anytime before its deadline. A process can not be executed after its deadline is over. So, you have to find the maximum number of processes that can be executed. Given that n <= 1000 and Ti & Di <= 1,000,000 For example:

Ti Di
3  4
4  8
11 23

Answer = 3

I tried to solve this question using branch & bound mechanism. I first sort the processes on the basis of deadline. Then like 0/1 knapsack, I recursively took 2 cases. One is to take current process and other one is to discard this process. But the complexity of this approach is 2^n and it gave me TLE. Please suggest a better approach for this problem.

I assume your question is "how many jobs can you achieve on time ?". The idea to use something like 0/1 knapsack is good. There is actually a DP resolution of 0/1 knapsack much more efficient than "recursively select or discard each item".

Let's call $t_{max} = max(D[i])$, the end horizon of your problem.

Create a vector $A$ of size $t_{max}$, $A_i[t]$ stands for the number of achieved jobs at time $t$ after considering all jobs until $i^{th}$ one. Initially, $A_0$ is filled with 0.

Then you loop on jobs, to build $A_i$ from $A_{i-1}$:

for t from D[i] to T[i] by -1:
    A[t] = max(A[t], A[t-T[i]]+1)

Time complexity is $O(Nt_{max})$.


Looking for a ranking algorithm that favors newer entries I'm working on a ranking system that will rank entries based on votes that have been cast over a period of time.  I'm looking for an algorithm that will calculate a score which is kinda like an average, however I would like it to favor newer scores over older ones.  I was thinking of something along the line of:

$$\frac{\mathrm{score}_1 +\ 2\cdot \mathrm{score}_2\ +\ \dots +\ n\cdot \mathrm{score}_n}{1 + 2 + \dots + n}$$

I was wondering if there were other algorithms which are usually used for situations like this and if so, could you please explain them?

You could use any function that gives a lower weight to older entries. For example, if data consists of scores, $s_1,\ldots,s_n$, where the index  corresponds to the 'time of arrival' of the entry, that is, newer entries have larger indices, then you could use a weight function that increase as $i$ increases. So any 'increasing' function will do. Examples include:

$f(x)=e^x$
$f(x)=\log x$
$f(x)=x$
$f(x)=x^2$

etc.

Then your function will be

$\dfrac{\sum_{i=1}^n s_i\cdot f(i)}{\sum_{i=1}^n f(i)}$.

Actually, it makes more sense to give the newest entry the lowest index and make the weight function decreasing. This way you can tune it by setting the weighting that you want to give to the first element.

Wikipedia has an entry on weight functions, some examples can be found on the page about weighted means.


The set of turing machine that stops with input zero is not recursive If M is a Turing Machine, consider the subset of $\mathbb{N}$ defined as:
$$ \mathrm{ZTM} = \{ x \mid M_x(0)\downarrow \} $$

i.e. the set of 'indexes' of machines that halt on zero. It is possible to use Rice's theorem to prove that this set is r.e. but not recursive.

But I'd like to have a direct proof, using directly some diagonalization argument if possible.

Hint: if you want to know whether $M$ accepts $w$, build a machine that replaces its input with $w$ and then does whatever $M$ does.


Difference between the Cartesian product in set theory and in relational algebra What's the difference between the Cartesian product in set theory and in relational algebra?

The Cartesian product in set theory is defined as:

$$A \times B = \{(a, b) \mid (a \in A) \land (b \in B)\}$$

I think this is exactly how it works in relational databases, but Wikipedia tries to make a difference that I don't understand:

$$ R \times S := \{ (r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m) \mid (r_1,r_2,\dots,r_n) \in R, (s_1,s_2,\dots,s_m) \in S \} $$

The Wikipedia definition merely "opens the parentheses". Using the pure set-theoretic definition, we would expect
$$ ((r_1,r_2,\dots,r_n),(s_1,s_2,\dots,s_m)) $$
instead of
$$ (r_1,r_2,\dots,r_n,s_1,s_2,\dots,s_m). $$
Assuming $R,S$ are both relations over the same universe $U$,
the Wikipedia definition ensures that $R \times S$ is an $(n+m)$-ary relation over $U$. Under the set-theoretic definition, we get a binary relation over $U^n$ when $n = m$, and a unary relation over $U^n \times U^m$ in general.

We often write $U^n \times U^m = U^{n+m}$, but this isn't in general an equality of sets (it might be in some special cases, depending on the exact definition of $U^n$). Rather, we identify $U^n \times U^m$ with $U^{n+m}$, that is, we ignore the difference (this informal notion can be formalized). The difference between $R \times S$ as sets and as relations is similar – we identify the two objects although they are "physically" different.


Enumerating programs as graphs, or executing graphs? Both programs and simple graphs can be enumerated using natural numbers (positive integers).

However, what languages or ideas most naturally combine the two?

For example enumerating programs using graphs instead of natural numbers.

Or executing graphs, in other words code described by a graphs shape instead of by text, and not just for tree shaped graphs.

We can summarize your original findings as follows: there is an effective enumeration for programs and graphs. An effective enumeration of a countable set $S$ is a computable bijection between the natural numbers and $S$, that is, a program $P(n)$ such that $S = \{ P(n) : n \geq 0 \}$ and $P(n) \neq P(m)$ for $n \neq m$.

There are many countable sets which can be effectively enumerated – there is nothing special about programs and graphs. We can generalize and say that if $S_1,S_2$ can be effectively enumerated, then there is a computable bijection between $S_1$ and $S_2$ (why?), but this doesn't say much about any relation between $S_1$ and $S_2$.


A Proof for NP-completeness I think the following question is a mix of the Traveling Salesman Problem and the Subset-sum Problem, which makes it really hard (for me) to solve... .
The problem is stated as follows:

There are a total of $n$ cities.
The salesman must start his journey at a certain city, and return to that specific city at the end of his tour.
Whenever the salesman reaches a city he hasn't been to, he can earn $r_i$ dollars there. $r$ is a positive real number, and $i$ denotes the city number.
The salesman can visit the same city more than once, but he cannot earn extra cash there.
The salesman does not have to visit every city.
By traveling from city $i$ to city $j$, a cost of $f_{ij}$ is incurred everytime. $f_{ij}$ is a positive real number. (This is like a negative weighted edge.)
The problem asks whether there exists a route for the salesman to earn a net revenue of at least $k$ dollars.

This problem is clearly in NP, but how should I prove that it is NP-complete?
Since the salesman can wonder around the same cities, can I still map this question to the 3-SAT problem (like the subset-sum case) and prove that it is NPC?
Many thanks.

Hint. Reduce Hamiltonian path to this problem. Use the rewards $r_i$ to say that you have to visit each city, use the costs $f_{i,j}$ to say that you can't use more than one edge per city and set the target $k$ to an appropriate value.


Efficient way to find the i-th size in a BST Given the following definition of binary search tree:

$$\text{size}(t)=\cases{0\qquad\qquad\qquad\qquad\qquad\qquad t=\text{ null}\\
1+\text{size(t.left)+size(t.right)}\qquad\text{otherwise}}$$

for each vertex in the tree t.size contain the size of it's subtree

  Write an algorithm  selection(T,i) that gets a Tree with size at each vertex and return the $i-$th smallest/largest size in the tree

Attempt:

I discovered that the size of a vertex is the number of vertices that there are in the specific root:

e.g:

                              V_1
                             /   \
                           V_2    V_3
                           /      / \
                         V_4     V_5 V_6

The size of $V_4,V_5,V_6$ is: $1+0=1$

The size of $V_2$ is: $1+1=2$

The size of $V_3$ is: $1+1+1=3$

The size of $V_1$ is: $1+3+2=6$

Now to scan all vertices in the tree using preorder or postorder and to find the $i-th$ size, running time $O(|V|)$,

I am looking for something more efficient.

(Please check the problem statement: having sub-tree sizes at each vertex available in constant time is very useful to find the $i$−th smallest/largest element/key (with $2$ being the 3rd smallest element in $1, 2, 2, 2, 3, 4$).)

For finding the $i$−th largest size, notice the tree to be a max-heap with respect to sub-tree sizes.
In search of the $i$−th smallest size, assume that the tree is perfectly balanced but for the path to one leaf, which is longer by i ($∄j: i = 2^j-1$). Before encountering that path/vertex, all sizes no larger than i will have been of the form ($2^j-1$). As you don't know if and where such a path/vertex exists, you will have to visit on the order of all n vertices.
Unless you find a way to know the $i$−th size among $Ο(n)$ candidates faster, this will be $Ω(n \log(i))$ in $Ο(i)$ space. (This depends on how much additional memory can be used, e.g., with $Ο(n)$ memory, you can do a counting sort of sizes encountered in $Ο(n)$ time.)

Run-time can be reduced by properly bounding the search:
Every non-empty tree will contain at least one leaf, so if i is $1$, return $1$.
For $1 < i$, keep track of the highest size s such that every size up to s is known to have been encountered. When s reaches $i$, return that. Never descend from vertices with size no greater than s.


shortest time based on traffic congestion data I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data.
Consider that I have a server which gives me real time traffic congestion data for all the path segments in a road network. Now I want to develop such an algorithm which can predict time to be taken based on these data. So in short:

time_to_be_taken_from_source_to_destination = function ( traffic_congestion_data ). And 'time_to_be_taken_from_source_to_destination' is proportional to 'traffic_congestion_data' as time increases when traffic_congestion increases.

Are there any such algorithm alraedy developed? Any idea? reference to any algorithm or theory will be appreciated.

There is no special "algorithm theory" behind this.

You decomposed this data into a graph, right? You have intersection nodes, and you have edges with path difficulty (distance/average speed), yes? The congestion data simply modifies the average speed of the edge, so it's just A* business as usual. Regular shortest path heuristics will probably still be relevant for conservation purposes if you're lazy.

Obviously a prominent example of an implementation of this would be https://maps.google.com/.


Which calculus is based on first-order functions and is Turing complete? Which calculus is based on first-order functions and is Turing complete?

I know of calculi which are Turing complete, but based on higher-order functions:

Lambda calculus
SKI combinator calculus

There is also a calculus based on first-order functions, but is not Turing complete:

Kappa calculus

I know that first-order functions by itself aren't Turing complete,
but first-order functions with recursion and primitive types as $\mathbb{N}$ is.

There are many, but I think the most famous one µ-recursive functions. It describes functions from $\mathbb{N}^{(\mathbb{N})}$ to $\mathbb{N}$, i.e. from tuples of naturals to naturals. This can be transformed into a theory of functions from $\mathbb{N}$ to $\mathbb{N}$ by composing with an encoding of tuples; I think the reason it isn't commonly presented that way is that it doesn't look neat.

µ-recursive functions are defined as follows:

All constant functions are µ-recursive.
The successor function ($S(n) = n+1$) is µ-recursive.
Projections ($\pi_i(n_1,\ldots,n_k) = n_i$) are µ-recursive.
Composition: if the $f_i$ and $g$ are µ-recursive then $(n_1,\ldots,n_{k_1+\ldots+k_m}) \mapsto g(f_1(n_1,\ldots,n_{k_1}), \ldots, f_m(n_{k_1+\ldots+k_{m-1}+1},\ldots,n_{k_1+\ldots+k_m}))$ is µ-recursive.
Primitive recursion: if $f$ and $g$ are µ-recursive then the function $h$ defined by $h(0,n_1,\ldots,n_k) = g(n_1,\ldots,n_k)$ and $h(n+1,n_1,\ldots,n_k) = f(n,n_1,\ldots,n_k,h(n,n_1,\ldots,n_k))$ is µ-recursive.
Minimisation: if $f$ is µ-recursive then so is the function that maps $n_1,\ldots,n_k$ to the smallest $x$ such that $f(n_1,\ldots,n_k,x) = 0$.

Note that in the definition of the minimisation operator, it is possible for $x$ not to exist. In this case the resulting function is partial. This calculus thus defines partial recursive functions.

If you restrict the calculus to total functions, you get the recursive functions, with the same computing power as Turing machines.

The minimisation operator is usually written $\mu$ and gives the calculus its name. If you omit it, the resulting set of functions are exactly the primitive recursive functions (indeed that's a convenient way to define them).


Interpretation of '1/3' in IEEE floating point representation For a rational number 1/3 below is the floating point representation(64 bit) of decimal expansion 0.3333333....

As per the above bit structure, I would like to interpret the value of exponent(11 bits) and value of fraction(52 bits).

exponent has
 11 bits. How do I interpret exponent value?

fraction has  52 bits.
   Here 0101 is decimal 5. Am not sure if we captured fractional part 33333333... of decimal expansion? To capture fractional part am I suppose to expect 0011 pattern instead of 0101. How do I interpret fractional part?

The fractional part is in binary: $(0.01010101\ldots)_2 = (0.333333\ldots)_{10}$. To convince yourself of this, try multiplying the binary $0.0101010101\ldots$ by $3$: you will get $0.111111\ldots = 1$. In a similar way, the decimal $0.0101010101\ldots$ equals $1/99$.

The mantissa (fractional part) in fact has an implicit $1.$ in front, so it actually equals $(1.01010101\ldots)_2 \approx 4/3$. The exponent should therefore be $-2$, since $1/3 = 4/3 \cdot 2^{-2}$. The exponent itself is stored with an offset of $1024$ (or more generally, $2^{w-1}$, where $w$ is the width of the exponent field), that is, instead of $-2$ we actually store $1022$, which in binary reads $01111111101$.

You should note that the floating point number doesn't represent $1/3$ exactly, rather a number pretty close to $1/3$. The only numbers representable exactly in floating point (given enough precision) are dyadic numbers, which are numbers of the form $A/2^B$ (for integer $A,B$).


Count arrays with size n, sum k and largest element m I'm trying to solve pretty complex problem with combinatorics.

Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K and all the elements in the range [1, M]

Constraints:

1 <= N <= 100
1 <= K <= 100
1 <= M <= 100

Example

Let's say N = 2, K = 5, M = 3. This means that we want to count arrays of integers of size 2 with sum of all elements equal to 5 and elements in range [1, 3]. There are total of 2 arrays: {2, 3} and {3, 2}. Please note that the order of the elements also matters, {2, 3} is not equal to {3, 2}

Second example: N = 4, K = 7, M = 3. We want to count arrays of length 4, sum of 7 and elements in range [1, 3].

There are total of 16 possible way of arrays: (1,1,2,3), (1,1,3,2), (2,1,1,3), (3,1,1,2), (2,3,1,1), (3,2,1,1), (1,2,3,1), (1,3,2,1), (1,2,1,3), (1,3,1,2), (1,2,2,2), (2,1,2,2), (2,2,1,2), (2,2,2,1)

What I have tried

I know that one solution is to generate all possible arrays, but such algorithm in best case will work in complexity O(N!) which is far too big for N = 100. I started thinking about solving this with three-dimensional dynamical programming, but I cannot find the relations between the states.

I'm thinking about this way: Let f(i, j, l) be the number of arrays of length i, sum j, and largest element l. We can see that for i = 0 f(i,j,l) = 0, so this is I think the base case. Also f(1, 1, 1) = 1 is another base case.

Now I cannot find the relations between the states. Can you give me some hints how to find the relations between the states. Thanks in advance.

You actually don't need the largest element l in your recursive function. It doesn't make such sense to use it, since the largest number in an array has no influence on the other numbers.

In most (all?) dynamic programming problems you have to think about the last step / the last part. For f(i, j) you have an array with i numbers. You can imagine, that in the last step you added the last number to the array. So before you added the last number, the array only consists of i-1 numbers.

Now, if the added number was 1, then there are f(i-1, j-1) many arrays. If the added number was 2, then there are f(i-1, j-2) many arrays. And so on...

Add all those possibilities up, and you end up with f(i, j).


Why is it that if we assume the Church-Turing thesis to be true, then human language must be recursive if the brain is finite? I was reading "Why Only Us" by Chomsky and Berwick, and it said:

  If one subscribes to the Church-Turing thesis along with the
  assumption that the brain is finite, then there is no way out: we
  require some notion of recursion to adequately describe such
  phenomena.

I find this sentence confusing. What does the Church-Turing thesis have to do with recursion and the human brain? If anything, it seems obviously false to me because the Church-Turing thesis talks about computable things that require a Turing Machine, which in turn obviously requires an infinite tape.  The brain obviously doesn't have this since the brain is finite, unless we somehow assume the brain can always "get a new piece of paper to write on". But even if that was resolved, what does recursion have to do with this, and how is any of this related to language?

This was a fun little rabbit-hole to jump into!  My understanding is not that dissimilar from what you wrote in your comment:

"Basically IF Church-Turning & Brain finite THEN recursion."

But you forgot to add "and if there is arbitrarily deep layering of semantic meaning".  So, really we would have:

If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.

Now let's see if I can unpack that a little for you.

The authors are arguing that the components of sentences are placed into semantic layers that can group words rather differently than strict word-ordering would suggest, and furthermore, that these layers are effectively unlimited.  Consider this sentence:

Mary and John went to the new movie (which was excellent) with Sam.

Mary, John, and Sam are at one semantic layer, the new movie is at a second, and the fact that the movie was excellent is at yet a third layer.

Mary and John went to the new movie, (which, as you expected, was excellent) with Sam.

We've now added a fourth semantic layer.  And, I hope it is obvious that we could keep going!  The sentence would become convoluted and hard to follow, but we could keep adding semantic layers as many times as we wish.

There is a second idea here as well. It is interesting that Mary, John, and Sam are at the same semantic layer, even though they are far apart in the sentence.  This is evidence that there really is some kind of semantic layering, and not merely word proximity at play.  We read "Mary and John", delve down into a new layer, and eventually return back to this first layer in order to add "with Sam".  I mention this because it is already suggestive of recursion!

I understand your objection about having a finite amount of brain, and it is a very good counter-argument to the idea that we can follow arbitrarily deep semantic layers, but it is not an objection to the idea that human language is structured to be able to create them, which is really what the authors are arguing.

If you accept that language is structured in such a way as to permit this arbitrarily deep layering, then you are doing something very similar to a Turing Machine, which can represent any computable function using a finite number of states.

The Church-Turing thesis involves the notion that all of these representations are, somehow, recursive.  This makes sense if you consider that all three of the systems involved (Godel, Turing, and Church) can do this same trick of going arbitrarily deep using a finite number of rules at the start.  There must be some mechanism that allows arbitrary depth, which means that we must be able to repeat rules or states, which means recursion.

We are very close to having finished here.  If arbitrarily deep semantic layering AND the Church-Turing Thesis AND a finite brain, THEN recursion.

We only are left with the finite brain.  But of course, if the brain were infinite, then we would have no need for recursion.  We could represent every semantic layer in a new region of the brain, and keep doing this forever.


check if a binary tree is a binary search tree I have some doubts about this algorithm which checks if a binary tree is a binary search tree:

isAbr(x)
    {
            if(x == NULL)
                    return <true, -∞, +∞>;
            if(x.left == NULL && x.right == NULL)
                    return <true, x.key, x.key>;

            <abrLeft, minLeft, maxLeft> = isAbr(x.left);
            <abrRight, minRight, maxRight> = isAbr(x.left);
            abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);
            min = MIN(minLeft, minRight, x.k);
            max = max(maxLeft, maxRight, x.k);

            return <abr, min, max>
    }

in particular, it is not clear to me what happens when a node has only one child:

for example, here, the node with the value 6 returns $<true, 6, 6>$, and the NULL node to the right of the root returns $<true, -∞, + ∞>$; but with the instruction abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft);
don't we get FALSE $(8 < -∞)$?

abr = abrLeft && abrRigh && (x.key > maxLeft) && (x.key < minLeft); should likely be comparing with maxLeft and minRight, not maxLeft and minLeft

if(x == NULL)
    return <true, -∞, +∞>;

I'm guessing the point of returning infinities here is to make a NULL vertex NEVER fail the > and < comparisons above, in which case in makes more sense to return <true, +∞, -∞>;


How to find the original coordinates of a point inside an irregular rectangle? I'm a third year computer science student. I'm working on a project Data-show touch screen In schools classrooms.
I'll try to explain my problem as much as I can.
The project has three main components; A computer, a Data-show and a webcam.
The teacher will plug the data-show in the computer and the computer screen will appear on the wall of the classroom to all students.
The main purpose of the project is to turn the image of the screen displayed on the classroom wall into interactive screen; when the teacher tabs with his finger on an image of a Button displayed on the wall, the webcam that is connected to the computer will capture the position of the teacher's finger and find his (x,y) coordinates for a reference point on the wall, and raise a click event in the related (x,y) position on the screen.
The screen of the computer has two dimensions; Width->X and Height->Y. And for every point in the screen such as P, it could be located on the screen using two numbers (Px,Py), where Px is the distance between the point P and the left side of the screen, and Py is the distance between the point P and the top side of the screen. In other words, the reference for all points in the screen is the top left corner of the screen.

The data-show will display an irregular Quadrilateral shape of the screen on the wall. the shapes will not be regular squares or rectangles due to the angle that the teacher puts the data-show in. What I'm asking for are the equations that will calculate the (x,y) point on the screen that represents the (x,y) tapped point on the wall.
There is mainly four shapes the data-show may display on the wall. For each shape of them the only known things are the coordinates of the four angles(corners) of the quadrilateral shape.
1. an optimal rectangle
The displayed image on wall has a very low chance to shape an optimal rectangle, but it's the basic shape that could be formed.

Suppose that the red point P'(Px',Py') represents the coordinates of the place the teacher tapped on with his finger.
To get the original (Px,Py) coordinates from the point (Px',Py') on the wall, I can do the following.

Calculate the width->X' and the height->Y' of the displayed image by the law of distance between two points.

find the ratio between X&X', and between Y&Y'. I'll call the first ratio rx and the second ratio ry.

Multiply Px' by rx to get Px, and multiply Py' by ry to get Py.

2. an optimal trapezoidal.

The displayed image on wall could also shape an optimal trapezoidal. I asked some of my friends from the applied mathematics college to help me to find the two equations to find the original coordinates of the point, and they did some calculations and came out with these two equations;
In this shape

To find X:

and to find Y I can use the same way used in the rectangle; finding the ratio between Y and the height of the trapezoidal H.

3. an irregular quadrilateral.
My question is about this shape, the data-show in most times will shape an irregular shape. Imagine this shape like

None of the shape's lines is vertical or horizontal, all lines may have different lengths and they may have different angels from each other.
My question is
I'm searching for equations that will find the original P(x,y) point of the point P'(X',Y'). Things I know are the coordinates of the points P1, P2, P3, P4, P'
What are those equations? and how are they derived?

This is what the concept of a homography was invented for.  You know the coordinates of the four corners on your screen and on the wall, and you want to find a transformation that maps from screen coordinates to wall coordinates.  There will be a homography that maps between the two coordinate systems.  So, your task is: given four points with known mappings, find a homography that is consistent with that.

If you're using OpenCV, see the findHomography() method, as well as warpPerspective().


Shortest path from $s$ to $v$ in unweighted simple directed graphs Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an efficient algorithm for finding the length of a shortest path from $s$ to every other vertex in the graph, fulfilling the following condition: the path includes at most two red edges. In other words, every $v∈V$ should be labeled with the length of a shortest path from $s$ to $v$ in which there are at most two edges from $E'$ and any number of edges from $E\backslash E'$.

Create a new graph $G' = (W,F)$ as follows:

For every every $v\in V$, create three vertices $v_0,v_1,v_2$ in $W$. The index $i$ in $v_i$ represents the fact that any path to this vertex uses exactly $i$ red edges.
For every edge $(u,v)\in E\setminus E'$, create the edges $(u_0,v_0)$, $(u_1,v_1)$ and $(u_2,v_2)$ in $F$.
For every edge $(u,v)\in E'$, create the edges $(u_0,v_1)$, $(u_1,v_2)$ in $F$.

Now you just have to compute the length of the shortest path from $s_0$ to any other vertex in your new graph $G'$ (if the vertex is unreachable then let this distance be $+\infty$). The length of the corresponding shortest path from $s$ to $v$ in $G$ is then the minimum of the lengths to $v_0,v_1$ and $v_2$.


Proving a DFA recognizes a language using induction The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction.

So far, I have managed to split each state up was follows:

q0: Nothing has been input yet.

q1: The last letter was a $1$ and the last two characters were not $01$.

q2: The last letter was a $0$ with the letter before that a $1$.

q3: The last letter was a $0$ and the last two characters were not $10$.

q4: The last letter was a $1$ with the letter before that a $0$.

q5: At least one of the two substrings has been seen.

Induction basis: The empty string does not have either of the substrings, so is correctly rejected.

But I am not too sure on how to proceed after this. I do not know how I should split the string up to prove that the $DFA$ is accurate.

If anyone knows how I should proceed with this, I would love some help!

The induction you probably want is to show that a string $w$ ends in state $q_i$ iff it satisfies the property associated to that state.

The basis then is that the empty string, which must end in $q_0$, satisfies the property there.

You should be more precise in some of your properties. In $q_4$, the string ends in 01 as you state, but has never seen any of the special strings, in particular it did not end in 101.


Energy consumption off CNN models I want to calculate/estimate the energy consumption for the different convolutional neural networks. Is there any possibility to measure the energy consumed by AlexNet for example with a tool or with Keras or something else?

The energy usage will vary depending on the machine, but as long as all of your results are from the same setup there's a comparatively low-tech, simple solution: Hook up your computer to an electricity meter and take some measurements with the computer "at rest", to get a baseline of its energy consumption. Then, run several trials with each model you're testing, and adjust the readings by the baseline to get the net difference in energy consumption when the model is running.


Proof with induction even number of letter I have to proof that in a word $w$ the number of the letter d is always even.
Let $L \subsetneq \Sigma^*$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$
such that a word $w$ is in $L$ if and only if it is $a$ or $b$ or of the form $w = ducvd$  where $u$ and $v$ are word of $L$.
Examples:
$dacad$, $ddacbdcad$, $dddbcbdcdbcbddcad$
I know there are three cases:

$|w| = 0$ the number of the letter d is zero and even

$|w| = 1$ and $w = a$ or $w = b$ same as number 1

$|w| = 5$ and $w = ducvd$ the number of letter d is even
I know how induction works, but I don't know to write the base, hypothesis and
step. I think it works with the length of $w$. Does somebody have a hint?

The proof is by induction on the length of $w$. If $|w| \leq 2$ then necessarily $w = a$ or $w = b$, and in both cases $w$ doesn't contain any $d$'s. If $|w| \geq 3$ then necessarily $w$ is of the form $ducvd$, where $u,v \in L$ are shorter words. By induction, each of $u,v$ contains an even number of $d$'s. It follows that $w$ also contains an even number of $d$'s: if $u,v$ contain $2s,2t$ many $d$'s (respectively), then $w$ contains $2s+2t+2=2(s+t+1)$, which is also even.


How do you produce a CNF from a circular graph with colouring? If you had a circular graph e.g. A->B->C->D->E->A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node of the same colour, what is the easiest way go about producing a Conjunctive Normal Form of node states (e.g. AR means A is coloured Red) where the models of the CNF correspond on a one to one basis to a legal colouring of the graph?

The easiest way is to solve the more general problem for (undirected) graphs and an arbitrary number of colors. Given a graph $G = (V,E)$ and a set of colors $C$, the formula has variables $x(v,c)$ for every vertex $v \in V$ and every color $c \in C$. There are clauses of three kinds:

For each vertex $v$, there is a clause $\bigvee_{c \in C} x(v,c)$.
For each vertex $v$ and each pair of colors $c,d \in C$, there is a clause $\lnot x(v,c) \lor \lnot x(v,d)$.
For each edge $(v,w)$ and each color $c$, there is a clause $\lnot x(v,c) \lor \lnot x(w,c)$.

In words, these clauses state that:

Vertex $v$ gets some color.
Vertex $v$ gets at most one color.
Vertices $v,w$ (which are connected) don't get the same color.


Is "super-exponential" a precise definition of algorithmic complexity? I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.

For instance, if an algorithm runs for $nC(n-1)$ steps, where $C(\cdot)$ is the Catalan number, is this algorithm super-exponential in $n$?

"Super-exponential" just means more than exponential, so a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim_{n\to\infty} f(n)/c^n=\infty$ for all constants $c$.
Conversely, a function is "sub-exponential" if it is $o(c^n)$ for every constant $c>1$, i.e., $\lim_{n\to\infty} f(n)/c^n=0$ for all constants $c>1$.
Asymptotically, the $n$th Catalan number is $\Theta(4^n\, n^{-3/2})$.  This is $o(4^n)$, so the Catalan numbers are not super-exponential; it is $\omega(2^n)$, so they're not subexponential either. The Catalan numbers are just exponential.
An exception to the above definitions is that, in some contexts, functions of the form $b^{n^k}$ for constants $b,k>1$ are considered to be exponential, even though
$$
\lim_{n\to\infty}\frac{b^{n^k}}{c^n}=\lim_{n\to\infty}b^{n^k-n\log_b c}=\infty\,.$$
For example, the complexity class EXP is defined as the class of languages decided by Turing machines running in time $O(2^{n^k})$ for any $k$. Thanks to Yuval Filmus for pointing this out.


Is this problem P or NP? Given a set of whole numbers $M=\{z_0, ..., z_n\}$ Are there $z_i$ and $z_j$ with $i \neq j$ but $z_i = z_j$?

Is this Problem (surely or only probably) in $P$ or in $NP$? Is it $NP-hard$?

This is the element distinctness problem, and can be solved in polynomial time in many ways. For example, you can go over all pairs of elements and compare them, or if the elements are comparable, you can sort them and then check for duplicate elements (though in principle comparisons could be very time consuming, and in that case potentially the algorithms wouldn't be polynomial time; there's no such problem with the former algorithm).

Make sure you understand what "polynomial time" is. Also, you have a false dichotomy in your title: every problem in P is also in NP; if P=NP then every problem in P is also NP-complete; and if P≠NP then there are problems which are neither in P nor NP-hard.


Which combinatorial problem is similar to this problem? I have $n$ clients and for each client I have different options to choose from, for example, $C= \{C_1,C_2 \}$. For each combination of $n$ options, there is a cost. I want to choose the best combination that minimizes the cost without calculating the cost for each option one by one and then choose the best one and I do not have any constraints. Which combinatorial problem is similar to this one?

For example, If I have $n=3$ and $C =\{1,2\}$, I have set of triples $(x_1,x_2,x_3)$ as $\mathcal{M}= \{(1,2,1),(1,2,2),(1,1,1),(1,1,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)\}$ and equation $cost=x_1+x_2+2x_3$ I want to find the triple that minimizes the cost without calculating one by one. The cost function can be any function not nessesary linear.

In a very literal sense, D.W.'s answer is correct. In the absence of any information about the cost function, there are no alternatives better than simply trying the cost function at each possible input.
However, in real-world applications, we usually know something about the cost function—and as soon as we have a little bit of structure, we can leverage that to create more efficient search strategies.
For example, if the cost function has a relatively simple closed form in terms of the inputs, you may be able to apply an optimizing SMT solver such as the widely-used Z3 from Microsoft Research (interactive tutorial here). These solvers use complex strategies to locate and exploit hidden structure in the input problem and find solutions more efficiently than brute-force search.


How many telescoping constructors will I have? The Builder Pattern solves the problem of Telescoping Constructors; that is, having a single constructor for every possible parameter combination (including those combinations for which a parameter is omitted).

So for example:

  public Food(int id, String name) {
    this(id, name, 0, 0, 0);
  }

  public Food(int id, String name, int calories) {
    this(id, name, calories, 0, 0);
  }

  public Food(int id, String name, int servingSize) {
    this(id, name, 0, servingSize, 0);
  }

  public Food(int id, String name, int fat) {
    this(id, name, 0, 0, fat);
  }

  public Food(int id, String name, int calories, int servingSize) {
    this(id, name, calories, servingSize, 0);
  }
  public Food(int id, String name, int calories, int fat) {
    this(id, name, calories, 0, fat);
  }

  public Food(int id, String name, int servingSize, int fat) {
    this(id, name, 0, servingSize, fat);
  }

  public Food(int id, String name, int calories, int servingSize, int fat) {
    this(id, name, calories, servingSize, fat);
  }

If you set the Builder Pattern up properly, using the voluminous amount of code required, you can simply:

Food food = new FoodBuilder().SetName("Bananas").SetCalories(120).Build();

using any combination of parameters in any order.

Assuming that each parameter in the constructor will always reside at the same relative location while still allowing for omitted parameters, how would one calculate the number of constructors required given the number n of optional parameters needed?

(in the above example, id and name are required parameters, while calories, servingSize, and fat are all optional parameters).

You'll need $2^n$ constructors.  You need one constructor for each possible subset of optional parameters.  There are $2^n$ such subsets.  You have $n$ things, and there are $2^n$ possible ways to choose a set containing some number of those things.

For each subset of optional parameters, you'll write down a constructor for that subset; the arguments to that constructor will be fully determined (they must include all of the required parameters, and all of the optional parameters in the chosen subset, in the specified order).

That said, in Java, the "create many constructors" pattern doesn't actually work, for reasons having nothing to do with combinatorics or the number of constructors.  You might notice that the type signature of the following two constructors is identical:

public Food(int id, String name, int calories, int servingSize) { ... }
public Food(int id, String name, int calories, int fat) { ... }

and that's not allowed in Java, because when the compiler sees an attempt to invoke the constructor (to instantiate the object) with a list of 4 parameters of type int, String, int, int, it won't know which of those two choices to choose.  The approach only works if all of the optional parameters have different, incompatible types.


Difference between present - absent bit and valid - invalid bit in a page table? while reading I found this:

  Present/Absent bit – Present or absent bit says whether a particular page you are looking for is present or absent. In case if it is not present, that is called Page Fault. It is set to 0 if the corresponding page is not in memory.

and

  Valid and Invalid bit are present in the page table of concern process and it indicate whether address generated by cpu is valid or invalid and tells whether the address generated belongs to process address space or not.

Also since the page table contains only the page entries for a process so how come V/I bit present in page table tell that the generated address is not valid for the addresses not present in process.

I am a beginner, so please help me build my concepts.

Many people confuse these two bits. I'll try to explain the concept to best of my knowledge.
Let's say we have 32 bit architecture. so process virtual address space(VAS) will have size of 2^32. VAS space of a process has kernel code and data part and user code and data part.Page table of process contains entries for both user/kernel part. kernel page table entries are same for all processes that is these virtual addresses are mapped to same physical memory frame for all processes.because memory has just one copy of OS code.
process when initialized doesn't use the full VAS.virtual addresses which are not in use as of now have valid bit zero(Invalid). It can make use of more addresses by calling sbrk(), brk() system call.These system calls are used internally by malloc in C(if no holes are present already). which will add more virtual address to process page table that means it will make those pages valid.
Now there is a catch, page table entries which had valid bit set recently are not yet mapped to physical frames, that is where present/absent bit comes into picture. or if they are swapped out due to lack of physical memory.
Now when process will try to access these newly validated virtual address/swapped out address, as present bit is not set it will generate a page fault. Now we'll switch to kernel mode to service the page fault.OS has the disk address of the page to be loaded, once page fault service routine is finished it will make present bit set in the process page table. Meanwhile this page fault routine is being serviced,current process is contexted out and new process is given the cpu as per scheduling algorithm so that CPU cycles are not wasted.
I hope this answer helps.


Testing two DFAs generate the same language by trying all strings upto a certain length Given the language

$EQ_{\mathrm{dfa}} =$ $\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$

Prove that $EQ_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings upto a certain size. Calculate a size that works.

(This is from Sipser chapter 4)

I make a directed graph as usual but if two transitions $\delta(q_1, c_1) = q_2$ and $\delta(q_1, c_2) = q_2$ then the graph I am making will just have one edge for these two characters. My idea is to walk the directed graph in a way so that every transition is traversed, but when I walk over an edge forming a cycle, I would need to traverse the edges I have previously walked through in the cycle once again. Do this for both the DFAs and choose the greater number of edges traversed. Then enumerate through all the strings of this length (from the given alphabet) and the two DFAs are equal only if they accept and reject on the same strings.

I could probably write some pseudocode, but I'm not sure if this is the correct way to approach the problem even.

It can be tested that way, provided we may use the number of states of both automata $A$ and $B$ to compute the bound.

Note that if a finite automaton $C$ has $n$ states then any state in $C$ is reachable by a string of at most $n-1$ letters, or that state is not reachable at all. Assume I want to check whether $L(C)=\Sigma^*$. If $C$ is deterministic then all reachable states must be accepting. This can be tested by checking that all strings up to length $n-1$ are in the language.

The check $L(A)=L(B)$ can be analyzed similarly by considering the product automaton, i.e., the automaton that simulates $A$ and $B$ in parallel.

The product construction needs a little twist. Rather than accepting if both automata accept (computing the intersection) you need to see whether both automata make the same yes/no decision. Thus accept when both components are accepting or when both components are not accepting. Thus the language is $(L(A)\cap L(B))\cup (L(A)^c\cap L(B)^c)$. If that language is $\Sigma^*$ then both automata are equivalent.


Can anyone explain how look-up tables are used for optimal Rubik's cube solvers such as Thistlethwaite's or Kociemba? I have implemented Thistlethwaite's algorithm however, it is far too slow as it is only using graph traversal over many Rubik's cube states. I am currently unsure of how look-up tables are implemented so any help on how I could do so would be greatly appreciated.

In case it's still relevant, the idea is to get indices based on cube states and store the distance (number of moves it takes) to reach the next group from the given state.
For example - G0->G1 only looks at edge orientations. This means, that if you only consider the orientation of an edge at a given position, there are 2^11 possible states (2 ways each of the 11 edges can be oriented, because the orientation of the 12th edge is "forced" in place by the other 11 edges, so the orientation can be assumed).
For G0->G1, it's easy to generate these indices because you can assign each edge position to a bit in a 11-bit integer, and convert it to decimal.
For a state which satisfies G1, the index would be 0 (00000000000) and for a state with all edges oriented badly, the index would be 2047 (11111111111) which gives unique index for each state from 0 to 2047.
Using this logic, run your IDDFS from a solved cube only using the available moves of the group until all permutations were visited. for G0->G1 it should be done in 7 depths.


Why are unbalanced partitions worse than balanced partitions in Quicksort? I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.

After reading this document it shows that worse case partitions are of the type $(0,(n-1)), (0,(n-2)), (0,(n-3))$ and so on. So the work on every step is $Cn, C(n-1), C(n-2)$ , it actually decreases since $C(n) > C(n-1)$. Correct me if I am wrong.

While in best case the partitions on every step can be assumed as $n/2$ on each side or $n/2$ or $n/2 - 1$ on each side. So the work done on each step, is $Cn$
 always.

So how is that better than unbalanced partitions ? The work actually decreases in every step for unbalanced partitions, while for balanced partitions the work actually remains constant on all the steps and depending on the partition algo it may even include the pivot which is already sorted.

for balanced partitions the work actually remains constant on all the steps

That's just false. Have another look at the algorithm: each recursive call gets an input that is properly smaller than the current one.

You also seem to be missing that, for the total cost, you need to add up all the steps. Just saying, "the inputs get smaller", doesn't tell you anything besides that the algorithm terminates.

In the worst case, you get the solution of a recurrence similar to

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= T(i-1) + i
\end{align*}$

which solves to some $T \in \Theta(n^2)$.

In the average case, you get the solution of a recurrence similar to

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= 2T(i/2) + i
\end{align*}$

which solves to some $T \in \Theta(n \log n)$.

To stress my point from above, consider

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= T(i/2) + i
\end{align*}$

which solves to some $T \in \Theta(n)$.

Or

$\qquad\begin{align*}
 T(1) &= 0 \\
 T(i) &= T(i/2) + 1
\end{align*}$

which solves to some $T \in \Theta(\log n)$.

You see that the specifics of the recurrence matter.


How to prove Exact cover problem is NP Complete using Vertex Cover problem? Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from Vertex Cover.

You can reduce from vertex cover in cubic graphs since it is known to be $\textrm{NP}$-hard. Let $G=(V,E)$ be the graph in the instance of vertex cover and, for $v \in V$, call $E_v = \{ (v,u) \mid (v,u) \in E \}$ the set of edges incident to $v$ in $G$.

Construct an instance of the exact cover problem as follows:

The elements to be covered are those in $E$.
There are $7$ sets $S_1^v, \dots, S_7^v$ for each vertex $v \in V$, namely those in $2^{E_v} \setminus \{ \emptyset \}$.

If there is an exact cover $C$ for this instance, then there is a vertex cover of $G$ of size at most $|C|$, namely $\{ v \in V \mid \{S_1^v, \dots, S_7^v\} \cap C \neq \emptyset\}$.

If there is a vertex cover $C$ of $G$, then there is an exact cover of size at most $|C|$. Arbitrarily assign each edge $(u,v)$ of $G$ to one of the vertices in $\{u,v\} \cap C$. For a vertex $v$, let $A_v$ be the set of edges assigned to $v$ and notice that if $A_v \neq \emptyset$ then $A_v = S_i^v$ for some $i \in \{1,\dots, 7\}$. The sought exact cover is then $\{ A_v \mid v \in V \wedge A_v \neq \emptyset \}$.

To conclude the proof you just need to observe that exact cover belongs to $\textrm{NP}$ since the cover itself is a certificate that can be checked in polynomial-time.


Sliding Window Protocol, waiting Time calculation With regard to this explanation in finding Round Trip Time I tried attempting the following question

Question

Frames of $1000$ bits are sent over a $10^6$bps duplex link between two hosts. The propagation time is $25$ ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

Let I be the minimum number of bits ($I$) that will be required to represent the sequence numbers distinctly assuming that no time gap needs to be given between transmission of two frames.

Suppose that the sliding window protocol is used with the sender window size of $2^l$
, where I is the numbers of bits as mentioned earlier and acknowledgements are always piggy backed. After sending $2^I$ frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)

  NB :  $I$ is found to be 5 bits from the link mentioned above

My Approach

Propogation TIme (given) = 25ms

Bandwidth (given)= $10^6$ bps

So, to fully utilize the channel, we must send 106 bits into the channel in a second, which will be 1000 frames per second as each frame is 1000 bits

I = 5, $\Rightarrow$ $2^I$ = 32 frames are sent.

Transmission time (for a frame of size 1000 bits) = $\frac{1000}{106} = 1$ ms.
So, transmission time for $32$ frames = $32$ ms.

$R_{TT}$ (Round Trip Time ) as calculate in the above link is 25ms. Hence the Waiting time would be $32-25=7ms$

But actual answer is given as $20$ms

What is the correct approach to this question ? please explain in detail how $R_{TT}$ should be calculated

You have not calculated the $R_{TT}$ you just used the Propagation Time that a frame needs to travel one way of the duplex link.

This is how you calculate the $R_{TT}$:

$R_{TT} =$ [Propagation time for frame] + [Transmission time for frame] + [Propagation time for ACK] + [Transmission time for ACK]

Since ACK is piggybacked we assume that its frame size will also be 1000bits, so the $R_{TT}$ is:

$R_{TT} = 25ms + 1ms + 25ms + 1ms = 52ms $

Therefore waiting time is: $52ms - 32ms = 20ms$


A lambda calculus evaluation involving Church numerals I understand that a Church numeral $c_n$ looks like $\lambda s. \lambda z. s$ (... n times ...) $s\;z$. This means nothing more than "the function $s$ applied $n$ times to the function $z$".

A possible definition of the $\mathtt{times}$ function is the following: $\mathtt{times} = \lambda m. \lambda n. \lambda s. m \; (n\; s)$. Looking at the body, I understand the logic behind the function. However, when I start evaluating, I get stuck. I will illustrate it with an example:

$$\begin{align*}
 (\lambda m. \lambda n. \lambda s. m \; (n\; s))(\lambda s.\lambda z.s\;s\;z)(\lambda s.\lambda z.s\;s\;s\;z) \mspace{-4em} \\
 \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; ((\lambda s.\lambda z.s\;s\;s\;z)\; s)) \\
 \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; (\lambda z.s\;s\;s\;z) \\
 \to^*& \lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z
\end{align*}$$

Now in this situation, if I first apply $(\lambda z.s\;s\;s\;z)\;z$, I get to the desired result. However, if I apply $(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)$ first, as I should because application is associative from the left, I get a wrong result:

$\lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \to \lambda s. \lambda z.(s\;s\;s\;(\lambda z.s\;s\;s\;z))\;\;z$

I can no longer reduce this. What am I doing wrong? The result should be $\lambda s. \lambda z.s\;s\;s\;s\;s\;s\;z$

I think your reduction is correct (I've only eyeballed it, though). At the end, you can't apply $(\lambda z. s s s z)$ to $z$, this never appears in the term. $\lambda z. f f z$ is $\lambda z. (f f) z$, not $\lambda z. f (f z)$. Functions in the lambda-calculus take a single argument; they are effectively curried: a two-argument function is implemented as a one-argument function that takes the first argument and returns a new one-argument function that takes the second argument and returns the result.

You made the same mistake when defining Church numerals. The Church numeral for $n$ is based on composing a function $n$ times. “The function $s$ applied $n$ times to the function $z$” $\lambda s. \lambda z. s (s ( … s \: z) … ))$. What you wrote is the function $s$ applied $n-1$ times to the function $s$ and finally to $z$, which doesn't strike me as a useful term.

$2 \times 3$ is thus $(\lambda m n s. m (n s)) (\lambda s z. s (s \: z)) (\lambda s z. s (s (s \: z)))$. I'll let you check that it does reduce to $\lambda s z. s (s (s (s (s (s \: z)))))$.


Proving that two sets of strings are equal I am stucked at this problem:

Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$.

Let's define foreach $i,j\in\{1,...,m\}$, $k\in\{0,1,...,m\}$

(Note: the $\delta$ below is the extension of $\delta$ to $\Sigma^*$)

$L_{i,j}^k=\{w\in\Sigma^*|\delta(q_i,w)=q_j \land \forall u\in PREFIX(w)-\{\epsilon,w\}, \delta(q_i,u)=q_x\to x\leq k\}$

Now let's define the following sets recursively:

For all $i,j\in\{1,...,m\}$:
$M_{i,j}^0=\{\sigma\in\Sigma|\delta(q_i,\sigma)=q_j\}\cup\begin{cases}
\emptyset, \text{if $i\neq j$} \\
\{\epsilon\}, \text{if $i=j$}
\end{cases}$

For all $i,j,k\in\{1,...,m\}$:
$M_{i,j}^k=M_{i,k}^{k-1}\cdot (M_{k,k}^{k-1})^* \cdot M_{k,j}^{k-1}\cup M_{i,j}^{k-1}$

Prove that for all $i,j\in\{1,...,m\}$ and $k\in\{0,1,...,m\}$ we get $L_{i,j}^k=M_{i,j}^k$.

I've tried to prove it by induction on $k$ but failed.

(Note: I've encountered these sets in the proof of the Theorem that says that every regular language has a regular expression)

Thanks a lot.

It is not totally clear what are your main obstacles to get the proof done.

Note that $L_{i,j}^k$ is the set of all strings $w$ on a path $\pi$ from $q_i$ to $q_j$ such that for each intermediate state $q_x$ we have $x\le k$; i.e., all intermediate states have index at most $k$.

Consider state $q_k$.
Now either the path $\pi$ does not enter $q_k$ at all: then all indices are at most $k-1$ meaning that $w$ belongs to $L_{i,j}^{k-1}$. Or it may enter $q_k$ one or more times. Thus the path is of the form $\pi: q_i \leadsto q_k \leadsto \dots \leadsto q_k \leadsto q_j$, where the subpaths may start and end in $q_k$, but do not pass that state. So the string $w$ can be partitioned into strings that belong to $L_{i,k}^{k-1}$, $L_{k,k}^{k-1}$, ..., $L_{k,k}^{k-1}$, $L_{k,j}^{k-1}$.

That should prove that $L_{i,j}^{k} = L_{i,k}^{k-1} ( L_{k,k}^{k-1} )^*L_{k,j}^{k-1} \cup L_{i,j}^{k-1}$ (or at least the inclusion from left to right, the other inclusion follows similar argumentation).

With this knowledge the induction is on the subscript $k$, and the induction step is

If $L_{i,j}^{k-1} = M_{i,j}^{k-1}$ for all $i,j$ then $L_{i,j}^{k} = M_{i,j}^{k}$ for all $i,j$.

This should be obvious, just plug in the equations we have.


Clarification on halting predicate computability I am tackling the halting problem right now and its remarkable theorem. My book states $\text{HALT}(x,y)$ is true if $\psi^{(1)}_{\mathcal P}$ is defined and conversely $\text{HALT}(x,y)$ is false if $\psi^{(1)}_{\mathcal P}$ is undefined.

The purpose of the theorem, of course, is showing that $\text{HALT}(x,y)$ is a not computable predicate. I will report the extract of the proof given:

Suppose $\text{HALT}(x,y)$ were computable. Then we could construct the program $\mathcal P$:

$$[A]\;\;\;\;\;\text{IF HALT}(X,X)\text{ GOTO } A$$

It is quite clear that $\mathcal P$ has been constructed so that

\begin{equation}
\psi^{(1)}_{\mathcal P}=
\begin{cases}
\text{undefined} \;\;\; \text{if HALT}(x,x) \\
0 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\text{if ~HALT}(x,x)
\end{cases}
\end{equation}

I don't understand how $\psi^{(1)}_{\mathcal P}$ is undefined if $\text{HALT}(x,x)$ is true, shouldn't $Y$ be equal to $0$ by default and moreover how could a non-terminating program be defined can have $0$ as output value. What am I missing here?

Edit: $\psi^{(1)}_{\mathcal P}(x)$ is the value of the output variable $Y$ at the terminal snapshot.

Let's walk through the proof given by [Davis94].  I am familiar with this text and have it in front of me.  The HALT predicate is defined:

$$
HALT(x,y) \Longleftrightarrow \text{program number $y$ eventually halts on input $x$.}
$$

Given this defintion of HALT, don't worry about how such a program would be defined.  It is not important.  Just assume that HALT exists, that it works, and that this is what it does: It uses $y$ (a Gödel number -- see Section 8 of Ch. 3) which represents a particular program, and $x$, an input to that program, and tells us if that program halts when it is run with that input.  It can do this for any program, with any input.

Now, let's define a new program called $P$:

$$
[A]~\text{IF}~HALT(X,X)~\text{GOTO A}
$$

Look at how we are using HALT here: we are asking "Does program X halt when given an input of X (itself)?"  And if it does halt, we loop infinitely -- creating a program that does not terminate -- a program that does not halt.  In other words:

$$
\psi_P^{(1)}(x) =
\begin{cases}
\text{undefined} & \text{if} & ~~~~HALT(x,x) \\
0 & \text{if} & \sim HALT(x,x)
\end{cases}
$$

Let's pause and answer your first question about $\psi_P^{(m)}$ being undefined: this is part of the definition given in Section 4 of Chapter 2: $\psi_P^{(m)}(r_1,...,r_m)$ is undefined if $P$ never terminates.  And our program never terminates when $HALT(x,x)$ is true because we have written it that way, it loops infinitely.  As to your second question about the default output of 0: this happens when the program $P$ does terminate.

Now let the Gödel number of our new program $P$ be $y_0$.  This means that

$$
HALT(x,y_0) \Longleftrightarrow ~ \sim HALT(x,x).
$$

(we are taking the left side from the definition of HALT and the right side from our program $P$).  Since this is true for any input $x$ we could also write:

$$
HALT(y_0,y_0) \Longleftrightarrow ~ \sim HALT(y_0,y_0),
$$

which is clearly a contradiction; HALT cannot exist.


Finding max flow in a undirected graph According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents something like $f((u,v))=c$ and $f((v,u))=c$ (where c is the capacity in the original undirected edge) but then that means the original graph has flow $2c$. Could someone prove or explain why the capacity restrictions are still satisfied?

What you describe can happen in a feasible flow. However the net flow across the (undirected) edge $\{u,v\}$ would be $0$. Also, you say that the original graph has flow $2c$, this is false since the amount of flow from a vertex $s$ to a vertex $t$ in a graph is not the sum of the flows across all the edges, but rather the amount of flow leaving $s$ or, equivalently, entering in $t$.


Does the naive conversion of a Boolean Formula to CNF have a polynomial or exponential complexity? I am reading the naive conversion to CNF, this procedure is explaining in this book book, but I have not found a conplexity analysis of this algorithm:

elimination of equivalence
Elimination of Implications
elimination of double negation
De Morgan Laws
distributive law

I found one implementation of this method in this Repo https://github.com/netom/satispy

Thanks

Any algorithm necessarily has exponential complexity, since the CNF of a formula can be exponentially longer than the DNF, and the input might be in DNF.


Solving $T(n)=4T(n/2)-1$ without using the master theorem How can I solve the following recurrence without using the master theorem?

$T(n)= 4T(n/2)-1$  for $n>4$ and $T(n)=5$  for $n\le 4$, $n$ is a power of $2$.

The idea is to convert this recurrence to the simpler recurrence
$$ S(n) = 4S(n/2). $$
How do we do this? Let $S(n) = T(n) + f(n)$. Since
$$
S(n) = T(n) + f(n) = 4T(n/2) - 1 + f(n) = 4S(n/2) - 4f(n/2) - 1 + f(n),
$$
we need that
$$
f(n) = 4f(n/2) + 1.
$$
Luckily, $f(n) = -1/3$ is a solution. So $S(n) = T(n) - 1/3$ satisfies
$$ S(n) = 4S(n/2), \qquad S(4) = 14/3. $$
You take it from here.


Creating a one-to-one mapping between a N-length list and M workers? I have a list of length N, and I have M workers.  I want each of my workers to independently select a contiguous section of the list, with the property that every element of my list is selected by exactly one worker.

Using the SQL notion of offset and limit, I have an approximation:

offset = (worker_number / total_workers * list_length).to_i
limit = list_length / total_workers + 1

The problem is that, for some values of N and M, this results in overlaps, where some elements are processed multiple times.

Is there a general solution that ensures the one-to-one correspondence between elements and workers, yet allows each worker to independently compute their offset and limit?

Sure.  Give the $i$th worker the range of items at indices from $\lfloor Ni/M \rfloor$ to $\lfloor N(i+1)/M \rfloor - 1$.

Here I assume indices range from $0$ to $N-1$, and workers are indexed by $i$, where $i$ ranges from $0$ to $M-1$.  Also, the notation $\lfloor x \rfloor$ represents the result of rounding $x$ down to the nearest integer.

This ensures that there are no overlaps, and the list is split evenly among the workers (as evenly as possible: each worker receives either $\lfloor N/M \rfloor$ items or $\lfloor N/M \rfloor + 1$ items).


Placing a point between two nearest ones I have a closed 2D shape expressed as a list of points, like that:

[
  {0,  5}, <-- {x, y}
  {10, 5},
  {15, 6},
  ...
]

The user has a canvas: each time he clicks on that canvas, a point will be appended to the list, and he will see the updated shape on screen.

How can insert the point between two nearest points instead of appending it to the list?

Let's say I have this shape:

All points got inserted counter-clockwise, starting from the first point to the left of the red one (meaning that the red one will be the last one):

Suppose that the user wants to place a point on the yellow area:

Right now the algorithm simply appends the new point to the list of existing points, so the new point will be inserted after point number 5, resulting in this shape:

Clearly I don't want this behaviour. I'd like the point to be inserted between points 3 and 4 instead, so that the result will be like that:

I came up with a possible solution.

Find distances between tuples and subtract them. The point's nearest tuple is the one with the minimum distances subtraction

Example:

d1 = abs(pink - blue)
d2 = abs(blue - green)
d3 = abs(green - red)
d4 = abs(red - yellow)
d5 = abs(yellow - pink)

Here, d2 will be the minimum, hence the point will be inserted between 3 and 4.

This approach however is buggy: if point 5 is a bit closer to the line between point 3 and 4, d3 will be the minimum, so the point would be inserted between points 4 and 5, which would be wrong.

Calculating areas of triangles instead of distances has the same issue.

I'm thinking there should be a way to take the segment distance into account. I mean, I would need to not only calculate distances between points, but also the new point's distance from the given segment. That way, I could tell that segment 3-4 is the nearest one, so I'll insert the point between 3 and 4.

So, what is an effective way to to handle this?

Don't add the point between the closest pair of points; add it between the endpoints of the closest edge.


How to group thousand of data points for each user I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each data point can have 3 states: true, false, unknown.
What could I do to group these data points so that they don't take too much space?
My initial plan is to basically cluster them. Something like:

unknown: [1-23, 25, 27]
true: [24, 26]
false: [28-30]

Where m-n represents number from m to n.

The solution was to use run-length encoding.
Let's say that I have:

The first 10 questions true
The next 24 false
The next 34 unknown

I'd transform it in 10T24F34U.
You can find more info on Wikipedia's Run-length encoding as provided by D.W. in the comments.
The main reason for this solution is to send data via an API. I'm not sure if I'm going to use this algorithm or just rely on the typical compression when sending data to a browser. So that is another possible solution.


What would you get if you add parameters to context free grammars? I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python grammar in ANTLR-like format:

// on top-level the statements have empty indent
program
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent)
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

My question: Does this kind of grammars (CFG with parameters) have a name?

It looks that it wouldn't be hard to write a recursive descent parser for this grammar (parameters should be basically parsers). What could be the difficulties with this approach?

Does addition of parameters raise the supported language class above context-free?

Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative grammar for a part of English", co-written with LGLT Meertens. In 1970, he produced a formalism of the concept; a useful overview is available in his 1971 paper "Affix Grammars for Programming Languages", a version of which I found on Citeseer.

In that paper, Koster compares his formalism (and another similar one) with Van Wijngaarden two-level grammars, and finds them to be very similar.

Dick Grune's invaluable annotated bibliography of parsing techniques includes a large number of other useful references for affix grammars and other non-Chomskyian formalisms. (See section 18.2.6 of the bibliography, although there are useful papers in other sections.) Grune covers affix grammars briefly in §15.3.2 of the second edition of Parsing Techniques: A Practical Guide (and even more briefly in the first edition, available online) mentioning the fact that it is easy to adapt top-down (and other) parsing techniques.

Unless the domain of parameters is finite, in which case they can be removed by statically generating all possible productions resulting in a CFG, the class of affix grammars is certainly a strict superset of the set of context-free grammars. (An affix grammar for $a^n b^n c^n$ can be found in Dick Grune's Parsing Techniques reference above.)

Koster, who was also an editor of the Algol 68 report, was the original developer of the Compiler Description Language (CDL), based on his ideas about affix grammars. This toolkit and its later derivatives were used in production for many years. This page, which I found with a Google search and whose permanence I cannot guarantee, has links to the manual and download site for CDL3.


Summed-area table for circular range queries A summed-area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid [Wikipedia]. Is there any algorithm for quickly and efficiently generating the sum of values in a circular subset of a grid?

The best way is to approximate circle with hexagon or octagon as desciribed in expired patent US 6507676 B1. Further improvement is to add rectangles to octagon to get more circular shape or like harold proposed cover the whole circle with rectangles. Unfortunately this defies the core efficiency of summed area table.
The naive way would be to use e.g. Bresenham circle algorithm and sum consecutive rectangles, which by the way is still big speed up, proportional to circle size. The best way is to inscribe square and add rectangles to get finer results. This is illustrated here.

Picture taken from http://yehar.com/

There is no possibility of creating SAT especially for circle even leaving jagged border, simple proof is from impossibility of tesselating space by circles.


Is there a tool that can check whether m |= p holds, where m and p are both ltl formula To the best of my understanding, m |= p asks whether the ltl formula p satisfies the ltl formula m. In other words, m -> p is a tautology. Here are some example of where m |= p hold:
Xp |= Fp

q  |= p U q

Gq |= Fq

Of course, trying to visualise all this in you head and trying to work out if m |= p holds can get very time consuming, especially if m and p are very long. So, I was wondering there is some tool/software/platform that can compute m |= p.

Yes, you can use an LTL-to-Büchi-automaton translator for this.
Let's assume that you want to check if $\psi \rightarrow \psi'$ is a valid LTL formula, i.e., every word satisfying the LTL property $\psi$ also satisfies the LTL property $\psi'$. This case is equivalent to finding out if $\psi \wedge \neg \psi'$ is satisfiable. Your $\psi \models \psi'$ notation is another way of writing this, but I would avoid it since the $\models$ relation is often defined differently in current research papers on the topic.
If we translate $\psi \wedge \neg \psi'$ to a Büchi automaton, we can easily check if its language is empty. In fact, optimizing LTL-to-Büchi translators remove states with an empty language, and hence you only need to check if the resulting automaton has no accepting state.
On example LTL-to-Büchi translator is ltl3ba. For instance, if you want to check if $\mathsf{F G }\,a$ implies $\mathsf{G F}\,a$, you can do that as follows:
./ltl3ba -f "(F G a) && !(G F a)"

Here, "-f" stands for "translate this formula that is given as a parameter".
The result is given in SPIN never claim form:
never {    /* (F G a) && !(G F a) */
T0_init:
    false;
}

There is no state ending with "_accept" in the name, which means in the SPIN never claim notation that there is no accepting state. So $(\mathsf{F G }\,a) \wedge \neg (\mathsf{G F}\,a)$ is not satisfiable.
There is also at least one LTL-to-Büchi translator with a web interface, namely the one from the SPOT framework.