League and Divisions problem (np-hard) There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team must belong to exactly one Division. There are min and max - minimal and maximal amount of teams per division. Every team travels once to every other team inside one division. The target is to divide the league into divisions in a way, that the total traveling distance for the whole league is minimized.

Input:
n - amount of teams
min - minimum teams per division
max - maximum teams per division
teams - array of teams (name,x,y)

Input example:
n = 10
min = 2
max = 3
teams = [{a,1,1},{b,2,1},{c,5,3},{d,9,8},{e,6,8},{f,5,1},{g,1,7},{h,6,6}{i,7,2},{j,2,7}]

Output:
League

Output example:
League = [[a,b,c],[d,e],[f,g,h],[i,j]]
One sub array stands for one division. It means that the teams a,b and c belong to one division and each of them will visit every other team from this division.
This is not the optimal solution

This is what an output of a real-world case could look like

I am struggling with selecting an algorithm for this issue. It is not a traveling salesman since we are not interested in simply visiting all of the locations. Neither the clustering approach is applicable since we need to keep the min
and max in mind and it's not what clustering does. What kind of algorithms can be used to tackle down this problem?

Balanced k-means clustering would probably work reasonably well here.  Unfortunately the true cost structure can't be modelled with this (or any clustering algorithm that I know of); you would need to instead use some increasing function of the distance from the cluster centroid (this could be just the distance itself, or e.g. a small positive power).  Balanced k-means will then try to cluster the teams into divisions in such a way that the sum of these per-team costs is minimised, while enforcing a hard upper bound (your max) on the number of teams in a division.  The chosen number k of divisions, as well as these upper bounds, implies a lower bound on the division size, though this won't necessarily agree with your desired min.  Hopefully, playing with the parameters a bit could get you close.

The idea is basically the same as regular k-means clustering, except that in the assignment phase, instead of assigning each point (team) to its nearest cluster (division), you solve an instance of the Assignment Problem in which each team is represented as a worker and each division is represented as max job slots: this enforces that each division receives at most max teams.  The problem can be solved with e.g. the Hungarian algorithm.

There's a paper here, but it seems to be behind a paywall unfortunately: https://link.springer.com/chapter/10.1007/978-3-662-44415-3_4


A linear temporal property that represents this (basic) execution? A question gives me a set of atomic propositions AP = {a, b, c}and asks me to give a linear temporal property that represents all executions over AP such that:

(1) a and b never happen at the same time

OR

(2) a is preceded by c

Can anyone give me some pointers on how to answer this question (possibly with a model solution)? So far all I have done is split the property into two parts such that the property $P$ is the union of $P_1$ and $P_2$ but I don't know how to formulate my answer.

(This question is from a past exam paper).

Any help is highly appreciated.

Since you are asked to formulate these properties in LTL, you might want to think of them as properties given with predicates over infinite sequences of states (or events where each event changes the state); in your case, you know that at each state some of the three propositions, {a, b, c} might be true.

When we talk about LTL, it's good to summarize what does the formalism support to figure out whether the given property can be formulated in it. Note that previously mentioned propositions are often formulated as state formulas, which might hold in a particular state. So, LTL supports: state formulas (propositions that might hold in particular state), (standard) Boolean operators (like logical or ||), and path quantifiers (like globally G and next X, which produce other state formulas), which effectively allow state formulas to describe sequences of states.

I will describe one potential solution in the "extended" LTL, which includes additional operators besides the fundamental ones. (These are easily expressible using only the basic operators, next and until; more details can be found in a more thorough treatment of LTL).

  So far all I have done is split the property into two parts such that the property P is the union of P1 and P2 but I don't know how to formulate my answer.

Indeed, at the top level, as you recognized, you should have union, which effectively translates to || of P1 and P2:

P1 || P2

Going back to P1 ((1) a and b never happen at the same time), which states that something should never happen, it's good to think whether such temporal quantification can be translated to some of the offered quantifiers in LTL. This is indeed possible, and "never some property P" can be expressed in terms of combining a Boolean operator and a quantifier, in the following way:

   G( not P ) (always, P is not true)

thus, P1 can be expressed by using given propositions as:

   G( not (a && b) ) (always, it is not true that both a and b hold)

On the other hand, as Shaull pointed out, the second property is a bit trickier. Although, such a requirement might have been written more precisely (to avoid ambiguity), we can interpret it to mean that a and c should happen, at some point, such that c happened earlier than a.

Now, when we identified earlier, we might think of another LTL quantifier that semantically matches the notion of ordering states (or events). That quantifier is:

   X (quantifier for next, i.e. formula that will hold in the next state)

Thus (under the interpretation that both propositions must be true at some point), we want to say that eventually, c happens, while at a point after that, eventually a happens as well:

   F( c && X(F a))

arriving at the final solution:

   P1 || P2 = (G( not (a && b) )) || F( c && X(F a))

which checks that either of the given properties are satisfied in the execution, as you originally suggested.

After you have an idea of how the formula should look like to makes sense (semantically, with respect to the property you want to model), you always want to check whether the formula is well formed, i.e. whether the formula is syntactically correct. (More details can be found in one of the more thorough treatments of LTL.)


What is the time complexity of subset testing? Consider the following problem:

  Let $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_m\}$ be
  two finite sets over $\mathbb{N}$. The sequences $a_1,...,a_n$ and $b_1,...,b_m$ do not have to be sorted.
  Given as inputs the strings $a_1,...,a_n$ and $b_1,...,b_m$, determine if $A \subseteq B$.

What is the time complexity of this problem?

Since you talk about sets I assume that there are no duplicates.

You can  assume $n \le m$ otherwise you can answer "no" in time $O(1)$.
You can further assume $\max_{a \in A} a \le \max_{b \in B} b$, otherwise the answer is again "no", and can be found in time $O(\min\{m, U\})$, where $U = \max_{a \in A} a$.

Your problem can be solved in $O(\min\{m \log n, U\})$ worst-case time. To do so use the best of the following two strategies:

Sort $A$. Keep a counter $x$ of how many elements from $B$ have been found in $A$. Initially $x=0$. For each element of $b \in B$ (in arbitrary order), determine whether $b \in A$ using a binary search. If $b \in A$ increment $x$. After all elements of $B$ have been examined, return true if and only if $x=n$.
Keep an array $X[0, \dots, U]$ of $U+1$ boolean elements. Initially all the elements of $X$ are false. For each element $b \in B$, check if $b \le U$ and if that is the case set $X[b]$ to true. Iterate over the elements $a \in A$ and check whether $X[a]$ is true for all of them. If this is the case return true, otherwise return false.

Notice that $\Omega(m \log n)$ is a lower bound on the worst-case time complexity needed to solve your problem (as a function of $m$ and $n$) in the algebraic computation tree model. See Corollary 3 on page 147 (155 of the pdf file) here.

You can also solve your problem in $O(m)$ expected time by using a hashset $H$:

Insert all the elements of $B$ into $H$. This takes $O(1)$ expected time per insert operation, i.e., $O(m)$ time in total.
For each element $a \in A$, check whether $a \in H$. This takes $O(1)$ expected time per check.


Consistency and completeness imply soundness? I understand that soundness implies consistency. Also, I understand that consistency alone does not imply soundness. But shouldn't consistency + completeness imply soundness? Scott Aaronson in his blog-post hints otherwise. What am I exactly missing?

Update: By completeness I assume that all sentences true under all interpretations are deducible. By soundness I assume that all deduced sentences are true under all interpretations. Finally, by consistency I assume that no sentence $P$ and its negation $\neg P$ can be deduced.

In the Scott Aaronson blog post you linked, (syntactic) consistency means that there is no sentence $P$  such that both $P$ and its negation can be deduced from the axioms of the theory.  (Syntactic) completeness means that either $P$ or $\neg P$ are deducible from the axioms.  And soundness means that if $P$ is deducible from the axioms then it is valid under all possible models/interpretations of the axioms.

Consistency + completeness does not imply soundness because you could have a set of axioms and a theorem $P$ where $P$ is deducible from the axioms, $\neg P$ is not deducible from the axioms but there is some model of the axioms under which $P$ is false and $\neg P$ is true.

Aaronson gives an example in his post:

  If I believe that there’s a giant purple boogeyman on the moon, then presumably my
  belief is unsound, but it might be perfectly consistent with my various other beliefs
  about boogeymen.

"There's a giant purple boogeyman on the moon" is (perhaps) syntactically consistent with your axioms because you do not believe that "there isn't a giant purple boogeyman on the moon."  Your axioms may be syntactically complete because they allow you to deduce at least one of the sentences "there's a giant purple boogeyman on the moon" or "there isn't a giant purple boogeyman on the moon."  But in fact it is not true that "there's a giant purple boogeyman on the moon," so your deduction is unsound even though your axioms and deductive system are both consistent and complete.

The hardest concept in the above is probably soundness.  Soundness relates the syntactic structure of your sentences and deduction rules to the interpretations (or models or semantics) of those sentences.  A model of a language is a set, along with some relations and functions on the members of that set.  For example, Gödel's language was the Peano axioms and the underlying model of the Peano axioms is the set of integers with (at least) an equality relation and a successor function.  The Peano axioms are (I think) sound: if you can prove something with the Peano axioms then it is true of the natural numbers.  But Gödel proved that the Peano axioms are not complete: there are sentences in the language of the Peano axioms that are in fact true of the natural numbers, but which are not derivable from the Peano axioms.


Word classification algorithms I am looking for algorithms to classify words in a paragraph of text. I am particularly interested in a classification to determine if a certain word is noun, verb, etc., but also looking for any kind of word-classification algorithms. I am given a smaller input (e.g. 200 words) so there is no many options for machine learning but I would really appreciate algorithms involving machine learning.

This is a standard problem in Natural Language Processing (NLP).

Classifying whether each word is a noun, verb, etc., is known as "part-of-speech tagging".  Searching on that term should turn up a lot of information about how to do that.

If you want to tag the words in some other way, you might be able to use other tagging algorithms.  They generally use some sort of machine learning approach and will probably require a large training set (200 words won't be enough).


Why is a set of attributes X not a key if X → Y holds but there exists a strict subset V of X where V → Y? Apologies if I butchered the question, I wasn't quite sure how to word it.

In the Ramakrishnan text (2nd edition) on page 423 (in the section on functional dependencies) this statement is made:

  If $X \rightarrow Y$ holds, where [$X$ is the set of key attributes and] $Y$ is the set of all attributes, and there is some subset $V$ of $X$ such that $V \rightarrow Y$ holds, then $X$ is a superkey; if $V$ is a strict subset of $X$, then $X$ is not a key.

I got the basic idea here (that if $X$ contains some $V$ where $V \rightarrow Y$ then $X$ is a key that contains a smaller key), but I must be misunderstanding something on the second case. Why isn't $X$ a key in the second case? It would seem that a strict subset would be a stronger case for being a "key within a key" which is how I understand a superkey to be structured.

Generally, you want to define a key as a superkey that is minimal with respect to inclusion; if $X$ is a superkey, $V$ is a superkey and $V \subset X$, then $X$ can't be minimal.

The intuitive idea behind the definition is that we don't want keys to contain "useless" attributes. For instance, imagine a table that contains a list of people, each of which has a unique number $K$, a name $N$ and a surname $S$. $K$ would be a key to that table, because it functionally determines all other attributes in the relation. The pair of attributes $\{K, S\}$ also functionally determines the entire relation, but attribute $S$ is "useless" in that respect, because it is itself determined by $K$.


Construction of a Deterministic Tree Automaton (DTA) Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$.

We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t are from a word in $L$}\}$ as a tree language.

