if P!=NP then this means that for some fixed $k$ not all true sentences $\phi$ of ZF have a proof of length ≤ $|ϕ|^k$.

You do not need to assume $P \neq NP$ to prove this claim. If all true sentences $\phi$ of ZF have a proof of length $\leq |\phi|^k$ then the halting problem could be solved by enumerating all proofs of "$M$ is halting" and "$M$ is not halting" up to that size. So it's not possible for all true sentences to have a short proof. Instead of  $|\phi|^k$ we can take a function that grows even faster, e.g. $2^{2^{2^{|\phi|}}}$. There's no computable limit on how long a proof can be compared to its statement.
However, to speak about true sentences, we are assuming implicitly that ZF already has a model. So this reasoning does not prove that ZF is consistent - it assumes it from the start. There's no contradiction between "not all true statements have a short proof" and "all statements have a short proof" if there are no true statements.


Turing machines with a finite number of states

You misunderstood your lecturer's claim. Their claim was that the language of descriptions of Turing machines with 100 states is decidable. The language accepted by each such machine need not be.

In other words, given a string, you can decide whether it describes a Turing machine having 100 states. That's the extent of the claim.


Are all hypothetical machine models for calculating runing time of an alogrithm same?

In RAM model, which is very close to our computers, standard arithmetic operations and assignments take same time disregarding values as far as they fit to computer word. This yields good estimate for runtime and apgorithm behaviour. When some operation takes $c$ time, but constant you may provide it in assymptotic analysis or omit it, becase such analysis takes into consideration length of the input as it grows.

For fine grained computation and small inputs it makes sense to check whether $\mathcal O(5n^2)$ is better than $\mathcal O(100n)$. In assymptotic case constants are dominated by input length, that is why there is no difference between 3 and 20000, so using 1 as time unit makes calculations easier.

It is up to analyzer, how fine grained is analysis, but also which model is chosen, differences here are huge. Between RAM model and Turing Machine model difference is polynomial. Between RAM and Real RAM or BSS machine are vast, instead of word-sized integers arbitrary real or respectively rational numbers could be stored with operations on them taking single time unit. This creates enormous computation gap. So the choice of model is crucial and models are nowhere near similar.

Convention is to use smallest plausible model.
If you sort integers in transdichotomous model, the size of numbers doesn't matter, in RAM it does, it takes unit cost if they fit word size or longer if they don't.


How to decrease the confidence of a Monte Carlo algorithm in its answer?

You can compute the probability that outcome $e$ is the unique plurality answer, when repeating the algorithm $k$ times, as follows:
$$
\sum_{\substack{a+b+c+d+e=k \\ a,b,c,d,e \geq 0 \\ e > a,b,c,d}} \frac{n!}{a!b!c!d!e!} \left(\frac{1}{4}\right)^e \left(\frac{3}{16}\right)^{k-e}.
$$
This can be computed explicitly. When $k = 70$, the probability is roughly $0.502$, and this is the minimal $k$ for which the probability exceeds $1/2$.


How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

Suppose that the function $\ell$ represents the input length of an algorithm, in terms of several parameters $\vec{x}$, and suppose that the function $T$ represents its running time, in terms of the same parameters $\vec{x}$. Furthermore, there is a collection of valid parameter settings.
We say that $T$ is linear in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C \ell(\vec{x})$.
Similarly, we say that $T$ is polynomial in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C\ell(\vec{x})^C$.
(We get these definitions from the usual definitions of time complexity.)
In your case, $\ell$ and $T$ depend on two parameters $n,W$, and $\ell(n,W) = (n+1)\log W$. A parameter setting is valid if $n \geq 1$ and $W \geq 2$ (this unstated assumption is needed to guarantee that your running times are positive). You are interested in two functions $T$: $T_1(n,W) = nW$ and $T_2(n,W) = n\log W$.
Let us start with the second function $T_2$. For any valid $n,W$ we have $n+1 \leq 2n$ and so $\ell(n,W) \leq 2T_2(n,W)$. Therefore $T_2$ is linear in $\ell$, with $M = 1$ and $C = 2$.
Now let us consider the first function $T_1$. Suppose that $T_1$ were polynomial in $\ell$, with parameters $M,C$. Thus if $n \geq 1$, $W \geq 2$, and $(n+1)\log W \geq M$, then $nW \leq C[(n+1)\log W]^C$. In particular, taking $n=1$, we get that for any $W \geq 2$, $W \leq C2^C(\log W)^C$. Equivalently, $W = O(\log^C W)$. However, this is clearly false. Therefore $T_1$ is not polynomial in $\ell$.


Note: I found a better technique which I give in a separate answer, which is more general, faster and simpler, though the complexity results remain somewhat similar. I chose to leave this answer rather than replace it, as it may be interesting to compare, and both solutions were too long for a single answer.

Let A, B and C be the three stacks.
I assume that the top of A and B are on the small index side.

I note (X,Y,p) the transfer of p elements from the top of X to the top
of Y. This has of course the effect of inverting the order of these p
elements, and has a cost p.

Let q and r the quotient and remainder of the integer division of m by
n. Thus m=q*n+r.

Pseudocode for the interleaving

% transfer of the m-n unmatched tail by chunk of n elements
For i from 1 by 1 to q-1 do
  % transfer the bottom n elements remaining in A
  (B,C,n)
  (A,C,m-i*n)
  (A,B,n)      % bottom n
  (C,A,m-i*n)
  (B,C,n)      % bottom n
  (C,A,n)      % bottom n
  (C,B,n)
  (A,C,n)      % bottom n
  end loop
if r≠0 then
  % transfer the remaining r elements of the umatched tail
  (B,C,n)
  (A,C,n)
  (A,B,r)      % bottom r
  (C,A,n)
  (B,C,r)      % bottom r
  (C,A,r)      % bottom r
  (C,B,n)
  (A,C,r)      % bottom r
  end if

% Now we have transferred the extra elements of A at the bottom of C.
% We have only 2n slots available in C, for intertwining A and B.
% But we have m-n free slots in A.

(A,C,n)   % rest of A inverted in C
(B,A,n)   % B inverted in A
k=n       % number of remaining elements of each stack still to be transferred
t=m-k     % available space in A to do the transfer
while k>0 do
  t=min(k,t)
  (C,A,t)   % last t of A in direct order in A
  (C,B,k-t) % top rest of A in B in direct order
  (A,B,t)   % last t of A inverted in B
  For i from 1 by 1 to t do    % intertwin in C last t elements of remainder
    (A,C,1)
    (B,C,1)
    end loop
  (B,C,k-t) % top rest of A inverted in C
  k=k-t
  t=2t
  end  loop

Complexity

I am only counting the number of moves. It actually gives the
complexity since the control statements introduce only a constant
factor on the moves and the number of moves is polynomial.

For one iteration of the first loop : $6n+2(m-i\times n)$

Hence the cost of the loop is $\sum_{i=1}^{q-1}6n+2(m-i\times n)$
= $(q-1)(6n+2m)-2nq(q-1)/2$ = $(q-1)(6n+2m-nq)$ = $(q-1)(6n+2m-(m-r))$
= $(q-1)(6n+m+r)$

The cost of the following conditional is at worst $4(n+r)$

So the total cost for the last $m-n$ elements of stack A is majored by
$q(6n+m+r) \leq q(7n+mn/n) \leq 7m+m^2/n$

The cost of transferring the tail of A is quadratic in $m$ when $n$ is
constant, as B becomes too small with increasing values of $m$ to do
the tranfer in a fixed number of passes over the whole stack. The
linear decrease of the remaining part to be transferred does not help
enough.

Things are however better with the parts of the two stacks that must
be intertwined.

There is a first cost of $2n$.

The cost of one iteration of the loop is $2t+2(k-t)+2t$, the cost of
the inner loop being $2t$. So this makes a total of $2(k+t)$.

If $m\geq 2n$ then the loop is executed only once, with $k=t=n$, hence
the cost is $4n$. Note that $4n\leq 2m$ in this case.

Otherwise we start the loop with $k=n$ and $t=m-n$, so that we
have $k+t=m$. But the update k=k-t; t=2t at the end of the loop
preserve this property as an invariant. So each iteration actually
costs $2(k+t)=2m$, except possibly the last one, since $t$ may be
reduced by the statement t=min(k,t), thus lowering the cost of that
last iteration. Note that, in this case, $2m\leq 4n$.

Since $t$ doubles at each iteration, but will not be greater than $n$,
the number of iterations is at worse $1+\log_2 n$, when $t$ starts with
value 1. Note that there must be at least one iteration when $n=1$
(though it could be simplified), in which case $\log_2 n=0$.

But the initial value of $t$ is actually $min(n,
m-n)$. Since it would take $\log_2 min(n, m-n)$ iterations to reach that value,
starting from 1, the actual number of iterations is $1+\log_2 n - \log_2
min(n, m-n) = $1+log_2 \frac{n}{min(n, m-n)}$

Hence the total cost for this part is less than $2n+4n(1+\log_2 \frac{n}{min(n, m-n)})$

So, the overall complexity in stack moves is $O(m^2/n+n(1+\log
\frac{n}{min(n, m-n))})$

In particular the complexity is linear in $n$ or $m$ when the ratio
$h=m/n$ remains constant.

This is obvious for the first term $m^2/n=h^2n$.

For the second term,  we have
$min(n,m-n)=min(n,n(h-1))=n min(1, h-1)$. Hence $n(1+\log
\frac{n}{min(n, m-n))})= n(1+\log\frac{1}{min(1, h-1))})$


Confusion regarding terminology surrounding perceptron learning

In machine learning, the perceptron is an algorithm for supervised learning of binary classifiers.

Its much complex than just drawing some graph and fitting a line to divide these data. I should tell you that you gone entirely wrong about the core concept.

Our brain are capable of solving complex problem, few of which are impossible for a computer to figure out. Thus scientist studies our brain and tried to mimic its biological structure to achieve its capability in computers. One of the initial steps towards it was perceptron.

Two types of perceptron are:

Single Layer perceptron - works only in linearly separable data.
Multi Layer perceptron - work with non linear data too.

Perceptron have the capability of learning from a given (training) data and implement that knowledge into another (new) data as we desire.

Your problem: (desired output)

  classify what type of flower a particular flower is?

There are thousands and thousands of types of flowers so, for simplicity I'm modifying you question as "classify if this flower is jasmine or not"

Input you fed to the perceptron are: (features)

  petal size, petal coloring, and leaf size

If you construct a perceptron (network) it will be:

$x_1, x_2, x_3$ are input neuron, $w_1, w_2, w_3$ are weights (mimicking the strength between biological neurons) and $Y$ is the output neuron.

You may have a question "Why 3 nodes (or neurons) in input and 1 node in output layer?" so I'm explaining that below:

