Lexing and parsing a language with juxtaposition as an operator

Juxtaposition is used in mathematics because most mathematical texts
use single character variables (possibly with diacritic signs,
subscripts, superscripts, etc...) so that there is no ambiguity.

A mathematician might write $2x$ to multiply $2$ and $x$. It would be
quite unusual to write $x2$ to multiply $x$ by $2$. Actually, as much
as I can see (but I am open to contrary examples) a numerical factor
always comes first in the product. This unstated rule implies that one
never has two numerical factors in succession, which would make it
difficult to interpret $22$, which could be $2\times 2$ or the single
number $22$.  Of course, if two numerical factors in a row were to be
acceptable, they would be separated by a space to avoid ambiguity.

Regarding variables, the same has to be true. Several variables can be
factors of a product (well, a sequence of products). Either you have a
rule that all variables are 1 letter (a constraint that cannot be
imposed on numbers), or you maust have a way to separate the
variables, either by a space, or by a $\times$ sign.

First I would point out that this is a pure lexer problem: how do I
determine what variables are juxtaposed as the factors of a product.
The fact that the operator are omitted is not really an issue for the
parser (though it may call for some appropriate techniques depending
on other syntactic aspects of the language, and the way they interact
with the feature we are discussing).

Of course, you can start playing games, like the following which you seem to be actually suggesting. Since all
variables are supposed to be declared (that is also true in
mathematics), you could juxtapose variables arbitrarily, without
spaces, to form a product, and rely on the lexer to determine how to
cut the string so that each cut out substring is a declared variable.
Of course, depending on what variables you have declared, this can
have an ambiguous result (as you suggest in your question), and produce a lattice of variables instead of a
sequence of variables.

I created the expression "lattice of variables" after the expression "word
lattice" used in speech recognition for exactly the same problem in a
different setting. For example, given that you have declared the seven
variables: a b c d ab bc cd. Then the string abcd can be cut into
several sequences of variables, that can be represented by a loopless
finite state automaton like the following (which is what is called a
word lattice in speech processing).

     /--- ab ---\
    /            \
    --- a --- b --\--cd --------\
-- /     \                       > -----
   \      \-- bc ------/--- d --/
    \                 /
     \-- ab --- c ---/

Creating this lattice is not difficult, using finite state techniques,
when the available variables are known. It would however probably
require some changes in standard lexers, as they usually identify
lexical element with simpler techniques, simpler use of context.

One way to do it is for the lexer to first identify the string as an
expression. It could then call a routine that would access the current
symbol table to find relevant identifiers and organise them as a trie
to cut the string into existing identifiers. Assuming no ambiguity,
the lexer could then give the successive identifiers to the parser,
interspersed with $\times$ symbols.  So it is rather easy to integrate
into existing architectures.

To limit the ambiguity, one can first eliminates by type checking all
variables with a type incompatible with use as factor in a product.
Or possibly, if there are different kinds of products requiring
compatible types, this can be used to eliminate inconsistant sequences
of variables.

Remaining ambiguities would probably no be a major problem for the
parser (possibly depending on parsing techniques, typing ...). But of
course, the ambiguity has to be resolved at some point, if the
language is supposed to convey only one meaning.

One way to do it could be to notify an error whenever such an
ambiguity is found, with some details about the ambiguity, thus
requesting the user to disambiguate by adding a space or a $\times$
symbol.

Though this can be handled technically, I do not think I would
recommend it in a language. Even if unambiguous, this is not extremely
readable, notwithstanding the fact that the ancient languages such as
Latin and Greek used to be written that way.

An alternative could be to accept this kind of notation only with the
usual constraints (in mathematics) that I stated above: number must be
first and variables must have a single letter for implicit product. But ambiguity could
remain between a single variable $xx$ and the product $x\times x$
written without the $\times$ symbol. I guess it would not be very
hard, with standard technology.

I think I have exhausted my imagination on this topic. It is not
technically difficult, for what I can see.
But why would all this be worth the trouble?


Is a Turing machine too strong of a model to model physical computation?

Is it too strong?
The concern should not be that a Turing machine is a too strong model because of the way we construct a Turing machine. Turing machine is essentially a framework for defining a notion of algorithm in its basic, simple steps. Every algorithm executed on a Turing machine can be executed by hand, meaning it is effectively calculable (one direction of Church-Turing thesis). The real question is - is there an effectively calculable function whose computation cannot be encoded in a Turing machine. This all seems that it must hold (and therefore many computer scientists accept Church-Turing thesis as true), but cannot formally be proven just because the term "effectively calculable" is not formally defined.

Why not bound it?
I am not sure if this satisfies your quest for "deep inherent reason why unboundness is a requirement", but think about it this way: What if we bound the tape? Say, a Turing machine must have tape of length at most $M$, for some $M \in \mathbb{N}$. Let's look at $2$ examples:

We can choose/construct a Turing machine $T_M$ that uses exactly $M$ distinct positions on a tape. Then, we can construct a Turing machine $T_{M+1}$ that runs exactly as $T_M$ with additional step - that it writes a symbol after the last symbol on its tape, once it finishes all the running steps of $T_M$.
This Turing machine (algorithm) $T_{M+1}$ therefore could not exists if we bounded the tape at $M$, but obviously - this algorithm is effectively computable.
Say you want to construct a Turing machine that adds two numbers. What if the length of numbers is more than $M$? We could not add them (nor even write them) with a Turing machine, but can obviously add them (say, by hand) via standard known algorithms for addition (that also doesn't have restrictions on length/tape).

Therefore, we must not bound the tape if we want to be able to compute things that we can in theory compute (by hand). The same arguments holds if we would want to bound the number of steps (time).

Computatioal complexity deals with resources required by an algorithm depending on size of the input, so you might want to look at that subject.

  So, are there any attempts to capture the notion of computability and what we know to be computable in the physical world in a model that is finite in nature?

Turing machine is a finite model.

Different model
$\lambda$-calculus is a computational model invented by Turing’s doctoral advisor Alonzo Church. It does not resemble Turing machine and it is based on a concept of definition and application of functions. Turing and Church proved that their models are equal in computational power.


Citation for finding node disjoint paths using maximum flow

This reduction appears in §4 (Menger's theorem) of ON THE MAX-FLOW MIN-CUT THEOREM OF NETWORKS, G. B. Dantzig and D. R. Fulkerson without citation to another work. It's possible that this was a reinvention, but it's not clear to me where to look next.


Given a sorted array $A$, how can it be efficiently determined whether $\exists i . A[i] = i$?

It can be done in $O(\log~n)$ for a $n$ element array $A$ by using a slightly modified version of binary search. This is possible because you stated that the input array is made of increasing integers and is therefore sorted. It does not matter what kind of integers your input actually contains: the integers may be negative, zero or positive as long as the array is sorted.

Your search for an index $i$ such that $A[i] = i$ is of course equivalent to searching for an index $i$ such that $A[i] - i = 0$ and the function $f(i) = A[i] - i$ is monotonically increasing so that the problem reduces to finding, if it exists, one point $i$ where the function value is zero. It follows that you are guaranteed that if a check fails you only have to explore one subarray, which leads to $O(\log~n)$ in the worst case.

Your algorithm starts by checking the middle element as usual. If the check succeeds (A[middle] - middle = 0), you have found the index you are searching for. If $A[middle] - middle < 0$, then you need to check the right subarray; otherwise ($A[middle] - middle > 0$), you have to check the left subarray.


Cost in time of constructing and running an NFA vs DFA for a given regex

Kiliki's answer has some things wrong.

They say:

  The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)

This doesn't even really make sense. If you are constructing a NFA from a regular expression there are no well defined "nodes" to speak of. A sufficient algorithm is the Thompson's construction.

Amortized time for constructing an NFA from a regular expression

A regular expression is composed literal characters stuck together in various ways

concatenation
alteration and
Kleene star.

Thompson's construction defines rules for making an NFA for literal characters. For the character 'x' where Os are states.

       x
    O ---> O

There are other rules for concatenation, etc. that join together NFA's like the one above, but the important part is that any operation adds a small finite number of states and transitions (never more than two states or four transitions actually. If you want the details have a look at the super helpful wiki link above).

The number of literals and operations (concatenation, etc.) is easily determined from the length of the string of the regular expression. The amount of one or the other is different only by a constant factor. Thus we can safely say that constructing an NFA from a regular expression using Thompson's construction is O(n) where n is the length of the string of the regular expression.


You can solve this using dynamic programming. Given trees $T_1,\ldots,T_n$, for each $1 \leq a \leq b \leq n$ compute the best way of concatenating $T_a,\ldots,T_b$. Details left to you.


How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

You're looking for a set of Pareto-optimal alternatives.  If you're looking for all such possibilities (i.e., looking to make $T$ as large as possible), you're looking for the Pareto-optimal front.  You asked for keywords or names to search for this -- those are standard terms for this concept.  See https://en.wikipedia.org/wiki/Multi-objective_optimization.

For specific situations, if the data is structured, it may be possible to take into account knowledge of the structure of the data to find a better algorithm -- but this will depend on the nature of the data.

In your specific case, there are algorithmic techniques that might lead to significant improvements in running time.  In particular, in your setting, each vector $v \in S$ is obtained as a sum of some component vectors $v = \sum_i v_i$, where we have a collection of sets $S_1,S_2,\dots,S_k$ and each $v_i$ is chosen from some set $S_i$.

Let me establish some notation and definitions, prove some mathematical results, and then show them how to compute the Pareto-optimal front for your specific situation.

Definition. We say that $u$ dominates $v$ if $u[j] \ge v[j]$ for all dimensions $j$.  (This is the same as what you call "covers", but "dominates" is the more standard term.)

Definition 1. If $S,T$ are sets, then $S+T$ is defined to be the set $S+T=\{s+t : s \in S, t \in T\}$.

Definition 2. If $S$ is a set of vectors, define $P(S)$ to be the Pareto-optimal front of $S$, i.e., the set of vectors $s \in S$ such that there does not exist any vector $t \in T$ that dominates $s$.

Your problem is the following: given sets $S_1,\dots,S_k$ of vectors, find the Pareto-optimal front of $S_1+\dots + S_k$, i.e., compute $P(S_1 + \dots + S_k)$.  I'll show an algorithm to compute this.

The following lemmas will be helpful:

Lemma 1. If $u$ dominates $v$, then $u+w$ dominates $v+w$.

Lemma 2. If $u_i$ dominates $v_i$ for each $i$, then $\sum_i u_i$ dominates $\sum_i v_i$.

Lemma 3. $P(S+T) = P(P(S)+P(T))$.

(Lemmas 2 and 3 follow immediately from Lemma 1.)

We'll now use Lemma 3 repeatedly to compute $P(S_1 + \dots + S_k)$.  We build a binary tree over the $k$ leaves $S_1,\dots,S_k$.  At each node, we compute the Pareto-optimal front of the sum of the two sets corresponding to its two children.

In other words, here's how we compute the Pareto-optimal front for several values of $k$:

$$P(S_1+S_2) = P(P(S_1)+P(S_2)).$$

$$P(S_1+S_2+S_3+S_4) = P(P(P(S_1)+P(S_2)) + P(P(S_3)+P(S_4))).$$

(In other words, to compute $P(S_1+S_2+S_3+S_4)$, we first compute $U_1 = P(S_1+S_2)$ efficiently using Lemma 3 and $U_2 = P(S_3 + S_4)$ using Lemma 3, then we compute $P(U_1+U_2)$ and use Lemma 3 to conclude that this is equal to $P(S_1+S_2+S_3+S_4)$.)

You can see how this works recursively.  To compute $P(S_1+\dots + S_k)$, we divide the sets in half, recursively compute $X=P(S_1+\dots + S_{k/2})$ and $Y=P(S_{k/2+1} + \dots + S_k)$ using the efficient algorithm, and then compute $P(X+Y)$.

At each stage of the binary tree, we are filtering out all dominated vectors.  If you're lucky, this greatly reduces the number of possibilities that remain at each level of the binary tree.

I suggest you try this on your specific application.  If, as you say, the final size of $P(S_1+\dots + S_k)$ is not too large (say $m$), then this should be efficient: the size at each internal node of the tree will be no larger than $m$, so the time to merge the two children of any node will be $O(m^3)$ [using the trivial quadratic algorithm mentioned in the question], and the total running time will be at most $O(m^3 k)$.  In practice, the actual running time might be significantly faster than that.

You could also explore different algorithms for computing $P(\cdot)$, the Pareto-optimal front of a set.  There are basically two standard algorithms: the "simple cull" algorithm [which is the same as the quadratic-time algorithm you mentioned in the question], and a recursive divide-and-conquer algorithm.

The simple cull algorithm has $O(n^2)$ worst-case running time, as you say.  Actually, if we know that the Pareto-optimal front has size $m$, the running time is a bit better: the running time is $O(mn)$.  (In other words, if we let $n=|S|$ and $m=|P(S)|$, then you can compute $P(S)$ from $S$ in $O(nm)$ time.)  The divide-and-conquer algorithm has $O(n (\log n)^{d-1})$ worst-case running time, which as you say in the question will likely be too small for your parameters.

However, it is also possible to combine the two techniques, where you use the recursive divide-and-conquer algorithm but once the problem size becomes small enough you switch to the simple cull algorithm.  Whether this will lead to any improvement in your actual setting can probably only be determined through experimentation.

For an overview of these algorithms, see for example Section of the following paper:

A Calculator for Pareto Points. Marc Geilen and Twan Basten.  Design, Automation & Test in Europe Conference & Exhibition 2007 (DATE'07), IEEE.

To compute $P(P(S)+P(T))$, the best algorithm I know is to compute $S'=P(S)$ and $T'=P(T)$ using one of the above methods, then compute $S'+T'$ using the obvious quadratic-time algorithm (combine all pairs), then compute $P(S'+T')$ using one of the above methods.


What is a distributed algorithm for generating random "private" pair-matchings?

Let's assume the agents are labeled $[0, n)$. Let $w > 2$ be a small constant, e.g. 4. Let $F_k(x)$ be an oblivious pseudo-random function (OPRF).
Let each agent generate random value $s_i$, announce $H(s_i)$ and then choose $r = \bigoplus_i s_i$ to ensure  a fair random shared seed (peers checking the hashes).
Initially agent $i$ chooses $X_i = i$. Then, some rounds take place. Use the chosen seed to derive a different $P_r$ and $w$ agents $A_{r,0}, A_{r,1}, \cdots, A_{r,w-1}$ for each round. Then, in round $r$ every agent computes
$$X'_i = (P_r - X_i) \bmod n$$
$$\hat X_i = \max(X_i, X'_i)$$
$$p = H(\hat X_i) \bmod  w$$
$$b =\text{get-secret}\left(p, r, \hat{X_i}\right) \bmod 2$$
where $\text{get-secret}(p, r, \hat{X})$ securely contacts agent $A_{r,p}$ and uses the OPRF primitive to compute $F_{K_{p,r}}(\hat{X})$, where $K_{p,r}$ is some never-shared secret round key generated (and stored) by agent $A_{r,p}$. Then, at the end of the round iff $b = 1$ the agent replaces $X_i$ with $X'_i$.
After the round is over the $w$ chosen agents $A$ can (and should) communicate to ensure no one cheated and asked for more than one secret. This ensures everyone only has partial information. If you force the $\text{get-secret}$ requests to be signed by agent $i$ one can even provide evidence another agent tried to cheat.
Do this for a sufficient* number of rounds and the result is that each agent $i$ has a value $X_i$ such that there is a permutation $\sigma(i) = X_i$, yet every agent only knows their own $\sigma(i)$, and is deeply unsure about anyone else's $\sigma(j)$.
However, this just gives us a secret random permutation. But we can use this to get a pairing. Note that if we let $g(i) = i \oplus 1$ (where $\oplus$ is XOR) then $f(i) = \sigma^{-1}(g(i))$ is a pairing (assuming zero-indexed permutations).
How can we compute $\sigma^{-1}$? By noting that each round is it's own inverse, each agent sets $X_i = g(X_i)$, and we run all the rounds again, in reverse order (with the same $P,A$ and $K$ values), again ensuring that no agent requests too many secrets. The end result is that $X_i$ contains the partner for each agent.

* The technique above is inspired by sometimes recurse shuffle. Read the paper for more ideas, and to get some bounds for what is sufficient.


Prove by induction that the running time of recursive Fibonacci is exponential

Observe that with

$\qquad  T(n) = T(n−1)+T(n−2)+3$

and

$\qquad T'(n) = 2 T'(n-2)$,

you have $T > T'$ assuming similar anchors, in particular because both functions are non-decreasing. $T'$ solves to $T'(n) \approx 2^{n/2} \geq 1.41^n$.

I intentionally provide only a sloppy sketch; I'll leave the formal proof to the interested reader.


Hoare Calculus Incorrect Assignment Axiom

Your solution is incorrect because you did not reach a contradiction. You claim that you reached a contradiction with the Assignment axiom. For this to be true, you must produce the negation of an instance of the axiom.

The axiom of assignment states that
$$\{P[e/x]\} \; x \mathbin{:=} e \; \{ P \}$$
In your example we would have $u$ instead of $x$, $t$ instead of $e$, and $P$ would be the statement $u = t$, which gives us the following instance of the axiom
$$\{ t = t \} \; u \mathbin{:=} t \; \{ u = t \}$$
You seem to think this is in contradiction with
$$\{ t = u + 1\} \; u \mathbin{:=} t \; \{ u = t \}$$
but that is a logical error. In fact, the axiom of assignment implies your statement:

$\{ t = t \}\; u \mathbin{:=} t \; \{ u = t \}$ (instance of the axiom of assignment, as above)
$\{ t = u + 1 \}\; u \mathbin{:=} t \; \{ u = t \}$ (weakening of the precondition because $t = u + 1 \Rightarrow t = t$.)

Hint: to solve the exercise, consider the possibility that the expression $t$ contains $u$.


The language $A = \Sigma^*$ is coRE. Since $A \triangle B = \overline{B}$, the statement you are trying to prove implies RE=coRE, which is known to be false: for example, the set of all programs that halt is in RE but not in coRE.


I suppose you mean simulating computer networks? because modelling is different (you can model your network as a graph for instance). If this is the case have a look at these simulators:

NS2: built with C++, a discrete-event simulator, open source, and perhaps the most useful. You would need to use Tcl to write the script of the simulation experiments. New open source libraries are always added. I suggest it, however, i know many consider it a bet complex. Good knowledge in C++ is required if you want to maximally exploit it (at least to print your statistics and analyze them). The newer version is NS3 (i have nt used it yet), but from what I read, you can write your simulation experiments using python or c++.
Opnet: I am not a fan, and it is not open-source. I think there is a student-version.
simjava: if you are a java person, then use this. (I haven't used it, but i saw it being cited in many research papers).

but be careful before starting working with any "network simulator" because in many cases you don't need complex simulators. A simple C++, Java or Python code would be sufficient. (Actually, it is always a good programming exercise to create your own discrete-event simulator for a network).

If you are interested in distributed processors simulation (from a theoretical point of view), then I would suggest erlang (a programming language). It is functional language very similar to Haskell (created by Eriksson). it is very easy to create processes with identities. But even more, you can let the processors exchange messages by sending/receiving messages in a very simple way.


How do 2-3 FingerTrees generalize to bigger branching factors?

Yes - if you read the original paper and assign the notions of safe and dangerous digits to the smallest and largest digits, the math should all go through.


What are the conditions for a NFA for its equivalent DFA to be maximal in size?

The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959.

To answer your question as stated in the title, there is no maximal DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one of the original states and one of the new ones. Thus, the new states will not be reachable from the initial state $q_0$, so the language accepted by the automaton will not change (since $\hat\delta(q_0,w)$ will remain the same for all $w\in\Sigma^*$).

That said, it is clear that there can be no conditions on a NFA for its equivalent DFA to be maximal, since there is no unique equivalent DFA. In contrast, the minimal DFA is unique up to isomorphism.

A canonical example of a language accepted by a NFA with $n+1$ states with equivalent DFA of $2^n$ states is
$$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the \(n\)-th symbol from the last one is 1}\}.$$
A NFA for $L$ is $A=\langle Q,\{0,1\},\delta,q_0,\{q_{n+1}\}\rangle$, with $\delta(q_0,0)=\{q_0\}$, $\delta(q_0,1)=\{q_0,q_1\}$ and $\delta(q_i,0)=\delta(q_i,1)=\{q_{i+1}\}$ for $i\in\{1,\ldots,n\}$. The DFA resulting of applying the powerset construction to this NFA will have $2^n$ states, because you need to represent all $2^n$ words of length $n$ as suffixes of a word in $L$.


Count all pairs of x,y such as x + y = c && x XOR y = d

Hint: $x+y=(x \text{ XOR } y)+2(x \text{ AND } y)$.


Inverse Reinforcement Learning and Apprenticeship Learning differences

Apprenticeship Learning uses Inverse Reinforcement Learning and there is a subtle difference between the two. Inverse Reinforcement Learning tries to recover the reward function ($R^*$) from demonstration trace of a teacher (an expert at the task being solved). Finding the optimal policy ($\pi^*$) from that "guessed" reward is what is meant by Apprenticeship Learning. More information on this link.


First of all, try to solve the recurrence relation using the master method.

Since $f(n) = O(n^{\log_2 3 - \epsilon})$ for some $\epsilon$, this is the first case of the master method. Therefore $$T(n) = \Theta(n^{\log_2 3})$$

If you replace $n$ by $2^n$, you will get your answer. i.e.
$$T(2^n) = \Theta(2^{n\log_2 3}) = \Theta(3^n)$$


Conditions for an Language to be infinite

Regular expressions correspond to a simple recursive definition, which starts with the symbols from some alphabet and extends them with applications of three operators: alternation, concatenation and Kleene closure.
So ask yourself: Which of these operators can produce an infinite set?

Formal definition:
Let $\Sigma$ be a finite set of symbols. Then the set of regular expressions $R_\Sigma$ is the smallest set of expressions which can be constructed using these rules:

Every $c \in \Sigma$ is in $R_\Sigma$.

$\lambda$ and $\emptyset$ are in $R_\Sigma$.

If $r$ and $s$ are regular expressions over the alphabet $\Sigma$ then so are:

$(r+s)$
$(rs)$
$(r^*)$

A standard proof technique for properties of regular expressions is to apply mathematical induction to this definition.


number of pair of vertices with at least 2 distinct paths between them in a undirected graph

I'm assuming that you're looking for the number of pairs of vertices having two disjoint simple paths connected them. A pair of vertices has two disjoint simple paths connecting them if they are in the same biconnected component. You can partition the graph into biconnected components in linear time. If the biconnected components have sizes $N_i$, then the number of pairs is $\sum_i \binom{N_i}{2}$.


Running time of recursive algorithm with geometric series

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \sum_{i = 0}^k{(3/2)^i} cn$$

The recursion will reach the base case when $2^k = n$ (i.e., $k = \log n$).
And it is common to suppose the base case is $T(1) = 1$ (or $T(1) = d \textrm{ for some constant } d$).

Then (please check the details),

$$T(n) \le 3^{\log n} + \sum_{i = 0}^{\log n}{(3/2)^i} cn = n^{\log 3} + 3cn^{\log 3} - 2cn = (3c+1) n ^{\log 3} - 2cn$$


In propositional logic how is the negation equivalent?

First thing is to accept and understand, that $A \Rightarrow C$ is same as $(\neg A) \lor C$. Using your example we obtain, that "If the battery is charged, then the phone is working" is same with "the battery is not charged or the phone is working".
Now following initial sentence $(A \land B) \Rightarrow C$ we have $\neg(A \land B) \lor C$, where last sounds as "not fulfilling (the battery is charged and the screen is not cracked) or (the phone is working)".
Now we come to negation of $\neg(A \land B) = (\neg A) \lor (\neg B)$. So sentence "not fulfilling (the battery is charged and the screen is not cracked)" is same as "(the battery is not charged) or  (the screen is cracked)"
Putting everything together we have
$$(A \land B) \Rightarrow C \text{ is same with } (\neg A)  \lor (\neg B) \lor C $$
in words last is "(the battery is not charged) or  (the screen is cracked) or (the phone is working)"


An NP-hard problem reduces to its complement?

First note that $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard since $X$ is $\mathcal{NP}$-hard (try to see why).
Since 3SAT is in $\mathcal{NP}$, any problem that can be reduced to 3SAT is in NP as well. So the statement suggests that the $\operatorname{co\mathcal{NP}}$-hard language $\overline X$ is in $\mathcal{NP}$.

On the other hand, saying that $\overline{X}$ is in $\mathcal{NP}$ is equivalent to saying that $X$ is in $\operatorname{co\mathcal{NP}}$. So in total we have $X \in \operatorname{co\mathcal{NP}}$ and $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard. So we get $X \leq_m^p \overline X$ by the definition of hardness.

Here is a bit of intuition of the fact that, if $X$ is $\mathcal{NP}$-hard, then $\overline{X}$ is $\operatorname{co\mathcal{NP}}$-hard.

Let $A$ be an arbitrary language in $\operatorname{co\mathcal{NP}}$. We have to show that $A \leq_m^p \overline{X}$. Let $B := \overline{A}$. Then $B$ is in $\mathcal{NP}$ and hence, $B \leq_m^p X$. This means there is a function $f$ computable in polynomial time, such that for an arbitrary word $x$, $x \in B$ if and only if $f(x) \in X$.

Now we show that $A \leq_m^p \overline{X}$. For a given word $x$. Using the same reduction $f$, we have $x \in A$ if and only if $x \notin B$ if and only if $f(x) \notin \overline{X}$ if and only if $f(x) \in X$.

Another note. Your intuition was right, but in the sentence

  I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

You should have probably said $\mathcal{NP}$ = $\operatorname{co\mathcal{NP}}$.


Is there any guarantee in asynchronous systems?

Your question is somewhat unclear. In asynchronous systems we normally assume that any message will eventually be delivered after some finite time. It if perfectly feasible to write an algorithm that sends infinitly many messages:
While(true):
   Send a message to p;
   If received message form p do <...>

This is valid and will indeed cause infinite number of message exchange. But the timings of these messages are unknown.
I am not sure what you mean at your second point. If there are no link-failures, all edge-cuts remain alive. As long as the processors are correct, the link will be utilized infinitely often.


Strengthening a given attack on discrete log

Suppose that we had a stronger guarantee: $A'$ is a randomized algorithm, and for every $b$, $\Pr[A'(b) = \log_g b] > 1/2$, over the randomness of the algorithm. In that case, you would construct $A$ by running $A'$ several times, and checking each output until you get one that satisfies $g^{A'(b)} = b$.
Now suppose that the guarantee is $\Pr_b[A'(b) = \log_g b] > 1/2$. You would like to somehow get "independent samples" of $A'(b)$. You can accomplish that using randomized self-reducibility. I'll let you fill that out since it's your exercise. The resulting algorithm is randomized, but by choosing the optimal randomness, you get a deterministic (but non-uniform) algorithm with the same guarantees.


Restricted version of the Clique problem?

This sounds like you are asking whether or not the NP-complete clique problem can be solved in logarithmic space. Using Turing machines, one tape is read only and stores the input graph. The other tape is bounded so that there's $c \lg n$ space available for some constant $c$. The class of problems solvable in this model is known as $L$, deterministic logarithmic space. (See wikipedia or in the complexity zoo)

It is unknown whether $\mathrm{CLIQUE} \in L$, but a positive answer would imply that $P = NP$, so you (almost surely?) won't find an answer. $L \subseteq P \subseteq NP$ and $\mathrm{CLIQUE} \in L$ implies $\mathrm{CLIQUE} \in P$, which implies $P = NP$.

Edit in case I misinterpreted the problem:

If you intend that the $k$ in $ \lg n^k = k \lg n $ is the same as the clique size $k$ (i.e. the amount of memory scales with input $k$), then there's a simple brute force algorithm: you can loop through all possible sets of $k$ nodes and check if they form a $k$-clique. A starting point for searching for better solutions might be the references of [1].

[1] Virginia Vassilevska, "Efficient algorithms for clique problems" pdf link


Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $

The reduction you suggest can be a bit simplified, by running the machines serially rather than "in parallel". That is, First check if $M$ accepts $\epsilon$, and if it does, run $M'$ on $w'$.

Your idea is to make sure that if $M$ accepts $\epsilon$, then the language of $f(\langle M\rangle)$ is $A_{TM}$, and otherwise it's empty.

We can do a similar thing to show that the language is not in RE, but it requires a bit more subtlety:

We show that $A_{\overline{TM,\epsilon}}\le_m L$ as follows. Given $\langle M \rangle$, the reduction outputs a machine $f(\langle M \rangle)$, which on input $\langle M',w' \rangle$ works as follows:

Simulate the run of $M$ on $\epsilon$ for $|\langle M',w' \rangle|$ steps.
If $M$ does not accept $\epsilon$ during that simulation, simulate $M'$ on $w'$ and answer whatever it answers.
Otherwise, if $M$ accepts $\epsilon$ during that simulation, reject.

Now, the crux of the construction is in step 1, where we simulate for a finite number of steps, but this number depends on the input, so it can grow arbitrarily large.

What we get is that if $M$ does not accept $\epsilon$, then we'll always get to step 2, so $L(f(\langle M\rangle))=A_{TM}$, and all is well.

However, if $M$ does accept $\epsilon$, then we get something a bit strange - for some small inputs, it may still be the case that we'll get to step 2. But for large enough inputs, we'll get to step 3. This means that $L(f(\langle M\rangle))$, so clearly there is no reduction from $A_{TM}$ to it, and we're done.


Could a standardized ternary system be more efficient than the binary system?

Whether this is more efficient depends on the physical properties of the medium, not on any fundamental principle of computer science.  And of course there's no reason to limit yourself to ternary systems; we can consider systems with $k$ levels, where $k$ is any integer with $k \ge 2$ (it doesn't have to be limited to $k=2$ or $k=3$).