The task is to construct a DTA for $T_L$.

A DTA A over $\Sigma = \Sigma_0  \cup \cdots \cup \Sigma_m  $ is a four tuple with $A= (Q,\Sigma, \delta, F)$ where Q is a finite state set, F final state set, and $\delta : \bigcup _{i=0}^m(Q^i \times \Sigma_i)\rightarrow Q$ and $Q^0 \times \Sigma_0 = \Sigma_0$.

My idea was to set $\Sigma _0 \subseteq L \subseteq \Sigma^*$. But how can the transition function check whether it is a word in L?

Your model is a bottom-up tree automaton. Let $P$ be the set of states of the finite state automaton for regular $L$. Now a state of the tree  automaton at a vertex $v$ of the tree contains all $P \times  P$ pairs $(p,q)$ such that there is a path from $p$ to $q$ on the string specified by the leaves under $v$. This can be deterministically evaluated in a bottom-up fashion.

More precisely, with every vertex $v$ we associate a binary relation $R(v)$ over $P$, thus $R(v) \subseteq P\times P$. Thus $(p,q)\in R(v)$ iff there is a path from $p$ to $q$ on the leaves under $v$.

For a leaf $v$ labelled $a\in \Sigma$ this means that $R(v) = \{(p,q)\mid (p,a,q) \in \delta\}$, where $\delta$ is the transition relation of the automaton for $L$.

If $u$ is a binary vertex (labelled by $*$) with children $v,w$, then the relation $R(u)$ is the compostition of $R(v)$ and $R(w)$.

We accept at the root $r$ if $R(r)$ contains an accepting pair $(p,q)$ where $p$ is the initial state and $q$ is final.


Minimize number of circles to cover set of points I'd like to minimize the number of circles $C$ to cover a set of points $P$ in 2D.

There is no fixed radius however each circle must contain exactly $N$ points. The circles may overlap. A point may be covered by multiple circles. All coordinates are floats.

Problem size: $|P| \leq 1000$, $5 < N < 15$

My current approach: I limited the possible center points of the circles to the set of points and just take the center point which covers the most uncovered points as long as there are uncovered points.

Good example with $N=3, |P|=9, |C|=3$ (optimal because $|C| = \lceil|P|/N\rceil$):

Non-optimal but valid example with $N=3, |P|=9, |C|=4$ (using my current approach, numbers indicates step):

I'm aware the problem might be a bit vague. Any hint on how to approach the problem is appreciated. I'm not necessarily interested in an optimal solution. An approximate/heuristic algorithm is totally fine.

Set Cover

If you restrict the possible center points of the circles to be the set of points, then this is an instance of set cover where the universe has $|P| \le 1000$ elements and where each set contains $N$ elements.  While set cover is NP-hard, there are algorithms for set cover that are faster than exhaustive search.

For these parameters, I expect it should be possible to find an optimal or near-optimal solution to the associated set cover problem, using standard algorithms for set cover.  I would recommend starting with the integer linear programming formulation and using a standard ILP solver (Gurobi, CPLEX) to find an optimal or near-optimal solution to the set cover problem.  That might be efficient enough for your purposes.

Your approach is known as the greedy algorithm for set cover.  It is known to give a $\lg N$-factor approximation, i.e., a covering that uses no more than $\lg N$ times as many circles as the optimal covering.  Thus, the ILP formulation may yield better solutions.  There are also heuristics for improving the greedy algorithm, e.g., BubbleSearch, which makes small random tweaks to the order suggested by the greedy strategy, repeats that some number of times, and takes the best solution found so far.  You could try them and compare them to how well the ILP formulation works, if you wish.

Geometric Set Cover

You could also look at algorithms for geometric set cover; some of those techniques may be useful here.  In particular, there are approximation algorithms and fast heuristics for geometric set cover, and you could try seeing if they are useful in your particular setting.  They use the extra geometric structure provided by the problem: this is not a totally arbitrary instance of set cover, but there is some additional structure.

Arbitrary Center Points

The above algorithms have one critical limitation: they only consider circles that are centered at some point in $P$.  There's no reason to expect the optimal solution to your problem to have this property.  Thus, they might fail to find the optimal solution to your original problem.

Fortunately, it's possible to fix this limitation.  It's possible to come up with a not-too-large set $U$ of candidate circles, such that the optimal solution is obtained by taking a subset of circles from $U$; then we can apply set-cover techniques to pick a minimal-size subset of $U$ that covers all of $P$.  In particular, we will use the following geometric facts:

Lemma 1. Let $C_0$ be any circle that covers exactly $N$ points.  Let $S \subset P$ be the set of $N$ points covered by $C_0$.  Then there exists a circle $C$ that (i) covers exactly $S$ and no other points and either (ii.1) has at least three points of $S$ along its circumference or (ii.2) has two points of $S$ along its circumference and is centered at their midpoint.

Proof. Consider any circle that covers exactly $S$ (and nothing more).  Pick the point $p \in S$ that is closest to the boundary of this circle.  Reduce the radius of the circle until $p$ is on the boundary.   Now if this circle doesn't have two points of $S$ along its circumference yet, move the center of the circle towards $p$, reducing the radius at the same rate, until the first time some other point is on the boundary -- call it $q$.  At this point we have a circle $C$ that covers all of $S$, contains $p,q$ on its boundary, and doesn't cover any points other than $S$.  Now let $m$ be the midpoint between $p,q$, and let $L$ be the line that is perpendicular to $pq$ and that intersects $m$.  If $C$ is centered at $m$, we're done.  Otherwise, $C$'s center is somewhere on $L$.  Move the center of $C$ along $L$ towards $m$, decreasing its radius at the same time so that $p,q$ remain on its circumference, until either the center reaches $m$ or the circumference hits a third point.  Either way, we are done.  $\Box$

Lemma 2. Given any three non-colinear points $p,q,r$, there is a unique circle that is tangent to all three (i.e., has all three on its circumference).  This circle can be efficiently computed.

Proof. Use the same procedure described in the proof of Lemma 1, but now without worrying about how many points are covered by the circle. $\Box$

Lemma 3. Given any two points $p,q$, there is a unique circle centered at their midpoint and tangent to both $p,q$.

Proof. Obvious.  $\Box$

With these lemmas, we can now suggest an algorithm:

For each set of three points $p,q,r \in P$, find the circle that is tangent to $p,q,r$.  Identify the points covered by this circle (e.g., using a quadtree).  If this circle covers exactly $N$ points, add it to $U$.
For each set of two points $p,q \in P$, find the circle centered at their midpoint and tangent to both.  If this circle covers exactly $N$ points, add it to $U$.

Lemma 1 now ensures that we need only consider circles in $U$; any set of $N$ points that can be exactly covered by some circle, can be covered by some circle in $U$.  Therefore, there exists an optimal solution to the original problem that uses only circles in $U$.  As an optimization, if there are two circles in $U$ that cover the same set of points, you can keep one of them and discard the other.

Therefore, the problem becomes:

Given a set $P$ of points and a set $U$ of circles (each covering exactly $N$ points from $P$), find the smallest subset of $U$ that covers all of $P$.

This is a finite set cover problem, and the solution to this set-cover problem is guaranteed to be optimal.  We obtain a set-cover instance with a universe of size $|P| \le 1000$  and with $|U|$ sets, each of size $N$.  This set cover problem can then be solved using standard algorithms for set cover, e.g., using an ILP solver.  We'll have $|U| \le |P|^3/6$ at worst, though in practice I expect $|U|$ will typically be much smaller (closer to $|P|^2$ or so).  The running time to create the set-cover instance will be at most $O(|P|^3)$; then we have to solve the set-cover instance.  I anticipate that, for these parameters, it might be possible to obtain an optimal or very-nearly-optimal solution to the original problem using off-the-shelf ILP solvers.

My thanks to @j_random_hacker for substantial assistance with this answer.


Calculate ϴ dependent on n for an algorithm with constant c I want to calculate ϴ dependent on n for this algorithm:

for (k = n; k < c; k++){
    j = 1;
    while(j < n){
        j++;
    }

n is the parameter. c is a constant.

I calculated the amount of operations to (c-n)*(n-1). But now I don't now how to deal with c.

I calculated the amount of operations to (c-n)*(n-1)

Not quite. If $n > c$ then the cost is not negative: it should be $(n-1) \max(c-n, 0) = \Theta(n) \max(c-n, 0)$. When $n$ is large (and in particular when $n > c$) what does this reduce to?


Determining Language from Context Free Grammar I am trying to understand how to write the language given the predicates of the context free grammar. As an example, I have the following grammar:

$S \to 0B \mid 1A$

$A \to 0 \mid 0S \mid 1AA$

$B \to 1 \mid 1S \mid 0BB$

What this says to me is that the first symbol can be either a 0 or 1, and the  next could be 0 or 1 or 1 or 0, and you continue down the parse tree from there.
How does one determine what the language of the grammar is? I having trouble putting the patterns of symbols into a language definition.

Structural induction would prove the following:

All words generated from $S$ have the same number of 0s and 1s.
All words generated from $A$ have an excess of one 0.
All words generated from $B$ have an excess of one 1.

Presumably the reverse is also true, but I'll leave such pondering for you.


Must a complete subgraph be induced? If we had some $K_n$ subgraph where $K_n \subseteq G$, must the complete subgraph $K_n$ be an induced subgraph from $G$? In other words, can we create a situation where we remove vertices from a simple graph $G$ to obtain some complete subgraph where the subgraph was not complete when it was a part of $G$?

Every complete subgraph $K_n$ contained in a graph $G$ can be considered as an induced subgraph of $G$. Note that, by definition, an induced subgraph is formed from a subset of the vertices of the original graph along with all of the edges connecting pairs of vertices in that subset.


DFA for a strings whose every subsequence of length five has at least two zeroes I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in it (which also means every sequence of length <5 is 'good'). I need to find a DFA which generates this language.

I can't say I tried everything, but each time I encountered the same problem, that is it always generated a subsequence of the form 11111... (I tried incorporating each subsequence of length 5 with two 0's in my DFA so that the last element returned to the beginning of the automaton, but this resulted in accepting 'bad' subsequences - for instance 00111 and 11100 were 'good', but 0011111100 wasn't).

Is there any way to do it?

There is a standard technique for problems like this, where the language can be specified in the form

  All words over some alphabet $\Sigma$ where [some condition] is satisfied by all contiguous substrings of a fixed length, $k$.

The key idea here is to define a collection of states $s_i$ where $0\le i \le |\Sigma|^k$. Basically, you are using the states to "remember" the most recently-seen $k$ characters. These states will be part of the finite automaton we'll build for our language.

In what follows, I'll use a simpler language than yours, so that the FA will be sufficiently small to fit here and still be readable. Let
$$
L=\{w\in\{0, 1\}^*\mid \text{every length-3 substring of $w$ contains at least 2 zeros}\}
$$
We'll define states $s_0, s_1, \dotsc, s_7$ to represent the three most recently-seen characters. It's convenient to do this representation in lexicographic order, so $s_0=\mathtt{000}$, $s_1=\mathtt{001}$, $s_2=\mathtt{010}$, $s_3=\mathtt{011}$, $s_4=\mathtt{100}$, $s_5=\mathtt{101}$, $s_6=\mathtt{110}$, and $s_7=\mathtt{111}$. In other words, $s_N$ will correspond to the 3-bit binary representation of $N$.

Now we'll add some more states to get from the start state to the $s$'s. All it takes is to construct a complete tree (binary in this example) having the $s$ states as leaves, like this:

All of the states in the FA above will be accepting states, except for the darkened ones. The $p_i$ states are all accepting, since we haven't yet seen a length-3 string, so we haven't violated the condition that defines the language $L$ and only the patterns $\mathtt{011}, \mathtt{101}$, $\mathtt{110}$, and $\mathtt{111}$ violate the condition of the language. These correspond to states $s_3, s_5, s_6, s_7$. Once we've entered one of these states, we reject the input word, so we might as well merge these into a single "dead" state, $d$, from which there will be no exit.

We're almost done; all that remains is to fill in the transitions among the $s_i$. Because of the way we chose the representations of the states, that's an easy task. If we're in state $s_i$, having just seen characters $b_1b_2b_3$, on input $b$ we'll pass to the state $s_j$, corresponding to the new pattern $b_2b_3b$. If you think about it for a moment, you'll see that $\delta(s_i, 0) = s_j$ where $j\equiv 2i\pmod8$ and $\delta(s_i, 1) = s_j$ where $j\equiv 2i+1\pmod8$. Thus, we'll have the following $s$ transitions (recall that we merged states $s_3, s_5, s_6, s_7$ into a single dead state, $d$):
$$\begin{array}{c|cc}
    &  0  &  1 \\ \hline
s_0 & s_0 & s_1 \\
s_1 & s_2 &  d \\
s_2 & s_4 &  d \\
s_4 & s_0 & s_1 \\
 d  &  d  &  d
\end{array}$$

completing the construction. The nice feature of this technique is that it's almost completely mechanical: the only hard part is making the $s$ transitions. The downside is that it produces a pretty big FA. Even in this simple example, we wound up with a 12-state FA, and if we had needed to look at the five most recent characters, we'd have a FA with 31 states just for the $p$s. In fact, if we apply the standard technique for DFA minimization, we would find that the minimal-state DFA for this example language would require only 7 states, with 6 of them being final.


Time complexity of Sieve of Eratosthenes Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?

Write a sum for the number of operations of removing multiples of primes. How many operations to remove all multiples of 103 for example from an array of n bits? How many operations to remove all multiples of a prime number p? So you get a sum.

Then you need to know what the sum 1/1 + 1/2 + 1/3 + ... + 1/n is (roughly) and importantly why. You see that by adding 1/1 + (1/2 + 1/3) + (1/4 + 1/5 + 1/6 + 1/7) + (1/8 + 1/9 ... + 1/15) + ... and there is an obvious upper bound.

Now instead of adding 1/k for $2^m ≤ k < 2^{m+1}$ you add 1/k for only the primes k with $2^m ≤ k < 2^{m+1}$. How many are there? What sum do you get now? And then you have a sum that looks almost exactly like the one you started with and gives you the result.


Could I apply the master theorem if my $N/b$ is $\varphi(N)$? Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise}
\end{cases}$$

where $\varphi(N)$ is Euler's totient function.

Can I somehow express $\varphi(N)$ as $N/b$, so I can apply the Master Theorem and resolve this recurrence?

You may assume $\varphi(N) = (p-1)(q-1)$, if it's easier that way.  You may also assume, if it helps, that $p$, $q$ are safe primes, that is, $p = 2p' + 1$ and $q = 2q' + 1$.  (Assume anything that makes the problem easier.  For instance, you can replace the function $\lg^3(\varphi(N))$ with any other that makes the problem easier, but do so only as a last resort.)

You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem.

First, show that $\phi(\phi(n)) < n/2$. This can be done as such:

Let $n = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $n$ ($p_i$ prime, $k_i>0$)

Suppose $n$ is even. Then $\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$ Thus $\phi(\phi(n)) < n/2$.
Suppose $n$ is odd and $n > 1$. Then $\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $n$. By the previous result $\phi(\phi(n)) < n/2$.

So we get the desired result.

Now suppose $n\geq2$. You can write:
$$T(n) = T(\phi(n))+\log(\phi(n))^3 = T(\phi(\phi(n)))+\log(\phi(\phi(n)))^3 + \log(\phi(n))^3.$$
$$T(n) \leq T(n/2) + 2\log(n)^3.$$

Now you can apply the master theorem here to get:
$$T(n) = O(log(n)^4).$$


Counting involving equivalence classes and languages Let $\Sigma$ be the alphabet $\{a, b, c, d\}$ and let $R$ be the following relation on $\Sigma^*$: $R(x, y)$ is true if every letter in string $x$ also occurs in $y$, and every letter in string $y$ also occurs in $x$.  (For example, $R(abba, babbb)$ is true and $R(abcb, cbbcb)$ is false.)  How many (non-empty) sets are in the partition of $\Sigma^*$ corresponding to $R$?  (That is, how many equivalence classes does R have?)

Any help will help.

If you look at two strings in your example $abba$ and $babbb$, they are composed of exactly the symbols from the set $\{a,b\}$, where each symbol appears at least once. So you can reduce  the counting problem in your question to counting the number of subsets of $\{a,b,c,d\}$. Note that one equivalence class would be $\{\lambda\}$ where $\lambda$ denotes the empty string. How many subsets does $\{a,b,c,d\}$ have?


Find the shortest path that goes through an even number of red edges I'm looking for an algorithm for the problem:

"Given an undirected graph with positive weights on its edges and some of the edges are red and some are blue. Describe an algorithm that finds the shortest (lightest) path which includes an even number of red edges, that goes from S to any vertex v."

The solution I thought about was, why not take the original Graph G(V,E) and create (I'm not quite sure if I can say "given" though I think it is) a sub graph which will include only the red edges, let's say Red(V',E'), intersect those two, so now I will have a new graph say G' which includes only the red edges.

And on that graph I will use dijkstra algorithm in order to find the shortest path.

The problem is it can ofc make some edges un-reachable so it will return there's no such path, while there might be a path if added some blue edges. I'm not quite sure how to go around it in order to get the perfect solution.

Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any path which starts and ends in $A$ must use an even number of red edges (after using a red edge to get to $B$, it has to use another red edge to get back to $A$). So just run any shortest-paths algorithm on this new "doubled" graph and keep only the shortest paths that both start and end in $A$.

More formally, let $v_A$ and $v_B$ be the two copies of $v$ that appear in $A$ and $B$, respectively. For each original edge $(u,v)$,

if $(u,v)$ is blue, the new graph will have edges $(u_A, v_A)$ and $(u_B, v_B)$.
if $(u,v)$ is red, the new graph will have edges $(u_A, v_B)$ and $(u_B, v_A)$.

Note that this transformation only works because the edge weights are positive. Otherwise you could do funky things like traverse a negative edge twice (once within $A$ and once within $B$) to achieve lighter paths in the doubled graph.


Choosing correct action in bottom up parsing Using grammar:

$
S \to aABe \\
A \to bcA \mid c \\
B \to b
$

to bottom parse a string $abcccde$, the course of action would be:
$
\begin{array}{c|c|c|c}
\hline
Step & Stack    & Input    & Action               \\ \hline
1    & \epsilon & abccde   & Shift                \\
2    & a        & bccde    & Shift                \\
3    & ab       & ccde     & Shift                \\
4    & abc      & cde      & Shift                \\
5    & abcc     & de       & Reduce \, by \, A \to c    \\
6    & abcA     & de       & Reduce \, by \, A \to bcA  \\
7    & aA       & de       & Shift                \\
8    & aAd      & e        & Reduce \, by \, B \to d    \\
9    & aAB      & e        & Shift                \\
10   & aABe     & \epsilon & Reduce \, by \, S \to aABe \\
11   & S        & \epsilon & Done
\end{array}
$

My questions are:

At step 4, why do we choose to Shift rather than to reduce $ A \to c$.
How would a parser decide which is correct to choose?

Because it will allow the string to be parsed. I know that is not a very satisfactory answer, but it really is the only answer. It is similar to asking why a particular step in a proof was chosen, and not some other step: because whoever wrote the proof (or, in this case, the derivation) somehow figured out how to do it.
That depends on the algorithm used by the parser. It might try one action, see if it works, and if not backtrack and try the next possibility. It might try both actions in parallel, reporting only the succesful one(s) at the end. It might have an analysis of the grammar that lets it know what to do in particular circumstances. You will probably see various different techniques as your course continues.


Shortest Minimax Path via Floyd-Warshall I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.)

Floyd-Warshall algorithm contains the following loop to enhance the distance (ds) and the next vertex (ns) matrices at each iteration.

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ds[i][k] != inf && ds[k][j] != inf) {
                final int d = ds[i][k] + ds[k][j];
                if (d < ds[i][j]) {
                    ds[i][j] = d;
                    ns[i][j] = k;
                }
            }

I replaced ds with two new matrices: ws (weights) and ls (lengths). Further, updated the iteration step as follows:

for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ws[i][k] != inf && ws[k][j] != inf) {
                final int w = Math.max(ws[i][k], ws[k][j]);
                final int l = ls[i][k] + ls[k][j];
                if (w < ws[i][j] || (w == ws[i][j] && l < ls[i][j])) {
                    ws[i][j] = w;
                    ls[i][j] = l;
                    ns[i][j] = k;
                }
            }

However, the modified algorithm finds paths with loops, that is, paths such as 1-3-2-3-4. While the maximum edge weight of the paths 1-3-2-3-4 and 1-3-4 are identical, the latter has a shorter path length and supposed to be returned by the enhanced Floyd-Warshall. Any ideas?