3 neuron in the input layer as we have 3 features(or inputs).

1 neuron in the output layer as we have 1 class (jasmine or not).

Input layer have 3 nodes which will carry you features to output neuron which will classify if its jasmine or not.

Unlike other classification methods, here we should teach the system (like a human brain learns when we first see a jasmine flower).

How will a computer come to know if its a jasmine flower? Answer is, by showing sample features (petal size, petal coloring, and leaf size) of many jasmine to it.

Note: In biology neural network, the neuron get activated when electric impulses exceeds a threshold. Mimicking it, we use a threshold function to active(output one) or not(output zero) a artificial neuron[ threshold value = $\theta$ ].

If the input is a jasmine flower, output neuron will output '1' else '0'.

$
Y =
     \begin{cases}
       \text{1,} &\quad\text{if $\sum_{}^{} w_ix_i>\theta $}\\
       \text{0,} &\quad\text{else}\\
     \end{cases}
$

Note: When we consider $w_i$ and $x_i$  as vector ($W$ and $X$ respectively) its can be written as $Y=W^tX$ (you mentioned it as objective function).

We give sample features (petal size, petal coloring, and leaf size) of jasmine to input neurons $x_1,x_2,x_3$ respectively and tell its a jasmine(set output as one). Meanwhile, the weights $w_1, w_2, w_3$ take some random (initial) values and output $Y$ is found. As we have given a jasmine data to input neuron we expect the output to be one but as weights are taken in random, the output wont be one and an error $E$ is formed.

$E =|ExpectedOutput - ActualOutput|$

This error is propagated back, so that according to the error the weights $w_1, w_2, w_3$ can be updated such that next time error will be much lesser or zero.

This process is called Training, the data used to train the perceptron is called Training data and the network after training is called trained network. The training is called back-propagation algorithm.

It learns from the training data we provide and this trained network can easily classify a new flower(can tell if its jasmine or not).

Read these : Biological neural networks, NPTEL Artificial intelligence, MIT Introduction: The Perceptron


Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language
$$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$
is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$.

You mention a confusion between grammars and languages. By definition, a language is $\mathrm{LL}(k)$ if it has an $\mathrm{LL}(k)$ grammar. To show that a language is not $\mathrm{LL}(k)$, you have to show that it has no $\mathrm{LL}(k)$ grammar.


Can Eve impersonate Alice or Bob by using a replay attack?

well, you don't really explain what happens in each step, and how the authentication procedure works, but your first suggestion is at the right direction. However, the impersonator wishes to authenticate himself, so the attack should actually be

$1. A \rightarrow E(B) : A, K_{AB}${$N_A$}
$2. E(A) \rightarrow B : E(A), K_{AB}${$N_A$}
$3. B \rightarrow E(A) : B, N_A, K_{AB}${$N_B$}
$4. E(B) \rightarrow A : E(B), N_A, K_{AB}${$N_B$}

and you are missing the last reply, but it is easy to see that Eve can generate both $N_A$ and $N_B$ and thus succeed with authenticating itself.
Try to write it more carefully: what exactly is begin sent at each step (i.e., what is the meaning of sending "A"?), and what verification each side performs at each step.

For the second example, such an attack cannot work. The identity $A$ is included inside the encryption, and Eve has no way to replace it.


Is there any relationship between grammar being ambiguous and the language itself?

There exist context-free languages which have no unambiguous grammar. Such languages are called "inherently ambiguous".

On the other hand, there is no such thing as a language which does not have an ambiguous grammar; any grammar can be made ambiguous by duplicating some or all of the non-terminals.

The fact that inherently ambiguous languages exist is interesting, but they rarely if ever show up in real-life parsing problems.


How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable?

Your enumerator is incorrect. Because there are infinitely many Turing machine descriptions in $G$, the loop corresponding to Line 3 will not halt, so i will never be increased. Also, Line 3.2 may not halt too.

The correct enumerator is:

E' =
for i = 1 to infinity:
    Run E, the enumerator of G, to get the ith description of Turing machine <Mi>
    Build an enumerator Ei for Mi
    for j = 1 to i - 1:
        Run Ej to get the ith string, print it
    Run Ei to get the first i strings, print them

Suppose $E_i$ prints $s_{i1},s_{i2},\ldots$ in order. Then after $i$ iterations, $E'$ would have printed $s_{11},\ldots,s_{1i},s_{21},\ldots,s_{2i},\ldots,s_{i1},\ldots,s_{ii}$ (note this is not the order they are printed), and would print $s_{1(i+1)},s_{2(i+1)},\ldots,s_{i(i+1)},s_{(i+1)1},\ldots,s_{(i+1)(i+1)}$ in order in the $(i+1)$th iteration. Of course, before printing a string, you can check if it has been printed to avoid duplicates.


Physical significance of pumping length in pumping lemma

First, in the Pumping Lemma as I know it, there is no such thing as the pumping length for a language. "For every regular language $L$ there exits a constant $p$ such that for any string  $w\in L$ with $|w|\ge p$ ...". In fact, if $L$ satisfies pumping length $p$ then it will also satisfy any pumping length larger than $p$. (This is not completely trivial, the requirements in the dots ... above mention $p$ again.)

So we can call the smallest length $p$ for which the pumping property holds "the" pumping length. This is indeed a property of the language. If I am right the pumping length for $L = a(aa)^*+b(bb)^*$ is three. Strings of length 3 and above can be "pumped".

As you observe yourself, every regular language can be pumped (well, that is what the Lemma states). And the proof may use any automaton for the language. Whenever a string is at least as long as the number of states in the automaton, its computation must repeat a state, and we can pump. We can use the smallest automaton for the language, to minimize the pumping length. That smallest deterministic automaton is in fact well-defined. Unfortunately this in general still does not fix the (minimal) pumping length. An automaton for $L$ above seems to use at least five states (and actually 6 if it must be deterministic).

But still the property seems tied to the regular language via a certain "minimal" automaton, and the length of strings that ensure repetition of states.

But hey, even non-regular languages might in fact be pumpable: the Pumping Lemma (or better Pumping Property) is not a characterization of the regular languages. See for instance "Languages that satisfy the pumping lemma but aren't regular?" where it is observed that languages of the form $c L\cup \{ c^k \mid k\neq 1 \}\cdot\{a,b\}^∗$ for any $L\subseteq \{a,b\}^*$ have the Pumping Property (for pumping length one or two, I believe).
I do not know a "physical" significance in the nonregular case.


The original conception of propositions-as-types did not distinguish propositions and types at all: all types are propositions. Under this view, we may indeed speak of different proofs of a proposition.

One way to understand the differences between different conceptions of propositions-as-types is to view them as capturing different notions of provability and truth:

If we say that Prop = Type then the elements of a proposition are the proofs, so we are capturing proof constructions. We may analyze proofs, and for instance distinguish them according to their size, the assumptions they use, etc.
If we say that Prop = HProp then the elements of a proposition witness existence of proofs (but are not specific proofs), so we are capturing provabillity. We can still discern the reason for a proposition being true, because we can analyze the proof as lons as further constructions do not depend on the choice of proof.
If we use the strict SProp which makes all proofs judgmentally equal (or simply erases proof altogether), then inside type theory we can never "discern" the reasons for a proposition being true, so this is more like truth, i.e., an external reason for something being the case. We do have soundness in the sense that type theory can express semantic entailment, e.g., if $p$ and $q$ are true then so is $p \land q$.

Coqs Prop is conservative in the sense that it makes no commitment as to what Prop is supposed to be. Coq is compatible with the view that Prop is an (impredicative) Type, as well as that it is something like HProp, or even just bool. This is a design decision.


A commonly-used symbol for the set of all heads of directed edges?

In Graphentheoretische Konzepte und Algorithmen by S. Krumke and H. Noltemeier, they introduce for an edge $e = (u,v)$ two functions

$\qquad\alpha(e) = u$ and
$\qquad\omega(e) = v$.

The inspiration is probably alpha = beginning and omega = ending. I have no idea if they invented it, or where they took it from, or how widely adapted this notation is.

But then, which symbol or name you use for the function does not matter. Just define it -- I doubt anybody would reference something that basic.

Using the standard lifting of functions to sets, we get

$\qquad\displaystyle \alpha(E) = \bigcup_{e \in E} \alpha(e)$

for any set $E$ of edges; similarly for $\omega$.


Thanks for your answers!
I looked into both connected components in an undirected graph and the Disjoint set and went for the latter.
After researching this dataset I found a few packages that provided an implementation, but I used this one:

https://github.com/nawatts/disjoint

I'm a junior developer and haven't really come in contact with this kind of problems so your points in the right direction are very much appreciated.


How is a grammatical rule applied if the variable is not part of the source word

When we write $a^n(BC)^n$, we mean the word composed of $n$ copies of $a$ followed by $n$ copies of $BC$; using $^n$ is just a shortcut. For example, $a^2(BC)^2$ is shortcut for the word $aaBCBC$. Indeed, $^n$ just doesn't belong to the syntax of words, which states that a word is a sequence of terminals and non-terminals.


What does least fix point and greatest fix point mean in Safety games

Probably the most common fixpoint expressions in model checking are things like $\mu X.A\cup(B\cap\circ X)$ and $\nu X.A\cap(B\cup\circ X)$, where $\circ$ is some flavour of "next state" operator. That is, the least $X$ such that $X = A\cup(B\cap\circ X)$, and the greatest $X$ such that $X = A\cap(B\cup\circ X)$, respectively. More generally, we are talking about fixpoints of monotonic set transformers, i.e. functions $P({\cal S})\to P({\cal S})$ operating on the subsets of a given set $\cal S$.

An intuitive way of thinking about least fixpoints is that they represent sets constructed bottom-up using constructors. Suppose you wanted to define the natural numbers as a subset of the reals: $n$ is a natural number iff it is $0$, or the successor of another natural number. This means that $\mathbb{N}$ is a fixpoint of the set transformer $F:S\mapsto\{0\}\cup succ(S)$. This is not enough, though: the set of all real numbers is also such a fixpoint. $\mathbb{N}$ is the least fixpoint, though, meaning that it only contains those elements which it has to in order to be a fixpoint. Computationally, this fixpoint is the limit you obtain by iterating the given set transformer $F$ on the empty set, gradually assembling the elements of $S$, i.e. the limit of $\emptyset,F(\emptyset),F(F(\emptyset)),\dots$.

In the case of $S:=\mu X.A\cup(B\cap\circ X)$ this means that $S$ contains exactly those elements which can reach $A$, satisfying $B$ until they get there; not requiring the least fixpoint would mean that you could additionally have arbitrary $B$-cycles, infinite $B$-paths never satisfying $A$, etc in your set.