For instance, Wifi apparently uses BSK (a binary system, $k=2$), QPSK (a quad-level system, $k=4$), 16-QAM (a 16-level system), or 64-QAM (a 64-level system).
Cable TV apparently uses 64-QAM and 256-QAM, which is a modulation scheme that uses $k=64$ or $k=256$ different levels.  Why?  Because this is more efficient than using a binary ($k=2$) system.  There are many other examples like this in the communications world.

On the other hand, digital circuits -- as typically used in a CPU -- seem to be most effective with two-level modulation (i.e., binary, $k=2$).  Why?  The physics are different.

So, yes, sometimes this is more efficient, and sometimes it is not.  It all depends on the specific properties of the hardware you're working with.  Those properties are a matter of electrical engineering and physics, rather than of computer science.

There's lots more on this subject at Ternary processing instead of Binary, Why Do Computers Use the Binary Number System (0,1)?, and Could computer architecture be reworked to support switching from binary to ternary, for example?, for starters.


Complexity class for concurrent algorithms

Parallel complexity uses the same Landau notation but a different machine model, usually the PRAM which allows polynomially many processors (in the input size). This gives rise to complexity classes like NC.

If you are into algorithms outside of massively-parallel settings, this is all quite useless: the existence of PRAM algorithms does not tell you anything about algorithms on "real" computers, i.e. such with finitely many processors.


Finding the longest path in an undirected node-weighted tree

No, your algorithm does not work sometimes.

Here is a counterexample. Let graph $G$ have five weighted nodes, $A\mapsto 1$, $B\mapsto -1$, $C\mapsto 0$, $D\mapsto 1$, $E\mapsto 1$. There are four edges, $AB$, $BC$, $CD$ and $CE$.

Let us run your algorithm.

Select node $B$ and run DFS($A$). We may get the maximum weight simple path $B, A$, whose weight is 0.
Run DFS($A$), we may find the maximum weight simple path that starts at $A$, which is $A, B, C, D$, whose weight is 1. That path is returned.

However, the simple path with the maximum weight is actually $D,C,E$ whose weight is $2$.


Find most valuable subset of a node weighed tree

I forget the name but it's a classic minimum-cut problem. You can always consider min-cut approach when you want to choose an optimal subset.