A working Java version of both algorithms and a test case which produces a path with loop can be found here.

Edit: Since no solutions were presented yet, I implemented my own shortest minimax path algorithm using incremental link removal method. Java sources to the solutions can be accessed from the above link.

No need to introduce two arrays. In the original algorithm the distance equals the minimum (over all paths) of the sum of edges (in the path). The new variant defines a distance as the minimum (over all paths) of the maximum of edges (in the path).

Then one only needs to rethink the instruction

       final int d = ds[i][k] + ds[k][j];

In my understanding of Floyd-Warshall the array ns stores the highest number of the shortest path: it is updated to k each time a shorter path is found. To retrieve the path itself I would use a recursive procedure short[i,j] = short[i,k] + short[k,j] where k=ns[i,j] and provided k<>i and k<>j. (adapted to your programming syntax)

In that way no vertex will be repeated on a shortest path, but that part of Foyd-Warshall I always find hard to explain.


A 4-bit combinatorial circuit that outputs 1 when integer greater than 7 and is odd number I need to draw a combinatorial circuit that when an integer is greater than 7 and is an odd number, the output will be 1. There are 4 inputs representing 4 bits and 1 output wire. The output wire is only 1 if an integer is greater than 7 and is an odd number.

My attempt: If I segment the 4-bit input as r x y z where if the input was 8, the 4-bits would be 1 0 0 1. I know that r and z must have an AND gate but cannot figure out a way to get x y to work. I drew a truth table and found that

1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

must all equal to 1 to satisfy the condition placed.
Any help is appreciated.

You've got the answer!

The number is eight or higher if the first bit is set. The number is odd if the last bit is set. So the answer is simply those two bits ANDed together. The two middle bits don't matter, you don't need to bother with them.


k-armed bandit - index policies vs. Q-learning I am interested in the stateless k-armed bandit problem, where an agent repeatedly chooses one of k independent arms, each with a different distribution of rewards, and tries to maximize its total reward.

I read many papers about this subject, but I am still confused, as there are two types of solutions:

A. It has been proven that the optimal solution to this problem is an index policy: For each arm, calculate a quality index, based on the rewards received from that arm so far. The index roughly estimates an upper confidence bound on the expected reward from that arm. Now choose the arm with the highest index.

B. On the other hand, this problem can also be presented as a Markov decision process, which can be solved by Q-learning. The general formula for Q-learning is:

$Q_{t+1}(s,a) := (1-z_t) Q_t(s,a) + z_t (R_t + g * max_{a'}(Q_t(s',a'))$

Where: t is the time, s is the state we were at, a is the action we did, s' is the state we got into, $z_t$ is the rate of learning at time t, R_t is the reward we received at time t, and g is a constant discount rate.

In this case, there is only a single non-terminal state. Each arm-pull is an episode: it starts with the initial state, and always goes to the final state. Therefore, the Q value of the final state is always 0, and we only need to calculate Q values for actions of the single initial state:

$Q_{t+1}(a) := (1-z_t) Q_t(a) + z_t R_t$

It is guaranteed that the process will converge to an optimal policy, if each action is selected eventually, and if the learning rate $z_t$ decreases in an appropriate rate (speficically, $\sum_{t=1}^\infty z_t^2 < \infty$ and $\sum_{t=1}^\infty z_t = \infty$).

Now, my question is: what is the relation between two methods for solving the k-armed bandit problem?

Is it possible to prove, that the Q values converge to one of the indices given in the literature?
Why use an index method, if it is possible to use the much simpler Q-learning method?

The difference between your formula and the index methods is that your formula gives more weight to recent data. If there's a lever that has large but infrequent rewards then your formula won't converge.

On the other hand, your formula will perform better than index methods if the reward distribution for some of the levers changes across time.

The next state is actually not the terminal state unless there are no more trials, so simplifying out $g * max_{a'}Q_{t}(s',a')$ is only valid if $g = 0$. But in this case $g = 0$ should work quite well.


How can there be stop and wait protocol for a simplex channel? Doesn't the receiver have to send back an acknowledgement frame?
So how can it send back a frame, since a simplex channel only allows transmission in one direction?

Some writers use the term "simplex" to mean that communication is only possible in one direction. Others use it to mean that communication is possible in both directions but not at the same time; this is also called "half-duplex". I suspect that the protocol you're talking about is for a half-duplex channel: the sender transmits for a while and then pauses to allow the receiver to use the channel in the opposite direction for acknowledgments.


How does a single-track Turing machine simulate a multi-track Turing machine? It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification of a transition function that does the job. If there are $k$ tracks, then we can think of symbols as being vectors and arrange them one after another in the tape; but again, what's the transition function like in the equivalent single-track machine?

If $\Sigma = (x_1,...,x_n)$ is the alphabet of the $m$-tracks $TM$, just use an expanded alphabet $\Sigma' = \Sigma \times ... \times \Sigma$ for the single-track $TM'$  ($|\Sigma'| = n^m$).

Every vector $\bar{x}_i$ of $m$ symbols from $\Sigma$ can be mapped to a unique alphabet symbol $u_i$ in $\Sigma'$: $\bar{x}_i = (x_{i_1},x_{i_2},...,x_{i_m}) \rightarrow u_i \in \Sigma'$

Hence every transition of $TM$ $(q_h,(x_{i_1},x_{i_2},...,x_{i_m}))\rightarrow (q_k,(x_{j_1},x_{j_2},...,x_{j_m}),dir)$
can be mapped to an equivalent transition in $TM'$ where the "read vector" $\bar{x_i}$ and "write vector" $\bar{x_j}$ are replaced with the corresponding alphabet symbols in $\Sigma'$: $(q_h,u_i)\rightarrow (q_k,u_j,dir)$


To what extent is an x86 machine equivalent to a Turing Machine? To what extent is the abstract model of computation specified by the x86 language Turing complete?
The above question is related to this question: Is C actually Turing-complete?
In theoretical computer science the random-access stored-program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.

The RASP is a random-access machine (RAM) model that, unlike the RAM, has its program in its "registers" together with its input. The
registers are unbounded (infinite in capacity); whether the number of
registers is finite is model-specific. Thus the RASP is to the RAM as
the Universal Turing machine is to the Turing machine. The RASP is an
example of the von Neumann architecture whereas the RAM is an example
of the Harvard architecture.
https://en.wikipedia.org/wiki/Random-access_stored-program_machine

The difference is: since x86 machines are finite, Turing machines can decide languages (decision problems) that cannot be decided by any x86 machine.

As I explained before, the idea of 'the set of decidable computations' is a category error.  Decidability is a property of formal languages (or equivalently, of decision problems), not of computations.  So, no, the statement in the second paragraph of your question is not correct.  It's not even wrong -- it is neither true nor false.

I suspect that perhaps you have found a statement of the Church-Turing thesis that is worded in a way that is confusing.  I suggest reading a standard reference on the Church-Turing thesis, and don't rely solely on the wording you have bolded.

It is true that every decision problem that can be solved by an x86 machine can be solved by a Turing machine (or, equivalently, every language that can be decided by an x86 machine can be decided by a Turing machine).  This is true because you can program a Turing machine to simulate the behavior of an x86 machine.  However, the converse is not the case: any real x86 machine has a fixed and finite amount of memory, while a Turing machine can use an unlimited amount of storage on its tape, so there are decision problems that can be solved by a Turing machine, but not by an x86 machine.  (Even if we take into account the amount of storage provided by disks, disks use fixed-length addresses, so there is a fixed and finite upper bound on the maximum amount of disk storage that can be addressed from a standard x86 machine.)

If you wanted an x86 machine to be equivalent in power to a Turing machine, you'd have to provide some way to extend its amount of storage without limits.  If you had a way to do that, then yes, any decision problem that can be decided by one could be decided by the other: each one could simulate the other.


Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata? I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG).
I suspect that languages like $\text{L} = \{10,10100,101001000, \dots\}$ can not be generated by a CFG. I can not see that intuitively (heuristics will help me). I have seen PDAs to be finite state automata in some places, and infinite in the rest.
Can someone tell me the limitations of a CFG / PDA (if any) and whether or not $\text{L}$ can be generated by a PDA/CFG? Additionally, are PDAs infinite state automata?

Since each context-free language can be described by a grammar, there are only countably many context-free languages (over a fixed alphabet). Therefore, "most" languages are not context-free. Examples of particular languages which are not context-free abound. Your language $\{ 1010^210^3\cdots 10^n : n \geq 1 \}$ is one such example. It can be proved to be non-context-free using the pumping lemma, for example.
Push-down automata have finitely many states, but an infinite stack. Although the stack is infinite, it can only be accessed in very specific ways, and this severely limits the power of the automaton. If we replace the stack with a queue, or add a second stack, then the automaton becomes much more powerful – equivalent to a Turing machine. But even such automata can only accept countably many languages. In particular, they cannot accept uncomputable languages such as that of the halting problem, as shown by Turing.


What are current approaches to auto-parallelisation? I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.

Automatic parallelization in the most general terms is extracting a dependency graph from the execution sequence of the program and executing distinct paths in this graph in parallel with synchronization introduced at the nodes of the graph where the paths merge.

Our ability to extract the dependency information varies depending on the programming language used. Functional languages have no side effects that makes it easier to parallelize. It is more difficult with imperative languages.
Several programming languages were proposed where parallelism may be implicit. Such as array programming languages.

Autoparallelization of inherently sequential programs like programs written in C or FORTRAN attracts significant practical interest. One classical reference work on the subject is Michael Wolfe's "Optimizing Supercompilers for Supercomputers" based on his 1982 PhD thesis [1].

One of the key areas of the work is parallelizing multidimensional loops. Observe that loop indices are often used in linear combinations inside loops (e.g. for a $N\times N$ matrix $a$ in a C language program a[I][J] is a reference to an element that lies at position a + I * N + J). Therefore dependencies between iterations can be expressed as linear equations. Thus the ability to solve systems of linear equations efficiently is important for autoparallelizing compilers.

In an important general case finding depdendencies between operators in a loop requires finding all solutions of a system of linear equations in integers. There exists no polynomial algorithm for finding a solution of such a system of equations, therefore approximate tests are employed, that can detect independence. An important class of tests are derived from Banerjee Inequality.

The essense of the method is as follows. Let $x$ and $y$ be vectors of unknowns of dimension $d$, and $\textrm{A}$, $\textrm{B}$ be some linear operators. For loop dependencies the values of indices usually have upper and lower bounds. Suppose $m_i \leq x_i,y_i \leq M_i$.

To test if a system of linear equations $\textrm{A}x - \textrm{B}y = c$ has a solution we find the upper bounds $UB_j$ and lower bounds $LB_j$ of $\textrm{A}x - \textrm{B}y$ for all possible values of $x$ and $y$, $m_i \leq x_i,y_i \leq M_i$ and test if $c$ lies within the bounds. If it does not, then there is no solution, and two memory references are independent, hence can be executed in parallel. This test is incomplete, but can be efficiently computed.

Different data-dependence heuristics are compared on real and synthetic benchmarks [2]. A recent overview of data-dependence analysis techniques can be found in the publications from the UCSD Kremlin project [3].

M. Wolfe, Optimizing Supercompilers for Supercomputers, 1989
K. Psarris, K. Kyriakopoulos, An Experimental Evaluation of Data Dependence Analysis Techniques, IEEE Transactions on Parallel and Distributed Systems, March 2004 (vol. 15 no. 3), pp. 196-213
S. Garcia, D. Jeon, C. Louie, M.B. Taylor, Kremlin: Rebooting and Rethinking gprof for the Multicore Age, PLDI'2011


Understanding Dijkstra's algorithms As far as I understand, Dijkstra's algorithm always picks the nearest neighbour.

But how does it work for the following graph?

    2
A-------B
 \     /
1 \   / 3
    C

var result = dijkstra(fromA, toB);

Step1: A->C is the shorter
Step2: C->B is the shorter
Answer: 1 + 3 === 4 // This is clearly wrong

What am I missing?

Dijkstra works as follows:

Take the first node from OPEN. Let $n$ denote such node. OPEN contains all nodes generated in ascending order of $g(n)$, where $g(n)$ is defined as $\sum\limits_{i=1}^{n-1} c(v_i, v_{i+1})$, and $c(v_i, v_{i+1})$ is the cost of the edge from $v_i$ to $v_{i+1}$. In other words, $g(n)$ is the sum of the edge costs in the path from the start state to node $n$.
If $n$ is the goal state, then halt. The optimal solution is the path from $s$ to $n$.
If $n$ is not the goal state, then verify whether it has been expanded before or not. Another list, called CLOSED contains those nodes already expanded. If $n$ is found in CLOSED, then go to 1. Otherwise, expand $n$ generating its successors. Evaluate $g(n')$ for each descendant $n'$ and add them to OPEN.
Remember you expanded $n$, so add it to another list called CLOSED. Go to 1.

Initially, OPEN=$\{s\}$ where $s$ is the start state and CLOSED=$\varnothing$ as you have expanded no node yet.

From your execution trace, it seems to me that you overlooked step 2, ie., Dijkstra stops when it is about to expand the goal state, and not when it is generated. As a matter of fact, you may generate the goal state an arbitrary number of times, but condition 2 is met only once.

Hence, in your specific case, Dijkstra works as follows:

Iteration #1
OPEN=$\{A\}$ and CLOSED=$\varnothing$

Take the first node from OPEN, $n=A$
It is not the goal state $A\neq B$
It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $C$ with a cost equal to 1 and $B$ with a cost equal to 2. They are now added to OPEN in ascending order of $g(n)$ so that OPEN=$\{C, B\}$
Add $A$ to CLOSED as it has been expanded, CLOSED=$\{A\}$

Iteration #2

Take the first node from OPEN, $n=C$
It is not the goal state, $C\neq B$
It does not appear in CLOSED, ie., it has not been expanded before. So that its descendants are generated: $B$ (its parent $A$ is easily removed as it is clearly its parent, but you can try to generate it as well and you'll see Dijkstra works smoothly the same). $B$ has now a $g$-value equal to 4 as it has been generated through the path $\langle A, C, B\rangle$. Hence, OPEN contains now $B$ twice: OPEN=$\{B, B\}$, the first one with a value equal to 2 (generated in the first iteration) and the second with a value equal to 4 (generated in this iteration).
Add $C$ to CLOSED as it has been expanded, CLOSED=$\{A, C\}$

Iteration 3

Take the first node from OPEN, $n=B$ (with a cost equal to 2).
It is the goal state. Halt with the path $\langle A, B\rangle$

Hope this helps,


Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)? I've learned from several sources that an LL(1) grammar is:

unambiguous,
not left-recursive,
and, deterministic (left-factorized).

What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):

A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).

I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:

We start by writing the three rules of the definition of an LL(1) grammar:

For every production A -> α | β with α ≠ β:

FIRST(α) ∩ FIRST(β) = Ø.
If β =>* ε then FIRST(α) ∩ FOLLOW(A) = Ø (also, if α =>* ε then FIRST(β) ∩ FOLLOW(A) = Ø).
Including ε in rule (1) implies that at most one of α and β can derive ε.

Proposition 1: A non-factored grammar is not LL(1).

Proof:

If a grammar G is non-factored then there exists a production in G of the form:

A -> ωα1 | ωα2 | ... | ωαn

(where αi is the i-th α, not the symbols α and i), with α1 ≠ α2 ≠ ... ≠ αn. We can then easily show that:

∩(i=1,..,n) FIRST(ωαi) ≠ Ø

which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎

Proposition 2: A left-recursive grammar is not LL(1).

Proof:

If a grammar is left-recursive then there exists a production in G of the form:

S -> Sα | β

Three cases arise here:

If FIRST(β) ≠ {ε} then:

    FIRST(β) ⊆ FIRST(S)

=>  FIRST(β) ∩ FIRST(Sα) ≠ Ø

which contradicts rule (1) of the definition.
If FIRST(β) = {ε} then:

2.1. If ε ∈ FIRST(α) then:

ε ∈ FIRST(Sα)

which contradicts rule (3) of the definition.

2.2. If ε ∉ FIRST(α) then:

    FIRST(α) ⊆ FIRST(S) (because β =>* ε)

=>  FIRST(α) ⊆ FIRST(Sα) ........ (I)

we also know that:

FIRST(α) ⊆ FOLLOW(S) ........ (II)

by (I) and (II), we have:

FIRST(Sα) ∩ FOLLOW(S) ≠ Ø

and since β =>* ε, this contradicts rule (2) of the definition.

In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎

Proposition 3: An ambiguous grammar is not LL(1).

Proof:

While the above proofs are mine, this one is not, it's by Kevin A. Naudé which I got from his answer that is linked below:

https://stackoverflow.com/a/18969767/6275103


P is contained in NP ∩ Co-NP? How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$?

I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.

A language $L$ is in $P$, we have an algorithm $A$ that runs in polynomial time that recognizes it.

It is easy to show that the complement of $L$,  $\bar{L}$, is in $P$. The algorithm to recognize it is to simulate $A$ but just invert the answer.

As long as $\bar{L}$ is in P (thus in NP), $L$ is in $co-NP$.


Realtime hardware/software versus PC software/hardware, how are these distinct and alike? This question stems from a few answers and comments on a question I posted in signal processing found here.

I guess I am a little confused. Are there any concrete differences between realtime software/hardware and just a regular PC?

I would try to list what I think the differences are but the list I have come up with is ambiguous and short.

The only thing I think makes sense to separate the two ideas is that PC software can run part of its code part of the time, real-time runs all of its code each time. So a PC can load a program but not all programs and run just that program for however long it pleases, real-time is just a single program with a bunch of if-else, switch logic basically a huge abstract collection of relays (PLC) that gets ran through every time it is called.

Yes I realize this is a pretty poor description, so I ask is there any good concrete ways to separate these ideas?

In general, the difference between "normal" and "real-time" is some sort of guarantee on the time it takes to complete job. In a normal system, usually you have no guarantees at all. Programs can get interrupted by other programs, the OS scheduler might not be completely fair, the processor does complicated things that alter the runtime between executions of the same code...

For most applications this does not matter.

Real-time systems are built such that one can guarantee that job X is always completed after at most Y seconds. This is important for example for the chip that decides when to deploy air bags--if that takes longer than expected, you're dead. To be able to give these guarantees you have to use special operating systems (or no operating system at all) that guarantees appropriate scheduling. It is also necessary to know a lot of details about the hardware you're using. Does your chip have a cache? What kind of replacement policy does it use? How many cycles does an addition take? Is that always the same number? What's the branch prediction algorithm? etc.

Many people confuse real-time systems with very powerful processors that can churn through data "in real time". But that's not (always) the case. The important thing is not how long it takes in absolute time, the important part is that it never takes longer than expected. There are trade-offs both in hard- and software between throughput (expected computation speed) and predictability (worst-case speed).


Minimizing total distance traveled by points in points cloud transformation I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than ε at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions). In such a case maximum point speed, V, should be introduced.

More than 2 points may lay on a line (e.g. 2 starting points and 2 destination ones may be collinear).

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

The greedy approach will not work, because if we start from point A
and choose the nearest destination point, we'll end up with E
moving to F, which is far from being optimal.
Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

If the trajectories must be lines and $\epsilon$ is small enough, the problem can be solved with min-cost matching. If all coordinates are integers with absolute value bounded by $H$, then two disjoint intervals with integer endpoints have distance at least $\frac{1}{4H}$ from each other. Hence if $\epsilon$ is less than this value, it might as well be 0.

Take any four points $A, B, C, D$ and assume that there exists a line segment connecting $A$ and $B$, one connecting $C$ and $D$, and that these line segments intersect at point $X$. Then $|A - B| + |C - D| = |A - X| + |B - X| + |C - X| + |D - X|$. Triangle inequality is strict when the three points do not lie on the same line, so if not all of $A,B,C,D$ are colinear, we can exchange the startpoints of the segments to decrease their total length. Thus, if no four points lie on a line, the minimum total length solution doesn't have intersecting line segments.

To find the minimum total length solution, we use min-cost matching, with cost $|A - B|$ to match points $A$ and $B$ (assuming one of $A$ and $B$ is a starting point, and the other is an endpoint).

To handle the case where some four points lie on a line, we just disallow matching $A$ and $B$ if some other point lies between them. Matching in this case is not always possible, for example if we have two startpoints, then two endpoints on a line.


Two addresses point to the same data - is the data then stored 2 times in the cache? Let's say a program reads the addresses 0x00 cd 10 54and0x00 cd 10 50. The tag size and and index size added are just 4 bits, the cache has 8 blocks to 8 Bytes and thus 4 together make a set. The CPU is 32 bit.

Then above addresses would point to:

0x00 cd 10 50: ca 01 6b 7f ff 00 10 ee ff 41 45 e8 00 a7 56 00

and would want to write ca 01 6b 7f ff 00 10 ee into set 0 with tag 0x00 cd 10 5

Let's say further say, the cache were empty beforehand. Is the data now written once or two times?

To answer the question: The read addresses are always rounded down to the next cache line address, then it will be looked up, whether an cache entry already matches this address.

In case yes: Then the address will just be ignored. Nothing further happens.

In case no: Then the data corresponding to the address will be load into the cache.


Operating System - CPU scheduling Decisions I understand that CPU scheduling takes place on 4 circumstances listed below:

When the process changes state from Running to Ready
Changes state from Running to Waiting
Changes state from Waiting to Ready
Process Terminates

However, i notice that the CPU scheduling does not take place when Ready to running. Why is this so?

The only way that a process can go from "ready" to "running" is if the scheduler just scheduled it. Running the scheduler as soon as the process started running would mean that you'd actually be running the scheduler the whole time.


Difference between := and ← in pseudocode This is a snippet from some pseudocode for a sorting algorithm. In it, the symbol ← is used to denote assignment, for example for the variable done. However, in the while loop the statement done:= false is written. I would assume it is also an assignment statement but I suspect it means somethings else, or perhaps extra, since if not, the ← would have simple be used again.

Algorithm MyAlgorithm(A, n)
    Input: Array of integer containing n elements
    Output: Possibly modified Array A

done ← true
j ← 0
while j ≤ n - 2 do
     if A[j] > A[j + 1] then
        swap(A[j], A[j + 1])
        done:= false
     j ← j + 1

The use of := in this context appears to be a slip-up from whomever it is who wrote that pseudocode. The initial impression given is that they have different meanings (I thought at first that := was perhaps "redefine", and that ← was "declare and define"). However, with the use of j ← j + 1 on the line following it, it seems clear that the := was a mistake.

In general, := and = are the most common assignment operators, seemingly in both pseudocode and real code. You may be interested in looking at notations of the assignment operator in various programming languages, which include :=, =, <-, ←, and many others.


evaluating time complexity of a code I'm trying to evaluate the time complexity of the following :

foo (n)
    if n ≤ 1
        return 1
    if n is odd
        for i=1 to n
            print i
        return foo(n-1) + 1
    if n is even
        i=n
        while i>2
            j=1
            while j<i
                j=j*2
            i=i/3
        return 2 * foo(n-1)

my attempt was to produce a recurrence relation broken into cases:

if $n \leq 1$ then :

$T(n)=\theta(1)$

if $n $ is odd then the for loop is executed $n$ times and we return a problem of size $n-1$ so :

$T(n)= T(n-1) + \theta(n)$

if $n$ is even then the inner while loop is executed $\theta(log_6(n))$ times and the outer while loop is executed $O(log_3(n)) $ times so totally that would be $O(log_3(n))= O(log(n))$ , and we return a problem of size $n-1$ twice so:

$T(n) = 2T(n-1) + O(log(n))$

ultimately :

$T(n) = T(n-1)+n $ if $n$ is odd

$T(n) = 2T(n-1)+log(n) $ if $n$ is even

$T(n) = 1 $ if $n = 1$

since whenever $n$ is odd , $n-1 $ is even , $n-2 $ is odd and so on..
that had me confused. Any ideas of how to solve this?

Your recurrence is
$$
T(n) = \begin{cases}
T(n-1) + n & \text{if $n>1$ is odd}, \\
2T(n-1) + \log n & \text{if $n$ is even}, \\
1 & \text{if $n=1$}.
\end{cases}
$$
We can convert it to a more amenable pair of recurrences. If $n > 1$ is odd then
$$
T(n) = T(n-1) + n = 2T(n-2) + n + \log(n-1).
$$
If $n > 2$ is even then
$$
T(n) = 2T(n-1) + \log n = 2T(n-2) + 2(n-1) + \log n.
$$
Finally,
$$
T(2) = 2T(1) + \log 2 = 2 + \log 2.
$$

We obtain the two recurrences
$$
T(2m+1) =
\begin{cases}
2T(2(m-1)+1) + (2m+1) + \log (2m) & \text{if $m > 0$}, \\
1 & \text{if $m = 0$}.
\end{cases} \\
T(2m) =
\begin{cases}
2T(2(m-1)) + 2(2m-1) + \log(2m) & \text{if $m > 1$}, \\
2 + \log 2 & \text{if $m = 1$}.
\end{cases}
$$
Both recurrences are of the form $S(m) = 2S(m-1) + \Theta(m)$. The simplest way of solving this is considering $R(m) = S(m)/2^m$, which satisfies the recurrence $R(m) = R(m-1) + \Theta(m/2^m)$. Since $\sum_{m=0}^\infty m/2^m$ converges, we see that $R(m) = \Theta(1)$ and so $S(m) = \Theta(2^m)$. This implies that $T(2m+b) = \Theta(2^m)$ (for $b=0,1$), and so $T(n) = \Theta(2^{n/2})$.


MAXSAT using dpll algorithm? It's possible to return from a dpll algorithm M as maximum for MAX-SAT problem?:
I have a sample:
https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f
we can modify recurrency to return the outcome of MAX-SAT?
Resources:
https://en.wikipedia.org/wiki/DPLL_algorithm

The DPLL algorithm doesn't try to satisfy as many clauses as possible.  If there is a satisfying assignment, DPLL will find it.  Otherwise DPLL will try a series of partial assignments until it runs out of possibilities, and then it will declare the formula unsatisfiable.  But in the case of an unsatisfiable formula, there is no guarantee that DPLL will discover the maximum number of satisfiable clauses on the way to proving unsatisfiability.
The MAXSAT problem is related to finding the minimally unsatisfiable subformulas (MUSes) of an instance.  Determining whether a set of clauses is a MUS is a DP-complete problem.  This is expected to be harder than mere NP-completeness, so it is unlikely that modifying DPLL to return partial solutions is going to be fruitful.  Given that the class DP is contained in $\Delta^P_2$ you might devise a scheme that calls DPLL (or related algorithms) a polynomial number of times to produce a MAXSAT result.


Equivalence rules for LTL - Getting stuck working with $ \square \lozenge $ & Until ($\textsf{ U}$ ) operators Need to prove equivalence for (or disprove equivalence for):

$
\hspace{1cm}\square ϕ → \lozenge ψ ≡ ϕ\textsf{ U }(ψ ∨ ¬ϕ) \\
$

My current attempt using the LTL equivalnce rules to determine equivalence:

$
\square ϕ → \lozenge ψ \\
≡\
¬\square ϕ \lor \lozenge ψ \hspace{1cm}(\textsf{"Mutual implication"} ϕ →ψ≡¬ϕ\lor ψ )\\
≡
\lozenge ¬ϕ \lor \lozenge ψ \hspace{1cm}(\textsf{"Duality"} ¬\square≡\lozenge ¬ )\\
≡
\lozenge (¬ϕ \lor ψ) \hspace{1cm}(\textsf{"Distributive law on"}\lozenge )\\
≡true \textsf{ U} (¬ϕ \lor ψ) \hspace{1cm}(\textsf{"Def of"}\lozenge )\\
≡true \textsf{ U} (ψ \lor ¬ϕ) \hspace{1cm}(\textsf{"Symmetry"}\lor)\\
$

After this I got stuck. I am not sure how to proceed from here to get the right side. Are other propositional logic rules allowed to be used in LTL, like for example identity disjunction?

In order to prove the equivalence of two formulas $\phi,\psi$, it is enough to show that for every computation $\pi$, it holds that $\pi\models \phi$ iff $\pi\models \psi$. This is semantic equivalence.

Let's look at (1). You got to the formula $true{\bf U} (\psi\vee \neg \phi)$. Now, this holds in a computation $\pi$ iff there exists $i\ge 0$ such that $\pi^i\models \psi\vee \neg \phi$. Assume now that $i$ is minimal with respect to this property, and consider the computations $\pi^j$ for $j<i$. If $\pi^j\models \neg \phi$, then $i$ is not minimal, so $\pi^j\models \phi$, which means that $\pi\models \phi {\bf U} (\psi\vee \neg \phi)$. Since the converse implication is trivial, we get that the two formulas are equivalent.

For (2) you should indeed show that the formulas are not equivalent. To do so, you need to show that there exists a computation $\pi$ that satisfies one but not the other.

Hint: It could be the case that $\phi$ holds only finitely many times, but $\psi$ does not hold after $\phi$.


What is the current state of the art in solving the halting problem? Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them.

To be a little more explicit about the sort of thing I'm looking for, total functional language compilers have to approximate the halting problem, proving that your source code terminates or saying it can't thus prove it. Idris, as far as I can tell, just uses a "one argument must be structurally smaller on each recursive call" primitive-recursion checker*; Isabelle is more sophisticated, with

datatype rosetree = Rose "'a rosetree list"

primrec rosemap :: "('a => 'b) => 'a rosetree => 'b rosetree" where
  "rosemap f (Rose as) = Rose (map (rosemap f) as)"

compiling fine despite the intermediate map on the recursive calls. Isabelle's fun mechanism seems even more powerful in terms of proving termination (although I can't think of a short, simple example for that off the top of my head).