For greatest fixpoints, you have the dual situation: the set contains all elements which are not explicitly eliminated by the given conditions. For $S=\nu X.A\cap(B\cup\circ X)$, this includes any element which satisfies $A$, and either also satisfies $B$ or has a successor in $S$. We pick the greatest fixpoint because we want to include everything which doesn't violate the requirements. Otherwise we might end up with an excessively restrictive set (such as the least fixpoint, which is just $A\cap B$ in this case). Computationally, this is the limit you get by iterating the transformer on the full set $\cal{S}$ of states, gradually eliminating all which fail the specification, i.e. the limit of ${\cal S},F({\cal S}),F(F({\cal S})),\dots$.


Greedy algorithm for even item distribution

It looks like a greedy algorithm cannot do it alone.

Here is an approach based on binary search.

Suppose we have a subroutine to determine that if it is possible to have a chocolate supply of $s$ after the truck driver has hauled between the stores, given $s$. Note that if $s$ is possible, than $t$ is possible for any $t<s$.

Let $m$ be the maximum among $c_i$. Let us check if $m/2$ is possible. If yes, let us try $(m/2 + m + 1)/2$. (+1 to ensure we will try $m$ just in case). If no, check $m/4$. I believe you can see the rest of binary search algorithm. Be careful with various boundary cases.

Now the problem is how to build that subroutine? We can think recursively. Let $s$ be given. If $c_1>s$, we will use a truck to move $c_1-s$ chocolates to $p_2$. Whatever is left when the the truck has reached $p_2$ will be added to $c_2$. So we got $c_2'$. If $c_1=s$, $c_2'=c_2$. If $c_1<s$, compute $d_2$, the least amount of the chocolate needed to be carried on a truck that starts from $p_2$ can reach $p_1$ to increase $c_1$ to $s$. Subtract that amount from $c_2$ and get $c_2'$, which might be negative. We can see that $s$ is possible initially if and only if $s$ is possible for $c_2', c_3, \cdots, c_n$ at $p_2,p_3,\cdots, p_n$ respectively.

There should be enough hint above. I will let you finish the rest of work.


Will ternary computers be faster than binary?