(Edit: It's called "project selection problem".)

Think about cutting nodes into two partitions $S$, $T$ and $S$ is what we choose. Ideally we want $S$ to contain all the positive nodes and avoid any negative node. However, it's not always possible. If there exists an edge $(u,v)$, $u\in S\to v\in S$. In the min-cut model, it means we can't cut this edge, so we set $capacity(u,v)=\inf$. Next consider what we should pay if we can't assign them ideally.

Create a source $s$ and a target $t$. For each node $u$, if $w_u$ is positive, add an edge $(s,u)$ and set $capacity(s,u)=w_u$. It means we lose $w_u$ if $u\notin S$. If $w_u$ is negative, add $(u,t)$ and set $capacity(u,t)=-w_u$. It means we lose $-w_u$ if $u \in S$.

The answer is $\sum_{w_u>0} w_u-min cut(s,t)$, and $M$ is the source partition.


Some other usages of the type Unit (I'm sure the list is not exhaustive):

(1) The value of type Unit is used to simulate functions of arity 0 in strict languages that don't have zero-argument functions, like in OCaml: f (). Essentially this is just for deferring computations.

(2) It also can be used to instantiate some parametrically polymorphic type when the actual "payload" is not some data, but the shape of a data structure, like when it's only the length of a list is of interest to us.

(3) Unit is used in dependently typed languages, for instance as a type-level analogue of the empty list or a dummy value.
A simple example in Coq:

Fixpoint nat_to_tuple (n : nat) : Set :=
match n with
  | O => unit                 (* ! *)
  | S n' => nat * nat_to_tuple n'
end % type.

Eval compute in (nat_to_tuple 3).

(* Evaluates to (nat * (nat * (nat * unit)))
   Note: unit in Coq corresponds to Unit in the question;
         nat is the type of natural numbers;
         Set is the type of types of programs.
 *)

You might want to take a look at a more educational (but longer) example on implementing the head function(hd) for length-indexed lists in the Certified Programming with Dependent Types book by A. Chlipala.


Algorithm to create n arrays with maximum difference

This problem is posed and solved in Ahlswede and Katona, Contributions to the geometry of Hamming spaces, page 10. If the number of vectors $N$ is even, the best solution is to choose $N/2$ pairs of a vector and its complement (obtained by switching 0s and 1s). If $N$ is odd then choose $N/2$ such pairs and add an arbitrary vector.

Curiously enough, if you want to minimize the average distance, then the answer is still unknown, though it is suspected to be a Hamming ball.


Your intuition is correct, the work is in identifying the things you're adding together.

The first bit is that printing a string of length $m$ takes $m$ operations, so the

System.out.println(input.substring(i,j));

line takes $j-i$ operations. (A side note here is that this code is in Java, unless I'm very much mistaken, and the substring(start, end) method gives the substring beginning at index start and ending at end-1)

So then at each iteration of the outer loop, we're printing a bunch of substrings, starting with a string of length one (just the character at index $i$) and ending with the substring that starts at $i$ and goes to the end of the string input.

To put that a dash more mathematically we're printing strings of length $1, 2, \ldots, n-i$. As the number of operations  required to print a string is the same as its length, we're doing $\sum_{k=1}^{n-i}k$ operations. Substituting Gauss's formula for this sum, we get that the number of operations is equal to:
$$
\frac{(n-i)(n-i+1)}{2}
$$

Then multiplying everything out gives the formula you have in your slides.


Floyd–Warshall algorithm on an undirected graph contains negative weight edges

Perhaps it is useful to be more precise about what is meant by "doesn't work".  If the directed graph contains a cycle of negative weight, then the notion of shortest path is not well-defined.  Therefore, it makes no sense to run a shortest-path algorithm on such a graph.   There's no hope for any algorithm to output the shortest path in such a graph, because there is no shortest path.

If you have an undirected graph with negative-weight edges, and you convert it to a directed graph in the obvious way, you'll end up with a directed graph that contains negative-weight cycles.  Consequently, no shortest path algorithm has any hope of success at finding shortest paths: there is no directed path (in the directed graph).  It doesn't matter what algorithm you are considering using.

Basically, the conversion from undirected graph to directed graph, in shortest path problems, is only correct if all weights are non-negative.  If all edge weights are non-negative, then the shortest path in the undirected graph corresponds to the shortest path in the directed graph you obtain in this way.  However, if the undirected graph has negative-weight edges, then there is no longer any such correspondence, so the conversion is not useful.


Product construction for given two finite automata

Here is a product construction for finite automata. I am considering you have two finite automata $M_1$ and $M_2$.
Let $M_1$ = $(Q_1,\Sigma ,\delta_1,q_{01},F_1)$ and $M_2$ = $(Q_2,\Sigma ,\delta_2,q_{02},F_2)$ be two finite automata with the same input alphabet.
Let us define $M$ such that

$$L(M) = L(M_1) \cap L(M_2) $$

Finite automata for $L(M)$ is defined as $M$ = $(Q,\Sigma ,\delta,q_0,F)$ , where
$Q$ is a finite set of states, $\Sigma$ is a input alphabet, $q_0$ is a start state, $\delta$ is a transition function and $F$ is final state of a finite automata $M$.

$Q$ = $Q_1$ X $Q_2$ (Cartesian product),
$\delta((q_1,q_2),a) = (\delta_1(q_1,a),\delta_2(q_2,a))$,
$q_0 = (q_{01},q_{02})$,
$(q_{1},q_{2}) \in F $ iff $q_1 \in F_1 $ and $q_2 \in F_2$.

Each state in $Q$ is a pair consisting of a state from $Q_1$ and a state from $Q_2$.
Reference : the Product Construction for Automata by Laura Kovács.


CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}

The string $bbaaa$ is not in the language, as Draconis pointed out (its prefix $b$ contains more $b$'s than $a$'s). As such, the second grammer is wrong.

However, the first suggestion is also wrong. It does not accept the string $abaaaa$, which belongs to the language.

The correct grammar is:

$$S \to \epsilon \mid aS \mid aSbS$$

To see that every word accepted by this grammar indeed belongs to the language, a straight-forward induction proof will do. So let's check that every word where each prefix has at least as many $a$'s as $b$'s is accepted by our grammar.

If the word is empty, we are done. Else it has to start with an $a$. There are two cases.

There is one prefix of the word that has an equal number of $a$'s and $b$'s. Write the word as $awbv$ where $awb$ is the shortest such prefix. Both $w$ and $v$ must belong to the language, so we can use the rule $S\to aSbS$.
Every prefix of the word has more $a$'s and $b$'s. Write the word as $aw$. Then $w$ must belong to the language, so we can use the rule $S \to aS$.


Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

I don't know of a reference, but there's a standard reduction from Hamiltonian paths/cycles to SAT which is fairly well-known. The reduction from SAT to 3SAT is then done by introducing additional variables to break up clauses, e.g.:

$$v_1 \vee \neg v_2 \vee v_3 \vee \neg v_4 \Rightarrow \left( v_1 \vee \neg v_2 \vee X\right) \wedge \left( v_3 \vee \neg v_4 \vee  \neg X\right)$$

Let $n$ be the number of nodes in the graph. Then define variables $x_{i,j}$ where $i,j \in \left\{1 \ldots n\right\}$, where $x_{i,j}$ is true if node $i$ appears in position $j$ in the Hamiltonian path.

Every node must appear somewhere on the path:

$$\bigwedge_{i} \left( \bigvee_{j} x_{i,j}\right)$$

Every position in the path must be occupied:

$$\bigwedge_{i} \left( \bigvee_{j} x_{j,i}\right)$$

No node appears on the path more than once:

$$\bigwedge_{i} \bigwedge_{j \ne k} \left( \neg x_{i,j} \vee \neg x_{i,k} \right)$$

No two distinct nodes occupy the same position:

$$\bigwedge_{i} \bigwedge_{j \ne k} \left( \neg x_{j,i} \vee \neg x_{k,i} \right)$$

Nonadjacent nodes cannot be adjacent on the path. If $E \subseteq N \times N$ is the set of edges:

$$\bigwedge_{k \ne \left|N\right|}\bigwedge_{(i,j) \not\in E} \left( \neg x_{k,i} \vee \neg x_{k+1,j}\right)$$

You can modify this in the obvious way if you're trying to find a Hamiltonian cycle.

On that, as a practical matter, if you are trying to find a Hamiltonian cycle and you intend to feed this to a SAT solver, you would normally assert a start node as another clause, e.g. $x_{1,1}$, to reduce the search space. Obviously for Hamiltonian paths, you don't do that.


In what ways can we distinguish between a human and bot behavior?

The most common/obvious way is a challenge-response test that is easy for humans but hard for computers (of course, but not only, CAPTCHA).

This kind of test is very effective{1} but falls under the HIP (Human Interactive Proofs) area: it's not transparent.

Typical, "simple" approaches to distinguish human website traffic from Bot are:

time it takes to populate all the fields and click the submit button of an input form (frequently used but simple to bypass).

Watching the cadence / pace of the communication is a more secure alternative (this is one of the feature of Google's No CAPTCHA reCAPTCHA);
honeypots (i.e. traps for bots that consist of a link or field present on the page that isn't visible to the human eye)
analysis of maximal continuous session length (humans have to rest) and correlation with time of day (see Distinguishing Humans from Bots
in Web Search Logs)

It must be considered that bot characteristics exhibit a wide variability for different crawler / different sites, therefore it's difficult to derive simple, deterministic heuristics: rule based systems imply a long list of static rules that are difficult to define and maintain (even by experts).

Machine learning techniques are often used:

Web robot detection: A probabilistic reasoning approach constructs a Bayesian Network that classifies automatically log sessions as being crawler or human induced
Discovery of web robot sessions based on their navigational patterns
uses C4.5 decision tree algorithm (after deriving the session features)
Detecting Click Fraud in Pay-Per-Click Streams of Online Advertising Networks develops Bloom Filter-derived techniques.
Neural networks applied to speed cheating detection in online computer games adopts an artificial neural network for bot detection in MMORPGs
Using Sentiment to Detect Bots on Twitter: Are Humans more Opinionated than Bots? tries Gaussian naive Bayes, Support Vector Machines and  Random Forests

Almost every available AI/ML "tool" has been experimented. The main problem using these supervised machine learning tools is labeling the training dataset.

Even restricting the analysis to network-oriented behavior, this is a question of tremendous scope, for this reason I'm giving some keywords for further searches.

Notes

Machine Learning based attacks are improving and CAPTCHAs also serves as a benchmark task for artificial intelligence technologies (e.g. The End is Nigh: Generic Solving of Text-based CAPTCHAs)

Keywords

HIP (Human Interactive Proofs), CAPTCHA, Keystroke dynamics, Keystroke cadence, typing dynamics, IDS (Intrusion Detection System), honeypot, click fraud, spambot

References

Designing Human Friendly Human Interaction Proofs (HIPs) by Kumar Chellapilla, Kevin Larson, Patrice Simard, Mary Czerwinski (Microsoft Research)
The End is Nigh: Generic Solving of Text-based CAPTCHAs by Elie Bursztein, Jonathan Aigrain, Angelika Moscicki, John C.Mitchell (2014)
Keystroke Dynamics User Authentication Based on Gaussian Mixture Model and Deep Belief Nets by Yunbin Deng, Yu Zhong (2013)
User Authentication Through Typing Biometrics Features by Lívia C. F. Araújo, Luiz H. R. Sucupira Jr., Miguel G. Lizárraga, Lee L. Ling, andJoão B. T. Yabu-Uti (2005)
Distinguishing Humans from Bots in Web Search Logs by Omer M. Duskin Dror, G. Feitelson
Web robot detection: A probabilistic reasoning approach by Athena Stassopouloua, Marios D. Dikaiakos (2008)
An investigation of WWW crawler behavior: characterization and metrics by M.D. Dikaiakos, A. Stassopoulou, L. Papageorgiou (Computer Communications, 2005)
Discovery of web robot sessions based on their navigational patterns by Pang-Ning Tan, Vipin Kumar (2002)
Telling humans and computers apart automatically by Luis von Ahn, Manuel Blum, John Langford (Comm. ACM, 2004)
Detecting Click Fraud in Pay-Per-Click Streams of Online Advertising Networks by Linfeng Zhang, Young Guan (IEEE, 2008)
Bots Problem in Online Games by Dewanshu Jain, Alok Gupta
Neural networks applied to speed cheating detection in online computer games by Gaspareto, Barone, Schneider (2008)
Quantifying Online Advertising Fraud: Ad-Click Bots vs Humans by Adrian Neal, Sander Kouwenhoven (2015)
Comparison of Classification Algorithms to tell Bots and Humans Apart by Christian Hadiwijaya Saputra, Erwin Adi, Shintia Revina, Bina Nusantara (2014)
Using Sentiment to Detect Bots on Twitter: Are Humans more Opinionated than Bots? by John P. Dickerson, Vadim Kagan, V.S. Subrahmanian (2014)


Proving the language which consists of all strings in some language is the same length as some string in another language is regular

Remember (or come up with) the proof for

$\qquad \displaystyle L_1, L_2 \in \mathsf{REG} \implies L_1 \cap L_2 \in \mathsf{REG}$.

Do you see how to modify the proof for your setting?

   Abstracting the equality of lengths thing, come up with a construction for an automaton for

 $\qquad \displaystyle L_l = \{ w \in \Sigma^* \mid \exists x \in L.\, |x|=|w|\}$

 for given, arbitrary $L \in \mathsf{REG}$ over $\Sigma$.

Do you see the connection?

   Now note that $L = A \cap B_l$.


I believe you have one bus too many. Taking the image from teach-ict.com:

The diagram shows two buses with memory and one internal bus. One memory bus fetches instructions (stored in memory) to the Control Unit and data (stored in the same memory) to the ALU. The second bus is the Address Bus which says which memory to read or write (both for instructinos and data).

The Control Unit decodes the instruction and tells the ALU what to do (add, subtract, divide...). The Control Unit and the ALU together are called the CPU.

There is no separate Control Bus with the memory. The Control "Bus" is internal in the CPU.

In the Harvard Architecture there is physically separate memory for instructions and data. It means there are 4 buses, 2 data buses (1 for instructions and 1 for data) and two address buses (1 to address the instruction memory and 1 to address the data memory). The "Control Unit" in the diagram is the combined Control Unit and ALU from the previous diagram, the CPU. Any Conrol "Bus" is internal to that unit.

To summarize the answer: a Control Bus is internal to the CPU and should not be considered in discussing interactions with memory. There is no Control Bus with memory.

(Note: The Input and Output shown in the Von Neumann diagram should be ignored, or should be considered also present in the Harvard Architecture.)


How does time/space complexity work with lisp

You get the fib(n) running time if you only expand one invocation of fib at a time. You haven't been told the exact execution model for several reasons:

It is messy.
It's not important.
It could depend on the implementation.
You need to worry about low-level stuff such as the complexity of integer operations.

The reason it's not important is that when measuring complexity we only care about the order of growth of the number of operations. So if a certain basic operation takes 3 or 13 units of time, it makes no difference for us.


Why does it take $O(f(n)^2)$ to simulate a 3-tape $O(f(n))$-time TM on a 1-tape  TM?

Have a look in the book of Hopcroft and Ullman "Introduction to automata theory, languages and computation" (ISBN 0-201-02988-X). I have only the German version of this book, but there it is mentioned as Theorem 12.5.

However the basic idea behind the tape-reduction from $k$ tapes to 1 is quite easy. Assume the running time is bounded by $f(n)$. You boost you working alphabet $\Gamma$, such that every super-character represents $k$ original characters and $k$ Flags. The flags store the position of the head of the corresponding simulated tape. To simulate one step of the old machine, we have to scan through the whole tape. However, the tape contains at most $O(f(n))$ characters, hence the scan needs $O(f(n))$ time. Since we simulate $O(f(n))$ steps the 1-tape machine runs in $O(f(n)^2)$. I think from here you can work out the details on your own.


How to find loop invariant from weakest precondition?

I'm only familiar with elementary hoare logic, which does not
account for returns/exits, which must be mimicked by booleans.
So let's rewrite your program to do just that.
In fact, it becomes easier to understand once we do so!

i ≔ N - 1 ;
found ≔ a[i] ≈ key;
while ¬found ∧ 0 ≤ i-1:
  i ≔ i - 1;
  found ≔ a[i] ≈ key;

Where we define

$$  N : a.length $$

Notice that we have 0 ≤ i - 1 instead of 0 ≤ i since after the decrement
i ≔ i - 1 the look-up a[i] in the next statement might not be well-defined.
So the loop guard ensures that the decrement is still non-negative and so
the look-up is well defined. In particular, look at case i ≈ 1; then
0 ≤ 0 ≈ 1 - 1 ≈ i - 1 and the loop decreases i to 0 and
the look-up is defined; afterwards the test 0 ≤ 0 - 1 fails and the loop
terminates.

Now your postcondition speaks of the return value, which is essentially just i, so let's simplify that to obtain

$$  R : 0 ≤ i < N ⇒ a[i] ≈ key $$

Now the postcondition ought to follow from the negation of the loop guard and the loop invariant: so let's take the invariant to be

$$P : i < N ∧ (found ≡ a[i] ≈ key)  % \text{  (we always have i < N and found is true iff a[i] ≈ key)} $$

then after the loop we have the post condition can be seen:

  after-loop we have the loop guard fails and the invaraint still holds
≡⟨ foramlise ⟩
  (found ∨ i-1 < 0) ∧ (i < N ∧ (found ≡ a[i] ≈ key))
⇒⟨ substitution ⟩
  (a[i] ≈ key ∨ i-1 < 0) ∧ i < N
⇒⟨ weakening: A ∨ B ⇒ A ∨ B ∨ C ⟩
  (a[i] ≈ key ∨ i-1 < 0 ∨ i < 0) ∧ i < N
≡⟨ arithmetic ⟩
  (a[i] ≈ key ∨ i < 0) ∧ i < N
≡⟨ implication ⟩
  (0 ≤ i ⇒ a[i] ≈ key) ∧ i < N
⇒⟨ weakening ⟩
  0 ≤ i < N ⇒ a[i] ≈ key

and that's the post-condition!

For ease of reference, let the guard be denoted by B; i.e.,

$$  B : ¬ found ∧ 0 ≤ i - 1 $$

We still haven't actually proved that P is an invaraint: ie that it does not vary with the
changes that occur in the loop body and that it is initally true i.e. we need to show

$$  \{ ? \}    i ≔ N - 1 ; found ≔ a[i] ≈ key \{P\} $$
  and
$$  \{P ∧ B\}  i ≔ i - 1 ; found ≔ a[i] ≈ key \{P\} $$

Initialisation is seen as follows:
the wp for assignment tells us: $$wp(Q , v ≔ e) = e \text{ well-defined } ∧ Q[e / v]$$, so applying twice means we need to have
the following as pre-condition:

  wp(P , i ≔ N - 1 ; found ≔ a[i] ≈ key)
≡⟨ sequence rule ⟩
  wp( wp(P , found ≔ a[i] ≈ key) , i ≔ N - 1)
≡⟨ assignment rule ⟩
  wp( a[i] well-defined ∧ P[ a[i] ≈ key / found ] , i ≔ N - 1)
≡⟨ definitions ⟩
  wp( 0 ≤ i < N ∧ i < N ∧ (a[i] ≈ key ≡ a[i] ≈ key) , i ≔ N - 1)
≡⟨ equivalence ⟩
  wp( 0 ≤ i < N , i ≔ N - 1)
≡⟨ assignment rule ⟩
  0 ≤ N-1 < N
≡⟨ arithmetic ⟩
  1 ≤ N

So the precondition is that the array is non-empty and in-particular is non-null (the well-definedness condition that you
mentioned).

For the invariance part we need to show

   {P ∧ B}  i ≔ i - 1 ; found ≔ a[i] ≈ key {P}
≡⟨ assignment rule ⟩
   {P ∧ B}  i ≔ i - 1 {0 ≤ i < N ∧ (found ≔ a[i] ≈ key ≡ a[i] ≈ key)}
≡⟨ reflexivitivy of equivalence ⟩
   {P ∧ B}  i ≔ i - 1 {0 ≤ i < N }
≡⟨ assignment rule ⟩
   P ∧ B ⇒ 0 ≤ i - 1 < N
≡⟨ definitions ⟩
   true

Sweet!

So the program now has annotations:

{ 1 ≤ N } // array is non-empty
i ≔ N - 1 ;
found ≔ a[i] ≈ key;
{invariant P }
while !found ∧ 0 ≤ i - 1:
  i ≔ i - 1;
  found ≔ a[i] ≈ key;
{ R }

We've only shown "partial correctness", for complete correctness we must
prove termination. In particular, we need to find a bound function bf
that is initially positive and
is decreased by the loop body: want bf such that for any constant t,

{ bf = t }   i ≔ i - 1; found ≔ a[i] ≈ key { bf < t }

Since during the loop body we always have P ∧ B and so namely 0 ≤ i - 1,
let's take the bound to be

$$  bf : i $$

Now since $B ⇒ 0 ≤ i-1 ⇒ 1 < i ⇒ 0 < bf$ we have that bf is initially positive.
(One might be tempted to try N-i as bound but that fails since the loop decreases
i which means that N-i increases!)
It remains to check that it is decreasing: for any t, we have

  { bf = t }   i ≔ i - 1; found ≔ a[i] ≈ key { bf < t }
≡⟨ assignment rule ; bf does not mention varaible `found` ⟩
  { bf = t }   i ≔ i - 1 { bf < t }
≡⟨ assigment rule ⟩
  bf = t ⇒ bf[ i-1 / i] < t
≡⟨ definitions ⟩
  i = t ⇒ i - 1 < t
≡⟨ arithmetic ⟩
  true

Alright! That was pretty fun!

One final note, if you write this, say in Python, or another language that
supports parallel assignment, you can make the program even more succinct!

i, found ≔ N - 1 , a[i] ≈ key;
while ¬found ∧ 0 ≤ i-1:
  i, found ≔ i - 1, a[i] ≈ key

Enjoy!


If $f = \prod_{i=1}^d x_i$ is a single monomial then
$$
\Pr[f=0] = 1 - \left(1 - \frac{1}{|\mathbb{F}|}\right)^d \geq \frac{d}{|\mathbb{F}|} - \frac{d^2}{2|\mathbb{F}|^2}.
$$
(The second bound is Bonferroni's inequality.)
This shows that Schwartz–Zippel is essentially tight when $d$ is small compared to $\mathbb{F}$.
The bound $1-(1-1/|\mathbb{F}|)^d$ is tight for multilinear polynomials, see this answer on math.se.


What should I call algorithms with non-linear non-constant time?

As mentioned by Bryce Kille in the comments, superlinear is what you are looking for. From Wiktionary:

  (mathematics) Describing a function that eventually grows faster than any linear one

(By the way, the first phrase in your question strikes me as rather odd: "[...] I want to refer to a group of algorithms that are mostly polynomial-time, but one of them is of complexity $O(N \log N)$." Do you simply mean "linear" instead of "polynomial-time"?)


What is the Big O time complexity of this algorithm?

The O(n log n) eventually grows faster than the O(n) algorithm. We always take the fastest growing component of the algorithm when deciding the complexity, so you're right that the total complexity of the algorithm is O(m n log(n))


Is Group Theory useful in Computer Science in areas other than cryptography?

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory.
An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with groups.


Finding the Shortest path in undirected weighted graph

All-Pairs-Shortest Path

Given a graph $G = (V, E)$ find the shortest path between any two nodes $u,v \in V$. It can be solved by Floyd-Warshall's Algorithm in time $O(|V|^3).$ Many believe the APSP problem requires $\Omega(n^3)$ time, but it remains open if there exists algorithms taking $O(n^{3 - \delta} \cdot \text{poly}(\log M))$, where $\delta > 0$ and edge weights are in the range $[-M, M]$.

The reasoning for this is upon close examination we see that the APSP problem can be solved by matrix multiplication. If we replace the operators to $\{\text{min}, +\}$ instead of $\{ +, \cdot \}$ we may use the framework for matrix multiplication to compute the solution. What is interesting is if there exists sub-cubic algorithms for the APSP problem, then there exists sub-cubic algorithms for many related graph and matrix problems [1].

[1] Subcubic Equivalences Between Path, Matrix, and Triangle Problems


Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

Yes, if $x$ and $y$ are chosen independently of each other.

One way to quickly see this is to note that the map $x \mapsto x \oplus y,$ for some constant $y,$ is a permutation of $\{0,1\}^n.$  This means that if $x$ is uniformly distributed over $\{0,1\}^n$ and $y$ is constant, then $x \oplus y$ is also uniformly distributed.  And since $x \oplus y$ is uniformly distributed for every constant $y,$ it follows that, if we make $y$ itself a random variable (independent of $x$), then the distribution of $x \oplus y$ will be a mixture of uniform distributions, and thus uniform.

Or we can just do the math:

$$\begin{aligned} {\rm P}(x \oplus y = a)
&= \sum_{b \in \{0,1\}^n} {\rm P}(x \oplus y = a \land y = b) \\
&= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b \land y = b) \\
&= \sum_{b \in \{0,1\}^n} {\rm P}(x = a \oplus b)\ {\rm P}(y = b) & (x \perp y) \\
&= \sum_{b \in \{0,1\}^n} \frac1{2^n}\ {\rm P}(y = b) & (x \sim \mathcal U\{0,1\}^n) \\
&= \frac1{2^n} \sum_{b \in \{0,1\}^n} {\rm P}(y = b) \\
&= \frac1{2^n}.
\end{aligned}$$

However, the assumption of independence is absolutely necessary here — without it, it's easy to come up with counterexamples, such as letting $x$ be uniformly distributed over $\{0,1\}^n$ and letting $y = x,$ which of course implies that $x \oplus y = 0^n.$


find if a string is periodic using a suffix tree, and prove it

It's wrong. Consider $aaaabb$, so you'll find that $aaa$ repeat twice and consider it as an answer, while it is obviously not.

Check each suffix with length $n>l\ge\frac{n}{2}$. If it's also a prefix of $s$, $s$ is periodic and $u$ is the prefix with length $n-l$. If you can't find such suffix $s$ is not periodic. The proof is straight forward: $s[i]=s[i+n-l]$ for $1\le i \le l$. So you can easily prove that $s[n-l+1..2(n-l)]=u$, and so on. Since $n-l\le\frac{n}{2}$, $u$ repeat at least twice. The converse is similar, by proving $s[i]=s[i+len(u)]$.

KMP or Z-algorithm are sufficient to do this, but if you really need a suffix tree solution:

Check each node on the path from root to the leaf which represents the whole string. If a node on this path represents a suffix with length $\ge\frac{n}{2}$ (except the whole string), we find the answer. (Note that each node on this path represents a prefix.)


transformation of constraint satisfaction to SAT

I'm not sure what you mean by CSP, but suppose that you mean the following: there are $n$ binary variables and $m$ constraints. Each constraint is associated with a $k$-tuple of (distinct) variables, for some $k$ depending on the constraint, along with a subset of $\{0,1\}^k$ which is the allowed assignments for the $k$-tuple of variables.

For example, graph coloring, or rather, whether a given graph $G$ can be $\chi$-colored, can be viewed as a CSP. If there are $n$ vertices (we identify the vertex set with $\{1,\ldots,n\}$) then we have $n$ groups $x_1,\ldots,x_n$ of $\lceil \log_2 \chi \rceil$ variables. For each $i \in \{1,\ldots,n\}$ there is a constraint on each group $x_i$ stating that the assignment for $x_i$ is the binary encoding of a number in the range $\{0,\ldots,\chi-1\}$. For any two connected vertices $(i,j)$ there is a constraint on both groups $x_i,x_j$ stating that $x_i \neq x_j$. This CSP is satisfiable iff $G$ is $\chi$-colorable.

In order to convert such a binary CSP to a SAT instance, we replace each constraint with the corresponding CNF. Continuing the example above, if $\chi = 2$ then for any $i,j$ there is a constraint $x_i \neq x_j$ which we realize as
$$(x_i \lor \lnot x_j) \land (\lnot x_i \lor x_j). $$
The resulting CNF is satisfiable iff the CSP is. You can use the standard reduction to convert this CNF to a 3CNF if you wish.

We can also handle CSPs which are not binary, i.e., in which the variables are not binary but rather have some finite domain. The idea is similar to how I described coloring as a CSP above, and left to the reader.


Are there algorithms to exactly minimize NFAs which are sometimes efficient?

SAT solvers have been pretty good at this. See [1] for more; the method produces a minimal automaton in almost all cases. Following some references, Tsyganov [2] combined the Kameda-Weiner with local search methods.

I don't know if there are readily available implementations out there, but at least [1] describes the reduction to SAT. One can then use any available SAT solver.

[1] Geldenhuys, Jaco, Brink Van Der Merwe, and Lynette Van Zijl. "Reducing nondeterministic finite automata with SAT solvers." Finite-State Methods and Natural Language Processing. Springer Berlin Heidelberg, 2010. 81-92.

[2] Tsyganov, Andrey V. "Local Search Heuristics for NFA State Minimization Problem." International Journal of Communications, Network and System Sciences 5 (2012).


how can this function be computed in polynomial time in regards to its input?

Let's start with solving the problem for 1-CNFs. The proof will be by example. If the truth assignment is $x_1=x_2=1,x_3=0$ then a 1-CNF for which this is the only satisfying assignment is
$$
x_1 \land x_2 \land \overline{x_3}.
$$
Now let's solve the problem for 2-CNFs, again by example. Continuing with our previous example, here is one possible construction:
$$
(x_1 \lor x_2) \land (x_1 \lor \overline{x_2}) \land
(x_2 \lor x_3) \land (x_2 \lor \overline{x_3}) \land
(\overline{x_3} \lor x_1) \land (\overline{x_3} \lor \overline{x_1}).
$$
More generally, we replace $x_i$ with $(x_i \lor x_j) \land (x_i \lor \overline{x_j})$ for an arbitrary $j \neq i$.

Your problem can be solved in a very similar way.


Time complexity for count-change procedure in SICP

Order of growth of number of steps: $\theta (n^5)$

We can prove that, in general, the order of growth of number of steps is $\theta (n^m)$, where $m$ is the number of types of coin available. Here is my (very) crude reasoning using induction:

When there is only one type of coin, the number of steps is obviously proportional to n.
Suppose it would take (cc n m) steps to change an amount of $n$ with $m$ types of coin. Now let's consider (cc n m+1): ($A$ is the denomination of the $m$th kind of coin.)

  (cc $n$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m+1$)
  = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m$) + (cc $n-3A$ $m+1$)
  = ......

It would eventually computes to

(cc n m) + (cc n-A m) + ... + (cc <something-negative> m+1)

There are approximately $n/A$ items. So the total number of steps would be proportional to $n/A*n^m$, which is proportional to $n^{m+1}$. Thus, the order of growth for number of steps of (cc n m) is $\theta (n^m)$.

Let $m$ be 5, and the order of growth of number of steps is $\theta (n^5)$.


Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?

The maximum number of elements in the heap at any given time is upper bounded by $k+1$.
Since each insertion or deletion from an heap requires $O(\log \eta)$ time where $\eta$ is the number of elements in the heap at the time of the operation, and $\eta \le k+1$, we know that each heap operation can be performed in time $O(\log (k+1) ) = O( \log k )$.
How many heap operations does the algorithm perform? Each element is inserted once, so there are $n$ insertions. In addition all but the largest $k-1$ elements are extracted. This yields a total of $n + (n-(k-1)) = 2n-k+1 = O(n)$ operations.
By multiplying the number of operations with our upper bound on the time required by each operation of $O(\log k)$  we obtain an overall time complexity of $O(n \log k)$.


Why there is a probability in the completeness part?

The standard definition of $\mathsf{IP}$ involves probability both in the completeness and soundness requirements. Removing randomness all together reduces $\mathsf{IP}$ to $\mathsf{NP}$ (the witness is the full accepting transcript).

Note that you can amplify the success probability by "repeating the protocol" (i.e. talking with a prover $P'$ who simulates repetitions) and taking the majority vote (you need to be slightly careful here, since your dealing with a special prover who has access to previous interactions, but you're saved by the universal quantifier in the soundness requirement).

If what's bothering you is the fact that the protocols you are familiar with satisfy completeness with probability $1$, then one example is the proof for graph non isomorphism being in $\mathsf{AM[2]}$, using the set lower bound protocol, where the completeness probability is smaller than 1.

That said, you can in fact remove the probability from the completeness requirement (i.e. say that there exists a prover which convinces $V$ with probability $1$, $V$ is still probabilistic) without changing the class $\mathsf{IP}$, but this is a non trivial fact, which follows from the protocol for TQBP in the $\mathsf{IP=PSPACE}$ proof (which succeeds with probability 1 in case the formula is true).


Finding solution of given recursive equation?

The trick in this case is to consider differences:
$$
T(n)-T(n-1) = \left(1 + \sum_{j=0}^{n-1} T(j)\right) - \left(1 + \sum_{j=0}^{n-2} T(j)\right) = T(n-1).
$$
Hence $T(n) = 2T(n-1)$, and so $T(n) = 2^n T(0)$.


Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?

Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the description of an ordinary Turing machine and its input and ask if that machine halts on that input. In a single step, you get an answer, and you can use that to perform further computation. (It doesn't matter whether it's in a single step or not: it would be enough if it was guaranteed to be in some finite number of steps.)

However, there are two problems with this approach.

Turing machines equipped with such an oracle can't decide their own halting problem: Turing's proof of the undecidability  of the ordinary halting problem can easily be modified to this new setting. In fact, there's an infinite hierarchy, known as the "Turing degrees", generated by giving the next level of the hierarchy an oracle for the halting problem of the previous one.
Nobody has ever suggested any way in which such an oracle could be physically implemented. It's all very well as a theoretical device but nobody has any clue how to build one.

Also, note that ZFC is, in a sense, weaker than naive set theory, not stronger. ZFC can't express Russell's paradox, whereas naive set theory can. As such, a better analogy would be to ask whether the halting problem is decidable for weaker models of computation than Turing machines. For example, the halting problem for deterministic finite automata (DFAs) is decidable, since DFAs are guaranteed to halt for every input.


Isn't Domain of a variable nothing but a constraint?

As you observe, restricting the domain of a variable has exactly the same effect as applying a unary constraint to it.

One situation where you might prefer to use unary constraints rather than restricted domains is when you want to control very tightly the relations that are allowed to be used in constraints. For example, if you want to investigate the computational complexity of CSP with a particular class of constraint languages.  On the other hand, such investigations often assume that all unary relations are included in the constraint language, which is equivalent to fixing a global domain but allowing the domain of any variable to be any subset of that.  (This is known as the "conservative" case because of certain algebraic properties of the constraint langauges.)


Partitioning planar graph cycles based on chords

If the original cycle has length $n$, there is a straightforward $O(n^5)$ time algorithm: simply guess which vertex each sublist should start at.

In other words, let the original cycle go through the vertices $v_1,v_2,\dots,v_n,v_1$.  Then you can choose indices $i,j,k,l$ (such that $1 \le i < j < k < l \le n$), where the first sublist contains $v_i,v_{i+1},\dots,v_j$, the second sublist contains $v_j,v_{j+1},\dots,v_k$, and so on (assuming index arithmetic wraps around modulo $n$).  There are only ${n \choose 4} \in O(n^4)$ possible choices for $i,j,k,l$, so you can exhaustively try them all and test each one to see whether it meets all your requirements, and then keep whichever one is best (according to your "difference-in-size" metric).

This proves that the problem can be solved in polynomial time.


In most cases in which such a reduction is presented, the reduction also works with $\infty$ replaced by a large enough number $M$ which is at most exponential in some power of $n$. If you replace $\infty$ by $M$ then you get a bona fide instance of $\Pi$, and this instance has polynomial size (and so the reduction runs in polynomial time) since $|M| = O(n^C)$ for some $C$, where $|M|$ is the length of the binary encoding of $M$.

You are right that using $\infty$ instead of $M$ is a bit sloppy, but it often results in a cleaner description, it being understood that the "real" reduction uses some large enough finite $M$.


What is second order logic in contrast to first order logic?
  What is monadic vs non monadic logic?

Monadic second-order logic is first-order logic plus quantification over sets. So, as well as being able to say that there exists a domain element with some property ($\exists x\dots$), you can also say that there exists a set of domain elements with some property. So, for example, we can define 3-colourability of graphs by saying

\begin{align*}
\exists R\,\exists G\,\exists B\, \big[&\forall x\,\big(x\in R\lor x\in G\lor x\in B\big)\\
&\land \neg\exists x\,\big((x\in R\land x\in G) \lor (x\in G\land x\in B) \lor (x\in B\land x\in R)\big)\\
&\land \forall x\,\forall y\,\big(E(x,y)\rightarrow \neg \big((x\in R\land y\in R)\lor (x\in G\land y\in G)\\
&\qquad\qquad\qquad\qquad\qquad\quad\lor (x\in B\land y\in B)\big)\big)\big]\,.
\end{align*}

In words, there are colours red, green and blue such that

every vertex has a colour
and no vertex has two colours
and, if there's an edge between two vertices, those two vertices don't have the same colour.

General second-order logic allows not just quantification over sets but also over arbitrary relations over the domain.  Recall that a relation is a set of $k$-tuples over the domain, for some $k$.  Sets are just unary relations: $k=1$ and a $1$-tuple is just an element of the domain.

  Why is it important for a second order logic to be monadic to be decidable OR why is this the wrong question?
  Why is monadic second order logic decidable?

Honestly, I don't remember the decidability issues. A key point is that full second-order logic lets you quantify into existence a linear order of the domain

\begin{align*}
    \exists R\,\forall x\,\forall y\,\forall z\,\big[&(R(x,y)\lor R(y,x)\big)\\
    &\big((R(x,y)\land R(y,x))\rightarrow x=y\big)\\
    &\big((R(x,y)\land R(y,z))\rightarrow R(x,z)\big)\big]\,.
\end{align*}

That is, there exists a binary relation that is total, antisymmetric and transitive, i.e., is a linear order on the domain $D$. That implicitly gives you a linear order on $D^n$ for any $n$, and you can use relations on $D^n$ for large enough $n$ to simulate a Turing machine tape.  But, with monadic SO, you can't do any of these things.

(I guess that, if your domain is infinite, you probably need to specify in addition that the linear order is discrete and has a minimal element; then you know that it has an initial segment that's isomorphic to the natural numbers, and that should be enough.)

On finite inputs, the existential fragment of SO – formulas of the form $\exists R_1\dots \exists R_k\,\varphi$, where the $R_i$ are relation symbols and $\varphi$ is first-order – defines exactly NP. Full second-order logic defines exactly the polynomial hierarchy.  This is exactly because of the ability to encode Turing machines and the fact that quantifying a fixed collection of relations gives you a polynomial amount of stuff to play with.

  The relation to at least DFAs?

We can represent strings over some finite alphabet $\Sigma$ by relational structures.  The vocabulary has a binary relation symbol $\leq$ that will be interpreted as a linear order, and a unany relation symbol $R_a$ for each character $a\in\Sigma$.  Each element of the domain is a character in the string, the linear order tells you what order the characters appear in and the relations $R_a$ tell you what character appears in each position.

Now, suppose we have a DFA with $k$ states and let's assume we're dealing with finite strings, for now.  We can write a formula that's broadly similar to the three-colourability formula above that says that our DFA accepts the string coded by its input.  It says that there are sets (of domain elements, i.e., positions in the string) $Q_1, \dots, Q_k$, such that $Q_i$ will be the set of positions in the string at which the automaton is in state $i$.  So assert that:

each position $j$ is in exactly one of $Q_1, \dots, Q_k$;
the first position is in $Q_1$ (assuming this is the start state);
if the $j$th position is in $Q_i$ then the $(j+1)$th position is in whatever state the automaton's transition function says it should be;
the final position is in an accepting state.

If this formula is true, the automaton must accept the string; if it's false, the automaton must reject.  For NFAs, we just say that each position is in at least one state and the final state is in at least one accepting state. For infinite inputs, we can code, e.g., the Büchi condition by saying "for all positions $j$ in the input, if $j$ is in an accepting state, there's some $j'>j$ such that $j'$ is also in an accepting state.

Right now, I don't recall the proof of the converse (that everything definable in MSO can be recognized by an appropriate automaton).  If I have time, I'll look that up and post a sketch.

Conversely, we can represent the meaning of MSO formulas by finite state automata inductively, following the construction of the automata. To do this we augment the alphabet of the automaton, by adding components that indicate the value of the free position variables $i$ and set variables $X$. If we read a string along the automaton we find exactly a single $1$ to indicate a certain postion $i$, and the positions in a set $X$ are marked likewise.

The basic formulas are $R_a(i)$ for "position $i$ has symbol $a$", $i\in X$ for "$i$ is an element of $X$" and $i<j$ for "position $i$ is before position $j$".
These formulas can be represented by the following simple finite state automata (over the augmented alphabet suited for the formula):

More complicated formulas are constructed using the Boolean connectives $\lor, \lnot$ and the existential quantifiers $\exists i, \exists X$. The intended meaning of these operators are easily translated to languages as the language operators union $\cup$, complement ${}^c$ and projection, which is the operation that removes the corresponding component from the augmented alphabet. For union we have to pay some attention to the augmented alphabets in case the two parts of the formula do not agree on the set of free variables. Projection is simple, but it will change a deterministic automaton into a nondeterministic one.


For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness?

Found their paper on ArXiv. It is quite easy to go from coloured Wang tiles to uncoloured shapes by introducing zig-zag boundaries, like a jig-saw, as illustrated in their Figure 3. So then still 23 tiles are needed, as colours are simply replaced by boundaries.

Their contribution is to move from boundaries to only rectangular tiles. The authors state in Lemma 3.3 how many rectangles are needed to replace coloured Wang tiles, and a long Section 5 is devoted to the proof of that lemma.


How do you say when a language is Turing-complete only in a trivial way?

Untyped or simply-typed lambda-calculus is Turing-complete even with no booleans at all. Adding more stuff in the language, such as boolean constants and a boolean base types, cannot make the language less powerful, therefore it is still Turing-complete.

“Turing-complete” means that there is some “reasonable encoding” under which the language can express arbitrary computations. “Reasonable encoding” is not a formal notion; what it really means is that you must say what you consider to be computation, and how natural integers are to be encoded. For example, in the lambda-calculus, computation is beta reduction, and one possible encoding of natural integers is Church numerals.

In the simply-typed lambda calculs, there are no booleans as a built-in notion, but they can be encoded:
$$\begin{align}
  \mathsf{true}_\tau &:= \lambda x\colon\tau. \lambda y\colon\tau. x \\
  \mathsf{false}_\tau &:= \lambda x\colon\tau. \lambda y\colon\tau. x \\
  \mathsf{ifthenelse}_\tau &:= \lambda f\colon\tau. \lambda g\colon\tau. \lambda b\colon(\tau\rightarrow\tau\rightarrow\tau). b \, f \, g \\
\end{align}$$

The lambda calculus with boolean constants but no corresponding destructor¹ nor any way to encode it (such as a polymorphic equality construct) does lack expressive power in a sense, but only in that it is unable to distinguish between the two boolean values. It isn't the language's computational power which is at state, but the particular encoding of booleans as the boolean constants you picked: the boolean data structure is not implemented correctly. In fact, that language does not have any boolean data structures: it has constants that you chose to call “true” and “false”, but that doesn't make them booleans given the lack of a destructor.

Consider a variant where you define the following constructors and destructor:
$$
  \dfrac{}{\Gamma \vdash \mathsf{dog} : \mathsf{daisy}} \qquad
  \dfrac{}{\Gamma \vdash \mathsf{cat} : \mathsf{daisy}} \qquad
  \dfrac{\Gamma \vdash M : \mathsf{daisy} \quad \Gamma \vdash N_0 : \tau \quad \Gamma \vdash N_1 : \tau}{\Gamma \vdash \mathsf{cheese}(M, N_0, N_1) : \tau} \\
  \dfrac{}{\Gamma \vdash \mathsf{true} : \mathsf{boolean}} \qquad
  \dfrac{}{\Gamma \vdash \mathsf{false} : \mathsf{boolean}}
$$
and the following reduction rules:
$$\begin{align}
  \mathsf{cheese}(\mathsf{dog},M,N) &\to M \\
  \mathsf{cheese}(\mathsf{cat},M,N) &\to N \\
\end{align}$$

This language has an encoding of the booleans as the type $\mathsf{daisy}$, with $\mathsf{cat}$ and $\mathsf{dog}$ as the constructors and $\mathsf{cheese}$ as the destructor. The type $\mathsf{boolean}$ is not a boolean type: it's just some type that happens to have two values (which are undistinguishable).

A “typed lambda calculus with booleans [without] that conditional operator” is a Turing-complete language that doesn't have booleans.

¹  A destructor in a typed calculus is a term such that a type constructor appears in the premises of its typing rules but not in the type of its conclusion. If/then/else is a destructor for booleans.


Does a problem stay NP-hard when an additional constraint is added to it?

For general $f$ you can't conclude that $P$ is NP-hard just from the fact that $P'$ is NP-hard. In order to do so, you would need to come up with a reduction from $P'$ to $P$. For such a reduction to work, you would need that for every value of $A$ there be a value of $B$ such that the two systems of constraints are equivalent. Unfortunately this is not the case.


Closed form solution of $T(n) = 5T(n-1) + n^2$

How to find the closed form solution of this equation?

This is linear nonhomogeneous recurrence relation of the form $a_n = a_n^{h}+a_n^{p}$ where former expression in the right hand side is homogeneous solution while later one particular. Now, $a_n^p$ becomes $p_2n^2+p_1n+p_0$ whereas $a_n^h$ becomes $\alpha5^n$. Now solve them.

Another straightforward approach is to recursively solve the equation as follows
$$\begin{align*}
T(n) &= 5\cdot T(n-1)+n^2 \\
     &= 5[5\cdot T(n-2)+(n-1)^2]+n^2 \\
     &= 5^2T(n-2)+5(n-1)^2 + n^2 \\
     &= 5^3T(n-3)+5^2(n-2)^2 + 5(n-1)^2 + n^2 \\
     & \vdots\\
     &= \sum_{k=0}^{n-1}5^{n-k}\cdot k^2
\end{align*}$$

  Is there a repeatable pattern for solving this equation?

The very word recurrence implies pattern.


Printing all paths of a tree and sorting the weight of edges

You can't do better than $\Omega(n^3)$ running time.

In a tree, there is a path between every pair of vertices, so there are $\Theta(n^2)$ paths.  The average path length can be $\Theta(n)$.  So the total length of the output can be $\Theta(n^3)$.  Obviously, no algorithm can run faster than that, since it takes at least $\Theta(n^3)$ time just to write out the output.


I managed to find an official github repository, and they use a padding of size 3, and therefore the output 112.


Brandes' betweenness algorithm for weighted undirected graph

Note: I assume that the OP is talking about Algorithm 1 in the paper "A Faster Algorithm for Betweenness Centrality" By Ulrik Brandes.

You probably have noticed that Algorithm 1 in the paper is for unweighted graphs. In this case, Dijkstra's algorithm@wiki amounts to BFS and a shortest path for a vertex $v$ is found immediately when $v$ is first encountered (in the pseudo-code, it is represented by if d[w] < 0 then). This property is due to the layer-by-layer search feature of BFS.

  $Q_1:$ If a node is the first occurrence , then we have to check d[neighbor_node] < 0. However, if not, do we have to check d[neighbor_node] > d[current] + length(current,neighbor_node)?

For weighted graphs,  the property mentioned above does not necessarily hold. So you need to replace (meaning the following is not needed any more) the if d[w] < 0 then predicate by a slightly involved one suitable for weighted graphs:

          [foreach] neighbor w of v [do] [if] d[v] + length(w,v) < d[w] [then]

Note that for weighted graph, you should use a priority queue.

  $Q_2:$ If greater, then do I have to delete previous updates like Queue, Pre[] and others?

No. You set d[], P[], sigma[] only when a shortest path is found. It is valid all the time once it is set. No need to update them later.


Proving a value is the result of the execution of an algorithm

This is known as verifiable computing or verified computation.  There are many protocols for verified computation, with different properties.  Some of them rely upon special hardware (e.g., SGX).  Many of them don't rely on special hardware and use cryptography.  Among the cryptographic solutions, there are some protocols that can be used with any program (but are potentially inefficient), and some that can only be used for specific programs or types of computations (but are much more efficient).

There's an entire line of research papers on the subject, and it is too broad to summarize in a single paragraph or two.  I suggest reading about interactive proofs, and about the Pepper, Ginger, Zaatar, Pinocchio, Pantry, and Truebit systems, among others.  I also recommend reading the following survey paper for an overview of cryptographic solutions that can handle general computation:

Verifying computations without reexecuting them, Michael Walfish, Andrew J. Blumberg, CACM 58(2), February 2015.

In practice, I suspect that the SGX-based schemes or Truebit are likely to be the most practical for general computation at the moment, though the research literature is progressing rapidly and this could change in the future.  For specific computations, it is sometimes possible to design a custom protocol that does much better, but that depends on the particular computation.


Search problem when the effects of actions are not deterministic

One helpful way to think of this is as a two-party game.  When it is Alice's turn, she chooses an action; then, Bob chooses among the possible states that the action could return, and the system transitions to that state.  We start at the start state $A$.   Alice wins if she eventually reaches the goal state $Z$.  Bob is trying to prevent Alice from ever reaching $Z$.

With this viewpoint in mind, there's a straightforward algorithm to determine whether Alice has a strategy to win this game.  Let $S$ denote the set of all possible states.  If $R \subseteq S$ is a set of states, define $f(R)$ to be the set of states $s$ such that there exists an action $a$ so that every state $t$ that could be returned by action $a$ (applied to $s$) satisfies $t \in R$.  Also let $R_0 = \{Z\}$.  Now compute the following sequence:

$$\begin{align*}
R_1 &= R_0 \cup f(R_0)\\
R_2 &= R_1 \cup f(R_1)\\
R_3 &= R_2 \cup f(R_2)\\
&\vdots
\end{align*}$$

Iterate until you reach a fixpoint, i.e., $R_{i+1}=R_i$.  Then $R_i$ is the set of states that can reach $Z$: for every $s \in R_i$, there exists a strategy that Alice can use to ensure she will reach the goal state $Z$.  So, we can simply check whether $A$ is in $R_i$ or not.

You can make the running time of this algorithm linear, by a simple trick.  Store the set $R_i$ explicitly in memory.  Also, you maintain a separate data structure for "the fringe": the set of states that can reach $R_i$ in a single step.  For each state $s$ in the fringe and each action $a$ available on $s$, you maintain a counter that counts how many of the possible results of applying $a$ to $s$ will take you to the current set $R_i$.  On each iteration, you can compute $R_{i+1}$ and update all of the counters.  Each counter only decreases; it never increases.  Also, a state $s$ is in $f(R_i)$ just when one of the actions available on $s$ has a counter that has decreased to zero, so computing $f(R_i)$ is just a matter of scanning the fringe and finding the counters that have hit zero; then you compute $R_{i+1}$, update the fringe, and update the affected counters.  The running time of this algorithm is linear in the size of "the graph", i.e., in the number of states plus the number of transitions (triples of state $s$, action $a$ available on $s$, and state $t$ that could be returned by this action).

However, this straightforward algorithm is not very memory-efficient: it requires explicitly storing a large set of states.  Also it requires enumerating the statespace, or a large part of the statespace.  Therefore, it might be sufficient for small systems, but for large systems it might not be attractive.

For larger systems, you might want to consult the model checking literature to see if there are better solutions.

For example, I suspect you might want to look at Alternating-time Temporal Logic (ATL), in the model checking literature.  It deals with search problems for two-party games.  I think I recall that there are model-checking algorithms for solving problems associated with these kinds of two-party games, but I'm not certain about that.

(Incidentally: another way to think about your problem is that the possible results from each action correspond to non-deterministic choices, and there is an adversary (Bob) who is resolving all non-determinism in the worst possible way.)


Why are we interested in square-free words?

Well, take a moment to reflect. Is a word or a string one of the most important and most common entities in this world? What are the most basic properties of a word or string?

its alphabet
its length
its sound
its meaning
its syntax or grammar
its origin
its usage as how to form sentences.
hmm, does it repeat part of itself? Or never (square-free)?

It looks like the property of being square-free is almost a fundamental property of a word (or a phrase, or a sentence).

In fact, it is amazing to me that the formal study of square-free words has not made it way into most of textbooks about the theory of automata and computation. It appears that the study of square-free words turns out to be a rather isolated field with less impact.

Nevertheless, the study of square-free words and related concepts is interesting and fruitful, as you have observed. I am, for one, charmed by the square-free words of infinite length over three letters 1.

"Real-life" application related to square-free words are sparse indeed. Abelian square-free words in algorithmic music by Laakso, T. might count as one; however, I cannot find that paper. (Gefwert, C., Orponen, P., Seppänen, J. (eds.) Logic, Mathematics and the Computer, vol. 14, pp. 292–297. Finnish Artificial Intelligence Society, Symposiosarja, Hakapaino, Helsinki).

Here are two related exercise to entertain your mind.

An abelian square is a subsequence of the form $s_1s_2$ where $s_2$ is a permutation of $s_1$. For example, $abcbac$ is an abelian square since $bac$ is a permutation of $abc$.

Exercise 1. (easy) Let the alphabet consist of 3 letters. Show a word of length 7 that is free of abelian square. Show that every word of length eight contains an abelian square.

Exercise 2. (very very hard) There is an infinite abelian-square-free word over an alphabet of size four.


Using the appropriate machine learning algorithm

There are not an appropiate algorithm for each problem, you must to research and compare results between your algorithms or techniques with an error measure (MSE, etc.).

In general, machine learning algorithms are empiric models (approximated functions). There are arised from the problem itself and a set of suppositions with no revealing the hidden model (many of them, are non-linear problems).

First of all, is necessary to be careful with the variables in the input and output layer, this can be categorical, symbolic or numeric (best case), and you have to model your own representation to preserve some features of interest (topology, etc.)

I will recommend you first of all, try with a multiple linear regression and explore the eventual correlations between variables to find any linear dependence, before do something.

Its a very good practice, normalize the numerical data in the training process, to get a well fitted bias.

Then, for instance, you could try with a multilayer feed forward neural network or SVD o fuzzy inference system.

I understand the machine learning problem as a research with a set of methods to get a good explanation for a given problem, and improvements on that methods.


Classical resources: CLRS Introduction to Algorithms, 3d edition, pages 47, 1150,  Donald Ervin Knuth TAOCP, 1997, volume 1, page 107.
More formal good resource for such cheatsheet you can find  in Jeremy Avigad and Kevin Donnelly article.
And, at end, for non negative case, let me bring some well known properties:
$$ \begin{array}{l}O(f ) + O(g) = O(f + g) =O(\max(f,g))\\
C=Const. \Rightarrow C\cdot O(f) = O(C \cdot f) = O(f) \\
 O(f )  O(g) = O(f g) \\
O( O( f)) = O(f ) \\
 g \ne 0 \Rightarrow \frac{O(f)}{g} = O\left(\frac{f}{g}\right)
\end{array}
$$
For your case: $f \in \frac{\Theta(n)}{o(n)}$, if an only if $\lim\limits_{n \to \infty}f(n)=\infty$.


Most graph libraries will find the connected components of a graph G as a list of connected subgraphs [H1, H2, H3, ...] and most of these libraries will have the functionality to obtain the number of nodes and number of edges in a graph. Assuming H is a simple graph (no loops, no multiple edges) with m edges and n vertices, one can say it is complete if

m == n*(n-1)/2

So, given the output of connected components, you should do:

for each graph H in [H1, H2, ...]
  int n = H.getNumVertices()
  int m = H.getNumEdges()
  if (n*(n-1) == 2*m)
    state that H is complete
  else
    state that H is not complete


Let $T$ be the set of all Turing machines.

Let $B = \{ (e,x, y) \in T \times \{0,1\}^* \times \mathbb{N} : e(x) \text{ halts in $y$ steps}\}$, and define $C = \{e \in T : \forall x \in \{0,1\}^*, \; \exists y \in \mathbb{N}, \; (e, x, y) \in B]$.

We start by proving $\text{TOT}=C$.

If $e \in \text{TOT}$ then, $\forall x \in \{0,1\}^*$, $e(x)$ halts. Let $y_x$ be the number of steps needed for $e(x)$ to halt. Then $ \forall x \in \{0,1\}^*$ there is a choice of $y \in \mathbb{N}$, namely $y = y_x$, such that $(e,x,y) \in B$, showing that $e \in C$ and hence $\text{TOT} \subseteq C$.

If $e \not\in \text{TOT}$, then $\exists x \in \{0,1\}^*$ such that $e(x)$ does not halt. Then $\exists x$, such that $\forall y \in \mathbb{N}$, $(e, x, y) \not\in B$, showing that if is false that $\forall x \in \{0,1\}^*, \exists y \in \mathbb{N}$ such that $(e, x, y) \in B$. As a consequence $e \not\in C$ implying $\text{TOT} \supseteq C$.

It remains to show that $B$ is computable.
To decide whether any given triple $(e, x,y) \in T \times \{0,1\}^* \times \mathbb{N}$ belongs to $B$  it suffices to consider a Turing machine $T'$ that simulates $e(x)$ for $y$ steps. If $e(x)$ halts, then $T'$ accepts. Otherwise, if $e(x)$ does not halt by the end of the $y$-th step, $T'$ rejects.


Algorithm to construct a parabola that hits a given target and avoids given boundaries

Consider an endpoint $(x_E,y_E)$  of an obstacle line segment.  I'm going to assume for simplicity that if the projectile goes exactly through $(x_E,y_E)$, this is a legal trajectory, i.e., it's OK for a projectile to "just graze" the obstacle.  (If that's not OK, it is easy to adjust the solution below to just miss the corner by a tiny amount $\epsilon$, or it is easy to adjust the size of each obstacle by $\epsilon$ in each direction.)
Let's define a "grazing constraint" as one of the following possibilities:

If the point $E$ is a vertex of an obstacle (i.e., an endpoint of an obstacle line segment) or is $R$ or $S$, then "The parabola must go through $E$" is a grazing constraint.

If $EF$ is an obstacle line segment, then "The parabola intersects $EF$ and is tangent to it" is a grazing constraint.

In this way, given $n$ obstacle line segments, we obtain $2n+2$ possible grazing constraints.
Now I make two claims:
Claim 1: Any two grazing constraints uniquely determine the parabola.
Proof: If both grazing constraints are of the "must go through E" type, then together with the target $T$, we have three points, and any three points uniquely define a parabola, i.e., given three points, there is a unique parabola that goes through those three points.  A similar argument can be made if one or both of the grazing constraints are of the "tangent" type.
Claim 2: If there is any solution to your problem, there is a solution that satisfies two of the possible grazing constraints listed above.
(I don't have a proof for this claim.)
This immediately suggests a simple algorithm: enumerate over all pairs of grazing constraints, find the unique parabola that satisfies those two grazing constraints and goes through the target $T$, and check whether this parabola avoids all obstacles and intersects the starting line segment RS.  You can check whether it avoids all obstacles by iterating over all obstacle line segments, and for each, finding the intersection using the method you described.  If there is a valid solution to your problem, this method will find it.
The running time of this method will be something like $O(n^3)$, where $n$ is the number of obstacle line segments.  I don't know if there is a more efficient method.  There might well be.