Basically: how do these work? Are there papers or textbooks about the algorithms involved somewhere? Is finding heuristics for the halting problem a current research subject?

*If I'm wrong about this, please do let me know about that, too.

The question as asked is indeed very broad. I give a brief answer here: What are some comparative studies on program termination verification tools?, but that really barely scratches the surface.

I do have several remarks:

In general, once must distinguish between whole program analyses, which are powerful, but do not scale very well for realistic development, and modular analyses which are weaker, but have hope of being integrated in a development environment. Isabelle and Idris both take this approach. As a side note, I'm not sure if this Fuhs et al paper corresponds to the "out of the box" termination check for Isabelle, but it might be enlightening in terms of what the state of the art is.
Termination of higher-order typed programs is difficult, because it involves subtle interactions between the type system features, the inductive types involved, and the "guard condition" required for function definitions. The more complicated the termination check, the less trustworthy the system, since consistency depends on it! These slides by Barras go into some of the nasty details for the Coq system.
Termination for higher-order systems with side effects (references) is particularly nasty. In particular, types are not enough anymore, even in the absence of recursion, see e.g. Landin's knot.


Random algorithm with biggest sequence that never repeats I am going to attempt to write a random number generator using exisiting randomize algorithms. Can you suggest which algorithm has the biggest sequence that never repeats? I don't care if they are fast or slow.

If you don't want to follow Yuval's advice :), Mersenne Twister algorithm is a good random number generator and has a quite simple implementation (period of $2^{19937}−1$). See Wikipedia page for quick highlights on advantages/disadvantages. There are also many open source implementations in many programming languages.

For technical details and in-deep analysis of the algorithm see M. Matsumoto's articles that are available on his page.


Selecting random element from complement of set Let $[n] = \{1, 2, \dots, n\}$. Suppose we have a subset $S$ of $[n]$ of size $k$.
Can we sample one element uniformly at random from $[n] \setminus S$ in $O(k)$ time?
It's okay to use $O(n)$ auxiliary memory assumed to be initialized with zeros, as long as your algorithm can run and clean up back to the initial zero state all in $O(k)$ time.

Yes actually, and it's quite simple.

Sample a random integer $q$ from $[n-k]$.
Initialize $c = |\{x \in S \mid x \leq q\}|$.
While $c > 0$, let $q \leftarrow q + 1$ and if $q \notin S$ decrement $c$.
Return $q$.