It depends. A number represented in base 3 will have fewer digits than the same number in base 2. Perhaps this means computations will be faster, since you have to work with fewer digits. However, perhaps the operations will become slower (since they're more complicated) so there might be no net gain - or perhaps even worse performance! There's no way to tell how fewer, complicated operations will compare to more, but simpler operations.

Another consideration is arithmetic. If you are working in base 10, then division by 10 is really easy with divisions in other bases being more work. Similarly, in base 2, division by 2 is easy. In base 3, division by 3 would be easy. If your application requires frequent division by 3, then base 3 would be beneficial.


How to show that the product of two binary numbers can be determined in AC1?

Multiplication can be done even with stronger restrictions, like $AC^1$ with bounded fan-in.

Proof is little hard to typeset here, but I will outline the sketch and give a link.

You shall prove, that addition of two m-bit numbers have $O(m)$ size and constant depth circuit and thus is in $AC^0$. This is pretty simple (start with looking for $O(m)$ depth and then simplify)
Then you need to generalize this result to addition of many m-bit numbers and show that it have logarithmic depth and thus in $AC^1$
And finally what you are looking for (product in $AC^1$) is simple corollary

Look into those lecture notes for example, where this proof is done in great details.


LTL Logic Finally, Globally and Until to irreflexive Version

Sorry, I misread your question at first as wanting to express the irreflexive variant using the reflexive variant (which could be done with the next operator). You don't actually need the next for the other direction.

I'm making the following assumption: By $w^{(i)}$ you mean the suffix of $w$ starting at the $i$ symbol, so for $w = w_0 w_1 w_2 \dots$, you have $w^{(i)} = w_i w_{i+1} w_{i+2} ...$

Then for all $w \in L$, you have:

$w \models F\varphi \Leftrightarrow w \models \varphi \lor F^+ \varphi$.
$w \models G \varphi \Leftrightarrow w \models \varphi \land G^+ \varphi$.
$w \models \varphi_1 U \varphi_2 \Leftrightarrow w \models \varphi_2 \lor (\varphi_1 \land (\varphi_1 U^+ \varphi_2))$.

If you want to show this formally, it follows directly from the definitions:

For 1. you have:

$\begin{align*}w \models F \varphi &\Leftrightarrow \exists i \geq 0: w^{(i)} \models \varphi \\ &\Leftrightarrow \exists i > 0: w^{(i)} \models \varphi \quad \text{ or } \quad  w^{(0)} \models \varphi \\ &\Leftrightarrow  w \models F^+\varphi \text{ or } w \models \varphi \\ &\Leftrightarrow w \models \varphi \lor F^+\varphi \end{align*}$

The argument for 2. is symmetric to 1.

For 3. you have (pay attention to $\leq$ vs $<$):

$\begin{align*}w \models \varphi_1 U \varphi_2 \Leftrightarrow & \exists i \geq 0 \forall 0 \leq j < i: w^{(j)} \models \varphi_1, w^{(i)} \models \varphi_2 \\ \Leftrightarrow & \exists i > 0 \forall0 \leq j < i: w^{(j)} \models \varphi_1 , w^{(i)} \models \varphi_2 \quad \text{ or } \quad w^{(0)} \models \varphi_2\\
\Leftrightarrow (& \exists i > 0 \forall0 < j < i: w^{(j)} \models \varphi_1 , w^{(i)} \models \varphi_2 \quad \text{ and } \quad w^{(0)} \models \varphi_1) \quad \text{ or } \quad w^{(0)} \models \varphi_2 \\
\Leftrightarrow (&w \models \varphi_1 U^+ \varphi_2 \quad \text{ and } \quad w \models \varphi_1 )\quad \text{ or } \quad w \models \varphi_2 \\
\Leftrightarrow & w \models \varphi_2 \lor (\varphi_1 \land (\varphi_1 U^+ \varphi_2))\end{align*}$

If you would have wanted to do the other direction, as I thought initially:

$w \models F^+ \varphi \Leftrightarrow w \models XF \varphi$
$w \models G^+ \varphi \Leftrightarrow w \models XG \varphi$
$w \models \varphi_1 U^+ \varphi_2 \Leftrightarrow w \models X(\varphi_1 U \varphi_2)$.

To show this formally, the argument would be similar to before.

When you combine both directions, this transformation is sometimes referred to as "unrolling", i.e. expanding $F \varphi \equiv \varphi \lor X F\varphi \equiv \varphi \lor X \varphi \lor XXF \varphi \equiv ...$ and $G \varphi \equiv \varphi \land XG \varphi \equiv \varphi \land X \varphi \land XXG \varphi \equiv ...$ etc.

Regarding your comment (not 100% sure if you were joking): $\lnot X$ is not $-1$ or "going backwards". You have $w \models \lnot X \varphi \Leftrightarrow w^{(1)} \not \models \varphi$. In other words, if you think in terms of Kripke structures and of $w$ as the vertex-label sequence of a path in this transition system, then $\lnot X \varphi$ means "in the next state, $\varphi$ does not hold".


How to create new language with languages $L_a = \{a\}, L_b = \{b\}$ and set operations?

Part 1. is ok. The idea behind is that you have to take the letters 2 by 2 and then make the star closure. Call $L_e$ the language of even words you just defined.

Part 2. Assume for a moment to have defined $L_o$ the language of words of even length from $L_a$ and $L_b$. Then to have even length and different initial and final letter you can just define

$L=L_a\cdot L_o\cdot L_b\cup L_b\cdot L_o\cdot L_a$

Remark that words in $L$ have length at least 3 since $a$ starts and finish with the same letter...

To define $L_o$ the idea is that an even word is just to exploit $L_e$:

$L_o=L_a\cdot L_e\cup L_b\cdot L_e$.


Solving a modified Travelling Salesman Problem(TSP)

As mentioned in the comments, you can compute APSP (All-Pairs Shortest Paths) at first and build the matrix $$D:=\left(d_{ij}\right)_{i,j\in[n]}$$, where $d_{ij}$ is the length of a shortest path from the vertex $i$ to the vertex $j$. By solving the usual travelling sales man on the graph $G'$ where $D$ is the adjacency matrix, you get a solution for your version of the problem. Try to see why this works as an exercise.

Your case is actually mentioned in the Wikipedia page under metrics.

Note that $D$ defines a metric and metric TSP admits a polynomial time 1.5-approximation. The same Wikipedia article contains more information about this algorithm under the section "Constructive heuristics".


Why does a color video compress better than a black and white video?

Human eye is very sensitive to luminance change and order of magnitude less sensitive to chrominance change.
MPEG under the hood is based on JPEG transform, so you have 8x8 blocks of DCT.
It blurs a bit the whole block approximating it. Colour space changes to YUV or YCbCr, to encode two channels of colour and one of luminance.
Luminance (grayscale if it was colour) is not compressed as much as new created two colours. These colours are fitted more loosely than luminance.
The most heavy tricks are in colour space and luminance is preserved with lower compression (and less stages).

If you have BW frame it cannot be dealt with high compression as this faster degrades quality. MPEG was not created to deal with BW data. Origins of this codec are from times when grayscale tv was appended colour on top of existing frame.
Here I mean origins, not the same scheme as bandwidth was smaller at this time, I am referring to colour space and compression over chrominance.

MPEG popular scheme is 4:2:2 which encodes four parts of luminance (BW) and two times two colour parts. Colour is encoded as differences, because there are two channels and three colours.
So simply 50% of data is well preserved luminance and 50% are three colours with higher compression ratio. Compressed better means greater ratio of original vs processed channel.
Luminance takes (taking it simple as luminance is part of these colours) roughly equal space as colour info.

Different codecs are using different strategies, I referred to MPEG, not some new mixed schemes.


I'll join your potential downvote-fest with a speculation-filled answer.

Here are two Expert System algorithms I've worked with in industry.

Rete Algorithm:

https://en.wikipedia.org/wiki/Rete_algorithm

IBM and Oracle both have large Rete systems.

From what I've experienced, these are rules and fact tables that can be exeucted as a single atomic rule, or a million rules all on the same problem.  In my case we expressed these rules as tables of values, and IF/ELSE logic rules that can be grouped and managed and revised and controlled.

General Problem Solver

https://en.wikipedia.org/wiki/General_Problem_Solver

My impression is GPS is more flexible, and better handles the "fuzzy logic" cases and "precedence rules" (Where the answer changes when you reoder the precedence of the rules).

From my experience, I expressed these rules as small LISP functions where the tool could chose the "best" answer even if there still were unsolved values in the LISP functions.

If I'm allowed to just blindly guess:

My guess just from my gut feel, is that he's using Jess:

http://www.jessrules.com/


Is the halting problem specific to Turing machines?

The halting problem applies to any model of computation: you can always ask, "Given this machine and this input for it, does the machine halt?" Indeed, for any two models of computation $A$ and $B$, you can always ask the more general question, "Is there an $A$-machine that, given a description of a $B$-machine and its input, determines whether that machine halts?" Often, we take $A=B$.

What does vary between machine models is decidability of the halting problem.  If we say "decidable" on its own, it means Turing-decidable, i.e., model $A$ above is Turing machines. For, e.g., $B$ is DFAs or PDAs, the halting problem is decidable: the machine always halts because it halts when it reaches the end of its input, the input is finite and the machine consumes one character of input at every step. For $B=$Turing machines, the well-known diagonalization argument proves undecidability, and this extends by reduction to any Turing-equivalent model of computation.  That is, any model of computation that can simulate and be simulated by Turing machines.

The diagonalization proof has few assumptions – see Wikipedia for more details. There needs to be a coding of machines so they can be used as inputs to the machines themselves and the machines need to be able to simulate an "if" statement, loop forever, return a value, duplicate a value and be closed under subprograms (i.e., the model wouldn't become more powerful if you let machines call each other as subroutines). Therefore, no model of computation that has these properties can decide its own halting problem.

Note that this includes any model that can simulate a Turing machine, even if that model is more powerful. For example, consider the class $H$ of Turing-like machines with an oracle for the Turing machine halting problem. That is, the machines operate just like Turing machines but have a special instruction that can look at the tape and give an immediate yes or no answer to the question, "Does the ordinary Turing machine described there halt on the input described?" Thus, the machines are more strictly powerful than ordinary Turing machines. These oracle machines cannot decide their own halting problem, by the same diagonalization proof as for ordinary Turing machines. In fact, there's a strict, infinite hierarchy of machines: consider machines $H'$ that have an oracle for the $H$-halting probem, and then machines $H''$ with an oracle for the $H$-halting problem and... See Turing degree and the arithmetical hierarchy for more on that.


Why there aren't any famous programming languages that implement what Alan Kay considers to be "real OOP"?

"OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things. It can be done in Smalltalk and in LISP. There are possibly other systems in which this is possible, but I'm not aware of them." - Alan Kay.
I would like to point that there is no single evidence of term OOP being coined by Alan Kay (if you find one, please share).

About C++ Alan gave statement: "I invented the term object-oriented, and I can tell you that C++ wasn't what I had in mind".

Other languages that may fall into "real OOP" is self programming language and probably Squeak and Objective-C.

When languages switched from messages to params passing, becoming bidirectional, it broke initial assumptions. Alan have pointed flaws in Simula design, so this one also do not count.

It is impossible to say that some languages are "better" than others, but being "real OOP" according to definition is some road taken by one influential author. Term OOP and class based programming was introduced in Simula, long before "real OOP" was supposedly coined.

All modern languages took other road and "modern OOP" is more down-to-earth, no asynchronous agents passing messages, microservices with own memory, everything being object by default.

Since there are performance hits in every step and there is no single reference gathering what it should do beside notes like actor-based programming is a way to go, because programmers should consider interactions of objects and interactions with users, we can safely assume "real OOP" by Alan Kay is only about road taken by him and not really implementable by others, so only smalltalk and squeak may be truly covered and other languages followed more pragmatic, expressive and performant way.


What Properties Matter For the Bound on Generalization Error of Hypothesis Set?

Rademacher complexity is also a tool used to bound generalization error.


Proof of Strong Duality Via Farkas Lemma

The following is based on the book "Combinatorial Optimization" by Papadimitriou and Steiglitz (chapter 3)

On LP duality, they first state a theorem that when a LP has a feasible solution, the dual also has one and on optimality their costs are equal (Theorem 3.1 in the book, based on the simplex algorithm)

This follows from the fact that the dual cost is always dominated by the primal cost.

i.e let $x$ and $\pi$ the solutions to the primal and dual respectively, then (i.e $c'$ is transpose vector of $c$)

$$c'x \ge \pi'Ax \ge \pi'b$$

So if the primal has a feasible solution so does the dual and on optimality they (the costs) are equal.

Then the Farkas Lemma (theorem 3.5 in the book) is proved based on this theorem.

But one can reverse the proof of Farkas Lemma in the book and prove Th. 3.1 from Farkas Lemma (Th. 3.5)

A sketch:

Farkas' Lemma states that (as stated in book):

  Given vectors $a_i \in R^n$, $i = 1,..m$ and another vector $c \in R^n$,

  iff $y'a_i \ge 0, \forall i \implies y'c \ge 0$, then $c \in C(a_i)$
  (i.e $c$ is in the cone generated by $a_i$)

Consider a LP:

$$\min{c'y}$$
$$a_i'y \ge 0, i =1..m$$
$$y \ne 0$$

The LP is feasible and bounded because $y = 0$ is a feasible point and $c'y \ge 0$ (by the lemma)

$c$ can be expressed as linear combination of the $a_i$'s using a vector $\pi$, where $\pi_i \ge 0$, i.e

$$c = \sum_1^m{\pi_i a_i}$$

Constructing the dual of the LP as:

$$A_j = col(a_{ij}, i=1..m) \in R^m$$
$$a_i = col(a_{ij}, j=1..n) \in R^n$$

gives the dual LP:

$$\max{0}$$
$$\pi'A_j = c_j, j = 1..n$$
$$\pi \ge 0$$

which has a feasible solution ($\pi$) and equal cost at optimality (strong duality theorem)


What are some examples of problems whose deterministic versions are easy, but become hard when injecting some uncertainty?

Linear Quadratic Regulation is a standard control-theoretic problem that is easy when deterministic. The problem is to minimize a quadratic cost while steering a linear system:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic_regulator

Interestingly, the problem remains easy when additive Gaussian noise disturbes the system and your observations of it:

https://en.wikipedia.org/wiki/Linear%E2%80%93quadratic%E2%80%93Gaussian_control

However, the problem becomes hard as soon as the noise is non-Gaussian (or even multiplicative Gaussian).


How is a hypergraph different from a bipartite graph?

Essentially, a hypergraph may be "nice" in some sense, but there may be no equivalent (or at least natural) corresponding notion of niceness for the associated bipartite graph.

One way to approach the question is by analogy with graphs.  Every graph can be represented by its incidence graph, a bipartite graph with vertices in one partition, and edges in the other.  Yet we seldom want to use this "standardised" bipartite representation of graphs, for a variety of reasons.  The same reasons (and more) apply to keeping hypergraphs as they are.

You comment below that this analogy with the graph case was your starting point.  Perhaps we have a different set of intuitions about why turning every graph into a bipartite graph is unnatural, so instead let me try another tack.

First, there are many different notions of what a hypergraph is, depending on the application.

One rather general definition is a set system, which allows the set of edges of the hypergraph to be a subset of the powerset of the vertices.  This allows empty edges, edges with size one, edges that are strictly contained in other edges, and some vertices may also not participate in any edge.  There are versions of hypergraphs that disallow some combination of each of these "features".  These features are important for some applications, and authors tend to rely on them implicitly, so it is worth checking the definition each time.

The best reference I know is Berge's book.  Note that it is essentially a reprint of the second half of his 1973 book on graphs and hypergraphs, and is quite hard to use: it is a useful reference but I can't wholeheartedly recommend it.  Berge requires in a hypergraph that there are no empty edges and that every vertex should be part of some edge, but allows repeated edges (giving a multiset of subsets of the powerset).  He calls a hypergraph with no edge contained in another a simple hypergraph.

Claude Berge, Hypergraphs: Combinatorics of Finite Sets, 1989, Elsevier.

If one disallows edges that are contained in other edges, but allows empty or singleton edges and repeated edges, then the dual graph of the hypergraph that you describe (usually called the incidence graph of the hypergraph, or sometimes referred to as its Levi graph) is a bipartite graph.  Further, the hypergraph can be reconstructed from its incidence graph.

Sometimes this is perfectly appropriate.  However, useful things do get scrambled if one breaks this particular shell.  As an example, various notions of colouring are interesting for hypergraphs, but these are highly unnatural in the bipartite graph setting.  Many other properties of classes of hypergraphs are also scrambled going to the incidence graph.

Perhaps the best part of Berge's book is its continual insistence (with many examples) that hypergraphs really are worth studying, and that they do nontrivially extend graphs.

Edit: clarified terminology, as suggested by vzn's answer.


What you describe is a sort of recursive merge which generalizes merge sort, and indeed results in the advertised complexity. The pointer procedure which you are trying to describe is usually just called merge.

Another approach is using a min-heap of size $k$, which stores the current "contenders" for the $k$ smallest elements. It is initialized with the smallest elements of each of the lists, and at each step you pop the smallest element and add it to the merged array, replacing it with the next smallest element in the corresponding list.


Sorted-greedy for Load Balancing Problem

Take for instance $m=2$ machines and $n=5$ jobs with processing times $4,3,3,2,2$.

The optimal schedule puts $4+3$ on one machine and $3+2+2$ on the orther machine.
Sorted-greedy assigns $4$ to the first machine, $3$ to the second machine, $3$ to the second machine, $2$ to the first machine, $2$ to the first machine. Hence the loads are $4+2+2$ and $3+3$.


Worst case, if the second call to rand() returns 0 and the first call doesn't, you get a floating point division by zero, and if you are using standard IEEE 754 arithmetic, the result is +infinity. In that case, the loop will run forever.

If you changed your code to exclude that case, and exclude the case that rand () might return a 128 bit integer, then for any implementation the size of x is limited, so the number of multiplications by 0.8 is limited, so the runtime is O (1).


IF A is reduced to B and B belongs to NPC then where does A belongs to?

If A reduce to B and B belongs to NPC, then surely A is in NP, but may or may not be NPC. A belongs to P is another question. If there given P = NP, then A would be belongs in P also.


How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

Your method is fine.  You just need to know how to do modular division.  Modular division is a bit different from division of two integers.  You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$.  You can compute the modular inverse using the extended Euclidean algorithm.

See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula.  To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.


Which addressing modes permits relocation without any change whatsoever in the code?

Code relocation can be done whenever addresses are not directly specified in the program (absolute), but are relative to some variable or other modifiable source.

In the 2 modes that you correctly specified as able to support relocation of code and data, the effective address is calculated based on the value loaded in another register.

For 3), base addressing, a register points to the base of the structure and the effective address is obtained by computing an offset from the base.  The base address register can be loaded at run time to point to the base of the structure so the code doesn't have to be modified.

For 4), PC relative, the effective memory address is obtained by computing an offset from the current PC.  No matter where the code is loaded in memory, the offsets are always the same so the code needs no modification.

Now the other 2 selections are a little more tricky.
1. Indirect addressing. This supports relocatable code since the effective address is determined based upon the contents of the initial load.  Code and data can move but with a data structure containing pointers to the code and/or data being at a fixed address. For example, the operating system may define that a pointer to the system's CPU database is always located at address 80002000, but the CPU database can be loaded at any address.    You COULD argue that the entire program is not relocatable because the pointers are at fixed locations, but really relocation is the one of the purposes of this addressing mode.

Indexed Addressing.  This depends upon a bit more definition of the term.  If you mean indexed ABSOLUTE mode, then no, I wouldn't consider this to be a mode that supports relocation.  In this case the effective address of data is based on an offset from a literal fixed address (ex: 1000 + R5).  In order to relocate this data (or code) the literal address would have to be changed in the code.  If it's indexed relative to a base register, then yes it supports code relocation since the base register can be loaded at run time.


Optimizing electoral votes in a political simulation... 200,000+ possibilities, how to run through them?

200000 is not a terribly large number, a brute force solution in Python would probably run in reasonable time. You'd have to implement a function that calculates your influences depending on your answers to the 14 issues and then just check all the possibilities. Python has some nice library functions that can help in the itertools package, but programming questions should better be asked on Stackoverflow.

A solution that is requires more learning to implement would writing down the problem as an Integer Linear Program and feeding it to a solver. That would probably scale much better than a naive brute force solution. It also sounds more sciency. But as I said, your problem instance is reasonably small.


If RAM is a Random Access Machine (i.e., a rudimentary computer with registers, memory and assorted instructions), the answer is just "build a DFA that recognizes the same language, simulate that DFA in code". I.e., have a transition table that tells you the next state for each combination of state and input symbol; start in the start state, check if the state after consuming all input is final.
More abstractly: RAM is equivalent in computing power to a Turing machine. As regular languages are decidable, they can be decided by a (deterministic) Turing machine or a RAM.


Size of neighborhood in local search for symmetric TSP

Let $\delta_{n,k}$ be the number of ways to select $k$ nonadjacent edges on a path of length $n$. We can compute $\delta_{n,k}$ using a simple recurrence:

$\delta_{n,0} = 1$.
$\delta_{0,k} = 0$ for $k > 0$.
$\delta_{n,k} = \delta_{n-1,k} + \delta_{n-2,k-1}$, where the first term corresponds to the case in which the first edge is chosen, and the other to the case in which the first edge is not chosen.

We can solve this recurrence and obtain $\delta_{n,k} = \binom{n-k+1}{k}$. Indeed, this satisfies the two base cases, and the inductive case is just Pascal's identity $\binom{n-k+1}{k} = \binom{n-k}{k} + \binom{n-k}{k-1}$.

To compute $\gamma_{n,k}$, choose a first edge arbitrarily. If it is chosen, we are left with a choice of $k-1$ edges in a path of length $n-3$, and otherwise we are left with a choice of $k$ edges in a path of length $n-1$. In other words,
$$
\gamma_{n,k} = \delta_{n-1,k} + \delta_{n-3,k-1} = \binom{n-k}{k} + \binom{n-k-1}{k-1}.
$$
This gives
$$
\begin{align*}
\gamma_{n,0} &= 1, \\
\gamma_{n,1} &= \binom{n-1}{1} + \binom{n-2}{0} = (n-1) + 1 = n, \\
\gamma_{n,2} &= \binom{n-2}{2} + \binom{n-3}{1} = \frac{(n-2)(n-3)}{2} + (n-3) = \frac{n(n-3)}{2},
\end{align*}
$$
and so on. Note that there is a difference in normalization: you count the edges with order, and I count them without order. This explains the factor of 2 in $\gamma_{n,2}$. In general, to take the order into account you need to multiply $\gamma_{n,k}$ by $k!$.


Difference between := and ← in pseudocode

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.


CNN/Neural Network: Can I still estimate 3 parameters if my input data has insufficient parameter labels?

Yes, this can be done.  Basically, you define a custom loss function, and then train the neural network to minimize this loss function.  In particular, you construct a single neural network that has 3 outputs; the first output is a measure of symmetry, the second of repetitiveness, and the third roundness.  The custom loss function should look at the output for which you have a known label and penalize the model according to how much that output is in error (it ignores the other 2 outputs).  For instance, if you are currently using mean-squared error, your custom loss function would be equal to the square of the difference between the known label and the corresponding output of the network.  This custom loss function is differentiable, so all the standard training methods (backpropagation, gradient descent, Adam solver, etc. etc.) work directly, with no modifications needed.

Many libraries for training neural networks will let you specify a custom loss function.


Does the memory get unallocated when program exits?

When you run your program its memory allocations take the form of page allocation requests to the operating system.  When your program terminates, the operating system notices and returns all the allocated pages to the list of free pages, which can then be used by other processes.  It does not matter if your program leaks memory (other than potentially using more memory as a result), because ultimately the operating system will reclaim everything.


BFS implementation: queue vs storing previous and next frontier

Your analysis is correct.  There is no major disadvantage of the two-list approach you outline.

One nice thing about the queue-based formulation of BFS is that it makes it easier to see the relationship to DFS and Dijkstra's algorithm.  Start with the queue-based formulation, and replace the queue with a stack, and you get DFS.  Replace the queue with a priority queue, and you get Dijkstra's algorithm.  This similarity is aesthetically pleasing and might help understand the algorithm better.

A slight disadvantage of your two-list based scheme is that it has somewhat higher memory consumption: only a constant factor higher, so maybe not a big deal, but it is somewhat higher.  This is because when you're traversing the current frontier, you keep around the items in the list that you've already traversed even after you've finished traversing them.  In contrast, the queue-based method doesn't do that.

Nonetheless, in the big picture, you are absolutely right; both methods are pretty similar and there's not an overwhelming reason to prefer one over the other.


Let $X_1,\dots,X_n$ denote the scores of the individual members of the team.  Then the score $Y$ of the team is given by

$$Y = X_1 + \dots + X_n - \min(X_1,\dots,X_n).$$

So, by linearity of expectation, the expected value of the score of the team will be

$$\mathbb{E}[Y] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] - \mathbb{E}[\min(X_1,\dots,X_n)].$$

This suggests a natural approach.  Given a candidate list of members of the team, calculate the expected team score $\mathbb{E}[Y]$ using this formula.  Try all possibilities for the list of team members, compute the expected team score for each, and pick the one that has the highest expected team score.

The biggest challenge is to evaluate the above formula for a particular list of team members.  It is easy to evaluate $\mathbb{E}[X_i]$, but evaluating $\mathbb{E}[\min(X_1,\dots,X_n)]$ where $X_1,\dots,X_n$ are independent Gaussian random variables is challenging.  This is an order statistic, and there are various techniques for approximating its expected value.  One is to numerically estimate a certain integral.  Another is to use the approximation $-\Phi^{-1}({n-0.375 \over n+0.25})$, where $\Phi$ is the cdf of the normal distribution.  See J.P. Royston, Expected Normal Order Statistics (Exact and Approximate), Journal of The Royal Statistical Society Series C (Applied Statistics), vol 31 no 2, pp.161-165.  There may be better algorithms; hopefully this gives you the technical terms to use for searching.


Are partial recursive functions analogous to recursive languages or r.e. languages?

Let me quote from the second edition of the same textbook, section 9.1 (sorry, I don't have the first one):

  Recall that a language L is recursively enumerable (abbreviated RE) if L = L(M) for some TM M. Also, we shall in Section 9.2 introduce "recursive" or "decidable" languages that are not only recursively enumerable, but are accepted by a TM that always halts, regardless of whether or not it accepts.

Therefore recursive languages are associated to total recursive functions, not partial.

Hope this answers both the questions.

EDIT: to answer the comment:

On the one hand, the reason lies on intuition: the Church-Turing thesis is about capturing the intuitive idea of "effective computability" or "things that we can actually compute". Imagine a program that, if there is a correct answer then it computes the answer, otherwise it never halts (i.e. it gives an answer only if there is an answer). Would you say that such a program computes the answer or not?

But on the other hand, if this intuitive picture doesn't convince you,  consider the following (way more concrete): consider an effective enumeration $(\varphi_i)_{i\in\mathbb{N}}$ of all total recursive functions and consider the function $\varphi:=x\mapsto\varphi_x(x)+1$. Now it is clear that you can compute $\varphi$: you can find the $x$-th function, you can compute it (as it is recursive) and you can sum 1 (as sum is recursive). But $\varphi$ cannot be total by a diagonal argument: if it were total than it would have its own index $i$, therefore

$$ \varphi(i) = \varphi_i(i)+1 = \varphi(i) +1 $$

which is a contradiction. This problem vanishes if you consider instead partial functions.


Is rejection sampling the only way to get a truly uniform distribution of random numbers?

Yes and no, depending on what you mean by “the only way”. Yes, in that there is no method that is guaranteed to terminate, the best you can do (for generic values of $N$ and $R$) is an algorithm that terminates with probability 1. No, in that you can make the “waste” as small as you like.

Why guaranteed termination is impossible in general

Suppose that you have a deterministic computation engine (a Turing machine or whatever floats your boat), plus an oracle that generates random elements of the $R$-element set $[0..R-1]$. Your goal is to generate an element of the $N$-element set $[0,N-1]$. The output of your engine depends only on the sequence of values returned by the oracle; it is a function $f$ of that potentially infinite sequence $(r_0, r_1, r_2, \ldots)$.

Suppose that your engine calls the oracle at most $m$ times. There might be traces for which the oracle is called less than $m$ times; if so, calling the oracle extra times so that it is always called exactly $m$ times does not change the output. So without loss of generality, we assume that the oracle is called exactly $m$ times. Then the probability of the outcome $x$ is the number of sequences $(r_0, \ldots, r_{m-1})$ such that $f(r_0, \ldots, r_{m-1}) = x$. Since the oracle is a uniform random generator, each sequence is equiprobable and has the probability $1/R^m$. Hence the probability of each outcome is of the form $A/R^m$ where $A$ is an integer between $0$ and $R^m$.

If $N$ divides $R^m$ for some $m$, then you can generate a uniform distribution over $N$ elements by calling the random generator $m$ times (this is left as an exercise to the reader). Otherwise, this is impossible: there is no way to obtain an outcome with probability $1/N$. Note that the condition is equivalent to saying that all of $N$'s prime factors are also factors of $R$ (this is more permissive than what you wrote in your question; for example you can pick a random element among 4 with a 6-sided fair die, even though 4 does not divide 6).

Reducing the waste

In your strategy, when $r \ge k\,N$, you don't have to re-draw immediately. Intuitively, there's a bit of entropy left in $[k\,N .. R-1]$ which you can keep in the mix.

Assume for a moment that you will in fact keep generating random numbers below $N$ forever, and you generate $u$ of them at a time by making $d$ draws. If you do a straightforward rejection sampling on this grouped generation, the waste over $d$ draws is $\dfrac{R^d - k\,N^u}{d}$, i.e. the remainder $R^d \mathbin{\mathrm{mod}} N^u$ divided by the number of draws. This can be as little as $\gcd(R,N)$. When $R$ and $N$ are coprime, you can make the waste arbitrarily small by picking sufficiently large values of $d$. For general values of $R$ and $N$, the calculation is more complicated because you need to take into account the generation of $\gcd(R,N)$ and $N/\gcd(R,N)$ separately, but again you can make the waste arbitrarily small with large enough groups.

In practice, even with relatively inefficient random numbers (e.g. in cryptography), it is rarely worth doing anything but simple rejection sampling, unless $N$ is small. For example, in cryptography, where $R$ is typically a power of 2 and $N$ is typically hundreds or thousands of bits, uniform random number generation usually proceeds by straight rejection sampling in the desired range.


Evaluating two different Algorithms, which one will scale better?

You are not looking for asymptotic behaviour, but for actual runtime for rather large n; you determine how large.

You can either analyse both algorithms, and estimate what their run times will be, or much easier, you can measure it. You have to be very careful if you do this with an optimising compiler, because they tend to throw away operations if they can prove they are not actually used. But done carefully, this will give you the actual numbers.

Draw some graph showing the runtime depending on N. And be aware that different processors or different compilers can produce rather different results. Also be aware that if the time "jumps" for certain sizes of n, lets say 50n nanoseconds if n < 10,000, 100n nanoseconds if n < 1,000,000 and 200n nanoseconds if n > 1,000,000 then your time may be depending on memory access, and you can often improve time significantly be re-arranging operations.


What is the computer science interpretation of a qubit?

A qubit is a vector in a 2-state complex space. Its vector form is something like Qubit = $ax + by$, which by convention in Dirac notation is $|Q\rangle = a|0\rangle + b|1\rangle$, where $|0\rangle$ and $|1\rangle$ represent linearly independent basis vectors and the coefficients $a,b$ are complex numbers. $a^2$ and $b^2$ represent the probability of measuring 0 or 1, and they can take on any complex value as long as $|a|^2 + |b|^2 = 1$ (which must be true because we only have one qubit).
In this framework, the qubit acts like a vector pointing from the origin which  naturally evolves or rotates around the infinitely many surface points of a ‘Bloch Sphere’ except when it’s measured it only ever tells you 0 or 1 (which represent the north and south poles of the sphere).
In short, a qubit is a vector.
The ‘infinitely many’ language comes from the ability of $a,b$ to take on any complex value so long as their squares equal 1. Measuring a qubit (meaning when you read it, touch it, look at it, record its value etc) only gives you 0 or 1, not both and not a decimal in between.
If you also think of the qubit as a wave, then the goal of quantum computing is to take a superposition of all possible results of a qubit string (000, 001, 010, 011 etc), weight the components appropriately to constructively and destructively interfere with one another, so that at the very end you’re biased to get the right result... with a nonzero probability that you will get the wrong answer even if you do everything right.
Incidentally a string of three qubits, you’ll notice, is the tensor product of three qubit vectors. This creates a complex space with $2^3 = 8$ basis vectors which our 3-string qubit can happily explore.


Fast query on the number of elements in a quarter plane

A 2D Fenwick tree can solve this in $O(\log^2 N)$ time and $O(N^2)$ space for both update and query, when your coordinates are integers and $N$ is the size of the maximum coordinate.
Fenwick trees are nice for competitive programming because they have a really compact implementation, for example in C++:
typedef unsigned long long uw;
uw lsb(uw x) { return x & -x; }
uw  up(uw x) { return x + lsb(x); }
uw  dn(uw x) { return x - lsb(x); }

template<class T> struct Fenwick2D {
  uw n; std::vector<std::vector<T>> b;
  Fenwick2D(uw n) : n(n), b(n+1, std::vector<T>(n+1)) { }

  void increase(uw x, uw y_, T v) {
    for (; x <= n; x = up(x))
      for (uw y = y_; y <= n; y = up(y))
        b[x][y] += v;
  }

  T prefix_sum(uw x, uw y_) {
    T s = 0;
    for (; x >= 1; x = dn(x))
      for (uw y = y_; y >= 1; y = dn(y))
        s += b[x][y];
    return s;
  }
};

And this shows your example from the question:
int main(int argc, char** argv) {
    Fenwick2D<int> fw(4);
    fw.increase(1, 1, 1);
    fw.increase(2, 2, 1);
    fw.increase(1, 2, 1);
    fw.increase(3, 2, 1);
    std::cout << fw.prefix_sum(1, 1) << "\n";
    std::cout << fw.prefix_sum(2, 2) << "\n";
    std::cout << fw.prefix_sum(3, 3) << "\n";
    return 0;
}

This data structure is more general than your problem as well. In general it can increase any grid element $g_{x,y}$ by value $v$ (which decreases for negative $v$), and ask the value of the lower quadrant prefix sum $\sum_{i\leq x}\sum_{j\leq y} g_{i,j}$ for any $x, y$. Note that this means you can get area sums as well using 4 queries by the inclusion-exclusion principle.


What is the correct algorithm to see whether N points lie on the same side of a line?

A quick theorem, in general:

A hyperplane in $\mathbb{R}^d$ can be defined by a vector
$\mathbf{v}$ and scalar $b$ as the set of points $\mathbf{x}$ such that $\mathbf{v}^T\mathbf{x} =
b$. It splits the
space $\mathbb{R}^d$ up into two half-spaces, one where $\mathbf{v}^T\mathbf{x}
\geq b$ and one
where $\mathbf{v}^T\mathbf{x} < b$.

So in 2D, if your line is defined by $\mathbf{v}, b$, all you have to do is check whether
either $\mathbf{v}^T\mathbf{x} \geq b$ or $\mathbf{v}^T\mathbf{x} < b$ holds for all your points $\mathbf{x}$.

You are probably used to a line being defined as $y = ax + b$. Note that we have
$\mathbf{x} = \begin{bmatrix}x\\y\end{bmatrix}$ (beware of the bold $\mathbf{x}$ as opposed to $x$).
Thus we can rewrite to a matrix equation:
$$y = ax + b$$
$$-ax + y = b$$
$$\begin{bmatrix}-a, 1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = b$$
$$\mathbf{v}^T\mathbf{x} = b$$
and we recover the above form, where $\mathbf{v} = \begin{bmatrix}-a\\1\end{bmatrix}$.
Thus all we have to do to check is if your points are a list of $(x, y)$ pairs is if either $-ax + y \geq b$ or $-ax + y < b$ for all of them.


In ID3 algorithm, which attribute to choose if information gains are equal?

Yes.  As @Aaron says, it's fine to choose an attribute arbitrarily.

Keep in mind that choosing the attribute with the highest information gain is just a heuristic.  It's a local greedy choice.  There is no guarantee that making the local greedy choice at each level will necessarily give you a global optimum (i.e., the best possible decision tree); indeed, it might not do so.  Instead, it is a heuristic that empirically seems to work pretty well in practice.  Resolving ties arbitrarily is in line with that heuristic.  There are already no guarantees when using this heuristic, so you're not giving up any theoretical guarantees in this way.  The primary focus of this heuristic is to make it efficient to build a decision tree (so you don't have to try all exponentially possible decision trees); resolving ties arbitrarily is in keeping with that focus.


Can abstract syntax trees be unparsed in subexponential time?

There is a version of your question for which unparsing is easy and can be done in linear time. However, I'm not entirely sure if your question pertains to this specific version of unparsing, so I'll look at that first.

You say in your question over at StackOverflow that your AST looks like "AnyObject -> AnyObject -> Vehicle [name="Car"]". Your question would be a lot easier if your AST looks like "Area -> Highway -> Car", that is, that we know which productions were taken when your AST was constructed/parsed. In ordinary context-free parsers, you (almost) always get this information: you might decide to throw it away, but (nearly) all parsing algorithms can also give you this information.

If you don't have this information, I'm pretty sure exponential time is the best you can do, unless you know something about your S-expressions. The problem then is simply recovering the "Area -> Highway -> Car" AST, the unparsing after that is the easy part.

If you do have this information, then we can just look at context-free grammars and try to unparse them. Consider this grammar:

  1: $S \to a$
  2: $S \to a S a$

An AST for this grammar may look like $S \to a (S \to a) a$, on input "aaa". Unparsing this AST is easy: perform a postorder walk of the tree and output all terminals found in this walk. The result is "aaa" again.

Things become a bit more complicated when you look at ambiguous context-free grammars. On one hand, things are still easy: you just pick any parse tree of your input and do the above: you can reconstruct all other parse trees from the result.

However, in the presence of disambiguation rules, you have to do something clever. In particular, the input "(1+2)*3" may be unparsed as "1+2*3", which is different from the original. It is possible to do this in linear time on $LR(1)$ grammars (where precedence and associativity are enforced like in Yacc) by doing a reverse $LR$ parse at unparse time. I'll skip the details, as this was not part of your question, but it can be done.


We can suppose without loss of generality that the elements of $A$ have complete sets of preferences (if an element of $A$ is indifferent to some elements of $B$, we put them at the bottom of the element's preference list).

Our goal would be to match elements of $A$ and elements of $B$ such that the resulting matching is stable in the following sense. For any two elements $a_1,a_2 \in A$, either $a_1$ prefers its current match to that of $a_2$, or $a_2$ prefers its current match to that of $a_1$.

Here are two different algorithms for solving the problem. The first uses a greedy approach. Order the elements of $A$ arbitrarily: $A = a_1,\ldots,a_n$. Let $a_1$ choose its top pick, let $a_2$ choose the top available pick, and so on. This results in a stable matching since if $i < j$ then $a_i$ prefers its current match to that of $a_j$.

A different approach, more similar to the Gale-Shapley algorithm, is iterative. Start with an arbitrary matching $f$. If there is a pair $a_1,a_2$ in which $a_1$ prefers $f(a_2)$ over $f(a_1)$ and $a_2$ prefers $f(a_1)$ over $f(a_2)$, then switch $f(a_1)$ and $f(a_2)$. This decreases the objective function $\Phi$ which is the sum over $i$ of the index of $f(a_i)$ in $a_i$'s preference list. Since $n \leq \Phi \leq n^2$ and $\Phi$ is an integer, we deduce that this algorithm terminates in $O(n^2)$ rounds.


Easy way to prove that this algorithm eventually terminates

Here's the solution for the case $k = 1$:

Assume the algorithm does not terminate.  Since there are a finite number of states of the algorithm (assignments of points to $A$ and $B$), the algorithm state must repeat in a cycle.  Since the cycle goes through different states, there must be a point that switches between $A$ and $B$ infinitely often.

Let $x$ be a point that switches infinitely often in this cycle.  Pick the first iteration of the algorithm within the cycle during which $x$ switches from $B$ to $A$.  For $x$ to switch to $A$, there must have been at least one point $x'$ in $A$, with $d_x^C > dist(x, x')$.  Arbitrarily pick the smallest-labeled such point; define a function $f$ so that $f(x) = x'$.  Note that $x'$ also must switch between $A$ and $B$ infinitely often (because if $x'$ stayed in $A$ permanently, so would $x$), so we can take $f(f(x)), f(f(f(x))),$ etc.

Since we have a finite number of points, the iterates of f must eventually repeat:  $f^n(x) = f^m(x)$ for some $m > n$.  Now look at the corresponding sequences of distances from C:  $d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ... $.  Since it repeats, this sequence cannot be uniformly decreasing.  There must be an iterate $o$ such that $d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Now, $f^{o-1}(x)$ and $f^o(x)$ are close enough to each other to cause each other to be in $A$, if one of them is.  That is, they're closer to each other than either of them is to $C$:
$d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$  (from definition of $f$)

So as soon as $f^{o-1}(x)$ and $f^o(x)$ are both in $A$, they will keep each other in $A$ forever (see lines 1-2 of the algorithm).  This contradicts the fact that all the iterates of $f$ must switch sets infinitely often.  Thus, for the case when $k = 1$, the algorithm terminates.


Tough. You are leaving linear programming.

Solve the problem without these equations and with no restriction for the sign of x. If by coincidence x matches one of the conditions, you are done. Otherwise you will need to solve the problem with one of these equations added.

Calculate how much changing x by eps changes the optimal solution. With that guess how much adding x=0, x>=c, or x<=-c would affect the optimal solution. Add the equation that seems to cause the least damage and solve with an optimal goal function G. Then try adding each of the other equations, with an additional restriction goal >= G.

You could have just tried adding each equation in turn and solving, but this way you might find quicker that one condition can’t lead to an optimal solution. For example if c=100 and your optimal solution was x=80, you can add x>=100, optimise , and you can likely show easy that x=0 or x<= -100 will lead to a worse outcome.


If your problem is with the 100 vertices limitation, then you're in the clear.
Consider the following reduction: given input $\left( G,t \right)$, if $G$ has under 100 vertices, exhaustively test all witnesses and check if $\left( G,t \right)\in A_1$, this can be done since $A_1\in NP$. Depending on whether or not $\left( G,t \right)\in A_1$ output some constant word in/not in $A_2$.

If G has more than 100 vertices, then your reduction outputs $\left(G,y\left(G,t\right)\right)$. Since you proved $\left( G,t \right)\in A_1 \iff \left(G,y\left(G,t\right)\right)\in A_2$ it's a reduction from $A_1$ to $A_2$. You will probably want (if you're dealing with polynomial time reductions) to show that $y\left(G,t\right)$ is computable in polynomial time.

The asymptotic behavior of the reduction's running time does not depend on how you treat small inputs (in this case, graphs with less than 100 vertices).

Edit: I should note that inputs can get arbitrarily large while keeping the graph small, by increasing $t$. However i assume that (as is with many natural graph problems e.g. clique, independent set) that if $t\ge f(|V_G|)$ for some increasing function $f$, you can simply decide whether or not $(G,t)\in A_1$.


Efficient alternatives to inclusion-exclusion

Unfortunately, if the only reasonable method to solve a problem is via inclusion/exclusion, it's going to take $\Omega(2^n)$ time. The reason for this is simple, there are $2^{n}-1$ sets we must inspect (if we don't, then we wouldn't have to do inclusion/exclusion!) So, there are no significant general improvements on inclusion/exclusion.

Asking for an algorithm to "have polynomial run time in most cases" is a rather vague empirical claim that is unfortunately hard to answer precisely and could have little value. A way to make this precise is a probabilistic algorithm. I'm not aware of any probabilistic variants of inclusion/exclusion, but I think that using another method than inclusion/exclusion would be better to create a probabilistic variant.

However, is inclusion/exclusion worthless? No. Often, inclusion/exclusion is used to obtain an algorithm that takes exponential time, but has only polynomial space usage. (sometimes, exponential space is a bigger problem in practice than exponential time!) For instance, the Hamiltonian cycle problem can be solved in $O^*(2^n)$ time but only polynomial space by inclusion/exclusion.

It could be the case that your specific problem has a more efficient solution, but that solution method then is likely very different from inclusion/exclusion.


What language should this NFA recognise?

Don't overthink it; your intuition is correct. The only strings that get you from the start state to the final state are $<anything>11$ or $<anything>101$. Once you're in the final state, any subsequent inputs are also accepted, so the language accepted by this FA is, as a regular expression, $(0+1)^*(11+101)(0+1)^*$, which is obviously all strings containing 11 or 101.


This is precisely Moore's 1957 formulation of what is now more commonly known as the Bellman-Ford algorithm.

Why does it work?

Moore's algorithm is a special case of Ford's more general relaxation strategy for computing single-source shortest paths:

while any edge is tense
    relax any tense edge

This generic algorithm will always halt after a finite number of relaxation steps with a shortest path tree, unless some negative-weight cycle is reachable from the source vertex (in which case, there is always at least one tense edge, so the algorithm will never halt).

For Moore's algorithm, it is not hard to the following observation by induction:

  Every tense edge leaves a vertex that is in the queue.

If fact, this lemma holds if we replace the queue with any other data structure that supports the operations "insert this" and "give me something".  (For example, using a priority queue gives us Dijkstra's algorithm!) The algorithm halts when the data structure is empty.  Thus, by the previous lemma, when the algorithm halts, there are no tense edges, so we have a shortest-path tree.

What is the running time?

We can naturally divide the execution of the algorithm into phases by adding an artificial token to the queue immediately after the source vertex, just before the main loop begins.  Each phase ends when we dequeue the token; if the queue is not empty, we enqueue the token again and start the next phase.  If the queue is empty after we dequeue the token, the algorithm ends.

Each vertex in the graph is dequeued at most once in any phase.  (Here I'm assuming that enqueuing a vertex that is already in the queue does not actually change the queue.)  Thus, each edge in the graph is relaxed at most one in any phase.  So each phase runs in $O(m)$ time.

Let $dist_i(v)$ denote the distance value stored in vertex $v$ after $i$ phases.  Initially, we have $dist_0(s) = 0$ and $dist_0(v) = \infty$ for all $v\ne s$.  It is easy to prove by induction that

  $dist_i(v)$ is at most the length of the shortest walk from $s$ to $v$ that uses at most $i$ edges.

This lemma immediately implies that the algorithm ends after at most $n-1$ phases (unless there is a negative cycle).  So altogether the algorithm runs in $O(mn)$ time.

For more details, see my lecture notes, or better yet, Bob Tarjan's excellent monograph Data Structures and Network Algorithms.  I believe Tarjan was the first to observe that Moore's algorithm is equivalent to Bellman-Ford.


Origin of tFAW (Four Activation Window) in DRAM timing constraint

The magic number is just 4 since (within one rank) you have just 8 banks where you can spread your consecutive accesses. The problem lies with the bank activation current drained from the entire array (or bank) of single cells (transistor + capacitor) needed to prepare the memory location to be read. If the consecutive read operations are falling each time in a different ROW within each bank than you have the activation problem kicking in each time. In order to avert a high current drain from the arrays you need to limit the number of consecutive bank activation over a rolling window of time. The reason why you need to prevent the bank from high energy / current drain is because this may cause a Voltage Reference (VR) deterioration. The VR is the standard Voltage level against which earch data read from the bank is compared to verify if what you are reading is 1 or a 0. Risking to alter the VR level may mean that the reliability of what your read or write is compromised.

However these tFAW and tRRD parameters are usually overestimated and a memory tuner may increase system performances by slightly changing these parameters.


Is checking if the length of a C program that can generate a string is less than a given number decidable?

The length of the smallest C program that generates a given string is known as the Kolmogorov complexity of the string. One of the basic properties of Kolmogorov complexity is its undecidability.


A certificate for there being no non-trivial divisor of $m$ smaller than $r$ is the factorization of $m$. We can check in polynomial time that all factors are indeed prime (since primality is in P by AKS primality test), that their product is $m$, and that all of them are at least $r$.


Decidability of a language and inclusion between two other languages

Your statement is false. Indeed, if $L$ is any language over $\Sigma$, then
$$ \emptyset \subseteq L \subseteq \Sigma^*.$$


Can a Boolean circuit be considered an algorithm?

Have a look at Turing-completeness and the Church-Turing thesis (CT). Basically, CT is saying that everything that is computable, is computable on a Turing machine. Many different models of computation are known to be equivalent to the Turing machine. Even if you are considering something esoteric you came up with yourself, if what you have is Turing-complete, you can claim that you really do have an algorithm.

A circuit is a non-uniform model of computation, meaning that different size circuit compute things for different size inputs. A Turing machine on the other hand is a uniform model, so it's used for all input lengths. Given a Turing machine, one can construct a Boolean circuit that is able to simulate all its computation if we put a bound on the Turing machine's memory. Also, given a circuit, we can build a Turing machine that simulates the circuit.


Solving the part-of-speech tagging problem with HMM

Isn't this exactly the same question you asked previously? I'll make some additional comments and add some links here. Hopefully that will help.

  is there are any particular reason why we prefere to solve it by generative model with a lot of assumption and not directly by estimating $P(Y∣X)$, given the training corpus it's still possible to estimate $p(y_i∣x_i)$?

It just depends. Choosing whether to model $P(X,Y)$ or $P(Y|X)$ is simply the choice of generative versus discriminative. Both have advantages. See the paper
On Discriminative vs. Generative classifiers by Ng and Jordan. One thing worth mentioning, that I didn't say last time, is unsupervised learning in a generative framework is normally straightforward. This means it is also fairly obvious how to do semi-supervised learning. Semi-supervised learning can be very helpful for NLP tasks where the amount of unlabeled data is essentially infinite and labelled data is hard to obtain. Semi-supervised learning is typically not as easy in a discriminative framework. See Co-training as an example of the later.

As for how one decomposes the joint, well that's up to you. There's no rule saying you cant decompose it as $P(X,Y) = P(X)P(Y|X)$. Doing so would be perfectly valid, just not sensible. Notice decomposing the joint this way includes the factor $P(Y|X)$ already. If you're ultimately interested in predictiong $Y$ given $X$, then you should should predict
$$
\begin{align*}
\arg\max_y P(Y=y,X=x)
&= \arg\max_y P(X=x)P(Y=y|X=x) \\
&= \arg\max_y P(Y=y|X=x).
\end{align*}
$$
So you just use $P(Y|X)$ and ignore $P(X)$ and we're back at a discriminative classifier.


Do I have the right definition of VC dimension?

A family of hypothesis functions on domain $\cal X$ is a subset of $\{0,1\}^{\cal X}$. A family $H$ shatters a set $S \subseteq \cal X$ if for every subset $T \subseteq S$ there exists a function $h \in H$ such that $h(s) = 1_{s \in T}$ for all $s \in S$, that is, $h(s) = 1$ if $s \in T$ and $h(s) = 0$ if $s \in S \setminus T$.

A singleton family $H$ cannot shatter any non-empty set $S$. Indeed, suppose that $H = \{h\}$ shatters $S \neq \emptyset$, and take any $s \in S$. Taking $T = \emptyset$, we see that $h(s) = 0$, whereas taking $T = S$, we see that $h(s) = 1$.


Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

I'll just show how to build a grammar for  $L_1 = \{ u\#v, |u|_a > |v|_a \}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$.

The idea is to write $u\#v$ as $xay\#v$ with $x,y,v \in \{a,b\}^*$ and $|y|_a = |v|_a$.  The construction of $y\#v$ is handled by the non-terminal $Z$ which "grows" it from the center.

$$
\begin{align*}
S &\to aS \mid bS \mid aZ \\
Z &\to bZ \mid Zb \mid aZa | \,\#
\end{align*}
$$


Generating constraints to solve dependently-typed metavariables?

There's a nice idiom, which is explained more in chapter 22 of Types and Programming Languages (it's used for polymorphism rather than dependent types, but the idea is the same). The idiom is as follows:

  A type checking system can be turned into a type inference system by making the rules linear and adding constraints.

I'll use the application rule as an example. The checking rule in dependent types is this:

$$\frac{\Gamma \vdash t:\Pi x:A.B\quad \Gamma\vdash u:A}{\Gamma\vdash t\ u: B[u/x]} $$

Linearizing this rule requires re-naming the 2 occurrences of $A$, such that we obtain:

$$\frac{\Gamma \vdash t:\Pi x:A_1.B\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]} $$

But this isn't correct anymore! We need to add the constraint $A_1\simeq A_2$:

$$\frac{\Gamma \vdash t:\Pi x:A_1.B\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}\quad A_1\simeq A_2 $$

Note that $\simeq$ denotes equivalence modulo your conversion relation ($\beta\eta$, typically), just like for the conversion rule, but it is now a unification constraint, since you may have meta-variables in your terms.

In the course of type checking, you'll accumulate constraints like these, to potentially solve them all at once at the end (or earlier for efficiency reasons).

Now things can get trickier, because the type of $t$ itself could be a metavariable in context! A more generally applicable rule would therefore be

$$\frac{\Gamma \vdash t:C\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}\ C\simeq \Pi x:A_1.B,\ A_1\simeq A_2 $$

Or alternatively, keeping the previous rule and adding the rule

$$\frac{}{\Gamma_1, x:C, \Gamma_2 \vdash x: A} C\simeq A $$

at variable lookup time.

Another useful remark is that in the checking system, the conversion rule only needs to be applied right before applications, and possibly once at the very end of the derivation. Since this rules correspond to a unification constraint in the inference system, this tells you where to place the constraints.


When you encounter these types of problems, the typical thing to do is to find some "decision scheme" that can decompose your big problem into a series of smaller problems. The gist of this problem is finding a set $(h_1, \dots, h_n)$ that maximizes your mean grade $\frac{\sum_{i \le n} f_i(h_i)}{n}$ subjected to the constraint that $\sum\limits_{i \le n} h_i \le H$. Notice that maximizing $\frac{\sum_{i \le n} f_i(h_i)}{n}$ is equivalent to just maximizing $\sum\limits_{i \le n} f_i(h_i)$ since the denominator $n$ is independent of the choices of $(h_1, \dots, h_n)$ that we make.

Now, there are various dynamic programming schemes that we can choose to solve this problem, each of which depends on some special interpretation of an "optimal functional" that we define. For me, the intuitive one is based on the idea of variable elimination, in which we eliminate one of the variables $h_i$ at each turn.

Here, let $\textrm{Best}(k, h)$ denote the maximum cumulative grade you can gain for the classes $C_k, C_{k+1}, \dots, C_n$ so that you spend no more than $h$ hours on all of their final projects. Given this interpretation, it is clear that our problem is to find $\textrm{Best}(n, H)$.

Now comes the fun/interesting part. First, we need to convince ourselves that this functional displays what we would call an "optimal substructure." In layman's words, this claims that if we know the best distribution of no more than 5 hours to Networking and Programming Languages' final projects, then we also know the best distribution of 8 hours to the Networking, PL, and OS' final projects if we decide to allocate 3 hours to the OS project. It's simple, we just use the same optimal budget of 5 hours for Networking and Programming languages that we already have.

In other words, this optimal substructure property guides us on the decision we have to make at each turn (because we don't have to worry about the subproblems). Here, $\textrm{Best}(k, h)$, according to the substructural property we've introduced above, must make a decision on what $h_k$ should be assigned. In addition, it must

Ensure that $h_k$ does not exceed its allocated hours of $h$, and
Maximize the grades contingent on the choices that it can make.

Therefore, when we consider the problem of computing $\textrm{Best}(k, h)$, there's a range of valid decisions that we can make, each corresponds with an assignment of a single value to $h_k$. For example, say I'm considering $\textrm{Best}(\textbf{Networking}, 5)$, which corresponds to the maximum cumulative grade that I can get in classes Networking, PL, and OS with only 5 hours to distribute between them. Now, I have to make a decision about how I will budge for Networking. Say I budget exactly 0 hours to networking, then I can spend 5 hours on PL and OS; alternative, I can budget 1 hour to networking and spend 4 hours between PL and OS, 2 hours to networking and 3 between PL and OS, etc. Each choice of time budget for Networking also determines a subproblem that I have to solve between PL and OS with the remaining time. Once we consider all of these choices (and subproblems), we must then commit to the problem that will give us the best solution.

This thought process should yield a recurrence for Best that can be computed in some increasing order of its parameter. This computation then takes the form of a tabulation over an $n \times H$ grid, each time spending approximately $O(k)$ (where $k \le n$ is the column number) time between the $O(k)$ choices, which gives an $O(n^2 H)$ algorithm.


context-free grammar for comma-separated list with comments

Define a non-terminal COMMENT which generates comments (in your case, // followed by arbitrary non-newline characters and then newline), as well as the empty string. In the definition of def, add COMMENT after ,.


What is the Purpose of Augmented Grammar in LR parsers?

The augmented grammar adds a new starting non-terminal $S'$ with the sole production $S' \to S$. This helps in detecting acceptance: If you reduce by this particular production (to the non-terminal $S'$), you are accepting. To reduce to the start non-terminal of the original grammar tells you nothing, it might appear on some right hand side.


Can a vectorized computation always be parallelized?

If there are dependencies between loop iterations, then the loop cannot be parallelized.  Depending upon the precise definition of "vectorized" you have in mind, your definition might imply that there are no dependencies -- or it might not.

Some examples:

foreach i in S:
    B[i] = f(A[i])

is parallelizable if f is a pure function and A,B don't alias (have no overlap).  (But it is in general not parallelizable if f writes to global state or performs any kind of I/O.)  More generally

foreach i in S:
    B[i] = f(i, x, y, ..)

is parallelizable if f is pure and does not access B (for reading or writing) and none of the arguments alias B.  However,

foreach i in S:
    B[i] = B[A[i]]

is not parallelizable, as there are dependencies between loop iterations.  (At least, it is not trivially parallelizable, if A is not known at compile time.)

I've written using foreach syntax but you can translate each example to map or apply and the same comments apply.


Rule induction principles in Harper's PFPL

At the beginning of Section 2.4 the book explains that $\mathcal{P}(J)$ stands for a property of a judgment $J$. That is, the $\mathcal{P}$ in $\mathcal{P}(a\ \mathtt{nat})$ does not stand for a property of numbers, but a property of the judgment $a\ \mathtt{nat}$, which is the judgment that "$a$ is a number".

It just so happens that the inference rules for $a\ \mathtt{nat}$ precisely match those for numbers. Namely, the two rules defining the judgment $a\ \mathtt{nat}$ are
$$\frac{ }{\mathtt{zero}\ \mathtt{nat}}$$
and
$$\frac{a\ \mathtt{nat}}{\mathtt{succ}(a)\ \mathtt{nat}}.$$
Therefore, if we want to show that the judgment $a\ \mathtt{nat}$ has some property $\mathcal{P}$, then we need to show that the base case $\mathtt{zero}\ \mathtt{nat}$ has the property $\mathcal{P}$, and that whenever $\mathcal{P}(a\ \mathtt{nat})$ holds then $\mathcal{P}(\mathtt{succ}(a)\ \mathtt{nat})$ holds as well.

Or to put it the other way, the strange looking "$\mathtt{nat}$" is there because we are not talking about numbers, but about the judgments "expression $a$ satisfies the judgment $\mathtt{nat}$".


Teaching NP-completeness - Turing reductions vs Karp reductions

I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model.

Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or try to discuss the subject with anyone who wasn't taught by you.

I agree that Cook reductions are in several ways more sensible and that there's no distinction between NP-hardness and coNP-hardness in practical terms, in the sense that they both mean "This problem is pretty hard and you're not going to get a general, efficient, exact algorithm that can cope with large instances." On the other hand, the distinction between NP and coNP isn't entirely an artifact of a theory based on Karp reductions: you don't often talk about graphs that are non-3-colourability or in which every set of $k$ vertices contains at least one edge. Somehow, the "natural" version of the problem often seems to be in NP rather than coNP.


maze solving algorithms (pledge algorithm)

If you use wall following with the right hand, you should place your hand on the right wall.

For the pledge algorithm your source says

  It's a guaranteed way to reach an exit on the outer edge of any 2D Maze from any point in the middle, however it's not able to do the reverse, i.e. find a solution within the Maze.

There is no guarantee that the exit reached is the one labeled "Exit" instead of the one labeled "Start".


What is the difference of temporal dynamics in RNNs and the NEF

There can be a lot of different ways in which recurrent neural networks can be used. RNNs can have any activation function (logistic sigmoid is most commonly used), and they can be multilayer. There are different algorithms which can be used to train them e.g., backpropagaion and different optimization techniques e.g., hessian free optimization which can be used to optimize the networks for a particular problem.

NEF has been used for simple recurrent connections (for implementing memory circuit), however, we need to do some work and try out multi-layer networks in order to truly figure out what the differences in dynamics would be.

We have also tried hopfield networks with pre-calculated weight matrices, and using sigmoid neurons and were able to achieve similar dynamics forming attractors. However, implementing hopfiled with dynamic learning of weight matrices is something which needs to be tried out.

I suspect that using sigmoid activation functions in NEF and applying the same learning algorithms should give results very similar  to RNNs (there might be some differences caused by synaptic filtering). However, if one uses an LIF curve as an activation function, then there is a possibility of greater differences.