This works because steps 2 and 3 forms a bijective mapping from $[n -k]$ to $[n] \setminus S$. Finally the algorithm runs in $O(k)$ because it's possible to check if $q \notin S$ in $O(1)$ time either by using a $O(n)$ memory bitset or a hash table and both steps $2$ and $3$ take at most $k$ steps.


Algorithm suggestion for ticket routing system using Machine Learning Background info

I'm a beginner in ML, let me start there. I'm trying to implement an intelligent system that can route a ticket (in a ticketing system), to the appropriate place based on a few parameters, 5-10.

How the algorithm should work

For example, ticket '1234' gets sent to 'accounting' by human, normally by reading the ticket description and title (finding keywords). The ML algorithm should learn where tickets go based on where similar (based on same keywords) tickets have gone before.

What I've tried

I implemented a very simple NN in JavaScript using the sigmoid function to predict discrete yes/no type of outputs. If I remove the sigmoid function, I could predict where the ticket should go, based on keywords turned into parameters, perhaps using linear regression.

The problem

I'm not sure how I can turn keywords into number parameters, (or vectors?), that can be fed into a simple linear regression implementation. With my limited knowledge, I'm not sure if linear regression is the way to go but it certainly sounds like it. Linear regression is also a simpler algorithm I'll be able to implement myself.

Is linear regression the way to go? How can I turn an arbitrary-length paragraph (ticket description) into meaningful keywords to be used by the algorithm?

Ideally this would be JavaScript, but I see no tags for JavaScript. Odd.

Linear regression does not seem like the right tool here.  This isn't a regression problem; it is a classification problem.  Regression outputs a continuous number; you need to output a category (which place the ticket should be routed to; presumably there is a finite list of candidate places).

I would suggest that you learn about natural language processing.  The very simplest thing you could try would be naive Bayes with bag-of-words features.  Fair warning: I would not expect that you will get especially good results without a lot of knowledge of NLP (and maybe not even then); it's probably going to be challenging to find a good solution for your problem.


Turing Machines proof notations In context of "Computability", I have went over some proofs for Recursion
Theorem using Turing Machine description. A TM $M$ stands for a single tape
Turing machine and $\langle M \rangle$ is the description of TM $M$. Even some semi-decidable machines such as $A_{\mathrm{TM}} = \{ \langle M, w \rangle \mid \text{TM $M$ accepts $w$} \}$. My question is simple:

What is difference between using $\langle M \rangle,\langle w \rangle$ vs $\langle M , w \rangle$ for a TM description?

A simplistic answer I assume is that it is being a convention in writing formal proof that books follows standard of combining all inputs as a single description (all inputs comes under single brackets as opposed to multiple descriptions)?

My question c

If
$M_1 = \{ \langle M , w \rangle \mid \text{TM $M$ accepts $w$} \}$ and
$M_2 = \{ \langle M \rangle , \langle w \rangle \mid \text{TM $M$ accepts $w$}
\}$

What's the difference between $M_1$ and $M_2$?

$\langle x \rangle$ simply denotes the encoding of some object $x$. $x$ can be a TM (e.g., its Gödel number), a string, some combination thereof (properly separated), or even other objects like a graph, etc.

This serves, for instance, to distinguish between $\{ \langle M \rangle \mid \text{$M$ is a TM} \}$, which contains encodings of TMs (e.g., their Gödel numbers or representations in binary), and $\{ M \mid \text{$M$ is a TM} \}$, which is the set of Turing machines themselves (as mathematical objects). The underlying motivation is that it is not clear how a TM (as an object) can be passed as an input; what you do is provide its "program", that is, its states and transition function.

When multiple objects are encoded together as a single string (i.e., to be seen as a single object), it is usual practice to denote it as $\langle x_1, \ldots, x_m \rangle$. Again, it is not immediate what the encoding is. It could be simply concatenating the encodings of each $x_i$ and separating them (e.g., $\langle x_1, \ldots, x_m \rangle = \langle x_1 \rangle \# \cdots \# \langle x_m \rangle$); it could also be that the encoding of $x_i$ is altered in some way (e.g., each $0$ or $1$ in $\langle x_i \rangle$ is doubled and each such representation is separated by $01$); it could even be that the entirety of the representation is compressed (so as to reduce its length) or that it is subject to some predetermined enumeration (e.g., as a vector over some countable space).

Generally, if they are relevant to the context at all, these descriptions should be made precise beforehand, as most textbooks do. In computability theory, except when covering Gödelization, they usually are not; this is because the actual length of the input is irrelevant to computability questions. Things are different in complexity theory—though it usually does not get much attention there either (besides coming up in a preface or similar); most objects are encoded in binary anyway, and multiple objects with only a constant stretch, which suffices for almost all complexity-theoretical topics.


Counting Colorings of a Grid Given a $n \times m$ grid, define a valid coloring as mapping from the grid cells to a set of $k$ available colors such that no two adjacent cells have the same color. Cells are considered as adjacent if they share a side. How many valid colorings are there? Let $f(n, m, k)$ be the answer.

I search for a way to compute $f(n, m, k)$ fast, primarily in terms of time complexity. However, a polynomial-time solution is not required.

This problem was proposed in Codesprint 5 at HackerRank with constraints $1 \le n,m \le 8$ and $k \le 10^9$. However, I am not asking for this particular case, so it does not matter so much. It is worth mentioning there is a discussion on TopCoder, but I do not get it after several readings.

Approaches. I present my thoughts as following. First, we may explicitly enumerate all colorings. This works only on very small instances, because the number of colorings is growing exponentially. In order to see this, consider an $1 \times m$ grid and $k = 3$ colors. The first cell may be colored in $3$ ways and each following cell in $2$ ways, which yields $f(1, m, 3) = 3 \cdot 2^{m - 1}$.

Let's consider $n = 2$. If $m = 1$, we simply get $f(2, 1, 3) = 6$. Assume, we know $f(2, m, 3)$ for some $m \in \mathbb{N}$. Let $X$ and $Y$ be the colors in the rightmost / last column for an abritrary valid coloring of $2 \times m$ grid. In $(m + 1)^{th}$ column, there are $2$ colors for the top cell $(Y$ and the third color, say $Z$). Distinguish between two cases.

Case #1: Top cell has color $Y$. Then, our bottom cell can get color $X$ or color $Z$. There are two possible choices.

Case #2: Top cell has color $Z$. Then, our bottom cell must have color $X$.

Altogether, there are $3$ possibilities for the next step, i.e. $f(2, m + 1, 3) = 3 \cdot f(2, m, 3)$. Using our base case and solving the recurrence, the result comes out to be $f(2, m, 3) = 2 \cdot 3^m$.

These counting arguments get more complicated for larger values of $n$, even for $n = 3$ I do not find an explicit formula. In the original problem, there are significantly more colors than cells. It should be sufficient to consider colorings with exactly $1, 2, \dots, mn$ colors (let $a_{i}$ be the respective answers) and compute $\displaystyle \sum_{i = 1}^{mn} \binom{k}{i} a_{i}$. Therefore, don't worry too much about this step.

Hints and approaches are appreciated as well as solutions and references.

For every graph $G$ on $n$ vertices there is a degree $n$ polynomial $\chi_G$ such that $\chi_G(k)$ is the number of valid $k$-colorings of the graph. This polynomial is known as the chromatic polynomial, and can be found in exponential time. The easiest solution to the programming challenge is to precompute the chromatic polynomials. For example, denoting the $n \times m$ grid by $G(n,m)$, we have
$$
\begin{align*}
\chi_{G(1,1)} &= x \\
\chi_{G(1,2)} &= x^2 - x \\
\chi_{G(2,2)} &= x^4 - 4x^3 + 6x^2 - 3x \\
\chi_{G(1,3)} &= x^3 - 2x^2 + x \\
\chi_{G(2,3)} &= x^6 - 7x^5 + 21x^4 - 33x^3 + 27x^2 - 9x \\
\chi_{G(3,3)} &= x^9 - 12x^8 + 66x^7 - 216x^6 + 459x^5 - 648x^4 + 594x^3 - 323x^2 + 79x
\end{align*}
$$


Selecting connected subgraph that exceeds value c, with least possible weight Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that,

Sum of all values in  $V^*$ crosses threshold $t$.
Sum of all weights(say $w^*$) in $V^*$ is as low as possible.

A practical example is finding smallest continuous area of a country that hosts at least $x\%$ of the population. In this case, value would be population, and weight would be area.
I found a related question, but it only asks about the complexity, not the algorithm.
I thought of 0 - 1 knapsack, such that values and weights swap role. So,

Size of knapsack is $t$, however we are allowed to cross it once.
minimize $w^*$.

However, I think this won't work, mainly because we can't order the nodes by $value/weights$, and secondly because of ability to exceed knapsack size.

This problem is NP-hard.
Let $S = \{x_1, \dots, x_n\}$ be an instance of partition.
Create a clique $G$ on $n$ nodes $v_1, \dots, v_n$.
Set both the cost and the weight of $v_i$ to $x_i$.
Set $t = \frac{1}{2}\sum_{x_i \in S} x_i$.
If there is a subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$, then the set of vertices $\{v_i \mid x_i \in C\}$ is connected, has total value $t$ and total weight $t$.
If there is no subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$ then every subset of vertices of $G$ either has total value smaller than $t$ (and hence is not a feasible solution), or has a total value larger than $t$, and hence also weight larger than $t$.
Then you have that the answer to the instance of partition is yes if and only if the optimal solution to your problem has measure (total weight) $t$.


Notation for expressing function call count during a program run Which notation can be used for expressing how many times that function or subroutine called during a run of a program?

Example program pseudocode:

$
a \gets 0 \\
\textbf{While } a \neq 5 \textbf{ do} \\
\quad \textit{function1()} \\
\quad a \gets a + 1 \\
\textbf{end}
$

$g: functions \rightarrow \mathbb{N}$ and for this example it is: $g(function1()) = 5$

I want to use it for expressing empirical observations depending on function call count.

Most of the time less than |iterSearch(searchState)|/3 child node searched during experiments.

What are the possible notations for function $g$ ?

Based on your desired usage and the fact that there likely isn't a widely-known notation for this, I think that, whatever notation your use, you should formally simply consider it a name. As you want to use the actual value, a variable (or function if you wish to distinguish among parameters for the call) would suffice.
What I mean by considering the notation a name is that you give your notation no syntactic status: it is simply a naming convention for some function or variable. This requires that you must define the name for each different method call number you wish to describe. I advise you to do this, as number of function calls is something that is context-dependent (calls by whom? calls made when?), so defining this for every function call separately gives a natural place to specify this.

So, for your particular example, a name like $\#\mathrm{function1}(\bullet)$ could work.
Then, we can write something like

Let $\#\mathrm{itersearch}(a)$ be the number of calls to the function $\mathrm{itersearch}()$ in the execution of algorithm A with parameter $a$.
(...)
Most of the time less than $\#\mathrm{iterSearch}(searchState)/3$ child nodes were searched during experiments.


Finding asymptotic time complexity So I'm studying for a midterm and my professor put out a sample exam with the answers, and I'm stuck on one of the questions.

The answer is Big-O(n^2 log n)

Could someone show me the steps necessary to go from regular time complexity to asymptotic time complexity?

Informally:

There are two applicable rules here, wrt. a polynomial:

You can throw away the constant coefficients of each term.
The fastest growing term is the only one that matters, since as $n \rightarrow \infty$ (approaches infinity), the other terms will be insignificant.

So due to rule 1, $20n^2 + 2n^2\log n - 2n + 1$ becomes $n^2+n^2\log n - n + 1$.

Now, only the largest-growing term here will be significant. The other terms will be insignificant when $n \rightarrow \infty$. The two first terms are obviously much faster growing, since they have an exponent of $2$. The second term is faster than the first because it has a non-constant multiplier that is more than $1$ as $n$ approaches infinity; it will thus make the term grow faster. Thus the second term becomes the only one remaining.

Now for the math:

How do we know we can throw away constants?

Because, let $f(x)$ be that term, then $af(x) \in \mathcal{O}\left(f(x)\right)$, where $a$ is a constant, not dependent on $x$. What this means, is that $f(x)$ will grow at the same rate as $af(x)$, (as $x \rightarrow \infty$), even if it will always be larger by a multiplicative constant. How can we prove this?

The definition of $f(x) \in g(x)$:

$$|f(x)| \le \; M |g(x)|\text{ for all }x>x_0.$$

Where $M$ is some positive constant, and there exists some $M$ and $x_0$ that makes this true.

So let's set $g(x)=f(x)$:

So the question becomes: Does there exist an $M > 0$ and $x_0$ such that this holds true?

$$|af(x)| \le \; M |f(x)|\text{ for all }x>x_0.$$

The answer is simple: set $M=|a|$, then we get $|af(x)| \le \; |af(x)|\text{ for all }x>x_0$, which is of course true, since they are actually equal. And since this is true, we get $af(x) \in \mathcal{O}\left(f(x)\right)$ as per the formal definition of big O notation.

How do we know we only care about the fastest growing term in a polynomial?

See wikipedia section on properties of big O notation:

  If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example

  $f(n) = 9 \log n + 5 (\log n)^3 + 3n^2 + 2n^3 = O(n^3) \,, \qquad\text{as } n\to\infty  \,\!.$

  In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

To prove this, we need to prove that given two terms in a polynomial, if one grows as fast or faster than another, then the entire polynomial is as fast as the faster growing term. Formally:

$\left.f(x) + g(x) \in \mathcal{O}\left(f(x)\right) \vphantom{\Bigg|} \right|
_{g(x)\in \mathcal{O}\left(f(x)\right)}$

Translation: term $f(x)$ plus term $g(x)$ is as fast as $f(x)$ if $g(x)$ is bounded by $f(x)$ (bounded means: grows at most as fast as).

Proof of this statement:

$$
\begin{eqnarray}
&&&\hspace{2pt}&\hphantom{(1)}&\hspace{1pt}&
\\
\exists_{x_0,M>0} ~ \left|f(x) + g(x)\right|
&\stackrel{?}{\le}&
M\left|f(x)\right|
~~~x>x_0 \text{ as } x\rightarrow \infty
&&(1)&&\text{Reformulate question}
\\
g(x) &\in& \mathcal{O}\left(f(x)\right)
&&(2)&&\text{Given}
\\
\exists_{x_{g0},M_g>0}~\left|g(x)\right|&\le&M_g\left|f(x)\right|
&&(3)&&\text{Restatement of (2)}
\\
&&~~~x>x_{g0} \text{ as } x\rightarrow \infty
\\
f(x) &\in& \mathcal{O}\left(f(x)\right)
&&(4)&&\text{Reflexive}
\\
\exists_{x_{f0}=0,M_f=1}~\left|f(x)\right|&\le&M_f\left|f(x)\right|
&&(5)&&\genfrac {}{}{0}{}{\text{Restatement of (4) via}}{\text{def., choosing values}}
\\
&&~~~x>x_{f0} \text{ as } x\rightarrow \infty
\\
\exists_{
  \genfrac{}{}{0}{} {x_{f0},x_{g0}} {M_f=1,M_g>0}
}
~|f(x)|+|g(x)|&\le&
M_f\left|f(x)\right|+M_g\left|f(x)\right|
&&(6)&&\text{Adding (3), (5)}
\\
&&
~~~x>\max\left(x_{f0},x_{g0}\right) \text{ as } x\rightarrow \infty
\\
&\le&
\left(M_f+M_g\right)\left|f(x)\right|
&&(7)&&\text{Simplying (6)}
\\
&&~~~x>\max\left(x_{f0},x_{g0}\right) \text{ as } x\rightarrow \infty
\\
|f(x)+g(x)| &\le&|f(x)| + |g(x)|
&&(7.1)&&\text{Math}
\\
\exists_{
  \genfrac{}{}{0}{} {x_{0}=\max\left(x_{g0},x_{f0}\right)} {M=M_f+M_g}
}~\left|f(x)+g(x)\right|&\le&
M\left|f(x)\right|
~~~x>x_0\text{ as } x\rightarrow \infty
&&(8)&&\text{Simplifying (7,7.1)}
\\
M_f &=& 1
&&(9)&&\text{Valid/chosen in (5)}
\\
x_{f0} &=& 0
&&(10)&&\text{Valid/chosen in (5)}
\\
\exists_{
  \genfrac{}{}{0}{} {x_{0}=\max\left(x_{g0},0\right)} {M=1+M_g}
}~\left|f(x)+g(x)\right|&\le&
M\left|f(x)\right|
~~~x>x_0\text{ as } x\rightarrow \infty
&&(11)&&\text{Simplifying (8,9,10)}
\end{eqnarray}
$$

Thus we can construct a valid $M$ and $x_0$ given a valid $M_g$, and $x_{g0}$, which we know exist, because $g(x)\in \mathcal{O}\left(f(x)\right)$ is given.


Where are C++ templates inside of the lambda cube? C++ templates have type variables and can express lambdas, so they must have System F embedded. But is that exactly where they are located in the lambda cube? Can C++ templates produce new types or express dependent types?

(I originally posted this to Stack Overflow, but they referred me over to here.)

But is that exactly where they are located in the lambda cube?

The lambda cube is not a giant spectrum on which all programming languages can be classified. It is precisely eight languages, which combine a lambda calculus (values abstracted over values) with all possible combinations of three features:

Values abstracted over types (parametric polymorphism)
Types abstracted over types (kinds / type constructors)
Types abstracted over values (dependent types)

So, the C++ template language isn't anywhere on the lambda cube, since it isn't any of those 8 languages.

The second thing to keep in mind is that we can't mix up C++ features and C++ template features. Just because C++ has lambdas, this doesn't (necessarily) mean that its template language has them.

It is possible to ask, which of the three lambda-cube features does C++ have? It would seem that it features the full power of the lambda cube, but I'm not enough of a C++ expert to know for sure.


P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q My problem: Define two sets P and Q of words (that is, two problems) such that: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q

Hint: Following the OP's suggestion, let $P$ be the set of all TMs halting on every input, and let $Q$ be the set of all TMs halting on the empty input. It is known that $Q$ is undecidable and semidecidable (indeed, $\Sigma_1^P$-complete) and that $P$ is undecidable and not semidecidable (indeed, $\Pi_2^P$-complete). Moreover, $P \subseteq Q$ since if $T \in P$ then $T$ halts on every input, and in particular $T$ halts on the empty input, so that $T \in Q$.


Running Build-Heap Algorithm on given numbers I don't fully understand this build-heap function. Lets assume we have array 3, 4, 5, 13, 16, 32.

It seems like we swap the parent when it is less than the current A[j] but which number does the loop start with? Maybe somebody can go through 2-3 loops and show how the array changes after 1st loop, 2nd loop, 3rd loop. Much appreciated. Oh, also, what would be the runtime?

for i=2 to n
    j = i
    while (j>1) and A[parent(j)]<A[j] do
        swap A(parent(j)] and A[j]
        j = parent(j)

It appears you're building a max-heap, where every element is greater than or equal to its child elements (if any). With that understanding, let's trace the action. First, the parent node of $A[j]$ will be $A[j/2]$ (integer division: discard any remainder) so we'll have
$$\begin{array}{r|cccccccc}
j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \dotsc\\
parent(j) & \_ & 1 & 1 & 2 & 2 & 3 & 3 & \dotsc
\end{array}$$
To keep things simple, we'll let the initial array be $[3,4,5,13]$:

Insert at $i=2$.

$A[parent(2)]=A[1]=3 < 4=A[2]$ so we swap $A[1]$ and $A[2]$, giving us the array
$$
[4,3,5,13]
$$

Insert at $i=3$.

$A[parent(3)]=A[1]=4 < 5=A[3]$ so we swap $A[1]$ and $A[3]$, giving us the array
$$
[5,3,4,13]
$$

Insert at $i=4$.

$A[parent(4)]=A[2]=3 < 13=A[4]$ so we swap $A[2]$ and $A[3]$, giving us the array
$$
[5,13,4,3]
$$
and now $j=parent(4)=2>1$ so we see if we need another swap.

$A[parent(2)]=A[1]=5 < 13=A[2]$ so we swap $A[1]$ and $A[2]$, giving us the array
$$
[13,5,4,3]
$$
and we're done, the array is now a max-heap.

The runtime of this algorithm is no worse than a multiple of $n\log n$ since none of the elements are further than $\log_2n$ from the root at $i=1$ so you'll need at most $\log n$ swaps for each of the $n$ elements. This, by the way, is not as good as possible: there's different algorithm that builds a heap in no more than a multiple of $n$ time.


Convert for loop into math sigma notation Have some code (written in C), need the equivalent notation for mathematics.
Is it possible using if-statements and sigma notation for this, and if so, how?

int res = 0;
for (int i=0; i < (N/2)+1; i=i+1)
  if (N % pow(2, i) == 0) res = i;

I have gotten as far as:

$$ \sum _{i=0}^{{N\over2}+1}\:(N \mod 2^i )$$ (missing the == 0 and res = i)

Ideas or a solution are welcome.

Let me define
$$f(x) = \begin{cases} 0 & x \ne 0 \\
 1 & x = 0\end{cases}$$
Now it is
$$ \sum _{i=0}^{{N\over2}+1}\:f(N \text { mod } 2^i)$$
The code calculates how many times number is divisible by two (which by the way could be simplified to checking number of trailing zeros in binary representation, say hacky method x & -x).

You can define {N, 2} for the highest power of a prime 2 that divides N, and it is the valid notation. There are other approaches and notations of greatest power of two dividing N at MathOverflow.